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

2
00:00:05,830 --> 00:00:07,910
>> Très bien, alors, la complexité de calcul.

3
00:00:07,910 --> 00:00:10,430
Juste un peu d'un avertissement
Avant de nous plonger dans de trop far--

4
00:00:10,430 --> 00:00:13,070
ce sera probablement parmi les
les choses les plus de maths-lourd

5
00:00:13,070 --> 00:00:14,200
nous parlons dans CS50.

6
00:00:14,200 --> 00:00:16,950
Espérons que ce ne sera pas trop écrasante
et nous allons essayer de vous guider

7
00:00:16,950 --> 00:00:19,200
dans le processus, mais
juste un peu d'un avertissement juste.

8
00:00:19,200 --> 00:00:21,282
Il ya un peu
des mathématiques en cause ici.

9
00:00:21,282 --> 00:00:23,990
Très bien, alors, afin de faire
utilisation de nos ressources informatiques

10
00:00:23,990 --> 00:00:28,170
dans le réel monde-- il est vraiment
important de comprendre les algorithmes

11
00:00:28,170 --> 00:00:30,750
et comment ils traitent les données.

12
00:00:30,750 --> 00:00:32,810
Si nous avons une très
algorithme efficace, nous

13
00:00:32,810 --> 00:00:36,292
peut minimiser la quantité de ressources
nous disposons pour traiter avec elle.

14
00:00:36,292 --> 00:00:38,750
Si nous avons un algorithme qui
va prendre beaucoup de travail

15
00:00:38,750 --> 00:00:41,210
pour traiter un très
vaste ensemble de données, il est

16
00:00:41,210 --> 00:00:44,030
va exiger plus
et plus de ressources, ce qui

17
00:00:44,030 --> 00:00:47,980
est de l'argent, de la RAM, tout ce genre de trucs.

18
00:00:47,980 --> 00:00:52,090
>> Donc, être capable d'analyser une
algorithme utilisant cet ensemble d'outils,

19
00:00:52,090 --> 00:00:56,110
essentiellement, demande à la question--
comment fonctionne cette échelle de l'algorithme

20
00:00:56,110 --> 00:00:59,020
comme on jette de plus en plus de données à elle?

21
00:00:59,020 --> 00:01:02,220
Dans CS50, la quantité de données que nous sommes
travailler avec est assez petite.

22
00:01:02,220 --> 00:01:05,140
Généralement, nos programmes vont
afin de fonctionner dans un deuxième ou less--

23
00:01:05,140 --> 00:01:07,830
probablement beaucoup moins
surtout au début.

24
00:01:07,830 --> 00:01:12,250
>> Mais pensez à une société qui traite
avec des centaines de millions de clients.

25
00:01:12,250 --> 00:01:14,970
Et ils ont besoin pour traiter
que les données de client.

26
00:01:14,970 --> 00:01:18,260
Comme le nombre de clients qu'ils
avoir devient de plus en plus grande,

27
00:01:18,260 --> 00:01:21,230
il va exiger
de plus en plus de ressources.

28
00:01:21,230 --> 00:01:22,926
Combien d'autres ressources?

29
00:01:22,926 --> 00:01:25,050
Eh bien, cela dépend de la façon dont
nous analysons l'algorithme,

30
00:01:25,050 --> 00:01:28,097
utilisant les outils de cette boîte à outils.

31
00:01:28,097 --> 00:01:31,180
Lorsque nous parlons de la complexité de
un algorithm-- qui, parfois, vous aurez

32
00:01:31,180 --> 00:01:34,040
entendre qu'elle a appelé le temps
la complexité ou de l'espace de la complexité

33
00:01:34,040 --> 00:01:36,190
mais nous allons juste
appeler complexity--

34
00:01:36,190 --> 00:01:38,770
nous sommes généralement parler
le pire scénario.

35
00:01:38,770 --> 00:01:42,640
Compte tenu de la pire tas de
les données que nous pourrions jeter à elle,

36
00:01:42,640 --> 00:01:46,440
comment cet algorithme va
traiter ou de traiter avec ces données?

37
00:01:46,440 --> 00:01:51,450
Nous appelons généralement le pire des cas
l'exécution d'un grand-O de l'algorithme.

