1
00:00:00,000 --> 00:00:02,892
>> [Muusika mängib]

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

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Linear
otsingu algoritmi me

4
00:00:07,180 --> 00:00:09,840
saab kasutada, et leida element massiivi.

5
00:00:09,840 --> 00:00:11,990
Algoritm tagasikutsumine
on samm-sammult komplekt

6
00:00:11,990 --> 00:00:15,030
käskude täitmise ülesanne.

7
00:00:15,030 --> 00:00:17,480
>> Lineaarse otsing
algoritmi toimib järgmiselt.

8
00:00:17,480 --> 00:00:22,200
Käi kogu massiivi vasakult
õige, otsin teatud element.

9
00:00:22,200 --> 00:00:26,380
>> In pseudokoodi, mis on rohkem
destilleeritud versioon sellest lausest,

10
00:00:26,380 --> 00:00:29,840
kui esimene element on see, mida
otsite, saate peatada.

11
00:00:29,840 --> 00:00:33,930
Muidu liikuda järgmisele element ja
jätkame ikka ja jälle, kuni sa leiad

12
00:00:33,930 --> 00:00:36,389
element, või ei ole.

13
00:00:36,389 --> 00:00:38,680
Nii saame kasutada lineaarset
otsingu algoritm, näiteks

14
00:00:38,680 --> 00:00:42,330
leida sihtväärtust
Üheksa selle massiivi.

15
00:00:42,330 --> 00:00:43,870
Noh me alustame algusest.

16
00:00:43,870 --> 00:00:45,970
Kui see on see, mida me oleme
otsin, saame lõpetada.

17
00:00:45,970 --> 00:00:47,890
See ei ole, et me ei otsi 11.

18
00:00:47,890 --> 00:00:50,220
Nii muidu liikuda järgmisele element.

19
00:00:50,220 --> 00:00:51,510
>> Nii me vaatame 23.

20
00:00:51,510 --> 00:00:52,730
Kas 23, mida me otsime?

21
00:00:52,730 --> 00:00:55,614
Noh ole, nii et me liigume edasi järgmise
element, ja järgmine element,

22
00:00:55,614 --> 00:00:57,780
ja me jätkame läbi
Selle protsessi üle ja üle

23
00:00:57,780 --> 00:01:01,030
ja jälle, kuni me maa
kohta sellises olukorras.

24
00:01:01,030 --> 00:01:03,910
>> Üheksa mida me otsime,
ja see element massiivi

25
00:01:03,910 --> 00:01:05,787
on see väärtus on üheksa.

26
00:01:05,787 --> 00:01:08,120
Ja nii me leidsime me oleme
otsin, ja me ei saa peatada.

27
00:01:08,120 --> 00:01:11,910
Lineaarse otsing on
lõpetatud edukalt.

28
00:01:11,910 --> 00:01:15,370
>> Aga kui me otsime
element, mis ei ole meie rida.

29
00:01:15,370 --> 00:01:17,040
Kas lineaarne otsing veel tööd?

30
00:01:17,040 --> 00:01:17,540
Noh kindel.

31
00:01:17,540 --> 00:01:19,947
Nii me kordame seda protsessi
alates esimesest element.

32
00:01:19,947 --> 00:01:21,780
Kui see on see, mida me oleme
otsin, saame lõpetada.

33
00:01:21,780 --> 00:01:22,800
See ei ole.

34
00:01:22,800 --> 00:01:25,020
Muidu me liikuda järgmise elemendi.

35
00:01:25,020 --> 00:01:29,050
>> Aga me ei saa hoida korrates seda protsessi,
uurida iga element omakorda

36
00:01:29,050 --> 00:01:31,720
lootes, et leiame number 50.

37
00:01:31,720 --> 00:01:33,750
Aga me ei tea, kas
Leidsime number 50

38
00:01:33,750 --> 00:01:38,290
või kui me ei ole, kuni oleme astunud
üle iga element massiivi.

39
00:01:38,290 --> 00:01:40,440
>> Alles siis, kui me oleme teinud
seda ja tulla lühike,

40
00:01:40,440 --> 00:01:43,040
saame järeldada, et
50 ei ole massiiv.

41
00:01:43,040 --> 00:01:46,410
Ja nii lineaarne otsing
algoritm, hästi see ei õnnestunud, per se.

42
00:01:46,410 --> 00:01:49,181
Aga mitte selles mõttes, et see
ei õnnestunud seda, mida

43
00:01:49,181 --> 00:01:49,930
Palusime tal seda teha.

44
00:01:49,930 --> 00:01:52,390
>> See ei õnnestunud, kuna
palju kui ta ei leidnud 50,

45
00:01:52,390 --> 00:01:54,070
kuid 50 ei olnud valikut.

46
00:01:54,070 --> 00:01:57,310
Aga me oleme ammendavalt otsisid
läbi iga element

47
00:01:57,310 --> 00:02:00,550
ja nii, kui me ei leia
midagi, lineaarne otsing veel

48
00:02:00,550 --> 00:02:05,230
õnnestub isegi kui
element ei massiivi.

49
00:02:05,230 --> 00:02:07,507
>> Mis siis halvimal juhul
stsenaarium lineaarne otsing?

50
00:02:07,507 --> 00:02:09,590
Noh me peame vaatama läbi
iga element,

51
00:02:09,590 --> 00:02:14,590
kas sellepärast, et siht element
on viimane element massiivi,

52
00:02:14,590 --> 00:02:18,510
või element ootame ei
tegelikult on olemas massiiv üldse.

53
00:02:18,510 --> 00:02:19,760
Milline on parim stsenaarium?

54
00:02:19,760 --> 00:02:22,430
Noh me võiksime leida
element kohe.

55
00:02:22,430 --> 00:02:24,360
Ja kui palju elemente
Kas me siis peame vaatama

56
00:02:24,360 --> 00:02:26,859
kell parimal juhul
Kui me vaatame seda

57
00:02:26,859 --> 00:02:28,400
ja me leiame ta alguses?

58
00:02:28,400 --> 00:02:29,850
Saame kohe lõpetada.

59
00:02:29,850 --> 00:02:32,984
>> Mida see öelda
keerukust lineaarne otsing?

60
00:02:32,984 --> 00:02:35,650
Noh halvimal juhul on meil
vaadata iga element.

61
00:02:35,650 --> 00:02:38,930
Ja nii see kulgeb O
n, halvimal juhul.

62
00:02:38,930 --> 00:02:41,540
>> Parimal juhul me teeme
leida element kohe.

63
00:02:41,540 --> 00:02:44,750
Ja nii jookseb omega 1.

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

65
00:02:45,780 --> 00:02:48,020
See on CS50.

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