Является ли поиск по Фибоначчи быстрее, чем двоичный поиск, независимо от операционной скорости ? Поскольку шаги двоичного поиска меньше.
Это зависит от базовой системы хранения для списка. Например, подумайте о диске. «Дешевле» искать место в том же цилиндре, который был ранее прочитан, поскольку считывающее устройство не должно двигаться. Таким образом, если ваши чтения намного ближе друг к другу, вам, скорее всего, потребуется меньше перемещать считывающее устройство, поэтому ожидаемое время каждого поиска на диске короче. Кроме того, для перемещения чтения руки через меньше цилиндров так же быстрее, чем перемещение его по более цилиндрам
В примере:
Это намного дешевле, чтобы переместить чтения руки от (1) до (2), чем от (1) до (3). А поскольку (2) является «ближе» (в терминах адресов), то (3), более короткие скачки, скорее всего, будут в этой категории. [От (1) до (2) рычаг чтения вообще не сдвинется, он будет только вращать диск до тех пор, пока он не достигнет этого значения]
Разделение на 2 может выполняться с помощью битового сдвига, это действительно медленнее, чем дополнение?
Это главным образом проблема аппаратного обеспечения (и оптимизации компилятора). Я не могу представить себе, почему производство не будет делать эту оптимизацию, а бит-сдвиг в большинстве реализованных я знаю, так же быстро, как и дополнения.
В чем преимущество поиска Фибоначчи по сравнению с бинарным поиском?
Как указано в (1) - более короткое расстояние между последовательными дисками приводит к более коротким (ожидаемым) временам поиска.
[Поиск по Фибоначчи] (http: //en.wikipedia.org/wiki/Fibonacci_search_technique): «..когда поиск элементов имеет неравномерное хранилище для хранения данных (т. е. время, необходимое для доступа к хранилищу, зависит от местоположения, ранее доступного), поиск Фибоначчи имеет преимущество перед двоичным поиск в небольшом сокращении среднего времени, необходимого для доступа к месту хранения ». – user2864740
«Я прочитал некоторые материалы, которые претендуют на« ссылку », ссылку, что-то? действительно ли нам нужно полагаться на вашу интерпретацию? –
@ KarolyHorvath, материалы - это всего лишь книга и блог на другом языке, поэтому я не перечислял их здесь. И то, что я сказал в вопросе, просто упоминается в разделе при сравнении алгоритмов поиска, без особого объяснения. Я думаю, что лучше я просто передаю их смысл здесь. – Solo