1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Vous avez probablement entendu des gens parler d'un algorithme rapide ou efficace

2
00:00:10,950 --> 00:00:13,090
pour l'exécution de votre tâche particulière,

3
00:00:13,090 --> 00:00:16,110
mais qu'est-ce que cela signifie pour un algorithme pour être rapide ou efficace?

4
00:00:16,110 --> 00:00:18,580
Eh bien, il ne parle pas d'une mesure en temps réel,

5
00:00:18,580 --> 00:00:20,500
comme des secondes ou minutes.

6
00:00:20,500 --> 00:00:22,220
C'est parce que le matériel informatique

7
00:00:22,220 --> 00:00:24,260
et logiciel varient considérablement.

8
00:00:24,260 --> 00:00:26,020
Mon programme pourrait fonctionner plus lentement que le vôtre,

9
00:00:26,020 --> 00:00:28,000
parce que je suis en train de courir sur un vieil ordinateur,

10
00:00:28,000 --> 00:00:30,110
ou parce que je suis à jouer à un jeu vidéo en ligne

11
00:00:30,110 --> 00:00:32,670
en même temps, ce qui est monopolisant toute ma mémoire,

12
00:00:32,670 --> 00:00:35,400
ou je pourrais être exécuté mon programme à travers différents logiciels

13
00:00:35,400 --> 00:00:37,550
qui communique avec la machine de manière différente à un niveau bas.

14
00:00:37,550 --> 00:00:39,650
C'est comme comparer des pommes et des oranges.

15
00:00:39,650 --> 00:00:41,940
Tout simplement parce que mon ordinateur plus lent prend plus de temps

16
00:00:41,940 --> 00:00:43,410
que le vôtre pour redonner une réponse

17
00:00:43,410 --> 00:00:45,510
ne signifie pas que vous avez l'algorithme plus efficace.

18
00:00:45,510 --> 00:00:48,830
>> Donc, puisque nous ne pouvons pas comparer directement les temps d'exécution des programmes

19
00:00:48,830 --> 00:00:50,140
en quelques secondes ou minutes,

20
00:00:50,140 --> 00:00:52,310
comment pouvons-nous comparer les 2 algorithmes différents

21
00:00:52,310 --> 00:00:55,030
quel que soit leur matériel ou logiciel?

22
00:00:55,030 --> 00:00:58,000
Pour créer une façon plus uniforme de mesure de l'efficacité algorithmique,

23
00:00:58,000 --> 00:01:00,360
les informaticiens et les mathématiciens ont mis au point

24
00:01:00,360 --> 00:01:03,830
concepts de mesure de la complexité d'un programme asymptotique

25
00:01:03,830 --> 00:01:06,110
et une notation appelée «Big Ohnotation '

26
00:01:06,110 --> 00:01:08,320
pour la description de ce produit.

27
00:01:08,320 --> 00:01:10,820
La définition formelle est que la fonction f (x)

28
00:01:10,820 --> 00:01:13,390
s'étend de l'ordre de g (x)

29
00:01:13,390 --> 00:01:15,140
s'il existe une certaine valeur (x), x ₀ et

30
00:01:15,140 --> 00:01:17,630
une constante, C, pour lequel

31
00:01:17,630 --> 00:01:19,340
f (x) est inférieur ou égal à

32
00:01:19,340 --> 00:01:21,230
que les temps constant g (x)

33
00:01:21,230 --> 00:01:23,190
pour tout x supérieur à x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Mais ne soyez pas effrayés par la définition formelle.

35
00:01:25,290 --> 00:01:28,020
Qu'est-ce que cela signifie réellement en termes moins théoriques?

36
00:01:28,020 --> 00:01:30,580
Eh bien, il s'agit essentiellement d'une méthode d'analyse

37
00:01:30,580 --> 00:01:33,580
la rapidité d'exécution d'un programme croît asymptotiquement.

