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

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

Підказка

Що вивчимо. Що таке складність алгоритму, як вона залежить від n і чому важливо обирати ефективний алгоритм.

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

Означення

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

Нас цікавить не секунди на певному комп’ютері, а те, як швидко зростає кількість операцій із збільшенням 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

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

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

  • O(n) — у 10 разів довше;

  • O(n²) — у 100 разів довше;

  • O(log n) — майже нічого.

Приклад

Сортування 1 000 000 чисел бульбашкою — порядку 10¹² операцій (години), а вбудованим методом — близько 2·10⁷ (частки секунди).

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

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

Емулятор

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

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

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

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

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

BitMath · https://bitmath.com.ua/informatyka/informatyka-8-tema-7/i8-skladnist