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

2
00:00:05,830 --> 00:00:07,910
>> Bine, deci, complexitatea de calcul.

3
00:00:07,910 --> 00:00:10,430
Doar un pic de o avertizare
înainte de a se arunca cu capul în noi prea far--

4
00:00:10,430 --> 00:00:13,070
Va fi, probabil, printre
lucrurile cele mai grele de matematica-

5
00:00:13,070 --> 00:00:14,200
vorbim despre în CS50.

6
00:00:14,200 --> 00:00:16,950
Să sperăm că nu va fi prea copleșitoare
și vom încerca să vă ghida

7
00:00:16,950 --> 00:00:19,200
prin acest proces, dar
doar un pic de un avertisment echitabil.

8
00:00:19,200 --> 00:00:21,282
Există un pic
de matematică implicat aici.

9
00:00:21,282 --> 00:00:23,990
Bine, astfel încât, în scopul de a face
folosirea resurselor noastre de calcul

10
00:00:23,990 --> 00:00:28,170
în world-- reală este într-adevăr
important să se înțeleagă algoritmi

11
00:00:28,170 --> 00:00:30,750
și modul în care acestea prelucrează datele cu caracter.

12
00:00:30,750 --> 00:00:32,810
Dacă avem un foarte
algoritm eficient, am

13
00:00:32,810 --> 00:00:36,292
poate reduce cantitatea de resurse
avem la dispoziție de a face cu ea.

14
00:00:36,292 --> 00:00:38,750
Dacă avem un algoritm care
este de gând să ia o mulțime de muncă

15
00:00:38,750 --> 00:00:41,210
pentru a procesa un adevărat
set mare de date, este

16
00:00:41,210 --> 00:00:44,030
O să solicite mai multe
și mai multe resurse, care

17
00:00:44,030 --> 00:00:47,980
este de bani, RAM, toate acest tip de lucruri.

18
00:00:47,980 --> 00:00:52,090
>> Deci, fiind în măsură să analizeze o
algoritm folosind acest set de instrumente,

19
00:00:52,090 --> 00:00:56,110
Practic, solicită question--
cum face acest lucru la scară algoritm

20
00:00:56,110 --> 00:00:59,020
așa cum am arunca tot mai multe date de la ea?

21
00:00:59,020 --> 00:01:02,220
În CS50, cantitatea de date suntem
de lucru cu este destul de mic.

22
00:01:02,220 --> 00:01:05,140
În general, programele noastre sunt de gând
pentru a rula într-un al doilea sau less--

23
00:01:05,140 --> 00:01:07,830
probabil mult mai puțin
în special de timpuriu.

24
00:01:07,830 --> 00:01:12,250
>> Dar gandeste-te la o companie care se ocupă
cu sute de milioane de clienți.

25
00:01:12,250 --> 00:01:14,970
Și au nevoie pentru a procesa
că datele clientului.

26
00:01:14,970 --> 00:01:18,260
Pe măsură ce numărul de clienți care le
au devine mai mare și mai mare,

27
00:01:18,260 --> 00:01:21,230
se va necesita
mai multe și mai multe resurse.

28
00:01:21,230 --> 00:01:22,926
Cât de mult mai multe resurse?

29
00:01:22,926 --> 00:01:25,050
Ei bine, asta depinde de modul în
analizăm algoritmul,

30
00:01:25,050 --> 00:01:28,097
utilizând instrumentele din acest set de instrumente.

31
00:01:28,097 --> 00:01:31,180
Când vorbim despre complexitatea
un algorithm-- care, uneori, veți

32
00:01:31,180 --> 00:01:34,040
auzi mentionat ca timp
complexitate sau spațiu complexitate

33
00:01:34,040 --> 00:01:36,190
dar noi suntem doar de gând
pentru a apela complexity--

34
00:01:36,190 --> 00:01:38,770
ne, în general, vorbim despre
scenariul cel mai rău caz.

35
00:01:38,770 --> 00:01:42,640
Având în vedere cel mai rău gramada absolută a
datele pe care le-ar putea arunca la ea,

36
00:01:42,640 --> 00:01:46,440
cum este acest algoritm va
procesa sau a face cu faptul că datele?

37
00:01:46,440 --> 00:01:51,450
Noi, în general, numim cel mai rău caz
execuție a unui algoritm de mare-O.

