1
00:00:00,000 --> 00:00:05,830

2
00:00:05,830 --> 00:00:07,910
>> Të gjithë të drejtë, kështu që, kompleksiteti kompjuterike.

3
00:00:07,910 --> 00:00:10,430
Vetëm pak e një paralajmërim
para se të zhyten në diskutim edhe far--

4
00:00:10,430 --> 00:00:13,070
kjo ndoshta do të jetë në mesin e
më të matematikës, të rënda gjëra

5
00:00:13,070 --> 00:00:14,200
ne flasim për në CS50.

6
00:00:14,200 --> 00:00:16,950
Shpresojmë se nuk do të jetë shumë e madhe
dhe ne do të përpiqemi dhe të ju udhëzojë

7
00:00:16,950 --> 00:00:19,200
nëpërmjet procesit, por
vetëm një grimë e një paralajmërim të drejtë.

8
00:00:19,200 --> 00:00:21,282
Ka pak
i matematikës të përfshira këtu.

9
00:00:21,282 --> 00:00:23,990
Të gjithë të drejtë, kështu që në mënyrë për të bërë
përdorimi i burimeve tona kompjuterike

10
00:00:23,990 --> 00:00:28,170
në world-- e vërtetë është e vërtetë
e rëndësishme për të kuptuar algoritme

11
00:00:28,170 --> 00:00:30,750
dhe se si ata përpunojnë të dhëna.

12
00:00:30,750 --> 00:00:32,810
Në qoftë se ne kemi një të vërtetë
algoritmi efikas, ne

13
00:00:32,810 --> 00:00:36,292
mund të minimizuar shumën e burimeve
ne kemi në dispozicion për t'u marrë me të.

14
00:00:36,292 --> 00:00:38,750
Në qoftë se ne kemi një algoritëm që
do të marrë një shumë punë

15
00:00:38,750 --> 00:00:41,210
për të përpunuar një të vërtetë
grup i madh i të dhënave, kjo është

16
00:00:41,210 --> 00:00:44,030
do të kërkojë më shumë
dhe më shumë burime, të cilat

17
00:00:44,030 --> 00:00:47,980
është e para, RAM, të gjitha atë lloj stuff.

18
00:00:47,980 --> 00:00:52,090
>> Pra, duke qenë në gjendje për të analizuar një
algorithm përdorur këtë set mjet,

19
00:00:52,090 --> 00:00:56,110
në thelb, kërkon question--
si e bën këtë shkallë algorithm

20
00:00:56,110 --> 00:00:59,020
si ne hedhin të dhënat e më shumë në atë?

21
00:00:59,020 --> 00:01:02,220
Në CS50, sasinë e të dhënave që ne jemi
duke punuar me është shumë i vogël.

22
00:01:02,220 --> 00:01:05,140
Në përgjithësi, programet tona janë duke shkuar
për të kandiduar në një të dytë apo less--

23
00:01:05,140 --> 00:01:07,830
ndoshta shumë më pak
veçanërisht në fillim.

24
00:01:07,830 --> 00:01:12,250
>> Por mendoni për një kompani që merret
me qindra e miliona konsumatorëve.

25
00:01:12,250 --> 00:01:14,970
Dhe ata kanë nevojë për një proces
se të dhënat e konsumatorëve.

26
00:01:14,970 --> 00:01:18,260
Ndërsa numri i klientëve që ata
kanë merr më të mëdha,

27
00:01:18,260 --> 00:01:21,230
ajo do të kërkojë
gjithnjë e më shumë burime.

28
00:01:21,230 --> 00:01:22,926
Sa më tepër burime?

29
00:01:22,926 --> 00:01:25,050
E pra, kjo varet se si
ne analizuar algoritmin,

30
00:01:25,050 --> 00:01:28,097
duke përdorur mjetet në këtë Toolbox.

31
00:01:28,097 --> 00:01:31,180
Kur ne flasim për kompleksitetin e
një algorithm-- që ndonjëherë ju do të

32
00:01:31,180 --> 00:01:34,040
dëgjojë atë referuara si kohë
Kompleksiteti ose hapësirë ​​kompleksitetin

