Линеарна претрага — разлика између измена
Садржај обрисан Садржај додат
refs |
м Бот: обликујем ISBN; козметичке измене |
||
Ред 22:
\end{cases}</math>
На пример, ако се тражена вредност појављује два пута у листи, и сва уређивања листе су подједнако могућа, очекивани број поређења је <math>\frac{n + 1}2</math>. Међутим, ако је познато да се тражена вредност једном појављује, тада је највише ''n'' - 1 поређења потребно, а очекивани број поређења је
<math>\displaystyle\frac{(n + 2)(n-1)}{2n}</math>
(на пример, за ''n'' = 2 резултат је 1, што одговара једном ,,if-then-else" конструктору).
Ред 33:
Перформансе линеарне претраге се побољшавају ако је жељена вредност ближе почетку листе него при крају. Дакле, ако се неке вредности траже више у односу на друге, пожељно је поставити их на почетак листе.
Посебно, када су елементи листе распоређени опадајућом вероватноћом, и ове вероватноће се [[геометријски дистрибуирају]], сложеност линеарне претраге је само O(1). Ако је величина листе <span>''n ''довољно</span> велика, линеарна претрага ће бити бржа од [[Бинарна претрага|бинарне претраге]], чија је сложеност O(log ''n'').<ref name="knuth">{{Cite book|last=Knuth|first=Donald|authorlink=Donald Knuth | series = The Art of Computer Programming | volume = 3 |title=Sorting and Searching | edition = 3rd | publisher = Addison-Wesley |year=1997|id=ISBN 978-0-201-89685-
== Апликација ==
Ред 48:
: За сваки елемен у листи:
:: ако тај елемент има жељену вредност,
:::
:: Врати ''Λ''.
У овом псеудокоду, последња линија је извршена само у случају да за сваки испитани елемент није пронађено подударање.
Ред 58:
=== Рекурзивна верзија ===
Линеарна претрага такође може бити описана као [[Рекурзија|рекурзивни алгоритам]]:
:
::
::
:::
:::
=== Претрага у обрнутом редоследу ===
Ред 80:
Ако је ''i'' ≤ 0, онда изађи из петље.
Ако је ''A''[''i''] = ''x'', онда изађи из петље.
Постави ''i'' на ''i''
Врати ''i''.
Већина рачунара има условну грану инструкција које тестирају знак вредности у регистру, или знак резултата најскорије аритметичке операције. Може се користити та инструкција, која је обично бржа него поређење са неком произвољном вредношћу (захтева одузимање), да спроведе команду "Ако је ≤ 0, онда изађи из петље".
Ову оптимизацију је лако имплементирати приликом [[Машински језик|машинског програмирања]] или у [[
=== Употреба контроле ===
Други начин да се додатно смањи је да се елиминишу све провере индекса петље. Ово се може урадити убацивањем самог жељеног елемента као контролне вредности на самом крају листе, као у овом псеудокоду:
:
:
:
::
::
:
Са овом стратегијом, није неопходно да се провери вредност i са листом дужине n: чак и ако x није нађен у А на почетку, петља ће прекинути када је i = n + 1. Међутим, ова метода је могућа само ако место у низу A[n + 1] постоји, али се не користи другачије. Сличнија уређења могу бити ако се низ претражује обрнутим редоследом, и елемент A(0) је доступан.
| |||