38
00:01:51,450 --> 00:01:56,770
Deci, un algoritm poate fi spus să
alerga în O de N sau O N pătrat.

39
00:01:56,770 --> 00:01:59,110
Si mai multe despre ceea ce
cele înseamnă într-o secundă.

40
00:01:59,110 --> 00:02:01,620
>> Uneori, însă, facem grijă
despre cel mai bun caz.

41
00:02:01,620 --> 00:02:05,400
În cazul în care datele sunt tot ceea ce ne-am dorit
să fie și a fost absolut perfect

42
00:02:05,400 --> 00:02:09,630
și am fost trimiterea acestui perfectă
set de date prin intermediul algoritmului nostru.

43
00:02:09,630 --> 00:02:11,470
Cum ar descurca în această situație?

44
00:02:11,470 --> 00:02:15,050
Uneori ne referim la faptul că în calitate de
mare-Omega, astfel încât, în contrast cu mare-O,

45
00:02:15,050 --> 00:02:16,530
avem mare-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega pentru cel mai bun caz.

47
00:02:18,880 --> 00:02:21,319
Big-O pentru scenariul cel mai rău caz.

48
00:02:21,319 --> 00:02:23,860
În general, atunci când vorbim despre
complexitatea unui algoritm,

49
00:02:23,860 --> 00:02:26,370
noi vorbim despre
în cel mai rău caz.

50
00:02:26,370 --> 00:02:28,100
Astfel încât să păstreze în minte.

51
00:02:28,100 --> 00:02:31,510
>> Și în această clasă, vom merge, în general,
să părăsească analiza riguroasă deoparte.

52
00:02:31,510 --> 00:02:35,350
Există științe și domenii
dedicat acest gen de lucruri.

53
00:02:35,350 --> 00:02:37,610
Când vorbim despre raționament
prin algoritmi,

54
00:02:37,610 --> 00:02:41,822
care vom face-bucata-cu bucată pentru mulți
algoritmi vorbim despre în clasa.

55
00:02:41,822 --> 00:02:44,780
Suntem de fapt doar vorbesc despre
raționamentul prin ea cu bun simț,

56
00:02:44,780 --> 00:02:47,070
nu cu formule, sau dovezi,
sau ceva de genul asta.

57
00:02:47,070 --> 00:02:51,600
Deci, nu vă faceți griji, Nu vom fi
transformându-se într-o mare clasă de matematică.

58
00:02:51,600 --> 00:02:55,920
>> Așa că am spus ne pasă de complexitate
deoarece pune întrebarea, cum

59
00:02:55,920 --> 00:03:00,160
Nu algoritmi noastre se ocupe mai mare și
seturi mari de date fiind aruncat la ei.

60
00:03:00,160 --> 00:03:01,960
Ei bine, ceea ce este un set de date?

61
00:03:01,960 --> 00:03:03,910
Ce am să spun când am spus asta?

62
00:03:03,910 --> 00:03:07,600
Aceasta înseamnă orice face cel mai mult
sens în context, să fiu sincer.

63
00:03:07,600 --> 00:03:11,160
Dacă avem un algoritm, The
Procese Strings-- suntem, probabil,

64
00:03:11,160 --> 00:03:13,440
vorbind despre dimensiunea șir.

65
00:03:13,440 --> 00:03:15,190
Asta e datele set--
dimensiunea, numărul

66
00:03:15,190 --> 00:03:17,050
de caractere care alcătuiesc șirul.

67
00:03:17,050 --> 00:03:20,090
Dacă vorbim despre o
algoritm care procesează fișiere,

68
00:03:20,090 --> 00:03:23,930
am putea vorbi despre modul în care
multe kilobytes cuprinde acel fișier.

69
00:03:23,930 --> 00:03:25,710
Și asta e setul de date.

70
00:03:25,710 --> 00:03:28,870
Dacă vorbim despre un algoritm
care se ocupă de matrice, mai general,

71
00:03:28,870 --> 00:03:31,510
cum ar fi algoritmi de sortare
sau căutarea algoritmi,

72
00:03:31,510 --> 00:03:36,690
ne, probabil vorba despre numărul
de elemente care cuprind o serie.

73
00:03:36,690 --> 00:03:39,272
>> Acum, putem măsura o
algorithm-- în special,