38
00:01:33,580 --> 00:01:37,170
C'est, comme la taille de vos entrées augmente vers l'infini,

39
00:01:37,170 --> 00:01:41,390
mot à dire, vous triez un tableau de taille 1000 par rapport à un tableau de taille 10.

40
00:01:41,390 --> 00:01:44,950
Comment l'exécution de votre programme de grandir?

41
00:01:44,950 --> 00:01:47,390
Par exemple, imaginez compter le nombre de caractères

42
00:01:47,390 --> 00:01:49,350
dans une chaîne de la façon la plus simple

43
00:01:49,350 --> 00:01:51,620
 en marchant à travers toute la chaîne

44
00:01:51,620 --> 00:01:54,790
lettre par lettre et en ajoutant 1 à un compteur pour chaque caractère.

45
00:01:55,700 --> 00:01:58,420
Cet algorithme est dit de courir en temps linéaire

46
00:01:58,420 --> 00:02:00,460
en ce qui concerne le nombre de caractères,

47
00:02:00,460 --> 00:02:02,670
"N" dans la chaîne.

48
00:02:02,670 --> 00:02:04,910
En bref, il s'exécute en O (n).

49
00:02:05,570 --> 00:02:07,290
Pourquoi est-ce?

50
00:02:07,290 --> 00:02:09,539
Eh bien, en utilisant cette approche, le temps nécessaire

51
00:02:09,539 --> 00:02:11,300
pour traverser la totalité de la chaîne

52
00:02:11,300 --> 00:02:13,920
est proportionnelle au nombre de caractères.

53
00:02:13,920 --> 00:02:16,480
Compter le nombre de caractères dans une chaîne de 20 caractères

54
00:02:16,480 --> 00:02:18,580
va prendre deux fois plus longtemps que nécessaire

55
00:02:18,580 --> 00:02:20,330
pour compter les caractères dans une chaîne de 10 caractères,

56
00:02:20,330 --> 00:02:23,000
parce que vous devez examiner tous les caractères

57
00:02:23,000 --> 00:02:25,740
et chaque personnage prend la même quantité de temps à regarder.

58
00:02:25,740 --> 00:02:28,050
Lorsque vous augmentez le nombre de caractères,

59
00:02:28,050 --> 00:02:30,950
le runtime augmente linéairement avec la longueur d'entrée.

60
00:02:30,950 --> 00:02:33,500
>> Maintenant, imaginez si vous décidez que le temps linéaire,

61
00:02:33,500 --> 00:02:36,390
O (n), n'était tout simplement pas assez rapide pour vous?

62
00:02:36,390 --> 00:02:38,750
Peut-être que vous stockez des chaînes énormes,

63
00:02:38,750 --> 00:02:40,450
et vous ne pouvez pas payer le temps supplémentaire qu'il faudrait

64
00:02:40,450 --> 00:02:44,000
de parcourir la totalité de leurs caractères de comptage une après l'autre.

65
00:02:44,000 --> 00:02:46,650
Alors, vous décidez d'essayer quelque chose de différent.

66
00:02:46,650 --> 00:02:49,270
Que faire si vous souhaitez arriver déjà stocker le nombre de caractères

67
00:02:49,270 --> 00:02:52,690
dans la chaîne, par exemple, dans une variable appelée "len",

68
00:02:52,690 --> 00:02:54,210
dès le début du programme,

69
00:02:54,210 --> 00:02:57,800
avant même enregistré le premier caractère dans votre chaîne?

70
00:02:57,800 --> 00:02:59,980
Ensuite, tout ce que vous auriez à faire dès maintenant pour savoir la longueur de chaîne,

71
00:02:59,980 --> 00:03:02,570
est de vérifier que la valeur de la variable.

72
00:03:02,570 --> 00:03:05,530
Vous n'auriez pas à regarder la chaîne elle-même à tous,

73
00:03:05,530 --> 00:03:08,160
et accéder à la valeur d'une variable est considérée comme len

