Lineær søgning

Lineær, sekventiel søgning  er en algoritme til at finde en given værdi af en vilkårlig funktion på et bestemt interval. Denne algoritme er den enkleste søgealgoritme og lægger i modsætning til for eksempel binær søgning ingen begrænsninger på funktionen og har den enkleste implementering. Søgningen efter en funktionsværdi udføres ved blot at sammenligne den næste værdi under overvejelse (som regel foregår søgningen fra venstre mod højre, det vil sige fra mindre værdier af argumentet til større) og, hvis værdierne match (med en eller anden nøjagtighed), så anses søgningen for at være afsluttet.

Hvis segmentet har længde N, så er det muligt at finde løsningen op til inden for tiden . At. den asymptotiske kompleksitet af algoritmen  er . På grund af dens lave effektivitet sammenlignet med andre algoritmer, bruges lineær søgning normalt kun, hvis søgesegmentet indeholder meget få elementer, dog kræver lineær søgning ikke yderligere hukommelse eller funktionsbehandling/analyse, så det kan fungere i streaming-tilstand, når der opnås direkte data fra enhver kilde. Også lineær søgning bruges ofte i form af lineære maksimum/minimum søgealgoritmer.

Som et eksempel kan vi overveje søgningen efter værdien af ​​en funktion på sættet af heltal præsenteret i en tabel.

Eksempel

Variabler og indeholder henholdsvis venstre og højre grænser for array-segmentet, hvor det element, vi skal bruge, er placeret. Forskning begynder med det første element i segmentet. Hvis den søgte værdi ikke er lig med værdien af ​​funktionen på det givne punkt, så udføres overgangen til det næste punkt. Det vil sige, at som et resultat af hver kontrol reduceres søgeområdet med et element.

Et eksempel i Swift 3, med "accelereret" søgning:

func linearSearch ( element : Int , i matrix : [ Int ]) -> Int ? { var array = array lad realLastElement : Int ? hvis array . er tom { retur nul } andet { realLastElement = matrix [ matrix . tælle - 1 ] matrix [ matrix . tælle - 1 ] = element } var i = 0 ; while array [ i ] != element { i += 1 ; } lad findedElement = array [ i ]; hvis i == array . antal - 1 && foundedElement != realLastElement { retur nul } andet { returnere i } }

Analyse

For en liste med n elementer er det bedste tilfælde et, hvor den værdi, du leder efter, er lig med det første element på listen, og kun én sammenligning er påkrævet. Det værste tilfælde er, når der ikke er nogen værdi i listen (eller det er helt til sidst på listen), i hvilket tilfælde n sammenligninger er nødvendige.

Hvis den ønskede værdi er på listen k gange, og alle forekomster er lige sandsynlige, er det forventede antal sammenligninger

For eksempel, hvis den ønskede værdi forekommer på listen én gang, og alle forekomster er lige sandsynlige, så er det gennemsnitlige antal sammenligninger . Men hvis det er kendt , at det forekommer én gang, så er n  - 1 sammenligninger nok, og det gennemsnitlige antal sammenligninger vil være lig med

(for n = 2 er dette tal 1, hvilket svarer til én hvis-så-andet-konstruktion).

I begge tilfælde er den beregningsmæssige kompleksitet af algoritmen O ( n ).

Ansøgninger

Generelt er en lineær søgning meget enkel at implementere og er anvendelig, når listen indeholder få elementer, eller i tilfælde af en enkelt søgning i en uordnet liste.

Hvis den samme liste formodes at blive søgt et stort antal gange, så giver det ofte mening at forbehandle listen, såsom at sortere og derefter bruge en binær søgning eller bygge en effektiv datastruktur til søgningen. Hyppig ændring af listen kan også påvirke valget af yderligere handlinger, da det nødvendiggør processen med at omstrukturere strukturen.

Se også

• Binær søgning
• dikotomi metode
• gyldne snit metode
• Ternær søgning
• råstyrke

Litteratur

• Donald Knuth . The Art of Computer Programming, bind 3. Sortering og søgning = The Art of Computer Programming, vol.3. Sortering og søgning. - 2. udg. - M . : "Williams" , 2007. - S. 824. - ISBN 0-201-89685-0 .