33
00:01:34,040 --> 00:01:36,190
por ne jemi vetëm duke shkuar
për të thirrur complexity--

34
00:01:36,190 --> 00:01:38,770
ne jemi përgjithësisht duke folur për
skenari më i keq-rast.

35
00:01:38,770 --> 00:01:42,640
Duke pasur parasysh grumbull absolute më e keqe e
të dhëna që ne mund të jetë hedhur në të,

36
00:01:42,640 --> 00:01:46,440
si është ky algoritëm do të
përpunojnë ose merren me këto të dhëna?

37
00:01:46,440 --> 00:01:51,450
Ne në përgjithësi e quajmë më të keq
Runtime e një algoritmi të mëdha-O.

38
00:01:51,450 --> 00:01:56,770
Pra, një algoritmi mund të thuhet se
drejtuar në O e n ose o të n katror.

39
00:01:56,770 --> 00:01:59,110
Dhe më shumë në lidhje me atë
ata që do të thotë në një të dytë.

40
00:01:59,110 --> 00:02:01,620
>> Ndonjëherë, edhe pse, ne bëjmë kujdes
në lidhje me rastin më të mirë.

41
00:02:01,620 --> 00:02:05,400
Nëse të dhënat është çdo gjë ne kemi kërkuar
ajo të jetë dhe kjo ishte absolutisht e përsosur

42
00:02:05,400 --> 00:02:09,630
dhe ne kemi qenë të dërguar këtë të përsosur
të vendosur e të dhënave përmes algorithm tonë.

43
00:02:09,630 --> 00:02:11,470
Si do të trajtojë në atë situatë?

44
00:02:11,470 --> 00:02:15,050
Ne nganjëherë referohen se si
madh-Omega, kështu që në kontrast me të madhe-O,

45
00:02:15,050 --> 00:02:16,530
ne kemi big-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega për rastin më të mirë.

47
00:02:18,880 --> 00:02:21,319
Big-O për skenarin më të keq.

48
00:02:21,319 --> 00:02:23,860
Në përgjithësi, kur flasim për
kompleksiteti i një algoritmi,

49
00:02:23,860 --> 00:02:26,370
ne jemi duke folur për
rastin më të keq skenari.

50
00:02:26,370 --> 00:02:28,100
Pra, mbani në mend.

51
00:02:28,100 --> 00:02:31,510
>> Dhe në këtë klasë, ne jemi duke shkuar në përgjithësi
për të lënë analizë rigoroze mënjanë.

52
00:02:31,510 --> 00:02:35,350
Nuk janë shkencat dhe fusha
përkushtuar për këtë lloj stuff.

53
00:02:35,350 --> 00:02:37,610
Kur ne flasim për arsyetim
përmes algoritme,

54
00:02:37,610 --> 00:02:41,822
që ne do të bëjmë copë-nga-pjesë për shumë
Algoritme flasim për në klasë.

55
00:02:41,822 --> 00:02:44,780
Ne jemi me të vërtetë vetëm duke folur për
arsyetuar nëpërmjet saj me sens të përbashkët,

56
00:02:44,780 --> 00:02:47,070
jo me formula, apo provave,
apo diçka të tillë.

57
00:02:47,070 --> 00:02:51,600
Pra, mos u bëni merak, ne nuk do të jetë
duke u kthyer në një klasë të madhe të matematikës.

58
00:02:51,600 --> 00:02:55,920
>> Kështu që unë tha se ne kujdesemi për kompleksitetin
sepse ai bën pyetjen, se si

59
00:02:55,920 --> 00:03:00,160
e algoritme tonë të trajtojë më të mëdha dhe
dhënave grupe të mëdha duke u hedhur në to.

60
00:03:00,160 --> 00:03:01,960
E pra, ajo që është një grup të dhënat?

61
00:03:01,960 --> 00:03:03,910
Çfarë dua të them kur kam thënë se?

62
00:03:03,910 --> 00:03:07,600
Kjo do të thotë çfarëdo që e bën më
kuptim në kontekst, të jetë i sinqertë.

