1
00:00:00,000 --> 00:00:02,892
>> [Přehrávání hudby]

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

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Linear
Vyhledávání je algoritmus jsme

4
00:00:07,180 --> 00:00:09,840
můžete použít k najít prvek v matici.

5
00:00:09,840 --> 00:00:11,990
Algoritmus odvolání
je krok-za-krokem set

6
00:00:11,990 --> 00:00:15,030
instrukcí pro dokončení úkolu.

7
00:00:15,030 --> 00:00:17,480
>> Lineární vyhledávání
algoritmus pracuje následujícím způsobem.

8
00:00:17,480 --> 00:00:22,200
Iteraci přes pole zleva
vpravo, hledá zadaného prvku.

9
00:00:22,200 --> 00:00:26,380
>> V pseudokódu, který je mnohem
destilovaná verze této věty,

10
00:00:26,380 --> 00:00:29,840
v případě, že první prvek je to, co
hledáte, můžete zastavit.

11
00:00:29,840 --> 00:00:33,930
V opačném případě, přesuňte na další prvek a
dál znovu a znovu, dokud nenajdete

12
00:00:33,930 --> 00:00:36,389
prvek, nebo ne.

13
00:00:36,389 --> 00:00:38,680
Takže můžeme použít lineární
vyhledávací algoritmus, například,

14
00:00:38,680 --> 00:00:42,330
najít cílovou hodnotu
devět v tomto poli.

15
00:00:42,330 --> 00:00:43,870
Tak jsme od začátku.

16
00:00:43,870 --> 00:00:45,970
Pokud je to to, co jsme
hledáte, můžeme zastavit.

17
00:00:45,970 --> 00:00:47,890
To není, že ne hledáme 11.

18
00:00:47,890 --> 00:00:50,220
Takže jinak, přesuňte na další prvek.

19
00:00:50,220 --> 00:00:51,510
>> Takže se podíváme na 23 ° C.

20
00:00:51,510 --> 00:00:52,730
Je 23 to, co hledáme?

21
00:00:52,730 --> 00:00:55,614
No ne, tak jsme se přesunout na další
prvek, a další prvek,

22
00:00:55,614 --> 00:00:57,780
a budeme pokračovat přes
tento proces znovu a znovu

23
00:00:57,780 --> 00:01:01,030
a znovu, dokud jsme přistát
na situaci, jako je tato.

24
00:01:01,030 --> 00:01:03,910
>> Devět je to, co hledáme,
a tento prvek pole

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

26
00:01:05,787 --> 00:01:08,120
A tak jsme našli to, co jsme
hledáte, a můžeme zastavit.

27
00:01:08,120 --> 00:01:11,910
Lineární vyhledávání má
dokončení úspěšně.

28
00:01:11,910 --> 00:01:15,370
>> Ale co v případě, že hledáme
prvek, který již není v naší poli.

29
00:01:15,370 --> 00:01:17,040
Má lineární hledání stále fungovat?

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

31
00:01:17,540 --> 00:01:19,947
Tak jsme tento proces opakovat
počínaje první prvek.

32
00:01:19,947 --> 00:01:21,780
Pokud je to to, co jsme
hledáte, můžeme zastavit.

33
00:01:21,780 --> 00:01:22,800
Není.

34
00:01:22,800 --> 00:01:25,020
Jinak jsme se přesunout na další prvek.

35
00:01:25,020 --> 00:01:29,050
>> Ale můžeme neustále opakují tento proces,
zkoumá každý prvek v pořadí,

36
00:01:29,050 --> 00:01:31,720
doufat, že najdeme číslo 50.

37
00:01:31,720 --> 00:01:33,750
Ale my, ne-li vědět,
jsme našli číslo 50

38
00:01:33,750 --> 00:01:38,290
nebo pokud jsme neměli, dokud jste vstoupil
nad každého jednotlivého prvku matice.

39
00:01:38,290 --> 00:01:40,440
>> Jen jednou jsme udělali
to a přijít krátká,

40
00:01:40,440 --> 00:01:43,040
můžeme konstatovat, že
50 není v matici.

41
00:01:43,040 --> 00:01:46,410
A tak se lineární hledání
algoritmus, dobře to selhalo, samo o sobě.

42
00:01:46,410 --> 00:01:49,181
Ale ne v tom smyslu, že
byl neúspěšný v tom, co

43
00:01:49,181 --> 00:01:49,930
Zeptali jsme se ho udělat.

44
00:01:49,930 --> 00:01:52,390
>> To byl neúspěšný v as
stejně jako to nenašel 50,

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

46
00:01:54,070 --> 00:01:57,310
Ale my jsme důkladně prohledali
přes každé jednotlivé součásti

47
00:01:57,310 --> 00:02:00,550
a tak, když jsme nenašli
něco, lineární hledání stále

48
00:02:00,550 --> 00:02:05,230
úspěšné i když
element není v matici.

49
00:02:05,230 --> 00:02:07,507
>> Takže to, co je nejhorší případ
Scénář s lineární hledání?

50
00:02:07,507 --> 00:02:09,590
No musíme prohlédnout
každý prvek,

51
00:02:09,590 --> 00:02:14,590
a to buď proto, že cílový prvek
je poslední prvek pole,

52
00:02:14,590 --> 00:02:18,510
nebo prvek hledáme není
v poli skutečně existují vůbec.

53
00:02:18,510 --> 00:02:19,760
Jaký je nejlepší scénář?

54
00:02:19,760 --> 00:02:22,430
Tak bychom mohli najít
prvek okamžitě.

55
00:02:22,430 --> 00:02:24,360
A kolik prvků
my pak budou muset hledat

56
00:02:24,360 --> 00:02:26,859
u v nejlepším případě,
pokud se díváme na to

57
00:02:26,859 --> 00:02:28,400
a my ho najdeme na začátku?

58
00:02:28,400 --> 00:02:29,850
Můžeme se okamžitě zastaví.

59
00:02:29,850 --> 00:02:32,984
>> Co to říká o
Složitost lineární hledání?

60
00:02:32,984 --> 00:02:35,650
No v nejhorším případě, máme
podívat se na každé jednotlivé součásti.

61
00:02:35,650 --> 00:02:38,930
A tak to běží v O.
n, v nejhorším případě.

62
00:02:38,930 --> 00:02:41,540
>> V nejlepším případě, budeme
okamžitě najít prvek.

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

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

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

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