Кожен клас складності малює криву
Побудова вартості порівняно з розміром вхідних даних
Розмістіть розмір вхідних даних N на осі x. Розмістіть вартість (операції, час) на осі y. Кожен клас складності створює відокремлену криву. Ви можете розпізнати швидкість зростання алгоритму за формою його кривої продуктивності.
O(1) — плаский горизонтальний лінія. Функція f(N) = 1. Немає нахилу. Вартість ніколи не змінюється незалежно від N. Пошук у таблиці хешування: чи містить таблиця 10 або 10 000 000 елементів, один розрахунок хешу стрибає до потрібного контейнера.
O(log N) — м'яка восходяща крива, нахил зменшується. При N = 1 000 000: вартість ≈ 20 операцій. Крива піднімається крутo при малому N, потім вирівнюється. Кожного подвоєння N додає рівно одну одиницю вартості.
O(N) — діагональна пряма лінія. Нахил = 1 (у асимптотичному сенсі). Вартість зростає з тією ж швидкістю, що й N. Якщо N потроюється, вартість потроюється.
O(N log N) — крутіша діагональ з легким восходящим вигином. Розташовується вище O(N), але нижче O(N²). Логарифмічний множник додає повільно зростаючий множник до лінійного нахилу.
O(N²) — парабола, що відкривається вверх. Нахил збільшується зі зростанням N. При N = 10: вартість = 100. При N = 100: вартість = 10 000. При N = 1 000: вартість = 1 000 000.
Зростаючий розрив
Співвідношення O(N²) / O(N) = N. Розрив між параболою та діагоналлю розширюється зі зростанням N. При N = 10: розрив у 10×. При N = 100: розрив у 100×. При N = 1 000: розрив у 1 000×. При N = 50 000: розрив у 50 000×. Розрив дорівнює N — завжди.
Розрахунок розриву масштабу
Великий граф залежності містить 50 000 пакетів (N = 50 000). Один алгоритм працює за часом O(N). Другий працює за часом O(N²). При цьому N співвідношення O(N²)/O(N) = N = 50 000.
Біcекція відрізка
Двійковий пошук як повторне ділення навпіл
Відсортований масив з N елементів утворює відрізок довжини N. Двійковий пошук багатократно ділить цей відрізок:
1. Вкажіть на середину залишкового відрізка.
2. Якщо ціль < середина: права половина зникає. Повторіть для лівої половини.
3. Якщо ціль > середина: ліва половина зникає. Повторіть для правої половини.
4. Якщо ціль = середина: готово.
Після k біcекцій залишковий відрізок має довжину N / 2^k. Пошук закінчується, коли ця довжина дорівнює 1:
N / 2^k = 1 → 2^k = N → k = log₂N
Таким чином, двійковий пошук у N елементах вимагає не більше log₂N порівнянь.
Ділення навпіл і подвоєння: дві сторони однієї кривої
Ділення навпіл і подвоєння — це геометричні інверси. Експоненціальна крива 2^k і логарифмічна крива log₂N — це відображення одна одної крізь лінію y = x.
Розглянемо складання паперу: аркуш починається товщиною 0,1 мм. Кожне складання подвоює товщину. Після 42 складань: 0,1 мм × 2^42 ≈ 439 804 км — далі за Місяцем (384 400 км). Двійковий пошук виконує зворотну операцію: почніть з N елементів, кожен крок ділить кількість навпіл, досягніть 1 елемента за log₂N кроків.
Геометрія: біcекція — це самоподібна операція. Кожна біcекція виробляє дві половини, які виглядають ідентично за структурою до цілого. Рекурсія та логарифми мають цю самоподібність.
Порівняння та подвоєння
Відсортований масив містить 1 048 576 елементів. Примітка: 1 048 576 = 2^20.
Функція хешування як геометричне відображення
Функція хешування як функція
Таблиця хешування відображає ключ на контейнер за допомогою функції хешування:
контейнер = hash(ключ) mod розмір_таблиці
Це функція у строгому математичному сенсі: вона відображає область (усі можливі ключі) на діапазон (індекси контейнерів 0 до розміру_таблиці − 1). Геометрична картина: ключі займають один простір; контейнери займають інший. Функція хешування проектує ключі на індекси контейнерів.
Пошук O(1) — прямий стрибок, без пошуку. Функція хешування обчислює індекс контейнера за постійний час. Стрибніть безпосередньо на цей контейнер. Немає обходу, немає циклу порівняння.
Коефіцієнт завантаження. При коефіцієнті завантаження 0,75, 75% контейнерів містять принаймні один елемент. Вище ~0,9, колізії збільшуються: два ключі хешуються до одного контейнера, утворюючи ланцюг елементів усередині цього контейнера. Пошук у довгому ланцюгу деградує до O(N) у гіршому випадку.
Якість розподілу як геометрія
Добре розподілена функція хешування розповсюджує ключі рівномірно по всім контейнерам. Геометрично: діапазон функції охоплює її кодомен рівномірно. Кожен контейнер отримує приблизно N / розмір_таблиці ключів.
Погана функція хешування кластеризує ключі у кілька контейнерів. Геометрично: діапазон функції скорочується до підмножини кодомену — більшість ключів відображаються на кілька точок. Залишилися контейнери сидять порожніми.
Зв'язок з MOAD-0001
Заміна списку набором вирішує MOAD-0001, оскільки набір внутрішньо використовує таблицю хешування. Сканування списку O(N) → пошук у таблиці хешування O(1). Геометрично: лінійний обхід послідовності трансформується у пряму проекцію через функцію. Послідовність зникає; функція замінює її.
Аналіз погано розподіленого хешування
Таблиця хешування містить 1 000 контейнерів і 900 елементів (коефіцієнт завантаження 0,9). Погана функція хешування надсилає 500 з цих елементів до одного контейнера.