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

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

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

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

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


big-o binary-search
person peterept    schedule 22.03.2012    source источник
comment
Похоже, вы пытаетесь добиться чего-то очень похожего на список пропуска   -  person Brian Roach    schedule 22.03.2012
comment
@BrianRoach Хотя даже список пропуска имеет сложность поиска O (log n). Единственное их преимущество перед ванильным бинарным деревом — это их свойства автобалансировки.   -  person Chris Pitman    schedule 22.03.2012

Ответы (4)


arrow_upward
3
arrow_downward

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

person Celada    schedule 22.03.2012
comment
И журнал (n / 34) = журнал (n) - журнал (34). Так что здесь нет даже постоянного множителя. - person Adam Mihalcin; 22.03.2012

arrow_upward
1
arrow_downward

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

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

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

person Eugen Rieck    schedule 22.03.2012
comment
Помимо скорости, есть еще одна причина использовать 32-битные целые числа вместо плавающей запятой для всего, что является углом (включая широту и долготу): с плавающей запятой значения, близкие к нулю, имеют большую доступную точность (больше десятичных разрядов сохраняется без потерь) и значения далеко от нуля меньше. Тем не менее, нет веских причин, по которым точки, расположенные ближе к экватору, должны храниться более точно, чем другие точки. Целые числа масштабируются таким образом, что 0 означает 0, а 2 147 483 648 означает, что π радиан эквивалентны дробным числам с фиксированной точкой и подходят для этого приложения. - person Celada; 22.03.2012
comment
Я сделаю это обязательно! Большой выигрыш, и, поскольку я уже генерирую данные в файл, я просто предварительно преобразую их в 32-битные. Очень хорошо. - person peterept; 22.03.2012
comment
@Celada Конечно, вы правы, но я подозреваю, что это будет иметь небольшие последствия в реальном мире: я подозреваю, что значения между -10 и -43, как в OQ, имеют точность с плавающей запятой, которая намного лучше, чем качество данных (GPS?) . Кроме того, источником данных является float, поэтому масштабирование не приведет к новой точности, которой не было в исходных данных. Тем не менее, мы согласны с тем, что int это правильный путь. - person Eugen Rieck; 22.03.2012

arrow_upward
0
arrow_downward

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

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

person seand    schedule 22.03.2012
comment
Конечно, да, но это имеет значение только в том случае, если оптимизация приводит к уменьшению асимптотической сложности количества элементов для поиска. Big-Oh на самом деле не что иное, как асимптотическое количество операций, необходимых для алгоритма. - person Chris Pitman; 22.03.2012

arrow_upward
0
arrow_downward

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

person Chris Pitman    schedule 22.03.2012
comment
В коде это будет выглядеть так: у меня -23,1234, поэтому я перехожу примерно к проценту -23 от -10 до -43. Затем я смотрю на значение, скажем, -33. Значит, теперь я прыгаю на определенный процент от -10 до -33 и так далее? - person peterept; 23.03.2012
comment
@peterept Верно. Чем однороднее ввод, тем вероятнее, что вы перейдете к нужной записи. - person Chris Pitman; 23.03.2012