Линеарна претрага — разлика између измена

Садржај обрисан Садржај додат
Нема описа измене
мНема описа измене
Ред 19:
(на пример, за ''n'' = 2 резултат је 1, што одговара једном ,,if-then-else" конструктору).
 
У сваком случају, [[Теорија комплексности|асимптотски]] најгори случај сложености и очекивана сложеност линеарне претраге су [[Велико О|О]](''n'').
 
=== Разноврсне вероватноће ===
Перформансе линеарне претраге се побољшавају ако је жељена вредност ближе почетку листе него при крају. Дакле, ако се неке вредности траже више у односу на друге, пожељно је поставити их на почетак листе.
 
Посебно, када су елементи листе распоређени опадајућом вероватноћом, и ове вероватноће се [[геометријски дистрибуирају]], сложеност линеарне претраге је само O(1). Ако је величина листе <span>''n ''довољно</span> велика, линеарна претрага ће бити бржа од [[Бинарна претрага|бинарне претраге]], чија је сложеност O(log ''n'').<ref name="knuth"><cite class="citation book" contenteditable="false">[[Donald Knut|Knuth, Donald]] (1997). </cite></ref>
 
== Апликација ==
Линеарна претрага је обично веома једноставна за имплементацију и практична када листа има само неколико елемената, или приликом обављања једне претраге неуређене листе.
 
Када више вредности треба да се претраже у истој листи, често се исплати да се реорганизује листа како би се искористиле брже методе. На пример, [[сортирање]] листе и употреба бинарне претраге, или изградња било какве ефикасне [[Структуре података претраге|структуре претраге података]] из њега. Ако се елементи листе често мењају, поновљена реорганизација може донети више проблема него користи.
 
Као резултат тога, иако у теорији други алгоритми претраа могу бити бржи од линеарне претраге (пример [[бинарна претрага]]), у пракси чак и на средњим низовима (око 100 предмета или мање) је можда неизводљиво да се користи било шта друго. На већим низовима, разумно је користити друге, брже методе претраге ако су подаци довољно велики, јер почетно време да се само припреме (сортирају) подаци може се упоредити са многим линеарним претрагама.<ref><cite class="citation web" contenteditable="false">Horvath, Adam. </cite></ref>
 
== Псеудокод ==
 
=== Напредно понављање ===
Овај [[псеудокод]] описује типичну варијанту линеарне претраге, у којој би резултат претраге требало да буде било локација елемента из листе у којој је нађена жељена вредност; или погрешна локација ''Λ'', да укаже да се жељени елемент не појављује у листи.
За сваки елемен у листи:
ако тај елемент има жељену вредност,
Ред 43:
У овом псеудокоду, последња линија је извршена само у случају да за сваки испитани елемент није пронађено подударање.
 
Ако је листа сачувана као [[Низ (структура података)|низ (структура података)]], локација може бити [[индекс]] нађене ставке (обично између 1 и n, или 0 и n-1). У том случају неважећа локација Λ може бити индекс пре првог елемента (као што је 0 или -1, респективно) или после последњег (n+1 или n, респективно).
 
Ако је листа једноставна [[Povezana lista|повезана листа]], онда локација елемента је његова [[Референца (програмирање)|референца]], и Λ је обично [[нулти показивач]].
 
=== Рекурзивна верзија ===
Линеарна претрага такође може бити описана као [[Рекурзија|рекурзивни алгоритам]]:
ЛинеарнаПретрага(вредност, листа)
ако је листа празна, врати ''Λ'';
Ред 56:
 
=== Претрага у обрнутом редоследу ===
Линеарна претрага низа је обично програмирана убрзањем индекса променљиве док не дође до задњег индекса. Ово обично захтева два [[Скуп инструкција|скупа]] поређења за сваки елемент листе: један да провери да ли је индекс достигао крај низа, а други да провери да ли елемент има жељену вредност. У многим рачунарима, може се смањити рад првог поређења претраживањем елемената обрнутим редоследом.
 
Претпоставимо да се низ А са елементима индексираним од 1 до n претражује за вредност x. Следећи псеудокод обавља напредну претрагу, враћајући n + 1 ако вредност није пронађена:
Ред 74:
Већина рачунара има условну грану инструкција које тестирају знак вредности у регистру, или знак резултата најскорије аритметичке операције. Може се користити та инструкција, која је обично бржа него поређење са неком произвољном вредношћу (захтева одузимање), да спроведе команду "Ако је ≤ 0, онда изађи из петље".
 
Ову оптимизацију је лако имплементирати приликом [[Машински језик|машинског програмирања]] или у [[Асемблер|асемблеру]]. Та грана инструкција није директно доступна у типичним [[Програмски језик високог нивоа|програмским језицима високог нивоа]], иако ће многи [[Компилатор|компајлери]] бити у стању да обаве ту оптимизацију сами.
 
=== Употреба контроле ===