74
00:03:08,160 --> 00:03:11,100
une opération asymptotiquement temps constant,

75
00:03:11,100 --> 00:03:13,070
ou O (1).

76
00:03:13,070 --> 00:03:17,110
Pourquoi est-ce? Eh bien, rappelez-vous ce que signifie la complexité asymptotique.

77
00:03:17,110 --> 00:03:19,100
Comment le changement d'exécution que la taille

78
00:03:19,100 --> 00:03:21,400
de vos entrées pousse?

79
00:03:21,400 --> 00:03:24,630
>> Dites que vous tentiez d'obtenir le nombre de caractères dans une grande chaîne.

80
00:03:24,630 --> 00:03:26,960
Eh bien, il ne serait pas question quelle taille vous que la chaîne,

81
00:03:26,960 --> 00:03:28,690
même un million de caractères,

82
00:03:28,690 --> 00:03:31,150
tout ce que vous auriez à faire pour trouver la longueur de la corde avec cette approche,

83
00:03:31,150 --> 00:03:33,790
est de lire la valeur de la len variable,

84
00:03:33,790 --> 00:03:35,440
que vous avez déjà fait.

85
00:03:35,440 --> 00:03:38,200
La longueur d'entrée, c'est la longueur de la chaîne que vous essayez de trouver,

86
00:03:38,200 --> 00:03:41,510
n'affecte pas du tout la rapidité de votre programme fonctionne.

87
00:03:41,510 --> 00:03:44,550
Cette partie de votre programme irait aussi vite sur une chaîne d'un seul caractère

88
00:03:44,550 --> 00:03:46,170
et une chaîne de mille caractères,

89
00:03:46,170 --> 00:03:49,140
et c'est pourquoi ce programme serait appelé fonctionne en temps constant

90
00:03:49,140 --> 00:03:51,520
par rapport à la taille de l'entrée.

91
00:03:51,520 --> 00:03:53,920
>> Bien sûr, il ya un inconvénient.

92
00:03:53,920 --> 00:03:55,710
Vous passez d'espace mémoire supplémentaire sur votre ordinateur

93
00:03:55,710 --> 00:03:57,380
stocker la variable

94
00:03:57,380 --> 00:03:59,270
et le temps supplémentaire qu'il vous faut

95
00:03:59,270 --> 00:04:01,490
à faire le stockage réelle de la variable,

96
00:04:01,490 --> 00:04:03,390
mais le point est toujours debout,

97
00:04:03,390 --> 00:04:05,060
savoir combien de temps votre chaîne était

98
00:04:05,060 --> 00:04:07,600
ne dépend pas de la longueur de la chaîne du tout.

99
00:04:07,600 --> 00:04:10,720
Ainsi, il s'exécute en O (1) ou constante de temps.

100
00:04:10,720 --> 00:04:13,070
Cela ne veut certainement pas signifier

101
00:04:13,070 --> 00:04:15,610
que votre code s'exécute dans l'étape 1,

102
00:04:15,610 --> 00:04:17,470
mais peu importe combien d'étapes il est,

103
00:04:17,470 --> 00:04:20,019
si elle ne change pas avec la taille des entrées,

104
00:04:20,019 --> 00:04:23,420
il est encore asymptotiquement constant que nous représentons en tant que O (1).

105
00:04:23,420 --> 00:04:25,120
>> Comme vous pouvez probablement le deviner,

106
00:04:25,120 --> 00:04:27,940
il ya beaucoup de différents grands runtimes O algorithmes permettant de mesurer avec.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algorithmes sont asymptotiquement plus lent que O (n) des algorithmes.

108
00:04:32,980 --> 00:04:35,910
Qui est, selon le nombre d'éléments (n) croît,

109
00:04:35,910 --> 00:04:39,280
finalement O (n) ² algorithmes prendra plus de temps

110
00:04:39,280 --> 00:04:41,000
que O (n) pour exécuter des algorithmes.

