Linearna pretraga

Linearna pretraga

Klasa	Algoritam sortiranja
Struktura podataka	Niz
Najgora performanca	$O(n)$
Najbolja performanca	$O(n)$
Najgora prostorna kompleksnost	$O(n)$

U računarstvu, linearna pretraga ili sekvencijalna pretraga je metoda za pronalaženje određene vrednosti u listi koja proverava svaki element u nizu (listi) dok se željeni element ne pronađe ili dok se ne prođe cela lista. Lista ne mora biti sortirana.

Linearna pretraga je najjednostavniji algoritam pretrage; to je poseban slučaj iscrpljujuće pretrage. U najgorem slučaju, složenost je proporcionalna broju elemenata u listi. Njegova očekivana složenost je takođe proporcionalna broju elemenata ako se svi elementi podjednako pretražuju. Ako lista ima više od nekoliko elemenata i često se pretražuje, onda složenije metode pretrage, kao što su binarna pretraga ili heširanje, mogu da budu prikladnije. Ove metode imaju bržu pretragu, ali zahtevaju dodatne resurse da postignu tu brzinu.

Analiza

Za listu sa n elementima, najbolji slučaj je kada je vrednost jednaka prvom elementu liste, jer je u tom slučaju potrebno samo jedno poređenje. Najgori slučaj je kada vrednost nije u listi (ili se javlja samo jednom na kraju liste), i u tom slučaju je potrebno n poređenja.

Ako se tražena vrednost javlja k puta u listi, i sva uređivanja liste su podjednako moguća, očekivani broj poređenja je

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

Na primer, ako se tražena vrednost pojavljuje dva puta u listi, i sva uređivanja liste su podjednako moguća, očekivani broj poređenja je ${\frac {n+1}{2}}$. Međutim, ako je poznato da se tražena vrednost jednom pojavljuje, tada je najviše n - 1 poređenja potrebno, a očekivani broj poređenja je

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