63
00:03:07,600 --> 00:03:11,160
Në qoftë se ne kemi një algoritëm, i
Proceset Strings-- ne jemi me siguri

64
00:03:11,160 --> 00:03:13,440
duke folur në lidhje me madhësinë e vargut.

65
00:03:13,440 --> 00:03:15,190
Kjo është të dhënat set--
madhësia, numri

66
00:03:15,190 --> 00:03:17,050
e karaktereve që përbëjnë vargun.

67
00:03:17,050 --> 00:03:20,090
Në qoftë se ne jemi duke folur për një
algorithm se proceset fotografi,

68
00:03:20,090 --> 00:03:23,930
ne mund të flasim për mënyrën se si
shumë kilobytes e përbëjnë këtë dosje.

69
00:03:23,930 --> 00:03:25,710
Dhe kjo është tërësia e të dhënave.

70
00:03:25,710 --> 00:03:28,870
Në qoftë se ne jemi duke folur për një algoritmi
që trajton vargjeve më në përgjithësi,

71
00:03:28,870 --> 00:03:31,510
të tilla si algoritme sorting
ose të kërkoni algoritme,

72
00:03:31,510 --> 00:03:36,690
ne jemi ndoshta duke folur për numrin
e elementeve që përbëjnë një koleksion.

73
00:03:36,690 --> 00:03:39,272
>> Tani, ne mund të masë një
algorithm-- në mënyrë të veçantë,

74
00:03:39,272 --> 00:03:40,980
kur unë them që ne mund të
të matur një algoritëm, unë

75
00:03:40,980 --> 00:03:43,840
thotë që ne mund të masë se sa
shumë burime ajo merr.

76
00:03:43,840 --> 00:03:48,990
Nëse këto burime janë, sa
bytes RAM-- ose MB RAM

77
00:03:48,990 --> 00:03:49,790
ajo përdor.

78
00:03:49,790 --> 00:03:52,320
Apo se sa kohë duhet për të drejtuar.

79
00:03:52,320 --> 00:03:56,200
Dhe ne mund ta quajmë këtë
matur, në mënyrë arbitrare, f e n.

80
00:03:56,200 --> 00:03:59,420
Ku n është numri i
elementet në grupin e të dhënave.

81
00:03:59,420 --> 00:04:02,640
Dhe f e n është se si shumë ca.

82
00:04:02,640 --> 00:04:07,530
Sa njësitë e burimeve të bën
ajo kërkon për të përpunuar këto të dhëna.

83
00:04:07,530 --> 00:04:10,030
>> Tani, ne fakt nuk e kujdesit
për atë f e n është pikërisht.

84
00:04:10,030 --> 00:04:13,700
Në fakt, ne shumë rrallë will--
sigurisht do të kurrë në këtë unë class--

85
00:04:13,700 --> 00:04:18,709
zhyten në ndonjë të vërtetë të thellë
Analiza e asaj f e n është.

86
00:04:18,709 --> 00:04:23,510
Ne jemi vetëm do të flasim për atë që f të
n është rreth, ose çfarë ajo tenton për të.

87
00:04:23,510 --> 00:04:27,600
Dhe tendenca e një algoritmi është
diktuar nga urdhër mandatit të tij më të lartë.

88
00:04:27,600 --> 00:04:29,440
Dhe ne mund të shohim se çfarë unë
të them me këtë, duke marrë

89
00:04:29,440 --> 00:04:31,910
një vështrim në një shembull më konkret.

90
00:04:31,910 --> 00:04:34,620
>> Pra, le të themi se ne kemi
tre algoritme të ndryshme.

91
00:04:34,620 --> 00:04:39,350
E para e cila merr n
Cubed, disa njësi të burimeve

92
00:04:39,350 --> 00:04:42,880
për të përpunuar një sërë të dhënash me madhësi n.

93
00:04:42,880 --> 00:04:47,000
Ne kemi një algoritëm të dytë që merr
n cubed plus burimet forme katrore n

94
00:04:47,000 --> 00:04:49,350
për të përpunuar një sërë të dhënash me madhësi n.

