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

2
00:00:05,830 --> 00:00:07,910
>> Va bene, quindi, la complessità computazionale.

3
00:00:07,910 --> 00:00:10,430
Solo un po 'di un avvertimento
Prima di tuffarci in troppo far--

4
00:00:10,430 --> 00:00:13,070
questo sarà probabilmente tra
le cose più matematica pesante

5
00:00:13,070 --> 00:00:14,200
parliamo in CS50.

6
00:00:14,200 --> 00:00:16,950
Speriamo che non sarà troppo schiacciante
e cercheremo di guidarvi

7
00:00:16,950 --> 00:00:19,200
attraverso il processo, ma
solo un po 'di un avvertimento fiera.

8
00:00:19,200 --> 00:00:21,282
C'è un po '
di matematica coinvolta qui.

9
00:00:21,282 --> 00:00:23,990
Va bene, così al fine di rendere
utilizzo delle nostre risorse di calcolo

10
00:00:23,990 --> 00:00:28,170
nel vero world-- è davvero
importante capire algoritmi

11
00:00:28,170 --> 00:00:30,750
e il modo in cui trattano dati.

12
00:00:30,750 --> 00:00:32,810
Se abbiamo una veramente
algoritmo efficiente, abbiamo

13
00:00:32,810 --> 00:00:36,292
può minimizzare la quantità di risorse
abbiamo a disposizione a che fare con esso.

14
00:00:36,292 --> 00:00:38,750
Se abbiamo un algoritmo che
sta andando a prendere un sacco di lavoro

15
00:00:38,750 --> 00:00:41,210
per elaborare un veramente
grande insieme di dati, è

16
00:00:41,210 --> 00:00:44,030
andando a richiedere più
e più risorse, che

17
00:00:44,030 --> 00:00:47,980
è il denaro, la RAM, tutto questo genere di cose.

18
00:00:47,980 --> 00:00:52,090
>> Quindi, essendo in grado di analizzare un
Algoritmo utilizzando questo set di strumenti,

19
00:00:52,090 --> 00:00:56,110
fondamentalmente, chiede al interrogo
come fa questa scala algoritmo

20
00:00:56,110 --> 00:00:59,020
come gettiamo sempre più dati a esso?

21
00:00:59,020 --> 00:01:02,220
Nel CS50, la quantità di dati che siamo
lavorando è piuttosto piccolo.

22
00:01:02,220 --> 00:01:05,140
In generale, i nostri programmi sono in corso
per l'esecuzione in un secondo o less--

23
00:01:05,140 --> 00:01:07,830
probabilmente molto meno
soprattutto nella fase iniziale.

24
00:01:07,830 --> 00:01:12,250
>> Ma pensare a una società che si occupa
con centinaia di milioni di clienti.

25
00:01:12,250 --> 00:01:14,970
E hanno bisogno di elaborare
i dati dei clienti.

26
00:01:14,970 --> 00:01:18,260
Poiché il numero di clienti che
avere diventa sempre più grande,

27
00:01:18,260 --> 00:01:21,230
sta andando a richiedere
sempre più risorse.

28
00:01:21,230 --> 00:01:22,926
Quanti altri mezzi?

29
00:01:22,926 --> 00:01:25,050
Beh, questo dipende da come
analizziamo l'algoritmo,

30
00:01:25,050 --> 00:01:28,097
utilizzando gli strumenti di questa casella.

31
00:01:28,097 --> 00:01:31,180
Quando si parla della complessità del
un algorithm-- che a volte si

32
00:01:31,180 --> 00:01:34,040
ascoltano indicato come il tempo
complessità o spazio complessità

33
00:01:34,040 --> 00:01:36,190
ma stiamo solo andando
chiamare complexity--

34
00:01:36,190 --> 00:01:38,770
stiamo generalmente parlando
la peggiore delle ipotesi.

35
00:01:38,770 --> 00:01:42,640
Dato il peggiore in assoluto di palo
dati che potremmo buttare a lui,

36
00:01:42,640 --> 00:01:46,440
come è questo algoritmo sta per
elaborare o trattare tali dati?

37
00:01:46,440 --> 00:01:51,450
In genere chiamiamo il caso peggiore
tempo di esecuzione di un algoritmo O-grande.

