1
00:00:00,000 --> 00:00:11,904
>> [Jouer de la musique]

2
00:00:11,904 --> 00:00:12,910
>> PROFESSEUR: Très bien.

3
00:00:12,910 --> 00:00:16,730
Ceci est ce qui est CS50
la fin de la troisième semaine.

4
00:00:16,730 --> 00:00:20,230
Donc, nous sommes ici aujourd'hui, pas dans Sanders
Théâtre, place dans Weidner Bibliothèque.

5
00:00:20,230 --> 00:00:23,170
A l'intérieur de laquelle est un studio
connu sous le nom Hauser en studio,

6
00:00:23,170 --> 00:00:28,310
ou dirons-nous en studio H, ou sont
nous say-- si vous avez apprécié cette blague,

7
00:00:28,310 --> 00:00:30,540
il est fait à partir de
camarade de classe, Mark, en ligne,

8
00:00:30,540 --> 00:00:32,420
qui a suggéré autant via Twitter.

9
00:00:32,420 --> 00:00:34,270
Maintenant, ce qui est cool à propos
être ici dans un studio

10
00:00:34,270 --> 00:00:38,410
est que je suis entouré par ces verts
murs, un écran vert ou incrustation,

11
00:00:38,410 --> 00:00:43,290
pour ainsi dire, ce qui signifie que ce CS50
équipe de production, à mon insu

12
00:00:43,290 --> 00:00:47,380
en ce moment, pourrait être mise
m'a le plus partout dans le monde,

13
00:00:47,380 --> 00:00:48,660
pour le meilleur ou pour le pire.

14
00:00:48,660 --> 00:00:51,800
>> Maintenant ce qui nous attend, problème réglé
deux est dans vos mains pour cette semaine,

15
00:00:51,800 --> 00:00:53,830
mais avec problème posé
trois cette semaine à venir,

16
00:00:53,830 --> 00:00:56,600
vous serez mis au défi avec
le jeu soi-disant de 15 ans,

17
00:00:56,600 --> 00:00:58,960
une faveur vieux parti qui
vous pourriez rappeler réception

18
00:00:58,960 --> 00:01:02,030
comme un enfant qui a tout un tas
des chiffres qui peuvent glisser vers le haut, le bas,

19
00:01:02,030 --> 00:01:05,790
gauche et droite, et il ya un fossé
dans le puzzle, dans lequel vous

20
00:01:05,790 --> 00:01:07,840
peut effectivement glisser les pièces du puzzle.

21
00:01:07,840 --> 00:01:11,150
En fin de compte vous recevez ce
Puzzle dans un ordre aléatoire demi,

22
00:01:11,150 --> 00:01:12,940
et l'objectif est de
le tri, de haut en bas,

23
00:01:12,940 --> 00:01:16,310
de gauche à droite, d'un
tout le chemin à travers 15.

24
00:01:16,310 --> 00:01:19,360
>> Malheureusement, la mise en œuvre
vous aurez à portée de main

25
00:01:19,360 --> 00:01:21,590
va être un logiciel
basé, non pas physiquement.

26
00:01:21,590 --> 00:01:25,280
Vous allez vraiment avoir à écrire
code avec lequel un étudiant ou un utilisateur peut

27
00:01:25,280 --> 00:01:26,760
jouer le jeu de 15.

28
00:01:26,760 --> 00:01:29,030
Et en fait, dans le pirate
édition de jeu de 15 ans,

29
00:01:29,030 --> 00:01:32,155
vous serez un défi de mettre en œuvre,
pas seulement le jeu de cette ancienne école

30
00:01:32,155 --> 00:01:35,010
jeu, mais plutôt la résolution
de celui-ci, la mise en oeuvre mode de dieu,

31
00:01:35,010 --> 00:01:38,280
pour ainsi dire, qui fait
résout le casse-tête pour l'humain,

32
00:01:38,280 --> 00:01:41,080
en leur fournissant soupçon,
après soupçon, après soupçon.

33
00:01:41,080 --> 00:01:42,280
Donc plus sur que la semaine prochaine.

34
00:01:42,280 --> 00:01:43,720
Mais voilà ce qui nous attend.

35
00:01:43,720 --> 00:01:47,610
>> Pour l'instant rappeler que plus tôt cette semaine
nous avons eu ce cliffhanger, si vous voulez,

36
00:01:47,610 --> 00:01:52,560
de sorte que le mieux que nous faisions le tri
sage était une limite supérieure de Big O n

37
00:01:52,560 --> 00:01:53,210
au carré.

38
00:01:53,210 --> 00:01:56,520
En d'autres termes, tri à bulles,
tri par sélection, le tri par insertion,

39
00:01:56,520 --> 00:01:59,120
chacun d'entre eux, bien que différente
dans leur mise en œuvre,

40
00:01:59,120 --> 00:02:03,480
dégénéré en un carré n courir
temps dans le pire des cas très.

41
00:02:03,480 --> 00:02:06,010
Et nous supposons généralement que
le pire cas pour le tri

42
00:02:06,010 --> 00:02:08,814
est celui qui vos entrées
sont complètement à l'envers.

43
00:02:08,814 --> 00:02:11,980
Et en effet, il a fallu pas mal de marches
pour mettre en œuvre chacune de ces algorithmes.

44
00:02:11,980 --> 00:02:15,110
>> Maintenant, à la fin de la classe
rappel, nous avons comparé tri à bulles

45
00:02:15,110 --> 00:02:19,390
contre la sélection sorte contre un autre
que nous avons appelé le tri par fusion à l'époque,

46
00:02:19,390 --> 00:02:22,120
et je propose que cela prend
profiter d'une leçon de la semaine

47
00:02:22,120 --> 00:02:24,060
zéro, diviser pour régner.

48
00:02:24,060 --> 00:02:28,810
Et la réalisation de quelque sorte une sorte de
logarithmique durée en fin de compte,

49
00:02:28,810 --> 00:02:31,024
lieu de quelque chose
qui est purement quadratique.

50
00:02:31,024 --> 00:02:33,440
Et il est pas tout à fait logarithmique,
il est un peu plus que cela.

51
00:02:33,440 --> 00:02:36,520
Mais si vous vous souvenez de la classe,
il était beaucoup, beaucoup plus rapide.

52
00:02:36,520 --> 00:02:38,210
Jetons un oeil à où nous nous sommes quittés.

53
00:02:38,210 --> 00:02:41,880

54
00:02:41,880 --> 00:02:45,370
>> Bubble sorte contre la sélection
Trier par rapport tri par fusion.

55
00:02:45,370 --> 00:02:47,700
Maintenant, ils sont tous en cours d'exécution, en
théorie, dans le même temps.

56
00:02:47,700 --> 00:02:50,510
Le CPU tourne à la même vitesse.

57
00:02:50,510 --> 00:02:54,990
Mais vous pouvez sentir comment cette ennuyeuse
va très rapidement devenir,

58
00:02:54,990 --> 00:02:58,790
et à quelle vitesse, lorsque nous injectons
un peu des algorithmes de la semaine zéro,

59
00:02:58,790 --> 00:03:00,080
pouvons-nous accélérer les choses.

60
00:03:00,080 --> 00:03:01,630
>> Donc sorte marque semble incroyable.

61
00:03:01,630 --> 00:03:05,220
Comment pouvons-nous en tirer parti, dans l'ordre
Pour trier des numéros plus rapidement.

62
00:03:05,220 --> 00:03:07,140
Eh bien, nous allons réfléchir retour
à un ingrédient qui nous

63
00:03:07,140 --> 00:03:10,380
avaient Retour à la semaine zéro, celle de
la recherche de quelqu'un dans un livre de téléphone,

64
00:03:10,380 --> 00:03:12,380
et de rappeler que la
pseudo que nous avons proposé,

65
00:03:12,380 --> 00:03:14,560
par lequel nous pouvons trouver
quelqu'un comme Mike Smith,

66
00:03:14,560 --> 00:03:16,310
regardé un petit quelque chose de ce genre.

67
00:03:16,310 --> 00:03:20,820
>> Maintenant, jetez un coup d'oeil en particulier
à la ligne 7 et 8, et 10 et 11,

68
00:03:20,820 --> 00:03:25,240
qui induisent cette boucle, par lequel nous gardions
revenir à la ligne 3, encore et encore,

69
00:03:25,240 --> 00:03:26,520
et encore.

70
00:03:26,520 --> 00:03:31,790
Mais il se trouve que nous pouvons voir
cet algorithme, ici en pseudo,

71
00:03:31,790 --> 00:03:33,620
un peu plus holistique.

72
00:03:33,620 --> 00:03:35,960
En fait, ce que je suis à la recherche
à ici sur l'écran,

73
00:03:35,960 --> 00:03:41,180
est un algorithme de recherche pour
Mike Smith chez certains ensemble de pages.

74
00:03:41,180 --> 00:03:45,520
Et en effet, nous pourrions simplifier cette
algorithme dans ces lignes 7 et 8,

75
00:03:45,520 --> 00:03:49,860
et 10 et 11 à juste dire cela,
que je vous ai présenté ici en jaune.

76
00:03:49,860 --> 00:03:52,210
En d'autres termes, si Mike
Smith est tôt dans le livre,

77
00:03:52,210 --> 00:03:55,004
nous ne devons spécifier étape
par étape, maintenant comment aller le trouver.

78
00:03:55,004 --> 00:03:56,920
Nous ne disposons pas de spécifier
pour revenir à la ligne 3,

79
00:03:56,920 --> 00:03:58,960
Pourquoi ne pas tout simplement à la place,
par exemple, plus généralement,

80
00:03:58,960 --> 00:04:01,500
rechercher Mike dans le
la moitié gauche de l'ouvrage.

81
00:04:01,500 --> 00:04:03,960
>> Inversement, si Mike est
effectivement plus tard dans le livre,

82
00:04:03,960 --> 00:04:07,540
pourquoi ne nous citons pas seulement la recherche unquote
pour Mike dans la bonne moitié du livre.

83
00:04:07,540 --> 00:04:11,030
En d'autres termes, pourquoi le faisons-nous pas simplement
sorte de botté de dégagement de nous dire,

84
00:04:11,030 --> 00:04:13,130
rechercher Mike dans ce
sous-ensemble de l'ouvrage,

85
00:04:13,130 --> 00:04:16,279
et de laisser à nos clients existants
algorithme pour nous dire

86
00:04:16,279 --> 00:04:18,750
comment chercher Mike dans
que la moitié gauche de l'ouvrage.

87
00:04:18,750 --> 00:04:20,750
En d'autres termes, notre
algorithme fonctionne si elle est

88
00:04:20,750 --> 00:04:24,670
un annuaire téléphonique de cette épaisseur, de ce
épaisseur, ou de toute épaisseur que ce soit.

89
00:04:24,670 --> 00:04:27,826
Donc, nous pouvons de manière récursive
définir cet algorithme.

90
00:04:27,826 --> 00:04:29,950
En d'autres termes, sur la
écran ici, est un algorithme

91
00:04:29,950 --> 00:04:33,130
pour la recherche de Mike Smith
parmi les pages d'un livre de téléphone.

92
00:04:33,130 --> 00:04:37,410
Donc, à la ligne 7 et 10, nous allons
juste dire exactement cela.

93
00:04:37,410 --> 00:04:40,250
Et je utiliser ce terme un moment
Il ya, en fait, la récursivité

94
00:04:40,250 --> 00:04:42,450
est le mot d'ordre pour l'instant,
et il est de ce processus

