Найкращий, Найгірший та Середній Випадок
Три способи вимірювання алгоритму
Вартість кожного алгоритму залежить від його входу. Два входи одного розміру можуть давати дуже різні часи виконання. Аналіз складності формалізує три точки зору на цю варіацію.
Найкращий випадок — Ω (Омега): вхід, який робить алгоритм найшвидшим. Для лінійного пошуку списку з N елементів: Ω(1) — мета знаходиться на першій позиції. Одне порівняння, готово.
Найгірший випадок — O (Big O): вхід, який робить алгоритм найповільнішим. Для лінійного пошуку: O(N) — мета знаходиться в кінці списку, або не з'являється взагалі. Кожен елемент потребує перевірки.
Середній випадок — Θ (Тета): очікувана вартість над усіма можливими входами, припускаючи рівномірний розподіл. Для лінійного пошуку, коли мета з однаковою ймовірністю може займати будь-яку з N позицій: Θ(N/2) = Θ(N). Константа 1/2 зникає, оскільки Theta виражає точне асимптотичне зростання, а не точні коефіцієнти.
Чому найгірший випадок домінує
Системи повинні обробляти найгірший випадок. Запит бази даних, який у середньому займає 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 застосовує аналіз складності до дефектів у реальному світі в робочому програмному забезпеченні. Див. The Missing Chapter: Algorithmic Complexity & MOAD-0001: The Sedimentary Defect.
Амортизована Вставка Таблиці Хешу
Таблиця хешу починається пустою та подвоює ємність, коли коефіцієнт завантаження перевищує 0,75. Вставлення 1000 елементів викликає рівно 10 подвоєння при ємностях 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.