[MUSIC JOC] DOUG LLOYD: Linear căutare este o noi algoritm se poate utiliza pentru a găsi un element într-o matrice. Un algoritm rechemare este un set de pas-cu-pas de instrucțiuni pentru finalizarea unei sarcini. 

Căutare liniară Algoritmul funcționează după cum urmează. Repeta peste matrice de la stânga la dreapta, în căutarea unui element specificat. 

În pseudocod, care este o mai versiunea distilată a acestei propoziții, În cazul în care primul element este ceea ce sunteți în căutarea pentru, vă puteți opri. În caz contrar, trece la elementul următor și mergi peste si peste până când veți găsi elementul, sau nu. Deci, putem folosi liniar algoritm de căutare, de exemplu, pentru a găsi valoarea țintă nouă în această matrice. Ei bine, vom începe de la început. Dacă e ceea ce suntem cauta, ne putem opri. Nu e, nu suntem în căutarea pentru 11. Deci în caz contrar, trece la elementul următor. 

Deci, ne uităm la 23. Este de 23 ceea ce căutăm? Ei bine, nu, asa ca am trece la următoarea element și elementul următor, și păstrăm trece prin acest proces de peste si peste și peste, până când vom ateriza pe o situatie ca asta. 

Nouă este ceea ce căutați, și acest element de matrice este, o valoare este de aceasta nouă. Și așa am găsit ceea ce suntem cauta, si ne putem opri. Căutare liniară are finalizat, cu succes. 

Dar ceea ce despre dacă căutăm un element care nu este în oferta noastră. Are căutare liniară încă mai funcționează? Bine sigur. Așa că am repeta acest proces începând de la primul element. Dacă e ceea ce suntem cauta, ne putem opri. Nu e. În caz contrar, vom trece la elementul următor. 

Dar putem repeta acest proces, examinarea fiecărui element, la rândul său, în speranța că vom găsi numărul 50. Dar nu vom ști dacă am găsit numărul 50 sau dacă nu am făcut-o, până când am pășit noi peste fiecare element unic de matrice. 

Doar o singură dată am făcut că și să vină scurt, putem concluziona că 50 nu este în matrice. Și astfel de căutare liniară algoritm, bine nu a reușit, în sine. Dar nu în sensul că nu a avut succes în a face ceea ce am cerut să facă. 

Acesta a avut succes în ca de mult ca nu a găsit 50, dar 50 nu a fost în matrice. Dar am căutat în mod exhaustiv prin fiecare singur element și așa, în timp ce nu am găsit nimic, căutare liniară încă reușește, chiar dacă Element nu este în matrice. 

Deci, ce este cel mai rău caz scenariu cu căutare liniară? Ei bine, trebuie sa ne uitam prin fiecare singur element, fie din cauză că elementul țintă este ultimul element de matrice, sau elementul căutăm nu există de fapt în matrice, la toate. Care este cel mai bun caz? Ei bine, am putea găsi elementul imediat. Și cât de multe elemente avem apoi să se uite la în cel mai bun caz, dacă suntem în căutarea pentru el și îl găsim la bun început? Ne putem opri imediat. 

Ce înseamnă acest spune despre complexitatea căutare liniară? Ei bine, în cel mai rău caz, ne-am să se uite la fiecare singur element. Și așa se execută în O de n, în cel mai rău caz. 

În cel mai bun caz, vom găsi imediat elementul. Și astfel se execută în omega de 1. 

Sunt Doug Lloyd. Acest lucru este CS50.