38
00:01:51,450 --> 00:01:56,770
Quindi un algoritmo può essere detto di
eseguito in O di n o n O di quadrato.

39
00:01:56,770 --> 00:01:59,110
E di più su ciò
quelli significa in un secondo.

40
00:01:59,110 --> 00:02:01,620
>> A volte, però, facciamo cura
circa la migliore delle ipotesi.

41
00:02:01,620 --> 00:02:05,400
Se i dati sono tutto quello che volevamo
che sia ed era assolutamente perfetto

42
00:02:05,400 --> 00:02:09,630
e siamo stati l'invio di questo perfetto
set di dati attraverso il nostro algoritmo.

43
00:02:09,630 --> 00:02:11,470
Come sarebbe gestire in quella situazione?

44
00:02:11,470 --> 00:02:15,050
Ci riferiamo a volte che, come
big-Omega, così in contrasto con O-grande,

45
00:02:15,050 --> 00:02:16,530
abbiamo grande-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega per la migliore delle ipotesi.

47
00:02:18,880 --> 00:02:21,319
Big-O per la peggiore delle ipotesi.

48
00:02:21,319 --> 00:02:23,860
In generale, quando si parla di
la complessità di un algoritmo,

49
00:02:23,860 --> 00:02:26,370
stiamo parlando della
nella peggiore delle ipotesi.

50
00:02:26,370 --> 00:02:28,100
Modo da tenere a mente.

51
00:02:28,100 --> 00:02:31,510
>> E in questa classe, stiamo andando in genere
di lasciare la rigorosa analisi da parte.

52
00:02:31,510 --> 00:02:35,350
Ci sono scienze e campi
dedicato a questo genere di cose.

53
00:02:35,350 --> 00:02:37,610
Quando si parla di ragionamento
tramite algoritmi,

54
00:02:37,610 --> 00:02:41,822
che faremo pezzo per pezzo per molti
Algoritmi parliamo della classe.

55
00:02:41,822 --> 00:02:44,780
Stiamo davvero parlando solo
ragionamento attraverso di essa con il senso comune,

56
00:02:44,780 --> 00:02:47,070
non con formule, o prove,
o qualcosa di simile.

57
00:02:47,070 --> 00:02:51,600
Quindi non preoccupatevi, Non saremo
si trasforma in una grande classe di matematica.

58
00:02:51,600 --> 00:02:55,920
>> Così ho detto ci preoccupiamo per la complessità
perché pone la domanda, come

59
00:02:55,920 --> 00:03:00,160
non i nostri algoritmi gestiscono più grande e
set di dati più grandi essere gettato contro di loro.

60
00:03:00,160 --> 00:03:01,960
Beh, quello che è un insieme di dati?

61
00:03:01,960 --> 00:03:03,910
Che cosa voglio dire quando ho detto che?

62
00:03:03,910 --> 00:03:07,600
Significa ciò che rende la maggior parte
senso nel contesto, ad essere onesti.

63
00:03:07,600 --> 00:03:11,160
Se abbiamo un algoritmo, il
Processi Strings-- probabilmente siamo

64
00:03:11,160 --> 00:03:13,440
parlando della dimensione della stringa.

65
00:03:13,440 --> 00:03:15,190
Ecco i dati set--
la dimensione, il numero

66
00:03:15,190 --> 00:03:17,050
di caratteri che compongono la stringa.

67
00:03:17,050 --> 00:03:20,090
Se stiamo parlando di un
algoritmo che elabora i file,

68
00:03:20,090 --> 00:03:23,930
potremmo parlare di come
molti kilobyte comprendono quel file.

69
00:03:23,930 --> 00:03:25,710
E questo è il set di dati.

70
00:03:25,710 --> 00:03:28,870
Se stiamo parlando di un algoritmo
che gestisce array più in generale,

71
00:03:28,870 --> 00:03:31,510
quali algoritmi di ordinamento
o la ricerca di algoritmi,

72
00:03:31,510 --> 00:03:36,690
probabilmente stiamo parlando del numero di
di elementi che compongono un array.

