1
00:00:00,000 --> 00:00:02,280
[Powered by Google Translate] [Semaine 3, suite]

2
00:00:02,280 --> 00:00:04,110
>> [David J. Malan - Université de Harvard]

3
00:00:04,110 --> 00:00:07,130
>> [C'est CS50. - CS50.TV]

4
00:00:07,130 --> 00:00:11,010
>> Très bien. Bienvenue à nouveau. C'est CS50 et c'est la fin de la semaine 3.

5
00:00:11,010 --> 00:00:14,680
>> Donc, pour ceux qui ne connaissent, l'année dernière Harvard a lancé ce qu'on appelle l'Innovation Lab,

6
00:00:14,680 --> 00:00:18,530
ou i-lab, qui est un magnifique bâtiment de l'autre côté de la rivière sur le campus HBS

7
00:00:18,530 --> 00:00:22,640
qui est ouvert aux étudiants des collèges, des étudiants, des étudiants GSAS de tous les campus à travers,

8
00:00:22,640 --> 00:00:27,000
y compris les professeurs, et c'est un endroit pour se réunir pour travailler sur des choses innovantes,

9
00:00:27,000 --> 00:00:29,180
choses particulièrement entrepreneuriales

10
00:00:29,180 --> 00:00:33,410
si vous et 0 ou plusieurs amis envisagez de faire quelque chose de l'esprit d'entreprise

11
00:00:33,410 --> 00:00:37,080
soit au cours de cette classe, après cette classe, ou au-delà.

12
00:00:37,080 --> 00:00:41,540
>> Ainsi, l'une des choses qu'ils font sur la durée J est de ces voyages,

13
00:00:41,540 --> 00:00:44,510
dont l'un est à New York, dont l'un est à la Silicon Valley.

14
00:00:44,510 --> 00:00:47,530
L'espace est très limité, mais c'est une occasion de côtoyer des MBA

15
00:00:47,530 --> 00:00:52,200
et les étudiants diplômés sur le campus et en fait passer du temps dans ces domaines respectifs

16
00:00:52,200 --> 00:00:55,500
bavarder startups, bavarder entrepreneurs, etc.

17
00:00:55,500 --> 00:00:57,870
Donc, si vous êtes intéressé, consultez cette URL ici.

18
00:00:57,870 --> 00:01:01,220
Il est également disponible sur les diapositives en ligne.

19
00:01:01,220 --> 00:01:04,610
>> Pourrait-on atténuer l'audio maison juste un peu?

20
00:01:04,610 --> 00:01:08,640
Si vous souhaitez vous joindre à nous pour le déjeuner ce vendredi, 1:15 pm in Fire & Ice, s'il vous plaît tête là.

21
00:01:08,640 --> 00:01:11,390
Toutes mes excuses si le formulaire est déjà rempli au moment où vous vous y rendre.

22
00:01:11,390 --> 00:01:13,750
Mais nous allons continuer cette tradition en avant.

23
00:01:13,750 --> 00:01:17,350
>> Aujourd'hui, nous continuons la discussion de niveau supérieur de divers problèmes que nous pouvons résoudre,

24
00:01:17,350 --> 00:01:21,330
en se concentrant beaucoup moins, aujourd'hui du moins, sur le code et bien plus encore sur les idées.

25
00:01:21,330 --> 00:01:24,720
Alors, pensez à revenir à la semaine 0, lorsque nous arracha un annuaire téléphonique dans la moitié,

26
00:01:24,720 --> 00:01:28,260
dont l'objectif était de faire quelque chose, il est vrai, un peu dramatique

27
00:01:28,260 --> 00:01:32,360
mais pour envoyer le point de recherche qui n'a pas besoin d'être nécessairement

28
00:01:32,360 --> 00:01:35,100
aussi évident à première vue que vous pourriez penser.

29
00:01:35,100 --> 00:01:40,200
Et la résolution de problèmes en général ne sont pas nécessairement toujours le meilleur -

30
00:01:40,200 --> 00:01:44,130
La solution la plus évidente serait pas nécessairement le meilleur.

31
00:01:44,130 --> 00:01:47,300
Nous avons donc eu cet annuaire et, franchement, chacun d'entre nous dans cette salle avait les instincts,

32
00:01:47,300 --> 00:01:51,470
très probablement, à commencer par le milieu lors de la recherche pour Mike Smith, puis aller à gauche ou à droite

33
00:01:51,470 --> 00:01:54,280
sur la base de ce que la lettre de l'alphabet nous est arrivé de se retrouver sur.

34
00:01:54,280 --> 00:01:57,560
>> Mais cette idée simple que nous, les humains ont pris pour acquis depuis si longtemps

35
00:01:57,560 --> 00:02:00,670
devriez vraiment commencer à venir à la pointe de votre esprit

36
00:02:00,670 --> 00:02:03,900
parce que les problèmes deviennent beaucoup plus complexes que d'un annuaire téléphonique,

37
00:02:03,900 --> 00:02:07,420
ces mêmes simples, des idées brillantes sont ce que l'on va nous permettre

38
00:02:07,420 --> 00:02:10,259
pour résoudre des problèmes beaucoup plus compliqués et plus intéressant,

39
00:02:10,259 --> 00:02:12,930
parmi eux certaines des choses que nous tenons pour acquis déjà ces jours-ci.

40
00:02:12,930 --> 00:02:15,720
Des milliards de pages Web dehors là, et pourtant, Google et Bing et autres

41
00:02:15,720 --> 00:02:17,660
sont en mesure de trouver des choses pour nous comme ça.

42
00:02:17,660 --> 00:02:22,300
Cela n'est pas le cas à l'aide d'une recherche linéaire, recherche dans toutes les pages Web possibles.

43
00:02:22,300 --> 00:02:25,290
Facebook est en mesure de vous dire qui tous vos amis sont ou amis d'amis,

44
00:02:25,290 --> 00:02:28,250
et cela aussi peut être fait en apparence en un instant ces jours-ci

45
00:02:28,250 --> 00:02:30,820
même si elles ont des millions d'utilisateurs.

46
00:02:30,820 --> 00:02:34,250
>> Et alors comment on fait résoudre des problèmes d'une telle ampleur finira par réduire

47
00:02:34,250 --> 00:02:37,830
les idées, nous avons examiné la semaine 0 et un peu plus aujourd'hui.

48
00:02:37,830 --> 00:02:42,320
Nous n'allons pas ré-exécuter cet algorithme, mais rappelons nous avons aussi fait la semaine 0 cet exercice

49
00:02:42,320 --> 00:02:44,780
où nous avions tout le monde se lever, prendre le numéro 1,

50
00:02:44,780 --> 00:02:48,720
et puis nous avons eu tout le monde l'auto-comptage par appariement éteint, ajouter vos numéros ensemble,

51
00:02:48,720 --> 00:02:51,930
puis la moitié de la bande s'assit sur chaque itération.

52
00:02:51,930 --> 00:02:56,750
Donc, nous sommes passés de 500 élèves de 250 à 125 et ainsi de suite.

53
00:02:56,750 --> 00:03:00,080
Mais, comme nous l'avons dit, le lundi, l'idée puissant, il

54
00:03:00,080 --> 00:03:02,460
était que si nous avons doublé la taille de ce problème

55
00:03:02,460 --> 00:03:06,480
et tous les enfants de la Justice ou CE 10 revint dans la chambre et nous a rejoint,

56
00:03:06,480 --> 00:03:09,510
ainsi, on pourrait probablement compter de ce groupe surplus total

57
00:03:09,510 --> 00:03:13,380
avec juste 1 itération grand plus de la boucle, car ils ne peut-être le double de la taille

58
00:03:13,380 --> 00:03:15,630
ou en cas de CE 10 un peu plus du double de la taille.

59
00:03:15,630 --> 00:03:18,440
Et donc on aurait pu passer un peu plus de temps,

60
00:03:18,440 --> 00:03:22,000
mais nous n'aurions pas à dépenser 400 ou 700 pas de plus.

61
00:03:22,000 --> 00:03:26,550
>> Juste pour peindre cette image d'une manière qui est un peu moins abstrait, il ne faut pas avoir tout le monde debout.

62
00:03:26,550 --> 00:03:31,100
Mais si ceux d'entre vous qui ont choisi de rester dans l'orchestre d'aujourd'hui ne me dérangerait pas debout,

63
00:03:31,100 --> 00:03:34,580
nous allons voir si nous pouvons trouver parmi vous qui est la personne la plus

64
00:03:34,580 --> 00:03:36,730
en faisant le même genre d'algorithme de comparaison.

65
00:03:36,730 --> 00:03:41,830
Donc, si vous êtes assis à l'orchestre, toutes mes excuses, mais l'étape 1, levez-vous;

66
00:03:41,830 --> 00:03:44,650
l'étape 2, paires au loin avec quelqu'un à proximité vous,

67
00:03:44,650 --> 00:03:49,360
comprendre qui est plus grand, et asseyez-vous si vous êtes plus courte.

68
00:03:49,360 --> 00:03:51,360
Ensuite, répétez.

69
00:03:51,360 --> 00:03:56,280
[Étudiants en murmurant]

70
00:04:13,450 --> 00:04:15,320
>> D'accord.

71
00:04:15,320 --> 00:04:19,010
D'accord. On reste debout. Quel est ton nom? >> Andrew.

72
00:04:19,010 --> 00:04:21,959
>> Andrew, vous êtes la personne la plus à l'orchestre, aujourd'hui.

73
00:04:21,959 --> 00:04:28,100
>> Félicitations. [Applaudissements et des acclamations] D'accord. Asseyez-vous. Donc, nous avons trouvé Andrew.

74
00:04:28,100 --> 00:04:30,870
Mais combien de temps cela a dû me prendre, par exemple, de trouver Andrew

75
00:04:30,870 --> 00:04:33,740
dans cette section orchestre de 50 + ou tant de gens?

76
00:04:33,740 --> 00:04:36,900
J'aurais pu prendre une approche assez simple et commencer ici.

77
00:04:36,900 --> 00:04:39,270
Et j'ai 2 personnes debout et je viens de les comparer,

78
00:04:39,270 --> 00:04:42,120
et puis je dis à celui qui est légèrement plus court: «Bon, vous vous asseyez,"

79
00:04:42,120 --> 00:04:44,380
et je vais vous rappeler qui était le plus grand personne.

80
00:04:44,380 --> 00:04:49,030
Puis-je répéter, répéter, répéter, et je m'accroche à la personne la plus grande

81
00:04:49,030 --> 00:04:51,920
jusqu'à ce que je trouve quelqu'un un peu plus grand qu'eux, à quel point

82
00:04:51,920 --> 00:04:54,950
la personne un peu plus court doit alors s'asseoir.

83
00:04:54,950 --> 00:04:57,690
Mais dans cet algorithme dans cette section orchestre, s'il ya n d'entre vous,

84
00:04:57,690 --> 00:05:00,480
le nombre de pas est que l'algorithme va prendre? >> [L'élève] N.

85
00:05:00,480 --> 00:05:03,580
>> Il va falloir n, à droite, parce que dans le pire des cas, pour ainsi dire,

86
00:05:03,580 --> 00:05:09,090
la personne la plus grande est la dernière personne que je reçois simplement par la malchance aléatoire.

87
00:05:09,090 --> 00:05:14,260
Donc, dans le pire des cas, le temps d'exécution de cet algorithme est linéaire, il est n,

88
00:05:14,260 --> 00:05:18,070
où n est le nombre total de personnes dans l'espace, l'ampleur du problème.

89
00:05:18,070 --> 00:05:19,600
Qu'en est-il de cet algorithme?

90
00:05:19,600 --> 00:05:22,080
Le fait que vous tous debout, puis encore la moitié d'entre vous assis,

91
00:05:22,080 --> 00:05:23,950
moitié d'entre vous assis, la moitié d'entre vous assis.

92
00:05:23,950 --> 00:05:26,070
Combien d'étapes faut qui ont pris si il ya des n-tu ici?

