Техника поиска Фибоначчи

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

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

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

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

Алгоритм

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

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

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

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

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

Учитывая таблицу записей R ₁ , R ₂ , ..., RN _, ключи которой расположены в порядке возрастания K ₁ < K ₂ < ... < K _N , алгоритм ищет заданный аргумент K . Предположим, N +1= F _{k +1}

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

Шаг 2. [Сравнить] Если < Ki , _K перейти к шагу 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 , 2 q − p ) (что перемещает p и q на две позиции назад в последовательности Фибоначчи); и вернитесь к шагу 2

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

См. также

Алгоритмы поиска

Ссылки

^ Jump up to: ^а ^б ^с Фергюсон, Дэвид Э. (1960). «Поиск Фибоначчиана» . Коммуникации АКМ . 3 (12): 648. дои : 10.1145/367487.367496 . S2CID 7982182 . Обратите внимание, что анализ времени выполнения в этой статье ошибочен, как указал Оверхолт в 1972 году (опубликовано в 1973 году).
^ Оверхолт, К.Дж. (1973). «Эффективность метода поиска Фибоначчи». БИТ Численная математика . 13 (1): 92–96. дои : 10.1007/BF01933527 . S2CID 120681132 .
^ Кифер, Дж. (1953). «Последовательный минимаксный поиск максимума» . Труды Американского математического общества . 4 (3): 502–506. дои : 10.1090/S0002-9939-1953-0055639-3 .
^ Кнут, Дональд Э. (2003). Искусство компьютерного программирования . Том. 3 (Второе изд.). п. 418.

Луракис, Манолис. «Поиск Фибоначчи в C» . Проверено 18 января 2007 г. Реализует описанный выше алгоритм (не оригинальный алгоритм Фергюсона).

[Ferguson1960-1] Jump up to: ^а ^б ^с Фергюсон, Дэвид Э. (1960). «Поиск Фибоначчиана» . Коммуникации АКМ . 3 (12): 648. дои : 10.1145/367487.367496 . S2CID 7982182 . Обратите внимание, что анализ времени выполнения в этой статье ошибочен, как указал Оверхолт в 1972 году (опубликовано в 1973 году).

[Overholt-2] Оверхолт, К.Дж. (1973). «Эффективность метода поиска Фибоначчи». БИТ Численная математика . 13 (1): 92–96. дои : 10.1007/BF01933527 . S2CID 120681132 .

[3] Кифер, Дж. (1953). «Последовательный минимаксный поиск максимума» . Труды Американского математического общества . 4 (3): 502–506. дои : 10.1090/S0002-9939-1953-0055639-3 .

[4] Кнут, Дональд Э. (2003). Искусство компьютерного программирования . Том. 3 (Второе изд.). п. 418.

[1]

[2]

[3]

[4]