Перейти до змісту

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

▶ Слайди Друк / PDF

Навіщо

Два алгоритми дають однакову відповідь, але один працює 1 секунду, а другий — рік. Складність показує, як росте час зі збільшенням обсягу даних 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). Важливий вигляд росту.

Як рахувати

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

Експеримент

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

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

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

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

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

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

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

Практика

Складність алгоритмів: графіки зростання кількості операцій окрема сторінка

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