Пошук Фібоначчі

Пошук Фібоначчі (в інформатиці) — це метод пошуку відсортованого масиву за допомогою алгоритму «розділяй та владарюй», який звужує можливі місця за допомогою чисел Фібоначчі. Метод пошуку Фібоначчі походить від методу пошуку золотого перетину, алгоритму Джека Кіфера (1953) для пошуку максимуму або мінімуму унімодальної функції в інтервалі.[1]

Порівняльна характеристика пошуку Фібоначчі та двійкового пошуку

[2] Порівняно з двійковим пошуком, де відсортований масив розділений на дві однакові за розміром частини, одна з яких розглядається далі, алгоритм пошуку Фібоначчі ділить масив на дві частини, розмірами яких є послідовні числа Фібоначчі. В середньому це призводить до виконання приблизно на 4 % більшої кількості порівнянь,[3] але його перевага в тому, що для обчислення індексів доступних елементів масиву потрібне лише додавання та віднімання, тоді як класичний двійковий пошук потребує бітового зсуву, ділення або множення, операції, які були менш поширеними на момент першої публікації пошуку Фібоначчі. Техніка пошуку Фібоначчі має середню та найвищу складність O (log n) (див. Нотація Ландау).

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

Якщо елементи, що шукаються, мають неоднорідне сховище пам'яті доступу (тобто час, необхідний для доступу до сховища, залежить від місця, до якого здійснюється доступ), пошук Фібоначчі може мати перевагу перед двійковим пошуком, дещо зменшивши середній час, необхідний для доступу до місця зберігання. Якщо пристрій, що виконує пошук, має кеш процесора з прямим відображенням, двійковий пошук може призвести до більшої кількості помилок кешу, оскільки елементи, до яких здійснюється доступ, часто мають тенденцію збиратися лише в декількох рядках кешу; це виправляється шляхом розділення масиву на частини, які, як правило, не знаходяться в другому степені. Якщо дані зберігаються на магнітній стрічці, де час пошуку залежить від поточної позиції головки, то компроміс між довшим часом пошуку та більшою кількістю порівнянь може призвести до зміненого алгоритму пошуку, аналогічного до алгоритму пошуку Фібоначчі.

Алгоритм

Нехай 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.

Альтернативна реалізація (з «Сортування та пошук» Кнута[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, 2q — p) (це переміщує p і q на дві позиції назад у послідовності Фібоначчі); і поверніться до кроку 2

Два варіанти алгоритму, представлені вище, завжди ділять поточний інтервал на більший і менший підінтервал. Хоча оригінальний алгоритм[2] розділив би новий інтервал на менший і більший підінтервал на кроці 4, він має ту ж саму перевагу, що і новий та знаходиться ближче до старого і більше підходить для прискорення пошуку на магнітній стрічці.

Див. також

Примітки
  1. Kiefer, J. (1953). Sequential minimax search for a maximum. Proc. American Mathematical Society 4: 502–506. doi:10.1090/S0002-9939-1953-0055639-3.
  2. Ferguson, David E. (1960). Fibonaccian searching. Communications of the ACM 3 (12): 648. doi:10.1145/367487.367496.
  3. Overholt, K. J. (1973). Efficiency of the Fibonacci search method. BIT Numerical Mathematics 13 (1): 92–96. doi:10.1007/BF01933527.
  4. Knuth, Donald E. (2003). The Art of Computer Programming. vol. 3 (вид. Second). с. 418.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.