Без відповідей (роздатка учню) ← До сторінки

Складність алгоритмів: час, пам’ять, O(n), O(n²)

Підказка

Що вивчимо. Як порівнювати алгоритми за кількістю операцій і чому важливо, як швидко зростає час при збільшенні даних.

Навіщо

Два алгоритми дають однакову відповідь, але один працює 1 секунду, а другий — рік. Складність показує, як росте час зі збільшенням обсягу даних n.

Означення

Складність алгоритму — залежність кількості виконуваних операцій (часова) або обсягу пам’яті (просторова) від розміру вхідних даних n.

Позначення O

O

Назва

Приклад

n = 1000

O(1)

стала

доступ до елемента за індексом

1

O(log n)

логарифмічна

бінарний пошук

10

O(n)

лінійна

пошук максимуму, сума

1 000

O(n log n)

вбудоване сортування

10 000

O(n²)

квадратична

сортування обміном

1 000 000

O(2ⁿ)

експоненціальна

перебір усіх підмножин

неможливо

Стала відкидається: 5n і 100n — обидва O(n). Важливий вигляд росту.

Як рахувати

  • Один цикл по n — O(n).

  • Цикл у циклі — O(n²).

  • Цикл, що ділить область навпіл, — O(log n).

  • Послідовні блоки додаються, береться найбільший.

for i in range(n):          # n разів
    for j in range(n):      # n разів
        print(i, j)         # O(n²)

Експеримент

Відкрийте лабораторію «Складність алгоритмів» нижче: вона порівнює кількість операцій у різних алгоритмів для різних n. Збільшіть n у 10 разів і дивіться, у скільки разів зросло навантаження.

Приклад

Якщо один крок = 1 мікросекунда, то для n = 1 000 000: O(n) — 1 секунда; O(n log n) — 20 секунд; O(n²) — 11 діб!

Складність за пам’яттю

Масив на n чисел — O(n) пам’яті. Сортування «на місці» — O(1) додаткової пам’яті.

Перевірте себе

  1. Яка складність пошуку максимуму? Бінарного пошуку?

  2. У скільки разів збільшиться час алгоритму O(n²), якщо n зросте втричі?

  3. Чому сталі множники відкидають?

BitMath · https://bitmath.com.ua/informatyka/informatyka-9-tema-7/i9-skladnist-alhorytmiv