[Mūzikas atskaņošanai] Doug LLOYD: Linear meklēšana ir algoritms mums var izmantot, lai atrastu elements masīva. Algoritms atsaukšana ir soli pa solim komplekts par norādījumiem, kā pabeigt uzdevumu. 

Lineārais meklēšana algoritms darbojas šādi. Atkārtot pāri masīvs no kreisās uz pa labi, skatoties uz noteiktu elementu. 

In pseudocode, kas ir vairāk destilēts versiju šo teikumu, ja pirmais elements ir tas, ko jūs meklējat, jūs varat pārtraukt. Pretējā gadījumā, pāriet uz nākamo elementu un glabāt iet vairāk un vairāk, līdz atrodat elements, vai jums nav. Tātad, mēs varam izmantot lineāro meklēšanas algoritmu, piemēram, atrast mērķlielumu deviņi šajā masīvā. Nu mēs sākam sākumā. Ja tas ir tas, ko mēs esam meklē, mēs varam apturēt. Tas nav, mēs nemeklējam 11. Tātad citādi, pāriet uz nākamo elementu. 

Tātad mēs skatāmies 23. Ir 23, ko mēs meklējam? Nu nē, tāpēc mēs pāriet uz nākamo elements, un nākamā elements, un mēs turpinām iet cauri šis process vairāk un vairāk un vairāk, kamēr mēs nolaisties par situāciju, kā šis. 

Deviņi ir tas, ko mēs meklējam, un šis elements no masīva ir, tā vērtība ir deviņi. Un tā mēs atradām to, ko mēs esam meklē, un mēs varam apturēt. Lineārais meklēšanai ir pabeigts veiksmīgi. 

Bet ko par to, ja mēs meklējam elements, kas nav mūsu masīvā. Vai lineārs meklēšana joprojām strādā? Nu pārliecināts. Tāpēc mēs atkārtot šo procesu sākot no pirmā elementa. Ja tas ir tas, ko mēs esam meklē, mēs varam apturēt. Tas nav. Pretējā gadījumā mēs virzāmies uz nākamo elementu. 

Bet mēs varam saglabāt šo procesu atkārtojot, Pārbaudot katru elementu, savukārt, cerot, ka mēs atrodam skaitli 50. Bet mēs nezinām, vai mēs esam noskaidrojuši, skaitli 50 vai arī, ja mēs neesam, kamēr mēs esam pastiprināts pār katru elementu masīva. 

Tikai tad, kad mēs esam darījuši kas un jānāk klajā īsu, mēs varam secināt, ka 50 neatrodas masīvs. Un tā lineārais meklēšana algoritms, arī tas neizdevās, per se. Bet ne tādā nozīmē, ka tā bija neveiksmīgs darot to, ko mēs lūdzām to darīt. 

Tas bija neveiksmīgs, jo cik tas neatrada 50, bet 50 nebija masīvs. Bet mēs esam izsmeļoši meklētas ar katru elementu un tā, kamēr mēs neatradām kaut kas, lineārā meklēt vēl izdodas pat ja elements nav masīvs. 

Tātad, kas ir sliktākais gadījums scenārijs ar lineāro meklēšanu? Nu mums ir jāskatās caur katru elements, nu tāpēc, ka mērķa elements ir pēdējais elements masīva, vai elements mēs meklējam nav faktiski pastāv masīvā vispār. Kāds ir labākais scenārijs? Nu mēs varētu atrast elements nekavējoties. Un cik daudz elementi mums tad ir jāmeklē pie labākajā gadījumā, ja mēs meklējam to un mēs redzam to jau pašā sākumā? Mēs varam apturēt nekavējoties. 

Ko tas saka par sarežģītība lineārā meklēt? Nu sliktākajā gadījumā, mums ir apskatīt katru elementu. Un tā tas darbojas O n, sliktākajā gadījumā. 

Labākajā gadījumā mēs esam gonna uzreiz atrast elementu. Un tā sākas ar omega 1. 

Es esmu Doug Lloyd. Tas ir CS50.