38
00:01:51,450 --> 00:01:56,770
Donc un algorithme peut être dit
courir dans O n ou O n carré.

39
00:01:56,770 --> 00:01:59,110
Et plus sur ce que
ceux qui signifie dans une seconde.

40
00:01:59,110 --> 00:02:01,620
>> Parfois, cependant, nous ne nous soucions
sur le meilleur scénario.

41
00:02:01,620 --> 00:02:05,400
Si les données sont tout ce que nous voulions
que ce soit et il était absolument parfait

42
00:02:05,400 --> 00:02:09,630
et nous avons envoyé cette parfaite
ensemble de données grâce à notre algorithme.

43
00:02:09,630 --> 00:02:11,470
Comment serait-il gérer dans cette situation?

44
00:02:11,470 --> 00:02:15,050
On se réfère parfois à ce que
grand-Omega, donc en contraste avec Big-O,

45
00:02:15,050 --> 00:02:16,530
Nous avons de grands-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega pour le meilleur scénario.

47
00:02:18,880 --> 00:02:21,319
Big-O pour le pire des scénarios.

48
00:02:21,319 --> 00:02:23,860
Généralement, quand on parle de
la complexité d'un algorithme,

49
00:02:23,860 --> 00:02:26,370
nous parlons de la
le pire des cas.

50
00:02:26,370 --> 00:02:28,100
Alors garde cela en tête.

51
00:02:28,100 --> 00:02:31,510
>> Et dans cette classe, nous sommes généralement aller
de quitter l'analyse rigoureuse de côté.

52
00:02:31,510 --> 00:02:35,350
Il ya sciences et des champs
consacré à ce genre de choses.

53
00:02:35,350 --> 00:02:37,610
Lorsque nous parlons de raisonnement
grâce à des algorithmes,

54
00:02:37,610 --> 00:02:41,822
que nous ferons morceau par morceau pour beaucoup
algorithmes que nous parlons dans la classe.

55
00:02:41,822 --> 00:02:44,780
Nous sommes vraiment juste parler
raisonnement avec le sens commun,

56
00:02:44,780 --> 00:02:47,070
pas avec des formules ou des preuves,
ou quelque chose comme ça.

57
00:02:47,070 --> 00:02:51,600
Donc, ne vous inquiétez pas, nous ne serons pas
se transformer en une grande classe de mathématiques.

58
00:02:51,600 --> 00:02:55,920
>> Donc je l'ai dit nous nous soucions de la complexité
car il pose la question, comment

59
00:02:55,920 --> 00:03:00,160
nos algorithmes ne traitent plus grand et
de plus grands ensembles de données étant jetés sur eux.

60
00:03:00,160 --> 00:03:01,960
Eh bien, ce qui est un ensemble de données?

61
00:03:01,960 --> 00:03:03,910
Qu'est-ce que je veux dire quand je dis cela?

62
00:03:03,910 --> 00:03:07,600
Cela signifie que tout ce que fait le plus
sens dans le contexte, pour être honnête.

63
00:03:07,600 --> 00:03:11,160
Si nous avons un algorithme, la
Processus Strings-- Nous sommes probablement

64
00:03:11,160 --> 00:03:13,440
parler de la taille de la chaîne.

65
00:03:13,440 --> 00:03:15,190
Voilà les données set--
la taille, le nombre

66
00:03:15,190 --> 00:03:17,050
des caractères qui composent la chaîne.

67
00:03:17,050 --> 00:03:20,090
Si nous parlons d'une
algorithme qui traite les fichiers,

68
00:03:20,090 --> 00:03:23,930
nous pourrions parler de la façon dont
de nombreux kilo-octets comprennent ce fichier.

69
00:03:23,930 --> 00:03:25,710
Et qui est le jeu de données.

70
00:03:25,710 --> 00:03:28,870
Si nous parlons d'un algorithme
qui gère les tableaux, plus généralement,

71
00:03:28,870 --> 00:03:31,510
comme algorithmes de tri
ou la recherche des algorithmes,

72
00:03:31,510 --> 00:03:36,690
nous parlons probablement sur le nombre
des éléments qui composent un tableau.