95
00:04:49,350 --> 00:04:52,030
Dhe ne kemi një të tretë
algorithm që shkon in-- se

96
00:04:52,030 --> 00:04:58,300
merr n minus cubed 8n katror
plus 20 n njësitë e burimeve

97
00:04:58,300 --> 00:05:02,370
të procesit të një algoritmi
me të dhënat e përcaktuara me madhësi n.

98
00:05:02,370 --> 00:05:05,594
>> Tani përsëri, ne me të vërtetë nuk do
për të marrë në këtë nivel të detajuar.

99
00:05:05,594 --> 00:05:08,260
Unë jam me të vërtetë vetëm kanë këto deri
këtu si një ilustrim i një pikë

100
00:05:08,260 --> 00:05:10,176
që unë jam do të jetë
bërë në një të dytë, i cili

101
00:05:10,176 --> 00:05:12,980
është se ne vetëm me të vërtetë intereson
për tendencën e gjërave

102
00:05:12,980 --> 00:05:14,870
si të dhënat grupe merrni më të mëdha.

103
00:05:14,870 --> 00:05:18,220
Pra, nëse tërësia e të dhënave është i vogël, nuk ka
në fakt një ndryshim goxha i madh

104
00:05:18,220 --> 00:05:19,870
në këto algoritme.

105
00:05:19,870 --> 00:05:23,000
Algoritmi i tretë ka
merr 13 herë më shumë,

106
00:05:23,000 --> 00:05:27,980
13 herë shuma e burimeve
për të kandiduar në lidhje me një të parë.

107
00:05:27,980 --> 00:05:31,659
>> Nëse set dhënat ynë është madhësia e 10, e cila
është më e madhe, por jo domosdoshmërisht i madh,

108
00:05:31,659 --> 00:05:33,950
ne mund të shohim se ka
në fakt pak e një ndryshim.

109
00:05:33,950 --> 00:05:36,620
Algoritmi i tretë
bëhet më efikase.

110
00:05:36,620 --> 00:05:40,120
Kjo është për të vërtetë 40% -
ose 60% më të efektshme.

111
00:05:40,120 --> 00:05:41,580
Ajo merr 40% sasinë e kohës.

112
00:05:41,580 --> 00:05:45,250
Ajo mund të run-- ajo mund të marrë
400 njësitë e burimeve

113
00:05:45,250 --> 00:05:47,570
për të përpunuar një sërë të dhënash të madhësisë 10.

114
00:05:47,570 --> 00:05:49,410
Ndërsa i pari
algorithm, nga ana tjetër,

115
00:05:49,410 --> 00:05:54,520
merr 1000 njësi të burimeve
për të përpunuar një sërë të dhënash të madhësisë 10.

116
00:05:54,520 --> 00:05:57,240
Por shikoni se çfarë ndodh si
numrat tanë të merrni edhe më të mëdha.

117
00:05:57,240 --> 00:05:59,500
>> Tani, ndryshimi
në mes të këtyre algoritmeve

118
00:05:59,500 --> 00:06:01,420
të fillojë të bëhet më pak i dukshëm.

119
00:06:01,420 --> 00:06:04,560
Dhe fakti se ka
ulët rendit terms-- ose më mirë,

120
00:06:04,560 --> 00:06:09,390
Termat me exponents-- ulët
fillojnë të bëhen të parëndësishme.

121
00:06:09,390 --> 00:06:12,290
Në qoftë se një grup të dhënave është e madhësisë
1000 dhe algorithm parë

122
00:06:12,290 --> 00:06:14,170
shkon në një miliard hapa.

123
00:06:14,170 --> 00:06:17,880
Dhe algoritmi i dytë shkon në
një miliard e një milion hapa.

124
00:06:17,880 --> 00:06:20,870
Dhe algorithm tretë shkon
në vetëm turpërohet prej një miliard hapa.

125
00:06:20,870 --> 00:06:22,620
Kjo është shumë e shumë një miliardë hapa.

