Алгоритмы с нуля
Нотация Big-O
В прошлом уроке ты научился подсчитывать шаги: алгоритм largestOf берёт примерно n шагов для списка из n элементов, а вложенный цикл берёт примерно n² шагов. Но что если ты неправильно подсчитал? Что если точное число 3n + 5, или 100n + 1000? Для большого n разница имеет значение? Оказывается: нет. Когда n становится большим, имеет значение только доминирующий член. Это идея за нотацией Big-O.
После этого урока ты можешь читать и писать нотацию Big-O (O(1), O(n), O(n²)), объяснить, почему мы отбрасываем константы и малые члены, и вывести Big-O простого кода, подсчитав циклы и их вложенность.
Нотация Big-O — это сокращение для описания того, как растёт число шагов алгоритма при росте размера входа n. Она игнорирует постоянные множители и малые члены, сосредоточиваясь только на доминирующем поведении.
Вот ключевая идея: когда n большой, доминирующий член берёт верх. Предположим, один алгоритм берёт 2n шагов, другой — n шагов. Оба удваиваются при удвоении n. Предположим, один берёт 3n², другой — n². Оба учетверяются при удвоении n. Постоянный множитель (2 против 1, или 3 против 1) не меняет скорость роста. Мы говорим, что оба O(n) и O(n²) соответственно — Big-O описывает скорость роста, а не точное количество шагов.
Например:
- Число шагов = n − 1 → Big-O O(n)
- Число шагов = 3n + 5 → Big-O O(n)
- Число шагов = n² / 2 → Big-O O(n²)
- Число шагов = 100 → Big-O O(1)
Почему отбрасываем константы и малые члены? При больших n доминирующий член доминирует над всем остальным. Сравним:
| n | n | 3n + 100 | n² / 2 | n² |
|---|---|---|---|---|
| 10 | 10 | 130 | 50 | 100 |
| 100 | 100 | 400 | 5 000 | 10 000 |
| 1 000 | 1 000 | 3 100 | 500 000 | 1 000 000 |
| 10 000 | 10 000 | 30 100 | 50 000 000 | 100 000 000 |
При n = 10 000:
- Разница между n и 3n + 100 мала: 10 000 против 30 100 — оба примерно «линейны».
- Разница между n² / 2 и n² составляет 50 000 000 против 100 000 000 — множитель 2, но оба примерно «квадратичны».
Для сравнения алгоритмов важна форма роста, не константа. Big-O захватывает форму.
Читаем нотацию как:
- O(1) = «big-O единицы» или «постоянное время» — цена не растёт с n
- O(n) = «big-O от n» или «линейное время» — цена растёт в пропорции к n
- O(n²) = «big-O от n в квадрате» или «квадратичное время» — цена растёт как квадрат n
- O(log n) = «big-O от log n» или «логарифмическое время» — цена растёт медленно, как логарифм n (позже)
Big-O — это верхняя граница — описывает рост в наихудшем случае. Для некоторых алгоритмов лучший и средний случаи отличаются, но Big-O обычно относится к наихудшему.
Выведем Big-O реального кода.
Фрагмент 1: Один цикл
function sumAll(numbers) {
let sum = 0;
for (let i = 0; i < numbers.length; i++) {
sum += numbers[i];
}
return sum;
}Цикл выполняется ровно n раз (один раз за элемент). Каждая итерация делает 1 сложение. Итого: примерно n шагов. Big-O O(n).
Фрагмент 2: Вложенные циклы
function allPairs(numbers) {
let count = 0;
for (let i = 0; i < numbers.length; i++) {
for (let j = 0; j < numbers.length; j++) {
count++;
}
}
return count;
}Внешний цикл выполняется n раз. Для каждой внешней итерации, внутренний цикл выполняется n раз. Итого: n × n = n² итераций. Big-O O(n²).
Фрагмент 3: Без цикла
function getFirst(array) {
return array[0];
}Одна операция: доступ к массиву. Не зависит от n. Big-O O(1).
Фрагмент 4: Цикл в условии
function findIndex(array, target) {
for (let i = 0; i < array.length; i++) {
if (array[i] === target) {
return i;
}
}
return -1;
}Наихудший случай: цель не в массиве, поэтому цикл выполняется все n раз. Big-O O(n) (наихудший случай).
Смотри, как число шагов масштабируется для одного цикла. Проследи sumAll на списке размером 3:
1
function sumAll(numbers) {
2
let sum = 0;
3
for (let i = 0; i < numbers.length; i++) {
4
sum += numbers[i];
5
}
6
return sum;
7
}
Для n = 3, цикл выполняется 3 раза. Для n = 100 — 100 раз. Для любого n — ровно n раз. Это линейный рост — O(n).
Вот рост разных классов Big-O при увеличении размера входа:
Заметь:
- O(1) плоская — никогда не меняется, сколько бы ни было n.
- O(n) прямая линия — удвой n, удвой цену.
- O(n²) кривая, что взлетает — удвой n, учетвери цену.
- O(log n) растёт очень медленно — почти плоская даже для большого n.
- O(n log n) между линейной и квадратичной — растёт немного быстрее O(n), но намного медленнее O(n²).
- O(2ⁿ) взрывается — даже малый рост n приводит к астрономическому росту цены.
Для практики:
- O(1) и O(log n) очень быстры.
- O(n) и O(n log n) практичны даже для больших входов.
- O(n²) приемлемо для малых и средних входов (до тысяч элементов).
- O(2ⁿ) непрактично кроме крошечных входов (до ~30 элементов).
Доминирующий член — вот что имеет значение. Алгоритм с 100n + 50 шагов — это всё ещё O(n) — константа 100 не меняет форму роста. Алгоритм с n² + 1000n — это всё ещё O(n²) — член n ничтожен при больших n.
Функция берёт 5n + 10 шагов для размера входа n. Её Big-O?
Алгоритм имеет цикл, что выполняется n раз, и внутри него ещё цикл, что выполняется n раз. Его Big-O?
Что означает O(1)?
Если n растёт от 100 к 1 000, число шагов в алгоритме O(n²) растёт в сколько раз?
Расставь эти классы Big-O от самого быстрого к самому медленному росту:
- O(2ⁿ)
- O(n²)
- O(n)
- O(1)
Граничные случаи
Что про O(log n) и O(n log n)? Это приходят из деления задачи пополам на каждом шаге (бинарный поиск) или сортировки. Log означает логарифм — база-2 логарифм 1 000 000 только примерно 20. Поэтому O(log n) очень быстро. O(n log n) медленнее O(n) но намного быстрее O(n²). Это не фокус этого урока; трек по математике покрывает рост и логарифмы глубоко.
Частая ошибка
Путать O(n) с O(2n). Оба всё ещё «линейны» — постоянный множитель не имеет значения. O(3n), O(n) и O(100n) растут с одной скоростью (линейно). Когда доминирующий член n, Big-O это O(n).
Почему мы отбрасываем константы и малые члены при записи нотации Big-O?
Нотация Big-O описывает, как растёт цена алгоритма при увеличении размера входа n. Мы отбрасываем постоянные множители и малые члены, держа только доминирующий. Алгоритм, берущий 3n + 100 шагов — это O(n); берущий n² / 2 — это O(n²). Обычные классы:
- O(1) — постоянное время, цена не растёт
- O(log n) — логарифмическое, растёт очень медленно
- O(n) — линейное, цена растёт в пропорции к n
- O(n log n) — немного быстрее чем O(n²)
- O(n²) — квадратичное, цена растёт как квадрат n
- O(2ⁿ) — экспоненциальное, растёт взрывно
Чтобы найти Big-O кода: подсчитай циклы. Один цикл над n элементов — O(n). Вложенные циклы — O(n²). Без циклов — O(1). Доминирующий член — вот что считается.