Какое уравнение Big-O описывает мой поиск?

Question

У меня есть отсортированный массив двойных чисел (фактически широт), которые относительно равномерно распределены в диапазоне от -10 до -43. Теперь, если я выполнил бинарный поиск по этому списку, я получу O (log N).

Но я могу дополнительно оптимизировать поиск, имея таблицу поиска, где у меня есть 34 клавиши (от -10 до -43), которые затем могут перейти прямо к начальной точке этого числа.

Например: -23.123424 сначала найдите ключ 23 и узнайте начальный и конечный диапазон всех значений -23. Затем я могу бинарный поиск с середины этого.

Как бы выглядел мой Big-O?

Answer 1

Это все еще O (log n).Обратите внимание: для поиска начальных индексов в вашей таблице поиска целых чисел требуется постоянное время, чтобы эта часть ничего не добавляла.Тогда это O (log n), чтобы выполнить бинарный поиск.На самом деле это займет примерно log n / 34, потому что вы ожидаете искать в массиве в 34 раза меньше (значения распределены в 34 различных интервалах с границами от -43 до -10), но постоянные множители не учитываются-O запись.

Answer 2

Это все равно будет O(log N), но для уменьшенного набора данных (представьте меньшее значение для N).

Поскольку таблица поиска содержит ок.1/34, что близко к 1/32 или 5 шагам в бинарном поиске, возможно, вы захотите провести сравнительный анализ, если это действительно помогает: дополнительные пути кода с большим количеством ошибок в кеше и одно или другое неправильное предсказание / конвейер ветвленияочистка может сделать это медленнее, чем прямой двоичный поиск.

Кроме того, если время поиска для таблицы в памяти является узким местом, вы можете рассмотреть возможность представления своих латов в виде значений Int32 - достаточно точных,но гораздо быстрее искать.

Answer 3

Ваша концепция близка к концепции интерполяционного поиска , за исключением того, что вместо единственной "интерполяции" один раз на составной части ключа он рекурсивно использует интерполяцию для интеллектуального управления двоичным поиском.Поскольку ваш домен относительно однороден, ожидаемое время выполнения составляет O(log log n).

Answer 4

Похоже, что ваша оптимизация поможет, но я думаю, что она все еще считается O (log N), потому что вам все еще нужно искать точное значение. Если бы это привело вас непосредственно к значению, это было бы O (1)

Это ограничение анализа Big-Oh. При этом не учитывается, что вы уменьшили количество значений, которые вы должны искать.