ПоглибленийІнформатика

Алгоритми та структури даних

Сортування, пошук, рекурсія, складність алгоритмів, структури даних.

Навіщо вивчати алгоритми?

Алгоритми — основа програмування. Вони визначають, наскільки швидко працюватиме програма. ⚡ Приклад: Пошук у відсортованому списку з 1 мільярда елементів: • Простий пошук: до 1 млрд операцій (роки!) • Бінарний пошук: до 30 операцій (мілісекунди!) 🏆 Різниця в мільйони разів!

Big O — складність алгоритмів

Big O показує, як зростає час виконання зі збільшенням даних:

✅ O(1) — константна: доступ до елемента за індексом
✅ O(log n) — логарифмічна: бінарний пошук
⚠️ O(n) — лінійна: звичайний пошук
⚠️ O(n log n) — хороші алгоритми сортування
❌ O(n²) — погані сортування (бульбашкове)
💀 O(2ⁿ) — експоненціальна: дуже повільно!

Бінарний пошук

Приклад

🔍 Алгоритм "поділяй і володарюй": Задача: Знайти число 7 у списку [1, 3, 5, 7, 9, 11, 13] 1️⃣ Середина = 7. Знайшли! Задача: Знайти число 3 1️⃣ Середина = 7. 3 < 7, шукаємо зліва. 2️⃣ Середина = 3. Знайшли! 📊 Для 1 мільярда елементів потрібно лише ~30 порівнянь!

💡 Історія: Алгоритм Google PageRank

💡

🔍 Google став №1 завдяки алгоритму! У 1998 році студенти Стенфорда Ларрі Пейдж і Сергій Брін винайшли PageRank — алгоритм ранжування веб-сторінок. 💡 Ідея: Чим більше сайтів посилаються на сторінку, тим вона важливіша. 🏆 Результат: Google став найпопулярнішою пошуковою системою, а Пейдж і Брін — мільярдерами! Назва "Google" — помилка написання "googol" (число 10¹⁰⁰).

Основні структури даних

📋 Масив (Array): елементи з індексами [0], [1], [2]...
🔗 Зв'язаний список (Linked List): елементи з посиланнями
📚 Стек (Stack): LIFO — останній зайшов, перший вийшов
🚶 Черга (Queue): FIFO — перший зайшов, перший вийшов
🌳 Дерево (Tree): ієрархічна структура
🗺️ Хеш-таблиця (Hash Table): швидкий пошук за ключем

🗺️ Задача комівояжера

💡

Одна з найвідоміших класичних задач інформатики: "У вас є N міст і відстані між ними. Як відвідати всі міста по одному разу і повернутися додому найкоротшим шляхом?" Звучить просто? Але для 60 міст кількість варіантів маршрутів більша, ніж атомів у Всесвіті! Її неможливо вирішити простим перебором, тому використовують евристичні алгоритми.

❓ Загадка тисячоліття: P vs NP

💡

Найбільша нерозв'язана проблема сучасної математики та інформатики, за вирішення якої інститут Клея пропонує $1,000,000. Суть: якщо ми можемо швидко перевірити рішення задачі (NP), чи можемо ми так само швидко знайти це рішення самостійно (P)? Якщо хтось доведе, що P = NP, це переверне наш світ кібербезпеки та біології!

Оцінка складності: Нотація "О-велике" (Big O)

Якщо алгоритм працює добре для 10 елементів, чи спрацює він для мільярда? О-велике показує, як зростає час роботи алгоритму зі збільшенням даних (n). • O(1) — миттєво (взяти першу книгу з полиці). • O(n) — лінійно (переглянути всі книги по черзі). • O(n²) — жахливо повільно (порівняти кожну книгу з кожною іншою). Хороший програміст вміє оптимізувати алгоритм з O(n²) до O(n log n).

Алгоритми сортування

Як комп'ютер впорядковує списки (від А до Я)? Це досі активна сфера досліджень!

Сортування бульбашкою (Bubble Sort): найпростіший, але найповільніший. Важкі елементи "спливають" у кінець списку. Складність O(n²).
Швидке сортування (Quick Sort): вибирає "опорний" елемент і розділяє масив на менші і більші. Працює в сотні разів швидше. Складність O(n log n).
Сортування злиттям (Merge Sort): ділить список навпіл, поки не залишаться по 1 елементу, а потім правильно "зшиває" їх назад. Стабільний і надійний.

Бінарний пошук: магія O(log n)

Приклад

Вам потрібно знайти слово "Програма" у словнику на 1000 сторінок. Ви відкриваєте його чітко посередині. Літера "М". Оскільки "П" далі за алфавітом, ви ВІДКИДАЄТЕ першу половину книги (500 сторінок)! Далі відкриваєте посередині другої половини... і так далі. Завдяки бінарному пошуку, щоб знайти слово серед 1 000 000 записів, комп'ютеру знадобиться всього лише 20 кроків, а не мільйон!