111
00:04:41,000 --> 00:04:43,960
Cela ne veut pas dire O (n) des algorithmes toujours courir plus vite

112
00:04:43,960 --> 00:04:46,410
que O (n) ² algorithmes, même dans le même environnement,

113
00:04:46,410 --> 00:04:48,080
sur le même matériel.

114
00:04:48,080 --> 00:04:50,180
Peut-être que pour des tailles d'entrée des petits,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² algorithme peut effectivement travailler plus vite,

116
00:04:52,900 --> 00:04:55,450
mais, par la suite, comme la taille d'entrée augmente

117
00:04:55,450 --> 00:04:58,760
vers l'infini, le O (n) ² algorithme de runtime

118
00:04:58,760 --> 00:05:02,000
finira par éclipser le temps d'exécution de O (n) algorithme.

119
00:05:02,000 --> 00:05:04,230
Tout comme n'importe quelle fonction mathématique quadratique

120
00:05:04,230 --> 00:05:06,510
 finira par dépasser n'importe quelle fonction linéaire,

121
00:05:06,510 --> 00:05:09,200
peu importe combien d'un chef de démarrer la fonction linéaire commence avec.

122
00:05:10,010 --> 00:05:12,000
Si vous travaillez avec de grandes quantités de données,

123
00:05:12,000 --> 00:05:15,510
algorithmes qui s'exécutent en O (n) ² peut vraiment finir par ralentir votre programme,

124
00:05:15,510 --> 00:05:17,770
mais pour des tailles d'entrée de petites,

125
00:05:17,770 --> 00:05:19,420
vous n'aurez probablement même pas remarqué.

126
00:05:19,420 --> 00:05:21,280
>> Une autre complexité asymptotique est,

127
00:05:21,280 --> 00:05:24,420
temps logarithmique, O (log n).

128
00:05:24,420 --> 00:05:26,340
Un exemple d'un algorithme qui fonctionne aussi rapidement

129
00:05:26,340 --> 00:05:29,060
est l'algorithme de recherche binaire classique,

130
00:05:29,060 --> 00:05:31,850
pour trouver un élément dans une liste triée de déjà-éléments.

131
00:05:31,850 --> 00:05:33,400
>> Si vous ne savez pas ce que recherche binaire fait,

132
00:05:33,400 --> 00:05:35,170
Je vais l'expliquer pour vous très rapidement.

133
00:05:35,170 --> 00:05:37,020
Disons que vous êtes à la recherche pour le numéro 3

134
00:05:37,020 --> 00:05:40,200
dans ce tableau d'entiers.

135
00:05:40,200 --> 00:05:42,140
Il se penche sur l'élément central du tableau

136
00:05:42,140 --> 00:05:46,830
et demande: «Est-ce que je veux élément supérieur, égal ou inférieur à cela?"

137
00:05:46,830 --> 00:05:49,150
Si c'est égal, tant mieux. Vous avez trouvé l'élément, et vous avez terminé.

138
00:05:49,150 --> 00:05:51,300
Si elle est supérieure, alors vous savez que l'élément

139
00:05:51,300 --> 00:05:53,440
doit être dans le côté droit de la matrice,

140
00:05:53,440 --> 00:05:55,200
et vous ne pouvez regarder que dans l'avenir,

141
00:05:55,200 --> 00:05:57,690
et si elle est plus petite, alors vous savez qu'il doit être sur le côté gauche.

142
00:05:57,690 --> 00:06:00,980
Ce processus est ensuite répété avec la baie de petite taille

143
00:06:00,980 --> 00:06:02,870
jusqu'à ce que l'élément a été retrouvé.

144
00:06:08,080 --> 00:06:11,670
>> Cet algorithme puissant coupe la taille du tableau en deux avec chaque opération.

145
00:06:11,670 --> 00:06:14,080
Ainsi, pour trouver un élément dans un tableau trié de taille 8,

