1 00:00:00,000 --> 00:00:00,488 2 00:00:00,488 --> 00:00:10,800 >> [Jouer de la musique] 3 00:00:10,800 --> 00:00:13,500 DAVID MALAN: Très bien. 4 00:00:13,500 --> 00:00:14,670 Très bien, bienvenue. 5 00:00:14,670 --> 00:00:18,120 Donc, c'est la Semaine 4, le début de celui-ci, déjà. 6 00:00:18,120 --> 00:00:21,320 Et vous vous souviendrez que la semaine dernière, nous avons mis coder de côté pour un peu 7 00:00:21,320 --> 00:00:24,240 et nous avons commencé à parler un peu plus de haut niveau, sur des choses comme 8 00:00:24,240 --> 00:00:28,130 recherche et de tri, qui, bien que idées un peu simples, sont 9 00:00:28,130 --> 00:00:31,840 représentatif d'une catégorie de problèmes vous allez commencer à résoudre en particulier 10 00:00:31,840 --> 00:00:34,820 que vous commencez à penser finale projets et des solutions intéressantes que vous 11 00:00:34,820 --> 00:00:36,760 pourrait avoir des problèmes du monde réel. 12 00:00:36,760 --> 00:00:39,490 Maintenant sorte de bulle a été l'un des plus simples de tels algorithmes, et il 13 00:00:39,490 --> 00:00:42,900 travaillé en ayant ces petits nombres dans une liste ou d'une sorte de matrice de 14 00:00:42,900 --> 00:00:46,530 bulle leur chemin vers le sommet, et la grands nombres déplacent leur chemin vers 15 00:00:46,530 --> 00:00:47,930 la fin de cette liste. 16 00:00:47,930 --> 00:00:50,650 >> Et rappelons que nous pouvions visualiser sorte de bulle un peu 17 00:00:50,650 --> 00:00:52,310 quelque chose comme ça. 18 00:00:52,310 --> 00:00:53,640 Alors laissez-moi aller de l'avant et cliquez sur Démarrer. 19 00:00:53,640 --> 00:00:55,350 J'ai présélectionné sorte de bulle. 20 00:00:55,350 --> 00:00:58,920 Et si vous vous souvenez que le plus grand bleu lignes représentent grands nombres, petit 21 00:00:58,920 --> 00:01:03,300 Les lignes bleues représentent un petit nombre, comme nous passons par ce encore et encore et 22 00:01:03,300 --> 00:01:07,680 de plus, la comparaison de deux barres côte à côte autre en rouge, nous allons échanger les 23 00:01:07,680 --> 00:01:11,010 le plus grand et le plus petit si ils sont hors d'usage. 24 00:01:11,010 --> 00:01:14,150 >> Donc cela va durer et continuer et aller , et vous verrez que le plus grand 25 00:01:14,150 --> 00:01:16,700 éléments font leur chemin à l' à droite, et les plus petits éléments sont 26 00:01:16,700 --> 00:01:17,900 se frayer un chemin vers la gauche. 27 00:01:17,900 --> 00:01:21,380 Mais nous avons commencé à quantifier l'efficacité, la 28 00:01:21,380 --> 00:01:22,970 la qualité de cet algorithme. 29 00:01:22,970 --> 00:01:25,200 Et nous avons dit que, dans le pire cas, cet algorithme a 30 00:01:25,200 --> 00:01:27,940 à peu près combien d'étapes? 31 00:01:27,940 --> 00:01:28,980 >> Alors n carré. 32 00:01:28,980 --> 00:01:30,402 Et ce qui était n? 33 00:01:30,402 --> 00:01:31,650 >> AUDIENCE: Nombre d'éléments. 34 00:01:31,650 --> 00:01:32,790 >> DAVID MALAN: Donc n est le nombre d'éléments. 35 00:01:32,790 --> 00:01:33,730 Et donc nous allons le faisons pas souvent. 36 00:01:33,730 --> 00:01:36,650 Chaque fois que nous voulons parler de la taille d'un problème ou la taille d'une 37 00:01:36,650 --> 00:01:39,140 entrée, ou la quantité de temps nécessaire pour produire une sortie, nous allons simplement 38 00:01:39,140 --> 00:01:41,610 quelle que soit généralisée l'entrée est la n. 39 00:01:41,610 --> 00:01:45,970 Donc, retour à la Semaine 0, les pages numériques dans le livre de téléphone est n. 40 00:01:45,970 --> 00:01:47,550 Le nombre d'étudiants dans la salle a été n. 41 00:01:47,550 --> 00:01:49,630 Donc, là aussi, nous suivons ce modèle. 42 00:01:49,630 --> 00:01:52,800 >> Maintenant, n carré n'est pas particulièrement rapide, donc nous avons essayé de faire mieux. 43 00:01:52,800 --> 00:01:55,970 Et donc nous avons regardé un couple de d'autres algorithmes, parmi lesquels 44 00:01:55,970 --> 00:01:57,690 était tri par sélection. 45 00:01:57,690 --> 00:01:59,180 Donc, tri par sélection était un peu différent. 46 00:01:59,180 --> 00:02:03,130 C'était presque simple, j'ose le dire, par lequel j'ai commencé au début de l' 47 00:02:03,130 --> 00:02:06,740 Liste de nos bénévoles et je viens à nouveau et encore et encore passé par 48 00:02:06,740 --> 00:02:10,060 la liste, arracher le plus petit élément à la fois et lui mettre ou 49 00:02:10,060 --> 00:02:13,040 elle au début de la liste. 50 00:02:13,040 --> 00:02:16,410 >> Mais cela, aussi, une fois que nous avons commencé à penser par le calcul et plus 51 00:02:16,410 --> 00:02:19,860 image, pensé à combien de fois J'allais en arrière et retour 52 00:02:19,860 --> 00:02:24,090 et-vient, nous l'avons dit dans le pire des cas, sélection sorte, aussi, était quoi? 53 00:02:24,090 --> 00:02:24,960 n au carré. 54 00:02:24,960 --> 00:02:27,490 Or, dans le monde réel, il pourrait en fait être légèrement plus rapide. 55 00:02:27,490 --> 00:02:30,620 Parce qu'encore une fois, je n'ai pas eu à tenir retour en arrière une fois que j'avais le tri 56 00:02:30,620 --> 00:02:31,880 plus petits éléments. 57 00:02:31,880 --> 00:02:35,090 Mais si nous pensons très grand n, et Si vous sorte de faire le calcul comme 58 00:02:35,090 --> 00:02:39,170 Je l'ai fait sur le plateau, avec le n carré moins quelque chose, tout le reste 59 00:02:39,170 --> 00:02:41,850 Outre le n carré, une fois n devient vraiment grand, ne 60 00:02:41,850 --> 00:02:42,850 vraiment autant d'importance. 61 00:02:42,850 --> 00:02:45,470 Donc, comme les informaticiens, nous trions de tourner un oeil aveugle à la plus petite 62 00:02:45,470 --> 00:02:49,220 facteurs et se concentrer uniquement sur le facteur de une expression qui va faire 63 00:02:49,220 --> 00:02:50,330 la plus grande différence. 64 00:02:50,330 --> 00:02:52,840 >> Eh bien, finalement, nous avons examiné au tri par insertion. 65 00:02:52,840 --> 00:02:56,620 Et ce fut dans le même esprit, mais plutôt que de passer par itérative et 66 00:02:56,620 --> 00:03:01,250 sélectionner le plus petit élément de l'un à un temps, j'ai plutôt pris la main que je 67 00:03:01,250 --> 00:03:04,070 a été traitée, et j'ai décidé, tout à droite, vous appartenez ici. 68 00:03:04,070 --> 00:03:06,160 Puis je suis passé à l'élément suivant et a décidé qu'il 69 00:03:06,160 --> 00:03:07,470 elle appartenait ici. 70 00:03:07,470 --> 00:03:08,810 Et puis je suis passé ainsi de suite. 71 00:03:08,810 --> 00:03:11,780 Et je pourrais à, le long du chemin, déplacer ces gars-là pour 72 00:03:11,780 --> 00:03:13,030 faire de la place pour eux. 73 00:03:13,030 --> 00:03:16,880 C'était donc en quelque sorte le renversement mentale de sélection sorte que nous 74 00:03:16,880 --> 00:03:18,630 appelé le tri par insertion. 75 00:03:18,630 --> 00:03:20,810 >> Donc ces sujets à se produire dans le monde réel. 76 00:03:20,810 --> 00:03:23,640 Il ya quelques années, quand un certain Le sénateur a été candidat à la présidence, 77 00:03:23,640 --> 00:03:27,160 Eric Schmidt, au moment où le chef de la direction Google, en fait eu l'occasion 78 00:03:27,160 --> 00:03:28,040 pour l'interviewer. 79 00:03:28,040 --> 00:03:32,010 Et nous avons pensé partager cette YouTube Clip pour vous ici, si nous pouvions mettre en place 80 00:03:32,010 --> 00:03:32,950 le volume. 81 00:03:32,950 --> 00:03:39,360 >> [LECTURE VIDEO] 82 00:03:39,360 --> 00:03:44,620 >> -Maintenant, sénateur, vous êtes ici chez Google, et je me plais à penser de la présidence 83 00:03:44,620 --> 00:03:46,042 comme un entretien d'embauche. 84 00:03:46,042 --> 00:03:47,770 >> [Rires] 85 00:03:47,770 --> 00:03:50,800 >> -Maintenant, il est difficile d'obtenir un travail en tant que président. 86 00:03:50,800 --> 00:03:52,480 Et vous allez à travers les rigueurs maintenant. 87 00:03:52,480 --> 00:03:54,330 Il est également difficile d'obtenir un emploi chez Google. 88 00:03:54,330 --> 00:03:59,610 Nous avons des questions et nous demandons nos candidats des questions. 89 00:03:59,610 --> 00:04:02,250 Et celui-ci est de Larry Schwimmer. 90 00:04:02,250 --> 00:04:05,325 >> [Rires] 91 00:04:05,325 --> 00:04:06,400 -Les gars, vous pensez que je plaisante? 92 00:04:06,400 --> 00:04:08,750 C'est juste ici. 93 00:04:08,750 --> 00:04:12,110 Quel est le moyen le plus efficace pour trier un million deux entiers bits? 94 00:04:12,110 --> 00:04:15,810 >> [Rires] 95 00:04:15,810 --> 00:04:18,260 >> -Eh bien, euh - 96 00:04:18,260 --> 00:04:19,029 >> -Je suis désolé. 97 00:04:19,029 --> 00:04:19,745 Peut-être que nous devrions - 98 00:04:19,745 --> 00:04:21,000 >> -Non, non, non, non, non. 99 00:04:21,000 --> 00:04:21,470 >> -Ce n'est pas une - 100 00:04:21,470 --> 00:04:22,185 OK. 101 00:04:22,185 --> 00:04:25,328 >> -Je pense que le tri à bulles serait être le mauvais chemin à parcourir. 102 00:04:25,328 --> 00:04:26,792 >> [Rires] 103 00:04:26,792 --> 00:04:28,510 >> [Acclamations et applaudissements] 104 00:04:28,510 --> 00:04:31,211 >> -Viens, qui lui a dit cela? 105 00:04:31,211 --> 00:04:32,155 OK. 106 00:04:32,155 --> 00:04:33,350 >> [FIN LECTURE VIDÉO] 107 00:04:33,350 --> 00:04:35,070 >> DAVID MALAN: Donc là vous l'avez. 108 00:04:35,070 --> 00:04:39,600 Nous avons donc commencé à quantifier ces cours d'exécution fois, pour ainsi dire, avec quelque chose 109 00:04:39,600 --> 00:04:43,480 appelé notation asymptotique, qui est seulement allusion à notre sorte de tournant 110 00:04:43,480 --> 00:04:47,420 les yeux sur ces facteurs petites et seulement en regardant le temps d'exécution, 111 00:04:47,420 --> 00:04:51,250 les performances de ces algorithmes, que n devient vraiment grande au fil du temps. 112 00:04:51,250 --> 00:04:55,110 Et donc nous avons introduit grand O. et Big O représentait quelque chose que nous avons pensé 113 00:04:55,110 --> 00:04:57,000 de comme une limite supérieure. 114 00:04:57,000 --> 00:04:59,570 Et effectivement, Barry, peut-on réduire que le micro un peu? 115 00:04:59,570 --> 00:05:01,040 >> Nous avons pensé que c'est une limite supérieure. 116 00:05:01,040 --> 00:05:04,710 Donc grand O de n moyens carré que dans le pire des cas, quelque chose comme 117 00:05:04,710 --> 00:05:07,780 sélection sorte prendrait n pas carré. 118 00:05:07,780 --> 00:05:10,310 Ou quelque chose comme le tri par insertion n serait pas carré. 119 00:05:10,310 --> 00:05:15,150 Maintenant, quelque chose comme insertion genre, ce qui était le pire des cas? 120 00:05:15,150 --> 00:05:18,200 Étant donné un tableau, ce qui est le pire possible scénario que vous pourriez trouver 121 00:05:18,200 --> 00:05:20,650 vous face à? 122 00:05:20,650 --> 00:05:21,860 >> C'est complètement à l'envers, non? 123 00:05:21,860 --> 00:05:24,530 Parce que si ce n'est complètement à l'envers, vous avez à faire beaucoup de travail. 124 00:05:24,530 --> 00:05:26,420 Parce que si vous êtes complètement à l'envers, vous allez trouver l' 125 00:05:26,420 --> 00:05:28,840 le plus grand élément ici, même si il appartient bas. 126 00:05:28,840 --> 00:05:31,140 Alors vous allez me dire, tout droit, à ce moment-là, vous appartenez ici, 127 00:05:31,140 --> 00:05:32,310 si vous le laissez seul. 128 00:05:32,310 --> 00:05:35,425 >> Ensuite, vous vous rendez compte, oh, zut, je dois déplacer cet élément légèrement inférieure à 129 00:05:35,425 --> 00:05:36,470 à gauche de vous. 130 00:05:36,470 --> 00:05:38,770 Ensuite, je dois le faire à nouveau et encore et encore. 131 00:05:38,770 --> 00:05:41,410 Et si je retournais en arrière, vous trierait de sentir la performance de 132 00:05:41,410 --> 00:05:45,540 cet algorithme, parce que je suis constamment brouillant tout le monde dans la 133 00:05:45,540 --> 00:05:46,510 tableau pour faire de la place pour cela. 134 00:05:46,510 --> 00:05:47,750 Donc, c'est le pire des cas. 135 00:05:47,750 --> 00:05:48,570 >> En revanche - 136 00:05:48,570 --> 00:05:50,320 et ce fut un cliffhanger dernière fois - 137 00:05:50,320 --> 00:05:54,065 nous avons dit que le tri par insertion était un oméga de quoi? 138 00:05:54,065 --> 00:05:57,530 Quel est le meilleur des cas rodage moment du tri par insertion? 139 00:05:57,530 --> 00:05:58,520 Donc, c'est en fait n. 140 00:05:58,520 --> 00:06:00,980 C'était le vide que nous avons laissé sur le plateau la dernière fois. 141 00:06:00,980 --> 00:06:03,160 >> Et c'est l'oméga de n car pourquoi? 142 00:06:03,160 --> 00:06:06,630 Eh bien, dans le meilleur cas, ce qui est tri par insertion va être remis? 143 00:06:06,630 --> 00:06:09,830 Eh bien, une liste qui est complètement triée déjà, un minimum de travail à faire. 144 00:06:09,830 --> 00:06:12,460 Mais ce qui est ordonnée au sujet de tri par insertion est que parce qu'il commence ici et 145 00:06:12,460 --> 00:06:15,340 décide, oh, vous êtes le numéro un, vous place ici. 146 00:06:15,340 --> 00:06:16,970 Oh, quelle bonne fortune. 147 00:06:16,970 --> 00:06:17,740 >> Vous êtes le numéro deux. 148 00:06:17,740 --> 00:06:19,030 Vous appartenez aussi ici. 149 00:06:19,030 --> 00:06:21,010 Numéro trois, c'est encore mieux, vous appartenez ici. 150 00:06:21,010 --> 00:06:25,210 Dès qu'elle arrive à la fin de l' Le pseudo-code de liste, par le tri par insertion 151 00:06:25,210 --> 00:06:28,010 que nous avons traversé verbalement la dernière fois, c'est fait. 152 00:06:28,010 --> 00:06:32,790 Mais la sélection sorte, en revanche, continué à faire quoi? 153 00:06:32,790 --> 00:06:35,260 >> Gardé en passant par la liste encore et encore et encore. 154 00:06:35,260 --> 00:06:39,160 Parce que l'idée fondamentale qu'il y avait seulement Une fois que vous avez regardé tout le chemin à l' 155 00:06:39,160 --> 00:06:42,500 fin de la liste peut vous être certain que l'élément que vous avez sélectionné est 156 00:06:42,500 --> 00:06:45,560 en effet le moment plus petit élément. 157 00:06:45,560 --> 00:06:48,920 Donc, ces différents modèles fin mentale par céder quelques-uns dans le monde réel très 158 00:06:48,920 --> 00:06:53,130 différences pour nous, ainsi que ces différences théoriques asymptotiques. 159 00:06:53,130 --> 00:06:56,910 >> Donc, pour récapituler, puis, grand O n carré, nous avons vu un peu comme 160 00:06:56,910 --> 00:06:58,350 algorithmes jusqu'ici. 161 00:06:58,350 --> 00:06:59,580 Big O n? 162 00:06:59,580 --> 00:07:02,870 Qu'est-ce qu'un algorithme qui pourrait être dit grand O de n? 163 00:07:02,870 --> 00:07:06,930 Dans le pire des cas, il faut un certain nombre d'étapes linéaires. 164 00:07:06,930 --> 00:07:07,810 >> OK, recherche linéaire. 165 00:07:07,810 --> 00:07:10,470 Et dans le pire des cas, où est l' élément que vous cherchez lorsque 166 00:07:10,470 --> 00:07:12,950 l'application de la recherche linéaire? 167 00:07:12,950 --> 00:07:14,680 >> OK, dans le pire des cas, il n'est même pas là. 168 00:07:14,680 --> 00:07:17,000 Ou dans le second cas le pire, c'est tout le chemin à la fin, ce qui est 169 00:07:17,000 --> 00:07:18,880 de plus-ou-moins une différence d'une seule étape. 170 00:07:18,880 --> 00:07:21,180 Ainsi, à la fin de la journée, nous pouvons dire que c'est linéaire. 171 00:07:21,180 --> 00:07:23,910 Big O n serait recherche linéaire, parce que dans le pire des cas, le 172 00:07:23,910 --> 00:07:26,610 élément n'est même pas là ou il est tout le chemin à la fin. 173 00:07:26,610 --> 00:07:29,370 >> Eh bien, grand O de journal de n. 174 00:07:29,370 --> 00:07:32,760 Nous n'avons pas parlé en détail sur , mais nous avons vu cela avant. 175 00:07:32,760 --> 00:07:36,840 Ce qui passe dans ce qu'on appelle logarithmique temps, dans le pire des cas? 176 00:07:36,840 --> 00:07:38,500 >> Ouais, recherche de manière binaire. 177 00:07:38,500 --> 00:07:42,930 Et recherche binaire dans le pire des cas pourrait avoir l'élément quelque part dans 178 00:07:42,930 --> 00:07:45,640 au milieu, ou quelque part à l'intérieur de la matrice. 179 00:07:45,640 --> 00:07:48,040 Mais vous ne trouverez une fois que vous diviser la liste en deux, en 180 00:07:48,040 --> 00:07:48,940 la moitié, en deux, la moitié. 181 00:07:48,940 --> 00:07:50,200 Et puis voilà, il est là. 182 00:07:50,200 --> 00:07:52,500 Ou encore, le pire des cas, il n'est même pas là. 183 00:07:52,500 --> 00:07:56,770 Mais vous ne savez pas que ce n'est pas là jusqu'à ce que vous atteignez cette sorte de dernier 184 00:07:56,770 --> 00:08:00,470 bottom-la plupart des éléments en réduisant de moitié et réduire de moitié et réduire de moitié. 185 00:08:00,470 --> 00:08:01,400 >> Big O 1. 186 00:08:01,400 --> 00:08:03,540 Donc, nous pourrions grand O 2, O grand de 3. 187 00:08:03,540 --> 00:08:06,260 Chaque fois que vous voulez juste un nombre constant, nous juste une sorte de juste simplifier 188 00:08:06,260 --> 00:08:07,280 que aussi grand O de 1. 189 00:08:07,280 --> 00:08:10,440 Même si si réaliste, il faut 2 ou même 100 mesures, si c'est un 190 00:08:10,440 --> 00:08:13,680 nombre constant d'étapes, nous disons juste big O 1. 191 00:08:13,680 --> 00:08:15,930 Qu'est-ce qu'un algorithme qui est en gros O 1? 192 00:08:15,930 --> 00:08:18,350 >> AUDIENCE: Trouver la longueur d'une variable. 193 00:08:18,350 --> 00:08:21,090 >> DAVID MALAN: Trouver l' longueur d'une variable? 194 00:08:21,090 --> 00:08:23,870 >> PUBLIC: Non, la longueur si elle est déjà trié. 195 00:08:23,870 --> 00:08:24,160 >> DAVID MALAN: Bon. 196 00:08:24,160 --> 00:08:27,850 OK, afin de trouver la longueur de quelque chose si la longueur de cette chose, comme 197 00:08:27,850 --> 00:08:30,020 un tableau est stocké dans une variable. 198 00:08:30,020 --> 00:08:33,380 Parce que vous pouvez simplement lire la variable, ou imprimer la variable, ou 199 00:08:33,380 --> 00:08:34,960 juste généralement accéder à cette variable. 200 00:08:34,960 --> 00:08:37,299 Et voila, cela prend du temps constant. 201 00:08:37,299 --> 00:08:38,909 >> En revanche, pensez à gratter. 202 00:08:38,909 --> 00:08:42,460 Repensez à la première semaine de C, appelant juste printf et l'impression 203 00:08:42,460 --> 00:08:46,240 quelque chose sur l'écran est sans doute constante de temps, car il suffit d' 204 00:08:46,240 --> 00:08:50,880 certains nombre de cycles CPU pour montrer que le texte sur l'écran. 205 00:08:50,880 --> 00:08:52,720 Ou attendre - t-il? 206 00:08:52,720 --> 00:08:56,430 Sinon, comment pourrions-nous modéliser l' performance de printf? 207 00:08:56,430 --> 00:09:00,420 Quelqu'un voudrait-il pas d'accord, que c'est peut-être pas le temps de vraiment constant? 208 00:09:00,420 --> 00:09:03,600 En quel sens peut-printf est en marche temps, en fait l'impression d'une chaîne de 209 00:09:03,600 --> 00:09:05,580 l'écran, que ce soit quelque chose autre que constante. 210 00:09:05,580 --> 00:09:07,860 >> AUDIENCE: [inaudible]. 211 00:09:07,860 --> 00:09:08,230 >> DAVID MALAN: Ouais. 212 00:09:08,230 --> 00:09:09,300 Tout dépend donc de notre point de vue. 213 00:09:09,300 --> 00:09:13,390 Si nous pensons réellement de l'entrée de printf comme étant la chaîne de caractères, et 214 00:09:13,390 --> 00:09:16,380 donc nous mesurons la taille de ce entrée par sa longueur - de sorte que nous appellerons 215 00:09:16,380 --> 00:09:17,780 que la longueur n et - 216 00:09:17,780 --> 00:09:21,990 sans doute, est lui-même printf grand O n parce que ça va vous prendre les mesures n 217 00:09:21,990 --> 00:09:24,750 à imprimer chacun de ces n personnages, le plus probable. 218 00:09:24,750 --> 00:09:27,730 Au moins dans la mesure où nous supposons que c'est peut-être l'aide d'une boucle for 219 00:09:27,730 --> 00:09:28,560 sous la hotte. 220 00:09:28,560 --> 00:09:30,860 >> Mais nous aurions à examiner cette code pour mieux le comprendre. 221 00:09:30,860 --> 00:09:33,650 Et en effet, une fois que vous les gars commencer l'analyse de vos propres algorithmes, vous 222 00:09:33,650 --> 00:09:34,900 littéralement faire exactement cela. 223 00:09:34,900 --> 00:09:37,765 Sorte de globe oculaire de votre code et de penser sur - tout droit, j'ai cette boucle 224 00:09:37,765 --> 00:09:41,870 ici ou j'ai un boucles imbriquées ici, qui va faire les choses n n fois, 225 00:09:41,870 --> 00:09:46,050 et vous pouvez trier la raison à votre façon dans le code, même si c'est 226 00:09:46,050 --> 00:09:47,980 pseudo et pas de code réelle. 227 00:09:47,980 --> 00:09:49,730 >> Alors que sur l'oméga de n carré? 228 00:09:49,730 --> 00:09:53,582 Ce qui était un algorithme qui dans le meilleur cas, a encore pris les mesures n carrés? 229 00:09:53,582 --> 00:09:54,014 Ouais? 230 00:09:54,014 --> 00:09:54,880 >> AUDIENCE: [inaudible]. 231 00:09:54,880 --> 00:09:55,900 >> DAVID MALAN: sélection sorte So. 232 00:09:55,900 --> 00:09:59,150 Parce que dans ce problème vraiment réduit au fait que de plus, je ne sais pas 233 00:09:59,150 --> 00:10:02,600 J'ai trouvé le plus petit courant jusqu'à J'ai vérifié tous les éléments sacrément. 234 00:10:02,600 --> 00:10:08,050 Donc l'oméga de, disons, n, nous viens avec un. 235 00:10:08,050 --> 00:10:09,300 Le tri par insertion. 236 00:10:09,300 --> 00:10:12,370 Si la liste se trouve être triés déjà, dans le meilleur des cas que nous venons de 237 00:10:12,370 --> 00:10:15,090 faire une passe à travers elle, à quel point nous sommes sûrs. 238 00:10:15,090 --> 00:10:17,890 Et puis, qui pourrait être dit est linéaire, c'est sûr. 239 00:10:17,890 --> 00:10:20,570 >> Qu'en est-il l'oméga de 1? 240 00:10:20,570 --> 00:10:23,790 Que, dans le meilleur des cas, pourrait prendre un nombre constant d'étapes? 241 00:10:23,790 --> 00:10:27,220 Recherche donc linéaire, si vous avoir de la chance et l'élément que vous cherchez 242 00:10:27,220 --> 00:10:31,000 qui est juste au début de la liste, si c'est là que vous commencez votre 243 00:10:31,000 --> 00:10:33,070 linéaire traversée de cette liste. 244 00:10:33,070 --> 00:10:35,180 >> Et cela est vrai d'un certain nombre de choses. 245 00:10:35,180 --> 00:10:37,660 Par exemple, même binaire recherche est l'oméga de 1. 246 00:10:37,660 --> 00:10:40,310 Parce que si vous avez vraiment sacrément la chance et smack-dab au milieu de 247 00:10:40,310 --> 00:10:42,950 votre tableau est le nombre vous cherchez? 248 00:10:42,950 --> 00:10:45,730 Ainsi, vous pouvez avoir de la chance là-bas, aussi. 249 00:10:45,730 --> 00:10:49,190 >> Celui-ci, enfin, l'oméga de n log n. 250 00:10:49,190 --> 00:10:52,573 Alors n log n, nous n'avons pas vraiment parler encore, mais - 251 00:10:52,573 --> 00:10:53,300 >> AUDIENCE: le tri par fusion? 252 00:10:53,300 --> 00:10:53,960 >> DAVID MALAN: Tri par fusion. 253 00:10:53,960 --> 00:10:56,920 C'était le cliffhanger de la dernière fois, où nous avons proposé, et nous avons montré 254 00:10:56,920 --> 00:10:58,600 visuellement, qu'il ya des algorithmes. 255 00:10:58,600 --> 00:11:02,470 Et le tri par fusion d'un seul exemple algorithme qui est fondamentalement plus rapide 256 00:11:02,470 --> 00:11:03,450 que certains de ces autres gars. 257 00:11:03,450 --> 00:11:07,800 En fait, fusionner courte est non seulement dans l' meilleur des cas n log n, dans le pire des 258 00:11:07,800 --> 00:11:09,460 cas n log n. 259 00:11:09,460 --> 00:11:14,540 Et quand vous avez cette coïncidence de Omega et grand O étant la même chose? 260 00:11:14,540 --> 00:11:17,310 Nous pouvons en fait décrire ce que ce qui est appelé thêta, si c'est un 261 00:11:17,310 --> 00:11:18,220 peu moins commun. 262 00:11:18,220 --> 00:11:21,730 Mais cela signifie simplement que les deux bornes, dans ce cas, sont les mêmes. 263 00:11:21,730 --> 00:11:25,770 >> Donc, le tri par fusion, qu'est-ce que cette vraiment se résument à nous? 264 00:11:25,770 --> 00:11:27,000 Eh bien, rappeler la motivation. 265 00:11:27,000 --> 00:11:30,340 Laisse-moi ôter une autre animation nous n'avons pas examiné la dernière fois. 266 00:11:30,340 --> 00:11:33,390 Celui-ci, même idée, mais il est un peu plus grand. 267 00:11:33,390 --> 00:11:36,160 Et je vais aller de l'avant et de souligner première - nous avons le tri par insertion sur 268 00:11:36,160 --> 00:11:39,410 En haut à gauche, puis sélection sorte, sorte de bulle, un couple d'autres sortes - 269 00:11:39,410 --> 00:11:42,670 coquille et rapide - que nous n'avons pas parlé environ, et le tas et le tri par fusion. 270 00:11:42,670 --> 00:11:47,090 >> Ainsi, au moins essayer de se concentrer vos yeux sur les trois premiers sur la gauche et ensuite 271 00:11:47,090 --> 00:11:49,120 le tri par fusion lorsque je clique cette flèche verte. 272 00:11:49,120 --> 00:11:51,900 Mais je vais laisser tous les exploités, juste pour vous donner une idée de la diversité des 273 00:11:51,900 --> 00:11:53,980 algorithmes qui existent dans le monde. 274 00:11:53,980 --> 00:11:56,180 Je vais laisser cette course pour quelques secondes. 275 00:11:56,180 --> 00:11:59,640 Et si vous vous concentrez vos yeux - choisir un algorithme, se concentrer sur cela pour seulement un 276 00:11:59,640 --> 00:12:02,970 secondes - vous allez commencer à voir le motif qu'elle est mise en œuvre. 277 00:12:02,970 --> 00:12:04,530 >> Le tri par fusion, un avis, est fait. 278 00:12:04,530 --> 00:12:06,430 Heap sorte, rapide genre, coquille - 279 00:12:06,430 --> 00:12:09,480 il semble donc que nous a présenté les trois pires algorithmes de semaine dernière. 280 00:12:09,480 --> 00:12:12,960 Mais c'est bien que nous sommes ici aujourd'hui pour regardez tri par fusion, qui est l'un des 281 00:12:12,960 --> 00:12:16,500 les plus faciles consiste à examiner, même mais il sera probablement plier votre esprit 282 00:12:16,500 --> 00:12:17,490 juste un petit peu. 283 00:12:17,490 --> 00:12:21,130 Ici, nous pouvons voir à quel point sélection sorte suce. 284 00:12:21,130 --> 00:12:24,600 >> Mais le revers de la médaille, c'est vraiment facile à mettre en œuvre. 285 00:12:24,600 --> 00:12:28,160 Et peut-être pour P Set 3, c'est l'un des algorithmes que vous avez choisi de mettre en œuvre 286 00:12:28,160 --> 00:12:28,960 pour l'édition standard. 287 00:12:28,960 --> 00:12:30,970 Parfaitement bien, parfaitement correct. 288 00:12:30,970 --> 00:12:35,210 >> Mais encore une fois, en tant que n devient grand, si vous choisir d'implémenter un algorithme plus rapide 289 00:12:35,210 --> 00:12:39,020 comme le tri par fusion, les chances sont plus grandes et grandes entrées, votre code est juste 290 00:12:39,020 --> 00:12:39,800 va courir plus vite. 291 00:12:39,800 --> 00:12:41,090 Votre site va travailler mieux. 292 00:12:41,090 --> 00:12:42,650 Vos utilisateurs vont être heureux. 293 00:12:42,650 --> 00:12:45,280 Et il ya ces effets de donner effectivement 294 00:12:45,280 --> 00:12:47,350 nous certains pensaient plus profond. 295 00:12:47,350 --> 00:12:49,990 >> Donc, nous allons jeter un oeil à ce que fusionner tri est fait tout au sujet. 296 00:12:49,990 --> 00:12:52,992 Le truc cool, c'est que fusionner tri est exactement cela. 297 00:12:52,992 --> 00:12:56,300 C'est, encore une fois, ce que nous avons appelé pseudo, étant pseudo- 298 00:12:56,300 --> 00:12:57,720 La syntaxe anglaise-like. 299 00:12:57,720 --> 00:12:59,890 Et la simplicité est sorte de fascinant. 300 00:12:59,890 --> 00:13:02,840 >> Donc, à l'entrée de n éléments - de sorte que signifie simplement, voici un tableau. 301 00:13:02,840 --> 00:13:04,000 Il faut que les choses n en elle. 302 00:13:04,000 --> 00:13:05,370 C'est tout ce que nous disons là. 303 00:13:05,370 --> 00:13:07,560 >> Si n est inférieur à 2, le retour. 304 00:13:07,560 --> 00:13:08,640 Donc, ce n'est que le cas le plus trivial. 305 00:13:08,640 --> 00:13:12,580 Si n est inférieur à 2, alors évidemment c'est 1 ou 0, dans ce cas, la chose 306 00:13:12,580 --> 00:13:14,780 est déjà trié, voire inexistante, Il suffit donc de retour. 307 00:13:14,780 --> 00:13:15,900 Il n'y a rien à faire. 308 00:13:15,900 --> 00:13:18,360 C'est donc un cas simple à arrachez. 309 00:13:18,360 --> 00:13:20,110 >> Sinon, nous avons trois étapes. 310 00:13:20,110 --> 00:13:23,650 Trier la moitié gauche des éléments, trier la moitié droite des éléments, 311 00:13:23,650 --> 00:13:26,650 puis fusionner les deux moitiés triés. 312 00:13:26,650 --> 00:13:29,400 Ce qui est intéressant ici, c'est que Je suis une sorte de barques à fond plat, non? 313 00:13:29,400 --> 00:13:32,300 Il ya une sorte de définition circulaire à cet algorithme. 314 00:13:32,300 --> 00:13:35,986 Dans quel sens est-ce algorithme de circulaire définition? 315 00:13:35,986 --> 00:13:37,850 >> AUDIENCE: [inaudible]. 316 00:13:37,850 --> 00:13:41,670 >> DAVID MALAN: Ouais, mon algorithme de tri, deux de ses mesures sont «tri 317 00:13:41,670 --> 00:13:44,640 quelque chose. "Et pour que pose la question, eh bien, ce que je vais utiliser 318 00:13:44,640 --> 00:13:46,460 à trier la moitié gauche et la moitié droite? 319 00:13:46,460 --> 00:13:49,600 Et la beauté, c'est que même si encore une fois, c'est l'esprit de flexion 320 00:13:49,600 --> 00:13:54,030 partie potentiellement, vous pouvez utiliser le même algorithme pour trier la moitié gauche. 321 00:13:54,030 --> 00:13:54,700 >> Mais attendez une minute. 322 00:13:54,700 --> 00:13:57,070 Quand on vous dit de trier les la moitié gauche, ce sont les deux 323 00:13:57,070 --> 00:13:58,240 mesures vont être le prochain? 324 00:13:58,240 --> 00:14:00,550 Nous allons régler la moitié gauche de l' la moitié gauche et la droite 325 00:14:00,550 --> 00:14:01,420 la moitié de la moitié gauche. 326 00:14:01,420 --> 00:14:04,430 Merde, comment puis-je trier ces deux moitiés ou en quartiers, maintenant? 327 00:14:04,430 --> 00:14:05,260 >> Mais c'est OK. 328 00:14:05,260 --> 00:14:07,830 Nous disposons d'un algorithme de tri ici. 329 00:14:07,830 --> 00:14:10,660 Et même si vous vous inquiétez au d'abord il s'agit d'une sorte d'infini 330 00:14:10,660 --> 00:14:12,780 boucle, c'est un cycle qui n'est jamais va finir - il va 331 00:14:12,780 --> 00:14:15,770 finir une fois ce qui se passe? 332 00:14:15,770 --> 00:14:16,970 Une fois que n est inférieur à 2. 333 00:14:16,970 --> 00:14:19,180 Qui finalement va se passer, parce que si vous continuez à réduire de moitié et 334 00:14:19,180 --> 00:14:23,020 réduire de moitié à réduire de moitié ces moitiés, sûrement finalement, vous allez finir 335 00:14:23,020 --> 00:14:25,350 avec seulement 1 ou 0 éléments. 336 00:14:25,350 --> 00:14:28,500 À ce moment-là, cet algorithme dit que vous avez terminé. 337 00:14:28,500 --> 00:14:31,020 >> Donc, la vraie magie dans cette algorithme semble être en 338 00:14:31,020 --> 00:14:33,470 que dernière étape, la fusion. 339 00:14:33,470 --> 00:14:37,190 Cette simple idée juste de fusionner deux choses, c'est ce qui est finalement aller 340 00:14:37,190 --> 00:14:40,920 pour nous permettre de trier un tableau de, disons, huit éléments. 341 00:14:40,920 --> 00:14:44,410 Je n'ai donc plus de huit balles anti-stress up ici, huit morceaux de papier, et un 342 00:14:44,410 --> 00:14:45,500 Google Glass - 343 00:14:45,500 --> 00:14:46,140 ce que je peux garder. 344 00:14:46,140 --> 00:14:46,960 >> [Rires] 345 00:14:46,960 --> 00:14:48,970 >> DAVID MALAN: Si nous pouvions prendre huit bénévoles, et nous allons voir si nous pouvons 346 00:14:48,970 --> 00:14:51,430 jouer cette rupture, donc. 347 00:14:51,430 --> 00:14:52,500 Wow, OK. 348 00:14:52,500 --> 00:14:53,565 Informatique devient amusant. 349 00:14:53,565 --> 00:14:54,320 Très bien. 350 00:14:54,320 --> 00:14:57,770 Alors que diriez-vous trois, plus grosse main là-haut. 351 00:14:57,770 --> 00:14:58,580 Quatre dans le dos. 352 00:14:58,580 --> 00:15:02,220 Et que diriez-vous, nous vous faisons trois dans cette ligne? 353 00:15:02,220 --> 00:15:03,390 Et quatre à l'avant. 354 00:15:03,390 --> 00:15:04,920 Donc vous huit, allez vers le haut. 355 00:15:04,920 --> 00:15:12,060 >> [Rires] 356 00:15:12,060 --> 00:15:13,450 >> DAVID MALAN: Je suis effectivement pas sûr de ce qu'il est. 357 00:15:13,450 --> 00:15:14,810 Est-ce les balles anti-stress? 358 00:15:14,810 --> 00:15:16,510 Les lampes de bureau? 359 00:15:16,510 --> 00:15:18,650 Le matériel? 360 00:15:18,650 --> 00:15:19,680 L'Internet? 361 00:15:19,680 --> 00:15:20,160 >> OK. 362 00:15:20,160 --> 00:15:21,310 Alors, venez sur place. 363 00:15:21,310 --> 00:15:22,310 Qui voudrait - 364 00:15:22,310 --> 00:15:23,570 garder à venir. 365 00:15:23,570 --> 00:15:24,240 Voyons voir. 366 00:15:24,240 --> 00:15:26,460 Et cela vous met dans un endroit - 367 00:15:26,460 --> 00:15:27,940 vous êtes dans un endroit un. 368 00:15:27,940 --> 00:15:28,670 Uh-oh, attendez une minute. 369 00:15:28,670 --> 00:15:30,760 1, 2, 3, 4, 5, 6, 7 - oh, bon. 370 00:15:30,760 --> 00:15:31,310 Très bien, nous sommes bons. 371 00:15:31,310 --> 00:15:35,130 Très bien, alors tout le monde a un siège, mais pas sur le verre Google. 372 00:15:35,130 --> 00:15:36,475 Permettez-moi de faire la queue ces haut. 373 00:15:36,475 --> 00:15:37,115 Quel est votre nom? 374 00:15:37,115 --> 00:15:37,440 >> MICHELLE: Michelle. 375 00:15:37,440 --> 00:15:38,090 >> DAVID MALAN: Michelle? 376 00:15:38,090 --> 00:15:42,000 Tout droit, vous arrivez à ressembler le geek, si c'est OK. 377 00:15:42,000 --> 00:15:44,625 Eh bien, moi aussi, je suppose, pour un instant. 378 00:15:44,625 --> 00:15:45,875 Tout droit, veille. 379 00:15:45,875 --> 00:15:48,510 380 00:15:48,510 --> 00:15:50,950 Nous avons essayé de trouver une cas d'utilisation de Google verre, et nous 381 00:15:50,950 --> 00:15:53,750 pensé qu'il serait amusant de faire ce quand les gens sont sur scène. 382 00:15:53,750 --> 00:15:57,120 Nous enregistrerons le monde à partir de leur point de vue. 383 00:15:57,120 --> 00:15:58,410 Très bien. 384 00:15:58,410 --> 00:15:59,830 Probablement pas ce que Google vise. 385 00:15:59,830 --> 00:16:02,260 Très bien, si vous ne me dérange pas porter ce pour les prochaines minutes difficiles, 386 00:16:02,260 --> 00:16:03,150 ce serait merveilleux. 387 00:16:03,150 --> 00:16:08,620 >> Très bien, nous avons donc ici un tableau de des éléments, et cette matrice, comme pour l' 388 00:16:08,620 --> 00:16:11,480 morceaux de papier dans ces gens-là » mains, est actuellement non triés. 389 00:16:11,480 --> 00:16:12,050 >> MICHELLE: Oh, c'est tellement bizarre. 390 00:16:12,050 --> 00:16:12,810 >> DAVID MALAN: C'est à peu près aléatoire. 391 00:16:12,810 --> 00:16:15,760 Et dans quelques instants, nous allons essayer de mettre en œuvre le tri par fusion ensemble 392 00:16:15,760 --> 00:16:17,950 et de voir où cette compréhension est la clé. 393 00:16:17,950 --> 00:16:21,970 Et le truc, ici, avec le tri par fusion est quelque chose que nous n'avons pas encore pris. 394 00:16:21,970 --> 00:16:24,030 Nous avons réellement besoin d'une espace supplémentaire. 395 00:16:24,030 --> 00:16:26,650 Alors, que va être particulièrement intéressant, c'est que ces 396 00:16:26,650 --> 00:16:29,270 les gars vont se déplacer un peu peu, parce que je vais supposer que 397 00:16:29,270 --> 00:16:31,880 il ya un tableau supplémentaire de l'espace, dire, juste derrière eux. 398 00:16:31,880 --> 00:16:34,570 >> Donc, si ils sont derrière leur chaise, c'est le réseau secondaire. 399 00:16:34,570 --> 00:16:36,960 S'ils sont assis ici, c'est la matrice primaire. 400 00:16:36,960 --> 00:16:40,170 Mais c'est une ressource que nous avons pas mobilisé à ce jour avec la bulle 401 00:16:40,170 --> 00:16:42,040 genre, avec sélection sorte, avec le tri par insertion. 402 00:16:42,040 --> 00:16:44,600 Rappelons semaine dernière, tout le monde juste genre de traîna en place. 403 00:16:44,600 --> 00:16:46,840 Ils n'ont pas utilisé toute la mémoire supplémentaire. 404 00:16:46,840 --> 00:16:49,310 Nous avons fait de la place pour les personnes en le déplacement des personnes autour. 405 00:16:49,310 --> 00:16:50,580 >> Donc, c'est une idée fondamentale, aussi. 406 00:16:50,580 --> 00:16:53,410 Il ya ce compromis, en général informatique, des ressources. 407 00:16:53,410 --> 00:16:55,800 Si vous voulez accélérer quelque chose comme le temps, vous allez 408 00:16:55,800 --> 00:16:56,900 avoir à payer un prix. 409 00:16:56,900 --> 00:17:00,750 Et l'un de ces prix est très souvent l'espace, la quantité de mémoire ou disque 410 00:17:00,750 --> 00:17:01,700 l'espace disque que vous utilisez. 411 00:17:01,700 --> 00:17:03,640 Or, franchement, le montant du temps du programmeur. 412 00:17:03,640 --> 00:17:06,700 Combien de temps cela vous prend, les ressources humaines, mettre en œuvre effectivement un peu plus 413 00:17:06,700 --> 00:17:07,829 algorithme compliqué. 414 00:17:07,829 --> 00:17:09,760 Mais pour aujourd'hui, le trade-off est le temps et dans l'espace. 415 00:17:09,760 --> 00:17:11,930 >> Donc, si vous pouviez juste levez numéros afin que nous puissions voir que vous êtes 416 00:17:11,930 --> 00:17:15,839 en effet correspondant 4, 2, 6, 1, 3, 7, 8. 417 00:17:15,839 --> 00:17:16,599 Excellente. 418 00:17:16,599 --> 00:17:19,520 Donc, je vais essayer d'orchestrer choses, si vous les gars ne peux 419 00:17:19,520 --> 00:17:21,800 suivre mon exemple ici. 420 00:17:21,800 --> 00:17:26,650 >> Je vais donc mettre en œuvre, d'abord, l' première étape du pseudo-code, qui est 421 00:17:26,650 --> 00:17:29,440 sur l'entrée de n éléments, si n est égal à inférieur à 2, puis revenir. 422 00:17:29,440 --> 00:17:31,370 Évidemment, cela ne veut pas s'appliquent, si nous passons. 423 00:17:31,370 --> 00:17:33,340 Donc trier la moitié gauche des éléments. 424 00:17:33,340 --> 00:17:36,220 Donc, cela signifie que je vais concentrer mon attention pour un instant sur ces 425 00:17:36,220 --> 00:17:37,310 quatre gars ici. 426 00:17:37,310 --> 00:17:39,774 Bon, qu'est-ce que je fais à côté? 427 00:17:39,774 --> 00:17:40,570 >> AUDIENCE: tri de la moitié gauche. 428 00:17:40,570 --> 00:17:42,780 >> DAVID MALAN: Alors maintenant, je dois trier la moitié gauche de ces gars-là. 429 00:17:42,780 --> 00:17:45,580 Parce qu'encore une fois, assumer vous-même l' objectif est de trier la moitié gauche. 430 00:17:45,580 --> 00:17:46,440 Comment pouvez-vous faire cela? 431 00:17:46,440 --> 00:17:49,140 Il suffit de suivre les instructions, même si nous le faisons encore. 432 00:17:49,140 --> 00:17:50,160 Donc trier la moitié gauche. 433 00:17:50,160 --> 00:17:52,030 Maintenant, je vais trier ces deux gars. 434 00:17:52,030 --> 00:17:53,563 Qu'est-ce qui vient après? 435 00:17:53,563 --> 00:17:54,510 >> AUDIENCE: trier la moitié gauche. 436 00:17:54,510 --> 00:17:55,460 >> DAVID MALAN: tri de la moitié gauche. 437 00:17:55,460 --> 00:18:00,680 Alors maintenant, ces derniers, ce siège ici, est une liste de taille 1. 438 00:18:00,680 --> 00:18:01,365 Et quel est votre nom? 439 00:18:01,365 --> 00:18:02,390 >> PRINCESSE DAISY: Princesse Daisy. 440 00:18:02,390 --> 00:18:03,690 >> DAVID MALAN: Princesse Daisy est ici. 441 00:18:03,690 --> 00:18:07,470 Et si elle est déjà trié, parce que la liste est de taille 1. 442 00:18:07,470 --> 00:18:09,490 Que dois-je faire la prochaine? 443 00:18:09,490 --> 00:18:13,680 OK, revenir, parce que cette liste est d' taille 1, qui est inférieur à 2. 444 00:18:13,680 --> 00:18:14,320 Alors quelle est la prochaine étape? 445 00:18:14,320 --> 00:18:17,490 Et maintenant que vous avez à type de revenir en arrière dans votre esprit. 446 00:18:17,490 --> 00:18:19,340 >> Trier la moitié droite, ce qui est - 447 00:18:19,340 --> 00:18:19,570 Quel est votre nom? 448 00:18:19,570 --> 00:18:20,220 >> Linda: Linda. 449 00:18:20,220 --> 00:18:20,980 >> DAVID MALAN: Linda. 450 00:18:20,980 --> 00:18:23,210 Et que faisons-nous maintenant que nous avons une liste de taille 1? 451 00:18:23,210 --> 00:18:24,440 >> AUDIENCE: Return. 452 00:18:24,440 --> 00:18:24,760 >> DAVID MALAN: Attention. 453 00:18:24,760 --> 00:18:29,540 Nous revenons d'abord, et maintenant la troisième étape - et si je genre de dépeindre par 454 00:18:29,540 --> 00:18:33,490 embrassant les deux sièges maintenant, maintenant je disposer de fusionner ces deux éléments. 455 00:18:33,490 --> 00:18:35,530 Alors maintenant, malheureusement, les éléments sont hors d'usage. 456 00:18:35,530 --> 00:18:39,920 Mais c'est là que le processus de fusion commence à obtenir convaincante. 457 00:18:39,920 --> 00:18:42,410 >> Donc, si vous pouviez défendre seulement un moment, je vais avoir besoin de vous, dans un 458 00:18:42,410 --> 00:18:44,170 moment, à l'étape derrière votre chaise. 459 00:18:44,170 --> 00:18:46,480 Et si Linda, parce que 2 est inférieur à 4, pourquoi ne pas 460 00:18:46,480 --> 00:18:48,130 vous venez autour première? 461 00:18:48,130 --> 00:18:48,690 Restez là. 462 00:18:48,690 --> 00:18:50,520 Donc, Linda, vous venez d'abord. 463 00:18:50,520 --> 00:18:53,820 >> Or, dans la réalité si c'est juste un tableau nous pourrions simplement déplacer son en temps réel 464 00:18:53,820 --> 00:18:55,360 à partir de ce fauteuil à cet endroit. 465 00:18:55,360 --> 00:18:57,770 Alors, imaginez qui a eu une constante nombre d'étapes 1. 466 00:18:57,770 --> 00:18:58,480 Et maintenant - 467 00:18:58,480 --> 00:19:01,490 mais nous avons besoin de vous mettre en le premier emplacement ici. 468 00:19:01,490 --> 00:19:03,930 >> Et maintenant, si vous pouviez venir autour, ainsi, nous allons 469 00:19:03,930 --> 00:19:06,300 être en position deux. 470 00:19:06,300 --> 00:19:09,120 Et même si cela se sent comme c'est prendre un certain temps, ce qui est bien c'est maintenant 471 00:19:09,120 --> 00:19:14,710 que la moitié gauche de l' la moitié gauche est maintenant triée. 472 00:19:14,710 --> 00:19:18,010 Alors quelle est la prochaine étape, si nous maintenant rembobiner plus loin dans l'histoire? 473 00:19:18,010 --> 00:19:18,980 >> AUDIENCE: la moitié droite. 474 00:19:18,980 --> 00:19:19,900 >> DAVID MALAN: tri de la moitié droite. 475 00:19:19,900 --> 00:19:21,320 Alors vous les gars ont à faire, aussi bien. 476 00:19:21,320 --> 00:19:23,510 Donc, si vous pouvez résister pour un instant? 477 00:19:23,510 --> 00:19:25,192 Et quel est votre nom? 478 00:19:25,192 --> 00:19:25,540 >> JESS: Jess. 479 00:19:25,540 --> 00:19:25,870 >> DAVID MALAN: Jess. 480 00:19:25,870 --> 00:19:29,720 OK, donc Jess est maintenant à gauche la moitié de la moitié droite. 481 00:19:29,720 --> 00:19:31,400 Et si c'est une liste de taille 1. 482 00:19:31,400 --> 00:19:32,380 Elle est évidemment triée. 483 00:19:32,380 --> 00:19:33,070 Et votre nom? 484 00:19:33,070 --> 00:19:33,630 >> MICHELLE: Michelle. 485 00:19:33,630 --> 00:19:35,340 >> DAVID MALAN: Michelle est évidemment une liste de taille 1. 486 00:19:35,340 --> 00:19:36,050 Elle a déjà triée. 487 00:19:36,050 --> 00:19:38,690 Alors maintenant, la magie opère, le processus de fusion. 488 00:19:38,690 --> 00:19:39,790 Alors, qui va venir d'abord? 489 00:19:39,790 --> 00:19:41,560 Évidemment, Michelle. 490 00:19:41,560 --> 00:19:43,280 Donc, si vous pouviez venir autour du dos. 491 00:19:43,280 --> 00:19:47,090 L'espace dont nous disposons pour elle maintenant est juste derrière cette chaise ici. 492 00:19:47,090 --> 00:19:51,580 Et maintenant, si vous pouviez revenir ainsi, nous avons maintenant, pour être clair, deux 493 00:19:51,580 --> 00:19:53,810 moitiés, chacune de taille 2 - 494 00:19:53,810 --> 00:19:57,090 et juste pour l'amour de représentation, si vous pourrait faire un peu d'espace - 495 00:19:57,090 --> 00:19:59,780 une moitié gauche ici, on la moitié droite ici. 496 00:19:59,780 --> 00:20:01,160 >> Rembobinez plus loin dans l'histoire. 497 00:20:01,160 --> 00:20:02,270 Quelle étape est le prochain? 498 00:20:02,270 --> 00:20:03,030 >> AUDIENCE: Fusionner. 499 00:20:03,030 --> 00:20:04,160 >> DAVID MALAN: Nous avons donc maintenant à fusionner. 500 00:20:04,160 --> 00:20:07,490 Alors OK, maintenant, heureusement, nous juste libéré quatre chaises. 501 00:20:07,490 --> 00:20:11,480 Donc, nous avons utilisé deux fois plus de mémoire, mais nous pouvons donner volte-face entre 502 00:20:11,480 --> 00:20:12,330 les deux tableaux. 503 00:20:12,330 --> 00:20:14,190 Alors quel numéro est à venir d'abord? 504 00:20:14,190 --> 00:20:14,850 Donc, Michelle, évidemment. 505 00:20:14,850 --> 00:20:16,680 Alors venez autour et de prendre votre siège ici. 506 00:20:16,680 --> 00:20:19,120 Et puis le numéro 2 est évidemment prochaine, si vous venez ici. 507 00:20:19,120 --> 00:20:21,520 Numéro 4, numéro 6. 508 00:20:21,520 --> 00:20:23,390 Et encore, même si il ya une peu de marche à pied, 509 00:20:23,390 --> 00:20:26,010 vraiment, ceux-ci pourraient se produire instantanément, en déplaçant une - 510 00:20:26,010 --> 00:20:26,880 OK, bien joué. 511 00:20:26,880 --> 00:20:28,350 >> [Rires] 512 00:20:28,350 --> 00:20:29,680 >> DAVID MALAN: Et maintenant nous sommes en assez bonne forme. 513 00:20:29,680 --> 00:20:34,910 La moitié gauche de l'ensemble entrée a été trié. 514 00:20:34,910 --> 00:20:37,370 Très bien, alors ces gars-là avait l'avantage de ma - 515 00:20:37,370 --> 00:20:40,340 Comment at-il finir toutes les filles sur le à gauche et tous les garçons sur la droite? 516 00:20:40,340 --> 00:20:42,450 >> OK, donc les gars au tour maintenant. 517 00:20:42,450 --> 00:20:44,680 Donc, je ne vais pas vous guidera à travers ces étapes. 518 00:20:44,680 --> 00:20:46,550 Nous allons voir si nous pouvons présenter une nouvelle demande le même pseudo. 519 00:20:46,550 --> 00:20:50,050 Si vous voulez aller de l'avant et se tenir debout, et vous les gars, laissez-moi vous donner le micro. 520 00:20:50,050 --> 00:20:52,990 Voyez si vous ne pouvez pas reproduire ce nous venons de faire ici sur la 521 00:20:52,990 --> 00:20:53,880 autre fin de la liste. 522 00:20:53,880 --> 00:20:59,530 Qui a besoin de parler le premier, sur la base de l'algorithme? 523 00:20:59,530 --> 00:21:03,210 Alors, expliquez ce que vous faites avant vous faites des mouvements du pied. 524 00:21:03,210 --> 00:21:05,930 >> INTERLOCUTEUR 1: D'accord, donc depuis Je suis la moitié gauche de l' 525 00:21:05,930 --> 00:21:07,790 la moitié gauche, je reviens. 526 00:21:07,790 --> 00:21:08,730 Droite? 527 00:21:08,730 --> 00:21:09,250 >> DAVID MALAN: Bon. 528 00:21:09,250 --> 00:21:10,350 >> INTERLOCUTEUR 1: Et puis - 529 00:21:10,350 --> 00:21:11,800 >> DAVID MALAN: Qui fait le micro aller à la prochaine? 530 00:21:11,800 --> 00:21:12,920 >> INTERLOCUTEUR 1: numéro suivant. 531 00:21:12,920 --> 00:21:14,720 >> ENCEINTE 2: Je suis donc la moitié droite de la moitié gauche de l' 532 00:21:14,720 --> 00:21:17,830 la moitié gauche, et je reviens. 533 00:21:17,830 --> 00:21:18,050 >> DAVID MALAN: Bon. 534 00:21:18,050 --> 00:21:18,550 Vous revenez. 535 00:21:18,550 --> 00:21:21,855 Alors maintenant, quelle est la prochaine étape pour vous deux? 536 00:21:21,855 --> 00:21:23,740 >> ENCEINTE 2: Nous voulons voir qui est plus petit. 537 00:21:23,740 --> 00:21:24,200 >> DAVID MALAN: Exactement. 538 00:21:24,200 --> 00:21:24,940 Nous voulons fusionner. 539 00:21:24,940 --> 00:21:27,590 L'espace que nous allons utiliser pour fusionner vous en, même si elles sont 540 00:21:27,590 --> 00:21:30,250 évidemment déjà triés, nous allons de suivre le même algorithme. 541 00:21:30,250 --> 00:21:31,560 Alors, qui va dans le dos en premier? 542 00:21:31,560 --> 00:21:35,720 Donc 3, puis 7. 543 00:21:35,720 --> 00:21:38,570 Et maintenant le micro va à ces gars-là, OK? 544 00:21:38,570 --> 00:21:43,590 >> Intervenant 3: Je suis la moitié droite de l' la moitié gauche, et mon n est inférieur 545 00:21:43,590 --> 00:21:45,048 1, donc je vais juste passer - 546 00:21:45,048 --> 00:21:46,380 >> DAVID MALAN: Bon. 547 00:21:46,380 --> 00:21:49,450 >> Intervenant 4: Je suis la moitié droite de l' la moitié droite de la moitié droite, et je suis 548 00:21:49,450 --> 00:21:51,740 aussi une personne, donc je suis va revenir. 549 00:21:51,740 --> 00:21:52,990 Alors maintenant, nous fusionnons. 550 00:21:52,990 --> 00:21:55,140 551 00:21:55,140 --> 00:21:56,150 >> Intervenant 3: Donc nous retournons. 552 00:21:56,150 --> 00:21:57,160 >> DAVID MALAN: Donc vous allez dans le dos. 553 00:21:57,160 --> 00:21:59,200 Donc 5 passe en premier, puis 8. 554 00:21:59,200 --> 00:22:01,240 Et maintenant public, qui est la étape, nous devons maintenant revenir en arrière 555 00:22:01,240 --> 00:22:02,200 sauvegarder dans nos esprits? 556 00:22:02,200 --> 00:22:02,940 >> AUDIENCE: Fusionner. 557 00:22:02,940 --> 00:22:07,270 >> DAVID MALAN: Fusion moitié gauche et à droite la moitié de la moitié gauche d'origine. 558 00:22:07,270 --> 00:22:08,840 Alors maintenant - 559 00:22:08,840 --> 00:22:10,520 et juste pour que cela soit clair, faire un peu d'espace 560 00:22:10,520 --> 00:22:11,690 entre vous deux les gars. 561 00:22:11,690 --> 00:22:13,800 Alors maintenant, c'est les deux listes, à gauche et à droite. 562 00:22:13,800 --> 00:22:18,320 Alors, comment pouvons-nous vous fusionnez maintenant les gars en la première rangée de sièges à nouveau? 563 00:22:18,320 --> 00:22:19,600 >> 3 passe en premier. 564 00:22:19,600 --> 00:22:20,850 Puis 5, évidemment. 565 00:22:20,850 --> 00:22:23,110 566 00:22:23,110 --> 00:22:27,330 Ensuite, 7, 8 et maintenant. 567 00:22:27,330 --> 00:22:28,710 OK, et maintenant nous sommes? 568 00:22:28,710 --> 00:22:29,650 >> Audience: non fait. 569 00:22:29,650 --> 00:22:32,440 >> DAVID MALAN: pas fait, parce que évidemment, il ya une étape restante. 570 00:22:32,440 --> 00:22:35,720 Mais encore une fois, la raison pour laquelle je suis en utilisant cette jargon comme "rewind dans votre esprit», 571 00:22:35,720 --> 00:22:37,160 c'est parce que c'est vraiment ce qui se passe. 572 00:22:37,160 --> 00:22:39,610 Nous allons à travers toutes ces étapes, mais nous sommes en quelque sorte une pause pour un 573 00:22:39,610 --> 00:22:42,480 moment, plongée profondément dans le algorithme, s'arrêtant un instant, 574 00:22:42,480 --> 00:22:45,840 plonger plus profondément dans l'algorithme, et Maintenant, nous devons trier du rembobinage dans notre 575 00:22:45,840 --> 00:22:49,430 esprit et annuler toutes ces couches que nous avons en quelque sorte mis en attente. 576 00:22:49,430 --> 00:22:51,790 >> Nous avons donc maintenant deux listes de taille 4. 577 00:22:51,790 --> 00:22:54,790 Si vous pouviez lever une dernière fois et de faire un peu de place ici pour 578 00:22:54,790 --> 00:22:57,230 clairement que c'est la gauche moitié de l'original, l' 579 00:22:57,230 --> 00:22:58,620 la moitié droite de l'original. 580 00:22:58,620 --> 00:23:01,060 Qui est le premier numéro que nous besoin de tirer dans le dos? 581 00:23:01,060 --> 00:23:01,870 Michelle, bien sûr. 582 00:23:01,870 --> 00:23:03,230 >> Nous avons donc mis Michelle ici. 583 00:23:03,230 --> 00:23:05,080 Et qui a le numéro 2? 584 00:23:05,080 --> 00:23:06,440 Numéro 2 vient sur le dos aussi. 585 00:23:06,440 --> 00:23:07,800 Numéro 3? 586 00:23:07,800 --> 00:23:08,510 Excellente. 587 00:23:08,510 --> 00:23:16,570 Numéro 4, numéro 5, numéro 6, numéro 7 et numéro 8. 588 00:23:16,570 --> 00:23:18,850 >> OK, donc il se sentait comme un grand d'étapes, pour sûr. 589 00:23:18,850 --> 00:23:22,390 Mais maintenant nous allons voir si nous ne pouvons pas confirmer sorte d'intuition que cette 590 00:23:22,390 --> 00:23:26,190 algorithme fondamentalement, d'autant plus que n devient vraiment grand, comme nous l'avons vu 591 00:23:26,190 --> 00:23:29,170 avec des animations, est fondamentalement plus rapide. 592 00:23:29,170 --> 00:23:33,400 Donc je revendique cet algorithme, dans le pire cas et même dans le meilleur des cas, 593 00:23:33,400 --> 00:23:36,160 est grand O n log n fois. 594 00:23:36,160 --> 00:23:39,160 Autrement dit, il ya certains aspects de cette algorithme qui prend n étapes, mais 595 00:23:39,160 --> 00:23:43,110 il ya un autre aspect quelque part dans cette itération, que boucle, qui 596 00:23:43,110 --> 00:23:44,410 prend log n étapes. 597 00:23:44,410 --> 00:23:49,154 Peut-on mettre le doigt sur ce que ceux deux numéros font référence à? 598 00:23:49,154 --> 00:23:51,320 Eh bien, où - 599 00:23:51,320 --> 00:23:54,160 Où as le micro aller? 600 00:23:54,160 --> 00:23:58,660 >> ENCEINTE 1: Est-ce le journal n être nous briser en deux - 601 00:23:58,660 --> 00:23:59,630 en divisant par deux, pour l'essentiel. 602 00:23:59,630 --> 00:24:00,120 >> DAVID MALAN: Exactement. 603 00:24:00,120 --> 00:24:03,000 Chaque fois que nous voyons dans n'importe quel algorithme ainsi Jusqu'ici, il ya eu ce modèle de 604 00:24:03,000 --> 00:24:04,200 diviser, la division, la division. 605 00:24:04,200 --> 00:24:05,700 Et il est généralement réduite à quelque chose qui est 606 00:24:05,700 --> 00:24:07,100 logarithmique, log base 2. 607 00:24:07,100 --> 00:24:10,180 Mais il pourrait être n'importe quoi, mais vous identifier base 2. 608 00:24:10,180 --> 00:24:11,330 >> Maintenant, qu'en est-il n? 609 00:24:11,330 --> 00:24:14,550 Je vois que nous avons sorte de vous divisés les gars - vous divisé, vous divisées, 610 00:24:14,550 --> 00:24:15,910 vous divise, vous divisée. 611 00:24:15,910 --> 00:24:18,760 D'où vient la fin de? 612 00:24:18,760 --> 00:24:19,810 >> Donc, c'est la fusion. 613 00:24:19,810 --> 00:24:20,610 Parce que penser. 614 00:24:20,610 --> 00:24:25,420 Lorsque vous fusionnez huit personnes ensemble, selon laquelle la moitié d'entre eux sont un ensemble de quatre 615 00:24:25,420 --> 00:24:27,770 et l'autre moitié est un autre ensemble de quatre, comment allez-vous 616 00:24:27,770 --> 00:24:28,820 de faire la fusion? 617 00:24:28,820 --> 00:24:30,830 Eh bien, les gars vous at-elle assez intuitive. 618 00:24:30,830 --> 00:24:34,140 >> Mais si je l'ai fait à la place un peu plus méthodiquement, je pourrais avoir pointé 619 00:24:34,140 --> 00:24:38,090 la personne la plus à gauche d'abord avec ma gauche main, pointé vers la personne la plus à gauche 620 00:24:38,090 --> 00:24:42,080 de la moitié de ma main droite, et juste par la suite traversé la 621 00:24:42,080 --> 00:24:46,990 liste, montrant le plus petit élément à chaque fois, se déplaçant le doigt dessus et 622 00:24:46,990 --> 00:24:48,970 plus que nécessaire tout au long de la liste. 623 00:24:48,970 --> 00:24:51,890 Mais quelle est la clé de cette fusion processus est je compare ces paires 624 00:24:51,890 --> 00:24:53,460 des éléments. 625 00:24:53,460 --> 00:24:57,270 De la moitié droite et de la gauche demi, je n'ai jamais faire marche arrière. 626 00:24:57,270 --> 00:25:00,570 >> Ainsi, la fusion elle-même prend pas plus de n étapes. 627 00:25:00,570 --> 00:25:03,250 Et combien de fois ai-je eu faire que la fusion? 628 00:25:03,250 --> 00:25:07,150 Eh bien, pas plus que n, et nous venons d' vu que la fusion finale. 629 00:25:07,150 --> 00:25:13,120 Et si vous faites quelque chose qui prend log n étapes n fois, ou vice versa, 630 00:25:13,120 --> 00:25:15,210 il va nous n log n fois donner. 631 00:25:15,210 --> 00:25:16,310 >> Et pourquoi est-ce mieux? 632 00:25:16,310 --> 00:25:19,600 Eh bien, si nous savons déjà que log n est mieux que n - à droite? 633 00:25:19,600 --> 00:25:22,590 Nous avons vu, à la recherche binaire, l'annuaire exemple, log n était certainement 634 00:25:22,590 --> 00:25:23,760 mieux que linéaire. 635 00:25:23,760 --> 00:25:28,420 Cela signifie donc que n log n fois est certainement mieux que n fois un autre 636 00:25:28,420 --> 00:25:30,390 n, n Alias ​​carré. 637 00:25:30,390 --> 00:25:32,400 Et c'est ce que nous ressentons en fin de compte. 638 00:25:32,400 --> 00:25:34,928 >> Alors salve d'applaudissements, si nous avons pu, pour ces gars-là. 639 00:25:34,928 --> 00:25:38,920 >> [Applaudissements] 640 00:25:38,920 --> 00:25:41,550 >> DAVID MALAN: Et vos cadeaux de départ - vous pouvez garder les numéros, 641 00:25:41,550 --> 00:25:44,010 si vous le souhaitez. 642 00:25:44,010 --> 00:25:45,620 Et votre cadeau d'adieu, comme d'habitude. 643 00:25:45,620 --> 00:25:47,290 Oh, et nous vous enverrons le film, Michelle. 644 00:25:47,290 --> 00:25:48,343 Je vous remercie. 645 00:25:48,343 --> 00:25:49,250 Très bien. 646 00:25:49,250 --> 00:25:50,400 Servez-vous d'une balle anti-stress. 647 00:25:50,400 --> 00:25:54,110 >> Et laissez-moi m'arrête, dans l'intervalle, notre ami Rob Bowden à offrir 648 00:25:54,110 --> 00:25:59,520 perspective un peu différente sur ce point, puisque vous pouvez penser à ces 649 00:25:59,520 --> 00:26:01,280 étapes se déroulent dans un peu manière différente. 650 00:26:01,280 --> 00:26:04,750 En fait, la mise en place de ce que Rob est sur le point pour nous montrer suppose que nous avons 651 00:26:04,750 --> 00:26:09,030 déjà fait la répartition de la grande liste en huit petites listes, 652 00:26:09,030 --> 00:26:10,570 chacun de taille 1. 653 00:26:10,570 --> 00:26:13,350 >> Nous allons donc changer le pseudo d'un peu juste sorte de faire au 654 00:26:13,350 --> 00:26:15,320 idée de base du fonctionnement de fusion. 655 00:26:15,320 --> 00:26:17,600 Mais le temps d'exécution de ce il s'agit de faire est encore 656 00:26:17,600 --> 00:26:19,110 va être la même. 657 00:26:19,110 --> 00:26:23,540 Et encore, la mise en place ici, c'est qu'il est commencé avec huit listes de taille 1. 658 00:26:23,540 --> 00:26:27,730 Alors vous avez raté la partie où il est effectivement fait le journal n log n, log n 659 00:26:27,730 --> 00:26:31,205 division de l'entrée. 660 00:26:31,205 --> 00:26:32,120 >> [LECTURE VIDEO] 661 00:26:32,120 --> 00:26:33,615 >> -C'est tout pour la première étape. 662 00:26:33,615 --> 00:26:38,270 Pour la deuxième étape, à plusieurs reprises fusionner des paires de listes. 663 00:26:38,270 --> 00:26:39,210 >> DAVID MALAN: Hm. 664 00:26:39,210 --> 00:26:41,270 Seulement audio est à venir sur mon ordinateur. 665 00:26:41,270 --> 00:26:42,520 Essayons encore une fois. 666 00:26:42,520 --> 00:26:45,330 667 00:26:45,330 --> 00:26:48,310 >> -Il suffit de choisir arbitrairement qui - Nous avons maintenant quatre listes. 668 00:26:48,310 --> 00:26:51,590 669 00:26:51,590 --> 00:26:52,120 En savoir avant. 670 00:26:52,120 --> 00:26:53,040 >> DAVID MALAN: Nous y voilà. 671 00:26:53,040 --> 00:27:00,510 >> -Fusion 108 et 15, nous finissons avec la liste 15, 108. 672 00:27:00,510 --> 00:27:07,170 La fusion de 50 et 4, nous retrouver avec 4, 50. 673 00:27:07,170 --> 00:27:12,990 Fusion 8 et 42, nous retrouver avec 8, 42. 674 00:27:12,990 --> 00:27:19,970 Et la fusion de 23 et 16, nous retrouver avec 16, 23. 675 00:27:19,970 --> 00:27:23,270 >> Maintenant, toutes nos listes sont de taille 2. 676 00:27:23,270 --> 00:27:26,690 Notez que chacun des quatre listes sont triées. 677 00:27:26,690 --> 00:27:29,450 Donc, nous pouvons commencer à fusionner des paires de listes nouveau. 678 00:27:29,450 --> 00:27:38,420 Fusion 15 et 108 et les 4 et 50, nous d'abord prendre le 4, puis le 15, puis 679 00:27:38,420 --> 00:27:41,500 le 50, puis le 108. 680 00:27:41,500 --> 00:27:50,610 Fusion 8, 42 et 16, 23, nous prenons d'abord le 8, puis le 16, puis le 23, 681 00:27:50,610 --> 00:27:52,700 puis le 42. 682 00:27:52,700 --> 00:27:57,600 >> Alors maintenant, nous avons seulement deux listes de taille 4, dont chacun est triée. 683 00:27:57,600 --> 00:28:01,170 Alors maintenant, nous fusionnons ces deux listes. 684 00:28:01,170 --> 00:28:11,835 Tout d'abord, nous prenons le 4, puis nous prenons le 8, puis nous prenons le 15, puis 16, puis 685 00:28:11,835 --> 00:28:19,456 23, puis 42, puis 50, puis 108. 686 00:28:19,456 --> 00:28:19,872 >> [FIN LECTURE VIDÉO] 687 00:28:19,872 --> 00:28:23,430 >> DAVID MALAN: Encore une fois, un avis, il n'a jamais touché une tasse donné plus d'une fois 688 00:28:23,430 --> 00:28:24,860 après avoir progressé au-delà. 689 00:28:24,860 --> 00:28:26,200 Alors qu'il n'a jamais répéter. 690 00:28:26,200 --> 00:28:29,850 Donc, il est toujours en mouvement sur le côté, et c'est là que nous avons eu notre n. 691 00:28:29,850 --> 00:28:33,290 >> Pourquoi ne pas laisser me soulever une animation que nous avons vu précédemment, mais cette fois 692 00:28:33,290 --> 00:28:35,110 se concentrer uniquement sur le tri par fusion. 693 00:28:35,110 --> 00:28:38,030 Permettez-moi d'aller de l'avant et de zoom sur cette ici. 694 00:28:38,030 --> 00:28:42,530 D'abord, permettez-moi à choisir une entrée aléatoire, magnifier cela, et vous pouvez trier de voir 695 00:28:42,530 --> 00:28:46,600 ce que nous avons pris pour acquis, plus tôt, le tri par fusion est en train de faire. 696 00:28:46,600 --> 00:28:50,330 >> Donc remarquerez que vous obtenez ces moitiés ou ces quartiers ou ces huitièmes de la 697 00:28:50,330 --> 00:28:53,140 problème qui tout d'un coup commencer à prendre la bonne forme. 698 00:28:53,140 --> 00:28:57,070 Et puis enfin, vous voyez à la toute fin que bam, 699 00:28:57,070 --> 00:28:58,860 tout est fusionné ensemble. 700 00:28:58,860 --> 00:29:01,690 >> Donc, ce ne sont que trois différents prend la même idée. 701 00:29:01,690 --> 00:29:05,980 Mais l'idée fondamentale, tout comme fracture et la conquête de la première classe, 702 00:29:05,980 --> 00:29:10,640 c'est que nous avons décidé de diviser en quelque sorte le problème en quelque chose de grand, en 703 00:29:10,640 --> 00:29:14,760 quelque chose sorte d'identique dans l'esprit, mais plus petite et plus petite et plus petite 704 00:29:14,760 --> 00:29:15,660 et plus petits. 705 00:29:15,660 --> 00:29:18,420 >> Maintenant, une autre façon amusante de tri de penser sur ceux-ci, même si elle n'est pas 706 00:29:18,420 --> 00:29:20,520 vais vous donner la même intuitive compréhension, est 707 00:29:20,520 --> 00:29:21,640 l'animation suivante. 708 00:29:21,640 --> 00:29:25,400 Donc, c'est un quelqu'un vidéo mis en place celle associée différente 709 00:29:25,400 --> 00:29:29,970 sons avec les diverses opérations de tri par insertion, par le tri par fusion, et 710 00:29:29,970 --> 00:29:31,150 pour un couple des autres. 711 00:29:31,150 --> 00:29:32,330 Donc, en un instant, je vais frapper Play. 712 00:29:32,330 --> 00:29:33,600 C'est environ une minute. 713 00:29:33,600 --> 00:29:37,410 Et même si vous pouvez encore voir l' les modèles se passe, cette fois vous pouvez 714 00:29:37,410 --> 00:29:41,420 également entendre comment ces algorithmes sont effectuer différemment et avec 715 00:29:41,420 --> 00:29:43,950 motifs quelque peu différents. 716 00:29:43,950 --> 00:29:45,830 >> C'est le tri par insertion. 717 00:29:45,830 --> 00:29:50,400 >> [TONS Lecture en cours] 718 00:29:50,400 --> 00:29:52,400 >> DAVID MALAN: Il essaie à nouveau pour insérer chaque élément 719 00:29:52,400 --> 00:29:52,900 dans laquelle elle appartient. 720 00:29:52,900 --> 00:29:54,628 C'est sorte de bulle. 721 00:29:54,628 --> 00:30:10,097 >> [TONS Lecture en cours] 722 00:30:10,097 --> 00:30:13,630 >> DAVID MALAN: Et vous pouvez trier des sensations comment relativement peu de travail qu'il fait 723 00:30:13,630 --> 00:30:15,834 à chaque étape. 724 00:30:15,834 --> 00:30:20,470 C'est ce qui sonne comme ennui. 725 00:30:20,470 --> 00:30:21,472 >> [TONS Lecture en cours] 726 00:30:21,472 --> 00:30:25,222 >> DAVID MALAN: C'est sélection sorte, où nous sélectionnons l'élément que nous voulons par 727 00:30:25,222 --> 00:30:28,845 en passant par encore et encore et encore et de le mettre au début. 728 00:30:28,845 --> 00:30:37,674 >> [TONS Lecture en cours] 729 00:30:37,674 --> 00:30:43,970 >> DAVID MALAN: C'est le tri par fusion, qui vous pouvez vraiment commencer à sentir. 730 00:30:43,970 --> 00:30:51,810 >> [TONS Lecture en cours] 731 00:30:51,810 --> 00:30:54,770 >> [Rires] 732 00:30:54,770 --> 00:30:58,395 >> DAVID MALAN: Quelque chose appelé gnome sorte, que nous n'avons pas examiné. 733 00:30:58,395 --> 00:31:13,630 >> [TONS Lecture en cours] 734 00:31:13,630 --> 00:31:17,910 >> DAVID MALAN: Alors, laissez-moi voir, maintenant, distrait que vous êtes Espérons que le 735 00:31:17,910 --> 00:31:21,110 musique, si je peux glisser un peu peu de mathématiques ici. 736 00:31:21,110 --> 00:31:24,850 Donc, il ya une quatrième façon que nous pouvons réfléchir à ce que ces moyens 737 00:31:24,850 --> 00:31:29,210 fonctions pour être plus rapide que ceux que nous avons vu auparavant. 738 00:31:29,210 --> 00:31:32,470 Et si vous venez au cours de un fond de mathématiques, vous 739 00:31:32,470 --> 00:31:36,030 savoir en fait peut-être déjà que vous peut gifler un terme à cette technique - 740 00:31:36,030 --> 00:31:40,400 à savoir la récursivité, une fonction qui se dit en quelque sorte. 741 00:31:40,400 --> 00:31:44,780 >> Et encore une fois, rappelons que le tri par fusion pseudocode était récursive dans le sens 742 00:31:44,780 --> 00:31:48,460 que l'une des étapes de tri par fusion était d'appeler sorte - 743 00:31:48,460 --> 00:31:49,740 qui est, elle-même. 744 00:31:49,740 --> 00:31:52,480 Mais heureusement, parce que nous avons gardé appelant tri ou tri par fusion, 745 00:31:52,480 --> 00:31:55,880 plus précisément, sur un plus petit et plus petit et petite liste, nous avons finalement 746 00:31:55,880 --> 00:32:00,005 creux de la vague grâce à ce que nous appellerons un scénario de base, le cas codée en dur qui 747 00:32:00,005 --> 00:32:04,270 dit que si la liste est petit, moins de 2 dans ce cas, il suffit de retourner immédiatement. 748 00:32:04,270 --> 00:32:07,550 Si nous n'avions pas ce cas particulier, le algorithme n'aurait jamais toucher le fond, 749 00:32:07,550 --> 00:32:11,010 et vous auriez fait entrer dans un boucle infinie vraiment jamais. 750 00:32:11,010 --> 00:32:14,330 >> Mais supposons que nous voulions maintenant mettre quelques chiffres à ce sujet, à nouveau, en utilisant n 751 00:32:14,330 --> 00:32:15,660 comme la dimension de l'entrée. 752 00:32:15,660 --> 00:32:18,680 Et je voulais vous demander, qu'est-ce le temps total impliqués dans 753 00:32:18,680 --> 00:32:19,800 courir tri par fusion? 754 00:32:19,800 --> 00:32:22,960 Ou, plus généralement, quel est le coût de celui-ci dans le temps? 755 00:32:22,960 --> 00:32:24,730 >> Eh bien, c'est assez facile à mesurer. 756 00:32:24,730 --> 00:32:29,010 Si n est inférieur à 2, le temps impliqué dans le tri n éléments, 757 00:32:29,010 --> 00:32:30,480 où n est 2, est égal à 0. 758 00:32:30,480 --> 00:32:31,410 Parce que nous retournons juste. 759 00:32:31,410 --> 00:32:32,510 Il n'ya pas de travail à faire. 760 00:32:32,510 --> 00:32:35,660 Maintenant, sans doute, c'est peut-être une ou deux étapes des mesures pour déterminer le montant de 761 00:32:35,660 --> 00:32:38,420 travail, mais il est assez proche de 0 que Je vais juste dire qu'aucun travail n'est 762 00:32:38,420 --> 00:32:40,940 requis si la liste est si petit d'être inintéressant. 763 00:32:40,940 --> 00:32:42,580 >> Mais ce cas est intéressant. 764 00:32:42,580 --> 00:32:47,320 Le cas récursif était la branche de le pseudo-code qui dit autre, en quelque sorte 765 00:32:47,320 --> 00:32:52,000 la moitié gauche, trier le bon la moitié, de fusionner les deux moitiés. 766 00:32:52,000 --> 00:32:55,530 Maintenant, pourquoi cette expression représenter cette dépense? 767 00:32:55,530 --> 00:32:58,690 Eh bien, T de n signifie simplement que l' le temps de trier n éléments. 768 00:32:58,690 --> 00:33:03,070 Et puis sur le côté droit de l' signe égal là, le T de n divisé 769 00:33:03,070 --> 00:33:06,600 par 2 se réfère au coût de quoi? 770 00:33:06,600 --> 00:33:07,570 Tri de la moitié gauche. 771 00:33:07,570 --> 00:33:10,990 L'autre T de n divisé par 2 est fait probablement référence au coût de 772 00:33:10,990 --> 00:33:12,390 trier la moitié droite. 773 00:33:12,390 --> 00:33:14,590 >> Et puis le plus n? 774 00:33:14,590 --> 00:33:15,420 Est la fusion. 775 00:33:15,420 --> 00:33:19,120 Parce que si vous avez deux listes, l'une des taille n sur 2 et un autre de taille n 776 00:33:19,120 --> 00:33:22,580 plus de 2, vous devez toucher essentiellement chacun de ces éléments, tout comme Rob 777 00:33:22,580 --> 00:33:24,990 touché chacun des gobelets, et juste comme nous l'avons souligné à chacun des 778 00:33:24,990 --> 00:33:26,310 bénévoles sur scène. 779 00:33:26,310 --> 00:33:28,790 Donc n est le coût de la fusion. 780 00:33:28,790 --> 00:33:31,780 >> Maintenant, malheureusement, cette formule C'est également lui-même récursive. 781 00:33:31,780 --> 00:33:36,390 Donc, si posé la question, si n est, disons, 16, si il ya 16 personnes sur scène 782 00:33:36,390 --> 00:33:40,670 ou 16 tasses dans la vidéo, combien au total mesures faut-il faire le tri 783 00:33:40,670 --> 00:33:41,550 avec tri par fusion? 784 00:33:41,550 --> 00:33:45,790 Il s'agit en fait pas une réponse évidente, parce que maintenant vous avez en quelque sorte 785 00:33:45,790 --> 00:33:48,500 récursive répondre à cette formule. 786 00:33:48,500 --> 00:33:51,190 >> Mais c'est OK, parce que je vous propose ce que nous faisons ce qui suit. 787 00:33:51,190 --> 00:33:56,670 Le temps nécessaire pour trier 16 personnes ou 16 tasses va être représenté 788 00:33:56,670 --> 00:33:58,020 généralement en T de 16 ans. 789 00:33:58,020 --> 00:34:01,400 Mais cela équivaut, selon notre formule précédente, 2 fois le montant 790 00:34:01,400 --> 00:34:04,780 de temps qu'il faut pour trier 8 tasses plus 16. 791 00:34:04,780 --> 00:34:08,590 Et encore une fois, plus 16 c'est le moment de fusionner, Et les deux fois T de 8 est le 792 00:34:08,590 --> 00:34:10,790 le temps de trier la moitié gauche et la moitié droite. 793 00:34:10,790 --> 00:34:11,989 >> Mais encore une fois, ce n'est pas suffisant. 794 00:34:11,989 --> 00:34:13,210 Nous devons plonger plus profond. 795 00:34:13,210 --> 00:34:16,409 Cela signifie que nous devons répondre à la question, ce qui est T de 8? 796 00:34:16,409 --> 00:34:19,610 Eh bien T de 8 à seulement 2 fois T de 4 et de 8. 797 00:34:19,610 --> 00:34:20,520 Eh bien, ce qui est de T 4? 798 00:34:20,520 --> 00:34:23,780 T 4 est à seulement 2 fois 2 T de plus 4. 799 00:34:23,780 --> 00:34:25,489 Eh bien, ce qui est de T 2? 800 00:34:25,489 --> 00:34:29,030 T 2 est de seulement 2 fois T de 1, plus 2. 801 00:34:29,030 --> 00:34:31,940 >> Et encore une fois, nous sommes en quelque sorte d'obtenir coincé dans ce cycle. 802 00:34:31,940 --> 00:34:34,790 Mais c'est sur le point de frapper ce dite cas de base. 803 00:34:34,790 --> 00:34:37,310 Car ce qui est de T 1, ne nous revendiquons? 804 00:34:37,310 --> 00:34:37,810 0. 805 00:34:37,810 --> 00:34:39,730 Alors maintenant, enfin, nous pouvons travailler à reculons. 806 00:34:39,730 --> 00:34:44,290 >> Si T 1 est égal à 0, je peux maintenant monter d'un Ligne à ce gars ici, et je ne peux 807 00:34:44,290 --> 00:34:46,330 branchez 0 pour T 1. 808 00:34:46,330 --> 00:34:51,770 Ce qui signifie qu'il est égal à 2 fois zéro, autrement connu comme 0, plus 2. 809 00:34:51,770 --> 00:34:53,739 Et afin que toute expression est 2. 810 00:34:53,739 --> 00:34:58,740 >> Maintenant, si je prends le T de 2, dont la réponse est 2, branchez-le sur la ligne médiane, T 811 00:34:58,740 --> 00:35:02,740 de 4, ça me donne 2 fois 2 + 4, donc 8. 812 00:35:02,740 --> 00:35:07,080 Si je branche ensuite dans 8 à la précédente ligne, qui me donne 2 fois 8, 16. 813 00:35:07,080 --> 00:35:12,470 Et si nous continuons alors que le 24, en ajoutant 16, nous obtenons finalement une 814 00:35:12,470 --> 00:35:13,820 valeur de 64. 815 00:35:13,820 --> 00:35:18,480 >> Maintenant que, en soi, sorte de parle rien à la notation n, l' 816 00:35:18,480 --> 00:35:20,700 Big O, l'oméga que nous avons parlé. 817 00:35:20,700 --> 00:35:24,890 Mais il s'avère que 64 est en effet 16, la taille de l'entrée, 818 00:35:24,890 --> 00:35:27,110 Connectez-base 2 de 16. 819 00:35:27,110 --> 00:35:30,200 Et si c'est un peu familier, juste repense, et il reviendra 820 00:35:30,200 --> 00:35:30,700 vous finalement. 821 00:35:30,700 --> 00:35:33,775 Si c'est la base log 2, c'est comme 2 élevé à la quelle vous donne 16? 822 00:35:33,775 --> 00:35:36,380 Oh, c'est 4, il ya 16 fois 4. 823 00:35:36,380 --> 00:35:39,380 >> Et encore, ce n'est pas un gros problème si cette est une sorte de vague souvenir maintenant. 824 00:35:39,380 --> 00:35:43,720 Mais pour l'instant, prendre sur la foi que 16 log 16 est 64. 825 00:35:43,720 --> 00:35:46,590 Et en effet, avec cette simple bon sens vérifier, nous avons confirmé - 826 00:35:46,590 --> 00:35:48,250 mais pas prouvé formellement - 827 00:35:48,250 --> 00:35:52,800 que le temps d'exécution de fusion genre est en effet n log n. 828 00:35:52,800 --> 00:35:53,790 >> Donc pas mal. 829 00:35:53,790 --> 00:35:57,260 C'est certainement mieux que l' algorithmes que nous avons vu jusqu'à présent, et 830 00:35:57,260 --> 00:36:00,710 c'est parce que nous avons misé, un, une technique appelée récursivité. 831 00:36:00,710 --> 00:36:03,880 Mais le plus intéressant que cela, qui notion de division et de conquête. 832 00:36:03,880 --> 00:36:07,460 Encore une fois, véritablement semaine 0 trucs qui même maintenant est récurrent dans un 833 00:36:07,460 --> 00:36:08,740 plus de manière convaincante. 834 00:36:08,740 --> 00:36:11,750 >> Maintenant, un peu d'exercice amusant, si vous avez jamais fait cela - et vous avez probablement 835 00:36:11,750 --> 00:36:14,660 n'aurait pas, parce que sorte de la normale les gens ne pensent pas à cela. 836 00:36:14,660 --> 00:36:20,650 Mais si je vais à google.com et si Je veux apprendre quelque chose sur 837 00:36:20,650 --> 00:36:22,356 récursivité, Entrée. 838 00:36:22,356 --> 00:36:25,106 839 00:36:25,106 --> 00:36:29,058 >> [Rires] 840 00:36:29,058 --> 00:36:32,030 [Plus de rires] 841 00:36:32,030 --> 00:36:33,385 DAVID MALAN: mauvaise blague propager lentement. 842 00:36:33,385 --> 00:36:34,450 [Rires] 843 00:36:34,450 --> 00:36:36,970 DAVID MALAN: Juste au cas où, il est là. 844 00:36:36,970 --> 00:36:38,710 Je n'ai pas l'épelle mal, et il ya la plaisanterie. 845 00:36:38,710 --> 00:36:40,810 Très bien. 846 00:36:40,810 --> 00:36:42,950 Expliquer aux gens à côté de vous si il n'a pas assez cliqué tout de suite. 847 00:36:42,950 --> 00:36:47,650 Mais récursivité, plus généralement, se réfère le procédé d'une fonction d'appel 848 00:36:47,650 --> 00:36:51,430 lui-même ou, plus généralement, la division d'un problème en quelque chose qui peut être 849 00:36:51,430 --> 00:36:56,220 résolus au coup par coup en résolvant identique problèmes de représentation. 850 00:36:56,220 --> 00:36:58,400 >> Changer les vitesses du bien, permettez- pour un instant. 851 00:36:58,400 --> 00:37:00,840 Nous aimons mettre fin à certains rebondissements, Commençons donc à mettre 852 00:37:00,840 --> 00:37:05,870 l'étape, pendant quelques minutes, sur une idée très simple - 853 00:37:05,870 --> 00:37:07,620 que d'échanger deux éléments, non? 854 00:37:07,620 --> 00:37:10,040 Tous ces algorithmes que nous avons été parler des deux dernières 855 00:37:10,040 --> 00:37:12,420 conférences impliquent une certaine sorte de permutation. 856 00:37:12,420 --> 00:37:14,630 Aujourd'hui, il a été visualisée en obtenant d'eux lever de leurs chaises et 857 00:37:14,630 --> 00:37:18,570 se promener, mais dans le code, nous n'aurions il suffit de prendre un élément d'un tableau 858 00:37:18,570 --> 00:37:20,370 et plop dans un autre. 859 00:37:20,370 --> 00:37:21,880 >> Alors, comment allons-nous faire cela? 860 00:37:21,880 --> 00:37:24,850 Eh bien, permettez-moi d'aller de l'avant et à écrire un programme rapide ici. 861 00:37:24,850 --> 00:37:31,600 Je vais aller de l'avant et faire ce que ce qui suit. 862 00:37:31,600 --> 00:37:33,910 Appelons cela - 863 00:37:33,910 --> 00:37:38,070 Que voulons-nous pour appeler celui-ci? 864 00:37:38,070 --> 00:37:38,650 >> En fait, non. 865 00:37:38,650 --> 00:37:39,420 Permettez-moi de revenir en arrière. 866 00:37:39,420 --> 00:37:41,220 Je ne veux pas faire ça encore cliffhanger. 867 00:37:41,220 --> 00:37:42,270 Il va gâcher le plaisir. 868 00:37:42,270 --> 00:37:43,600 Faisons-le à la place. 869 00:37:43,600 --> 00:37:47,430 >> Supposons que je veux écrire un peu programme et qui englobe maintenant cette 870 00:37:47,430 --> 00:37:48,700 idée de la récursivité. 871 00:37:48,700 --> 00:37:50,370 J'ai en quelque sorte devancé de moi là-bas. 872 00:37:50,370 --> 00:37:51,420 Je vais faire ce qui suit. 873 00:37:51,420 --> 00:38:00,220 >> Tout d'abord, un rapide incluent la norme io.h, ainsi qu'un comprennent des cs50.h. 874 00:38:00,220 --> 00:38:03,200 Et puis je vais aller de l'avant et déclarer void main int 875 00:38:03,200 --> 00:38:04,360 de la manière habituelle. 876 00:38:04,360 --> 00:38:07,920 J'ai réalisé que je l'ai mal nommé le fichier, de sorte Permettez-moi d'ajouter une extension c. ici, donc 877 00:38:07,920 --> 00:38:09,510 que nous pouvons compiler correctement. 878 00:38:09,510 --> 00:38:10,970 Commencez cette fonction. 879 00:38:10,970 --> 00:38:13,290 >> Et la fonction que je veux écrire, tout à fait simplement, est celui qui demande le 880 00:38:13,290 --> 00:38:16,210 utilisateur pour un certain nombre, puis ajoute tous les nombres compris entre cette 881 00:38:16,210 --> 00:38:19,920 nombre et, disons, 0. 882 00:38:19,920 --> 00:38:22,510 Alors d'abord je vais aller de l'avant et déclarer int n. 883 00:38:22,510 --> 00:38:24,760 Puis-je copier un code qui nous avons utilisé pendant un certain temps. 884 00:38:24,760 --> 00:38:26,660 Alors que quelque chose est vrai. 885 00:38:26,660 --> 00:38:28,000 Je reviendrai dans un instant. 886 00:38:28,000 --> 00:38:29,010 >> Ce que je veux faire? 887 00:38:29,010 --> 00:38:33,460 Je veux dire printf positif entier s'il vous plaît. 888 00:38:33,460 --> 00:38:36,130 Et puis je vais dire n obtient obtenir int. 889 00:38:36,130 --> 00:38:38,800 Encore une fois, un peu de code passe-partout que nous avons utilisé auparavant. 890 00:38:38,800 --> 00:38:40,810 Et je vais le faire tandis que n est inférieur à 1. 891 00:38:40,810 --> 00:38:44,120 Donc, cela fera en sorte que l'utilisateur me donne un entier positif. 892 00:38:44,120 --> 00:38:45,490 >> Et maintenant, je vais faire ce qui suit. 893 00:38:45,490 --> 00:38:51,020 Je tiens à ajouter tous les numéros et entre 1 et n, ou 0 et n, 894 00:38:51,020 --> 00:38:52,570 équivalente, pour obtenir la somme totale. 895 00:38:52,570 --> 00:38:55,100 Ainsi, le grand symbole sigma que vous vous en souvenez. 896 00:38:55,100 --> 00:38:59,050 Donc, je vais le faire en première convocation une fonction appelée sigma, 897 00:38:59,050 --> 00:39:06,030 passer en n, et puis je vais printf dire, la réponse est là. 898 00:39:06,030 --> 00:39:08,180 >> Donc en bref, je reçois et Int de l'utilisateur. 899 00:39:08,180 --> 00:39:09,280 Je m'assure que c'est positif. 900 00:39:09,280 --> 00:39:12,700 Je déclare une variable appelée réponse type int et boutique en elle le retour 901 00:39:12,700 --> 00:39:15,610 valeur de sigma, en passant dans le n en entrée. 902 00:39:15,610 --> 00:39:17,060 Et puis je imprimer cette réponse. 903 00:39:17,060 --> 00:39:19,550 >> Malheureusement, même si sigma sonne comme quelque chose qui pourrait être en 904 00:39:19,550 --> 00:39:24,040 le fichier math.h, sa déclaration, c'est vraiment pas. 905 00:39:24,040 --> 00:39:24,690 Donc, c'est OK. 906 00:39:24,690 --> 00:39:26,170 Je peux mettre en place moi-même. 907 00:39:26,170 --> 00:39:29,160 Je vais mettre en place une fonction appelée sigma, et ça va prendre un 908 00:39:29,160 --> 00:39:29,900 paramètre - 909 00:39:29,900 --> 00:39:32,100 Appelons cela m, juste donc c'est différent. 910 00:39:32,100 --> 00:39:35,910 Et puis ici, je vais vous dire, De plus, si m est inférieur à 1 - ce qui est un 911 00:39:35,910 --> 00:39:38,180 programme très inintéressant. 912 00:39:38,180 --> 00:39:41,700 Donc, je vais aller de l'avant et retourner immédiatement 0. 913 00:39:41,700 --> 00:39:45,920 Il n'a tout simplement pas de sens d'additionner tous les nombres compris entre 1 et m si m 914 00:39:45,920 --> 00:39:48,470 est lui-même égal à 0 ou négative. 915 00:39:48,470 --> 00:39:50,900 >> Et puis je vais aller de l'avant et le faire très itérative. 916 00:39:50,900 --> 00:39:53,090 Je vais faire ce genre de vieille école, et je vais aller de l'avant 917 00:39:53,090 --> 00:39:57,150 et dire que je vais déclarer une somme égale à 0. 918 00:39:57,150 --> 00:39:59,630 Alors je vais devoir une boucle de int - 919 00:39:59,630 --> 00:40:02,820 et laissez-moi faire pour qu'il corresponde à notre Code de la distribution, de sorte que vous avez une copie 920 00:40:02,820 --> 00:40:07,500 à la maison. int i obtient 1 sur un maximum de i est inférieur ou égal à m. 921 00:40:07,500 --> 00:40:09,430 i plus plus. 922 00:40:09,430 --> 00:40:11,430 Et puis à l'intérieur de cette boucle for - 923 00:40:11,430 --> 00:40:12,440 nous y sommes presque - 924 00:40:12,440 --> 00:40:15,810 somme se montant plus 1. 925 00:40:15,810 --> 00:40:17,670 Et puis je vais retourner la somme. 926 00:40:17,670 --> 00:40:19,420 >> J'ai donc fait ce rapidement, tout à fait vrai. 927 00:40:19,420 --> 00:40:22,775 Mais encore une fois, la fonction principale est assez simple, basé sur le code que nous avons 928 00:40:22,775 --> 00:40:23,190 écrit jusqu'à présent. 929 00:40:23,190 --> 00:40:25,610 Utilise la double boucle pour obtenir un positif Int de l'utilisateur. 930 00:40:25,610 --> 00:40:29,870 Je puis passer cette int à une nouvelle fonction appelé sigma, l'appelant, encore une fois, n. 931 00:40:29,870 --> 00:40:33,100 Et je stocke la valeur de retour, la réponse à partir de la boîte noire actuellement 932 00:40:33,100 --> 00:40:35,460 connue sous le nom sigma, en une variable appelée réponse. 933 00:40:35,460 --> 00:40:36,580 Puis je l'imprime. 934 00:40:36,580 --> 00:40:39,090 >> Si maintenant nous continuons l'histoire, comment est-sigma mise en œuvre? 935 00:40:39,090 --> 00:40:40,840 Je propose de mettre en œuvre comme suit. 936 00:40:40,840 --> 00:40:43,560 Tout d'abord, un peu de vérification des erreurs pour s'assurer que l'utilisateur n'est pas 937 00:40:43,560 --> 00:40:46,480 déconner avec moi et en passant une valeur négative ou 0. 938 00:40:46,480 --> 00:40:49,710 Ensuite, je déclare une variable appelée résumer et mettre à 0. 939 00:40:49,710 --> 00:40:55,910 >> Et maintenant, je commence à passer de i égale 1 tout le chemin jusqu'à et y compris m, 940 00:40:55,910 --> 00:41:00,130 parce que je veux inclure tout le nombres de un à m, inclusivement. 941 00:41:00,130 --> 00:41:04,350 Et à l'intérieur de cette boucle for, je fais juste somme obtient ce qu'il est maintenant, plus l' 942 00:41:04,350 --> 00:41:08,900 valeur de i. 943 00:41:08,900 --> 00:41:10,370 Plus la valeur de i. 944 00:41:10,370 --> 00:41:14,090 >> En passant, si vous n'avez pas vu ce avant, il ya un peu de sucre syntaxique 945 00:41:14,090 --> 00:41:14,870 pour cette ligne. 946 00:41:14,870 --> 00:41:21,120 Je peux réécrire ce que, plus égal à i, juste pour me sauver quelques frappes 947 00:41:21,120 --> 00:41:22,570 et de regarder un peu plus frais. 948 00:41:22,570 --> 00:41:23,140 Mais c'est tout. 949 00:41:23,140 --> 00:41:24,660 C'est fonctionnellement la même chose. 950 00:41:24,660 --> 00:41:26,710 >> Malheureusement, ce code de ne va pas compiler encore. 951 00:41:26,710 --> 00:41:31,600 Si je cours faire sigma 0, comment vais- Je vais faire engueuler? 952 00:41:31,600 --> 00:41:33,473 Qu'est-ce que ça va pas aimer? 953 00:41:33,473 --> 00:41:35,740 >> AUDIENCE: [inaudible]. 954 00:41:35,740 --> 00:41:37,800 >> DAVID MALAN: Oui, je n'ai pas déclaré la fonction en haut, à droite? 955 00:41:37,800 --> 00:41:40,590 C est un peu stupide, en ce qu'elle ne Est-ce que vous lui demandez de faire, et vous 956 00:41:40,590 --> 00:41:41,880 avoir à le faire dans cet ordre. 957 00:41:41,880 --> 00:41:45,910 Et donc, si je frappe Entrez ici, je vais obtenir un avertissement sur sigma implicite 958 00:41:45,910 --> 00:41:46,860 déclaration. 959 00:41:46,860 --> 00:41:48,120 >> Oh, pas un problème. 960 00:41:48,120 --> 00:41:50,370 Je peux aller jusqu'au sommet, et je peux dire, d'accord, attendez une minute. 961 00:41:50,370 --> 00:41:54,240 Sigma est une fonction qui renvoie un int et il s'attend à une 962 00:41:54,240 --> 00:41:56,620 int en entrée, point-virgule. 963 00:41:56,620 --> 00:41:59,550 Ou je pourrais mettre toute la fonction dessus principal, mais en général, je serais 964 00:41:59,550 --> 00:42:02,260 recommander contre cela, parce que c'est agréable d'avoir toujours principal en haut de sorte 965 00:42:02,260 --> 00:42:06,310 vous pouvez plonger à droite et savoir ce qu'est un programme est de faire en lisant principal en premier. 966 00:42:06,310 --> 00:42:07,930 >> Alors maintenant, laissez-moi éclaircir l'écran. 967 00:42:07,930 --> 00:42:09,330 Remake sigma 0. 968 00:42:09,330 --> 00:42:10,340 Tout semble à vérifier. 969 00:42:10,340 --> 00:42:11,970 Permettez-moi de courir sigma 0. 970 00:42:11,970 --> 00:42:12,770 Inter positive. 971 00:42:12,770 --> 00:42:15,580 Je vais lui donner le nombre 3 Pour faire simple. 972 00:42:15,580 --> 00:42:18,710 Alors qu'il devrait me donner 3 plus 2 plus 1, donc 6. 973 00:42:18,710 --> 00:42:20,750 Entrer, et en effet je reçois 6. 974 00:42:20,750 --> 00:42:21,820 >> Je peux faire quelque chose de grand - 975 00:42:21,820 --> 00:42:24,080 50, 12, 75. 976 00:42:24,080 --> 00:42:27,690 Tout comme une tangente, je vais faire quelque chose de ridicule comme un très gros 977 00:42:27,690 --> 00:42:30,375 nombre, Oh, qui a effectivement travaillé sur - 978 00:42:30,375 --> 00:42:31,600 hein, je ne pense pas que ce soit juste. 979 00:42:31,600 --> 00:42:32,810 Voyons voir. 980 00:42:32,810 --> 00:42:34,060 Disons vraiment plaisante pas avec elle. 981 00:42:34,060 --> 00:42:37,150 982 00:42:37,150 --> 00:42:38,400 >> C'est un problème. 983 00:42:38,400 --> 00:42:43,180 984 00:42:43,180 --> 00:42:44,970 Que se passe-t-il? 985 00:42:44,970 --> 00:42:46,050 Le code n'est pas si mal. 986 00:42:46,050 --> 00:42:48,470 C'est toujours linéaire. 987 00:42:48,470 --> 00:42:50,810 Sifflement est un bon effet, si. 988 00:42:50,810 --> 00:42:52,060 Que se passe-t-il? 989 00:42:52,060 --> 00:42:54,700 990 00:42:54,700 --> 00:42:55,620 >> Ne sais pas si je l'ai entendu. 991 00:42:55,620 --> 00:42:57,620 Ainsi, il s'avère - et c'est une parenthèse. 992 00:42:57,620 --> 00:42:59,400 Ce n'est pas au coeur de l' idée de la récursivité. 993 00:42:59,400 --> 00:43:02,480 Il s'avère, parce que je suis en train de représenter un tel grand nombre, la plupart 994 00:43:02,480 --> 00:43:06,980 Elle est certainement une mauvaise interprétation C en tant que numéro de pas positif, 995 00:43:06,980 --> 00:43:09,980 mais nombre négatif. 996 00:43:09,980 --> 00:43:12,690 >> Nous n'avons pas parlé de cela, mais il s'avère qu'il ya des nombres négatifs 997 00:43:12,690 --> 00:43:14,210 dans le monde en plus de nombres positifs. 998 00:43:14,210 --> 00:43:16,290 Et les moyens par lesquels vous pouvez représenter un nombre négatif 999 00:43:16,290 --> 00:43:19,530 essentiellement, c'est, vous utilisez une peu spécial pour indiquer 1000 00:43:19,530 --> 00:43:20,400 positif et négatives. 1001 00:43:20,400 --> 00:43:22,950 C'est un peu plus complexe que cela, mais c'est l'idée de base. 1002 00:43:22,950 --> 00:43:26,740 >> Donc, malheureusement, si C est une source de confusion de ces bits comme réellement un sens, 1003 00:43:26,740 --> 00:43:30,790 oh, c'est un nombre négatif, ma boucle ici, par exemple, est en réalité jamais 1004 00:43:30,790 --> 00:43:31,740 va se terminer. 1005 00:43:31,740 --> 00:43:33,850 Donc, si je devais imprimer réellement quelque chose encore et encore, nous aurions 1006 00:43:33,850 --> 00:43:34,650 voir grand-chose. 1007 00:43:34,650 --> 00:43:36,220 Mais encore une fois, ce n'est pas la question. 1008 00:43:36,220 --> 00:43:38,590 C'est vraiment juste une sorte de curiosité intellectuelle que nous viendrons 1009 00:43:38,590 --> 00:43:39,550 sauvegarder à terme. 1010 00:43:39,550 --> 00:43:43,400 Mais pour l'instant, c'est un bon mise en œuvre si nous supposons que l' 1011 00:43:43,400 --> 00:43:45,970 utilisateur fournira ints , qui entrent dans ints. 1012 00:43:45,970 --> 00:43:49,370 >> Mais je prétends que ce code, franchement, on pourrait faire tellement plus simple. 1013 00:43:49,370 --> 00:43:54,060 Si l'objectif à portée de main est de prendre un certain nombre comme m et additionnez tous les 1014 00:43:54,060 --> 00:43:59,510 nombres compris entre 1 et, ou, inversement, entre 1 et, je prétends 1015 00:43:59,510 --> 00:44:03,380 que je peux emprunter cette idée que fusionner Trier avait, qui prenait un problème 1016 00:44:03,380 --> 00:44:05,660 de cette taille et en le divisant en quelque chose de plus petit. 1017 00:44:05,660 --> 00:44:09,875 Peut-être pas la moitié, mais plus petit, mais de la même manière représentative. 1018 00:44:09,875 --> 00:44:12,130 Même idée, mais un petit problème. 1019 00:44:12,130 --> 00:44:15,470 >> Donc, je suis en fait - permettez-moi de sauvegarder ce fichier avec un numéro de version différent. 1020 00:44:15,470 --> 00:44:17,670 Nous appelons cette version 1 au lieu de 0. 1021 00:44:17,670 --> 00:44:20,790 Et je prétends que je peux réellement réimplémenter ce dans ce genre de 1022 00:44:20,790 --> 00:44:22,160 hallucinante façon. 1023 00:44:22,160 --> 00:44:23,710 >> Je vais laisser une partie de lui seul. 1024 00:44:23,710 --> 00:44:27,710 Je vais dire si m est inférieur supérieure ou même égale à 0 - 1025 00:44:27,710 --> 00:44:29,280 Je vais juste être un peu plus anal cette fois 1026 00:44:29,280 --> 00:44:30,520 avec ma vérification des erreurs - 1027 00:44:30,520 --> 00:44:33,190 Je vais aller de l'avant et retourner 0. 1028 00:44:33,190 --> 00:44:34,490 C'est arbitraire. 1029 00:44:34,490 --> 00:44:37,500 Je suis tout simplement de décider si l'utilisateur me donne un nombre négatif, je suis 1030 00:44:37,500 --> 00:44:41,490 retour 0, et qu'ils auraient dû lire la documentation de plus près. 1031 00:44:41,490 --> 00:44:42,170 >> Autres - 1032 00:44:42,170 --> 00:44:44,070 Remarquez ce que je vais faire. 1033 00:44:44,070 --> 00:44:49,260 Sinon, je vais retourner m plus - 1034 00:44:49,260 --> 00:44:51,010 ce qui est sigma de m? 1035 00:44:51,010 --> 00:44:56,710 Eh bien, sigma de m plus m moins 1, plus m moins 2 m + moins 3. 1036 00:44:56,710 --> 00:44:58,030 Je ne veux pas écrire tout cela. 1037 00:44:58,030 --> 00:44:59,120 Pourquoi ne pas simplement botté de dégagement? 1038 00:44:59,120 --> 00:45:05,080 Moi-même de manière récursive avec un peu petit problème, point-virgule, 1039 00:45:05,080 --> 00:45:06,840 et appeler cela un jour? 1040 00:45:06,840 --> 00:45:07,040 >> Droite? 1041 00:45:07,040 --> 00:45:10,980 Maintenant, ici aussi, vous pourriez vous sentir ou de s'inquiéter qu'il s'agit d'une boucle infinie que je suis 1042 00:45:10,980 --> 00:45:15,450 induisant, par lequel je suis la mise en œuvre sigma en appelant sigma. 1043 00:45:15,450 --> 00:45:20,342 Mais c'est tout à fait correct, parce que je pensé avant une ajouté, dont les lignes? 1044 00:45:20,342 --> 00:45:22,600 >> AUDIENCE: [inaudible]. 1045 00:45:22,600 --> 00:45:25,430 >> DAVID MALAN: 23 à 26, qui c'est mon cas condition. 1046 00:45:25,430 --> 00:45:28,390 Parce que ce qui est bien sur l' soustraction ici, parce que je continue 1047 00:45:28,390 --> 00:45:31,180 distribuant les petits problèmes sigma, plus petit problèmes, plus petit - ce n'est pas 1048 00:45:31,180 --> 00:45:31,870 la moitié de la taille. 1049 00:45:31,870 --> 00:45:34,380 Ce n'est qu'une étape de plus petit bébé, mais c'est OK. 1050 00:45:34,380 --> 00:45:38,050 Parce que finalement, nous travaillerons notre chemin vers le bas à 1 ou 0. 1051 00:45:38,050 --> 00:45:41,630 Et une fois que nous avons atteint 0, sigma n'est pas va s'appeler plus. 1052 00:45:41,630 --> 00:45:43,590 Il va retourner immédiatement 0. 1053 00:45:43,590 --> 00:45:47,960 >> Ainsi, l'effet, si vous sorte de vent cette dans votre esprit, est d'ajouter m plus 1054 00:45:47,960 --> 00:45:52,740 m moins 1 m + moins 2 m + moins 3, plus point, point, point, m moins 1055 00:45:52,740 --> 00:45:57,820 m, éventuellement en vous donnant 0, et le effet est finalement d'ajouter tous 1056 00:45:57,820 --> 00:45:59,070 ces choses ensemble. 1057 00:45:59,070 --> 00:46:02,380 Donc, nous n'avons pas, avec la récursivité, résolu le problème que nous 1058 00:46:02,380 --> 00:46:03,470 ne pouvait pas résoudre avant. 1059 00:46:03,470 --> 00:46:06,840 En effet, la version 0 de cela, et chaque problème à ce jour, a été solvable 1060 00:46:06,840 --> 00:46:09,980 avec juste l'aide de boucles ou de tout des boucles ou des constructions similaires. 1061 00:46:09,980 --> 00:46:13,150 >> Mais la récursivité, si j'ose dire, nous donne une autre façon de penser 1062 00:46:13,150 --> 00:46:17,010 problèmes, de sorte que si l'on peut prendre un problème, divisez-le à partir de quelque chose 1063 00:46:17,010 --> 00:46:22,340 un peu large dans quelque chose un peu petit, je prétends que nous pouvons le résoudre 1064 00:46:22,340 --> 00:46:26,040 peut-être un peu plus élégamment en termes de la conception, avec moins de code, 1065 00:46:26,040 --> 00:46:30,980 et peut-être même résoudre des problèmes qui pourraient être plus difficile, comme nous allons finalement 1066 00:46:30,980 --> 00:46:33,280 voir, la résolution purement itérative. 1067 00:46:33,280 --> 00:46:35,980 >> Mais le cliffhanger que j'ai fait vouloir nous quitter sur ce n'était. 1068 00:46:35,980 --> 00:46:40,720 Permettez-moi d'aller de l'avant et ouvrir un fichier à partir de - 1069 00:46:40,720 --> 00:46:44,300 en fait, permettez-moi d'aller d' faire très vite. 1070 00:46:44,300 --> 00:46:46,875 Permettez-moi d'aller de l'avant et propose ce qui suit. 1071 00:46:46,875 --> 00:46:51,160 1072 00:46:51,160 --> 00:46:54,785 Parmi le code d'aujourd'hui est ce fichier ici. 1073 00:46:54,785 --> 00:47:01,090 1074 00:47:01,090 --> 00:47:03,050 Celui-là, NOSWAP. 1075 00:47:03,050 --> 00:47:06,260 >> Donc, c'est un peu stupide programme qui J'ai fouetté jusqu'à ce que prétend faire 1076 00:47:06,260 --> 00:47:06,940 ce qui suit. 1077 00:47:06,940 --> 00:47:10,140 En principal, il déclare d'abord une int appelé X et lui attribue 1078 00:47:10,140 --> 00:47:11,100 la valeur de 1. 1079 00:47:11,100 --> 00:47:13,520 Puis il déclare un int y et assigne la valeur 2. 1080 00:47:13,520 --> 00:47:15,310 Puis il affiche ce x et y est. 1081 00:47:15,310 --> 00:47:17,781 Puis il dit, en échangeant, dot dot dot. 1082 00:47:17,781 --> 00:47:21,670 >> Ensuite, il prétend être l'appel d'une fonction appelé swap, passant en x et 1083 00:47:21,670 --> 00:47:24,290 y, dont l'idée est que nous espérons x et y reviendront 1084 00:47:24,290 --> 00:47:25,620 différent, c'est le contraire. 1085 00:47:25,620 --> 00:47:27,110 Il prétendre ensuite échangé! 1086 00:47:27,110 --> 00:47:28,420 avec un point d'exclamation. 1087 00:47:28,420 --> 00:47:30,190 Puis il affiche x et y. 1088 00:47:30,190 --> 00:47:33,480 >> Mais il s'avère que cette très démonstration simple vers le bas 1089 00:47:33,480 --> 00:47:35,570 ici est en fait buggy. 1090 00:47:35,570 --> 00:47:38,870 Même si je suis déclarant temporaire variable et mettre temporairement dans un 1091 00:47:38,870 --> 00:47:42,010 , alors je suis réaffectation un la valeur de b - 1092 00:47:42,010 --> 00:47:45,080 qui se sent raisonnable, parce que j'ai enregistré une copie d'un en température. 1093 00:47:45,080 --> 00:47:48,410 Puis-je modifier b à l'égalité tout ce qui était en température. 1094 00:47:48,410 --> 00:47:51,610 Cette sorte de jeu de coquille de déplacer une en b et b en en utilisant cette 1095 00:47:51,610 --> 00:47:54,360 Moyen-homme appelé température se sent parfaitement raisonnable. 1096 00:47:54,360 --> 00:47:57,270 >> Mais je prétends que quand je lance cette code, comme je le fais maintenant - 1097 00:47:57,270 --> 00:47:59,490 laissez-moi aller de l'avant et le coller dans ici. 1098 00:47:59,490 --> 00:48:01,995 Je vais appeler cette noswap.c. 1099 00:48:01,995 --> 00:48:05,630 Et comme son nom l'indique, ce n'est pas va être un bon programme. 1100 00:48:05,630 --> 00:48:09,460 Faire NOSWAP. / Non échangeable. 1101 00:48:09,460 --> 00:48:12,110 x est 1, y est égal à 2, permutation, permuter. 1102 00:48:12,110 --> 00:48:14,220 x est 1, y est égal à 2. 1103 00:48:14,220 --> 00:48:16,920 Ceci est fondamentalement mauvais, même si cela semble parfaitement 1104 00:48:16,920 --> 00:48:17,730 raisonnable pour moi. 1105 00:48:17,730 --> 00:48:21,330 Et il ya une raison, mais nous ne sommes pas vais vous révéler la raison pour l'instant. 1106 00:48:21,330 --> 00:48:24,610 >> Pour l'instant le deuxième cliffhanger je voulais vous laisser avec cette, une 1107 00:48:24,610 --> 00:48:27,120 annonce de toutes sortes sur les codes promos. 1108 00:48:27,120 --> 00:48:31,590 Notre innovation avec jours de retard cette année a provoqué un nombre non négligeable 1109 00:48:31,590 --> 00:48:33,830 de questions, ce qui était pas notre intention. 1110 00:48:33,830 --> 00:48:36,590 L'intention de ces codes promo, où si vous faites partie du problème 1111 00:48:36,590 --> 00:48:39,850 mettre au début, obtenant ainsi une journée supplémentaire, C'était vraiment pour vous aider les gars aide 1112 00:48:39,850 --> 00:48:42,420 vous commencez tôt, en quelque sorte par vous incentivizing. 1113 00:48:42,420 --> 00:48:44,880 Nous permet de répartir la charge sur les heures de bureau mieux afin que 1114 00:48:44,880 --> 00:48:45,740 c'est une sorte de gagnant-gagnant. 1115 00:48:45,740 --> 00:48:48,860 >> Malheureusement, je pense que mes instructions n'ont pas été, à ce jour, très claire, de sorte 1116 00:48:48,860 --> 00:48:52,230 Je suis retourné ce week-end et mis à jour le spec en plus, le texte audacieux de 1117 00:48:52,230 --> 00:48:53,600 expliquer balles comme celles-ci. 1118 00:48:53,600 --> 00:48:56,900 Et juste pour le dire plus publiquement, par par défaut, les ensembles de problèmes sont dus jeudi 1119 00:48:56,900 --> 00:48:58,400 à midi, par le programme. 1120 00:48:58,400 --> 00:49:02,030 Si vous commencez tôt, finir une partie de le problème posé par les mercredi à 12h00 1121 00:49:02,030 --> 00:49:05,170 PM, la partie qui se rapporte à un coupon code, l'idée est que vous pouvez prolonger 1122 00:49:05,170 --> 00:49:07,710 votre date limite pour la P fixé jusqu'à vendredi. 1123 00:49:07,710 --> 00:49:10,890 C'est, peu hors une infime partie de la P définir par rapport à ce qui est généralement le 1124 00:49:10,890 --> 00:49:13,200 problème plus vaste, et que vous achetez vous un jour supplémentaire. 1125 00:49:13,200 --> 00:49:15,190 Encore une fois, il vous arrive de penser à l'ensemble des problèmes, vous reçoit 1126 00:49:15,190 --> 00:49:16,380 les heures de bureau plus tôt. 1127 00:49:16,380 --> 00:49:20,670 Mais le problème de code promo est encore tenus, même si vous ne les envoyez pas. 1128 00:49:20,670 --> 00:49:23,340 >> Mais il est plus convaincante cela. 1129 00:49:23,340 --> 00:49:26,520 (Aparté) Et ces gens de quitter début vas le regretter. 1130 00:49:26,520 --> 00:49:28,620 Comme le sont les gens sur le balcon. 1131 00:49:28,620 --> 00:49:32,510 Je m'excuse à l'avance pour les gens sur le balcon, pour des raisons qui seront 1132 00:49:32,510 --> 00:49:33,920 effacer en un instant. 1133 00:49:33,920 --> 00:49:37,050 >> Donc, nous avons la chance d'avoir l'un des Anciens boursiers de l'enseignement de la tête de CS50 à 1134 00:49:37,050 --> 00:49:39,302 une société appelée dropbox.com. 1135 00:49:39,302 --> 00:49:45,500 Ils ont très généreusement fait don d'un code promo ici pour cet espace, 1136 00:49:45,500 --> 00:49:48,180 qui est en place à partir de la habituelles 2 gigaoctets. 1137 00:49:48,180 --> 00:49:51,740 Donc ce que je pensais que nous allions faire sur cette la note finale est de faire un peu un cadeau, 1138 00:49:51,740 --> 00:49:55,380 lequel, dans un instant, nous allons révéler le gagnant et qui dispose d'un coupon 1139 00:49:55,380 --> 00:49:57,980 code que vous pouvez ensuite aller à leur site web, tapez-le, et voila, obtenir un 1140 00:49:57,980 --> 00:50:01,370 ensemble beaucoup plus d'espace pour votre Dropbox appareil et vos fichiers personnels. 1141 00:50:01,370 --> 00:50:05,690 >> Et d'abord, qui souhaiterait participer dans ce dessin? 1142 00:50:05,690 --> 00:50:09,630 OK, maintenant que rend encore plus amusant. 1143 00:50:09,630 --> 00:50:14,010 La personne qui reçoit ce 25 giga-octets code promo - ce qui est loin 1144 00:50:14,010 --> 00:50:16,150 plus convaincante que la fin jours maintenant, peut-être - 1145 00:50:16,150 --> 00:50:20,620 est celui qui est assis sur le dessus d'un Coussin de siège sous lequel il ya 1146 00:50:20,620 --> 00:50:21,620 que le code de coupon. 1147 00:50:21,620 --> 00:50:23,480 Vous pouvez maintenant regarder sous le coussin de siège. 1148 00:50:23,480 --> 00:50:28,710 1149 00:50:28,710 --> 00:50:29,680 >> [LECTURE VIDEO] 1150 00:50:29,680 --> 00:50:31,620 >> -Un, deux, trois. 1151 00:50:31,620 --> 00:50:35,015 >> [CRIE] 1152 00:50:35,015 --> 00:50:35,985 >> Vous obtenez une voiture! 1153 00:50:35,985 --> 00:50:36,670 Vous obtenez une voiture! 1154 00:50:36,670 --> 00:50:37,970 >> DAVID MALAN: Nous allons voir vous mercredi. 1155 00:50:37,970 --> 00:50:38,904 >> Vous obtenez une voiture! 1156 00:50:38,904 --> 00:50:39,371 Vous obtenez une voiture! 1157 00:50:39,371 --> 00:50:40,305 Vous obtenez une voiture! 1158 00:50:40,305 --> 00:50:41,706 Vous obtenez une voiture! 1159 00:50:41,706 --> 00:50:43,107 Vous obtenez une voiture! 1160 00:50:43,107 --> 00:50:45,530 >> DAVID MALAN: les gens avec balcon, venez ici-bas à l'avant, 1161 00:50:45,530 --> 00:50:46,866 où nous avons extras. 1162 00:50:46,866 --> 00:50:50,282 >> -Tout le monde a une voiture! 1163 00:50:50,282 --> 00:50:52,234 Tout le monde a une voiture! 1164 00:50:52,234 --> 00:50:52,722 >> [FIN LECTURE VIDÉO] 1165 00:50:52,722 --> 00:50:54,590 >> Narrateur: Lors de la prochaine CS50 - 1166 00:50:54,590 --> 00:51:00,374 >> ENCEINTE 5: Oh mon dieu mon dieu mon dieu mon dieu mon dieu mon dieu mon dieu mon dieu mon dieu mon dieu - 1167 00:51:00,374 --> 00:51:02,106 >> [JEUX] UKELELE