Сложность алгоритма (Big-O)

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

Нотация Big-O (О-большое) оценивает порядок роста функции сверху. Формальное определение: если найдутся константа c > 0 и число n0 такие, что для всех n ≥ n0 выполняется f(n) ≤ c · g(n), то говорят, что f(n) = O(g(n)). На практике постоянные множители и слагаемые низшего порядка отбрасывают: 3n + 5 = O(n), n² + 100n = O(n²). Обычно оценивают худший случай работы алгоритма.

Самые распространённые классы сложности расположены по скорости роста. O(1) — константная (например, обращение к элементу a[i]); O(log n) — логарифмическая (двоичный поиск); O(n) — линейная (один цикл, например for x in a: s += x); O(n log n) — эффективная сортировка (сортировка слиянием, Timsort); O(n²) — квадратичная (два вложенных цикла, сортировка пузырьком); O(2^n) — экспоненциальная (перебор всех подмножеств множества из n элементов). Сложности последовательных блоков складываются, и остаётся наибольшая, а сложности вложенных циклов перемножаются.

На больших n разница огромна. Если считать, что компьютер выполняет около 100 миллионов простых операций в секунду, то при n = 1 000 000 алгоритм O(n) работает около сотой доли секунды, алгоритм O(n log n) — примерно 0,2 секунды, а алгоритм O(n²) занимает около 10 000 секунд, то есть почти 3 часа. Поэтому на больших данных сложность алгоритма влияет на время работы сильнее, чем скорость устройства.

Главное

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