73
00:03:36,690 --> 00:03:39,272
>> Maintenant, nous pouvons mesurer une
algorithm-- en particulier,

74
00:03:39,272 --> 00:03:40,980
quand je dis que nous pouvons
mesurer un algorithme, je

75
00:03:40,980 --> 00:03:43,840
dire que nous pouvons mesurer
de nombreuses ressources qu'il prend.

76
00:03:43,840 --> 00:03:48,990
Si ces ressources sont, combien
octets de RAM-- ou Mo de RAM

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

78
00:03:49,790 --> 00:03:52,320
Ou combien de temps qu'il faut pour exécuter.

79
00:03:52,320 --> 00:03:56,200
Et nous pouvons appeler cela
mesurer, arbitrairement, de f n.

80
00:03:56,200 --> 00:03:59,420
Où n est le nombre de
éléments de l'ensemble de données.

81
00:03:59,420 --> 00:04:02,640
Et f de n est le nombre de quadragénaires.

82
00:04:02,640 --> 00:04:07,530
Combien d'unités de ressources ne
il exige de traiter ces données.

83
00:04:07,530 --> 00:04:10,030
>> Maintenant, nous ne nous soucions pas fait
sur ce que f de n est exactement.

84
00:04:10,030 --> 00:04:13,700
En fait, nous will-- très rarement
Certainement jamais dans ce que je class--

85
00:04:13,700 --> 00:04:18,709
plonger dans quelle vraiment profonde
analyse de ce f de n est.

86
00:04:18,709 --> 00:04:23,510
Nous allons juste parler de ce que f
n est d'environ ou qui tend à.

87
00:04:23,510 --> 00:04:27,600
Et la tendance d'un algorithme est
dicté par son terme d'ordre le plus élevé.

88
00:04:27,600 --> 00:04:29,440
Et nous pouvons voir ce que je
dire par là en prenant

89
00:04:29,440 --> 00:04:31,910
un oeil à un exemple plus concret.

90
00:04:31,910 --> 00:04:34,620
>> Alors disons que nous avons
trois algorithmes différents.

91
00:04:34,620 --> 00:04:39,350
Le premier d'entre eux prend n
cubes, certaines unités de ressources

92
00:04:39,350 --> 00:04:42,880
pour traiter un ensemble de données de taille n.

93
00:04:42,880 --> 00:04:47,000
Nous avons un deuxième algorithme qui prend
n cubes ainsi que des ressources n carrés

94
00:04:47,000 --> 00:04:49,350
pour traiter un ensemble de données de taille n.

95
00:04:49,350 --> 00:04:52,030
Et nous avons un troisième
algorithme qui exécute in-- que

96
00:04:52,030 --> 00:04:58,300
prend n moins cubes 8n carré
plus 20 n unités de ressources

97
00:04:58,300 --> 00:05:02,370
pour traiter un algorithme
avec l'ensemble de taille n données.

98
00:05:02,370 --> 00:05:05,594
>> Maintenant, encore une fois, nous allons vraiment pas
pour entrer dans ce niveau de détail.

99
00:05:05,594 --> 00:05:08,260
Je suis vraiment ai juste ces up
ici comme une illustration d'un point

100
00:05:08,260 --> 00:05:10,176
que je vais être
prise dans une seconde, qui

101
00:05:10,176 --> 00:05:12,980
est que nous nous soucions seulement vraiment
à propos de la tendance des choses

102
00:05:12,980 --> 00:05:14,870
que les ensembles de données deviennent plus grands.

103
00:05:14,870 --> 00:05:18,220
Donc, si l'ensemble de données est petite, il ya
fait une très grande différence

104
00:05:18,220 --> 00:05:19,870
dans ces algorithmes.

105
00:05:19,870 --> 00:05:23,000
Le troisième algorithme y
prend 13 fois plus longtemps,

106
00:05:23,000 --> 00:05:27,980
13 fois la quantité de ressources
à courir par rapport à la première.

107
00:05:27,980 --> 00:05:31,659
>> Si notre ensemble de données est la taille 10, qui
est plus grand, mais pas nécessairement énorme,

108
00:05:31,659 --> 00:05:33,950
nous pouvons voir qu'il ya
en fait un peu de différence.