74
00:03:39,272 --> 00:03:40,980
când spun putem
măsura un algoritm, am

75
00:03:40,980 --> 00:03:43,840
înseamnă putem măsura cât de
multe resurse este nevoie de sus.

76
00:03:43,840 --> 00:03:48,990
Dacă aceste resurse sunt, cât de multe
bytes de RAM-- sau MB de memorie RAM

77
00:03:48,990 --> 00:03:49,790
îl folosește.

78
00:03:49,790 --> 00:03:52,320
Sau cât de mult timp este nevoie pentru a rula.

79
00:03:52,320 --> 00:03:56,200
Și putem apela acest
măsura, în mod arbitrar, f de n.

80
00:03:56,200 --> 00:03:59,420
Unde n este numărul de
elemente în setul de date.

81
00:03:59,420 --> 00:04:02,640
Și f de n este cât de multe ceva de.

82
00:04:02,640 --> 00:04:07,530
Cât de multe unități de resurse nu
nevoie de ea pentru a procesa aceste date.

83
00:04:07,530 --> 00:04:10,030
>> Acum, noi de fapt nu-mi pasă
despre ceea ce f de n este exact.

84
00:04:10,030 --> 00:04:13,700
De fapt, am foarte rar will--
cu siguranță nu va fi niciodată în această I class--

85
00:04:13,700 --> 00:04:18,709
se arunca cu capul în orice într-adevăr profund
analiză a ceea ce f de n este.

86
00:04:18,709 --> 00:04:23,510
Noi doar vorbi despre ceea ce f de
n este de aproximativ sau ceea ce tinde sa.

87
00:04:23,510 --> 00:04:27,600
Și tendința unui algoritm este
dictate de termen sa cea mai mare comanda.

88
00:04:27,600 --> 00:04:29,440
Și putem vedea ceea ce am
înseamnă că prin luarea de

89
00:04:29,440 --> 00:04:31,910
o privire la un exemplu mai concret.

90
00:04:31,910 --> 00:04:34,620
>> Deci, haideți să spunem că avem
trei algoritmi diferite.

91
00:04:34,620 --> 00:04:39,350
Prima dintre care are n
tocati, unele unități de resurse

92
00:04:39,350 --> 00:04:42,880
pentru a procesa un set de date de dimensiune n.

93
00:04:42,880 --> 00:04:47,000
Avem un al doilea algoritm care ia
n tocata plus resurse n patrat

94
00:04:47,000 --> 00:04:49,350
pentru a procesa un set de date de dimensiune n.

95
00:04:49,350 --> 00:04:52,030
Și avem un al treilea
algoritm care rulează in-- care

96
00:04:52,030 --> 00:04:58,300
preia n minus tocata 8N pătrat
plus 20 de unități de resurse n

97
00:04:58,300 --> 00:05:02,370
pentru a procesa un algoritm
cu un set de dimensiune n date.

98
00:05:02,370 --> 00:05:05,594
>> Acum, din nou, cu adevarat nu vom
pentru a obține în acest nivel de detaliu.

99
00:05:05,594 --> 00:05:08,260
Sunt foarte Trebuie doar astea
aici ca o ilustrare a unui punct

100
00:05:08,260 --> 00:05:10,176
că am de gând să fie
face într-un al doilea, care

101
00:05:10,176 --> 00:05:12,980
este că ne pasă cu adevărat numai
despre tendința de lucruri

102
00:05:12,980 --> 00:05:14,870
ca seturile de date devin mai mari.

103
00:05:14,870 --> 00:05:18,220
Deci, dacă setul de date este mic, nu e
de fapt, o diferență destul de mare

104
00:05:18,220 --> 00:05:19,870
în aceste algoritmi.

105
00:05:19,870 --> 00:05:23,000
Al treilea Algoritmul acolo
durează de 13 ori mai mult,

106
00:05:23,000 --> 00:05:27,980
De 13 ori cantitatea de resurse
pentru a rula în raport cu primul.

107
00:05:27,980 --> 00:05:31,659
>> Dacă setul de date este dimensiunea noastră 10, care
este mai mare, dar nu neapărat frumos,

108
00:05:31,659 --> 00:05:33,950
putem vedea că nu există
de fapt, un pic de o diferenta.

