Техника поиска Фибоначчи - Fibonacci search technique

Эта статья про алгоритм программирования. О методе нахождения экстремума математической функции см. Поиск по золотому сечению .

В информатике , то методика поиска Фибоначчи является метод поиска в отсортированный массив с использованием алгоритма разделяй и властвуй , что сужает возможные места с помощью чисел Фибоначчи . По сравнению с двоичным поиском, когда отсортированный массив делится на две части равного размера, одна из которых исследуется далее, поиск Фибоначчи делит массив на две части, размеры которых являются последовательными числами Фибоначчи. В среднем это приводит к увеличению числа выполняемых сравнений примерно на 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 = 1.

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

  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 , ключи в порядке возрастания К 1 < К 2 <... < K N , поиски алгоритма для данного аргумента K . Предположим, что N + 1 = F k +1

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

Шаг 2. [Сравнить] Если K < K i , перейти к шагу 3 ; если K > K я перейти на шаг 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. ^ a b c Фергюсон, Дэвид Э. (1960). «Фибоначчианский поиск». Коммуникации ACM . 3 (12): 648. DOI : 10,1145 / 367487,367496 . S2CID  7982182 . Обратите внимание, что анализ времени работы в этой статье ошибочен, как указал Оверхольт (1972).
  2. ^ Оверхолт, KJ (1973). «Эффективность метода поиска Фибоначчи». BIT Численная математика . 13 (1): 92–96. DOI : 10.1007 / BF01933527 . S2CID  120681132 .
  3. Перейти ↑ Kiefer, J. (1953). «Последовательный минимаксный поиск максимума» . Труды Американского математического общества . 4 (3): 502–506. DOI : 10.1090 / S0002-9939-1953-0055639-3 .
  4. ^ Кнут, Дональд Э. (2003). Искусство программирования . т. 3 (Второе изд.). п. 418. |volume=имеет дополнительный текст ( справка )
  • Луракис, Манолис. «Фибоначчианский поиск в C» . Проверено 18 января 2007 года . Реализует вышеуказанный алгоритм (не оригинальный алгоритм Фергюсона).