1
00:00:00,000 --> 00:00:02,892
>> [Muzika]

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

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Linear
Kërkimi është një algoritmi ne

4
00:00:07,180 --> 00:00:09,840
mund të përdorni për të gjetur një element në një rrjet.

5
00:00:09,840 --> 00:00:11,990
Një risjell algoritëm
është një grup hap-pas-hapi

6
00:00:11,990 --> 00:00:15,030
Udhëzimet për plotësimin e një detyre.

7
00:00:15,030 --> 00:00:17,480
>> Kërkimi lineare
algorithm punon si vijon.

8
00:00:17,480 --> 00:00:22,200
Iterate nëpër rrjet nga e majta në të
e drejtë, duke kërkuar për një element të caktuar.

9
00:00:22,200 --> 00:00:26,380
>> Në pseudokod, e cila është më e
version i distiluar i këtij dënimi,

10
00:00:26,380 --> 00:00:29,840
elementi i parë në qoftë se është ajo
ju jeni duke kërkuar për të, ju mund të ndalojë.

11
00:00:29,840 --> 00:00:33,930
Përndryshe, të shkojë në elementin e ardhshëm dhe
do të mbajë mbi dhe mbi derisa ju të gjeni

12
00:00:33,930 --> 00:00:36,389
element, ose ju nuk e bëni.

13
00:00:36,389 --> 00:00:38,680
Kështu që ne mund të përdorni lineare
Kërkimi algorithm, për shembull,

14
00:00:38,680 --> 00:00:42,330
për të gjetur vlerën e synuar
nëntë në këtë grup.

15
00:00:42,330 --> 00:00:43,870
E pra ne të fillojë në fillim.

16
00:00:43,870 --> 00:00:45,970
Në qoftë se kjo është ajo që ne jemi
në kërkim të, ne mund të ndalet.

17
00:00:45,970 --> 00:00:47,890
Kjo nuk është, ne nuk jemi duke kërkuar për 11.

18
00:00:47,890 --> 00:00:50,220
Pra ndryshe, të shkojë në elementin e ardhshëm.

19
00:00:50,220 --> 00:00:51,510
>> Pra, ne shikojmë në 23.

20
00:00:51,510 --> 00:00:52,730
Është 23 atë që ne jemi duke kërkuar për?

21
00:00:52,730 --> 00:00:55,614
E pra jo, kështu që ne të lëvizin në të ardhshëm
element, dhe element tjetër,

22
00:00:55,614 --> 00:00:57,780
dhe do të vazhdojmë duke shkuar nëpër
ky proces pa pushim

23
00:00:57,780 --> 00:01:01,030
dhe mbi, deri ne toke
në një situatë si kjo.

24
00:01:01,030 --> 00:01:03,910
>> Nëntë është ajo që ne jemi duke kërkuar për,
dhe ky element i vektorit

25
00:01:03,910 --> 00:01:05,787
është, kjo është vlerë është nëntë.

26
00:01:05,787 --> 00:01:08,120
Dhe kështu kemi gjetur atë që ne jemi
kërkoni, dhe ne mund të ndalet.

27
00:01:08,120 --> 00:01:11,910
Kërkimi lineare ka
përfundoi, me sukses.

28
00:01:11,910 --> 00:01:15,370
>> Por ajo që për në qoftë se ne jemi duke kërkuar për
një element që nuk është në rrjet tonë.

29
00:01:15,370 --> 00:01:17,040
A kërkimit linear ende punë?

30
00:01:17,040 --> 00:01:17,540
Edhe i sigurt.

31
00:01:17,540 --> 00:01:19,947
Pra, ne përsëris këtë proces
duke filluar në elementin e parë.

32
00:01:19,947 --> 00:01:21,780
Në qoftë se kjo është ajo që ne jemi
në kërkim të, ne mund të ndalet.

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

34
00:01:22,800 --> 00:01:25,020
Përndryshe, ne shkojmë në elementin e ardhshëm.