109
00:05:33,950 --> 00:05:36,620
Al treilea Algoritmul
devine mai eficientă.

110
00:05:36,620 --> 00:05:40,120
Este vorba despre de fapt 40% -
sau 60% mai eficient.

111
00:05:40,120 --> 00:05:41,580
Este nevoie 40% cantitatea de timp.

112
00:05:41,580 --> 00:05:45,250
Se poate run-- poate dura
400 de unități de resurse

113
00:05:45,250 --> 00:05:47,570
pentru a procesa un set de date de dimensiune 10.

114
00:05:47,570 --> 00:05:49,410
Întrucât primele
algoritm, prin contrast,

115
00:05:49,410 --> 00:05:54,520
ia 1.000 de unități de resurse
pentru a procesa un set de date de dimensiune 10.

116
00:05:54,520 --> 00:05:57,240
Dar uite ce se întâmplă ca
numerele noastre obține chiar mai mare.

117
00:05:57,240 --> 00:05:59,500
>> Acum, diferența
între aceste algoritmi

118
00:05:59,500 --> 00:06:01,420
începe să devină un pic mai puțin evidente.

119
00:06:01,420 --> 00:06:04,560
Iar faptul că există
inferior-comanda terms-- sau, mai degrabă,

120
00:06:04,560 --> 00:06:09,390
termeni cu exponents-- inferior
începe să devină irelevante.

121
00:06:09,390 --> 00:06:12,290
În cazul în care un set de date este de mărime
1000 și primul algoritm

122
00:06:12,290 --> 00:06:14,170
ruleaza in un miliard de pași.

123
00:06:14,170 --> 00:06:17,880
Și al doilea algoritm rulează în
un miliard și un milion de pași.

124
00:06:17,880 --> 00:06:20,870
Și a treia algoritmul rulează
în doar timid de un miliard de pași.

125
00:06:20,870 --> 00:06:22,620
E destul de mult de un miliard de pași.

126
00:06:22,620 --> 00:06:25,640
Acești termeni de ordin inferior începe
pentru a deveni cu adevărat lipsită de relevanță.

127
00:06:25,640 --> 00:06:27,390
Și într-adevăr la
ciocan acasă point--

128
00:06:27,390 --> 00:06:31,240
în cazul în care intrarea de date este de dimensiuni un
million-- toate trei dintre acestea destul de mult

129
00:06:31,240 --> 00:06:34,960
ia una quintillion-- dacă
matematica mea este la câțiva pași correct--

130
00:06:34,960 --> 00:06:37,260
pentru a procesa o intrare de date
de dimensiuni un milion.

131
00:06:37,260 --> 00:06:38,250
Asta-i o mulțime de pași.

132
00:06:38,250 --> 00:06:42,092
Iar faptul că unul dintre ei ar putea
ia un cuplu de 100.000, sau un cuplu de 100

133
00:06:42,092 --> 00:06:44,650
milioane mai puțin atunci când
vorbim despre un număr

134
00:06:44,650 --> 00:06:46,990
că big-- e un fel de irelevant.

135
00:06:46,990 --> 00:06:50,006
Toate acestea au tendința de a lua
aproximativ n tocata,

136
00:06:50,006 --> 00:06:52,380
și așa ne-ar referi de fapt
la toate aceste algoritmi

137
00:06:52,380 --> 00:06:59,520
ca fiind de ordinul a n
tocata sau mare-O din n tocata.

138
00:06:59,520 --> 00:07:03,220
>> Iată o listă a unora dintre mai mult
clasele comune complexitate de calcul

139
00:07:03,220 --> 00:07:05,820
că vom întâlni în
algoritmi, în general.

140
00:07:05,820 --> 00:07:07,970
Și, de asemenea, în mod special CS50.

141
00:07:07,970 --> 00:07:11,410
Acestea sunt comandate de la
în general, cel mai rapid în partea de sus,

142
00:07:11,410 --> 00:07:13,940
să general mai lent în partea de jos.

143
00:07:13,940 --> 00:07:16,920
Deci, algoritmi de timp constant tind
să fie cel mai rapid, indiferent

144
00:07:16,920 --> 00:07:19,110
de dimensiunea
introducere de date treci la.

