0
Я закодировал алгоритм поиска в отсортированном массиве со сложностью log2 (n)/5. Он полезен?Есть ли какой-либо алгоритм для поиска элемента в отсортированном массиве со сложностью меньше log2 (n)
A
ответ
12
Доказано, что вы не можете опускаться ниже O (log (n)) для поиска, который предполагает только операции сравнения. сложность log2 (n)/5 - это то же самое, что и O (log (n)).
Полезность зависит от того, для чего вы его используете.
2
Невозможно сделать лучше, чем log₂n, без каких-либо других предположений о массиве, отличном от того, что он отсортирован, или без создания предварительной компиляции/создания данных.
Как вы планируете завершить менее чем за шагом log₂n, если элемент, который вы ищете, отсутствует в вашем массиве?
+0
Этот алгоритм работает для списка случайных чисел. Я дал тестовые данные из 5, 20 000 случайных чисел. Так что я думаю, что это может быть полезно в каждой задаче, а иногда и в случае небольших номеров, его сложность близка к постоянной сложности. в случае число нет сложности лучше log2n –
+0
В этом случае есть O (loglogn) алгоритмы. Смотрите: http://www.dcc.uchile.cl/~rbaeza/ftp/tour.ps.gz – Imran
1
Конечно, вы всегда можете спорить о том или нет нелинейного поиск обязательно быстрее, чем линейный поиск: http://www.ddj.com/184405848
То есть, если вы ищете строку кэша, это может быть быстрее искать его линейно, чем ветвление.
4
Hm. Сложный вопрос. Почему бы вам не опубликовать свой алгоритм и не посмотрим, что вы делаете.
Однако для реальной победы вы должны быть лучше, чем O (log2 log2 (n))? Вот что интерполяционный поиск делает в среднем ..
+0
сэр, я думаю, что он близок к log2 (log2 (n)), но я не могу его математически доказать. сделали это на случайных данных такого размера, как (10, 100, 1000, 10000 и 512000). В то время как mo операций log2() не работает в binary.it основывается на предположении, что числа находятся на постоянном расстоянии, таком как (5, 10,15,20,25) –
+0
Ну, я задал этот вопрос, чтобы узнать, является ли мой алгоритм новым или нет. И из-за помощи ура я обнаружил, что это просто интерполяционный поиск. –
1
Я думаю, что было бы полезно, если бы это быстрее, чем другие существующие алгоритмы O (LOGN) поиска на практике. Другими словами, если ваш тестовый тест показывает улучшение скорости. Однако для очень больших входов постоянные улучшения времени (например, 1/5) не имеют большого значения. Вот почему наибольшее значение имеет асимптотическая сложность алгоритма .
Этот алгоритм работает для списка случайных чисел. Я дал тестовые данные из 520 000 случайных чисел. Так что я думаю, что он может быть полезен в каждой задаче, а иногда и в случае небольших номеров, его сложность просто близка к постоянной сложность. –
у вас, похоже, есть небольшое заблуждение о том, что именно сложнее. – shoosh