1 00:00:00,000 --> 00:00:11,100 >> [Jouer de la musique] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. Malan: Très bien. 3 00:00:11,490 --> 00:00:12,170 Alors, bienvenue en arrière. 4 00:00:12,170 --> 00:00:15,180 C'est CS50, et l'est la fin de la troisième semaine. 5 00:00:15,180 --> 00:00:17,770 >> Donc, rappeler au cours des dernières semaines, nous avons consacré un peu de 6 00:00:17,770 --> 00:00:20,820 fois sur C, la programmation, la syntaxe. 7 00:00:20,820 --> 00:00:24,680 Et c'est tout à fait normal, si vous êtes encore aux prises avec des problèmes Set 2, pour être 8 00:00:24,680 --> 00:00:25,950 cogner la tête contre le mur. 9 00:00:25,950 --> 00:00:28,310 C'est messages d'erreur cryptique prospectifs et les bugs que vous 10 00:00:28,310 --> 00:00:29,220 ne peut pas tout à fait pourchasser. 11 00:00:29,220 --> 00:00:32,310 Parce que, rassurez-vous, qui en seulement une le temps de quelques semaines, vous allez regarder en arrière sur 12 00:00:32,310 --> 00:00:35,930 des choses comme César, et [? V-Genair,?] peut-être même se fissurer, et 13 00:00:35,930 --> 00:00:40,050 réalisez à quel point vous êtes dans une courte période de temps. 14 00:00:40,050 --> 00:00:43,670 Donc, si c'est une consolation, accrochez-vous pour l'instant. 15 00:00:43,670 --> 00:00:46,610 >> Aujourd'hui, cependant, nous commençons à transition à des choses plus haut niveau. 16 00:00:46,610 --> 00:00:49,820 Et nous commençons à prendre pour acquis que vous les gars savent comment programmer, ou à 17 00:00:49,820 --> 00:00:52,090 moins les débuts de que le niveau de confort. 18 00:00:52,090 --> 00:00:56,520 Et nous allons commencer à examiner comment nous pouvons aller sur la conception de programmes plus 19 00:00:56,520 --> 00:00:57,440 efficacement. 20 00:00:57,440 --> 00:01:01,090 Comment pouvons-nous aller sur l'optimisation de la efficacité de nos algorithmes, et 21 00:01:01,090 --> 00:01:03,110 généralement résoudre plus problèmes intéressants. 22 00:01:03,110 --> 00:01:06,850 Et à partir de tenir pour acquis que, si nous le voulions, nous pourrions coder tout 23 00:01:06,850 --> 00:01:08,350 des exemples que nous avons à l'esprit. 24 00:01:08,350 --> 00:01:11,430 Donc, aujourd'hui, nous ne touchons pas le clavier pour toute forme de code. 25 00:01:11,430 --> 00:01:15,150 Ça va être beaucoup plus élevé, et en fin de compte, sur la résolution de problèmes. 26 00:01:15,150 --> 00:01:20,490 >> Donc, pour arriver à ce point, permettez-moi de proposer que les sept suivants 27 00:01:20,490 --> 00:01:24,290 rectangles représentent sept portes, derrière qui sont tout un tas d' 28 00:01:24,290 --> 00:01:26,340 numéros, parmi lesquels se trouve le numéro 50. 29 00:01:26,340 --> 00:01:30,470 Permettez-moi de projeter cette sur cette écran ici. 30 00:01:30,470 --> 00:01:36,770 Et de proposer que nous avons besoin d'un volontaire pour m'aider à trouver un numéro devant 31 00:01:36,770 --> 00:01:38,140 Internet ici pour voir. 32 00:01:38,140 --> 00:01:40,755 Venez sur place, dans le rose. 33 00:01:40,755 --> 00:01:43,050 Très bien. 34 00:01:43,050 --> 00:01:43,930 Quel est votre nom? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [Inaudible] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. Malan: Pardon? 37 00:01:45,170 --> 00:01:45,860 >> JENNIFER: Jennifer. 38 00:01:45,860 --> 00:01:46,390 >> DAVID J. Malan: Jennifer. 39 00:01:46,390 --> 00:01:46,980 Tout droit, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Enchanté de faire votre connaissance. 41 00:01:47,630 --> 00:01:48,370 Venez sur place. 42 00:01:48,370 --> 00:01:52,430 Il s'agit donc voici sept portes, et ce J'aimerais que vous fassiez pour nous ici, 43 00:01:52,430 --> 00:01:56,560 en face de l'ensemble de vos camarades de classe, est nous trouver le numéro 50. 44 00:01:56,560 --> 00:02:00,860 Pour trouver un numéro, vous pouvez coup d'oeil derrière l'une de ces portes en tapant simplement 45 00:02:00,860 --> 00:02:03,030 sur l'une des portes, et va révéler son numéro. 46 00:02:03,030 --> 00:02:06,080 Et nous allons voir à quelle vitesse vous peut nous trouver le numéro, 50. 47 00:02:06,080 --> 00:02:09,979 48 00:02:09,979 --> 00:02:11,229 >> 15. 49 00:02:11,229 --> 00:02:13,110 50 00:02:13,110 --> 00:02:14,360 16. 51 00:02:14,360 --> 00:02:16,270 52 00:02:16,270 --> 00:02:16,530 50. 53 00:02:16,530 --> 00:02:17,350 Bien fait. 54 00:02:17,350 --> 00:02:18,040 Très bien. 55 00:02:18,040 --> 00:02:19,906 Salve d'applaudissements pour Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [Applaudissements] 57 00:02:21,530 --> 00:02:22,320 >> Très bien. 58 00:02:22,320 --> 00:02:25,254 Alors quelle est votre stratégie pour trouver le nombre, 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Euh, je pensais que peut-être si - 60 00:02:27,222 --> 00:02:27,714 [Inaudible] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. Malan: Oh. 62 00:02:28,206 --> 00:02:29,630 Donnez-lui une seconde. 63 00:02:29,630 --> 00:02:32,420 Ainsi était votre stratégie pour trouver le nombre, 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: Je viens de commencer à l' commence à voir le premier numéro 65 00:02:34,760 --> 00:02:38,590 j'étais, et puis j'ai pensé, peut-être si ils sont triés, je vais continuer 66 00:02:38,590 --> 00:02:39,970 tapant plus haut? 67 00:02:39,970 --> 00:02:40,140 >> DAVID J. Malan: OK. 68 00:02:40,140 --> 00:02:42,910 Et nous semblons avoir trouvé que ce soit le cas. 69 00:02:42,910 --> 00:02:45,670 Bien, nous allons peler les couches juste un peu, et vous voulez aller 70 00:02:45,670 --> 00:02:47,640 avant et révéler les autres portes vous auriez pu choisir? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: Oh, ma chérie. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. Malan: Ah. 74 00:02:53,128 --> 00:02:54,280 >> JENNIFER: Je viens donc eu de la chance. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. Malan: Donc, vous avez de la chance. 76 00:02:55,270 --> 00:02:55,710 Très bien. 77 00:02:55,710 --> 00:02:56,795 Donc pas mal. 78 00:02:56,795 --> 00:02:58,750 Mais c'est une question intéressante aperçu, non? 79 00:02:58,750 --> 00:03:01,870 Si vous avez pris, et que vous avez reçu, En effet, un peu de chance là-bas. 80 00:03:01,870 --> 00:03:05,350 Mais si vous supposiez que les chiffres étaient triée, pouvez-vous être plus précis 81 00:03:05,350 --> 00:03:08,750 la manière dont cette influence votre comportement? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Donc, si ils ont été triés, je pensait peut-être plus petit au plus grand. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. Malan: OK. 84 00:03:11,970 --> 00:03:15,260 >> JENNIFER: Ou si cela a fini par être vraiment grand, alors le plus grand au plus petit. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. Malan: OK. 86 00:03:15,540 --> 00:03:18,170 Donc, du plus grand au plus petit, ou plus petit au plus grand. 87 00:03:18,170 --> 00:03:21,990 Mais permettez-moi de proposer, supposons que vous deviez eu de chance, et supposer qu'ils 88 00:03:21,990 --> 00:03:26,840 n'ont pas été, en fait, triées, combien d' ces portes pourraient vous ont dû peek 89 00:03:26,840 --> 00:03:28,590 derrière dans ce pire des cas? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Tous. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. Malan: Tous. 92 00:03:30,420 --> 00:03:31,740 Donc, nous allons généraliser que n. 93 00:03:31,740 --> 00:03:34,790 Il se trouve être 7, mais nous allons plus dire généralement qu'il ya n portes sur le 94 00:03:34,790 --> 00:03:35,650 écran ici. 95 00:03:35,650 --> 00:03:40,110 Ainsi, dans le pire des cas, vous auriez regarder derrière 7 portes ou n portes. 96 00:03:40,110 --> 00:03:44,140 Et donc c'est vraiment, c'est un peu de chance aujourd'hui, mais c'est vraiment un linéaire 97 00:03:44,140 --> 00:03:46,440 algorithme de toutes sortes, même si vous ont eu la gentillesse de sauter autour. 98 00:03:46,440 --> 00:03:47,080 Est-ce juste? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Ouais. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. Malan: Eh bien, laissez-moi voir si votre changements de stratégie si je nous déplacer 101 00:03:50,000 --> 00:03:52,190 notre deuxième exemple ici avec 7 portes différentes. 102 00:03:52,190 --> 00:03:55,240 Mêmes chiffres, mais cette moment où ils sont triés. 103 00:03:55,240 --> 00:03:58,350 Quelle est votre stratégie ici va être, essayer de mettre hors de votre esprit ce que 104 00:03:58,350 --> 00:03:59,310 les autres numéros ont été - 105 00:03:59,310 --> 00:03:59,930 >> JENNIFER: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. Malan: - plus tôt? 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Commençons avec la première. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. Malan: Très bien. 109 00:04:03,540 --> 00:04:05,190 Commencez avec la première. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 Maintenant, où allez-vous aller, et pourquoi? 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4 est vraiment petit. 113 00:04:10,040 --> 00:04:12,500 Donc, si ils sont en quelque sorte peut-être plus petit au plus grand, il devrait 114 00:04:12,500 --> 00:04:13,290 être le double, et -. 115 00:04:13,290 --> 00:04:13,670 >> DAVID J. Malan: OK. 116 00:04:13,670 --> 00:04:15,990 Voyons, que vous en pensez? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Essayez la dernière. 118 00:04:19,050 --> 00:04:19,500 Nice. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. Malan: Très bien fait. 120 00:04:20,880 --> 00:04:21,860 Très bien. 121 00:04:21,860 --> 00:04:23,010 >> [Applaudissements] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. Malan: OK. 123 00:04:24,310 --> 00:04:26,790 Donc, vous êtes en train de faire cette horriblement, parce que vous êtes 124 00:04:26,790 --> 00:04:27,700 le faire très bien. 125 00:04:27,700 --> 00:04:31,150 Qui nous laisse incapable de faire certains points. 126 00:04:31,150 --> 00:04:32,565 Donc, nous allons essayer de revenir ici. 127 00:04:32,565 --> 00:04:34,560 >> JENNIFER: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. Malan: Très bien fait, néanmoins. 129 00:04:35,980 --> 00:04:39,060 Vous avez donc commencé dès le début, vous avez vu que c'était 4, puis vous 130 00:04:39,060 --> 00:04:40,240 déplacé à la fin. 131 00:04:40,240 --> 00:04:42,320 Mais supposons que vous n'avez pas eu la chance là-bas, et supposons 50 132 00:04:42,320 --> 00:04:42,890 était ailleurs. 133 00:04:42,890 --> 00:04:46,190 Que votre troisième étape aurait été? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Retour au début. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. Malan: Retour au début. 136 00:04:48,320 --> 00:04:51,320 OK, donc vous avez touché cette porte, qui était de 8. 137 00:04:51,320 --> 00:04:51,660 Très bien. 138 00:04:51,660 --> 00:04:52,650 Donc, ce n'est pas 50. 139 00:04:52,650 --> 00:04:55,380 Où aimeriez-vous avoir regardé prochaine? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: Si je n'ai pas savent qu'ils triés. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. Malan: C'est exact. 142 00:04:57,005 --> 00:04:58,490 Eh bien, si vous ne saviez ils ont été triés - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Oh, je ne savais, oui. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. Malan: - Mais vous n'avez pas savoir où 50 était encore? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Juste continuer. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. Malan: Très bien. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Continuez. 149 00:05:03,800 --> 00:05:05,270 OK, je peux travailler avec. 150 00:05:05,270 --> 00:05:05,610 >> JENNIFER: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. Malan: Maintenant, si vous êtes juste va continuer, quel est votre 152 00:05:07,210 --> 00:05:09,680 algorithme dévolues soutenu dans. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: Le linéaire -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. Malan: C'est un peu linéaire. 155 00:05:11,820 --> 00:05:13,480 Mais permettez-moi de proposer, laissez- me mis sur la sellette. 156 00:05:13,480 --> 00:05:14,900 Permettez-moi de vous rafraîchir la page. 157 00:05:14,900 --> 00:05:17,120 même nombre, même arrangement, mêmes portes. 158 00:05:17,120 --> 00:05:21,350 Mais repense à cette première journée classe quand nous avons déchiré un annuaire téléphonique dans 159 00:05:21,350 --> 00:05:25,480 la moitié, en quelque sorte, et ce qui était notre stratégie là-bas? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Commencez par le milieu. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. Malan: OK. 162 00:05:26,690 --> 00:05:27,610 Donc, commencer au milieu. 163 00:05:27,610 --> 00:05:28,790 Allons donc de l'avant et de simuler cela. 164 00:05:28,790 --> 00:05:30,720 Commencez par le milieu par révéler cette porte. 165 00:05:30,720 --> 00:05:31,660 Ainsi, le nombre 16. 166 00:05:31,660 --> 00:05:35,290 Alors, qu'est-ce que le gars fort dû le faire, qui a déchiré le livre de téléphone de moitié, 167 00:05:35,290 --> 00:05:38,450 pour se rendre à la prochaine idée? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Va avec cette moitié. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. Malan: Et pourquoi à droite? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: S'ils étaient en quelque sorte de plus petit au plus grand, puis 50 devrait être 171 00:05:43,900 --> 00:05:44,720 à cette fin. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. Malan: Bon. 173 00:05:44,920 --> 00:05:45,390 Tout à fait raisonnable. 174 00:05:45,390 --> 00:05:48,380 Donc, comme un annuaire téléphonique, vous allez à l' droit, par opposition à la gauche, mais ici 175 00:05:48,380 --> 00:05:49,500 est la clé emporter. 176 00:05:49,500 --> 00:05:53,930 Vous pouvez maintenant jeter ou déchirer, la moitié de ce problème, vous laissant pas 177 00:05:53,930 --> 00:05:55,970 avec 7 portes, mais vraiment avec seulement 3. 178 00:05:55,970 --> 00:05:57,870 Qui est à peu près la moitié de la ampleur du problème. 179 00:05:57,870 --> 00:05:58,350 Très bien. 180 00:05:58,350 --> 00:06:01,890 Alors maintenant, ce que vous auriez fait après que vous allez bien? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: Donc 16 est encore assez faible, par rapport à 50, alors peut-être que je vais essayer, 182 00:06:05,870 --> 00:06:06,700 comme, celui-ci. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. Malan: Très bien. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Très bien, alors maintenant quel est votre instinct vous dit? 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: Je peux jeter ce et puis juste - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. Malan: OK. 188 00:06:12,360 --> 00:06:14,212 Bon, vous pouvez jeter la moitié gauche là. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - choisir celui-ci. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. Malan: Et la droite. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Ouais. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. Malan: Donc, même si c'est dur à voir peut-être, quand il ya seulement 193 00:06:17,820 --> 00:06:21,320 7 portes, pensent, maintenant, la cohérence de l' 194 00:06:21,320 --> 00:06:22,620 algorithme que vous venez d'appliquer. 195 00:06:22,620 --> 00:06:24,510 Dans le cas précédent, vous avez fait avoir de la chance, ce qui était super. 196 00:06:24,510 --> 00:06:26,540 Mais vous avez utilisé une heuristique, Je dirais. 197 00:06:26,540 --> 00:06:29,150 Vous avez utilisé sorte de vos instincts, et sachant qu'elle soit triée, si c'est assez 198 00:06:29,150 --> 00:06:31,600 petite au début, évidemment, nous avons obtenu d'aller plus vers la droite. 199 00:06:31,600 --> 00:06:34,990 Mais dans un certain sens, vous avez de la chance, parce que c'était peut-être le numéro 100, 200 00:06:34,990 --> 00:06:36,220 et peut-être 50 était plus dans le milieu. 201 00:06:36,220 --> 00:06:37,910 Peut-être 50 était encore ici. 202 00:06:37,910 --> 00:06:40,960 >> Mais qu'est-ce que vous avez fait un peu différemment cette époque, vous avez fait la même chose 203 00:06:40,960 --> 00:06:42,150 encore et encore. 204 00:06:42,150 --> 00:06:45,310 Et je dirais que ce que vous venez n'a, bien influencé par le téléphone 205 00:06:45,310 --> 00:06:48,100 exemple livre, est quelque chose de beaucoup plus algorithmique, et beaucoup 206 00:06:48,100 --> 00:06:49,930 moins spécial tubé. 207 00:06:49,930 --> 00:06:51,620 Beaucoup moins instinctive. 208 00:06:51,620 --> 00:06:57,160 Donc à la fin de la journée, comment vous décrivez l'efficacité de l' 209 00:06:57,160 --> 00:07:00,530 premier algorithme, où vous êtes allé de gauche à droite, par rapport à la 210 00:07:00,530 --> 00:07:03,430 second algorithme ici? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: celui-ci devrait, comme, peut-être réduire de moitié le temps, voire plus, oui. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. Malan: OK, peut-être même plus. 213 00:07:07,320 --> 00:07:10,150 Poussons un peu plus à ce sujet. 214 00:07:10,150 --> 00:07:13,030 Ce qui, si nous continuons cette logique, nous avons certainement réduit de moitié le 215 00:07:13,030 --> 00:07:15,830 temps de fonctionnement de ce second algorithme en jetant la moitié de la 216 00:07:15,830 --> 00:07:18,470 chiffres, mais qu'avons-nous fait à la prochaine itération, lorsque Jennifer a révélé 217 00:07:18,470 --> 00:07:20,615 le deuxième nombre? 218 00:07:20,615 --> 00:07:22,830 >> Nous nouveau divisé par deux le nombre de portes. 219 00:07:22,830 --> 00:07:25,270 Et puis, qu'avons-nous fait après cela, si il y avait plus de portes pour jouer avec? 220 00:07:25,270 --> 00:07:27,520 Nous souhaitons réduire de moitié, et encore, et encore, et encore. 221 00:07:27,520 --> 00:07:30,420 Et ce n'était que comme vous les gars tout debout à la première semaine de 222 00:07:30,420 --> 00:07:33,000 classe, la moitié d'entre vous assis, à moitié de vous asseoir, la moitié d'entre vous 223 00:07:33,000 --> 00:07:35,440 assis, jusqu'à ce qu'un seul âme était debout. 224 00:07:35,440 --> 00:07:39,050 Et nous avons dit que le temps d'exécution de que le nombre d'étapes qu'il a fallu était 225 00:07:39,050 --> 00:07:40,430 de l'ordre de quoi? 226 00:07:40,430 --> 00:07:41,230 >> INTERLOCUTEUR 1: [inaudible] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. Malan: Donc log base 2 de n, ou tout simplement plus simple, connectez-vous sur n. 228 00:07:43,970 --> 00:07:45,060 Donc, quelque chose logarithmique. 229 00:07:45,060 --> 00:07:48,380 Et le graphique n'est pas une ligne droite qui vient juste de pire en pire, c'était 230 00:07:48,380 --> 00:07:52,490 Cette courbe intéressante qui n'a pas devenir si mauvais temps. 231 00:07:52,490 --> 00:07:53,910 Donc, nous allons tenir à cette idée. 232 00:07:53,910 --> 00:07:54,690 Remercions Jennifer. 233 00:07:54,690 --> 00:07:56,150 Merci beaucoup d'être venu sur place. 234 00:07:56,150 --> 00:07:57,400 Et une seconde. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Pas de lampes de bureau aujourd'hui, mais nous n'avez CS50 balles anti-stress. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Yay. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. Malan: Très bien, ici. 239 00:08:04,410 --> 00:08:06,545 Merci pour encourir la contrainte ici. 240 00:08:06,545 --> 00:08:07,350 Très bien. 241 00:08:07,350 --> 00:08:10,620 Donc, nous allons voir si nous ne pouvons pas maintenant formaliser cela un peu plus. 242 00:08:10,620 --> 00:08:14,820 Encore une fois, ce que nous venons de faire est essentiellement la même chose que nous avons fait 243 00:08:14,820 --> 00:08:16,660 en ce que la première semaine. 244 00:08:16,660 --> 00:08:23,780 Mais plutôt que de fin avec juste un linéaire algorithme, qui nous dépeint 245 00:08:23,780 --> 00:08:27,210 précédemment que cette ligne droite, de sorte que, si nous mettons une plus porte sur 246 00:08:27,210 --> 00:08:29,610 l'écran, puis Jennifer serait ont dû chercher, potentiellement, 247 00:08:29,610 --> 00:08:30,600 derrière une porte plus. 248 00:08:30,600 --> 00:08:33,490 Si nous mettons deux portes, elle pourrait avoir regarder derrière deux portes. 249 00:08:33,490 --> 00:08:35,990 >> Et donc, il y avait cette linéaire la relation entre la taille de l' 250 00:08:35,990 --> 00:08:39,059 le problème, par exemple, l'axe des x, et la quantité de temps nécessaire pour 251 00:08:39,059 --> 00:08:40,440 résoudre le y. 252 00:08:40,440 --> 00:08:43,330 Mais l'image que je faisais allusion à était au début de cette ligne verte. 253 00:08:43,330 --> 00:08:45,970 Vert délibérément, parce que il me sentais mieux. 254 00:08:45,970 --> 00:08:49,790 En théorie, l'algorithme, lorsque nous l'avons fait avec l'annuaire téléphonique, lorsque nous l'avons fait 255 00:08:49,790 --> 00:08:52,420 avec vous les gars compter les uns les autres, et dans le second cas, lorsque Jennifer juste 256 00:08:52,420 --> 00:08:55,250 at-il ici, c'était en quelque sorte de fondamentalement mieux. 257 00:08:55,250 --> 00:08:57,180 Parce que ce n'était pas simplement deux fois plus vite. 258 00:08:57,180 --> 00:08:58,870 Ce n'était même pas quatre fois plus rapide. 259 00:08:58,870 --> 00:09:03,290 Il était tout dépend de ce que l' taille de l'entrée était, quant au nombre de 260 00:09:03,290 --> 00:09:05,220 mesures qu'il a finalement pris. 261 00:09:05,220 --> 00:09:08,040 >> Et si cette idée simple que nous avons tous pris pour acquis avec l'annuaire téléphonique, 262 00:09:08,040 --> 00:09:10,200 peut même être appliquée à quelque chose comme ça. 263 00:09:10,200 --> 00:09:12,380 Et cela pourrait être plus décontractée connu sous le nom, comme vous pouvez 264 00:09:12,380 --> 00:09:13,940 imaginer, diviser pour régner. 265 00:09:13,940 --> 00:09:16,390 Non contrairement à ce qu'on a fait, bien sûr, avec l'annuaire. 266 00:09:16,390 --> 00:09:18,300 >> Mais le pseudo, le rappel était présent. 267 00:09:18,300 --> 00:09:21,800 Donc, nous ne le ferons pas nouveau, mais rappelle cette première semaine, nous avons tous se levèrent 268 00:09:21,800 --> 00:09:25,140 puis la moitié d'entre vous assis, la moitié des vous vous êtes assis, la moitié d'entre vous assis. 269 00:09:25,140 --> 00:09:29,280 Cet algorithme a été mis en œuvre dans un peu d'une façon de tricher, en ce sens, il 270 00:09:29,280 --> 00:09:32,870 n'était pas seulement l'un des me compter, fondamentalement, de manière plus efficace. 271 00:09:32,870 --> 00:09:35,830 Dans ce cas, je me tirant parti une ressource secondaire. 272 00:09:35,830 --> 00:09:39,470 En quelque sorte, plusieurs processeurs, plusieurs cerveaux, plusieurs gens intelligents dans l' 273 00:09:39,470 --> 00:09:42,740 chambre aidaient-moi de quelque chose linéaire à quelque chose 274 00:09:42,740 --> 00:09:45,190 logarithmique, à partir de quelque chose rouge à quelque chose de vert. 275 00:09:45,190 --> 00:09:48,650 >> Mais dans ce cas, Jennifer seul peut améliorer fondamentalement sur l' 276 00:09:48,650 --> 00:09:52,370 les performances de son premier algorithme par, encore une fois, juste à y penser un peu plus difficile. 277 00:09:52,370 --> 00:09:56,650 Et maintenant, quand vient le temps de mettre en œuvre ces choses, calculer 278 00:09:56,650 --> 00:10:00,670 quelles lignes de code que vous pouvez écrire comme que vous pouvez répéter à nouveau, et 279 00:10:00,670 --> 00:10:03,350 encore, et encore, une sorte de dans un mode en boucle. 280 00:10:03,350 --> 00:10:06,370 Parce que vous n'allez pas avoir le luxe, comme Jennifer a fait au début, à 281 00:10:06,370 --> 00:10:10,460 tout simplement avoir tout un tas d'ifs et de dire, hmm, si ce premier numéro est 4, 282 00:10:10,460 --> 00:10:11,800 Permettez-moi de sauter tout le chemin jusqu'à la fin. 283 00:10:11,800 --> 00:10:14,180 Oh, si ce nombre est trop grand, Passons arbitrairement retour 284 00:10:14,180 --> 00:10:15,220 au second élément. 285 00:10:15,220 --> 00:10:18,210 Vous verrez que ça va être beaucoup difficile à formaliser ce que nous, les humains 286 00:10:18,210 --> 00:10:21,270 tenir pour acquis que très raisonnable heuristiques, mais un ordinateur est seulement 287 00:10:21,270 --> 00:10:23,260 vais faire ce que vous lui demandez de faire. 288 00:10:23,260 --> 00:10:25,280 >> Maintenant, cela a très intéressant implications. 289 00:10:25,280 --> 00:10:29,950 Ce graphique est une sorte de destinée à trier des submerger visuellement, mais demeure, où 290 00:10:29,950 --> 00:10:32,230 est la droite de ce graphique? 291 00:10:32,230 --> 00:10:35,330 Où est le graphe linéaire que nous appelons n? 292 00:10:35,330 --> 00:10:37,580 Eh bien, c'est un peu vers le bas de cette image, non? 293 00:10:37,580 --> 00:10:40,500 Donc, tout ce que nous avons fait c'est que nous avons sorte de zoom arrière à l'axe des x et l' 294 00:10:40,500 --> 00:10:44,780 axe des ordonnées pour tenter de se faire une idée de ce que d'autres types de courbes ressemblent. 295 00:10:44,780 --> 00:10:47,760 >> Et les spécificités de la mathématique expressions d'aujourd'hui ne sera pas question de manière 296 00:10:47,760 --> 00:10:52,440 beaucoup, mais remarquez qu'il ya beaucoup de algorithmes qui sont bien pires que 297 00:10:52,440 --> 00:10:53,470 quelque chose qui est linéaire. 298 00:10:53,470 --> 00:10:55,410 En effet, n cubes semble assez mauvais. 299 00:10:55,410 --> 00:10:58,400 2 au n semble assez mauvais. n carré semble assez mauvais. 300 00:10:58,400 --> 00:11:01,630 Et nous verrons ce que certains d'entre eux pourrait être en réalité aujourd'hui. 301 00:11:01,630 --> 00:11:05,430 Et log n ne se sent pas aussi mauvais, mais mieux que n est log base 2 de n. 302 00:11:05,430 --> 00:11:08,080 Mais vous savez, il aurait été encore Plus étonnant si Jennifer, ou si nous, 303 00:11:08,080 --> 00:11:12,910 cette première semaine, était venu avec quelque chose qui n'est journal de journal de n. 304 00:11:12,910 --> 00:11:15,880 >> Donc, en d'autres termes, il ya toute cette éventail de solutions possibles à 305 00:11:15,880 --> 00:11:18,570 problèmes, mais même ici, un avis ce qui va se passer. 306 00:11:18,570 --> 00:11:22,910 Quand je effectuer un zoom arrière, laquelle de ces courbes qui va se révéler être l'absolu 307 00:11:22,910 --> 00:11:26,630 pire de celles sur l'écran maintenant? 308 00:11:26,630 --> 00:11:28,680 Alors n cubes semble assez mauvais pour le moment. 309 00:11:28,680 --> 00:11:32,470 Mais si l'on zoom arrière et voir plus de la x et l'axe des y, qui va 310 00:11:32,470 --> 00:11:34,550 dominer finalement? 311 00:11:34,550 --> 00:11:37,120 Ainsi, il s'avère en fait que 2 à l' n, et vous pouvez comprendre cela juste par 312 00:11:37,120 --> 00:11:39,990 branchant un plus grand chiffres, et vous verrez que 2 à l' 313 00:11:39,990 --> 00:11:42,070 n effet, s'agrandit beaucoup plus vite. 314 00:11:42,070 --> 00:11:45,530 Si nous voulons vraiment effectuer un zoom arrière, un 2 à la algorithme n aspire absolument. 315 00:11:45,530 --> 00:11:48,170 Je veux dire que cela va prendre un peu de temps pour la 316 00:11:48,170 --> 00:11:49,460 ordinateur à travers le taux de désabonnement. 317 00:11:49,460 --> 00:11:52,500 >> Mais vous verrez au fil du temps, en particulier avec les futures séries de problèmes et même 318 00:11:52,500 --> 00:11:55,600 derniers projets, vos données sont ensemble devient grand, d'accord? 319 00:11:55,600 --> 00:11:58,300 Même dans la première version de Facebook, comme le nombre d'amis, et l' 320 00:11:58,300 --> 00:12:01,840 nombre d'utilisateurs enregistrés a large, vous pouvez trier de téléphone à l'intérieur et 321 00:12:01,840 --> 00:12:05,530 mettre en œuvre quelque chose avec recherche linéaire, ou un simple tri 322 00:12:05,530 --> 00:12:07,030 algorithme, comme nous le verrons aujourd'hui. 323 00:12:07,030 --> 00:12:09,280 Vous devez commencer à penser plus difficile et plus difficile à propos de ces problèmes. 324 00:12:09,280 --> 00:12:12,070 Et les types de lieux de problèmes tels que Facebook et Google et Microsoft, 325 00:12:12,070 --> 00:12:16,350 et d'autres travaillent sur sont précisément ces sorte de Big Data genre de questions 326 00:12:16,350 --> 00:12:18,530 de plus en plus ces jours-ci. 327 00:12:18,530 --> 00:12:18,900 >> Très bien. 328 00:12:18,900 --> 00:12:23,800 Donc, le succès de Jennifer dans ce second algorithme, franchement, elle n'a étonnamment 329 00:12:23,800 --> 00:12:26,110 bien la première fois, mais nous allons écrire comme chance pour que nous 330 00:12:26,110 --> 00:12:27,000 peut faire ce point. 331 00:12:27,000 --> 00:12:30,970 Dans le second cas, elle a mobilisé une algorithme qui répète encore et 332 00:12:30,970 --> 00:12:34,670 encore une fois, mais elle a pris pour acquis une certaines hypothèses que nous permettions 333 00:12:34,670 --> 00:12:39,370 , mais elle exploite le détail deuxième fois qu'elle n'a pas eu l' 334 00:12:39,370 --> 00:12:39,840 première fois. 335 00:12:39,840 --> 00:12:41,800 Qui était quoi? 336 00:12:41,800 --> 00:12:43,050 >> Que la liste a été triée. 337 00:12:43,050 --> 00:12:46,350 Donc dès que la liste a été triée, nous affirment que Jennifer était capable de faire 338 00:12:46,350 --> 00:12:47,480 fondamentalement mieux. 339 00:12:47,480 --> 00:12:51,450 7 portes, oui, n'est-ce pas intéressant, mais supposons que ce que nous sommes 7 millions de portes. 340 00:12:51,450 --> 00:12:54,080 Connexion de n va certainement d'effectuer beaucoup, beaucoup 341 00:12:54,080 --> 00:12:55,610 plus rapide dans le long terme. 342 00:12:55,610 --> 00:12:58,880 Mais elle a dû subir l' portes triés pour elle. 343 00:12:58,880 --> 00:13:02,320 Maintenant, j'ai pris la liberté de le faire à l'avance sur l'écran de l'ordinateur 344 00:13:02,320 --> 00:13:05,160 ici, mais supposons que Jennifer eu à le faire elle-même? 345 00:13:05,160 --> 00:13:10,120 Supposons que les portes en question données représentées dans une base de données, ou 346 00:13:10,120 --> 00:13:14,260 amis inscrits à Facebook, ou toutes les pages Web sur l'Internet qui 347 00:13:14,260 --> 00:13:16,880 divers sites Web pourraient avoir besoin à l'index ou la recherche terminée. 348 00:13:16,880 --> 00:13:20,940 >> Supposons que vous venez d'avoir un ensemble de données brutes défini et il a été laissé à vous, ou à 349 00:13:20,940 --> 00:13:23,010 Jennifer à faire que le tri? 350 00:13:23,010 --> 00:13:26,950 C'est, plutôt, exige que nous répondions la question, eh bien, combien de temps 351 00:13:26,950 --> 00:13:31,080 aurait pris Jennifer, ou même moi, pour trier ces chiffres à l'avance afin 352 00:13:31,080 --> 00:13:32,680 qu'elle pouvait tirer parti de cela? 353 00:13:32,680 --> 00:13:32,880 Droite? 354 00:13:32,880 --> 00:13:36,620 Parce que l'implication, bien sûr, est si ça me prend un certain temps pour trier 355 00:13:36,620 --> 00:13:40,800 les nombres, qui est le diable se soucie que vous peut trouver un nombre comme 50 si vite, 356 00:13:40,800 --> 00:13:44,850 comme dans le cas de Jennifer, si nous avons plus que accablé la quantité de temps totale 357 00:13:44,850 --> 00:13:46,920 il a fallu en triant les choses à l'avance? 358 00:13:46,920 --> 00:13:49,320 >> Donc, nous allons voir si nous ne pouvons pas l' peindre le tableau ici. 359 00:13:49,320 --> 00:13:51,370 J'ai tout un tas plus de stress boules, si cela aide 360 00:13:51,370 --> 00:13:52,270 briser la glace ici. 361 00:13:52,270 --> 00:13:55,690 Et si vous voulez bien, nous besoin de sept bénévoles - 362 00:13:55,690 --> 00:13:57,060 sur, OK. 363 00:13:57,060 --> 00:13:57,240 Wow. 364 00:13:57,240 --> 00:13:59,250 Donc, nous n'avons pas à dépenser sur les lampes de bureau, paraît-il. 365 00:13:59,250 --> 00:13:59,690 Très bien. 366 00:13:59,690 --> 00:14:01,530 Alors que diriez-vous deux à l'avant. 367 00:14:01,530 --> 00:14:04,160 Que diriez-vous deux gars dans le dos. 368 00:14:04,160 --> 00:14:04,870 C'est donc quatre. 369 00:14:04,870 --> 00:14:09,890 Que diriez-vous devant cinq, six et sept ans. 370 00:14:09,890 --> 00:14:10,320 Juste là. 371 00:14:10,320 --> 00:14:13,260 Votre ami vous a souligner, ainsi vous obtenez le prix. 372 00:14:13,260 --> 00:14:13,700 >> Très bien. 373 00:14:13,700 --> 00:14:14,410 Venez sur place. 374 00:14:14,410 --> 00:14:17,120 Et pourquoi ne pas vous avons les gars viennent par ici. 375 00:14:17,120 --> 00:14:18,960 Je vais vous donner à chacun un numéro. 376 00:14:18,960 --> 00:14:22,150 Et aller de l'avant et d'organiser vous-mêmes identique à ce qui est 377 00:14:22,150 --> 00:14:25,180 représentée sur l'écran. 378 00:14:25,180 --> 00:14:26,530 >> [Interposition VOIX] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. Malan: Oop, désolé. 380 00:14:28,160 --> 00:14:30,210 Bug. 381 00:14:30,210 --> 00:14:32,180 Très bien. 382 00:14:32,180 --> 00:14:32,750 Eh bien, nous y voilà. 383 00:14:32,750 --> 00:14:34,180 Le numéro cinq. 384 00:14:34,180 --> 00:14:35,136 Le numéro six. 385 00:14:35,136 --> 00:14:37,770 Un, deux, trois, quatre, cinq, six, sept ans. 386 00:14:37,770 --> 00:14:39,410 Oh, c'est bizarre. 387 00:14:39,410 --> 00:14:41,210 >> ENCEINTE 2: Je vais chercher un -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. Malan: Bonne affaire. 389 00:14:41,900 --> 00:14:43,130 Très bien. 390 00:14:43,130 --> 00:14:44,611 Merci pour votre participation. 391 00:14:44,611 --> 00:14:47,200 >> [Applaudissements] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 Très bien. 394 00:14:48,860 --> 00:14:51,970 Nous avons donc quatre, deux, six, un, trois, sept, cinq. 395 00:14:51,970 --> 00:14:56,010 Parfait, donc nous avons sept bénévoles ici, qui sont de largeur égale à l' 396 00:14:56,010 --> 00:14:57,430 tableau que nous jouons avec la précédente. 397 00:14:57,430 --> 00:14:59,470 Et j'ai choisi sept pour des raisons ce sera juste 398 00:14:59,470 --> 00:15:00,840 pratique dans un peu. 399 00:15:00,840 --> 00:15:04,400 Et je vais proposer d'abord que nous trions ces sept bénévoles. 400 00:15:04,400 --> 00:15:06,786 Si vous le souhaitez, d'abord, pour dire bonjour si. 401 00:15:06,786 --> 00:15:08,970 Depuis cela va être un maladroites plusieurs minutes. 402 00:15:08,970 --> 00:15:10,370 Présentez-vous. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Salut, je suis la Grâce. 404 00:15:10,980 --> 00:15:14,190 Je suis un étudiant en deuxième année dans Leverett House. 405 00:15:14,190 --> 00:15:14,620 >> BRANSON: Salut. 406 00:15:14,620 --> 00:15:15,620 Je suis Branson. 407 00:15:15,620 --> 00:15:16,920 Je suis un étudiant de première année en soudure. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> GABE: Salut. 410 00:15:20,230 --> 00:15:21,040 Je suis Gabe. 411 00:15:21,040 --> 00:15:22,300 Je suis un junior dans le Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Je suis Neil. 414 00:15:25,980 --> 00:15:29,090 Je suis un étudiant de première année à Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Je suis Jason. 416 00:15:29,550 --> 00:15:32,816 Je suis un étudiant de première année en Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Je suis Mike. 418 00:15:33,700 --> 00:15:37,360 Je suis un étudiant de première année à Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Je suis Jess. 420 00:15:37,990 --> 00:15:40,313 Je suis un étudiant en deuxième année dans Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. Malan: Excellent. 422 00:15:41,300 --> 00:15:41,850 Très bien. 423 00:15:41,850 --> 00:15:44,190 Eh bien, merci à tous nos bénévoles ici jusqu'à présent. 424 00:15:44,190 --> 00:15:47,110 Et le défi à relever maintenant va être de trier de ces gars, mais 425 00:15:47,110 --> 00:15:50,250 nous allons devoir réfléchir un peu dur sur l'efficacité avec laquelle nous avons fait 426 00:15:50,250 --> 00:15:51,110 triés eux. 427 00:15:51,110 --> 00:15:52,580 Donc, nous allons d'abord essayer. 428 00:15:52,580 --> 00:15:55,970 Les gars, vous pouvez voir les numéros les uns des autres tout en plaçant autour des coins. 429 00:15:55,970 --> 00:15:59,380 Allez-y et prenez quelques secondes, et Trier-vous de plus petit sur le 430 00:15:59,380 --> 00:16:01,240 laissé à la plus grande sur la droite. 431 00:16:01,240 --> 00:16:02,490 Allez. 432 00:16:02,490 --> 00:16:07,010 433 00:16:07,010 --> 00:16:07,530 >> OK. 434 00:16:07,530 --> 00:16:08,030 Bon. 435 00:16:08,030 --> 00:16:09,370 C'était vraiment sacrément rapide. 436 00:16:09,370 --> 00:16:14,040 Maintenant, quelqu'un ici, ce qui était l'algorithme que ces gars-elles appliquées? 437 00:16:14,040 --> 00:16:14,900 >> INTERLOCUTEUR 1: petit au plus grand. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. Malan: OK. 439 00:16:15,000 --> 00:16:18,070 Au plus grand est vraiment le genre de objectif, mais je ne suis pas sûr que c'est 440 00:16:18,070 --> 00:16:18,890 vraiment un algorithme. 441 00:16:18,890 --> 00:16:21,810 Au plus grand ne veut pas dire moi étape par étape quoi faire. 442 00:16:21,810 --> 00:16:22,833 Ouais? 443 00:16:22,833 --> 00:16:24,083 >> INTERLOCUTEUR 1: [inaudible] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> DAVID J. Malan: OK. 446 00:16:26,280 --> 00:16:28,920 Donc si vous voyez une personne plus petite que votre numéro, puis passer à 447 00:16:28,920 --> 00:16:29,680 le droit d'entre eux. 448 00:16:29,680 --> 00:16:32,800 Donc, c'est maintenant obtenir plus expressive, ressemble plus à un algorithme, parce que vous 449 00:16:32,800 --> 00:16:35,410 peut dire, si ce, alors que. 450 00:16:35,410 --> 00:16:37,050 Nous avons donc une sorte de construction conditionnelle. 451 00:16:37,050 --> 00:16:39,700 Et ces gars-là ont semblé faire quelques fois, parce que certains d'entre vous ont déplacé un bit 452 00:16:39,700 --> 00:16:40,420 d'une distance. 453 00:16:40,420 --> 00:16:43,410 Donc il y avait sans doute une sorte de boucle passe dans leur esprit. 454 00:16:43,410 --> 00:16:44,610 >> Mais nous allons essayer de formaliser cela. 455 00:16:44,610 --> 00:16:47,540 Si vous pouviez réinitialisé à cet arrangement. 456 00:16:47,540 --> 00:16:50,650 Voyons voir si nous ne pouvons pas formaliser ce une bit, puis poser la question, juste 457 00:16:50,650 --> 00:16:51,580 comment efficace est-ce? 458 00:16:51,580 --> 00:16:54,220 Bien sûr, lorsque nous faisons cela plus lentement, il va se sentir aussi bien d' 459 00:16:54,220 --> 00:16:57,210 un algorithme, mais nous allons voir si nous pouvons mettre nos doigts sur les mesures précises. 460 00:16:57,210 --> 00:16:58,670 >> Alors vous deux gars sont quatre et deux ans. 461 00:16:58,670 --> 00:17:01,020 Ou vous commandez correcte ou incorrecte? 462 00:17:01,020 --> 00:17:01,900 De toute évidence erronée. 463 00:17:01,900 --> 00:17:02,710 Donc nous avons échangé. 464 00:17:02,710 --> 00:17:05,170 Maintenant, je vais passer à côté ici et dire quatre à six. 465 00:17:05,170 --> 00:17:06,240 Êtes-vous correcte ou incorrecte? 466 00:17:06,240 --> 00:17:06,599 >> GABE: C'est exact. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. Malan: C'est exact. 468 00:17:07,180 --> 00:17:08,300 Six et un? 469 00:17:08,300 --> 00:17:08,609 Nan. 470 00:17:08,609 --> 00:17:09,630 Swap. 471 00:17:09,630 --> 00:17:10,490 C'est donc deux swaps. 472 00:17:10,490 --> 00:17:11,710 Six et trois? 473 00:17:11,710 --> 00:17:11,980 Nan. 474 00:17:11,980 --> 00:17:13,000 Swap. 475 00:17:13,000 --> 00:17:13,930 Six et sept? 476 00:17:13,930 --> 00:17:14,630 On dirait bien. 477 00:17:14,630 --> 00:17:15,396 Sept et cinq ans? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [Inaudible] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. Malan: OK, échanger. 480 00:17:17,089 --> 00:17:19,770 Et triés. 481 00:17:19,770 --> 00:17:19,980 Très bien. 482 00:17:19,980 --> 00:17:21,440 Alors, évidemment pas, non? 483 00:17:21,440 --> 00:17:22,470 Donc il y avait plus de choses. 484 00:17:22,470 --> 00:17:24,920 Mais, en effet, ces gars-là, même juste instinctivement. 485 00:17:24,920 --> 00:17:25,450 maintenu en mouvement. 486 00:17:25,450 --> 00:17:27,710 Ils ne s'arrêtent pas, une fois qu'ils corrigé un problème. 487 00:17:27,710 --> 00:17:27,839 So. 488 00:17:27,839 --> 00:17:29,390 En effet, je vais devoir de faire la même chose. 489 00:17:29,390 --> 00:17:32,720 Je vais faire le tri de rembobinage retour au début de ce problème, 490 00:17:32,720 --> 00:17:35,630 ou le début de cette gamme de personnes, nous allons commencer à les appeler. 491 00:17:35,630 --> 00:17:38,366 >> Et maintenant, que si mon algorithme sur la seconde passe être? 492 00:17:38,366 --> 00:17:39,220 >> INTERLOCUTEUR 1: Même chose. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. Malan: Même chose. 494 00:17:39,940 --> 00:17:41,460 Et cela, je commence à aimer, non? 495 00:17:41,460 --> 00:17:44,720 Dès que vous pouvez vous retrouver à faire la même chose encore et encore, c'est 496 00:17:44,720 --> 00:17:47,890 de plus en plus comme un algorithme, et l'instinct moins humain. 497 00:17:47,890 --> 00:17:48,680 >> Alors maintenant, nous y revoilà. 498 00:17:48,680 --> 00:17:49,870 Deux et quatre? 499 00:17:49,870 --> 00:17:50,220 No. 500 00:17:50,220 --> 00:17:51,050 Quatre et un? 501 00:17:51,050 --> 00:17:53,380 Ah, il y avait effectivement un certain encore du travail à faire. 502 00:17:53,380 --> 00:17:53,620 Pour et trois? 503 00:17:53,620 --> 00:17:54,572 Bon. 504 00:17:54,572 --> 00:17:56,000 Quatre à six? 505 00:17:56,000 --> 00:17:58,380 Six et cinq? 506 00:17:58,380 --> 00:17:59,470 Six et sept? 507 00:17:59,470 --> 00:18:00,970 OK, maintenant, c'est fait. 508 00:18:00,970 --> 00:18:01,550 OK, no. 509 00:18:01,550 --> 00:18:02,710 Je dois y retourner. 510 00:18:02,710 --> 00:18:05,130 >> Alors maintenant, encore une fois, nous faisons ce un peu plus délibérément. 511 00:18:05,130 --> 00:18:08,700 Et maintenant, il ya juste un cerveau l'exécution de cet algorithme. 512 00:18:08,700 --> 00:18:10,290 Un CPU, si vous voulez. 513 00:18:10,290 --> 00:18:13,090 Et franchement, c'est la seule ressource nous allons avoir accès. 514 00:18:13,090 --> 00:18:16,280 Et une fois que nous ne retournons à un clavier et avoir quelque chose comme C à notre 515 00:18:16,280 --> 00:18:19,600 disposition, nous ne sommes qu'à l'écriture d'un programme que peut faire une chose à la fois. 516 00:18:19,600 --> 00:18:22,900 Considérant que, ces gars-là il ya un instant, nous leveraged leur intelligence collective 517 00:18:22,900 --> 00:18:24,180 comme vous avez fait dans la semaine zéro. 518 00:18:24,180 --> 00:18:24,980 Donc, nous allons continuer à faire ça. 519 00:18:24,980 --> 00:18:26,260 >> Deux et un. 520 00:18:26,260 --> 00:18:26,945 Deux et trois. 521 00:18:26,945 --> 00:18:27,460 Trois et quatre. 522 00:18:27,460 --> 00:18:28,310 Quatre et cinq. 523 00:18:28,310 --> 00:18:28,620 Cinq et six ans. 524 00:18:28,620 --> 00:18:30,510 Six et sept ans. 525 00:18:30,510 --> 00:18:31,880 Fait? 526 00:18:31,880 --> 00:18:34,560 Donc je suis, mais laissez-moi jouer l'avocat du diable. 527 00:18:34,560 --> 00:18:37,950 Dois-je, le type d'ordinateur qui vient fait une passe dans cette gamme de 528 00:18:37,950 --> 00:18:40,225 personnes, savent que je suis fait? 529 00:18:40,225 --> 00:18:40,670 >> INTERLOCUTEUR 1: No. 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. Malan: Alors pourquoi? 531 00:18:41,050 --> 00:18:46,900 Qu'est-ce que je dois faire pour conclure de façon décisive que je suis fait? 532 00:18:46,900 --> 00:18:48,230 Probablement encore une passe. 533 00:18:48,230 --> 00:18:48,430 Droite? 534 00:18:48,430 --> 00:18:51,760 Parce que tout ce que je sais de ce précédent passe, c'est que j'ai corrigé une erreur. 535 00:18:51,760 --> 00:18:53,920 Et cela signifie, peut-être il ya encore une autre erreur 536 00:18:53,920 --> 00:18:54,840 que je dois corriger. 537 00:18:54,840 --> 00:18:58,680 Donc, je ne peux être sûr de rembobinage, et puis vérifier, un à deux, deux et 538 00:18:58,680 --> 00:19:00,940 trois, trois et quatre, quatre et cinq, cinq et six, six et sept ans. 539 00:19:00,940 --> 00:19:02,510 OK, maintenant je n'ai pas de travail. 540 00:19:02,510 --> 00:19:05,990 >> Je peux certainement me rappeler que je n'ai rien fait de travailler avec quelque chose comme une variable, 541 00:19:05,990 --> 00:19:06,975 comme un int. 542 00:19:06,975 --> 00:19:12,490 Appelez-swaps, et si swaps est 0 une fois que je obtenir ici, et il a commencé à 0, puis 543 00:19:12,490 --> 00:19:15,520 Je voudrais juste être stupide pour continuer dans les deux sens, en vérifiant à nouveau, et 544 00:19:15,520 --> 00:19:16,450 encore, et encore, pas vrai? 545 00:19:16,450 --> 00:19:18,450 Parce que vous êtes coincé dans une certaine sorte de boucle infinie. 546 00:19:18,450 --> 00:19:21,250 Donc dès que il ya 0 swaps, nous pouvons affirmer que cette 547 00:19:21,250 --> 00:19:23,810 algorithme est en effet complet. 548 00:19:23,810 --> 00:19:25,400 >> Maintenant, nous allons mettre un nom sur ce point. 549 00:19:25,400 --> 00:19:28,930 L'algorithme que je propose que nous venons de mise en œuvre est quelque chose appelé bulle 550 00:19:28,930 --> 00:19:32,800 trier, connue en tant que telle dans le sens d' les chiffres qui sont plus grands types de 551 00:19:32,800 --> 00:19:37,990 bulle leur chemin vers le haut, ou vers le haut à la fin de la série de nombres. 552 00:19:37,990 --> 00:19:40,270 Mais comment était efficace cet algorithme? 553 00:19:40,270 --> 00:19:44,600 Combien d'étapes je n'ai eu physiquement Prenez, par exemple, pour trier ces 554 00:19:44,600 --> 00:19:45,850 sept humains? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Quatre à cinq? 557 00:19:49,550 --> 00:19:51,420 OK, trop nombreux, c'est en fin de compte va être la réponse. 558 00:19:51,420 --> 00:19:54,960 Mais même alors, le nombre précis n'est pas si intéressant. 559 00:19:54,960 --> 00:19:56,670 Nous allons généraliser comme n. 560 00:19:56,670 --> 00:20:00,520 Donc, si je n'avais N nombre de personnes ici, et ils étaient, en quelque sorte, dans un ordre aléatoire à l' 561 00:20:00,520 --> 00:20:02,180 commencer, en ce que l'ordre original. 562 00:20:02,180 --> 00:20:04,910 Eh bien, combien d'étapes je n'ai eu à prendre sur la première passe? 563 00:20:04,910 --> 00:20:09,810 C'était un, deux, trois, quatre, cinq, six, et ils sont sept personnes, donc 564 00:20:09,810 --> 00:20:13,670 c'est sept, six -, c'est donc n moins un étapes la première fois. 565 00:20:13,670 --> 00:20:16,280 >> Maintenant, combien d'étapes je n'ai eu à prendre quand j'ai rembobiné? 566 00:20:16,280 --> 00:20:19,310 Eh bien, nous pourrions doubler que si nous voulions vraiment, mais pour l'instant, je suis 567 00:20:19,310 --> 00:20:22,300 juste dire, tout droit, autre n moins 1. 568 00:20:22,300 --> 00:20:25,240 Ainsi, le n moins 1 va se faire ennuyeux à suivre, nous allons donc 569 00:20:25,240 --> 00:20:26,400 juste arrondir légèrement. 570 00:20:26,400 --> 00:20:27,770 Donc 2n étapes. 571 00:20:27,770 --> 00:20:29,310 Donc, 14 étapes, donner ou prendre. 572 00:20:29,310 --> 00:20:31,930 >> Combien de fois ai-je pris une étape la prochaine fois? 573 00:20:31,930 --> 00:20:33,740 Eh bien, c'est 3n. 574 00:20:33,740 --> 00:20:34,510 vraiment. 575 00:20:34,510 --> 00:20:37,920 Et maintenant, dans le pire des cas, pour Ainsi, combien de fois aurais-je 576 00:20:37,920 --> 00:20:41,730 passé d'avant en arrière, d'avant en arrière, l'exécution de cet algorithme, en échangeant 577 00:20:41,730 --> 00:20:44,620 personnes sur chaque passe, en gros? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 Il s'agit en fait sur n carré, non? 580 00:20:50,010 --> 00:20:53,000 >> Parce que dans le pire des cas, vous pouvez genre de penser intuitivement, 581 00:20:53,000 --> 00:20:54,800 même si cela peut prendre un peu peu de temps à couler po 582 00:20:54,800 --> 00:20:57,590 Dans le pire des cas, à quoi ces sept personnes ont ressemblé, dans 583 00:20:57,590 --> 00:21:00,230 termes de l'accord de leur nombre? 584 00:21:00,230 --> 00:21:01,460 Complètement à l'envers, non? 585 00:21:01,460 --> 00:21:02,815 Et juste pour simuler que, quel est votre nom? 586 00:21:02,815 --> 00:21:03,360 >> MIKE: Mike. 587 00:21:03,360 --> 00:21:03,640 >> DAVID J. Malan: Mike? 588 00:21:03,640 --> 00:21:08,100 OK, Mike, pouvez-vous joindre à moi juste sur ici juste pour une seconde? 589 00:21:08,100 --> 00:21:08,880 En fait, non. 590 00:21:08,880 --> 00:21:10,150 Désolé Mike, le rembobinage let. 591 00:21:10,150 --> 00:21:10,910 Quel est votre nom? 592 00:21:10,910 --> 00:21:11,180 >> NEIL: Neil. 593 00:21:11,180 --> 00:21:11,640 >> DAVID J. Malan: Neil. 594 00:21:11,640 --> 00:21:13,750 OK, Neil, tu viens avec moi, si vous ne me dérange pas. 595 00:21:13,750 --> 00:21:17,150 Donc je vais proposer, juste pour simplicité, que Neil est maintenant dans sa 596 00:21:17,150 --> 00:21:18,510 pire des cas. 597 00:21:18,510 --> 00:21:20,720 Mais souviens comment j'ai mis en place mon algorithme. 598 00:21:20,720 --> 00:21:24,530 Je compare, comparer, comparer, comparer, comparer, oh. 599 00:21:24,530 --> 00:21:26,640 Maintenant, ces gars-là sont hors de l'ordre, de sorte que je fixe. 600 00:21:26,640 --> 00:21:27,980 Alors vous les gars swap. 601 00:21:27,980 --> 00:21:31,630 Mais considérons maintenant, combien plus loin Neil ne doivent aller? 602 00:21:31,630 --> 00:21:32,690 C'est à peu près n. 603 00:21:32,690 --> 00:21:33,570 Vous savez, ce n'est pas vraiment n. 604 00:21:33,570 --> 00:21:36,040 C'est comme si, n moins 1, mais je suis en train de garder une trace agacé de la petite 605 00:21:36,040 --> 00:21:37,550 numéro, nous allons donc simplement l'appeler n. 606 00:21:37,550 --> 00:21:42,860 >> Donc, si Neil se déplace d'une étape au maximum chaque temps, et pour déplacer une étape Neil, 607 00:21:42,860 --> 00:21:46,580 Je dois faire ce passe vraiment fastidieux dans les deux sens, c'est à peu près 608 00:21:46,580 --> 00:21:52,080 Ce faisant, n étapes, un total de n fois, parce que ça va me prendre 609 00:21:52,080 --> 00:21:55,820 que de nombreuses mesures pour obtenir Neil tous la voie à l'endroit où il appartient. 610 00:21:55,820 --> 00:21:58,620 Sans parler de tout le monde si vous les gars ont tous mis-commandé ainsi. 611 00:21:58,620 --> 00:22:01,100 >> Alors appelons sorte de bulle n carré. 612 00:22:01,100 --> 00:22:04,860 Le temps d'exécution de cet algorithme, l' les performances de cet algorithme, l' 613 00:22:04,860 --> 00:22:07,120 l'efficacité de cet algorithme, nous allons seulement décrire plus 614 00:22:07,120 --> 00:22:08,800 généralement que le n au carré. 615 00:22:08,800 --> 00:22:11,650 Ce qui est bien, parce que je pouvais faire le même exemple avec huit personnes, dont neuf 616 00:22:11,650 --> 00:22:15,450 personnes, un million de personnes, et que réponse ne va pas changer. 617 00:22:15,450 --> 00:22:18,870 >> Donc, si vous les gars ne me dérangerait pas, nous allons vous remettre à l'endroit où vous avez commencé. 618 00:22:18,870 --> 00:22:22,510 Et nous allons essayer deux autres approches et voir si nous ne pouvons pas faire fondamentalement 619 00:22:22,510 --> 00:22:23,820 mieux que cela. 620 00:22:23,820 --> 00:22:27,130 Alors, cette fois, je vais proposer une sorte d'algorithme différent. 621 00:22:27,130 --> 00:22:29,950 C'était très intelligent de nous la dernière fois, et vous les gars avaient raison d'avoir l' 622 00:22:29,950 --> 00:22:32,470 instincts droit de tout genre d'échange par paires. 623 00:22:32,470 --> 00:22:36,500 Mais si je voulais vraiment aborder cette simplement, et mon but est de déplacer 624 00:22:36,500 --> 00:22:39,800 tous les petits nombres de cette façon, et pousser tous les grands chiffres que 625 00:22:39,800 --> 00:22:43,030 Ainsi, pourquoi ne pas simplement le faire dans le plus naïve façon possible et voir si je 626 00:22:43,030 --> 00:22:45,730 peut faire mieux que ce qui était un algorithme assez complexe? 627 00:22:45,730 --> 00:22:46,620 >> Voyons donc. 628 00:22:46,620 --> 00:22:48,940 Quatre est un joli petit nombre, donc je suis vais vous laisser là-bas moment. 629 00:22:48,940 --> 00:22:50,610 Ooh, numéro deux, c'est encore mieux. 630 00:22:50,610 --> 00:22:52,230 Ainsi, vous pouvez simplement aller de l'avant pour un moment? 631 00:22:52,230 --> 00:22:55,670 C'est actuellement mon petit numéroté candidat, et je vais vous rappeler 632 00:22:55,670 --> 00:22:57,000 que, avec, comme, une variable. 633 00:22:57,000 --> 00:22:57,930 Mais je vais garder le contrôle. 634 00:22:57,930 --> 00:22:59,890 Y at-il quelqu'un dont nombre est plus petit? 635 00:22:59,890 --> 00:23:00,460 Six, non. 636 00:23:00,460 --> 00:23:01,390 Oh, il ya encore Neil. 637 00:23:01,390 --> 00:23:04,050 >> Donc, je vais vous faire reculer sorte de point de vue conceptuel. 638 00:23:04,050 --> 00:23:05,120 Neil se présentera. 639 00:23:05,120 --> 00:23:08,440 Et maintenant, la variable que j'utilise pour garder trace de qui a la plus petite 640 00:23:08,440 --> 00:23:11,390 nombre est mis à jour pour contenir L'emplacement de Neil. 641 00:23:11,390 --> 00:23:12,110 Eh bien, voyons voir. 642 00:23:12,110 --> 00:23:13,960 Trois, sept, cinq. 643 00:23:13,960 --> 00:23:15,590 OK, je sais que Neil était le plus petit. 644 00:23:15,590 --> 00:23:18,110 Quelle est la chose la plus simple pour moi de faire maintenant? 645 00:23:18,110 --> 00:23:21,410 Je ne vais pas perdre mon temps par tout bouillonnement Neil un endroit à la gauche. 646 00:23:21,410 --> 00:23:25,350 Pourquoi ne pas simplement mettre Neil où il appartient, ce qui est bien sûr où? 647 00:23:25,350 --> 00:23:26,160 >> Tout le chemin au début. 648 00:23:26,160 --> 00:23:27,720 Donc, Neil, viens avec moi. 649 00:23:27,720 --> 00:23:28,910 Et quelle est votre nom? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Grace. 651 00:23:29,310 --> 00:23:29,710 >> DAVID J. Malan: Grace. 652 00:23:29,710 --> 00:23:29,920 OK. 653 00:23:29,920 --> 00:23:32,490 Donc, Grace, malheureusement, vous êtes type de la manière. 654 00:23:32,490 --> 00:23:34,290 Alors, comment pouvons-nous résoudre ce problème? 655 00:23:34,290 --> 00:23:34,490 Droite? 656 00:23:34,490 --> 00:23:37,500 Si c'est un tableau, il ya seulement sept emplacements. 657 00:23:37,500 --> 00:23:40,830 Rappelons que, avec Rob, nous avons parlé déclarant âges, et nous n'avions qu'une 658 00:23:40,830 --> 00:23:41,740 nombre fini d'âges? 659 00:23:41,740 --> 00:23:42,535 Même idée ici. 660 00:23:42,535 --> 00:23:44,300 Nous ne disposons que d'un nombre fini d'entiers. 661 00:23:44,300 --> 00:23:47,590 La grâce est en quelque sorte dans notre Ainsi, alors comment pouvons-nous résoudre ce problème? 662 00:23:47,590 --> 00:23:49,555 >> Le plus simple, c'est comme, Grace, désolé. 663 00:23:49,555 --> 00:23:51,870 Vous allez avoir à aller sur il afin que nous puissions faire de la place. 664 00:23:51,870 --> 00:23:55,290 Maintenant, si vous pensez à ce sujet, peut-être nous avons juste fait qu'aggraver le problème. 665 00:23:55,290 --> 00:23:58,510 Et peut-être que nous avons fait, parce que si Grâce étaient au bon endroit? 666 00:23:58,510 --> 00:24:01,730 Mais nous savons qu'elle n'est pas, parce que autrement, elle aurait été 667 00:24:01,730 --> 00:24:03,980 debout avant au lieu de Neil en ce moment, non? 668 00:24:03,980 --> 00:24:05,550 Nous avons déjà vérifié son numéro rupture. 669 00:24:05,550 --> 00:24:05,770 >> Très bien. 670 00:24:05,770 --> 00:24:09,110 Alors maintenant, Neil est au bon endroit, et Je peux faire une légère optimisation. 671 00:24:09,110 --> 00:24:11,740 Pour la prochaine minute, je vais ignorer Neil tous ensemble, afin de ne pas 672 00:24:11,740 --> 00:24:15,280 perdre son temps, ou accidentellement permuter lui au mauvais endroit. 673 00:24:15,280 --> 00:24:17,805 Alors maintenant, comment puis-je trouver le prochain élément qui est plus petit? 674 00:24:17,805 --> 00:24:18,480 Deux. 675 00:24:18,480 --> 00:24:20,225 C'est un assez bon nombre, si vous voulez aller de l'avant et 676 00:24:20,225 --> 00:24:21,100 Je me souviens de vous. 677 00:24:21,100 --> 00:24:21,980 Six, rien de bon. 678 00:24:21,980 --> 00:24:24,820 Quatre, trois, sept, cinq, rien de bon. 679 00:24:24,820 --> 00:24:26,800 Permettez-moi de vous déplacer à votre juste place. 680 00:24:26,800 --> 00:24:28,470 Et nous avons juste eu de la chance cette fois. 681 00:24:28,470 --> 00:24:31,350 >> Maintenant, je vais ignorer ces deux gars, et maintenant faire une plus 682 00:24:31,350 --> 00:24:32,260 passer à travers cela. 683 00:24:32,260 --> 00:24:33,490 Six, c'est un assez petit nombre. 684 00:24:33,490 --> 00:24:34,300 Allons de l'avant. 685 00:24:34,300 --> 00:24:35,220 Oh, désolé. 686 00:24:35,220 --> 00:24:37,640 Le nombre de Grace est meilleure, donc marcher sur l'avant. 687 00:24:37,640 --> 00:24:38,260 Four. 688 00:24:38,260 --> 00:24:39,120 Désolé, Grace. 689 00:24:39,120 --> 00:24:39,950 Y retourner. 690 00:24:39,950 --> 00:24:41,550 Numéro trois, c'est mieux. 691 00:24:41,550 --> 00:24:42,290 Seven. 692 00:24:42,290 --> 00:24:42,720 Cinq. 693 00:24:42,720 --> 00:24:43,550 Et maintenant, quel est votre nom? 694 00:24:43,550 --> 00:24:44,000 >> JASON: Jason. 695 00:24:44,000 --> 00:24:44,420 >> DAVID J. Malan: Jason. 696 00:24:44,420 --> 00:24:47,050 Alors, Jason est maintenant le plus petit élément j'ai choisi. 697 00:24:47,050 --> 00:24:49,160 Où est-ce qu'il va aller? 698 00:24:49,160 --> 00:24:50,380 Alors, où est six. 699 00:24:50,380 --> 00:24:51,210 Et votre nom est nouveau? 700 00:24:51,210 --> 00:24:51,710 >> GABE: Gabe. 701 00:24:51,710 --> 00:24:52,340 >> DAVID J. Malan: Gabe. 702 00:24:52,340 --> 00:24:53,220 Gabe est dans la manière. 703 00:24:53,220 --> 00:24:54,640 Quelle est la meilleure chose à faire? 704 00:24:54,640 --> 00:24:58,390 Échanger ces deux gars et continuez. 705 00:24:58,390 --> 00:24:59,020 Alors maintenant, nous allons voir. 706 00:24:59,020 --> 00:25:00,170 Qui est le plus petit? 707 00:25:00,170 --> 00:25:01,030 Four. 708 00:25:01,030 --> 00:25:01,990 Laissez-moi juste un peu de triche. 709 00:25:01,990 --> 00:25:03,090 Cinq va être le plus petit. 710 00:25:03,090 --> 00:25:05,220 Je trouve prochaine, si vous voulez à l'étape avant, qu'est-ce que je dois faire avec 711 00:25:05,220 --> 00:25:06,820 ces gars-là, avec Gabe? 712 00:25:06,820 --> 00:25:08,450 Swap nouveau. 713 00:25:08,450 --> 00:25:10,740 Alors maintenant, encore un peu dans le désordre. 714 00:25:10,740 --> 00:25:14,140 J'ai trouvé Gabe pour être la plus petite, de sorte Je pop sortir, vous vous déplacez gars plus. 715 00:25:14,140 --> 00:25:15,190 Et fait. 716 00:25:15,190 --> 00:25:17,200 >> Donc réponse est la même. 717 00:25:17,200 --> 00:25:18,600 Le résultat final est le même. 718 00:25:18,600 --> 00:25:22,730 Laquelle de ces deux algorithmes est le meilleur? 719 00:25:22,730 --> 00:25:23,500 Le second, j'ai entendu. 720 00:25:23,500 --> 00:25:24,252 Pourquoi? 721 00:25:24,252 --> 00:25:25,900 >> Intervenant 3: Il n pas [inaudible]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. Malan: C'est n étapes au maximum. 723 00:25:27,600 --> 00:25:28,490 Intéressant. 724 00:25:28,490 --> 00:25:30,610 Alors, est-ce bien? 725 00:25:30,610 --> 00:25:33,630 Alors, comment ai-je trouvé l' plus petit élément? 726 00:25:33,630 --> 00:25:37,060 Combien d'étapes je n'ai eu à prendre le trouver le plus petit élément? 727 00:25:37,060 --> 00:25:39,220 J'ai jeté un oeil tout le chemin à la fin, non? 728 00:25:39,220 --> 00:25:41,530 Parce que dans ce cas le plus défavorable, ce qui si Neil était ici? 729 00:25:41,530 --> 00:25:45,700 Il suffit donc de trouver le plus petit élément me n étapes, ou n moins 1 prend. 730 00:25:45,700 --> 00:25:46,100 Mais, OK. 731 00:25:46,100 --> 00:25:46,980 Donc, fixer Neil. 732 00:25:46,980 --> 00:25:48,740 Rappelez-vous que, il ya une minute ou deux. 733 00:25:48,740 --> 00:25:51,680 >> Mais comment ai-je trouver le prochain plus petit élément? 734 00:25:51,680 --> 00:25:54,830 C'est n moins 1 ou moins 2 n vraiment, à partir du nombre d'étapes. 735 00:25:54,830 --> 00:25:55,440 Alors OK. 736 00:25:55,440 --> 00:25:57,390 Donc, je n'ai N moins 2. 737 00:25:57,390 --> 00:25:57,600 Très bien. 738 00:25:57,600 --> 00:25:59,130 Alors, qui se sent un peu mieux. 739 00:25:59,130 --> 00:25:59,730 Très bien. 740 00:25:59,730 --> 00:26:03,270 Combien d'étapes la prochaine fois pour trouver le numéro trois? 741 00:26:03,270 --> 00:26:04,420 Alors n moins 4. 742 00:26:04,420 --> 00:26:07,670 Donc ça baisse, soit un de moins l'étape à chaque itération. 743 00:26:07,670 --> 00:26:08,740 Donc, ce ne se sent mieux, non? 744 00:26:08,740 --> 00:26:13,450 Si la dernière fois, c'était à peu près n fois n, cette fois, c'est n moins 1, plus n moins 745 00:26:13,450 --> 00:26:16,500 2, plus n moins 3, plus n moins 4, point, point, point. 746 00:26:16,500 --> 00:26:18,750 Mais si vous vous souvenez de votre lycée manuels scolaires, la petite triche 747 00:26:18,750 --> 00:26:24,380 feuille à l'arrière qui a des formules, si vous ajoutez cette série de chiffres, 748 00:26:24,380 --> 00:26:31,280 quel est le nombre total d'étapes va être que je prends ici? 749 00:26:31,280 --> 00:26:36,580 >> C'est l'un de ceux, comme, n moins 1, n fois, divisé par deux. 750 00:26:36,580 --> 00:26:39,040 Alors permettez-moi de voir si je peux tirer cette place pendant un moment. 751 00:26:39,040 --> 00:26:42,230 Et encore, je suis un peu arrondi certains chiffres juste pour garder notre vie simple, 752 00:26:42,230 --> 00:26:47,830 mais si je me souviens, c'est quelque chose comme si Je fais n moins 1 choses, alors n moins 753 00:26:47,830 --> 00:26:53,570 2, alors n moins 3, il ya à peu près quelque chose comme ceci sur 2, et si je 754 00:26:53,570 --> 00:26:55,510 multiplier cette rupture, c'est fait place n. 755 00:26:55,510 --> 00:26:58,940 Cela ne veut pas se sentir trop bon. n moins n supérieur à 2. 756 00:26:58,940 --> 00:27:00,350 >> Mais voici la chose. 757 00:27:00,350 --> 00:27:03,720 En informatique, lorsque les problèmes commencer à devenir intéressant, c'est lorsque n 758 00:27:03,720 --> 00:27:04,700 devient vraiment grand. 759 00:27:04,700 --> 00:27:08,110 Et quand n devient vraiment grand, ce qui ces valeurs va dominer tous 760 00:27:08,110 --> 00:27:09,750 des autres? 761 00:27:09,750 --> 00:27:10,990 C'est un peu le n carré, non? 762 00:27:10,990 --> 00:27:13,340 Oui, en divisant par 2 est très bonne. 763 00:27:13,340 --> 00:27:16,740 Mais si vous parlez milliards d'éléments de données, ou des milliards d' 764 00:27:16,740 --> 00:27:18,700 morceaux de données, OK, donc vous êtes deux fois plus vite. 765 00:27:18,700 --> 00:27:22,440 Mais qui se soucie vraiment si grand nombre, si ce facteur est ce qui est 766 00:27:22,440 --> 00:27:23,040 plus en plus. 767 00:27:23,040 --> 00:27:25,990 Et sûrement, il fait plus de une différence que ce gars-là. 768 00:27:25,990 --> 00:27:29,120 Ainsi, même si vous les gars ont raison, le deuxième algorithme, nous l'appellerons 769 00:27:29,120 --> 00:27:32,970 tri par sélection, est, dans le monde réel, un peu plus rapide potentiellement, parce que je suis 770 00:27:32,970 --> 00:27:35,360 prenant de moins en moins étapes chaque fois. 771 00:27:35,360 --> 00:27:37,340 >> Ce n'est pas vraiment fondamentalement plus rapide. 772 00:27:37,340 --> 00:27:41,430 Parce que si nous jouons en fait cela pour les grandes valeurs de n, à la fin de 773 00:27:41,430 --> 00:27:44,750 le jour, pendant assez grand n, il est toujours va se sentir assez lent. 774 00:27:44,750 --> 00:27:46,770 Eh bien, permettez-moi de prendre un dernier passage à cela. 775 00:27:46,770 --> 00:27:48,920 C'est ce que j'appellerais sélection sorte. 776 00:27:48,920 --> 00:27:51,040 Vous les gars vous pouvez réinitialiser une dernière fois? 777 00:27:51,040 --> 00:27:53,550 Et dans ce dernier cas, je vais de proposer quelque chose 778 00:27:53,550 --> 00:27:54,970 appelé le tri par insertion. 779 00:27:54,970 --> 00:27:57,470 Le tri par insertion être, conceptuellement, un peu différent. 780 00:27:57,470 --> 00:28:00,980 >> Plutôt que d'aller d'avant en arrière et sélectionner le plus petit élément, je suis 781 00:28:00,980 --> 00:28:05,030 aller juste pour faire face à chacun de ces les gars que je rencontre, et insérer 782 00:28:05,030 --> 00:28:06,850 eux dans leur bon endroit. 783 00:28:06,850 --> 00:28:10,160 Donc je vais commencer avec Grace, et je vois qu'elle est numéro quatre. 784 00:28:10,160 --> 00:28:11,720 D'où vient le numéro quatre appartiennent? 785 00:28:11,720 --> 00:28:14,940 Je n'ai pas commencé le tri rien, ainsi la grâce arrive à rester là. 786 00:28:14,940 --> 00:28:18,355 Et maintenant, je vais demander, si vous pouviez faire un pas à droite, cette 787 00:28:18,355 --> 00:28:21,650 ma liste triée, c'est mon non triés liste restante. 788 00:28:21,650 --> 00:28:23,260 Alors maintenant, je vais passer à côté, et quel est votre nom? 789 00:28:23,260 --> 00:28:23,700 >> BRANSON: Branson. 790 00:28:23,700 --> 00:28:24,150 >> DAVID J. Malan: Branson. 791 00:28:24,150 --> 00:28:25,375 Alors Branson est le numéro deux. 792 00:28:25,375 --> 00:28:27,490 Donc, je vais vous prendre pour un moment. 793 00:28:27,490 --> 00:28:30,940 Et maintenant, où vous situez-vous dans ce tableau? 794 00:28:30,940 --> 00:28:32,360 Donc, pour le droit de grâce. 795 00:28:32,360 --> 00:28:35,670 Encore une fois, nous sommes en quelque sorte de faire Grâce faire beaucoup de travail ici. 796 00:28:35,670 --> 00:28:37,290 Où allons-nous vous mettons? 797 00:28:37,290 --> 00:28:40,120 Nous allons donc vous glisser à l' à gauche, et insérer Branson là. 798 00:28:40,120 --> 00:28:41,680 Mais maintenant, je prétends que vous les gars sont faites. 799 00:28:41,680 --> 00:28:43,240 Mais remarquez, je ne vais pas utiliser l'espace supplémentaire. 800 00:28:43,240 --> 00:28:45,130 C'est encore 2 éléments ici, 5 ici. 801 00:28:45,130 --> 00:28:47,910 Taille totale du tableau est 7, donc je suis ne triche pas, d'accord? 802 00:28:47,910 --> 00:28:51,950 >> Nous avons donc maintenant, avec Gabe ici, l' numéro six, où vous situez-vous? 803 00:28:51,950 --> 00:28:52,650 Vous avez encore de la chance. 804 00:28:52,650 --> 00:28:53,820 Donc, vous arrivez à rester là. 805 00:28:53,820 --> 00:28:57,210 Il suffit de prendre un léger cran vers la droite juste pour faire comprendre que vous êtes triés. 806 00:28:57,210 --> 00:29:00,520 Et maintenant nous avons Neil nouveau numéro un, où allez-vous? 807 00:29:00,520 --> 00:29:03,540 Et maintenant où nous commençons à voir que Cet algorithme, bien que le premier 808 00:29:03,540 --> 00:29:05,950 vue, se sent assez intelligent, regarder ce qui va se passer. 809 00:29:05,950 --> 00:29:07,370 Si vous pouviez aller de l'avant. 810 00:29:07,370 --> 00:29:09,260 >> Où voulons-nous mettre Neil? 811 00:29:09,260 --> 00:29:11,830 Alors, évidemment, ici, alors comment pouvons-nous obtenir Neil là? 812 00:29:11,830 --> 00:29:12,970 Faisons cette étape-par-étape. 813 00:29:12,970 --> 00:29:15,620 Gabe, où devez-vous aller? 814 00:29:15,620 --> 00:29:19,590 Yep, alors prenez un grand pas, ou deux demi-étapes pour faire 815 00:29:19,590 --> 00:29:20,820 une étape là-bas. 816 00:29:20,820 --> 00:29:21,750 Grace, où allez-vous? 817 00:29:21,750 --> 00:29:22,510 Bon. 818 00:29:22,510 --> 00:29:23,500 Donc, une autre étape. 819 00:29:23,500 --> 00:29:24,960 Et enfin, Branson? 820 00:29:24,960 --> 00:29:25,460 Une autre étape. 821 00:29:25,460 --> 00:29:27,190 Et maintenant, nous pouvons mettre en place Neil. 822 00:29:27,190 --> 00:29:28,440 >> Alors maintenant, poursuivre cette logique. 823 00:29:28,440 --> 00:29:32,420 Même si nous ne sommes pas en train de passer Neil plus, et plus, et plus, pour le mettre 824 00:29:32,420 --> 00:29:36,420 où il va, dans le pire des cas, le prochain numéro nous pourrions rencontrer pouvait 825 00:29:36,420 --> 00:29:42,220 soit le nombre, par exemple, il y avait un certain nombre zéro, alors nous allons passer tout de 826 00:29:42,220 --> 00:29:42,730 ces gars-là. 827 00:29:42,730 --> 00:29:44,950 Supposons qu'il ya un certain nombre, négatif un, alors nous devons changer 828 00:29:44,950 --> 00:29:46,080 tous ces gars-là. 829 00:29:46,080 --> 00:29:48,500 Nous sommes donc vraiment juste une sorte de retournement le problème autour, de sorte que nous sommes 830 00:29:48,500 --> 00:29:52,620 le transfert de la charge de la Procédé de sélection de manière à l'insertion 831 00:29:52,620 --> 00:29:56,930 processus, tels que vous les gars ont juste eu de se déplacer à peu près n moins quelque chose 832 00:29:56,930 --> 00:29:57,940 nombre d'étapes. 833 00:29:57,940 --> 00:30:01,200 Et que nombre de mesures ne va à augmenter à mesure que je sélectionne plus de numéros, 834 00:30:01,200 --> 00:30:04,730 si je dois continuer à pousser les gars dos, et le dos, et le dos. 835 00:30:04,730 --> 00:30:08,320 >> Donc, le plus triste, c'est maintenant l'ensemble de ces algorithmes sont n au carré. 836 00:30:08,320 --> 00:30:10,570 Allons de l'avant et grâce à ces les gars, et de visualiser ces un peu 837 00:30:10,570 --> 00:30:11,090 différemment. 838 00:30:11,090 --> 00:30:12,312 Très bien fait. 839 00:30:12,312 --> 00:30:14,120 >> [Applaudissements] 840 00:30:14,120 --> 00:30:15,030 >> Très bien. 841 00:30:15,030 --> 00:30:16,280 Là vous allez. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Merci pour - 844 00:30:18,470 --> 00:30:19,190 >> BRANSON: [Inaudible] garder les chiffres. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. Malan: Non, vous pouvez garder les numéros ainsi. 846 00:30:21,990 --> 00:30:23,440 Très bien. 847 00:30:23,440 --> 00:30:24,100 Bien fait. 848 00:30:24,100 --> 00:30:25,300 Très bien. 849 00:30:25,300 --> 00:30:30,510 Donc, nous allons voir si nous ne pouvons maintenant résumer plus rapidement et plus visuellement, 850 00:30:30,510 --> 00:30:33,410 exactement ce qui vient de se passer ici comme suit. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Je vais aller de l'avant et tirez Firefox. 853 00:30:38,770 --> 00:30:41,310 Nous allons lier cette manifestation sur le site Web du cours. 854 00:30:41,310 --> 00:30:43,870 Java est un peu gênant de faire fonctionner dans certains navigateurs de nos jours. 855 00:30:43,870 --> 00:30:46,760 Donc, si vous jouez avec ça à la maison, réalisez que vous pourriez avoir besoin d'utiliser Firefox 856 00:30:46,760 --> 00:30:47,990 pour que cela marche. 857 00:30:47,990 --> 00:30:50,440 Et ce que je vais faire avec cette démonstration est le suivant. 858 00:30:50,440 --> 00:30:54,875 >> Au fond, j'ai tout un tas d' les options du menu, y compris un début et une 859 00:30:54,875 --> 00:30:55,840 le bouton d'arrêt. 860 00:30:55,840 --> 00:30:59,450 Par ailleurs, en passant, il semble y avoir une bug dans ces programmes, par lequel vous 861 00:30:59,450 --> 00:31:03,720 ne peut pas réellement voir le démarrage ou d'arrêt bouton sauf si vous détenez commande ou Alt 862 00:31:03,720 --> 00:31:06,560 plus et zoom, qui curieusement vous montre plus de boutons. 863 00:31:06,560 --> 00:31:09,090 Il suffit donc de FYI si vous jouez avec ça à la maison. 864 00:31:09,090 --> 00:31:12,870 Maintenant, je vais cliquer sur Démarrer en un moment, après avoir spécifié un délai d', 865 00:31:12,870 --> 00:31:16,810 comme, à 200 millisecondes ici, afin que nous puissions voir ce qui se passe. 866 00:31:16,810 --> 00:31:20,180 >> Donc, je prétends que c'est une visualisation du premier algorithme 867 00:31:20,180 --> 00:31:23,730 ces gars ont fait, sorte de bulle, où nous avons échangé personnes par paires. 868 00:31:23,730 --> 00:31:27,490 L'idée maîtresse de cette visualisation est que la hauteur des barres 869 00:31:27,490 --> 00:31:30,510 représente la taille du nombre. 870 00:31:30,510 --> 00:31:32,210 Donc, le plus grand de la barre, le Plus le nombre. 871 00:31:32,210 --> 00:31:33,680 Shorter la barre, plus le nombre. 872 00:31:33,680 --> 00:31:38,630 Et si vous remarquez, nous allons à travers la première itération de l'algorithme, 873 00:31:38,630 --> 00:31:42,620 permutation nombre, petits et grands, de sorte que le petit nombre vient en premier et 874 00:31:42,620 --> 00:31:44,280 le grand nombre va vers la droite. 875 00:31:44,280 --> 00:31:48,770 >> Et dès que nous aurons le fin d'un tableau de beaucoup plus nombreux que les sept, nous sommes 876 00:31:48,770 --> 00:31:49,900 va revenir au début. 877 00:31:49,900 --> 00:31:51,140 Et d'anticiper cela. 878 00:31:51,140 --> 00:31:54,860 À l'extrême gauche, ce petit gars va à échanger sur le côté, et ce 879 00:31:54,860 --> 00:31:56,010 processus se répète. 880 00:31:56,010 --> 00:31:59,450 Maintenant, cette visualisation devient rapidement ennuyeux, alors laissez-moi aller de l'avant et arrêter 881 00:31:59,450 --> 00:32:04,170 , changer le retard quelque chose de beaucoup plus rapide juste pour obtenir maintenant, une idée de 882 00:32:04,170 --> 00:32:05,060 cet algorithme. 883 00:32:05,060 --> 00:32:07,840 >> Donc, même si je n'ai SPEd it up, c'est comme passer mon processeur, l'achat 884 00:32:07,840 --> 00:32:08,580 un nouvel ordinateur. 885 00:32:08,580 --> 00:32:12,980 Je n'ai pas fondamentalement changé ma algorithme, mais vous pouvez en effet voir plus 886 00:32:12,980 --> 00:32:16,800 clairement qu'avec des humains, que le grand numéros bouillonnent vers le haut, 887 00:32:16,800 --> 00:32:20,900 et le petit nombre bouillonnent vers le bas. 888 00:32:20,900 --> 00:32:22,390 Et maintenant cette chose ici triée. 889 00:32:22,390 --> 00:32:25,260 Et en passant, sur les places, il ya juste un peu de comptabilité là pour 890 00:32:25,260 --> 00:32:28,010 vous aider à compter le nombre de comparaisons, ou combien de swaps ont 891 00:32:28,010 --> 00:32:28,950 effectivement été fait. 892 00:32:28,950 --> 00:32:30,750 >> Eh bien, nous allons essayer l'un des les autres que nous avons vu. 893 00:32:30,750 --> 00:32:37,116 Permettez-moi clique sur sorte de bulle ici, et Permettez-moi à choisir, et cette page Web entière 894 00:32:37,116 --> 00:32:38,936 est un peu buggé. 895 00:32:38,936 --> 00:32:41,155 Nous allons accepter le risque et le relancer. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Nous y voilà. 898 00:32:45,030 --> 00:32:47,180 Alors, faisons sélection sorte. 899 00:32:47,180 --> 00:32:49,140 Je ne sais pas pourquoi le menu apparaît là-bas. 900 00:32:49,140 --> 00:32:54,070 Prenons un zoom avant pour résoudre ce problème bug, changer cela en 50. 901 00:32:54,070 --> 00:32:56,020 Ah, nous allons faire en fait beaucoup plus rapidement. 902 00:32:56,020 --> 00:32:59,160 Cinq millisecondes ou plus, et le démarrer. 903 00:32:59,160 --> 00:33:00,470 >> Donc, c'est la sélection sorte. 904 00:33:00,470 --> 00:33:03,070 Encore une fois, pensez à ce que nous fait avec les humains ici. 905 00:33:03,070 --> 00:33:08,490 Nous sommes allés dans le tableau et sélectionné le plus petit élément nouveau, 906 00:33:08,490 --> 00:33:09,250 et encore, et encore. 907 00:33:09,250 --> 00:33:11,110 Je prétends maintenant que c'était encore assez mauvais. 908 00:33:11,110 --> 00:33:15,010 Il était encore sur n carré, donner ou prendre, mais il était, dans le monde réel, un peu 909 00:33:15,010 --> 00:33:18,280 plus rapide, parce que je prends en effet légèrement moins pas à chaque fois. 910 00:33:18,280 --> 00:33:19,800 Mais nous ne parlons quoi? 911 00:33:19,800 --> 00:33:21,830 Peut-être 40 ou si les bars ici? 912 00:33:21,830 --> 00:33:23,200 Nous ne parlons pas 40 millions. 913 00:33:23,200 --> 00:33:27,430 Donc, il n'est pas totalement clair pour moi que était en effet un gain significatif. 914 00:33:27,430 --> 00:33:32,530 >> Permettez-moi maintenant de revenir en arrière et changer à notre troisième algorithme, qui a été sélectionnez 915 00:33:32,530 --> 00:33:33,180 le tri par insertion. 916 00:33:33,180 --> 00:33:36,380 Et maintenant c'est vraiment buggé parce que le menu devrait vraiment pas être là-bas. 917 00:33:36,380 --> 00:33:40,840 Alors maintenant, nous allons revenir en arrière ici et commencer à cet algorithme. 918 00:33:40,840 --> 00:33:43,270 Whoop, démarrer et arrêter. 919 00:33:43,270 --> 00:33:47,160 Alors celui-ci sorte de a un joli motif pour cela, par lequel nous sommes à nouveau 920 00:33:47,160 --> 00:33:50,240 l'insertion, les humains, ou en ce cas, les barres en 921 00:33:50,240 --> 00:33:52,620 leur emplacement approprié. 922 00:33:52,620 --> 00:33:55,430 Et il l'a déjà fait avant Je me suis retourné. 923 00:33:55,430 --> 00:33:58,940 Mais celui-ci, aussi, en théorie, n est encore au carré. 924 00:33:58,940 --> 00:34:01,430 >> Donc, nous allons voir si nous ne pouvons pas résumer ceux-ci comme suit. 925 00:34:01,430 --> 00:34:04,750 Je vais aller de l'avant et juste pour donner nous une sorte de façon commune de parler 926 00:34:04,750 --> 00:34:08,489 à propos de ces choses, permettez-moi de vous présenter juste un peu de notation ici. 927 00:34:08,489 --> 00:34:12,480 Vous êtes sur le point de voir quelque chose appelé grand O, parce que c'est littéralement un grand 928 00:34:12,480 --> 00:34:16,320 O. Et c'est une façon qu'un ordinateur scientifique ou un mathématicien utilise même 929 00:34:16,320 --> 00:34:19,230 pour décrire le temps d'exécution d'un algorithme. 930 00:34:19,230 --> 00:34:21,400 Combien d'étapes faut-il réellement prendre? 931 00:34:21,400 --> 00:34:25,080 >> Maintenant, je vais me mettre dans l'embarras avec mon écriture ici dans un instant. 932 00:34:25,080 --> 00:34:29,020 Mais permettez-moi d'aller de l'avant et dire que ce sera grand O ici. 933 00:34:29,020 --> 00:34:33,610 Et permettez-moi de vous présenter un autre symbole, un oméga de capital. 934 00:34:33,610 --> 00:34:37,080 Omega va être le contraire, essentiellement, de la grande O. considérant grand O 935 00:34:37,080 --> 00:34:40,790 moyens, dans le pire des cas, combien de temps pourrait un algorithme prendre, 936 00:34:40,790 --> 00:34:43,480 fonction de n, oméga va être combien de temps pourrait-il 937 00:34:43,480 --> 00:34:45,409 prendre dans le meilleur des cas. 938 00:34:45,409 --> 00:34:48,090 Et nous verrons ce que nous entendons par meilleur des cas, dans un instant. 939 00:34:48,090 --> 00:34:49,940 >> Commençons donc quelque chose de simple. 940 00:34:49,940 --> 00:34:54,719 Permettez-moi de commencer par une recherche linéaire. 941 00:34:54,719 --> 00:34:55,679 Donc, pas de tri. 942 00:34:55,679 --> 00:34:58,000 Nous appelons cette recherche linéaire. 943 00:34:58,000 --> 00:35:01,140 Et maintenant, faire un peu d' tableau de là. 944 00:35:01,140 --> 00:35:06,600 Et maintenant, dans le cas de la recherche linéaire, dans le pire des cas, le nombre d'étapes est 945 00:35:06,600 --> 00:35:11,770 il va me prendre pour trouver un nombre de choix arbitraire? 946 00:35:11,770 --> 00:35:14,540 Et il ya n portes au total ou le nombre total de n. 947 00:35:14,540 --> 00:35:15,940 Le pire des cas. 948 00:35:15,940 --> 00:35:18,800 Combien d'étapes que je vais devoir prendre pour trouver le numéro 50 dans un tableau 949 00:35:18,800 --> 00:35:20,830 de n portes? 950 00:35:20,830 --> 00:35:21,410 Et pourquoi? 951 00:35:21,410 --> 00:35:23,680 Car il pourrait être tout le manière plus sur la fin. 952 00:35:23,680 --> 00:35:27,120 Alors, un peu comme Jennifer a rencontré, le numéro 50 était tout le chemin, donc dans 953 00:35:27,120 --> 00:35:30,760 le pire des cas, la recherche linéaire est grand O de n, on va dire. 954 00:35:30,760 --> 00:35:33,430 >> Qu'en est-il le meilleur des cas, si vous avez vraiment de la chance? 955 00:35:33,430 --> 00:35:36,200 Il va juste faire un pas, ou un nombre constant d'étapes. 956 00:35:36,200 --> 00:35:37,830 Nous allons donc décrire que comme 1. 957 00:35:37,830 --> 00:35:39,010 Donc, c'est très bon. 958 00:35:39,010 --> 00:35:41,210 Maintenant, si nous avons fait quelque chose comme la recherche binaire? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Recherche donc binaire, dans le pire cas, a pris combien de temps? 961 00:35:47,846 --> 00:35:49,250 >> [Interposition VOIX] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. Malan: Donc en fait, je entendu à quelques endroits. 963 00:35:51,310 --> 00:35:56,390 Donc, c'est en fait log n, donner ou prendre, parce que nous divisons la liste de moitié 964 00:35:56,390 --> 00:36:00,730 encore, et encore, et encore, nous sommes en mesure à trouver, en fin de compte, la valeur, 965 00:36:00,730 --> 00:36:04,750 si elle est là, mais il ya un hic. 966 00:36:04,750 --> 00:36:08,590 Quel est le principe que nous devons tenir pour acquis pour la recherche binaire? 967 00:36:08,590 --> 00:36:09,700 Il doit être trié. 968 00:36:09,700 --> 00:36:12,770 Ce n'est pas triée, vous pouvez diviser la chose dans la moitié encore et encore, et vous 969 00:36:12,770 --> 00:36:15,490 peuvent aller à gauche, et vous pouvez aller à droite, et vous pouvez aller à gauche et à droite, mais vous êtes 970 00:36:15,490 --> 00:36:18,070 ne va pas à trouver l'élément si la liste n'est pas triée, parce que 971 00:36:18,070 --> 00:36:18,790 vous pourriez le manquer. 972 00:36:18,790 --> 00:36:22,120 Parce que votre heuristique, pour aller à gauche ou à droite va être faussée si c'est 973 00:36:22,120 --> 00:36:23,420 en effet non trié. 974 00:36:23,420 --> 00:36:26,110 Il ya donc une sorte de coût caché d'utiliser quelque chose comme ça. 975 00:36:26,110 --> 00:36:29,250 >> Maintenant, passons à notre tri algorithmes ne recherche - 976 00:36:29,250 --> 00:36:31,140 Oh, en fait, allons dans ce vide. 977 00:36:31,140 --> 00:36:33,190 recherche binaire dans le meilleur des cas? 978 00:36:33,190 --> 00:36:36,290 C'est également 1 si elle se trouve être au beau milieu de la baie, ou 979 00:36:36,290 --> 00:36:37,810 au milieu de l'annuaire téléphonique. 980 00:36:37,810 --> 00:36:39,710 Maintenant, nous allons faire sorte de bulle. 981 00:36:39,710 --> 00:36:42,570 Encore une fois, maintenant, nous entrons dans l' sortes, et pas les recherches. 982 00:36:42,570 --> 00:36:47,220 >> Dans le pire des cas, combien d'étapes avons-nous réclamation sorte de bulle va prendre? 983 00:36:47,220 --> 00:36:48,410 n au carré. 984 00:36:48,410 --> 00:36:49,200 Donc, je vais faire ça. 985 00:36:49,200 --> 00:36:51,710 Oh, mon écriture est encore pire quand il est prévu que les gros. 986 00:36:51,710 --> 00:36:52,510 Très bien. 987 00:36:52,510 --> 00:36:53,570 Donc, c'est yan carré. 988 00:36:53,570 --> 00:36:59,460 Et dans le meilleur des cas, de sorte de bulle, combien d'étapes que ça va prendre? 989 00:36:59,460 --> 00:37:00,980 1, j'ai entendu. 990 00:37:00,980 --> 00:37:01,760 >> INTERLOCUTEUR 1: n. 991 00:37:01,760 --> 00:37:03,286 >> DAVID J. Malan: n, j'ai entendu. 992 00:37:03,286 --> 00:37:04,200 >> INTERLOCUTEUR 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> DAVID J. Malan: 2, j'ai entendu. 994 00:37:05,010 --> 00:37:06,670 Dois-je entendre 3? 995 00:37:06,670 --> 00:37:07,080 Très bien. 996 00:37:07,080 --> 00:37:11,390 Alors j'ai entendu 1, n, 2, mais Reprenons en dehors d'au moins la première de celles 997 00:37:11,390 --> 00:37:12,330 suggestions, 1. 998 00:37:12,330 --> 00:37:15,370 Ce n'est pas un mauvais instinct, car il genre de suit un modèle ici. 999 00:37:15,370 --> 00:37:19,670 Mais si cela ne prend que 1 étape, comment dans le monde pourrais-je prétendre que la liste 1000 00:37:19,670 --> 00:37:22,900 est trié, parce que si je suis seulement permis de prendre 1 étape, combien d'éléments 1001 00:37:22,900 --> 00:37:25,230 pourrais-je fait vérifier pour être sûr? 1002 00:37:25,230 --> 00:37:28,270 Eh bien, 1, ce qui signifie qu'il ya n moins 1 des éléments qui pourraient être hors de 1003 00:37:28,270 --> 00:37:31,310 ordre, et je vais sur la foi après consultant d'une élément sur lequel l' 1004 00:37:31,310 --> 00:37:31,850 chose est triée. 1005 00:37:31,850 --> 00:37:33,930 Donc 1 n'est pas correct ici. 1006 00:37:33,930 --> 00:37:35,710 Donc, minimalement, combien de dois-je regarder? 1007 00:37:35,710 --> 00:37:36,680 >> [Interposition VOIX] 1008 00:37:36,680 --> 00:37:40,160 >> DAVID J. Malan: n moins 1, ou vraiment, n, parce que je dois regarder chaque 1009 00:37:40,160 --> 00:37:42,190 élément pour s'assurer que ce n'est pas en panne. 1010 00:37:42,190 --> 00:37:44,750 Mais encore une fois, nous allons sorte de vague notre mains sur les petits chiffres et 1011 00:37:44,750 --> 00:37:47,100 présumons que, en n devient grand, ils sont inintéressant de toute façon. 1012 00:37:47,100 --> 00:37:48,380 C'est donc ce tri à bulles. 1013 00:37:48,380 --> 00:37:49,830 Et maintenant, nous allons faire ces deux derniers. 1014 00:37:49,830 --> 00:37:53,520 Sélection sorte, et puis nous allons faire le tri par insertion. 1015 00:37:53,520 --> 00:37:57,160 Et puis nous allons faire sauter votre esprit avec quelque chose de beaucoup 1016 00:37:57,160 --> 00:37:58,926 mieux que tout cela. 1017 00:37:58,926 --> 00:38:00,410 Très bien. 1018 00:38:00,410 --> 00:38:04,700 >> Quel est le pire des cas en cours d'exécution moment de la sélection sorte? 1019 00:38:04,700 --> 00:38:05,680 >> Intervenant 4: n carré. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. Malan: n carré, j'entends. 1021 00:38:06,710 --> 00:38:09,790 Mais pourquoi n carré, intuitivement? 1022 00:38:09,790 --> 00:38:11,170 >> Intervenant 4: Parce que nous venons de le faire. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. Malan: Parce que nous venons de le faire. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Bonne réponse. 1026 00:38:13,380 --> 00:38:16,660 Mais intuitivement, pourquoi est-sélection Trier carré n? 1027 00:38:16,660 --> 00:38:18,980 Qu'avons nous avons à faire encore et encore? 1028 00:38:18,980 --> 00:38:22,570 Nous devions garder la numérisation à travers, sont vous le plus petit, vous êtes le 1029 00:38:22,570 --> 00:38:24,020 plus petite, êtes-vous la plus petite. 1030 00:38:24,020 --> 00:38:27,480 Et a accordé, nous avons pu prendre n étapes, alors n moins 1, alors n moins 2. 1031 00:38:27,480 --> 00:38:30,700 Mais si vous ajoutez genre de ceux tout en place, ou les prendre sur la foi que j'ai ajouté 1032 00:38:30,700 --> 00:38:34,810 leur place à l'avance, on obtient à peu près n carré moins certains nombres plus petits. 1033 00:38:34,810 --> 00:38:36,730 Donc, je vais appeler ce n carré. 1034 00:38:36,730 --> 00:38:39,530 Mais avec la sélection sorte dans le meilleur cas, combien d'étapes il est 1035 00:38:39,530 --> 00:38:40,632 va me prendre? 1036 00:38:40,632 --> 00:38:41,840 >> ENCEINTE 5: [inaudible] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. Malan: C'est malheureusement toujours n carré, non? 1038 00:38:44,350 --> 00:38:49,590 Parce que si je sélectionne les plus petits élément, et nous avons eu sept personnes ici, 1039 00:38:49,590 --> 00:38:53,280 Je sais seulement que, une fois que j'arrive à la très fin, que j'ai trouvé le plus petit 1040 00:38:53,280 --> 00:38:55,670 nombre, partout où il elle aurait pu. 1041 00:38:55,670 --> 00:38:58,820 Mais comment puis-je trouver le prochain plus petit nombre? 1042 00:38:58,820 --> 00:39:00,160 Je dois faire un autre passage. 1043 00:39:00,160 --> 00:39:04,810 Donc, dans le meilleur des cas, ce qui est le entrée à la sélection sorte? 1044 00:39:04,810 --> 00:39:07,830 Il s'agit d'une liste déjà de tri, numéro un, numéro deux, numéro trois, numéro quatre. 1045 00:39:07,830 --> 00:39:08,600 Mais je suis un ordinateur. 1046 00:39:08,600 --> 00:39:10,190 Je ne peux que regarder un chose à la fois. 1047 00:39:10,190 --> 00:39:12,465 Je ne peux pas trier de franchir une étape arrière comme un humain et dire, 1048 00:39:12,465 --> 00:39:14,030 ooh, cela semble correct. 1049 00:39:14,030 --> 00:39:17,580 >> Je ne peux que juger la justesse dans tri par sélection en sélectionnant l' 1050 00:39:17,580 --> 00:39:18,370 plus petit nombre. 1051 00:39:18,370 --> 00:39:21,390 Mais même si je trouve un nombre premier, si je ne sais rien d'autre sur 1052 00:39:21,390 --> 00:39:24,460 les autres numéros, que je n'ai pas, tout ce que je sais que j'ai remis un tableau 1053 00:39:24,460 --> 00:39:27,930 ou un ensemble de portes qui sont derrière nombres, la seule façon que je sais que l'un 1054 00:39:27,930 --> 00:39:28,680 était la plus petite? 1055 00:39:28,680 --> 00:39:32,440 Si je reçois tout ce chemin et de réaliser, putain, on était en effet le plus petit. 1056 00:39:32,440 --> 00:39:34,870 >> Mais comment puis-je alors déterminer que deux est le plus petit à côté? 1057 00:39:34,870 --> 00:39:38,350 En faisant la même inefficacité encore et encore. 1058 00:39:38,350 --> 00:39:42,210 Donc finalement, avec le tri par insertion, comment, dans le pire des cas, 1059 00:39:42,210 --> 00:39:44,990 avons-nous dit qu'il exécute? 1060 00:39:44,990 --> 00:39:49,100 Elle aussi est n carré. 1061 00:39:49,100 --> 00:39:53,020 Et que diriez-vous avec le meilleur des cas? 1062 00:39:53,020 --> 00:39:56,282 Nous allons laisser cela comme un cliffhanger. 1063 00:39:56,282 --> 00:40:00,090 Nous allons combler cette vierge prochaine fois, mais d'abord, permettez-moi de proposer que nous 1064 00:40:00,090 --> 00:40:02,620 fondamentalement faire mieux que tout cela, tout va bien? 1065 00:40:02,620 --> 00:40:05,220 >> Alors, pensez par vous-même ce que l'insertion Trier ça va être. 1066 00:40:05,220 --> 00:40:06,910 Eh bien, ce n'était pas très spectaculaire, parce que je suis le seul 1067 00:40:06,910 --> 00:40:08,970 qui a vu le changement. 1068 00:40:08,970 --> 00:40:09,620 Wow. 1069 00:40:09,620 --> 00:40:10,420 OK. 1070 00:40:10,420 --> 00:40:12,615 Nous avons donc ici un peu démonstration différente. 1071 00:40:12,615 --> 00:40:16,580 Si je zoome ici, vous verrez que le la gauche, nous avons sorte de bulle, dans la 1072 00:40:16,580 --> 00:40:20,740 milieu nous avons sélection sorte, et sur l'extrême droite, nous avons quelque chose que nous 1073 00:40:20,740 --> 00:40:23,380 n'ont pas encore regardé appelé le tri par fusion. 1074 00:40:23,380 --> 00:40:26,080 Mais considérons ce que nous avons fait ici jusqu'à aujourd'hui. 1075 00:40:26,080 --> 00:40:29,200 Quand Jennifer premier venu sur la scène, nous sommes allés à travers le tableau de nombres 1076 00:40:29,200 --> 00:40:33,750 encore, et encore, avec recherche linéaire, et nous avons eu temps de fonctionnement linéaire, grand O 1077 00:40:33,750 --> 00:40:35,100 de n, pour ainsi dire. 1078 00:40:35,100 --> 00:40:41,000 >> Lorsque l'on considère maintenant la première semaine de classe, quand nous avions diviser et conquérir, 1079 00:40:41,000 --> 00:40:43,740 et nous avions l'annuaire déchirement, et Jennifer, et nous avons collectivement 1080 00:40:43,740 --> 00:40:47,500 effet de levier qui perspicacité clé, qui était de vous répétez encore et encore par 1081 00:40:47,500 --> 00:40:50,930 en quelque sorte jeter, jeter, jeter, la moitié du problème, ou 1082 00:40:50,930 --> 00:40:55,320 généralement, la division d'un problème dans la moitié, puis le traitement du morceau de plus petit 1083 00:40:55,320 --> 00:40:59,630 le problème que conceptuellement équivalente à l'autre, nous avons en quelque sorte 1084 00:40:59,630 --> 00:41:00,910 fondamentalement mieux. 1085 00:41:00,910 --> 00:41:04,720 Mais avec tri à bulles, avec sélection sorte, avec le tri par insertion, nous avons peut 1086 00:41:04,720 --> 00:41:06,560 aucune de ces idées que Jennifer a fait. 1087 00:41:06,560 --> 00:41:10,220 Nous avons assez bien y sommes allés en arrière et de suite tout un tas de fois, et nous 1088 00:41:10,220 --> 00:41:12,650 choses un peu tordu, l'échange dans cet ordre, peut-être 1089 00:41:12,650 --> 00:41:13,730 l'insertion ou la sélection. 1090 00:41:13,730 --> 00:41:16,950 Mais à la fin de la journée, j'ai fait beaucoup de la marche maladroite en arrière. 1091 00:41:16,950 --> 00:41:21,160 Nous n'avons pas vraiment tirer parti de quelque chose intelligent comme Jennifer aimé division 1092 00:41:21,160 --> 00:41:22,040 et conquérante. 1093 00:41:22,040 --> 00:41:25,620 >> Donc, le tri par fusion, en revanche, que nous ne verra pas avant la semaine prochaine, ça va 1094 00:41:25,620 --> 00:41:29,540 tirer parti de cette idée clé en divisant l'entrée, puis réduire de moitié, puis 1095 00:41:29,540 --> 00:41:30,580 réduire de moitié, puis réduire de moitié. 1096 00:41:30,580 --> 00:41:34,590 Et à chaque itération de la boucle, le tri de la moitié gauche et la droite 1097 00:41:34,590 --> 00:41:38,200 la moitié, puis la moitié gauche de la moitié gauche, et la moitié droite de la gauche, puis 1098 00:41:38,200 --> 00:41:40,990 la moitié gauche de la moitié droite, et la moitié droite de la partie droite. 1099 00:41:40,990 --> 00:41:42,840 Et répéter encore et encore. 1100 00:41:42,840 --> 00:41:46,170 >> Vous verrez donc cela visuellement, mais cette est ce qui nous attend la semaine prochaine. 1101 00:41:46,170 --> 00:41:49,760 Et en général, quand on pense un peu peu plus difficile sur un tel problème. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Nous avons n carré sur la gauche, n carré au milieu, et n 1104 00:41:57,970 --> 00:41:59,400 log n sur la droite. 1105 00:41:59,400 --> 00:42:00,590 Il ya donc votre véritable cliffhanger. 1106 00:42:00,590 --> 00:42:02,040 Nous vous verrons lundi. 1107 00:42:02,040 --> 00:42:05,163 >> [Applaudissements]