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

Що таке алгоритми?

Алгоритм — це кінцева, однозначна послідовність інструкцій, яка вирішує проблему. Вивчення алгоритмів досліджує правильність (чи дає воно правильну відповідь?) та ефективність (скільки часу та пам’яті потрібно?). Структури даних організовують дані так, щоб алгоритми могли працювати ефективно. Разом вони є основою комп'ютерної науки.

Класи Big-O

Частотність та складність простору

Велике-О позначення описує граничну верхню межу на час виконання як функцію від розміру вхідних даних n, ігноруючи константи та доданки нижчого порядку. Формально: f(n) = O(g(n)) якщо існує c і n₀ таке, що f(n) ≤ c·g(n) для всіх n ≥ n₀.

Практичне значення: алгоритм O(n²) на n = 10⁶ потребує приблизно 10¹² операцій. Алгоритм O(n log n) потребує лише приблизно 2×10⁷ — різниця в 50 000 разів. Вибір алгоритму домінує над швидкістю апаратного забезпечення. Жодна кількість обладнання не робить алгоритму O(n!) здійсненним для великих n. Велике-Огма (Ω) надає нижні межі; Велике-Тета (Θ) надає точні межі.

Сортування алгоритмів

Python використовує Timsort (гібридний злитий + сортування вставками). C++ STL використовує Introsort (гібридний швидке сортування + херсорт + сортування вставками). Для майже відсортованих даних, сортування вставками виграє. Злитий алгоритм сортування коли потрібна стабільність. Херсорт для гарантованого O(n log n) за O(1) простору.

Двохетапний пошук та метод поділу на частини

Двохетапний пошук знаходить елемент у відсоркованому масиві за часом O(log n): порівняйте з серединою; рекурсивно обробляйте відповідну половину. Достатньо 20 порівнянь для 10^6 елементів.

Метод поділу на частини: (1) розділіть на підзадачі; (2) розв’язуйте рекурсивно; (3) об’єднайте. Рекурентне співвідношення T(n) = 2T(n/2) + O(n) вирішується до O(n log n) за допомогою теореми Мартіна. Приклади: FFT O(n log n), множення Каратуби O(n^1,585), матричне множення Страссен O(n^2,81).

Алгоритми графів

Графи G=(V,E) моделюють зв’язки. Більшість реальних проблем маршрутизації, планування та мереж спрощуються до задач з графами.

BFS — Пошук у ширину

O(V+E). Відвідує всіх сусідів першими; використовує чергу. Знаходить найкоротший шлях (у незважених графах). Використовується в веб-крашторах, відстанях соціальних мереж, заповненні потоків.

DFS — Пошук у глибину

O(V+E). Досліджує якнайглибше першим; використовує стек/рекурсію. Використовується в топологічному сортуванні, виявленні циклів, SCCs, розв’язанні лабіринтів.

Алгоритм Дейкстри

O((V+E) log V) з чергою пріоритетів. Найкоротший шлях від одного джерела в невід'ємно ваговому графі. Використовується в навігації GPS та маршрутизації OSPF.

Bellman-Ford

O(VE). Обробляє ребра з від’ємною вагою та виявляє негативні цикли. Використовується в маршрутизації BGP інтернету.

Floyd-Warshall (all-pairs shortest paths): O(V^3) for k in 1..V: for i in 1..V: for j in 1..V: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) Minimum Spanning Tree: Kruskal's: O(E log E) - sort edges, add if no cycle (union-find) Prim's: O((V+E) log V) - grow MST from a seed vertex

Динамічне програмування

Динамічне програмування (DP) вирішує задачі оптимізації, розбиваючи їх на перекриваючіся підзадачі та зберігаючи рішення для запобігання повторному обчисленню. Два підходи:

Мемоізація (top-down): рекурсивно розв’язує, кешує результати (наприклад, Фібоначчі з мемоізацією: O(n) замість O(2^n)).

Табуляція (bottom-up): заповнює таблицю від найменших підзадач догори; унеможливлює ризик переповнення стеку.

Classic DP problems: Fibonacci: F(n) = F(n-1) + F(n-2) O(n) time, O(n) space 0/1 Knapsack: dp[i][w] = max(dp[i-1][w], v_i + dp[i-1][w-w_i]) O(nW) Longest Common dp[i][j] = dp[i-1][j-1]+1 (match) Subsequence: = max(dp[i-1][j], dp[i][j-1]) (no match) Edit Distance: dp[i][j] = min(insert, delete, replace) Coin Change: dp[i] = min dp[i-c] + 1 for each coin c

Жадібні алгоритми

Жадібні алгоритми роблять локально оптимальний вибір на кожному кроці, сподіваючись досягти глобального оптимуму. Вони простіші та швидші за DP, але працюють лише для певних структур задач.

Правильно працює жадібний: Алгоритм Крускалу для знаходження мінімального покриваючого дерева, алгоритм Прима для знаходження мінімального покриваючого дерева, алгоритм Дейкстри (з від’ємними вагами), кодування Хаффмана (оптимальні префіксні коди), планування інтервалів (вибирайте за раннім часом завершення).

Неправильно працює жадібний: Задача 0/1 типу рюкзака (фрагментарна версія розв’язується жадібно; цілочисельна не є), найкоротший шлях з від’ємними ребрами, створення змішаного капіталу з будь-якої системи монет.

Неповність NP

Запитання P проти NP є центральною невирішеною проблемою в галузі інформатики. Визначення:

P: рішення задач, які можна розв’язати за поліноміальний час.

NP: рішення задач, для яких їхні розв’язки можуть бути перевірені за поліноміальний час (але не обов’язково за поліноміальний час).

NP-повне: задачі, які належать до NP і для яких кожна задача NP може бути зведена до них за поліноміальний час.

NP-складне: задачі, принаймні так само складні, як NP-повні задачі; не обов’язково належать до NP.

Відомі NP-повні задачі: Логічна задовольняючаність (SAT), Задача про туристичний маршрут (TSP), Розфарбування графа, Гамільтонів шлях, Підмножина суми, Рюкзак. Якщо P = NP, то всі ці задачі матимуть розв’язки за поліноміальний час — більшість криптографічної безпеки руйнується. Більшість дослідників у галузі складності вважають, що P ≠ NP, але питання залишається відкритим (Мільйонний проблемний фонд, приз $1 мільйона).

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Hash Function Avalanche Visualizer і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.