Быстрый поиск заданного числа в упорядоченном массиве
Поиска чего? Дырки в заднице?
Заданного числа в упорядоченном массиве, ясен чебурек.
Делением пополам?
А быстрее - никак?
Алгоритм Боуера и Мура.(описывать долго. ya.ru поможет )
FAQ уже проверил? algolist.manual.ru например.
Быстрее O(log N) умеет искать только Бог и квантовый компьютер еще, может быть.
для данных с нормальным распределением есть всякие методы касательных и прочая хрень...
В условии задачи, про это ничего не сказано.
Ботай Кнута.
Ну типа это слегка зависит от реализации операции сравнения. Но если у нас операция сравнения дает 1 бит результата (типа 0: a>=b или 1: a<b а это так и есть на самом деле почти всегда, то возможность гарантированного нахождения элемента в сортированном массиве быстрее чем за log N (логарифм двоичный, округленный вверх) означает что мы сумели закодировать N чисел менее чем logN битами. Чего, естественно, не может быть. Это, конечно, не вполне строгое док-во, но общая идея именно такая.
Откуда мораль: если у нас операция сравнения, например, жрет три числа (x, l, r и результат у нее - где находится х по отношению к отрезку [l, r] - левее, правее, или внутри, то логарифм становится по основанию 3.
А если мы вообще в специальной хэш-таблице ищем, а элементов не очень много, то поиск будет за константное время производиться: например, если мы хотим искать среди уникальных чисел от 0 до 99999, то мы можем просто завести массивчик от 0 до 99999, и помечать там те числа, которые у нас есть. И выяснять, есть ли у нас там данное число за одну операцию =)
Вот.
Откуда мораль: если у нас операция сравнения, например, жрет три числа (x, l, r и результат у нее - где находится х по отношению к отрезку [l, r] - левее, правее, или внутри, то логарифм становится по основанию 3.
А если мы вообще в специальной хэш-таблице ищем, а элементов не очень много, то поиск будет за константное время производиться: например, если мы хотим искать среди уникальных чисел от 0 до 99999, то мы можем просто завести массивчик от 0 до 99999, и помечать там те числа, которые у нас есть. И выяснять, есть ли у нас там данное число за одну операцию =)
Вот.
Таким методом и произвольный массив можно отсортировать за O(1).
А что, не правда?
Есть алгоритмы, которые быстро работают при непомерных запросах к ресурсам.
Есть алгоритмы, которые работают не так быстро, зато памяти жрут ну совсем мало.
Про сортировку - утверждения про то, что самый хороший алгоритм работает за какое-то время - наверняка такой алгоритм ищется среди тех, которые требуют памяти, скажем O(N N- длина массива.
Алгоритмы, которые затребуют памяти O(e^N) или ещё больше - O(N^N) - работают принципиально быстрее.
Есть алгоритмы, которые быстро работают при непомерных запросах к ресурсам.
Есть алгоритмы, которые работают не так быстро, зато памяти жрут ну совсем мало.
Про сортировку - утверждения про то, что самый хороший алгоритм работает за какое-то время - наверняка такой алгоритм ищется среди тех, которые требуют памяти, скажем O(N N- длина массива.
Алгоритмы, которые затребуют памяти O(e^N) или ещё больше - O(N^N) - работают принципиально быстрее.
Алгоритмы, которые затребуют памяти O(e^N) или ещё больше - O(N^N) - работают принципиально быстрее.
чтобы загадить O(N^N) памяти нужно как минимум O(N^N) времени
чтобы загадить O(N^N) памяти нужно как минимум O(N^N) времени
это может быть не важно, в данном случае задача сформулирована не корректно - не понятно сколько раз мы хотим искать и как часто меняется исходный массив....
если нужно искать числа очень часто в константном массиве то нам пох на время его изначальной сортировки и уж тем более на время закидывания его в память
дает 1 бит результата... на самом деле почти всегда
На самом-то деле
сравнение _очень_ часто позволяет не только ответить на вопрос "кто больше", но и на вопрос "насколько больше", например когда числа сравниваются с помощью вычитания. Соответственно каждое сравнение несет дофига информации чтд...К тому же на практике зачастую используются алгоритмы, которые работают медленно в смысле С нормы (а математика изучает в основном ее зато работают быстро в смысле L нормы. В задачах реального времени такое не допустимо (ядерный реактор, скажем) а в других местах совершенно нормально. Тот же qsort работает _в худшем случае_ намного медленнее чем NlogN но _как правило_ случай оказывается не худшим
Оставить комментарий
kuby
кто-нибудь помнит алгоритм?