Обобщенный быстрый поиск.

Определение

Основная идея - разбиение пространства ключей на независимые подпространства.

• При таком независимом разбиении на M подпространств сложность уменьшается.
• При увеличении M, время поиска уменьшается, затраты памяти увеличиваются.
• При M ~ N имеется зона оптимальности, поиск уже проводится за O(1), а память O(N).

1. Предположим у нас есть база данных городов с их численностью.

2. Заменим списки для каждой буквы, на деревья быстрого поиска, с учетом численности.