145
00:07:19,110 --> 00:07:23,760
Ei iau întotdeauna o singură operație sau
o unitate de resurse pentru a face față.

146
00:07:23,760 --> 00:07:25,730
S-ar putea fi de 2, s-ar putea
fie de 3, ar putea fi de 4.

147
00:07:25,730 --> 00:07:26,910
Dar e un număr constant.

148
00:07:26,910 --> 00:07:28,400
Aceasta nu variază.

149
00:07:28,400 --> 00:07:31,390
>> Algoritmi de timp logaritmice
sunt ceva mai bine.

150
00:07:31,390 --> 00:07:33,950
Și un foarte bun exemplu de
un algoritm de timp logaritmică

151
00:07:33,950 --> 00:07:37,420
le-ați văzut cu siguranță de acum este
ruperea în afară de cartea de telefon

152
00:07:37,420 --> 00:07:39,480
pentru a găsi Mike Smith în cartea de telefon.

153
00:07:39,480 --> 00:07:40,980
Am tăiat problema în jumătate.

154
00:07:40,980 --> 00:07:43,580
Și așa cum n devine mai mare
și mai mare și larger--

155
00:07:43,580 --> 00:07:47,290
De fapt, de fiecare dată când dublu
n, este nevoie de doar un pas.

156
00:07:47,290 --> 00:07:49,770
Așa că e mult mai bine
decât, să spunem, timp liniar.

157
00:07:49,770 --> 00:07:53,030
Care este, dacă n dubla, aceasta
ia un număr dublu de pași.

158
00:07:53,030 --> 00:07:55,980
Dacă vă tripla n, este nevoie de
tripla numărul de pași.

159
00:07:55,980 --> 00:07:58,580
Un pas pe unitate.

160
00:07:58,580 --> 00:08:01,790
>> Apoi lucrurile devin un pic more--
mai puțin mare de acolo.

161
00:08:01,790 --> 00:08:06,622
Ai timp ritmic liniar, uneori
numit timp liniar jurnal sau doar n log n.

162
00:08:06,622 --> 00:08:08,330
Și vom exemplu
de un algoritm care

163
00:08:08,330 --> 00:08:13,370
ruleaza in n log n, care este mai bine
decât pătrată time-- n pătrat.

164
00:08:13,370 --> 00:08:17,320
Sau timp polinomial, n două
orice număr mai mare decât doi.

165
00:08:17,320 --> 00:08:20,810
Sau timp exponențială, care
este chiar worse-- C n.

166
00:08:20,810 --> 00:08:24,670
Deci, un numar constant ridicat la
puterea mărimii de intrare.

167
00:08:24,670 --> 00:08:28,990
Deci, dacă există 1,000-- dacă
introducerea datelor este de mărime 1,000,

168
00:08:28,990 --> 00:08:31,310
ar fi nevoie de C la puterea 1000-lea.

169
00:08:31,310 --> 00:08:33,559
E mult mai rău decât timp polinomial.

170
00:08:33,559 --> 00:08:35,030
>> Timp factorial este chiar mai rău.

171
00:08:35,030 --> 00:08:37,760
Și, de fapt, acolo într-adevăr
Există algoritmi timp infinit,

172
00:08:37,760 --> 00:08:43,740
cum ar fi, așa-numitele sort-- prost, acesta
de locuri de muncă este de a amesteca aleator o serie

173
00:08:43,740 --> 00:08:45,490
și apoi verificați pentru a vedea
fie că este vorba sortate.

174
00:08:45,490 --> 00:08:47,589
Și dacă nu e, la întâmplare
shuffle nou matrice

175
00:08:47,589 --> 00:08:49,130
și verificați pentru a vedea dacă este sortate.

176
00:08:49,130 --> 00:08:51,671
Și, după cum puteți, probabil, imagine--
vă puteți imagina o situație

177
00:08:51,671 --> 00:08:55,200
în cazul în care, în cel mai rău caz, ceea ce va
nu începe de fapt cu matrice.

178
00:08:55,200 --> 00:08:57,150
Că algoritmul ar fi pentru totdeauna.

179
00:08:57,150 --> 00:08:59,349
Și așa ar fi o
algoritm de timp infinit.

180
00:08:59,349 --> 00:09:01,890
Sperăm că nu va fi scris
orice moment factorial sau infinit

