[SKAN MŪZIKA]
DAGS LOIDS: Lineārā meklēšana ir algoritms, ko varam izmantot, lai
atrastu elementu masīvā.
Algoritma atsaukšana ir norādījumu kopums uzdevuma izpildei soli pa
solim.
Lineārās meklēšanas algoritms darbojas šādi.
Atkārtojiet masīvu no kreisās puses uz labo, meklējot noteiktu
elementu.
Pseidokodā, kas ir šī izteikuma detalizētāka versija, varat
apstāties, ja pirmais elements ir tas, ko meklējat.
Pretējā gadījumā pārejiet uz nākamo elementu un turpiniet to atkal un
atkal, līdz atrodat vai neatrodat elementu.
Tātad mēs varam izmantot lineāro meklēšanas algoritmu, piemēram, lai
šajā masīvā atrastu mērķa vērtību deviņi.
Tad mēs sākam no sākuma.
Ja tas ir tas, ko mēs meklējam, mēs varam apstāties.
Tā nav, mēs nemeklējam 11.
Tad pārejiet uz nākamo elementu.
Tātad mēs skatāmies uz 23.
Vai 23 ir tas, ko mēs meklējam?
Nu nav tas, tāpēc mēs pārejam pie nākamā elementa un nākamā elementa,
un mēs turpinām iet cauri šim procesam atkal un atkal, līdz nonākam
līdz šādai situācijai.
Deviņi ir tas, ko mēs meklējam, un šis masīva elements ir, tā vērtība
ir deviņi.
Un tā mēs atradām to, ko meklējam, un varam apstāties.
Lineārā meklēšana ir veiksmīgi pabeigta.
Bet ko darīt, ja mēs meklējam elementu, kas nav mūsu masīvā.
Vai lineārā meklēšana joprojām darbosies?
Noteikti.
Tātad mēs atkārtojam šo procesu, sākot ar pirmo elementu.
Ja tas ir tas, ko mēs meklējam, mēs varam apstāties.
Tā nav.
Tad mēs pārejam uz nākamo elementu.
Bet mēs varam turpināt atkārtot šo procesu, pārbaudot katru elementu
pēc kārtas, cerot, ka atradīsim skaitli 50.
Bet mēs neuzzināsim, vai esam atraduši skaitli 50 vai neesam
atraduši, kamēr nebūsim izgājuši cauri katram masīva elementam.
Tikai tad, kad esam to paveikuši un panākuši rezultātu, mēs varam
secināt, ka 50 nav iekļauts masīvā.
Un tāpēc lineārās meklēšanas algoritms , kā tāds,neizdevās.
Bet ne tādā nozīmē, ka tam neizdevās izdarīt to, ko mēs tam prasījām.
Tam neizdevās, jo neatrada 50, bet 50 nebija masīvā.
Bet mēs esam izsmeļoši izmeklējuši katru elementu, un tāpēc, lai gan
mēs neko neatradām, lineārā meklēšana joprojām izdodas, pat ja
elements nav masīvā.
Tātad, kāds ir sliktākais scenārijs ar lineāro meklēšanu?
Mums ir jāizskata katrs atsevišķais elements vai nu tāpēc, ka mērķa
elements ir pēdējais masīva elements, vai arī elements, kuru mēs
meklējam, patiesībā nemaz nepastāv masīvā.
Kāds ir labākais scenārijs?
Nu, mēs varētu nekavējoties atrast elementu.
Un cik daudz elementu mums labākajā gadījumā ir jāapskata, ja mēs to
meklējam un atrodam pašā sākumā?
Mēs varam nekavējoties apstāties.
Ko tas saka par lineārās meklēšanas sarežģītību?
Sliktākajā gadījumā mums ir jāaplūko katrs elements.
Un tā tas darbojas n skaitļa O, sliktākajā gadījumā.
Labākajā gadījumā mēs nekavējoties atradīsim elementu.
Un tā darbojas omega 1 skaitlī.
Es esmu Dags Loids.
Šis ir CS50.