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

Складність алгоритмів: кількість операцій, O(n), O(log n), O(n²)

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

Складність алгоритму

Нас цікавить не секунди на певному комп’ютері, а те, як швидко зростає кількість операцій із збільшенням n.

Типові класи

Запис

Назва

Приклад

n = 1000

O(1)

константна

доступ до a[i]

1

O(log n)

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

двійковий пошук

≈ 10

O(n)

лінійна

лінійний пошук, сума

1000

O(n log n)

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

≈ 10 000

O(n²)

квадратична

бульбашка, вибір, вставки

1 000 000

Що це означає на практиці

Якщо дані збільшити вдесятеро:

Просторова складність

Окрім часу, алгоритм потребує пам’яті. Іноді можна «купити» швидкість за пам’ять (наприклад, словник для швидкого пошуку).

Емулятор

У лабораторії нижче порівняйте кількість операцій для різних алгоритмів і подивіться, як вони ростуть із n (також у логарифмічному масштабі).

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

  1. У скільки разів зросте кількість операцій O(n²) при збільшенні n у 3 рази?

  2. Чому двійковий пошук швидший за лінійний?

  3. Для яких n різниця між O(n) і O(n²) непомітна?

Практика

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

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