📅 Липень 2026
📊 67 алгоритмів
🗂 9 напрямків
Складність алгоритмів: велика таблиця
Одна довга таблиця з прокруткою, що містить часову та просторову складність кожного важливого алгоритму, який використовується в симуляціях цього сайту: сортування, графи, просторові/колізійні структури, обчислювальна геометрія, чисельне інтегрування, машинне навчання, процедурна генерація, криптографія та рендеринг. Для вужчої, з фільтром, шпаргалки sorting/searching/graph/spatial/ numerical/physics з колонками best/average/worst дивіться Довідник складності алгоритмів.
N розмір вхідних даних
V, E вершини, ребра
K діапазон ключів / кількість унікальних значень
d вимірність / глибина
k ітерації / кластери / сусідні елементи
| Алгоритм | Час | Пам'ять | Нотатки |
|---|---|---|---|
| Сортування та вибір | |||
| Timsort | O(N log N) | O(N) | Гібрид merge- та insertion-сортування. Стабільний. Використовується за замовчуванням у V8 (Array.prototype.sort) та Python. |
| Introsort | O(N log N) | O(log N) | Quicksort, що переходить на heapsort при глибокій рекурсії. Використовується у C++ std::sort. |
| Counting Sort | O(N + K) | O(K) | K — діапазон цілочисельних ключів. Не є порівняльним сортуванням, тому нижня межа O(N log N) не діє. |
| Radix Sort | O(d·(N + K)) | O(N + K) | d — кількість розрядів/проходів. Швидкий для цілих чисел або рядків фіксованої довжини. |
| Quickselect | O(N) avg / O(N²) worst | O(1) | Знаходить k-й найменший елемент без повного сортування. Основа для median-of-medians (гарантований O(N)). |
| Графи та пошук шляху | |||
| BFS | O(V + E) | O(V) | Найкоротший шлях у графах без ваг. Черга FIFO. |
| DFS | O(V + E) | O(V) | Виявлення циклів, топологічне сортування, компоненти зв’язності. |
| Dijkstra (binary heap) | O((V+E) log V) | O(V) | Лише невід’ємні ваги. Fibonacci heap покращує до O(E + V log V). |
| Bellman-Ford | O(V·E) | O(V) | Працює з від’ємними вагами; виявляє від’ємні цикли. |
| Floyd-Warshall | O(V³) | O(V²) | Найкоротші шляхи між усіма парами вершин через динамічне програмування. |
| A* Search | O(E) worst | O(V) | Dijkstra + допустима евристика h(n). На практиці досліджує значно менше вузлів. |
| Topological Sort (Kahn’s) | O(V + E) | O(V) | Впорядковує DAG так, щоб кожне ребро вказувало вперед. Використовується для графів залежностей. |
| Union-Find (path compression) | O(α(N)) amortized | O(N) | α — обернена функція Аккермана, практично константа. На ній базується MST Крускала. |
| Kruskal’s MST | O(E log E) | O(V) | Сортує ребра, додає через Union-Find, уникаючи циклів. |
| Prim’s MST (binary heap) | O(E log V) | O(V) | Вирощує одне дерево від стартової вершини. Кращий за Крускала на щільних графах. |
| PageRank (power iteration) | O(k·E) | O(V) | k — кількість ітерацій до збіжності. Кожна ітерація — одне множення розрідженої матриці на вектор. |
| Minimax + Alpha-Beta | O(b^(d/2)) best / O(b^d) worst | O(d) | b — коефіцієнт розгалуження, d — глибина. Хороше впорядкування ходів наближає до найкращого випадку. |
| Просторові структури та колізії | |||
| k-d Tree (build) | O(N log N) | O(N) | Запит (найближчий сусід): O(log N) в середньому, O(N) у гіршому випадку при високій розмірності. |
| Octree / Quadtree (build) | O(N log N) | O(N) | Глибина зазвичай обмежена; перебудовується або оновлюється поступово щокадру для рухомих тіл. |
| Barnes-Hut (N-body) | O(N log N) | O(N) | Параметр θ балансує точність і швидкість порівняно з наївним O(N²) для всіх пар. |
| Fast Multipole Method | O(N) | O(N) | Асимптотично швидший за Barnes-Hut для дуже великих N; складніший у реалізації. |
| Spatial Hash Grid | O(1) avg | O(N) | Вставка/запит на комірку за сталий середній час. Розмір комірки має відповідати радіусу взаємодії. |
| BVH Build (SAH) | O(N log N) | O(N) | Surface Area Heuristic дає майже оптимальну вартість обходу для трасування променів. |
| Sweep and Prune (broad phase) | O(N log N) | O(N) | Сортує AABB вздовж однієї осі; проходить у пошуку перекритих інтервалів. |
| GJK (narrow phase) | O(1) amortized | O(1) | Ітеративне уточнення симплексу; для пари зазвичай достатньо кількох ітерацій. |
| EPA (penetration depth) | O(k) iterations | O(k) | Запускається після виявлення перекриття GJK; розширює політоп до збіжності. |
| Обчислювальна геометрія | |||
| Convex Hull (Graham scan) | O(N log N) | O(N) | Сортування за кутом, потім прохід зі стеком. |
| Convex Hull (QuickHull) | O(N log N) avg / O(N²) worst | O(N) | «Розділяй і володарюй», аналогічно quicksort. |
| Delaunay Triangulation | O(N log N) | O(N) | «Розділяй і володарюй» або інкрементально з переворотом ребер. Двоїста до діаграми Вороного. |
| Voronoi Diagram (Fortune’s sweep) | O(N log N) | O(N) | Алгоритм лінії розгортки з «береговою лінією» параболічних дуг. |
| Marching Cubes | O(N) | O(N) | N — кількість вокселів. Один варіант з таблиці пошуку на комірку (256 конфігурацій). |
| Marching Squares | O(N) | O(N) | 2D-аналог Marching Cubes (16 конфігурацій). Використовується для контурів рельєфу, метаболів. |
| Чисельне інтегрування та фізика | |||
| Explicit Euler | O(N) / step | O(N) | Точність 1-го порядку. Енергія «дрейфує» з часом — уникати для орбітальної механіки. |
| Semi-implicit (Symplectic) Euler | O(N) / step | O(N) | Спочатку оновлює швидкість, потім позицію. Обмежена похибка енергії — типовий вибір для ігор. |
| Velocity Verlet | O(N) / step | O(N) | Точність 2-го порядку, оборотний у часі, чудове збереження енергії. |
| Runge-Kutta 4 (RK4) | O(4N) / step | O(N) | 4 обчислення похідної на крок для точності 4-го порядку. Не симплектичний. |
| Position-Based Dynamics (PBD) | O(N · iter) | O(N) | Ітеративна проєкція обмежень. Стабільний, але жорсткість залежить від кількості ітерацій. |
| XPBD | O(N · iter) | O(N) | Розширення PBD на основі піддатливості — жорсткість не залежить від кількості ітерацій. |
| SPH (per step) | O(N) with spatial hash | O(N) | Наївний пошук сусідів для всіх пар — O(N²); просторове хешування знижує до майже лінійного. |
| Lattice Boltzmann (LBM, per step) | O(N) | O(N) | N — комірки решітки (D2Q9/D3Q19). Зіткнення + перенесення, чудово паралелиться на GPU. |
| Finite Difference (per step) | O(N) | O(N) | N — вузли сітки. Оновлення за шаблоном; стійкість визначається умовою CFL. |
| Conjugate Gradient | O(N·√κ) iterations | O(N) | κ — число обумовленості (симетричної додатно визначеної) матриці системи. |
| Fast Fourier Transform (FFT) | O(N log N) | O(N) | Лежить в основі спектральних методів, аналізу звуку та синтезу океанських хвиль (FFT water). |
| Машинне навчання та ШІ | |||
| k-Means Clustering | O(N·k·i·d) | O(N + k) | N точок, k кластерів, i ітерацій, d вимірів. Збігається лише до локального оптимуму. |
| k-Nearest Neighbours (brute-force) | O(N·d) | O(N) | На один запит. k-d дерево чи ball tree знижують це приблизно до O(log N) при низькій розмірності. |
| PCA (via SVD) | O(min(N²d, Nd²)) | O(Nd) | N зразків, d вимірів. Рандомізований SVD дає значно швидше наближення при великому d. |
| Gradient Descent (per step) | O(N·d) | O(d) | N зразків, d параметрів. Mini-batch варіанти замінюють N на розмір батчу B за крок. |
| Backpropagation (per layer) | O(N) | O(N) | N — кількість ваг у шарі; один прямий і один зворотний прохід на крок навчання. |
| Genetic Algorithm (per generation) | O(pop · fitness cost) | O(pop) | pop — розмір популяції. Загальна вартість зростає з кількістю поколінь × популяцію × оцінку пристосованості. |
| MCMC / Metropolis-Hastings (per sample) | O(1) / step | O(1) | Стала робота на крок пропозиції, але потрібно багато кроків для досягнення цільового розподілу (час змішування). |
| Процедурна генерація та шум | |||
| Perlin Noise (3D, per sample) | O(1) | O(1) | 8 пошуків градієнта + трилінійна інтерполяція на запит, незалежно від розміру сітки. |
| Simplex Noise (3D, per sample) | O(1) | O(1) | Менше обчислень кутів, ніж у Перліна, у вищих вимірах (4 проти 8 у 3D); без напрямкових артефактів. |
| Worley / Cellular Noise | O(k) | O(1) | k — кількість опорних точок у сусідніх комірках (зазвичай 9–27). Основа текстур на кшталт «тріщин» та клітинних візерунків. |
| L-System (expand n iterations) | O(len₀ · r^n) | O(len₀ · r^n) | r — середній коефіцієнт розширення правила. Довжина рядка зростає експоненційно з глибиною ітерацій n. |
| Diamond-Square (terrain) | O(N²) | O(N²) | Сітка висот N×N. Класичний фрактальний генератор рельєфу, простий, але з помітними артефактами сітки. |
| Hydraulic Erosion (droplet-based) | O(D · steps) | O(N) | D — кількість симульованих крапель; кожна проходить «steps» комірок, відкладаючи/розмиваючи осад. |
| Рядки, стиснення та криптографія | |||
| Knuth-Morris-Pratt (KMP) | O(N + M) | O(M) | N — довжина тексту, M — довжина шаблону. Без відкату в тексті завдяки функції відмов. |
| Levenshtein / Edit Distance | O(N·M) | O(min(N,M)) | Класичне ДП; пам’ять можна звести до одного рядка за допомогою «rolling» масивів. |
| Huffman Coding (build) | O(N log N) | O(N) | N — кількість унікальних символів. Оптимальний префіксний код для відомих частот символів. |
| Run-Length Encoding | O(N) | O(N) worst | Тривіальний однопрохідний алгоритм; ефективний лише для даних з довгими повторами. |
| SHA-256 | O(N) | O(1) | N — довжина повідомлення у 512-бітних блоках. Фіксований внутрішній стан, одностороння (необоротна) функція. |
| AES-256 (encrypt one block) | O(1) | O(1) | Фіксовані 14 раундів на 128-бітний блок незалежно від розміру повідомлення. |
| RSA Modular Exponentiation | O(log e) | O(1) | Square-and-multiply; e — публічна експонента. Безпека спирається на складність факторизації, а не на сам алгоритм. |
| Рендеринг | |||
| Ray-Sphere / Ray-Triangle Test | O(1) | O(1) | Розв’язок у замкненій формі: квадратне рівняння (сфера) або Möller-Trumbore (трикутник) на тест. |
| Ray Marching (SDF) | O(steps) / pixel | O(1) | Кроки sphere tracing обмежені максимальною кількістю ітерацій і відстанню; вартість залежить від складності SDF сцени. |
| Path Tracing (per pixel) | O(bounces · samples) | O(1) / pixel | Монте-Карло інтегрування рівняння рендерингу; шум спадає як O(1/√samples). |
| Rasterization (per triangle) | O(pixels covered) | O(1) / pixel | Функції країв у просторі екрана; GPU апаратно розпаралелює обробку всіх покритих пікселів/фрагментів. |
Немає алгоритмів, що відповідають фільтру.
Складності — це типові/середні значення для інженерних рішень, а не формальні доведення найгіршого випадку для кожного рядка — дивіться відповідний туторіал алгоритму або Глосарій алгоритмів для означень і виведень.