181
00:09:01,890 --> 00:09:04,510
algoritmi în CS50.

182
00:09:04,510 --> 00:09:09,150
>> Deci, să ia un pic mai mult
uite la un simplu beton

183
00:09:09,150 --> 00:09:11,154
clase de complexitate de calcul.

184
00:09:11,154 --> 00:09:13,070
Deci, avem o example--
sau două exemple here--

185
00:09:13,070 --> 00:09:15,590
algoritmilor timp constant,
care întotdeauna

186
00:09:15,590 --> 00:09:17,980
o singură operațiune în cel mai rău caz.

187
00:09:17,980 --> 00:09:20,050
Deci, primul example--
avem o funcție

188
00:09:20,050 --> 00:09:23,952
chemat 4 pentru tine, care
ia o serie de dimensiuni 1000.

189
00:09:23,952 --> 00:09:25,660
Dar apoi se pare că
nu uita de fapt

190
00:09:25,660 --> 00:09:29,000
la it-- nu pasă cu adevărat ceea ce este
interiorul ei, de care matrice.

191
00:09:29,000 --> 00:09:30,820
Întotdeauna doar întoarce patru.

192
00:09:30,820 --> 00:09:32,940
Deci, faptul că algoritmul,
în ciuda faptului că aceasta

193
00:09:32,940 --> 00:09:35,840
ia 1.000 de elemente nu
face nimic cu ei.

194
00:09:35,840 --> 00:09:36,590
Doar întoarce patru.

195
00:09:36,590 --> 00:09:38,240
Este întotdeauna un singur pas.

196
00:09:38,240 --> 00:09:41,600
>> De fapt, se adaugă 2 nums-- care
am văzut înainte ca well--

197
00:09:41,600 --> 00:09:43,680
doar procesele două numere întregi.

198
00:09:43,680 --> 00:09:44,692
Nu este un singur pas.

199
00:09:44,692 --> 00:09:45,900
Este de fapt un cuplu pași.

200
00:09:45,900 --> 00:09:50,780
Ai un, te b, ce le adăugați
împreună, și voi ieșire rezultatele.

201
00:09:50,780 --> 00:09:53,270
Deci, este de 84 pași.

202
00:09:53,270 --> 00:09:55,510
Dar e mereu constant,
indiferent de a sau b.

203
00:09:55,510 --> 00:09:59,240
Aveți pentru a obține un, pentru a primi b, se adaugă
le împreună, de ieșire rezultatul.

204
00:09:59,240 --> 00:10:02,900
Așa că e un algoritm de timp constant.

205
00:10:02,900 --> 00:10:05,170
>> Iată un exemplu de
algorithm-- timp liniar

206
00:10:05,170 --> 00:10:08,740
un algoritm care gets-- care are
un pas suplimentar, eventual,

207
00:10:08,740 --> 00:10:10,740
ca intrare creste cu 1.

208
00:10:10,740 --> 00:10:14,190
Deci, să spunem că suntem în căutarea pentru
numărul 5 interiorul unui tablou.

209
00:10:14,190 --> 00:10:16,774
S-ar putea avea o situație în care
puteți găsi destul de devreme.

210
00:10:16,774 --> 00:10:18,606
Dar ai putea avea, de asemenea
o situație în care

211
00:10:18,606 --> 00:10:20,450
ar putea fi ultimul element de matrice.

212
00:10:20,450 --> 00:10:23,780
Într-o serie de dimensiuni 5, în cazul în care
căutăm numărul 5.

213
00:10:23,780 --> 00:10:25,930
Ar fi nevoie de 5 pași.

214
00:10:25,930 --> 00:10:29,180
Și, de fapt, imaginați-vă că nu există
nu 5 oriunde în această matrice.

215
00:10:29,180 --> 00:10:32,820
Noi încă mai trebuie de fapt să se uite la
fiecare singur element de matrice

216
00:10:32,820 --> 00:10:35,550
în scopul de a determina
dacă este sau nu de 5 este acolo.

217
00:10:35,550 --> 00:10:39,840
>> Deci, în cel mai rău caz, care este faptul că
elementul este ultimul în matrice

218
00:10:39,840 --> 00:10:41,700
sau nu există deloc.

219
00:10:41,700 --> 00:10:44,690
Noi încă mai trebuie să se uite la
toate n elemente.

