>> [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.