Fibonacci search technique (original) (raw)
في علم الحاسوب، تقنية فيبوناتشي للبحث (بالإنجليزية: Fibonacci search technique) هي طريقة للبحث تمكن من ايجاد قيمة معينة في مستعملةً خوارزمية فرق تسد.
| Property | Value |
|---|---|
| dbo:abstract | في علم الحاسوب، تقنية فيبوناتشي للبحث (بالإنجليزية: Fibonacci search technique) هي طريقة للبحث تمكن من ايجاد قيمة معينة في مستعملةً خوارزمية فرق تسد. (ar) In computer science, the Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers. Compared to binary search where the sorted array is divided into two equal-sized parts, one of which is examined further, Fibonacci search divides the array into two parts that have sizes that are consecutive Fibonacci numbers. On average, this leads to about 4% more comparisons to be executed, but it has the advantage that one only needs addition and subtraction to calculate the indices of the accessed array elements, while classical binary search needs bit-shift (see Bitwise operation), division or multiplication, operations that were less common at the time Fibonacci search was first published. Fibonacci search has an average- and worst-case complexity of O(log n) (see Big O notation). The Fibonacci sequence has the property that a number is the sum of its two predecessors. Therefore the sequence can be computed by repeated addition. The ratio of two consecutive numbers approaches the Golden ratio, 1.618... Binary search works by dividing the seek area in equal parts (1:1). Fibonacci search can divide it into parts approaching 1:1.618 while using the simpler operations. If the elements being searched have non-uniform access memory storage (i. e., the time needed to access a storage location varies depending on the location accessed), the Fibonacci search may have the advantage over binary search in slightly reducing the average time needed to access a storage location. If the machine executing the search has a direct mapped CPU cache, binary search may lead to more cache misses because the elements that are accessed often tend to gather in only a few cache lines; this is mitigated by splitting the array in parts that do not tend to be powers of two. If the data is stored on a magnetic tape where seek time depends on the current head position, a tradeoff between longer seek time and more comparisons may lead to a search algorithm that is skewed similarly to Fibonacci search. Fibonacci search is derived from Golden section search, an algorithm by Jack Kiefer (1953) to search for the maximum or minimum of a unimodal function in an interval. (en) Пошук Фібоначчі (в інформатиці) — це метод пошуку за допомогою алгоритму «розділяй та владарюй», який звужує можливі місця за допомогою чисел Фібоначчі. Метод пошуку Фібоначчі походить від методу пошуку золотого перетину, алгоритму (1953) для пошуку максимуму або мінімуму в інтервалі. (uk) |
| dbo:wikiPageExternalLink | http://www.ics.forth.gr/~lourakis/fibsrch/ |
| dbo:wikiPageID | 8995012 (xsd:integer) |
| dbo:wikiPageLength | 6811 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1073794960 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Binary_search_algorithm dbr:Bitwise_operation dbr:Unimodal_function dbc:Search_algorithms dbr:Golden_ratio dbr:Magnetic_tape_data_storage dbr:Computer_science dbr:CPU_cache dbr:Fibonacci_number dbr:Jack_Kiefer_(statistician) dbr:Big_O_notation dbr:Divide_and_conquer_algorithm dbr:Golden_section_search dbr:Sorted_array dbr:Search_algorithms |
| dbp:wikiPageUsesTemplate | dbt:About dbt:Cite_web dbt:Technical |
| dcterms:subject | dbc:Search_algorithms |
| gold:hypernym | dbr:Method |
| rdf:type | dbo:Software yago:WikicatSearchAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | في علم الحاسوب، تقنية فيبوناتشي للبحث (بالإنجليزية: Fibonacci search technique) هي طريقة للبحث تمكن من ايجاد قيمة معينة في مستعملةً خوارزمية فرق تسد. (ar) Пошук Фібоначчі (в інформатиці) — це метод пошуку за допомогою алгоритму «розділяй та владарюй», який звужує можливі місця за допомогою чисел Фібоначчі. Метод пошуку Фібоначчі походить від методу пошуку золотого перетину, алгоритму (1953) для пошуку максимуму або мінімуму в інтервалі. (uk) In computer science, the Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers. Compared to binary search where the sorted array is divided into two equal-sized parts, one of which is examined further, Fibonacci search divides the array into two parts that have sizes that are consecutive Fibonacci numbers. On average, this leads to about 4% more comparisons to be executed, but it has the advantage that one only needs addition and subtraction to calculate the indices of the accessed array elements, while classical binary search needs bit-shift (see Bitwise operation), division or multiplication, operations that were less common at the time Fibonacci search was first publi (en) |
| rdfs:label | تقنية فيبوناتشي للبحث (ar) Fibonacci search technique (en) Пошук Фібоначчі (uk) |
| owl:sameAs | freebase:Fibonacci search technique yago-res:Fibonacci search technique wikidata:Fibonacci search technique dbpedia-ar:Fibonacci search technique dbpedia-fa:Fibonacci search technique dbpedia-sr:Fibonacci search technique dbpedia-th:Fibonacci search technique dbpedia-uk:Fibonacci search technique https://global.dbpedia.org/id/4ZqN3 |
| prov:wasDerivedFrom | wikipedia-en:Fibonacci_search_technique?oldid=1073794960&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Fibonacci_search_technique |
| is dbo:wikiPageRedirects of | dbr:Fibonacci_search dbr:Fibonaccian_search |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Fibonacci dbr:Fibonacci_number dbr:Golden-section_search dbr:Search_algorithm dbr:List_of_things_named_after_Fibonacci dbr:Fibonacci_search dbr:Fibonaccian_search |
| is foaf:primaryTopic of | wikipedia-en:Fibonacci_search_technique |