Сложность алгоритма и O-нотация - Вопросы

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

От самого быстрого к самому медленному:

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

Основные правила:

• Константы-множители отбрасываются: 8n^4 = O(n^4), (n^2)/5 = O(n^2).
• Учитывается только самый быстрорастущий член: n^2 + n = O(n^2), 2^n + n^9 = O(2^n).
• Основание логарифма не указывают — логарифмы с разными основаниями отличаются лишь на постоянный множитель, поэтому пишут просто O(log n).
• Последовательные блоки складываются, вложенные — перемножаются: два цикла подряд дают O(n) + O(n) = O(n), а цикл внутри цикла — O(n) × O(n) = O(n^2).

Временная сложность (time complexity) оценивает, как растёт число операций, то есть время выполнения. Пространственная сложность (space complexity) — как растёт объём дополнительной памяти, которую алгоритм использует помимо самих входных данных. Эти оценки не обязаны совпадать: алгоритм может работать за O(n) по времени, но требовать лишь O(1) дополнительной памяти (обходит массив, храня только счётчик). Часто между временем и памятью приходится искать компромисс: ускорение за счёт кэширования результатов увеличивает расход памяти.

Один и тот же алгоритм может отработать по-разному в зависимости от входных данных, поэтому различают три оценки:

• Худший случай — верхняя граница, обозначается O-большим; её обычно и приводят, потому что она гарантирует, что медленнее не будет.
• Средний случай — типичное поведение на случайных данных (Θ, «тета-большое»).
• Лучший случай — нижняя граница (Ω, «омега-большое»).

Пример: линейный поиск в лучшем случае находит элемент сразу — O(1), а в худшем проходит весь массив — O(n). Когда говорят «сложность линейного поиска — O(n)», имеют в виду именно худший случай.