Линеарна претрага — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
Нема описа измене |
||
Ред 25:
Перформансе линеарне претраге се побољшавају ако је жељена вредност ближе почетку листе него при крају. Дакле, ако се неке вредности траже више у односу на друге, пожељно је поставити их на почетак листе.
Посебно, када су елементи листе распоређени опадајућом вероватноћом, и ове вероватноће се [[геометријски дистрибуирају]], сложеност линеарне претраге је само O(1). Ако је величина листе <span>''n ''довољно</span> велика, линеарна претрага ће бити бржа од [[Бинарна претрага|бинарне претраге]], чија је сложеност O(log ''n'').<ref name="knuth">
| series = The Art of Computer Programming
| volume = 3 |title=Sorting and Searching
| edition = 3rd
| publisher = Addison-Wesley
| year = 1997
| isbn = 0-201-89685-0
| chapter = Section 6.1: Sequential Searching,
| pages = 396–408
}}
</ref>
== Апликација ==
Линија 32 ⟶ 44:
Када више вредности треба да се претраже у истој листи, често се исплати да се реорганизује листа како би се искористиле брже методе. На пример, [[сортирање]] листе и употреба бинарне претраге, или изградња било какве ефикасне [[Структуре података претраге|структуре претраге података]] из њега. Ако се елементи листе често мењају, поновљена реорганизација може донети више проблема него користи.
Као резултат тога, иако у теорији други алгоритми претраа могу бити бржи од линеарне претраге (пример [[бинарна претрага]]), у пракси чак и на средњим низовима (око 100 предмета или мање) је можда неизводљиво да се користи било шта друго. На већим низовима, разумно је користити друге, брже методе претраге ако су подаци довољно велики, јер почетно време да се само припреме (сортирају) подаци може се упоредити са многим линеарним претрагама.<ref>
== Псеудокод ==
| |||