Побудувати таблиці, які демонструють залежність часу роботи алгоритмів з різними функціями часової складності від розміру вхідних даних. 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 разів.
Ответы
Ответ:
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 для обох функцій часової складності.