Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Пошук Фібоначчі в інформатиці це метод пошуку en за допомогою алгоритму розділяй та владарюй який звужує можливі місця з

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

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

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

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

Порівняно з двійковим пошуком, де відсортований масив розділений на дві однакові за розміром частини, одна з яких розглядається далі, алгоритм пошуку Фібоначчі ділить масив на дві частини, розмірами яких є послідовні числа Фібоначчі. В середньому це призводить до виконання приблизно на 4 % більшої кількості порівнянь, але його перевага в тому, що для обчислення індексів доступних елементів масиву потрібне лише додавання та віднімання, тоді як класичний двійковий пошук потребує бітового зсуву, ділення або множення, операції, які були менш поширеними на момент першої публікації пошуку Фібоначчі. Техніка пошуку Фібоначчі має середню та найвищу складність 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.

Альтернативна реалізація (з «Сортування та пошук» Кнута): Дана таблиця записів 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

Два варіанти алгоритму, представлені вище, завжди ділять поточний інтервал на більший і менший підінтервал. Хоча оригінальний алгоритм розділив би новий інтервал на менший і більший підінтервал на кроці 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.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Poshuk Fibonachchi v informatici ce metod poshuku en za dopomogoyu algoritmu rozdilyaj ta vladaryuj yakij zvuzhuye mozhlivi miscya za dopomogoyu chisel Fibonachchi Metod poshuku Fibonachchi pohodit vid metodu poshuku zolotogo peretinu algoritmu en 1953 dlya poshuku maksimumu abo minimumu unimodalnoyi funkciyi v intervali Porivnyalna harakteristika poshuku Fibonachchi ta dvijkovogo poshukuPorivnyano z dvijkovim poshukom de vidsortovanij masiv rozdilenij na dvi odnakovi za rozmirom chastini odna z yakih rozglyadayetsya dali algoritm poshuku Fibonachchi dilit masiv na dvi chastini rozmirami yakih ye poslidovni chisla Fibonachchi V serednomu ce prizvodit do vikonannya priblizno na 4 bilshoyi kilkosti porivnyan ale jogo perevaga v tomu sho dlya obchislennya indeksiv dostupnih elementiv masivu potribne lishe dodavannya ta vidnimannya todi yak klasichnij dvijkovij poshuk potrebuye bitovogo zsuvu dilennya abo mnozhennya operaciyi yaki buli mensh poshirenimi na moment pershoyi publikaciyi poshuku Fibonachchi Tehnika poshuku Fibonachchi maye serednyu ta najvishu skladnist O log n div Notaciya Landau Poslidovnist Fibonachchi maye taku vlastivist sho chislo ye sumoyu dvoh poperednikiv Tomu poslidovnist mozhe buti obchislena shlyahom povtornogo dodavannya Spivvidnoshennya dvoh poslidovnih chisel nablizhayetsya do Zolotogo peretinu 1 618 Binarnij poshuk pracyuye shlyahom rozdilennya oblasti poshuku na rivni chastini 1 1 Poshuk Fibonachchi mozhe rozdiliti jogo na chastini sho nablizhayutsya do 1 1 618 vikoristovuyuchi prostishi operaciyi Yaksho elementi sho shukayutsya mayut neodnoridne shovishe pam yati dostupu tobto chas neobhidnij dlya dostupu do shovisha zalezhit vid miscya do yakogo zdijsnyuyetsya dostup poshuk Fibonachchi mozhe mati perevagu pered dvijkovim poshukom desho zmenshivshi serednij chas neobhidnij dlya dostupu do miscya zberigannya Yaksho pristrij sho vikonuye poshuk maye kesh procesora z pryamim vidobrazhennyam dvijkovij poshuk mozhe prizvesti do bilshoyi kilkosti pomilok keshu oskilki elementi do yakih zdijsnyuyetsya dostup chasto mayut tendenciyu zbiratisya lishe v dekilkoh ryadkah keshu ce vipravlyayetsya shlyahom rozdilennya masivu na chastini yaki yak pravilo ne znahodyatsya v drugomu stepeni Yaksho dani zberigayutsya na magnitnij strichci de chas poshuku zalezhit vid potochnoyi poziciyi golovki to kompromis mizh dovshim chasom poshuku ta bilshoyu kilkistyu porivnyan mozhe prizvesti do zminenogo algoritmu poshuku analogichnogo do algoritmu poshuku Fibonachchi AlgoritmNehaj k viznachayetsya yak element u F masivi chisel Fibonachchi n F m rozmir masivu Yaksho n ne ye chislom Fibonachchi todi nehaj F m ye najmenshim chislom u masivi F yake perevishuye n Masiv chisel Fibonachchi viznachenij de F k 2 F k 1 F k koli k 0 F 1 1 a F 0 0 Dlya togo shob pereviriti chi ye element u spisku vporyadkovanih nomeriv vikonajte taki diyi Vstanovit k m Yaksho k 0 zupinitsya Nemaye zbigu element vidsutnij u masivi Porivnyajte element iz elementom u F k 1 Yaksho predmet vidpovidaye zupinitsya Yaksho element menshij nizh zapis F k 1 vidkinte elementi z pozicij F k 1 Vid 1 do n Vstanovit k k 1 i povernitsya do kroku 2 Yaksho element bilshij nizh F k 1 vidkinte elementi z pozicij 1 do F k 1 Perenumerujte reshtu elementiv vid 1 do F k 2 vstanovit k k 2 i povernitsya do kroku 2 Alternativna realizaciya z Sortuvannya ta poshuk Knuta Dana tablicya zapisiv R 1 R 2 R N klyuchi yakogo zrostayut u poryadku zrostannya K 1 lt K 2 lt lt K N algoritm zdijsnyuye poshuk zadanogo argumentu K Pripustimo N 1 F k 1 Krok 1 Inicializujte i F k p F k 1 q F k 2 v algoritmi p i q budut poslidovnimi chislami Fibonachchi Krok 2 Porivnyajte Yaksho K lt K i perejdit do kroku 3 yaksho K gt K i perejdit do kroku 4 i yaksho K K i algoritm zavershuyetsya uspishno Krok 3 Zmenshit i Yaksho q 0 algoritm zavershuyetsya nevdalo V inshomu vipadku vstanovlyuyetsya i p q i q q p q ce peremishuye p i q na odnu poziciyu nazad u poslidovnosti Fibonachchi potim povernitsya do kroku 2 Krok 4 Zbilshit i Yaksho p 1 algoritm zavershuyetsya nevdalo V inshomu vipadku vstanovit i p q i q p q 2q p ce peremishuye p i q na dvi poziciyi nazad u poslidovnosti Fibonachchi i povernitsya do kroku 2 Dva varianti algoritmu predstavleni vishe zavzhdi dilyat potochnij interval na bilshij i menshij pidinterval Hocha originalnij algoritm rozdiliv bi novij interval na menshij i bilshij pidinterval na kroci 4 vin maye tu zh samu perevagu sho i novij ta znahoditsya blizhche do starogo i bilshe pidhodit dlya priskorennya poshuku na magnitnij strichci Div takozhAlgoritmi poshukuPrimitkiKiefer J 1953 Sequential minimax search for a maximum Proc American Mathematical Society 4 502 506 doi 10 1090 S0002 9939 1953 0055639 3 Ferguson David E 1960 Fibonaccian searching Communications of the ACM 3 12 648 doi 10 1145 367487 367496 Overholt K J 1973 Efficiency of the Fibonacci search method BIT Numerical Mathematics 13 1 92 96 doi 10 1007 BF01933527 Knuth Donald E 2003 The Art of Computer Programming T vol 3 vid Second s 418

Дата публікації:
Топ