109
00:05:33,950 --> 00:05:36,620
Le troisième algorithme
devient plus efficace.

110
00:05:36,620 --> 00:05:40,120
Il est environ 40% en fait -
ou 60% plus efficace.

111
00:05:40,120 --> 00:05:41,580
Il faut 40% du temps.

112
00:05:41,580 --> 00:05:45,250
Il peut run-- il peut prendre
400 unités de ressources

113
00:05:45,250 --> 00:05:47,570
pour traiter un ensemble de données de taille 10.

114
00:05:47,570 --> 00:05:49,410
Alors que le premier
algorithme, par contraste,

115
00:05:49,410 --> 00:05:54,520
prend 1.000 unités de ressources
pour traiter un ensemble de données de taille 10.

116
00:05:54,520 --> 00:05:57,240
Mais regardez ce qui se passe comme
nos chiffres deviennent encore plus grand.

117
00:05:57,240 --> 00:05:59,500
>> Or, la différence
entre ces algorithmes

118
00:05:59,500 --> 00:06:01,420
commencer à devenir un peu moins apparente.

119
00:06:01,420 --> 00:06:04,560
Et le fait qu'il y a
ordre inférieur terms-- ou plutôt,

120
00:06:04,560 --> 00:06:09,390
termes avec exponents-- inférieure
commencer à devenir hors de propos.

121
00:06:09,390 --> 00:06:12,290
Si un ensemble de données est de taille
1000 et le premier algorithme

122
00:06:12,290 --> 00:06:14,170
fonctionne dans un milliards étapes.

123
00:06:14,170 --> 00:06:17,880
Et le deuxième algorithme fonctionne en
un milliard et un million étapes.

124
00:06:17,880 --> 00:06:20,870
Et le troisième algorithme exécute
dans un peu moins d'un milliard d'étapes.

125
00:06:20,870 --> 00:06:22,620
Il est à peu près un milliard d'étapes.

126
00:06:22,620 --> 00:06:25,640
Ces termes d'ordre inférieur commencent
pour devenir vraiment pertinent.

127
00:06:25,640 --> 00:06:27,390
Et juste pour vraiment
marteler le point--

128
00:06:27,390 --> 00:06:31,240
si l'entrée de données est une taille de
million-- tous les trois de ces à peu près

129
00:06:31,240 --> 00:06:34,960
prendre une quintillion-- si
mes calculs sont étapes correct--

130
00:06:34,960 --> 00:06:37,260
pour traiter une entrée de données
de la taille d'un million.

131
00:06:37,260 --> 00:06:38,250
Cela fait beaucoup d'étapes.

132
00:06:38,250 --> 00:06:42,092
Et le fait que l'un d'eux pourrait
prendre une couple de 100.000, ou un couple 100

133
00:06:42,092 --> 00:06:44,650
encore moins quand millions
nous parlons d'un certain nombre

134
00:06:44,650 --> 00:06:46,990
que big-- il est un peu hors de propos.

135
00:06:46,990 --> 00:06:50,006
Ils ont tous tendance à prendre
n cubes environ,

136
00:06:50,006 --> 00:06:52,380
et ainsi nous aurions effectivement reporter
à l'ensemble de ces algorithmes

137
00:06:52,380 --> 00:06:59,520
comme étant de l'ordre de n
cubes ou Big-O de n cubes.

138
00:06:59,520 --> 00:07:03,220
>> Voici une liste de quelques-uns des plus
classes de complexité de calcul communes

139
00:07:03,220 --> 00:07:05,820
que nous allons rencontrer dans
algorithmes, en général.

140
00:07:05,820 --> 00:07:07,970
Et aussi spécifiquement dans CS50.

141
00:07:07,970 --> 00:07:11,410
Ceux-ci sont commandés à partir
généralement plus rapide au sommet,

142
00:07:11,410 --> 00:07:13,940
généralement le plus lent à en bas.

143
00:07:13,940 --> 00:07:16,920
Donc algorithmes de constante de temps ont tendance
être le plus rapide, quel que soit

144
00:07:16,920 --> 00:07:19,110
de la taille de la
entrée de données vous passez.

145
00:07:19,110 --> 00:07:23,760
Ils prennent toujours une opération ou
une unité de ressources pour faire face à.

