1
00:00:00,000 --> 00:00:02,892
>> [Muzikos grojimo]

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

3
00:00:05,347 --> 00:00:07,180
Doug LLOYD: Linijinis
paieška algoritmas mes

4
00:00:07,180 --> 00:00:09,840
galite naudoti norėdami rasti masyve elementų.

5
00:00:09,840 --> 00:00:11,990
Algoritmas Prisiminkite
yra žingsnis po žingsnio rinkinys

6
00:00:11,990 --> 00:00:15,030
Nurodymų pildymo užduotį.

7
00:00:15,030 --> 00:00:17,480
>> Linijinis paieška
algoritmas veikia taip.

8
00:00:17,480 --> 00:00:22,200
Pakartoti visoje masyvo iš kairės į
teisė, ieško tam tikro elemento.

9
00:00:22,200 --> 00:00:26,380
>> Be Pseudocode, kuri yra daugiau
distiliuotas versija šį sakinį,

10
00:00:26,380 --> 00:00:29,840
jei pirmasis elementas yra tai, kas
jūs ieškote, jūs galite sustabdyti.

11
00:00:29,840 --> 00:00:33,930
Priešingu atveju, pereiti prie kito elemento ir
nesustoti daugiau ir daugiau, kol rasite

12
00:00:33,930 --> 00:00:36,389
elementas, arba jūs neturite.

13
00:00:36,389 --> 00:00:38,680
Taigi, mes galime naudoti tiesinę
paieškos algoritmas, pavyzdžiui,

14
00:00:38,680 --> 00:00:42,330
rasti siektiną vertę
devynių šiame masyve.

15
00:00:42,330 --> 00:00:43,870
Na mes pradėti iš pradžių.

16
00:00:43,870 --> 00:00:45,970
Jei tai, ką mes
ieško, mes galime sustabdyti.

17
00:00:45,970 --> 00:00:47,890
Tai ne, mes ne ieško 11.

18
00:00:47,890 --> 00:00:50,220
Taigi, kitaip, pereiti prie kito elemento.

19
00:00:50,220 --> 00:00:51,510
>> Taigi, mes pažvelgti į 23.

20
00:00:51,510 --> 00:00:52,730
Ar 23 ką mes ko ieškote?

21
00:00:52,730 --> 00:00:55,614
Na ne, todėl mes pereiti į kitą
elementas, ir kitą elementas,

22
00:00:55,614 --> 00:00:57,780
ir mes nuolat išgyvena
šis procesas vėl ir vėl

23
00:00:57,780 --> 00:01:01,030
ir daugiau, kol mes žemę
dėl kaip šią situaciją.

24
00:01:01,030 --> 00:01:03,910
>> Devyni yra tai, ką mes ieškome,
ir šis masyvo elementas

25
00:01:03,910 --> 00:01:05,787
yra, tai yra, vertės nėra devyni.

26
00:01:05,787 --> 00:01:08,120
Ir todėl mes radome tai, ką mes
ieško, ir mes galime sustoti.

27
00:01:08,120 --> 00:01:11,910
Linijinis paieška turi
baigė sėkmingai.

28
00:01:11,910 --> 00:01:15,370
>> Bet ką apie tai, jei mes ieškome
elementas, kuris yra ne mūsų masyvo.

29
00:01:15,370 --> 00:01:17,040
Ar linijinis paieška vis dar dirba?

30
00:01:17,040 --> 00:01:17,540
Na tikrai.

31
00:01:17,540 --> 00:01:19,947
Taigi mes kartoti šį procesą
pradedant pirmojo elemento.

32
00:01:19,947 --> 00:01:21,780
Jei tai, ką mes
ieško, mes galime sustabdyti.

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

34
00:01:22,800 --> 00:01:25,020
Priešingu atveju, mes judėti į kitą elementą.

35
00:01:25,020 --> 00:01:29,050
>> Tačiau mes galime nuolat kartoti šį procesą,
nagrinėja kiekvieną elementą savo ruožtu,

36
00:01:29,050 --> 00:01:31,720
tikiuosi, kad mes rasti skaičių 50.

37
00:01:31,720 --> 00:01:33,750
Bet mes nežinome, jei
mes pastebėjome skaičių 50

38
00:01:33,750 --> 00:01:38,290
arba jei mes padarėme ne, kol mes sustiprino
per kiekvieną elementą masyvo.

39
00:01:38,290 --> 00:01:40,440
>> Tik tada, kai mes padarėme
kad ir sugalvoti trumpas,

40
00:01:40,440 --> 00:01:43,040
galime daryti išvadą, kad
50 yra ne masyvo.

41
00:01:43,040 --> 00:01:46,410
Ir taip linijinis paieška
algoritmas, gerai ji nepavyko, per se.

42
00:01:46,410 --> 00:01:49,181
Bet ne ta prasme, kad jį
buvo nesėkmingas daryti tai, ką

43
00:01:49,181 --> 00:01:49,930
mes paprašėme ją daryti.

44
00:01:49,930 --> 00:01:52,390
>> Tai buvo nesėkmingas, nes
kiek ji nerado 50,

45
00:01:52,390 --> 00:01:54,070
bet 50 buvo ne masyvo.

46
00:01:54,070 --> 00:01:57,310
Bet mes turime išsamiai ieškoma
per kiekvieną elementą

47
00:01:57,310 --> 00:02:00,550
ir taip, o neradome
nieko, linijinis paieška vis dar

48
00:02:00,550 --> 00:02:05,230
pavyksta, net jei
elementas yra ne masyvo.

49
00:02:05,230 --> 00:02:07,507
>> Taigi, kas blogiausiu atveju
scenarijus su linijiniu paieškoje?

50
00:02:07,507 --> 00:02:09,590
Na, mes turime pažvelgti pro
kiekvienas elementas,

51
00:02:09,590 --> 00:02:14,590
arba todėl, kad tikslinė elementas
yra paskutinis elementas masyve,

52
00:02:14,590 --> 00:02:18,510
ar elementas mes ieškome ne
iš tikrųjų egzistuoja masyvo ne visiems.

53
00:02:18,510 --> 00:02:19,760
Koks geriausias scenarijus?

54
00:02:19,760 --> 00:02:22,430
Na, mes galime rasti
elementas iš karto.

55
00:02:22,430 --> 00:02:24,360
Ir kiek elementai
mes tada turite ieškoti

56
00:02:24,360 --> 00:02:26,859
ne geriausiu atveju,
jei mes ieškome jai

57
00:02:26,859 --> 00:02:28,400
ir mes rasti pačioje pradžioje?

58
00:02:28,400 --> 00:02:29,850
Mes galime nedelsiant nutraukti.

59
00:02:29,850 --> 00:02:32,984
>> Ką tai sako apie
sudėtingumas tiesinės paieškoje?

60
00:02:32,984 --> 00:02:35,650
Na, blogiausiu atveju, mes turime
pažvelgti į kiekvieną elementą.

61
00:02:35,650 --> 00:02:38,930
Ir todėl jis veikia O
N, blogiausiu atveju.

62
00:02:38,930 --> 00:02:41,540
>> Geriausiu atveju, mes gonna
iš karto rasti elementą.

63
00:02:41,540 --> 00:02:44,750
Ir taip eina omega 1.

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

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

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