Достижение линейного ожидаемого времени выполнения

До настоящего момента структура данных словаря рассматривалась как «черный ящик», а (13.31) выражает границу времени выполнения алгоритма как сумму времени вычислений и операций со словарем.

Для реализации словаря будет использоваться универсальная схема хеширования наподобие описанной в разделе 13.6. После того как алгоритм применит схему хеширования, случайность используется в нем двумя разными способами: во-первых, добавляемые точки располагаются в случайном порядке; во-вторых, для каждого нового минимального расстояния δ рандомизация применяется для создания новой хеш-таблицы с использованием универсальной схемы хеширования.

При вставке новой точки pi алгоритм использует операцию хеш-таблицы Lookup для нахождения всех узлов в 25 подквадратах, близких к pi. Однако если в хеш-таблице присутствуют коллизии, то эти 25 операций могут потребовать проверки много более чем 25 узлов. Утверждение (13.23) из раздела 13.6 показывает, что каждая операция Lookup требует проверки O(1) ранее вставленных точек (в ожидании).

Интуитивно понятно, что выполнение в ожидании O(n) операций с хеш-таблицей, в каждой из которых задействована проверка в ожидании O(1) элементов, приведет к ожидаемому общему времени выполнения O(n). Чтобы точно выразить это интуитивное представление, необходимо внимательно проследить за тем, как взаимодействуют эти два источника случайности.

(13.32) Допустим, рандомизированный алгоритм нахождения ближайшей пары был реализован с применением универсальной схемы хеширования. В ожидании общее количество точек, рассматриваемых во время операций Lookup, имеет границу O(n).

Доказательство. Из (13.31) мы знаем, что ожидаемое количество операций Lookup равно O(n), а из (13.23) — что каждая из этих операций требует рассмотрения в ожидании всего O(1) точек. Чтобы сделать вывод о том, что ожидаемое количество рассматриваемых точек равно O(n), мы проанализируем связь между этими двумя источниками случайности.