Линеарна претрага

Линеарна претрага
Класа	Алгоритам сортирања
Структура података	Низ
Најгора перформанца
Најбоља перформанца
Најгора просторна комплексност

У рачунарству, линеарна претрага или секвенцијална претрага је метода за проналажење одређене вредности у листи која проверава сваки елемент у низу (листи) док се жељени елемент не пронађе или док се не прође цела листа. Листа не мора бити сортирана.

Линеарна претрага је најједноставнији алгоритам претраге; то је посебан случај исцрпљујуће претраге. У најгорем случају, сложеност је пропорционална броју елемената у листи. Његова очекивана сложеност је такође пропорционална броју елемената ако се сви елементи подједнако претражују. Ако листа има више од неколико елемената и често се претражује, онда сложеније методе претраге, као што су бинарна претрага или хеширање, могу да буду прикладније. Ове методе имају бржу претрагу, али захтевају додатне ресурсе да постигну ту брзину.

Анализа

За листу са n елементима, најбољи случај је када је вредност једнака првом елементу листе, јер је у том случају потребно само једно поређење. Најгори случај је када вредност није у листи (или се јавља само једном на крају листе), и у том случају је потребно n поређења.

Ако се тражена вредност јавља к пута у листи, и сва уређивања листе су подједнако могућа, очекивани број поређења је

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

На пример, ако се тражена вредност појављује два пута у листи, и сва уређивања листе су подједнако могућа, очекивани број поређења је ${\frac {n+1}{2}}$ . Међутим, ако је познато да се тражена вредност једном појављује, тада је највише n - 1 поређења потребно, а очекивани број поређења је

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

(на пример, за n = 2 резултат је 1, што одговара једном ,,if-then-else" конструктору).

У сваком случају, асимптотски најгори случај сложености и очекивана сложеност линеарне претраге су О(n).

Разноврсне вероватноће

Перформансе линеарне претраге се побољшавају ако је жељена вредност ближе почетку листе него при крају. Дакле, ако се неке вредности траже више у односу на друге, пожељно је поставити их на почетак листе.

Посебно, када су елементи листе распоређени опадајућом вероватноћом, и ове вероватноће се геометријски дистрибуирају, сложеност линеарне претраге је само O(1). Ако је величина листе n довољно велика, линеарна претрага ће бити бржа од бинарне претраге, чија је сложеност O(log n).^[3]

Апликација

Линеарна претрага је обично веома једноставна за имплементацију и практична када листа има само неколико елемената, или приликом обављања једне претраге неуређене листе.

Када више вредности треба да се претраже у истој листи, често се исплати да се реорганизује листа како би се искористиле брже методе. На пример, сортирање листе и употреба бинарне претраге, или изградња било какве ефикасне структуре претраге података из њега. Ако се елементи листе често мењају, поновљена реорганизација може донети више проблема него користи.

Као резултат тога, иако у теорији други алгоритми претраа могу бити бржи од линеарне претраге (пример бинарна претрага), у пракси чак и на средњим низовима (око 100 предмета или мање) је можда неизводљиво да се користи било шта друго. На већим низовима, разумно је користити друге, брже методе претраге ако су подаци довољно велики, јер почетно време да се само припреме (сортирају) подаци може се упоредити са многим линеарним претрагама.^[4]

Псеудокод

Напредно понављање

Овај псеудокод описује типичну варијанту линеарне претраге, у којој би резултат претраге требало да буде било локација елемента из листе у којој је нађена жељена вредност; или погрешна локација Λ, да укаже да се жељени елемент не појављује у листи.

За сваки елемен у листи:

ако тај елемент има жељену вредност,

заустави претрагу и врати локацију елемента.

Врати Λ.

У овом псеудокоду, последња линија је извршена само у случају да за сваки испитани елемент није пронађено подударање.

Ако је листа сачувана као низ (структура података), локација може бити индекс нађене ставке (обично између 1 и n, или 0 и n-1). У том случају неважећа локација Λ може бити индекс пре првог елемента (као што је 0 или -1) или после последњег (n+1 или n).

Ако је листа једноставна повезана листа, онда локација елемента је његова референца, и Λ је обично нулти показивач.

Рекурзивна верзија

Линеарна претрага такође може бити описана као рекурзивни алгоритам:

ЛинеарнаПретрага (вредност, листа)

ако је листа празна, врати Λ;

у супротном

ако први елемент листе има жељену вредност, врати његову локацију;

у супротном врати ЛинеарнаПретрага (вредност, остатак листе)

Претрага у обрнутом редоследу

Линеарна претрага низа је обично програмирана убрзањем индекса променљиве док не дође до задњег индекса. Ово обично захтева два скупа поређења за сваки елемент листе: један да провери да ли је индекс достигао крај низа, а други да провери да ли елемент има жељену вредност. У многим рачунарима, може се смањити рад првог поређења претраживањем елемената обрнутим редоследом.

Претпоставимо да се низ А са елементима индексираним од 1 до n претражује за вредност x. Следећи псеудокод обавља напредну претрагу, враћајући n + 1 ако вредност није пронађена:

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

Следећи псеудокод претражује низ у обрнутом редоследу, враћајући 0 ако елемент није пронађен:

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

Већина рачунара има условну грану инструкција које тестирају знак вредности у регистру, или знак резултата најскорије аритметичке операције. Може се користити та инструкција, која је обично бржа него поређење са неком произвољном вредношћу (захтева одузимање), да спроведе команду "Ако је ≤ 0, онда изађи из петље".

Ову оптимизацију је лако имплементирати приликом машинског програмирања или у асемблеру. Та грана инструкција није директно доступна у типичним програмским језицима високог нивоа, иако ће многи компајлери бити у стању да обаве ту оптимизацију сами.

Употреба контроле

Други начин да се додатно смањи је да се елиминишу све провере индекса петље. Ово се може урадити убацивањем самог жељеног елемента као контролне вредности на самом крају листе, као у овом псеудокоду:

Постави A[n + 1] на x.

Постави i на 1.

Понови ову петљу:

Ако је A[i] = x, онда изађи из петље.

Постави i на i + 1.

Врати i.

Са овом стратегијом, није неопходно да се провери вредност i са листом дужине n: чак и ако x није нађен у А на почетку, петља ће прекинути када је i = n + 1. Међутим, ова метода је могућа само ако место у низу A[n + 1] постоји, али се не користи другачије. Сличнија уређења могу бити ако се низ претражује обрнутим редоследом, и елемент A(0) је доступан.

Иако је напор избегнут захваљујући овим малим радом, ипак је значајна компонента додатног обављања сваког корака претраге, која је мала. Само ако је много елемената вероватно да ће се упоредити биће од користи с обзиром методе које чине мање поређења, али намећу друге услове.

Линеарна претрага уређене листе

За уређене листе које морају бити приступане редом, као што су повезане листе или фајлови са променљивом дужином евиденције који немају индекс, просечне перформансе се могу побољшати одустајањем на првом елементу који је већи од недостижне циљане вредности, него прегледали целу листу.

Ако је листа сачувана као уређен низ, онда је бинарна претрага скоро увек ефикаснија него линеарна претрага као са n > 8, рецимо, осим ако не постоји разлог да се претпостави да ће већина претраге бити за мале елементе близу почетка сортиране листе.

Имплементација

Овај алгоритам има најједноставнију имплементацију у свим програмским језицима.

Псеудо код:^[1]

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;
}

