Lineáris keresés

A lineáris, szekvenciális keresés egy algoritmus egy tetszőleges függvény adott értékének megtalálására egy bizonyos intervallumon. Ez az algoritmus a legegyszerűbb keresési algoritmus, és ellentétben például a bináris kereséssel , nem szab semmilyen korlátozást a függvényre, és a legegyszerűbb megvalósítása. A függvényérték keresése a következő figyelembe vett érték egyszerű összehasonlításával történik (a keresés általában balról jobbra történik, vagyis az argumentum kisebb értékeitől a nagyobbakig), és ha az értékek egyezést (ilyen vagy olyan pontossággal), akkor a keresés befejezettnek minősül.

Ha a szakasz N hosszúságú, akkor időn belül meg lehet találni a megoldást . Hogy. az algoritmus aszimptotikus összetettsége . A többi algoritmushoz képest alacsony hatékonysága miatt a lineáris keresést általában csak akkor alkalmazzák, ha a keresési szegmens nagyon kevés elemet tartalmaz, azonban a lineáris keresés nem igényel további memóriát vagy függvényfeldolgozást/elemzést, így közvetlen beszerzéskor streaming módban is működhet. adatok bármilyen forrásból. A lineáris keresést gyakran használják lineáris maximum/minimum keresési algoritmusok formájában. $\epsilon$ ${N \over \epsilon }$ $Tovább)$

Példaként tekinthetjük egy függvény értékének keresését a táblázatban bemutatott egész számok halmazán.

Példa

A és változók a tömbszegmens bal és jobb oldali határait tartalmazzák, ahol a szükséges elem található. A kutatás a szegmens első elemével kezdődik. Ha a keresett érték nem egyenlő a függvény értékével az adott pontban, akkor a következő pontra való áttérés történik. Azaz minden ellenőrzés eredményeként a keresési terület egy elemmel csökken. $L$ $R$

int függvény Lineáris Keresés(A tömb, int L, int R, int kulcs); kezdődik ha X = L-től R-ig tegyük ha A[X] = kulcs, akkor vissza X visszatérés -1; // elem nem található vége;

Példa a Swift 3-ban, "gyorsított" kereséssel:

func linearSearch ( elem : Int , tömbben : [ Int ]) - > Int ? { var array = tömb let realLastElement : Int ? ha tömb . isEmpty { vissza nulla } másik { realLastElement = tömb [ tömb . szám - 1 ] array [ array . count - 1 ] = elem } var i = 0 ; while array [ i ] != elem { i += 1 ; } legyen findedElement = tömb [ i ]; ha i == tömb . count - 1 && foundedElement != realLastElement { vissza nulla } másik { vissza i } }

Elemzés

Egy n elemből álló lista esetén a legjobb eset az, amikor a keresett érték megegyezik a lista első elemével, és csak egy összehasonlítás szükséges. A legrosszabb eset az, ha nincs érték a listában (vagy a lista legvégén van), ilyenkor n összehasonlításra van szükség.

Ha a kívánt érték k - szer szerepel a listában, és minden előfordulás egyformán valószínű, akkor az összehasonlítások várható száma

{\begin{cases}n&k=0\\[5pt]\displaystyle {\frac {n+1}{k+1}}&1\leq k\leq n.\end{cases}}

Például, ha a kívánt érték egyszer szerepel a listában, és minden előfordulás egyformán valószínű, akkor az összehasonlítások átlagos száma . Ha azonban tudjuk , hogy egyszer előfordul, akkor n - 1 összehasonlítás elegendő, és az összehasonlítások átlagos száma egyenlő lesz ${\frac {n+1}{2))$

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

( n = 2 esetén ez a szám 1, ami egy if-then-else konstrukciónak felel meg).

Mindkét esetben az algoritmus számítási bonyolultsága O ( n ).

Alkalmazások

A lineáris keresés általában nagyon egyszerűen megvalósítható, és akkor alkalmazható, ha a lista kevés elemet tartalmaz, vagy egyetlen keresés esetén egy rendezetlen listában.

Ha ugyanabban a listában többször kell keresni, akkor gyakran van értelme a listát előfeldolgozni, például rendezni , majd bináris keresést használni , vagy valamilyen hatékony adatszerkezetet felépíteni a kereséshez. A lista gyakori módosítása a további intézkedések megválasztását is befolyásolhatja, mivel szükségessé teszi a struktúra átalakításának folyamatát.

Lásd még

Irodalom

Donald Knuth . The Art of Computer Programming, Volume 3. Sorting and Searching = The Art of Computer Programming, vol.3. Rendezés és keresés. - 2. kiadás - M . : "Williams" , 2007. - S. 824. - ISBN 0-201-89685-0 .