220
00:10:44,690 --> 00:10:47,120
Și așa acest algoritm
se execută în timp liniar.

221
00:10:47,120 --> 00:10:50,340
Puteți confirma că, prin
extrapolarea un pic, spunând:

222
00:10:50,340 --> 00:10:53,080
dacă am avut o serie de 6 elemente și
am fost în căutarea pentru numărul 5,

223
00:10:53,080 --> 00:10:54,890
ar putea dura 6 pași.

224
00:10:54,890 --> 00:10:57,620
Dacă avem o gama de 7 element și
căutăm numărul 5.

225
00:10:57,620 --> 00:10:59,160
Ar putea dura 7 trepte.

226
00:10:59,160 --> 00:11:02,920
Așa cum am mai adăuga un element nostru
matrice, este nevoie de încă un pas.

227
00:11:02,920 --> 00:11:06,750
Asta e un algoritm liniar
în cel mai rău caz.

228
00:11:06,750 --> 00:11:08,270
>> Cuplu întrebări rapide pentru tine.

229
00:11:08,270 --> 00:11:11,170
Care este runtime-- ceea ce este
cel mai rău caz, runtime-

230
00:11:11,170 --> 00:11:13,700
din acest fragment special de cod?

231
00:11:13,700 --> 00:11:17,420
Deci, am o buclă de 4 aici care ruleaza
de la J este egal cu 0, tot drumul pana la m.

232
00:11:17,420 --> 00:11:21,980
Și ceea ce văd aici, este faptul că
corp din bucla se execută în timp constant.

233
00:11:21,980 --> 00:11:24,730
Deci, folosind terminologia care
am vorbit deja about-- ce

234
00:11:24,730 --> 00:11:29,390
ar fi cel mai rău caz,
execuție a acestui algoritm?

235
00:11:29,390 --> 00:11:31,050
Ia-o a doua.

236
00:11:31,050 --> 00:11:34,270
Partea interioară a buclei
se execută în timp constant.

237
00:11:34,270 --> 00:11:37,510
Iar partea exterioară a
bucla este de gând să ruleze ori m.

238
00:11:37,510 --> 00:11:40,260
Deci, ce este runtime cel mai rău caz aici?

239
00:11:40,260 --> 00:11:43,210
Ai ghicit mare-O de m?

240
00:11:43,210 --> 00:11:44,686
Ai avea dreptate.

241
00:11:44,686 --> 00:11:46,230
>> Ce zici de un altul?

242
00:11:46,230 --> 00:11:48,590
De data aceasta avem o
buclă în interiorul unei bucle.

243
00:11:48,590 --> 00:11:50,905
Avem o buclă exterioară
care ruleaza de la zero la p.

244
00:11:50,905 --> 00:11:54,630
Și avem o buclă interioară care ruleaza
de la zero la p, și în interiorul acestuia

245
00:11:54,630 --> 00:11:57,890
Am afirmă că trupul
buclă se execută în timp constant.

246
00:11:57,890 --> 00:12:02,330
Deci, ce este runtime mai rău caz
din acest fragment special de cod?

247
00:12:02,330 --> 00:12:06,140
Ei bine, din nou, avem o
buclă exterioară care ruleaza ori p.

248
00:12:06,140 --> 00:12:09,660
Și fiecare iterație time--
din bucla, mai degrabă.

249
00:12:09,660 --> 00:12:13,170
Avem o buclă interioară
care ruleaza, de asemenea, ori p.

250
00:12:13,170 --> 00:12:16,900
Și apoi în interiorul că, nu e
constantă fragment time-- puțin acolo.

251
00:12:16,900 --> 00:12:19,890
>> Deci, dacă avem o buclă exterioară care
ruleaza p ori în interiorul căruia este

252
00:12:19,890 --> 00:12:22,880
o buclă interioară care
ruleaza p times-- ceea ce este

253
00:12:22,880 --> 00:12:26,480
cel mai rău caz, runtime-
de acest fragment de cod?

254
00:12:26,480 --> 00:12:30,730
Ai ghicit mare-O din p pătrat?

255
00:12:30,730 --> 00:12:31,690
>> Sunt Doug Lloyd.

256
00:12:31,690 --> 00:12:33,880
Acest lucru este CS50.

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