Овој функцији прослеђујемо три вредности, тражени број, низ и број чланова низа. А функција враћа индекс тог бтоја у низу ако постоји и нулу ако тај број не постоји. Овај код је сличан коду у програмском језику С.

Особине алгоритма

Линеарн о (секвенциално) претраживање подразумева пролажење кроз низ да би смо нашли тражени елемент.

Овај алгоритам је веома спор јер да би смо пронашли одговарајући елемент ми морамо да прођемо кроз цео низ. Ако низ има 1000000 и тражи се елемент на позицији 999999 ми морамо да прођемо кроз цео низ да би смо пронашли тај елемент. И онда ће претрага трајати предуго.

Стратегије претраживања

Имамо две основне врсте стратегија претраживања:

Слепо претраживање
Усмерено претраживање

Својства алгоритама за претраживање

Потпуност - Алгоритам је потпун ако налази решење увек ако оно постоји
Оптималност - Алгоритам је потпун ако проналази оптимално решење
Просторна сложеност
Временска сложеност

Комплексност алгоритма

Короз овај низ пролазимо n пута да би смо пронашли елемент у низу. Тако да је комплексност овог алгоритма О(n). Најбољи случај је кад у лисити имамо један елемент и тада је сложеност О(1).

Види још

Референце

^ ^а ^б ^в Шкарић, Милан; Виктор Радовић (2009). „5”. Увод у програмирање (Прво изд.). Београд: Микро књига. стр. 205. ISBN 978-86-7555-349-6. „Низови и претраживање”
^ ^а ^б ^в Томашевић, Мило (2008). „Прво”. Алгоритми и структуре података (Прво изд.). Београд: Академска мисао. стр. 406. ISBN 978-86-7466-328-8. Приступљено 9. 2. 2016. „Просторна сложеност алгоритма”
^ Knuth, Donald (1997). „Section 6.1: Sequential Searching”. Sorting and Searching. The Art of Computer Programming. 3 (3rd изд.). Addison-Wesley. стр. 396—408. ISBN 978-0-201-89685-5.
^ Horvath, Adam. „Binary search and linear search performance on the .NET and Mono platform”. Приступљено 19. 4. 2013.

Литература

Introductions to algorithms -Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, књигу можете погледати овде Архивирано на сајту Wayback Machine (18. октобар 2016)
Алгоритми и структуре података - Мило Томашевић
Увод у програмирање - Милан Шкарић

[Низови-1] а ^б ^в Шкарић, Милан; Виктор Радовић (2009). „5”. Увод у програмирање (Прво изд.). Београд: Микро књига. стр. 205. ISBN 978-86-7555-349-6. „Низови и претраживање”

[Комплексност-2] а ^б ^в Томашевић, Мило (2008). „Прво”. Алгоритми и структуре података (Прво изд.). Београд: Академска мисао. стр. 406. ISBN 978-86-7466-328-8. Приступљено 9. 2. 2016. „Просторна сложеност алгоритма”

[knuth-3] Knuth, Donald (1997). „Section 6.1: Sequential Searching”. Sorting and Searching. The Art of Computer Programming. 3 (3rd изд.). Addison-Wesley. стр. 396—408. ISBN 978-0-201-89685-5.

[4] Horvath, Adam. „Binary search and linear search performance on the .NET and Mono platform”. Приступљено 19. 4. 2013.

[1]

[2]

[3]

[4]


Класа	Алгоритам сортирања^[1]
Структура података	Низ^[1]
Најгора перформанца	$O(n)$ ^[2]
Најбоља перформанца	$O(n)$ ^[2]
Најгора просторна комплексност	$O(n)$ ^[2]