Базові алгоритми пошуку та сортування і їх складність

📌 Про що ця тема

Тут перевіряють, чи вмієш ти відрізняти базові алгоритми пошуку (лінійний, двійковий) і сортування (бульбашкове, вибором, вставками) та оцінювати їхню ефективність через обчислювальну складність. Ключове поняття — складність алгоритму, яку записують у «О-нотації» (O-велике).

📖 Головне

• Обчислювальна складність показує, як швидко зростає кількість операцій алгоритму зі збільшенням обсягу даних n. Записують як O(…) — оцінка при великих n.

• Лінійний (послідовний) пошук: перевіряємо елементи по черзі, поки не знайдемо потрібний. Працює на будь-якому масиві. Складність O(n).

• Двійковий (бінарний) пошук: працює ТІЛЬКИ на відсортованому масиві. Беремо середній елемент, порівнюємо з шуканим і відкидаємо половину масиву. Складність O(log n) — дуже швидко.

• Сортування бульбашкове: сусідні елементи порівнюються й міняються місцями, якщо стоять неправильно; за кожен прохід найбільший «спливає» в кінець. Складність O(n²).

• Сортування вибором: шукаємо мінімальний елемент і ставимо його на перше місце, потім серед решти — знову мінімум, і т.д. Складність O(n²).

• Сортування вставками: беремо наступний елемент і «вставляємо» його на правильне місце серед уже впорядкованих зліва. Складність O(n²), але швидке на майже відсортованих даних.

• Порядок зростання швидкості: O(1) < O(log n) < O(n) < O(n·log n) < O(n²).

• Висновок: двійковий пошук значно швидший за лінійний, але потребує попереднього сортування.

🔢 Як це працює на прикладі

Двійковий пошук числа 7 у масиві [1,3,5,7,9,11]: 6 елементів.

Крок 1: середина — між 5 і 7, беремо індекс 2 (значення 5). 7 > 5 → шукаємо в правій половині [7,9,11].

Крок 2: середина цієї частини — 9. 7 < 9 → ліва частина [7].

Крок 3: залишився 7 — знайдено. Усього 3 порівняння замість 4 при лінійному пошуку. Для масиву з 1000 елементів двійковий дасть ≈10 кроків (log₂1000≈10), а лінійний — до 1000.

⚠️ Типові помилки

• Застосовують двійковий пошук до невідсортованого масиву — він дасть неправильний результат.

• Плутають O(log n) і O(n): думають, що лінійний пошук такий самий швидкий, що й двійковий.

• Вважають, що складність залежить від конкретних чисел, а не від кількості елементів n.

• Плутають сортування вибором і бульбашкове: у вибором шукають мінімум і один раз переставляють, у бульбашковому багато обмінів сусідів.

• Забувають, що O(n²) означає: при подвоєнні n кількість операцій зростає приблизно вчетверо.

🎯 Що завчити напамʼять

• Лінійний пошук — O(n), двійковий — O(log n) (лише для відсортованих).

• Бульбашкове, вибором, вставками — усі O(n²).

• Шкала зростання: O(1) < O(log n) < O(n) < O(n·log n) < O(n²).

• Двійковий пошук щоразу відкидає половину елементів.

🧠 Перевір себе

1. Яка складність лінійного пошуку?

2. Чи можна застосувати двійковий пошук до невідсортованого масиву?

3. Яка складність у бульбашкового сортування?

4. Що швидше при великих n: O(n) чи O(log n)?

Відповіді: 1 — O(n); 2 — ні, масив має бути відсортованим; 3 — O(n²); 4 — O(log n).