[Přehrávání hudby] DOUG LLOYD: Linear Vyhledávání je algoritmus jsme můžete použít k najít prvek v matici. Algoritmus odvolání je krok-za-krokem set instrukcí pro dokončení úkolu. 

Lineární vyhledávání algoritmus pracuje následujícím způsobem. Iteraci přes pole zleva vpravo, hledá zadaného prvku. 

V pseudokódu, který je mnohem destilovaná verze této věty, v případě, že první prvek je to, co hledáte, můžete zastavit. V opačném případě, přesuňte na další prvek a dál znovu a znovu, dokud nenajdete prvek, nebo ne. Takže můžeme použít lineární vyhledávací algoritmus, například, najít cílovou hodnotu devět v tomto poli. Tak jsme od začátku. Pokud je to to, co jsme hledáte, můžeme zastavit. To není, že ne hledáme 11. Takže jinak, přesuňte na další prvek. 

Takže se podíváme na 23 ° C. Je 23 to, co hledáme? No ne, tak jsme se přesunout na další prvek, a další prvek, a budeme pokračovat přes tento proces znovu a znovu a znovu, dokud jsme přistát na situaci, jako je tato. 

Devět je to, co hledáme, a tento prvek pole je, že to je hodnota devět. A tak jsme našli to, co jsme hledáte, a můžeme zastavit. Lineární vyhledávání má dokončení úspěšně. 

Ale co v případě, že hledáme prvek, který již není v naší poli. Má lineární hledání stále fungovat? No jistě. Tak jsme tento proces opakovat počínaje první prvek. Pokud je to to, co jsme hledáte, můžeme zastavit. Není. Jinak jsme se přesunout na další prvek. 

Ale můžeme neustále opakují tento proces, zkoumá každý prvek v pořadí, doufat, že najdeme číslo 50. Ale my, ne-li vědět, jsme našli číslo 50 nebo pokud jsme neměli, dokud jste vstoupil nad každého jednotlivého prvku matice. 

Jen jednou jsme udělali to a přijít krátká, můžeme konstatovat, že 50 není v matici. A tak se lineární hledání algoritmus, dobře to selhalo, samo o sobě. Ale ne v tom smyslu, že byl neúspěšný v tom, co Zeptali jsme se ho udělat. 

To byl neúspěšný v as stejně jako to nenašel 50, ale 50 nebyl v poli. Ale my jsme důkladně prohledali přes každé jednotlivé součásti a tak, když jsme nenašli něco, lineární hledání stále úspěšné i když element není v matici. 

Takže to, co je nejhorší případ Scénář s lineární hledání? No musíme prohlédnout každý prvek, a to buď proto, že cílový prvek je poslední prvek pole, nebo prvek hledáme není v poli skutečně existují vůbec. Jaký je nejlepší scénář? Tak bychom mohli najít prvek okamžitě. A kolik prvků my pak budou muset hledat u v nejlepším případě, pokud se díváme na to a my ho najdeme na začátku? Můžeme se okamžitě zastaví. 

Co to říká o Složitost lineární hledání? No v nejhorším případě, máme podívat se na každé jednotlivé součásti. A tak to běží v O. n, v nejhorším případě. 

V nejlepším případě, budeme okamžitě najít prvek. A tak běží v omega 1. 

Jsem Doug Lloyd. To je CS50.