Стратегія «розділяй та володарюй»

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

Стратегія «розділяй та володарюй» (divide and conquer) — це підхід до побудови алгоритмів, коли задачу розбивають на кілька менших підзадач того самого типу, розвʼязують їх, а потім обʼєднують результати. На іспиті перевіряють розуміння самої ідеї, вміння впізнати її в класичних алгоритмах (бінарний пошук, швидке та злиттєве сортування) й оцінити складність таких алгоритмів.

📖 Головне

• Три кроки стратегії: Розділяй (поділити задачу на підзадачі), Володарюй (розвʼязати підзадачі, зазвичай рекурсивно), Обʼєднуй (скласти з часткових розвʼязків загальну відповідь).

• Базовий випадок — настільки мала підзадача, що її розвʼязують напряму, без подальшого поділу. Без нього рекурсія не зупиниться.

• Рекурсія — природний інструмент реалізації: функція викликає сама себе для менших частин.

• Бінарний пошук: у впорядкованому масиві щоразу беремо середину й відкидаємо половину. Складність O(log n).

• Сортування злиттям (merge sort): масив ділять навпіл, кожну половину сортують рекурсивно, потім зливають. Складність O(n·log n), стабільне.

• Швидке сортування (quick sort): обирають опорний елемент (pivot), розбивають масив на менші й більші за нього, рекурсивно сортують частини. У середньому O(n·log n), у гіршому O(n²).

• Перевага підходу — зменшення складності порівняно з «наївним» перебором (напр. O(log n) замість O(n) при пошуку).

• Загальна оцінка: якщо задачу ділять на частини й на кожному рівні роблять O(n) роботи, а рівнів log n, разом виходить O(n·log n).

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

Бінарний пошук числа 23 у масиві [2, 5, 8, 12, 16, 23, 38, 56, 72]:

• Крок 1: середина — елемент з індексом 4 (значення 16). 23 > 16 → шукаємо у правій половині [23, 38, 56, 72].

• Крок 2: середина правої частини — 56 (або 38 залежно від округлення). 23 < 56 → ліва підчастина [23, 38].

• Крок 3: середина — 23. Знайдено!

За 3 порівняння замість 9 при лінійному пошуку. Для n елементів потрібно приблизно log₂n кроків.

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

• Плутають «розділяй та володарюй» з динамічним програмуванням: у динамічному підзадачі перекриваються й результати зберігають, тут — зазвичай незалежні.

• Забувають про базовий випадок — рекурсія стає нескінченною.

• Вважають, що бінарний пошук працює на будь-якому масиві; він вимагає ВПОРЯДКОВАНОГО масиву.

• Плутають складність merge sort і quick sort у гіршому випадку: merge завжди O(n·log n), quick може деградувати до O(n²).

• Думають, що поділ сам по собі прискорює; виграш дає саме відкидання/незалежна обробка частин.

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

• Три кроки: розділяй → володарюй → обʼєднуй.

• Бінарний пошук — O(log n), потрібен відсортований масив.

• Merge sort — O(n·log n) завжди.

• Quick sort — O(n·log n) у середньому, O(n²) у гіршому.

• Обовʼязкова наявність базового випадку рекурсії.

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

1. Які три кроки лежать в основі стратегії «розділяй та володарюй»?

2. Яка умова обовʼязкова для роботи бінарного пошуку?

3. Чому merge sort надійніший за quick sort за складністю в гіршому випадку?

4. Що станеться з рекурсивним алгоритмом без базового випадку?

Відповіді: 1 — розділяй (поділ на підзадачі), володарюй (розвʼязання, часто рекурсивно), обʼєднуй (складання результату); 2 — масив має бути впорядкованим; 3 — merge sort завжди дає O(n·log n), а quick sort у гіршому випадку деградує до O(n²); 4 — рекурсія не зупиниться (нескінченний виклик, переповнення стека).