Какой из них быстрее и на сколько? Линейный поиск 1000 элементов на 1 Ghz или двоичный поиск 1 миллиона элементов на 5 Ghz? Учитывая, что каждая инструкция работает в 5 раз быстрее на 5 ГГц, а одна итерация линейного поиска на 2 раза быстрее, чем двоичный поиск.Сравнение двух алгоритмов
Бинарный поиск имеет сложность O (log n); линейный поиск имеет сложность O (n). Вы делаете математику, следуя еще несколько советов:
Q. What is the maximum number of comparisons that a binary search function will make when searching for a value in a 1,000 - element array?
A. То есть журнал (1000) база два ~ =
Q. Какое максимальное число сравнений о том, что Линейная функция будет искать при поиске значения в массиве из 1000 элементов?
A.
Что вы думаете об этом? Как вы видите линейный поиск, который дает шанс, что это o (n) по сравнению с бинарным поиском, который равен o (log n)? – Rotem
Но у обоих есть разные процессоры. –
. Гандикап процессора должен был быть в пользу линейного поиска, чтобы сделать игровое поле более ровным. В худшем случае двоичный код будет принимать ~ 20 итераций, тогда как линейный будет 1000. – Rotem