73
00:03:36,690 --> 00:03:39,272
>> Ora, siamo in grado di misurare una
algorithm-- in particolare,

74
00:03:39,272 --> 00:03:40,980
quando dico che possiamo
misurare un algoritmo, I

75
00:03:40,980 --> 00:03:43,840
significa che possiamo misurare come
molte risorse che occupa.

76
00:03:43,840 --> 00:03:48,990
Se tali risorse sono, quanti
byte di RAM-- o megabyte di RAM

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

78
00:03:49,790 --> 00:03:52,320
O quanto tempo necessario per l'esecuzione.

79
00:03:52,320 --> 00:03:56,200
E possiamo chiamare questo
misura, arbitrariamente, f n.

80
00:03:56,200 --> 00:03:59,420
Dove n è il numero di
elementi del set di dati.

81
00:03:59,420 --> 00:04:02,640
E f n è il numero di quarantina.

82
00:04:02,640 --> 00:04:07,530
Quante unità di risorse fa
si richiede di elaborare tali dati.

83
00:04:07,530 --> 00:04:10,030
>> Ora, in realtà non ci interessa
su ciò che f n è esattamente.

84
00:04:10,030 --> 00:04:13,700
In effetti, abbiamo will-- molto raramente
certamente non sarà mai in questo io class--

85
00:04:13,700 --> 00:04:18,709
tuffarsi in qualsiasi veramente profondo
analisi di ciò che f n è.

86
00:04:18,709 --> 00:04:23,510
Stiamo solo andando a parlare di ciò che di f
n è approssimativamente o ciò tende a.

87
00:04:23,510 --> 00:04:27,600
E la tendenza di un algoritmo
dettata dal suo termine di ordine più alto.

88
00:04:27,600 --> 00:04:29,440
E possiamo vedere quello che ho
dire con che prendendo

89
00:04:29,440 --> 00:04:31,910
uno sguardo ad un esempio più concreto.

90
00:04:31,910 --> 00:04:34,620
>> Quindi cerchiamo di dire che abbiamo
tre diversi algoritmi.

91
00:04:34,620 --> 00:04:39,350
Il primo dei quali prende n
cubetti, alcune unità di risorse

92
00:04:39,350 --> 00:04:42,880
per elaborare un insieme di dati di dimensione n.

93
00:04:42,880 --> 00:04:47,000
Abbiamo un secondo algoritmo che prende
n cubetti più risorse n quadrati

94
00:04:47,000 --> 00:04:49,350
per elaborare un insieme di dati di dimensione n.

95
00:04:49,350 --> 00:04:52,030
E abbiamo un terzo
algoritmo che esegue dentro-- che

96
00:04:52,030 --> 00:04:58,300
riprende n meno cubetti 8n quadrato
più 20 n unità di risorse

97
00:04:58,300 --> 00:05:02,370
di elaborare un algoritmo
l'insieme di dati di dimensione n.

98
00:05:02,370 --> 00:05:05,594
>> Ora di nuovo, noi non stiamo andando
per entrare in questo livello di dettaglio.

99
00:05:05,594 --> 00:05:08,260
Sono davvero ho solo questi in su
qui come un esempio di un punto

100
00:05:08,260 --> 00:05:10,176
che ho intenzione di essere
facendo in un secondo,

101
00:05:10,176 --> 00:05:12,980
è che abbiamo solo veramente a cuore
per la tendenza delle cose

102
00:05:12,980 --> 00:05:14,870
come i set di dati diventano più grandi.

103
00:05:14,870 --> 00:05:18,220
Quindi, se il set di dati è piccolo, non c'è
in realtà una bella differenza

104
00:05:18,220 --> 00:05:19,870
in questi algoritmi.

105
00:05:19,870 --> 00:05:23,000
Il terzo algoritmo di lì
prende 13 volte più a lungo,

106
00:05:23,000 --> 00:05:27,980
13 volte la quantità di risorse
eseguire rispetto al primo.

107
00:05:27,980 --> 00:05:31,659
>> Se il nostro set di dati è la dimensione 10, che
è più grande, ma non necessariamente enorme,

108
00:05:31,659 --> 00:05:33,950
possiamo vedere che non c'è
in realtà un po 'di differenza.