93
00:05:26,070 --> 00:05:30,200
[L'élève] N log n. >> Ce serait pire. Log n.

94
00:05:30,200 --> 00:05:32,930
>> Donc log n, même si vous ne me souviens pas bien ce qu'est un logarithme est,

95
00:05:32,930 --> 00:05:38,410
pour l'instant, juste apprécier ce qu'il rapporte en quelque sorte à cette réduction de moitié et réduire de moitié et réduire de moitié.

96
00:05:38,410 --> 00:05:41,000
Il ne doit pas être un facteur de 2. Ce pourrait être un facteur de 3.

97
00:05:41,000 --> 00:05:46,560
Mais c'est cette répétition du même genre de facteur tels que la taille du problème commence ici

98
00:05:46,560 --> 00:05:49,620
mais va immédiatement ici, puis là, puis là, puis ici.

99
00:05:49,620 --> 00:05:53,580
Vous ne prenez de petites bouchées de régler le problème, vous êtes vraiment loin à lui couper

100
00:05:53,580 --> 00:05:56,160
avec un grand coup à chaque fois.

101
00:05:56,160 --> 00:06:00,810
Donc, nous avons eu 50 personnes, puis 25, puis 12 ½ ou 13 personnes debout,

102
00:06:00,810 --> 00:06:05,370
puis 6 ans et demi et ainsi de suite jusqu'à ce que finalement juste debout Andrew a été laissé.

103
00:06:05,370 --> 00:06:08,710
Donc, nous allons appeler ce journal de n, et vous pouvez visualiser ce qui suit.

104
00:06:08,710 --> 00:06:12,570
Rappelons cette image là où un algorithme linéaire est comme la ligne rouge là-bas,

105
00:06:12,570 --> 00:06:17,520
la ligne jaune est le comptage par l'algorithme de 2s que nous avons utilisé pour les élèves de comptage

106
00:06:17,520 --> 00:06:22,300
dans le passé, mais aujourd'hui, le Saint-Graal va rester cette ligne verte

107
00:06:22,300 --> 00:06:25,470
où si nous avons doublé le nombre de personnes dans l'orchestre, ou tout simplement dit:

108
00:06:25,470 --> 00:06:29,170
l'enfer, nous allons avoir tout le monde dans toute la salle debout, pas une grosse affaire

109
00:06:29,170 --> 00:06:31,560
parce que nous grosso modo doubler le nombre de personnes ici-bas,

110
00:06:31,560 --> 00:06:33,500
1 plus itération, pas un problème.

111
00:06:33,500 --> 00:06:36,200
>> Nous avons constaté Andrew ou celui qui arrive à être plus grand que Andrew

112
00:06:36,200 --> 00:06:38,770
dans la mezzanine ou sur le balcon.

113
00:06:38,770 --> 00:06:42,140
Donc, cette idée simple que nous avons pris tellement de soi dans un annuaire téléphonique,

114
00:06:42,140 --> 00:06:46,170
rendre compte qu'il ya tellement d'endroits différents où nous pouvons l'appliquer.

115
00:06:46,170 --> 00:06:50,810
Juste pour gifler un peu de jargon - en fait, plutôt que le jargon d'abord,

116
00:06:50,810 --> 00:06:52,750
me laisser aller à cette image ici.

117
00:06:52,750 --> 00:06:56,970
À l'heure actuelle, nous avons parlé n et n / 2 et puis connectez-vous de n,

118
00:06:56,970 --> 00:07:00,500
mais nous pouvons certainement trouver, comme nous le verrons au cours du semestre,

119
00:07:00,500 --> 00:07:05,130
autre type de formules mathématiques pour décrire cette notion générale du temps de marche.

120
00:07:05,130 --> 00:07:07,580
Ceux-ci sont sortis de leur contexte pour l'instant car nous verrons d'ici peu

121
00:07:07,580 --> 00:07:09,900
algorithmes que ceux-ci représentent en fait.

122
00:07:09,900 --> 00:07:17,990
>> Mais remarquez ici la ligne linéaire n, la ligne droite, est en réalité très faible pointant vers la droite maintenant.

123
00:07:17,990 --> 00:07:22,950
C'est en quelque sorte une illusion d'optique que nous venons de changer ce que l'axe des x représente

124
00:07:22,950 --> 00:07:26,130
et l'axe des y, et nous pouvons faire un point en ligne droite dans n'importe quelle direction nous voulons.

125
00:07:26,130 --> 00:07:30,350
Mais la raison pour laquelle il est si apparemment déchargées maintenant

126
00:07:30,350 --> 00:07:35,690
C'est parce que nous avions besoin de faire de la place sur ce graphique pour beaucoup plus lents fois de suite.

127
00:07:35,690 --> 00:07:39,030
Pour l'instant, sachez qu'il ya quelques algorithmes assez mauvais dans la vie,

128
00:07:39,030 --> 00:07:43,790
dont certains n'ont pas pris les mesures n ou, mieux encore, vous n étapes, mais bien plus encore.

129
00:07:43,790 --> 00:07:48,820
Donc, au-dessus de la ligne n ici à l'avis en bas il ya n fois journal de n,

130
00:07:48,820 --> 00:07:51,410
et nous verrons ce que cela signifie avant longtemps.

131
00:07:51,410 --> 00:07:56,010
Ci-dessus qui est n au carré, et nous n'avons pas vu tous les algorithmes n carrés encore, mais nous sommes sur le point d'.

132
00:07:56,010 --> 00:07:57,660
Et cela a l'air vraiment mauvais.

133
00:07:57,660 --> 00:08:01,610
Il ya 2 au n, quelque chose exponentielle, qui se sent encore pire.

134
00:08:01,610 --> 00:08:05,760
Et pourtant, curieusement, alors il n en cubes, qui, si vous êtes en quelque sorte penser à l'avenir,

135
00:08:05,760 --> 00:08:10,000
si vous sorte de faire le calcul, 2 au n devient effectivement beaucoup plus droite,

136
00:08:10,000 --> 00:08:15,930
beaucoup plus haut que n cubes si vous regardez les axes assez loin.

137
00:08:15,930 --> 00:08:19,890
Donc remarquerez tout de suite ces axes sont arbitrairement de 2 à 10 sur l'axe x.

138
00:08:19,890 --> 00:08:21,770
>> Et qu'est-ce que ça veut dire?

139
00:08:21,770 --> 00:08:23,890
Cela signifie que 2 personnes à 10 personnes dans la salle.

140
00:08:23,890 --> 00:08:27,200
C'est tout moyen x: taille du problème, quel que soit le contexte.

141
00:08:27,200 --> 00:08:30,420
Et un axe vertical en ce moment est le nombre de secondes ou le nombre d'étapes -

142
00:08:30,420 --> 00:08:31,840
une certaine unité de temps.

143
00:08:31,840 --> 00:08:34,740
Mais remarquez que c'est 0 à 60 et 0 à 10.

144
00:08:34,740 --> 00:08:38,549
Mais si l'on sorte de zoom arrière, comme vous le feriez dans Excel ou un logiciel de cartographie,

145
00:08:38,549 --> 00:08:43,370
et nous remontons à 200.000, remarquez que quelque chose comme 2 à n

146
00:08:43,370 --> 00:08:47,520
va complètement submerger les temps d'exécution de carré n,

147
00:08:47,520 --> 00:08:50,960
n cubes, n log n - tout ce dont nous avons parlé jusqu'à présent.

148
00:08:50,960 --> 00:08:54,190
Et pourtant, le hic, c'est quand vous commencez à parler de choses comme Facebook

149
00:08:54,190 --> 00:08:57,150
où vous avez beaucoup, beaucoup, beaucoup de gens tous interconnectés,

150
00:08:57,150 --> 00:09:00,650
vous avez n personnes, dont chacun peut en avoir autant que des amis n

151
00:09:00,650 --> 00:09:02,860
si tout le monde est une sorte de copain-copain dans le monde,

152
00:09:02,860 --> 00:09:08,100
eh bien, c'est n fois n déjà, donc c'est n carrés amitiés possibles,

153
00:09:08,100 --> 00:09:10,950
au moins dans 1 sens, n carrés amitiés possibles.

154
00:09:10,950 --> 00:09:15,330
Alors que suggère déjà que la recherche graphe social de Facebook, pour ainsi dire,

155
00:09:15,330 --> 00:09:18,090
peut commencer à être exprimé dans ces sortes de formules.

156
00:09:18,090 --> 00:09:19,820
>> Nous allons revenir et faire ce beaucoup plus concret,

157
00:09:19,820 --> 00:09:23,280
mais pour l'instant, l'objectif pour les prochaines semaines de nombreux

158
00:09:23,280 --> 00:09:27,170
va pour être sûr de ne pas aller sur les algorithmes de mise en œuvre ou code

159
00:09:27,170 --> 00:09:29,870
qui finissent par prendre autant de temps que quelque chose comme ça.

160
00:09:29,870 --> 00:09:33,110
Mais la chose de fascinant de l'informatique si vous continuez dans ce domaine

161
00:09:33,110 --> 00:09:38,320
prendre des cours comme CS121, CS124, qui sont tous deux des cours théoriques,

162
00:09:38,320 --> 00:09:41,300
c'est qu'il ya effectivement quelques problèmes qui existent dans ce monde

163
00:09:41,300 --> 00:09:45,710
que, fondamentalement, aussi loin que nous le savons, ne peuvent être résolus plus vite

164
00:09:45,710 --> 00:09:48,880
que le pire de ces graphiques suggère en fait.

165
00:09:48,880 --> 00:09:53,660
Donc, il ya beaucoup de problèmes ouverts dans ce monde pour faire beaucoup mieux que les humains ont à ce jour.

166
00:09:53,660 --> 00:09:56,130
>> Donc, nous allons commencer puis avec cet exemple.

167
00:09:56,130 --> 00:09:59,650
Nous avons vu Sean lutte avec cet appareil photo, trop maladroitement sur vidéo.

168
00:09:59,650 --> 00:10:05,270
Mais la réalité était quand Sean a été chargé de trouver sur un tableau comme celui-ci au nombre 7,

169
00:10:05,270 --> 00:10:10,300
rappelle que j'ai dit, "Il ya quelque part derrière ces morceaux de papier ou des portes blanches

170
00:10:10,300 --> 00:10:12,570
"Le chiffre 7. Sean, le trouver pour nous."

171
00:10:12,570 --> 00:10:14,200
Et il était extrêmement difficile à regarder

172
00:10:14,200 --> 00:10:15,790
parce qu'il a été vraiment du mal avec ce problème.

173
00:10:15,790 --> 00:10:19,720
Mais la réalité était Sean a fait comme tout le monde dans la salle pourrait avoir fait.

174
00:10:19,720 --> 00:10:21,890
Il a fallu un peu plus d'une personne typique peut avoir,

175
00:10:21,890 --> 00:10:24,760
mais il a supposé qu'il y avait un truc à ce problème,

176
00:10:24,760 --> 00:10:26,590
il a supposé qu'il manquait quelque chose.

177
00:10:26,590 --> 00:10:29,320
Et il n'a pas aidé des centaines d'yeux portaient sur lui.

178
00:10:29,320 --> 00:10:34,250
>> Mais la réalité était si l'entrée au problème est une série de nombres aléatoires

179
00:10:34,250 --> 00:10:37,120
et on vous demande de trouver 1 tel numéro,

180
00:10:37,120 --> 00:10:39,770
le meilleur que vous pouvez faire est de recherche linéaire.

181
00:10:39,770 --> 00:10:44,060
Commencez par la gauche, vers la droite, ou de commencer à droite, vers la gauche.

182
00:10:44,060 --> 00:10:48,300
Rétroactivement, on pourrait penser, «Sean, pourquoi ne pas vous venez de commencer à partir de l'autre extrémité?"

183
00:10:48,300 --> 00:10:52,120
Eh bien, 7 aurait tout aussi bien pu ici au hasard,

184
00:10:52,120 --> 00:10:54,980
mais j'ai délibérément mis là parce que je pensais qu'il ne va pas commencer à la fin.

185
00:10:54,980 --> 00:10:59,320
Donc j'ai un peu manipulé la situation, mais par hasard 7 aurait pu être n'importe où.

186
00:10:59,320 --> 00:11:02,380
Ainsi, à partir de l'extrémité droite aurait pu être mieux alors,

187
00:11:02,380 --> 00:11:04,320
mais que faire si l'an prochain je déménage 7 ailleurs?

188
00:11:04,320 --> 00:11:06,830
Ce n'est pas une solution radicalement nouvelle du problème -

189
00:11:06,830 --> 00:11:10,520
à partir de 1 extrémité ou l'autre - quand vous êtes pas donné d'autres hypothèses.

190
00:11:10,520 --> 00:11:13,620
Donc, Sean a commencé à chercher à travers les chiffres et il dit: «5. Ce n'est pas ici."

191
00:11:13,620 --> 00:11:17,280
Puis il est allé là et j'ai vu 19, puis il s'arrêta pendant environ 20 secondes,

192
00:11:17,280 --> 00:11:22,330
puis il a ouvert ce pour le 13, puis il est devenu évident

193
00:11:22,330 --> 00:11:24,270
qu'il ne semble pas y avoir de modèle ici.

194
00:11:24,270 --> 00:11:28,090
Il n'était pas 1, 2, 3, 4 ou analogue. Il y avait des lacunes dans les chiffres, ce qui n'a pas aidé.

195
00:11:28,090 --> 00:11:32,320
Et aussi, le fait que j'ai utilisé ces pièces bon marché de papier pour couvrir les numéros

196
00:11:32,320 --> 00:11:35,270
est en fait délibérée, parce que si j'ai enlevé tous ces morceaux de papier,

197
00:11:35,270 --> 00:11:38,760
plupart d'entre nous, Sean inclus, aurait probablement regarda sorte de macroscopiquement

198
00:11:38,760 --> 00:11:43,410
au tableau et dit: «Oh, 7 est évidemment juste là." Nous l'avons fait instantanément.

199
00:11:43,410 --> 00:11:46,460
>> Et c'est peut-être la façon dont le cerveau humain fonctionne dans une certaine mesure,

200
00:11:46,460 --> 00:11:50,730
mais en réalité, ses yeux ou de l'esprit est probablement l'écrémage des numéros de droite à gauche,

201
00:11:50,730 --> 00:11:55,190
de gauche à droite, au milieu de sur - quelque chose se passait physiologiquement

202
00:11:55,190 --> 00:11:57,640
de telle sorte que c'était comme cela se passait instantanément,

203
00:11:57,640 --> 00:12:01,360
mais les chances sont encore à l'intérieur il y avait une sorte de méthodologie pour trouver 7.

204
00:12:01,360 --> 00:12:05,160
Et en effet, maintenant que nous parlons de tableaux et structures de données

205
00:12:05,160 --> 00:12:08,780
et à l'intérieur mémoire d'un ordinateur, la seule chose que nous, les humains peuvent faire

206
00:12:08,780 --> 00:12:13,070
est de regarder emplacements de mémoire individuels 1 à la fois.

207
00:12:13,070 --> 00:12:16,600
>> Ainsi, chaque autre endroit pourrait tout aussi bien être couvert avec une feuille de papier

208
00:12:16,600 --> 00:12:21,170
parce que nous ne pouvons pas le voir de toute façon. Nous pouvons seulement faire 1 chose à la fois.

209
00:12:21,170 --> 00:12:25,030
Donc dans ce cas, en cas de Sean, nous y sommes allés et nous avons ici

210
00:12:25,030 --> 00:12:31,040
et puis nous sommes allés ici, ici, ici, ici, a obtenu intelligent d'ici la fin

211
00:12:31,040 --> 00:12:34,450
et juste un peu sauté celui-ci de façon arbitraire et il a trouvé 7.

212
00:12:34,450 --> 00:12:37,470
Celui-ci n'était pas particulièrement spécial. Elle aussi était en panne.

213
00:12:37,470 --> 00:12:39,530
Mais il a finalement trouvé 7.

214
00:12:39,530 --> 00:12:45,360
Mais maintenant, les plats à emporter est vraiment le meilleur que vous pouvez faire quand donné aucune information

215
00:12:45,360 --> 00:12:50,400
autres que les numéros au hasard triés consiste à partir de la gauche ou de la droite commence.

216
00:12:50,400 --> 00:12:54,950
Ou diable, vous pouvez ouvrir des portes au hasard, mais même alors, qu'est-ce que cela signifie d'être aléatoire?

217
00:12:54,950 --> 00:12:57,220
Eh bien, nous aurions en quelque sorte à formaliser ce que cela signifie de commencer ici,

218
00:12:57,220 --> 00:13:01,150
puis aller ici, puis allez ici. Sean a bien fait, et il était juste amusant à regarder.

219
00:13:01,150 --> 00:13:06,340
Et si au lieu nous changeons le problème un peu et faire apparaître Sean cette année, si vous voulez?

220
00:13:06,340 --> 00:13:09,460
Souhaitez-on être à l'aise de monter sur scène et la résolution d'un problème un peu différent

221
00:13:09,460 --> 00:13:12,330
et apparaissant sur l'appareil photo?

222
00:13:12,330 --> 00:13:15,720
>> Allons au-delà de l'orchestre parce que vous les gars ont été très impliqué aujourd'hui déjà.

223
00:13:15,720 --> 00:13:21,430
Que diriez-vous en rose, dans le chapeau? Allez vers le bas. Quel est votre nom? >> Alex. >> Alex. D'accord.

224
00:13:21,430 --> 00:13:24,580
Donc Alex sera Sean cette année et apparaîtra dans les prochaines années

225
00:13:24,580 --> 00:13:27,770
CS50 valeur de conférences.

226
00:13:27,770 --> 00:13:30,340
Alex, ravi de vous rencontrer. >> Ravi de vous rencontrer aussi.

227
00:13:30,340 --> 00:13:33,470
Le défi à portée de main pour vous est que vous avez un peu plus facile

228
00:13:33,470 --> 00:13:38,950
en ce que je vous dis les mêmes numéros sont ici, mais ils sont maintenant triés.

229
00:13:38,950 --> 00:13:41,800
Alors maintenant, votre objectif est de trouver le numéro 7.

230
00:13:41,800 --> 00:13:45,370
Et en fait, nous devrions vraiment faire ceci - Tu es genre de tricherie, comme un ordinateur ne serait pas,

231
00:13:45,370 --> 00:13:47,990
en regardant ce que les chiffres étaient il ya un instant.

232
00:13:47,990 --> 00:13:50,360
Avec de la craie est en fait ce ne va pas aider tant que ça,

233
00:13:50,360 --> 00:13:52,810
mais supposons que vous ne savez pas ce que le tableau original est.

234
00:13:52,810 --> 00:13:56,600
Tout ce que vous savez maintenant, c'est que vous avez un tableau de nombres triés

235
00:13:56,600 --> 00:14:00,360
qui pourrait avoir des écarts entre eux, et votre but est de trouver le numéro 7.

236
00:14:00,360 --> 00:14:05,080
Comment voulez-vous, un être humain raisonnable étant, prendre pour trouver le numéro 7?

237
00:14:05,080 --> 00:14:07,770
>> Aller de bas en haut? Ok >>. Allez faible à élevé.

238
00:14:07,770 --> 00:14:10,990
Et ne pas les déchirer. Disons simplement les relever afin de pouvoir les réutiliser.

239
00:14:10,990 --> 00:14:14,730
Ok, donc 1. Attendez. Avant de continuer, qui était de 1, manifestement erronée.

240
00:14:14,730 --> 00:14:17,270
Donc ce qui se passe dans votre esprit maintenant? Quelle est votre prochaine étape?

241
00:14:17,270 --> 00:14:23,250
Le prochain. Ok >>. Le prochain. Bon. 3, de manière incorrecte. Quelle est votre prochaine étape?

242
00:14:23,250 --> 00:14:27,670
Continuer à avancer. Tous droits >>. Continuer à avancer. 5.

243
00:14:27,670 --> 00:14:31,110
Donc, continuez à aller, et laissez-moi vous remettre ce pour la postérité.

244
00:14:31,110 --> 00:14:35,720
7. >> Excellent. Très bon. Trouvé le numéro 7. [Applaudissements]

245
00:14:35,720 --> 00:14:39,720
Donc, ce qui était bon, mais trop Sean trouvé le numéro 7.

246
00:14:39,720 --> 00:14:44,490
Et je soutiens que vous n'avez pas vraiment exploité cette information supplémentaire,

247
00:14:44,490 --> 00:14:47,780
qui est que ces nombres sont triés.

248
00:14:47,780 --> 00:14:51,520
Ainsi pouvons-nous faire mieux? Toutes les suggestions ici? Oui, à l'arrière.

249
00:14:51,520 --> 00:14:54,710
[L'élève] Recherche binaire. >> Je n'ai aucune idée de ce que recherche binaire est.

250
00:14:54,710 --> 00:14:58,030
>> [L'élève] Commencer au milieu. >> Commencer au milieu. D'accord. Donc, nous allons voir si nous pouvons y arriver.

251
00:14:58,030 --> 00:15:02,580
Donc, si on vous dit au lieu de départ à partir du milieu, aller de l'avant et d'ouvrir la porte du milieu.

252
00:15:02,580 --> 00:15:04,580
Il ya 8 d'entre eux, de sorte que vous allez avoir à choisir arbitrairement le

253
00:15:04,580 --> 00:15:09,800
légèrement vers la gauche ou vers la droite. D'accord. 7! [Applaudissements] Très bien.

254
00:15:09,800 --> 00:15:11,410
D'accord, mais où allions-nous avec ça?

255
00:15:11,410 --> 00:15:14,990
Supposons que pour briser l'égalité que vous aviez commencé ici

256
00:15:14,990 --> 00:15:16,670
parce qu'il est tout aussi pu se passer ainsi.

257
00:15:16,670 --> 00:15:19,540
Nous là juste pour savoir que 7 était là. Donc, c'est 13.

258
00:15:19,540 --> 00:15:21,980
Donc, si ils sont triés et nous avons commencé dans le milieu,

259
00:15:21,980 --> 00:15:24,600
quel serait le prochain mouvement optimal ont été?

260
00:15:24,600 --> 00:15:27,740
Aller à gauche. Et donc voici l'exemple du livre de téléphone de nouveau.

261
00:15:27,740 --> 00:15:30,130
Si 13 est ici et nous savons que la liste est triée,

262
00:15:30,130 --> 00:15:33,900
alors tous ces morceaux de papier sont sans intérêt pour nous maintenant

263
00:15:33,900 --> 00:15:37,400
parce que nous savons déjà que 7 doit être à gauche

264
00:15:37,400 --> 00:15:39,510
si ces nombres sont triés et nous avons trouvé 13.

265
00:15:39,510 --> 00:15:42,500
>> Alors, quel est votre prochain déménagement ici? >> Allez à gauche. >> Très bien.

266
00:15:42,500 --> 00:15:45,080
Alors, allez à gauche, et - attendez, hey, hey, hey. C'est de la triche.

267
00:15:47,140 --> 00:15:51,350
Alors vous avez trouvé 7, mais ce qui est l'algorithme que nous venons d'appliquer?

268
00:15:51,350 --> 00:15:56,450
Commencer au milieu. Bon >>. Alors, quel est le prolongement logique de cette même idée?

269
00:15:56,450 --> 00:15:58,970
Oh, juste pour eux. >> Exactement. >> Je commence donc ici. Bon >>.

270
00:15:58,970 --> 00:16:02,020
Alors maintenant, nous sommes allés un peu à gauche à nouveau. Il est 3.

271
00:16:02,020 --> 00:16:05,310
Mais les plats à emporter est intéressant, c'est maintenant que l'on ne vous pas à vous en soucier?

272
00:16:05,310 --> 00:16:08,040
Ces 2. Ces 2 >>. Alors maintenant, celui-ci peut aller loin, celui-ci peut aller loin.

273
00:16:08,040 --> 00:16:12,330
Maintenant, le problème qui était de 8, puis a été de 4 taille est la taille 2.

274
00:16:12,330 --> 00:16:16,430
Nous recevons assez proche. Encore une fois, allez au milieu de ces 2 éléments.

275
00:16:16,430 --> 00:16:20,430
>> D'accord. Donc, c'est une sorte de malheureux que maintenant nous allons toujours à gauche parce que nous sommes arrondi vers le bas.

276
00:16:20,430 --> 00:16:25,150
Mais c'est bien parce que maintenant nous le jetez et tout le reste, nous laissant avec seulement 7.

277
00:16:25,150 --> 00:16:30,490
Donnons une salve d'applaudissements. Nous avons trouvé 7 fois. [Applaudissements] D'accord. Bien sûr.

278
00:16:30,490 --> 00:16:32,220
Accrochez-vous pour seulement 1 seconde de plus.

279
00:16:32,220 --> 00:16:36,630
Même si ce genre de processus suivant a pris un peu plus longtemps que nous avons pensé qu'il serait,

280
00:16:36,630 --> 00:16:40,150
franchement, vos premiers instincts étaient les meilleurs, pas vrai? Nous avons trouvé 7 instantanément.

281
00:16:40,150 --> 00:16:46,740
Mais nous avons trouvé 7 plus rapide, peu importe ce que, dans cet exemple par rapport à celui-ci

282
00:16:46,740 --> 00:16:50,100
parce que si les numéros sont tous triés, un peu comme les pages d'un annuaire téléphonique,

283
00:16:50,100 --> 00:16:54,580
vous pouvez en effet couper la moitié du problème encore et encore et encore.

284
00:16:54,580 --> 00:16:56,740
Et ce n'est pas tout à fait aussi facile de voir cela avec seulement 8 chiffres

285
00:16:56,740 --> 00:17:00,100
par opposition à un annuaire de 1000 pages où vous avez vraiment le voir visuellement,

286
00:17:00,100 --> 00:17:03,120
mais dans ce cas là quand Sean cherchait 7,

287
00:17:03,120 --> 00:17:06,020
le nombre d'étapes dans le pire des cas, cela aurait-il emporté? >> [L'élève] 7.

288
00:17:06,020 --> 00:17:11,670
7 dans le pire des cas. Eh bien, dans le pire des cas non pas 7 s'il ya 8 portes ici.

289
00:17:11,670 --> 00:17:13,440
Il lui aurait fallu 8 étapes.

290
00:17:13,440 --> 00:17:18,170
>> Donc, si il ya des portes n, il aurait pu prendre Sean il ya quelques années n étapes.

291
00:17:18,170 --> 00:17:21,520
Maintenant, dans votre cas, Alex, étant donné que ces nombres sont triés -

292
00:17:21,520 --> 00:17:25,130
et nous pouvons en déduire ce genre de d'où nous avons été à ce jour dans cette histoire -

293
00:17:25,130 --> 00:17:28,300
quel est le temps d'exécution de l'algorithme plus intelligent Alex

294
00:17:28,300 --> 00:17:30,770
de partir du milieu, puis répéter?

295
00:17:30,770 --> 00:17:36,490
[L'élève] 3. >> Donc, il va y avoir 3, à peu près, si vous allez 8 à 4 à 2 à 1.

296
00:17:36,490 --> 00:17:40,660
Donc 3 étapes ou, plus généralement, c'est à nouveau log n.

297
00:17:40,660 --> 00:17:43,380
Chaque fois que vous réduire de moitié et réduire de moitié et réduire de moitié et réduire de moitié,

298
00:17:43,380 --> 00:17:45,290
c'est une expression de cette idée de log n.

299
00:17:45,290 --> 00:17:48,140
Et pour que vous aurait pris seulement 3 étapes, et elle l'a fait

300
00:17:48,140 --> 00:17:50,890
une fois que nous avons ouvert les portes de réduire de moitié et réduire de moitié,

301
00:17:50,890 --> 00:17:53,770
alors que cela aurait pris quelques Sean 7 ou 8 étapes.

302
00:17:53,770 --> 00:17:56,330
Je vous remercie d'être avec nous cette année. >> Merci. Nice Vous réunion.

303
00:17:56,330 --> 00:18:00,170
Merci à Alex. De même >>. [Applaudissements]

304
00:18:00,170 --> 00:18:02,150
>> Quel est alors l'implication réelle de cette situation?

305
00:18:02,150 --> 00:18:06,050
Maintenant, imaginez que ce n'est pas 8 portes, ce qui, franchement, nous pouvions tous trouver quelque chose

306
00:18:06,050 --> 00:18:10,430
8 portes derrière assez rapidement simplement en déchirant les morceaux de papier et d'aller avec nos instincts.

307
00:18:10,430 --> 00:18:14,430
Mais que faire si il ya un million de portes? Et si c'est 4 milliards portes?

308
00:18:14,430 --> 00:18:19,630
Dans le cas de 4 milliards de portes, vous allez vraiment vouloir aller avec l'algorithme d'Alex,

309
00:18:19,630 --> 00:18:23,150
binaire de recherche que nous allons commencer à l'appeler ou de diviser pour régner, plus généralement,

310
00:18:23,150 --> 00:18:25,220
où vous gardez réduire de moitié et réduire de moitié le problème,

311
00:18:25,220 --> 00:18:30,510
parce que si vous avez 4 milliards portes, combien de fois pouvez-vous couper 4 milliards de moitié?

312
00:18:30,510 --> 00:18:33,870
[L'élève] 32. >> Il s'agit en fait 32. Vous pouvez nous en sortir sur un morceau de papier ou dans votre tête.

313
00:18:33,870 --> 00:18:38,490
Vous allez 4 milliards à 2 milliards to 1 milliard à un demi-milliard, à 250 millions d'euros, point, point, point.

314
00:18:38,490 --> 00:18:41,620
Et si vous faites le calcul, vous allez en effet obtenir 32,

315
00:18:41,620 --> 00:18:44,950
et qui se rapporte effectivement à l'informatique car nous avons l'habitude de compter des puissances de 2.

316
00:18:44,950 --> 00:18:47,600
2 à la 32 arrive à être de 4 milliards d'euros.

317
00:18:47,600 --> 00:18:51,440
Donc, il ya beaucoup d'intérêt pour ce genre de puissances de 2 en informatique.

318
00:18:51,440 --> 00:18:55,120
>> Mais qu'est-ce environ 8 milliards? Combien de pas est ce que cela va prendre s'il ya 8 milliards portes?

319
00:18:55,120 --> 00:19:00,350
[L'élève] 33. Alors >> 33. Et s'il y avait 16 milliards portes? Combien de pas est ce que cela va prendre?

320
00:19:00,350 --> 00:19:05,020
[L'élève] 34. >> 34. Nous pourrions poursuivre ce genre d'ad nauseam. Mais c'est une chose puissante.

321
00:19:05,020 --> 00:19:09,430
Vous pouvez introduire des milliards de plus d'entrées à votre problème, mais pas une grosse affaire,

322
00:19:09,430 --> 00:19:14,140
vous venez de prendre 1 morceau supplémentaire hors de lui et nous donne ainsi quelque chose comme binaire de recherche

323
00:19:14,140 --> 00:19:15,920
ou diviser pour régner, plus généralement.

324
00:19:15,920 --> 00:19:17,990
Mais je suis un peu tricher ici, non?

325
00:19:17,990 --> 00:19:22,410
Dans le cas de l'algorithme d'Alex, elle avait un avantage sur Sean.

326
00:19:22,410 --> 00:19:27,780
Elle savait que ces chiffres ont été triés, mais Alex ne pas avoir à les trier elle-même.

327
00:19:27,780 --> 00:19:30,520
J'ai l'avance est venu vers le tableau noir et la nature des assurés

328
00:19:30,520 --> 00:19:33,670
que j'ai dessiné les tous dans un ordre trié, puis je les ai recouvertes de papier.

329
00:19:33,670 --> 00:19:35,850
Mais combien de travail cela s'est-il me prendre?

330
00:19:35,850 --> 00:19:40,110
Si nous avions commencé avec ces numéros dans un ordre apparemment aléatoire -

331
00:19:40,110 --> 00:19:43,320
dans ce cas, ces chiffres simples, 1 à 8 ici -

332
00:19:43,320 --> 00:19:46,090
comment pouvons-nous aller sur le tri de ces valeurs?

333
00:19:46,090 --> 00:19:52,530
Si vous étiez un homme chargé de cette tâche, ce type d'approche intuitive prendriez-vous

334
00:19:52,530 --> 00:19:54,800
pour trier un tas de chiffres?

335
00:19:54,800 --> 00:19:57,050
Ces choses ont été présentés comme des pièces de puzzle. Ouais.

336
00:19:57,050 --> 00:19:59,950
>> [Étudiants] je prendrais chaque numéro et de le comparer à chacun

337
00:19:59,950 --> 00:20:03,180
et continuez vers la gauche. >> Très bien.

338
00:20:03,180 --> 00:20:05,720
Alors, prenez chaque numéro, de le comparer à celui à côté de lui,

339
00:20:05,720 --> 00:20:09,610
et puis juste continuer à avancer le long de la liste, le type de rejiggering choses que vous allez.

340
00:20:09,610 --> 00:20:13,800
Nous avons donc ici une chance pour peut-être un peu plus les gens à s'impliquer.

341
00:20:13,800 --> 00:20:16,290
Avons-nous plus de 8 volontaires qui aimeraient venir?

342
00:20:16,290 --> 00:20:23,950
Un peu moins de pression puisque vous n'êtes pas le seul. 1, 2, 3, 4, 5, 6, 7, 8.

343
00:20:23,950 --> 00:20:28,190
Allez vers le bas. Les gars, vous allez être les numéros 1 à 8.

344
00:20:28,190 --> 00:20:36,050
Voyons voir si nous ne pouvons pas faire ce tri pour Alex beaucoup de la même manière que je l'ai fait à l'avance.

345
00:20:36,050 --> 00:20:37,640
1, 2, 3, 4.

346
00:20:37,640 --> 00:20:40,760
Allez-y et si vous voulez, s'alignent sur scène entre le pupitre et moi ici

347
00:20:40,760 --> 00:20:44,960
dans le même ordre que la diapositive à l'écran.

348
00:20:47,910 --> 00:20:49,680
Uh-oh.

349
00:20:50,370 --> 00:20:53,230
Nous allons vous travaillez dans l'exemple suivant. Oh, attendez, attendez. Nous y voilà. Attendez.

350
00:20:53,230 --> 00:20:57,570
L'exemple suivant est maintenant. Ici vous allez. Numéro 8. Venez sur place.

351
00:20:57,570 --> 00:21:00,270
Très bien. Trier selon vous-mêmes à ce sujet.

352
00:21:00,270 --> 00:21:03,620
Faites glisser un peu sur le côté de la musique se trouvent ici.

353
00:21:03,620 --> 00:21:12,310
Nous avons donc 4, 2, 6 - entrer là, par ici, juste là - 3.

354
00:21:12,310 --> 00:21:17,570
Ouais. D'accord. Vous aller là-bas. Non, vous restez là.

355
00:21:17,570 --> 00:21:21,840
Ouais, juste là. Non, je me trompe. Juste là. Bon, très bien. D'accord.

356
00:21:21,840 --> 00:21:24,930
Alors maintenant, nous allons les trier dans un ordre croissant.

357
00:21:24,930 --> 00:21:26,210
>> Comment puis-je m'y prendre?

358
00:21:26,210 --> 00:21:28,630
L'algorithme qui a été proposé il ya un instant pourquoi ne pas simplement comparer

359
00:21:28,630 --> 00:21:31,970
les gens qui sont un peu à côté de l'autre, puis corriger les erreurs,

360
00:21:31,970 --> 00:21:33,540
se déplaçant de gauche à droite.

361
00:21:33,540 --> 00:21:36,580
Nous avons donc ici 4 et 2, manifestement hors de l'ordre. Laissez vous échanger. D'accord.

362
00:21:36,580 --> 00:21:40,760
Alors maintenant, je vais passer à la ligne. 4 et 6, nope. [Rires]

363
00:21:40,760 --> 00:21:45,010
6 et 8, très bon. 8 et 1, permettez-moi de vous échanger les gars. Très bien.

364
00:21:45,010 --> 00:21:48,030
Donc, 8 et 3, échangez-vous les gars.

365
00:21:48,030 --> 00:21:52,280
8 et 7, permettez-moi de vous échanger les gars. 5 et 8, excellente.

366
00:21:52,280 --> 00:21:54,820
Je vous donne une liste triée.

367
00:21:54,820 --> 00:21:56,860
Très bien. Donc, pas tout à fait.

368
00:21:56,860 --> 00:22:01,180
Mais il vaut mieux parce que le nombre de cas plus importants - au point 8 -

369
00:22:01,180 --> 00:22:04,030
ont sorte de bouillonnait de la gauche vers la droite.

370
00:22:04,030 --> 00:22:08,010
Alors, j'ai fait 1 d'entre eux le droit, mais il se sent comme cela ne résout pas complètement le problème.

371
00:22:08,010 --> 00:22:11,150
>> Alors, que proposez-vous nous faire maintenant? >> [L'élève] Continuer à le faire. >> Nous vous continuez à le faire.

372
00:22:11,150 --> 00:22:13,740
Et se rendre compte, encore une fois, nous avons mis les choses juste en ayant tous les êtres humains

373
00:22:13,740 --> 00:22:17,180
sorte d'intelligence s'organisent en fonction de cette image,

374
00:22:17,180 --> 00:22:19,040
mais maintenant nous devons être beaucoup plus méthodique.

375
00:22:19,040 --> 00:22:21,510
Nous devons être algorithmique à ce sujet, comme si nous écrivons le code -

376
00:22:21,510 --> 00:22:23,520
dans ce cas, pseudo-verbale.

377
00:22:23,520 --> 00:22:26,040
Permettez-moi donc essayer de nouveau. Cela a plutôt bien fonctionné. Il n'a pas le résoudre.

378
00:22:26,040 --> 00:22:30,400
Mais quand il doute, essayez et essayez à nouveau. Donc, 2 et 4, ne plus l'aider.

379
00:22:30,400 --> 00:22:33,200
4 et 6. Ah! 6 et 1, soit un peu mieux maintenant.

380
00:22:33,200 --> 00:22:39,740
6 et 3, c'est bien. 6 et 7, 7 et 5, 7 et 8, bien.

381
00:22:39,740 --> 00:22:44,060
Et vous savez, je peux probablement ignorer 8 maintenant parce qu'il est à la fin de la liste.

382
00:22:44,060 --> 00:22:47,250
Peut-être que nous n'avons pas à vous inquiéter au sujet de quelqu'un en passant devant lui.

383
00:22:47,250 --> 00:22:49,240
Mais attendons de voir si c'est une hypothèse fort.

384
00:22:49,240 --> 00:22:52,340
Maintenant, la liste est - putain - pas triée. Essayons encore une fois.

385
00:22:52,340 --> 00:22:56,440
SO 2 et 4, 4 et 1, 4 et 3.

386
00:22:56,440 --> 00:22:59,230
4 et 6, bon. 6 et 5, très bien.

387
00:22:59,230 --> 00:23:04,890
6, 7, et 8, bien. Mais remarquez, je peux juste m'arrêter là maintenant et arrêter ici maintenant?

388
00:23:04,890 --> 00:23:07,770
[L'élève] Oui. Ouais >>?

389
00:23:07,770 --> 00:23:11,160
Que faire si l'un de vous avait été le numéro 9 tout le chemin là-bas?

390
00:23:11,160 --> 00:23:13,640
Il aurait été triés. Bon >>. Il aurait été triés pour la première fois autour.

391
00:23:13,640 --> 00:23:16,050
Bon. Donc, revenons à nouveau. Nous y sommes presque.

392
00:23:16,050 --> 00:23:22,800
1 et 2, 2 et 3, 3 et 4, 4 et 5, 5 et 6, 6 et 7, 7 et 8.

393
00:23:22,800 --> 00:23:26,640
>> Je fait maintenant, mais, encore une fois, je suis un ordinateur qui ne peut faire ce qu'on me dit de faire,

394
00:23:26,640 --> 00:23:30,120
et je me souviens que c'est maintenant que je fait juste fait un peu de travail.

395
00:23:30,120 --> 00:23:31,700
Quelque chose a changé ici.

396
00:23:31,700 --> 00:23:37,100
Je n'ai donc pas techniquement confirmé visuellement ou algorithmiquement que cette liste est bien triée.

397
00:23:37,100 --> 00:23:40,720
Donc, pour faire bonne mesure, juste pour être anale à ce sujet, nous allons faire cette fois-1 plus.

398
00:23:40,720 --> 00:23:44,040
Si 1 et 2, 2 et 3, 3 et 4. Et vous savez quoi?

399
00:23:44,040 --> 00:23:46,190
Pour faire bonne mesure, je vais garder la trace de ma main cette fois

400
00:23:46,190 --> 00:23:51,110
combien de swaps je fais tout pour que je sache combien de travail que j'ai fait en réalité.

401
00:23:51,110 --> 00:23:56,930
3 et 4, 4 et 5, 5 et 6, 6 et 7, 7 et 8. Pas de swaps.

402
00:23:56,930 --> 00:24:00,800
Alors maintenant, je légitimement être idiot pour faire cela à nouveau

403
00:24:00,800 --> 00:24:03,330
parce que si je le faisais pas de travail à travers ce passage des êtres humains,

404
00:24:03,330 --> 00:24:06,710
il est clair que cela va se reproduire si aucun d'entre eux est une sorte de hasard

405
00:24:06,710 --> 00:24:10,410
contradictoirement se déplacer. Alors maintenant, je peux m'arrêter.

406
00:24:10,410 --> 00:24:15,120
Maintenant, nous allons poser la question, combien de travail cela at-il réellement me prendre?

407
00:24:15,120 --> 00:24:18,260
Combien d'étapes ne prendrait-il? N >> carré.

408
00:24:18,260 --> 00:24:20,400
Ouais, donc n carré. Où trouvez-vous n carré de?

409
00:24:20,400 --> 00:24:22,660
Vous devez vérifier chaque numéro -

410
00:24:22,660 --> 00:24:26,530
Il ya un nombre n, et vous devez vérifier chaque numéro avec les nombres n d'autres.

411
00:24:26,530 --> 00:24:29,030
Bon. >> Donc ça n carré. Bon >>.

412
00:24:29,030 --> 00:24:31,060
>> Ainsi, il se sent comme il pourrait très bien être n carré, non?

413
00:24:31,060 --> 00:24:33,820
Il est n de ces gars-là, 8 précisément dans ce cas,

414
00:24:33,820 --> 00:24:37,590
mais chaque fois que je suis passé par cette liste, je comparais la première personne contre le second,

415
00:24:37,590 --> 00:24:39,650
le deuxième contre le troisième, encore et encore et encore,

416
00:24:39,650 --> 00:24:42,450
et quand je suis arrivé à la fin, qu'est-ce que je dois faire? Je l'ai refait.

417
00:24:42,450 --> 00:24:46,280
Donc, si nous généralisons cette explication, nous avons n personnes

418
00:24:46,280 --> 00:24:51,090
et je fais, évidemment, 8 étapes, n étapes, chaque fois que je passe par cet algorithme.

419
00:24:51,090 --> 00:24:56,070
Mais combien de fois dans le pire des cas, puis-je avoir à passer par cette liste de personnes?

420
00:24:56,070 --> 00:24:59,370
[L'élève] N fois. Probablement >> n, à droite, parce que dans le pire des cas,

421
00:24:59,370 --> 00:25:03,410
ce qui est probablement le pire des cas arrangement de ces gars de l'obtenir-aller?

422
00:25:03,410 --> 00:25:06,520
Si elles sont complètement inversé l'ordre

423
00:25:06,520 --> 00:25:09,310
parce que juste suppose que mentalement, let's - Quel est ton nom? >> Bowen.

424
00:25:09,310 --> 00:25:12,510
Bowen. D'accord. Donc Bowen, viens par ici pendant un moment.

425
00:25:12,510 --> 00:25:16,150
>> Supposons que Bowen était là au début de l'algorithme,

426
00:25:16,150 --> 00:25:19,790
et nous ne savons pas ce que tout le monde l'est, mais Bowen ici, selon cet algorithme -

427
00:25:19,790 --> 00:25:23,820
et si vous voulez simplement vous promener avec moi - va bouillonner, comme il l'a fait la première fois,

428
00:25:23,820 --> 00:25:25,740
tout le chemin vers la fin.

429
00:25:25,740 --> 00:25:29,400
Mais supposons que la personne à côté de Bowen était le numéro 7.

430
00:25:29,400 --> 00:25:33,450
Je dois revenir en arrière et obtenir le numéro 7, ce qui signifie que je dois y aller tout le chemin de retour ici.

431
00:25:33,450 --> 00:25:36,980
Maintenant, je dois avoir cette balade même avec la personne qui est le numéro 7.

432
00:25:36,980 --> 00:25:40,140
Mais que faire si ensuite le numéro 6 était à côté de lui aussi?

433
00:25:40,140 --> 00:25:42,180
Ensuite, je dois revenir en arrière et obtenir 6.

434
00:25:42,180 --> 00:25:46,490
Encore une fois, à chaque itération de cette boucle je parle à chacun des n personnes,

435
00:25:46,490 --> 00:25:50,090
et je pourrais avoir à faire n de ces promenades pour m'assurer que je suis en tirant

436
00:25:50,090 --> 00:25:53,760
tous les grands éléments de dos et d'avant en arrière jusqu'à la fin de la liste.

437
00:25:53,760 --> 00:25:58,230
Tant de choses n n fois est à n fois n ou n carrés.

438
00:25:58,230 --> 00:26:02,050
>> Donc ici nous avons déjà un algorithme qui n'est plus n, ce n'est plus log n,

439
00:26:02,050 --> 00:26:04,820
c'est en fait pire que tout ce que nous avons fait auparavant.

440
00:26:04,820 --> 00:26:09,840
Donc genre de Alex eu de la chance dans ce que j'ai fait tout le travail apparemment à l'avant pour elle,

441
00:26:09,840 --> 00:26:14,690
l'ensemble des travaux coûteux, de sorte qu'elle puisse profiter de cet algorithme de recherche binaire,

442
00:26:14,690 --> 00:26:16,420
qui est log n.

443
00:26:16,420 --> 00:26:18,240
Mais ce qui est cohérent avec le thème de lundi.

444
00:26:18,240 --> 00:26:23,260
Nous avons donné un peu plus d'espace, nous avons utilisé plus de bits, afin d'accélérer notre temps de course.

445
00:26:23,260 --> 00:26:26,170
Donc, un peu comme il ya ce compromis entre le temps et l'espace,

446
00:26:26,170 --> 00:26:31,060
il pourrait aussi bien être compromis entre le temps passé en sorte avant de faire les choses prêt à aller

447
00:26:31,060 --> 00:26:35,000
et fait exécuter un algorithme comme la recherche. Essayons une autre.

448
00:26:35,000 --> 00:26:39,050
Si vous les gars ne me dérangerait pas juste rapidement réorganiser pour correspondre à ce que vous encore,

449
00:26:39,050 --> 00:26:42,240
nous allons essayer quelque chose de légèrement différent, où ce n'est pas tout à fait aussi simple

450
00:26:42,240 --> 00:26:45,760
comme on vient de corriger toutes les erreurs par paires, ce qui est super intuitive.

451
00:26:45,760 --> 00:26:48,150
Disons plutôt être un peu plus délibéré et le faire.

452
00:26:48,150 --> 00:26:51,010
Celui-ci aussi je vous propose est sans doute assez intuitive.

453
00:26:51,010 --> 00:26:55,070
>> Choisissons la plus petite personne de la liste encore et encore. Alors on y va.

454
00:26:55,070 --> 00:26:57,350
4, vous êtes la plus petite personne, j'ai donc vu jusqu'à présent,

455
00:26:57,350 --> 00:27:00,520
donc je vais mentalement rappeler que simplement en pointant sur vous pour l'instant.

456
00:27:00,520 --> 00:27:05,020
2. Ooh! Oubliez le numéro 4. Je viens de trouver le plus petit élément nouveau dans cette liste.

457
00:27:05,020 --> 00:27:07,410
Je vais genre de souvenir. 6, 8.

458
00:27:07,410 --> 00:27:11,190
Ooh! 1. Au revoir. Alors maintenant, je vais rappeler le numéro 1.

459
00:27:11,190 --> 00:27:14,790
Nous savons que 1 est le plus petit, mais je suis l'ordinateur. Que faire si il ya un 0?

460
00:27:14,790 --> 00:27:17,140
Que faire si il ya un -1? Je dois continuer.

461
00:27:17,140 --> 00:27:20,990
Donc, 3, 7, 5, nope. D'accord. Donc, le numéro 1 est la plus faible.

462
00:27:20,990 --> 00:27:23,640
Laissez-moi vous sélectionnez dans la liste - nous allons aller de cette façon -

463
00:27:23,640 --> 00:27:27,760
et vous mettre arbitrairement au début de la liste.

464
00:27:27,760 --> 00:27:29,740
Maintenant, attendez une minute. J'ai un peu triché.

465
00:27:29,740 --> 00:27:34,010
Si ces gars-là ne représentent pas une liste de 8 personnes, mais un tableau,

466
00:27:34,010 --> 00:27:37,050
8 gros morceaux de mémoire contiguë - ça vous dérange pas en arrière pour un instant?

467
00:27:37,050 --> 00:27:39,060
Il ya en fait pas de place pour vous ici.

468
00:27:39,060 --> 00:27:41,840
Alors, comment pouvons-nous faire de la place pour - quel est votre nom? >> Sammy. >> Sammy.

469
00:27:41,840 --> 00:27:43,710
Comment pouvons-nous faire de la place pour Sammy?

470
00:27:43,710 --> 00:27:46,760
>> Nous nous déplaçons les n qui sont devant moi. Ok >>.

471
00:27:46,760 --> 00:27:48,850
Donc, nous pourrions déplacer les n personnes qui sont devant lui,

472
00:27:48,850 --> 00:27:52,400
donc si vous voulez les gars de prendre 1 délibéré, étape spectaculaire vers la gauche.

473
00:27:52,400 --> 00:27:57,000
Ils ont tous fait cela à l'unisson, mais la dernière fois que j'ai écrit un peu de code,

474
00:27:57,000 --> 00:27:59,740
vous ne pouvez pas trier de passer beaucoup de choses à la fois.

475
00:27:59,740 --> 00:28:02,450
On pourrait le faire dans une boucle, une fois en mouvement tout le monde à la fois.

476
00:28:02,450 --> 00:28:04,340
Donc, si vous les gars ne me dérangerait pas en reculant vers la droite,

477
00:28:04,340 --> 00:28:07,230
et Sammy, si vous pouviez revenir en arrière, car il n'y a toujours pas de place pour vous,

478
00:28:07,230 --> 00:28:11,420
Maintenant, nous allons le faire. Où était Sammy il ya un instant? Juste là.

479
00:28:11,420 --> 00:28:16,140
Il ya donc une lacune. Ainsi, vous pouvez déplacer dans l'angle de Sammy.

480
00:28:16,140 --> 00:28:20,580
Maintenant personne suivante et maintenant personne suivante, maintenant personne suivante. Maintenant, nous avons la place pour Sammy.

481
00:28:20,580 --> 00:28:23,490
Maintenant, quelqu'un dans le public - ce qui était bon, que c'était exact,

482
00:28:23,490 --> 00:28:27,070
cela faisait un peu de temps - ce qui est plus rapide? Ouais.

483
00:28:27,070 --> 00:28:29,440
[L'élève] Un nouveau tableau? >> Qu'est-ce que c'est? >> [L'élève] Un nouveau tableau? >> Très bien.

484
00:28:29,440 --> 00:28:33,200
>> Donc compatible avec cette idée de juste compromis, pourquoi ne pas simplement faire un nouveau tableau

485
00:28:33,200 --> 00:28:36,570
 puis Sammy nagera dans l'espace en face de ces personnes, par exemple,

486
00:28:36,570 --> 00:28:39,600
et nous pouvons commencer à remplir un nouveau tableau tout à fait. Cela aussi pourrait fonctionner.

487
00:28:39,600 --> 00:28:42,450
Mais je ne suis pas intéressé à passer plus de place aujourd'hui. Ce qui est une autre approche?

488
00:28:42,450 --> 00:28:46,630
[L'élève] Swap. Ok >>. Nous pourrions simplement échanger ces 2 gars. Quel est ton nom?

489
00:28:46,630 --> 00:28:49,390
Mario. Mario >>. Alors Mario, vous étiez en train ici.

490
00:28:49,390 --> 00:28:52,480
Sammy, tu peux revenir en arrière un instant? Mario était là.

491
00:28:52,480 --> 00:28:55,830
Nous n'avons pas de place pour toi plus, donc si vous ne me dérangerait pas aller là où Sammy est,

492
00:28:55,830 --> 00:29:02,430
nous allons mettre Sammy ici, et maintenant, je dirais que le fonctionnement échange de Sammy était beaucoup plus rapide.

493
00:29:02,430 --> 00:29:06,370
Nous avons fait 1 opération d'échanger ces gars-là, ou peut-être 2 à échanger ces gars-là,

494
00:29:06,370 --> 00:29:11,210
mais nous n'avons pas fait 1, 2, 3, 4, de sorte que se sent mieux. Maintenant, attendez une minute.

495
00:29:11,210 --> 00:29:14,660
J'ai en quelque sorte fait qu'aggraver le problème, car le numéro 4 était un peu proche du début.

496
00:29:14,660 --> 00:29:19,470
Maintenant, numéro 4 est un peu plus près à cette fin, mais je ne sais pas vraiment ou égal.

497
00:29:19,470 --> 00:29:23,330
Donc, c'est juste la malchance que le numéro 4 est un peu plus loin de son lieu de destination.

498
00:29:23,330 --> 00:29:25,110
Donc, nous allons maintenant répéter cet algorithme.

499
00:29:25,110 --> 00:29:28,410
>> Pour résumer, aussi longtemps que cette histoire était tout ce que nous n'avons été marcher dans la liste

500
00:29:28,410 --> 00:29:31,130
à la recherche de la plus petite personne numérotées.

501
00:29:31,130 --> 00:29:34,530
Alors maintenant, nous allons le faire à nouveau. Nous n'avons pas à vous soucier de Sammy plus.

502
00:29:34,530 --> 00:29:37,590
On peut juste aller ici. Ooh! Numéro 2. C'est un chiffre assez faible.

503
00:29:37,590 --> 00:29:41,180
6, 8, 4, 3, 7, 5. Bon, très bien.

504
00:29:41,180 --> 00:29:43,770
Et heureusement, par hasard, je n'ai pas à déplacer - >> Willie.

505
00:29:43,770 --> 00:29:45,910
Willie parce qu'il est à sa place en ce moment.

506
00:29:45,910 --> 00:29:48,110
Faisons-le encore une fois et ignorer ces 2 gars.

507
00:29:48,110 --> 00:29:50,460
6. C'est un chiffre assez faible. Ooh! 8 est certainement plus grand.

508
00:29:50,460 --> 00:29:53,410
4. Concentrons-nous sur 4. Ooh! 3 est encore mieux.

509
00:29:53,410 --> 00:29:58,290
7 et 5. Alors, que faisons-nous maintenant avec - >> Roger. >> Roger?

510
00:29:58,290 --> 00:30:00,250
Nous allons lui échanger avec le numéro 6.

511
00:30:00,250 --> 00:30:03,570
Donc, si 6 et 3 aimerait échanger,

512
00:30:03,570 --> 00:30:07,320
nous avons maintenant obtenu sorte de la chance que 6 est plus proche de l'endroit où elle devrait être,

513
00:30:07,320 --> 00:30:10,300
mais c'est juste une coïncidence ici. Donc, nous allons maintenant passer ici.

514
00:30:10,300 --> 00:30:13,430
8 est un nombre assez petit. Ooh! 4 est plus petite.

515
00:30:13,430 --> 00:30:17,130
6, 7, 5. Que devons-nous faire maintenant? Swap >>. >> Exactement.

516
00:30:17,130 --> 00:30:19,010
Alors maintenant, nous allons faire ce genre de rapide.

517
00:30:19,010 --> 00:30:24,460
8, 6, 7, 5. D'où vient 5 aller? Bon. D'accord.

518
00:30:24,460 --> 00:30:28,380
6, 7, 8. 6 obtient de rester là où elle est. Quel est ton nom? >> Rosalie.

519
00:30:28,380 --> 00:30:31,770
Rosalie arrive à rester où elle est. 7 doit à - Voyons voir. 7, 8. D'accord.

520
00:30:31,770 --> 00:30:35,100
Donc 7 arrive à rester où elle est. Quel est ton nom? Amna >>. Amna >>.

521
00:30:35,100 --> 00:30:39,670
>> Donc, Amna arrive à rester où elle est, et le numéro 8 est déjà là où il devrait maintenant être.

522
00:30:39,670 --> 00:30:43,960
Bon, très bien. Se sent comme nous ne faisons que créer du travail pour nous-mêmes ici, cependant.

523
00:30:43,960 --> 00:30:47,440
Quel est finalement le temps d'exécution de cet algorithme?

524
00:30:47,440 --> 00:30:51,900
Si l'on pense à ces gens pas comme 8, mais en tant que n? >> C'est n.

525
00:30:51,900 --> 00:30:55,440
Il est n étapes, mais nous vérifions à chaque fois.

526
00:30:55,440 --> 00:30:57,570
D'accord. N, mais que vous vérifiez à chaque fois?

527
00:30:57,570 --> 00:31:03,450
D'accord, mais si elle est n étapes, je ne devrais pas avoir pu vous triez simplement en allant 1, 2, 3, 4?

528
00:31:03,450 --> 00:31:05,590
Oh! D'accord, c'est une grosse différence.

529
00:31:05,590 --> 00:31:08,050
Donc n carré pourquoi? Qu'est-ce qui se passe réellement?

530
00:31:08,050 --> 00:31:12,130
Il ya n personnes dans cette liste, mais pour trouver la plus petite personne dans la liste

531
00:31:12,130 --> 00:31:16,200
dans le pire des cas, combien de démarches dois-je prendre? N. >>

532
00:31:16,200 --> 00:31:19,160
>> N, à droite, parce que dans le pire des cas, le numéro 1 est tout le chemin là-bas,

533
00:31:19,160 --> 00:31:20,990
donc je dois aller le chercher ou elle.

534
00:31:20,990 --> 00:31:25,500
Et puis, quand je me suis finalement rendu compte 1 était le plus petit, puis il est assez rapide pour les échanger.

535
00:31:25,500 --> 00:31:28,450
Mais maintenant, je dois commencer par le début et chercher qui?

536
00:31:28,450 --> 00:31:31,980
La personne la plus petite suivante, qui est de 2. Lorsque, dans le pire des cas est de 2?

537
00:31:31,980 --> 00:31:34,320
Oh, mon Dieu. C'est tout le chemin là-bas à la fin.

538
00:31:34,320 --> 00:31:37,000
Alors maintenant, je viens de faire un autre n étapes, un autre des étapes n.

539
00:31:37,000 --> 00:31:41,200
Et si nous avons des gens n et dans le pire des cas, la personne est plus petit n quelques pas,

540
00:31:41,200 --> 00:31:45,230
c'est encore n fois n, et nous avons à nouveau n carré.

541
00:31:45,230 --> 00:31:47,280
Ce ne se sent pas bien.

542
00:31:47,280 --> 00:31:52,150
Et en fait, même dans le meilleur des cas - supposer qu'ils commencent triés -

543
00:31:52,150 --> 00:31:59,080
combien d'étapes faut-il pour moi en utilisant cet algorithme pour trier ces personnes n?

544
00:31:59,080 --> 00:32:01,010
N au carré. >> J'ai entendu n carré. Pourquoi n au carré?

545
00:32:01,010 --> 00:32:05,240
Parce que vous avez encore à vérifier à chaque fois. Ouais >>.

546
00:32:05,240 --> 00:32:08,060
Et vous devez les échanger. >> Même si nous, les humains sont des sortes de omniscient

547
00:32:08,060 --> 00:32:10,770
dans le sens visuel que nous pouvons juste une sorte de voir que ce sont triés,

548
00:32:10,770 --> 00:32:12,140
un ordinateur n'est pas si malin.

549
00:32:12,140 --> 00:32:14,040
Il va regarder ici et ici et ici,

550
00:32:14,040 --> 00:32:16,610
mais si ce qu'il cherche le plus petit élément,

551
00:32:16,610 --> 00:32:22,110
vous ne savez que vous avez trouvé le plus petit élément de ce moment-là? Une fois que vous êtes à la fin.

552
00:32:22,110 --> 00:32:25,880
Mais à ce stade, vous avez trouvé que le plus petit élément pour le moment.

553
00:32:25,880 --> 00:32:28,810
Vous ne savez pas nécessairement quoi que ce soit d'autre au sujet de l'état du monde.

554
00:32:28,810 --> 00:32:30,880
Donc, il faut aller encore et encore et encore.

555
00:32:30,880 --> 00:32:34,880
>> Alors cette fois je ne regarde muet parce que je vérifie, d'accord, 2, tu es le plus petit,

556
00:32:34,880 --> 00:32:37,530
mais je ne sais pas qui, au total encore.

557
00:32:37,530 --> 00:32:41,090
3, 4, 5, 6, 7, 8. Bon, très bien. 2 était bien plus petit.

558
00:32:41,090 --> 00:32:43,150
Maintenant, nous allons trouver le plus petit côté. D'accord.

559
00:32:43,150 --> 00:32:48,350
3, vous êtes actuellement le plus petit. Voyons voir. 4, 5, 6, 7, 8. Bon, encore une fois eu de la chance.

560
00:32:48,350 --> 00:32:53,170
3 était bien au bon endroit. Mais je vais continuer à le faire encore et encore et encore.

561
00:32:53,170 --> 00:32:55,990
Comment pouvons-nous faire un tant soit peu mieux?

562
00:32:55,990 --> 00:33:00,120
Au lieu d'avoir les gens paires de bulles du plus petit au plus grand à

563
00:33:00,120 --> 00:33:04,350
et au lieu d'aller d'avant en arrière dans la liste des choix de la personne la plus petite, puis,

564
00:33:04,350 --> 00:33:09,780
pourquoi ne pas insérer à la place de ces personnes dans une étape nouvelle liste par étape?

565
00:33:09,780 --> 00:33:13,080
Essayons ceci. Maintenant laissez-moi appeler cette chose tri par insertion.

566
00:33:13,080 --> 00:33:17,250
Nous voici donc ici. Numéro 1. Je ne se soucie pas de n'importe qui d'autre dans cette liste.

567
00:33:17,250 --> 00:33:21,310
Mon objectif maintenant est de mettre le numéro 1 au début d'une liste triée.

568
00:33:21,310 --> 00:33:23,910
Et je vais proposer puisque je n'ai que 8 gros morceaux de la mémoire,

569
00:33:23,910 --> 00:33:28,670
arbitrairement en ce moment je suis le mur entre ma liste de soi-disant non triés,

570
00:33:28,670 --> 00:33:32,740
et toute personne qui est derrière moi, je vais la revendication est triée.

571
00:33:32,740 --> 00:33:34,680
Nous avons donc maintenant le numéro 1.

572
00:33:34,680 --> 00:33:39,240
Je veux l'insérer dans ma liste triée, donc je vais juste passer mon mur ici,

573
00:33:39,240 --> 00:33:43,930
et maintenant je prétends que cette liste est triée, cette liste n'est pas triée - du moins pour autant que je sache.

574
00:33:43,930 --> 00:33:46,070
Je ne peux pas voir tous les numéros à la fois.

575
00:33:46,070 --> 00:33:49,000
>> Maintenant, il m'arrive de rencontrer le numéro 2. Que dois-je faire de lui?

576
00:33:49,000 --> 00:33:54,380
Je vous insérez maintenant dans la liste triée. Mais remarquez avec quelle facilité ce que c'était.

577
00:33:54,380 --> 00:33:59,650
Je viens de regarder. Le numéro 1 est là. Oh, bien sûr 2 passe à côté du numéro 1.

578
00:33:59,650 --> 00:34:03,700
Maintenant que dois-je faire avec 3? Je vous insérer dans la liste triée. Mais c'était super facile.

579
00:34:03,700 --> 00:34:07,250
C'est super facile, c'est super facile, c'est super facile, super facile, super facile.

580
00:34:07,250 --> 00:34:12,790
Et maintenant, tout est trié derrière moi, et combien d'étapes ne prendrait-il?

581
00:34:12,790 --> 00:34:15,620
[Étudiants] N. >> Donc, c'est seulement n. Nous avons été chanceux.

582
00:34:15,620 --> 00:34:18,860
Ce n'est que n pourquoi? >> [L'élève] Parce que la liste a été triée.

583
00:34:18,860 --> 00:34:21,630
La liste est déjà triée. Nous avons donc eu de la chance.

584
00:34:21,630 --> 00:34:25,639
Mais nous avons conçu un algorithme qui exploite cette fois ce genre de chance,

585
00:34:25,639 --> 00:34:29,420
que le meilleur des cas, de ne pas perdre de temps inutilement.

586
00:34:29,420 --> 00:34:31,750
Donc, nous avons maintenant ce que nous appellerons sortes de bulles

587
00:34:31,750 --> 00:34:33,949
où les gens sorte de bulle jusqu'à deux à deux.

588
00:34:33,949 --> 00:34:38,100
Nous avons maintenant tri par sélection où nous arracher la plus petite personne encore et encore.

589
00:34:38,100 --> 00:34:42,350
Et maintenant nous avons le tri par insertion où l'on sorte de façon proactive mettre les gens là où ils appartiennent

590
00:34:42,350 --> 00:34:45,000
dans une liste triée de plus en plus.

591
00:34:45,000 --> 00:34:49,679
Si nous pouvions, une salve d'applaudissements pour ces gars ici. [Applaudissements]

592
00:34:49,679 --> 00:34:52,310
Prenons notre 5 minutes de pause ici.

593
00:34:52,310 --> 00:34:55,139
Et quand nous reviendrons, nous ferons sauter ensemble de ces algorithmes hors de l'eau

594
00:34:55,139 --> 00:35:00,260
quelque chose de mieux. Très bien. Merci beaucoup. Vous pouvez garder ces souvenirs.

595
00:35:01,710 --> 00:35:04,330
Très bien. Nous sommes de retour.

596
00:35:04,330 --> 00:35:08,420
>> Et pour résumer très vite, nous avons eu ces approches 3 différents pour le tri,

597
00:35:08,420 --> 00:35:13,000
tout l'intérêt de ce qui était pour arriver au point où quelqu'un comme Alex

598
00:35:13,000 --> 00:35:16,930
pourrait rechercher une liste de numéros rapides que quelqu'un comme Sean pouvait.

599
00:35:16,930 --> 00:35:19,830
Et même si nous avons des exemples simples avec 8 numéros,

600
00:35:19,830 --> 00:35:24,000
vous pourriez facilement extrapoler à 8 pages, 8 milliards de pages Web,

601
00:35:24,000 --> 00:35:26,680
ou 800 millions d'amis sur Facebook.

602
00:35:26,680 --> 00:35:30,090
Ainsi, ces algorithmes peuvent certainement évoluer pour ces types de valeurs,

603
00:35:30,090 --> 00:35:32,300
et les idées sont finalement les mêmes.

604
00:35:32,300 --> 00:35:36,140
Alors tri à bulles est le premier où l'on sorte de barboter jusqu'à la plus grande personne

605
00:35:36,140 --> 00:35:39,110
tout le chemin à droite en échangeant les gens par paires.

606
00:35:39,110 --> 00:35:42,040
Puis nous avons eu ce que nous appellerons tri par sélection où j'ai un peu plus délibérément

607
00:35:42,040 --> 00:35:46,480
continué à regarder dans la liste, sélectionner le plus petit nombre encore et encore et encore,

608
00:35:46,480 --> 00:35:49,530
la suite logique de ce qui est que la liste est finalement triés.

609
00:35:49,530 --> 00:35:53,780
Puis, dans la troisième, j'ai inséré les gens à leur juste place,

610
00:35:53,780 --> 00:35:57,720
et nous avons un exemple très artificiel en ce que la liste a été déjà triés,

611
00:35:57,720 --> 00:36:01,100
mais c'était pour envoyer le message que dans le cas du tri par insertion,

612
00:36:01,100 --> 00:36:02,670
vous pouvez avoir de la chance.

613
00:36:02,670 --> 00:36:07,930
Si les numéros sont déjà triés, ça ne va vous prendre des mesures pour s'assurer n autant,

614
00:36:07,930 --> 00:36:10,870
alors que vous êtes tri par sélection vision en tunnel un peu plus

615
00:36:10,870 --> 00:36:14,360
et vous n'avez pas toujours se rendre compte que la liste est déjà triée.

616
00:36:14,360 --> 00:36:16,830
Voyons donc ce tri à bulles en action ici.

617
00:36:16,830 --> 00:36:19,590
Dans l'exemple suivant, nous sommes sur le point de voir des barres verticales

618
00:36:19,590 --> 00:36:23,030
dont les hauteurs représenter des nombres afin que nous puissions régler le tri des visualize arriver.

619
00:36:23,030 --> 00:36:26,630
Plus la barre est haute, plus le nombre; plus la barre est grande, plus le nombre.

620
00:36:26,630 --> 00:36:28,860
>> Et nous allons le jouer à cette vitesse par défaut.

621
00:36:28,860 --> 00:36:33,460
Ça va aller un peu vite pour le moment, mais le rouge est à l'affiche de 2 bars

622
00:36:33,460 --> 00:36:35,480
on compare côte à côte.

623
00:36:35,480 --> 00:36:39,520
Et si vous regardez attentivement, ce qui se passe, c'est que si les barres sont hors d'usage,

624
00:36:39,520 --> 00:36:42,300
le plus petit est déplacé vers la gauche, plus l'un à droite,

625
00:36:42,300 --> 00:36:44,360
et puis vous continuez à avancer.

626
00:36:44,360 --> 00:36:48,520
Donc, si nous le faisons encore et encore, vous remarquerez que les plus petites barres

627
00:36:48,520 --> 00:36:51,090
vont continuer à inching leur chemin vers la gauche

628
00:36:51,090 --> 00:36:54,130
et les plus grandes barres vont continuer à inching leur chemin vers la droite.

629
00:36:54,130 --> 00:36:58,490
Et en effet, nous commençons à voir un modèle tout le chemin sur la droite

630
00:36:58,490 --> 00:37:04,790
comme nous l'avons vu 8 et puis 7 éventuellement bouillonne à l'autre bout de notre liste humaine.

631
00:37:04,790 --> 00:37:08,750
Donc, cela va très vite devenir un peu fastidieux, alors laissez-moi arrêter ce pour un moment.

632
00:37:08,750 --> 00:37:10,980
Permettez-moi de changer la vitesse beaucoup plus rapide.

633
00:37:10,980 --> 00:37:15,380
Je ne change pas l'algorithme, je fais juste l'animation se produire plus rapidement.

634
00:37:15,380 --> 00:37:18,410
Tri à bulles Pourtant, même algorithme,

635
00:37:18,410 --> 00:37:21,910
mais maintenant vous pouvez voir beaucoup plus vite que notre démonstration verbale

636
00:37:21,910 --> 00:37:25,900
que les plus grands éléments sont en effet bouillonne vers le haut.

637
00:37:25,900 --> 00:37:29,860
>> Soit dit en passant, ces petits carrés en bas à gauche et en bas à droite

638
00:37:29,860 --> 00:37:33,520
ne sont que des petits rappels concernant le nombre de comparaisons que vous faites.

639
00:37:33,520 --> 00:37:37,620
Mais pour l'instant, nous pouvons nous concentrer sur la pyramide qui est train de prendre forme, et voilà.

640
00:37:37,620 --> 00:37:41,510
Le plus petit élément est sur la gauche, le plus grand sur la droite, et tout le reste entre les deux.

641
00:37:41,510 --> 00:37:44,470
Maintenant, nous allons plutôt jeter un oeil à tri par sélection.

642
00:37:44,470 --> 00:37:47,260
Je vais aller de l'avant et appuyez sur Stop. Nous allons obtenir un nouvel ensemble aléatoire de barres.

643
00:37:47,260 --> 00:37:50,930
Tri par sélection, rappel, parcourt la liste encore et encore et encore,

644
00:37:50,930 --> 00:37:54,900
arracher le plus petit élément. Donc, voici tri par sélection.

645
00:37:54,900 --> 00:37:58,390
On dirait qu'il ya moins de travail passe en ce moment parce que nous ne sommes pas comparer deux à deux

646
00:37:58,390 --> 00:38:02,590
mais nous sommes juste une sorte de cherry picking les plus petits éléments de droite à gauche.

647
00:38:02,590 --> 00:38:06,890
Cela a pris très peu de temps, il ya donc une dichotomie déjà.

648
00:38:06,890 --> 00:38:11,820
Juste parce qu'un algorithme est dit de prendre le temps au carré n, comme tri à bulles

649
00:38:11,820 --> 00:38:16,100
et comme tri par sélection, ceux qui sont vraiment pires moments de cas en cours d'exécution.

650
00:38:16,100 --> 00:38:21,790
Par exemple, dans le cas de, disons, tri par sélection,

651
00:38:21,790 --> 00:38:27,240
En fait, je suis sélectionnant la plus petite personne et de mettre lui ici,

652
00:38:27,240 --> 00:38:29,620
alors je vais le faire à nouveau, alors je vais le faire encore une fois,

653
00:38:29,620 --> 00:38:32,070
mais il y avait une légère optimisation que je pourrais faire.

654
00:38:32,070 --> 00:38:35,040
>> Dès que je me suis déplacé numéro 1 ici - Sammy dans ce cas -

655
00:38:35,040 --> 00:38:38,630
qu'est-ce que je dois faire avec lui par la suite? >> [L'élève] Laisse-le.

656
00:38:38,630 --> 00:38:40,140
Laissez-le, non? Rien.

657
00:38:40,140 --> 00:38:44,310
Je n'ai pas besoin de toujours parler à nouveau Sammy parce que si j'avais choisi le plus petit élément

658
00:38:44,310 --> 00:38:48,580
et le mettre ici, pourquoi perdre du temps aller jusqu'au bout de ma liste?

659
00:38:48,580 --> 00:38:54,590
Sur la prochaine itération permettez-moi de réellement se déplacer que le numéro 2, pour le numéro 3.

660
00:38:54,590 --> 00:38:57,640
Donc, en réalité, je ne faisais pas les choses n n fois.

661
00:38:57,640 --> 00:39:05,380
Je faisais des choses n, alors n - 1 choses, alors n - 2 choses, alors n - 3 choses,

662
00:39:05,380 --> 00:39:07,080
alors n - 4, point, point, point.

663
00:39:07,080 --> 00:39:09,470
Nous avons un peu d'une série géométrique, ce qui signifie simplement

664
00:39:09,470 --> 00:39:11,450
vous ajoutez des numéros de plus en plus petites.

665
00:39:11,450 --> 00:39:17,940
Non n + n + n + n mais n + 7 + 6 + 5 + 4 + 3 + 2 + 1.

666
00:39:17,940 --> 00:39:21,380
Et qu'est-ce qui fonctionne généralement avéré être -

667
00:39:21,380 --> 00:39:24,280
Je vais gâcher ma planche ici pour un instant -

668
00:39:24,280 --> 00:39:28,990
qui va travailler à être quelque chose comme n (n - 1) / 2

669
00:39:28,990 --> 00:39:31,930
si nous juste une sorte de coup d'oeil à l'arrière d'un livre de maths où vous avez tous les cheat feuilles

670
00:39:31,930 --> 00:39:33,410
pour les formules.

671
00:39:33,410 --> 00:39:37,760
Si vous êtes juste ajouter quelque chose de n + n - 1 + n - 2, cela revient à quelque chose comme ceci.

672
00:39:37,760 --> 00:39:42,320
Et si nous multiplions ce genre de sortir, qui est n au carré moins n / 2.

673
00:39:42,320 --> 00:39:46,400
Je répétais n carré, mais, et c'est parce que j'étais un peu en prenant un raccourci mental

674
00:39:46,400 --> 00:39:51,950
car, en réalité, moins carré n n divisé par 2 est en effet le véritable nombre d'étapes

675
00:39:51,950 --> 00:39:55,510
qu'un algorithme comme tri par sélection prendrait si on a vraiment compté jusqu'à

676
00:39:55,510 --> 00:39:58,800
l'ensemble de ces comparaisons et tout le travail peu occupé que nous faisions.

677
00:39:58,800 --> 00:40:03,210
Mais franchement, une fois n arrive à être comme un million ou un milliard, qui diable se soucie

678
00:40:03,210 --> 00:40:07,160
si vous faites un milliard de moins carré d'un milliard divisé par 2?

679
00:40:07,160 --> 00:40:09,320
Un milliard carré est un chiffre énorme.

680
00:40:09,320 --> 00:40:13,580
Vous pouvez prendre un autre milliard hors de lui avec - n. Ce n'est pas une grosse affaire.

681
00:40:13,580 --> 00:40:18,770
Donc, plus les nombres deviennent les moins importantes de ces conditions inférieures sont ordonnées.

682
00:40:18,770 --> 00:40:24,230
Qui se soucie si vous divisez par 2 si vous parlez quadrillions de nombre d'étapes?

683
00:40:24,230 --> 00:40:29,710
>> Donc, en général, les informaticiens ont tendance à jeter tout mais le plus grand terme,

684
00:40:29,710 --> 00:40:33,140
et nous venons sorte de simplifier le monde et dire que cet algorithme

685
00:40:33,140 --> 00:40:38,130
a pris des mesures à peu près n carré. C'est le temps d'exécution d'un algorithme.

686
00:40:38,130 --> 00:40:40,760
Donc, nous allons revenir sur ce point dans un instant avec quelques exemples concrets,

687
00:40:40,760 --> 00:40:45,940
mais pour l'instant, c'est un peu de la motivation derrière tout intuitive simplifiant notre monde

688
00:40:45,940 --> 00:40:51,170
et parler des termes les plus importants plutôt que d'entrer dans toutes ces formules de fantaisie.

689
00:40:51,170 --> 00:40:53,540
Donc, c'était tri par sélection, et nous avons eu un peu de chance là-bas.

690
00:40:53,540 --> 00:40:57,360
Regardons le tri par insertion. Permettez-moi aller de l'avant et de commencer celui-ci aussi.

691
00:40:57,360 --> 00:41:00,330
Maintenant, remarquez le modèle de ce qui se passe est un peu différent,

692
00:41:00,330 --> 00:41:03,410
et nous avons commencé avec des nombres aléatoires,

693
00:41:03,410 --> 00:41:06,890
mais si l'on fait de compter le nombre d'étapes dans le pire des cas,

694
00:41:06,890 --> 00:41:11,070
si la liste a commencé tout à fait dans le bon ordre,

695
00:41:11,070 --> 00:41:13,380
nous ne ferions que de prendre des mesures n de réaliser autant.

696
00:41:13,380 --> 00:41:18,240
>> Mais si la liste devait effectivement vers l'arrière - par exemple, dans ce cas ici -

697
00:41:18,240 --> 00:41:23,860
remarque alors nous avons à faire beaucoup plus de travail dans ce cas.

698
00:41:23,860 --> 00:41:27,080
Et il devrait me sens un peu de vous comme celui-ci est une sorte de travailler plus fort

699
00:41:27,080 --> 00:41:30,900
pour obtenir ces éléments plus petits à gauche, et c'est parce que nous avons eu de chance.

700
00:41:30,900 --> 00:41:34,210
La liste a été triée par accident dans le sens inverse.

701
00:41:34,210 --> 00:41:38,110
En revanche, avec le tri par insertion si nous imiter ce que nous avons fait avec nos hommes ici

702
00:41:38,110 --> 00:41:42,670
en commençant par tout le monde, puis triés commencer, il est un algorithme assez bon, non?

703
00:41:42,670 --> 00:41:45,010
C'est déjà, en fait, triées.

704
00:41:45,010 --> 00:41:48,670
Donc, nous allons essayer de résumer exactement combien de temps ces choses nous prennent

705
00:41:48,670 --> 00:41:52,360
en introduisant un peu de jargon ou de la notation qui est en fait beaucoup plus simple

706
00:41:52,360 --> 00:41:54,320
que le genre de fanciness suggère.

707
00:41:54,320 --> 00:41:59,030
Cette chose ici, ce grand A sur l'écran, ce qui est un informaticien utilise généralement

708
00:41:59,030 --> 00:42:03,640
pour décrire le pire temps d'exécution d'un algorithme.

709
00:42:03,640 --> 00:42:07,360
>> Encore une fois, par le pire des cas, il est totalement dépendant du contexte.

710
00:42:07,360 --> 00:42:10,890
Ce que nous entendons par le pire des cas varie totalement basé sur le problème dont nous parlons.

711
00:42:10,890 --> 00:42:14,550
Mais dans le cas du tri, ce qui est le pire possible?

712
00:42:14,550 --> 00:42:17,860
Tout est à l'envers, car il se sent juste comme ça représente beaucoup de travail pour nous.

713
00:42:17,860 --> 00:42:21,330
J'ai griffonné quelques-uns des algorithmes que nous avons vu jusqu'à présent:

714
00:42:21,330 --> 00:42:24,930
recherche linéaire, binaire de recherche comme avec l'annuaire ou les morceaux de papier,

715
00:42:24,930 --> 00:42:28,960
puis trier tri à bulles, tri par sélection, d'insertion et comme nous l'avons vu de nos hommes,

716
00:42:28,960 --> 00:42:31,770
puis 1 autre qui est finalement va être appelé tri par fusion.

717
00:42:31,770 --> 00:42:37,710
Donc, à la recherche linéaire dans le pire des cas, combien d'étapes faut-il pour trouver le numéro 7

718
00:42:37,710 --> 00:42:40,690
si il ya des portes n comme Sean face? >> [L'élève] N.

719
00:42:40,690 --> 00:42:44,180
N. Donc, nous allons écrire grand O de n.

720
00:42:44,180 --> 00:42:47,010
Je vais remplir quelques blancs. Ceci est juste une grille d'ébauches.

721
00:42:47,010 --> 00:42:52,990
Mais dans le meilleur des cas avec recherche linéaire, 7 aurait pu être au tout début de la liste,

722
00:42:52,990 --> 00:42:55,520
et Sean aurait commencé à regarder le début de la liste.

723
00:42:55,520 --> 00:42:58,940
Donc, si vous utilisez la recherche linéaire et vérifier simplement de gauche à droite ou de droite à gauche peut-être -

724
00:42:58,940 --> 00:43:02,650
ils sont équivalent - dans le meilleur des cas, le nombre d'étapes pourraient recherche linéaire,

725
00:43:02,650 --> 00:43:05,550
comme algorithme de Sean, prendre? Seulement 1 étape.

726
00:43:05,550 --> 00:43:09,450
>> Alors, je vais dire que c'est la notation oméga.

727
00:43:09,450 --> 00:43:11,570
C'est juste oméga majuscule.

728
00:43:11,570 --> 00:43:15,000
Omega est juste la façon sexy de dire le meilleur des cas en temps continu.

729
00:43:15,000 --> 00:43:18,900
Ainsi, dans le meilleur des cas, le temps d'exécution est une étape unique ou un nombre constant d'étapes -

730
00:43:18,900 --> 00:43:24,270
1 dans ce cas -, mais dans le pire des cas, grand O, il est effectivement n étapes.

731
00:43:24,270 --> 00:43:28,110
Et celui-là, thêta, nous sommes en fait ne va pas chercher à l'heure actuelle.

732
00:43:28,110 --> 00:43:30,090
Ce n'est pas pertinent à cet exemple particulier.

733
00:43:30,090 --> 00:43:31,990
Mais maintenant, nous allons essayer de recherche binaire.

734
00:43:31,990 --> 00:43:35,990
Dans le pire des cas avec une recherche binaire, le nombre de pas est ce que ça va prendre pour trouver le numéro 7

735
00:43:35,990 --> 00:43:38,340
ou ce que nous recherchons? >> [L'élève] Log n.

736
00:43:38,340 --> 00:43:40,980
Encore faudra n log parce que tout comme Alex eu de chance

737
00:43:40,980 --> 00:43:44,030
quand nous avons vraiment travaillé sur le problème méthodiquement

738
00:43:44,030 --> 00:43:48,220
et elle n'a pas trouvé le numéro 7 jusqu'à la toute dernière porte, elle regarda,

739
00:43:48,220 --> 00:43:51,720
même si, en toute justice, elle a obtenu de jeter certaines portes le long du chemin,

740
00:43:51,720 --> 00:43:56,920
recherche binaire dans le pire des cas, a une durée de log n.

741
00:43:56,920 --> 00:43:59,230
Et encore une fois, qui parle de cette division et de conquête.

742
00:43:59,230 --> 00:44:01,140
Mais qu'en est-il dans le meilleur des cas?

743
00:44:01,140 --> 00:44:04,790
Et Alex fait l'expérience que le meilleur des cas à droite quand elle est venue sur scène.

744
00:44:04,790 --> 00:44:07,290
Combien de pas est-ce que prendre en binaire de recherche? >> [L'élève] 1.

745
00:44:07,290 --> 00:44:09,380
1, juste parce qu'elle a été chanceux.

746
00:44:09,380 --> 00:44:12,520
Mais c'est bien parce oméga se réfère à meilleur des cas,

747
00:44:12,520 --> 00:44:15,770
Entrées meilleur des cas, même si c'est juste aléatoire simple chance.

748
00:44:15,770 --> 00:44:18,900
>> Maintenant, cela aussi nous allons juste une sorte de vide congé pour le moment.

749
00:44:18,900 --> 00:44:21,010
Tri à bulles Que diriez-vous maintenant?

750
00:44:21,010 --> 00:44:24,290
Dans le pire des cas, avec une sorte de bulle, tout le monde est dans l'ordre inverse,

751
00:44:24,290 --> 00:44:26,380
nous devons donc faire beaucoup de bulles.

752
00:44:26,380 --> 00:44:30,190
Mais combien de pas est ce que cela va prendre dans le pire des cas? >> [L'élève] carré N.

753
00:44:30,190 --> 00:44:32,550
Ce fut le n au carré, parce que si vous pensez cela,

754
00:44:32,550 --> 00:44:36,410
si la liste est complètement à l'envers - 8 est ici, 1 est ici -

755
00:44:36,410 --> 00:44:40,530
comme chose commence à faire des bulles, le numéro 8 va se déplacer de cette façon, de cette façon,

756
00:44:40,530 --> 00:44:44,540
Ainsi, de cette façon, mais où est le numéro 7 dans le pire des cas?

757
00:44:44,540 --> 00:44:47,720
Ici, elle est encore là-bas. Donc, nous devons le faire encore et encore.

758
00:44:47,720 --> 00:44:53,190
Et c'est là que nous obtenons étapes n, alors n - 1 étapes, alors n - 2 étapes.

759
00:44:53,190 --> 00:44:55,960
Et si vous prenez ma parole - que si vous multipliez sorte de sortir,

760
00:44:55,960 --> 00:45:00,110
il est à peu près carré n à la fin avec quelques autres termes qui nous allons ignorer pour le moment -

761
00:45:00,110 --> 00:45:06,890
puis dans le pire des cas, tri à bulles est n au carré, donner ou prendre.

762
00:45:06,890 --> 00:45:09,490
Mais qu'en est-il le meilleur des cas avec tri à bulles?

763
00:45:09,490 --> 00:45:13,050
Quel est le meilleur scénario? Tous les nombres sont triés déjà.

764
00:45:13,050 --> 00:45:15,920
Et quel était l'heuristique que j'ai utilisé, le truc que j'ai utilisé,

765
00:45:15,920 --> 00:45:20,110
se rendre compte que je n'avais pas fait de travaux et pourrait donc s'arrêter tôt?

766
00:45:20,110 --> 00:45:23,590
[L'élève] Check it la fois. Check it >> une fois. Mais ce que je faisais en cours de route?

767
00:45:23,590 --> 00:45:26,130
J'ai été faire le suivi du nombre de swaps que j'ai fait.

768
00:45:26,130 --> 00:45:30,650
Et j'ai réalisé que si je n'ai pas compté les swaps sur mes doigts, puis je l'ai fait pas de travail.

769
00:45:30,650 --> 00:45:34,300
Je certainement ne devrait pas essayer de ne pas travailler à nouveau, afin que je puisse s'arrêter.

770
00:45:34,300 --> 00:45:37,830
>> Ainsi, dans le meilleur des cas, de tri à bulles lorsque la liste est déjà trié,

771
00:45:37,830 --> 00:45:41,530
que diriez-vous de la notation oméga-dire, le meilleur des cas, temps de marche?

772
00:45:41,530 --> 00:45:48,040
C'est juste n. Nous devons faire un peu de travail, mais nous ne disposons que de faire une valeur de 1 promenade de travail.

773
00:45:48,040 --> 00:45:50,490
Et là aussi, je vais laisser ce champ vide partiel.

774
00:45:50,490 --> 00:45:52,430
Et maintenant, tri par sélection.

775
00:45:52,430 --> 00:45:56,010
Tri par sélection m'avait arracher la plus petite personne encore et encore.

776
00:45:56,010 --> 00:45:58,380
Et qu'est-ce que nous disons que le temps d'exécution de ce test?

777
00:45:58,380 --> 00:46:00,590
C'était n au carré dans le pire des cas.

778
00:46:00,590 --> 00:46:05,220
Et malheureusement, dans le meilleur des cas, il est également n carré

779
00:46:05,220 --> 00:46:08,840
parce que je n'ai pas le genre de vue omniscient du monde entier;

780
00:46:08,840 --> 00:46:13,140
Je sais seulement sur une itération complète que j'ai effectivement trouvé la plus petite personne.

781
00:46:13,140 --> 00:46:15,860
Alors sorte de suce tri par sélection, en ce sens,

782
00:46:15,860 --> 00:46:17,920
mais l'avantage est que c'est un peu intuitive.

783
00:46:17,920 --> 00:46:21,470
Il est assez facile à coder, car tout ce que vous avez à faire est d'écrire quelques imbriqué des boucles,

784
00:46:21,470 --> 00:46:24,620
typiquement, qui passe par la recherche de la plus petite élément

785
00:46:24,620 --> 00:46:27,840
et met ensuite le plus petit élément à sa place à la fin de la liste.

786
00:46:27,840 --> 00:46:29,900
Donc, là aussi, il va y avoir un compromis.

787
00:46:29,900 --> 00:46:34,440
La quantité de temps cela vous prend à penser et à réellement développer quelque chose en écrivant du code

788
00:46:34,440 --> 00:46:39,460
pourrait très bien prendre plus de temps si vous voulez une meilleure performance algorithme et plus rapide.

789
00:46:39,460 --> 00:46:41,780
>> Mais si vous avez vraiment juste une sorte de code quelque chose en place rapide et sale

790
00:46:41,780 --> 00:46:45,000
et juste un peu prendre l'idée stupide possible que vous pouvez penser,

791
00:46:45,000 --> 00:46:47,580
cela pourrait prendre quelques minutes pour le code, mais avec grands ensembles de données

792
00:46:47,580 --> 00:46:49,580
votre algorithme pourrait prendre des heures à courir.

793
00:46:49,580 --> 00:46:51,690
Et moi-même je l'école d'études supérieures serait parfois faire ces compromis.

794
00:46:51,690 --> 00:46:55,660
Il serait 3h du matin, j'ai essayé d'analyser certaines très grand ensemble de données

795
00:46:55,660 --> 00:46:59,650
liée à la recherche sur la sécurité que je faisais, et il a été soit passer 5 minutes

796
00:46:59,650 --> 00:47:03,210
peaufiner mon programme pour analyser les données et d'aller dormir

797
00:47:03,210 --> 00:47:08,420
ou de passer 8 heures, il se juste à droite de sorte qu'il fonctionne instantanément et ne pas aller dormir.

798
00:47:08,420 --> 00:47:10,530
Et donc, là aussi c'est un peu une décision consciente.

799
00:47:10,530 --> 00:47:12,740
Moins de temps de développement, plus de sommeil.

800
00:47:12,740 --> 00:47:14,780
Avec le recul, je n'aurais probablement pas encourager cette

801
00:47:14,780 --> 00:47:19,120
lorsque l'objectif ici est d'optimiser la qualité du code,

802
00:47:19,120 --> 00:47:21,280
mais aussi dans le monde réel est un très bon compromis.

803
00:47:21,280 --> 00:47:25,130
Moins de temps, moins de performance ou vice versa.

804
00:47:25,130 --> 00:47:28,110
Nous voilà donc enfin avoir une chance de parler de thêta.

805
00:47:28,110 --> 00:47:32,830
Theta notation est quelque chose informaticiens peuvent apporter dans la conversation

806
00:47:32,830 --> 00:47:36,160
quand grand O et oméga arrive d'être la même chose.

807
00:47:36,160 --> 00:47:40,160
Vous dites thêta pour vraiment envoyer le message que c'est un peu un serré lié.

808
00:47:40,160 --> 00:47:43,340
Peu importe si le scénario est bon ou mauvais, il est n au carré.

809
00:47:43,340 --> 00:47:46,510
Donc, il n'est tout simplement pas pertinente dans ces histoires ici.

810
00:47:46,510 --> 00:47:48,560
Le tri par insertion est le dernier que nous avons regardé,

811
00:47:48,560 --> 00:47:50,830
où je viens d'insérer tout le monde dans le bon endroit.

812
00:47:50,830 --> 00:47:54,930
Dans le meilleur des cas, ce fut le temps d'exécution du tri par insertion que nous avons vu ici?

813
00:47:54,930 --> 00:47:57,250
[L'élève] Le meilleur des cas? >> Le meilleur des cas.

814
00:47:57,250 --> 00:48:00,100
>> Il a été n parce que, dans le meilleur des cas tous triés,

815
00:48:00,100 --> 00:48:02,580
et Sammy et personne d'autre vraiment eu à se déplacer du tout.

816
00:48:02,580 --> 00:48:04,610
Ils étaient déjà à leur juste place.

817
00:48:04,610 --> 00:48:08,570
Ainsi, le tri par insertion dans le meilleur des cas, dans ce cas, n.

818
00:48:08,570 --> 00:48:12,770
Mais dans le pire des cas, c'est une sorte de n carrés. Pourquoi?

819
00:48:12,770 --> 00:48:16,230
Si ma liste de sujets humains est dans l'ordre inverse,

820
00:48:16,230 --> 00:48:21,260
J'ai d'abord commencer par le numéro 8 et je lui insérer ou elle dans la bonne position, qui se trouve ici.

821
00:48:21,260 --> 00:48:25,270
J'ai un peu de mouvement sur le côté. Ces gars-là ne sont pas triés, il ou elle est triée.

822
00:48:25,270 --> 00:48:28,970
Mais maintenant, il m'arrive de trouver qui ensuite? >> [L'élève] 7.

823
00:48:28,970 --> 00:48:31,250
7 dans le pire des cas, parce que c'est dans l'ordre inverse.

824
00:48:31,250 --> 00:48:34,920
>> Voici donc 7. D'où vient 7 appartiennent? Définitivement derrière moi.

825
00:48:34,920 --> 00:48:39,460
Mais maintenant 7 appartient effectivement pas immédiatement derrière moi, mais derrière le numéro 8,

826
00:48:39,460 --> 00:48:41,880
Je dois donc dire: «Excusez-moi, le numéro 8, pouvez-vous s'il vous plaît déplacer de cette façon

827
00:48:41,880 --> 00:48:44,640
"Faire de la place pour 7?" Maintenant, je rencontre 6.

828
00:48:44,640 --> 00:48:48,530
"Oh, excusez-moi, le numéro 8 et le numéro 7, pouvez-vous aller pour faire place à 6?"

829
00:48:48,530 --> 00:48:52,360
Donc, en d'autres termes, avec le tri par insertion, même si je ne fais pas beaucoup de mouvement,

830
00:48:52,360 --> 00:48:56,330
les gens derrière moi faisons beaucoup plus de travail, et que ça doit coûter du temps à quelqu'un.

831
00:48:56,330 --> 00:48:58,000
Il va coûter l'heure de l'ordinateur.

832
00:48:58,000 --> 00:49:01,450
Ainsi, dans le cas du tri par insertion nous souffrons encore.

833
00:49:01,450 --> 00:49:06,260
Si vous commencez à ajouter le nombre total d'étapes, on finit par frapper à peu près carré n

834
00:49:06,260 --> 00:49:11,160
parce que ces gars ont besoin pour faire place à l'être humain à réinséré dans cette liste.

835
00:49:11,160 --> 00:49:15,960
Et dans ce cas theta n'est tout simplement pas applicable à l'histoire particulière à portée de main.

836
00:49:15,960 --> 00:49:21,100
C'est bien joli. Nous avons ces moyens 3 différentes de parler de la durée de fonctionnement.

837
00:49:21,100 --> 00:49:26,370
Mais qu'est-ce que cela signifie réellement en termes réels si nous essayons réellement coder un algorithme?

838
00:49:26,370 --> 00:49:31,620
>> Permettez-moi de proposer qu'il y ait un algorithme encore meilleur là-bas

839
00:49:31,620 --> 00:49:33,740
que lui-même a certains compromis.

840
00:49:33,740 --> 00:49:36,890
Nous allons appeler le tri par fusion, et c'est un peu de cet algorithme magique

841
00:49:36,890 --> 00:49:42,840
qui fonctionne plus rapidement en quelque sorte, et c'est tellement facile à exprimer, au moins en pseudo-code.

842
00:49:42,840 --> 00:49:46,900
La mise en œuvre de ce type de fusion algorithme va être comme suit.

843
00:49:46,900 --> 00:49:50,860
Lorsque vous avez donné n éléments - nombres n, n personnes, quelle que soit - d'abord il ya un test de cohérence.

844
00:49:50,860 --> 00:49:56,340
Si n est inférieur à 2, le tri par fusion s'arrête. Elle renvoie, pour ainsi dire.

845
00:49:56,340 --> 00:50:00,830
Pourquoi vous arrêter si n est inférieur à 2? >> [Réponse de l'élève inaudible]

846
00:50:00,830 --> 00:50:04,480
Droite. Et de plus, n est pas le numéro de la liste, n est la taille de la liste.

847
00:50:04,480 --> 00:50:07,660
Si n est inférieur à 2, cela signifie que votre liste est soit 1,

848
00:50:07,660 --> 00:50:09,640
où vous êtes évidemment triés si c'est numéro 1,

849
00:50:09,640 --> 00:50:11,710
ou 0, auquel cas il n'y a rien à trier,

850
00:50:11,710 --> 00:50:13,570
donc nous avons besoin de ce genre de scénario de base.

851
00:50:13,570 --> 00:50:20,350
Si la liste est si courte qu'il n'y a tout simplement rien à faire, littéralement, ne rien faire. Retour.

852
00:50:20,350 --> 00:50:25,090
Sinon trier la moitié gauche des éléments, puis trier la moitié droite des éléments,

853
00:50:25,090 --> 00:50:27,410
puis fusionner les 2 moitiés triés.

854
00:50:27,410 --> 00:50:32,130
>> Ce genre de ressemble à un petit tricheur laquelle je vous demande comment trier les éléments

855
00:50:32,130 --> 00:50:34,900
et vous me dites, "Tri de la moitié gauche, trier la moitié droite."

856
00:50:34,900 --> 00:50:37,240
Je suis comme: «Très bien. Comment pouvez-vous trier la moitié gauche?"

857
00:50:37,240 --> 00:50:40,670
"Trier la moitié gauche de la moitié gauche, trier la moitié droite de la partie gauche, puis fait."

858
00:50:40,670 --> 00:50:44,060
Vous êtes un peu cyclique définir ce que signifie pour trier,

859
00:50:44,060 --> 00:50:46,790
mais il s'avère que c'est en fait brillante dans ce cas.

860
00:50:46,790 --> 00:50:50,230
Ce n'est pas vraiment ce cercle vicieux qui n'en finit pas

861
00:50:50,230 --> 00:50:52,550
parce qu'il ne finissent quand? >> [L'élève] Lorsque vous arrivez à 1 chose.

862
00:50:52,550 --> 00:50:54,220
Lorsque vous arrivez à 1 chose.

863
00:50:54,220 --> 00:50:57,850
Ainsi, même si vous pourriez commencer avec 8 personnes et je dis: «Trier la moitié gauche de ces personnes,

864
00:50:57,850 --> 00:51:00,480
ces 4 personnes, "alors je dis:« Comment pouvez-vous trier la moitié gauche? "

865
00:51:00,480 --> 00:51:03,450
"Eh bien, trier les 2 gens d'ici." Et puis vous êtes comme, "Très bien, très bien."

866
00:51:03,450 --> 00:51:05,520
"Comment pouvez-vous trier la moitié gauche de ces gens?"

867
00:51:05,520 --> 00:51:09,040
"Juste trier cette personne 1 ici." Quelle est la révélation éclatante maintenant?

868
00:51:09,040 --> 00:51:13,050
Je dois trier 1 personne. Terminé. Je n'ai pas à faire n'importe quel travail.

869
00:51:13,050 --> 00:51:16,580
Mais maintenant, je dois trier cette personne, mais ils sont une seule personne, rien à faire.

870
00:51:16,580 --> 00:51:21,490
>> Ainsi, la magie est apparemment dans cette troisième étape: la fusion des moitiés triés.

871
00:51:21,490 --> 00:51:25,770
Alors sorte de fusion prend cette idée brillante que si vous cassez un gros problème vers le bas

872
00:51:25,770 --> 00:51:28,650
en 2 petites, de taille identique problèmes

873
00:51:28,650 --> 00:51:32,710
et puis juste un peu de colle les plus petites solutions ensemble à la fin,

874
00:51:32,710 --> 00:51:34,720
Je propose que nous pouvons faire beaucoup, [son de frappe] beaucoup mieux

875
00:51:34,720 --> 00:51:38,050
que n'importe lequel de tri par sélection ou le tri par insertion.

876
00:51:38,050 --> 00:51:40,690
En fait, j'ai été en ignorant que pendant une demi-heure, mais je ne sais vraiment pas ce qui se passe

877
00:51:40,690 --> 00:51:45,040
dehors aujourd'hui. [Vrombissement] [rires]

878
00:51:45,040 --> 00:51:49,660
Donc, nous allons voir si nous pouvons le voir avec un peu d'aide de notre ami Rob Bowden.

879
00:51:49,660 --> 00:51:52,810
Il ya 2 grandes étapes dans le processus de tri par fusion.

880
00:51:52,810 --> 00:51:56,400
Tout d'abord, en permanence diviser la liste en deux moitiés de tasses

881
00:51:56,400 --> 00:51:59,610
jusqu'à ce que nous avons un tas de listes avec juste 1 tasse en eux.

882
00:51:59,610 --> 00:52:02,150
Ne vous inquiétez pas si une liste contient un nombre impair

883
00:52:02,150 --> 00:52:04,830
et vous ne pouvez pas faire une coupe parfaitement propre entre eux.

884
00:52:04,830 --> 00:52:08,740
Juste choisir arbitrairement qui liste pour y inclure la tasse supplémentaire po

885
00:52:08,740 --> 00:52:11,320
Donc, nous allons diviser ces listes.

886
00:52:12,420 --> 00:52:14,570
Maintenant, nous avons 2 listes.

887
00:52:18,930 --> 00:52:20,930
Maintenant, nous avons 4 listes.

888
00:52:25,730 --> 00:52:28,740
Maintenant, nous avons 8 listes avec une tasse unique dans chaque liste.

889
00:52:28,740 --> 00:52:31,520
Donc, c'est tout pour l'étape 1.

890
00:52:31,520 --> 00:52:37,280
Pour l'étape 2, nous avons à plusieurs reprises réunis des paires de listes en utilisant l'algorithme de fusion, nous avons appris avant.

891
00:52:37,280 --> 00:52:44,320
La fusion de 108 et 15, nous retrouver avec la liste des 15, 108.

892
00:52:45,240 --> 00:52:51,330
La fusion de 50 et 4 on se retrouve avec 4, 50.

893
00:52:51,330 --> 00:52:56,950
La fusion de 8 et 42 nous nous retrouvons avec 8, 42.

894
00:52:57,790 --> 00:53:04,360
Et la fusion de 23 et 16 nous nous retrouvons avec 16, 23.

895
00:53:04,360 --> 00:53:08,030
Maintenant, tous nos listes sont de taille 2.

896
00:53:08,030 --> 00:53:10,980
Notez que chacun des 4 listes sont triées,

897
00:53:10,980 --> 00:53:14,230
afin que nous puissions commencer la fusion des paires de listes.

898
00:53:14,230 --> 00:53:22,150
La fusion de 15 et 108 et 4 et 50 nous avons d'abord prendre le 4, puis le 15,

899
00:53:22,150 --> 00:53:26,250
puis le 50, puis le 108.

900
00:53:26,250 --> 00:53:33,020
La fusion de 8, 42 et 16, 23 nous avons d'abord prendre le 8, puis le 16,

901
00:53:33,020 --> 00:53:37,170
puis le 23, puis le 42.

902
00:53:37,170 --> 00:53:42,490
Donc maintenant nous avons seulement 2 listes de taille 4, dont chacune est triée.

903
00:53:42,490 --> 00:53:45,940
Alors maintenant, nous fusionnons ces 2 listes.

904
00:53:45,940 --> 00:53:54,230
Nous prenons d'abord le 4, puis nous prenons le 8, puis nous prenons la 15

905
00:53:54,230 --> 00:54:05,280
et 16 et 23 et 42 et 50 et 108.

906
00:54:05,280 --> 00:54:09,020
Et c'est fait. Nous avons maintenant une liste triée.

907
00:54:09,020 --> 00:54:13,740
>> Rob a eu la gentillesse de profiter de quelque chose que nous n'avons pas encore fait.

908
00:54:13,740 --> 00:54:16,540
Il a été suggéré, mais nous n'avons pas vraiment le faire.

909
00:54:16,540 --> 00:54:19,230
Il faisait quelque chose de physiquement avec les verres qui suggère

910
00:54:19,230 --> 00:54:23,680
il passait une ressource en plus de temps. >> [L'élève] Space. >> C'est l'espace.

911
00:54:23,680 --> 00:54:27,360
Le fait qu'il ait eu ce genre de bi-niveau de la table où il avait de place ici

912
00:54:27,360 --> 00:54:31,960
et de l'espace a été fait ici-bas ce qui implique qu'il utilise deux fois plus d'espace

913
00:54:31,960 --> 00:54:36,390
comme l'un de nos algorithmes à ce jour - tri tri par insertion, tri à bulles, ou la sélection -

914
00:54:36,390 --> 00:54:40,780
mais il a été tirant parti de cet espace supplémentaire pour genre de choses se déplacent d'avant en arrière

915
00:54:40,780 --> 00:54:42,600
tout en gardant les choses en ordre.

916
00:54:42,600 --> 00:54:47,540
Et même si elle se sent comme nous sommes arrivés à une liste triée, on se sent comme il a fallu un certain temps.

917
00:54:47,540 --> 00:54:51,060
En réalité, ce que Rob faisait était exactement cet algorithme.

918
00:54:51,060 --> 00:54:56,780
Il a pris le premier problème de taille n, divisé en une moitié gauche et une moitié droite.

919
00:54:56,780 --> 00:54:59,380
C'est quand il a déménagé les tasses. Puis, il répéta ce processus.

920
00:54:59,380 --> 00:55:03,390
Il a divisé 4 en 2 groupes de 2 ici et ici.

921
00:55:03,390 --> 00:55:08,520
Puis, il répéta ce processus et divisé 2 en 2 séries de 1 pour chacune de ces coupes différentes.

922
00:55:08,520 --> 00:55:11,000
Et c'est là que l'occasion se présente brillante.

923
00:55:11,000 --> 00:55:15,840
A ce moment de l'histoire, Rob avait 8 listes de taille 1,

924
00:55:15,840 --> 00:55:18,860
qui ont tous été triés déjà.

925
00:55:18,860 --> 00:55:20,630
>> Alors qu'est-ce qu'il procède à faire?

926
00:55:20,630 --> 00:55:25,260
Deux à deux, il a pris cette liste triée et cette liste triée et les fusionner.

927
00:55:25,260 --> 00:55:28,200
Puis il prit celui-ci et de les fusionner, puis celle-ci et de les fusionner,

928
00:55:28,200 --> 00:55:30,670
alors celui-ci et de les fusionner.

929
00:55:30,670 --> 00:55:32,390
Et puis, qu'at-il fait ensuite?

930
00:55:32,390 --> 00:55:36,580
Il a ensuite re-fusionner les listes grandes et puis re-fusionné les listes plus grandes.

931
00:55:36,580 --> 00:55:41,170
Et si vous pensez à ce que intuitivement pour l'instant, que faisait-il vraiment?

932
00:55:41,170 --> 00:55:45,450
Il divisait le problème en deux, moitié, moitié, en deux

933
00:55:45,450 --> 00:55:47,600
afin d'obtenir ces listes super-petits.

934
00:55:47,600 --> 00:55:51,290
Puis il a eu la gentillesse de combiner double, double, double, double.

935
00:55:51,290 --> 00:55:54,120
Alors qu'il faisait deux fois autant de travail que nous avons vu jusqu'à présent

936
00:55:54,120 --> 00:55:56,930
avec tout ce qui touche à diviser pour régner, mais pas une grosse affaire.

937
00:55:56,930 --> 00:55:59,630
Travail deux fois plus n'est pas une grosse affaire. C'est juste un facteur constant.

938
00:55:59,630 --> 00:56:03,920
Et tout comme notre expression arithmétique avant, je vais juste à traverser les facteurs constants

939
00:56:03,920 --> 00:56:10,170
comme le temps 2. Qui s'en soucie? Si c'est 2 fois 2 milliards, c'est encore beaucoup d'étapes.

940
00:56:10,170 --> 00:56:13,160
Ainsi, cette étape de fusion semble être l'intuition clé.

941
00:56:13,160 --> 00:56:17,000
Passons en revue ce que numériquement avant - Oh, ce n'est pas d'être poursuivi pour le moment.

942
00:56:17,000 --> 00:56:22,890
Parcourons cette numériquement juste pour réellement voir comment cela se joue.

943
00:56:22,890 --> 00:56:25,940
Il s'agit la plupart du temps juste un petit pauvre d'animation.

944
00:56:25,940 --> 00:56:27,750
Nous allons proposer cela.

945
00:56:27,750 --> 00:56:31,480
Le temps d'exécution du tri par fusion - nous avons juste besoin d'un moyen de parler à ce sujet.

946
00:56:31,480 --> 00:56:34,380
Ce n'est pas les mathématiques, c'est juste une sorte de manière succincte de nous exprimer.

947
00:56:34,380 --> 00:56:39,080
Donc T représente le temps et n représente quoi? >> [L'élève] La taille de la -

948
00:56:39,080 --> 00:56:41,400
>> [Malan] L'ampleur du problème, le nombre de personnes.

949
00:56:41,400 --> 00:56:45,470
Je suis donc prétendre que le temps d'exécution de trier les gens n va de 0 quantité de temps

950
00:56:45,470 --> 00:56:50,290
si n est inférieur à 2, parce que si vous avez 1 tasse ou pas de tasses, vous n'avez rien à trier.

951
00:56:50,290 --> 00:56:55,160
Mais plus généralement, je vais proposer que le temps d'exécution pour trier n éléments

952
00:56:55,160 --> 00:56:59,350
sera le temps nécessaire pour trier la moitié gauche, plus la moitié droite

953
00:56:59,350 --> 00:57:03,110
plus - de quoi s'agit supplémentaire + n? >> [L'élève] Tri par fusion.

954
00:57:03,110 --> 00:57:07,260
[Malan] Il est en train de fusionner, parce que si vous avez n / 2 éléments ici

955
00:57:07,260 --> 00:57:11,500
et vous avez n / 2 éléments ici, combien de temps faut-il pour les fusionner?

956
00:57:11,500 --> 00:57:15,050
Tout comme Rob, vous avez pour arracher celui-ci ici, peut-être arracher par ici,

957
00:57:15,050 --> 00:57:17,120
plumer par ici, par ici arracher, plumer ici.

958
00:57:17,120 --> 00:57:19,400
Vous devez toucher chacune des coupelles fois.

959
00:57:19,400 --> 00:57:22,030
Et s'il ya en plus 4 tasses 4 tasses, c'est 8 tasses

960
00:57:22,030 --> 00:57:25,200
ou, plus généralement, 8 tasses n.

961
00:57:25,200 --> 00:57:28,470
Ainsi, l'étape de fusion, nous pouvons exprimer que n,

962
00:57:28,470 --> 00:57:31,330
et qui consiste littéralement le nombre de fois où Rob physiquement touché

963
00:57:31,330 --> 00:57:33,410
l'un de ceux tasses en styromousse.

964
00:57:33,410 --> 00:57:35,850
Donc, nous allons maintenant faire un exemple arbitraire.

965
00:57:35,850 --> 00:57:41,850
S'il ya 16 tasses, quel est le temps d'exécution du tri, en utilisant l'algorithme de Rob, 16 tasses?

966
00:57:41,850 --> 00:57:44,710
C'est 2 fois la quantité de temps qu'il faut pour trier 8 tasses

967
00:57:44,710 --> 00:57:46,920
parce que nous avons ici, 8 tasses 8 tasses ici.

968
00:57:46,920 --> 00:57:51,520
Je ne sais pas combien de temps cela prend, nous sommes donc en la généralisant comme T pour le moment.

969
00:57:51,520 --> 00:57:53,320
Qui sait ce que c'est?

970
00:57:53,320 --> 00:57:58,990
Mais maintenant, je peux trier de manière récursive ou à plusieurs reprises poser la même question.

971
00:57:58,990 --> 00:58:01,920
Combien de temps faut-il pour trier 8 tasses?

972
00:58:01,920 --> 00:58:07,030
8 tasses que je vais dire prend le temps qu'il faut pour trier 4 tasses 4 tasses ainsi que,

973
00:58:07,030 --> 00:58:08,880
puis de les fusionner ensemble.

974
00:58:08,880 --> 00:58:13,080
Très bien. Nous entrons dans un cycle déjà. Combien de temps faut-il pour trier 4 tasses?

975
00:58:13,080 --> 00:58:19,150
Le temps qu'il faut pour trier 4 tasses 2 tasses est plus 2 tasses de tri ainsi que le processus de fusion.

976
00:58:19,150 --> 00:58:21,440
Très bien. Combien de temps faut-il pour trier 2 tasses?

977
00:58:21,440 --> 00:58:26,290
2 tasses est la quantité de temps qu'il faut pour trier 1 tasse plus le temps qu'il faut pour régler une autre tasse

978
00:58:26,290 --> 00:58:29,040
plus la quantité de temps qu'il faut pour fusionner, ce qui est à seulement 2.

979
00:58:29,040 --> 00:58:33,340
>> Très bien. Dernière question. Combien de temps faut-il pour trier 1 tasse?

980
00:58:33,340 --> 00:58:37,260
Voici le scénario de base que nous avions prédit que nous avions frappé plus tôt.

981
00:58:37,260 --> 00:58:42,250
Le fait qu'il ne prend pas de travail que ce soit pour trier le plus petit des problèmes

982
00:58:42,250 --> 00:58:44,120
signifie que désormais, sorte de style école primaire,

983
00:58:44,120 --> 00:58:46,460
on peut juste aller commencer à brancher ces chiffres en arrière po

984
00:58:46,460 --> 00:58:50,630
Nous savons maintenant ce que T 1 est, si je peux brancher sur 0 pour T 1.

985
00:58:50,630 --> 00:58:54,420
Cela me donnera la réponse à T 2, que j'ai ensuite peut brancher plus haut.

986
00:58:54,420 --> 00:58:56,930
Cela me donnera de T 4, qui je peux brancher plus haut.

987
00:58:56,930 --> 00:58:58,920
Cela me donnera T de 8, ce que je peux brancher plus haut.

988
00:58:58,920 --> 00:59:04,330
Et si je fais réellement que les mathématiques en branchant ces réponses,

989
00:59:04,330 --> 00:59:08,590
Je puis obtenir de T 16 est 64.

990
00:59:08,590 --> 00:59:12,090
Et qu'est-ce que 64 représentent-ils?

991
00:59:12,090 --> 00:59:15,700
Si T est de 16, oui, c'est 16 fois 4.

992
00:59:15,700 --> 00:59:20,120
Donc je réclame maintenant que le temps d'exécution de cette chose appelée le tri par fusion -

993
00:59:20,120 --> 00:59:22,590
et cela va être le plus chic de ceux que nous avons vus jusqu'à présent -

994
00:59:22,590 --> 00:59:26,160
va être appelé n log n

995
00:59:26,160 --> 00:59:31,140
car combien de fois peut diviser Rob tout un tas de coupes en deux? Log n.

996
00:59:31,140 --> 00:59:34,370
C'est la même chose que l'exemple du livre de téléphone, c'est le même que l'exemple d'auto-comptage.

997
00:59:34,370 --> 00:59:36,380
>> Combien de fois pouvez-vous partager quelque chose en deux?

998
00:59:36,380 --> 00:59:38,410
Cependant, il ya cette étape de fusion.

999
00:59:38,410 --> 00:59:42,920
Vous pourriez avoir à diviser les tasses dans la moitié encore et encore et encore,

1000
00:59:42,920 --> 00:59:45,640
mais chaque fois que vous allez avoir à fusionner.

1001
00:59:45,640 --> 00:59:48,270
Et nous l'avons dit plus tôt que la fusion tasses n prend les mesures n

1002
00:59:48,270 --> 00:59:52,060
parce que vous devez arracher une tasse, une tasse arracher, et vous avez de toucher chaque tasse une fois,

1003
00:59:52,060 --> 00:59:53,510
tout comme Rob a fait.

1004
00:59:53,510 --> 00:59:59,430
Donc, si nous faisons quelque chose de log n fois et nous faisons les choses n sur chacun de ces itérations,

1005
00:59:59,430 --> 01:00:03,090
chacun de ces halvings, nous avons n log n fois.

1006
01:00:03,090 --> 01:00:07,220
Donc, si nous branchons sur 16 dans cet exemple, 16 fois le logarithme de 16 -

1007
01:00:07,220 --> 01:00:10,600
ne vous inquiétez pas pourquoi c'est le cas pour l'instant parce que je n'ai pas tiré de la base -

1008
01:00:10,600 --> 01:00:16,100
mais logarithme de base 2 de 16 est 4, 16 fois 4 est 64.

1009
01:00:16,100 --> 01:00:22,350
Mais en revanche, si nous avions utilisé tri à bulles ou la sélection ou l'insertion de tri tri avec 16 numéros,

1010
01:00:22,350 --> 01:00:26,420
quelle serait la durée de fonctionnement ont été si n est de 16?

1011
01:00:26,420 --> 01:00:33,310
Il serait de 16 au carré, qui est de 256, ce qui, même si vous n'avez pas tout à fait suivi toutes les mathématiques,

1012
01:00:33,310 --> 01:00:38,390
256 est plus grand que 64. C'est vraiment l'emporter magique ici.

1013
01:00:38,390 --> 01:00:41,990
Et se rendre compte que le travail à travers ce dans les petits exemples que l'on veut sur un pset

1014
01:00:41,990 --> 01:00:44,260
Il est d'autant plus intuitif.

1015
01:00:44,260 --> 01:00:49,070
Mais qu'est-ce que cela signifie vraiment en termes de sensation de cet algorithme est la suivante:

1016
01:00:49,070 --> 01:00:54,520
Si l'on fait regarder tri par fusion ici - permettez-moi de tirer vers le haut dans cette fenêtre ici -

1017
01:00:54,520 --> 01:00:58,560
ceci est un exemple légèrement différent dans lequel nous avons tous les 3 de ces algorithmes -

1018
01:00:58,560 --> 01:01:01,440
bulle, la sélection, et de fusionner - juste à côté.

1019
01:01:01,440 --> 01:01:03,740
>> Ils ont tous commencé avec des barres aléatoires, et c'est une bonne chose.

1020
01:01:03,740 --> 01:01:06,240
Personne n'a un avantage fondamental sur l'autre.

1021
01:01:06,240 --> 01:01:09,500
Je vais dans un instant cliquez sur chacune de ces animations - Cliquez sur Démarrer, sur Démarrer, Démarrer -

1022
01:01:09,500 --> 01:01:13,270
aussi vite que je peux pour que, grosso modo, ils commencent tous en même temps,

1023
01:01:13,270 --> 01:01:17,450
et considérons que le pire des cas tri à bulles de temps de fonctionnement, c'est quoi? >> [L'élève] carré N.

1024
01:01:17,450 --> 01:01:21,560
N au carré. Pire des cas, tri par sélection du temps de fonctionnement est? N au carré.

1025
01:01:21,560 --> 01:01:25,150
Et tri par fusion est apparemment - même si vous n'avez pas bien suivi toutes les mathématiques aujourd'hui,

1026
01:01:25,150 --> 01:01:30,610
ça va devenir beaucoup plus intuitive avec le temps - est, nous prétendons, n log n fois.

1027
01:01:30,610 --> 01:01:35,210
Et parce que log n est strictement inférieur à n fois, nous avons de grands nombres,

1028
01:01:35,210 --> 01:01:40,230
n log n fois est plus petit que n fois n ou n au carré.

1029
01:01:40,230 --> 01:01:44,410
Alors qu'est-ce que ça fait d'être effectivement un meilleur algorithme en termes de temps d'exécution,

1030
01:01:44,410 --> 01:01:50,380
n log n fois par rapport au carré de n? Nous y voilà. Clic, clic, clic.

1031
01:01:55,690 --> 01:01:58,650
>> C'est ce que cela signifie d'utiliser quelque chose comme le tri par fusion.

1032
01:01:58,650 --> 01:02:01,680
Nous avons un moment. Voyons voir ce qui se passe ici.

1033
01:02:09,440 --> 01:02:12,440
[Rires] C'est l'argent de sur tri à bulles?

1034
01:02:14,960 --> 01:02:16,730
Il dépend plutôt de l'entrée parfois.

1035
01:02:16,730 --> 01:02:18,120
Voyons voir.

1036
01:02:18,120 --> 01:02:23,320
Allez. Il se sent comme il rattrape son retard. >> [L'élève] Aller, tri à bulles!

1037
01:02:23,320 --> 01:02:27,370
[Étudiants en murmurant]

1038
01:02:27,370 --> 01:02:29,120
[Malan] Ouais, ouais.

1039
01:02:29,120 --> 01:02:34,520
[Étudiants murmure] Allez, allez, allez!

1040
01:02:37,210 --> 01:02:40,450
[Tout acclamations] [applaudissements]

1041
01:02:40,450 --> 01:02:46,240
Alors maintenant, avec 1 dernière démo finale, si c'est un peu difficile à envelopper votre esprit autour de la mathématique

1042
01:02:46,240 --> 01:02:49,280
ou sorte de la visualisation de là, vous pouvez réellement entendre les vitesses

1043
01:02:49,280 --> 01:02:51,000
de différents algorithmes différemment.

1044
01:02:51,000 --> 01:02:53,900
Il s'agit d'une personne d'animation réalisé que réellement associés sons

1045
01:02:53,900 --> 01:02:56,980
le procédé de permutation et la hauteur des barres.

1046
01:02:56,980 --> 01:03:00,440
Comme nous allons le voir ici, il ya quelques algorithmes de tri plus là-bas que les gens ont pensé.

1047
01:03:00,440 --> 01:03:03,660
Cette première va être le tri par insertion, et ce sera voler à travers

1048
01:03:03,660 --> 01:03:07,090
et vous donner un sentiment sonore du fonctionnement de ces algorithmes différents.

1049
01:03:07,090 --> 01:03:09,080
Voici le tri par insertion.

1050
01:03:09,080 --> 01:03:18,410
[Bip électronique]

1051
01:03:18,410 --> 01:03:20,730
[Malan] Tri bulle.

1052
01:03:20,730 --> 01:03:46,850
[Bip rapide électronique]

1053
01:03:46,850 --> 01:03:48,950
[Malan] sort de sélection.

1054
01:03:48,950 --> 01:04:03,580
[Bip rapide électronique]

1055
01:04:03,580 --> 01:04:05,770
[Malan] tri par fusion.

1056
01:04:05,770 --> 01:04:17,270
[Bip électronique]

1057
01:04:17,270 --> 01:04:20,180
[Bip ralentit] [rires]

1058
01:04:20,180 --> 01:04:22,590
[Malan] Gnome sorte.

1059
01:04:22,590 --> 01:04:38,580
[Bip électronique]

1060
01:04:39,740 --> 01:04:46,150
>> C'est CS50. Nous vous verrons la semaine prochaine. [Applaudissements et des acclamations]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]