>> [Muusika mängib]
DOUG LLOYD: Linear otsingu algoritmi me
saab kasutada, et leida element massiivi.
Algoritm tagasikutsumine on samm-sammult komplekt
käskude täitmise ülesanne.
>> Lineaarse otsing algoritmi toimib järgmiselt.
Käi kogu massiivi vasakult õige, otsin teatud element.
>> In pseudokoodi, mis on rohkem destilleeritud versioon sellest lausest,
kui esimene element on see, mida otsite, saate peatada.
Muidu liikuda järgmisele element ja jätkame ikka ja jälle, kuni sa leiad
element, või ei ole.
Nii saame kasutada lineaarset otsingu algoritm, näiteks
leida sihtväärtust Üheksa selle massiivi.
Noh me alustame algusest.
Kui see on see, mida me oleme otsin, saame lõpetada.
See ei ole, et me ei otsi 11.
Nii muidu liikuda järgmisele element.
>> Nii me vaatame 23.
Kas 23, mida me otsime?
Noh ole, nii et me liigume edasi järgmise element, ja järgmine element,
ja me jätkame läbi Selle protsessi üle ja üle
ja jälle, kuni me maa kohta sellises olukorras.
>> Üheksa mida me otsime, ja see element massiivi
on see väärtus on üheksa.
Ja nii me leidsime me oleme otsin, ja me ei saa peatada.
Lineaarse otsing on lõpetatud edukalt.
>> Aga kui me otsime element, mis ei ole meie rida.
Kas lineaarne otsing veel tööd?
Noh kindel.
Nii me kordame seda protsessi alates esimesest element.
Kui see on see, mida me oleme otsin, saame lõpetada.
See ei ole.
Muidu me liikuda järgmise elemendi.
>> Aga me ei saa hoida korrates seda protsessi, uurida iga element omakorda
lootes, et leiame number 50.
Aga me ei tea, kas Leidsime number 50
või kui me ei ole, kuni oleme astunud üle iga element massiivi.
>> Alles siis, kui me oleme teinud seda ja tulla lühike,
saame järeldada, et 50 ei ole massiiv.
Ja nii lineaarne otsing algoritm, hästi see ei õnnestunud, per se.
Aga mitte selles mõttes, et see ei õnnestunud seda, mida
Palusime tal seda teha.
>> See ei õnnestunud, kuna palju kui ta ei leidnud 50,
kuid 50 ei olnud valikut.
Aga me oleme ammendavalt otsisid läbi iga element
ja nii, kui me ei leia midagi, lineaarne otsing veel
õnnestub isegi kui element ei massiivi.
>> Mis siis halvimal juhul stsenaarium lineaarne otsing?
Noh me peame vaatama läbi iga element,
kas sellepärast, et siht element on viimane element massiivi,
või element ootame ei tegelikult on olemas massiiv üldse.
Milline on parim stsenaarium?
Noh me võiksime leida element kohe.
Ja kui palju elemente Kas me siis peame vaatama
kell parimal juhul Kui me vaatame seda
ja me leiame ta alguses?
Saame kohe lõpetada.
>> Mida see öelda keerukust lineaarne otsing?
Noh halvimal juhul on meil vaadata iga element.
Ja nii see kulgeb O n, halvimal juhul.
>> Parimal juhul me teeme leida element kohe.
Ja nii jookseb omega 1.
>> Ma olen Doug Lloyd.
See on CS50.