126
00:06:22,620 --> 00:06:25,640
Ato Termat ulët rendit të fillojë
për t'u bërë me të vërtetë e parëndësishme.

127
00:06:25,640 --> 00:06:27,390
Dhe vetëm për të vërtetë
çekiç Shtëpi point--

128
00:06:27,390 --> 00:06:31,240
në qoftë se input të dhënave është i Madhësi A
million-- të gjitha tre prej tyre shumë e shumë

129
00:06:31,240 --> 00:06:34,960
të marrë një quintillion-- nëse
matematikë im është hapa correct--

130
00:06:34,960 --> 00:06:37,260
për të përpunuar një kontribut të dhënave
të madhësisë së një milion.

131
00:06:37,260 --> 00:06:38,250
Kjo është një shumë e hapa.

132
00:06:38,250 --> 00:06:42,092
Dhe fakti se njëri prej tyre mund
të marrë një çift 100.000, ose një çift 100

133
00:06:42,092 --> 00:06:44,650
milion edhe më pak kur
ne jemi duke folur për një numër

134
00:06:44,650 --> 00:06:46,990
se big-- kjo është lloj i parëndësishme.

135
00:06:46,990 --> 00:06:50,006
Ata të gjithë kanë tendencë për të marrë
përafërsisht n cubed,

136
00:06:50,006 --> 00:06:52,380
dhe kështu ne fakt do i referohemi
të gjitha këto algoritme

137
00:06:52,380 --> 00:06:59,520
si me urdhër të n
Cubed ose i madh-o i n kub.

138
00:06:59,520 --> 00:07:03,220
>> Këtu është një listë e disa prej më të
klasa të zakonshme kompjuterike kompleksiteti

139
00:07:03,220 --> 00:07:05,820
se ne do të hasni në
algoritme, në përgjithësi.

140
00:07:05,820 --> 00:07:07,970
Dhe gjithashtu në mënyrë specifike në CS50.

141
00:07:07,970 --> 00:07:11,410
Këto janë urdhëruar nga
përgjithësisht më të shpejtë në krye,

142
00:07:11,410 --> 00:07:13,940
në përgjithësi slowest në fund.

143
00:07:13,940 --> 00:07:16,920
Pra, algoritme kohë konstante tentojnë
të jetë më e shpejtë, pa marrë parasysh

144
00:07:16,920 --> 00:07:19,110
i madhësisë e
Futja e të dhënave ju të kalojë në.

145
00:07:19,110 --> 00:07:23,760
Ata gjithmonë të marrë një operacion ose
një njësi e burimeve për t'u marrë me të.

146
00:07:23,760 --> 00:07:25,730
Ajo mund të jetë 2, ajo mund
të jetë 3, mund të jetë 4.

147
00:07:25,730 --> 00:07:26,910
Por kjo është një numër konstant.

148
00:07:26,910 --> 00:07:28,400
Ajo nuk ndryshon.

149
00:07:28,400 --> 00:07:31,390
>> Algoritme kohë logaritmike
janë pak më të mirë.

150
00:07:31,390 --> 00:07:33,950
Dhe një shembull të vërtetë të mirë të
një algoritmi logaritmike kohë

151
00:07:33,950 --> 00:07:37,420
ju keni parë me siguri deri tani është
vrullshëm përveç i librit telefonit

152
00:07:37,420 --> 00:07:39,480
për të gjetur Mike Smith në librin e telefonit.

153
00:07:39,480 --> 00:07:40,980
Ne prerë problemin në gjysmë.

154
00:07:40,980 --> 00:07:43,580
Dhe kështu si n merr më të mëdha
dhe më të mëdha dhe larger--

155
00:07:43,580 --> 00:07:47,290
në fakt, çdo herë që të dyfishtë
n, ajo merr vetëm një hap më shumë.

156
00:07:47,290 --> 00:07:49,770
Pra, kjo është shumë më mirë
se, të themi, koha lineare.

157
00:07:49,770 --> 00:07:53,030
E cila është në qoftë se ju të dyfishtë n, ajo
merr dyfishin e numrit të hapave.

