1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [RIPRODUZIONE DI BRANI MUSICALI] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. MALAN: Questo è CS50. 5 00:00:12,550 --> 00:00:14,612 E questo è l'inizio di tre settimana. 6 00:00:14,612 --> 00:00:16,820 Quindi abbiamo un sacco di eccitante cose da coprire oggi. 7 00:00:16,820 --> 00:00:20,160 Un sacco di opportunità per i volontari sul palco. 8 00:00:20,160 --> 00:00:22,780 E alla fine, oggi è non si tratta di codice a tutti. 9 00:00:22,780 --> 00:00:24,820 Ma si tratta di idee, e si tratta di algoritmi, 10 00:00:24,820 --> 00:00:28,420 e in realtà riportando alcune delle le lezioni apprese dalla settimana pari a zero, 11 00:00:28,420 --> 00:00:31,910 quale richiamo, noi ha introdotto questa mostruosità. 12 00:00:31,910 --> 00:00:33,880 E indebitamento ispirazione questo, per iniziare 13 00:00:33,880 --> 00:00:36,879 per risolvere sempre più sofisticati problemi algoritmicamente. 14 00:00:36,879 --> 00:00:38,420 Ma prima, un paio di annunci. 15 00:00:38,420 --> 00:00:42,020 Quindi uno, se volete aderire Personale e compagni di classe del CS50 a pranzo 16 00:00:42,020 --> 00:00:44,670 questo Venerdì, sia qui che in Cambridge, ea New Haven, 17 00:00:44,670 --> 00:00:48,060 si prega di visitare il corso del sito web, dove un URL può essere trovato. 18 00:00:48,060 --> 00:00:50,390 Lezione questo Mercoledì sarà non essere qui a Sanders. 19 00:00:50,390 --> 00:00:53,610 Sarà solo online, così sintonizzarsi sul sito di CS50, 20 00:00:53,610 --> 00:00:55,850 se qui a Cambridge o New Haven pure. 21 00:00:55,850 --> 00:00:58,110 >> E allora il problema impostare due è già nelle vostre mani. 22 00:00:58,110 --> 00:01:03,067 Se non avete ancora tuffato in, mi permetta per offrire la suggestione parole forti 23 00:01:03,067 --> 00:01:05,150 che, soprattutto ora, come il problema pone anticipo, 24 00:01:05,150 --> 00:01:08,669 davvero si vuole da adesso, se non dilettarsi un po 'durante il fine settimana o prima 25 00:01:08,669 --> 00:01:10,710 quando in primo luogo escono su Venerdì, perché ti 26 00:01:10,710 --> 00:01:14,380 trovano che non sono necessariamente sempre più lungo o più impegnativo per 27 00:01:14,380 --> 00:01:14,950 se. 28 00:01:14,950 --> 00:01:17,575 Penso che troverete che, in generale, tendono ad assumere più o meno 29 00:01:17,575 --> 00:01:18,892 intorno stessa quantità di tempo. 30 00:01:18,892 --> 00:01:20,850 Ma dipende certamente lo studente, e 31 00:01:20,850 --> 00:01:22,880 dipende dalla mentalità con il quale ci si avvicina. 32 00:01:22,880 --> 00:01:24,910 Ma invariabilmente, si sta andando a correre contro qualche muro, 33 00:01:24,910 --> 00:01:26,350 e si sta andando a colpire alcuni bug, e sei solo 34 00:01:26,350 --> 00:01:27,950 non sarà in grado di ottenere su di esso ad un certo punto. 35 00:01:27,950 --> 00:01:31,380 Ed è estremamente prezioso per poter di allontanarsi, tornare il giorno successivo, 36 00:01:31,380 --> 00:01:35,286 andare in orario d'ufficio, post su CS50 Discutere o simili, per ottenere effettivamente sbloccato. 37 00:01:35,286 --> 00:01:36,160 Modo da tenere a mente. 38 00:01:36,160 --> 00:01:40,830 A partire prima possibile è la cosa migliore che puoi fare. 39 00:01:40,830 --> 00:01:44,160 Quindi, ecco dove siamo partiti la classe, oltre a settimana pari a zero. 40 00:01:44,160 --> 00:01:47,441 E possiamo ottenere un volontario qui per aiutarmi a trovare microfoni? 41 00:01:47,441 --> 00:01:47,940 OK. 42 00:01:47,940 --> 00:01:48,900 In piedi già. 43 00:01:48,900 --> 00:01:50,080 Vieni su. 44 00:01:50,080 --> 00:01:53,707 Indovinate che è così che sta andando a lavorare. 45 00:01:53,707 --> 00:01:54,415 Come ti chiami? 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 Vieni su. 49 00:01:57,910 --> 00:01:58,619 Felice di conoscerti. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Piacere di conoscerti. 51 00:01:59,910 --> 00:02:02,772 DAVID J. MALAN: E lei fosse qui con noi in settimana a zero, naturalmente. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: ero. 53 00:02:03,028 --> 00:02:03,160 Io ero. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. MALAN: Così si potrebbe andare avanti e trovare per noi Mike Smith, 55 00:02:05,868 --> 00:02:08,639 piu 'veloce che puoi? 56 00:02:08,639 --> 00:02:10,639 Piu 'veloce che puoi. 57 00:02:10,639 --> 00:02:13,756 Letteralmente strappando il problema a metà come si deve. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Uhm. 59 00:02:15,130 --> 00:02:17,380 DAVID J. MALAN: Letteralmente strappando il problema a metà. 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 Molto bene. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. MALAN: OK. 65 00:02:23,700 --> 00:02:24,200 Bene. 66 00:02:24,200 --> 00:02:24,701 Grazie. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Molto bene. 68 00:02:25,700 --> 00:02:26,210 OK. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. MALAN: E così ora, hai whittled giù 70 00:02:27,610 --> 00:02:29,320 alla metà della dimensione del problema. 71 00:02:29,320 --> 00:02:31,267 Ora, siamo giù a un quarto. 72 00:02:31,267 --> 00:02:33,475 Stai pagando attenzione da che parte stiamo mantenendo? 73 00:02:33,475 --> 00:02:34,405 >> [Ride] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Sì, io think-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. MALAN: Che cosa siamo in sezione? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: Silenziatori, così. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. MALAN: OK. 78 00:02:39,941 --> 00:02:42,810 Ma Mike Smith sta andando essere dopo Silenziatori. 79 00:02:42,810 --> 00:02:44,130 Così-- 80 00:02:44,130 --> 00:02:48,180 >> [Ride] 81 00:02:48,180 --> 00:02:48,742 >> Tutto ok. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Dove stiamo cercando? 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: Ora, siamo in chirurgico. 86 00:02:54,760 --> 00:02:57,840 Ora, i medici. 87 00:02:57,840 --> 00:02:58,340 Adesso-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- andiamo con reali. 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 OK. 92 00:03:01,470 --> 00:03:03,700 Se avete bisogno reale. 93 00:03:03,700 --> 00:03:05,250 Ora, da che parte è Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: In questo modo. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. MALAN: Quale modo? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Aspetta. 97 00:03:08,240 --> 00:03:08,790 M è-- giusto? 98 00:03:08,790 --> 00:03:09,110 Abbiamo iniziato with-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. MALAN: Sì. 100 00:03:10,090 --> 00:03:10,650 Sono lasciati. 101 00:03:10,650 --> 00:03:11,430 Destra. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Sì. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. MALAN: Così Mike qui. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Che cosa? 105 00:03:13,990 --> 00:03:14,665 >> [Ride] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Cattivo esempio, ragazzi. 108 00:03:18,330 --> 00:03:18,830 Scusate. 109 00:03:18,830 --> 00:03:21,610 DAVID J. MALAN: Questo insegnerà di saltare dalla sedia. 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 Ti ho preso. 113 00:03:23,390 --> 00:03:24,670 Ti ho preso. 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 Questo è-- OK, ti ho fatto. 117 00:03:26,812 --> 00:03:27,520 Smith proprio qui? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. MALAN: Smith, grazie. 119 00:03:28,894 --> 00:03:30,535 Quindi continuerò guardare Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Oh, sì. 121 00:03:30,790 --> 00:03:31,340 No no no. 122 00:03:31,340 --> 00:03:31,600 Oh no. 123 00:03:31,600 --> 00:03:31,940 Questo è mio. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. MALAN: Oh, hai Smith. 125 00:03:32,580 --> 00:03:33,415 OK. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Sì, Smith ha ottenuto proprio qui. 127 00:03:34,040 --> 00:03:34,700 Scusate ragazzi. 128 00:03:34,700 --> 00:03:35,860 Ho pensato che Michael-- erano alla ricerca di Michael. 129 00:03:35,860 --> 00:03:36,550 Scusate. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. MALAN: Va bene. 131 00:03:37,550 --> 00:03:39,950 Va bene, ora siamo in Paccini e Figli. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini e figli. 133 00:03:41,242 --> 00:03:43,158 DAVID J. MALAN: Solo tu e io siamo in su questo. 134 00:03:43,158 --> 00:03:44,050 OK. 135 00:03:44,050 --> 00:03:45,130 Dove siamo Mike Smith. 136 00:03:45,130 --> 00:03:45,830 Fabbro. 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 Siamo in R per la spazzatura. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Rifiuti. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Si tratta di andare a prendere un po '. 143 00:03:52,480 --> 00:03:54,340 >> [Ride] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. MALAN: Scarpe. 146 00:03:56,720 --> 00:03:58,080 Siamo in scarpe. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Ora stiamo gonna-- 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. MALAN: Nizza. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: Which-- 150 00:04:01,980 --> 00:04:03,620 [Ride] 151 00:04:03,620 --> 00:04:05,440 Oh, questo è grande. 152 00:04:05,440 --> 00:04:06,910 [Ride] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. MALAN: Va bene. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Oh, questo è buono. 156 00:04:11,365 --> 00:04:14,425 Non penso che ho intenzione di avere amici PSAT dopo questo. 157 00:04:14,425 --> 00:04:15,300 DAVID J. MALAN: Good. 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 Quindi cerchiamo di distruggere questo a metà. 163 00:04:21,600 --> 00:04:22,270 Va bene. 164 00:04:22,270 --> 00:04:25,606 Questo finisce male comunque, perché Mike Smith non sarà nelle pagine gialle. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. MALAN: No, va bene. 167 00:04:27,140 --> 00:04:28,930 Ma facciamo finta come lui è in questa pagina. 168 00:04:28,930 --> 00:04:33,260 Così ora, hai tagliuzzato il problema verso il basso ad una pagina, e abbiamo trovato Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [INCORAGGIANTE] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 Bene grazie. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 OK. 174 00:04:41,200 --> 00:04:43,646 E 'stato straordinario. 175 00:04:43,646 --> 00:04:45,954 Ma era ancora più veloce di ricerca lineare, 176 00:04:45,954 --> 00:04:47,870 in cui si comincia a inizio del libro, 177 00:04:47,870 --> 00:04:51,210 e ci spostiamo il nostro modo da sinistra a destra, alla fine alla ricerca di Mike Smith. 178 00:04:51,210 --> 00:04:53,540 E così, se la rubrica telefonica aveva forse 1.000 pagine, 179 00:04:53,540 --> 00:04:56,300 forse ci sarebbe voluto noi 10 o giù di lì di pagina lacrime. 180 00:04:56,300 --> 00:04:59,380 >> Ma si può avere sfruttato toccato un presupposto 181 00:04:59,380 --> 00:05:03,602 Durante tutto questo, che vale a dire che la rubrica telefonica in anticipo era quello? 182 00:05:03,602 --> 00:05:04,310 PUBBLICO: Ordinato. 183 00:05:04,310 --> 00:05:05,000 DAVID J. MALAN: E 'ordinato. 184 00:05:05,000 --> 00:05:05,160 Destra? 185 00:05:05,160 --> 00:05:07,909 E 'in ordine alfabetico, in modo da che tutti questi nomi e numeri 186 00:05:07,909 --> 00:05:11,230 sono allineati dalla A di al Z di, e in ordine alfabetico in mezzo. 187 00:05:11,230 --> 00:05:13,100 Ma oggi, ci chiediamo ora la domanda, beh, 188 00:05:13,100 --> 00:05:16,170 come ha fatto Verizon o il telefono società lo fanno in quello stato? 189 00:05:16,170 --> 00:05:19,560 >> Perché è una cosa da sfruttare tale ipotesi, e quindi, 190 00:05:19,560 --> 00:05:22,570 risolvere un problema con un algoritmo più efficiente. 191 00:05:22,570 --> 00:05:24,900 Ma non abbiamo mai veramente ha chiesto in settimana a zero, beh, 192 00:05:24,900 --> 00:05:27,790 quanto costa Verizon o qualcun altro 193 00:05:27,790 --> 00:05:29,620 per ottenere che rubrica in modo ordinato? 194 00:05:29,620 --> 00:05:29,780 >> Destra? 195 00:05:29,780 --> 00:05:31,529 Non importa se guardando Mike Smith 196 00:05:31,529 --> 00:05:35,190 è super veloce, se si prende un anno per ordinare le pagine inizialmente. 197 00:05:35,190 --> 00:05:35,690 Destra? 198 00:05:35,690 --> 00:05:38,620 Si potrebbe anche solo vagliare attraverso una rubrica randomizzato, 199 00:05:38,620 --> 00:05:40,690 se sta andando essere super costoso a risolverlo. 200 00:05:40,690 --> 00:05:42,350 Quindi, se siamo in grado di avere un altro volontario. 201 00:05:42,350 --> 00:05:46,350 Diamo uno sguardo qui a come siamo arrivati ​​su up-- might-- come 202 00:05:46,350 --> 00:05:48,100 potremmo andare sull'ordinamento questi. 203 00:05:48,100 --> 00:05:51,990 >> E se la Giordania potrebbe effettivamente unirsi a noi qui sul palco. 204 00:05:51,990 --> 00:05:55,100 Andiamo per un attimo. 205 00:05:55,100 --> 00:05:56,359 Come ti chiami? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. MALAN: Caroline, andiamo su. 208 00:05:58,691 --> 00:06:02,070 E sarai unito da me e Giordania qui. 209 00:06:02,070 --> 00:06:03,800 Caroline, grazie. 210 00:06:03,800 --> 00:06:04,300 Tutto ok. 211 00:06:04,300 --> 00:06:08,330 Quindi quello che abbiamo qui per Caroline è di 26 azzurri libri 212 00:06:08,330 --> 00:06:10,747 che FAS utilizza per amministrare alcuni esami finali. 213 00:06:10,747 --> 00:06:13,330 Questi sono sempre difficili da trovare, ma quello che abbiamo fatto in anticipo 214 00:06:13,330 --> 00:06:15,800 è che abbiamo messo il nome di qualcuno sul fronte di ciascuno di questi, 215 00:06:15,800 --> 00:06:18,133 ma abbiamo mantenuto semplice da poi mettere i nomi completi. 216 00:06:18,133 --> 00:06:22,720 Così avremmo messo la persona con il nome L, D, J, B, tutto il percorso da A a Z, 217 00:06:22,720 --> 00:06:24,090 ma sono in ordine casuale. 218 00:06:24,090 --> 00:06:26,890 E così, se si farebbe, a parlare la vostra strada attraverso il problema, come si 219 00:06:26,890 --> 00:06:31,620 farlo, si può andare avanti e ordinare questi per noi, dalla A alla Z. 220 00:06:31,620 --> 00:06:34,070 >> PUBBLICO: OK, allora L è come, al centro. 221 00:06:34,070 --> 00:06:35,050 C sta cominciando. 222 00:06:35,050 --> 00:06:42,410 B. J prima di L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. MALAN: Mantenere questa pensato per un secondo. 224 00:06:45,140 --> 00:06:48,910 Perché altrimenti, questo è solo interessa a te, a me, e la Giordania. 225 00:06:48,910 --> 00:06:49,724 Ci siamo. 226 00:06:49,724 --> 00:06:50,640 PUBBLICO: [incomprensibile]. 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 Che stai facendo? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M viene dopo 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, Bene. 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. Sì. 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. Così sembra che sei making-- andare avanti. 238 00:07:10,689 --> 00:07:12,730 Sembra che si sta facendo una grande pila qui, 239 00:07:12,730 --> 00:07:13,910 e una specie di grande pila laggiù. 240 00:07:13,910 --> 00:07:16,230 Così la prima metà dell'alfabeto, seconda metà dell'alfabeto. 241 00:07:16,230 --> 00:07:16,460 OK. 242 00:07:16,460 --> 00:07:16,960 Bene. 243 00:07:16,960 --> 00:07:19,680 Tipo di dividere il problema in due. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Già. 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. Quindi stai tipo di selezione una dopo l'altra, 248 00:07:25,070 --> 00:07:27,620 metterlo a destra oa sinistra, o Z sta succedendo pavimento. 249 00:07:27,620 --> 00:07:28,012 OK. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z sta succedendo sul pavimento. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. MALAN: OK. 252 00:07:29,360 --> 00:07:30,920 Y sta sul pavimento. 253 00:07:30,920 --> 00:07:31,735 Ora possiamo mettere 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 andando a sinistra. 256 00:07:33,700 --> 00:07:36,017 S sta andando bene. 257 00:07:36,017 --> 00:07:37,642 Va bene, A sta andando fino in fondo a sinistra. 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: Ora, bene. 260 00:07:39,873 --> 00:07:43,260 Abbiamo A, B, C W andare laggiù. 261 00:07:43,260 --> 00:07:45,566 Va bene, 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: Nel centro, sto gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. MALAN: OK. 266 00:07:50,000 --> 00:07:52,375 Così ora, stiamo andando a tipo di unire questi vari pali. 267 00:07:52,375 --> 00:08:00,730 Quindi da A a C, poi vedo D, e E, e F, e G e H e I. piacevole. 268 00:08:00,730 --> 00:08:05,540 J, K. E poi, questo mucchio è a testa in giù, ma va bene. 269 00:08:05,540 --> 00:08:06,040 Certo. 270 00:08:06,040 --> 00:08:07,240 Siamo in grado di tagliare alcuni angoli. 271 00:08:07,240 --> 00:08:07,950 OK. 272 00:08:07,950 --> 00:08:10,530 E poi abbiamo bisogno di W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Sì. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. MALAN: Eccellente. 275 00:08:11,880 --> 00:08:14,122 Quindi un grande grazie a Caroline per l'ordinamento questi. 276 00:08:14,122 --> 00:08:15,030 >> [INCORAGGIANTE] 277 00:08:15,030 --> 00:08:17,287 >> Grazie. 278 00:08:17,287 --> 00:08:18,120 Grazie mille. 279 00:08:18,120 --> 00:08:22,910 Così ora consideriamo per un attimo come Caroline è andato a fare che, 280 00:08:22,910 --> 00:08:26,040 e che cosa esattamente ci sono stati in grado a-- come 281 00:08:26,040 --> 00:08:28,409 erano in grado di risolvere il problema quando eravamo solo 282 00:08:28,409 --> 00:08:29,950 dato un sacco di input casuali. 283 00:08:29,950 --> 00:08:31,610 >> Beh, sembra che ci era un po 'di un sistema di lì? 284 00:08:31,610 --> 00:08:32,110 Destra. 285 00:08:32,110 --> 00:08:34,495 Così le lettere precedenti in alfabeto, lei 286 00:08:34,495 --> 00:08:37,120 era messa a sinistra, e la lettere successive dell'alfabeto, 287 00:08:37,120 --> 00:08:38,270 lei stava mettendo nel giusto. 288 00:08:38,270 --> 00:08:40,500 E non appena ha trovato alcune lettere prossimali, quelli 289 00:08:40,500 --> 00:08:43,124 che vanno a destra accanto all'altro, lei avrebbe messo quelle in ordine. 290 00:08:43,124 --> 00:08:46,750 E così abbiamo avuto tipo di questi piccoli mucchi di ingressi ordinati che si verificano. 291 00:08:46,750 --> 00:08:50,540 >> E così che è abbastanza simile a quello che la maggior parte di noi umani avrebbero fatto. 292 00:08:50,540 --> 00:08:53,530 Ci sarebbe una sorta di vagliare attraverso di essa, e ci piacerebbe sorta di avere un meccanismo. 293 00:08:53,530 --> 00:08:56,930 Ma potrebbe essere difficile da scrivere giù in una formula per sé. 294 00:08:56,930 --> 00:08:59,010 Sembrava un po 'più organico di quello. 295 00:08:59,010 --> 00:09:02,560 Quindi vediamo se possiamo ora legato il problema con un minor numero di ingressi. 296 00:09:02,560 --> 00:09:05,170 >> Invece di 26, diamo fare qualcosa di molto meno 297 00:09:05,170 --> 00:09:09,890 con solo dire, sette, dietro queste porte, per così dire. 298 00:09:09,890 --> 00:09:11,300 Ci sono solo sette numeri? 299 00:09:11,300 --> 00:09:15,240 E se l'obiettivo ora mano è quello di trovare un valore, 300 00:09:15,240 --> 00:09:17,850 vediamo come in modo efficiente siamo in grado di andare a fare questo. 301 00:09:17,850 --> 00:09:22,460 E vediamo se possiamo ora iniziare ad applicare alcuni numeri, 302 00:09:22,460 --> 00:09:26,310 o alcune formule con cui descrivere l'efficienza della nostra rubrica 303 00:09:26,310 --> 00:09:31,060 Algoritmo, il nostro algoritmo libro esame, e più in generale, la ricerca di informazioni. 304 00:09:31,060 --> 00:09:34,770 >> Quindi, per questo, mi permetta di andare avanti, e sul touch screen qui, 305 00:09:34,770 --> 00:09:41,100 mettere su un browser web che ha esattamente questi sette porte. 306 00:09:41,100 --> 00:09:46,670 E se avessimo potuto ottenere un altro volontariato a venire su qui, 307 00:09:46,670 --> 00:09:48,480 Ho messo queste stesse porte qui. 308 00:09:48,480 --> 00:09:49,170 Volontario rapido. 309 00:09:49,170 --> 00:09:51,130 >> Questo tra-- demo sono in corso di un sempre più veloce ora. 310 00:09:51,130 --> 00:09:51,600 Vieni giù. 311 00:09:51,600 --> 00:09:52,308 Come ti chiami? 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 Va bene, Trevor, vieni giù. 315 00:09:55,770 --> 00:09:59,212 Così Trevor si è offerto volontario qui per fare un problema simile, ma uno che è 316 00:09:59,212 --> 00:10:02,170 stretto nella portata, e che sta andando per permetterci di cercare di formalizzare ora 317 00:10:02,170 --> 00:10:03,970 il processo per ordinare questi numeri. 318 00:10:03,970 --> 00:10:05,500 >> Così Trevor, piacere di conoscerti. 319 00:10:05,500 --> 00:10:08,720 Così qui è un array, in modo da parlare, una lista di sette porte. 320 00:10:08,720 --> 00:10:10,327 Vai avanti e noi trovare il numero 50. 321 00:10:10,327 --> 00:10:12,410 E poi, dopo il fatto, raccontarci come lo avete trovato. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Dovrebbe essere-- tutto bene. 324 00:10:20,040 --> 00:10:21,945 Sì, questo è quello qui? 325 00:10:21,945 --> 00:10:24,680 Uh Oh. 326 00:10:24,680 --> 00:10:25,560 OK. 327 00:10:25,560 --> 00:10:26,680 Si è scelto quello. 328 00:10:26,680 --> 00:10:28,690 Bene. 329 00:10:28,690 --> 00:10:29,780 >> E bene. 330 00:10:29,780 --> 00:10:30,970 Ora si è fatto clic che uno. 331 00:10:30,970 --> 00:10:34,060 E lasciate che vi dia il microfono, in modo da avere in un attimo. 332 00:10:34,060 --> 00:10:37,000 Andare avanti e fare clic sul della porta accanto che si intende. 333 00:10:37,000 --> 00:10:39,812 Si Bene. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Posso deselezionare una porta? 335 00:10:41,020 --> 00:10:42,620 DAVID J. MALAN: No, non è possibile deselezionare. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Questo. 338 00:10:43,974 --> 00:10:45,640 DAVID J. MALAN: Dove vuoi andare? 339 00:10:45,640 --> 00:10:46,410 Quale? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: Quello. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. MALAN: No. 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: OK. 343 00:10:48,450 --> 00:10:48,735 Questo. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. MALAN: Sì. 345 00:10:49,020 --> 00:10:49,700 Quello era buono. 346 00:10:49,700 --> 00:10:50,380 Tutto ok. 347 00:10:50,380 --> 00:10:53,900 Allora, qual è stato il tuo algoritmo o Procedura per fare questo, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Ho appena passato attraverso porte fino a quando ho trovato un 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. MALAN: OK. 350 00:10:56,940 --> 00:10:58,150 Ottimo algoritmo. 351 00:10:58,150 --> 00:10:59,540 Così va bene. 352 00:10:59,540 --> 00:11:03,120 Perché in effetti, se rivelo ciò che è dietro queste due porte, cosa 353 00:11:03,120 --> 00:11:06,954 troveremo qui è che abbiamo solo ingresso casuale. 354 00:11:06,954 --> 00:11:08,870 Così che era in realtà come buono come si potrebbe ottenere. 355 00:11:08,870 --> 00:11:12,509 E infatti, si ha meglio esaurientemente ricerca l'intero array, 356 00:11:12,509 --> 00:11:15,300 perché sarebbe stato davvero sfortunato se aveste colpire il numero 357 00:11:15,300 --> 00:11:16,604 50 all'ultimo porta. 358 00:11:16,604 --> 00:11:18,520 Ma cosa succederebbe se invece ti ha dato una supposizione. 359 00:11:18,520 --> 00:11:20,630 Supponiamo che io sorta tutti queste porte intorno, 360 00:11:20,630 --> 00:11:23,500 in modo da avere il numeri ordinati questa volta, 361 00:11:23,500 --> 00:11:29,730 ma questa volta è in realtà un different-- questa volta, 362 00:11:29,730 --> 00:11:32,640 in realtà è ordinato per voi. 363 00:11:32,640 --> 00:11:35,380 E ora l'obiettivo a portata di mano è quello di colpire il numero 50. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. MALAN: Che cosa è l'algoritmo sta per essere? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: Beh, se è ordinato, è sia in corso 367 00:11:39,628 --> 00:11:42,710 essere-- se più grande al più grande, decrescente, sarà il primo, 368 00:11:42,710 --> 00:11:44,751 o se è il contrario, sarà l'ultimo. 369 00:11:44,751 --> 00:11:48,897 Quindi mi limiterò a toccare questo porta, e quindi basta toccare l'ultima porta. 370 00:11:48,897 --> 00:11:49,980 DAVID J. MALAN: Eccellente. 371 00:11:49,980 --> 00:11:50,270 Tutto ok. 372 00:11:50,270 --> 00:11:51,150 Così abbiamo trovato il numero 50. 373 00:11:51,150 --> 00:11:52,970 Così, non appena si sapeva sono stati ordinati, abbiamo 374 00:11:52,970 --> 00:11:55,040 sono stati in grado di sfruttare questa ipotesi. 375 00:11:55,040 --> 00:11:57,040 Quindi sono troppo simili l'esempio rubrica telefonica. 376 00:11:57,040 --> 00:11:59,540 Non appena si hanno, anche con un piccolo problema come questo, 377 00:11:59,540 --> 00:12:02,380 gli ingressi pre-ordinati, possiamo effettivamente trovare il valore discutibilmente 378 00:12:02,380 --> 00:12:03,130 Più efficiente. 379 00:12:03,130 --> 00:12:05,800 >> E io non ti ho detto se era ordinati piccolo al grande, o grande a piccolo, 380 00:12:05,800 --> 00:12:08,080 e quindi era molto ragionevole iniziare ad un'estremità o dall'altra 381 00:12:08,080 --> 00:12:09,750 per scoprire che in realtà valore di destinazione. 382 00:12:09,750 --> 00:12:11,400 Quindi, grazie a Trevor pure. 383 00:12:11,400 --> 00:12:13,260 E io propose-- ben fatto. 384 00:12:13,260 --> 00:12:16,960 Abbiamo un po 'di clip, in realtà, che è tra i nostri momenti preferiti in CS50, 385 00:12:16,960 --> 00:12:19,700 per cui a volte queste demo non abbastanza andare secondo i piani. 386 00:12:19,700 --> 00:12:22,050 E infatti in questo momento, io tirato su l'interfaccia sbagliata 387 00:12:22,050 --> 00:12:23,508 con cui utilizzare il touch screen. 388 00:12:23,508 --> 00:12:24,660 Così che era colpa mia lì. 389 00:12:24,660 --> 00:12:26,600 >> Quindi, questo renderà per la clip del prossimo anno come 390 00:12:26,600 --> 00:12:28,570 motivo per cui stavo cliccando sul mio schermo. 391 00:12:28,570 --> 00:12:31,390 Ma diamo un rapido sguardo a quello che è successo l'anno scorso 392 00:12:31,390 --> 00:12:34,770 con Jay, che è venuto in su, molto come Trevor qui, volontariamente, 393 00:12:34,770 --> 00:12:39,380 e in questo breve filmato, vedrete come questa stessa demo non ha fatto abbastanza 394 00:12:39,380 --> 00:12:41,074 rivelano le stesse lezioni apprese. 395 00:12:41,074 --> 00:12:41,740 [RIPRODUZIONE VIDEO] 396 00:12:41,740 --> 00:12:45,360 -Tutti Io voglio fare ora è di trovare per me, e per noi, 397 00:12:45,360 --> 00:12:51,674 davvero, il numero 50 un passo alla volta. 398 00:12:51,674 --> 00:12:52,450 >> -il Numero 50? 399 00:12:52,450 --> 00:12:53,190 >> -il Numero 50. 400 00:12:53,190 --> 00:12:55,356 E si può rivelare ciò che è dietro ciascuna di queste porte 401 00:12:55,356 --> 00:12:58,540 semplicemente toccando con un dito. 402 00:12:58,540 --> 00:13:00,910 Accidenti. 403 00:13:00,910 --> 00:13:02,870 >> [Ride] 404 00:13:02,870 --> 00:13:03,806 >> [FINE RIPRODUZIONE] 405 00:13:03,806 --> 00:13:05,430 DAVID J. MALAN: Così che è andato molto bene. 406 00:13:05,430 --> 00:13:06,796 Quelli erano le porte non ordinati. 407 00:13:06,796 --> 00:13:08,670 E Jay, naturalmente, trovato tutto troppo in fretta. 408 00:13:08,670 --> 00:13:12,910 Trevor ha fatto un lavoro molto migliore in termini di un momento insegnabile, 409 00:13:12,910 --> 00:13:15,850 per così dire, in quest'anno prendendo più tempo per trovarlo. 410 00:13:15,850 --> 00:13:17,950 Certo, poi abbiamo dato Jay una seconda possibilità, 411 00:13:17,950 --> 00:13:20,320 per cui abbiamo ordinato le porte, proprio come abbiamo fatto per Trevor, 412 00:13:20,320 --> 00:13:22,300 e Trevor ha fatto super ben questo momento. 413 00:13:22,300 --> 00:13:26,124 Ma Jay ha fatto la metà rapidamente. 414 00:13:26,124 --> 00:13:26,790 [RIPRODUZIONE VIDEO] 415 00:13:26,790 --> 00:13:29,650 -Il Obiettivo ora è quello di anche noi trovare il numero 50, 416 00:13:29,650 --> 00:13:33,030 ma farlo algoritmicamente, e ci dicono come si sta andando su di esso. 417 00:13:33,030 --> 00:13:33,660 >> -OK. 418 00:13:33,660 --> 00:13:35,604 >> -E Se lo trovate, di mantenere il film. 419 00:13:35,604 --> 00:13:37,228 Se non lo trovate, si dà indietro. 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 >> - [Incomprensibile] OK. 423 00:13:40,800 --> 00:13:46,236 Così sto andando a controllare le estremità prima per determinare se there's-- Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Applausi] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [FINE RIPRODUZIONE] 427 00:13:55,729 --> 00:13:56,520 DAVID J. MALAN: OK. 428 00:13:56,520 --> 00:13:59,760 Così l'ordinamento chiaramente porte porta ad una maggiore efficienza. 429 00:13:59,760 --> 00:14:01,680 E così, due volte più veloce è quello che volevo dire lì. 430 00:14:01,680 --> 00:14:03,270 E così Jay ha avuto fortuna entrambe le volte. 431 00:14:03,270 --> 00:14:06,685 E ha anche avuto fortuna in quell'ultima anno, ho ordinato alcuni dischi Blu-ray 432 00:14:06,685 --> 00:14:07,560 per dare realmente fuori. 433 00:14:07,560 --> 00:14:09,768 Mi dispiace di quest'anno, abbiamo non ha avuto la stessa, Trevor. 434 00:14:09,768 --> 00:14:11,540 Ma meglio ancora era qualche anno fa. 435 00:14:11,540 --> 00:14:14,820 E alcuni di voi potrebbe sapere questo compagno, Sean, che quando era in CS50, 436 00:14:14,820 --> 00:14:17,780 è stata contestata con l'esatta stesso problema, anche se in SD, 437 00:14:17,780 --> 00:14:19,360 come vedrete presto, back in the day. 438 00:14:19,360 --> 00:14:22,622 E troverete che non solo lui prendere un po 'più lungo di Jay, 439 00:14:22,622 --> 00:14:25,580 un po 'più lungo di Trevor, è stato in realtà questa meravigliosa opportunità 440 00:14:25,580 --> 00:14:29,820 di impegnarsi quasi tutti nel folla a la prezzo è giusto, incoraggiando 441 00:14:29,820 --> 00:14:31,889 lui trovare il numero che stavamo cercando. 442 00:14:31,889 --> 00:14:32,930 Andiamo. prendere una rapida occhiata. 443 00:14:32,930 --> 00:14:33,320 >> [RIPRODUZIONE VIDEO] 444 00:14:33,320 --> 00:14:33,820 >> -OK. 445 00:14:33,820 --> 00:14:36,680 Così il vostro compito qui, Sean, è il seguente. 446 00:14:36,680 --> 00:14:40,860 Ho nascosto dietro questi porte il numero sette. 447 00:14:40,860 --> 00:14:45,120 Ma nascosto in alcune di queste porte così sono altri numeri negativi. 448 00:14:45,120 --> 00:14:47,500 E il vostro obiettivo è quello di pensare di questa riga superiore di numeri 449 00:14:47,500 --> 00:14:50,390 come solo un array, o semplicemente sequenza di pezzi di carta 450 00:14:50,390 --> 00:14:51,510 con i numeri dietro di loro. 451 00:14:51,510 --> 00:14:55,540 E il vostro obiettivo è, utilizzando solo la parte superiore array di qui, mi troverete il numero sette. 452 00:14:55,540 --> 00:14:58,570 E stiamo andando poi a criticare come si fa a farlo. 453 00:14:58,570 --> 00:14:59,070 -Tutto ok. 454 00:14:59,070 --> 00:15:00,850 Noi -Trova il numero sette, per favore. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 No. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Cinque, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Ride] 461 00:15:24,770 --> 00:15:25,910 >> Non è una domanda trabocchetto. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Uno. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Ride] 466 00:15:34,695 --> 00:15:37,861 A questo punto, il punteggio non è molto bene, così si potrebbe anche andare avanti. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Tre. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Ride] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Andare avanti. 473 00:15:47,774 --> 00:15:50,690 Francamente, non posso fare a meno di chiedermi cosa stai ancora pensando, so-- 474 00:15:50,690 --> 00:15:51,959 >> [Ride] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Solo la fila superiore, così Hai tre sinistra. 477 00:15:55,020 --> 00:15:56,200 Così mi trovare sette. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Ride] 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 Sette. 484 00:16:26,946 --> 00:16:28,780 >> [Applausi] 485 00:16:28,780 --> 00:16:29,426 >> Tutto ok. 486 00:16:29,426 --> 00:16:30,360 >> [FINE RIPRODUZIONE] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. MALAN: Così abbiamo potuto Guardate queste per tutto il giorno. 488 00:16:31,840 --> 00:16:34,090 E, naturalmente, alcuni dei demo di quest'anno forse 489 00:16:34,090 --> 00:16:36,330 sarà ora finire in prossimo Video anno pure. 490 00:16:36,330 --> 00:16:39,040 Così ora cerchiamo di realtà concentrarsi sugli algoritmi 491 00:16:39,040 --> 00:16:42,140 qui, e vedere se non possiamo ora inizia formalizzare 492 00:16:42,140 --> 00:16:46,650 come possiamo fare per ottenere i nostri dati in questo stato che è ordinato, 493 00:16:46,650 --> 00:16:50,054 così che alla fine, possiamo in realtà cercare in modo più efficiente. 494 00:16:50,054 --> 00:16:52,470 E anche se stiamo andando utilizzare piuttosto piccoli insiemi di dati, 495 00:16:52,470 --> 00:16:54,511 come l'otto numeri che avere qui sul bordo, 496 00:16:54,511 --> 00:16:58,230 in ultima analisi, queste stesse idee potevano applicare a 1.000 ingressi, un milione di ingressi, 497 00:16:58,230 --> 00:17:02,100 4 miliardi ingressi, perché gli algoritmi stanno per essere fondamentalmente lo stesso. 498 00:17:02,100 --> 00:17:05,359 >> E così questo è il nostro ultimo opportunità per i volontari oggi, 499 00:17:05,359 --> 00:17:09,790 ma forse il più coinvolto, per il quale abbiamo bisogno di otto volontari 500 00:17:09,790 --> 00:17:12,960 a venire e noi a piedi attraverso la processo di smistamento quello che sarà presto 501 00:17:12,960 --> 00:17:15,212 essere su questi leggii qui. 502 00:17:15,212 --> 00:17:16,170 Permettetemi di iniziare di nuovo qui. 503 00:17:16,170 --> 00:17:19,692 >> Così uno nel verde turquoise-- è? 504 00:17:19,692 --> 00:17:21,130 Stai commettendo? 505 00:17:21,130 --> 00:17:21,630 Due. 506 00:17:21,630 --> 00:17:23,069 Vieni giù. 507 00:17:23,069 --> 00:17:23,569 OK. 508 00:17:23,569 --> 00:17:24,420 Tre. 509 00:17:24,420 --> 00:17:25,400 Quattro. 510 00:17:25,400 --> 00:17:27,247 Lasciate me-- OK, cinque. 511 00:17:27,247 --> 00:17:28,830 Sei stato nominato dal tuo amico. 512 00:17:28,830 --> 00:17:31,340 Sei, sette e otto. 513 00:17:31,340 --> 00:17:32,130 Vieni su. 514 00:17:32,130 --> 00:17:32,630 Tutto ok. 515 00:17:32,630 --> 00:17:33,190 Grazie mille. 516 00:17:33,190 --> 00:17:33,689 Vieni su. 517 00:17:33,689 --> 00:17:34,790 Vieni su. 518 00:17:34,790 --> 00:17:35,330 >> Tutto ok. 519 00:17:35,330 --> 00:17:38,890 Quindi quello che abbiamo qui-- e questo è tra i più difficili, 520 00:17:38,890 --> 00:17:42,390 dal momento che questo sarà necessario che si umorismo me per un po 'di tempo. 521 00:17:42,390 --> 00:17:43,442 Si deve essere il numero uno. 522 00:17:43,442 --> 00:17:44,150 Come ti chiami? 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 Davide. 526 00:17:46,092 --> 00:17:46,800 Come ti chiami? 527 00:17:46,800 --> 00:17:47,140 >> GIUSEPPE: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. MALAN: Giuseppe, sei il numero due. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, numero tre. 530 00:17:52,260 --> 00:17:53,722 Stefan, numero quattro. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 DAVID J. MALAN: Cynthia, numero cinque. 533 00:17:57,548 --> 00:17:58,452 [Incomprensibile] 534 00:17:58,452 --> 00:17:59,618 DAVID J. MALAN: [incomprensibile]. 535 00:17:59,618 --> 00:18:00,391 David, numero sei. 536 00:18:00,391 --> 00:18:00,890 MATT: Matt. 537 00:18:00,890 --> 00:18:02,160 DAVID J. MALAN: Matt numero sette. 538 00:18:02,160 --> 00:18:02,850 E? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. MALAN: Waverly, numero otto. 541 00:18:04,470 --> 00:18:04,970 Tutto ok. 542 00:18:04,970 --> 00:18:06,510 Se could-- whoops. 543 00:18:06,510 --> 00:18:08,820 Se tutto, come il tuo prima sfida, ci 544 00:18:08,820 --> 00:18:10,820 sono otto leggii qui di fronte al pubblico. 545 00:18:10,820 --> 00:18:14,200 Se si potesse mettere i numeri questi leggii in modo 546 00:18:14,200 --> 00:18:16,560 che siano allineati con il stessi numeri sul tabellone. 547 00:18:16,560 --> 00:18:19,560 Quindi fare voi stessi sembrano che mettere i numeri in questi musica 548 00:18:19,560 --> 00:18:21,960 sta qui. 549 00:18:21,960 --> 00:18:25,980 Ottimo finora. 550 00:18:25,980 --> 00:18:26,600 >> Eccellente. 551 00:18:26,600 --> 00:18:26,890 OK. 552 00:18:26,890 --> 00:18:29,556 Così ora, stiamo andando a chiedere il domanda in diversi modi. 553 00:18:29,556 --> 00:18:31,610 Come possiamo andare sull'ordinamento queste persone qui? 554 00:18:31,610 --> 00:18:34,500 Perché abbiamo avuto alcuni approcci in precedenza, per cui siamo stati 555 00:18:34,500 --> 00:18:36,360 tipo di fare due secchi diversi. 556 00:18:36,360 --> 00:18:38,842 E poi siamo stati in genere mettendo insieme le cose. 557 00:18:38,842 --> 00:18:41,050 Non appena abbiamo visto due numeri che apparteneva insieme, 558 00:18:41,050 --> 00:18:41,975 li abbiamo messi insieme. 559 00:18:41,975 --> 00:18:43,350 Due lettere che vanno insieme. 560 00:18:43,350 --> 00:18:45,058 >> Ma vediamo se siamo non può formalizzare questo, 561 00:18:45,058 --> 00:18:48,044 in modo da avere alla fine alcuni pseudo-codice si vuole, 562 00:18:48,044 --> 00:18:49,710 con cui è possibile risolvere questi problemi. 563 00:18:49,710 --> 00:18:51,870 Così ora, sto cercando fuori a questi numeri qui. 564 00:18:51,870 --> 00:18:55,030 E vedo un sacco di errori. 565 00:18:55,030 --> 00:18:57,750 In ultima analisi, voglio uno sulla sinistra e otto sulla destra. 566 00:18:57,750 --> 00:19:00,650 >> E così sto guardando questi due, quattro e due. 567 00:19:00,650 --> 00:19:02,930 E qual è il problema, ovviamente? 568 00:19:02,930 --> 00:19:04,261 Già. 569 00:19:04,261 --> 00:19:04,760 Così. 570 00:19:04,760 --> 00:19:07,160 Due viene ovviamente prima quattro, in modo da sapere che cosa? 571 00:19:07,160 --> 00:19:10,210 Permettetemi innanzitutto di prendere un approccio avido, se si vuole, molto problema come 572 00:19:10,210 --> 00:19:13,790 set tra-- se vi ricordate dal Standard Edition di Set problema Uno, 573 00:19:13,790 --> 00:19:16,820 dove ho appena risolvere localmente il problema che è proprio qui di fronte a me 574 00:19:16,820 --> 00:19:17,690 e vedere dove mi porta. 575 00:19:17,690 --> 00:19:17,870 >> OK. 576 00:19:17,870 --> 00:19:20,161 Così due e quattro, lasciami andare avanti e appena si scambiano due. 577 00:19:20,161 --> 00:19:22,400 Se si riesce a spostare fisicamente voi stessi e la vostra carta, 578 00:19:22,400 --> 00:19:25,040 Mi sembra di aver ottenuto la elencare in una condizione migliore. 579 00:19:25,040 --> 00:19:26,330 >> Ora, sono buone. 580 00:19:26,330 --> 00:19:28,480 Ho intenzione di andare avanti, quattro e sei, sembra buono. 581 00:19:28,480 --> 00:19:29,110 Non è un problema. 582 00:19:29,110 --> 00:19:30,440 Sei e otto, OK. 583 00:19:30,440 --> 00:19:31,860 Otto e uno, un altro problema. 584 00:19:31,860 --> 00:19:34,750 Perché ciò che è vero circa otto e uno? 585 00:19:34,750 --> 00:19:36,990 Uno viene prima delle otto, e così che cosa dobbiamo fare? 586 00:19:36,990 --> 00:19:38,090 Facciamo scambiano questi due. 587 00:19:38,090 --> 00:19:39,316 Uno e otto. 588 00:19:39,316 --> 00:19:40,690 E ora, ho intenzione di andare avanti. 589 00:19:40,690 --> 00:19:42,030 Ho intenzione di continuare a guardare avanti. 590 00:19:42,030 --> 00:19:42,840 E vediamo cosa succede. 591 00:19:42,840 --> 00:19:44,680 Otto e tre, di Certo, fuori uso. 592 00:19:44,680 --> 00:19:45,815 Facciamo swap. 593 00:19:45,815 --> 00:19:46,940 Otto e sette, naturalmente. 594 00:19:46,940 --> 00:19:47,481 Guasto. 595 00:19:47,481 --> 00:19:48,280 Facciamo swap. 596 00:19:48,280 --> 00:19:49,940 Otto e cinque, naturalmente, cerchiamo di swap. 597 00:19:49,940 --> 00:19:50,560 Tutto ok. 598 00:19:50,560 --> 00:19:51,880 Lista è ordinata. 599 00:19:51,880 --> 00:19:53,060 sì? 600 00:19:53,060 --> 00:19:54,280 >> OK, ovviamente non. 601 00:19:54,280 --> 00:19:55,860 Ma è un po 'meglio, giusto? 602 00:19:55,860 --> 00:19:57,270 Perché avviso quello che è successo. 603 00:19:57,270 --> 00:20:01,749 Ogni volta che abbiamo effettuato uno swap, una più piccola Numero tipo di percolato in questo modo, 604 00:20:01,749 --> 00:20:03,790 e un numero più grande percolato in questo modo, o faremo 605 00:20:03,790 --> 00:20:06,880 iniziare dicendo bolle al sinistra o verso destra gorgogliare. 606 00:20:06,880 --> 00:20:10,080 >> Ora, non è sufficiente, perché nel migliore dei casi un numero potrebbe 607 00:20:10,080 --> 00:20:11,990 si sono spostati uno spot in avanti, o nel peggiore dei casi, 608 00:20:11,990 --> 00:20:13,880 un numero potrebbe avere spostato più un punto. 609 00:20:13,880 --> 00:20:16,369 Così si sa che cosa, questo tipo di funzionato abbastanza bene finora. 610 00:20:16,369 --> 00:20:17,410 Vorrei solo provare di nuovo. 611 00:20:17,410 --> 00:20:18,880 Due e quattro, sono OK. 612 00:20:18,880 --> 00:20:20,180 Quattro e sei, sono OK. 613 00:20:20,180 --> 00:20:21,790 Sei e uno, fuori uso. 614 00:20:21,790 --> 00:20:23,007 Quindi cerchiamo di voi due swap. 615 00:20:23,007 --> 00:20:25,840 E ora, il problema del preavviso cominciando a diventare un po 'di nuovo meglio. 616 00:20:25,840 --> 00:20:27,006 Sei e tre, fuori uso. 617 00:20:27,006 --> 00:20:28,100 Diamo voi due swap. 618 00:20:28,100 --> 00:20:29,730 Sei e sette, sei buono. 619 00:20:29,730 --> 00:20:32,230 Sette e cinque, naturalmente, fuori ordine. 620 00:20:32,230 --> 00:20:33,920 Sette e otto, in ordine. 621 00:20:33,920 --> 00:20:36,470 E ora, potrei aver bisogno di fare questo un paio di volte. 622 00:20:36,470 --> 00:20:39,830 E infatti, pensare per voi stessi forse quante volte al massimo 623 00:20:39,830 --> 00:20:41,330 potrei camminare avanti e indietro? 624 00:20:41,330 --> 00:20:42,390 >> Torneremo a questo. 625 00:20:42,390 --> 00:20:43,700 Così due e quattro sono ancora OK. 626 00:20:43,700 --> 00:20:44,940 Quattro e uno, no. 627 00:20:44,940 --> 00:20:45,747 Quindi, andiamo swap. 628 00:20:45,747 --> 00:20:47,830 E ancora, notare visivamente uno è una specie di ribollimento 629 00:20:47,830 --> 00:20:49,163 a sinistra, dove dovrebbe essere. 630 00:20:49,163 --> 00:20:50,010 Quattro e tre swap. 631 00:20:50,010 --> 00:20:51,330 Quattro e sei. 632 00:20:51,330 --> 00:20:53,100 Sei e cinque swap. 633 00:20:53,100 --> 00:20:53,959 Sei e sette. 634 00:20:53,959 --> 00:20:55,000 Sette e otto sono buoni. 635 00:20:55,000 --> 00:20:55,500 >> Bene. 636 00:20:55,500 --> 00:20:58,460 Stiamo ottenendo ancora meglio. 637 00:20:58,460 --> 00:20:59,130 Quindi cerchiamo di vedere. 638 00:20:59,130 --> 00:21:00,940 Ora, abbiamo due e uno. 639 00:21:00,940 --> 00:21:02,520 Naturalmente, scambiare. 640 00:21:02,520 --> 00:21:07,520 Due e tre, tre e quattro, quattro e cinque, sei e sette, sette e otto. 641 00:21:07,520 --> 00:21:08,020 Bene. 642 00:21:08,020 --> 00:21:08,730 E sai una cosa? 643 00:21:08,730 --> 00:21:11,190 Perché ho fatto un cambio lì, mi permetta di fare un controllo di integrità. 644 00:21:11,190 --> 00:21:13,023 Lasciami andare fino in fondo torna all'inizio. 645 00:21:13,023 --> 00:21:13,680 OK. 646 00:21:13,680 --> 00:21:14,750 Uno, two-- yup, vedi? 647 00:21:14,750 --> 00:21:15,870 Qualcosa non andava. 648 00:21:15,870 --> 00:21:18,420 Tre, quattro, cinque, sei, sette, otto. 649 00:21:18,420 --> 00:21:21,920 E in questo ultimo passo, sono a vostro agio con la mia ora 650 00:21:21,920 --> 00:21:23,830 sostenendo che è ordinato? 651 00:21:23,830 --> 00:21:24,330 OK. 652 00:21:24,330 --> 00:21:25,880 Visivamente, questo è assolutamente vero. 653 00:21:25,880 --> 00:21:28,410 Ma funzionalmente, cosa ha anche appena capita 654 00:21:28,410 --> 00:21:31,870 in tale ultimo passo che permette per confermare che questa lista è davvero 655 00:21:31,870 --> 00:21:32,660 ordinati? 656 00:21:32,660 --> 00:21:34,477 >> Che cosa ho fatto o non fare questo ultimo passo? 657 00:21:34,477 --> 00:21:35,810 PUBBLICO: ci sono stati cambiamenti. 658 00:21:35,810 --> 00:21:36,120 DAVID J. MALAN: Siamo spiacenti? 659 00:21:36,120 --> 00:21:37,070 PUBBLICO: Nessuna modifica. 660 00:21:37,070 --> 00:21:38,653 DAVID J. MALAN: Non ci sono stati cambiamenti. 661 00:21:38,653 --> 00:21:41,947 Quindi sarebbe stupido da parte mia fare di nuovo quello stesso algoritmo 662 00:21:41,947 --> 00:21:43,780 se non ho fatto alcun cambia la prima volta. 663 00:21:43,780 --> 00:21:45,160 E lo Stato non è cambiata. 664 00:21:45,160 --> 00:21:47,576 Certo, io non ho intenzione di fare Eventuali modifiche per la seconda volta. 665 00:21:47,576 --> 00:21:49,820 E così, è sicuro ora per dire, elenco è ordinato. 666 00:21:49,820 --> 00:21:52,069 >> E in effetti, questo è ora qualcosa che faremo in generale 667 00:21:52,069 --> 00:21:56,900 chiamata bubble sort, per cui due a due, correggete ancora errori, 668 00:21:56,900 --> 00:22:00,210 e ancora, e ancora, e si andare avanti e indietro, 669 00:22:00,210 --> 00:22:03,370 e avanti e indietro, fino a che non rendere tali swap, a quel punto 670 00:22:03,370 --> 00:22:07,089 si può essere sicuri, sì, mi finito fissare tutti gli errori. 671 00:22:07,089 --> 00:22:08,630 Cerchiamo di reimpostare e cercare un altro approccio. 672 00:22:08,630 --> 00:22:11,590 Se voi ragazzi poteste tornare in l'ordine che fosse un momento fa, 673 00:22:11,590 --> 00:22:13,780 che si presentava così. 674 00:22:13,780 --> 00:22:17,640 Ora, prendiamo un approccio un po 'di più come il libro esame, 675 00:22:17,640 --> 00:22:21,122 per cui siamo stati costantemente selezionando la lettera dell'alfabeto 676 00:22:21,122 --> 00:22:22,830 che tipo di volevamo a che fare con il prossimo. 677 00:22:22,830 --> 00:22:26,420 Forse era un alto lettera, come A, o un basso lettera Z. 678 00:22:26,420 --> 00:22:28,170 >> Così tutti sono nuovo in questo ordine. 679 00:22:28,170 --> 00:22:29,800 E ora mi permetta di fare questo. 680 00:22:29,800 --> 00:22:34,880 Vediamo so di avere otto numeri qui. 681 00:22:34,880 --> 00:22:37,410 Ho intenzione di andare avanti e appena deliberatamente selezionare 682 00:22:37,410 --> 00:22:38,520 gli elementi più piccoli. 683 00:22:38,520 --> 00:22:38,760 Destra? 684 00:22:38,760 --> 00:22:39,801 Questo sembra troppo intuitiva. 685 00:22:39,801 --> 00:22:42,560 Perché non trovo il più piccolo elemento, messo a cui appartiene, 686 00:22:42,560 --> 00:22:45,280 quindi ottenere il successivo elemento più piccolo, mettere a cui appartiene, e sufficiente ripetere. 687 00:22:45,280 --> 00:22:46,820 >> Perché intuitivamente, che dovrebbe funzionare anche. 688 00:22:46,820 --> 00:22:48,441 Così quattro, che è un numero piuttosto piccolo. 689 00:22:48,441 --> 00:22:49,940 Io vado a ricordare dove questo è. 690 00:22:49,940 --> 00:22:50,523 Apetta un minuto. 691 00:22:50,523 --> 00:22:51,577 Due è più piccolo. 692 00:22:51,577 --> 00:22:53,910 Permettetemi ora di ricordare dove due è, e dimenticare quattro. 693 00:22:53,910 --> 00:22:55,050 Ce ne occuperemo più avanti. 694 00:22:55,050 --> 00:22:56,460 Sei, non mi interessa. 695 00:22:56,460 --> 00:22:57,810 Otto, io non sono interessato a. 696 00:22:57,810 --> 00:22:59,780 Uno è il mio nuovo numero di piccole dimensioni. 697 00:22:59,780 --> 00:23:01,470 Quindi ho intenzione di ricordare dove si è. 698 00:23:01,470 --> 00:23:02,534 Tre, non è interessato. 699 00:23:02,534 --> 00:23:03,450 Sette, non è interessato. 700 00:23:03,450 --> 00:23:04,530 Cinque, non è interessato. 701 00:23:04,530 --> 00:23:07,390 >> Così, senza cadere il palco quest'anno, 702 00:23:07,390 --> 00:23:09,890 Vado a prendere il numero tra-- e ciò che è stato di nuovo il tuo nome? 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 E se tu potessi venire con me a l'inizio della lista, 706 00:23:13,540 --> 00:23:14,870 mettiamo dove si appartiene. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- come ti chiami? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. MALAN: Stefan è in mezzo. 710 00:23:18,191 --> 00:23:23,490 Quindi, prima di Stefan risolve questo problema, che cosa dobbiamo fare? 711 00:23:23,490 --> 00:23:25,412 Che cosa facciamo con Stefan? 712 00:23:25,412 --> 00:23:27,269 >> PUBBLICO: [incomprensibile]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. MALAN: OK. 714 00:23:28,060 --> 00:23:28,850 Così potremmo farlo. 715 00:23:28,850 --> 00:23:31,730 Potremmo sorta di prendere Stefan e la sua quattro, e appena messo in una variabile 716 00:23:31,730 --> 00:23:33,530 e tenere su di esso per una certa quantità di tempo, 717 00:23:33,530 --> 00:23:35,220 rendendo così spazio per il numero uno. 718 00:23:35,220 --> 00:23:36,280 E questo non è male. 719 00:23:36,280 --> 00:23:39,270 Potrei suggerire, perché non fare abbiamo appena messo Stefan qui? 720 00:23:39,270 --> 00:23:41,610 Perché questo potrebbe violare uno delle idee che abbiamo iniziato 721 00:23:41,610 --> 00:23:44,830 parlando l'ultima volta, la settimana scorsa? 722 00:23:44,830 --> 00:23:45,330 Sì? 723 00:23:45,330 --> 00:23:45,740 >> PUBBLICO: [incomprensibile]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. MALAN: Non c'è nessun indice per esso. 725 00:23:46,860 --> 00:23:49,735 Se pensate a questo, infatti, come un serie, questo è come uno negativo, 726 00:23:49,735 --> 00:23:52,900 quindi non c'è memoria realtà qui se questo è davvero un array, 727 00:23:52,900 --> 00:23:55,090 come abbiamo dichiarato la scorsa settimana a lezione. 728 00:23:55,090 --> 00:23:56,250 Quindi non dobbiamo farlo. 729 00:23:56,250 --> 00:23:57,340 Possiamo memorizzare in una variabile. 730 00:23:57,340 --> 00:23:57,820 >> O sai una cosa? 731 00:23:57,820 --> 00:23:59,153 Ho sentito qualcuno altro suggerire. 732 00:23:59,153 --> 00:24:01,020 Che altro potremmo fare con Stefan? 733 00:24:01,020 --> 00:24:03,770 Perché noi non solo lo sfrattare e lo ha messo su dove il numero uno era. 734 00:24:03,770 --> 00:24:05,170 Quindi, se volete andare là. 735 00:24:05,170 --> 00:24:07,300 E infatti, questo è un soluzione piuttosto buona. 736 00:24:07,300 --> 00:24:10,480 Ora, da un lato, ho genere di fatto il problema peggiore. 737 00:24:10,480 --> 00:24:13,650 Quattro è ora più lontana da dove dovrebbe essere. 738 00:24:13,650 --> 00:24:14,900 Dovrebbe essere verso questo mezzo. 739 00:24:14,900 --> 00:24:16,100 >> Ma sai cosa? 740 00:24:16,100 --> 00:24:17,630 Che avrebbe potuto essere la sfortuna. 741 00:24:17,630 --> 00:24:18,822 Forse numero otto era qui. 742 00:24:18,822 --> 00:24:20,530 E così, forse avremmo hanno ottenuto fortunato, 743 00:24:20,530 --> 00:24:22,460 e spinto otto più vicini alla fine. 744 00:24:22,460 --> 00:24:24,710 Così, alla fine della giornata, E 'sorta di tutte le medie fuori. 745 00:24:24,710 --> 00:24:26,085 Non abbiamo bisogno di preoccuparsi quattro. 746 00:24:26,085 --> 00:24:29,400 Tutto quello che interessa ora è selezionando l'elemento più piccolo. 747 00:24:29,400 --> 00:24:32,030 >> E ora, che cosa ho intenzione di fare è dimenticare il numero uno 748 00:24:32,030 --> 00:24:35,160 in modo permanente, perché so che il lista dietro di me è ora ordinato. 749 00:24:35,160 --> 00:24:36,720 Così la mia lista era già formato a otto. 750 00:24:36,720 --> 00:24:37,720 Ora, è di dimensioni sette. 751 00:24:37,720 --> 00:24:40,340 Quindi il mio problema è sempre più piccolo, seppur linearmente. 752 00:24:40,340 --> 00:24:43,022 Così ora, ho intenzione di selezionare il corrente elemento più piccolo, due. 753 00:24:43,022 --> 00:24:46,520 Sei, otto, quattro, tre, sette, cinque. 754 00:24:46,520 --> 00:24:47,770 Questo è stato l'elemento più piccolo. 755 00:24:47,770 --> 00:24:49,416 Così che cosa sono io intenzione di fare with-- quello che era di nuovo il tuo nome? 756 00:24:49,416 --> 00:24:49,760 >> GIUSEPPE: Joseph. 757 00:24:49,760 --> 00:24:50,085 >> DAVID J. MALAN: Giuseppe? 758 00:24:50,085 --> 00:24:52,000 Stiamo per lasciare Giuseppe a posto. 759 00:24:52,000 --> 00:24:54,842 Ora, ho intenzione di far finta che questi ragazzi are-- bene, 760 00:24:54,842 --> 00:24:56,550 So che questi due sono già ordinati. 761 00:24:56,550 --> 00:24:58,424 Passiamo ora concentriamoci sul resto della lista. 762 00:24:58,424 --> 00:25:00,080 Sei è la corrente più piccolo. 763 00:25:00,080 --> 00:25:01,190 Otto è più grande. 764 00:25:01,190 --> 00:25:02,970 Quattro è ora il più piccolo corrente. 765 00:25:02,970 --> 00:25:04,762 Tre è ora il più piccolo corrente. 766 00:25:04,762 --> 00:25:07,720 E così ora, ho intenzione di selezionare tre, che è-- cosa di nuovo il tuo nome? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. MALAN: Serena, se potessi afferrare il vostro numero e di swap with-- 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 Vieni indietro, e siamo andare per scambiare quei due. 772 00:25:15,220 --> 00:25:17,360 E ora, mettiamo questo il pilota automatico. 773 00:25:17,360 --> 00:25:21,589 Ho intenzione di andare e lasciare a voi ragazzi per selezionare i prossimi elementi più piccoli. 774 00:25:21,589 --> 00:25:22,380 Dun, dun, dun, dun. 775 00:25:22,380 --> 00:25:24,560 Numero quattro, cosa si deve fare? 776 00:25:24,560 --> 00:25:26,261 Eccellente. 777 00:25:26,261 --> 00:25:27,760 Ora, ho intenzione di fare un altro passo. 778 00:25:27,760 --> 00:25:28,590 Dun, dun, dun, dun. 779 00:25:28,590 --> 00:25:31,465 Vedo cinque è il immediatamente inferiore. 780 00:25:31,465 --> 00:25:32,840 Ora, sto andando fare un altro passaggio. 781 00:25:32,840 --> 00:25:33,631 Dun, dun, dun, dun. 782 00:25:33,631 --> 00:25:34,880 Sei è il più piccolo. 783 00:25:34,880 --> 00:25:35,520 Bene. 784 00:25:35,520 --> 00:25:36,585 Sette è il più piccolo. 785 00:25:36,585 --> 00:25:37,085 Nessun cambiamento. 786 00:25:37,085 --> 00:25:38,630 Otto è il più piccolo. 787 00:25:38,630 --> 00:25:39,170 Fatto. 788 00:25:39,170 --> 00:25:43,900 >> Quindi quello che abbiamo appena fatto da iterativamente selezionando un elemento dopo l'altro 789 00:25:43,900 --> 00:25:47,230 è implementare qualcosa che siamo andare a formalizzare la selezione sorta. 790 00:25:47,230 --> 00:25:49,120 Ed è forse anche semplice da spiegare, 791 00:25:49,120 --> 00:25:51,310 in che letteralmente tutto quello che voglia di fare è mantenere 792 00:25:51,310 --> 00:25:54,700 andando avanti e indietro attraverso la lista la selezione, il prossimo elemento più piccolo, 793 00:25:54,700 --> 00:25:55,720 fino a quando il gioco è fatto. 794 00:25:55,720 --> 00:25:58,650 >> Quindi è ancora più semplice, forse intuitivamente, rispetto allo scorso. 795 00:25:58,650 --> 00:26:00,020 Proviamo un ultimo uno. 796 00:26:00,020 --> 00:26:03,060 Se voi ragazzi poteste ripristinare voi nelle seguenti posizioni 797 00:26:03,060 --> 00:26:08,600 un'ultima volta, vediamo se non possiamo ora formalizzare un altro approccio. 798 00:26:08,600 --> 00:26:12,857 In realtà, sarebbe qualcuno là fuori piace proporre 799 00:26:12,857 --> 00:26:14,440 in quale altro modo si potrebbe andare a fare questo? 800 00:26:14,440 --> 00:26:17,439 Senza tirare fuori parole d'ordine o tipo di risposte che sono già noti, 801 00:26:17,439 --> 00:26:19,689 solo intuitivamente, cosa potevamo fare? 802 00:26:19,689 --> 00:26:21,635 >> PUBBLICO: [incomprensibile]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. MALAN: Sì. 804 00:26:22,510 --> 00:26:24,620 Quindi c'è qualche grande intuizione lì. 805 00:26:24,620 --> 00:26:28,020 Buone cose sembrano accadere finora in informatica quando ci dividiamo 806 00:26:28,020 --> 00:26:30,832 e conquistare il problema della divisione a metà e metà e metà. 807 00:26:30,832 --> 00:26:32,540 E così in effetti, abbiamo potrebbe iniziare a farlo. 808 00:26:32,540 --> 00:26:35,754 E infatti, che sta per essere, noi provvederemo vedere, uno dei nostri migliori soluzioni ancora. 809 00:26:35,754 --> 00:26:37,420 Ma torniamo a quel poco tempo. 810 00:26:37,420 --> 00:26:40,500 In realtà, stiamo andando a fare che un po 'più tardi questa settimana. 811 00:26:40,500 --> 00:26:42,180 Che altro potremmo fare per risolvere questo problema? 812 00:26:42,180 --> 00:26:44,647 Quindi, tutti qui sono in ordine apparentemente casuale. 813 00:26:44,647 --> 00:26:45,230 Sai cosa? 814 00:26:45,230 --> 00:26:48,320 Invece di andare avanti e indietro, avanti e indietro, avanti e indietro 815 00:26:48,320 --> 00:26:50,624 ogni volta, questo si sente come Sto facendo un sacco di camminare. 816 00:26:50,624 --> 00:26:52,790 Perché non appena comincio a l'inizio della lista, 817 00:26:52,790 --> 00:26:54,960 e appena messo quattro a cui appartiene? 818 00:26:54,960 --> 00:26:59,680 Permettetemi quindi di presumo per il momento che la mia lista è solo questo primo elemento. 819 00:26:59,680 --> 00:27:04,937 È quattro ordinati in questo momento nel tempo, se tutto mi interessa è tutto qui? 820 00:27:04,937 --> 00:27:06,520 Questa è una sorta di banalmente vero, giusto? 821 00:27:06,520 --> 00:27:10,000 Come l'elenco contenente un numero, e che il numero quattro è ovviamente ordinato. 822 00:27:10,000 --> 00:27:13,070 >> Quindi lasciatemi stipula le che questo elenco è ordinato. 823 00:27:13,070 --> 00:27:15,090 Ma ora ho il resto di questa lista. 824 00:27:15,090 --> 00:27:17,240 Così ora, ho incontrato due. 825 00:27:17,240 --> 00:27:21,690 Da dove viene, ovviamente, due appartenere rispetto a quattro? 826 00:27:21,690 --> 00:27:22,580 Prima di quattro. 827 00:27:22,580 --> 00:27:23,862 Cosa posso fare qui? 828 00:27:23,862 --> 00:27:24,820 Mi ricordi come ti chiami? 829 00:27:24,820 --> 00:27:25,090 >> GIUSEPPE: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. MALAN: Giuseppe, se si potesse fare un passo indietro 831 00:27:26,030 --> 00:27:27,790 per un attimo con il vostro numero. 832 00:27:27,790 --> 00:27:31,130 E ora che cosa dovrebbe Stefan fare qui? 833 00:27:31,130 --> 00:27:33,720 Spostiamo Stefan qui. 834 00:27:33,720 --> 00:27:35,520 E ora, lascia Giuseppe venire qui. 835 00:27:35,520 --> 00:27:39,660 E ora, mi permetta di sostengo che tutto qui è ordinato. 836 00:27:39,660 --> 00:27:42,474 Quindi, risultato simile, ma una fondamentalmente diverso approccio. 837 00:27:42,474 --> 00:27:44,140 Non ho nemmeno guardato cosa c'è là sotto. 838 00:27:44,140 --> 00:27:46,310 Continuo a prendere gli elementi come sono consegnati a me, 839 00:27:46,310 --> 00:27:47,240 e trattare con loro. 840 00:27:47,240 --> 00:27:48,330 >> Così ora, vedo numero sei. 841 00:27:48,330 --> 00:27:51,110 Da dove viene il numero sei appartiene? 842 00:27:51,110 --> 00:27:53,250 Abbiamo due, quattro, sei. 843 00:27:53,250 --> 00:27:54,800 Esattamente dove si trova in questo momento. 844 00:27:54,800 --> 00:27:57,750 Quindi lasciamo che da sola, e ora affermare che questa parte della lista 845 00:27:57,750 --> 00:27:58,772 è ora ordinato. 846 00:27:58,772 --> 00:28:01,230 E così, questo si sente fondamentalmente diversa, in quanto io sono solo 847 00:28:01,230 --> 00:28:05,230 si muove attraverso la lista qui lineare, e sto mai raddoppio indietro. 848 00:28:05,230 --> 00:28:05,730 Sì. 849 00:28:05,730 --> 00:28:06,230 Tutto ok. 850 00:28:06,230 --> 00:28:08,190 Così otto, dove appartieni? 851 00:28:08,190 --> 00:28:08,730 Giusto qui. 852 00:28:08,730 --> 00:28:09,310 Perfetto. 853 00:28:09,310 --> 00:28:10,210 Così ora, uno. 854 00:28:10,210 --> 00:28:10,900 Uh Oh. 855 00:28:10,900 --> 00:28:13,010 Questo si sente come se fosse sta per essere costoso. 856 00:28:13,010 --> 00:28:15,690 Ora, nell'algoritmo precedente, Ho appena scambiato persone. 857 00:28:15,690 --> 00:28:18,648 Quindi perché lo mettere tutta la strada a all'inizio, ma poi si trasferisce Giuseppe. 858 00:28:18,648 --> 00:28:21,450 Ma se mi muovo Joseph, ora ciò che sta per essere sbagliato? 859 00:28:21,450 --> 00:28:24,250 >> Ora, ho una sorta di undone-- ho fatto un passo in avanti e poi 860 00:28:24,250 --> 00:28:26,300 un passo indietro, perché ora Joseph sarebbe fuori ordine. 861 00:28:26,300 --> 00:28:26,830 Quindi cerchiamo di fare questo. 862 00:28:26,830 --> 00:28:29,150 Se potessi prendere il numero uno e un passo indietro per un attimo. 863 00:28:29,150 --> 00:28:30,490 Come possiamo put-- cosa Era di nuovo il tuo nome? 864 00:28:30,490 --> 00:28:31,130 >> ANNAN: Annan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. MALAN: Annan a posto? 866 00:28:32,610 --> 00:28:36,091 Che cosa deve accadere per quanto riguarda a due, quattro, sei, otto e? 867 00:28:36,091 --> 00:28:37,570 Tutti hanno bisogno di cambiare. 868 00:28:37,570 --> 00:28:42,590 Quindi, se otto vorrebbe spostare prima, poi sei, poi quattro, poi due. 869 00:28:42,590 --> 00:28:45,380 E poi Annan, se aveste piacerebbe venire qui, bene. 870 00:28:45,380 --> 00:28:47,760 Ma qui, abbiamo appena tipo di pagato un prezzo 871 00:28:47,760 --> 00:28:49,510 in un punto diverso nell'algoritmo. 872 00:28:49,510 --> 00:28:52,550 Mentre l'ultima volta con la selezione tipo, e anche bubble sort, 873 00:28:52,550 --> 00:28:54,700 Sto camminando avanti e indietro, avanti e indietro, 874 00:28:54,700 --> 00:28:58,360 che è certamente sommando tempo-saggio, e letteralmente graduale. 875 00:28:58,360 --> 00:29:00,660 >> Insertion sort, in un primo momento sguardo, sembra che sia 876 00:29:00,660 --> 00:29:05,150 super-intelligente, nel senso che io sono solo facendo lento, progressi incrementali, 877 00:29:05,150 --> 00:29:07,120 ma io non ho intenzione questo avanti e indietro. 878 00:29:07,120 --> 00:29:09,410 Ma se qualcuno è davvero fuori ordine, avviso 879 00:29:09,410 --> 00:29:10,840 tutto il lavoro che ho appena avuto a che fare. 880 00:29:10,840 --> 00:29:14,750 Ho dovuto spostare metà della lista solo per fare spazio a numero uno. 881 00:29:14,750 --> 00:29:16,790 Quindi è la stessa quantità del lavoro finora essa 882 00:29:16,790 --> 00:29:18,690 sente, solo un diverso tipo di lavoro. 883 00:29:18,690 --> 00:29:19,370 >> Continuiamo. 884 00:29:19,370 --> 00:29:22,657 Così ora sappiamo che tutti tra uno e otto sono allineati. 885 00:29:22,657 --> 00:29:23,740 Qui, ho numero tre. 886 00:29:23,740 --> 00:29:25,864 Se vi piace prendere numero tre, un passo indietro uno. 887 00:29:25,864 --> 00:29:28,260 E che voi ragazzi dovete fare? 888 00:29:28,260 --> 00:29:28,760 Yep. 889 00:29:28,760 --> 00:29:33,070 Ecco, questo è un altro, due, tre passi. 890 00:29:33,070 --> 00:29:36,010 Tre unità di tempo che proprio costano me, in modo che tre ora posso andare bene. 891 00:29:36,010 --> 00:29:37,460 Infine, sette. 892 00:29:37,460 --> 00:29:39,730 >> Andiamo avanti e avere si prende un passo indietro. 893 00:29:39,730 --> 00:29:42,780 Questo è solo andare a costarci una unità di tempo, ma questo è OK. 894 00:29:42,780 --> 00:29:44,170 E ora, cinque di andare a essere un po 'più costoso. 895 00:29:44,170 --> 00:29:45,340 Se vuoi fare un passo indietro. 896 00:29:45,340 --> 00:29:48,380 Dobbiamo muoverci otto, e sette, e sei. 897 00:29:48,380 --> 00:29:50,749 E poi ognuno è ora ordinato. 898 00:29:50,749 --> 00:29:52,290 Quindi una grande mano per i nostri volontari qui. 899 00:29:52,290 --> 00:29:53,554 Grazie mille. 900 00:29:53,554 --> 00:29:56,220 >> [Applausi] 901 00:29:56,220 --> 00:29:56,860 >> Grazie a tutti. 902 00:29:56,860 --> 00:29:57,520 Grazie a tutti. 903 00:29:57,520 --> 00:30:02,940 Vediamo quindi ora solo come costosa tutto questo è stato. 904 00:30:02,940 --> 00:30:06,210 Consideriamo forse il più semplice di questi, bolla sorta. 905 00:30:06,210 --> 00:30:09,950 E io dico semplice, solo perché si può risolvere semplicemente avidamente 906 00:30:09,950 --> 00:30:11,660 risolvere il problema a coppie qui. 907 00:30:11,660 --> 00:30:13,720 Risolvere il problema a coppie qui, ancora e ancora 908 00:30:13,720 --> 00:30:17,680 e ancora, ripetendo come molti volte è effettivamente necessario. 909 00:30:17,680 --> 00:30:21,050 >> Così si scopre che con una bolla di sorta, beh, 910 00:30:21,050 --> 00:30:25,820 quanti passi devo prendere su il primo passaggio di tale algoritmo? 911 00:30:25,820 --> 00:30:30,850 Potrei take-- andiamo see-- uno, due, tre, quattro, cinque, sei, sette. 912 00:30:30,850 --> 00:30:32,190 E c'è otto elementi qui. 913 00:30:32,190 --> 00:30:35,280 Quindi è come se n meno 1 passi ottenere dall'inizio della lista 914 00:30:35,280 --> 00:30:36,380 alla fine della lista. 915 00:30:36,380 --> 00:30:41,350 >> Ma con selezione tipo, ricordo che io sono selezionando ripetutamente gli elementi 916 00:30:41,350 --> 00:30:44,590 e ancora una volta che è più piccolo, Sto mettendo a posto, 917 00:30:44,590 --> 00:30:46,616 ma poi io non sono guardando dietro di me di nuovo. 918 00:30:46,616 --> 00:30:49,490 Quindi penso che sia un po 'più chiaro allora che la prima volta, potrei 919 00:30:49,490 --> 00:30:52,680 prendere ogni n meno 1 passi per trovare l'elemento più piccolo. 920 00:30:52,680 --> 00:30:55,920 Poi li ho messi a posto, e io sfrattare chiunque fosse qui in passato. 921 00:30:55,920 --> 00:30:57,500 >> Ma allora non c'è bisogno di continuare a guardare a questo elemento, 922 00:30:57,500 --> 00:30:59,040 perché so che è già il più piccolo. 923 00:30:59,040 --> 00:31:01,581 Così ora, posso guardare solo sette elementi, poi sei elementi, 924 00:31:01,581 --> 00:31:03,290 poi cinque elementi, poi quattro elementi. 925 00:31:03,290 --> 00:31:06,900 E così matematicamente, se n è il numero di elementi o numeri 926 00:31:06,900 --> 00:31:11,990 che abbiamo iniziato con, che potete immaginare che questo è lo stesso come n meno 1, 927 00:31:11,990 --> 00:31:14,250 più n meno 2 punti, più n meno 3 punti, 928 00:31:14,250 --> 00:31:16,780 inclusa n meno 4 passaggi, tutte le fino in fondo a un solo passo. 929 00:31:16,780 --> 00:31:18,160 E sono il mio ultimo persona. 930 00:31:18,160 --> 00:31:20,650 >> E se vi ricordate che un sacco di stats libri o libri di matematica 931 00:31:20,650 --> 00:31:24,730 avere quelle formule sul cartonato schiena o di fronte a loro, 932 00:31:24,730 --> 00:31:27,690 si scopre che questa serie può essere espresso più semplicemente 933 00:31:27,690 --> 00:31:28,857 come n volte n meno 1 su 2. 934 00:31:28,857 --> 00:31:31,273 E va bene se questo non è in prima linea nella tua mente. 935 00:31:31,273 --> 00:31:32,420 Ma questo è vero. 936 00:31:32,420 --> 00:31:34,449 Questo è solo un modo più semplice di scriverlo. 937 00:31:34,449 --> 00:31:36,240 E poi se si pensa torna a scuola elementare, 938 00:31:36,240 --> 00:31:38,698 quando si può lanciare moltiplicando cose fuori, questo naturalmente, 939 00:31:38,698 --> 00:31:41,820 è solo n squadrato minus n diviso 2. 940 00:31:41,820 --> 00:31:44,772 Tutto quello che ho fatto è espandere le espressioni lì. 941 00:31:44,772 --> 00:31:46,730 E quindi cerchiamo di riscrivere questo un po 'diverso. 942 00:31:46,730 --> 00:31:49,780 Questo è n al quadrato diviso per 2 meno n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Quindi, di nuovo, io sono solo tipo di applicazione alcuni aritmetica governa lì. 944 00:31:53,270 --> 00:31:57,140 Ma si noti che ora il più grande termine in questa espressione, per così dire, 945 00:31:57,140 --> 00:31:58,540 è che n quadrato. 946 00:31:58,540 --> 00:32:02,910 Quindi sì, è n squared diviso 2, minus n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Ma in generale, se n è sarà un grande valore, 948 00:32:05,080 --> 00:32:08,740 Ho intenzione di affermare che n quadrato sta per essere il fattore dominante. 949 00:32:08,740 --> 00:32:10,490 E 'solo andando essere un collaboratore più grande 950 00:32:10,490 --> 00:32:12,877 il numero di passi di n / 2. 951 00:32:12,877 --> 00:32:13,960 Così che cosa voglio dire con questo? 952 00:32:13,960 --> 00:32:16,795 Proviamo un semplice esempio, anche anche se la matematica diventa un po 'grande. 953 00:32:16,795 --> 00:32:20,210 >> Quindi supponiamo abbiamo avuto 1 milione di persone sul palco, o 1 milione di cose 954 00:32:20,210 --> 00:32:21,320 che vogliamo risolvere. 955 00:32:21,320 --> 00:32:23,730 Facciamo collegare un milione in esattamente quella formula 956 00:32:23,730 --> 00:32:27,230 per vedere quanti passi ci vuole totale per ordinare un milione di elementi utilizzando per esempio, 957 00:32:27,230 --> 00:32:28,560 selection sort. 958 00:32:28,560 --> 00:32:30,760 >> Così avremmo la stessa formula di prima. 959 00:32:30,760 --> 00:32:34,120 Mi piacerebbe inserisco un milione, in modo che ricevo un milione al quadrato diviso per 2, 960 00:32:34,120 --> 00:32:35,990 meno un milione diviso 2. 961 00:32:35,990 --> 00:32:40,180 Se lo faccio matematica in anticipo qui, abbiamo 500 miliardi 962 00:32:40,180 --> 00:32:47,460 meno 500.000, che ci dà 499.999.500.000, 963 00:32:47,460 --> 00:32:49,270 che è maledettamente grande. 964 00:32:49,270 --> 00:32:54,370 >> Infatti, se si confrontano ora 499 miliardi, 999 milioni, 965 00:32:54,370 --> 00:33:01,210 500.000 contro il nostro valore originale, 500 miliardi, è così dannatamente vicino. 966 00:33:01,210 --> 00:33:06,850 Destra? n squadrato diviso per 2 dà noi-- o meglio, n squared diviso 2 967 00:33:06,850 --> 00:33:08,370 ci ha dato 500 miliardi. 968 00:33:08,370 --> 00:33:13,510 Che è maledettamente vicino a 499.999.500.000, 969 00:33:13,510 --> 00:33:17,970 vale a dire sottraendo via 500.000, o più in generale, sottraendo off 970 00:33:17,970 --> 00:33:20,010 n al quadrato, non è un grosso problema. 971 00:33:20,010 --> 00:33:22,490 Il n quadrato rende questi numero cresce veramente veloce. 972 00:33:22,490 --> 00:33:25,790 >> Ora, questo è solo importante nella misura in cui come noi, come gli informatici, 973 00:33:25,790 --> 00:33:29,350 sono generalmente non andare a prendersi cura tanto circa le sfumature di queste formule 974 00:33:29,350 --> 00:33:31,400 e esattamente ciò che il risposte precise sono. 975 00:33:31,400 --> 00:33:33,390 Ci interessa solo che, sai cosa? 976 00:33:33,390 --> 00:33:37,810 Alla fine della giornata, questa formula è dell'ordine di n quadrato. 977 00:33:37,810 --> 00:33:39,350 >> Sì, stiamo dividendo per 2 in là. 978 00:33:39,350 --> 00:33:41,360 Sì, stiamo sottraendo off n meno 2. 979 00:33:41,360 --> 00:33:46,860 Ma alla fine della giornata, il termine che ci fa male e ci costa molto 980 00:33:46,860 --> 00:33:48,995 un sacco di passi è quel termine quadrato. 981 00:33:48,995 --> 00:33:51,370 E così quello che un informatico sta per fare in generale 982 00:33:51,370 --> 00:33:54,160 è ignorare tutti coloro termini di ordine più piccoli, 983 00:33:54,160 --> 00:33:56,900 e basta guardare quello che contribuisce maggiormente al costo. 984 00:33:56,900 --> 00:34:00,530 >> E questo è bello, perché possiamo ora parla in modo molto maggiore generalità 985 00:34:00,530 --> 00:34:02,470 di algoritmi, e in grado di confrontarli. 986 00:34:02,470 --> 00:34:04,550 E il fatto che io sono usando questo O è intenzionale. 987 00:34:04,550 --> 00:34:06,680 Quando dico sull'ordine di, io sono specificamente 988 00:34:06,680 --> 00:34:09,560 riferendosi a qualcosa chiamato grande O. E grande O 989 00:34:09,560 --> 00:34:14,090 è una notazione che un computer scienziato usa per descrivere 990 00:34:14,090 --> 00:34:16,710 un limite superiore su qualcosa. 991 00:34:16,710 --> 00:34:21,150 >> Quindi, se si dice che un algoritmo è in grande O di n al quadrato, 992 00:34:21,150 --> 00:34:23,380 come ho proposto solo un poco fa, che i mezzi 993 00:34:23,380 --> 00:34:27,710 che in termini di funzionamento tempo o la sua efficienza, 994 00:34:27,710 --> 00:34:30,090 prende sull'ordine n di passi quadrato. 995 00:34:30,090 --> 00:34:31,420 Forse di più, forse meno. 996 00:34:31,420 --> 00:34:33,435 Ma è dell'ordine di n quadrato. 997 00:34:33,435 --> 00:34:34,560 E questo è il limite superiore. 998 00:34:34,560 --> 00:34:36,530 Non sarà più doloroso di quello. 999 00:34:36,530 --> 00:34:40,800 Non sarà n cubetti, o 2 al n, o qualcosa di molto più grande. 1000 00:34:40,800 --> 00:34:43,800 Questo è un limite superiore su qualunque che il costo è. 1001 00:34:43,800 --> 00:34:46,150 Quindi, dato che, diciamo prendere in considerazione solo alcuni esempi. 1002 00:34:46,150 --> 00:34:49,820 E questo è solo un elenco finito tempi di funzionamento di molto comuni 1003 00:34:49,820 --> 00:34:52,870 per algoritmi che è destinata ad essere illustrativo di alcune cose che abbiamo 1004 00:34:52,870 --> 00:34:53,600 già visto. 1005 00:34:53,600 --> 00:34:58,060 >> Così, per esempio, nel caso di selezione tipo, quello che sto sostenendo qui 1006 00:34:58,060 --> 00:35:02,250 è in esecuzione che la selezione di genere tempo è dell'ordine di n quadrato. 1007 00:35:02,250 --> 00:35:06,260 Nel peggiore dei casi, ho intenzione di avere un sacco di numeri casuali qui. 1008 00:35:06,260 --> 00:35:08,600 E come abbiamo visto matematicamente, se io continuo a camminare 1009 00:35:08,600 --> 00:35:11,310 l'elenco, attraverso la lista, la selezione del immediatamente inferiore 1010 00:35:11,310 --> 00:35:14,410 ripetutamente elemento, se in realtà scrivere tutti i passaggi 1011 00:35:14,410 --> 00:35:18,750 Sto prendendo come ho proposto formulaically prima, è dell'ordine di n quadrata 1012 00:35:18,750 --> 00:35:20,370 passi che sto prendendo. 1013 00:35:20,370 --> 00:35:24,520 >> E si scopre che bolla ordinamento e insertion sort 1014 00:35:24,520 --> 00:35:27,370 sono altrettanto lento nel caso peggiore. 1015 00:35:27,370 --> 00:35:32,040 Si consideri, ad esempio, insertion sort, l'ultimo algoritmo ci siamo occupati, 1016 00:35:32,040 --> 00:35:35,500 che ha avuto Osserviamo l'elemento, e poi inserirla in cui essa appartiene. 1017 00:35:35,500 --> 00:35:38,720 E poi abbiamo guardato l'elemento successivo, ed inserito in cui essa appartiene. 1018 00:35:38,720 --> 00:35:40,990 >> Quindi prendere in considerazione lo scenario migliore possibile. 1019 00:35:40,990 --> 00:35:45,590 Supponiamo che io avevo i miei volontari in fila letteralmente come questo, da uno a otto, 1020 00:35:45,590 --> 00:35:47,440 già ordinati. 1021 00:35:47,440 --> 00:35:51,300 Quanti passi è insertion sort andando a prendere per ordinare otto persone, 1022 00:35:51,300 --> 00:35:55,640 se arrivano sul palco cercando in questo modo? 1023 00:35:55,640 --> 00:35:57,410 >> Otto persone già ordinati. 1024 00:35:57,410 --> 00:35:58,760 E io uso insertion sort. 1025 00:35:58,760 --> 00:36:02,180 Quest'ultima degli algoritmi. 1026 00:36:02,180 --> 00:36:03,640 Bene, rivivere veloce reale. 1027 00:36:03,640 --> 00:36:05,504 Quindi, se mi metto qui, ne vedo uno. 1028 00:36:05,504 --> 00:36:06,420 Dove si appartiene? 1029 00:36:06,420 --> 00:36:07,730 Appartiene proprio qui. 1030 00:36:07,730 --> 00:36:08,330 Vedo due. 1031 00:36:08,330 --> 00:36:09,660 Dov'è due appartengono? 1032 00:36:09,660 --> 00:36:10,260 Giusto qui. 1033 00:36:10,260 --> 00:36:10,900 Vedo tre. 1034 00:36:10,900 --> 00:36:11,920 Dov'è tre appartengono? 1035 00:36:11,920 --> 00:36:12,480 Giusto qui. 1036 00:36:12,480 --> 00:36:13,100 >> Vedo quattro. 1037 00:36:13,100 --> 00:36:13,600 Giusto qui. 1038 00:36:13,600 --> 00:36:15,660 Cinque, sei, sette, otto. 1039 00:36:15,660 --> 00:36:17,320 Non c'è motivo di ripetermi. 1040 00:36:17,320 --> 00:36:21,260 E così, quanti passi è che in termini di n? 1041 00:36:21,260 --> 00:36:23,870 È nell'ordine di n passi, giusto? n meno 1. 1042 00:36:23,870 --> 00:36:27,567 Ma ho preso una serie lineare di di passi, e ora ho finito. 1043 00:36:27,567 --> 00:36:28,900 Ecco, questo è il caso migliore, però. 1044 00:36:28,900 --> 00:36:29,983 Che cosa circa il caso peggiore? 1045 00:36:29,983 --> 00:36:32,730 Che otto erano là, e sette erano laggiù, 1046 00:36:32,730 --> 00:36:35,840 e uno e due erano qui, così che l'elenco fosse veramente invertito? 1047 00:36:35,840 --> 00:36:38,300 >> Ebbene, che cosa succede davvero se questo è il numero? 1048 00:36:38,300 --> 00:36:41,300 E faremo solo un paio di esempi. 1049 00:36:41,300 --> 00:36:49,300 Che cosa succede se, infatti, il numero otto è qui, e le urla number--. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Che importa se, in effetti, il numero di otto è tutto fin qui, 1052 00:36:56,430 --> 00:36:57,790 e sto usando insertion sort? 1053 00:36:57,790 --> 00:36:58,290 >> OK. 1054 00:36:58,290 --> 00:37:00,280 Io rivendico al momento è a posto. 1055 00:37:00,280 --> 00:37:03,152 Ma ora, da dove viene seven-- sette va? 1056 00:37:03,152 --> 00:37:04,360 Naturalmente, va qui. 1057 00:37:04,360 --> 00:37:06,760 Quindi devo passare otto più di un posto. 1058 00:37:06,760 --> 00:37:08,554 Ora sei, dove va a finire? 1059 00:37:08,554 --> 00:37:09,220 Bene, tutto bene. 1060 00:37:09,220 --> 00:37:13,150 Ora, devo passare otto sopra un luogo, e sette su un luogo, 1061 00:37:13,150 --> 00:37:14,440 e poi mi plop giù sei. 1062 00:37:14,440 --> 00:37:16,870 >> Così la prima volta, essa costo me un passo per sistemare le cose, 1063 00:37:16,870 --> 00:37:18,570 poi mi è costato due passi per sistemare le cose. 1064 00:37:18,570 --> 00:37:20,370 Quanti passi è andando a prendere per risolvere 1065 00:37:20,370 --> 00:37:22,720 cose da mettere cinque nel posto giusto? 1066 00:37:22,720 --> 00:37:23,340 Tre. 1067 00:37:23,340 --> 00:37:29,520 Perché ora devo spostare uno, due, tre. 1068 00:37:29,520 --> 00:37:32,430 Quanti passi sta andando a prendere di mettere quattro al posto giusto? 1069 00:37:32,430 --> 00:37:36,040 4 più 5, più 6, più 7. 1070 00:37:36,040 --> 00:37:40,260 >> E così è matematicamente identico a quello che abbiamo descritto per la selezione sorta. 1071 00:37:40,260 --> 00:37:42,130 Abbiamo questa serie questo è solo l'aumento. 1072 00:37:42,130 --> 00:37:45,650 1 più 2 più 3 più 4, o, al contrario, 7 più 6 1073 00:37:45,650 --> 00:37:52,610 oltre 5 più 4 aggiunge per oggi fini per l'ordine di n al quadrato. 1074 00:37:52,610 --> 00:37:57,640 >> Permettetemi quindi di stipula le anche che bubble sort è anche n al quadrato. 1075 00:37:57,640 --> 00:38:01,340 Perché con bubble sort, ogni volta che vado attraverso la lista, 1076 00:38:01,340 --> 00:38:03,100 Sto prendendo approssimativamente quanti passi? 1077 00:38:03,100 --> 00:38:06,260 Ogni volta che ho letteralmente a piedi da lì a là? 1078 00:38:06,260 --> 00:38:07,960 Circa n passi. 1079 00:38:07,960 --> 00:38:12,650 Ma quante volte potrei bisogno di passare attraverso la lista? 1080 00:38:12,650 --> 00:38:13,920 >> Beh, più o meno il tempo n. 1081 00:38:13,920 --> 00:38:15,680 Forse n meno 1, ma circa n volte. 1082 00:38:15,680 --> 00:38:16,430 Beh, perché? 1083 00:38:16,430 --> 00:38:19,560 Bene, con bubble sort, se si parte con bubble sort, 1084 00:38:19,560 --> 00:38:23,570 con l'elenco nella peggiore possibile situazione, che è ancora completamente 1085 00:38:23,570 --> 00:38:25,550 al contrario, che cosa succederà? 1086 00:38:25,550 --> 00:38:28,830 Vado attraverso la lista, e il numero di uno appartiene tutto il modo là. 1087 00:38:28,830 --> 00:38:33,280 >> Ma con bubble sort, fino a che punto si fa a passare il mio primo passaggio attraverso la lista? 1088 00:38:33,280 --> 00:38:36,620 Quanti punti si procura più vicino al posto giusto? 1089 00:38:36,620 --> 00:38:37,240 Solo uno. 1090 00:38:37,240 --> 00:38:40,281 Quindi, se si tipo di ragione attraverso questo, ogni volta attraverso questo algoritmo, 1091 00:38:40,281 --> 00:38:41,880 Che prendono circa n passi di David. 1092 00:38:41,880 --> 00:38:44,940 Ma come molti passi l'elenco è 1093 00:38:44,940 --> 00:38:49,060 andando a prendere per uno a bolla a sinistra cui appartiene? 1094 00:38:49,060 --> 00:38:51,840 >> Ha avuto modo di muoversi come, n spazi in questo modo. 1095 00:38:51,840 --> 00:38:57,960 Quindi, solo per fare l'ordinamento della lista, Devo camminare avanti e indietro n volte. 1096 00:38:57,960 --> 00:39:01,540 E ogni volta, io sono guardando n elementi. 1097 00:39:01,540 --> 00:39:05,410 Quindi, fare le cose n n volte su l'ordine di n quadrato. 1098 00:39:05,410 --> 00:39:07,220 >> Ora, vedremo in qualche dei corti che 1099 00:39:07,220 --> 00:39:10,440 sono incorporati in prossimo problema del CS50 set, un altro approccio a questi, 1100 00:39:10,440 --> 00:39:13,490 ma per ora, diciamo solo in considerazione altre volte in esecuzione, 1101 00:39:13,490 --> 00:39:16,840 soprattutto se quelli smistamento prendono un po 'di tempo per affondare dentro. 1102 00:39:16,840 --> 00:39:21,790 Che cosa è un algoritmo che abbiamo visto già che assume dell'ordine di n passi? 1103 00:39:21,790 --> 00:39:27,560 >> Quello che dovrebbe adottare una serie lineare di di passi che abbiamo visto fino ad ora? 1104 00:39:27,560 --> 00:39:29,350 Che cos'è? 1105 00:39:29,350 --> 00:39:30,480 La ricerca elenco telefonico. 1106 00:39:30,480 --> 00:39:31,390 Il primo algoritmo. 1107 00:39:31,390 --> 00:39:31,560 Destra? 1108 00:39:31,560 --> 00:39:33,650 Dove siamo linearmente la ricerca di Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Davvero. 1110 00:39:34,150 --> 00:39:37,180 Da settimane a zero, quando ho iniziato girando una pagina alla volta, 1111 00:39:37,180 --> 00:39:40,095 e ho anche detto che era una specie sensazione di un algoritmo lineare, 1112 00:39:40,095 --> 00:39:42,720 e abbiamo avuto quella foto sulla scheda con la linea rossa retta 1113 00:39:42,720 --> 00:39:44,678 e il giallo dritto linea, quelli erano davvero 1114 00:39:44,678 --> 00:39:46,810 algoritmi che sono in grande O di n. 1115 00:39:46,810 --> 00:39:50,680 >> Poiché trovare Mike Smith in un telefono libro di pagine n, nel caso peggiore, 1116 00:39:50,680 --> 00:39:52,422 me n passi potrebbe prendere. 1117 00:39:52,422 --> 00:39:53,630 Che cosa circa la presa di presenza? 1118 00:39:53,630 --> 00:39:55,790 Uno due tre quattro cinque sei. 1119 00:39:55,790 --> 00:39:59,420 Qual è il tempo di esecuzione di questo algoritmo per prendere la partecipazione? 1120 00:39:59,420 --> 00:40:03,070 Big O di n, perché in teoria I devono puntare tutti nella stanza. 1121 00:40:03,070 --> 00:40:05,861 >> Ora, come un a parte, per quanto riguarda il altro ottimizzazione di settimana pari a zero? 1122 00:40:05,861 --> 00:40:08,117 Due, quattro, sei, otto, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Uno scienziato di computer sarebbe realizzare, aspetta un minuto, 1124 00:40:10,200 --> 00:40:12,320 questo è l'ordine di n diviso da due fasi. 1125 00:40:12,320 --> 00:40:12,820 Destra? 1126 00:40:12,820 --> 00:40:14,444 Perché sto facendo due persone alla volta. 1127 00:40:14,444 --> 00:40:17,015 Ma stiamo andando a ignorare quei termini di ordine inferiore, 1128 00:40:17,015 --> 00:40:19,140 e stiamo solo andando a buttare via la divisione per 2, 1129 00:40:19,140 --> 00:40:21,830 e dire, grande O di n per tale algoritmo pure. 1130 00:40:21,830 --> 00:40:22,760 >> Che dire di questa? 1131 00:40:22,760 --> 00:40:26,170 Ci salteremo su alcuni di questi, ma cosa è un algoritmo che fosse registro di n? 1132 00:40:26,170 --> 00:40:29,900 Che ha preso circa il log n passi? 1133 00:40:29,900 --> 00:40:30,870 Il divide et impera. 1134 00:40:30,870 --> 00:40:31,369 Esattamente. 1135 00:40:31,369 --> 00:40:33,900 Come la rubrica esempio Settimana zero e prima di oggi, 1136 00:40:33,900 --> 00:40:36,191 dove abbiamo diviso il problema ancora e ancora e ancora. 1137 00:40:36,191 --> 00:40:39,070 Abbiamo disegnato sul tabellone a settimana zero come una linea verde curva, 1138 00:40:39,070 --> 00:40:41,460 e abbiamo detto che giorno era un algoritmo logaritmica. 1139 00:40:41,460 --> 00:40:44,970 >> E in effetti, il numero di passi che prende per eseguire divide et impera, 1140 00:40:44,970 --> 00:40:48,610 o ricerca binaria come inizieremo definendolo, come nella rubrica telefonica, 1141 00:40:48,610 --> 00:40:50,680 è dell'ordine di log e gradini. 1142 00:40:50,680 --> 00:40:52,470 E questo è un po 'di uno strano. 1143 00:40:52,470 --> 00:40:54,910 >> Che cosa fa un passo, o più specificamente 1144 00:40:54,910 --> 00:40:56,240 un numero costante di passi? 1145 00:40:56,240 --> 00:40:58,865 Forse è a due, forse è tre, ma uno scienziato informatico solo 1146 00:40:58,865 --> 00:41:01,423 semplifica come grande O di 1, un numero costante di passi. 1147 00:41:01,423 --> 00:41:04,256 Che cosa è qualcosa che si potrebbe fare che prende un numero costante di passi? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Qual è il tempo di esecuzione di applausi? 1150 00:41:10,930 --> 00:41:11,920 Tempo costante. 1151 00:41:11,920 --> 00:41:12,420 Destra? 1152 00:41:12,420 --> 00:41:15,490 Come, che cosa è il tempo di esecuzione fare qualsiasi cosa che richiede un solo 1153 00:41:15,490 --> 00:41:18,570 operazione, come stampare F Ciao Mondo. 1154 00:41:18,570 --> 00:41:24,110 Che potrebbe dire di essere costante di tempo, a meno che meno caso angolo con stampa F, 1155 00:41:24,110 --> 00:41:28,260 quello che potrebbe essere il tempo di esecuzione di stampa F effettivamente essere? 1156 00:41:28,260 --> 00:41:28,790 E perché? 1157 00:41:28,790 --> 00:41:30,550 Qual è la misura n in quel caso? 1158 00:41:30,550 --> 00:41:32,251 >> PUBBLICO: [incomprensibile]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. MALAN: Esattamente. 1160 00:41:33,250 --> 00:41:34,900 Il numero di caratteri vogliamo stampare. 1161 00:41:34,900 --> 00:41:36,191 Quindi è molto sensibili al contesto. 1162 00:41:36,191 --> 00:41:39,910 Oggi, ci siamo concentrati molto su lettere e numeri qui sul tabellone. 1163 00:41:39,910 --> 00:41:43,540 Ma potrebbe anche essere caratteri in una stringa effettiva. 1164 00:41:43,540 --> 00:41:46,420 Così si scopre c'è un altro provvedimento che inizierà preoccuparsi, 1165 00:41:46,420 --> 00:41:48,530 e questo è il contrario di grande O, per così dire. 1166 00:41:48,530 --> 00:41:50,120 >> Questa è la notazione omega. 1167 00:41:50,120 --> 00:41:53,380 Mentre grande O vuol dire che cosa è, il limite superiore il tempo di esecuzione? 1168 00:41:53,380 --> 00:41:55,580 Al massimo, quanto tempo potrebbe prendere qualcosa? 1169 00:41:55,580 --> 00:41:59,250 Omega-- dispiace questo continua a venire up-- è l'opposto di quello, 1170 00:41:59,250 --> 00:42:02,960 per cui si tratta di un limite inferiore al quantità di tempo qualcosa potrebbe prendere. 1171 00:42:02,960 --> 00:42:10,480 >> Così. per esempio, che cosa è un algoritmo che prende passi sempre n quadrati? 1172 00:42:10,480 --> 00:42:15,600 Ebbene, uno degli algoritmi che abbiamo visto oggi, infatti, potrebbe essere quello. 1173 00:42:15,600 --> 00:42:16,720 Selection sort. 1174 00:42:16,720 --> 00:42:18,270 Selezione una specie abbastanza stupido. 1175 00:42:18,270 --> 00:42:21,760 Anche se il algorithm-- dispiace, anche se l'array è già ordinato, 1176 00:42:21,760 --> 00:42:24,150 selection sort sta per tenere a ripercorrere la lista 1177 00:42:24,150 --> 00:42:28,907 per assicurarsi che ha il più piccolo elemento ancora e ancora e ancora. 1178 00:42:28,907 --> 00:42:31,740 E anche se gli esseri umani nel pubblico sa che, aspetta un minuto, 1179 00:42:31,740 --> 00:42:33,948 hai già superato il elemento più piccolo, il computer 1180 00:42:33,948 --> 00:42:37,300 non sa che fino a quando non appare tutto il percorso attraverso la lista. 1181 00:42:37,300 --> 00:42:40,240 Analogamente, un limite inferiore che potrebbe anche essere presa in considerazione 1182 00:42:40,240 --> 00:42:42,000 potrebbe essere tempo lineare. 1183 00:42:42,000 --> 00:42:48,260 >> Quanto tempo ci vuole per Elementi tipo n nel migliore 1184 00:42:48,260 --> 00:42:52,420 caso usando qualcosa come bubble sort? 1185 00:42:52,420 --> 00:42:54,280 Supponiamo che la vostra lista è già ordinato. 1186 00:42:54,280 --> 00:42:56,696 Abbiamo detto bubble sort assume l'ordine di n passi quadrato. 1187 00:42:56,696 --> 00:42:59,640 Ma cosa succede se è già ordinato? 1188 00:42:59,640 --> 00:43:02,310 Che cosa succede se ti rendi conto dopo un passaggio attraverso l'array 1189 00:43:02,310 --> 00:43:03,540 che hai fatto non swap? 1190 00:43:03,540 --> 00:43:05,970 Avete bisogno di continuare a fare più passaggi? 1191 00:43:05,970 --> 00:43:06,470 >> No. 1192 00:43:06,470 --> 00:43:10,340 Quindi un limite inferiore bubble sort potrebbe dirsi lineare. 1193 00:43:10,340 --> 00:43:11,830 Omega di n. 1194 00:43:11,830 --> 00:43:14,450 E possiamo guardare altri di questi. 1195 00:43:14,450 --> 00:43:17,990 Quindi, diamo un rapido sguardo a solo una visualizzazione qui 1196 00:43:17,990 --> 00:43:20,790 per vedere come queste si distinguono. 1197 00:43:20,790 --> 00:43:24,592 Ho intenzione di andare giù qui in questo Pagina che è disponibile sul sito web di C50, 1198 00:43:24,592 --> 00:43:27,550 ma sarà un dolore per arrivare a lavorare, dato che utilizza una tecnologia chiamata 1199 00:43:27,550 --> 00:43:30,560 Applet Java, che è una in gran parte non supportata in questi giorni, 1200 00:43:30,560 --> 00:43:32,730 almeno da Chrome e alcuni altri. 1201 00:43:32,730 --> 00:43:37,070 >> E lasciatemi andare avanti e accelerare l'operazione e spiegare cosa sta succedendo. 1202 00:43:37,070 --> 00:43:40,840 Questa è una dimostrazione di bolla tipo, il primo algoritmo che abbiamo guardato. 1203 00:43:40,840 --> 00:43:43,950 Ed è una visualizzazione dal fatto che ciascun di queste barre rappresenta un numero. 1204 00:43:43,950 --> 00:43:45,710 Più grande è il bar, il più grande è il numero. 1205 00:43:45,710 --> 00:43:47,520 Più piccolo è il bar, minore è il numero. 1206 00:43:47,520 --> 00:43:50,353 E che cosa si può vedere visivamente, anche anche se questo sta andando super veloce, 1207 00:43:50,353 --> 00:43:53,699 è che la barra rossa è come me, camminare avanti e indietro, che fissa i problemi. 1208 00:43:53,699 --> 00:43:56,740 Si può vedere che gli elementi più grandi sono infatti ribolle a destra, 1209 00:43:56,740 --> 00:43:59,650 e gli elementi più piccoli sono gorgogliare verso sinistra. 1210 00:43:59,650 --> 00:44:01,870 E qui, se si effettivamente guardare più da vicino, 1211 00:44:01,870 --> 00:44:04,330 possiamo effettivamente contare il numero di confronti e swap 1212 00:44:04,330 --> 00:44:05,350 che sono stati fatti. 1213 00:44:05,350 --> 00:44:07,360 >> Ma invece, diamo un'occhiata al secondo algoritmo 1214 00:44:07,360 --> 00:44:11,240 abbiamo guardato in precedenza con il nostro volontari, selezione di ordinamento. 1215 00:44:11,240 --> 00:44:13,500 Visivamente, ha un effetto molto diverso. 1216 00:44:13,500 --> 00:44:16,820 Ma è, ancora una volta, molto intuitivo, in che continuiamo a selezionare quello immediatamente inferiore 1217 00:44:16,820 --> 00:44:18,660 elemento, e abbiamo ottenuto un po 'di fortuna. 1218 00:44:18,660 --> 00:44:20,110 Che sentiva fondamentalmente più veloce. 1219 00:44:20,110 --> 00:44:22,840 Ma se ci siamo imbattuti di nuovo e di nuovo e di nuovo con un sacco di input, 1220 00:44:22,840 --> 00:44:26,680 ci piacerebbe vedere che è davvero ancora in grande O di n al quadrato. 1221 00:44:26,680 --> 00:44:29,920 >> Facciamo un ultimo uno qui, insertion sort, 1222 00:44:29,920 --> 00:44:33,180 che era il terzo algoritmo abbiamo guardato, e richiamo 1223 00:44:33,180 --> 00:44:36,700 che questo occupa della Elementi come li incontra, 1224 00:44:36,700 --> 00:44:39,290 Ma poi forse turni le cose per fare spazio, 1225 00:44:39,290 --> 00:44:41,660 l'inserimento di elementi a cui appartengono. 1226 00:44:41,660 --> 00:44:45,330 >> E anche questo finisce per dare il risultato finale. Ora tutti e tre questi 1227 00:44:45,330 --> 00:44:46,490 sentivo abbastanza veloce. 1228 00:44:46,490 --> 00:44:48,740 E infatti, io li imbattuto in un buon clip. 1229 00:44:48,740 --> 00:44:52,510 Ma fondamentalmente, sono tutti piuttosto orribile, ad essere onesti. 1230 00:44:52,510 --> 00:44:56,960 Tutti questi algoritmi finora che vengono eseguiti in grande O di n al quadrato 1231 00:44:56,960 --> 00:44:59,270 prendere un po 'di tempo di esecuzione alla fine. 1232 00:44:59,270 --> 00:45:01,920 >> E infatti, possiamo vedere e sentire questo, infine, 1233 00:45:01,920 --> 00:45:04,090 se mi tiro su questa terza e ultima demo. 1234 00:45:04,090 --> 00:45:05,840 Questa è un'altra visualizzazione che sta andando 1235 00:45:05,840 --> 00:45:08,500 per mostrare bubble sort a sinistra, selezione sorta nel mezzo, 1236 00:45:08,500 --> 00:45:13,410 e qualcosa, come uno dei nostri mano solleva in precedenza suggerito, 1237 00:45:13,410 --> 00:45:15,020 merge sort sulla destra. 1238 00:45:15,020 --> 00:45:16,937 Un divide et impera strategia sulla destra. 1239 00:45:16,937 --> 00:45:19,520 E questo è, infatti, ciò che siamo andando a guardare il Mercoledì. 1240 00:45:19,520 --> 00:45:21,990 Ma andiamo tempo queste per l'esecuzione in parallelo. 1241 00:45:21,990 --> 00:45:26,765 È approssimativamente lo stesso numero di elementi, il tutto in esecuzione allo stesso tempo. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble sort vs selezione sorta vs merge sort. 1244 00:45:34,440 --> 00:45:36,760 >> Ora, stanno tutti in esecuzione in teoria, allo stesso tempo. 1245 00:45:36,760 --> 00:45:39,830 La CPU è in esecuzione al la stessa velocità, ma 1246 00:45:39,830 --> 00:45:44,014 può sentire che noia questo è molto rapidamente sta per diventare, 1247 00:45:44,014 --> 00:45:45,930 e quanto velocemente quando iniettiamo un po 'di settimane 1248 00:45:45,930 --> 00:45:49,330 Gli algoritmi di zero può abbiamo accelerare le cose. 1249 00:45:49,330 --> 00:45:51,760 >> E ora confrontiamo questi in un ultimo modulo. 1250 00:45:51,760 --> 00:45:55,710 Ho intenzione di andare avanti Sito web CS50, dove 1251 00:45:55,710 --> 00:45:59,020 abbiamo questo ultimo anello per oggi, dove qualcuno su internet 1252 00:45:59,020 --> 00:46:03,960 gentilmente messo insieme un video che cattura ciò che diverso ordinamento 1253 00:46:03,960 --> 00:46:07,510 algoritmi suonano come. 1254 00:46:07,510 --> 00:46:09,577 Questo è insertion sort. 1255 00:46:09,577 --> 00:46:12,072 >> [SEGNALE ACUSTICO] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Per cui si sta applicando una frequenza in base all'altezza del bar bar. 1258 00:46:16,850 --> 00:46:19,826 Questo è il Bubble sort. 1259 00:46:19,826 --> 00:46:21,822 >> [ACUSTICO Warped] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Prossimamente è-- venire accanto selezione è-- sorta, 1262 00:46:45,774 --> 00:46:48,820 dove ancora una volta, stiamo selezionando il successivo elemento più piccolo, 1263 00:46:48,820 --> 00:46:51,820 e possiamo vederlo crescere da sinistra a destra. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Merge sorta, il nostro vincitore finora oggi. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Notate come è dividere le cose in [incomprensibile] a metà e quarti. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Sorta Gnome, che non abbiamo ha parlato, e crea visivamente 1270 00:47:21,660 --> 00:47:24,450 e audally un po 'di forma e suono diverso. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Andando avanti e indietro, pulire le cose. 1273 00:47:30,160 --> 00:47:32,230 Verificate anche heapsort sul sito web di questo tipo. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> E questo è tutto. 1276 00:47:36,810 --> 00:47:38,210 Ci vediamo la prossima volta. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing E MUSICA] 1279 00:47:48,334 --> 00:50:24,839