Алгоритмы и сложность (Big O)

Почему один код быстрее другого: Big O, поиск, сортировка и структуры данных.

Классы сложности — нажми на класс для примера

Язык примеров:

Шаг 1 из 3

Зачем думать об эффективности

Размер данных имеет значение

javascript

Функция делает n² операций:

  n = 100    →       10 000 операций  → мгновенно
  n = 10 000 →  100 000 000 операций  → ~1 секунда
  n = 100 000 → 10 000 000 000 операций → ~3 часа!

Алгоритм, который "работает" на 100 элементах, может быть непригоден для 100 000.

Big O — нотация сложности

Big O описывает как растёт время работы при увеличении входных данных.

Мы смотрим на худший случай и порядок роста, игнорируя константы:

javascript

5n + 100 → O(n)      (константы не важны)
n² + n   → O(n²)     (доминирует n²)

Основные классы сложности

javascript

O(1)      — константное время   (не зависит от n)
O(log n)  — логарифмическое     (очень хорошо)
O(n)      — линейное            (нормально)
O(n log n)— линейно-логарифм.  (хорошо для сортировки)
O(n²)     — квадратичное        (плохо при больших n)
O(2ⁿ)     — экспоненциальное    (очень плохо)

Пакетные менеджеры и зависимости Базовые алгоритмы