35
00:01:25,020 --> 00:01:29,050
>> Por ne mund të mbani përsëritur këtë proces,
shqyrtuar çdo element nga ana tjetër,

36
00:01:29,050 --> 00:01:31,720
duke shpresuar se ne gjejmë numrin 50.

37
00:01:31,720 --> 00:01:33,750
Por ne nuk do të dimë nëse
ne kemi gjetur numrin 50

38
00:01:33,750 --> 00:01:38,290
ose në qoftë se ne nuk e bëri, deri sa ne kemi rritur
mbi çdo element të vetëm të vektorit.

39
00:01:38,290 --> 00:01:40,440
>> Vetëm një herë ne kemi bërë
se dhe ardhur deri të shkurtër,

40
00:01:40,440 --> 00:01:43,040
mund të arrijmë në përfundimin se
50 nuk eshte ne vektorit.

41
00:01:43,040 --> 00:01:46,410
Dhe kështu Kërkimi lineare
algorithm, edhe ajo nuk arriti, në vetvete.

42
00:01:46,410 --> 00:01:49,181
Por jo në kuptimin se ajo
ishte i pasuksesshëm në duke bërë atë

43
00:01:49,181 --> 00:01:49,930
kemi kërkuar atë për të bërë.

44
00:01:49,930 --> 00:01:52,390
>> Ajo ishte i pasuksesshëm në si
më shumë që ajo nuk ka gjetur 50,

45
00:01:52,390 --> 00:01:54,070
por 50 nuk ishte në rrjet.

46
00:01:54,070 --> 00:01:57,310
Por ne kemi kërkuar në mënyrë shteruese
përmes çdo element të vetme

47
00:01:57,310 --> 00:02:00,550
dhe kështu, ndërsa ne nuk ka gjetur
çdo gjë, kërko lineare ende

48
00:02:00,550 --> 00:02:05,230
pason edhe nëse
element nuk është në vektorit.

49
00:02:05,230 --> 00:02:07,507
>> Pra, çfarë është rasti më i keq
Skenari me kërkim linear?

50
00:02:07,507 --> 00:02:09,590
E pra ne duhet të shohim përmes
çdo element i vetëm,

51
00:02:09,590 --> 00:02:14,590
ose për shkak se elementi objektiv
është elementi i fundit i vektorit,

52
00:02:14,590 --> 00:02:18,510
ose elementi ne jemi duke kërkuar për nuk ka
në fakt ekzistojnë në rrjet në të gjitha.

53
00:02:18,510 --> 00:02:19,760
Çfarë është skenari më i mirë?

54
00:02:19,760 --> 00:02:22,430
Edhe ne mund të gjeni
element menjëherë.

55
00:02:22,430 --> 00:02:24,360
Dhe sa elemente
nuk kemi atëherë duhet të shohim

56
00:02:24,360 --> 00:02:26,859
në në rastin më të mirë,
në qoftë se ne jemi duke kërkuar për të

57
00:02:26,859 --> 00:02:28,400
dhe ne gjejmë atë në fillim?

58
00:02:28,400 --> 00:02:29,850
Ne mund të ndalet menjëherë.

59
00:02:29,850 --> 00:02:32,984
>> Çfarë do të thotë kjo në lidhje me
Kompleksiteti i kërkimit lineare?

60
00:02:32,984 --> 00:02:35,650
Edhe në rastin më të keq, ne kemi
për të parë në çdo element të vetëm.

61
00:02:35,650 --> 00:02:38,930
Dhe kështu ajo shkon në O e
n, në rastin më të keq.

62
00:02:38,930 --> 00:02:41,540
>> Në rastin më të mirë, ne jemi gonna të
gjeni elementin menjëherë.

63
00:02:41,540 --> 00:02:44,750
Dhe kështu shkon në omega e 1.

64
00:02:44,750 --> 00:02:45,780
>> Unë jam Doug Lloyd.

65
00:02:45,780 --> 00:02:48,020
Kjo është CS50.

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