[Музички] Даг LLOYD: Линеарна пребарување е алгоритам ние можат да го користат за да се најде елемент во низата. Една потсетиме алгоритам е збир чекор-по-чекор упатства за завршување на задачата. 

Линеарниот пребарување алгоритам работи како што следува. Iterate низ низа од лево кон право, во потрага по одреден елемент. 

Во pseudocode, што е повеќе дестилирана верзија на оваа реченица, ако првиот елемент е тоа што што го барате, можете да престанете. Во спротивно, се движи кон следниот елемент и Продолжувам да одам одново и одново додека не најдете елемент, или не. За да можеме да го користите линеарниот пребарување алгоритам, на пример, да се најде на целната вредност девет во оваа низа. Па да почнеме од почеток. Ако тоа е она што ние сме барате, ние може да го запре. Тоа не е, ние не сме во потрага по 11. Па на друг начин, се движи кон следниот елемент. 

Значи ние се погледне во 23. 23 е она што го барате? Па не, за да можеме да се движи кон следниот елемент, и на следниот елемент, а ние продолжуваме да оди преку овој процес одново и одново и одново, додека не се приземји во ваква ситуација. 

Девет е она што го барате, и овој елемент на низата е, тоа е вредност е девет. И така ние се најде она што ние сме во потрага по, а ние може да го запре. Линеарниот пребарување има завршен, успешно. 

Но, што е, ако ние сме во потрага по елемент кој не е во нашата низа. Се линеарно пребарување се уште работат? И сигурен. Па ние го повторите овој процес почнувајќи од првиот елемент. Ако тоа е она што ние сме барате, ние може да го запре. Не е. Инаку, ние се движи кон следниот елемент. 

Но, можеме да ги повторува овој процес, испитување на секој елемент од своја страна, со надеж дека ќе најдеме бројот 50. Но, ние не ќе се знае дали Наидовме на бројот 50 или ако не, се додека ние сме зачекори во текот на секој елемент од низата. 

Само еднаш, ние го направивме кој и да дојде до краток, можеме да заклучиме дека 50 не е во низа. И така на линеарно пребарување алгоритам, и тоа не успеа, само по себе. Но не во смисла дека тоа бил неуспешен во тоа што ние тоа треба да го стори. 

Тоа беше неуспешен во што колку што тоа не се најде на 50, 50 но не беше во низа. Но, ние се исцрпно претрес преку секој елемент И така, додека ние не најдете ништо, линеарно пребарување сеуште успева дури и ако елемент не е во низа. 

Значи, што е најлош случај сценариото со линеарно пребарување? И ние треба да се погледне преку секој елемент, или поради тоа што цел елемент е последниот елемент на низата, или елемент ние сме во потрага по не навистина постојат во низа на сите. Што е најдоброто сценарио? И ние би можеле да се најдат на елемент веднаш. И колку елементи И така, треба да се погледне на во најдобар случај, ако ние сме во потрага по него и ние го најдете на самиот почеток? Можеме да престанат веднаш. 

Што ни кажува тоа за Комплексноста на линеарно пребарување? И во најлош случај, имаме да се погледне во секој елемент. И така таа работи во о на n, во најлош случај. 

Во најдобар случај, ние ќе отидеме најдете елемент веднаш. И така работи во омега на 1. 

Јас сум Даг Лојд. Ова е CS50.