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

Question

Временная сложность показывает, как растёт время выполнения алгоритма при увеличении входных данных. Обычно используют нотацию Big O, где учитывают только доминирующий фактор роста. Константы и малые члены отбрасываются. Основной фокус — на количестве операций в худшем случае.

YeaHub · Accepted Answer

ОпределениеВременная сложность (Big O) — это оценка роста количества операций алгоритма в зависимости от размера входных данных n.Базовые шаги определения сложностиОпределить, от чего зависит размер входа (n)Посчитать количество операцийОставить доминирующий членИгнорировать константыПримеры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++) {
    // операция
  }
}
Важные нюансыВложенные циклы → умножение сложностейПоследовательные циклы → сложность складывается, но остаётся доминирующаяЧаще всего оценивают худший случайВыводОпределение временной сложности — это умение абстрагироваться от деталей реализации и смотреть на рост количества операций при увеличении n.