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

Lineární vyhledávání

Třída	Algoritmus vyhledávání
Nejhorší výkon	O ( n )
Nejlepší výkon	O (1)
Průměrný výkon	O ( n/2 )
Nejhorší prostorová složitost	O (1) iterativní

V počítačové vědě je lineární vyhledávání nebo sekvenční vyhledávání metodou pro nalezení prvku v seznamu . Postupně kontroluje každý prvek seznamu, dokud není nalezena shoda nebo nebyl prohledán celý seznam.

Lineární vyhledávání probíhá v nejhorším lineárním čase a provádí n nejvíce srovnání, kde n je délka seznamu. Pokud je pravděpodobné, že bude prohledán každý prvek, pak má lineární vyhledávání průměrný případ n+1/2srovnání, ale průměrný případ může být ovlivněn, pokud se pravděpodobnosti 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, jako jsou binární vyhledávací algoritmus a hashovací tabulky , umožňují výrazně rychlejší vyhledávání všech kromě krátkých seznamů.

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í se neúspěšně ukončí.

Základní algoritmus

Vzhledem k tomu, seznam L o n prvků s hodnotami či záznamů L ₀ .... L _{n -1} a cílové hodnoty T , následující podprogramu použití lineární hledání najít index cílové T v L .

1. Nastavte i na 0.
2. Pokud L _i = T , hledání úspěšně skončí; vrátit i .
3. Zvyšte i o 1.
4. Pokud i < n , přejděte ke kroku 2. V opačném případě hledání skončí neúspěšně.

S hlídkou

Výše uvedený základní algoritmus provádí dvě srovnání za iteraci: jedno pro kontrolu, zda se L _i rovná T , a druhé pro kontrolu, zda i stále ukazuje na platný rejstřík seznamu. Přidáním dalšího záznamu L _n do seznamu ( hodnota sentinelu ), který se rovná cíli, lze druhé srovnání eliminovat až do konce hledání, čímž se algoritmus zrychlí. Pokud cíl není uveden v seznamu, vyhledávání se dostane na hlídku.

1. Nastavte i na 0.
2. Pokud L _i = T , přejděte ke kroku 4.
3. Zvyšte i o 1 a přejděte ke kroku 2.
4. Pokud i < n , hledání úspěšně skončí; vrátit i . Jinak hledání neúspěšně skončí.

V objednaném stole

Pokud je seznam seřazen tak, že L ₀ ≤ L ₁ ... ≤ L _{n −1} , může vyhledávání rychleji zjistit nepřítomnost cíle tím, že vyhledávání skončí, jakmile L _i překročí cíl. Tato variace vyžaduje sentinel, který je větší než cíl.

1. Nastavte i na 0.
2. Pokud L _i ≥ T , přejděte ke kroku 4.
3. Zvyšte i o 1 a přejděte ke kroku 2.
4. Pokud L _i = T , hledání úspěšně skončí; vrátit i . Jinak hledání neúspěšně skončí.

Analýza

U seznamu s n položkami je nejlepším případem, když se hodnota rovná prvnímu prvku seznamu, v takovém případě stačí pouze jedno srovnání. Nejhorší je, když hodnota není v seznamu (nebo se vyskytuje pouze jednou na konci seznamu), v takovém případě je potřeba n srovnání.

Dojde-li hodnota žádá K časů v seznamu a všechny orderings ze seznamu jsou stejně pravděpodobné, že se očekává, že počet porovnání se

${\ 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 objeví v seznamu jednou a všechna seřazení v seznamu jsou stejně pravděpodobná, očekávaný počet srovnání je . Je -li však známo, že k němu dojde jednou, pak je zapotřebí maximálně n - 1 srovnání a očekávaný počet srovnání je ${\ displaystyle {\ frac {n+1} {2}}}$

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

(například pro n = 2 je to 1, což odpovídá jedné konstrukci if-then-else).

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

Nejednotné pravděpodobnosti

Výkon lineárního vyhledávání se zlepší, pokud je požadovaná hodnota pravděpodobněji blízko začátku seznamu než jeho konce. Pokud je tedy u některých hodnot mnohem pravděpodobnější, že budou vyhledávány než u jiných, je žádoucí je umístit na začátek seznamu.

Zejména když jsou položky seznamu uspořádány v pořadí klesající pravděpodobnosti a tyto pravděpodobnosti jsou geometricky rozloženy , náklady na lineární vyhledávání jsou pouze O (1).

aplikace

Lineární vyhledávání je obvykle velmi jednoduché implementovat a je praktické, když seznam obsahuje pouze 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 lze seznam seřadit a použít binární vyhledávání , nebo z něj vytvořit efektivní strukturu vyhledávacích dat . Pokud se obsah seznamu často mění, může být opakovaná reorganizace větším problémem, než by stálo za to.

V důsledku toho, 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 dokonce na středně velkých polích (kolem 100 položek nebo méně) může být nemožné použít cokoli jiného. Na větších polích má smysl používat jiné, rychlejší vyhledávací metody, pouze pokud jsou data dostatečně velká, protože počáteční čas na přípravu (třídění) dat je srovnatelný s mnoha lineárními vyhledáváními.

Viz také

• Ternární hledání
• Hash stůl
• Problém lineárního vyhledávání

Reference

Citace

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. ISBN  0-201-89685-0