1
00:00:00,000 --> 00:00:02,892
>> [TÓNLIST spila]

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

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Línuleg
leit er reiknirit við

4
00:00:07,180 --> 00:00:09,840
Hægt er að nota til að finna stak í fylki.

5
00:00:09,840 --> 00:00:11,990
Reiknirit muna
er skref-fyrir-skref sett

6
00:00:11,990 --> 00:00:15,030
leiðbeiningar um að ljúka verkefni.

7
00:00:15,030 --> 00:00:17,480
>> The línuleg leit
reiknirit virkar eins og hér segir.

8
00:00:17,480 --> 00:00:22,200
Iterate yfir fylking frá vinstri til
rétt, að tiltekinn þáttur.

9
00:00:22,200 --> 00:00:26,380
>> Í sauðakóðanum, sem er meira
eimað útgáfa af þessari setningu,

10
00:00:26,380 --> 00:00:29,840
ef fyrsti þátturinn er það
þú ert að leita að, getur þú hættir.

11
00:00:29,840 --> 00:00:33,930
Annars, að fara á næsta frumefni og
halda áfram aftur og aftur þar til þú finnur

12
00:00:33,930 --> 00:00:36,389
þáttur, eða þú hefur ekki.

13
00:00:36,389 --> 00:00:38,680
Þannig að við getum notað línulegan
leit reiknirit, til dæmis,

14
00:00:38,680 --> 00:00:42,330
að finna markgildið
níu í þessu fylki.

15
00:00:42,330 --> 00:00:43,870
Jæja við byrjum á byrjuninni.

16
00:00:43,870 --> 00:00:45,970
Ef það er það sem við erum
að leita að, getum við hætt.

17
00:00:45,970 --> 00:00:47,890
Það er ekki, við erum ekki að leita að 11.

18
00:00:47,890 --> 00:00:50,220
Svo annars, að fara á næsta frumefni.

19
00:00:50,220 --> 00:00:51,510
>> Þannig að við lítum á 23.

20
00:00:51,510 --> 00:00:52,730
Er 23 það sem við erum að leita að?

21
00:00:52,730 --> 00:00:55,614
Jæja nei, svo við fara til the næstur
þáttur, og næsta frumefni,

22
00:00:55,614 --> 00:00:57,780
og við höldum að fara í gegnum
þetta ferli aftur og aftur

23
00:00:57,780 --> 00:01:01,030
og aftur, þar til við lendum
á aðstæðum eins og þetta.

24
00:01:01,030 --> 00:01:03,910
>> Níu er það sem við erum að leita að,
og þessi þáttur í fylkinu

25
00:01:03,910 --> 00:01:05,787
er það gildi er níu.

26
00:01:05,787 --> 00:01:08,120
Og svo við fundum það sem við erum
að leita að, og við getum hætt.

27
00:01:08,120 --> 00:01:11,910
The línuleg leit hefur
lokið, með góðum árangri.

28
00:01:11,910 --> 00:01:15,370
>> En hvað um ef við erum að leita að
þáttur sem er ekki í fylking okkar.

29
00:01:15,370 --> 00:01:17,040
Er línuleg leit vinna enn?

30
00:01:17,040 --> 00:01:17,540
Jæja viss.

31
00:01:17,540 --> 00:01:19,947
Þannig að við endurtaka þetta ferli
byrja á fyrstu frumefni.

32
00:01:19,947 --> 00:01:21,780
Ef það er það sem við erum
að leita að, getum við hætt.

33
00:01:21,780 --> 00:01:22,800
Það er ekki.

34
00:01:22,800 --> 00:01:25,020
Annars, hreyfa við á næsta frumefni.

35
00:01:25,020 --> 00:01:29,050
>> En við getum halda að endurtaka þetta ferli,
skoða hvert frumefni aftur,

36
00:01:29,050 --> 00:01:31,720
vona að við finnum fjölda 50.

37
00:01:31,720 --> 00:01:33,750
En við munum ekki vita ef
við höfum fundið númer 50

38
00:01:33,750 --> 00:01:38,290
eða ef við gerðum ekki, fyrr en við höfum stigið
yfir hvert einasta þáttur í array.

39
00:01:38,290 --> 00:01:40,440
>> Aðeins þegar við höfum gert
sem og að koma upp stutt,

40
00:01:40,440 --> 00:01:43,040
við getum gert að
50 er ekki í fylkinu.

41
00:01:43,040 --> 00:01:46,410
Og svo línuleg leit
reiknirit, vel það tókst ekki, í sjálfu sér.

42
00:01:46,410 --> 00:01:49,181
En ekki í þeim skilningi að það
var misheppnaður í að gera það

43
00:01:49,181 --> 00:01:49,930
spurði við það að gera.

44
00:01:49,930 --> 00:01:52,390
>> Það var misheppnaður í eins
mikið og það var ekki að finna 50,

45
00:01:52,390 --> 00:01:54,070
en 50 var ekki í array.

46
00:01:54,070 --> 00:01:57,310
En við höfum tæmandi leitað
í gegnum hvert einasta þáttur

47
00:01:57,310 --> 00:02:00,550
og svo, á meðan við höfum ekki fundið
nokkuð, línuleg leit samt

48
00:02:00,550 --> 00:02:05,230
tekst jafnvel þótt
þátturinn er ekki í fylkinu.

49
00:02:05,230 --> 00:02:07,507
>> Svo er það versta
dæmi með línuleg leit?

50
00:02:07,507 --> 00:02:09,590
Jæja við verðum að líta í gegnum
hvert einasta þáttur,

51
00:02:09,590 --> 00:02:14,590
annaðhvort vegna þess að miða þáttur
er síðasta þáttur í array,

52
00:02:14,590 --> 00:02:18,510
eða þátturinn sem við erum að leita að er ekki
í raun fyrir hendi í fylkinu yfirleitt.

53
00:02:18,510 --> 00:02:19,760
Hvað er besta falli?

54
00:02:19,760 --> 00:02:22,430
Jæja við gætum fundið
þáttur strax.

55
00:02:22,430 --> 00:02:24,360
Og hversu margir þættir
höfum við þá að leita

56
00:02:24,360 --> 00:02:26,859
á í besta tilfelli,
ef við erum að leita að því

57
00:02:26,859 --> 00:02:28,400
og við finnum það í upphafi?

58
00:02:28,400 --> 00:02:29,850
Við getum hætt strax.

59
00:02:29,850 --> 00:02:32,984
>> Hvað þýðir þetta að segja um
flókið línuleg leit?

60
00:02:32,984 --> 00:02:35,650
Jæja í versta tilfelli, höfum við
að líta á hvert einasta þáttur.

61
00:02:35,650 --> 00:02:38,930
Og svo það rennur í O frá
n, í versta tilfelli.

62
00:02:38,930 --> 00:02:41,540
>> Í besta tilfelli, við erum ađ
finna þáttur strax.

63
00:02:41,540 --> 00:02:44,750
Og svo keyrir omega af 1.

64
00:02:44,750 --> 00:02:45,780
>> Ég er Doug Lloyd.

65
00:02:45,780 --> 00:02:48,020
Þetta er CS50.

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