146
00:07:23,760 --> 00:07:25,730
Il pourrait être 2, il pourrait
être trois, il peut être 4.

147
00:07:25,730 --> 00:07:26,910
Mais il est un nombre constant.

148
00:07:26,910 --> 00:07:28,400
Il ne varie pas.

149
00:07:28,400 --> 00:07:31,390
>> Les algorithmes de temps logarithmique
sont un peu mieux.

150
00:07:31,390 --> 00:07:33,950
Et un très bon exemple de
un algorithme logarithmique

151
00:07:33,950 --> 00:07:37,420
vous avez sûrement vu désormais est la
déchirer du livre de téléphone

152
00:07:37,420 --> 00:07:39,480
à trouver Mike Smith dans le livre de téléphone.

153
00:07:39,480 --> 00:07:40,980
Nous avons réduit le problème de moitié.

154
00:07:40,980 --> 00:07:43,580
Et de manière plus large n obtient
et plus grande et larger--

155
00:07:43,580 --> 00:07:47,290
En fait, chaque fois que vous double
n, il prend seulement un pas de plus.

156
00:07:47,290 --> 00:07:49,770
Voilà donc beaucoup mieux
que, par exemple, le temps linéaire.

157
00:07:49,770 --> 00:07:53,030
Qui est si vous doublez n, il
prend le double du nombre d'étapes.

158
00:07:53,030 --> 00:07:55,980
Si vous triplez n, il faut
tripler le nombre d'étapes.

159
00:07:55,980 --> 00:07:58,580
Une étape par unité.

160
00:07:58,580 --> 00:08:01,790
>> Puis les choses deviennent un peu plus--
peu moins grande à partir de là.

161
00:08:01,790 --> 00:08:06,622
Vous avez le temps rythmique linéaire, parfois
appelé journal temps linéaire ou tout simplement n log n.

162
00:08:06,622 --> 00:08:08,330
Et nous allons un exemple
d'un algorithme qui

163
00:08:08,330 --> 00:08:13,370
points en n log n, ce qui est encore mieux
time-- quadratique de n au carré.

164
00:08:13,370 --> 00:08:17,320
Ou polynomiale, deux n
un nombre quelconque supérieur à deux.

165
00:08:17,320 --> 00:08:20,810
Ou le temps exponentielle, ce qui
est encore worse-- C au n.

166
00:08:20,810 --> 00:08:24,670
Ainsi, certains nombre constant porté à
la puissance de la taille de l'entrée.

167
00:08:24,670 --> 00:08:28,990
Donc, si il ya 1,000-- si le
entrée de données est de taille 1000,

168
00:08:28,990 --> 00:08:31,310
il faudrait C à la puissance 1000 e.

169
00:08:31,310 --> 00:08:33,559
Il est bien pire que le temps polynomiale.

170
00:08:33,559 --> 00:08:35,030
>> Temps factorielle est encore pire.

171
00:08:35,030 --> 00:08:37,760
Et en fait, il ne sont pas vraiment
Il existe des algorithmes de temps infini,

172
00:08:37,760 --> 00:08:43,740
tels que, soi-disant sort-- stupide dont
travail consiste à mélanger de façon aléatoire un tableau

173
00:08:43,740 --> 00:08:45,490
puis vérifier
si elle est triée.

174
00:08:45,490 --> 00:08:47,589
Et si elle est pas, au hasard
mélangez à nouveau le tableau

175
00:08:47,589 --> 00:08:49,130
et vérifier pour voir si elle est triée.

176
00:08:49,130 --> 00:08:51,671
Et comme vous pouvez probablement imagine--
vous pouvez imaginer une situation

177
00:08:51,671 --> 00:08:55,200
où, dans le pire des cas, que la volonté
jamais réellement commencer avec le tableau.

178
00:08:55,200 --> 00:08:57,150
Cet algorithme courrait toujours.

179
00:08:57,150 --> 00:08:59,349
Et ce serait une
algorithme de temps infini.

180
00:08:59,349 --> 00:09:01,890
Espérons que vous ne serez pas écrivez
tout moment factoriel ou infini

181
00:09:01,890 --> 00:09:04,510
algorithmes dans CS50.