95
00:04:42,450 --> 00:04:47,210
de faire quelque chose d'une certaine manière cyclique par
en utilisant le code que vous avez déjà,

96
00:04:47,210 --> 00:04:49,722
et de l'appeler à nouveau,
et de nouveau, et de nouveau.

97
00:04:49,722 --> 00:04:51,930
Maintenant, il va être importante
de toute façon que l'on fond

98
00:04:51,930 --> 00:04:53,821
dehors, et ne faites pas cela infiniment long.

99
00:04:53,821 --> 00:04:56,070
Sinon, nous allons
ont en effet une boucle infinie.

100
00:04:56,070 --> 00:04:59,810
Mais nous allons voir si nous pouvons emprunter cette idée
d'une récursion, faire quelque chose de nouveau

101
00:04:59,810 --> 00:05:03,600
et encore et encore, pour résoudre
le problème de tri par fusion

102
00:05:03,600 --> 00:05:05,900
Trier, d'autant plus efficacement.

103
00:05:05,900 --> 00:05:06,970
>> Donc, je vous donne le tri par fusion.

104
00:05:06,970 --> 00:05:07,920
Nous allons jeter un coup d'oeil.

105
00:05:07,920 --> 00:05:10,850
Voici donc pseudo, avec
que nous pourrions mettre en œuvre le tri,

106
00:05:10,850 --> 00:05:12,640
en utilisant cet algorithme appelé tri par fusion.

107
00:05:12,640 --> 00:05:13,880
Et il est tout simplement cela.

108
00:05:13,880 --> 00:05:15,940
En entrée de n éléments,
en d'autres termes, si vous êtes

109
00:05:15,940 --> 00:05:18,830
n donné des éléments et des chiffres et
lettres ou ce que l'entrée est,

110
00:05:18,830 --> 00:05:22,430
si vous êtes donné n éléments, le cas
n est inférieur à 2, il suffit de revenir.

111
00:05:22,430 --> 00:05:22,930
Droit?

112
00:05:22,930 --> 00:05:26,430
En effet, si n est inférieur à 2, qui
signifie que ma liste d'éléments

113
00:05:26,430 --> 00:05:30,446
est soit de taille 0 ou 1, et
dans ces deux cas triviaux,

114
00:05:30,446 --> 00:05:31,570
la liste est déjà trié.

115
00:05:31,570 --> 00:05:32,810
Si il n'y a pas de liste, elle est triée.

116
00:05:32,810 --> 00:05:35,185
Et si il ya une liste de longueur
1, il est évidemment triés.

117
00:05:35,185 --> 00:05:38,280
Donc, l'algorithme doit seulement
vraiment faire quelque chose d'intéressant,

118
00:05:38,280 --> 00:05:40,870
si nous avons deux ou plus
éléments donnés pour nous.

119
00:05:40,870 --> 00:05:42,440
Alors regardons la magie alors.

120
00:05:42,440 --> 00:05:47,500
Else trier la moitié gauche des éléments,
ensuite trier la moitié droite d'éléments,

121
00:05:47,500 --> 00:05:49,640
puis fusionner les moitiés triés.

122
00:05:49,640 --> 00:05:52,440
Et ce qui est un peu l'esprit de flexion
ici, est que je ne pas vraiment

123
00:05:52,440 --> 00:05:56,190
semblent vous avoir dit
rien pour l'instant, pas vrai?

124
00:05:56,190 --> 00:05:59,560
Tout ce que je l'ai dit est, donné une liste de
n éléments, trier la moitié gauche,

125
00:05:59,560 --> 00:06:01,800
puis la moitié droite, puis
fusionner les moitiés triés,

126
00:06:01,800 --> 00:06:03,840
mais où est la sauce secrète réelle?

127
00:06:03,840 --> 00:06:05,260
Où est l'algorithme?

128
00:06:05,260 --> 00:06:09,150
Bien il se trouve que ces deux lignes
d'abord, la moitié gauche de tri des éléments,

129
00:06:09,150 --> 00:06:13,970
et trier moitié droite d'éléments,
sont des appels récursifs, pour ainsi dire.

130
00:06:13,970 --> 00:06:16,120
>> Après tout, à ce
point dans le temps, je dois

131
00:06:16,120 --> 00:06:18,950
un algorithme avec lequel
trier tout un tas d'éléments?

132
00:06:18,950 --> 00:06:19,450
Oui.

133
00:06:19,450 --> 00:06:20,620
Il est juste ici.

134
00:06:20,620 --> 00:06:25,180
Il est ici à l'écran, et
si je peux utiliser ce même ensemble d'étapes

135
00:06:25,180 --> 00:06:28,500
pour trier la moitié gauche,
que je peux la moitié droite.

136
00:06:28,500 --> 00:06:30,420
Et en effet, encore, et encore.

137
00:06:30,420 --> 00:06:34,210
Donc, d'une certaine manière ou d'une autre, et nous allons bientôt
voir cela, la magie de tri par fusion

138
00:06:34,210 --> 00:06:37,967
est intégré dans ce très finale
ligne, fusionnant les moitiés triés.

139
00:06:37,967 --> 00:06:39,300
Et cela semble assez intuitif.

140
00:06:39,300 --> 00:06:41,050
Vous prenez deux moitiés, et vous,
en quelque sorte, les fusionner,

141
00:06:41,050 --> 00:06:43,260
et nous verrons ce
concrètement dans un instant.

142
00:06:43,260 --> 00:06:45,080
>> Mais ceci est un algorithme complet.

143
00:06:45,080 --> 00:06:46,640
Et nous allons voir exactement pourquoi.

144
00:06:46,640 --> 00:06:50,912
Eh bien supposons que nous sommes donné ces mêmes
huit éléments ici sur l'écran, un

145
00:06:50,912 --> 00:06:53,120
à huit, mais ils sont
afin apparemment aléatoire.

146
00:06:53,120 --> 00:06:55,320
Et l'objectif est à portée de main
pour trier ces éléments.

147
00:06:55,320 --> 00:06:58,280
Eh bien comment puis-je aller sur
le faire en utilisant, à nouveau,

148
00:06:58,280 --> 00:07:00,407
tri par fusion, selon ce pseudo?

149
00:07:00,407 --> 00:07:02,740
Et encore, ce ancrer dans
votre esprit, pour un instant.

150
00:07:02,740 --> 00:07:05,270
Le premier cas est assez
triviale, si elle est inférieure à 2,

151
00:07:05,270 --> 00:07:07,060
juste retour, il n'y a pas de travail à faire.

152
00:07:07,060 --> 00:07:09,290
Alors, vraiment, il ya juste trois
des mesures pour vraiment garder à l'esprit.

153
00:07:09,290 --> 00:07:11,081
Encore une fois, et encore, je suis
allez vouloir d'avoir

154
00:07:11,081 --> 00:07:13,980
pour trier la moitié gauche,
trier la moitié droite,

155
00:07:13,980 --> 00:07:15,890
puis une fois que leur
deux moitiés sont triées,

156
00:07:15,890 --> 00:07:18,710
Je tiens à les fusionner
en une liste triée.

157
00:07:18,710 --> 00:07:19,940
Alors garde cela en tête.

158
00:07:19,940 --> 00:07:21,310
>> Alors, voici la liste originale.

159
00:07:21,310 --> 00:07:23,510
Traitons cela comme une
tableau, comme nous avons commencé à

160
00:07:23,510 --> 00:07:25,800
la deuxième semaine, ce qui est une
bloc contigu de mémoire.

161
00:07:25,800 --> 00:07:28,480
Dans ce cas, contenant huit
numéros, dos à dos à dos.

162
00:07:28,480 --> 00:07:30,700
Et maintenant, nous allons appliquer le tri par fusion.

163
00:07:30,700 --> 00:07:33,300
Donc, je tiens d'abord à trier
la moitié gauche de cette liste,

164
00:07:33,300 --> 00:07:37,370
et nous allons, par conséquent,
concentrer le 4, 8, 6, et 2.

165
00:07:37,370 --> 00:07:41,000
>> Maintenant, comment puis-je faire
le tri d'une liste de taille 4?

166
00:07:41,000 --> 00:07:45,990
Eh bien, je dois tenir compte maintenant
tri de la gauche de la moitié gauche.

167
00:07:45,990 --> 00:07:47,720
Encore une fois, nous allons rembobiner pour un instant.

168
00:07:47,720 --> 00:07:51,010
Si le pseudo-code est présent,
et je me donne huit éléments,

169
00:07:51,010 --> 00:07:53,230
8 est évidemment plus grande
supérieur ou égal à 2.

170
00:07:53,230 --> 00:07:54,980
Donc, avec le premier cas ne concerne pas.

171
00:07:54,980 --> 00:07:58,120
Donc, pour trier huit éléments, je premier
trier la moitié gauche d'éléments,

172
00:07:58,120 --> 00:08:01,930
puis-je trier la moitié droite, puis je fusionne
les deux moitiés, chacune triées de taille quatre.

173
00:08:01,930 --> 00:08:02,470
D'ACCORD.

174
00:08:02,470 --> 00:08:07,480
>> Mais si vous venez de me dire, trier la
la moitié gauche, qui est maintenant de la taille 4,

175
00:08:07,480 --> 00:08:09,350
comment puis-je trier la moitié gauche?

176
00:08:09,350 --> 00:08:11,430
Eh bien, si je dois un
quatre éléments de saisie,

177
00:08:11,430 --> 00:08:14,590
Je trie d'abord la gauche
deux, puis le droit à deux,

178
00:08:14,590 --> 00:08:16,210
et puis je les fusionner.

179
00:08:16,210 --> 00:08:18,700
Encore une fois, ça devient un peu
d'un esprit de flexion jeu ici,

180
00:08:18,700 --> 00:08:21,450
parce que vous, en quelque sorte, doivent
rappelez-vous où vous êtes dans l'histoire,

181
00:08:21,450 --> 00:08:23,620
mais à la fin de la journée,
étant donné un certain nombre d'éléments,

182
00:08:23,620 --> 00:08:25,620
vous voulez d'abord pour trier la
la moitié gauche, puis la moitié droite,

183
00:08:25,620 --> 00:08:26,661
puis de les fusionner.

184
00:08:26,661 --> 00:08:28,630
Commençons à faire exactement cela.

185
00:08:28,630 --> 00:08:30,170
Voici l'entrée de huit éléments.

186
00:08:30,170 --> 00:08:31,910
Maintenant, nous sommes à la recherche à la moitié gauche ici.

187
00:08:31,910 --> 00:08:33,720
Comment puis-je trier quatre éléments?

188
00:08:33,720 --> 00:08:35,610
Eh bien, je trie première la moitié gauche.

189
00:08:35,610 --> 00:08:37,720
Maintenant, comment puis-je trier la moitié gauche?

190
00:08:37,720 --> 00:08:39,419
Eh bien, je l'ai été donné deux éléments.

191
00:08:39,419 --> 00:08:41,240
Donc, nous allons trier ces deux éléments.

192
00:08:41,240 --> 00:08:44,540
La figure 2 est supérieur ou
égal à 2, bien sûr.

193
00:08:44,540 --> 00:08:46,170
Alors que le premier cas ne concerne pas.

194
00:08:46,170 --> 00:08:49,010
>> Donc, je dois maintenant trier la gauche
la moitié de ces deux éléments.

195
00:08:49,010 --> 00:08:50,870
La moitié gauche, bien sûr, est à seulement 4.

