Довідник
Довідник складності алгоритмів
Часова та просторова складність за Big-O для кожної категорії алгоритмів, які застосовуються в симуляціях, з практичними нотатками про те, коли кожен з них важливий за інтерактивної частоти кадрів.
O(1) / O(log N)
O(N)
O(N log N)
O(N²)
O(N³)+ Уникайте для N>100 за 60fps
| Алгоритм | Категорія | Час (середній) | Час (найгірший) | Пам'ять | Нотатки |
|---|---|---|---|---|---|
| Quicksort | Сортування | O(N log N) | O(N²) | O(log N) | Найгірший випадок на відсортованих даних. На місці. Дружній до кешу. Стандартний вибір. |
| Merge Sort | Сортування | O(N log N) | O(N log N) | O(N) | Стабільне. Гарантоване O(N log N). Додаткова пам'ять = N. |
| Heapsort | Сортування | O(N log N) | O(N log N) | O(1) | На місці, але нестабільне. Погана поведінка з кешем. |
| Insertion Sort | Сортування | O(N²) | O(N²) | O(1) | Швидке для майже відсортованих N<50. Стабільне. Онлайн. |
| Counting Sort | Сортування | O(N+K) | O(N+K) | O(K) | K = діапазон значень. O(N), коли K ≈ N. |
| Radix Sort | Сортування | O(d·N) | O(d·N) | O(N+K) | d = розрядність. Стабільне. Застосовується в GPU-сортуванні частинок. |
| Binary Search | Пошук | O(log N) | O(log N) | O(1) | Потрібен відсортований масив. 1М елементів → 20 порівнянь. |
| Hash Table Lookup | Пошук | O(1) | O(N) | O(N) | Найгірший випадок — за колізій. Середній — амортизоване O(1). |
| Linear Search | Пошук | O(N) | O(N) | O(1) | Дружній до кешу. Єдиний варіант для невідсортованих підмножин. |
| BFS | Графи | O(V+E) | O(V+E) | O(V) | Найкоротший шлях у незважених графах. Черга FIFO. |
| DFS | Графи | O(V+E) | O(V+E) | O(V) | На основі стеку. Застосовується для топологічного сортування, генерації лабіринтів. |
| Dijkstra (binary heap) | Графи | O((V+E) log V) | O((V+E) log V) | O(V) | Найкоротший шлях у графі з невід'ємними вагами. Застосовується в пошуку шляху. |
| A* Search | Графи | O(E log V) | O(V²) | O(V) | Алгоритм Дейкстри, керований евристикою. Оптимальний за допустимої евристики. |
| Bellman-Ford | Графи | O(V·E) | O(V·E) | O(V) | Обробляє від'ємні ваги ребер. Виявляє від'ємні цикли. |
| Floyd-Warshall | Графи | O(V³) | O(V³) | O(V²) | Найкоротші шляхи між усіма парами. Непрактичний для V>1000. |
| Prim's MST | Графи | O(E log V) | O(E log V) | O(V+E) | Мінімальне кістякове дерево. Застосовується для генерації лабіринтів. |
| KD-Tree build | Просторові | O(N log N) | O(N²) | O(N) | Після побудови запит kNN — O(log N). Погіршується у високих вимірностях. |
| Quad/Octree build | Просторові | O(N log N) | O(N²) | O(N) | Адаптивне поділення. Застосовується в N-body Barnes-Hut: O(N log N). |
| Spatial Hash lookup | Просторові | O(1) сер. | O(N) | O(N) | Амортизоване O(1). Найкраще для рівномірних розподілів частинок (SPH). |
| Uniform Grid | Просторові | O(k) | O(N) | O(W·H) | k = середня кількість частинок на клітинку. Дуже швидко для щільних симуляцій. |
| FFT | Числові | O(N log N) | O(N log N) | O(N) | Швидке перетворення Фур'є. Замінює O(N²) DFT. GPU FFT в океані на WebGL. |
| Conjugate Gradient | Числові | O(N√κ) | O(N²) | O(N) | κ = число обумовленості. O(N^1.5) для 2D-лапласіана. Ітеративний розв'язувач. |
| Gaussian Elim. (LU) | Числові | O(N³) | O(N³) | O(N²) | Прямий розв'язувач. Точний. Практичний лише для N ≤ 10³ у реальному часі. |
| Newton's Method | Числові | O(log 1/ε) | O(N²·iter) | O(1) | Квадратична збіжність поблизу кореня. Для систем потрібен якобіан. |
| Broad-phase AABB | Фізика | O(N log N) | O(N²) | O(N) | Sort-and-sweep. Близько до O(N) для повільних об'єктів. |
| Narrow-phase GJK | Фізика | O(1) на пару | O(1) | O(1) | Обчислення відстані між опуклими тілами. Ітеративний, зазвичай 10–15 ітерацій. |
| SPH (neighbour find) | Фізика | O(N·k) | O(N²) | O(N) | k = частинки в радіусі ядра. Просторовий хеш зводить до пошуку O(1). |
| Spring-lattice | Фізика | O(N·springs) | O(N·springs) | O(N) | Пружин ≈ 4–8× N для регулярної ґратки. Лінійна за N. Застосовується для тканини, руйнування. |
| N-body O(N²) | Фізика | O(N²) | O(N²) | O(N) | Попарна гравітація. GPU-паралельно = ~16k частинок за 60fps. |
| Barnes-Hut N-body | Фізика | O(N log N) | O(N²) | O(N) | Октодерево + мультиполь: віддалені кластери розглядаються як одна маса. θ = 0.5–0.9. |
Коротка довідка з Big-O
O(1)
Константна — не залежить від розміру вхідних даних. Завжди швидка.
Пошук у хеш-таблиці, доступ за індексом масиву
O(log N)
Логарифмічна — вдвічі зменшує задачу на кожному кроці. 1млрд → 30 кроків.
Бінарний пошук, операції зі збалансованим BST
O(N)
Лінійна — масштабується прямо пропорційно до розміру. Стандартний прохід.
Пошук максимуму, підрахунок, інтегрування Верле
O(N log N)
Лінеарифмічна — оптимальна нижня межа для сортування на основі порівнянь.
Mergesort, FFT, алгоритм Дейкстри
O(N²)
Квадратична. Прийнятна для N≤10⁴; за 60fps — N≤~3000.
Наївний N-body, сортування вставками, наївний SPH
O(N³)
Кубічна. Практична межа N≤~300 на кадр.
Метод Гаусса, Floyd-Warshall
O(2^N) / O(N!)
Експоненціальна / факторіальна. Лише крихітні N. Територія NP-складних задач.
Сума підмножини (повний перебір), наївний TSP