Как считать временную сложность?
На этой странице
Временная сложность показывает, сколько операций делает алгоритм при росте input. Чтобы ее считать, нужно смотреть на циклы, рекурсию, вложенные структуры, вызовы методов и то, сколько раз каждый элемент реально обрабатывается.
Вопрос
Как посчитать временную сложность алгоритма по коду?
Один цикл
function sum(nums: number[]): number {
let total = 0
for (const num of nums) {
total += num
}
return total
}Массив длины n, один проход:
O(n)Два независимых цикла
function process(a: number[], b: number[]): void {
for (const x of a) console.log(x)
for (const y of b) console.log(y)
}Если размеры разные:
O(a + b)Не нужно автоматически писать O(n), если inputs независимы.
Вложенные циклы
function pairs(nums: number[]): void {
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums.length; j++) {
console.log(nums[i], nums[j])
}
}
}Каждый элемент сравнивается с каждым:
O(n^2)Цикл с делением пополам
function binarySearch(nums: number[], target: number): number {
let left = 0
let right = nums.length - 1
while (left <= right) {
const mid = Math.floor((left + right) / 2)
if (nums[mid] === target) return mid
if (nums[mid] < target) left = mid + 1
else right = mid - 1
}
return -1
}На каждом шаге отбрасываем половину:
O(log n)Откуда берется логарифм? Посчитаем, сколько раз можно делить 16 элементов пополам, пока не останется один:
16 -> 8 -> 4 -> 2 -> 1 (4 шага, 2^4 = 16)log2(n) - это ответ на вопрос "сколько раз нужно поделить n пополам, чтобы дойти до 1". Для миллиона элементов это всего около 20 шагов.
Когда вложенный цикл - не O(n^2)
Вложенность сама по себе ничего не решает: важно, сколько раз в сумме выполняется внутренний цикл.
function countLetters(words: string[]): number[] {
const result: number[] = []
for (const word of words) {
const counts = new Array(26).fill(0)
for (const char of word) {
counts[char.charCodeAt(0) - 97]++
}
result.push(counts.filter((c) => c > 0).length)
}
return result
}Внешний цикл идет по словам, внутренний - по буквам слова. Каждая буква всех слов обрабатывается один раз, поэтому сложность O(L), где L - общее число букв, а не O(n^2).
Похожая ситуация в sliding window: внутри for есть while, но левая граница за все время сдвигается не больше n раз, поэтому итог O(n).
Учитывай встроенные методы
const result = nums.filter((x) => x > 0).map((x) => x * 2)filter проходит массив, map проходит новый массив:
O(n)Но с двумя проходами. Big O одинаковый, константа больше.
Что отвечать на собеседовании?
Чтобы посчитать time complexity, я определяю размер input, смотрю, сколько раз каждый элемент обрабатывается, учитываю вложенные циклы, рекурсию и стоимость встроенных методов. Последовательные проходы складываются, вложенные часто перемножаются, а деление области поиска пополам дает O(log n).
Что важно помнить: частые ошибки
- Не учитывать
sort,slice,includes,shift. - Писать
O(n^2)для любых двух циклов, даже если они не вложенные. - Забывать, что
Array.prototype.shift()может бытьO(n). - Не различать
nиmдля двух inputs. - Оценивать только happy path.
Мини-шпаргалка
- Один проход -
O(n). - Два независимых прохода -
O(n + m)илиO(n). - Вложенные циклы - часто
O(n^2). - Деление пополам -
O(log n). - Сортировка - часто
O(n log n). - Встроенные методы тоже имеют стоимость.