196
00:08:50,870 --> 00:08:54,020
Alors, comment puis-je trier une liste d'un élément?

197
00:08:54,020 --> 00:08:57,960
Eh bien maintenant, ce cas de base spéciale
en haut, pour ainsi dire, applique.

198
00:08:57,960 --> 00:09:01,470
1 est inférieur à 2, et ma
la liste est en effet de taille 1.

199
00:09:01,470 --> 00:09:02,747
Je viens donc de retour.

200
00:09:02,747 --> 00:09:03,580
Je ne fais rien.

201
00:09:03,580 --> 00:09:06,770
Et en effet, regarder ce que je l'ai
fait, 4 est déjà trié.

202
00:09:06,770 --> 00:09:09,220
Comme je suis déjà
partiellement réussi ici.

203
00:09:09,220 --> 00:09:11,750
>> Maintenant que semble un peu stupide
la revendication, mais il est vrai.

204
00:09:11,750 --> 00:09:13,700
4 est une liste de taille 1.

205
00:09:13,700 --> 00:09:15,090
Il est déjà triée.

206
00:09:15,090 --> 00:09:16,270
Voilà la moitié gauche.

207
00:09:16,270 --> 00:09:18,010
Maintenant, je trier la moitié droite.

208
00:09:18,010 --> 00:09:22,310
Mon entrée est un élément, 8
de même, déjà triés.

209
00:09:22,310 --> 00:09:25,170
Stupide, trop, mais encore une fois,
ce principe de base

210
00:09:25,170 --> 00:09:28,310
va nous permettre maintenant de construire
en haut de cette succès.

211
00:09:28,310 --> 00:09:32,260
4 triés, 8 sont triés, maintenant
quelle était cette dernière étape?

212
00:09:32,260 --> 00:09:35,330
Donc, la troisième et dernière étape, toute
fois que vous êtes le tri d'une liste, le rappel,

213
00:09:35,330 --> 00:09:38,310
était de fusionner les deux moitiés,
la gauche et la droite.

214
00:09:38,310 --> 00:09:39,900
Donc, nous allons faire exactement cela.

215
00:09:39,900 --> 00:09:41,940
Ma moitié gauche est, bien sûr, 4.

216
00:09:41,940 --> 00:09:43,310
Ma moitié droite est 8.

217
00:09:43,310 --> 00:09:44,100
>> Donc, nous allons le faire.

218
00:09:44,100 --> 00:09:46,410
Je vais d'abord à allouer
de la mémoire supplémentaire,

219
00:09:46,410 --> 00:09:48,680
que je vais représente ici,
comme un tableau secondaire,

220
00:09:48,680 --> 00:09:49,660
qui est assez grand pour tenir cette.

221
00:09:49,660 --> 00:09:52,243
Mais vous pouvez imaginer d'étendre
ce rectangle, la totalité de la longueur,

222
00:09:52,243 --> 00:09:53,290
si nous avons besoin plus tard.

223
00:09:53,290 --> 00:09:58,440
Comment dois-je prendre 4 et 8, et de fusionner
ces deux listes de taille 1 ensemble?

224
00:09:58,440 --> 00:10:00,270
Ici aussi, assez simple.

225
00:10:00,270 --> 00:10:03,300
4 vient en premier, puis vient 8.

226
00:10:03,300 --> 00:10:07,130
Parce que si je veux trier la
la moitié gauche, puis la moitié droite,

227
00:10:07,130 --> 00:10:09,900
puis fusionner ces deux moitiés
ensemble, dans l'ordre de tri,

228
00:10:09,900 --> 00:10:11,940
4 vient en premier, puis vient 8.

229
00:10:11,940 --> 00:10:15,810
>> Donc, nous semblons faire des progrès, même
si je ne l'ai pas fait tout le travail réel.

230
00:10:15,810 --> 00:10:17,800
Mais rappelez-vous où nous sommes dans l'histoire.

231
00:10:17,800 --> 00:10:19,360
Nous avons pris l'origine huit éléments.

232
00:10:19,360 --> 00:10:21,480
Nous avons réglé la moitié gauche, qui est de 4.

233
00:10:21,480 --> 00:10:24,450
Ensuite, nous avons trié la moitié gauche
de la moitié gauche, ce qui est deux.

234
00:10:24,450 --> 00:10:25,270
Et c'est reparti.

235
00:10:25,270 --> 00:10:26,920
Nous en avons terminé avec cette étape.

236
00:10:26,920 --> 00:10:29,930
>> Donc, si nous avons trié les
la moitié des 2 partis, maintenant nous

237
00:10:29,930 --> 00:10:32,130
avoir pour trier la moitié droite de 2.

238
00:10:32,130 --> 00:10:35,710
Donc, la moitié droite de 2 est
ces deux valeurs, ici, six et deux.

239
00:10:35,710 --> 00:10:40,620
Alors prenons maintenant une entrée de la taille
2, et de trier la moitié gauche, puis

240
00:10:40,620 --> 00:10:42,610
la moitié droite, puis
les fusionner.

241
00:10:42,610 --> 00:10:45,722
Eh bien, comment puis-je trier une liste de taille
1, contenant juste le numéro 6?

242
00:10:45,722 --> 00:10:46,430
Je suis déjà fait.

243
00:10:46,430 --> 00:10:48,680
Cette liste de taille 1 est triée.

244
00:10:48,680 --> 00:10:52,140
>> Comment puis-je trier une autre liste de
taille 1, la demi prétendu droit.

245
00:10:52,140 --> 00:10:54,690
Eh bien, elle aussi, est déjà trié.

246
00:10:54,690 --> 00:10:56,190
Le numéro 2 est seul.

247
00:10:56,190 --> 00:11:00,160
Alors maintenant, je dois deux moitiés, gauche et
Bon, je dois les fusionner.

248
00:11:00,160 --> 00:11:01,800
Permettez-moi de me donner un peu d'espace supplémentaire.

249
00:11:01,800 --> 00:11:05,580
Et de mettre 2 là,
puis 6 là, ainsi

250
00:11:05,580 --> 00:11:10,740
trier cette liste, gauche et droite,
et la fusion ensemble, en fin de compte.

251
00:11:10,740 --> 00:11:12,160
Donc, je suis légèrement meilleure forme.

252
00:11:12,160 --> 00:11:16,250
Je ne suis pas fait, parce que clairement 4, 8, 2,
6 est pas la dernière commande que je veux.

253
00:11:16,250 --> 00:11:20,640
Mais je dois maintenant deux listes de taille 2, que
ont tous deux, respectivement, été triés.

254
00:11:20,640 --> 00:11:24,580
Alors maintenant, si vous rembobinez dans votre esprit de
oeil, où n'a que de nous laisser?

255
00:11:24,580 --> 00:11:28,520
Je ai commencé avec huit éléments, alors je
taillé vers le bas de la moitié gauche de quatre,

256
00:11:28,520 --> 00:11:31,386
puis la moitié gauche de deux, et
puis la moitié droite de 2,

257
00:11:31,386 --> 00:11:34,510
Je finis donc, le tri de la gauche
la moitié des 2 et la moitié droite de 2,

258
00:11:34,510 --> 00:11:37,800
alors quelle est la troisième et dernière étape ici?

259
00:11:37,800 --> 00:11:41,290
Je dois fusionner
deux listes de taille 2.

260
00:11:41,290 --> 00:11:42,040
Donc, nous allons aller de l'avant.

261
00:11:42,040 --> 00:11:43,940
Et sur l'écran ici, donner
moi un peu de mémoire supplémentaire,

262
00:11:43,940 --> 00:11:47,170
si, techniquement, remarque que je l'ai
eu tout un tas d'espace en haut sommet vierge

263
00:11:47,170 --> 00:11:47,670
Là.

264
00:11:47,670 --> 00:11:50,044
Si je veux être particulièrement
efficace de l'espace sage,

265
00:11:50,044 --> 00:11:52,960
Je ne pouvais tout simplement commencer à déplacer les éléments
avant et en arrière, haut et bas.

266
00:11:52,960 --> 00:11:55,460
Mais juste pour la clarté visuelle,
Je vais le mettre en bas,

267
00:11:55,460 --> 00:11:56,800
de garder les choses belle et propre.

268
00:11:56,800 --> 00:11:58,150
>> Donc, je dois deux listes de taille 2.

269
00:11:58,150 --> 00:11:59,770
La première liste a 4 et 8.

270
00:11:59,770 --> 00:12:01,500
La deuxième liste a 2 et 6.

271
00:12:01,500 --> 00:12:03,950
Disons fusionner ces
ensemble dans l'ordre.

272
00:12:03,950 --> 00:12:09,910
2, bien sûr, vient en premier,
puis 4, puis 6, puis 8.

273
00:12:09,910 --> 00:12:12,560
Et maintenant, nous semblons
un endroit intéressant.

274
00:12:12,560 --> 00:12:15,720
Maintenant, je suis la moitié de l'trié
liste, et comme par hasard, il est

275
00:12:15,720 --> 00:12:18,650
tous les nombres pairs, mais que
est, en effet, juste une coïncidence.

276
00:12:18,650 --> 00:12:22,220
Et maintenant je l'ai trié la gauche
moitié, de sorte qu'il est 2, 4, 6 et 8.

277
00:12:22,220 --> 00:12:23,430
Rien est irrecevable.

278
00:12:23,430 --> 00:12:24,620
Qui se sent comme progrès.

279
00:12:24,620 --> 00:12:26,650
>> Maintenant, il se sent comme je l'ai
été de parler toujours maintenant,

280
00:12:26,650 --> 00:12:29,850
donc ce qui reste à voir si cette
algorithme est, en effet, plus efficace.

281
00:12:29,850 --> 00:12:31,766
Mais nous allons à travers
it Super méthodiquement.

282
00:12:31,766 --> 00:12:34,060
Un ordinateur, bien sûr,
serait faire comme ça.

283
00:12:34,060 --> 00:12:34,840
Alors, où en sommes-nous?

284
00:12:34,840 --> 00:12:36,180
Nous avons commencé avec huit éléments.

285
00:12:36,180 --> 00:12:37,840
Je trié la moitié gauche de 4.

286
00:12:37,840 --> 00:12:39,290
Je semble être fait avec cela.

287
00:12:39,290 --> 00:12:42,535
Alors maintenant, la prochaine étape est de
trier la moitié droite de 4.

288
00:12:42,535 --> 00:12:44,410
Et cette partie nous pouvons aller
grâce à un peu plus

289
00:12:44,410 --> 00:12:47,140
rapidement, même si vous êtes
Bienvenue pour rembobiner ou faire une pause, juste

290
00:12:47,140 --> 00:12:49,910
penser par elle au
votre propre rythme, mais ce

291
00:12:49,910 --> 00:12:53,290
nous avons maintenant l'occasion de
faire la même algorithme exact sur quatre

292
00:12:53,290 --> 00:12:54,380
des nombres différents.

293
00:12:54,380 --> 00:12:57,740
>> Donc, nous allons aller de l'avant, et se concentrer sur
la moitié droite, que nous sommes ici.

294
00:12:57,740 --> 00:13:01,260
La moitié gauche de cette
la moitié droite, et maintenant le

295
00:13:01,260 --> 00:13:04,560
la moitié gauche de la gauche
la moitié de cette moitié droite,

296
00:13:04,560 --> 00:13:08,030
et comment puis-je trier une liste de taille
1 contenant juste le numéro 1?

297
00:13:08,030 --> 00:13:09,030
C'est déjà fait.

298
00:13:09,030 --> 00:13:11,830
Comment dois-je faire la même chose pour une liste
de taille 1 contenant seulement 7?

299
00:13:11,830 --> 00:13:12,840
C'est déjà fait.

300
00:13:12,840 --> 00:13:16,790
Étape trois pour cette demi puis
est de fusionner ces deux éléments

301
00:13:16,790 --> 00:13:20,889
dans une nouvelle liste de taille 2, 1 et 7.

302
00:13:20,889 --> 00:13:23,180
Ne semble pas avoir fait tout
que beaucoup de travail intéressant.

303
00:13:23,180 --> 00:13:24,346
Voyons ce qui arrive ensuite.

304
00:13:24,346 --> 00:13:29,210
Je viens trié la moitié gauche de la
la moitié droite de mon entrée d'origine.

305
00:13:29,210 --> 00:13:32,360
Maintenant, nous allons trier le droit
moitié, qui contient 5 et 3.

306
00:13:32,360 --> 00:13:35,740
Voyons à nouveau regarder à gauche
la moitié, triés, la moitié droite, triés,

307
00:13:35,740 --> 00:13:39,120
et de fusionner les deux ensemble,
dans un peu d'espace supplémentaire,

308
00:13:39,120 --> 00:13:41,670
3 vient en premier, puis vient 5.

309
00:13:41,670 --> 00:13:46,190
Et maintenant, nous avons trié les
la moitié gauche de la moitié droite

310
00:13:46,190 --> 00:13:49,420
du problème d'origine, et
la moitié droite de la moitié droite

311
00:13:49,420 --> 00:13:50,800
du problème original.

312
00:13:50,800 --> 00:13:52,480
Quelle est la troisième et dernière étape?

313
00:13:52,480 --> 00:13:54,854
Eh bien, pour fusionner ces deux moitiés ensemble.

314
00:13:54,854 --> 00:13:57,020
Alors permettez-moi de me mettre un peu
espace supplémentaire, mais, encore une fois, je

315
00:13:57,020 --> 00:13:58,699
pourrait être l'aide de cet espace en haut sommet de rechange.

316
00:13:58,699 --> 00:14:00,490
Mais nous allons continuer
simple visuellement.

317
00:14:00,490 --> 00:14:07,070
Permettez-moi de fusion dans l'entreprise 1, et
puis 3, puis 5, puis 7.

318
00:14:07,070 --> 00:14:10,740
Ainsi me laissant maintenant avec le
moitié droite du problème original

319
00:14:10,740 --> 00:14:12,840
qui est parfaitement triés.

320
00:14:12,840 --> 00:14:13,662
>> Donc ce qui reste?

321
00:14:13,662 --> 00:14:16,120
Je me sens comme je ne cesse de dire le
mêmes choses encore et encore,

322
00:14:16,120 --> 00:14:18,700
mais qui est le reflet de la
fait que nous utilisons la récursion.

323
00:14:18,700 --> 00:14:21,050
Le processus de l'aide d'un
algorithme encore, et encore,

324
00:14:21,050 --> 00:14:23,940
sur de plus petits sous-ensembles de
le problème d'origine.

325
00:14:23,940 --> 00:14:27,580
Donc, je l'ai maintenant une gauche trié
la moitié du problème d'origine.

326
00:14:27,580 --> 00:14:30,847
Je dois une demi triée droit
du problème original.

327
00:14:30,847 --> 00:14:32,180
Quelle est la troisième et dernière étape?

328
00:14:32,180 --> 00:14:33,590
Oh, il est la fusion.

329
00:14:33,590 --> 00:14:34,480
Donc, nous allons le faire.

330
00:14:34,480 --> 00:14:36,420
Disons allouer une partie supplémentaire
mémoire, mais mon dieu, nous

331
00:14:36,420 --> 00:14:37,503
pourrait mettre partout maintenant.

332
00:14:37,503 --> 00:14:40,356
Nous avons tellement d'espace disponible
pour nous, mais nous allons garder les choses simples.

333
00:14:40,356 --> 00:14:42,730
Au lieu d'aller en arrière et
-vient avec la mémoire originale,

334
00:14:42,730 --> 00:14:44,480
disons simplement faire
visuellement ici-bas,

335
00:14:44,480 --> 00:14:47,240
pour finir la fusion de la
la moitié gauche et la moitié droite.

336
00:14:47,240 --> 00:14:49,279
>> Donc, en fusionnant, que dois-je faire?

337
00:14:49,279 --> 00:14:50,820
Je veux prendre les éléments dans l'ordre.

338
00:14:50,820 --> 00:14:53,230
Donc, en regardant la moitié gauche,
Je vois le premier numéro est de 2.

339
00:14:53,230 --> 00:14:55,230
Je regarde la moitié droite,
Je vois le premier numéro

340
00:14:55,230 --> 00:14:58,290
est 1, donc évidemment, qui
numéro dois-je tiens à arracher,

341
00:14:58,290 --> 00:15:00,430
et de mettre en premier dans ma liste finale?

342
00:15:00,430 --> 00:15:01,449
Bien sûr, 1.

343
00:15:01,449 --> 00:15:02,990
Maintenant, je veux poser la même question.

344
00:15:02,990 --> 00:15:05,040
Sur la moitié gauche, je l'ai
encore obtenu le numéro 2.

345
00:15:05,040 --> 00:15:07,490
Sur la moitié droite,
Je dois le numéro 3.

346
00:15:07,490 --> 00:15:08,930
Lequel veux-je choisir?

347
00:15:08,930 --> 00:15:11,760
Bien sûr, le numéro 2 et
Remarquez maintenant les candidats

348
00:15:11,760 --> 00:15:13,620
4 sont à gauche, 3 à droite.

349
00:15:13,620 --> 00:15:15,020
Allons, bien sûr, choisir 3.

350
00:15:15,020 --> 00:15:18,020
Les candidats sont désormais sur 4
la gauche, 5 à droite.

351
00:15:18,020 --> 00:15:19,460
Nous, bien sûr, choisir 4.

352
00:15:19,460 --> 00:15:21,240
6 sur la gauche, 5 à droite.

353
00:15:21,240 --> 00:15:22,730
Nous, bien sûr, choisir 5.

354
00:15:22,730 --> 00:15:25,020
6 sur la gauche, sur la droite 7.

355
00:15:25,020 --> 00:15:29,320
Nous choisissons 6, puis nous
choisissez 7, puis nous choisissons 8.

356
00:15:29,320 --> 00:15:30,100
Voila.

357
00:15:30,100 --> 00:15:34,370
>> Donc, un grand nombre de mots plus tard, nous
ont trié cette liste de huit éléments

358
00:15:34,370 --> 00:15:38,450
dans une liste de un à huit,
que ça augmente avec chaque étape,

359
00:15:38,450 --> 00:15:40,850
mais combien de temps fait
il nous a fallu pour le faire.

360
00:15:40,850 --> 00:15:43,190
Eh bien, je l'ai délibérément
choses énoncées imagée

361
00:15:43,190 --> 00:15:46,330
ici, afin que nous puissions type de
voir ou apprécier la division

362
00:15:46,330 --> 00:15:49,060
dans la conquête de ce qui a été le cas.

363
00:15:49,060 --> 00:15:52,830
>> En effet, si vous regardez en arrière à la veillée,
Je l'ai laissé tous ces pointillés

364
00:15:52,830 --> 00:15:55,660
en place des titulaires, vous pouvez,
sorte de, voir, dans l'ordre inverse,

365
00:15:55,660 --> 00:15:58,800
si vous regardez en arrière de type dans
l'histoire maintenant, ma liste originale

366
00:15:58,800 --> 00:16:00,250
est, bien sûr, de la taille 8.

367
00:16:00,250 --> 00:16:03,480
Et puis, précédemment, je étais
traiter avec deux listes de taille 4,

368
00:16:03,480 --> 00:16:08,400
puis quatre listes de taille 2,
puis huit listes de taille 1.

369
00:16:08,400 --> 00:16:10,151
>> Alors qu'est-ce,
en quelque sorte, de vous rappeler?

370
00:16:10,151 --> 00:16:11,858
Eh bien, en effet, l'une des
les algorithmes que nous avons

371
00:16:11,858 --> 00:16:14,430
regardé jusqu'ici où nous
fracture, et diviser, et diviser,

372
00:16:14,430 --> 00:16:19,500
garder d'avoir des choses à nouveau, et
encore, les résultats de cette idée générale.

373
00:16:19,500 --> 00:16:23,100
Et donc il ya quelque chose
logarithmique passe ici.

374
00:16:23,100 --> 00:16:26,790
Et il est pas tout à fait du journal n, mais
il ya un élément logarithmique

375
00:16:26,790 --> 00:16:28,280
à ce que nous venons de faire.

376
00:16:28,280 --> 00:16:31,570
>> Voyons maintenant comment cela est fait.

377
00:16:31,570 --> 00:16:34,481
Alors connectez-de n, était à nouveau
un grand temps de fonctionnement,

378
00:16:34,481 --> 00:16:36,980
quand nous avons fait quelque chose comme
recherche binaire, comme nous l'appelons maintenant,

379
00:16:36,980 --> 00:16:40,090
la stratégie de diviser pour mieux régner
par l'intermédiaire duquel nous avons trouvé Mike Smith.

380
00:16:40,090 --> 00:16:41,020
Maintenant, techniquement.

381
00:16:41,020 --> 00:16:43,640
Voilà journal de base 2 n, même
si dans la plupart des classes de mathématiques,

382
00:16:43,640 --> 00:16:45,770
10 est généralement la base que vous assumez.

383
00:16:45,770 --> 00:16:48,940
Mais les scientifiques informatiques presque toujours
penser et à parler en termes de base 2,

384
00:16:48,940 --> 00:16:52,569
donc nous disons généralement juste de journal
n, au lieu de log base 2 de n,

385
00:16:52,569 --> 00:16:55,110
mais ils sont exactement une seule et
même dans le monde de l'informatique

386
00:16:55,110 --> 00:16:57,234
la science, et en passant,
il ya un facteur constant

387
00:16:57,234 --> 00:17:01,070
différence entre les deux, il est donc
moot de toute façon, pour des raisons plus formelles.

388
00:17:01,070 --> 00:17:04,520
>> Mais pour l'instant, ce que nous nous soucions
à propos de cet exemple est.

389
00:17:04,520 --> 00:17:08,520
Donc, il ne faut pas prouver par exemple, mais à
utiliser moins un exemple des numéros

390
00:17:08,520 --> 00:17:10,730
à portée de main comme un test de cohérence, si vous voulez.

391
00:17:10,730 --> 00:17:14,510
Donc, la formule était précédemment base de journal
2 n, mais ce qui est n dans ce cas.

392
00:17:14,510 --> 00:17:18,526
Je devais nombres n originales, ou 8
du nombre initial spécifiquement.

393
00:17:18,526 --> 00:17:20,359
Maintenant, cela fait un peu
tout, mais je suis assez

394
00:17:20,359 --> 00:17:25,300
assurer que log base 2
la valeur de 8 est 3,

395
00:17:25,300 --> 00:17:29,630
et en effet, ce qui est agréable à ce sujet est
3 qui est exactement le nombre de fois

396
00:17:29,630 --> 00:17:33,320
que vous pouvez diviser une liste
de longueur 8, encore et encore,

397
00:17:33,320 --> 00:17:36,160
et encore, jusqu'à ce que vous êtes de gauche
avec des listes de juste taille 1.

398
00:17:36,160 --> 00:17:36,660
Droit?

399
00:17:36,660 --> 00:17:40,790
8 va à 4, va à 2,
passe à 1, et que ce

400
00:17:40,790 --> 00:17:43,470
reflète exactement ce que
image que nous avions il ya un instant.

401
00:17:43,470 --> 00:17:47,160
Donc un peu de raison de vérifier l'endroit où
le logarithme est en réalité impliqué.

402
00:17:47,160 --> 00:17:50,180
>> Alors maintenant, quoi d'autre est impliqué ici? n.

403
00:17:50,180 --> 00:17:53,440
Donc remarquerez que tous les
fois que je partagerai la liste,

404
00:17:53,440 --> 00:17:58,260
mais dans l'ordre inverse dans l'histoire
ici, je faisais toujours n choses.

405
00:17:58,260 --> 00:18:02,320
Cette étape de fusion exige que
Je touche chacun des numéros,

406
00:18:02,320 --> 00:18:05,060
afin de glisser dans
son emplacement approprié.

407
00:18:05,060 --> 00:18:10,760
Ainsi, même si la hauteur de cette
schéma est de taille log n de n ou 3,

408
00:18:10,760 --> 00:18:13,860
en particulier, en d'autres termes,
Je l'ai fait trois divisions ici.

409
00:18:13,860 --> 00:18:18,800
Combien de travail ai-je fait horizontalement
le long de ce tableau à chaque fois?

410
00:18:18,800 --> 00:18:21,110
>> Eh bien, je l'ai fait n étapes de
travailler, parce que si je l'ai

411
00:18:21,110 --> 00:18:24,080
obtenu quatre éléments et les quatre éléments,
et je dois les fusionner.

412
00:18:24,080 --> 00:18:26,040
Je dois passer par
ces quatre et ces quatre,

413
00:18:26,040 --> 00:18:28,123
en fin de compte pour les fusionner
Retour en huit éléments.

414
00:18:28,123 --> 00:18:32,182
Si à l'inverse, je dois huit doigts
ici, que je ne le fais pas, et huit

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- Si je l'ai
eu quatre doigts sur ici,

416
00:18:34,390 --> 00:18:37,380
ce que je fais, quatre doigts
ici, ce que je fais,

417
00:18:37,380 --> 00:18:40,590
alors que ce même
par exemple comme avant, si je fais

418
00:18:40,590 --> 00:18:44,010
ont huit doigts si, dans
totale, ce que je peux, en quelque sorte, faire.

419
00:18:44,010 --> 00:18:47,950
Je peux faire exactement ici,
alors je peux certainement

420
00:18:47,950 --> 00:18:50,370
fusionner toutes ces listes
de taille 1 ensemble.

421
00:18:50,370 --> 00:18:54,050
Mais je dois certainement à regarder
à chaque élément exactement une fois.

422
00:18:54,050 --> 00:18:59,640
Ainsi, la hauteur de ce processus est log n,
la largeur de ce processus, pour ainsi dire,

423
00:18:59,640 --> 00:19:02,490
est N, donc ce que nous semblons
d'avoir, en fin de compte, est

424
00:19:02,490 --> 00:19:06,470
un temps de course de taille n log n fois.

425
00:19:06,470 --> 00:19:08,977
>> En d'autres termes, nous avons divisé
la liste, journal n fois,

426
00:19:08,977 --> 00:19:11,810
mais à chaque fois que nous avons fait, nous avons eu
de toucher tous les éléments

427
00:19:11,810 --> 00:19:13,560
afin de les fusionner
tous ensemble, qui

428
00:19:13,560 --> 00:19:18,120
a été n étape, nous avons donc n fois log N,
ou comme un informaticien dirait,

429
00:19:18,120 --> 00:19:20,380
asymptotiquement, qui
serait le grand mot

430
00:19:20,380 --> 00:19:22,810
pour décrire la partie supérieure
lié sur un temps de fonctionnement,

431
00:19:22,810 --> 00:19:28,010
nous courons dans une grande o
de log n fois, pour ainsi dire.

432
00:19:28,010 --> 00:19:31,510
>> Maintenant, cela est significatif, parce
rappellent ce que les durées de fonctionnement étaient

433
00:19:31,510 --> 00:19:34,120
avec tri à bulles, et la sélection
Trier, et le tri par insertion,

434
00:19:34,120 --> 00:19:38,200
et même quelques autres qui existent,
n carré était où nous en étions.

435
00:19:38,200 --> 00:19:39,990
Et vous pouvez, en quelque sorte, le voir ici.

436
00:19:39,990 --> 00:19:45,720
Si n est évidemment carré n fois
n, mais ici nous avons n log n fois,

437
00:19:45,720 --> 00:19:48,770
et nous savons déjà de la semaine
zéro, ce log n, l'logarithmique,

438
00:19:48,770 --> 00:19:50,550
est quelque chose de mieux que linéaire.

439
00:19:50,550 --> 00:19:52,930
Après tout, rappeler l'image
avec le rouge et le jaune

440
00:19:52,930 --> 00:19:56,500
et les lignes vertes que nous Drew,
logarithmique ligne verte était beaucoup plus faible.

441
00:19:56,500 --> 00:20:00,920
Et donc, beaucoup mieux et plus vite
que les lignes jaunes et rouges droites,

442
00:20:00,920 --> 00:20:05,900
n fois log n est, en effet, de mieux
de n fois n, ou n au carré.

443
00:20:05,900 --> 00:20:09,110
>> Donc, nous semblons avoir
identifié une fusion de l'algorithme

444
00:20:09,110 --> 00:20:11,870
genre qui fonctionne dans beaucoup
le temps plus vite, et en effet,

445
00:20:11,870 --> 00:20:16,560
Voilà pourquoi, plus tôt cette semaine, lorsque
nous avons vu ce concours entre les bulles

446
00:20:16,560 --> 00:20:20,750
Trier, tri par sélection, et de fusionner
tri, le tri par fusion vraiment, vraiment gagné.

447
00:20:20,750 --> 00:20:23,660
Et en effet, nous ne l'avons même pas attendre
pour tri à bulles et de sélection Trier

448
00:20:23,660 --> 00:20:24,790
finir.

449
00:20:24,790 --> 00:20:27,410
>> Prenons maintenant un autre passe
à ce, à partir d'un peu plus

450
00:20:27,410 --> 00:20:31,030
point de vue formel, juste au
cas, cela résonne mieux

451
00:20:31,030 --> 00:20:33,380
que la discussion de niveau supérieur.

452
00:20:33,380 --> 00:20:34,880
Alors, voici à nouveau l'algorithme.

453
00:20:34,880 --> 00:20:36,770
Demandons-nous,
ce que le temps d'exécution

454
00:20:36,770 --> 00:20:39,287
est de cette algorithmes différentes étapes?

455
00:20:39,287 --> 00:20:41,620
Divisons dans la première
boîtier et le deuxième cas.

456
00:20:41,620 --> 00:20:46,280
Le SI et de l'autre dans le cas si,
Si n est inférieur à 2, il suffit de retourner.

457
00:20:46,280 --> 00:20:47,580
On se sent comme constante de temps.

458
00:20:47,580 --> 00:20:50,970
Il est, en quelque sorte, comme deux étapes,
Si n est inférieur à 2, puis retour.

459
00:20:50,970 --> 00:20:54,580
Mais comme nous le disions, le lundi,
constante de temps, ou grand o 1,

460
00:20:54,580 --> 00:20:57,130
peut être deux, trois étapes
mesures, voire 1000 étapes.

461
00:20:57,130 --> 00:20:59,870
Ce qui importe est qu'il est
un nombre constant d'étapes.

462
00:20:59,870 --> 00:21:03,240
Donc, la surbrillance jaune pseudo
tourne ici dans, nous l'appellerons,

463
00:21:03,240 --> 00:21:04,490
constante de temps.

464
00:21:04,490 --> 00:21:06,780
Donc, plus formellement, et
nous allons cette to--

465
00:21:06,780 --> 00:21:09,910
sera la mesure dans laquelle on
officialiser ce droit maintenant-- T de n,

466
00:21:09,910 --> 00:21:15,030
le temps d'exécution d'un problème
qui prend n somethings comme entrée,

467
00:21:15,030 --> 00:21:19,150
Big O est égal à un,
Si n est inférieur à 2.

468
00:21:19,150 --> 00:21:20,640
Donc, il est conditionnelle à ce sujet.

469
00:21:20,640 --> 00:21:24,150
Donc, pour être clair, si n est inférieur à
2, nous avons une très courte liste, puis

470
00:21:24,150 --> 00:21:29,151
le temps d'exécution, de T n, où n est égal à
1 ou 0, dans ce cas très précis,

471
00:21:29,151 --> 00:21:30,650
il va juste être constante de temps.

472
00:21:30,650 --> 00:21:32,691
Il va prendre un
l'étape, à deux pas, peu importe.

473
00:21:32,691 --> 00:21:33,950
Il est un nombre fixe d'étapes.

474
00:21:33,950 --> 00:21:38,840
>> Ainsi, la partie juteuse doit sûrement être en
l'autre cas dans le pseudo-code.

475
00:21:38,840 --> 00:21:40,220
Le cas ELSE.

476
00:21:40,220 --> 00:21:44,870
Trier moitié gauche d'éléments, en quelque sorte droit
la moitié des éléments, fusionner moitiés triés.

477
00:21:44,870 --> 00:21:46,800
Combien de temps dure chacune de ces étapes prend-il?

478
00:21:46,800 --> 00:21:49,780
Eh bien, si le fonctionnement
le temps de trier n éléments

479
00:21:49,780 --> 00:21:53,010
est, disons qu'il est très
génériquement, T n,

480
00:21:53,010 --> 00:21:55,500
puis le tri de la gauche
la moitié des éléments

481
00:21:55,500 --> 00:21:59,720
est, en quelque sorte, comme dire,
T de n divisé par deux,

482
00:21:59,720 --> 00:22:03,000
et le tri de même la moitié droite
d'éléments est, en quelque sorte, comme dire,

483
00:22:03,000 --> 00:22:06,974
T n de 2 divisée, et ensuite
la fusion des moitiés triées.

484
00:22:06,974 --> 00:22:08,890
Eh bien, si je dois un peu
nombre d'éléments ici,

485
00:22:08,890 --> 00:22:11,230
comme quatre, et un nombre
d'éléments ici, comme quatre,

486
00:22:11,230 --> 00:22:14,650
et je dois fusionner chacun de ces quatre
dans, et chacun de ces quatre, une

487
00:22:14,650 --> 00:22:17,160
après l'autre, de sorte que
finalement, je dois huit éléments.

488
00:22:17,160 --> 00:22:20,230
Il se sent comme si ce Big O de n étapes?

489
00:22:20,230 --> 00:22:23,500
Si je dois n doigts et chacun des
eux doit être fusionné en place,

490
00:22:23,500 --> 00:22:25,270
qui est comme un autre n étapes.

491
00:22:25,270 --> 00:22:27,360
>> Donc, en effet formulaically,
nous pouvons exprimer cela,

492
00:22:27,360 --> 00:22:29,960
quoique un peu au premier abord effroyablement
coup d'oeil, mais il ya quelque chose

493
00:22:29,960 --> 00:22:31,600
qui capte exactement cette logique.

494
00:22:31,600 --> 00:22:35,710
Le temps d'exécution, de T n, si n
est supérieur ou égal à 2.

495
00:22:35,710 --> 00:22:42,500
Dans ce cas, le cas ELSE, est T de n
divisé par 2, plus T de N divisé par 2,

496
00:22:42,500 --> 00:22:45,320
en plus grande de n o, certains
Numéro linéaire d'étapes,

497
00:22:45,320 --> 00:22:51,630
peut-être exactement n, peut-être 2 fois
n, mais il est à peu près, afin de n.

498
00:22:51,630 --> 00:22:54,060
Alors que, aussi, est de savoir comment nous pouvons
exprimer cette formulaically.

499
00:22:54,060 --> 00:22:56,809
Maintenant, vous ne seriez pas le savoir à moins
vous avez enregistré dans votre esprit,

500
00:22:56,809 --> 00:22:58,710
ou recherchez-le dans le
Retour d'un manuel, qui

501
00:22:58,710 --> 00:23:00,501
pourraient avoir un peu
antisèche à la fin,

502
00:23:00,501 --> 00:23:03,940
mais cela est, en effet, va
nous donner une grande o n log n,

503
00:23:03,940 --> 00:23:06,620
parce que la récurrence
vous voyez ici à l'écran,

504
00:23:06,620 --> 00:23:09,550
si vous avez réellement fait sortir, avec
un nombre infini d'exemples,

505
00:23:09,550 --> 00:23:13,000
ou vous l'avez fait formulaically, vous le feriez
voir que cela, parce que cette formule

506
00:23:13,000 --> 00:23:17,100
lui-même est récursive, avec des t
n sur quelque chose sur la droite,

507
00:23:17,100 --> 00:23:21,680
et t du N de la gauche, cela peut
être effectivement exprimé, en fin de compte,

508
00:23:21,680 --> 00:23:24,339
aussi grand feu de n log n.

509
00:23:24,339 --> 00:23:26,130
Si pas convaincu, que ce
bien pour le moment, juste

510
00:23:26,130 --> 00:23:28,960
prendre sur la foi, qui est que, en effet,
ce qui conduit à récurrence,

511
00:23:28,960 --> 00:23:31,780
mais ceci est juste un peu plus d'un
approche mathématique de la recherche

512
00:23:31,780 --> 00:23:36,520
à la durée de fonctionnement de tri par fusion
sur la base de son seul pseudocode.

513
00:23:36,520 --> 00:23:39,030
>> Prenons maintenant un peu
pause de tout cela,

514
00:23:39,030 --> 00:23:41,710
et jeter un oeil à une
certaine ancien sénateur, qui

515
00:23:41,710 --> 00:23:44,260
pourrait ressembler un peu familier,
qui est assis avec Eric de Google

516
00:23:44,260 --> 00:23:48,410
Schmidt, il ya quelque temps, pour une entrevue
sur scène, en face de tout un tas

517
00:23:48,410 --> 00:23:53,710
de personnes, parler en fin de compte à propos
un sujet, qui est assez maintenant familière.

518
00:23:53,710 --> 00:23:54,575
Nous allons jeter un coup d'oeil.

519
00:23:54,575 --> 00:24:01,020

520
00:24:01,020 --> 00:24:03,890
>> Eric Schmidt: Maintenant, sénateur,
vous êtes ici chez Google,

521
00:24:03,890 --> 00:24:09,490
et je plais à penser de la
présidence comme une entrevue d'emploi.

522
00:24:09,490 --> 00:24:11,712
Maintenant, il est difficile d'obtenir un emploi en tant que président.

523
00:24:11,712 --> 00:24:12,670
PRÉSIDENT OBAMA: Droit.

524
00:24:12,670 --> 00:24:13,940
Eric Schmidt: Et vous êtes
va faire [inaudible] maintenant.

525
00:24:13,940 --> 00:24:15,523
Il est également difficile d'obtenir un emploi chez Google.

526
00:24:15,523 --> 00:24:17,700
PRÉSIDENT OBAMA: Droit.

527
00:24:17,700 --> 00:24:21,330
>> Eric Schmidt: Nous avons des questions,
et nous demandons à nos questions aux candidats,

528
00:24:21,330 --> 00:24:24,310
et celui-ci est de Larry Schwimmer.

529
00:24:24,310 --> 00:24:25,890
>> PRÉSIDENT OBAMA: OK.

530
00:24:25,890 --> 00:24:27,005
>> Eric Schmidt: Qu'est-ce?

531
00:24:27,005 --> 00:24:28,130
Les gars, vous pensez que je plaisante?

532
00:24:28,130 --> 00:24:30,590
Il est juste ici.

533
00:24:30,590 --> 00:24:33,490
Quel est le moyen le plus efficace pour
trier une entiers de 32 millions de bits?

534
00:24:33,490 --> 00:24:37,560

535
00:24:37,560 --> 00:24:38,979
>> PRÉSIDENT OBAMA: Well--

536
00:24:38,979 --> 00:24:41,020
Eric Schmidt: Parfois,
peut-être je suis désolé, maybe--

537
00:24:41,020 --> 00:24:42,750
PRÉSIDENT OBAMA: Non, non,
non, non, non, je think--

538
00:24:42,750 --> 00:24:43,240
Eric Schmidt: Ce ne est pas it--

539
00:24:43,240 --> 00:24:45,430
PRÉSIDENT OBAMA: Je
penser, je pense que la bulle

540
00:24:45,430 --> 00:24:46,875
Trier serait le mauvais chemin à parcourir.

541
00:24:46,875 --> 00:24:49,619

542
00:24:49,619 --> 00:24:50,535
Eric Schmidt: Viens.

543
00:24:50,535 --> 00:24:52,200
Qui lui a dit cela?

544
00:24:52,200 --> 00:24:54,020
D'ACCORD.

545
00:24:54,020 --> 00:24:55,590
Je ne l'ai pas l'informatique on--

546
00:24:55,590 --> 00:24:58,986
>> PRÉSIDENT OBAMA: nous avons
obtenu nos espions là-dedans.

547
00:24:58,986 --> 00:24:59,860
PROFESSEUR: Très bien.

548
00:24:59,860 --> 00:25:03,370
Laissons derrière nous maintenant
monde théorique d'algorithmes

549
00:25:03,370 --> 00:25:06,520
dans l'analyse asymptotique
celui-ci, et de revenir à certains sujets

550
00:25:06,520 --> 00:25:09,940
de la semaine zéro et un, et le démarrage
pour enlever des roues de formation,

551
00:25:09,940 --> 00:25:10,450
si vous voulez.

552
00:25:10,450 --> 00:25:13,241
Pour que vous compreniez vraiment
en fin de compte à partir du sol, ce qui est

553
00:25:13,241 --> 00:25:16,805
passe sous le capot, lorsque vous
écrire, compiler et exécuter des programmes.

554
00:25:16,805 --> 00:25:19,680
Rappelons en particulier, que cela était
le premier programme de C, nous avons examiné,

555
00:25:19,680 --> 00:25:22,840
canonique, programme simple
de toutes sortes, relativement parlant,

556
00:25:22,840 --> 00:25:24,620
dans laquelle, elle imprime, Bonjour tout le monde.

557
00:25:24,620 --> 00:25:27,610
Et rappeler que je l'ai dit, le processus
que le code source passe par

558
00:25:27,610 --> 00:25:28,430
est exactement cela.

559
00:25:28,430 --> 00:25:31,180
Vous prenez votre code source, passez
à travers un compilateur, comme Clang,

560
00:25:31,180 --> 00:25:34,650
et il en sort code objet, que
pourrait ressembler à ceci, zéros et de uns

561
00:25:34,650 --> 00:25:37,880
que le processeur de l'ordinateur, centrale
unité de traitement ou du cerveau,

562
00:25:37,880 --> 00:25:39,760
comprend finalement.

563
00:25:39,760 --> 00:25:42,460
>> Il se trouve que ce est une
peu d'une simplification excessive,

564
00:25:42,460 --> 00:25:44,480
que nous sommes maintenant dans un
mesure de démêler

565
00:25:44,480 --> 00:25:46,720
de comprendre ce qui a vraiment été
passe sous le capot

566
00:25:46,720 --> 00:25:48,600
chaque fois que vous exécutez
Bruit, ou plus généralement,

567
00:25:48,600 --> 00:25:53,040
chaque fois que vous faites un programme,
utilisant Marque et CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
En particulier, des trucs comme
ci est généré,

569
00:25:56,760 --> 00:25:58,684
lorsque vous compilez d'abord votre programme.

570
00:25:58,684 --> 00:26:00,600
En d'autres termes, lorsque vous
prendre votre code source

571
00:26:00,600 --> 00:26:04,390
et le compiler, ce qui est premier
étant délivré en sortie par Clang

572
00:26:04,390 --> 00:26:06,370
est quelque chose de connu comme le code assembleur.

573
00:26:06,370 --> 00:26:08,990
Et en fait, il ressemble exactement à cela.

574
00:26:08,990 --> 00:26:11,170
>> Je courais une commande à la
ligne de commande plus tôt.

575
00:26:11,170 --> 00:26:16,260
La hello.c de Clang dash capitale,
et cela a créé un fichier

576
00:26:16,260 --> 00:26:19,490
pour moi appelées hello.s,
l'intérieur de laquelle étaient exactement

577
00:26:19,490 --> 00:26:22,290
ces contenus, et un peu plus
ci-dessus et un peu plus bas,

578
00:26:22,290 --> 00:26:25,080
mais je l'ai mis le plus juteux
ici des informations sur l'écran.

579
00:26:25,080 --> 00:26:29,190
Et si vous regardez attentivement, vous verrez
au moins quelques mots-clés familier.

580
00:26:29,190 --> 00:26:31,330
Nous avons principale en haut.

581
00:26:31,330 --> 00:26:35,140
Nous avons printf dans le milieu.

582
00:26:35,140 --> 00:26:38,670
Et nous avons aussi Bonjour tout le monde
n barre oblique inverse entre guillemets bas.

583
00:26:38,670 --> 00:26:42,450
>> Et tout le reste ici
est instructions de niveau très bas

584
00:26:42,450 --> 00:26:45,500
que le processeur de l'ordinateur comprend.

585
00:26:45,500 --> 00:26:50,090
Instructions CPU qui se déplacent mémoire
autour, que les chaînes de charge de la mémoire,

586
00:26:50,090 --> 00:26:52,750
et, finalement, d'impression
choses sur l'écran.

587
00:26:52,750 --> 00:26:56,780
Maintenant, ce qui se passe si après
ce code d'assemblage est généré?

588
00:26:56,780 --> 00:26:59,964
En fin de compte, que vous faites, en effet,
générer encore de code objet.

589
00:26:59,964 --> 00:27:02,630
Mais les mesures qui ont vraiment
été se passe sous le capot

590
00:27:02,630 --> 00:27:04,180
regarder un peu plus comme ça.

591
00:27:04,180 --> 00:27:08,390
Source code devient le code assembleur,
qui devient alors le code objet,

592
00:27:08,390 --> 00:27:11,930
et les mots-clés ici sont que,
lorsque vous compilez votre code source,

593
00:27:11,930 --> 00:27:16,300
out vient code assembleur, puis
lorsque vous assemblez votre code d'assemblage,

594
00:27:16,300 --> 00:27:17,800
out vient code objet.

595
00:27:17,800 --> 00:27:20,360
>> Maintenant Clang est super sophistiqué,
comme beaucoup de compilateurs,

596
00:27:20,360 --> 00:27:23,151
et il fait tout de ces étapes
en même temps, et il ne fait pas nécessairement

597
00:27:23,151 --> 00:27:25,360
sortie tout intermédiaire
fichiers que vous pouvez même voir.

598
00:27:25,360 --> 00:27:28,400
Il compile les choses,
qui est le terme général qui

599
00:27:28,400 --> 00:27:30,000
décrit tout ce processus.

600
00:27:30,000 --> 00:27:32,000
Mais si vous voulez vraiment
d'être particulier, il ya

601
00:27:32,000 --> 00:27:34,330
beaucoup plus de choses là-bas aussi.

602
00:27:34,330 --> 00:27:38,860
>> Mais nous allons examiner maintenant aussi que même
ce programme super simple, hello.c,

603
00:27:38,860 --> 00:27:40,540
une fonction appelée.

604
00:27:40,540 --> 00:27:41,870
Il appelle printf.

605
00:27:41,870 --> 00:27:46,900
Mais je ne l'ai pas écris printf, en effet,
qui vient avec c, pour ainsi dire.

606
00:27:46,900 --> 00:27:51,139
Il est un rappel de la fonction qui est
déclaré dans io.h standard, qui

607
00:27:51,139 --> 00:27:53,180
est un fichier d'en-tête, qui
est un sujet que nous allons effectivement

608
00:27:53,180 --> 00:27:55,780
plonger plus en profondeur avant longtemps.

609
00:27:55,780 --> 00:27:58,000
Mais un fichier d'en-tête est
généralement accompagnée

610
00:27:58,000 --> 00:28:02,920
par un fichier de code, fichier de code source, de sorte
tout comme il existe io.h. norme

611
00:28:02,920 --> 00:28:05,930
>> Il ya quelque temps, quelqu'un,
ou quelqu'un, a également écrit

612
00:28:05,930 --> 00:28:11,040
un fichier appelé io.c standard, dans
où les définitions réels,

613
00:28:11,040 --> 00:28:15,220
ou implémentations de printf,
et grappes d'autres fonctions,

614
00:28:15,220 --> 00:28:16,870
sont en fait écrit.

615
00:28:16,870 --> 00:28:22,140
Donc, étant donné que, si nous considérons avoir
ici sur la gauche, hello.c, que lorsque

616
00:28:22,140 --> 00:28:26,250
compilé, nous donne hello.s, même si
Clang ne dérange pas l'épargne dans un endroit

617
00:28:26,250 --> 00:28:31,360
nous pouvons le voir, et que le code assembleur
obtient assemblés en hello.o, qui

618
00:28:31,360 --> 00:28:34,630
est, en effet, le nom par défaut
donnée chaque fois que vous compilez la source

619
00:28:34,630 --> 00:28:39,350
coder en code objet, mais ne sont pas
tout à fait prêt à l'exécuter encore,

620
00:28:39,350 --> 00:28:41,460
car une autre étape
qui doit arriver, et a

621
00:28:41,460 --> 00:28:44,440
est passé pour le passé quelques-uns
semaines, peut-être à votre insu.

622
00:28:44,440 --> 00:28:47,290
>> Plus précisément, quelque part
CS50 en IDE, et ce,

623
00:28:47,290 --> 00:28:49,870
aussi, sera un peu une
simplification pour un moment,

624
00:28:49,870 --> 00:28:54,670
il est, ou était sur un temps,
un fichier appelé io.c standard,

625
00:28:54,670 --> 00:28:58,440
que quelqu'un compilé dans
io.s standard ou l'équivalent,

626
00:28:58,440 --> 00:29:02,010
que quelqu'un ensuite assemblé
io.o en standard,

627
00:29:02,010 --> 00:29:04,600
ou il se trouve dans un
fichier légèrement différente

628
00:29:04,600 --> 00:29:07,220
format qui peut avoir un différent
extension de fichier tout à fait,

629
00:29:07,220 --> 00:29:11,720
mais en théorie et conceptuellement, exactement
ces mesures devaient se produire dans une certaine forme.

630
00:29:11,720 --> 00:29:14,060
Ce qui veut dire, que maintenant
quand je écrire un programme,

631
00:29:14,060 --> 00:29:17,870
hello.c, qui dit simplement, Bonjour tout le monde,
et je suis en utilisant le code de quelqu'un d'autre

632
00:29:17,870 --> 00:29:22,480
comme printf, qui était autrefois sur un
temps, dans un fichier appelé io.c standard,

633
00:29:22,480 --> 00:29:26,390
puis de toute façon je dois prendre mon
code objet, mes zéros et de uns,

634
00:29:26,390 --> 00:29:29,260
et l'objet de cette personne
code, ou zéros et de uns,

635
00:29:29,260 --> 00:29:34,970
et en quelque sorte lier ensemble dans
un fichier final, appelé bonjour, que

636
00:29:34,970 --> 00:29:38,070
a tous les zéros et
ceux de ma fonction principale,

637
00:29:38,070 --> 00:29:40,830
et tous les zéros
et ceux pour printf.

638
00:29:40,830 --> 00:29:44,900
>> Et en effet, ce dernier processus est
appelé, reliant votre code objet.

639
00:29:44,900 --> 00:29:47,490
La sortie de laquelle
est un fichier exécutable.

640
00:29:47,490 --> 00:29:49,780
Donc, en toute équité, à la
fin de la journée, rien

641
00:29:49,780 --> 00:29:52,660
a changé depuis la première semaine, quand nous
première commencé à compiler des programmes.

642
00:29:52,660 --> 00:29:55,200
En effet, tout cela a été
passe sous le capot,

643
00:29:55,200 --> 00:29:57,241
mais maintenant nous sommes dans une position
où nous pouvons réellement

644
00:29:57,241 --> 00:29:58,794
démêler ces différentes étapes.

645
00:29:58,794 --> 00:30:00,710
Et en effet, à la fin
de la journée, nous sommes toujours

646
00:30:00,710 --> 00:30:04,480
gauche avec des zéros et de uns, qui
est en fait une excellente introduction maintenant

647
00:30:04,480 --> 00:30:08,620
à l'autre de capacité C, qui
nous avons pas eu à tirer parti le plus probable

648
00:30:08,620 --> 00:30:11,250
à ce jour, connu sous le nom opérateurs binaires.

649
00:30:11,250 --> 00:30:15,220
En d'autres termes, à ce jour, chaque fois que nous avons
traiter les données en C ou les variables C,

650
00:30:15,220 --> 00:30:17,660
nous avons eu des choses comme
chars et des flotteurs et ins

651
00:30:17,660 --> 00:30:21,990
et longs et doubles et similaires, mais
tous ceux qui sont au moins huit bits.

652
00:30:21,990 --> 00:30:25,550
Nous avons encore jamais été en mesure de
manipuler des bits individuels,

653
00:30:25,550 --> 00:30:28,970
même si un bit individuel, nous
savez, peut représenter un 0 et un 1.

654
00:30:28,970 --> 00:30:32,640
Or il se trouve que, dans C, vous
peuvent avoir accès à des bits individuels,

655
00:30:32,640 --> 00:30:35,530
si vous connaissez la syntaxe,
avec laquelle de les atteindre.

656
00:30:35,530 --> 00:30:38,010
>> Donc, nous allons jeter un coup d'oeil
aux opérateurs au niveau du bit.

657
00:30:38,010 --> 00:30:41,700
Donc, ici photographiés sont quelques symboles
nous avons, en quelque sorte, en quelque sorte, vu avant.

658
00:30:41,700 --> 00:30:45,580
Je vois une esperluette, un vertical
bar, et quelques autres ainsi,

659
00:30:45,580 --> 00:30:49,430
et rappeler que esperluette esperluette
est quelque chose que nous avons vu auparavant.

660
00:30:49,430 --> 00:30:54,060
L'opérateur logique ET, où vous avez
deux d'entre eux en même temps, ou la logique OU

661
00:30:54,060 --> 00:30:56,300
l'opérateur, où vous
avoir deux barres verticales.

662
00:30:56,300 --> 00:31:00,550
Opérateurs binaires, que nous allons
voir fonctionner sur des morceaux individuellement,

663
00:31:00,550 --> 00:31:03,810
il suffit d'utiliser un seul esperluette, un
seule barre verticale, le symbole caret

664
00:31:03,810 --> 00:31:06,620
vient ensuite, la petite
tilde, puis à gauche

665
00:31:06,620 --> 00:31:08,990
support de crochet gauche, ou
crochet droit crochet droit.

666
00:31:08,990 --> 00:31:10,770
Chacun de ceux-ci ont des significations différentes.

667
00:31:10,770 --> 00:31:11,950
>> En fait, nous allons jeter un coup d'oeil.

668
00:31:11,950 --> 00:31:16,560
Allons vieille école aujourd'hui, et l'utilisation
un écran tactile d'antan,

669
00:31:16,560 --> 00:31:18,002
connu comme un tableau blanc.

670
00:31:18,002 --> 00:31:19,710
Et ce tableau blanc
va nous permettre

671
00:31:19,710 --> 00:31:27,360
pour exprimer certains symboles assez simples,
ou plutôt des formules assez simples,

672
00:31:27,360 --> 00:31:29,560
que nous puissions finalement
l'effet de levier, afin

673
00:31:29,560 --> 00:31:33,230
à l'accès individuel
bits dans un programme C.

674
00:31:33,230 --> 00:31:34,480
En d'autres termes, nous allons le faire.

675
00:31:34,480 --> 00:31:37,080
Parlons d'abord pour une
instant sur esperluette,

676
00:31:37,080 --> 00:31:39,560
qui est le bit à bit ET opérateur.

677
00:31:39,560 --> 00:31:42,130
En d'autres termes, ceci est
un opérateur qui permet

678
00:31:42,130 --> 00:31:45,930
moi d'avoir une variable de gauche
généralement, et une variable de droite,

679
00:31:45,930 --> 00:31:50,640
ou une valeur individuelle, que si nous ET
ensemble, me donne un résultat final.

680
00:31:50,640 --> 00:31:51,560
Alors qu'est-ce que je veux dire?

681
00:31:51,560 --> 00:31:54,840
Si dans un programme, vous avez une variable
qui stocke une de ces valeurs,

682
00:31:54,840 --> 00:31:58,000
ou nous allons garder les choses simples, et juste
écrire zéros et de uns individuellement,

683
00:31:58,000 --> 00:32:00,940
voici comment l'opérateur esperluette fonctionne.

684
00:32:00,940 --> 00:32:06,400
0 0 esperluette va égaler 0.

685
00:32:06,400 --> 00:32:07,210
Maintenant, pourquoi est-ce?

686
00:32:07,210 --> 00:32:09,291
>> Il est très similaire à
Expressions booléennes,

687
00:32:09,291 --> 00:32:10,540
que nous avons discuté jusqu'à présent.

688
00:32:10,540 --> 00:32:15,800
Si vous pensez que, après tout, le 0 est
false, 0 est faux, faux et faux

689
00:32:15,800 --> 00:32:18,720
est, comme nous l'avons discuté
logiquement, aussi fausse.

690
00:32:18,720 --> 00:32:20,270
Donc, nous obtenons 0 ici aussi.

691
00:32:20,270 --> 00:32:24,390
Si vous prenez 0 esperluette
1, ainsi que, aussi,

692
00:32:24,390 --> 00:32:29,890
va être 0, car pour cette
expression du côté gauche pour être vrai ou 1,

693
00:32:29,890 --> 00:32:32,360
il aurait besoin d'être vrai et vrai.

694
00:32:32,360 --> 00:32:36,320
Mais ici nous avons fausse
et vrai, ou 0 et 1.

695
00:32:36,320 --> 00:32:42,000
Maintenant, encore une fois, si nous avons une esperluette
0, qui, lui aussi, va être 0,

696
00:32:42,000 --> 00:32:47,240
et si nous avons une esperluette 1,
Enfin ne nous avons un peu 1.

697
00:32:47,240 --> 00:32:50,340
Donc, en d'autres termes, nous ne faisons pas
quelque chose d'intéressant avec cet opérateur

698
00:32:50,340 --> 00:32:51,850
pour l'instant, cet opérateur esperluette.

699
00:32:51,850 --> 00:32:53,780
Il est le bit à bit ET opérateur.

700
00:32:53,780 --> 00:32:57,290
Mais ce sont les ingrédients
par lequel nous pouvons faire

701
00:32:57,290 --> 00:32:59,240
choses intéressantes, comme nous le verrons bientôt.

702
00:32:59,240 --> 00:33:02,790
>> Maintenant regardons juste la seule
barre verticale ici sur la droite.

703
00:33:02,790 --> 00:33:06,710
Si je dois un bit 0 et je
OU avec le bit à bit

704
00:33:06,710 --> 00:33:11,030
OU opérateur, un autre bit 0,
que ça va me donner 0.

705
00:33:11,030 --> 00:33:17,540
Si je prends un peu et ou il avec 0
un bit 1, alors je vais obtenir 1.

706
00:33:17,540 --> 00:33:19,830
Et en fait, juste pour
clarté, permettez-moi de revenir en arrière,

707
00:33:19,830 --> 00:33:23,380
de sorte que mes barres verticales
ne sont pas pris pour des 1.

708
00:33:23,380 --> 00:33:26,560
Permettez-moi de réécrire tous
ma 1 est un peu plus

709
00:33:26,560 --> 00:33:32,700
clairement, afin que nous voyons ensuite, si je
ont un 1 ou 0, cela va être un 1,

710
00:33:32,700 --> 00:33:39,060
et si je dois un 1 ou 1 que,
aussi, va être un 1.

711
00:33:39,060 --> 00:33:42,900
Donc vous pouvez voir que la logique OU
opérateur se comporte très différemment.

712
00:33:42,900 --> 00:33:48,070
Cela me donne 0 ou 0 me donne 0, mais
toute autre combinaison me donne 1.

713
00:33:48,070 --> 00:33:52,480
Tant que je suis un 1 dans le
formule, le résultat va être une.

714
00:33:52,480 --> 00:33:55,580
>> Par contraste avec le ET
l'opérateur, l'esperluette,

715
00:33:55,580 --> 00:34:00,940
que si je dois deux 1 dans le
équation, puis-je obtenir en fait un sur 1.

716
00:34:00,940 --> 00:34:02,850
Maintenant, il ya quelques autres
opérateurs ainsi.

717
00:34:02,850 --> 00:34:04,810
L'un d'eux est un peu plus compliquée.

718
00:34:04,810 --> 00:34:07,980
Alors laissez-moi aller de l'avant et d'effacer
ce afin de libérer un peu d'espace.

719
00:34:07,980 --> 00:34:13,020

720
00:34:13,020 --> 00:34:16,460
Et nous allons jeter un oeil à la
caret, juste un instant.

721
00:34:16,460 --> 00:34:18,210
Ceci est typiquement un
caractère que vous pouvez taper

722
00:34:18,210 --> 00:34:21,420
sur votre Maj de maintien de clavier et
puis l'un des numéros au sommet de votre US

723
00:34:21,420 --> 00:34:22,250
clavier.

724
00:34:22,250 --> 00:34:26,190
>> Donc, cela est l'exclusif
Opérateur OU, OU exclusif.

725
00:34:26,190 --> 00:34:27,790
Donc, nous venons de voir l'opérateur OR.

726
00:34:27,790 --> 00:34:29,348
Ceci est l'opérateur OU exclusif.

727
00:34:29,348 --> 00:34:30,639
Ce qui est réellement la différence?

728
00:34:30,639 --> 00:34:34,570
Eh bien disons juste regarder la formule,
et l'utiliser comme ingrédients finalement.

729
00:34:34,570 --> 00:34:37,690
0 0 XOR.

730
00:34:37,690 --> 00:34:39,650
Je vais dire est toujours 0.

731
00:34:39,650 --> 00:34:41,400
Voilà la définition de XOR.

732
00:34:41,400 --> 00:34:47,104
XOR 0 1 va être une.

733
00:34:47,104 --> 00:34:58,810
Une XOR 0 va être 1,
et 1 XOR 1 va être?

734
00:34:58,810 --> 00:34:59,890
Faux?

735
00:34:59,890 --> 00:35:00,520
Ou à droite?

736
00:35:00,520 --> 00:35:01,860
Je ne sais pas.

737
00:35:01,860 --> 00:35:02,810
0.

738
00:35:02,810 --> 00:35:04,700
Maintenant, ce qui se passe ici?

739
00:35:04,700 --> 00:35:06,630
Eh bien réfléchir à la
nom de cet opérateur.

740
00:35:06,630 --> 00:35:09,980
OU exclusif, de sorte que le
nom, type de, suggère,

741
00:35:09,980 --> 00:35:13,940
la réponse est que va être
1 si les entrées sont exclusifs,

742
00:35:13,940 --> 00:35:15,560
exclusivement différente.

743
00:35:15,560 --> 00:35:18,170
Donc, voici les entrées sont les
même, de sorte que la sortie est de 0.

744
00:35:18,170 --> 00:35:20,700
Ici, les entrées sont le
même, de sorte que la sortie est de 0.

745
00:35:20,700 --> 00:35:25,640
Voici les sorties sont différents, ils
sont exclusifs, et donc la sortie est 1.

746
00:35:25,640 --> 00:35:28,190
Il est donc très similaire à
Et, il est très similaire,

747
00:35:28,190 --> 00:35:32,760
ou plutôt il est très similaire à
OU, mais seulement d'une manière exclusive.

748
00:35:32,760 --> 00:35:36,210
Celui-ci est plus un 1,
parce que nous avons deux de 1,

749
00:35:36,210 --> 00:35:38,621
et non pas exclusivement, un seul d'entre eux.

750
00:35:38,621 --> 00:35:39,120
Bien.

751
00:35:39,120 --> 00:35:40,080
Qu'en est-il des autres?

752
00:35:40,080 --> 00:35:44,220
Eh bien, le tilde, quant à lui, est
effectivement agréable et simple, heureusement.

753
00:35:44,220 --> 00:35:46,410
Et ceci est un unaire
opérateur, ce qui signifie

754
00:35:46,410 --> 00:35:50,400
il est appliqué à une seule entrée,
l'un des opérandes, pour ainsi dire.

755
00:35:50,400 --> 00:35:51,800
Non à une gauche et une droite.

756
00:35:51,800 --> 00:35:56,050
En d'autres termes, si vous prenez de tilde
0, la réponse sera le contraire.

757
00:35:56,050 --> 00:35:59,710
Et si vous prenez tilde de 1, la
Réponse Il sera le contraire.

758
00:35:59,710 --> 00:36:02,570
Donc, l'opérateur tilde est
une façon de nier un peu,

759
00:36:02,570 --> 00:36:06,000
ou de retournement un peu de
0 à 1, ou 1-0.

760
00:36:06,000 --> 00:36:09,820
>> Et cela nous laisse enfin
avec seulement deux opérateurs finaux,

761
00:36:09,820 --> 00:36:13,840
Le soi-disant décalage à gauche, et de la
dite opérateur de décalage à droite.

762
00:36:13,840 --> 00:36:16,620
Jetons un regard sur la façon dont ces travaux.

763
00:36:16,620 --> 00:36:20,780
L'opérateur de décalage à gauche, écrite
avec deux équerres de ce genre,

764
00:36:20,780 --> 00:36:22,110
fonctionne comme suit.

765
00:36:22,110 --> 00:36:27,390
Si mon entrée, ou mon opérande, à gauche
opérateur de décalage est tout simplement un 1.

766
00:36:27,390 --> 00:36:33,750
Et je puis dire que l'ordinateur
décalage à gauche que 1, disons sept places,

767
00:36:33,750 --> 00:36:37,150
le résultat est comme si je
prendre que 1, et le déplacer

768
00:36:37,150 --> 00:36:40,160
sept emplacements sur la
gauche, et par défaut,

769
00:36:40,160 --> 00:36:42,270
nous allons supposer que
l'espace vers la droite

770
00:36:42,270 --> 00:36:44,080
va être complétée par des zéros.

771
00:36:44,080 --> 00:36:50,316
En d'autres termes, 1 Maj gauche 7 va
de me donner que 1, suivi par 1, 2, 3,

772
00:36:50,316 --> 00:36:54,060
4, 5, 6, 7 zéros.

773
00:36:54,060 --> 00:36:57,380
Donc dans un sens, il vous permet de
prendre un petit nombre comme 1,

774
00:36:57,380 --> 00:37:00,740
et de faire clairement beaucoup
beaucoup, beaucoup plus grand de cette manière,

775
00:37:00,740 --> 00:37:06,460
mais nous allons réellement voir
des approches plus intelligentes pour elle

776
00:37:06,460 --> 00:37:08,080
à la place, ainsi,

777
00:37:08,080 --> 00:37:08,720
>> Bien.

778
00:37:08,720 --> 00:37:10,060
Voilà pour trois semaines.

779
00:37:10,060 --> 00:37:11,400
Nous vous verrons la prochaine fois.

780
00:37:11,400 --> 00:37:12,770
Cela a été CS50.

781
00:37:12,770 --> 00:37:17,270

782
00:37:17,270 --> 00:37:22,243
>> [Jouer de la musique]

783
00:37:22,243 --> 00:37:25,766
>> ENCEINTE 1: Il était au snack-
bar de manger un hot fudge sundae.

784
00:37:25,766 --> 00:37:28,090
Il avait tout sur son visage.

785
00:37:28,090 --> 00:37:30,506
Il porte que le chocolat comme une barbe

786
00:37:30,506 --> 00:37:31,756
SPEAKER 2: Que faites-vous?

787
00:37:31,756 --> 00:37:32,422
Intervenant 3: Hmmm?

788
00:37:32,422 --> 00:37:33,500
Quoi?

789
00:37:33,500 --> 00:37:36,800
>> SPEAKER 2: Est-ce que vous venez de double dip?

790
00:37:36,800 --> 00:37:38,585
Vous double plongé la puce.

791
00:37:38,585 --> 00:37:39,460
Intervenant 3: Excusez-moi.

792
00:37:39,460 --> 00:37:44,440
SPEAKER 2: Vous plongé la puce, vous
a pris une bouchée, et vous plongé à nouveau.

793
00:37:44,440 --> 00:37:44,940
Intervenant 3:

794
00:37:44,940 --> 00:37:48,440
SPEAKER 2: Voilà comme mettre
votre droit de la bouche tout dans la trempette.

795
00:37:48,440 --> 00:37:52,400
La prochaine fois que vous prenez une puce,
il suffit de tremper une fois, et y mettre fin.

796
00:37:52,400 --> 00:37:53,890
>> Intervenant 3: Vous savez quoi, Dan?

797
00:37:53,890 --> 00:37:58,006
Vous trempez la façon dont vous voulez plonger.

798
00:37:58,006 --> 00:38:01,900
Je vais tremper la manière que je veux plonger.

799
00:38:01,900 --> 00:38:03,194