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

Краткий ответ

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

Полный ответ

Что такое сложность

Сложность алгоритма показывает, как растёт потребление ресурсов (времени или памяти) при увеличении размера входных данных n.

Big O нотация

Описывает верхнюю границу роста функции, игнорируя константы и младшие слагаемые:

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

Мини‑примеры

O(1) — доступ к элементу:

arr[0]; // всегда одна операция

O(n) — поиск в массиве:

arr.find(x => x === target); // до n сравнений

O(n²) — вложенные циклы:

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

Временная vs пространственная

• Временная — количество операций.
• Пространственная — объём дополнительной памяти.

Пример: рекурсивный Фибоначчи имеет O(2ⁿ) по времени и O(n) по памяти (стек вызовов).

Практическое применение

• Выбор структур данных: массив vs хеш‑таблица.
• Оптимизация узких мест в коде.
• Оценка масштабируемости решения.

Частые ошибки

• Путать средний и худший случай.
• Игнорировать константы в реальных задачах.
• Преждевременная оптимизация без измерений.