Что такое временная сложность алгоритма?

Что такое временная сложность?

Временная сложность алгоритма — это математическая оценка количества операций, которые выполняет алгоритм в зависимости от размера входных данных (n). Она не измеряет реальное время в секундах, а показывает, как быстро растёт время выполнения при увеличении n. Это ключевой инструмент для выбора оптимального алгоритма.

Основные виды сложности

• O(1) — константная: время не зависит от n (например, доступ к элементу массива по индексу).
• O(log n) — логарифмическая: время растёт медленно (например, бинарный поиск).
• O(n) — линейная: время пропорционально n (например, поиск в неотсортированном массиве).
• O(n log n) — часто встречается в эффективных сортировках (например, быстрая сортировка).
• O(n²) — квадратичная: время растёт быстро (например, пузырьковая сортировка).

Пример кода

// O(1) — константная сложность
function getFirstElement(arr) {
  return arr[0];
}

// O(n) — линейная сложность
function findElement(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

// O(n²) — квадратичная сложность
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

Как применять?

При выборе алгоритма для задачи важно учитывать ожидаемый размер данных. Для маленьких массивов (n < 100) разница между O(n²) и O(n log n) может быть незаметна, но для больших данных (n > 10 000) она становится критической. Всегда стремитесь к минимальной возможной сложности, но помните о trade-off с памятью.

Вывод: Понимание временной сложности помогает писать эффективный код и избегать узких мест в производительности, особенно при работе с большими объёмами данных.