Зачем мы измеряем алгоритмы
Одна и та же программа работает быстро на новом компьютере и медленно на старом. Поэтому секунды — плохой способ сравнивать два алгоритма: число зависит от машины, а не только от кода.
Вместо этого мы считаем шаги: сколько простых операций выполняет алгоритм. Шаг — это одно маленькое действие, например чтение значения, сравнение двух чисел или их сложение.
Нотация Big O описывает, как растёт число шагов при росте входных данных. Она не говорит «это занимает 3 секунды». Она говорит «если вход удваивается, работа удваивается» — это O(n) — или «если вход удваивается, работа остаётся прежней» — это O(1).
Big O смотрит на худший случай: наибольшее число шагов, которое алгоритм может потребовать для входа размера n.
Подсчёт шагов
Цикл, который посещает каждый элемент массива, делает один проход на элемент. Для 5 элементов это 5 шагов, для 10 элементов — 10 шагов. Число шагов совпадает с nums.length.
Нас не интересует точное число. Нас интересует форма роста: вдвое больше вход — вдвое больше шагов. Такая форма называется линейной и записывается как O(n).
Подсчитать шаги цикла
Функция добавляет внутри цикла счётчик steps++. Массив из 5 элементов требует 5 шагов, массив из 10 элементов — 10 шагов: счёт следует за размером входа.
Вывод: программа на TypeScript и захваченный вывод
function countSteps(nums: number[]): number {
let steps = 0
let sum = 0
for (const n of nums) {
sum += n
steps++
}
console.log("сумма:", sum)
return steps
}
const small = [2, 4, 6, 8, 10]
const big = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
console.log("шагов для 5 элементов:", countSteps(small))
console.log("шагов для 10 элементов:", countSteps(big))
Удвоение входа удваивает работу
Программа выполняет один и тот же считающий цикл для n = 100, 200 и 400. Каждый раз, когда n удваивается, число шагов тоже удваивается. Это отличительный признак O(n).
Вывод: программа на TypeScript и захваченный вывод
const pad = (value: number, width: number): string => String(value).padStart(width)
for (const n of [100, 200, 400]) {
let steps = 0
for (let i = 0; i < n; i++) {
steps++
}
console.log(`n = ${pad(n, 3)} -> ${pad(steps, 3)} шагов`)
}
Классы роста
Большинство алгоритмов попадает в несколько распространённых классов роста, от самого быстрого к самому медленному:
O(1) постоянный — работа не растёт.O(log n) логарифмический — удвоение входа добавляет всего один шаг.O(n) линейный — работа растёт вместе с входом.O(n log n) — хороший алгоритм сортировки.O(n²) квадратичный — цикл внутри цикла.O(2ⁿ) экспоненциальный — работа удваивается с каждым дополнительным элементом.
Для маленьких входов разница ничтожна. Для больших входов она решает, ответит ли программа сразу или не закончит никогда.
Сравнить классы роста
Таблица показывает число шагов для растущего n. При n = 16 значение log n равно всего 4, тогда как 2ⁿ — уже 65536. Чем больше становится n, тем сильнее классы расходятся.
Вывод: программа на TypeScript и захваченный вывод
const pad = (value: string | number, width: number): string => String(value).padStart(width)
console.log(pad("n", 5), pad("log n", 7), pad("n", 5), pad("n log n", 9), pad("n^2", 6), pad("2^n", 8))
for (const n of [1, 2, 4, 8, 16]) {
const logn = Math.log2(n)
console.log(
pad(n, 5),
pad(logn.toFixed(0), 7),
pad(n, 5),
pad((n * logn).toFixed(0), 9),
pad(n * n, 6),
pad(2 ** n, 8),
)
}
Что Big O игнорирует
Big O сохраняет только форму роста и отбрасывает детали. O(2n), O(n + 5) и O(n) — это один и тот же класс: линейный.
Почему? Потому что для больших входов постоянный множитель перестаёт иметь значение. Алгоритм, который делает 2 прохода по миллиону элементов, всё равно находится в другом мире по сравнению с тем, который сравнивает каждый элемент с каждым другим.
Точные правила упрощения — отбросить константы, отбросить младшие слагаемые — разбираются на отдельной странице далее в этой группе.
Два цикла — это всё равно O(n)
Программа делает два отдельных прохода по массиву: один для суммы, другой для наибольшего значения. Это 2n шагов — 16 для 8 элементов. Big O отбрасывает константу 2, поэтому это всё равно O(n).
Вывод: программа на TypeScript и захваченный вывод
const nums = [3, 1, 4, 1, 5, 9, 2, 6]
let steps = 0
// Проход 1: сумма.
let sum = 0
for (const n of nums) {
sum += n
steps++
}
// Проход 2: наибольшее значение.
let biggest = nums[0]
for (const n of nums) {
if (n > biggest) {
biggest = n
}
steps++
}
console.log("сумма:", sum)
console.log("максимум:", biggest)
console.log("элементов:", nums.length)
console.log("шагов:", steps)