Метод поиска Фибоначчи

редактировать

В информатике метод поиска Фибоначчи - это метод поиска в отсортированном массиве с использованием деления и алгоритм захвата, который сужает возможные местоположения с помощью чисел Фибоначчи. По сравнению с бинарным поиском, где отсортированный массив делится на две части равного размера, одна из которых исследуется далее, поиск Фибоначчи делит массив на две части, размеры которых являются последовательными числами Фибоначчи. В среднем это приводит к увеличению числа выполняемых сравнений примерно на 4%, но имеет то преимущество, что для вычисления индексов элементов массива, к которым осуществляется доступ, требуется только сложение и вычитание, в то время как классический двоичный поиск требует сдвига битов, деления или умножения, операции, которые были менее распространены во время первой публикации поиска Фибоначчи. Поиск Фибоначчи имеет среднюю и худшую сложность O (log n) (см. нотация Big O ).

Последовательность Фибоначчи обладает тем свойством, что число является суммой двух своих предшественников. Следовательно, последовательность может быть вычислена путем повторного сложения. Отношение двух последовательных чисел приближается к золотому сечению, 1,618... Двоичный поиск работает путем деления области поиска на равные части (1: 1). Поиск по Фибоначчи может разделить его на части, приближающиеся к 1: 1,618, при использовании более простых операций.

Если элементы, в которых выполняется поиск, имеют неоднородное хранилище памяти доступа (т. Е. Время, необходимое для доступа к местоположению хранилища, зависит от местоположения, к которому осуществляется доступ), поиск Фибоначчи может иметь преимущество перед двоичным поиском в небольшом сокращении среднее время, необходимое для доступа к месту хранения. Если машина, выполняющая поиск, имеет прямое отображение кэш ЦП, двоичный поиск может привести к большему количеству промахов в кэше, потому что элементы, к которым осуществляется доступ, часто имеют тенденцию собираться только в нескольких строках кэша; это смягчается путем разделения массива на части, которые не имеют степени двойки. Если данные хранятся на магнитной ленте , где время поиска зависит от текущего положения головки, компромисс между более длительным временем поиска и большим количеством сравнений может привести к алгоритму поиска, который искажен аналогично поиску Фибоначчи.

Поиск по Фибоначчи происходит от поиска по золотому сечению, алгоритма Джека Кифера (1953) для поиска максимума или минимума унимодальной функции в интервале.

Алгоритм

Пусть k определяется как элемент в F, массиве чисел Фибоначчи. n = F m - размер массива. Если n не является числом Фибоначчи, пусть F m будет наименьшим числом в F, которое больше n.

Массив чисел Фибоначчи определяется где F k + 2 = F k + 1 + F k, когда k ≥ 0, F 1 = 1 и F 0 = 0.

Чтобы проверить, находится ли элемент в списке упорядоченных номеров, выполните следующие действия:

  1. Установить k = m.
  2. Если k = 0, остановиться. Нет совпадения; элемента нет в массиве.
  3. Сравните элемент с элементом в F k − 1.
  4. Если элемент совпадает, остановитесь.
  5. Если элемент меньше, чем запись F k-1, отбросить элементы с позиций F k-1 + 1 до n. Установите k = k - 1 и вернитесь к шагу 2.
  6. Если элемент больше, чем запись F k − 1, отбросить элементы с позиций с 1 по F k − 1. Перенумеровать оставшиеся элементы с 1 на F k − 2, установить k = k - 2 и вернуться к шагу 2.

Альтернативная реализация (из «Сортировка и поиск» Кнута):

Для данной таблицы записей R 1, R 2,..., R N, ключи которых расположены в порядке возрастания K 1< K2<... < KN, алгоритм ищет заданный аргумент K. Предположим, N + 1 = F k + 1

Шаг 1. [Инициализация] i ← F k, p ← F k -1, q ← F k-2 (на протяжении всего алгоритма p и q будут последовательными числами Фибоначчи)

Шаг 2. [Сравнить] Если K < Ki, переходите к шагу 3; если K>K i перейти к этапу 4; и если K = K i, алгоритм успешно завершается.

Шаг 3. [Уменьшение i] Если q = 0, алгоритм завершается неудачно. В противном случае установите (i, p, q) ← (i - q, q, p - q) (который перемещает p и q на одну позицию назад в последовательности Фибоначчи); затем вернитесь к шагу 2

шагу 4. [Увеличить i] Если p = 1, алгоритм завершится безуспешно. В противном случае установите (i, p, q) ← (i + q, p - q, 2q - p) (который перемещает p и q на две позиции назад в последовательности Фибоначчи); и вернуться к шагу 2

Два варианта алгоритма, представленные выше, всегда делят текущий интервал на больший и меньший подынтервалы. Исходный алгоритм, однако, разделил бы новый интервал на меньший и больший подынтервалы на шаге 4. Это имеет то преимущество, что новый i ближе к старому i и больше подходит для ускорения поиска на магнитной ленте.

См. Также

Ссылки

  1. ^ Фергюсон, Дэвид Э. (1960). «Фибоначчианский поиск». Коммуникации ACM. 3 (12): 648. doi : 10.1145 / 367487.367496. Обратите внимание, что анализ времени работы в этой статье ошибочен, как указывает Оверхольт (1972).
  2. ^Оверхольт, KJ (1973). «Эффективность метода поиска Фибоначчи». BIT Численная математика. 13 (1): 92–96. doi : 10.1007 / BF01933527.
  3. ^Кифер, Дж. (1953). «Последовательный минимаксный поиск максимума». Proc. Американское математическое общество. 4 : 502–506. doi : 10.1090 / S0002-9939-1953-0055639-3.
  4. ^Кнут, Дональд Э. (2003). Искусство программирования. т. 3 (Второе изд.). п. 418.
  • Луракис, Манолис. «Фибоначчианский поиск в C». Проверено 18 января 2007 г. Реализует вышеуказанный алгоритм (не оригинальный алгоритм Фергюсона).
Последняя правка сделана 2021-05-20 14:58:24
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте