Lineární vyhledávání - Linear search

Lineární vyhledávání
Třída	Vyhledávací algoritmus
Nejhorší případ výkon	Ó(n)
Nejlepší případ výkon	Ó(1)
Průměrný výkon	Ó(n / 2)
Nejhorší případ složitost prostoru	Ó(1) iterativní

v počítačová věda, a lineární vyhledávání nebo sekvenční vyhledávání je metoda pro vyhledání prvku v a seznam. Postupně kontroluje každý prvek seznamu, dokud není nalezena shoda nebo není prohledán celý seznam.^[1]

V nejhorším případě se spustí lineární vyhledávání lineární čas a dělá nanejvýš $n$ srovnání, kde $n$ je délka seznamu. Pokud je stejně pravděpodobné, že bude prohledán každý prvek, má lineární vyhledávání průměrný případ $.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px;white-space:nowrap} n + 1 / 2$ srovnání, ale průměrný případ může být ovlivněn, pokud se pravděpodobnost vyhledávání pro každý prvek liší. Lineární vyhledávání je zřídka praktické, protože jiné vyhledávací algoritmy a schémata, například binární vyhledávací algoritmus a hash tabulky, umožňují výrazně rychlejší vyhledávání všech seznamů kromě krátkých.^[2]

Algoritmus

Lineární vyhledávání postupně kontroluje každý prvek seznamu, dokud nenajde prvek, který odpovídá cílové hodnotě. Pokud algoritmus dosáhne konce seznamu, hledání bude neúspěšně ukončeno.^[1]

Základní algoritmus

Vzhledem k seznamu $L$ z $n$ prvky s hodnotami nebo evidence $L 0 .... L n -1$ a cílová hodnota $T$ , následující podprogram používá lineární vyhledávání k nalezení indexu cíle $T$ v $L$ .^[3]

Soubor $i$ na 0.
Li $L i = T$ , hledání je úspěšně ukončeno; vrátit se $i$ .
Zvýšit $i$ o 1.
Li $i < n$ , přejděte ke kroku 2. Jinak bude hledání neúspěšně ukončeno.

S hlídkou

Výše uvedený základní algoritmus provádí dvě srovnání na jednu iteraci: jedno pro kontrolu, zda $L i$ rovná se Ta druhý zkontrolovat, zda $i$ stále ukazuje na platný index seznamu. Přidáním dalšího záznamu $L n$ do seznamu (a sentinelová hodnota ), který se rovná cíli, lze druhé srovnání eliminovat až do konce hledání, čímž se algoritmus zrychlí. Hledání nebude zasláno, pokud cíl není uveden v seznamu.^[4]

Soubor $i$ na 0.
Li $L i = T$ , přejděte ke kroku 4.
Zvýšit $i$ o 1 a přejděte ke kroku 2.
Li $i < n$ , hledání je úspěšně ukončeno; vrátit se $i$ . Jinak hledání skončí neúspěšně.

V objednané tabulce

Pokud je seznam seřazen tak, že $L 0 \leq L 1 ... \leq L n -1$ , vyhledáním lze rychleji zjistit nepřítomnost cíle jednorázovým ukončením hledání $L i$ překračuje cíl. Tato variace vyžaduje indikátor, který je větší než cíl.^[5]

Soubor $i$ na 0.
Li $L i \geq T$ , přejděte ke kroku 4.
Zvýšit $i$ o 1 a přejděte ke kroku 2.
Li $L i = T$ , hledání je úspěšně ukončeno; vrátit se $i$ . Jinak hledání skončí neúspěšně.

Analýza

Seznam s n položek, nejlepší je, když se hodnota rovná prvnímu prvku seznamu, v takovém případě je potřeba pouze jedno srovnání. Nejhorší případ je, když hodnota není v seznamu (nebo se na konci seznamu objeví jen jednou), v takovém případě n jsou nutná srovnání.

Pokud nastane hledaná hodnota k časy v seznamu a všechna pořadí v seznamu jsou stejně pravděpodobná, očekávaný počet srovnání je

{ displaystyle { begin {cases} n & { mbox {if}} k = 0 [5pt] displaystyle { frac {n + 1} {k + 1}} & { mbox {if}} 1 leq k leq n. end {případy}}}

Pokud se například hledaná hodnota v seznamu vyskytne jednou a všechna pořadí v seznamu jsou stejně pravděpodobná, očekávaný počet srovnání je ${ displaystyle { frac {n + 1} {2}}}$ . Pokud ano známý že k ní dojde jednou, nanejvýš n - Je zapotřebí 1 srovnání a očekávaný počet srovnání je

{ displaystyle displaystyle { frac {(n + 2) (n-1)} {2n}}}

