1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [Jouer de la musique] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. Malan: Ceci est CS50. 5 00:00:12,550 --> 00:00:14,612 Et ceci est le début de trois semaines. 6 00:00:14,612 --> 00:00:16,820 Donc, nous avons beaucoup d'exciter choses à couvrent aujourd'hui. 7 00:00:16,820 --> 00:00:20,160 Un grand nombre de possibilités pour bénévoles sur scène. 8 00:00:20,160 --> 00:00:22,780 Et en fin de compte, est aujourd'hui pas sur le code du tout. 9 00:00:22,780 --> 00:00:24,820 Mais il est des idées, et il est sur les algorithmes, 10 00:00:24,820 --> 00:00:28,420 et effectivement ramener quelques-uns des les leçons tirées de la semaine zéro, 11 00:00:28,420 --> 00:00:31,910 dans lequel le rappel, nous introduit cette monstruosité. 12 00:00:31,910 --> 00:00:33,880 Et emprunts d'inspiration à partir de cela, pour démarrer 13 00:00:33,880 --> 00:00:36,879 pour résoudre de plus en plus sophistiquée problèmes algorithmique. 14 00:00:36,879 --> 00:00:38,420 Mais d'abord, quelques annonces. 15 00:00:38,420 --> 00:00:42,020 Donc un, si vous souhaitez rejoindre Le personnel et les camarades de classe de CS50 au déjeuner 16 00:00:42,020 --> 00:00:44,670 ce vendredi, à la fois ici et dans Cambridge, et à New Haven, 17 00:00:44,670 --> 00:00:48,060 s'il vous plaît visitez le cours de site Web, où une URL peut être trouvée. 18 00:00:48,060 --> 00:00:50,390 Lecture de ce mercredi sera ne pas être ici à Sanders. 19 00:00:50,390 --> 00:00:53,610 Il sera en ligne seulement, de sorte syntoniser sur le site de CS50, 20 00:00:53,610 --> 00:00:55,850 que ce soit ici à Cambridge ou New Haven ainsi. 21 00:00:55,850 --> 00:00:58,110 >> Et puis, problème réglé deux est déjà dans vos mains. 22 00:00:58,110 --> 00:01:03,067 Si vous ne l'avez pas encore plongé, permettez-moi à offrir la suggestion très ferme 23 00:01:03,067 --> 00:01:05,150 que, surtout maintenant, en tant que le problème définit l'avance, 24 00:01:05,150 --> 00:01:08,669 vous ne voulez vraiment commencer maintenant, si pas tremper un peu sur le week-end ou avant 25 00:01:08,669 --> 00:01:10,710 quand ils vont d'abord sur Vendredi, parce que vous allez 26 00:01:10,710 --> 00:01:14,380 constatent qu'ils ne sont pas nécessairement obtenir plus longues ou plus difficile par 27 00:01:14,380 --> 00:01:14,950 se. 28 00:01:14,950 --> 00:01:17,575 Je pense que vous verrez que, dans général, ils ont tendance à prendre plus ou moins 29 00:01:17,575 --> 00:01:18,892 autour même laps de temps. 30 00:01:18,892 --> 00:01:20,850 Mais cela dépend certainement sur l'élève, et il 31 00:01:20,850 --> 00:01:22,880 dépend de l'état d'esprit avec lequel vous vous en approchez. 32 00:01:22,880 --> 00:01:24,910 Mais invariablement, vous allez de se heurter à un mur, 33 00:01:24,910 --> 00:01:26,350 et vous allez frapper un bug, et vous êtes juste 34 00:01:26,350 --> 00:01:27,950 ne va pas être en mesure de obtenir sur elle à un moment donné. 35 00:01:27,950 --> 00:01:31,380 Et il est extrêmement précieux de pouvoir de prendre du recul, de revenir le lendemain, 36 00:01:31,380 --> 00:01:35,286 aller à des heures de bureau, post sur CS50 Discutez ou similaire, pour obtenir réellement débloqué. 37 00:01:35,286 --> 00:01:36,160 Alors garde cela en tête. 38 00:01:36,160 --> 00:01:40,830 Début au plus tôt que possible est la meilleure chose que vous pouvez faire. 39 00:01:40,830 --> 00:01:44,160 Alors, voici où nous avons commencé la classe, au cours de la semaine zéro. 40 00:01:44,160 --> 00:01:47,441 Et pouvons-nous obtenir un bénévole ici pour me aider à trouver micros? 41 00:01:47,441 --> 00:01:47,940 D'ACCORD. 42 00:01:47,940 --> 00:01:48,900 Debout déjà. 43 00:01:48,900 --> 00:01:50,080 Allez vers le haut. 44 00:01:50,080 --> 00:01:53,707 Devinez qui est comment il va travailler. 45 00:01:53,707 --> 00:01:54,415 Comment t'appelles tu? 46 00:01:54,415 --> 00:01:55,570 ALAN ESTRADA: Alan Estrada. 47 00:01:55,570 --> 00:01:56,778 DAVID J. Malan: Alan Estrada. 48 00:01:56,778 --> 00:01:57,910 Allez vers le haut. 49 00:01:57,910 --> 00:01:58,619 Enchanté de faire votre connaissance. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Ravi de vous rencontrer. 51 00:01:59,910 --> 00:02:02,772 DAVID J. Malan: Et vous étiez ici avec nous dans la semaine zéro, bien sûr. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: je me trouvais. 53 00:02:03,028 --> 00:02:03,160 J'étais. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. Malan: Pourriez-vous aller de l'avant et trouver pour nous Mike Smith, 55 00:02:05,868 --> 00:02:08,639 aussi vite que tu peux? 56 00:02:08,639 --> 00:02:10,639 Aussi vite que tu peux. 57 00:02:10,639 --> 00:02:13,756 Littéralement déchirer le problème dans la moitié que vous avez besoin. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Um. 59 00:02:15,130 --> 00:02:17,380 DAVID J. Malan: Littéralement déchirer le problème en deux. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN ESTRADA: Oh. 62 00:02:22,083 --> 00:02:22,583 Mm. 63 00:02:22,583 --> 00:02:23,300 Très bien. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. Malan: OK. 65 00:02:23,700 --> 00:02:24,200 Bien. 66 00:02:24,200 --> 00:02:24,701 Merci. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Très bon. 68 00:02:25,700 --> 00:02:26,210 D'ACCORD. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. Malan: Et maintenant, vous avez taillé vers le bas 70 00:02:27,610 --> 00:02:29,320 à la moitié de la taille du problème. 71 00:02:29,320 --> 00:02:31,267 Maintenant, nous en sommes à un quart. 72 00:02:31,267 --> 00:02:33,475 Êtes-vous attentif à de quel côté nous gardons? 73 00:02:33,475 --> 00:02:34,405 >> [Rire] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Oui, je think-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. Malan: Quelle section sommes-nous? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: Silencieux, donc. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. Malan: OK. 78 00:02:39,941 --> 00:02:42,810 Mais Mike Smith va être après Silencieux. 79 00:02:42,810 --> 00:02:44,130 Ainsi-- 80 00:02:44,130 --> 00:02:48,180 >> [Rire] 81 00:02:48,180 --> 00:02:48,742 >> Bien. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Où cherchons-nous? 83 00:02:50,200 --> 00:02:52,049 DAVID J. Malan: Mike Smith. 84 00:02:52,049 --> 00:02:53,090 ALAN ESTRADA: Mike Smith. 85 00:02:53,090 --> 00:02:54,760 DAVID J. Malan: Maintenant, nous sommes dans chirurgicale. 86 00:02:54,760 --> 00:02:57,840 Maintenant, les médecins. 87 00:02:57,840 --> 00:02:58,340 Maintenant-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- Passons avec du vrai. 89 00:02:59,856 --> 00:03:00,370 Real. 90 00:03:00,370 --> 00:03:00,970 >> DAVID J. Malan: Real. 91 00:03:00,970 --> 00:03:01,470 D'ACCORD. 92 00:03:01,470 --> 00:03:03,700 Si vous avez besoin réel. 93 00:03:03,700 --> 00:03:05,250 Maintenant, où est Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: cette façon. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. Malan: Quel chemin? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Attendez. 97 00:03:08,240 --> 00:03:08,790 M de la droite? 98 00:03:08,790 --> 00:03:09,110 Nous avons commencé avec-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. Malan: Ouais. 100 00:03:10,090 --> 00:03:10,650 Ils sont partis. 101 00:03:10,650 --> 00:03:11,430 Tu as raison. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Ouais. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. Malan: Donc Mike ici. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Quoi? 105 00:03:13,990 --> 00:03:14,665 >> [Rire] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Mauvais exemple, les gars. 108 00:03:18,330 --> 00:03:18,830 Pardon. 109 00:03:18,830 --> 00:03:21,610 DAVID J. Malan: Cela vous apprendra vous de sauter de votre chaise. 110 00:03:21,610 --> 00:03:22,318 >> ALAN ESTRADA: Oh. 111 00:03:22,318 --> 00:03:22,890 Oh. 112 00:03:22,890 --> 00:03:23,390 Je vous ai compris. 113 00:03:23,390 --> 00:03:24,670 Je vous ai compris. 114 00:03:24,670 --> 00:03:25,170 Oh. 115 00:03:25,170 --> 00:03:25,669 Oh. 116 00:03:25,669 --> 00:03:26,812 Cette est-- OK, je vous suis. 117 00:03:26,812 --> 00:03:27,520 Smith ici? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. Malan: Smith, je vous remercie. 119 00:03:28,894 --> 00:03:30,535 Je vais donc continuer à chercher jusqu'à Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Oh, oui. 121 00:03:30,790 --> 00:03:31,340 Non non Non. 122 00:03:31,340 --> 00:03:31,600 Oh non. 123 00:03:31,600 --> 00:03:31,940 Ceci est à moi. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. Malan: Oh, vous avez Smith. 125 00:03:32,580 --> 00:03:33,415 D'ACCORD. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Ouais, je Smith a obtenu ici. 127 00:03:34,040 --> 00:03:34,700 Désolé les gars. 128 00:03:34,700 --> 00:03:35,860 Je pensais que nous Michael-- étaient à la recherche pour Michael. 129 00:03:35,860 --> 00:03:36,550 Pardon. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. Malan: Il est OK. 131 00:03:37,550 --> 00:03:39,950 Très bien, maintenant nous sommes dans Paccini and Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini et fils. 133 00:03:41,242 --> 00:03:43,158 DAVID J. Malan: Seulement vous et moi sommes sur cette. 134 00:03:43,158 --> 00:03:44,050 D'ACCORD. 135 00:03:44,050 --> 00:03:45,130 Retrouvez-nous Mike Smith. 136 00:03:45,130 --> 00:03:45,830 Smith. 137 00:03:45,830 --> 00:03:46,310 >> ALAN ESTRADA: Smith. 138 00:03:46,310 --> 00:03:46,750 >> DAVID J. Malan: Smith. 139 00:03:46,750 --> 00:03:47,728 Nous sommes dans la R pour les déchets. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Déchets. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Cela va prendre un certain temps. 143 00:03:52,480 --> 00:03:54,340 >> [Rire] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. Malan: Chaussures. 146 00:03:56,720 --> 00:03:58,080 Nous sommes dans les chaussures. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Maintenant, nous sommes gonna-- 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. Malan: Nice. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: qui-- 150 00:04:01,980 --> 00:04:03,620 [Rire] 151 00:04:03,620 --> 00:04:05,440 Oh, ce qui est excellent. 152 00:04:05,440 --> 00:04:06,910 [Rire] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. Malan: Il est OK. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Oh, ce qui est bon. 156 00:04:11,365 --> 00:04:14,425 Je ne pense pas que je vais avoir des copains SPAT après cela. 157 00:04:14,425 --> 00:04:15,300 DAVID J. Malan: Bon. 158 00:04:15,300 --> 00:04:16,078 Sporting. 159 00:04:16,078 --> 00:04:17,036 ALAN ESTRADA: Sporting. 160 00:04:17,036 --> 00:04:18,668 Um, L, M, N, O, P. 161 00:04:18,668 --> 00:04:19,459 DAVID J. Malan: OK. 162 00:04:19,459 --> 00:04:21,600 Donc, nous allons déchirer cette moitié. 163 00:04:21,600 --> 00:04:22,270 C'est bon. 164 00:04:22,270 --> 00:04:25,606 Cela finit mal de toute façon, parce que Mike Smith ne sera pas dans les pages jaunes. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. Malan: Non, il est OK. 167 00:04:27,140 --> 00:04:28,930 Mais supposons que il est sur cette page. 168 00:04:28,930 --> 00:04:33,260 Alors maintenant, vous avez taillé le problème vers le bas à une page, et nous avons trouvé Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [CHEERING] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 D'accord, merci. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 D'ACCORD. 174 00:04:41,200 --> 00:04:43,646 Ce fut extraordinaire. 175 00:04:43,646 --> 00:04:45,954 Mais il était encore plus rapide de la recherche linéaire, 176 00:04:45,954 --> 00:04:47,870 dans laquelle nous commençons à la début du livre, 177 00:04:47,870 --> 00:04:51,210 et nous passons notre chemin de gauche à droite, éventuellement à la recherche de Mike Smith. 178 00:04:51,210 --> 00:04:53,540 Et donc, si le livre de téléphone avait peut-être de 1000 pages, 179 00:04:53,540 --> 00:04:56,300 peut-être qu'il aurait fallu nous 10 ou si la page des larmes. 180 00:04:56,300 --> 00:04:59,380 >> Mais vous avez peut-être mobilisé touché une hypothèse 181 00:04:59,380 --> 00:05:03,602 Pendant tout ce qui est à dire que le livre de téléphone à l'avance était quoi? 182 00:05:03,602 --> 00:05:04,310 AUDIENCE: Trier. 183 00:05:04,310 --> 00:05:05,000 DAVID J. Malan: Il est triée. 184 00:05:05,000 --> 00:05:05,160 Droit? 185 00:05:05,160 --> 00:05:07,909 Il est triée par ordre alphabétique, de sorte que tous ces noms et numéros 186 00:05:07,909 --> 00:05:11,230 sont triées de la Une de la Z de, et par ordre alphabétique entre les deux. 187 00:05:11,230 --> 00:05:13,100 Mais aujourd'hui, nous demandons maintenant la question, eh bien, 188 00:05:13,100 --> 00:05:16,170 comment avez Verizon ou le téléphone société l'obtenir dans cet état? 189 00:05:16,170 --> 00:05:19,560 >> Parce qu'il est une chose à tirer parti cette hypothèse et, par conséquent, 190 00:05:19,560 --> 00:05:22,570 résoudre un problème avec un algorithme plus efficace. 191 00:05:22,570 --> 00:05:24,900 Mais on n'a jamais vraiment demandé à la semaine zéro, ainsi, 192 00:05:24,900 --> 00:05:27,790 combien ça coûte Verizon ou quelqu'un d'autre 193 00:05:27,790 --> 00:05:29,620 pour obtenir ce livre de téléphone dans l'ordre de tri? 194 00:05:29,620 --> 00:05:29,780 >> Droit? 195 00:05:29,780 --> 00:05:31,529 Il n'a pas d'importance si regardant Mike Smith 196 00:05:31,529 --> 00:05:35,190 est super rapide, si cela vous prend un année pour trier les pages initialement. 197 00:05:35,190 --> 00:05:35,690 Droit? 198 00:05:35,690 --> 00:05:38,620 Vous pourriez tout aussi bien passer au crible à travers un livre de téléphone randomisé, 199 00:05:38,620 --> 00:05:40,690 si ça va être super cher de faire le tri. 200 00:05:40,690 --> 00:05:42,350 Donc, si nous pouvons avoir un autre bénévole. 201 00:05:42,350 --> 00:05:46,350 Prenons un oeil ici à comment nous arrivons sur up-- might-- comment 202 00:05:46,350 --> 00:05:48,100 nous pourrions aller sur le tri-ci. 203 00:05:48,100 --> 00:05:51,990 >> Et si la Jordanie pouvait effectivement rejoignez-nous ici sur scène. 204 00:05:51,990 --> 00:05:55,100 Allez pour un instant. 205 00:05:55,100 --> 00:05:56,359 Comment t'appelles tu? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. Malan: Caroline, venu sur place. 208 00:05:58,691 --> 00:06:02,070 Et vous serez rejoint par moi et la Jordanie ici. 209 00:06:02,070 --> 00:06:03,800 Caroline, je vous remercie. 210 00:06:03,800 --> 00:06:04,300 Bien. 211 00:06:04,300 --> 00:06:08,330 Donc, ce que nous avons ici pour Caroline est de 26 livres bleus 212 00:06:08,330 --> 00:06:10,747 que le SAF utilise pour administrer certains examens finaux. 213 00:06:10,747 --> 00:06:13,330 Ceux-ci deviennent difficiles à trouver, mais ce que nous avons fait à l'avance 214 00:06:13,330 --> 00:06:15,800 est que nous avons mis le nom de quelqu'un sur la face avant de chacun d'eux, 215 00:06:15,800 --> 00:06:18,133 mais nous avons gardé les choses simples en puis éteindre les noms complets. 216 00:06:18,133 --> 00:06:22,720 Nous voudrions donc mettre la personne avec le nom L, D, J, B, tout le chemin de A à Z, 217 00:06:22,720 --> 00:06:24,090 mais ils sont dans un ordre aléatoire. 218 00:06:24,090 --> 00:06:26,890 Et donc si vous voulez, parler votre chemin à travers le problème comme vous 219 00:06:26,890 --> 00:06:31,620 do it, pouvez-vous aller de l'avant et trier ces pour nous, de A à Z. 220 00:06:31,620 --> 00:06:34,070 >> AUDIENCE: OK, alors L est comme, au milieu. 221 00:06:34,070 --> 00:06:35,050 C commence. 222 00:06:35,050 --> 00:06:42,410 B. J avant L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. Malan: Maintenez cette pensé pendant une seconde. 224 00:06:45,140 --> 00:06:48,910 En raison par ailleurs, ceci est seulement intéressant pour vous, moi, et la Jordanie. 225 00:06:48,910 --> 00:06:49,724 Nous y voilà. 226 00:06:49,724 --> 00:06:50,640 AUDIENCE: [inaudible]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 DAVID J. Malan: OK. 229 00:06:58,090 --> 00:06:59,310 Que faites-vous? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M vient après O. 231 00:07:01,730 --> 00:07:02,564 >> DAVID J. Malan: OK. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 DAVID J. Malan: O, Bon. 234 00:07:04,120 --> 00:07:04,970 >> CAROLINE: E. 235 00:07:04,970 --> 00:07:06,730 >> DAVID J. Malan: E, F. Ouais. 236 00:07:06,730 --> 00:07:07,620 >> CAROLINE: T, U, V 237 00:07:07,620 --> 00:07:10,689 >> DAVID J. Malan: V, T, U, V. Donc, il dirait que vous êtes making-- continuer. 238 00:07:10,689 --> 00:07:12,730 Il semble que vous faites un gros tas ici, 239 00:07:12,730 --> 00:07:13,910 et une sorte de grand tas là-bas. 240 00:07:13,910 --> 00:07:16,230 Donc, la première moitié de l'alphabet, deuxième moitié de l'alphabet. 241 00:07:16,230 --> 00:07:16,460 D'ACCORD. 242 00:07:16,460 --> 00:07:16,960 Bien. 243 00:07:16,960 --> 00:07:19,680 Type de scinder le problème en deux. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Ouais. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 DAVID J. Malan: OK. 247 00:07:22,980 --> 00:07:25,070 K. Donc, vous sorte de la sélection les uns après les autres, 248 00:07:25,070 --> 00:07:27,620 mettre à gauche ou à droite, ou Z qui se passe sur le plancher. 249 00:07:27,620 --> 00:07:28,012 D'ACCORD. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z va sur le sol. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. Malan: OK. 252 00:07:29,360 --> 00:07:30,920 Y va sur le sol. 253 00:07:30,920 --> 00:07:31,735 Maintenant, nous pouvons mettre X. 254 00:07:31,735 --> 00:07:32,409 >> CAROLINE: G. 255 00:07:32,409 --> 00:07:33,700 DAVID J. Malan: G va à gauche. 256 00:07:33,700 --> 00:07:36,017 S va droit. 257 00:07:36,017 --> 00:07:37,642 Tout à droite, un va tout le chemin à gauche. 258 00:07:37,642 --> 00:07:38,790 >> CAROLINE: A, B, C, D. 259 00:07:38,790 --> 00:07:39,873 >> DAVID J. Malan: Maintenant, bon. 260 00:07:39,873 --> 00:07:43,260 Nous avons A, B, C. W va là-bas. 261 00:07:43,260 --> 00:07:45,566 Tout droit, T. 262 00:07:45,566 --> 00:07:46,611 >> CAROLINE: H, I, J. 263 00:07:46,611 --> 00:07:47,860 DAVID J. Malan: H, I, J. Good. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: Dans le centre, je gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. Malan: OK. 266 00:07:50,000 --> 00:07:52,375 Alors maintenant, nous allons genre de fusionner ces différentes piles. 267 00:07:52,375 --> 00:08:00,730 Donc A à C, alors je ne vois D, et E, et F, et G, et H, et I. Nice. 268 00:08:00,730 --> 00:08:05,540 J, K. Et puis, cette pile est à l'envers, mais ce est OK. 269 00:08:05,540 --> 00:08:06,040 Bien sûr. 270 00:08:06,040 --> 00:08:07,240 Nous pouvons couper certains coins. 271 00:08:07,240 --> 00:08:07,950 D'ACCORD. 272 00:08:07,950 --> 00:08:10,530 Et puis, nous avons besoin de W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Ouais. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. Malan: Excellent. 275 00:08:11,880 --> 00:08:14,122 Donc un grand merci à Caroline pour le tri-ci. 276 00:08:14,122 --> 00:08:15,030 >> [CHEERING] 277 00:08:15,030 --> 00:08:17,287 >> Merci. 278 00:08:17,287 --> 00:08:18,120 Merci beaucoup. 279 00:08:18,120 --> 00:08:22,910 Alors maintenant, nous allons examiner un instant comment Caroline a passé en faisant cela, 280 00:08:22,910 --> 00:08:26,040 et exactement ce que nous avons ont pu to-- comment nous 281 00:08:26,040 --> 00:08:28,409 ont réussi à résoudre que problème lorsque nous étions juste 282 00:08:28,409 --> 00:08:29,950 étant donné tout un tas de données aléatoires. 283 00:08:29,950 --> 00:08:31,610 >> Eh bien, il semble qu'il y était un peu d'un système là-bas? 284 00:08:31,610 --> 00:08:32,110 Droit. 285 00:08:32,110 --> 00:08:34,495 Ainsi, les premières lettres dans l'alphabet, elle 286 00:08:34,495 --> 00:08:37,120 est mise à la gauche, et la dernières lettres de l'alphabet, 287 00:08:37,120 --> 00:08:38,270 elle mettait dans le droit. 288 00:08:38,270 --> 00:08:40,500 Et dès qu'elle a trouvé quelques lettres proximales, ceux 289 00:08:40,500 --> 00:08:43,124 qui vont juste à côté de l'autre, elle mettrait ceux dans l'ordre. 290 00:08:43,124 --> 00:08:46,750 Et donc nous avons eu ces genre de petite tas d'entrées triées survenus. 291 00:08:46,750 --> 00:08:50,540 >> Et voilà tout à fait comme ce que la plupart d'entre nous les humains feraient. 292 00:08:50,540 --> 00:08:53,530 Nous sorte de passer au crible, et nous aimerions sorte de avons un mécanisme. 293 00:08:53,530 --> 00:08:56,930 Mais il pourrait être difficile d'écrire vers le bas dans une formule en soi. 294 00:08:56,930 --> 00:08:59,010 Il se sentait un peu plus organique que cela. 295 00:08:59,010 --> 00:09:02,560 Donc, nous allons voir si nous pouvons désormais liés le problème avec moins d'intrants. 296 00:09:02,560 --> 00:09:05,170 >> Au lieu de 26, nous allons faire quelque chose de beaucoup moins 297 00:09:05,170 --> 00:09:09,890 avec juste dire sept, derrière ces portes, pour ainsi dire. 298 00:09:09,890 --> 00:09:11,300 Y at-il seulement sept chiffres? 299 00:09:11,300 --> 00:09:15,240 Et si l'objectif maintenant à la main est de trouver une valeur, 300 00:09:15,240 --> 00:09:17,850 nous allons voir comment efficacement nous pouvons le faire de manière. 301 00:09:17,850 --> 00:09:22,460 Et nous allons voir si nous pouvons maintenant commencer à appliquer certains numéros, 302 00:09:22,460 --> 00:09:26,310 ou certaines formules qui pour décrire l'efficacité de notre livre de téléphone 303 00:09:26,310 --> 00:09:31,060 algorithme, notre algorithme de livre de l'examen, et plus généralement, la recherche d'informations. 304 00:09:31,060 --> 00:09:34,770 >> Donc, pour cela, laissez-moi aller de l'avant, et sur l'écran tactile ici, 305 00:09:34,770 --> 00:09:41,100 mettre en place un navigateur web qui a exactement ces sept portes. 306 00:09:41,100 --> 00:09:46,670 Et si nous pouvions obtenir un autre volontaire de venir par ici, 307 00:09:46,670 --> 00:09:48,480 Je l'ai mis ces mêmes portes ici. 308 00:09:48,480 --> 00:09:49,170 Bénévole rapide. 309 00:09:49,170 --> 00:09:51,130 >> Cette démos vont plus appréciées --choisissez-- à un moment plus en plus vite. 310 00:09:51,130 --> 00:09:51,600 Venez faire un tour. 311 00:09:51,600 --> 00:09:52,308 Comment t'appelles tu? 312 00:09:52,308 --> 00:09:53,040 TREVOR: Trevor. 313 00:09:53,040 --> 00:09:53,998 >> DAVID J. Malan: Trevor? 314 00:09:53,998 --> 00:09:55,770 Tout droit, Trevor, allez vers le bas. 315 00:09:55,770 --> 00:09:59,212 Donc, Trevor a fait du bénévolat ici pour faire un problème similaire, mais celui qui est 316 00:09:59,212 --> 00:10:02,170 une portée plus restreinte, et que ça va pour nous permettre d'essayer de formaliser maintenant 317 00:10:02,170 --> 00:10:03,970 le processus pour le tri de ces chiffres. 318 00:10:03,970 --> 00:10:05,500 >> Donc, Trevor, agréable de vous rencontrer. 319 00:10:05,500 --> 00:10:08,720 Donc, voici un tableau, pour ainsi parler, une liste de sept portes. 320 00:10:08,720 --> 00:10:10,327 Allez-y et nous trouver le numéro 50. 321 00:10:10,327 --> 00:10:12,410 Et puis après le fait, nous dire comment vous l'avez trouvé. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Devrait être: tout droit. 324 00:10:20,040 --> 00:10:21,945 Oui, ceci est une ici? 325 00:10:21,945 --> 00:10:24,680 Uh-oh. 326 00:10:24,680 --> 00:10:25,560 D'ACCORD. 327 00:10:25,560 --> 00:10:26,680 Vous avez cliqué sur celui-là. 328 00:10:26,680 --> 00:10:28,690 Bien. 329 00:10:28,690 --> 00:10:29,780 >> Et bien. 330 00:10:29,780 --> 00:10:30,970 Maintenant vous avez cliqué sur celui-là. 331 00:10:30,970 --> 00:10:34,060 Et permettez-moi de vous donner le micro, de sorte que vous avez dans un instant. 332 00:10:34,060 --> 00:10:37,000 Allez-y et cliquez sur le côté que vous avez l'intention. 333 00:10:37,000 --> 00:10:39,812 Oui bien. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Puis-je décocher une porte? 335 00:10:41,020 --> 00:10:42,620 DAVID J. Malan: Non, vous ne pouvez pas décocher. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Celui-ci. 338 00:10:43,974 --> 00:10:45,640 DAVID J. Malan: Où voulez-vous aller? 339 00:10:45,640 --> 00:10:46,410 Lequel? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: Celui-là. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. Malan: Non 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: OK. 343 00:10:48,450 --> 00:10:48,735 Celui-ci. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. Malan: Oui. 345 00:10:49,020 --> 00:10:49,700 C'était bien. 346 00:10:49,700 --> 00:10:50,380 Bien. 347 00:10:50,380 --> 00:10:53,900 Alors quel était votre algorithme ou procédure pour ce faire, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Je vient de traverser portes jusqu'à ce que je trouve un 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. Malan: OK. 350 00:10:56,940 --> 00:10:58,150 Excellente algorithme. 351 00:10:58,150 --> 00:10:59,540 Donc ça va. 352 00:10:59,540 --> 00:11:03,120 Car en fait, si je révèle ce qui est derrière ces deux autres portes, ce qui 353 00:11:03,120 --> 00:11:06,954 nous trouverons ici est que nous avons seulement entrée aléatoire. 354 00:11:06,954 --> 00:11:08,870 Donc, qui était en réalité aussi bien que vous pourriez obtenir. 355 00:11:08,870 --> 00:11:12,509 Et en fait, vous avez mieux que recherche exhaustive la totalité du tableau, 356 00:11:12,509 --> 00:11:15,300 parce qu'il aurait été vraiment malchanceux si vous aviez frappé le nombre 357 00:11:15,300 --> 00:11:16,604 50 à la dernière porte. 358 00:11:16,604 --> 00:11:18,520 Mais que faire si nous avons la place vous a donné une hypothèse. 359 00:11:18,520 --> 00:11:20,630 Supposons que je sorte tout ces portes autour, 360 00:11:20,630 --> 00:11:23,500 de sorte que vous avez la numéros triées cette fois, 361 00:11:23,500 --> 00:11:29,730 mais cette fois il est fait un different-- cette fois, 362 00:11:29,730 --> 00:11:32,640 il est effectivement triés pour vous. 363 00:11:32,640 --> 00:11:35,380 Et maintenant, l'objectif à portée de main est de frapper le numéro 50. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. Malan: Quelle est votre algorithme va être? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: Eh bien, si elle est trié, il est soit aller 367 00:11:39,628 --> 00:11:42,710 à être-- si grand au plus grand, décroissant, ça va être le premier, 368 00:11:42,710 --> 00:11:44,751 ou si elle est le contraire, ce sera la dernière. 369 00:11:44,751 --> 00:11:48,897 Alors je vais vous suffit de toucher cette porte, et puis appuyez simplement sur la dernière porte. 370 00:11:48,897 --> 00:11:49,980 DAVID J. Malan: Excellent. 371 00:11:49,980 --> 00:11:50,270 Bien. 372 00:11:50,270 --> 00:11:51,150 Donc, nous avons trouvé le numéro 50. 373 00:11:51,150 --> 00:11:52,970 Donc dès que vous saviez ils ont été triés, nous 374 00:11:52,970 --> 00:11:55,040 ont été en mesure de tirer parti de cette hypothèse. 375 00:11:55,040 --> 00:11:57,040 Donc, ils sont trop comme l'exemple du livre de téléphone. 376 00:11:57,040 --> 00:11:59,540 Dès que vous avez, même avec un petit problème de ce genre, 377 00:11:59,540 --> 00:12:02,380 vos entrées pré-triés, nous pouvons effectivement trouver la valeur sans doute 378 00:12:02,380 --> 00:12:03,130 plus efficacement. 379 00:12:03,130 --> 00:12:05,800 >> Et je ne vous ai pas si elle était dis triés petite à grande, ou grand au plus petit, 380 00:12:05,800 --> 00:12:08,080 et il était donc très raisonnable à commencer à une extrémité ou l'autre 381 00:12:08,080 --> 00:12:09,750 pour trouver effectivement cette valeur cible. 382 00:12:09,750 --> 00:12:11,400 Donc merci à Trevor ainsi. 383 00:12:11,400 --> 00:12:13,260 Et je vais propose-- bien fait. 384 00:12:13,260 --> 00:12:16,960 Nous avons un petit clip, en fait, que est parmi nos moments préférés dans CS50, 385 00:12:16,960 --> 00:12:19,700 lequel, parfois, ces démos ne vont pas tout à fait comme prévu. 386 00:12:19,700 --> 00:12:22,050 Et en effet, en ce moment, je tiré vers le haut de la mauvaise interface 387 00:12:22,050 --> 00:12:23,508 avec laquelle d'utiliser l'écran tactile. 388 00:12:23,508 --> 00:12:24,660 Donc, qui était de ma faute il. 389 00:12:24,660 --> 00:12:26,600 >> Donc, ce sera pour faire le clip de l'année prochaine, 390 00:12:26,600 --> 00:12:28,570 pourquoi je suis en cliquant sur mon propre écran. 391 00:12:28,570 --> 00:12:31,390 Mais jetons un rapide coup d'oeil à ce qui est arrivé l'année dernière 392 00:12:31,390 --> 00:12:34,770 avec Jay, qui est venu, beaucoup Trevor comme ici, volontaire, 393 00:12:34,770 --> 00:12:39,380 et dans ce court clip, vous verrez comment cette même démo n'a pas tout 394 00:12:39,380 --> 00:12:41,074 révéler les mêmes leçons apprises. 395 00:12:41,074 --> 00:12:41,740 [LECTURE VIDÉO] 396 00:12:41,740 --> 00:12:45,360 -Tous Je veux que vous faites maintenant est à trouver pour moi, et pour nous, 397 00:12:45,360 --> 00:12:51,674 vraiment, le nombre 50 un pas à la fois. 398 00:12:51,674 --> 00:12:52,450 >> -Le Nombre 50? 399 00:12:52,450 --> 00:12:53,190 >> -Le Nombre de 50. 400 00:12:53,190 --> 00:12:55,356 Et vous pouvez révéler ce qui est derrière chacune de ces portes 401 00:12:55,356 --> 00:12:58,540 tout simplement en le touchant avec un doigt. 402 00:12:58,540 --> 00:13:00,910 Bon sang. 403 00:13:00,910 --> 00:13:02,870 >> [Rire] 404 00:13:02,870 --> 00:13:03,806 >> [FIN LECTURE] 405 00:13:03,806 --> 00:13:05,430 DAVID J. Malan: Alors qui va très bien. 406 00:13:05,430 --> 00:13:06,796 Ce sont les portes non triés. 407 00:13:06,796 --> 00:13:08,670 Et Jay, bien sûr, trouvé trop vite. 408 00:13:08,670 --> 00:13:12,910 Trevor a fait un bien meilleur travail en termes d'un moment enseignable, 409 00:13:12,910 --> 00:13:15,850 pour ainsi dire, cette année prendre plus de temps pour le trouver. 410 00:13:15,850 --> 00:13:17,950 Bien sûr, nous avons Jay une deuxième chance, 411 00:13:17,950 --> 00:13:20,320 lequel nous avons trié les portes, tout comme nous l'avons fait pour Trevor, 412 00:13:20,320 --> 00:13:22,300 et Trevor a fait super bien passé cette fois. 413 00:13:22,300 --> 00:13:26,124 Mais Jay l'a fait deux fois moins vite. 414 00:13:26,124 --> 00:13:26,790 [LECTURE VIDÉO] 415 00:13:26,790 --> 00:13:29,650 -Le Objectif est maintenant d'aussi nous trouver le numéro 50, 416 00:13:29,650 --> 00:13:33,030 mais le faire de façon algorithmique, et nous dire comment vous allez à ce sujet. 417 00:13:33,030 --> 00:13:33,660 >> -D'ACCORD. 418 00:13:33,660 --> 00:13:35,604 >> -Et Si vous le trouvez, vous gardez le film. 419 00:13:35,604 --> 00:13:37,228 Si vous ne le trouvez pas, vous lui donnez de retour. 420 00:13:37,228 --> 00:13:38,044 >> -Man. 421 00:13:38,044 --> 00:13:38,860 >> Oh! 422 00:13:38,860 --> 00:13:40,800 >> - [Inaudible] OK. 423 00:13:40,800 --> 00:13:46,236 Donc, je vais vérifier les extrémités d'abord déterminer si there's-- Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Applaudissements] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [FIN LECTURE] 427 00:13:55,729 --> 00:13:56,520 DAVID J. Malan: OK. 428 00:13:56,520 --> 00:13:59,760 Donc, le tri des portes clairement conduit à une plus grande efficacité. 429 00:13:59,760 --> 00:14:01,680 Et oui, deux fois plus rapide est ce que je voulais dire il. 430 00:14:01,680 --> 00:14:03,270 Et Jay eu de la chance les deux fois. 431 00:14:03,270 --> 00:14:06,685 Et il a aussi eu de la chance dans ce dernier année, je commandé des disques Blu-ray 432 00:14:06,685 --> 00:14:07,560 pour donner en fait sortir. 433 00:14:07,560 --> 00:14:09,768 Je suis désolé de cette année, nous n'a pas eu le même, Trevor. 434 00:14:09,768 --> 00:14:11,540 Mais mieux encore était il ya quelques années. 435 00:14:11,540 --> 00:14:14,820 Et certains d'entre vous le savent garçon, Sean, qui quand il était dans CS50, 436 00:14:14,820 --> 00:14:17,780 a été contestée avec l'exacte même problème, mais en SD, 437 00:14:17,780 --> 00:14:19,360 comme vous le verrez bientôt, retour dans la journée. 438 00:14:19,360 --> 00:14:22,622 Et vous verrez que non seulement fait il prend un peu plus longtemps que Jay, 439 00:14:22,622 --> 00:14:25,580 un peu plus de Trevor, il était effectivement cette merveilleuse occasion 440 00:14:25,580 --> 00:14:29,820 pour engager presque tout le monde dans le foule à la Price is Right, encourageant 441 00:14:29,820 --> 00:14:31,889 lui de trouver le nombre que nous cherchions. 442 00:14:31,889 --> 00:14:32,930 Voyons. jeter un regard rapide. 443 00:14:32,930 --> 00:14:33,320 >> [LECTURE VIDÉO] 444 00:14:33,320 --> 00:14:33,820 >> -D'ACCORD. 445 00:14:33,820 --> 00:14:36,680 Donc votre tâche ici, Sean, est le suivant. 446 00:14:36,680 --> 00:14:40,860 Je l'ai caché derrière ces portes le nombre de sept. 447 00:14:40,860 --> 00:14:45,120 Mais caché dans certaines de ces portes ainsi sont les autres nombres négatifs. 448 00:14:45,120 --> 00:14:47,500 Et votre but est de penser de cette ligne haut de numéros 449 00:14:47,500 --> 00:14:50,390 comme juste un tableau, ou tout simplement séquence de morceaux de papier 450 00:14:50,390 --> 00:14:51,510 avec des chiffres derrière eux. 451 00:14:51,510 --> 00:14:55,540 Et votre but est, en utilisant uniquement le haut tableau ici, me trouver le nombre de sept. 452 00:14:55,540 --> 00:14:58,570 Et nous allons ensuite critiquer comment vous allez le faire. 453 00:14:58,570 --> 00:14:59,070 -Bien. 454 00:14:59,070 --> 00:15:00,850 Nous -Trouver le nombre de sept, s'il vous plaît. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Non. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Cinq, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Rire] 461 00:15:24,770 --> 00:15:25,910 >> Il est pas une question piège. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 One. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Rire] 466 00:15:34,695 --> 00:15:37,861 À ce stade, votre score est pas très bon, alors vous pourriez aussi bien continuer. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Trois. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Rire] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Continue. 473 00:15:47,774 --> 00:15:50,690 Franchement, je ne peux pas aider mais se demander ce que vous même y penser, so-- 474 00:15:50,690 --> 00:15:51,959 >> [Rire] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Seule la rangée du haut, de sorte vous avez trois. 477 00:15:55,020 --> 00:15:56,200 Donc me trouver sept. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Rire] 480 00:16:02,167 --> 00:16:14,870 481 00:16:14,870 --> 00:16:15,370 17. 482 00:16:15,370 --> 00:16:25,675 483 00:16:25,675 --> 00:16:26,946 Sept. 484 00:16:26,946 --> 00:16:28,780 >> [Applaudissements] 485 00:16:28,780 --> 00:16:29,426 >> Bien. 486 00:16:29,426 --> 00:16:30,360 >> [FIN LECTURE] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. Malan: afin que nous puissions regarder ces tout au long de la journée. 488 00:16:31,840 --> 00:16:34,090 Et bien sûr, quelques-uns des Les démos de cette année peut-être 489 00:16:34,090 --> 00:16:36,330 va maintenant se retrouver dans le prochain la vidéo de l'année ainsi. 490 00:16:36,330 --> 00:16:39,040 Alors maintenant, de laisser effectivement mettre l'accent sur les algorithmes 491 00:16:39,040 --> 00:16:42,140 ici, et voir si nous ne pouvons pas maintenant commencer à officialiser 492 00:16:42,140 --> 00:16:46,650 comment nous pouvons prendre pour obtenir nos données dans cet état qu'il est triée, 493 00:16:46,650 --> 00:16:50,054 de sorte que, finalement, nous pouvons réellement rechercher plus efficacement. 494 00:16:50,054 --> 00:16:52,470 Et même si nous allons à utiliser assez petits ensembles de données, 495 00:16:52,470 --> 00:16:54,511 comme le huit chiffres que nous avoir ici sur la carte, 496 00:16:54,511 --> 00:16:58,230 finalement, ces mêmes idées pourraient appliquer 1000 entrées, un million d'entrées, 497 00:16:58,230 --> 00:17:02,100 4 milliards d'entrées, car les algorithmes vont être fondamentalement la même. 498 00:17:02,100 --> 00:17:05,359 >> Et donc cela est notre dernier occasion pour les bénévoles d'aujourd'hui, 499 00:17:05,359 --> 00:17:09,790 mais peut-être le plus impliqué, pour lesquels nous avons besoin de huit volontaires 500 00:17:09,790 --> 00:17:12,960 à venir et de nous guider à travers le processus de tri ce qui sera bientôt 501 00:17:12,960 --> 00:17:15,212 être sur ces Pupitres ici. 502 00:17:15,212 --> 00:17:16,170 Permettez-moi de commencer ici. 503 00:17:16,170 --> 00:17:19,692 >> Donc, une dans le vert turquoise-- est-il? 504 00:17:19,692 --> 00:17:21,130 Vous engagez-vous? 505 00:17:21,130 --> 00:17:21,630 Deux. 506 00:17:21,630 --> 00:17:23,069 Venez faire un tour. 507 00:17:23,069 --> 00:17:23,569 D'ACCORD. 508 00:17:23,569 --> 00:17:24,420 Trois. 509 00:17:24,420 --> 00:17:25,400 Quatre. 510 00:17:25,400 --> 00:17:27,247 Laissez moi-- OK, cinq. 511 00:17:27,247 --> 00:17:28,830 Vous êtes étant désignés par votre ami. 512 00:17:28,830 --> 00:17:31,340 Six, sept, huit. 513 00:17:31,340 --> 00:17:32,130 Allez vers le haut. 514 00:17:32,130 --> 00:17:32,630 Bien. 515 00:17:32,630 --> 00:17:33,190 Merci beaucoup. 516 00:17:33,190 --> 00:17:33,689 Allez vers le haut. 517 00:17:33,689 --> 00:17:34,790 Allez vers le haut. 518 00:17:34,790 --> 00:17:35,330 >> Bien. 519 00:17:35,330 --> 00:17:38,890 Donc, ce que nous avons et ce ici-- est parmi les plus difficiles, 520 00:17:38,890 --> 00:17:42,390 car cela nécessite que vous l'humour moi juste un peu de temps. 521 00:17:42,390 --> 00:17:43,442 Tu seras numéro un. 522 00:17:43,442 --> 00:17:44,150 Comment t'appelles tu? 523 00:17:44,150 --> 00:17:44,610 >> Annan: Annan. 524 00:17:44,610 --> 00:17:45,526 >> DAVID J. Malan: Annan. 525 00:17:45,526 --> 00:17:46,092 David. 526 00:17:46,092 --> 00:17:46,800 Comment t'appelles tu? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. Malan: Joseph, vous êtes numéro deux. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, numéro trois. 530 00:17:52,260 --> 00:17:53,722 Stefan, numéro quatre. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 DAVID J. Malan: Cynthia, numéro cinq. 533 00:17:57,548 --> 00:17:58,452 [Inaudible] 534 00:17:58,452 --> 00:17:59,618 DAVID J. Malan: [inaudible]. 535 00:17:59,618 --> 00:18:00,391 David, le numéro six. 536 00:18:00,391 --> 00:18:00,890 MATT: Matt. 537 00:18:00,890 --> 00:18:02,160 DAVID J. Malan: le numéro de Matt sept. 538 00:18:02,160 --> 00:18:02,850 Et? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. Malan: Waverly, numéro huit. 541 00:18:04,470 --> 00:18:04,970 Bien. 542 00:18:04,970 --> 00:18:06,510 Si vous could-- whoops. 543 00:18:06,510 --> 00:18:08,820 Si vous tous, que votre premier défi, il 544 00:18:08,820 --> 00:18:10,820 sont huit pupitres ici face à l'auditoire. 545 00:18:10,820 --> 00:18:14,200 Si vous pouviez mettre vos numéros sur ces pupitres de telle sorte 546 00:18:14,200 --> 00:18:16,560 qu'ils alignent avec le mêmes numéros sur la carte. 547 00:18:16,560 --> 00:18:19,560 Donc, assurez-vous ressembler à ça par mettre vos numéros sur ces musiques 548 00:18:19,560 --> 00:18:21,960 se tient ici. 549 00:18:21,960 --> 00:18:25,980 Excellente jusqu'ici. 550 00:18:25,980 --> 00:18:26,600 >> Excellente. 551 00:18:26,600 --> 00:18:26,890 D'ACCORD. 552 00:18:26,890 --> 00:18:29,556 Alors maintenant, nous allons demander à la question de plusieurs façons différentes. 553 00:18:29,556 --> 00:18:31,610 Comment pouvons-nous aller sur le tri ces gens ici? 554 00:18:31,610 --> 00:18:34,500 Parce que nous avons eu quelques approches plus tôt, de sorte que nous avons été 555 00:18:34,500 --> 00:18:36,360 sorte de faire deux seaux différents. 556 00:18:36,360 --> 00:18:38,842 Et puis nous étions généralement assemblant des choses ensemble. 557 00:18:38,842 --> 00:18:41,050 Dès que nous avons vu deux numéros qui appartenaient ensemble, 558 00:18:41,050 --> 00:18:41,975 nous les mettons ensemble. 559 00:18:41,975 --> 00:18:43,350 Deux lettres qui vont ensemble. 560 00:18:43,350 --> 00:18:45,058 >> Mais nous allons voir si nous ne peut pas formaliser ce, 561 00:18:45,058 --> 00:18:48,044 de sorte que nous avons en fin de compte certains pseudo-code vous voulez, 562 00:18:48,044 --> 00:18:49,710 avec lequel vous pouvez résoudre ces problèmes. 563 00:18:49,710 --> 00:18:51,870 Alors maintenant, je suis à la recherche sur ces chiffres ici. 564 00:18:51,870 --> 00:18:55,030 Et je vois tout un tas d'erreurs. 565 00:18:55,030 --> 00:18:57,750 En fin de compte, je veux un sur le gauche et huit sur la droite. 566 00:18:57,750 --> 00:19:00,650 >> Et donc je suis à la recherche ces deux, quatre et deux. 567 00:19:00,650 --> 00:19:02,930 Et quel est le problème, évidemment? 568 00:19:02,930 --> 00:19:04,261 Ouais. 569 00:19:04,261 --> 00:19:04,760 Ainsi. 570 00:19:04,760 --> 00:19:07,160 Deux vient évidemment avant quatre, de sorte que vous savez quoi? 571 00:19:07,160 --> 00:19:10,210 Permettez-moi d'abord prendre une approche gloutonne, si vous voulez, comme beaucoup de problème 572 00:19:10,210 --> 00:19:13,790 mettre One-- si vous vous souvenez de la Standard Edition du problème Set One, 573 00:19:13,790 --> 00:19:16,820 où je viens de résoudre localement le problème qui est ici en face de moi 574 00:19:16,820 --> 00:19:17,690 et voir où cela me mène. 575 00:19:17,690 --> 00:19:17,870 >> D'ACCORD. 576 00:19:17,870 --> 00:19:20,161 Donc, deux et quatre, laissez-moi aller avant et juste vous échanger deux. 577 00:19:20,161 --> 00:19:22,400 Si vous pouvez déplacer physiquement vous et votre papier, 578 00:19:22,400 --> 00:19:25,040 Il me semble avoir obtenu le énumérer dans un meilleur état. 579 00:19:25,040 --> 00:19:26,330 >> Maintenant, ils sont bons. 580 00:19:26,330 --> 00:19:28,480 Je vais passer à autre chose, quatre et six, semble bon. 581 00:19:28,480 --> 00:19:29,110 Pas de problème. 582 00:19:29,110 --> 00:19:30,440 Six et huit ans, OK. 583 00:19:30,440 --> 00:19:31,860 Huit et un, un autre problème. 584 00:19:31,860 --> 00:19:34,750 Parce que ce qui est vrai à propos de huit et un? 585 00:19:34,750 --> 00:19:36,990 On vient avant huit, et ainsi que devrions-nous faire? 586 00:19:36,990 --> 00:19:38,090 Disons permuter ces deux. 587 00:19:38,090 --> 00:19:39,316 Un et huit. 588 00:19:39,316 --> 00:19:40,690 Et maintenant, je vais continuer. 589 00:19:40,690 --> 00:19:42,030 Je vais continuer à regarder de l'avant. 590 00:19:42,030 --> 00:19:42,840 Et nous allons voir ce qui se passe. 591 00:19:42,840 --> 00:19:44,680 Huit et trois, Bien sûr, sur commande. 592 00:19:44,680 --> 00:19:45,815 Laissez de swap. 593 00:19:45,815 --> 00:19:46,940 Huit et sept ans, bien sûr. 594 00:19:46,940 --> 00:19:47,481 Hors service. 595 00:19:47,481 --> 00:19:48,280 Laissez de swap. 596 00:19:48,280 --> 00:19:49,940 Swap de huit et cinq ans, bien sûr, laisser. 597 00:19:49,940 --> 00:19:50,560 Bien. 598 00:19:50,560 --> 00:19:51,880 Liste est triée. 599 00:19:51,880 --> 00:19:53,060 Oui? 600 00:19:53,060 --> 00:19:54,280 >> OK, évidemment pas. 601 00:19:54,280 --> 00:19:55,860 Mais il est un peu mieux, non? 602 00:19:55,860 --> 00:19:57,270 Parce que ce qui est arrivé préavis. 603 00:19:57,270 --> 00:20:01,749 Chaque fois que nous avons joué un swap, un plus petit Numéro sorte de percolation de cette façon, 604 00:20:01,749 --> 00:20:03,790 et un plus grand nombre percolé cette façon, ou nous allons 605 00:20:03,790 --> 00:20:06,880 commencer à dire barboter à la gauche ou barboter vers la droite. 606 00:20:06,880 --> 00:20:10,080 >> Maintenant, il ne suffit pas, parce au mieux, un certain nombre pourrait 607 00:20:10,080 --> 00:20:11,990 ont déplacé un seul endroit avant, ou au pire, 608 00:20:11,990 --> 00:20:13,880 un certain nombre pourrait avoir déplacé un endroit plus loin. 609 00:20:13,880 --> 00:20:16,369 Donc, vous savez quoi, ce genre d'assez bien fonctionné jusqu'ici. 610 00:20:16,369 --> 00:20:17,410 Permettez-moi d'essayer à nouveau. 611 00:20:17,410 --> 00:20:18,880 Deux et quatre, ils sont OK. 612 00:20:18,880 --> 00:20:20,180 Quatre et six, ils sont OK. 613 00:20:20,180 --> 00:20:21,790 Six et, sur commande. 614 00:20:21,790 --> 00:20:23,007 Donc, nous allons vous deux swap. 615 00:20:23,007 --> 00:20:25,840 Et maintenant, le problème de remarquer commence à faire un peu mieux encore. 616 00:20:25,840 --> 00:20:27,006 Six et trois, sur commande. 617 00:20:27,006 --> 00:20:28,100 Disons que vous deux swap. 618 00:20:28,100 --> 00:20:29,730 Six et sept, vous êtes bon. 619 00:20:29,730 --> 00:20:32,230 Sept et cinq, bien sûr, hors de l'ordre. 620 00:20:32,230 --> 00:20:33,920 Sept et huit, dans l'ordre. 621 00:20:33,920 --> 00:20:36,470 Et maintenant, je pourrais avoir besoin de faire un peu plus de temps. 622 00:20:36,470 --> 00:20:39,830 Et en fait, pensez par vous-mêmes peut-être le nombre de fois maximum 623 00:20:39,830 --> 00:20:41,330 pourrais-je avoir à marcher en arrière? 624 00:20:41,330 --> 00:20:42,390 >> Nous reviendrons à cela. 625 00:20:42,390 --> 00:20:43,700 Donc, deux et quatre sont toujours OK. 626 00:20:43,700 --> 00:20:44,940 Quatre et un, Nope. 627 00:20:44,940 --> 00:20:45,747 Donc, nous allons swap. 628 00:20:45,747 --> 00:20:47,830 Et encore une fois, remarquez visuellement l'un est une sorte de bouillonnement 629 00:20:47,830 --> 00:20:49,163 vers la gauche, où il devrait être. 630 00:20:49,163 --> 00:20:50,010 Quatre et trois swap. 631 00:20:50,010 --> 00:20:51,330 Quatre et six. 632 00:20:51,330 --> 00:20:53,100 Six et cinq swap. 633 00:20:53,100 --> 00:20:53,959 Six et sept. 634 00:20:53,959 --> 00:20:55,000 Sept et huit sont bonnes. 635 00:20:55,000 --> 00:20:55,500 >> Bien. 636 00:20:55,500 --> 00:20:58,460 Nous recevons encore mieux. 637 00:20:58,460 --> 00:20:59,130 Voyons donc. 638 00:20:59,130 --> 00:21:00,940 , Nous avons maintenant deux et un. 639 00:21:00,940 --> 00:21:02,520 Bien sûr, échanger. 640 00:21:02,520 --> 00:21:07,520 Deux et trois, trois et quatre, quatre et cinq, six et sept, sept et huit. 641 00:21:07,520 --> 00:21:08,020 Bien. 642 00:21:08,020 --> 00:21:08,730 Et vous savez quoi? 643 00:21:08,730 --> 00:21:11,190 Parce que je faisais un changement là, laissez-moi faire un test de cohérence. 644 00:21:11,190 --> 00:21:13,023 Laissez-moi aller tout le chemin Retour au début. 645 00:21:13,023 --> 00:21:13,680 D'ACCORD. 646 00:21:13,680 --> 00:21:14,750 Un, two-- yup, vous voyez? 647 00:21:14,750 --> 00:21:15,870 Quelque chose clochait. 648 00:21:15,870 --> 00:21:18,420 Trois, quatre, cinq, six, sept, huit. 649 00:21:18,420 --> 00:21:21,920 Et dans ce dernier passage, sont vous à l'aise avec mon maintenant 650 00:21:21,920 --> 00:21:23,830 affirmant qu'il est triée? 651 00:21:23,830 --> 00:21:24,330 D'ACCORD. 652 00:21:24,330 --> 00:21:25,880 Visuellement, qui est absolument vrai. 653 00:21:25,880 --> 00:21:28,410 Mais fonctionnellement, ce qui n'a également le fruit du hasard 654 00:21:28,410 --> 00:21:31,870 dans cette dernière passe qui vous permet pour confirmer que cette liste est en effet 655 00:21:31,870 --> 00:21:32,660 triés? 656 00:21:32,660 --> 00:21:34,477 >> Qu'est-ce que je fais ou ne pas faire cette dernière passe? 657 00:21:34,477 --> 00:21:35,810 PUBLIC: Il a eu aucun changement. 658 00:21:35,810 --> 00:21:36,120 DAVID J. Malan: Désolé? 659 00:21:36,120 --> 00:21:37,070 PUBLIC: Aucun changement. 660 00:21:37,070 --> 00:21:38,653 DAVID J. Malan: Aucun changement. 661 00:21:38,653 --> 00:21:41,947 Donc, il serait stupide de ma part refaire ce même algorithme 662 00:21:41,947 --> 00:21:43,780 si je ne faisais pas modifie la première fois. 663 00:21:43,780 --> 00:21:45,160 Et l'Etat n'a pas changé. 664 00:21:45,160 --> 00:21:47,576 Certes, je ne vais pas faire change toute la deuxième fois. 665 00:21:47,576 --> 00:21:49,820 Et donc, il est sûr maintenant à-dire, la liste est triée. 666 00:21:49,820 --> 00:21:52,069 >> Et en effet, cela est maintenant quelque chose que nous allons généralement 667 00:21:52,069 --> 00:21:56,900 appel tri à bulles, de sorte que deux à deux, vous corrigez les erreurs à nouveau, 668 00:21:56,900 --> 00:22:00,210 et encore, et encore, et vous continuer à aller d'avant en arrière, 669 00:22:00,210 --> 00:22:03,370 et d'avant en arrière, jusqu'à ce que vous faire aucune de ces swaps, à quel point 670 00:22:03,370 --> 00:22:07,089 vous pouvez être sûr, oui, je terminé de résoudre tous des erreurs. 671 00:22:07,089 --> 00:22:08,630 Disons réinitialisation et essayer une autre approche. 672 00:22:08,630 --> 00:22:11,590 Si vous les gars pourrait retourner dans l'ordre que vous étiez il ya un moment, 673 00:22:11,590 --> 00:22:13,780 qui ressemblait à ceci. 674 00:22:13,780 --> 00:22:17,640 Maintenant, nous allons prendre une approche un peu plus comme le livre de l'examen, 675 00:22:17,640 --> 00:22:21,122 par lequel nous étions constamment la sélection de la lettre de l'alphabet 676 00:22:21,122 --> 00:22:22,830 que nous voulions type de pour faire face à la prochaine. 677 00:22:22,830 --> 00:22:26,420 Peut-être qu'il était un haut lettre, comme A, ou une lettre de faible Z. 678 00:22:26,420 --> 00:22:28,170 >> Donc tout le monde est de retour dans cet ordre. 679 00:22:28,170 --> 00:22:29,800 Et maintenant, permettez-moi de le faire. 680 00:22:29,800 --> 00:22:34,880 Voyons, je sais que je dois huit chiffres ici. 681 00:22:34,880 --> 00:22:37,410 Je vais aller de l'avant et il suffit de sélectionner délibérément 682 00:22:37,410 --> 00:22:38,520 les plus petits éléments. 683 00:22:38,520 --> 00:22:38,760 Droit? 684 00:22:38,760 --> 00:22:39,801 Cela semble trop intuitive. 685 00:22:39,801 --> 00:22:42,560 Pourquoi je ne trouve pas le moindre élément, mis là où il appartient, 686 00:22:42,560 --> 00:22:45,280 puis obtenir le prochain plus petit élément, mettez où il appartient, et il suffit de répéter. 687 00:22:45,280 --> 00:22:46,820 >> Parce intuitivement, qui devrait fonctionner aussi. 688 00:22:46,820 --> 00:22:48,441 Donc, quatre, qu'il ya un joli petit nombre. 689 00:22:48,441 --> 00:22:49,940 Je vais me rappeler où cela est. 690 00:22:49,940 --> 00:22:50,523 Attendez une minute. 691 00:22:50,523 --> 00:22:51,577 Deux est plus petit. 692 00:22:51,577 --> 00:22:53,910 Permettez-moi de me souviens maintenant où deux est, et oublier quatre. 693 00:22:53,910 --> 00:22:55,050 Nous nous en occuperons plus tard. 694 00:22:55,050 --> 00:22:56,460 Six, je ne suis pas intéressé. 695 00:22:56,460 --> 00:22:57,810 Huit, je ne suis pas intéressé. 696 00:22:57,810 --> 00:22:59,780 L'un est mon nouveau petit nombre. 697 00:22:59,780 --> 00:23:01,470 Donc, je vais vous rappeler où l'on est. 698 00:23:01,470 --> 00:23:02,534 Trois, pas intéressé. 699 00:23:02,534 --> 00:23:03,450 Sept, pas intéressé. 700 00:23:03,450 --> 00:23:04,530 Cinq, pas intéressé. 701 00:23:04,530 --> 00:23:07,390 >> Donc sans tomber la scène cette année, 702 00:23:07,390 --> 00:23:09,890 Je vais saisir le numéro One-- et ce qui est votre nom? 703 00:23:09,890 --> 00:23:10,150 >> Annan: Annan. 704 00:23:10,150 --> 00:23:11,220 >> DAVID J. Malan: Annan. 705 00:23:11,220 --> 00:23:13,540 Et si vous pouviez me joindre au le début de la liste, 706 00:23:13,540 --> 00:23:14,870 nous allons vous mettre où vous appartenez. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- quel est votre nom? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. Malan: Stefan est dans la manière. 710 00:23:18,191 --> 00:23:23,490 Donc, avant de Stefan résout ce problème, que devrions-nous faire? 711 00:23:23,490 --> 00:23:25,412 Que faisons-nous avec Stefan? 712 00:23:25,412 --> 00:23:27,269 >> AUDIENCE: [inaudible]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. Malan: OK. 714 00:23:28,060 --> 00:23:28,850 Donc, nous pourrions le faire. 715 00:23:28,850 --> 00:23:31,730 Nous pourrions sorte de prendre Stefan et son quatre, et il suffit de mettre dans une variable 716 00:23:31,730 --> 00:23:33,530 et les garder avec lui pour une certaine quantité de temps, 717 00:23:33,530 --> 00:23:35,220 rendant ainsi la place pour le numéro un. 718 00:23:35,220 --> 00:23:36,280 Et qui est déjà pas mal. 719 00:23:36,280 --> 00:23:39,270 Je pourrais suggérer, pourquoi ne pas nous venons de mettre Stefan ici? 720 00:23:39,270 --> 00:23:41,610 Pourquoi ce pourrait violer l'une des idées que nous avons commencé 721 00:23:41,610 --> 00:23:44,830 parler de la dernière fois, la semaine dernière? 722 00:23:44,830 --> 00:23:45,330 Ouais? 723 00:23:45,330 --> 00:23:45,740 >> AUDIENCE: [inaudible]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. Malan: Il n'y a pas l'indice pour elle. 725 00:23:46,860 --> 00:23:49,735 Si vous pensez cela, en effet, comme un diodes, elle est comme un négatif, 726 00:23:49,735 --> 00:23:52,900 il n'y a donc pas de mémoire réellement ici si cela est en effet un tableau, 727 00:23:52,900 --> 00:23:55,090 comme nous avons déclaré la semaine dernière dans la leçon. 728 00:23:55,090 --> 00:23:56,250 Donc, nous ne devrions pas le faire. 729 00:23:56,250 --> 00:23:57,340 Nous pourrions stocker dans une variable. 730 00:23:57,340 --> 00:23:57,820 >> Ou vous savez quoi? 731 00:23:57,820 --> 00:23:59,153 Je entendu quelqu'un d'autre, il suggère. 732 00:23:59,153 --> 00:24:01,020 Que pourrions-nous faire avec Stefan? 733 00:24:01,020 --> 00:24:03,770 Pourquoi avons-nous expulser non seulement lui et le mettre sur le lieu où était numéro un. 734 00:24:03,770 --> 00:24:05,170 Donc, si vous voulez aller là-bas. 735 00:24:05,170 --> 00:24:07,300 Et en effet, ceci est un assez bonne solution. 736 00:24:07,300 --> 00:24:10,480 Maintenant, d'une part, je l'ai genre du fait qu'aggraver le problème. 737 00:24:10,480 --> 00:24:13,650 Quatre est maintenant plus loin d'où il devrait être. 738 00:24:13,650 --> 00:24:14,900 Il doit être orienté vers cette demi. 739 00:24:14,900 --> 00:24:16,100 >> Mais vous savez quoi? 740 00:24:16,100 --> 00:24:17,630 Cela aurait pu être la malchance. 741 00:24:17,630 --> 00:24:18,822 Numéro huit Peut-être était ici. 742 00:24:18,822 --> 00:24:20,530 Et ainsi, nous aurions peut- ont eu la chance, 743 00:24:20,530 --> 00:24:22,460 et huit poussé plus près de la fin. 744 00:24:22,460 --> 00:24:24,710 Donc à la fin de la journée, Il sorte de toutes les moyennes sur. 745 00:24:24,710 --> 00:24:26,085 On n'a pas besoin de se soucier de quatre. 746 00:24:26,085 --> 00:24:29,400 Tout ce que je me soucie de ce moment est la sélection du plus petit élément. 747 00:24:29,400 --> 00:24:32,030 >> Et maintenant, ce que je vais faire oublier est numéro un 748 00:24:32,030 --> 00:24:35,160 en permanence, parce que je sais que le Liste derrière moi est maintenant triée. 749 00:24:35,160 --> 00:24:36,720 Donc ma liste était auparavant la taille de huit. 750 00:24:36,720 --> 00:24:37,720 Maintenant, il est de la taille de sept. 751 00:24:37,720 --> 00:24:40,340 Donc, mon problème est d'obtenir plus petit, quoique de façon linéaire. 752 00:24:40,340 --> 00:24:43,022 Alors maintenant, je vais sélectionner le plus petit élément de courant, deux. 753 00:24:43,022 --> 00:24:46,520 Six, huit, quatre, trois, sept, cinq. 754 00:24:46,520 --> 00:24:47,770 Ce fut le plus petit élément. 755 00:24:47,770 --> 00:24:49,416 Alors, que vais-je faire avec-- ce qui est votre nom? 756 00:24:49,416 --> 00:24:49,760 >> JOSEPH: Joseph. 757 00:24:49,760 --> 00:24:50,085 >> DAVID J. Malan: Joseph? 758 00:24:50,085 --> 00:24:52,000 Nous allons laisser Joseph en place. 759 00:24:52,000 --> 00:24:54,842 Maintenant, je vais faire semblant que ces gars soient: ainsi, 760 00:24:54,842 --> 00:24:56,550 Je sais que ces deux sont déjà triés. 761 00:24:56,550 --> 00:24:58,424 Concentrons-nous maintenant sur le reste de la liste. 762 00:24:58,424 --> 00:25:00,080 Six est le plus petit courant. 763 00:25:00,080 --> 00:25:01,190 Huit est plus grand. 764 00:25:01,190 --> 00:25:02,970 Quatre est maintenant le plus petit courant. 765 00:25:02,970 --> 00:25:04,762 Trois est maintenant le plus petit courant. 766 00:25:04,762 --> 00:25:07,720 Et maintenant, je vais choisir trois, général qui: quel est votre nom? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. Malan: Serena, si vous pouviez saisir votre numéro et d'échange avec-- 769 00:25:10,620 --> 00:25:11,550 Kalsang: Kalsang. 770 00:25:11,550 --> 00:25:12,940 DAVID J. Malan: Kalsang. 771 00:25:12,940 --> 00:25:15,220 Venez sur le dos, et nous sommes aller à échanger les deux. 772 00:25:15,220 --> 00:25:17,360 Et maintenant, nous allons mettre cela sur le pilote automatique. 773 00:25:17,360 --> 00:25:21,589 Je vais aller et le laisser à vous les gars pour sélectionner les prochains petits éléments. 774 00:25:21,589 --> 00:25:22,380 Dun, Dun, Dun, Dun. 775 00:25:22,380 --> 00:25:24,560 Numéro quatre, que devez-vous faire? 776 00:25:24,560 --> 00:25:26,261 Excellente. 777 00:25:26,261 --> 00:25:27,760 Maintenant, je vais faire un autre passage. 778 00:25:27,760 --> 00:25:28,590 Dun, Dun, Dun, Dun. 779 00:25:28,590 --> 00:25:31,465 Je vois cinq est le prochain plus petit. 780 00:25:31,465 --> 00:25:32,840 Maintenant, je vais prendre une autre passe. 781 00:25:32,840 --> 00:25:33,631 Dun, Dun, Dun, Dun. 782 00:25:33,631 --> 00:25:34,880 Six est le plus petit. 783 00:25:34,880 --> 00:25:35,520 Bien. 784 00:25:35,520 --> 00:25:36,585 Sept est le plus petit. 785 00:25:36,585 --> 00:25:37,085 Pas de changement. 786 00:25:37,085 --> 00:25:38,630 Huit est le plus petit. 787 00:25:38,630 --> 00:25:39,170 Terminé. 788 00:25:39,170 --> 00:25:43,900 >> Donc, ce que nous venons de faire par itérative la sélection d'un élément après l'autre 789 00:25:43,900 --> 00:25:47,230 est de mettre en œuvre quelque chose que nous sommes aller à formaliser que la sélection sorte. 790 00:25:47,230 --> 00:25:49,120 Et il est peut-être même simple à expliquer, 791 00:25:49,120 --> 00:25:51,310 en ce que littéralement tout ce que vous voulez faire est de simplement continuer 792 00:25:51,310 --> 00:25:54,700 des allers-retours dans la liste la sélection, la prochaine plus petit élément, 793 00:25:54,700 --> 00:25:55,720 jusqu'à ce que vous avez terminé. 794 00:25:55,720 --> 00:25:58,650 >> Donc, il est encore plus simple, peut-être intuitivement, que la dernière. 795 00:25:58,650 --> 00:26:00,020 Essayons un dernier. 796 00:26:00,020 --> 00:26:03,060 Si vous les gars pourrait vous réinitialiser dans les positions suivantes 797 00:26:03,060 --> 00:26:08,600 une dernière fois, nous allons voir si nous ne pouvons pas maintenant officialiser un autre approche. 798 00:26:08,600 --> 00:26:12,857 En fait, quelqu'un aurait là vous proposer 799 00:26:12,857 --> 00:26:14,440 sinon comment nous pourrions le faire de manière? 800 00:26:14,440 --> 00:26:17,439 Sans jetant des mots à la mode ou genre des réponses qui sont déjà connus, 801 00:26:17,439 --> 00:26:19,689 juste intuitivement, que pourrions-nous faire? 802 00:26:19,689 --> 00:26:21,635 >> AUDIENCE: [inaudible]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. Malan: Ouais. 804 00:26:22,510 --> 00:26:24,620 Donc, il ya une certaine grande intuition il. 805 00:26:24,620 --> 00:26:28,020 Les bonnes choses semblent se produire à ce jour en informatique quand nous divisons 806 00:26:28,020 --> 00:26:30,832 et conquérir le problème de la division en deux et moitié-moitié. 807 00:26:30,832 --> 00:26:32,540 Et en effet, nous pourrait commencer à le faire. 808 00:26:32,540 --> 00:26:35,754 Et en fait, que ça va être, nous allons voir, un de nos meilleurs solutions encore. 809 00:26:35,754 --> 00:26:37,420 Mais revenons à cette avant longtemps. 810 00:26:37,420 --> 00:26:40,500 En fait, nous allons faire un peu plus tard cette semaine. 811 00:26:40,500 --> 00:26:42,180 Que pourrions-nous faire pour résoudre ce problème? 812 00:26:42,180 --> 00:26:44,647 Donc, tout le monde ici est en Afin apparemment aléatoire. 813 00:26:44,647 --> 00:26:45,230 Tu sais quoi? 814 00:26:45,230 --> 00:26:48,320 Plutôt que d'aller et venir, d'avant en arrière, d'avant en arrière 815 00:26:48,320 --> 00:26:50,624 à chaque fois, cela se sent comme Je fais beaucoup de marche. 816 00:26:50,624 --> 00:26:52,790 Pourquoi dois-je pas simplement commencer à le début de la liste, 817 00:26:52,790 --> 00:26:54,960 et vient de mettre quatre où il appartient? 818 00:26:54,960 --> 00:26:59,680 Alors permettez-moi suppose pour le moment que ma liste est seulement ce premier élément. 819 00:26:59,680 --> 00:27:04,937 Est de quatre triés en ce moment dans le temps, si tout ce que je me soucie est tout ici? 820 00:27:04,937 --> 00:27:06,520 Cette est une sorte de trivialement vrai, non? 821 00:27:06,520 --> 00:27:10,000 Comme la liste contenant un certain nombre, et ce nombre est quatre évidemment triée. 822 00:27:10,000 --> 00:27:13,070 >> Alors laissez-moi juste stipule par que cette liste est triée. 823 00:27:13,070 --> 00:27:15,090 Mais maintenant, je dois le reste de cette liste. 824 00:27:15,090 --> 00:27:17,240 Alors maintenant, je rencontre deux. 825 00:27:17,240 --> 00:27:21,690 Où fait deux évidemment appartenir à l'égard de quatre? 826 00:27:21,690 --> 00:27:22,580 Avant de quatre. 827 00:27:22,580 --> 00:27:23,862 Alors qu'est-ce que je peux faire ici? 828 00:27:23,862 --> 00:27:24,820 Quel est votre nom? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. Malan: Joseph, si vous pouviez revenir en arrière 831 00:27:26,030 --> 00:27:27,790 juste un moment avec votre numéro. 832 00:27:27,790 --> 00:27:31,130 Et maintenant, que devrait Stefan faire ici? 833 00:27:31,130 --> 00:27:33,720 Changeons Stefan ici. 834 00:27:33,720 --> 00:27:35,520 Et maintenant, laissez-Joseph venir ici. 835 00:27:35,520 --> 00:27:39,660 Et maintenant, permettez-moi de prétendre que tout ici est triée. 836 00:27:39,660 --> 00:27:42,474 Donc, résultat similaire, mais un approche fondamentalement différente. 837 00:27:42,474 --> 00:27:44,140 Je l'ai même pas regardé ce qui est là-bas. 838 00:27:44,140 --> 00:27:46,310 Je garde juste prendre les éléments comme ils sont remis à moi, 839 00:27:46,310 --> 00:27:47,240 et de traiter avec eux. 840 00:27:47,240 --> 00:27:48,330 >> Alors maintenant, je vois le numéro six. 841 00:27:48,330 --> 00:27:51,110 D'où vient le numéro six appartiennent? 842 00:27:51,110 --> 00:27:53,250 Nous avons deux, quatre, six. 843 00:27:53,250 --> 00:27:54,800 Exactement là où elle est maintenant. 844 00:27:54,800 --> 00:27:57,750 Alors laissons cela seul, et maintenant prétendre que cette partie de la liste 845 00:27:57,750 --> 00:27:58,772 est maintenant triée. 846 00:27:58,772 --> 00:28:01,230 Et oui, cela se sent fondamentalement différent que je suis juste 847 00:28:01,230 --> 00:28:05,230 se déplaçant à travers la liste ici linéairement, et je ne suis jamais doubler dos. 848 00:28:05,230 --> 00:28:05,730 Oui. 849 00:28:05,730 --> 00:28:06,230 Bien. 850 00:28:06,230 --> 00:28:08,190 Donc, huit, où appartenez-vous? 851 00:28:08,190 --> 00:28:08,730 Ici. 852 00:28:08,730 --> 00:28:09,310 Parfait. 853 00:28:09,310 --> 00:28:10,210 Alors maintenant, un. 854 00:28:10,210 --> 00:28:10,900 Uh-oh. 855 00:28:10,900 --> 00:28:13,010 Cela se sent comme il est va être cher. 856 00:28:13,010 --> 00:28:15,690 Maintenant, dans l'algorithme précédent, Je viens troqué personnes. 857 00:28:15,690 --> 00:28:18,648 Donc, je pourrais le mettre tout le chemin à au début, mais ensuite déplacé Joseph. 858 00:28:18,648 --> 00:28:21,450 Mais si je déménage Joseph, maintenant ce qui va être le problème? 859 00:28:21,450 --> 00:28:24,250 >> Maintenant, je l'ai sorte de undone-- je l'ai fait un pas en avant, puis 860 00:28:24,250 --> 00:28:26,300 un pas en arrière, parce que maintenant Joseph serait irrecevable. 861 00:28:26,300 --> 00:28:26,830 Donc, nous allons le faire. 862 00:28:26,830 --> 00:28:29,150 Si vous pouviez prendre le numéro un et pas en arrière pour un instant. 863 00:28:29,150 --> 00:28:30,490 Comment pouvons-nous ce que put-- est votre nom? 864 00:28:30,490 --> 00:28:31,130 >> Annan: Annan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. Malan: Annan en place? 866 00:28:32,610 --> 00:28:36,091 Que faut-il en ce qui concerne à deux, quatre, six et huit? 867 00:28:36,091 --> 00:28:37,570 Ils ont tous besoin de passer. 868 00:28:37,570 --> 00:28:42,590 Donc, si huit aimerait déplacer d'abord, puis six, puis quatre, puis deux. 869 00:28:42,590 --> 00:28:45,380 Et puis Annan, si vous aviez envie de venir ici, bon. 870 00:28:45,380 --> 00:28:47,760 Mais ici, nous venons sorte de payé un prix 871 00:28:47,760 --> 00:28:49,510 à un point différent dans l'algorithme. 872 00:28:49,510 --> 00:28:52,550 Considérant que la dernière fois avec la sélection Trier, et même tri à bulles, 873 00:28:52,550 --> 00:28:54,700 Je marche arrière et arrière, d'avant en arrière, 874 00:28:54,700 --> 00:28:58,360 qui est certainement l'addition Time-Wise, et littéralement pas à pas. 875 00:28:58,360 --> 00:29:00,660 >> Le tri par insertion, au premier vue, ressemble il est 876 00:29:00,660 --> 00:29:05,150 super-intelligente, en ce que je suis juste faisant lent, des progrès graduels, 877 00:29:05,150 --> 00:29:07,120 mais je ne vais pas ce retour en arrière. 878 00:29:07,120 --> 00:29:09,410 Mais si quelqu'un est en effet sur ordonnance, un avis 879 00:29:09,410 --> 00:29:10,840 tout le travail que je viens d'avoir à faire. 880 00:29:10,840 --> 00:29:14,750 Je devais passer la moitié de la liste juste pour faire de la place pour le numéro un. 881 00:29:14,750 --> 00:29:16,790 Il est donc la même quantité des travaux à ce jour, il 882 00:29:16,790 --> 00:29:18,690 sent, juste un type de travail différent. 883 00:29:18,690 --> 00:29:19,370 >> Nous allons continuer. 884 00:29:19,370 --> 00:29:22,657 Alors maintenant, nous savons que tout le monde entre un et huit sont triés. 885 00:29:22,657 --> 00:29:23,740 Ici, je dois numéro trois. 886 00:29:23,740 --> 00:29:25,864 Si vous aimez à ramasser Numéro trois, un recul. 887 00:29:25,864 --> 00:29:28,260 Et qu'est-ce que vous les gars ont besoin de faire? 888 00:29:28,260 --> 00:29:28,760 Yep. 889 00:29:28,760 --> 00:29:33,070 Voilà donc un autre, deux, trois étapes. 890 00:29:33,070 --> 00:29:36,010 Trois unités de temps qui coûtent tout simplement moi, alors que trois peux maintenant adapter. 891 00:29:36,010 --> 00:29:37,460 Enfin, sept. 892 00:29:37,460 --> 00:29:39,730 >> Allons de l'avant et avoir vous prenez un pas en arrière. 893 00:29:39,730 --> 00:29:42,780 Ceci est seulement va nous coûter une unité de temps, mais cela est OK. 894 00:29:42,780 --> 00:29:44,170 Et maintenant, cinq va être un peu plus cher. 895 00:29:44,170 --> 00:29:45,340 Si vous souhaitez prendre du recul. 896 00:29:45,340 --> 00:29:48,380 Nous devons aller de huit, et sept, et six. 897 00:29:48,380 --> 00:29:50,749 Et puis tout le monde est maintenant triée. 898 00:29:50,749 --> 00:29:52,290 Donc une grosse main à nos bénévoles ici. 899 00:29:52,290 --> 00:29:53,554 Merci beaucoup. 900 00:29:53,554 --> 00:29:56,220 >> [Applaudissements] 901 00:29:56,220 --> 00:29:56,860 >> Merci à tous. 902 00:29:56,860 --> 00:29:57,520 Merci à tous. 903 00:29:57,520 --> 00:30:02,940 Voyons donc maintenant à quel point coûteuse tout cela était. 904 00:30:02,940 --> 00:30:06,210 Prenons peut-être le simple de ceux-ci, sorte de bulle. 905 00:30:06,210 --> 00:30:09,950 Et je dis simple, seulement parce que vous pouvez résoudre avec avidité par tout 906 00:30:09,950 --> 00:30:11,660 résoudre le problème par paires ici. 907 00:30:11,660 --> 00:30:13,720 Correction du problème par paires ici, encore et encore 908 00:30:13,720 --> 00:30:17,680 et encore, en répétant autant fois que vous avez réellement besoin pour. 909 00:30:17,680 --> 00:30:21,050 >> Donc, il se trouve que avec une sorte de bulle, et bien, 910 00:30:21,050 --> 00:30:25,820 combien d'étapes dois-je prendre le premier passage de cet algorithme? 911 00:30:25,820 --> 00:30:30,850 Je pourrais take-- nous allons see-- un, deux, trois, quatre, cinq, six, sept. 912 00:30:30,850 --> 00:30:32,190 Et il ya huit éléments ici. 913 00:30:32,190 --> 00:30:35,280 Donc, il est comme n moins 1 à étapes obtenir dès le début de la liste 914 00:30:35,280 --> 00:30:36,380 à la fin de la liste. 915 00:30:36,380 --> 00:30:41,350 >> Mais avec la sélection sorte, rappelle que je suis sélectionnant encore et encore les éléments 916 00:30:41,350 --> 00:30:44,590 et encore que le plus petit, Je mets en place, 917 00:30:44,590 --> 00:30:46,616 mais je ne suis pas regarder derrière moi. 918 00:30:46,616 --> 00:30:49,490 Donc, je pense qu'il est un peu plus clair alors que la première fois, je pourrais 919 00:30:49,490 --> 00:30:52,680 prendre toutes les mesures n moins 1 pour trouver le plus petit élément. 920 00:30:52,680 --> 00:30:55,920 Puis je les ai mis en place, et je évincer celui qui était là auparavant. 921 00:30:55,920 --> 00:30:57,500 >> Mais je ne dois pas continuer à chercher à cet élément, 922 00:30:57,500 --> 00:30:59,040 parce que je sais qu'il est déjà la plus petite. 923 00:30:59,040 --> 00:31:01,581 Alors maintenant, je peux regarder seulement sept éléments, puis six éléments, 924 00:31:01,581 --> 00:31:03,290 puis cinq éléments, puis quatre éléments. 925 00:31:03,290 --> 00:31:06,900 Et si mathématiquement, si n est le nombre d'éléments ou de nombres 926 00:31:06,900 --> 00:31:11,990 que nous avons commencé avec, vous pouvez l'imaginer ce qui est le même que n moins 1, 927 00:31:11,990 --> 00:31:14,250 plus n moins 2 étapes, plus n moins 3 étapes, 928 00:31:14,250 --> 00:31:16,780 ainsi n moins 4 étapes, tous les chemin vers le bas à une seule étape. 929 00:31:16,780 --> 00:31:18,160 Et je suis sur ma dernière personne. 930 00:31:18,160 --> 00:31:20,650 >> Et si vous vous souvenez que beaucoup des stats des livres ou des livres de mathématiques 931 00:31:20,650 --> 00:31:24,730 avoir les formules sur le Relié dos ou face d'eux, 932 00:31:24,730 --> 00:31:27,690 il se trouve que cette série peut être exprimé plus simplement 933 00:31:27,690 --> 00:31:28,857 que n fois n moins 1 sur 2. 934 00:31:28,857 --> 00:31:31,273 Et il est très bien si cela ne à la pointe de votre esprit. 935 00:31:31,273 --> 00:31:32,420 Mais cela est vrai. 936 00:31:32,420 --> 00:31:34,449 Voilà juste un moyen plus simple de l'écrire. 937 00:31:34,449 --> 00:31:36,240 Et puis si vous pensez Retour à l'école primaire, 938 00:31:36,240 --> 00:31:38,698 lorsque vous venez de commencer à multiplier les choses, cela bien sûr, 939 00:31:38,698 --> 00:31:41,820 est tout simplement n carré moins n divisé par 2. 940 00:31:41,820 --> 00:31:44,772 Tout ce que je l'ai fait est élargir les expressions là. 941 00:31:44,772 --> 00:31:46,730 Et nous allons donc réécrire ce un peu différemment. 942 00:31:46,730 --> 00:31:49,780 Cela n carré divisé par 2 moins n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Encore une fois, je suis juste un peu de l'application un peu d'arithmétique y règne. 944 00:31:53,270 --> 00:31:57,140 Mais remarquez maintenant que le plus grand terme dans cette expression, pour ainsi dire, 945 00:31:57,140 --> 00:31:58,540 n est que carré. 946 00:31:58,540 --> 00:32:02,910 Alors oui, il est n carré divisée par deux, moins n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Mais en règle générale, si n est égal à va être une grande valeur, 948 00:32:05,080 --> 00:32:08,740 Je vais prétendre que n carré va être le facteur dominant. 949 00:32:08,740 --> 00:32:10,490 Il va juste être un plus grand contributeur 950 00:32:10,490 --> 00:32:12,877 pour le nombre de pas que les n / 2. 951 00:32:12,877 --> 00:32:13,960 Alors qu'est-ce que je veux dire par là? 952 00:32:13,960 --> 00:32:16,795 Essayons un exemple simple, même si le calcul est un peu grosse. 953 00:32:16,795 --> 00:32:20,210 >> Supposons donc que nous avons eu 1 million de personnes sur scène, ou 1 million de choses 954 00:32:20,210 --> 00:32:21,320 que nous voulons trier. 955 00:32:21,320 --> 00:32:23,730 Branchons un million dans exactement cette formule 956 00:32:23,730 --> 00:32:27,230 pour voir combien d'étapes il faut totale pour trier un million d'éléments à l'aide par exemple, 957 00:32:27,230 --> 00:32:28,560 tri par sélection. 958 00:32:28,560 --> 00:32:30,760 >> Il faudrait donc la même formule que précédemment. 959 00:32:30,760 --> 00:32:34,120 Je branche un millions, de sorte que je reçois un million carré divisé par 2, 960 00:32:34,120 --> 00:32:35,990 moins d'un million divisé par 2. 961 00:32:35,990 --> 00:32:40,180 Si je ne fais que les mathématiques à l'avance ici, nous avons 500 milliards 962 00:32:40,180 --> 00:32:47,460 moins 500 000, qui nous donne 499 999 500 000, 963 00:32:47,460 --> 00:32:49,270 qui est sacrément grand. 964 00:32:49,270 --> 00:32:54,370 >> En fait, si vous comparez maintenant 499 000 000 000 999 millions d'euros, 965 00:32:54,370 --> 00:33:01,210 500.000 contre notre valeur d'origine, 500 milliards, il est sacrément proche. 966 00:33:01,210 --> 00:33:06,850 Droit? n au carré divisée par deux donne us-- ou plutôt, n au carré divisée par 2 967 00:33:06,850 --> 00:33:08,370 nous a donné 500 milliards. 968 00:33:08,370 --> 00:33:13,510 Voilà sacrément proche à 499 999 500 000, 969 00:33:13,510 --> 00:33:17,970 qui est-à-dire hors soustrayant 500 000, ou, plus généralement, de soustraction 970 00:33:17,970 --> 00:33:20,010 n carré, pas vraiment un gros problème. 971 00:33:20,010 --> 00:33:22,490 Le n carré rend ces nombre augmente très vite. 972 00:33:22,490 --> 00:33:25,790 >> Maintenant, ce qui est important dans la mesure où seulement comme nous, que les scientifiques informatiques, 973 00:33:25,790 --> 00:33:29,350 ne sont généralement pas aller à tant de soin sur les nuances de ces formules 974 00:33:29,350 --> 00:33:31,400 et exactement ce que le des réponses précises sont. 975 00:33:31,400 --> 00:33:33,390 Nous nous soucions seulement que, vous savez quoi? 976 00:33:33,390 --> 00:33:37,810 A la fin de la journée, cette formule est de l'ordre de n au carré. 977 00:33:37,810 --> 00:33:39,350 >> Oui, nous sommes en divisant par 2 là. 978 00:33:39,350 --> 00:33:41,360 Oui, nous soustrayant hors n moins 2. 979 00:33:41,360 --> 00:33:46,860 Mais à la fin de la journée, le terme qui nous fait mal et nous coûte vraiment 980 00:33:46,860 --> 00:33:48,995 beaucoup d'étapes est que ce terme carré. 981 00:33:48,995 --> 00:33:51,370 Et alors un informaticien va généralement faire 982 00:33:51,370 --> 00:33:54,160 est ignorer tous ceux petits termes d'ordre, 983 00:33:54,160 --> 00:33:56,900 et il suffit de regarder celui qui contribue le plus au coût. 984 00:33:56,900 --> 00:34:00,530 >> Et c'est bien, parce que nous pouvons parler maintenant de façon beaucoup plus générale 985 00:34:00,530 --> 00:34:02,470 sur les algorithmes, et peut les comparer. 986 00:34:02,470 --> 00:34:04,550 Et le fait que je suis en utilisant cette O est délibérée. 987 00:34:04,550 --> 00:34:06,680 Quand je dis de l'ordre de, je suis particulièrement 988 00:34:06,680 --> 00:34:09,560 faisant référence à quelque chose appelé Big O. et Big O 989 00:34:09,560 --> 00:34:14,090 est une notation qui un ordinateur chercheur utilise pour décrire 990 00:34:14,090 --> 00:34:16,710 une borne supérieure sur quelque chose. 991 00:34:16,710 --> 00:34:21,150 >> Donc, si vous dites que un algorithme est dans le grand O n carré, 992 00:34:21,150 --> 00:34:23,380 comme je l'ai proposé juste un il ya un moment, que des moyens 993 00:34:23,380 --> 00:34:27,710 qu'en termes de son fonctionnement temps ou son efficacité, 994 00:34:27,710 --> 00:34:30,090 il faut de l'ordre n étapes de carré. 995 00:34:30,090 --> 00:34:31,420 Peut-être plus, peut-être moins. 996 00:34:31,420 --> 00:34:33,435 Mais il est de l'ordre de n carré. 997 00:34:33,435 --> 00:34:34,560 Et qui est la limite supérieure. 998 00:34:34,560 --> 00:34:36,530 Ça ne va pas être plus douloureux que cela. 999 00:34:36,530 --> 00:34:40,800 Ça ne va pas être n cubes, ou 2 au n, ou quelque chose de beaucoup plus grand. 1000 00:34:40,800 --> 00:34:43,800 Ceci est une borne supérieure sur tout ce que le coût est. 1001 00:34:43,800 --> 00:34:46,150 Donc, étant donné que, disons considérer que quelques exemples. 1002 00:34:46,150 --> 00:34:49,820 Et cela est juste une liste finie temps de course de très communes 1003 00:34:49,820 --> 00:34:52,870 pour les algorithmes qui est censé être illustrative de certaines choses que nous avons 1004 00:34:52,870 --> 00:34:53,600 déjà vu. 1005 00:34:53,600 --> 00:34:58,060 >> Ainsi, par exemple, dans le cas de tri par sélection, ce que je réclame ici 1006 00:34:58,060 --> 00:35:02,250 est la course de sorte que la sélection le temps est de l'ordre de n carré. 1007 00:35:02,250 --> 00:35:06,260 Dans le pire des cas, je vais devoir tout un tas de nombres aléatoires ici. 1008 00:35:06,260 --> 00:35:08,600 Et comme nous l'avons vu mathématiquement, si je continue à marcher 1009 00:35:08,600 --> 00:35:11,310 dans la liste, à travers la liste, sélectionner la prochaine plus petite 1010 00:35:11,310 --> 00:35:14,410 élément, encore et encore, si je fait écrire toutes les étapes 1011 00:35:14,410 --> 00:35:18,750 Je prends comme je l'ai proposé formulaically avant, il est de l'ordre de n carré 1012 00:35:18,750 --> 00:35:20,370 étapes que je vais prendre. 1013 00:35:20,370 --> 00:35:24,520 >> Et il se trouve que la bulle tri et le tri par insertion 1014 00:35:24,520 --> 00:35:27,370 sont tout aussi lente dans le pire des cas. 1015 00:35:27,370 --> 00:35:32,040 Considérons, par exemple, le tri par insertion, le dernier algorithme nous avons traité, 1016 00:35:32,040 --> 00:35:35,500 qui nous avait regardons l'élément, puis insérez où il appartient. 1017 00:35:35,500 --> 00:35:38,720 Et puis nous avons regardé l'élément suivant, et il inséré où il appartient. 1018 00:35:38,720 --> 00:35:40,990 >> Considérons donc le meilleur scénario possible. 1019 00:35:40,990 --> 00:35:45,590 Supposons que je l'avais ma ligne jusqu'à bénévoles littéralement comme cela, de un à huit, 1020 00:35:45,590 --> 00:35:47,440 déjà triés. 1021 00:35:47,440 --> 00:35:51,300 Combien d'étapes est le tri par insertion va prendre pour trier huit personnes, 1022 00:35:51,300 --> 00:35:55,640 si elles arrivent sur scène regarder comme ça? 1023 00:35:55,640 --> 00:35:57,410 >> Huit personnes déjà triées. 1024 00:35:57,410 --> 00:35:58,760 Et je l'utilise le tri par insertion. 1025 00:35:58,760 --> 00:36:02,180 Ce dernier des algorithmes. 1026 00:36:02,180 --> 00:36:03,640 Eh bien, nous allons rejouer très vite. 1027 00:36:03,640 --> 00:36:05,504 Donc, si je commence ici, je vois un. 1028 00:36:05,504 --> 00:36:06,420 Où peut-on appartiennent? 1029 00:36:06,420 --> 00:36:07,730 Il appartient ici. 1030 00:36:07,730 --> 00:36:08,330 Je vois deux. 1031 00:36:08,330 --> 00:36:09,660 Où est-ce deux appartiennent? 1032 00:36:09,660 --> 00:36:10,260 Ici. 1033 00:36:10,260 --> 00:36:10,900 Je vois trois. 1034 00:36:10,900 --> 00:36:11,920 Où est-ce trois appartiennent? 1035 00:36:11,920 --> 00:36:12,480 Ici. 1036 00:36:12,480 --> 00:36:13,100 >> Je vois quatre. 1037 00:36:13,100 --> 00:36:13,600 Ici. 1038 00:36:13,600 --> 00:36:15,660 Cinq, six, sept, huit. 1039 00:36:15,660 --> 00:36:17,320 Il n'y a pas de raison de me répéter. 1040 00:36:17,320 --> 00:36:21,260 Et oui, comment de nombreuses étapes est que, en termes de n? 1041 00:36:21,260 --> 00:36:23,870 Il est de l'ordre de n étapes, non? n moins 1. 1042 00:36:23,870 --> 00:36:27,567 Mais je pris un certain nombre linéaire d'étapes, et maintenant je suis fait. 1043 00:36:27,567 --> 00:36:28,900 Voilà donc le meilleur des cas, cependant. 1044 00:36:28,900 --> 00:36:29,983 Qu'en est-il le pire des cas? 1045 00:36:29,983 --> 00:36:32,730 Qu'est-ce que huit étaient là-bas, et sept étaient là-bas, 1046 00:36:32,730 --> 00:36:35,840 et un et deux étaient ici, donc que la liste était vraiment inversé? 1047 00:36:35,840 --> 00:36:38,300 >> Eh bien, ce qui se passe en effet si tel est le nombre? 1048 00:36:38,300 --> 00:36:41,300 Et nous le ferons seulement quelques exemples. 1049 00:36:41,300 --> 00:36:49,300 Que faire si, en effet, le nombre de huit est ici, et les whoops number--. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Alors que faire si, en effet, le nombre huit est tout le chemin ici, 1052 00:36:56,430 --> 00:36:57,790 et je suis en utilisant le tri par insertion? 1053 00:36:57,790 --> 00:36:58,290 >> D'ACCORD. 1054 00:36:58,290 --> 00:37:00,280 Je prétends au moment où il est en place. 1055 00:37:00,280 --> 00:37:03,152 Mais maintenant, où est-sept seven-- aller? 1056 00:37:03,152 --> 00:37:04,360 Bien sûr, il va ici. 1057 00:37:04,360 --> 00:37:06,760 Donc, je dois passer huit plus un seul endroit. 1058 00:37:06,760 --> 00:37:08,554 Maintenant, six, où faut-il aller? 1059 00:37:08,554 --> 00:37:09,220 Eh bien, tout droit. 1060 00:37:09,220 --> 00:37:13,150 Maintenant, je dois passer huit plus un lieu, et sept sur une place, 1061 00:37:13,150 --> 00:37:14,440 et puis je plop six. 1062 00:37:14,440 --> 00:37:16,870 >> Donc, la première fois, il coûts moi une étape pour arranger les choses, 1063 00:37:16,870 --> 00:37:18,570 alors il m'a coûté deux étapes pour arranger les choses. 1064 00:37:18,570 --> 00:37:20,370 Combien d'étapes est-il va prendre pour corriger 1065 00:37:20,370 --> 00:37:22,720 choses à mettre cinq au bon endroit? 1066 00:37:22,720 --> 00:37:23,340 Trois. 1067 00:37:23,340 --> 00:37:29,520 Parce que maintenant je dois déplacer un, deux, trois. 1068 00:37:29,520 --> 00:37:32,430 Combien d'étapes est qu'il va prendre de mettre quatre à la bonne place? 1069 00:37:32,430 --> 00:37:36,040 4 plus 5, plus 6, plus 7. 1070 00:37:36,040 --> 00:37:40,260 >> Et il est donc mathématiquement identique à ce que nous avons décrit pour la sélection sorte. 1071 00:37:40,260 --> 00:37:42,130 Nous avons cette série qui est juste de plus en plus. 1072 00:37:42,130 --> 00:37:45,650 1 + 2 + 3 plus 4, ou à l'inverse, plus 6 7 1073 00:37:45,650 --> 00:37:52,610 plus 5 plus 4 ajoute pour aujourd'hui à des fins de l'ordre de n carré. 1074 00:37:52,610 --> 00:37:57,640 >> Permettez-moi donc ce que stipule par trop tri à bulles est également n carré. 1075 00:37:57,640 --> 00:38:01,340 Parce que, avec tri à bulles, chaque fois que je vais dans la liste, 1076 00:38:01,340 --> 00:38:03,100 Je prends à peu près combien de pas? 1077 00:38:03,100 --> 00:38:06,260 Chaque fois que je me suis littéralement marcher de là à là? 1078 00:38:06,260 --> 00:38:07,960 Environ n étapes. 1079 00:38:07,960 --> 00:38:12,650 Mais combien de fois que je pourrais besoin de passer par la liste? 1080 00:38:12,650 --> 00:38:13,920 >> Eh bien, à peu près n temps. 1081 00:38:13,920 --> 00:38:15,680 Peut-être n moins 1, mais à peu près n fois. 1082 00:38:15,680 --> 00:38:16,430 Eh bien, pourquoi est-ce? 1083 00:38:16,430 --> 00:38:19,560 Eh bien, avec tri à bulles, si nous commençons avec tri à bulles, 1084 00:38:19,560 --> 00:38:23,570 avec la liste dans le pire possible situation qui est complètement nouveau 1085 00:38:23,570 --> 00:38:25,550 vers l'arrière, ce qui va se passer? 1086 00:38:25,550 --> 00:38:28,830 Je passe par la liste, et le nombre on appartient tout le chemin là-bas. 1087 00:38:28,830 --> 00:38:33,280 >> Mais avec tri à bulles, ne jusqu'où on déplacer sur mon premier passage dans la liste? 1088 00:38:33,280 --> 00:38:36,620 Combien de points peut-il obtenir plus proche de l'endroit correct? 1089 00:38:36,620 --> 00:38:37,240 Juste un. 1090 00:38:37,240 --> 00:38:40,281 Donc, si vous sorte de la raison à travers cela, à chaque fois grâce à cet algorithme, 1091 00:38:40,281 --> 00:38:41,880 Prenant environ n les étapes de David. 1092 00:38:41,880 --> 00:38:44,940 Mais combien de passes la liste est-il 1093 00:38:44,940 --> 00:38:49,060 va prendre pour l'un de bulle vers la gauche où il appartient? 1094 00:38:49,060 --> 00:38:51,840 >> Il a de se déplacer comme, n espaces de cette façon. 1095 00:38:51,840 --> 00:38:57,960 Il suffit donc de faire le tri de la liste, Je dois marcher en arrière n fois. 1096 00:38:57,960 --> 00:39:01,540 Et chaque fois, je suis regardant n éléments. 1097 00:39:01,540 --> 00:39:05,410 Donc, faire des choses n n fois sur l'ordre de n carré. 1098 00:39:05,410 --> 00:39:07,220 >> Maintenant, nous allons voir dans certains des shorts qui 1099 00:39:07,220 --> 00:39:10,440 sont intégrés dans le prochain problème de CS50 fixer, une autre approche à ceux-ci, 1100 00:39:10,440 --> 00:39:13,490 mais pour l'instant, nous allons examiner tout d'autres fois de suite, 1101 00:39:13,490 --> 00:39:16,840 surtout si ceux tri prennent un peu de temps pour sombrer dans. 1102 00:39:16,840 --> 00:39:21,790 Qu'est-ce qu'un algorithme que nous avons déjà vu qui prend de l'ordre de n étapes? 1103 00:39:21,790 --> 00:39:27,560 >> Ce qui devrait prendre un certain nombre linéaire des mesures que nous avons vu jusqu'à présent? 1104 00:39:27,560 --> 00:39:29,350 Qu'est ce que c'est? 1105 00:39:29,350 --> 00:39:30,480 La recherche dans l'annuaire de téléphone. 1106 00:39:30,480 --> 00:39:31,390 Le premier algorithme. 1107 00:39:31,390 --> 00:39:31,560 Droit? 1108 00:39:31,560 --> 00:39:33,650 Où nous sommes linéairement la recherche de Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 En effet. 1110 00:39:34,150 --> 00:39:37,180 De la semaine zéro, quand je commencé tourner une page à la fois, 1111 00:39:37,180 --> 00:39:40,095 et même je l'ai dit qu'il était gentil d'un algorithme de sensation linéaire, 1112 00:39:40,095 --> 00:39:42,720 et nous avons eu cette image sur le bord avec la ligne rouge droite 1113 00:39:42,720 --> 00:39:44,678 et le jaune droite ligne, ceux qui étaient effectivement 1114 00:39:44,678 --> 00:39:46,810 algorithmes qui sont en grand O de n. 1115 00:39:46,810 --> 00:39:50,680 >> Parce que pour trouver Mike Smith dans un téléphone livre de n pages, dans le pire des cas, 1116 00:39:50,680 --> 00:39:52,422 n pourrait me prendre des mesures. 1117 00:39:52,422 --> 00:39:53,630 Qu'en est-il prendre les présences? 1118 00:39:53,630 --> 00:39:55,790 Un deux trois quatre cinq six. 1119 00:39:55,790 --> 00:39:59,420 Quelle est la durée de cette algorithme pour prendre les présences? 1120 00:39:59,420 --> 00:40:03,070 Big O n, car en théorie je faire pointer tout le monde dans la salle. 1121 00:40:03,070 --> 00:40:05,861 >> Maintenant, en aparté, que dire de la autre optimisation de la semaine zéro? 1122 00:40:05,861 --> 00:40:08,117 Deux, quatre, six, huit, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Un chercheur en informatique serait réaliser, attendez une minute, 1124 00:40:10,200 --> 00:40:12,320 qui est de l'ordre de n divisé par deux étapes. 1125 00:40:12,320 --> 00:40:12,820 Droit? 1126 00:40:12,820 --> 00:40:14,444 Parce que je fais deux personnes à la fois. 1127 00:40:14,444 --> 00:40:17,015 Mais nous allons ignorer ces termes d'ordre inférieur, 1128 00:40:17,015 --> 00:40:19,140 et nous allons juste jeter le diviser par 2, 1129 00:40:19,140 --> 00:40:21,830 et dire simplement, grand O n pour que l'algorithme ainsi. 1130 00:40:21,830 --> 00:40:22,760 >> Qu'en est-il celui-là? 1131 00:40:22,760 --> 00:40:26,170 Nous passerons sur certains d'entre eux, mais ce était un algorithme qui était journal de n? 1132 00:40:26,170 --> 00:40:29,900 Cela a pris environ log n étapes? 1133 00:40:29,900 --> 00:40:30,870 Le diviser pour régner. 1134 00:40:30,870 --> 00:40:31,369 Exactement. 1135 00:40:31,369 --> 00:40:33,900 Comme l'exemple du livre de téléphone dans semaine zéro et plus tôt aujourd'hui, 1136 00:40:33,900 --> 00:40:36,191 où nous avons divisé le problème Encore et encore et encore. 1137 00:40:36,191 --> 00:40:39,070 Nous avons tiré sur le conseil de la semaine zéro comme une ligne verte incurvée, 1138 00:40:39,070 --> 00:40:41,460 et nous avons dit ce jour-là, il était un algorithme logarithmique. 1139 00:40:41,460 --> 00:40:44,970 >> Et en effet, le nombre d'étapes qu'il prend pour effectuer diviser et conquérir, 1140 00:40:44,970 --> 00:40:48,610 ou recherche binaire que nous allons commencer l'appelant, comme dans le livre de téléphone, 1141 00:40:48,610 --> 00:40:50,680 est de l'ordre de journal et les étapes. 1142 00:40:50,680 --> 00:40:52,470 Et cela est un peu un étrange. 1143 00:40:52,470 --> 00:40:54,910 >> Qu'est-ce que fait un pas, ou plus précisément 1144 00:40:54,910 --> 00:40:56,240 un nombre constant d'étapes? 1145 00:40:56,240 --> 00:40:58,865 Peut-être qu'il est deux, peut-être il est trois, mais un informaticien juste 1146 00:40:58,865 --> 00:41:01,423 simplifie aussi grand O de 1, un certain nombre constant d'étapes. 1147 00:41:01,423 --> 00:41:04,256 Qu'est-ce quelque chose que vous pourriez le faire prend un nombre constant d'étapes? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Quelle est la durée de fonctionnement de frappant? 1150 00:41:10,930 --> 00:41:11,920 Constante de temps. 1151 00:41:11,920 --> 00:41:12,420 Droit? 1152 00:41:12,420 --> 00:41:15,490 Comme, quelle est la durée de fonctionnement de faire quelque chose qui prend un seul 1153 00:41:15,490 --> 00:41:18,570 fonctionnement, comme imprimer F Bonjour tout le monde. 1154 00:41:18,570 --> 00:41:24,110 Cela pourrait être considéré comme la constante de temps, moins moins le cas de coin avec impression F, 1155 00:41:24,110 --> 00:41:28,260 Quel pourrait être le temps d'exécution de l'impression F effectivement être? 1156 00:41:28,260 --> 00:41:28,790 Et pourquoi? 1157 00:41:28,790 --> 00:41:30,550 Quel est n mesure dans ce cas? 1158 00:41:30,550 --> 00:41:32,251 >> AUDIENCE: [inaudible]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. Malan: Exactement. 1160 00:41:33,250 --> 00:41:34,900 Le nombre de caractères nous voulons imprimer. 1161 00:41:34,900 --> 00:41:36,191 Il est donc très sensible au contexte. 1162 00:41:36,191 --> 00:41:39,910 Aujourd'hui, nous nous concentrons beaucoup sur les lettres et chiffres ici sur la carte. 1163 00:41:39,910 --> 00:41:43,540 Mais il pourrait également être caractères dans une chaîne réelle. 1164 00:41:43,540 --> 00:41:46,420 Donc, il se trouve qu'il ya un autre mesure qui va commencer à se soucier, 1165 00:41:46,420 --> 00:41:48,530 et voilà le contraire de Big O, pour ainsi dire. 1166 00:41:48,530 --> 00:41:50,120 >> Voilà notation oméga. 1167 00:41:50,120 --> 00:41:53,380 Alors que Big O signifie ce qui est, la borne supérieure sur votre temps de fonctionnement? 1168 00:41:53,380 --> 00:41:55,580 Au maximum, combien de temps pourrait prendre quelque chose? 1169 00:41:55,580 --> 00:41:59,250 Omega-- désolé de ce qui continue à venir up-- est à l'opposé de cela, 1170 00:41:59,250 --> 00:42:02,960 de sorte qu'il est une borne inférieure sur le quantité de fois que quelque chose pourrait prendre. 1171 00:42:02,960 --> 00:42:10,480 >> Ainsi. par exemple, ce qui est un algorithme qui prend des mesures toujours n carrés? 1172 00:42:10,480 --> 00:42:15,600 Eh bien, l'un des algorithmes nous avons vu aujourd'hui, en fait, peut-être aussi. 1173 00:42:15,600 --> 00:42:16,720 Sorte de sélection. 1174 00:42:16,720 --> 00:42:18,270 Sélection est en quelque sorte assez stupide. 1175 00:42:18,270 --> 00:42:21,760 Même si le regrette algorithm--, même si le tableau est déjà trié, 1176 00:42:21,760 --> 00:42:24,150 tri par sélection va continuer à marcher dans la liste 1177 00:42:24,150 --> 00:42:28,907 pour vous assurer qu'il a le plus petit élément nouveau et encore et encore. 1178 00:42:28,907 --> 00:42:31,740 Et même si vous les humains dans le auditoire que, attendez une minute, 1179 00:42:31,740 --> 00:42:33,948 vous avez déjà passé le plus petit élément, l'ordinateur 1180 00:42:33,948 --> 00:42:37,300 ne sait pas que jusqu'à ce qu'il ressemble tout le chemin à travers la liste. 1181 00:42:37,300 --> 00:42:40,240 De même, une limite inférieure que pourraient également être pris en compte 1182 00:42:40,240 --> 00:42:42,000 pourrait être le temps linéaire. 1183 00:42:42,000 --> 00:42:48,260 >> Combien de temps faut-il pour Trier n éléments dans le meilleur 1184 00:42:48,260 --> 00:42:52,420 cas en utilisant quelque chose comme tri à bulles? 1185 00:42:52,420 --> 00:42:54,280 Supposons que votre liste est déjà trié. 1186 00:42:54,280 --> 00:42:56,696 Nous avons dit bubble sort prend l'ordre de n carré étapes. 1187 00:42:56,696 --> 00:42:59,640 Mais que faire si il est déjà triée? 1188 00:42:59,640 --> 00:43:02,310 Que faire si vous vous rendez compte après un passage à travers la matrice 1189 00:43:02,310 --> 00:43:03,540 que vous avez fait aucun swap? 1190 00:43:03,540 --> 00:43:05,970 Avez-vous besoin de continuer à faire plus de passes? 1191 00:43:05,970 --> 00:43:06,470 >> Non. 1192 00:43:06,470 --> 00:43:10,340 Donc, une limite inférieure tri à bulles pourrait être considéré comme linéaire. 1193 00:43:10,340 --> 00:43:11,830 Omega de n. 1194 00:43:11,830 --> 00:43:14,450 Et nous pouvons regarder d'autres de ces ainsi. 1195 00:43:14,450 --> 00:43:17,990 Donc, nous allons jeter un coup d'œil à seulement une visualisation ici 1196 00:43:17,990 --> 00:43:20,790 de voir comment ceux-ci se distinguent. 1197 00:43:20,790 --> 00:43:24,592 Je vais descendre ici dans cette page qui est disponible sur le site Web de C50, 1198 00:43:24,592 --> 00:43:27,550 mais ce sera une douleur à faire fonctionner, car il utilise une technologie appelée 1199 00:43:27,550 --> 00:43:30,560 Applets Java, qui est un largement non pris en charge ces jours, 1200 00:43:30,560 --> 00:43:32,730 au moins par Chrome et de certains autres. 1201 00:43:32,730 --> 00:43:37,070 >> Et laissez-moi aller de l'avant et la vitesse de cette et d'expliquer ce qui se passe. 1202 00:43:37,070 --> 00:43:40,840 Ceci est une démonstration de la bulle Trier, le premier algorithme que nous avons regardé. 1203 00:43:40,840 --> 00:43:43,950 Et il est une visualisation en ce que chaque de ces barres représente un nombre. 1204 00:43:43,950 --> 00:43:45,710 Le plus gros de la barre, plus le nombre. 1205 00:43:45,710 --> 00:43:47,520 Le plus petit de la barre, plus le nombre. 1206 00:43:47,520 --> 00:43:50,353 Et ce que vous pouvez voir visuellement, même si cela se passe super rapide, 1207 00:43:50,353 --> 00:43:53,699 est que la barre rouge est comme moi, marche arrière et des problèmes de fixation de suite. 1208 00:43:53,699 --> 00:43:56,740 Vous pouvez voir que les plus gros éléments sont en effet bouillonnant vers la droite, 1209 00:43:56,740 --> 00:43:59,650 et les éléments plus petits sont barbotage jusqu'à la gauche. 1210 00:43:59,650 --> 00:44:01,870 Et ici, si nous effectivement regarder de plus près, 1211 00:44:01,870 --> 00:44:04,330 nous pouvons réellement compter le nombre de comparaisons et des swaps 1212 00:44:04,330 --> 00:44:05,350 qui ont été faites. 1213 00:44:05,350 --> 00:44:07,360 >> Mais à la place, regardons à la deuxième algorithme 1214 00:44:07,360 --> 00:44:11,240 nous avons vu précédemment avec notre bénévoles, la sélection de tri. 1215 00:44:11,240 --> 00:44:13,500 Visuellement, il a un effet très différent. 1216 00:44:13,500 --> 00:44:16,820 Mais il est, à nouveau, très intuitive, dans que nous gardons en sélectionnant la prochaine plus petite 1217 00:44:16,820 --> 00:44:18,660 élément, et nous avons eu un peu de chance. 1218 00:44:18,660 --> 00:44:20,110 Qui se sentait fondamentalement plus rapide. 1219 00:44:20,110 --> 00:44:22,840 Mais si nous avons couru encore et encore et encore avec beaucoup d'entrées, 1220 00:44:22,840 --> 00:44:26,680 nous verrions qu'il est bien toujours en grand O n carré. 1221 00:44:26,680 --> 00:44:29,920 >> Faisons un dernier ici, le tri par insertion, 1222 00:44:29,920 --> 00:44:33,180 qui était le troisième algorithme nous avons regardé, et le rappel 1223 00:44:33,180 --> 00:44:36,700 que celui-ci traite de la éléments comme il les rencontre, 1224 00:44:36,700 --> 00:44:39,290 Mais alors, il peut-être des changements la parole à faire de la place, 1225 00:44:39,290 --> 00:44:41,660 insertion d'éléments où ils appartiennent. 1226 00:44:41,660 --> 00:44:45,330 >> Et cela aussi finit par donner le résultat final. Maintenant, tous les trois de ceux 1227 00:44:45,330 --> 00:44:46,490 senti assez vite. 1228 00:44:46,490 --> 00:44:48,740 Et en effet, je les ai couru à un assez bon clip. 1229 00:44:48,740 --> 00:44:52,510 Mais, fondamentalement, ils sont tous assez horrible, pour être honnête. 1230 00:44:52,510 --> 00:44:56,960 Tous ces algorithmes jusqu'ici qui fonctionnent en grande O n carré 1231 00:44:56,960 --> 00:44:59,270 prendre un peu de temps à courir à la fin. 1232 00:44:59,270 --> 00:45:01,920 >> Et en effet, nous pouvons voir et sentir ce enfin 1233 00:45:01,920 --> 00:45:04,090 si je tire cette troisième et dernière démo. 1234 00:45:04,090 --> 00:45:05,840 Ceci est un autre visualisation qui va 1235 00:45:05,840 --> 00:45:08,500 pour montrer tri à bulles sur la gauche, tri par sélection dans le milieu, 1236 00:45:08,500 --> 00:45:13,410 et quelque chose, comme l'un de nos main soulève suggéré plus tôt, 1237 00:45:13,410 --> 00:45:15,020 tri par fusion sur la droite. 1238 00:45:15,020 --> 00:45:16,937 Un diviser pour mieux régner stratégie sur la droite. 1239 00:45:16,937 --> 00:45:19,520 Et qui est, en fait, ce que nous sommes va regarder le mercredi. 1240 00:45:19,520 --> 00:45:21,990 Mais laisser le temps de ces pour fonctionner en parallèle. 1241 00:45:21,990 --> 00:45:26,765 Il est à peu près le même nombre de éléments, le tout fonctionnant en même temps. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble sorte vs sélection Trier vs tri par fusion. 1244 00:45:34,440 --> 00:45:36,760 >> Maintenant, ils sont tous en cours d'exécution en théorie en même temps. 1245 00:45:36,760 --> 00:45:39,830 Le CPU tourne à la même vitesse, mais vous 1246 00:45:39,830 --> 00:45:44,014 peut sentir combien ennuyeux cela est va très rapidement devenir, 1247 00:45:44,014 --> 00:45:45,930 et à quelle vitesse lorsque nous injectons un peu de la semaine 1248 00:45:45,930 --> 00:45:49,330 Les algorithmes de zéro peut nous accélérer les choses. 1249 00:45:49,330 --> 00:45:51,760 >> Et maintenant, nous allons comparer ceux-ci dans une dernière forme. 1250 00:45:51,760 --> 00:45:55,710 Je vais aller de l'avant sur le site de CS50, où 1251 00:45:55,710 --> 00:45:59,020 nous avons ce lien finale pour aujourd'hui, où quelqu'un sur internet 1252 00:45:59,020 --> 00:46:03,960 mettre ensemble gentiment une vidéo capture ce tri différente 1253 00:46:03,960 --> 00:46:07,510 algorithmes ressemblent. 1254 00:46:07,510 --> 00:46:09,577 Ceci est le tri par insertion. 1255 00:46:09,577 --> 00:46:12,072 >> [BIP] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Lequel vous postulez une fréquence basé sur la hauteur de la barre de bar. 1258 00:46:16,850 --> 00:46:19,826 Ceci est tri à bulles. 1259 00:46:19,826 --> 00:46:21,822 >> [BIP Warped] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Prochainement est-- venir jusqu'à la prochaine sélection sorte est--, 1262 00:46:45,774 --> 00:46:48,820 où, là encore, nous sommes sélection le prochain plus petit élément, 1263 00:46:48,820 --> 00:46:51,820 et nous pouvons le voir grandir de gauche à droite. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Fusionner sorte, notre gagnant jusqu'à aujourd'hui. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Remarquez comment il est divisant les choses dans [inaudible] la moitié et les quartiers. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Trier Gnome, dont nous avons pas parlé, et crée visuellement 1270 00:47:21,660 --> 00:47:24,450 et audally un peu forme et son différent. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Aller et retour, nettoyage choses. 1273 00:47:30,160 --> 00:47:32,230 Consultez également heapsort sur le site de ce type. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> Et c'est tout. 1276 00:47:36,810 --> 00:47:38,210 Nous vous verrons la prochaine fois. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing ET MUSIQUE] 1279 00:47:48,334 --> 00:50:24,839