182
00:09:04,510 --> 00:09:09,150
>> Donc, nous allons prendre un peu plus
regard concret sur certains simple

183
00:09:09,150 --> 00:09:11,154
classes de complexité de calcul.

184
00:09:11,154 --> 00:09:13,070
Nous avons donc une example--
ou deux exemples ici--

185
00:09:13,070 --> 00:09:15,590
des algorithmes de constante de temps,
qui prennent toujours

186
00:09:15,590 --> 00:09:17,980
une seule opération dans le pire des cas.

187
00:09:17,980 --> 00:09:20,050
Donc la première example--
nous avons une fonction

188
00:09:20,050 --> 00:09:23,952
appelé 4 pour vous, qui
prend un tableau de taille de 1000.

189
00:09:23,952 --> 00:09:25,660
Mais alors, semble-t-
ne fait pas regarder

190
00:09:25,660 --> 00:09:29,000
au it-- ne se soucie pas vraiment ce qui est
à l'intérieur, de ladite matrice.

191
00:09:29,000 --> 00:09:30,820
Toujours retourne juste quatre.

192
00:09:30,820 --> 00:09:32,940
Ainsi, cet algorithme,
malgré le fait qu'il

193
00:09:32,940 --> 00:09:35,840
prend 1.000 éléments n'a pas
faire quelque chose avec eux.

194
00:09:35,840 --> 00:09:36,590
Retourne juste quatre.

195
00:09:36,590 --> 00:09:38,240
Il est toujours une seule étape.

196
00:09:38,240 --> 00:09:41,600
>> En fait, ajouter 2 qui nums--
nous avons vu auparavant que well--

197
00:09:41,600 --> 00:09:43,680
processus juste deux entiers.

198
00:09:43,680 --> 00:09:44,692
Il est pas une seule étape.

199
00:09:44,692 --> 00:09:45,900
Il est en fait un couple d'étapes.

200
00:09:45,900 --> 00:09:50,780
Vous obtenez un, vous obtenez b, vous les ajoutez
ensemble, et sortie des résultats.

201
00:09:50,780 --> 00:09:53,270
Donc, il est 84 étapes.

202
00:09:53,270 --> 00:09:55,510
Mais il est toujours constante,
indépendamment de a ou b.

203
00:09:55,510 --> 00:09:59,240
Vous devez obtenir un, obtenez b, ajouter
ensemble, sortie du résultat.

204
00:09:59,240 --> 00:10:02,900
Voilà donc un algorithme de temps constant.

205
00:10:02,900 --> 00:10:05,170
>> Voici un exemple d'un
linéaire algorithm-- de temps

206
00:10:05,170 --> 00:10:08,740
un algorithme qui gets-- qui prend
une étape supplémentaire, le cas échéant,

207
00:10:08,740 --> 00:10:10,740
que votre entrée augmente de 1.

208
00:10:10,740 --> 00:10:14,190
Donc, disons que nous recherchons
le nombre 5 à l'intérieur d'un tableau.

209
00:10:14,190 --> 00:10:16,774
Vous pourriez avoir une situation où
vous pouvez le trouver assez tôt.

210
00:10:16,774 --> 00:10:18,606
Mais vous pourriez aussi avoir
une situation où il

211
00:10:18,606 --> 00:10:20,450
pourrait être le dernier élément du tableau.

212
00:10:20,450 --> 00:10:23,780
Dans un tableau de taille 5, si
nous recherchons pour le numéro 5.

213
00:10:23,780 --> 00:10:25,930
Il faudrait 5 étapes.

214
00:10:25,930 --> 00:10:29,180
Et en fait, imaginez qu'il ya
pas 5 partout dans ce tableau.

215
00:10:29,180 --> 00:10:32,820
En fait, nous avons encore à regarder
chaque élément du tableau

216
00:10:32,820 --> 00:10:35,550
afin de déterminer
si oui ou non il est 5.

217
00:10:35,550 --> 00:10:39,840
>> Donc, dans le pire des cas, ce qui est ce que
l'élément est la dernière dans le tableau

218
00:10:39,840 --> 00:10:41,700
ou ne existe pas du tout.

219
00:10:41,700 --> 00:10:44,690
Nous avons encore à regarder
tous les n éléments.

