1
00:00:00,000 --> 00:00:02,892
>> [Prehrávanie hudby]

2
00:00:02,892 --> 00:00:05,347

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Linear
Vyhľadávanie je algoritmus sme

4
00:00:07,180 --> 00:00:09,840
môžete použiť na nájsť prvok v matici.

5
00:00:09,840 --> 00:00:11,990
Algoritmus odvolanie
je krok-za-krokom set

6
00:00:11,990 --> 00:00:15,030
inštrukcií pre dokončenie úlohy.

7
00:00:15,030 --> 00:00:17,480
>> Lineárne vyhľadávanie
algoritmus pracuje nasledujúcim spôsobom.

8
00:00:17,480 --> 00:00:22,200
Iterácii cez pole zľava
vpravo, hľadá zadaného prvku.

9
00:00:22,200 --> 00:00:26,380
>> V pseudokódu, ktorý je oveľa
destilovaná verzia tejto vety,

10
00:00:26,380 --> 00:00:29,840
v prípade, že prvý prvok je to, čo
hľadáte, môžete zastaviť.

11
00:00:29,840 --> 00:00:33,930
V opačnom prípade, presuňte na ďalší prvok a
ďalej znovu a znovu, kým nenájdete

12
00:00:33,930 --> 00:00:36,389
prvok, alebo nie.

13
00:00:36,389 --> 00:00:38,680
Takže môžeme použiť lineárny
vyhľadávací algoritmus, napríklad,

14
00:00:38,680 --> 00:00:42,330
nájsť cieľovú hodnotu
deväť v tomto poli.

15
00:00:42,330 --> 00:00:43,870
Tak sme od začiatku.

16
00:00:43,870 --> 00:00:45,970
Ak je to to, čo sme
hľadáte, môžeme zastaviť.

17
00:00:45,970 --> 00:00:47,890
To nie je, že nie hľadáme 11.

18
00:00:47,890 --> 00:00:50,220
Takže inak, presuňte na ďalší prvok.

19
00:00:50,220 --> 00:00:51,510
>> Takže sa pozrieme na 23 ° C.

20
00:00:51,510 --> 00:00:52,730
Je 23 to, čo hľadáme?

21
00:00:52,730 --> 00:00:55,614
No nie, tak sme sa presunúť na ďalší
prvok, a ďalší prvok,

22
00:00:55,614 --> 00:00:57,780
a budeme pokračovať cez
tento proces znovu a znovu

23
00:00:57,780 --> 00:01:01,030
a znovu, kým sme pristáť
na situáciu, ako je táto.

24
00:01:01,030 --> 00:01:03,910
>> Deväť je to, čo hľadáme,
a tento prvok poľa

25
00:01:03,910 --> 00:01:05,787
je, že to je hodnota deväť.

26
00:01:05,787 --> 00:01:08,120
A tak sme našli to, čo sme
hľadáte, a môžeme zastaviť.

27
00:01:08,120 --> 00:01:11,910
Lineárne vyhľadávanie má
dokončenie úspešne.

28
00:01:11,910 --> 00:01:15,370
>> Ale čo v prípade, že hľadáme
prvok, ktorý už nie je v našej poli.

29
00:01:15,370 --> 00:01:17,040
Má lineárny hľadanie stále fungovať?

30
00:01:17,040 --> 00:01:17,540
No iste.

31
00:01:17,540 --> 00:01:19,947
Tak sme tento proces opakovať
počnúc prvý prvok.

32
00:01:19,947 --> 00:01:21,780
Ak je to to, čo sme
hľadáte, môžeme zastaviť.

33
00:01:21,780 --> 00:01:22,800
Nie je.

34
00:01:22,800 --> 00:01:25,020
Inak sme sa presunúť na ďalší prvok.

35
00:01:25,020 --> 00:01:29,050
>> Ale môžeme neustále opakujú tento proces,
skúma každý prvok v poradí,

36
00:01:29,050 --> 00:01:31,720
dúfať, že nájdeme číslo 50.

37
00:01:31,720 --> 00:01:33,750
Ale my, ak nie vedieť,
sme našli číslo 50

38
00:01:33,750 --> 00:01:38,290
alebo ak sme nemali, kým ste vstúpil
nad každého jednotlivého prvku matice.

39
00:01:38,290 --> 00:01:40,440
>> Len raz sme urobili
to a prísť krátka,

40
00:01:40,440 --> 00:01:43,040
môžeme konštatovať, že
50 nie je v matici.

41
00:01:43,040 --> 00:01:46,410
A tak sa lineárny hľadanie
algoritmus, dobre to zlyhalo, samo o sebe.

42
00:01:46,410 --> 00:01:49,181
Ale nie v tom zmysle, že
bol neúspešný v tom, čo

43
00:01:49,181 --> 00:01:49,930
Opýtali sme sa ho urobiť.

44
00:01:49,930 --> 00:01:52,390
>> To bol neúspešný v as
rovnako ako to nenašiel 50,

45
00:01:52,390 --> 00:01:54,070
ale 50 nebol v poli.

46
00:01:54,070 --> 00:01:57,310
Ale my sme dôkladne prehľadali
cez každej jednotlivé súčasti

47
00:01:57,310 --> 00:02:00,550
a tak, keď sme nenašli
niečo, lineárne hľadanie stále

48
00:02:00,550 --> 00:02:05,230
úspešné aj keď
element nie je v matici.

49
00:02:05,230 --> 00:02:07,507
>> Takže to, čo je najhorší prípad
Scenár s lineárnou hľadanie?

50
00:02:07,507 --> 00:02:09,590
No musíme prehliadnuť
každý prvok,

51
00:02:09,590 --> 00:02:14,590
a to buď preto, že cieľový prvok
je posledný prvok poľa,

52
00:02:14,590 --> 00:02:18,510
alebo prvok hľadáme nie je
v poli skutočne existujú vôbec.

53
00:02:18,510 --> 00:02:19,760
Aký je najlepší scenár?

54
00:02:19,760 --> 00:02:22,430
Tak by sme mohli nájsť
prvok okamžite.

55
00:02:22,430 --> 00:02:24,360
A koľko prvkov
my potom budú musieť hľadať

56
00:02:24,360 --> 00:02:26,859
u v najlepšom prípade,
ak sa pozeráme na to

57
00:02:26,859 --> 00:02:28,400
a my ho nájdeme na začiatku?

58
00:02:28,400 --> 00:02:29,850
Môžeme sa okamžite zastaví.

59
00:02:29,850 --> 00:02:32,984
>> Čo to hovorí o
Zložitosť lineárna hľadanie?

60
00:02:32,984 --> 00:02:35,650
No v najhoršom prípade, máme
pozrieť sa na každé jednotlivé súčasti.

61
00:02:35,650 --> 00:02:38,930
A tak to beží v O.
n, v najhoršom prípade.

62
00:02:38,930 --> 00:02:41,540
>> V najlepšom prípade, budeme
okamžite nájsť prvok.

63
00:02:41,540 --> 00:02:44,750
A tak beží v omega 1.

64
00:02:44,750 --> 00:02:45,780
>> Som Doug Lloyd.

65
00:02:45,780 --> 00:02:48,020
To je CS50.

66
00:02:48,020 --> 00:02:49,876