re:re:actable
Урок 033 минуты чтения

Как считать временную сложность?

На этой странице
Кратко

Временная сложность показывает, сколько операций делает алгоритм при росте 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).
  • Встроенные методы тоже имеют стоимость.

Документация

Wikipedia: Time complexity.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам