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

2
00:00:05,830 --> 00:00:07,910
>> Molt bé, així, la complexitat computacional.

3
00:00:07,910 --> 00:00:10,430
Només una mica d'un advertiment
Abans d'aprofundir en massa far--

4
00:00:10,430 --> 00:00:13,070
això probablement serà entre
les coses més pesat de matemàtiques

5
00:00:13,070 --> 00:00:14,200
parlem en CS50.

6
00:00:14,200 --> 00:00:16,950
Esperem que no sigui massa aclaparador
i anem a tractar de guiar

7
00:00:16,950 --> 00:00:19,200
a través del procés, però
només una mica d'una advertència justa.

8
00:00:19,200 --> 00:00:21,282
Hi ha una mica
de matemàtiques involucrades aquí.

9
00:00:21,282 --> 00:00:23,990
D'acord, amb la finalitat de fer
ús dels nostres recursos computacionals

10
00:00:23,990 --> 00:00:28,170
en el real món-- és realment
important entendre algoritmes

11
00:00:28,170 --> 00:00:30,750
i com es processen les dades.

12
00:00:30,750 --> 00:00:32,810
Si tenim una realitat
algoritme eficient, ens

13
00:00:32,810 --> 00:00:36,292
pot reduir al mínim la quantitat de recursos
que tenim disponible per tractar amb ell.

14
00:00:36,292 --> 00:00:38,750
Si tenim un algoritme que
es va a prendre un munt de treball

15
00:00:38,750 --> 00:00:41,210
per processar una realitat
gran conjunt de dades, és

16
00:00:41,210 --> 00:00:44,030
requerirà més
i més recursos, que

17
00:00:44,030 --> 00:00:47,980
són els diners, la memòria RAM, tot aquest tipus de coses.

18
00:00:47,980 --> 00:00:52,090
>> Per tant, ser capaç d'analitzar una
algoritme que utilitza aquest conjunt d'eines,

19
00:00:52,090 --> 00:00:56,110
bàsicament, es pregunta el pregunta--
Com funciona aquesta escala algoritme

20
00:00:56,110 --> 00:00:59,020
com tirem més i més dades en ell?

21
00:00:59,020 --> 00:01:02,220
En CS50, la quantitat de dades que estem
treballar amb és bastant petita.

22
00:01:02,220 --> 00:01:05,140
En general, els nostres programes van
per executar-se en un segon o less--

23
00:01:05,140 --> 00:01:07,830
probablement molt menys
sobretot des del principi.

24
00:01:07,830 --> 00:01:12,250
>> Però pensa en una empresa que ofertes
amb centenars de milions de clients.

25
00:01:12,250 --> 00:01:14,970
I necessiten per processar
que les dades del client.

26
00:01:14,970 --> 00:01:18,260
A mesura que el nombre de clients als quals
tenen fa més gran i més gran,

27
00:01:18,260 --> 00:01:21,230
que requerirà
més i més recursos.

28
00:01:21,230 --> 00:01:22,926
Quants més recursos?

29
00:01:22,926 --> 00:01:25,050
Bé, això depèn de com
analitzem l'algorisme,

30
00:01:25,050 --> 00:01:28,097
utilitzant les eines d'aquesta caixa d'eines.

31
00:01:28,097 --> 00:01:31,180
Quan parlem de la complexitat de
1 algorithm-- que de vegades hauràs

32
00:01:31,180 --> 00:01:34,040
escoltar la seva pronunciació coneix com a temps
complexitat o espai complexitat

33
00:01:34,040 --> 00:01:36,190
però només anem
cridar complexity--

34
00:01:36,190 --> 00:01:38,770
estem parlant en general,
el pitjor dels casos.

35
00:01:38,770 --> 00:01:42,640
Tenint en compte el pitjor pila absoluta
dades que podríem estar llançant en ell,

36
00:01:42,640 --> 00:01:46,440
com es va a aquest algoritme
processar o tractar amb aquestes dades?

37
00:01:46,440 --> 00:01:51,450
En general, anomenem el pitjor dels casos
temps d'execució d'un algoritme gran-O.

38
00:01:51,450 --> 00:01:56,770
Així que un algoritme podria dir-se que
executar a O de n o O de n al quadrat.

39
00:01:56,770 --> 00:01:59,110
I més del que
aquells vol dir en un segon.

40
00:01:59,110 --> 00:02:01,620
>> A vegades, però, ens importa
sobre el millor dels casos.

41
00:02:01,620 --> 00:02:05,400
Si les dades són tot el que volíem
que sigui i que era absolutament perfecte

42
00:02:05,400 --> 00:02:09,630
i estàvem enviant aquesta perfecta
un conjunt de dades a través del nostre algorisme.

43
00:02:09,630 --> 00:02:11,470
Com seria gestionar en aquesta situació?

44
00:02:11,470 --> 00:02:15,050
A vegades ens referim al fet que a mesura
big-Omega, de manera que en contrast amb la gran-O,

45
00:02:15,050 --> 00:02:16,530
tenim grans Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega per el millor dels casos.

47
00:02:18,880 --> 00:02:21,319
Big-O per al pitjor dels casos.

48
00:02:21,319 --> 00:02:23,860
Generalment, quan es parla de
la complexitat d'un algorisme,

49
00:02:23,860 --> 00:02:26,370
estem parlant de la
pitjor dels casos.

50
00:02:26,370 --> 00:02:28,100
Així que tingues-ho en compte.

51
00:02:28,100 --> 00:02:31,510
>> I en aquesta classe, estem generalment va
per deixar l'anàlisi rigorosa de costat.

52
00:02:31,510 --> 00:02:35,350
Hi ha ciències i camps
dedicat a aquest tipus de coses.

53
00:02:35,350 --> 00:02:37,610
Quan parlem de raonament
a través d'algoritmes,

54
00:02:37,610 --> 00:02:41,822
que farem peça per peça per a molts
algoritmes que ens parlen de la classe.

55
00:02:41,822 --> 00:02:44,780
Realment estem parlant només de
raonament a través d'ell amb el sentit comú,

56
00:02:44,780 --> 00:02:47,070
no amb fórmules, o proves,
ni res d'això.

57
00:02:47,070 --> 00:02:51,600
Així que no es preocupi, nosaltres no serem
convertint-se en una classe de matemàtiques gran.

58
00:02:51,600 --> 00:02:55,920
>> Així que li vaig dir que ens preocupem per la complexitat
perquè fa la pregunta, com

59
00:02:55,920 --> 00:03:00,160
no manegen els nostres algoritmes més gran i
grans conjunts de dades que són llançats contra ells.

60
00:03:00,160 --> 00:03:01,960
Bé, el que és un conjunt de dades?

61
00:03:01,960 --> 00:03:03,910
Què vaig voler dir quan vaig dir això?

62
00:03:03,910 --> 00:03:07,600
Significa ho aprofita al màxim
sentit en el context, per ser honest.

63
00:03:07,600 --> 00:03:11,160
Si tenim un algoritme, el
Processos Strings-- estem probablement

64
00:03:11,160 --> 00:03:13,440
parlant sobre la mida de la cadena.

65
00:03:13,440 --> 00:03:15,190
Això és les dades definido--
la mida, el nombre

66
00:03:15,190 --> 00:03:17,050
de caràcters que componen la cadena.

67
00:03:17,050 --> 00:03:20,090
Si estem parlant d'un
algoritme que processa els arxius,

68
00:03:20,090 --> 00:03:23,930
podríem estar parlant de com
molts kilobytes comprenen aquest arxiu.

69
00:03:23,930 --> 00:03:25,710
I aquest és el conjunt de dades.

70
00:03:25,710 --> 00:03:28,870
Si estem parlant d'un algoritme
que maneja arrays de manera més general,

71
00:03:28,870 --> 00:03:31,510
tals com algoritmes d'ordenació
o la recerca d'algoritmes,

72
00:03:31,510 --> 00:03:36,690
probablement estem parlant de la sèrie
dels elements que conformen una matriu.

73
00:03:36,690 --> 00:03:39,272
>> Ara, podem mesurar una
algorithm-- en particular,

74
00:03:39,272 --> 00:03:40,980
quan dic que podem
mesuro un algoritme, que

75
00:03:40,980 --> 00:03:43,840
vol dir que podem mesurar la
molts recursos que ocupa.

76
00:03:43,840 --> 00:03:48,990
Ja sigui que aquests recursos són, quants
bytes de RAM-- o megabytes de RAM

77
00:03:48,990 --> 00:03:49,790
que utilitza.

78
00:03:49,790 --> 00:03:52,320
O quant de temps es triga a executar.

79
00:03:52,320 --> 00:03:56,200
I podem cridar a això
mesurar, de manera arbitrària, f de n.

80
00:03:56,200 --> 00:03:59,420
On n és el nombre de
elements en el conjunt de dades.

81
00:03:59,420 --> 00:04:02,640
I f de n és el nombre de tants.

82
00:04:02,640 --> 00:04:07,530
Quantes unitats de recursos fa
es requereix per processar aquestes dades.

83
00:04:07,530 --> 00:04:10,030
>> Ara, en realitat no ens importa
sobre el que f de n és exactament.

84
00:04:10,030 --> 00:04:13,700
De fet, molt rarament voluntat--
sens dubte mai es en aquest class-- I

85
00:04:13,700 --> 00:04:18,709
bussejar en qualsevol realment profund
anàlisi del que f de n és.

86
00:04:18,709 --> 00:04:23,510
Només anem a parlar del f de
n és d'aproximadament o el que tendeix a.

87
00:04:23,510 --> 00:04:27,600
I la tendència d'un algoritme és
dictat pel seu terme més alt ordre.

88
00:04:27,600 --> 00:04:29,440
I podem veure el que
dir amb que en prendre

89
00:04:29,440 --> 00:04:31,910
Una mirada a un exemple més concret.

90
00:04:31,910 --> 00:04:34,620
>> Així que anem a dir que tenim
tres algorismes diferents.

91
00:04:34,620 --> 00:04:39,350
El primer dels quals té n
cubs, algunes unitats de recursos

92
00:04:39,350 --> 00:04:42,880
per processar un conjunt de dades de grandària n.

93
00:04:42,880 --> 00:04:47,000
Tenim un segon algorisme que pren
n cubs més recursos n al quadrat

94
00:04:47,000 --> 00:04:49,350
per processar un conjunt de dades de grandària n.

95
00:04:49,350 --> 00:04:52,030
I tenim una tercera
algoritme que s'executa en-- que

96
00:04:52,030 --> 00:04:58,300
ocupa n 8n menys a la galleda quadrat
més 20 n unitats de recursos

97
00:04:58,300 --> 00:05:02,370
per processar un algoritme
amb conjunt de grandària n de dades.

98
00:05:02,370 --> 00:05:05,594
>> Ara, de nou, que realment no anem
per entrar en aquest nivell de detall.

99
00:05:05,594 --> 00:05:08,260
Estic realment només tinc aquestes dalt
aquí com una il·lustració d'un punt

100
00:05:08,260 --> 00:05:10,176
que jo seré
decisions en un segon, el que

101
00:05:10,176 --> 00:05:12,980
és que només ens importa
sobre la tendència de les coses

102
00:05:12,980 --> 00:05:14,870
com els conjunts de dades es fan més grans.

103
00:05:14,870 --> 00:05:18,220
Així que si el conjunt de dades és petit, hi ha
en realitat una diferència bastant gran

104
00:05:18,220 --> 00:05:19,870
en aquests algoritmes.

105
00:05:19,870 --> 00:05:23,000
El tercer algoritme allà
pren 13 vegades més,

106
00:05:23,000 --> 00:05:27,980
13 vegades la quantitat de recursos
per funcionar en relació amb la primera.

107
00:05:27,980 --> 00:05:31,659
>> Si el nostre conjunt de dades és de grandària 10, que
és més gran, però no necessàriament enorme,

108
00:05:31,659 --> 00:05:33,950
podem veure que hi ha
en realitat una mica de diferència.

109
00:05:33,950 --> 00:05:36,620
El tercer algoritme
es torna més eficient.

110
00:05:36,620 --> 00:05:40,120
Es tracta en realitat del 40% -
o 60% més eficient.

111
00:05:40,120 --> 00:05:41,580
Es triga 40% la quantitat de temps.

112
00:05:41,580 --> 00:05:45,250
Pot run-- pot prendre
400 unitats de recursos

113
00:05:45,250 --> 00:05:47,570
per processar un conjunt de dades de mida 10.

114
00:05:47,570 --> 00:05:49,410
Mentre que la primera
algoritme, per contra,

115
00:05:49,410 --> 00:05:54,520
té 1.000 unitats de recursos
per processar un conjunt de dades de mida 10.

116
00:05:54,520 --> 00:05:57,240
Però mira el que passa com
els nostres números es posen encara més gran.

117
00:05:57,240 --> 00:05:59,500
>> Ara, la diferència
entre aquests algoritmes

118
00:05:59,500 --> 00:06:01,420
començar a ser una mica menys aparent.

119
00:06:01,420 --> 00:06:04,560
I el fet que hi ha
d'ordre inferior terms-- o més aviat,

120
00:06:04,560 --> 00:06:09,390
termes amb menor exponents--
començar a ser irrellevant.

121
00:06:09,390 --> 00:06:12,290
Si un conjunt de dades és de grandària
1000 i el primer algoritme

122
00:06:12,290 --> 00:06:14,170
corre en uns mil milions de passos.

123
00:06:14,170 --> 00:06:17,880
I el segon algoritme s'executa en
mil milions i va un milió de passos.

124
00:06:17,880 --> 00:06:20,870
I la tercera algoritme s'executa
en poc menys de mil milions de passos.

125
00:06:20,870 --> 00:06:22,620
És més o almenys mil milions d'passos.

126
00:06:22,620 --> 00:06:25,640
Aquests termes d'ordre inferior comencen
per arribar a ser realment irrellevant.

127
00:06:25,640 --> 00:06:27,390
I només per realment
martell casa el point--

128
00:06:27,390 --> 00:06:31,240
si l'entrada de dades és de grandària a
milions-- aquests tres o menys

129
00:06:31,240 --> 00:06:34,960
prendre'n un quintillion-- si
meus matemàtiques és passos correct--

130
00:06:34,960 --> 00:06:37,260
per processar una entrada de dades
de la mida d'un milió.

131
00:06:37,260 --> 00:06:38,250
Això és un munt de passos.

132
00:06:38,250 --> 00:06:42,092
I el fet que un d'ells podria
prendre un parell de 100.000, o una parella 100

133
00:06:42,092 --> 00:06:44,650
milions menys encara quan
estem parlant d'un nombre

134
00:06:44,650 --> 00:06:46,990
que big-- és una cosa irrellevant.

135
00:06:46,990 --> 00:06:50,006
Tots ells tendeixen a prendre
aproximadament n en cubs,

136
00:06:50,006 --> 00:06:52,380
i així podríem realment referir
a tots aquests algoritmes

137
00:06:52,380 --> 00:06:59,520
com estant en l'ordre de n
en cubs o gran-O de n cubs.

138
00:06:59,520 --> 00:07:03,220
>> Aquí està una llista d'alguns dels més
classes comunes complexitat computacional

139
00:07:03,220 --> 00:07:05,820
que anem trobem en
algoritmes, en general.

140
00:07:05,820 --> 00:07:07,970
I també específicament en CS50.

141
00:07:07,970 --> 00:07:11,410
Aquests estan ordenats de
generalment més ràpida a la part superior,

142
00:07:11,410 --> 00:07:13,940
a generalment més lent en la part inferior.

143
00:07:13,940 --> 00:07:16,920
Així algoritmes de temps constant tendeixen
ser el més ràpid, sense tenir en compte

144
00:07:16,920 --> 00:07:19,110
de la mida de la
entrada de dades es passa a.

145
00:07:19,110 --> 00:07:23,760
Ells sempre tenen una sola operació o
una unitat de recursos per fer front a.

146
00:07:23,760 --> 00:07:25,730
Podria ser 2, podria
ser de 3, podria ser 4.

147
00:07:25,730 --> 00:07:26,910
Però és un nombre constant.

148
00:07:26,910 --> 00:07:28,400
No varia.

149
00:07:28,400 --> 00:07:31,390
>> Algorismes temps logarítmiques
són lleugerament millor.

150
00:07:31,390 --> 00:07:33,950
I un bon exemple de
un algoritme de temps logarítmica

151
00:07:33,950 --> 00:07:37,420
segurament has vist per ara és el
estripant de la guia telefònica

152
00:07:37,420 --> 00:07:39,480
trobar Mike Smith a la guia telefònica.

153
00:07:39,480 --> 00:07:40,980
Tallem el problema a la meitat.

154
00:07:40,980 --> 00:07:43,580
I així, a mesura que n es fa més gran
i més gran i larger--

155
00:07:43,580 --> 00:07:47,290
de fet, cada vegada que el doble
n, només es necessita un pas més.

156
00:07:47,290 --> 00:07:49,770
Així que això és molt millor
que, per exemple, el temps lineal.

157
00:07:49,770 --> 00:07:53,030
Què és si es duplica n, que
pren el doble del nombre de passos.

158
00:07:53,030 --> 00:07:55,980
Si Triple N, es necessita
triplicar el nombre de passos.

159
00:07:55,980 --> 00:07:58,580
Un pas per unitat.

160
00:07:58,580 --> 00:08:01,790
>> Després les coses es posen una mica més--
poc menys gran d'allà.

161
00:08:01,790 --> 00:08:06,622
Tens temps rítmic lineal, de vegades
anomenat registre de temps lineal o simplement n log n.

162
00:08:06,622 --> 00:08:08,330
I anem a un exemple
d'un algoritme que

163
00:08:08,330 --> 00:08:13,370
carreres en n log n, el que és encara millor
que quadràtica temps-- n al quadrat.

164
00:08:13,370 --> 00:08:17,320
O el temps polinomi, n de dos
qualsevol nombre més gran que dos.

165
00:08:17,320 --> 00:08:20,810
O temps exponencial, el que
és encara worse-- C per al n.

166
00:08:20,810 --> 00:08:24,670
Així que alguns nombre constant elevar fins
el poder de la mida de l'entrada.

167
00:08:24,670 --> 00:08:28,990
Així que si hi ha 1,000-- si el
l'entrada de dades és de mida 1000,

168
00:08:28,990 --> 00:08:31,310
prendria C al poder 1000.

169
00:08:31,310 --> 00:08:33,559
És molt pitjor que temps polinomial.

170
00:08:33,559 --> 00:08:35,030
>> Temps factorial és encara pitjor.

171
00:08:35,030 --> 00:08:37,760
I de fet, en realitat ho fan
Hi algoritmes de temps infinit,

172
00:08:37,760 --> 00:08:43,740
com ara, els anomenats sort-- estúpida la
treball consisteix en barrejar aleatòriament un conjunt

173
00:08:43,740 --> 00:08:45,490
i després comproveu
ja sigui ordenades.

174
00:08:45,490 --> 00:08:47,589
I si no és així, a l'atzar
barrejar la matriu de nou

175
00:08:47,589 --> 00:08:49,130
i comprovar per veure si es tracta de resoldre el problema.

176
00:08:49,130 --> 00:08:51,671
I com vostè probablement pot imagine--
es pot imaginar una situació

177
00:08:51,671 --> 00:08:55,200
on en el pitjor dels casos, que la voluntat
En realitat mai començar amb la matriu.

178
00:08:55,200 --> 00:08:57,150
Aquest algoritme aniria per sempre.

179
00:08:57,150 --> 00:08:59,349
I pel que seria un
algoritme de temps infinit.

180
00:08:59,349 --> 00:09:01,890
Esperem que no va a escriure
qualsevol moment factorial o infinit

181
00:09:01,890 --> 00:09:04,510
algoritmes en CS50.

182
00:09:04,510 --> 00:09:09,150
>> Per tant, anem a fer una mica més
aspecte concret en algun simple

183
00:09:09,150 --> 00:09:11,154
classes de complexitat computacional.

184
00:09:11,154 --> 00:09:13,070
Així que tenim un exemple--
o dos exemples aquí--

185
00:09:13,070 --> 00:09:15,590
d'algoritmes de temps constants,
que sempre prendre

186
00:09:15,590 --> 00:09:17,980
una sola operació en el pitjor dels casos.

187
00:09:17,980 --> 00:09:20,050
Així que la primera exemple--
tenim una funció

188
00:09:20,050 --> 00:09:23,952
anomenada 4 per a vostè, que
pren una matriu de mida 1000.

189
00:09:23,952 --> 00:09:25,660
Però llavors, aparentment
en realitat no mirar

190
00:09:25,660 --> 00:09:29,000
en it-- no li importa realment el que és
dins d'ella, d'aquesta matriu.

191
00:09:29,000 --> 00:09:30,820
Sempre simplement torna quatre.

192
00:09:30,820 --> 00:09:32,940
Per tant, aquest algoritme,
malgrat el fet que

193
00:09:32,940 --> 00:09:35,840
té 1.000 elements no
fer res amb ells.

194
00:09:35,840 --> 00:09:36,590
Només torna quatre.

195
00:09:36,590 --> 00:09:38,240
És sempre un sol pas.

196
00:09:38,240 --> 00:09:41,600
>> De fet, afegir 2 nums-- que
que hem vist abans com bé--

197
00:09:41,600 --> 00:09:43,680
simplement processa dos enters.

198
00:09:43,680 --> 00:09:44,692
No és un sol pas.

199
00:09:44,692 --> 00:09:45,900
En realitat és un parell de passos.

200
00:09:45,900 --> 00:09:50,780
Vostè rep una, s'obté b, s'agreguen
junts, i vostès, els resultats de sortida.

201
00:09:50,780 --> 00:09:53,270
Així que és 84 passos.

202
00:09:53,270 --> 00:09:55,510
Però sempre és constant,
independentment de a o b.

203
00:09:55,510 --> 00:09:59,240
Has de aconseguir una, obtenir b, afegiu
junts, el resultat de sortida.

204
00:09:59,240 --> 00:10:02,900
Així que això és un algoritme de temps constant.

205
00:10:02,900 --> 00:10:05,170
>> Heus aquí un exemple d'un
algorithm-- temps lineal

206
00:10:05,170 --> 00:10:08,740
un algoritme que gets-- que pren
un pas addicional, possiblement,

207
00:10:08,740 --> 00:10:10,740
com la seva entrada creix un 1.

208
00:10:10,740 --> 00:10:14,190
Així que, diguem que estem buscant
el número 5 a l'interior d'una matriu.

209
00:10:14,190 --> 00:10:16,774
És possible que tingui una situació en la
vostè ho pot trobar bastant d'hora.

210
00:10:16,774 --> 00:10:18,606
Però també podria tenir
una situació on

211
00:10:18,606 --> 00:10:20,450
podria ser l'últim element de la matriu.

212
00:10:20,450 --> 00:10:23,780
En una matriu de mida 5, si
estem buscant el número 5.

213
00:10:23,780 --> 00:10:25,930
Prendria 5 passos.

214
00:10:25,930 --> 00:10:29,180
I de fet, imagino que hi ha
No maig arreu d'aquesta matriu.

215
00:10:29,180 --> 00:10:32,820
Encara en realitat hem de mirar
cada element de la matriu

216
00:10:32,820 --> 00:10:35,550
amb la finalitat de determinar
si 5 és allà.

217
00:10:35,550 --> 00:10:39,840
>> Així que en el pitjor dels casos, i és que
l'element és l'última en la matriu

218
00:10:39,840 --> 00:10:41,700
o no existeix en absolut.

219
00:10:41,700 --> 00:10:44,690
Encara hem de mirar
tots els n elements.

220
00:10:44,690 --> 00:10:47,120
I així, aquest algoritme
s'executa en temps lineal.

