1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> ENCEINTE: Très bien, c'est CS50. 3 00:00:14,910 --> 00:00:19,020 C'est la fin de la troisième semaine, et si vous n'avez pas pris avantage déjà, 4 00:00:19,020 --> 00:00:21,790 savent qu'il y aura déjeuner ce vendredi comme d'habitude, où 5 00:00:21,790 --> 00:00:25,430 vous pouvez profiter de la bonne conversation et de la nourriture à feu et de glace 6 00:00:25,430 --> 00:00:27,980 avec une partie de sa CS50 le personnel et les camarades de classe. 7 00:00:27,980 --> 00:00:30,170 Rendez-vous à l'adresse ici. 8 00:00:30,170 --> 00:00:33,420 >> Maintenant vous pouvez rappeler, ou vous pourrait bientôt se familiariser avec, 9 00:00:33,420 --> 00:00:35,970 ces choses ici, qui sont donnés à la fin 10 00:00:35,970 --> 00:00:37,850 du semestre pour de nombreuses classes. 11 00:00:37,850 --> 00:00:40,870 Livres bleus soi-disant examen, dans lequel vous écrivez vos réponses aux examens. 12 00:00:40,870 --> 00:00:44,240 Maintenant, je dois ici 26 comme livres bleus, sur chacun d'entre eux 13 00:00:44,240 --> 00:00:47,580 est écrit un nom, de A à Z. Et en effet les noms sont aussi simple que cela, un 14 00:00:47,580 --> 00:00:50,490 à Z. Et l'un des les buts fixés aujourd'hui 15 00:00:50,490 --> 00:00:53,910 va être de continuer ce nous avons commencé le lundi, ce qui n'est pas 16 00:00:53,910 --> 00:00:57,830 tellement regardant le code, mais vraiment regardant idées et la résolution de problèmes. 17 00:00:57,830 --> 00:01:00,170 Un des buts et promesses de ce cours 18 00:01:00,170 --> 00:01:02,985 est de vous apprendre à penser plus attentivement, plus méthodique, 19 00:01:02,985 --> 00:01:05,400 et de résoudre les problèmes de manière plus efficace. 20 00:01:05,400 --> 00:01:09,526 Et en effet, nous pouvons le faire vraiment sans même toucher une ligne de code. 21 00:01:09,526 --> 00:01:12,150 Donc, j'ai un couple d'éléphants jusqu'à aujourd'hui, orange et bleu, 22 00:01:12,150 --> 00:01:15,780 si nous pouvions obtenir un bénévole, peut-être de plus loin que d'habitude. 23 00:01:15,780 --> 00:01:18,070 Que diriez-vous là, venez nous voir. 24 00:01:18,070 --> 00:01:24,180 Le but de ce qui va être à aider ainsi administrer cet examen ici. 25 00:01:24,180 --> 00:01:24,935 Quel est votre nom? 26 00:01:24,935 --> 00:01:25,768 >> PUBLIC: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 ENCEINTE: Mary Beth, venez sur place. 28 00:01:27,560 --> 00:01:29,560 Laissez-moi le micro là pour vous. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Ravi de vous rencontrer. 31 00:01:32,880 --> 00:01:34,005 >> PUBLIC: Ravi de vous rencontrer. 32 00:01:34,005 --> 00:01:36,790 ENCEINTE: Très bien, donc j'ai ici bleu livres de A à Z, 33 00:01:36,790 --> 00:01:41,680 et je vais faire semblant que J'ai l'un des étudiants, 34 00:01:41,680 --> 00:01:45,770 et ils viennent dans un peu au hasard à la fin d'un bloc d'examen de trois heures, 35 00:01:45,770 --> 00:01:49,400 donc ils se retrouvent dans une certaine ordre semi-aléatoire comme ça. 36 00:01:49,400 --> 00:01:54,510 Maintenant, votre travail dans un instant va à être-- c'est en fait la façon dont ils se 37 00:01:54,510 --> 00:01:56,820 tourné à la fin de la classe, le plus probable. 38 00:01:56,820 --> 00:02:01,120 Votre travail maintenant va être, tout à fait tout simplement, pour trier ces livres bleus pour nous 39 00:02:01,120 --> 00:02:05,220 de A à Z. 40 00:02:05,220 --> 00:02:08,400 >> PUBLIC: Oh, c'est va prendre une éternité. 41 00:02:08,400 --> 00:02:13,747 >> ENCEINTE: Et nous allons regarder comme vous le faites, pas de pression. 42 00:02:13,747 --> 00:02:15,330 PUBLIC: Non, pas de pression ou quoi que ce soit. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> ENCEINTE: Et pour le plaisir, Mettons en place une minuterie. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> PUBLIC: Tellement amusant, très amusant. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> Président: Je peux tenir le micro pour vous. 49 00:02:38,574 --> 00:02:40,240 Très bien, nous venons de doubler notre vitesse. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Alors en attendant, laissez-moi de poser ce qui est va être la question pour Mary Beth 52 00:02:49,060 --> 00:02:51,540 est ce qu'elle fait, comment est- elle va de résoudre cela? 53 00:02:51,540 --> 00:02:54,040 Et en fait, vous pourriez ne pas avoir jamais pensé à quelque chose 54 00:02:54,040 --> 00:02:57,440 aussi simple que lorsque vous décrochez jusqu'à 26 livres de ce genre, 55 00:02:57,440 --> 00:02:59,350 qui ne avoir un naturel leur ordonnant. 56 00:02:59,350 --> 00:03:01,335 Quel est le processus que vous utilisez réellement? 57 00:03:01,335 --> 00:03:03,770 Est-il assez aléatoire juste choisir le premier que vous voyez 58 00:03:03,770 --> 00:03:05,250 et de le mettre à sa place? 59 00:03:05,250 --> 00:03:09,680 Ne vous déplacez d'abord vos mains autour de Vous cherchez un alors à la recherche de B? 60 00:03:09,680 --> 00:03:11,722 Avez-vous jetez un oeil à un paire de côte à côte 61 00:03:11,722 --> 00:03:14,680 et dire simplement, attendez une minute, ce n'est pas droite, puis échanger l'ordre? 62 00:03:14,680 --> 00:03:16,960 Nous avons déjà vu le lundi qu'il ya un certain nombre de façons 63 00:03:16,960 --> 00:03:22,140 dans lequel nous pouvons le faire, et En effet, comme nous nous approchons de la fin ici, 64 00:03:22,140 --> 00:03:26,360 Je voudrais peut-être prendre note de ce que Mary Beth fait. 65 00:03:26,360 --> 00:03:30,040 Nous avons quelques pieux, il semble, une plus gros, trois petits. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> PUBLIC: Je leur ordonnant quand je trouve deux lettres 68 00:03:36,415 --> 00:03:39,540 que je connais sont ensemble dans une séquence, Je les ai mis ensemble pour que je ne fais pas 69 00:03:39,540 --> 00:03:42,915 avoir à vous soucier de garder piste de toute une rangée de livres. 70 00:03:42,915 --> 00:03:45,706 C'est juste, oh, A est le premier, J'ai cette pile ici. 71 00:03:45,706 --> 00:03:47,580 ENCEINTE: Alors, presque comme une pièces de puzzle qui 72 00:03:47,580 --> 00:03:49,860 avoir le droit de forme correspondre les uns aux autres. 73 00:03:49,860 --> 00:03:51,026 PUBLIC: Presque, oui. 74 00:03:51,026 --> 00:03:55,320 ENCEINTE: OK, excellent. 75 00:03:55,320 --> 00:03:59,850 Et maintenant, chacun de ces piles est probablement triés? 76 00:03:59,850 --> 00:04:00,990 >> PUBLIC: Ouais. 77 00:04:00,990 --> 00:04:09,900 >> ENCEINTE: Très bien, de A à Z. Tous droite, félicitations, vous l'avez fait. 78 00:04:09,900 --> 00:04:11,461 Vous avez le choix. 79 00:04:11,461 --> 00:04:11,960 Blue? 80 00:04:11,960 --> 00:04:13,530 Très bien, je vous remercie pour cela. 81 00:04:13,530 --> 00:04:16,679 Alors Mary Beth ne propose ce que son approche était, 82 00:04:16,679 --> 00:04:19,720 mais ce qui est une autre approche comment vous pourrait aller sur le tri de ces choses? 83 00:04:19,720 --> 00:04:21,130 Qu'auriez-vous fait? 84 00:04:21,130 --> 00:04:24,060 Le record à battre aurait été une minute et 50 secondes ou plus, 85 00:04:24,060 --> 00:04:26,039 ainsi que ceux que j'ai oublié de compter. 86 00:04:26,039 --> 00:04:27,080 Qu'auriez-vous fait? 87 00:04:27,080 --> 00:04:27,579 Ouais? 88 00:04:27,579 --> 00:04:28,735 PUBLIC: Prenez la pile. 89 00:04:28,735 --> 00:04:29,776 Commencer par le début. 90 00:04:29,776 --> 00:04:32,284 Vérifiez vos papiers. 91 00:04:32,284 --> 00:04:36,586 Et si le haut est plus élevé que, peut-être, ils sont, 92 00:04:36,586 --> 00:04:38,980 celui du bas est supérieur, puis les passer. 93 00:04:38,980 --> 00:04:41,300 >> ENCEINTE: OK, donc à partir en haut et en bas, 94 00:04:41,300 --> 00:04:43,716 et de travailler ensuite votre chemin intérieur comme ça, les échanger? 95 00:04:43,716 --> 00:04:46,580 OK, donc un peu similaire dans l'esprit de tri à bulles, 96 00:04:46,580 --> 00:04:49,160 mais en choisissant les extrêmes pas les paires adjacentes. 97 00:04:49,160 --> 00:04:52,080 Mais le court, c'est qu'il n'y a sûrement un tas de différentes façons 98 00:04:52,080 --> 00:04:54,210 nous pourrions le faire, et franchement, je pense que vous sorte de 99 00:04:54,210 --> 00:04:55,700 adopté quelques approches, non? 100 00:04:55,700 --> 00:05:00,567 Vous avez fait sorte de quatre piles triées, et alors effectivement les fusionnés. 101 00:05:00,567 --> 00:05:02,650 Et c'est, disons-le, un autre technique tout à fait. 102 00:05:02,650 --> 00:05:06,950 Vous n'avez pas le traiter comme un gros tas, vous avez divisé le problème en quatre quads, 103 00:05:06,950 --> 00:05:09,820 si vous voulez, et puis en quelque sorte les fusionner à la fin. 104 00:05:09,820 --> 00:05:13,410 >> Donc, nous allons examiner, en fin de compte, sinon comment nous pourrions le faire. 105 00:05:13,410 --> 00:05:15,860 Nous avons formalisé la notion de tri à bulles dernière fois, 106 00:05:15,860 --> 00:05:18,780 et tri à bulles rappel était une algorithme que nous avons visualisé 107 00:05:18,780 --> 00:05:22,640 avec huit de vos camarades de classe ici, apparemment triés au hasard au début. 108 00:05:22,640 --> 00:05:26,110 Et puis nous avons décidé par paires, si deux éléments sont hors d'usage, 109 00:05:26,110 --> 00:05:26,950 il suffit de les échanger. 110 00:05:26,950 --> 00:05:28,930 Donc, quatre et deux sont évidemment hors de commande, 111 00:05:28,930 --> 00:05:31,080 Donc, ces deux camarades de classe de changer de place. 112 00:05:31,080 --> 00:05:35,390 Et puis nous avons répété avec quatre et six, puis six et huit ans, à chaque itération, 113 00:05:35,390 --> 00:05:36,980 déplaçant vers la droite. 114 00:05:36,980 --> 00:05:42,590 >> Donc, étant donné huit personnes, combien de paires comparaisons que j'ai fait en marchant de 115 00:05:42,590 --> 00:05:45,220 de gauche à droite dans une telle itération? 116 00:05:45,220 --> 00:05:48,410 Combien de comparaisons? 117 00:05:48,410 --> 00:05:49,197 Sept, non? 118 00:05:49,197 --> 00:05:51,405 Parce que s'il ya huit personnes, mais vous avez la paire 119 00:05:51,405 --> 00:05:53,880 eux et vous garder en mouvement un bond vers la droite, 120 00:05:53,880 --> 00:05:56,060 vous n'allez pas avoir huit comparaisons parce que vous ne pouvez pas comparer 121 00:05:56,060 --> 00:05:59,226 un élément contre lui-même, ou il serait juste inutile, si vous avez sept. 122 00:05:59,226 --> 00:06:01,290 Ou, plus généralement, si nous avons n personnes, nous 123 00:06:01,290 --> 00:06:04,300 faire n moins 1 comparaisons avec tri à bulles. 124 00:06:04,300 --> 00:06:08,150 >> Donc, nous allons examiner maintenant comment bonne ou mauvais tri à bulles était réellement, et essayer 125 00:06:08,150 --> 00:06:13,570 de nous donner vocabulaire qui à des algorithmes de la critique de ce genre, 126 00:06:13,570 --> 00:06:14,430 et bientôt la nôtre. 127 00:06:14,430 --> 00:06:16,970 Ainsi, le premier passage à travers tri à bulles, la première fois 128 00:06:16,970 --> 00:06:20,909 Je suis de gauche à droite sur la stade, moi n moins 1 comparaisons pris. 129 00:06:20,909 --> 00:06:22,950 Et que ça va être mon unité de mesure, non? 130 00:06:22,950 --> 00:06:26,170 J'étais un peu parler et se promener, un peu rapide, un peu lent, 131 00:06:26,170 --> 00:06:29,300 donc compter mon nombre de secondes n'est pas particulièrement révélateur, 132 00:06:29,300 --> 00:06:32,260 mais le comptage du nombre de opérations que j'ai fait le lundi, 133 00:06:32,260 --> 00:06:35,900 comparaison de deux personnes, qui se sent comme une belle unité de mesure. 134 00:06:35,900 --> 00:06:40,980 >> Donc n moins 1 étapes de la première fois, mais alors qu'est-ce qui s'est passé après? 135 00:06:40,980 --> 00:06:46,610 Quelle est la seule tête d'un laissez-passer à travers une liste non triée autrement? 136 00:06:46,610 --> 00:06:49,840 Que pouvez-vous me dire à propos de l'élément qui était tout le chemin là-bas? 137 00:06:49,840 --> 00:06:51,300 Ouais? 138 00:06:51,300 --> 00:06:52,870 C'était le plus grand élément, non? 139 00:06:52,870 --> 00:06:55,710 Numéro huit, même si elle commencé ici, chaque fois que je 140 00:06:55,710 --> 00:06:57,860 son rapport contre un voisin, elle a gardé 141 00:06:57,860 --> 00:07:00,480 bouillonner vers la droite côté de la liste. 142 00:07:00,480 --> 00:07:02,710 Et en effet, c'est là que l'algorithme tire son nom. 143 00:07:02,710 --> 00:07:07,630 >> Maintenant, par cette logique, le nombre de comparaisons besoin que je fais sur le deuxième temps 144 00:07:07,630 --> 00:07:09,800 Je fais cette passe de gauche à droite? 145 00:07:09,800 --> 00:07:10,730 n moins 2, non? 146 00:07:10,730 --> 00:07:14,297 Il serait juste de perdre mon temps si je garder comparant huit contre quelqu'un 147 00:07:14,297 --> 00:07:16,630 d'autre parce que nous savons déjà elle était à la bonne place. 148 00:07:16,630 --> 00:07:19,760 Donc, c'est un peu d'une optimisation, de sorte que le passage suivant 149 00:07:19,760 --> 00:07:23,899 va être plus n moins deux étapes, où n est le nombre de personnes. 150 00:07:23,899 --> 00:07:26,940 Maintenant, vous pouvez sorte de extrapoler, même si vous n'êtes pas un informaticien, 151 00:07:26,940 --> 00:07:27,680 comment cela se termine. 152 00:07:27,680 --> 00:07:31,259 A l'issue de cet algorithme, probablement vous avez juste une comparaison gauche. 153 00:07:31,259 --> 00:07:33,800 Vous devez fixer le type de au début de la liste en cas de deux 154 00:07:33,800 --> 00:07:36,540 et un sont irrecevables et devrait être l'un et deux, 155 00:07:36,540 --> 00:07:40,330 si ce touche le fond à plus 1 comparaison finale. 156 00:07:40,330 --> 00:07:44,500 >> Maintenant, le point, point, point genre de vagues c'est mains de quelques-uns des plus juteux de détails, 157 00:07:44,500 --> 00:07:46,452 mais disons simplement aller de l'avant et de simplifier. 158 00:07:46,452 --> 00:07:48,660 Si vous vous souvenez de haute école, franchement, beaucoup d'entre vous 159 00:07:48,660 --> 00:07:50,340 eu livres de mathématiques qui ont un peu de feuille de triche 160 00:07:50,340 --> 00:07:52,550 sur le capot avant ou la couverture qui vous a montré 161 00:07:52,550 --> 00:07:56,400 sommations ce de la série comme ce finalement ajoutée jusqu'à. 162 00:07:56,400 --> 00:07:59,600 Dans le cas général, si vous avez un variables comme n, et en effet celui-ci, 163 00:07:59,600 --> 00:08:01,634 si vous regardé votre livre de mathématiques de la vieille école, 164 00:08:01,634 --> 00:08:04,050 vous verriez que ce fait ajoute à cette somme ici, 165 00:08:04,050 --> 00:08:07,970 n fois n moins 1 le tout divisé par 2. 166 00:08:07,970 --> 00:08:11,172 Donc pour l'instant je vais juste en définit cela est vrai, alors sur un acte de foi, 167 00:08:11,172 --> 00:08:12,880 c'est ce que cela résume jusqu'à, et nous avons pu 168 00:08:12,880 --> 00:08:14,341 prouver que, dans un cas plus général. 169 00:08:14,341 --> 00:08:15,590 Mais maintenant, nous allons étendre cela. 170 00:08:15,590 --> 00:08:19,920 Donc, nous allons multiplier ce, de sorte que c'est n carré, moins n, le tout divisé par 2. 171 00:08:19,920 --> 00:08:23,200 C'est vraiment n carré, divisé par 2, moins n plus de 2, 172 00:08:23,200 --> 00:08:25,010 de sorte que c'est tout beau et intéressant. 173 00:08:25,010 --> 00:08:27,060 Mais qu'advient-il si nous maintenant le plug-in d'une valeur? 174 00:08:27,060 --> 00:08:29,724 Supposons que je n'avais pas huit personnes, mais disent un million. 175 00:08:29,724 --> 00:08:31,890 Et un million seulement parce c'est un assez grand nombre, 176 00:08:31,890 --> 00:08:34,039 nous allons brancher que dans et voir ce qui se passe. 177 00:08:34,039 --> 00:08:39,039 Donc, si je branche un million dans cette formule Je vais me faire un million carré, 178 00:08:39,039 --> 00:08:42,868 divisée par deux, moins un millions d'euros, divisé par 2. 179 00:08:42,868 --> 00:08:44,159 Maintenant, qu'est-ce que cela va correspondre? 180 00:08:44,159 --> 00:08:47,354 Donc 500 milliards, moins de 500.000. 181 00:08:47,354 --> 00:08:49,270 Et si je fais effectivement que les mathématiques sur, que des moyens 182 00:08:49,270 --> 00:08:53,920 que le tri d'un million personnes atteintes de la sorte de bulle 183 00:08:53,920 --> 00:09:01,800 pourrait me prendre 499999500000 étapes ou des comparaisons à la fin, 184 00:09:01,800 --> 00:09:02,900 nous ne faisons que l'extrapolation. 185 00:09:02,900 --> 00:09:06,860 >> Cela se sent assez lent, mais franchement mesurer une entrée particulière 186 00:09:06,860 --> 00:09:09,160 comme ça, n'est pas du tout révélateur. 187 00:09:09,160 --> 00:09:14,050 Mais en effet, il ne suggère que n devient plus grand et plus large, cet algorithme 188 00:09:14,050 --> 00:09:16,280 sorte de se sent pire et pire, ou vous avez vraiment 189 00:09:16,280 --> 00:09:20,450 commencer à sentir la douleur de cette exponentiation, qui n carré, 190 00:09:20,450 --> 00:09:21,770 qui ajoute assez vite. 191 00:09:21,770 --> 00:09:25,340 Et ce détail n'est pas perdu sur les gens, en fait, 192 00:09:25,340 --> 00:09:29,640 Il ya quelques années, un certain sénateur qui était campagne, assis pour une entrevue 193 00:09:29,640 --> 00:09:32,180 avec Eric de Google Schmidt, PDG de l'époque, 194 00:09:32,180 --> 00:09:36,380 et a été contestée par une question un peu comme nous explorons aujourd'hui. 195 00:09:36,380 --> 00:09:38,468 Jetons un coup d'oeil. 196 00:09:38,468 --> 00:09:45,280 >> [VIDEO LECTURE] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Vous êtes ici à Google, et j'aime 198 00:09:48,560 --> 00:09:53,382 de penser à la présidence comme un entretien d'embauche. 199 00:09:53,382 --> 00:09:56,434 Maintenant, il est difficile d'obtenir un travail en tant que président, 200 00:09:56,434 --> 00:09:58,100 et vous allez à travers les rigueurs maintenant. 201 00:09:58,100 --> 00:10:01,860 Il est également difficile d'obtenir un emploi chez Google. 202 00:10:01,860 --> 00:10:05,490 Nous avons des questions, et nous demander à nos questions aux candidats, 203 00:10:05,490 --> 00:10:09,770 et celui-ci est de Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 What-- que vous en pensez, je suis blague, c'est ici. 205 00:10:14,760 --> 00:10:17,930 Quel est le moyen le plus efficace pour trier un million de nombres entiers de 32 bits? 206 00:10:17,930 --> 00:10:21,800 207 00:10:21,800 --> 00:10:24,350 >> -Well-- 208 00:10:24,350 --> 00:10:25,200 >> -Je Suis désolé, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> Non, non, non. 210 00:10:27,400 --> 00:10:30,700 Je pense que le tri à bulles serait la bonne façon de faire. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> -Allez, Qui lui a dit cela? 213 00:10:38,180 --> 00:10:40,590 Je ne vois pas l'ordinateur la science dans votre arrière-plan. 214 00:10:40,590 --> 00:10:42,130 >> -We've Obtenu nos espions là-dedans. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Nous allons demander un autre question de l'entrevue. 217 00:10:48,444 --> 00:10:49,300 >> [FIN LECTURE VIDÉO] 218 00:10:49,300 --> 00:10:52,290 >> ENCEINTE: Donc parler chiffres précis cependant, 219 00:10:52,290 --> 00:10:53,890 ne va pas être d'une grande utilité. 220 00:10:53,890 --> 00:10:56,810 Ce n'est pas une leçon de vie que de bulle sorte, donné un million entrées, 221 00:10:56,810 --> 00:10:58,590 pourrait prendre jusqu'à 500 milliards étapes. 222 00:10:58,590 --> 00:11:01,120 Vous ne pouvez pas vraiment généraliser aussi efficacement que de 223 00:11:01,120 --> 00:11:03,560 et prendre de bonnes décisions de conception lors de l'écriture des programmes. 224 00:11:03,560 --> 00:11:07,070 Alors concentrons-nous bien sur la façon dont nous pourrions simplifier ce résultat. 225 00:11:07,070 --> 00:11:11,780 >> Donc j'ai surligné en jaune ici le résultat au carré de n divisé par deux, 226 00:11:11,780 --> 00:11:14,330 si un million carré divisé par deux, et ensuite 227 00:11:14,330 --> 00:11:16,710 J'ai souligné ce la réponse ultime était 228 00:11:16,710 --> 00:11:20,180 une fois nous avons soustrait de n divisé par 2. 229 00:11:20,180 --> 00:11:24,850 Et la demande que je vais faire maintenant est, qui est le diable se soucie si vous soustrayez off 230 00:11:24,850 --> 00:11:30,060 un peu vieux n sur 2 lorsque le premier partie de cette formule est tellement plus grand? 231 00:11:30,060 --> 00:11:33,910 Il domine l'autre terme, n au carré divisée par 2 232 00:11:33,910 --> 00:11:37,510 est tellement plus vaste, clairement, comme n devient grand comme un million, 233 00:11:37,510 --> 00:11:41,450 qui est-il vraiment une grande différence à la fin de la journée entre 500 milliards 234 00:11:41,450 --> 00:11:45,730 et 499 999 500 000? 235 00:11:45,730 --> 00:11:46,349 Pas vraiment. 236 00:11:46,349 --> 00:11:48,640 Et donc ce que nous allons faire comme les informaticiens est 237 00:11:48,640 --> 00:11:53,270 ignorer ces termes d'ordre inférieur et prendre quelque chose comme ça et vraiment 238 00:11:53,270 --> 00:11:56,050 juste simplifier à l' terme qui se passe à la matière. 239 00:11:56,050 --> 00:12:00,315 Les plus grands de nos ensembles de données obtiennent, le plus grand nos bases de données obtiennent, les pages Web plus 240 00:12:00,315 --> 00:12:02,690 nous devons rechercher, le plus amis que vous avez sur Facebook. 241 00:12:02,690 --> 00:12:07,340 >> Comme n est grande, plus nous sommes vraiment va se soucier de la plus grande 242 00:12:07,340 --> 00:12:11,560 terme à une telle analyse de les performances de nos algorithmes. 243 00:12:11,560 --> 00:12:16,230 Et je vais vous dire, vous savez quoi, tri à bulles est de l'ordre de grand O, 244 00:12:16,230 --> 00:12:18,060 de l'ordre de n au carré. 245 00:12:18,060 --> 00:12:20,090 Ce n'est pas exactement n au carré comme nous l'avons vu, 246 00:12:20,090 --> 00:12:22,060 mais qui se soucie vraiment sur ces petites conditions, 247 00:12:22,060 --> 00:12:24,390 et franchement, qui a vraiment se soucie si nous divisons par 2? 248 00:12:24,390 --> 00:12:25,870 C'est juste un facteur constant. 249 00:12:25,870 --> 00:12:29,480 Et est de 500 milliards contre 250 milliards vraiment un gros problème? 250 00:12:29,480 --> 00:12:32,190 Je ne pouvais tout simplement attendre un an, laisser mon ordinateur portable littéralement 251 00:12:32,190 --> 00:12:34,810 obtenir deux fois plus vite dans le matériel, et ce genre de différence 252 00:12:34,810 --> 00:12:36,650 juste disparaît naturellement avec le temps. 253 00:12:36,650 --> 00:12:39,300 >> Qu'est-ce que nous nous soucions est l'expression, la partie 254 00:12:39,300 --> 00:12:42,489 de l'expression qui va varier comme notre entrée devient de plus en plus grande. 255 00:12:42,489 --> 00:12:45,280 Et en effet, dans le monde réel, c'est ce qui se passe de plus en plus 256 00:12:45,280 --> 00:12:48,330 est des entrées à nos problèmes et algorithmes sont de plus. 257 00:12:48,330 --> 00:12:53,470 Donc grand O va être la notation, la notation asymptotique, que nous venons de 258 00:12:53,470 --> 00:12:57,160 utiliser comme des informaticiens pour décrire la performance, ou le temps d'exécution, 259 00:12:57,160 --> 00:12:58,130 d'un algorithme. 260 00:12:58,130 --> 00:13:00,800 Afin que nous puissions comparer les algorithmes sur des ordinateurs différents écrits 261 00:13:00,800 --> 00:13:04,170 par des personnes différentes, en utilisant une certaine mesure fondamentalement similaire 262 00:13:04,170 --> 00:13:07,557 comme le nombre de comparaisons que vous êtes faire, ou peut-être le nombre de swaps 263 00:13:07,557 --> 00:13:08,140 vous faites. 264 00:13:08,140 --> 00:13:11,910 >> Ce que nous n'allons pas compte est la quantité de temps 265 00:13:11,910 --> 00:13:13,981 qui passe sur l'horloge sur le mur en général. 266 00:13:13,981 --> 00:13:16,230 Qu'est-ce que nous n'allons pas à s'inquiéter est de savoir comment la quantité de mémoire 267 00:13:16,230 --> 00:13:17,820 vous utilisez aujourd'hui à moins, si c'est 268 00:13:17,820 --> 00:13:19,370 autre ressource que nous pourrions mesurer. 269 00:13:19,370 --> 00:13:23,610 Nous allons essayer de fonder nos analyses uniquement sur les opérations de base, les uns, 270 00:13:23,610 --> 00:13:25,930 franchement, que vous pouvez voir plus visuellement. 271 00:13:25,930 --> 00:13:30,700 Donc, avec quelque chose comme grand O n carré, je prétends que O n carré 272 00:13:30,700 --> 00:13:35,820 est une limite supérieure sur la soi-disant temps de tri à bulles en cours d'exécution. 273 00:13:35,820 --> 00:13:38,820 En d'autres termes, si vous voulu prétendre qu'il n'y a 274 00:13:38,820 --> 00:13:41,370 cette limite supérieure du nombre de les étapes d'un algorithme peut prendre, 275 00:13:41,370 --> 00:13:46,240 ça va être dans le grand O n carré dans ce cas, une limite supérieure. 276 00:13:46,240 --> 00:13:49,710 >> Que faire si je change le lieu histoire soit pas tri à bulles, 277 00:13:49,710 --> 00:13:50,910 mais de cette limite supérieure. 278 00:13:50,910 --> 00:13:54,030 Pouvez-vous penser à un algorithme que nous avons examiné déjà 279 00:13:54,030 --> 00:13:59,530 dont la borne supérieure, le maximum mesure du temps ou des opérations, 280 00:13:59,530 --> 00:14:04,300 serait, dit-on borné n par une fonction linéaire, 281 00:14:04,300 --> 00:14:07,260 pas une quadratique qui est courbé? 282 00:14:07,260 --> 00:14:10,780 Qu'est-ce que c'est un algorithme qui prend toujours plus 283 00:14:10,780 --> 00:14:12,860 que comme n étapes, ou 2n, étapes ou des étapes de 3n? 284 00:14:12,860 --> 00:14:13,360 Ouais? 285 00:14:13,360 --> 00:14:15,030 >> PUBLIC: Trouver l' plus grand nombre dans une liste? 286 00:14:15,030 --> 00:14:16,930 >> ENCEINTE: Parfait, trouver le plus grand nombre dans une liste. 287 00:14:16,930 --> 00:14:18,940 Si on me donne une liste de les gens, par exemple, 288 00:14:18,940 --> 00:14:21,440 chacun qui tient un certain nombre, quel est le nombre maximum 289 00:14:21,440 --> 00:14:23,770 des mesures qu'il doit me prendre, une personne raisonnablement intelligente, 290 00:14:23,770 --> 00:14:27,530 de trouver le plus grand personne dans cette liste? 291 00:14:27,530 --> 00:14:28,100 n, non? 292 00:14:28,100 --> 00:14:31,320 Parce que dans le pire des cas, où pourrait être la plus grande valeur? 293 00:14:31,320 --> 00:14:32,700 A droite, tout le chemin à la fin. 294 00:14:32,700 --> 00:14:34,575 Ainsi, dans le pire des cas limite supérieure, je pourrais 295 00:14:34,575 --> 00:14:36,450 avoir à aller tout le chemin ici et être comme, 296 00:14:36,450 --> 00:14:39,170 oh, voici le numéro huit, ou quelle que soit la valeur est. 297 00:14:39,170 --> 00:14:41,330 Maintenant, il serait tout simplement stupide si je continuais à aller, non? 298 00:14:41,330 --> 00:14:43,840 Vous recherchez de plus en plus des éléments si le dernier d'entre eux est là-bas? 299 00:14:43,840 --> 00:14:45,340 Alors sûrement, n est une limite supérieure. 300 00:14:45,340 --> 00:14:47,420 Je n'ai pas besoin de prendre plus de pas que cela. 301 00:14:47,420 --> 00:14:51,580 >> Alors que faire si la place j'ai proposé que il existe des algorithmes dans ce monde qui 302 00:14:51,580 --> 00:14:57,750 avoir un temps d'exécution qui est délimitée par le grand O de log n, log n? 303 00:14:57,750 --> 00:15:00,390 Où avons-nous vu cela auparavant? 304 00:15:00,390 --> 00:15:00,890 Ouais? 305 00:15:00,890 --> 00:15:03,309 >> PUBLIC: Dans le problème de l'annuaire téléphonique? 306 00:15:03,309 --> 00:15:04,850 ENCEINTE: Comme le problème de l'annuaire téléphonique. 307 00:15:04,850 --> 00:15:07,754 Quelle a été la mesure de la beaucoup de temps ou combien de larmes il 308 00:15:07,754 --> 00:15:10,170 ça m'a fait de trouver quelqu'un comme Mike Smith dans l'annuaire? 309 00:15:10,170 --> 00:15:13,212 Nous avons affirmé qu'il était log n, et même si inconnu ou il c'est 310 00:15:13,212 --> 00:15:15,170 un peu brumeux ce qu'est un logarithme ou exposant était, 311 00:15:15,170 --> 00:15:17,650 n'oubliez pas que log n désigne généralement le processus, 312 00:15:17,650 --> 00:15:20,790 dans ce cas, de diviser quelque chose de nouveau en deux, et encore, 313 00:15:20,790 --> 00:15:25,790 et de nouveau, et de nouveau, de telle sorte qu'il obtient de plus en plus petit que vous faites cela. 314 00:15:25,790 --> 00:15:28,470 >> Alors connectez-de n se réfère, bien sûr, à l'exemple du livre de téléphone, 315 00:15:28,470 --> 00:15:32,662 à la recherche binaire en théorie, lorsque nous eu les portes virtuelles sur le plateau, 316 00:15:32,662 --> 00:15:34,370 ou quand Sean était la recherche de quelque chose. 317 00:15:34,370 --> 00:15:37,374 S'il avait utilisé la recherche binaire, log n serait la limite supérieure de la quantité d' 318 00:15:37,374 --> 00:15:38,040 temps que prend. 319 00:15:38,040 --> 00:15:44,027 Mais ces algorithmes qui couraient dans log n assumé ce détail clé? 320 00:15:44,027 --> 00:15:45,360 Que la liste a été triée, non? 321 00:15:45,360 --> 00:15:47,789 Votre algorithme est erroné si votre entrée n'est pas triée, 322 00:15:47,789 --> 00:15:49,830 et pourtant vous utilisez quelque chose comme une recherche binaire 323 00:15:49,830 --> 00:15:51,704 parce que vous pourriez sauter droit sur l'élément 324 00:15:51,704 --> 00:15:53,600 sans se rendre compte qu'il s'agit bien là. 325 00:15:53,600 --> 00:15:55,600 >> Maintenant, ce que cela peut signifier, grand O d'un seul? 326 00:15:55,600 --> 00:15:59,117 Cela ne signifie pas que votre algorithme prend une et une seule étape, 327 00:15:59,117 --> 00:16:01,200 cela signifie simplement qu'il faut une nombre constant d'étapes. 328 00:16:01,200 --> 00:16:04,060 C'est peut-être une, c'est peut-être 10, c'est peut-être 1000, 329 00:16:04,060 --> 00:16:07,750 mais il est indépendant de l'ampleur du problème. 330 00:16:07,750 --> 00:16:10,850 Peu importe la taille n est, un algorithme de constante de temps 331 00:16:10,850 --> 00:16:12,747 prend toujours le même nombre de mesures. 332 00:16:12,747 --> 00:16:15,080 Alors, que peut-être un algorithme nous avons parlé ou tout simplement 333 00:16:15,080 --> 00:16:20,418 intuitivement que vient de vous que va toujours dans ce qu'on appelle la constante de temps? 334 00:16:20,418 --> 00:16:20,918 Ouais? 335 00:16:20,918 --> 00:16:22,001 >> PUBLIC: Ajouter deux nombres. 336 00:16:22,001 --> 00:16:25,320 ENCEINTE: Ajouter deux nombres, 2 plus 2 égale 4, c'est fait. 337 00:16:25,320 --> 00:16:27,227 Donc, cela pourrait fonctionner, quoi d'autre? 338 00:16:27,227 --> 00:16:28,560 Que diriez-monde plus réel, ouais? 339 00:16:28,560 --> 00:16:30,686 >> PUBLIC: Trouver l' première chose que dans une liste. 340 00:16:30,686 --> 00:16:32,810 ENCEINTE: Trouver le premier élément dans une liste, bien sûr. 341 00:16:32,810 --> 00:16:34,540 Nous avons effectivement parlé sur les tableaux déjà, 342 00:16:34,540 --> 00:16:36,540 Comment obtenez-vous à la premier élément d'un tableau, 343 00:16:36,540 --> 00:16:40,465 peu importe combien de temps l' tableau est en code C? 344 00:16:40,465 --> 00:16:43,090 Vous utilisez simplement comme le support notation zéro, bam, vous y êtes. 345 00:16:43,090 --> 00:16:46,120 Et en effet les tableaux, comme un côté, support chose généralement connue 346 00:16:46,120 --> 00:16:49,240 que l'accès aléatoire, accès aléatoire la mémoire, parce que vous pouvez littéralement 347 00:16:49,240 --> 00:16:50,284 sauter à un endroit quelconque. 348 00:16:50,284 --> 00:16:52,700 Nous pouvons le faire encore plus simplement nous pouvons revenir en arrière à la semaine zéro 349 00:16:52,700 --> 00:16:53,900 quand nous avons fait Scratch. 350 00:16:53,900 --> 00:16:59,707 Combien de temps at-il fallu pour l' dit bloc dans Scratch à exécuter? 351 00:16:59,707 --> 00:17:00,790 Juste le temps constant, non? 352 00:17:00,790 --> 00:17:03,960 Dis quelque chose, dit quelque chose, il n'a pas d'importance 353 00:17:03,960 --> 00:17:07,359 comment grandes rayures monde, il est toujours va prendre la même quantité de temps 354 00:17:07,359 --> 00:17:08,490 simplement dire quelque chose. 355 00:17:08,490 --> 00:17:11,089 >> Donc, c'est la constante de temps, mais quel est le revers de la médaille? 356 00:17:11,089 --> 00:17:13,030 Si tel était supérieure limites, si nous voulons 357 00:17:13,030 --> 00:17:17,089 pour décrire les limites inférieures de nos algorithmes durée? 358 00:17:17,089 --> 00:17:19,852 Près d'un meilleur des cas potentiellement, si vous voulez, 359 00:17:19,852 --> 00:17:23,060 si ces termes peuvent s'appliquer à mieux cas, pires, étuis moyenne plus 360 00:17:23,060 --> 00:17:26,359 en général, mais concentrons-nous seulement sur des bornes inférieures plus généralement. 361 00:17:26,359 --> 00:17:31,920 Qu'est-ce que c'est un algorithme qui a une borne inférieure de n étapes, 362 00:17:31,920 --> 00:17:33,350 2n, ou des étapes ou des étapes de 3n? 363 00:17:33,350 --> 00:17:36,241 Certains facteurs de n étapes, c'est sa borne inférieure. 364 00:17:36,241 --> 00:17:36,740 Ouais? 365 00:17:36,740 --> 00:17:37,910 >> PUBLIC: Bubble sorte? 366 00:17:37,910 --> 00:17:41,610 >> ENCEINTE: Bubble sorte prend vous minimalement n pas, pourquoi? 367 00:17:41,610 --> 00:17:42,279 Pourquoi donc? 368 00:17:42,279 --> 00:17:45,320 Pourquoi devrait-il commencer à venir à vous intuitivement, même si ce n'est pas simplement 369 00:17:45,320 --> 00:17:46,530 encore? 370 00:17:46,530 --> 00:17:47,030 Ouais? 371 00:17:47,030 --> 00:17:47,990 >> PUBLIC: [inaudible]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 ENCEINTE: Exactement. 374 00:17:52,360 --> 00:17:55,810 Dans le meilleur scénario possible de tri à bulles, et beaucoup d'algorithmes, 375 00:17:55,810 --> 00:17:58,769 si je vous remets huit personnes qui sont déjà triés, 376 00:17:58,769 --> 00:18:00,560 il serait insensé pour vous, l'algorithme, 377 00:18:00,560 --> 00:18:02,202 à aller et venir plus d'une fois, non? 378 00:18:02,202 --> 00:18:04,285 Parce que dès que vous marcher dans la liste une fois, 379 00:18:04,285 --> 00:18:08,090 vous devez réaliser, oh, je n'ai fait aucune swaps, cette liste est triée, sortie. 380 00:18:08,090 --> 00:18:09,700 Mais cela va vous prendre des mesures n. 381 00:18:09,700 --> 00:18:12,033 >> Et inversement, ce qui est une autre façon de penser? 382 00:18:12,033 --> 00:18:15,240 Tri à bulles est un oméga, pour ainsi dire, de n, 383 00:18:15,240 --> 00:18:19,050 parce que si vous regardez moins de n éléments, ce qui 384 00:18:19,050 --> 00:18:23,009 est la question fondamentale là-bas? 385 00:18:23,009 --> 00:18:24,550 Vous ne savez pas si c'est réglé, à droite. 386 00:18:24,550 --> 00:18:26,800 Nous les humains pourraient coup d'œil à huit personnes et être comme, oh, c'est réglé, 387 00:18:26,800 --> 00:18:28,430 Cela ne m'a pas pris les mesures n, mais il l'a fait. 388 00:18:28,430 --> 00:18:30,810 Vos yeux, même si vous nature de faire un grand champ de vision, 389 00:18:30,810 --> 00:18:33,184 vous avez regardé huit éléments, vous avez regardé huit personnes, 390 00:18:33,184 --> 00:18:34,610 c'est huit étapes efficacement. 391 00:18:34,610 --> 00:18:38,612 Et que si je marche dans l'ensemble faire la liste, je me rends compte, oui, triés. 392 00:18:38,612 --> 00:18:41,320 Si je m'arrête à mi-chemin de penser, tout à droite, il est assez triée jusqu'à présent, 393 00:18:41,320 --> 00:18:42,520 quelles sont les chances que ce n'est pas triée? 394 00:18:42,520 --> 00:18:44,186 Que les algorithmes ne va pas être correct. 395 00:18:44,186 --> 00:18:46,250 Peut être plus rapide, mais incorrect. 396 00:18:46,250 --> 00:18:48,500 >> Alors maintenant, nous avons un moyen de décrivant une baisse des limites, 397 00:18:48,500 --> 00:18:49,710 et que dire de la constante de temps? 398 00:18:49,710 --> 00:18:54,565 Qu'est-ce que c'est un algorithme qui a une faible lié à son temps d'exécution de celui-ci? 399 00:18:54,565 --> 00:18:58,350 1 étape, 2 étapes, 10 étapes, mais constant, indépendant de n, 400 00:18:58,350 --> 00:18:59,310 la taille de l'entrée? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Oui, à l'arrière. 403 00:19:04,600 --> 00:19:05,309 >> PUBLIC: Printf? 404 00:19:05,309 --> 00:19:06,183 ENCEINTE: Qu'est-ce que c'est? 405 00:19:06,183 --> 00:19:07,184 PUBLIC: Printf? 406 00:19:07,184 --> 00:19:07,850 ENCEINTE: Printf. 407 00:19:07,850 --> 00:19:08,400 OK, bien sûr. 408 00:19:08,400 --> 00:19:10,720 Donc, il faut un nombre fixe d'étapes. 409 00:19:10,720 --> 00:19:13,170 Et je dois maintenant-- maintenant que nous parlons de code C 410 00:19:13,170 --> 00:19:16,040 et pas Scratch, quelque chose comme par exemple, la fonction printf, 411 00:19:16,040 --> 00:19:17,710 nous devrions commencer à obtenir prudent. 412 00:19:17,710 --> 00:19:21,090 Parce que printf ne prend entrée, c'est une chaîne, 413 00:19:21,090 --> 00:19:23,220 et les chaînes n'ont techniquement longueur. 414 00:19:23,220 --> 00:19:25,530 Donc, si nous voulons maintenant prendre sur vous, si cela ne vous dérange pas, 415 00:19:25,530 --> 00:19:29,430 techniquement, nous pourrions soutenir que printf ne prendre une entrée de longueur variable, 416 00:19:29,430 --> 00:19:32,270 et sûrement cela peut prendre plus temps pour imprimer une chaîne de cette longue, 417 00:19:32,270 --> 00:19:33,560 de cette longueur. 418 00:19:33,560 --> 00:19:36,570 >> Alors que faire si l'on considère que la tri et de recherche des exemples? 419 00:19:36,570 --> 00:19:40,450 Qu'est-ce à propos de Mike Smith dans le téléphone livre, ou recherche binaire plus généralement? 420 00:19:40,450 --> 00:19:42,220 Dans le meilleur des cas, ce qui pourrait arriver? 421 00:19:42,220 --> 00:19:45,577 J'ouvre le livre de téléphone et, bam, il ya le numéro de Mike Smith. 422 00:19:45,577 --> 00:19:46,660 Je peux l'appeler tout de suite. 423 00:19:46,660 --> 00:19:49,390 >> Pris un peu, peut-être deux étapes, mais un nombre constant d'étapes 424 00:19:49,390 --> 00:19:50,230 si je eu de la chance. 425 00:19:50,230 --> 00:19:52,570 Et franchement, nous avons vu sur Lundi un camarade de classe 426 00:19:52,570 --> 00:19:54,710 être assez chanceux deux fois de suite. 427 00:19:54,710 --> 00:19:57,050 Et c'était en effet constant fois en baisse limites 428 00:19:57,050 --> 00:20:01,280 sur l'algorithme en question pour trouver le nombre 50 derrière ceux fermée 429 00:20:01,280 --> 00:20:01,830 portes. 430 00:20:01,830 --> 00:20:06,400 >> Maintenant, en passant, si vous découvrez que les deux grand O, la limite supérieure, 431 00:20:06,400 --> 00:20:09,310 et l'oméga, la limite inférieure, sont l'un dans le même, que 432 00:20:09,310 --> 00:20:11,830 C'est la même formule à entre parenthèses, vous pouvez également 433 00:20:11,830 --> 00:20:15,170 dire, juste pour être de fantaisie, que quelque chose est en thêta 434 00:20:15,170 --> 00:20:18,270 de n ou thêta d'une autre valeur. 435 00:20:18,270 --> 00:20:20,661 Cela signifie juste quand grand O et oméga sont les mêmes. 436 00:20:20,661 --> 00:20:21,910 Maintenant, qu'en est-il de sélection sorte? 437 00:20:21,910 --> 00:20:23,400 Nous allons utiliser ce nouveau vocabulaire. 438 00:20:23,400 --> 00:20:27,407 En sélection sorte, ce sont nous faire encore, et encore, et encore? 439 00:20:27,407 --> 00:20:29,990 J'allais en arrière à travers la liste, à la recherche de qui? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Le plus petit nombre. 442 00:20:34,730 --> 00:20:37,560 >> Alors, comment de nombreuses étapes, comment de nombreuses comparaisons ai-je 443 00:20:37,560 --> 00:20:43,250 avoir à faire afin de déterminer qui le plus petit élément de la liste est? 444 00:20:43,250 --> 00:20:44,437 n moins 1, non? 445 00:20:44,437 --> 00:20:47,770 Parce que si je viens de commencer par celle que je suis donné et je commence à lui comparer, 446 00:20:47,770 --> 00:20:49,519 alors lui ou elle, lui ou elle, lui ou elle, je 447 00:20:49,519 --> 00:20:52,010 ne peut lier les éléments ainsi que n moins une fois. 448 00:20:52,010 --> 00:20:55,630 Donc, la sélection se sorte de la même n moins 1 étapes de la première heure. 449 00:20:55,630 --> 00:20:59,540 >> Combien de pas faut-il pour trouver le deuxième élément le plus petit? 450 00:20:59,540 --> 00:21:02,920 n moins 2, parce que je suis étant muet si je regarde toujours les mêmes personnes 451 00:21:02,920 --> 00:21:06,280 encore si je l'ai déjà choisi ou elle et les mettre à leur place. 452 00:21:06,280 --> 00:21:09,270 Et la troisième étape, n moins 3, puis n moins 4. 453 00:21:09,270 --> 00:21:11,020 Nous avons vu ce modèle avant, et en fait 454 00:21:11,020 --> 00:21:13,460 sélection sorte similaire a une borne supérieure 455 00:21:13,460 --> 00:21:16,210 de n au carré si nous le faisons jusqu'à ce que la somme. 456 00:21:16,210 --> 00:21:19,790 Quelle est sa limite inférieure, la sélection sorte? 457 00:21:19,790 --> 00:21:25,350 Au minimum, combien sélection de must de temps sorte prendre, comme nous l'avons défini le lundi? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Proposer des deux options. 460 00:21:30,490 --> 00:21:32,360 C'est peut-être n, comme avant. 461 00:21:32,360 --> 00:21:35,040 C'est peut-être n carré, comme il est maintenant que la limite supérieure. 462 00:21:35,040 --> 00:21:35,874 >> PUBLIC: n carré. 463 00:21:35,874 --> 00:21:36,664 ENCEINTE: n carré. 464 00:21:36,664 --> 00:21:37,368 Pourquoi? 465 00:21:37,368 --> 00:21:40,060 >> PUBLIC: Parce que vous avez à définir [inaudible]. 466 00:21:40,060 --> 00:21:41,510 >> ENCEINTE: Exactement. 467 00:21:41,510 --> 00:21:45,077 Au moins que je l'ai définie sélection sorte il était assez naïf, continuez, 468 00:21:45,077 --> 00:21:46,160 trouver le plus petit élément. 469 00:21:46,160 --> 00:21:47,770 Allez encore une fois, trouver le plus petit élément. 470 00:21:47,770 --> 00:21:49,490 Allez encore une fois, trouver le plus petit élément. 471 00:21:49,490 --> 00:21:51,700 Il n'y a pas de genre l'optimisation de là que 472 00:21:51,700 --> 00:21:54,350 pourraient me laisser avorter après seulement n de marches. 473 00:21:54,350 --> 00:21:57,080 Donc, en fait, la sélection sorte, l'oméga de n carré. 474 00:21:57,080 --> 00:22:00,667 >> Qu'en est-il du tri par insertion, où j'ai pris qui m'a donné, et puis je lui laissais 475 00:22:00,667 --> 00:22:01,750 ou son au bon endroit? 476 00:22:01,750 --> 00:22:04,958 Puis je me rendis à la deuxième personne, lui balancé au bon endroit. 477 00:22:04,958 --> 00:22:07,910 Ensuite, la personne suivante, flac lui au bon endroit. 478 00:22:07,910 --> 00:22:10,537 Notez que ceci est très linéaire, pour ainsi dire. 479 00:22:10,537 --> 00:22:12,620 Je suis une ligne droite, je suis ne va-et-vient, 480 00:22:12,620 --> 00:22:16,080 Je n'ai jamais regarder en arrière vraiment, mais ce qui se passe quand je l'ai insérer 481 00:22:16,080 --> 00:22:20,302 ou elle dans le début de la liste que nous avons fait le lundi? 482 00:22:20,302 --> 00:22:21,010 Ce qui se passe? 483 00:22:21,010 --> 00:22:21,510 Ouais? 484 00:22:21,510 --> 00:22:23,122 PUBLIC: [inaudible]. 485 00:22:23,122 --> 00:22:24,830 ENCEINTE: Ouais, était la capture, non? 486 00:22:24,830 --> 00:22:26,746 Vous vous souvenez sans doute de vos camarades de classe, si elles 487 00:22:26,746 --> 00:22:29,670 ont été faire aucun mouvement avec leurs pieds, c'était une opération. 488 00:22:29,670 --> 00:22:33,610 Donc, si il y avait trois personnes ici et la nouvelle personne appartenait loin là-bas, 489 00:22:33,610 --> 00:22:37,360 sur une longue étape comme celle-ci, bien sûr, il ou elle pouvait aller jusqu'à la fin. 490 00:22:37,360 --> 00:22:40,074 Mais si nous pensons à un ordinateur et un réseau de mémoire, 491 00:22:40,074 --> 00:22:41,990 ces gens vont d'avoir à mélanger sur 492 00:22:41,990 --> 00:22:43,260 pour faire place à cette personne. 493 00:22:43,260 --> 00:22:46,930 Et pour que n moins 1 tergiversations, n moins deux tergiversations, n 494 00:22:46,930 --> 00:22:50,660 moins 3 tergiversations est juste un peu passe derrière moi, pas en face de moi 495 00:22:50,660 --> 00:22:52,710 comme avant, dans un certain sens. 499 00:22:52,557 --> 00:22:54,640 Maintenant, en passant, et comme vous pourriez avoir vu en ligne 500 00:22:54,640 --> 00:22:57,699 si vous commencez à fouiller sur sortes, il ya tant de ceux différents 501 00:22:57,699 --> 00:22:59,490 là-bas, certains d'entre eux mieux que d'autres. 502 00:22:59,490 --> 00:23:02,200 En effet, c'est une bogosort c'est le genre de plaisir à regarder. 503 00:23:02,200 --> 00:23:06,650 Bogosort prend un ensemble de numéros ou dire un jeu de cartes, 504 00:23:06,650 --> 00:23:09,870 les mélange de façon aléatoire, et vérifie si ils sont triés. 505 00:23:09,870 --> 00:23:12,130 Et si non, le fait encore. 506 00:23:12,130 --> 00:23:14,140 Et si non, le fait encore. 507 00:23:14,140 --> 00:23:15,440 Si non, le fait encore. 508 00:23:15,440 --> 00:23:17,060 Incroyablement stupide. 509 00:23:17,060 --> 00:23:19,520 >> Et en effet, si vous lisez comme l'article de Wikipedia, 510 00:23:19,520 --> 00:23:21,200 son surnom est une sorte stupide. 511 00:23:21,200 --> 00:23:25,180 Il finira par travailler, je l'espère, suffisamment de temps, 512 00:23:25,180 --> 00:23:28,240 mais ce laps de temps pourrait prendre un certain temps. 513 00:23:28,240 --> 00:23:31,650 Donc, les choses de la vitesse de si je pouvais, laisser à partir de l'exemple de Mary Beth plus tôt, 514 00:23:31,650 --> 00:23:35,150 en ayant un peu plus d'éléments, mais deux autres processeurs. 515 00:23:35,150 --> 00:23:37,100 Deux personnes, si vous ne me dérangerait pas vous joindre à moi. 516 00:23:37,100 --> 00:23:40,972 Comment environ 1 ici, et nous allons go-- personne là-bas? 517 00:23:40,972 --> 00:23:41,722 Personne là-bas? 518 00:23:41,722 --> 00:23:42,221 Dáccord. 519 00:23:42,221 --> 00:23:44,190 Vous avec le noir chemise, oui, allez vers le bas. 520 00:23:44,190 --> 00:23:45,000 Très bien, quel est votre nom? 521 00:23:45,000 --> 00:23:45,720 >> PUBLIC: Peter. 522 00:23:45,720 --> 00:23:46,100 >> ENCEINTE: Qu'est-ce que c'est? 523 00:23:46,100 --> 00:23:46,766 >> PUBLIC: Peter. 524 00:23:46,766 --> 00:23:49,450 ENCEINTE: Peter, David, ravi de vous rencontrer. 525 00:23:49,450 --> 00:23:53,670 Très bien, nous avons Peter ici, si vous envie de venir sur la table ici. 526 00:23:53,670 --> 00:23:54,550 Et quel est votre nom? 527 00:23:54,550 --> 00:23:55,216 >> PUBLIC: Elena. 528 00:23:55,216 --> 00:23:55,970 ENCEINTE: Elena. 529 00:23:55,970 --> 00:23:57,030 OK, nice to meet you. 530 00:23:57,030 --> 00:23:58,060 Elena répond Peter. 531 00:23:58,060 --> 00:23:59,170 Peter, Elena. 532 00:23:59,170 --> 00:24:02,290 Et nous aurons besoin Andrew ici aussi, s'il vous plaît. 533 00:24:02,290 --> 00:24:06,107 Et votre défi va être pour trier un jeu de cartes. 534 00:24:06,107 --> 00:24:08,190 Et si familier, pont de cartes devrait en fin de compte 535 00:24:08,190 --> 00:24:11,064 trier un petit quelque chose comme ce que nous ferons les clubs, alors 536 00:24:11,064 --> 00:24:13,660 les piques, les coeurs et diamants, de l'as comme un, 537 00:24:13,660 --> 00:24:15,570 tout le chemin jusqu'à roi. 538 00:24:15,570 --> 00:24:20,890 >> Les cartes que je vais vous donner vont être 52 en quantité. 539 00:24:20,890 --> 00:24:23,160 Nous allons similaire fois que vous, dans un instant. 540 00:24:23,160 --> 00:24:26,410 Nous allons jeter Andrew sur l'écran ici, 541 00:24:26,410 --> 00:24:28,170 de façon à regarder comme vous le faites. 542 00:24:28,170 --> 00:24:31,070 Et de sorte que l'intégralité de cette est d'autant plus visible, 543 00:24:31,070 --> 00:24:33,490 ce sont les cartes que j'ai eu sur Amazon. 544 00:24:33,490 --> 00:24:42,861 Donc, ils sont déjà au hasard trié, et nous allons vous chronométrer. 545 00:24:42,861 --> 00:24:44,610 Et nous allons keep it real cette fois, 546 00:24:44,610 --> 00:24:47,820 donc nous allons essayer de faire pression sur vous parce que sinon ce sera être fastidieux 547 00:24:47,820 --> 00:24:48,460 rapidement. 548 00:24:48,460 --> 00:24:53,860 Si vous pouviez passer à trier 52 éléments ensemble via des moyens, maintenant. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> Et encore une fois, comme nous le montre ces les gars font ce, à la fin 551 00:25:07,180 --> 00:25:10,200 va produire une évidente Par conséquent, penser vraiment 552 00:25:10,200 --> 00:25:12,962 comment ils sont chaque faire, comment vous pourriez le décrire. 553 00:25:12,962 --> 00:25:15,045 Parce qu'encore une fois, ce sont tous les processus, algorithmes 554 00:25:15,045 --> 00:25:17,090 que nous prenons pour acquis comme un être humain. 555 00:25:17,090 --> 00:25:22,349 Mais vous avez eu probablement longtemps intuition, longtemps avant que vous même 556 00:25:22,349 --> 00:25:24,390 pensé à prendre une informatique vous classe 557 00:25:24,390 --> 00:25:27,223 aurait eu l'intuition de qui pour résoudre les problèmes de ce genre. 558 00:25:27,223 --> 00:25:29,560 Mais une fois que vous reconnaissez les modèles et commencer 559 00:25:29,560 --> 00:25:32,407 de formaliser les étapes avec qui vous résoudre ces problèmes, 560 00:25:32,407 --> 00:25:35,490 vous verrez que vous pouvez résoudre beaucoup plus intéressant et beaucoup plus complexe 561 00:25:35,490 --> 00:25:39,190 problèmes rapidement. 562 00:25:39,190 --> 00:25:42,351 Donc, quelqu'un dans le public, ce qui est au moins un élément de l'algorithme 563 00:25:42,351 --> 00:25:43,350 qu'ils utilisent ici? 564 00:25:43,350 --> 00:25:44,275 >> PUBLIC: [inaudible] 565 00:25:44,275 --> 00:25:45,150 ENCEINTE: Qu'est-ce que c'est? 566 00:25:45,150 --> 00:25:47,062 PUBLIC: En costume. 567 00:25:47,062 --> 00:25:47,770 ENCEINTE: En costume. 568 00:25:47,770 --> 00:25:50,630 Alors d'abord ils se regroupent tous les diamants ensemble 569 00:25:50,630 --> 00:25:52,560 Il semble que l'ensemble de l' coeurs ensemble, il semble, 570 00:25:52,560 --> 00:25:56,520 et ainsi de suite, sans égard pour les numéros sur les cartes. 571 00:25:56,520 --> 00:26:00,900 Et maintenant, ils apparaissent, par exemple, à les trier par numéro. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Très bon. 574 00:26:08,910 --> 00:26:12,370 >> Très bien, alors ce qui se passe à être la dernière étape alors ici? 575 00:26:12,370 --> 00:26:16,950 Une fois que nous avons quatre couleurs triées, ce qui devons-nous faire pour les quatre piles 576 00:26:16,950 --> 00:26:20,059 afin d'obtenir une triés pont, tout simplement? 577 00:26:20,059 --> 00:26:21,350 Nous avons donc besoin de les fusionner à nouveau. 578 00:26:21,350 --> 00:26:25,160 >> Donc, il ya une idée intéressante qui encore une fois, disons-le, est très intuitive même 579 00:26:25,160 --> 00:26:28,140 si vous ne l'auriez jamais giflé ce genre de étiquette. 580 00:26:28,140 --> 00:26:31,900 Cette notion fondamentale de la division le problème n'est pas dans la moitié de ce temps, 581 00:26:31,900 --> 00:26:33,410 mais au moins en quatre morceaux. 582 00:26:33,410 --> 00:26:36,810 Résolution à peu près problèmes fondamentalement identiques 583 00:26:36,810 --> 00:26:40,480 indépendamment les uns des autres, et en fusionnant les résultats. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 Et, excellent, fait. 586 00:26:50,140 --> 00:26:52,140 Très bien, un grand rond d'applaudissements, si nous le pouvions. 587 00:26:52,140 --> 00:26:56,480 >> [Applaudissements] 588 00:26:56,480 --> 00:26:59,740 >> Président: Je n'ai aucune idée de ce que vous aurez faites avec ceux-ci, mais vous pouvez y aller. 589 00:26:59,740 --> 00:27:01,690 Merci beaucoup. 590 00:27:01,690 --> 00:27:04,660 Voyons donc, à deux minutes et huit secondes, 591 00:27:04,660 --> 00:27:07,490 si vous souhaitez défier vos amis. 592 00:27:07,490 --> 00:27:12,160 Qu'est-ce donc qui se passe à être tirer de cette 593 00:27:12,160 --> 00:27:13,830 que nous pouvons tirer parti de façon plus générale? 594 00:27:13,830 --> 00:27:16,080 Eh bien, pensez à ce tableau de nombres, 595 00:27:16,080 --> 00:27:19,060 et repense maintenant à une partie de la pseudo que nous avons écrit dans le passé, 596 00:27:19,060 --> 00:27:22,080 et ce fut le pseudo-code pour résoudre le problème de l'annuaire téléphonique. 597 00:27:22,080 --> 00:27:25,150 Lequel en pseudo je énumérées de façon plus méthodique 598 00:27:25,150 --> 00:27:28,400 de décrire comment j'ai fait un très intuitive algorithme humain de diviser le téléphone 599 00:27:28,400 --> 00:27:31,650 livre en deux, répéter, répéter, répéter, jusqu'à ce que je trouve quelqu'un comme Mike Smith, 600 00:27:31,650 --> 00:27:33,790 si il est en effet dans l'annuaire téléphonique. 601 00:27:33,790 --> 00:27:37,610 >> Mais j'ai un peu l'habitude ce que j'appellerai une approche très itérative ici, 602 00:27:37,610 --> 00:27:42,160 en particulier préavis ligne 8 et la ligne 11. 603 00:27:42,160 --> 00:27:46,750 Ce sont la preuve d'une itératif approche, une approche en boucle, 604 00:27:46,750 --> 00:27:49,040 parce que c'est exactement le comportement qu'ils induisent. 605 00:27:49,040 --> 00:27:52,910 Ces lignes deux disent aller à ligne de trois, et vous pouvez sorte de 606 00:27:52,910 --> 00:27:55,140 penser que, dans votre l'œil de l'esprit comme étant une boucle. 607 00:27:55,140 --> 00:27:59,080 Il vous dit de revenir à l'étape trois et répéter, encore et encore, 608 00:27:59,080 --> 00:28:00,010 et de nouveau. 609 00:28:00,010 --> 00:28:04,410 >> Mais que faire si nous misons sur une idée clé ici que nous n'avons pas la dernière fois, 610 00:28:04,410 --> 00:28:10,280 et de simplifier la ligne 8 et ligne 11 et leurs voisins 611 00:28:10,280 --> 00:28:12,840 comme tout cela, en jaune. 612 00:28:12,840 --> 00:28:16,480 Ce n'est pas fondamentalement raccourcir le pseudo beaucoup, 613 00:28:16,480 --> 00:28:20,530 mais il est fondamentalement changer la nature de mon algorithme. 614 00:28:20,530 --> 00:28:24,220 Ce que je suis en train de dire à l'étape 7, à l'étape 10, 615 00:28:24,220 --> 00:28:29,140 est à la recherche de Mike de la même manière exacte, 616 00:28:29,140 --> 00:28:31,580 mais juste à la gauche la moitié ou la moitié droite. 617 00:28:31,580 --> 00:28:33,420 >> En d'autres termes, si Je pars de la première étape, 618 00:28:33,420 --> 00:28:36,150 ramasser annuaire téléphonique, ouverte à milieu de livre de téléphone, regardez les noms, 619 00:28:36,150 --> 00:28:39,010 si Smith est parmi Nom, appeler Mike, d'autre 620 00:28:39,010 --> 00:28:44,340 si Smith est antérieure dans le livre, l'étape sept rechercher Mike dans la moitié gauche de livre. 621 00:28:44,340 --> 00:28:47,130 Mais ce genre de sent comme ça me laissant pendre, non? 622 00:28:47,130 --> 00:28:49,240 En jaune, est une instruction, mais comment puis-je 623 00:28:49,240 --> 00:28:51,870 rechercher Mike dans la gauche la moitié de l'annuaire téléphonique? 624 00:28:51,870 --> 00:28:54,210 Où dois-je une Je algorithme avec lequel 625 00:28:54,210 --> 00:28:57,100 peut chercher quelqu'un comme Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Eh bien, c'est nous regarder en face. 627 00:28:58,980 --> 00:29:03,090 Je peux littéralement utiliser exactement la même programme va effectivement au sommet 628 00:29:03,090 --> 00:29:06,490 et remettez-course les mêmes lignes de code. 629 00:29:06,490 --> 00:29:10,610 >> Ainsi, même si cela doit se sentir comme un peu de définition cyclique 630 00:29:10,610 --> 00:29:13,480 où vous répondez à quelqu'un est question par tout type de demande 631 00:29:13,480 --> 00:29:15,990 la même question, comme pourquoi, pourquoi, pourquoi? 632 00:29:15,990 --> 00:29:21,580 La réalité est que nous avons codé en dur quelques lignes spéciales, l'étape 4, 633 00:29:21,580 --> 00:29:25,320 qui est un cas, et l'étape 12, qui est effectivement une autre branche, 634 00:29:25,320 --> 00:29:30,120 parce que nous avons ces mesures palliatives, cet algorithme prend fin si nous 635 00:29:30,120 --> 00:29:32,050 trouver Mike, ou si nous ne le faisons pas. 636 00:29:32,050 --> 00:29:36,810 Mais à l'étape 7 et 10 maintenant, nous avons ce que nous appellerons un algorithme récursif. 637 00:29:36,810 --> 00:29:40,420 Et la récursivité est en effet une idée puissante c'est un peu l'esprit de flexion dans un premier temps, 638 00:29:40,420 --> 00:29:42,500 que nous pouvons maintenant appliquer comme suit. 639 00:29:42,500 --> 00:29:46,600 >> Le tri par fusion sera la dernière sorte que nous regardons, au moins en classe formellement. 640 00:29:46,600 --> 00:29:50,040 Et c'est fondamentalement différent de ces trois dernière, et certainement 641 00:29:50,040 --> 00:29:52,140 quatre derniers si nous incluons bogosort. 642 00:29:52,140 --> 00:29:54,810 Voici le pseudo-code pour le tri par fusion. 643 00:29:54,810 --> 00:30:00,170 Quand à l'entrée de n éléments, ainsi donné une matrice de taille n, si n est inférieur à 2, 644 00:30:00,170 --> 00:30:01,040 retourner. 645 00:30:01,040 --> 00:30:03,610 Alors, pourquoi ai-je que santé mentale vérifier d'abord? 646 00:30:03,610 --> 00:30:09,477 Quelle est la conséquence si je vous remets un réseau dont la longueur est inférieure à n 2? 647 00:30:09,477 --> 00:30:11,060 Il est déjà trié, de toute évidence, non? 648 00:30:11,060 --> 00:30:13,640 Parce que la liste a soit un élément, qui est trivialement 649 00:30:13,640 --> 00:30:15,180 trié parce que c'est la seule chose qui existe. 650 00:30:15,180 --> 00:30:18,138 Ou, il est de la taille zéro, ce qui signifie il n'y a rien à trier, donc par nature 651 00:30:18,138 --> 00:30:18,720 elle est triée. 652 00:30:18,720 --> 00:30:20,410 Il ya juste rien de mal là-bas. 653 00:30:20,410 --> 00:30:22,310 Donc, c'est notre affaire dite de base. 654 00:30:22,310 --> 00:30:24,440 >> C'est dans le même esprit à ce que nous avons fait avec Mike. 655 00:30:24,440 --> 00:30:26,023 Si Mike dans l'annuaire téléphonique, appelez-le. 656 00:30:26,023 --> 00:30:27,740 Si il n'est pas là, abandonner. 657 00:30:27,740 --> 00:30:31,240 C'est une affaire dite de base, pour s'assurer cet algorithme à la fin de la journée 658 00:30:31,240 --> 00:30:33,540 s'arrête dans certaines circonstances. 659 00:30:33,540 --> 00:30:37,890 >> Mais voici le saut de la foi maintenant, sinon, trier la moitié gauche des éléments, 660 00:30:37,890 --> 00:30:39,740 ensuite trier le droit la moitié des éléments, 661 00:30:39,740 --> 00:30:41,189 puis fusionner les moitiés triées. 662 00:30:41,189 --> 00:30:43,230 Et c'est là qu'il se sent comme nous défilez. 663 00:30:43,230 --> 00:30:46,900 Je vous ai demandé de trier n éléments, et je suis 664 00:30:46,900 --> 00:30:50,712 dire, OK, faites-le par le tri la gauche et la droite de tri. 665 00:30:50,712 --> 00:30:52,420 Mais je dis un autre chose, et ce 666 00:30:52,420 --> 00:30:55,530 est le thème clé, il semble dans l'intuition à ce jour, 667 00:30:55,530 --> 00:30:57,380 il ya cette troisième étape de fusion. 668 00:30:57,380 --> 00:31:00,430 Qui, même si elle semble tellement stupide dans l'esprit, 669 00:31:00,430 --> 00:31:02,320 comme juste fusionner des choses ainsi, il semble 670 00:31:02,320 --> 00:31:05,380 être une étape clé vers l' réassemblage de deux problèmes que 671 00:31:05,380 --> 00:31:07,330 ont été divisés en fin de compte la moitié. 672 00:31:07,330 --> 00:31:12,090 >> Donc, le tri par fusion, faisons cela, si vous voulez humour moi, avec un plus démonstration, 673 00:31:12,090 --> 00:31:14,730 tellement que nous avons une numéros de travailler avec. 674 00:31:14,730 --> 00:31:19,470 Puis-je échanger huit le stress balles pour huit personnes? 675 00:31:19,470 --> 00:31:29,320 Très bien, que diriez-vous trois, vous quatre dans cette section, cinq, six, et nous allons 676 00:31:29,320 --> 00:31:30,720 ne 7, 8, viennent sur place. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 OK, ouais OK. 679 00:31:36,520 --> 00:31:38,640 Minus 8, il nous aller, plus 1. 680 00:31:38,640 --> 00:31:39,150 Excellente. 681 00:31:39,150 --> 00:31:42,000 Tous sont à droite sur la place, nous allons vous donner rapidement des numéros. 682 00:31:42,000 --> 00:31:50,800 Le numéro deux, numéro trois, numéro quatre, nombre de cinq, six, sept et huit. 683 00:31:50,800 --> 00:31:52,140 J'ai fait huit correctement cette fois. 684 00:31:52,140 --> 00:31:56,390 >> OK, alors allez-y si vous le pouviez, et nous allons trier dans l'ordre original 685 00:31:56,390 --> 00:31:59,810 que nous avons eu hier qui a examiné comme ça, si vous voulez bien. 686 00:31:59,810 --> 00:32:03,620 Et nous allons le faire en face de la table. 687 00:32:03,620 --> 00:32:06,510 Très bien, alors le tri par fusion. 688 00:32:06,510 --> 00:32:08,820 C'est là que ça se passe pour obtenir assez intéressant, 689 00:32:08,820 --> 00:32:12,800 parce que j'ai l'impression de me donner beaucoup moins d'informations aujourd'hui. 690 00:32:12,800 --> 00:32:15,149 >> Donc, le tri par fusion d'abord sur l'entrée de n éléments, 691 00:32:15,149 --> 00:32:18,440 et n'est évidemment pas inférieur à deux, c'est huit, donc j'ai un peu plus de travail à faire. 692 00:32:18,440 --> 00:32:21,140 Alors maintenant, mentalement nous comme une classe sont maintenant dans l'autre branche, 693 00:32:21,140 --> 00:32:22,540 ce qui signifie trois étapes. 694 00:32:22,540 --> 00:32:25,017 Tout d'abord, je dois trier la la moitié gauche des éléments. 695 00:32:25,017 --> 00:32:26,350 Alors, comment puis-je m'y prendre? 696 00:32:26,350 --> 00:32:28,950 Eh bien, je vais type de diviser mentalement la liste ici, 697 00:32:28,950 --> 00:32:30,700 vous n'avez pas à déplacer physiquement, et je suis 698 00:32:30,700 --> 00:32:33,180 va se concentrer uniquement sur la la moitié gauche des éléments ici. 699 00:32:33,180 --> 00:32:36,770 Alors, comment dois-je aller sur le tri maintenant une liste de taille quatre? 700 00:32:36,770 --> 00:32:38,730 Quel est mon algorithme? 701 00:32:38,730 --> 00:32:42,580 D'abord, je vérifie est n moins de deux, non, si je passe à l'autre bloc à nouveau. 702 00:32:42,580 --> 00:32:43,900 Trier gauche de la moitié des éléments. 703 00:32:43,900 --> 00:32:45,608 >> Alors maintenant, à nouveau, mentalement, et c'est là que 704 00:32:45,608 --> 00:32:49,550 vous avez à courir beaucoup d' l'histoire mentale, si vous voulez. 705 00:32:49,550 --> 00:32:51,940 Maintenant, je suis le tri de la gauche la moitié de la moitié gauche. 706 00:32:51,940 --> 00:32:57,000 Très bien, alors maintenant je appeler mon même fusion algorithme de tri, est n moins de deux? 707 00:32:57,000 --> 00:33:00,590 Non, il est deux, donc je dois trier la moitié gauche et la moitié droite. 708 00:33:00,590 --> 00:33:02,042 Alors on y va, trier la moitié gauche. 709 00:33:02,042 --> 00:33:03,750 Pourquoi ne pas vous venez de avancer d'un pas. 710 00:33:03,750 --> 00:33:04,415 Quel est votre nom? 711 00:33:04,415 --> 00:33:04,860 >> PUBLIC: Darren. 712 00:33:04,860 --> 00:33:05,260 >> ENCEINTE: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan a pris les devants. 714 00:33:06,040 --> 00:33:06,748 >> PUBLIC: Darren. 715 00:33:06,748 --> 00:33:09,000 ENCEINTE: Darren, fait. 716 00:33:09,000 --> 00:33:10,090 Avez-vous dit Darren ou Dan? 717 00:33:10,090 --> 00:33:10,550 >> PUBLIC: Darren. 718 00:33:10,550 --> 00:33:11,216 >> ENCEINTE: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, Darren a intensifié vers l'avant et il est maintenant triée. 720 00:33:14,422 --> 00:33:16,130 Et c'est presque un revendication inepte, non? 721 00:33:16,130 --> 00:33:18,862 Je ne crois pas vraiment à la réalisation quoi que ce soit, mais nous allons procéder. 722 00:33:18,862 --> 00:33:20,820 Maintenant, permettez-moi de trier le droit la moitié des éléments. 723 00:33:20,820 --> 00:33:21,200 Quel est votre nom? 724 00:33:21,200 --> 00:33:21,690 >> PUBLIC: Luke. 725 00:33:21,690 --> 00:33:22,273 >> ENCEINTE: Luke. 726 00:33:22,273 --> 00:33:23,400 Allez, un pas en avant. 727 00:33:23,400 --> 00:33:25,640 Fait, j'ai trié Luke. 728 00:33:25,640 --> 00:33:28,570 La moitié gauche est maintenant triée et la moitié droite est maintenant triée, 729 00:33:28,570 --> 00:33:30,770 mais encore une fois, il ya une étape clé ici. 730 00:33:30,770 --> 00:33:32,940 Que dois-je la prochaine dois faire? 731 00:33:32,940 --> 00:33:33,941 Fusionner les deux moitiés triées. 732 00:33:33,941 --> 00:33:36,648 Maintenant, nous allons avoir juste chacun dans les deux sens de cette façon, 733 00:33:36,648 --> 00:33:38,620 parce que je sorte de besoin un espace de travail. 734 00:33:38,620 --> 00:33:40,411 C'est presque comme si ceux-ci les gars sont sur une table, 735 00:33:40,411 --> 00:33:42,460 et j'ai besoin d'une certaine marge pour les déplacer sur. 736 00:33:42,460 --> 00:33:44,170 Donc, je vais fusionner vous les gars en regardant 737 00:33:44,170 --> 00:33:45,960 à la moitié gauche et la moitié droite. 738 00:33:45,960 --> 00:33:48,740 Et qui vient évidemment en premier lieu, moitié moitié gauche ou à droite? 739 00:33:48,740 --> 00:33:52,710 Donc, la moitié droite, donc passons Luke sur ici à la position initiale de Darren. 740 00:33:52,710 --> 00:33:57,640 Et maintenant de fusionner leur moitié gauche dans, Darren va passer là. 741 00:33:57,640 --> 00:33:59,750 >> Alors se sent comme presque un effet bulle de tri, 742 00:33:59,750 --> 00:34:02,482 mais mon algorithme fondamental, très différent cette fois. 743 00:34:02,482 --> 00:34:04,815 Mais c'est maintenant que les choses deviennent un peu ennuyeux parce que vous 744 00:34:04,815 --> 00:34:06,810 avoir à rembobiner mentalement où ai-je m'arrête. 745 00:34:06,810 --> 00:34:09,893 Je viens fusionné les moitiés triées, qui signifie que je suis là où dans mon algorithme? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Je dois trier la moitié droite, non? 748 00:34:13,770 --> 00:34:15,910 >> Si vous rembobinez, littéralement sur la vidéo, vous aurez 749 00:34:15,910 --> 00:34:18,339 voyons que nous sommes arrivés à ce point de Luke et Darren 750 00:34:18,339 --> 00:34:21,370 en triant la gauche la moitié de la moitié gauche. 751 00:34:21,370 --> 00:34:23,430 Ensuite, nous avons fusionné les moitiés triées, qui 752 00:34:23,430 --> 00:34:27,941 signifie la prochaine étape est en quelque sorte le la moitié droite de la moitié gauche. 753 00:34:27,941 --> 00:34:29,649 Très bien, nous allons donc le faire plus rapidement. 754 00:34:29,649 --> 00:34:33,282 Très bien, six, je vais la revendication vous êtes maintenant triées, allez de l'avant. 755 00:34:33,282 --> 00:34:33,990 Quel est votre nom? 756 00:34:33,990 --> 00:34:34,589 >> PUBLIC: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> ENCEINTE: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano est maintenant triée. 759 00:34:36,010 --> 00:34:36,450 Et quel est votre nom? 760 00:34:36,450 --> 00:34:37,080 >> PUBLIC: Alex. 761 00:34:37,080 --> 00:34:38,379 >> ENCEINTE: Alex est maintenant triée. 762 00:34:38,379 --> 00:34:40,750 La moitié gauche, moitié droite, ce qui est la dernière étape? 763 00:34:40,750 --> 00:34:41,250 Fusionner. 764 00:34:41,250 --> 00:34:44,310 Assez trivial, donc je suis s'apprêtent à fusionner en six, 765 00:34:44,310 --> 00:34:46,930 prendre un peu de recul, huit, prendre un peu de recul. 766 00:34:46,930 --> 00:34:49,530 Et maintenant, remarquez ce n'est un plat à emporter utile, ce 767 00:34:49,530 --> 00:34:53,930 est maintenant vrai sur la moitié gauche de l' liste, indépendamment de la façon dont nous avons commencé? 768 00:34:53,930 --> 00:34:55,090 Il est triée. 769 00:34:55,090 --> 00:34:57,750 >> Maintenant, il n'est pas triée dans le grand schéma des choses, 770 00:34:57,750 --> 00:35:00,250 mais il est trié indépendamment de l'autre moitié. 771 00:35:00,250 --> 00:35:04,100 Maintenant, ce que je suis pas sur si je continue rembobinage comment l'histoire a commencé? 772 00:35:04,100 --> 00:35:05,680 Maintenant, je dois trier la moitié droite. 773 00:35:05,680 --> 00:35:07,630 Alors maintenant, nous sommes le chemin du retour à le début de l'histoire, 774 00:35:07,630 --> 00:35:08,921 et nous allons le faire plus rapidement. 775 00:35:08,921 --> 00:35:11,320 Donc, je vais trier la moitié droite de l'ensemble de la liste. 776 00:35:11,320 --> 00:35:13,060 Quelle est la prochaine étape? 777 00:35:13,060 --> 00:35:15,840 Trier la moitié gauche de la moitié droite. 778 00:35:15,840 --> 00:35:18,715 Trier la moitié gauche de la la moitié gauche de la moitié droite. 779 00:35:18,715 --> 00:35:19,590 Et quel est votre nom? 780 00:35:19,590 --> 00:35:20,230 >> PUBLIC: Omar. 781 00:35:20,230 --> 00:35:21,970 >> ENCEINTE: Omar, pas en avant, c'est fait. 782 00:35:21,970 --> 00:35:22,860 La moitié gauche est triée. 783 00:35:22,860 --> 00:35:23,330 Et quel est votre nom? 784 00:35:23,330 --> 00:35:23,820 >> PUBLIC: Chris. 785 00:35:23,820 --> 00:35:25,620 >> Conférencier: Chris, faire un pas avant, vous êtes maintenant triées. 786 00:35:25,620 --> 00:35:27,010 Quelle est l'étape clé maintenant? 787 00:35:27,010 --> 00:35:27,510 Fusionner. 788 00:35:27,510 --> 00:35:30,509 Donc, on va fusionner en place ici, si vous pouviez prendre un peu de recul, 789 00:35:30,509 --> 00:35:32,930 et trois va prendre du recul, de fusionner. 790 00:35:32,930 --> 00:35:38,080 Donc, la moitié gauche de l' la moitié droite, est maintenant triée. 791 00:35:38,080 --> 00:35:41,747 Franchement, cet algorithme se sent comme nous gaspillent beaucoup plus de temps qu'avant, 792 00:35:41,747 --> 00:35:44,830 mais si nous l'avons fait en temps réel, nous allons voir ce que les plats à emporter vont être. 793 00:35:44,830 --> 00:35:47,970 Maintenant je suis ici, à droite la moitié de la moitié droite, 794 00:35:47,970 --> 00:35:50,170 laissez-moi aller de l'avant et trier la moitié gauche. 795 00:35:50,170 --> 00:35:51,482 Avancez, quel est votre nom? 796 00:35:51,482 --> 00:35:52,190 PUBLIC: Ramsey. 797 00:35:52,190 --> 00:35:53,210 ENCEINTE: Ramsey est maintenant triée. 798 00:35:53,210 --> 00:35:53,570 Quel est votre nom? 799 00:35:53,570 --> 00:35:54,200 >> PUBLIC: Marina. 800 00:35:54,200 --> 00:35:57,033 >> ENCEINTE: Marina est maintenant triée comme bien, si vous prenez un pas en avant. 801 00:35:57,033 --> 00:36:00,690 Étape clé ici est maintenant fusionner, je suis va arracher de mes deux listes, 802 00:36:00,690 --> 00:36:01,720 gauche et à droite. 803 00:36:01,720 --> 00:36:05,150 Cinq va venir en premier, et sept va venir après. 804 00:36:05,150 --> 00:36:06,410 Et encore une fois, c'est délibéré. 805 00:36:06,410 --> 00:36:08,535 Le fait qu'ils prennent étapes avant et en arrière 806 00:36:08,535 --> 00:36:12,997 est censé représenter que nous ne pouvons pas faire cet algorithme en place aussi facilement 807 00:36:12,997 --> 00:36:15,830 comme tri à bulles, et la sélection sorte, et le tri par insertion où nous venons 808 00:36:15,830 --> 00:36:16,960 gardé échange personnes. 809 00:36:16,960 --> 00:36:19,940 J'ai littéralement besoin d'une sorte de papier brouillon dans lequel 810 00:36:19,940 --> 00:36:21,827 de mettre ces gens pendant que je fais la fusion, 811 00:36:21,827 --> 00:36:23,410 et alors je peux les remettre en place. 812 00:36:23,410 --> 00:36:27,260 Et c'est la clé parce que je suis en utilisant un nouvelle ressource, l'espace, pas juste le temps. 813 00:36:27,260 --> 00:36:28,270 >> OK, c'est incroyable. 814 00:36:28,270 --> 00:36:32,050 La moitié gauche est triée, la moitié droite est trié, maintenant que la fusion touche pas. 815 00:36:32,050 --> 00:36:33,450 Comment vais-je fusionner ce? 816 00:36:33,450 --> 00:36:35,470 Donc, si vous suivez mon main gauche et la main droite, 817 00:36:35,470 --> 00:36:38,930 Je vais montrer ma main gauche à la moitié gauche, ma main droite 818 00:36:38,930 --> 00:36:42,680 à la moitié droite, et maintenant je dois décider, étape par étape qui à fusionner dans. 819 00:36:42,680 --> 00:36:44,650 Qui vient évidemment en premier? 820 00:36:44,650 --> 00:36:45,150 Numéro un. 821 00:36:45,150 --> 00:36:47,327 Alors, venez par ici, voici notre bloc-notes. 822 00:36:47,327 --> 00:36:49,910 Alors maintenant numéro un, et un avis ce que je vais faire avec ma main droite, 823 00:36:49,910 --> 00:36:54,152 Je vais passer ma seule main droite enjamber au point numéro trois, 824 00:36:54,152 --> 00:36:55,860 et maintenant je dois faire la même décision. 825 00:36:55,860 --> 00:36:58,387 Et en fait se tenir droit dans avant de Luc ici si vous pouviez, 826 00:36:58,387 --> 00:36:59,720 parce que c'est notre bloc-notes. 827 00:36:59,720 --> 00:37:00,610 Alors, qui vient après? 828 00:37:00,610 --> 00:37:05,000 Nous avons Luke avec le numéro deux ou Chris avec le numéro trois. 829 00:37:05,000 --> 00:37:07,460 Évidemment Luke, nombre deux, si vous venez ici. 830 00:37:07,460 --> 00:37:11,270 >> Mais ma main gauche maintenant va être incrémenté pour pointer vers Darren, 831 00:37:11,270 --> 00:37:15,160 et voici la clé emporter avec la fusion, je vais continuer à faire ça, 832 00:37:15,160 --> 00:37:17,340 évidemment, si vous nature de suivre la logique. 833 00:37:17,340 --> 00:37:19,670 Mais mes mains ne sont jamais va revenir en arrière, 834 00:37:19,670 --> 00:37:23,861 ce qui signifie que je ne jamais passer à la gauche avec mon processus de fusion, 835 00:37:23,861 --> 00:37:26,360 et que ça va être la clé de notre analyse dans un instant. 836 00:37:26,360 --> 00:37:27,859 >> Alors maintenant, nous allons terminer ce rapidement. 837 00:37:27,859 --> 00:37:31,650 Donc trois vient ensuite, puis quatre vient ensuite, 838 00:37:31,650 --> 00:37:38,750 et maintenant cinq vient ensuite, puis six, et sept, et enfin huit. 839 00:37:38,750 --> 00:37:42,960 On se sent comme le plus lent algorithme encore, mais pas si l'on fait 840 00:37:42,960 --> 00:37:45,510 exécuter au même genre de la vitesse d'horloge, pour ainsi 841 00:37:45,510 --> 00:37:48,106 prendre la parole, avec le même cochant horloge comme avant. 842 00:37:48,106 --> 00:37:48,605 Pourquoi? 843 00:37:48,605 --> 00:37:51,100 Eh bien, Jetons un regarder le résultat final. 844 00:37:51,100 --> 00:37:56,990 >> Revenons ici, laissez-moi tirer vers le haut une démonstration visuelle 845 00:37:56,990 --> 00:37:59,030 de ce que nous venons de faire. 846 00:37:59,030 --> 00:38:06,110 Zoom avant ici, sur ce Cette page ici, en disant Firefox 847 00:38:06,110 --> 00:38:08,200 que nous voulons faire la queue dans cette boîte, nous allons 848 00:38:08,200 --> 00:38:11,260 dire tri à bulles, avec laquelle nous sommes maintenant bien connu, 849 00:38:11,260 --> 00:38:14,130 sélection sorte, qui est un autre assez simple un, 850 00:38:14,130 --> 00:38:18,250 et maintenant le tri par fusion d'aujourd'hui, qui sera notre fin à son apogée. 851 00:38:18,250 --> 00:38:21,530 La raison pour laquelle il a pris beaucoup plus de temps ici avec les humains et moi verbalement est, 852 00:38:21,530 --> 00:38:23,480 évidemment, je vous explique chaque étape. 853 00:38:23,480 --> 00:38:26,920 Mais si vous exécutez simplement ceci, beaucoup comme nous l'avons fait tri et de sélection bulle 854 00:38:26,920 --> 00:38:30,890 sorte non seulement visuellement, montre combien plus efficace 855 00:38:30,890 --> 00:38:33,330 ce levier de division et conquête 856 00:38:33,330 --> 00:38:39,150 peut être appliqué à un ensemble de données qui est même pas la taille de huit, mais même beaucoup, 857 00:38:39,150 --> 00:38:39,970 beaucoup plus grand. 858 00:38:39,970 --> 00:38:44,585 Je vous donne le tri par fusion, à côté de l' côté de ces autres algorithmes. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Cela va obtenir douloureux rapidement, et la fin 861 00:38:58,530 --> 00:39:00,890 n'est pas particulièrement à son apogée, ils finissent juste en haut triés. 862 00:39:00,890 --> 00:39:05,280 Mais l'essentiel est que emporter Regardez comment beaucoup plus rapidement le tri par fusion 863 00:39:05,280 --> 00:39:08,110 était, à moins que vous pensez que je suis juste un peu de jouer avec vous. 864 00:39:08,110 --> 00:39:13,100 Si nous faisons cela, une dernière fois, laissez de recharger ce, revenons 865 00:39:13,100 --> 00:39:14,960 et choisissez tri à bulles, et juste pour le plaisir, 866 00:39:14,960 --> 00:39:17,330 choisissons insertion sorte, pour faire bonne mesure. 867 00:39:17,330 --> 00:39:20,020 Et cette fois encore, nous allons choisir le tri par fusion et nous allons 868 00:39:20,020 --> 00:39:21,595 fait fonctionner ces côte à côte. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> Et ce n'est pas, en fait, un coup de chance. 871 00:39:26,930 --> 00:39:31,140 Ce que j'ai effectivement fait est que je n'ai divisé mon entrée dans la moitié, encore une fois, 872 00:39:31,140 --> 00:39:32,240 et encore, et encore. 873 00:39:32,240 --> 00:39:35,590 Et il ya seulement tant de fois que vous pouvez divisez votre entrée en deux moitiés, gauche 874 00:39:35,590 --> 00:39:36,240 et à droite. 875 00:39:36,240 --> 00:39:39,425 Quelle est la formule que nous continuons à voir qui décrit la division en deux 876 00:39:39,425 --> 00:39:41,050 encore, et encore, et encore, et encore? 877 00:39:41,050 --> 00:39:41,890 >> PUBLIC: Ouverture n. 878 00:39:41,890 --> 00:39:42,760 >> ENCEINTE: Ouverture n. 879 00:39:42,760 --> 00:39:46,300 Mais il ya une autre étape clé, cet algorithme n'est pas log n étapes. 880 00:39:46,300 --> 00:39:48,992 Si l'on ne log n étapes, nous serions dans le même problème 881 00:39:48,992 --> 00:39:51,200 comme avant où nous ne pouvons pas être que tout est trié. 882 00:39:51,200 --> 00:39:54,480 Vous devez regarder peu à n éléments pour être sûr que n éléments sont triés, 883 00:39:54,480 --> 00:39:55,950 sinon c'est un acte de foi. 884 00:39:55,950 --> 00:39:59,810 >> C'est donc peu log n étapes, mais Qu'en est-il de cette étape de fusion touche 885 00:39:59,810 --> 00:40:04,370 où j'ai fusionné ma moitié gauche et à droite moitié et traversa la scène? 886 00:40:04,370 --> 00:40:06,980 Combien d'étapes, c'est que de fusionner? 887 00:40:06,980 --> 00:40:10,150 C'est n, mais je n'ai pas juste fusionner la dernière fois. 888 00:40:10,150 --> 00:40:15,089 Sur chacun de ces appels imbriqués, sur chaque de ces fusions imbriqués, je n'ai toujours trié. 889 00:40:15,089 --> 00:40:18,380 J'ai fusionné ces deux gars, alors ces deux les gars, alors ces deux gars et ainsi de suite. 890 00:40:18,380 --> 00:40:19,955 >> Donc, je n'ai fusion, encore et encore. 891 00:40:19,955 --> 00:40:20,580 Combien de fois? 892 00:40:20,580 --> 00:40:23,510 Donc, chaque fois que je divise le liste dans la moitié, j'ai fait une fusion. 893 00:40:23,510 --> 00:40:25,460 Divisez la liste en deux, faire une fusion. 894 00:40:25,460 --> 00:40:28,570 Donc, si divisant la liste qui peut être fait log n fois, 895 00:40:28,570 --> 00:40:33,880 et la fusion prend finalement n étapes, ce qui pourrait être maintenant la partie supérieure 896 00:40:33,880 --> 00:40:37,000 lié à la gestion moment de notre algorithme? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> Et en effet, c'est ce que nous avons accompli ici. 899 00:40:40,560 --> 00:40:44,650 Donc la sensation que vous voyez visuellement quand ces trois choses fonctionnent côte à côte 900 00:40:44,650 --> 00:40:47,930 n est au carré en fonction de n carré contre n log n. 901 00:40:47,930 --> 00:40:51,010 Qui fondamentalement nous le verrons, non seulement aujourd'hui, mais à l'avenir, 902 00:40:51,010 --> 00:40:52,760 est beaucoup, beaucoup plus rapide. 903 00:40:52,760 --> 00:40:56,010 Une salve d'applaudissements pour ces gars-là, Je vais les récompenser avec des boules de stress. 904 00:40:56,010 --> 00:41:00,260 Disons ajourner ici aujourd'hui, et nous vous voir lundi. 905 00:41:00,260 --> 00:41:02,255