1
00:00:00,000 --> 00:00:02,892
>> [Predvaja glasba]

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

3
00:00:05,347 --> 00:00:07,180
Doug LLOYD: Linear
Iskanje je algoritem smo

4
00:00:07,180 --> 00:00:09,840
lahko uporabite, da bi našli element matrike.

5
00:00:09,840 --> 00:00:11,990
Algoritem odpoklic
je korak-po-korak set

6
00:00:11,990 --> 00:00:15,030
navodil za dokončanje naloge.

7
00:00:15,030 --> 00:00:17,480
>> Linearni iskanje
Algoritem deluje na naslednji način.

8
00:00:17,480 --> 00:00:22,200
Ponovil čez paleto od leve proti
Pravica, ki išče določen element.

9
00:00:22,200 --> 00:00:26,380
>> V psevdokoda, ki je bolj
destilirane različica tega stavka,

10
00:00:26,380 --> 00:00:29,840
če je prvi element je tisto
iščeš, se lahko ustavite.

11
00:00:29,840 --> 00:00:33,930
V nasprotnem primeru, se premaknete na naslednji element in
nadaljuj znova in znova, dokler ne boste našli

12
00:00:33,930 --> 00:00:36,389
element, ali pa ne.

13
00:00:36,389 --> 00:00:38,680
Tako bomo lahko uporabili linearno
iskalni algoritem, na primer,

14
00:00:38,680 --> 00:00:42,330
najti ciljno vrednost
devet v tem polju.

15
00:00:42,330 --> 00:00:43,870
No začnemo na začetku.

16
00:00:43,870 --> 00:00:45,970
Če je to tisto, kar smo
išče moremo ustaviti.

17
00:00:45,970 --> 00:00:47,890
Saj ne, ne bomo iskali 11.

18
00:00:47,890 --> 00:00:50,220
Torej drugače, se premaknite na naslednji element.

19
00:00:50,220 --> 00:00:51,510
>> Torej gledamo na 23.

20
00:00:51,510 --> 00:00:52,730
Je 23, kar iščemo?

21
00:00:52,730 --> 00:00:55,614
No no, tako da gremo na naslednjo
Element, naslednji element,

22
00:00:55,614 --> 00:00:57,780
in smo ostali šli skozi
ta postopek znova in znova

23
00:00:57,780 --> 00:01:01,030
in več, dokler ne bomo pristali
o situaciji, kot je ta.

24
00:01:01,030 --> 00:01:03,910
>> Devet je tisto, kar smo iskali,
in ta element matrike

25
00:01:03,910 --> 00:01:05,787
je, da je vrednost je devet.

26
00:01:05,787 --> 00:01:08,120
In tako smo ugotovili, kaj smo
išče, in ne moremo ustaviti.

27
00:01:08,120 --> 00:01:11,910
Linearni iskanje ima
končana uspešno.

28
00:01:11,910 --> 00:01:15,370
>> Ampak, kaj pa če smo iskali
element, ki ga ni v naši matriki.

29
00:01:15,370 --> 00:01:17,040
Ali linearno iskanje še vedno deluje?

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

31
00:01:17,540 --> 00:01:19,947
Tako smo ta postopek ponovite
izhajajoč iz prvega elementa.

32
00:01:19,947 --> 00:01:21,780
Če je to tisto, kar smo
išče moremo ustaviti.

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

34
00:01:22,800 --> 00:01:25,020
Sicer pa smo se premaknete na naslednji element.

35
00:01:25,020 --> 00:01:29,050
>> Vendar smo lahko ponavljajo ta proces,
preučuje vsak element v zameno

36
00:01:29,050 --> 00:01:31,720
v upanju, da bomo našli številko 50.

37
00:01:31,720 --> 00:01:33,750
Ampak ne bomo vedeli, če
Ugotovili smo številko 50

38
00:01:33,750 --> 00:01:38,290
ali če ne bomo storili, dokler ne bomo stopili
več kot vsak element matrike.

39
00:01:38,290 --> 00:01:40,440
>> Šele ko smo naredili
da in prišli do kratkega,

40
00:01:40,440 --> 00:01:43,040
lahko sklepamo, da
50 ni v matriki.

41
00:01:43,040 --> 00:01:46,410
In tako linearno iskanje
algoritem, tudi to ni uspelo, per se.

42
00:01:46,410 --> 00:01:49,181
Vendar ne v smislu, da je
ni bila uspešna pri tem, kaj

43
00:01:49,181 --> 00:01:49,930
smo ga prosili, da storiti.

44
00:01:49,930 --> 00:01:52,390
>> Leta, kot je bila neuspešna
toliko, kot je ni našel 50,

45
00:01:52,390 --> 00:01:54,070
vendar 50 ni v matriki.

46
00:01:54,070 --> 00:01:57,310
Vendar smo izčrpno iskali
skozi vsak element

47
00:01:57,310 --> 00:02:00,550
in tako, medtem ko nismo našli
karkoli, linearno iskanje vedno

48
00:02:00,550 --> 00:02:05,230
uspe tudi če
Element ni v matriki.

49
00:02:05,230 --> 00:02:07,507
>> Torej, kaj je v najslabšem primeru
Scenarij z linearnim iskanju?

50
00:02:07,507 --> 00:02:09,590
No, moramo odmisliti
vsak posamezen element,

51
00:02:09,590 --> 00:02:14,590
bodisi zato, ker je ciljna element
je zadnji element matrike,

52
00:02:14,590 --> 00:02:18,510
ali element, ki ga iščemo ne
v matriki pravzaprav sploh obstajajo.

53
00:02:18,510 --> 00:02:19,760
Kaj je najboljši scenarij?

54
00:02:19,760 --> 00:02:22,430
No, morda bomo našli
Element takoj.

55
00:02:22,430 --> 00:02:24,360
In koliko elementov
bomo potem morali pogledati

56
00:02:24,360 --> 00:02:26,859
na v najboljšem primeru
Če iščemo zanjo

57
00:02:26,859 --> 00:02:28,400
in smo ga našli na samem začetku?

58
00:02:28,400 --> 00:02:29,850
Mi lahko takoj ustavi.

59
00:02:29,850 --> 00:02:32,984
>> Kaj to povedati o
kompleksnost linearne iskanju?

60
00:02:32,984 --> 00:02:35,650
No, v najslabšem primeru pa imamo
gledati na vsak posamezen element.

61
00:02:35,650 --> 00:02:38,930
In tako teče v O
n, v najslabšem primeru.

62
00:02:38,930 --> 00:02:41,540
>> V najboljšem primeru bomo
takoj poiščite element.

63
00:02:41,540 --> 00:02:44,750
In tako teče v omega 1.

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

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

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