stringtranslate.com

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

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

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

Дана таблица записей R 1 , R 2 , ..., R N , ключи которой расположены в порядке возрастания K 1 < K 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 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 , 2 q − p ) (что перемещает p и q на две позиции назад в последовательности Фибоначчи); и вернитесь к шагу 2

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

Смотрите также

Ссылки

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