Каждый класс сложности рисует кривую
Нанесите стоимость на график в зависимости от размера входа
Поместите размер входа N на ось x. Поместите стоимость (операции, время) на ось y. Каждый класс сложности производит отчетливую кривую. Вы можете распознать темп роста алгоритма по форме его кривой производительности.
O(1) — плоская горизонтальная линия. Функция f(N) = 1. Нет наклона. Стоимость никогда не меняется независимо от N. Поиск в хеш-таблице: независимо от того, содержит ли таблица 10 или 10 000 000 элементов, одно вычисление хеша переходит в нужную ячейку.
O(log N) — нежная восходящая кривая, наклон уменьшается. При N = 1 000 000: стоимость ≈ 20 операций. Кривая резко поднимается при малых 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.
Деление отрезка прямой пополам
Двоичный поиск как повторяющееся деление пополам
Отсортированный массив из N элементов образует отрезок прямой длины N. Двоичный поиск повторяющимся образом делит этот отрезок пополам:
1. Укажите на середину оставшегося отрезка.
2. Если цель < середина: правая половина исчезает. Повторите для левой половины.
3. Если цель > середина: левая половина исчезает. Повторите для правой половины.
4. Если цель = середина: готово.
После k делений пополам оставшийся отрезок имеет длину 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 шагов.
Геометрия: деление пополам — это самоподобная операция. Каждое деление пополам производит две половины, которые идентичны по структуре целому. Рекурсия и логарифмы разделяют эту самоподобность.
Сравнения и удвоения
Отсортированный массив содержит 1 048 576 элементов. Заметим: 1 048 576 = 2^20.
Хеш-функция как геометрическое отображение
Хеш-функция как функция
Хеш-таблица отображает ключ в ячейку, используя хеш-функцию:
bucket = hash(key) mod table_size
Это функция в строгом математическом смысле: она отображает область определения (все возможные ключи) на область значений (индексы ячеек от 0 до table_size − 1). Геометрический образ: ключи занимают один пространство; ячейки занимают другое. Хеш-функция проектирует ключи на индексы ячеек.
O(1) поиск — прямой переход, без поиска. Хеш-функция вычисляет индекс ячейки в постоянное время. Переходите напрямую в эту ячейку. Нет обхода, нет цикла сравнения.
Коэффициент загрузки. При коэффициенте загрузки 0,75, 75% ячеек содержат хотя бы один элемент. Выше ~0,9, столкновения увеличиваются: два ключа отображаются в одну ячейку, образуя цепь элементов внутри этой ячейки. Поиск в длинной цепи деградирует до O(N) в худшем случае.
Качество распределения как геометрия
Хорошо распределенная хеш-функция равномерно распределяет ключи по всем ячейкам. Геометрически: область значений функции охватывает её кодобласть равномерно. Каждая ячейка получает приблизительно N / table_size ключей.
Плохая хеш-функция кластеризует ключи в несколько ячеек. Геометрически: область значений функции коллапсирует в подмножество кодобласти — большинство ключей отображаются в те же несколько точек. Остальные ячейки остаются пустыми.
Связь с MOAD-0001
Замена списка набором исправляет MOAD-0001, потому что набор использует хеш-таблицу внутренне. Сканирование списка O(N) → поиск в хеш-таблице O(1). Геометрически: линейный обход последовательности трансформируется в прямую проекцию через функцию. Последовательность исчезает; функция её заменяет.
Анализ плохо распределенного хеша
Хеш-таблица имеет 1 000 ячеек и 900 элементов (коэффициент загрузки 0,9). Плохая хеш-функция отправляет 500 из этих элементов в одну ячейку.