(například pro n = 2 toto je 1, což odpovídá jednomu konstruktu if-then-else).

Ať tak či onak, asymptoticky nejhorší náklady a očekávané náklady na lineární vyhledávání jsou oba Ó (n).

Nejednotné pravděpodobnosti

Výkon lineárního vyhledávání se zlepšuje, pokud je požadovaná hodnota pravděpodobněji na začátku seznamu než na jeho konci. Pokud jsou tedy některé hodnoty mnohem pravděpodobnější, že budou prohledány, než jiné, je žádoucí je umístit na začátek seznamu.

Zejména když jsou položky seznamu uspořádány v pořadí podle klesající pravděpodobnosti a tyto pravděpodobnosti jsou geometricky rozloženo, cena lineárního vyhledávání je pouze O (1). ^[6]

aplikace

Implementace lineárního vyhledávání je obvykle velmi jednoduchá a je praktická, když seznam obsahuje jen několik prvků, nebo když provádíte jediné vyhledávání v neuspořádaném seznamu.

Když je třeba ve stejném seznamu hledat mnoho hodnot, často se vyplatí seznam předem zpracovat, aby bylo možné použít rychlejší metodu. Například jeden může třídit seznam a použít binární vyhledávání, nebo vybudovat efektivní struktura dat vyhledávání z toho. Pokud by se obsah seznamu často měnil, může být opakovaná reorganizace více potíží, než za jakou stojí.

Výsledkem je, že i když teoreticky mohou být jiné vyhledávací algoritmy rychlejší než lineární vyhledávání (například binární vyhledávání ), v praxi ani na středních polích (kolem 100 položek nebo méně) by bylo nemožné použít cokoli jiného. Na větších polích má smysl použít jiné, rychlejší metody vyhledávání, pouze pokud jsou data dostatečně velká, protože počáteční čas na přípravu (řazení) dat je srovnatelný s mnoha lineárními vyhledáváními.^[7]

Viz také

Reference

Citace

^ ^A ^b Knuth 1998, §6.1 („Sekvenční vyhledávání“).
^ Knuth 1998, §6.2 ("Hledání podle srovnání klíčů").
^ Knuth 1998, §6.1 („Sekvenční vyhledávání“), pododdíl „Algoritmus B“.
^ Knuth 1998, §6.1 („Sekvenční vyhledávání“), pododdíl „Algoritmus Q“.
^ Knuth 1998, §6.1 („Sekvenční vyhledávání“), pododdíl „Algoritmus T“.
^ Knuth, Donald (1997). "Část 6.1: Sekvenční vyhledávání,". Třídění a vyhledávání. Umění počítačového programování. 3 (3. vyd.). Addison-Wesley. 396–408. ISBN 0-201-89685-0.
^ Horvath, Adam. „Binární vyhledávání a výkon lineárního vyhledávání na platformě .NET a Mono“. Citováno 19. dubna 2013.

Funguje

Knuth, Donald (1998). Třídění a vyhledávání. Umění počítačového programování. 3 (2. vyd.). Reading, MA: Addison-Wesley Professional.CS1 maint: ref = harv (odkaz) ISBN 0-201-89685-0

[FOOTNOTEKnuth1998§6.1_("Sequential_search")-1] A ^b Knuth 1998, §6.1 („Sekvenční vyhledávání“).

[FOOTNOTEKnuth1998§6.2_("Searching_by_Comparison_Of_Keys")-2] Knuth 1998, §6.2 ("Hledání podle srovnání klíčů").

[FOOTNOTEKnuth1998§6.1_("Sequential_search"),_subsection_"Algorithm_B"-3] Knuth 1998, §6.1 („Sekvenční vyhledávání“), pododdíl „Algoritmus B“.

[FOOTNOTEKnuth1998§6.1_("Sequential_search"),_subsection_"Algorithm_Q"-4] Knuth 1998, §6.1 („Sekvenční vyhledávání“), pododdíl „Algoritmus Q“.

[FOOTNOTEKnuth1998§6.1_("Sequential_search"),_subsection_"Algorithm_T"-5] Knuth 1998, §6.1 („Sekvenční vyhledávání“), pododdíl „Algoritmus T“.

[knuth-6] Knuth, Donald (1997). "Část 6.1: Sekvenční vyhledávání,". Třídění a vyhledávání. Umění počítačového programování. 3 (3. vyd.). Addison-Wesley. 396–408. ISBN 0-201-89685-0.

[7] Horvath, Adam. „Binární vyhledávání a výkon lineárního vyhledávání na platformě .NET a Mono“. Citováno 19. dubna 2013.

[1]

[2]

[3]

[4]

[5]

[6]

[7]