158
00:07:53,030 --> 00:07:55,980
Nëse ju trefishojë n, ajo merr
trefishojë numrin e hapave.

159
00:07:55,980 --> 00:07:58,580
Një hap për njësi.

160
00:07:58,580 --> 00:08:01,790
>> Atëherë gjërat merrni një more-- vogël
më pak e madhe nga atje.

161
00:08:01,790 --> 00:08:06,622
Ju keni kohë linear ritmike, nganjëherë
quajtur log herë linear ose vetëm n log n.

162
00:08:06,622 --> 00:08:08,330
Dhe ne do një shembull
e një algoritmi që

163
00:08:08,330 --> 00:08:13,370
shkon në n log n, e cila është ende më mirë
se time-- n katror katror.

164
00:08:13,370 --> 00:08:17,320
Ose kohë polinom, n dy
çdo numër i madh se dy.

165
00:08:17,320 --> 00:08:20,810
Ose kohë eksponenciale, e cila
edhe worse-- C me n.

166
00:08:20,810 --> 00:08:24,670
Pra, disa numër konstante ngritur në
fuqia e madhësisë së kontributit.

167
00:08:24,670 --> 00:08:28,990
Pra, nëse nuk ka 1,000-- nëse
Futja e të dhënave është e madhësisë 1.000,

168
00:08:28,990 --> 00:08:31,310
ajo do të marrë C fuqisë 1,000th.

169
00:08:31,310 --> 00:08:33,559
Kjo është një shumë më keq se sa kohë polinomit.

170
00:08:33,559 --> 00:08:35,030
>> Ora faktorial është edhe më keq.

171
00:08:35,030 --> 00:08:37,760
Dhe në fakt, ka të vërtetë të bëjë
ekzistojnë algoritme kohë pafund,

172
00:08:37,760 --> 00:08:43,740
të tilla si, e ashtuquajtura sort-- budalla të cilit
Detyra është që rastësisht riorganizimi një grup

173
00:08:43,740 --> 00:08:45,490
dhe pastaj kontrolloni për të parë
nëse është e renditura.

174
00:08:45,490 --> 00:08:47,589
Dhe në qoftë se kjo nuk është, rastësisht
riorganizimi array përsëri

175
00:08:47,589 --> 00:08:49,130
dhe kontrolloni për të parë nëse është e renditura.

176
00:08:49,130 --> 00:08:51,671
Dhe si ju ndoshta mund të imagine--
ju mund të imagjinoni një situatë

177
00:08:51,671 --> 00:08:55,200
ku në më të keq, që vullneti i
kurrë nuk të vërtetë të fillojë me rrjet.

178
00:08:55,200 --> 00:08:57,150
Kjo algorithm do të kandidojë përgjithmonë.

179
00:08:57,150 --> 00:08:59,349
Dhe kështu që do të jetë një
algorithm kohë pafund.

180
00:08:59,349 --> 00:09:01,890
Shpresojmë se ju nuk do të jetë me shkrim
çdo kohë faktorial ose i pafund

181
00:09:01,890 --> 00:09:04,510
Algoritme në CS50.

182
00:09:04,510 --> 00:09:09,150
>> Pra, le të marrin një pak më shumë
vështrim konkrete në disa thjeshtë

183
00:09:09,150 --> 00:09:11,154
Klasat kompjuterike kompleksitetit.

184
00:09:11,154 --> 00:09:13,070
Pra, ne kemi një example--
ose dy shembuj here--

185
00:09:13,070 --> 00:09:15,590
e algoritme kohë të vazhdueshme,
që gjithmonë të marrë

186
00:09:15,590 --> 00:09:17,980
një operacion të vetëm në më të keq.

187
00:09:17,980 --> 00:09:20,050
Pra, të example-- parë
ne kemi një funksion

188
00:09:20,050 --> 00:09:23,952
4 thirrje për ju, që
merr një grup të madhësisë 1,000.

189
00:09:23,952 --> 00:09:25,660
Por pastaj me sa duket
ka të vërtetë nuk duket

190
00:09:25,660 --> 00:09:29,000
në it-- nuk ka të vërtetë kujdes se çfarë është
në brendësi të saj, e atij grup.