221
00:10:47,120 --> 00:10:50,340
Pot confirmar que per
extrapolar una mica en dir:

222
00:10:50,340 --> 00:10:53,080
si tinguéssim una matriu de 6 elements i
que estàvem buscant per al número 5,

223
00:10:53,080 --> 00:10:54,890
pot ser que prengui 6 passos.

224
00:10:54,890 --> 00:10:57,620
Si tenim un conjunt de 7 elements i
estem buscant el número 5.

225
00:10:57,620 --> 00:10:59,160
Pot ser que prengui 7 passos.

226
00:10:59,160 --> 00:11:02,920
A mesura que afegim un element més al nostre
matriu, que es necessita un pas més.

227
00:11:02,920 --> 00:11:06,750
Això és un algoritme lineal
en el pitjor dels casos.

228
00:11:06,750 --> 00:11:08,270
>> Parella preguntes ràpides per a vostè.

229
00:11:08,270 --> 00:11:11,170
Quina és la runtime-- el que és
el pitjor dels casos-runtime

230
00:11:11,170 --> 00:11:13,700
d'aquest fragment de codi en particular?

231
00:11:13,700 --> 00:11:17,420
Així que tinc un bucle de 4 aquí que corre
des j és igual a 0, tot el camí fins m.

232
00:11:17,420 --> 00:11:21,980
I el que estic veient aquí, és que el
cos del bucle s'executa en temps constant.

233
00:11:21,980 --> 00:11:24,730
Així, utilitzant la terminologia que
ja hem parlat sobre-- el

234
00:11:24,730 --> 00:11:29,390
seria el pitjor dels casos
temps d'execució d'aquest algorisme?

235
00:11:29,390 --> 00:11:31,050
Tome un segon.

236
00:11:31,050 --> 00:11:34,270
La part interna del bucle
corre en temps constant.

237
00:11:34,270 --> 00:11:37,510
I la part exterior de la
bucle es va a executar m vegades.

238
00:11:37,510 --> 00:11:40,260
Quin és el pitjor dels casos el temps d'execució en aquesta llista?

239
00:11:40,260 --> 00:11:43,210
Sabia vostè endevina gran-O de m?

240
00:11:43,210 --> 00:11:44,686
Vostè tindria raó.

241
00:11:44,686 --> 00:11:46,230
>> Què hi ha d'una altra?

242
00:11:46,230 --> 00:11:48,590
Aquest cop tenim una
bucle dins d'un bucle.

243
00:11:48,590 --> 00:11:50,905
Tenim un bucle exterior
que va des de zero a p.

244
00:11:50,905 --> 00:11:54,630
I tenim un bucle intern que s'executa
de zero a p, ia l'interior d'això,

245
00:11:54,630 --> 00:11:57,890
Declaro que el cos de la
bucle s'executa en temps constant.

246
00:11:57,890 --> 00:12:02,330
Quin és el pitjor dels casos el temps d'execució
d'aquest fragment de codi en particular?

247
00:12:02,330 --> 00:12:06,140
Bé, de nou, tenim una
llaç extern que s'executa p vegades.

248
00:12:06,140 --> 00:12:09,660
I cada iteració temps--
d'aquest bucle, més bé.

249
00:12:09,660 --> 00:12:13,170
Tenim un bucle intern
que també corre p vegades.

250
00:12:13,170 --> 00:12:16,900
I després dins d'això, hi ha el
constant petit fragment temps-- allà.

251
00:12:16,900 --> 00:12:19,890
>> Així que si tenim un bucle exterior que
corre p vegades dins dels quals és

252
00:12:19,890 --> 00:12:22,880
un bucle interior que
corre p vegades-- el que és

253
00:12:22,880 --> 00:12:26,480
el pitjor dels casos-runtime
d'aquest fragment de codi?

254
00:12:26,480 --> 00:12:30,730
Sabia vostè endevina gran-O de p al quadrat?

255
00:12:30,730 --> 00:12:31,690
>> Sóc Doug Lloyd.

256
00:12:31,690 --> 00:12:33,880
Això és CS50.

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