109
00:05:33,950 --> 00:05:36,620
Il terzo algoritmo
diventa più efficiente.

110
00:05:36,620 --> 00:05:40,120
Si tratta di realtà il 40% -
o il 60% più efficiente.

111
00:05:40,120 --> 00:05:41,580
Prende 40% la quantità di tempo.

112
00:05:41,580 --> 00:05:45,250
Può run-- si può prendere
400 unità di risorse

113
00:05:45,250 --> 00:05:47,570
di elaborare un insieme di dati di dimensioni 10.

114
00:05:47,570 --> 00:05:49,410
Considerando che la prima
algoritmo, per contrasto,

115
00:05:49,410 --> 00:05:54,520
prende 1.000 unità di risorse
di elaborare un insieme di dati di dimensioni 10.

116
00:05:54,520 --> 00:05:57,240
Ma guardate cosa succede come
i nostri numeri diventano ancora più grande.

117
00:05:57,240 --> 00:05:59,500
>> Ora, la differenza
tra questi algoritmi

118
00:05:59,500 --> 00:06:01,420
iniziare a diventare un po 'meno evidente.

119
00:06:01,420 --> 00:06:04,560
E il fatto che ci sono
di ordine inferiore terms-- o meglio,

120
00:06:04,560 --> 00:06:09,390
patti con bassa exponents--
iniziare a diventare irrilevante.

121
00:06:09,390 --> 00:06:12,290
Se un insieme di dati è di dimensioni
1.000 e il primo algoritmo

122
00:06:12,290 --> 00:06:14,170
viene eseguito in un miliardo di passi.

123
00:06:14,170 --> 00:06:17,880
E il secondo algoritmo viene eseguito in
un miliardo e un milione di passi.

124
00:06:17,880 --> 00:06:20,870
E il terzo algoritmo funziona
in poco meno di un miliardo di punti.

125
00:06:20,870 --> 00:06:22,620
E 'più o meno un miliardo di passi.

126
00:06:22,620 --> 00:06:25,640
Questi termini di ordine inferiore iniziano
per diventare davvero irrilevante.

127
00:06:25,640 --> 00:06:27,390
E proprio per davvero
martello a casa il Point--

128
00:06:27,390 --> 00:06:31,240
se l'input dei dati è di dimensioni un
million-- tutti e tre di questi più o meno

129
00:06:31,240 --> 00:06:34,960
prendere uno quintillion-- se
la mia matematica è a pochi passi correct--

130
00:06:34,960 --> 00:06:37,260
per elaborare un ingresso dati
di dimensioni un milione.

131
00:06:37,260 --> 00:06:38,250
Questo è un sacco di passi.

132
00:06:38,250 --> 00:06:42,092
E il fatto che uno di essi potrebbe
prendere un paio di 100.000, o una coppia di 100

133
00:06:42,092 --> 00:06:44,650
milioni di ancor meno quando
stiamo parlando di un numero

134
00:06:44,650 --> 00:06:46,990
che big-- è una specie di irrilevante.

135
00:06:46,990 --> 00:06:50,006
Tutti tendono a prendere
circa n cubetti,

136
00:06:50,006 --> 00:06:52,380
e così ci sarebbe in realtà riferirsi
a tutti questi algoritmi

137
00:06:52,380 --> 00:06:59,520
come essendo dell'ordine di n
a cubetti o O-grande di n cubetti.

138
00:06:59,520 --> 00:07:03,220
>> Ecco un elenco di alcuni dei più
classi comuni di complessità computazionale

139
00:07:03,220 --> 00:07:05,820
che ci incontriamo nella
algoritmi, generalmente.

140
00:07:05,820 --> 00:07:07,970
E anche specificamente in CS50.

141
00:07:07,970 --> 00:07:11,410
Questi sono ordinati da
generalmente più veloce in alto,

142
00:07:11,410 --> 00:07:13,940
a generalmente più lenta in basso.

143
00:07:13,940 --> 00:07:16,920
Così algoritmi costante di tempo tendono
essere il più veloce, indipendentemente

144
00:07:16,920 --> 00:07:19,110
della dimensione del
inserimento dei dati si passa.

