Лучший, худший и средний случай
Три способа измерить алгоритм
Стоимость любого алгоритма зависит от его входных данных. Два входа одинакового размера могут производить совершенно разные временные характеристики. Анализ сложности формализует три точки зрения на это изменение.
Лучший случай — Ω (Омега): вход, который делает алгоритм самым быстрым. Для линейного поиска в списке из N элементов: Ω(1) — цель занимает первое место. Один сравнение, сделано.
Худший случай — O (Большое О): вход, который делает алгоритм самым медленным. Для линейного поиска: O(N) — цель находится в конце списка, или вообще не появляется. Каждый элемент требует проверки.
Средний случай — Θ (Тета): ожидаемая стоимость по всем возможным входам, предполагая равномерное распределение. Для линейного поиска с целью, равной вероятностью занимающей любое из N позиций: Θ(N/2) = Θ(N). Постоянная 1/2 исчезает, потому что Тета описывает узкие асимптотические рост, а не точные коэффициенты.
Почему худший случай доминирует
Системы должны обрабатывать худший случай. Запрос базы данных, который в среднем занимает 10 миллисекунд, но иногда занимает 60 секунд, вызывает видимое сбои для пользователя. Инженеры проектируют для худших границ, чтобы производительность оставалась предсказуемой, независимо от входных данных. Анализ среднего случая имеет значение в вероятностных настройках, но анализ худшего случая дает гарантии.
Анализ случая бинарного поиска
Бинарный поиск работает только со отсортированными массивами. На каждом шаге: сравните цель с элементом в середине. Если цель равна середине, верните ее. Если цель меньше, рекурсивно перейдите на левую половину. Если больше, рекурсивно перейдите на правую половину.
Каждое сравнение исключает половину оставшихся кандидатов.
Рост памяти и торговля временем и пространством
Счет памяти, а не операций
Комплексность времени измеряет количество выполненных операций алгоритма. Комплексность пространства измеряет дополнительную выделенную память за пределами входных данных. Оба важны в производственных системах: быстрый алгоритм, который выделяет O(N²) памяти, выедет сервер.
O(1) пространства: постоянная дополнительная память, независимо от N. Вместное сортировка (например, сортировка вставками) меняет элементы внутри исходного массива. Оно использует несколько временных переменных - O(1), независимо от размера массива.
O(N) пространства: память пропорциональная размеру входных данных. Создание копии N-элементного массива требует N ячеек. Сборка множества хеша из списка N строк хранит до N элементов.
O(N²) пространства: память пропорциональная N². Сборка N×N матрицы смежности для графа с N вершинами требует N² ячеек. При N = 10,000 вершин, это 10^8 элементов - сотни мегабайт для простого булевого поля.
Торговля временем и пространством
Один из фундаментальных ходов в разработке алгоритма: торговля пространством на время, или временем на пространство.
Хэш-таблицы используют O(N) дополнительной памяти, чтобы достичь O(1) поиска. Без хеш-таблицы, сканирование списка достигает O(N) поиска с O(1) дополнительной памятью. Хэш-таблица платит память за скорость.
Мемоизация сохраняет ранее вычисленные результаты (O(N) или больше памяти) для избежания повторного вычисления. Рекурсивный Фибоначчи без мемоизации работает за O(2^N) времени. С мемоизацией: O(N) времени и O(N) памяти. Инвестиция в пространство уменьшает время экспоненциально.
Словарь хеша против отсортированного списка
Сравните две стратегии подсчета слов в документе из N слов:
Стратегия A: словарь (хэш-карта). Вставляем каждый слов; увеличиваем его счетчик.
Стратегия B: поддерживаем отсортированный список виденных слов; используем бинарный поиск для проверки принадлежности перед вставкой.
Амортизированная анализация: Распределение стоимости
Когда периодические расходы не разрушают среднюю производительность
Некоторые операции иногда дороги, но дешевы в среднем по всему последовательности. Амортизированная анализация вычисляет среднюю стоимость операции за весь последовательность - не худший случай стоимости одной операции.
Динамический массив (Python список, Java ArrayList): начинает с емкости 1. Когда емкость полна, удваивает емкость. Удваивание копирует все существующие элементы: O(N) работа для одного добавления. Но удваивания редки. После N общих добавлений, сколько общих операций копирования произошло?
Удваивания происходят при емкостях 1, 2, 4, 8, ..., N/2. Количество копий: 1 + 2 + 4 + ... + N/2. Это геометрическая сумма, равная N - 1 общих копий через все N добавлений. Среднее копий за добавление: (N - 1) / N < 1, поэтому O(1) амортизированная за добавление несмотря на O(N) худший случайная стоимость за удваивание.
Почему амортизированная анализация имеет значение
Система, которая иногда останавливается, чтобы изменить размер, сбалансировать или сжимать структуру, может казаться иметь тревожащие худшие индивидуальные операции. Амортизированная анализация показывает, что тревога ложна: редкие дорогие события оплачиваются многими дешевыми. Понимание амортизированной стоимости предотвращает переделку: добавление сложности для избежания редкого O(N) операции, которая вносит только O(1) амортизировано - это потраченная работа.
Глубже: Курс без Хэмминга применяет анализ сложности к реальным дефектам в производственной программной продукции. См. [Пропущенный главу: Алгоритмическая сложность](/en/un/unhamming_algorithmic_complexity) & [MOAD-0001: Седиментный дефект](/en/un/unhamming_moad_sedimentary).
Амортизированная стоимость вставки в хэш-таблице
Хэш-таблица начинается с пустого состояния и удваивает свою емкость, когда коэффициент загрузки превышает 0,75. Вставка 1,000 элементов вызывает ровно 10 удвоений с емкостями 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.