191
00:09:29,000 --> 00:09:30,820
Gjithmonë vetëm kthehet katër.

192
00:09:30,820 --> 00:09:32,940
Pra, kjo algorithm,
pavarësisht nga fakti se ajo

193
00:09:32,940 --> 00:09:35,840
merr 1000 elemente nuk
të bëjë asgjë me ta.

194
00:09:35,840 --> 00:09:36,590
Vetëm kthehet katër.

195
00:09:36,590 --> 00:09:38,240
Kjo është gjithmonë një hap të vetëm.

196
00:09:38,240 --> 00:09:41,600
>> Në fakt, shtoni 2 nums-- që
ne kemi parë më parë si well--

197
00:09:41,600 --> 00:09:43,680
vetëm proceset dy integers.

198
00:09:43,680 --> 00:09:44,692
Kjo nuk është një hap të vetëm.

199
00:09:44,692 --> 00:09:45,900
Është në fakt hapa një çift.

200
00:09:45,900 --> 00:09:50,780
Ju merrni një, ju merrni b, ju shtoni ato
së bashku, dhe ju prodhimit rezultatet.

201
00:09:50,780 --> 00:09:53,270
Pra, kjo është 84 hapa.

202
00:09:53,270 --> 00:09:55,510
Por është gjithmonë konstante,
pavarësisht nga një ose b.

203
00:09:55,510 --> 00:09:59,240
Ju duhet të merrni një, të merrni b, shtoni
ata së bashku, prodhimi rezultati.

204
00:09:59,240 --> 00:10:02,900
Pra, kjo është një algoritëm konstante kohë.

205
00:10:02,900 --> 00:10:05,170
>> Ja një shembull i një
algorithm-- kohë lineare

206
00:10:05,170 --> 00:10:08,740
një algoritmi që gets-- që merr
një hap tjetër, ndoshta,

207
00:10:08,740 --> 00:10:10,740
si input juaj rritet me 1.

208
00:10:10,740 --> 00:10:14,190
Pra, le të thonë se ne jemi duke kërkuar për
numri 5 brenda një grup.

209
00:10:14,190 --> 00:10:16,774
Ju mund të keni një situatë ku
ju mund të gjeni atë mjaft herët.

210
00:10:16,774 --> 00:10:18,606
Por ju gjithashtu mund të ketë
një situatë ku ajo

211
00:10:18,606 --> 00:10:20,450
mund të jetë element i fundit i vektorit.

212
00:10:20,450 --> 00:10:23,780
Në një rrjet të madhësisë 5, në qoftë
ne jemi duke kërkuar për numrin 5.

213
00:10:23,780 --> 00:10:25,930
Ajo do të marrë 5 hapa.

214
00:10:25,930 --> 00:10:29,180
Dhe në fakt, imagjinoni se ka
jo 5 kudo në këtë grup.

215
00:10:29,180 --> 00:10:32,820
Ne ende të vërtetë duhet të shikojmë në
çdo element i vetëm i vektorit

216
00:10:32,820 --> 00:10:35,550
në mënyrë të përcaktuar
nëse janë apo jo 5 është atje.

217
00:10:35,550 --> 00:10:39,840
>> Pra, në rastin më të keq, i cili është se
element është i fundit në grup

218
00:10:39,840 --> 00:10:41,700
apo nuk ekziston fare.

219
00:10:41,700 --> 00:10:44,690
Ne ende duhet të shikoni në
të gjithë elementet n.

220
00:10:44,690 --> 00:10:47,120
Dhe kështu kjo algoritëm
shkon në kohë lineare.

221
00:10:47,120 --> 00:10:50,340
Ju mund të konfirmojë se nga
nxjerrjen pak duke thënë:

222
00:10:50,340 --> 00:10:53,080
në qoftë se kemi pasur një koleksion të 6-element dhe
ne kemi qenë në kërkim për numrin 5,

223
00:10:53,080 --> 00:10:54,890
ajo mund të marrë 6 hapa.