145
00:07:19,110 --> 00:07:23,760
Prendono sempre una operazione o
una unità di risorse per far fronte.

146
00:07:23,760 --> 00:07:25,730
Potrebbe essere 2, potrebbe
essere di 3, potrebbe essere 4.

147
00:07:25,730 --> 00:07:26,910
Ma è un numero costante.

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

149
00:07:28,400 --> 00:07:31,390
>> Algoritmi tempo logaritmico
sono un po 'meglio.

150
00:07:31,390 --> 00:07:33,950
E davvero un buon esempio di
un algoritmo di tempo logaritmico

151
00:07:33,950 --> 00:07:37,420
avete sicuramente visto ormai è il
lacerazione della rubrica

152
00:07:37,420 --> 00:07:39,480
trovare Mike Smith nella rubrica.

153
00:07:39,480 --> 00:07:40,980
Abbiamo tagliato il problema a metà.

154
00:07:40,980 --> 00:07:43,580
E così quando n diventa più grande
e più grande e larger--

155
00:07:43,580 --> 00:07:47,290
infatti, ogni volta che si raddoppia
n, ci vuole solo un altro passo.

156
00:07:47,290 --> 00:07:49,770
Ecco, questo è molto meglio
rispetto, ad esempio, il tempo lineare.

157
00:07:49,770 --> 00:07:53,030
Quale è se si raddoppia n, esso
prende il doppio del numero di passi.

158
00:07:53,030 --> 00:07:55,980
Se triplicare n, ci vuole
triplicare il numero di passi.

159
00:07:55,980 --> 00:07:58,580
Un passo per unità.

160
00:07:58,580 --> 00:08:01,790
>> Poi le cose si fanno un po more--
poco meno grande da lì.

161
00:08:01,790 --> 00:08:06,622
Avete tempo ritmico lineare, a volte
chiamato registro tempo lineare o solo n log n.

162
00:08:06,622 --> 00:08:08,330
E faremo un esempio
di un algoritmo che

163
00:08:08,330 --> 00:08:13,370
viene eseguito in n log n, che è ancora meglio
di tempo-- quadratica n al quadrato.

164
00:08:13,370 --> 00:08:17,320
Oppure tempo polinomiale, n due
qualsiasi numero maggiore di due.

165
00:08:17,320 --> 00:08:20,810
Oppure tempo esponenziale, che
è anche peggio-- C al n.

166
00:08:20,810 --> 00:08:24,670
Così alcuni numero costante elevato a
il potere della dimensione dell'input.

167
00:08:24,670 --> 00:08:28,990
Quindi, se c'è 1,000-- se la
immissione dei dati è di dimensioni 1.000,

168
00:08:28,990 --> 00:08:31,310
ci vorrebbe C al potere 1000.

169
00:08:31,310 --> 00:08:33,559
E 'molto peggio di un tempo polinomiale.

170
00:08:33,559 --> 00:08:35,030
>> Tempo fattoriale è ancora peggio.

171
00:08:35,030 --> 00:08:37,760
E in effetti, c'è davvero fare
Esistono algoritmi tempo infinito,

172
00:08:37,760 --> 00:08:43,740
come ad esempio, i cosiddetti sort-- stupido cui
compito è quello di mescolare in modo casuale un array

173
00:08:43,740 --> 00:08:45,490
e quindi verificare
se è ordinato.

174
00:08:45,490 --> 00:08:47,589
E se non lo è, in modo casuale
mescolare di nuovo l'array

175
00:08:47,589 --> 00:08:49,130
e verificare se è ordinato.

176
00:08:49,130 --> 00:08:51,671
E come si può probabilmente imagine--
si può immaginare una situazione

177
00:08:51,671 --> 00:08:55,200
dove nel caso peggiore, che la volontà
mai effettivamente iniziare con l'array.

178
00:08:55,200 --> 00:08:57,150
Questo algoritmo funzionerebbe per sempre.

179
00:08:57,150 --> 00:08:59,349
E così che sarebbe un
algoritmo di tempo infinito.

180
00:08:59,349 --> 00:09:01,890
Speriamo che non sarà la scrittura
qualsiasi momento fattoriale o infinito

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

