Есть ли алгоритм поиска элемента в отсортированном массиве со сложностью меньше log2 (n)

Question

Я кодировал алгоритм поиска в отсортированном массиве со сложностью log2 (n) / 5. Это полезно?

Answer 1

Доказано, что вы не можете получить значение ниже O (log (n)) для поиска, который предполагает только операции сравнения. сложность log2 (n) / 5 - это то же самое, что и O (log (n)).
Полезность зависит от того, для чего вы его используете.

Answer 2

Hm. Сложный вопрос. Почему бы вам не опубликовать свой алгоритм и показать нам, что вы делаете.

Однако, для реального выигрыша вы должны быть лучше, чем O (log2 log2 (n))? Это то, что в среднем выполняет интерполяционный поиск ..

http://en.wikipedia.org/wiki/Interpolation_search

Answer 3

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

Как вы предлагаете завершить менее чем за логон шагов, если искомого элемента нет в вашем массиве?

Answer 4

Я думаю, было бы полезно, если бы он был быстрее, чем другие существующие алгоритмы поиска O (logn) на практике . Другими словами, если ваше тестирование производительности показывает улучшение скорости. Однако для очень больших входных данных постоянные улучшения времени (например, 1/5) не имеют большого значения. Вот почему наибольшее значение придается алгоритму асимптотической сложности .

Answer 5

Конечно, вы всегда можете поспорить о том, обязательно ли нелинейный поиск быстрее, чем линейный: http://www.ddj.com/184405848

Т.е., если вы ищете строку кэша, линейный поиск может быть быстрее, чем ветвление.