Как определить временную сложность алгоритма

Определение

Временная сложность (Big O) — это оценка роста количества операций алгоритма в зависимости от размера входных данных n.

Базовые шаги определения сложности

1. Определить, от чего зависит размер входа (n)

2. Посчитать количество операций

3. Оставить доминирующий член

4. Игнорировать константы

Примеры

O(1) — константная

arr[0];

O(n) — линейная

for (let i = 0; i < arr.length; i++) {
  // операция
}

O(n²) — квадратичная

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    // операция
  }
}

Важные нюансы

1. Вложенные циклы → умножение сложностей

2. Последовательные циклы → сложность складывается, но остаётся доминирующая

3. Чаще всего оценивают худший случай

Вывод

Определение временной сложности — это умение абстрагироваться от деталей реализации и смотреть на рост количества операций при увеличении n.