182
00:09:04,510 --> 00:09:09,150
>> Allora, facciamo un po 'di più
sguardo concreto ad alcune semplici

183
00:09:09,150 --> 00:09:11,154
classi di complessità computazionale.

184
00:09:11,154 --> 00:09:13,070
Quindi abbiamo un example--
o due esempi qui--

185
00:09:13,070 --> 00:09:15,590
algoritmi di tempo costante,
che sempre prendere

186
00:09:15,590 --> 00:09:17,980
una singola operazione nel caso peggiore.

187
00:09:17,980 --> 00:09:20,050
Quindi la prima example--
abbiamo una funzione

188
00:09:20,050 --> 00:09:23,952
chiamato 4 per te, che
accetta un array di dimensioni 1.000.

189
00:09:23,952 --> 00:09:25,660
Ma poi a quanto pare
in realtà non guardare

190
00:09:25,660 --> 00:09:29,000
a it-- in realtà non importa ciò che è
all'interno di esso, di tale matrice.

191
00:09:29,000 --> 00:09:30,820
Sempre restituisce solo quattro.

192
00:09:30,820 --> 00:09:32,940
Quindi, tale algoritmo,
nonostante il fatto che

193
00:09:32,940 --> 00:09:35,840
prende 1.000 elementi non
fare qualcosa con loro.

194
00:09:35,840 --> 00:09:36,590
Proprio restituisce quattro.

195
00:09:36,590 --> 00:09:38,240
E 'sempre un solo passo.

196
00:09:38,240 --> 00:09:41,600
>> In realtà, aggiungere 2 nums-- che
abbiamo visto prima come well--

197
00:09:41,600 --> 00:09:43,680
appena due interi processi.

198
00:09:43,680 --> 00:09:44,692
Non è un solo passo.

199
00:09:44,692 --> 00:09:45,900
In realtà è un paio di passi.

200
00:09:45,900 --> 00:09:50,780
Si ottiene un, si ottiene b, vengono aggiunti
insieme, e voi di uscita dei risultati.

201
00:09:50,780 --> 00:09:53,270
Quindi è di 84 gradini.

202
00:09:53,270 --> 00:09:55,510
Ma è sempre costante,
indipendentemente a o b.

203
00:09:55,510 --> 00:09:59,240
Dovete ottenere un, ottenere b, aggiungere
insieme, uscita il risultato.

204
00:09:59,240 --> 00:10:02,900
Quindi questo è un algoritmo di tempo costante.

205
00:10:02,900 --> 00:10:05,170
>> Ecco un esempio di un
tempo algorithm-- lineari

206
00:10:05,170 --> 00:10:08,740
un algoritmo che gets-- che prende
un passo ulteriore, eventualmente,

207
00:10:08,740 --> 00:10:10,740
come ingresso cresce di 1.

208
00:10:10,740 --> 00:10:14,190
Quindi, diciamo che stiamo cercando
il numero 5 all'interno di una matrice.

209
00:10:14,190 --> 00:10:16,774
Si potrebbe avere una situazione in cui
si può trovare abbastanza presto.

210
00:10:16,774 --> 00:10:18,606
Ma si potrebbe anche avere
una situazione in cui

211
00:10:18,606 --> 00:10:20,450
potrebbe essere l'ultimo elemento dell'array.

212
00:10:20,450 --> 00:10:23,780
In un array di dimensioni 5, se
stiamo cercando il numero 5.

213
00:10:23,780 --> 00:10:25,930
Ci vorrebbero 5 passi.

214
00:10:25,930 --> 00:10:29,180
E infatti, immaginare che ci sia
non 5 ovunque in questo array.

215
00:10:29,180 --> 00:10:32,820
Abbiamo ancora in realtà dobbiamo guardare
ogni singolo elemento dell'array

216
00:10:32,820 --> 00:10:35,550
per determinare
o meno 5 è lì.

217
00:10:35,550 --> 00:10:39,840
>> Quindi nel caso peggiore, che è quella
l'elemento è ultima nell'array

218
00:10:39,840 --> 00:10:41,700
o non esiste affatto.

219
00:10:41,700 --> 00:10:44,690
Dobbiamo ancora guardare
tutti gli n elementi.