224
00:10:54,890 --> 00:10:57,620
Në qoftë se ne kemi një rrjet të 7-element dhe
ne jemi duke kërkuar për numrin 5.

225
00:10:57,620 --> 00:10:59,160
Ajo mund të marrë 7 hapa.

226
00:10:59,160 --> 00:11:02,920
Si ne shtoni një element më shumë për tonë
grup, ajo merr një hap më shumë.

227
00:11:02,920 --> 00:11:06,750
Kjo është një algoritmi linear
në rastin më të keq.

228
00:11:06,750 --> 00:11:08,270
>> Çifti pyetje të shpejtë për ju.

229
00:11:08,270 --> 00:11:11,170
Çfarë është runtime-- çfarë është
më të keq-rast runtime

230
00:11:11,170 --> 00:11:13,700
e këtij copë të veçantë të kodit?

231
00:11:13,700 --> 00:11:17,420
Kështu që unë kam një lak 4 këtu që shkon
nga j barabartë me 0, gjatë gjithë rrugës deri në m.

232
00:11:17,420 --> 00:11:21,980
Dhe ajo që unë jam duke parë këtu, është se
trupi i lak shkon në kohë të vazhdueshëm.

233
00:11:21,980 --> 00:11:24,730
Pra, duke përdorur terminologjinë që
ne kemi folur tashmë? Për çfarë

234
00:11:24,730 --> 00:11:29,390
do të ishte më i keq i rastit
Runtime e këtij algoritmi?

235
00:11:29,390 --> 00:11:31,050
Merrni një të dytë.

236
00:11:31,050 --> 00:11:34,270
Pjesa e brendshme e lak
shkon në kohë të vazhdueshme.

237
00:11:34,270 --> 00:11:37,510
Dhe pjesa e jashtme e
lak do të kandidojë m herë.

238
00:11:37,510 --> 00:11:40,260
Pra, çfarë është më të keq rast runtime këtu?

239
00:11:40,260 --> 00:11:43,210
A ju me mend të madhe-O i m?

240
00:11:43,210 --> 00:11:44,686
Ju do të jetë e drejtë.

241
00:11:44,686 --> 00:11:46,230
>> Si në lidhje me një tjetër?

242
00:11:46,230 --> 00:11:48,590
Këtë herë ne kemi një
lak brenda një lak.

243
00:11:48,590 --> 00:11:50,905
Ne kemi një lak e jashtme
që shkon nga zero deri f.

244
00:11:50,905 --> 00:11:54,630
Dhe ne kemi një lak të brendshme që shkon
nga zero në p, dhe brenda kësaj,

245
00:11:54,630 --> 00:11:57,890
Unë pohojnë se trupi
lak shkon në kohë të vazhdueshme.

246
00:11:57,890 --> 00:12:02,330
Pra, çfarë është më të keq rast runtime
e këtij copë të veçantë të kodit?

247
00:12:02,330 --> 00:12:06,140
E pra, përsëri, ne kemi një
lak e jashtme që shkon herë fq.

248
00:12:06,140 --> 00:12:09,660
Dhe çdo përsëritje time--
e atij lak, në vend.

249
00:12:09,660 --> 00:12:13,170
Ne kemi një lak të brendshme
që gjithashtu shkon herë fq.

250
00:12:13,170 --> 00:12:16,900
Dhe pastaj brenda se, nuk ka
copë konstante time-- pak atje.

251
00:12:16,900 --> 00:12:19,890
>> Pra, nëse ne kemi një lak e jashtme që
shkon herë p brenda e cila është

252
00:12:19,890 --> 00:12:22,880
një lak i brendshëm që
shkon p Times-- çfarë është

253
00:12:22,880 --> 00:12:26,480
më të keq-rast runtime
e këtij copë të kodit?

254
00:12:26,480 --> 00:12:30,730
A ju me mend i madh-o i p katror?

255
00:12:30,730 --> 00:12:31,690
>> Unë jam Doug Lloyd.

256
00:12:31,690 --> 00:12:33,880
Kjo është CS50.

257
00:12:33,880 --> 00:12:35,622