(обратите внимание, я автор nedtries). Я думаю, что мое объяснение сложности на передней части страницы Nedtries имеет смысл? Возможно, нет.
Ключ, который вам не хватает, заключается в том, что разница между битами определяет сложность. Чем больше разница, тем ниже стоимость поиска, а чем меньше разница, тем выше стоимость поиска.
Тот факт, что это работает, проистекает из современных процессоров, вышедших из строя. Как простое упрощение: если вы избегаете основной памяти, ваш код работает примерно в 40-80 раз быстрее, чем если вы зависите от основной памяти. Это означает, что вы можете выполнить 50-150 операций за время, необходимое для загрузки одной вещи из памяти. Это означает, что вы можете немного отсканировать и выяснить, на какой узел нам нужно перейти, чтобы посмотреть следующий, не намного дольше, чем время, необходимое для загрузки строки кэша для этого узла в память.
Это эффективно удаляет логику, битовое сканирование и все остальное из анализа сложности. Все они могут быть O (N ^ N), и это не имеет значения. Что сейчас важно, так это то, что выбор следующего узла, на который нужно смотреть, фактически свободен, поэтому число узлов, которые должны быть загружены для проверки, является ограничением масштабирования, и, следовательно, это среднее число просмотренных узлов из общего числа узлов, что является его средней сложностью, потому что медлительность основной памяти - безусловно самое большое ограничение сложности.
Имеет ли это смысл? Это означает странности, например, если некоторые биты плотно упакованы на одном конце ключа, но слабо упакованы на другом конце ключа, поиск в плотно упакованном конце будет значительно медленнее (приближается к O (log N), где N - число плотных элементов), чем ищет в слабо упакованном конце (приближается к O (1)).
Когда-нибудь скоро я перейду к добавлению новых функций, которые используют эту функцию побитовых попыток, так что вы можете сказать "добавить этот узел в свободно / плотно упакованное пространство и вернуть выбранный вами ключ" и все виды вариации на эту тему. К сожалению, как всегда, все сводится ко времени и требует времени.
Найл