220
00:10:44,690 --> 00:10:47,120
E così questo algoritmo
viene eseguito in tempo lineare.

221
00:10:47,120 --> 00:10:50,340
È possibile confermare che,
estrapolando un po 'dicendo:

222
00:10:50,340 --> 00:10:53,080
se avessimo un array di 6 elementi e
stavamo cercando per il numero 5,

223
00:10:53,080 --> 00:10:54,890
si potrebbe prendere 6 punti.

224
00:10:54,890 --> 00:10:57,620
Se abbiamo un array di 7 elementi e
stiamo cercando il numero 5.

225
00:10:57,620 --> 00:10:59,160
Si potrebbe prendere 7 passi.

226
00:10:59,160 --> 00:11:02,920
Come si aggiunge un ulteriore elemento per il nostro
array, ci vuole un passo in più.

227
00:11:02,920 --> 00:11:06,750
Questo è un algoritmo lineare
nel caso peggiore.

228
00:11:06,750 --> 00:11:08,270
>> Coppia brevi domande per voi.

229
00:11:08,270 --> 00:11:11,170
Qual è la cosa è runtime--
il caso peggiore runtime

230
00:11:11,170 --> 00:11:13,700
di questo particolare frammento di codice?

231
00:11:13,700 --> 00:11:17,420
Così ho un ciclo 4 qui che corre
da j è uguale a 0, tutta la strada fino a m.

232
00:11:17,420 --> 00:11:21,980
E quello che sto vedendo qui, è che il
corpo del ciclo viene eseguito in tempo costante.

233
00:11:21,980 --> 00:11:24,730
Quindi, utilizzando la terminologia che
abbiamo già parlato about-- cosa

234
00:11:24,730 --> 00:11:29,390
sarebbe il caso peggiore
tempo di esecuzione di questo algoritmo?

235
00:11:29,390 --> 00:11:31,050
Prendete un secondo.

236
00:11:31,050 --> 00:11:34,270
La parte interna del loop
viene eseguito in tempo costante.

237
00:11:34,270 --> 00:11:37,510
E la parte esterna del
ciclo è andare a correre m volte.

238
00:11:37,510 --> 00:11:40,260
Allora qual è il tempo di esecuzione nel caso peggiore qui?

239
00:11:40,260 --> 00:11:43,210
Avete indovinato O-grande di m?

240
00:11:43,210 --> 00:11:44,686
Avreste ragione.

241
00:11:44,686 --> 00:11:46,230
>> Che ne dite di un altro?

242
00:11:46,230 --> 00:11:48,590
Questa volta abbiamo una
ciclo all'interno di un ciclo.

243
00:11:48,590 --> 00:11:50,905
Abbiamo un ciclo esterno
che va da zero a p.

244
00:11:50,905 --> 00:11:54,630
E abbiamo un ciclo interno che gira
da zero a p, e all'interno di questo,

245
00:11:54,630 --> 00:11:57,890
Premetto che il corpo
ciclo viene eseguito in tempo costante.

246
00:11:57,890 --> 00:12:02,330
Allora qual è il tempo di esecuzione nel caso peggiore
di questo particolare frammento di codice?

247
00:12:02,330 --> 00:12:06,140
Bene, ancora una volta, abbiamo un
anello esterno che corre p volte.

248
00:12:06,140 --> 00:12:09,660
E ogni iterazione tempo--
di quel ciclo, piuttosto.

249
00:12:09,660 --> 00:12:13,170
Abbiamo un ciclo interno
che corre anche p volte.

250
00:12:13,170 --> 00:12:16,900
E poi dentro di questo, c'è il
costante piccolo frammento tempo-- lì.

251
00:12:16,900 --> 00:12:19,890
>> Quindi, se abbiamo un ciclo esterno che
gestisce p volte all'interno del quale è

252
00:12:19,890 --> 00:12:22,880
un ciclo interno che
gestisce p times-- ciò che è

253
00:12:22,880 --> 00:12:26,480
il caso peggiore runtime
di questo frammento di codice?

254
00:12:26,480 --> 00:12:30,730
Avete indovinato O-grande di p quadrato?

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

256
00:12:31,690 --> 00:12:33,880
Questo è CS50.

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