(na primer, za n = 2 rezultat je 1, što odgovara jednom ,,if-then-else" konstruktoru).

U svakom slučaju, asimptotski najgori slučaj složenosti i očekivana složenost linearne pretrage su O(n).

Raznovrsne verovatnoće

Performanse linearne pretrage se poboljšavaju ako je željena vrednost bliže početku liste nego pri kraju. Dakle, ako se neke vrednosti traže više u odnosu na druge, poželjno je postaviti ih na početak liste.

Posebno, kada su elementi liste raspoređeni opadajućom verovatnoćom, i ove verovatnoće se geometrijski distribuiraju, složenost linearne pretrage je samo O(1). Ako je veličina liste n dovoljno velika, linearna pretraga će biti brža od binarne pretrage, čija je složenost O(log n).

Aplikacija

Linearna pretraga je obično veoma jednostavna za implementaciju i praktična kada lista ima samo nekoliko elemenata, ili prilikom obavljanja jedne pretrage neuređene liste.

Kada više vrednosti treba da se pretraže u istoj listi, često se isplati da se reorganizuje lista kako bi se iskoristile brže metode. Na primer, sortiranje liste i upotreba binarne pretrage, ili izgradnja bilo kakve efikasne strukture pretrage podataka iz njega. Ako se elementi liste često menjaju, ponovljena reorganizacija može doneti više problema nego koristi.

Kao rezultat toga, iako u teoriji drugi algoritmi pretraa mogu biti brži od linearne pretrage (primer binarna pretraga), u praksi čak i na srednjim nizovima (oko 100 predmeta ili manje) je možda neizvodljivo da se koristi bilo šta drugo. Na većim nizovima, razumno je koristiti druge, brže metode pretrage ako su podaci dovoljno veliki, jer početno vreme da se samo pripreme (sortiraju) podaci može se uporediti sa mnogim linearnim pretragama.

Pseudokod

Napredno ponavljanje

Ovaj pseudokod opisuje tipičnu varijantu linearne pretrage, u kojoj bi rezultat pretrage trebalo da bude bilo lokacija elementa iz liste u kojoj je nađena željena vrednost; ili pogrešna lokacija Λ, da ukaže da se željeni element ne pojavljuje u listi.

Za svaki elemen u listi:

ako taj element ima željenu vrednost,

zaustavi pretragu i vrati lokaciju elementa.

Vrati Λ.

U ovom pseudokodu, poslednja linija je izvršena samo u slučaju da za svaki ispitani element nije pronađeno podudaranje.

Ako je lista sačuvana kao niz (struktura podataka), lokacija može biti indeks nađene stavke (obično između 1 i n, ili 0 i n-1). U tom slučaju nevažeća lokacija Λ može biti indeks pre prvog elementa (kao što je 0 ili -1) ili posle poslednjeg (n+1 ili n).

Ako je lista jednostavna povezana lista, onda lokacija elementa je njegova referenca, i Λ je obično nulti pokazivač.

Rekurzivna verzija

Linearna pretraga takođe može biti opisana kao rekurzivni algoritam:

LinearnaPretraga (vrednost, lista)

ako je lista prazna, vrati Λ;

u suprotnom

ako prvi element liste ima željenu vrednost, vrati njegovu lokaciju;

u suprotnom vrati LinearnaPretraga (vrednost, ostatak liste)

Pretraga u obrnutom redosledu

Linearna pretraga niza je obično programirana ubrzanjem indeksa promenljive dok ne dođe do zadnjeg indeksa. Ovo obično zahteva dva skupa poređenja za svaki element liste: jedan da proveri da li je indeks dostigao kraj niza, a drugi da proveri da li element ima željenu vrednost. U mnogim računarima, može se smanjiti rad prvog poređenja pretraživanjem elemenata obrnutim redosledom.

Pretpostavimo da se niz A sa elementima indeksiranim od 1 do n pretražuje za vrednost x. Sledeći pseudokod obavlja naprednu pretragu, vraćajući n + 1 ako vrednost nije pronađena:

 Постави i на 1.
 Понови ову петљу:
     Ако је i > n, онда изађи из петље.
     Ако је A[i] = x, онда изађи из петље.
     Постави i на i + 1.
 Врати i.

Sledeći pseudokod pretražuje niz u obrnutom redosledu, vraćajući 0 ako element nije pronađen:

 Постави i за n.
 Понови ову петљу:
     Ако је i ≤ 0, онда изађи из петље.
     Ако је A[i] = x, онда изађи из петље.
     Постави i на i − 1.
 Врати i.

Većina računara ima uslovnu granu instrukcija koje testiraju znak vrednosti u registru, ili znak rezultata najskorije aritmetičke operacije. Može se koristiti ta instrukcija, koja je obično brža nego poređenje sa nekom proizvoljnom vrednošću (zahteva oduzimanje), da sprovede komandu "Ako je ≤ 0, onda izađi iz petlje".

Ovu optimizaciju je lako implementirati prilikom mašinskog programiranja ili u asembleru. Ta grana instrukcija nije direktno dostupna u tipičnim programskim jezicima visokog nivoa, iako će mnogi kompajleri biti u stanju da obave tu optimizaciju sami.

Upotreba kontrole

Drugi način da se dodatno smanji je da se eliminišu sve provere indeksa petlje. Ovo se može uraditi ubacivanjem samog željenog elementa kao kontrolne vrednosti na samom kraju liste, kao u ovom pseudokodu:

Postavi A[n + 1] na x.

Postavi i na 1.

Ponovi ovu petlju:

Ako je A[i] = x, onda izađi iz petlje.

Postavi i na i + 1.

Vrati i.

Sa ovom strategijom, nije neophodno da se proveri vrednost i sa listom dužine n: čak i ako x nije nađen u A na početku, petlja će prekinuti kada je i = n + 1. Međutim, ova metoda je moguća samo ako mesto u nizu A[n + 1] postoji, ali se ne koristi drugačije. Sličnija uređenja mogu biti ako se niz pretražuje obrnutim redosledom, i element A(0) je dostupan.

Iako je napor izbegnut zahvaljujući ovim malim radom, ipak je značajna komponenta dodatnog obavljanja svakog koraka pretrage, koja je mala. Samo ako je mnogo elemenata verovatno da će se uporediti biće od koristi s obzirom metode koje čine manje poređenja, ali nameću druge uslove.

Linearna pretraga uređene liste

Za uređene liste koje moraju biti pristupane redom, kao što su povezane liste ili fajlovi sa promenljivom dužinom evidencije koji nemaju indeks, prosečne performanse se mogu poboljšati odustajanjem na prvom elementu koji je veći od nedostižne ciljane vrednosti, nego pregledali celu listu.

Ako je lista sačuvana kao uređen niz, onda je binarna pretraga skoro uvek efikasnija nego linearna pretraga kao sa n > 8, recimo, osim ako ne postoji razlog da se pretpostavi da će većina pretrage biti za male elemente blizu početka sortirane liste.

Implementacija

Ovaj algoritam ima najjednostavniju implementaciju u svim programskim jezicima.

Pseudo kod:

int LinearSort(int a[100],int n,int trazeniBroj) {
 int i;
 for(i=0;i<n;i++) {
  if(a[i]==trazeniBroj) {
   return i;
   break;
  }
 }
 return 0;
}

Ovoj funkciji prosleđujemo tri vrednosti, traženi broj, niz i broj članova niza. A funkcija vraća indeks tog btoja u nizu ako postoji i nulu ako taj broj ne postoji. Ovaj kod je sličan kodu u programskom jeziku S.

Osobine algoritma

Linearn o (sekvencialno) pretraživanje podrazumeva prolaženje kroz niz da bi smo našli traženi element.

Ovaj algoritam je veoma spor jer da bi smo pronašli odgovarajući element mi moramo da prođemo kroz ceo niz. Ako niz ima 1000000 i traži se element na poziciji 999999 mi moramo da prođemo kroz ceo niz da bi smo pronašli taj element. I onda će pretraga trajati predugo.

Strategije pretraživanja

Imamo dve osnovne vrste strategija pretraživanja:

1. Slepo pretraživanje
2. Usmereno pretraživanje

Svojstva algoritama za pretraživanje

1. Potpunost - Algoritam je potpun ako nalazi rešenje uvek ako ono postoji
2. Optimalnost - Algoritam je potpun ako pronalazi optimalno rešenje
3. Prostorna složenost
4. Vremenska složenost

Kompleksnost algoritma

Koroz ovaj niz prolazimo n puta da bi smo pronašli element u nizu. Tako da je kompleksnost ovog algoritma O(n). Najbolji slučaj je kad u lisiti imamo jedan element i tada je složenost O(1).

Vidi još

• Heš tabela
• Problem linearne pretrage

Literatura

• Introductions to algorithms -Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, knjigu možete pogledati ovde Arhivirano na sajtu Wayback Machine (18. oktobar 2016)
• Algoritmi i strukture podataka - Milo Tomašević
• Uvod u programiranje - Milan Škarić