146
00:06:14,080 --> 00:06:16,170
tout au plus (log ₂ 8),

147
00:06:16,170 --> 00:06:18,450
ou 3 de ces opérations,

148
00:06:18,450 --> 00:06:22,260
vérification de l'élément du milieu, puis en coupant le tableau dans la moitié sera nécessaire,

149
00:06:22,260 --> 00:06:25,670
alors un tableau de taille 16 a (log ₂ 16),

150
00:06:25,670 --> 00:06:27,480
ou 4 opérations.

151
00:06:27,480 --> 00:06:30,570
C'est seulement 1 de plus pour une vaste opération de doubler de taille.

152
00:06:30,570 --> 00:06:32,220
Doublement de la taille de la matrice

153
00:06:32,220 --> 00:06:35,160
augmente le temps d'exécution de seulement 1 morceau de ce code.

154
00:06:35,160 --> 00:06:37,770
Encore une fois, en vérifiant l'élément central de la liste, puis fractionnement.

155
00:06:37,770 --> 00:06:40,440
Ainsi, il est dit de fonctionner en temps logarithmique,

156
00:06:40,440 --> 00:06:42,440
O (log n).

157
00:06:42,440 --> 00:06:44,270
Mais attendez, dites-vous,

158
00:06:44,270 --> 00:06:47,510
N'est-ce pas dépendre du lieu dans la liste l'élément que vous recherchez est?

159
00:06:47,510 --> 00:06:50,090
Que faire si le premier élément que vous regardez se trouve être la bonne?

160
00:06:50,090 --> 00:06:52,040
Ensuite, il ne prend que 1 opération,

161
00:06:52,040 --> 00:06:54,310
peu importe la taille de la liste est.

162
00:06:54,310 --> 00:06:56,310
>> Eh bien, c'est pourquoi les informaticiens ont termes plus

163
00:06:56,310 --> 00:06:58,770
la complexité asymptotique qui reflètent le meilleur des cas

164
00:06:58,770 --> 00:07:01,050
et le pire des cas les performances d'un algorithme.

165
00:07:01,050 --> 00:07:03,320
Plus exactement, les limites supérieure et inférieure

166
00:07:03,320 --> 00:07:05,090
sur le runtime.

167
00:07:05,090 --> 00:07:07,660
Dans le meilleur des cas pour la recherche binaire, notre élément est

168
00:07:07,660 --> 00:07:09,330
juste là au milieu,

169
00:07:09,330 --> 00:07:11,770
et vous l'obtiendrez en temps constant,

170
00:07:11,770 --> 00:07:14,240
peu importe la taille du reste du tableau est.

171
00:07:15,360 --> 00:07:17,650
Le symbole utilisé pour cela est Ω.

172
00:07:17,650 --> 00:07:19,930
Ainsi, cet algorithme est dit de courir dans Ω (1).

173
00:07:19,930 --> 00:07:21,990
Dans le meilleur des cas, il trouve rapidement l'élément,

174
00:07:21,990 --> 00:07:24,200
peu importe la taille du tableau est,

175
00:07:24,200 --> 00:07:26,050
mais dans le pire des cas,

176
00:07:26,050 --> 00:07:28,690
qu'il doit accomplir (log n) vérifie fendus

177
00:07:28,690 --> 00:07:31,030
du tableau pour trouver le bon élément.

178
00:07:31,030 --> 00:07:34,270
Le pire des cas limites supérieures sont appelées avec le grand "O" que vous connaissez déjà.

179
00:07:34,270 --> 00:07:38,080
Ainsi, il est O (log n), mais Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> Une recherche linéaire, en revanche,

181
00:07:40,680 --> 00:07:43,220
dans lequel vous guidera à travers chaque élément du tableau

182
00:07:43,220 --> 00:07:45,170
pour trouver celui que vous voulez,

183
00:07:45,170 --> 00:07:47,420
Ω est au mieux (1).

184
00:07:47,420 --> 00:07:49,430
Encore une fois, le premier élément que vous voulez.