220
00:10:44,690 --> 00:10:47,120
Et si cet algorithme
fonctionne en temps linéaire.

221
00:10:47,120 --> 00:10:50,340
Vous pouvez confirmer que par
extrapolant un peu en disant,

222
00:10:50,340 --> 00:10:53,080
si nous avions un tableau 6-élément et
nous étions à la recherche pour le numéro 5,

223
00:10:53,080 --> 00:10:54,890
il pourrait prendre 6 étapes.

224
00:10:54,890 --> 00:10:57,620
Si nous avons un ensemble de 7 éléments et
nous recherchons pour le numéro 5.

225
00:10:57,620 --> 00:10:59,160
Il pourrait prendre 7 étapes.

226
00:10:59,160 --> 00:11:02,920
Comme nous ajoutons un élément de plus à notre
tableau, il prend un pas de plus.

227
00:11:02,920 --> 00:11:06,750
Voilà un algorithme linéaire
dans le pire des cas.

228
00:11:06,750 --> 00:11:08,270
>> Couple de questions pour vous.

229
00:11:08,270 --> 00:11:11,170
Quelle est la runtime-- ce qui est
le pire des cas d'exécution

230
00:11:11,170 --> 00:11:13,700
de ce bout de code particulier?

231
00:11:13,700 --> 00:11:17,420
Je dois donc une boucle de 4 ici qui fonctionne
De J est égal à 0, tout le chemin jusqu'à m.

232
00:11:17,420 --> 00:11:21,980
Et ce que je vois ici, est que le
corps de la boucle fonctionne en temps constant.

233
00:11:21,980 --> 00:11:24,730
Donc, en utilisant la terminologie
nous avons déjà parlé ce about--

234
00:11:24,730 --> 00:11:29,390
serait le pire des cas
exécution de cet algorithme?

235
00:11:29,390 --> 00:11:31,050
Prenez une seconde.

236
00:11:31,050 --> 00:11:34,270
La partie interne de la boucle
fonctionne en temps constant.

237
00:11:34,270 --> 00:11:37,510
Et la partie extérieure de la
boucle va courir m fois.

238
00:11:37,510 --> 00:11:40,260
Alors, quel est le pire des cas runtime ici?

239
00:11:40,260 --> 00:11:43,210
Avez-vous deviné Big-O de m?

240
00:11:43,210 --> 00:11:44,686
Vous avez raison.

241
00:11:44,686 --> 00:11:46,230
>> Que diriez-vous les uns les autres?

242
00:11:46,230 --> 00:11:48,590
Cette fois, nous avons une
boucle à l'intérieur d'une boucle.

243
00:11:48,590 --> 00:11:50,905
Nous avons une boucle externe
qui va de zéro à p.

244
00:11:50,905 --> 00:11:54,630
Et nous avons une boucle interne qui fonctionne
de zéro à p, et à l'intérieur de cela,

245
00:11:54,630 --> 00:11:57,890
Je déclare que le corps de la
boucle fonctionne en temps constant.

246
00:11:57,890 --> 00:12:02,330
Alors, quel est le pire des cas d'exécution
de ce bout de code particulier?

247
00:12:02,330 --> 00:12:06,140
Eh bien, encore une fois, nous avons une
boucle externe qui exécute p fois.

248
00:12:06,140 --> 00:12:09,660
Et chaque itération time--
de cette boucle, plutôt.

249
00:12:09,660 --> 00:12:13,170
Nous avons une boucle intérieure
qui fonctionne aussi p fois.

250
00:12:13,170 --> 00:12:16,900
Et puis à l'intérieur de cela, il ya la
constante petit extrait time-- il.

251
00:12:16,900 --> 00:12:19,890
>> Donc, si nous avons une boucle externe qui
exécute p fois intérieur de ce qui est

252
00:12:19,890 --> 00:12:22,880
une boucle intérieure qui
p exécute ce qui est times--

253
00:12:22,880 --> 00:12:26,480
le pire des cas d'exécution
de ce bout de code?

254
00:12:26,480 --> 00:12:30,730
Avez-vous deviné Big-O de p carré?

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

256
00:12:31,690 --> 00:12:33,880
Ceci est CS50.

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