Алгоритмическая сложность: понятие и примеры
Выберите правильное определение алгоритмической сложности:
Теория: что такое алгоритмическая сложность
Алгоритмическая сложность описывает зависимость затрат алгоритма от размера входных данных n.
Чаще всего рассматриваются две величины: временная сложность (сколько операций требуется) и сложность по памяти (сколько дополнительной памяти требуется).
Фраза «оценка ресурсов в зависимости от размера входных данных» — ключ к правильному определению.
Три главных элемента определения:
- Оценка (а не точное измерение времени).
- Ресурсы (обычно время и/или память).
- Зависимость от n (размера входа).
Нотации O, Ω, Θ (асимптотика)
Для описания роста затрат используются асимптотические обозначения.
О-большое (Big O) — наиболее распространённая запись верхней оценки роста затрат по времени или памяти при увеличении n.
В асимптотическом анализе обычно игнорируются константы и менее значимые слагаемые, чтобы сравнивать именно порядок роста.
Мини-словарь:
O(g(n)): верхняя оценка; часто интерпретируется как «не растёт быстрее, чем g(n)» при больших n.Ω(g(n)): нижняя оценка; показывает, что быстрее определённого уровня опуститься нельзя.Θ(g(n)): «точная» по порядку оценка; и сверху, и снизу один и тот же порядок роста.
Пример идеи, почему константы отбрасываются:
- Если алгоритм делает
3n + 10операций, то по порядку роста этоO(n), потому что при больших n линейная часть определяет поведение.
// Условная иллюстрация: сравнение выражений по росту (не измерение времени)
function opsA(n) { return 3 * n + 10 } // O(n)
function opsB(n) { return n * n } // O(n^2)
for (const n of [10, 100, 1000]) {
console.log(n, opsA(n), opsB(n))
}
Примеры на JavaScript (время и память)
В примерах ниже размер входа — n = arr.length.
Важно различать время (сколько шагов делает алгоритм) и память (сколько дополнительной памяти создаётся поверх входных данных).
function exampleO1(arr) {
// Время: O(1) — одна операция чтения по индексу
// Память: O(1) — дополнительная память почти не используется
return arr[0]
}
function exampleOn(arr) {
// Время: O(n) — один проход по массиву
// Память: O(1) — хранится только sum
let sum = 0
for (let i = 0; i < arr.length; i++) {
sum += arr[i]
}
return sum
}
function exampleOn2(arr) {
// Время: O(n^2) — вложенные циклы
// Память: O(1)
let count = 0
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if (arr[i] === arr[j]) count++
}
}
return count
}
Логарифмический пример обычно связан с бинарным поиском по отсортированному массиву: на каждом шаге остаётся примерно половина диапазона, поэтому шагов требуется порядка log n.
function binarySearch(sortedArr, target) {
let left = 0
let right = sortedArr.length - 1
while (left <= right) {
const mid = Math.floor((left + right) / 2)
const value = sortedArr[mid]
if (value === target) return mid
if (value < target) left = mid + 1
else right = mid - 1
}
return -1
}
Таблица типичных классов сложности
Главная цель таблицы — быстро сопоставлять «как будет расти цена» при увеличении n.
| Обозначение | Как растёт при увеличении n | Пример идеи |
|---|---|---|
O(1) | Почти не меняется | Доступ по индексу, фиксированное число действий |
O(log n) | Растёт очень медленно | Деление диапазона пополам (бинарный поиск) |
O(n) | Пропорционально n | Один проход по данным |
O(n log n) | Между n и n^2 | Эффективные сортировки сравнениями |
O(n^2) | Быстро ухудшается | Два вложенных прохода по данным |
O(2^n), O(n!) | Становится непрактичным очень быстро | Полный перебор вариантов |
Схема роста (условно, без чисел):
n увеличивается →
O(1) -------------------------
O(log n) ----+----+----+----+----
O(n) /////////////////////////
O(n log n) ///////////////////////////////
O(n^2) //////////////////////////////////////////////
O(2^n) ////////////////////////////////////////////////////////////////
Итого: правильный ответ — 4, потому что алгоритмическая сложность описывает, как растут затраты времени и/или памяти при увеличении размера входных данных, обычно через асимптотические обозначения вроде O(n) или O(n^2).