185
00:07:49,430 --> 00:07:51,930
Donc, ce n'est pas grave la taille du tableau est.

186
00:07:51,930 --> 00:07:54,840
Dans le pire des cas, c'est le dernier élément du tableau.

187
00:07:54,840 --> 00:07:58,560
Donc, vous avez à marcher à travers tous les éléments contenus dans le tableau n pour le trouver,

188
00:07:58,560 --> 00:08:02,170
comme si vous étiez à la recherche d'un 3.

189
00:08:04,320 --> 00:08:06,030
Ainsi, il s'exécute en O (n)

190
00:08:06,030 --> 00:08:09,330
car il est proportionnel au nombre d'éléments dans le tableau.

191
00:08:10,800 --> 00:08:12,830
>> Un autre symbole utilisé est Θ.

192
00:08:12,830 --> 00:08:15,820
Cela peut être utilisé pour décrire des algorithmes où les meilleurs et les pires des cas

193
00:08:15,820 --> 00:08:17,440
sont les mêmes.

194
00:08:17,440 --> 00:08:20,390
C'est le cas dans les algorithmes de chaîne de longueur dont nous avons parlé plus tôt.

195
00:08:20,390 --> 00:08:22,780
Autrement dit, si nous le stocker dans une variable avant

196
00:08:22,780 --> 00:08:25,160
nous stockons la chaîne et y accéder ultérieurement en temps constant.

197
00:08:25,160 --> 00:08:27,920
Peu importe ce numéro

198
00:08:27,920 --> 00:08:30,130
que nous stockons dans cette variable, nous aurons à le regarder.

199
00:08:33,110 --> 00:08:35,110
Le meilleur cas est, nous le regardons

200
00:08:35,110 --> 00:08:37,120
et calculer la longueur de la chaîne.

201
00:08:37,120 --> 00:08:39,799
Alors Ω (1) ou le meilleur des cas la constante de temps.

202
00:08:39,799 --> 00:08:41,059
Le pire des cas est,

203
00:08:41,059 --> 00:08:43,400
nous regarder et trouver la longueur de la chaîne.

204
00:08:43,400 --> 00:08:47,300
Donc, O (1) ou constante de temps dans le pire des cas.

205
00:08:47,300 --> 00:08:49,180
Donc, puisque le meilleur des cas et le pire des cas sont les mêmes,

206
00:08:49,180 --> 00:08:52,520
ce qui peut être dit de courir en Θ (1) fois.

207
00:08:54,550 --> 00:08:57,010
>> En résumé, nous avons de bonnes façons de raisonner sur l'efficacité des codes

208
00:08:57,010 --> 00:09:00,110
sans rien connaître le temps du monde réel qu'ils prennent à courir,

209
00:09:00,110 --> 00:09:02,270
qui est affectée par de nombreux facteurs extérieurs,

210
00:09:02,270 --> 00:09:04,190
y compris le matériel différent, logiciels,

211
00:09:04,190 --> 00:09:06,040
ou les spécificités de votre code.

212
00:09:06,040 --> 00:09:08,380
De plus, il nous permet de bien raisonner sur ce qui va se passer

213
00:09:08,380 --> 00:09:10,180
lorsque la taille de l'augmentation des entrées.

214
00:09:10,180 --> 00:09:12,490
>> Si vous utilisez en O (n) ² algorithme,

215
00:09:12,490 --> 00:09:15,240
ou pire, un O (2 ⁿ) algorithme,

216
00:09:15,240 --> 00:09:17,170
l'un des types les plus rapides en croissance,

217
00:09:17,170 --> 00:09:19,140
vous allez vraiment commencer à remarquer le ralentissement

218
00:09:19,140 --> 00:09:21,220
lorsque vous commencez à travailler avec de grandes quantités de données.

219
00:09:21,220 --> 00:09:23,590
>> C'est la complexité asymptotique. Merci.