Лучший, худший и средний случаи
Три способа измерить алгоритм
Стоимость каждого алгоритма зависит от его входных данных. Два входа одинакового размера могут дать совершенно разные времена выполнения. Анализ сложности формализует три перспективы этой вариации.
Лучший случай — Ω (Омега): входные данные, которые позволяют алгоритму завершиться быстрее всего. Для линейного поиска по списку из N элементов: Ω(1) — целевой элемент находится на первой позиции. Одно сравнение, готово.
Худший случай — O (Big 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 list, 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), — это потраченная впустую работа.
Углубление: курс unhamming применяет анализ сложности к реальным дефектам в производственном программном обеспечении. См. Недостающая глава: алгоритмическая сложность & MOAD-0001: осадочный дефект.
Амортизированная вставка в хеш-таблицу
Хеш-таблица начинается пустой и удваивает емкость, когда коэффициент загрузки превышает 0,75. Вставка 1000 элементов вызывает ровно 10 удвоений с емкостями 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.