Question

Побудувати таблиці, які демонструють залежність часу роботи алгоритмів з різними функціями часової складності від розміру вхідних даних. 1. Нехай для розміру n вхідних даних час роботи алгоритму дорівнює f(n) мікросекунд. Побудувати електронну таблицю для визначення часу роботи алгоритму (в секундах), для розмірів вхідних даних 10, 20, ..., 200 (константу для переведення мікросекунд у секунди запишіть у комірку A1, після чого використовуйте абсолютне посилання на цю комірку).
f1(n) = n^1/2
f2(n) = 2^n
2. Користуючись побудованою у завданні 1 таблицею, для кожної з функцій f1(n) і f2(n) визначте максимальне значення n, для яких задача може бути розв'язана за час t, якщо t = 1 сек, 1 хв, 1 год, 1 день, 1 місяць, 1 рік, 1 століття.
3. Користуючись у завданні 1 таблицею, визначте, як змінить масимальне значення n, для яких задача може бути розв'язана за 1 сек при збільшенні швидкодії у 100 разів, у 1000 разів.

Answer 1

Ответ:

1. Для побудови таблиці часу роботи алгоритмів з різними функціями часової складності від розміру вхідних даних, ми можемо модифікувати код, що був наведений вище, щоб він записував час роботи алгоритму у список для кожного розміру матриці. Потім ми можемо використовувати ці списки для створення електронної таблиці.

python

import random

import time

# створюємо функцію для знаходження суми чисел, які знаходяться вище головної діагоналі

def sum_above_diagonal(matrix):

    sum = 0

    for i in range(10):

        for j in range(i+1, 10):

            sum += matrix[i][j]

    return sum

# створюємо списки для збереження часу роботи алгоритму для кожного розміру матриці

f1_times = []

f2_times = []

for n in range(10, 201, 10):

    # створюємо двовимірний масив розмірністю n на n і заповнюємо його випадковими числами

    matrix = [[random.randint(0, 9) for j in range(n)] for i in range(n)]

    # знаходимо час роботи алгоритму для функції f1(n)

    start_time = time.time()

    sum_above_diagonal(matrix)

    end_time = time.time()

    f1_times.append(end_time - start_time)

    # знаходимо час роботи алгоритму для функції f2(n)

    start_time = time.time()

    # додатково збільшуємо розмір матриці для функції f2(n), щоб уникнути дуже маленьких значень часу

    sum_above_diagonal([[random.randint(0, 9) for j in range(n+10)] for i in range(n+10)])

    end_time = time.time()

    f2_times.append(end_time - start_time)

# виводимо списки часу роботи алгоритму на екран

print("f1(n) times:", f1_times)

print("f2(n) times:", f2_times)

Після запуску цього коду, ми отримаємо списки `f1_times` і `f2_times`, які містять час роботи алгоритму для кожного розміру матриці. Можна використовувати ці списки для створення електронної таблиці, наприклад у програмі Excel.

2. Для визначення максимального значення n, для якого задача може бути розв'язана за час t, ми можемо використовувати формулу часової складності алгоритму та підставляти різні значення n і t, щоб знайти найбільше значення n. Наприклад, для функції f1(n), формула часової складності є O(n^1/2), тому ми можемо записати:

n_max_t_1s = (1 / A1)**2

n_max_t_1min = (60 / A1)**2

n_max_t_1hour = (3600 / A1)**2

n_max_t_1day = (86400 / A1)**2

n_max_t_1month = (2592000 / A1)**2

n_max_t_1year = (31536000 / A1)**2

n_max_t_1century = (3153600000 / A1)**2

Аналогічно, для функції f2(n), формула часової складності є O(2^n), тому ми можемо записати:

n_max_t_1s = log2(1 / A1)

n_max_t_1min = log2(60 / A1)

n_max_t_1hour = log2(3600 / A1)

n_max_t_1day = log2(86400 / A1)

n_max_t_1month = log2(2592000 / A1)

n_max_t_1year = log2(31536000 / A1)

n_max_t_1century = log2(3153600000 / A1)

3. Щоб визначити, як зміниться максимальне значення n, для якого задача може бути розв'язана за 1 сек при збільшенні швидкодії у 100 разів або 1000 разів, ми можемо використовувати формули, які були наведені в попередньому пункті, і підставляти нові значення часу t. Наприклад, якщо швидкість збільшиться у 100 разів, то новий час роботи алгоритму буде 1/100 секунди, тому ми можемо записати:

n_max_new_speed_100x = (1 / (A1 * 100))**2

Аналогічно, для збільшення швидкодії у 1000 разів:

n_max_new_speed_1000x = (1 / (A1 * 1000))**2

Ці формули можна використовувати для обчислення нових максимальних значень n для обох функцій часової складності.