1 00:00:00,000 --> 00:00:00,488 2 00:00:00,488 --> 00:00:10,800 >> [MUSIC PLAYING] 3 00:00:10,800 --> 00:00:13,500 DAVID MALAN: Va bene. 4 00:00:13,500 --> 00:00:14,670 Va bene, bentornato. 5 00:00:14,670 --> 00:00:18,120 Quindi questo è Settimana 4, l'inizio della stessa, già. 6 00:00:18,120 --> 00:00:21,320 E vi ricordate che la scorsa settimana, abbiamo messo codificare a parte solo per un po ' 7 00:00:21,320 --> 00:00:24,240 e abbiamo iniziato a parlare un po 'di più di alto livello, di cose come 8 00:00:24,240 --> 00:00:28,130 ricerca e l'ordinamento, che però le idee un po 'semplici, sono 9 00:00:28,130 --> 00:00:31,840 rappresentativo di una classe di problemi si inizierà a risolvere in particolare 10 00:00:31,840 --> 00:00:34,820 come si inizia a pensare finale progetti e soluzioni interessanti che si 11 00:00:34,820 --> 00:00:36,760 potrebbe avere a problemi reali. 12 00:00:36,760 --> 00:00:39,490 Ora bubble sort è stato uno dei più semplici tali algoritmi ed esso 13 00:00:39,490 --> 00:00:42,900 lavorato avendo questi piccoli numeri in un elenco o in una matrice di tipo 14 00:00:42,900 --> 00:00:46,530 bolla la loro strada fino alla cima, e il grandi numeri spostano la loro strada verso il basso per 15 00:00:46,530 --> 00:00:47,930 la fine di quella lista. 16 00:00:47,930 --> 00:00:50,650 >> E ricordiamo che potremmo visualizzare bubble sort un po ' 17 00:00:50,650 --> 00:00:52,310 qualcosa di simile a questo. 18 00:00:52,310 --> 00:00:53,640 Quindi, mi permetta di andare avanti e fare clic sul pulsante Start. 19 00:00:53,640 --> 00:00:55,350 Ho preselezionati bubble sort. 20 00:00:55,350 --> 00:00:58,920 E se vi ricordate che il blu più alto linee rappresentano grandi numeri, piccolo 21 00:00:58,920 --> 00:01:03,300 le linee blu rappresentano piccoli numeri, come passiamo attraverso questo nuovo e di nuovo e 22 00:01:03,300 --> 00:01:07,680 nuovamente, confrontando due barre adiacenti altro in rosso, stiamo andando a scambiare la 23 00:01:07,680 --> 00:01:11,010 più grande e il più piccolo, se sono fuori uso. 24 00:01:11,010 --> 00:01:14,150 >> Quindi questo sarà andare avanti e andare avanti e andare su, e vedrete che il più grande 25 00:01:14,150 --> 00:01:16,700 elementi stanno facendo la loro strada verso il destra, e gli elementi più piccoli sono 26 00:01:16,700 --> 00:01:17,900 facendosi largo a sinistra. 27 00:01:17,900 --> 00:01:21,380 Ma abbiamo cominciato a quantificare l'efficienza, la 28 00:01:21,380 --> 00:01:22,970 qualità di questo algoritmo. 29 00:01:22,970 --> 00:01:25,200 E abbiamo detto che nel peggiore caso, questo algoritmo ha preso 30 00:01:25,200 --> 00:01:27,940 approssimativamente quanti passi? 31 00:01:27,940 --> 00:01:28,980 >> Così n quadrato. 32 00:01:28,980 --> 00:01:30,402 E che cosa era n? 33 00:01:30,402 --> 00:01:31,650 >> AUDIENCE: numero di elementi. 34 00:01:31,650 --> 00:01:32,790 >> DAVID MALAN: Quindi è stata la n numero di elementi. 35 00:01:32,790 --> 00:01:33,730 E così lo faremo spesso. 36 00:01:33,730 --> 00:01:36,650 Ogni volta che vogliamo parlare della dimensione di un problema o la dimensione di un 37 00:01:36,650 --> 00:01:39,140 ingresso, o la quantità di tempo necessario per produrre un output, ci limiteremo a 38 00:01:39,140 --> 00:01:41,610 qualunque sia generalizzata l'ingresso è come n. 39 00:01:41,610 --> 00:01:45,970 Quindi torna alla Settimana 0, le pagine del numero nella rubrica era n. 40 00:01:45,970 --> 00:01:47,550 Il numero di studenti nella stanza è stata di n. 41 00:01:47,550 --> 00:01:49,630 Quindi anche qui, stiamo seguendo quel modello. 42 00:01:49,630 --> 00:01:52,800 >> Ora n quadrato non è particolarmente veloce, quindi abbiamo cercato di fare di meglio. 43 00:01:52,800 --> 00:01:55,970 E così abbiamo guardato un paio di altri algoritmi, tra cui 44 00:01:55,970 --> 00:01:57,690 erano selection sort. 45 00:01:57,690 --> 00:01:59,180 Quindi, ordinamento per selezione è un po 'diverso. 46 00:01:59,180 --> 00:02:03,130 Era quasi più semplice, oserei dire, per cui ho iniziato all'inizio del 47 00:02:03,130 --> 00:02:06,740 elenco dei nostri volontari e io di nuovo e ancora e ancora ha attraversato 48 00:02:06,740 --> 00:02:10,060 la lista, pizzicando la più piccola elemento alla volta e mettendo lui o 49 00:02:10,060 --> 00:02:13,040 lei all'inizio della lista. 50 00:02:13,040 --> 00:02:16,410 >> Ma anche questo, una volta che abbiamo iniziato a pensare attraverso la matematica e più grande 51 00:02:16,410 --> 00:02:19,860 immagine, ha pensato a quante volte Stavo andando avanti e indietro e indietro 52 00:02:19,860 --> 00:02:24,090 e indietro, abbiamo detto, nel caso peggiore, selection sort, troppo, era quello che? 53 00:02:24,090 --> 00:02:24,960 n al quadrato. 54 00:02:24,960 --> 00:02:27,490 Ora, nel mondo reale, potrebbe realtà essere marginalmente più veloce. 55 00:02:27,490 --> 00:02:30,620 Perché ancora una volta, non ho dovuto tenere backtracking una volta che avevo ordinato il 56 00:02:30,620 --> 00:02:31,880 elementi più piccoli. 57 00:02:31,880 --> 00:02:35,090 Ma se ci pensiamo molto grande N, e se si ordina di fare fuori la matematica come 58 00:02:35,090 --> 00:02:39,170 Ho fatto sulla scheda, con il n quadrato qualcosa di meno, tutto il resto 59 00:02:39,170 --> 00:02:41,850 oltre al n al quadrato, una volta n diventa veramente grande, non 60 00:02:41,850 --> 00:02:42,850 importa tanto. 61 00:02:42,850 --> 00:02:45,470 Così come gli informatici, abbiamo una sorta di chiudere un occhio per il più piccolo 62 00:02:45,470 --> 00:02:49,220 fattori e concentrarsi solo sul fattore in un'espressione che sta andando a fare 63 00:02:49,220 --> 00:02:50,330 la differenza più grande. 64 00:02:50,330 --> 00:02:52,840 >> Bene, infine, abbiamo cercato a insertion sort. 65 00:02:52,840 --> 00:02:56,620 E questo era simile nello spirito, ma piuttosto che passare attraverso iterativo e 66 00:02:56,620 --> 00:03:01,250 selezionare l'elemento più piccolo uno alla tempo, ho invece preso la mano che mi 67 00:03:01,250 --> 00:03:04,070 è stato trattato, e ho deciso, tutti a destra, tu appartieni qui. 68 00:03:04,070 --> 00:03:06,160 Poi sono passato al prossimo elemento e ha deciso che lui o 69 00:03:06,160 --> 00:03:07,470 lei apparteneva qui. 70 00:03:07,470 --> 00:03:08,810 E poi mi sono spostato su e su. 71 00:03:08,810 --> 00:03:11,780 E potrei a, lungo la strada, spostare questi ragazzi al fine di 72 00:03:11,780 --> 00:03:13,030 fare spazio per loro. 73 00:03:13,030 --> 00:03:16,880 Così che era una sorta di inversione mentale di ordinamento per selezione che abbiamo 74 00:03:16,880 --> 00:03:18,630 chiamato insertion sort. 75 00:03:18,630 --> 00:03:20,810 >> Quindi questi argomenti che si verifichi nel mondo reale. 76 00:03:20,810 --> 00:03:23,640 Solo pochi anni fa, quando un certo senatore era candidato alla presidenza, 77 00:03:23,640 --> 00:03:27,160 Eric Schmidt, al momento l'amministratore delegato di Google, in realtà ha avuto l'opportunità 78 00:03:27,160 --> 00:03:28,040 per intervistarlo. 79 00:03:28,040 --> 00:03:32,010 E abbiamo pensato di condividere questo YouTube Clip per voi qui, se potessimo alzare 80 00:03:32,010 --> 00:03:32,950 il volume. 81 00:03:32,950 --> 00:03:39,360 >> [RIPRODUZIONE VIDEO] 82 00:03:39,360 --> 00:03:44,620 >> -Ora, il senatore, sei qui a Google, e mi piace pensare di presidenza 83 00:03:44,620 --> 00:03:46,042 come un colloquio di lavoro. 84 00:03:46,042 --> 00:03:47,770 >> [Risata] 85 00:03:47,770 --> 00:03:50,800 >> -Ora è difficile da ottenere un lavoro come presidente. 86 00:03:50,800 --> 00:03:52,480 E che stai passando i rigori ora. 87 00:03:52,480 --> 00:03:54,330 E 'anche difficile ottenere un lavoro presso Google. 88 00:03:54,330 --> 00:03:59,610 Abbiamo domande e chiediamo i nostri candidati domande. 89 00:03:59,610 --> 00:04:02,250 E questo è da Larry Schwimmer. 90 00:04:02,250 --> 00:04:05,325 >> [Risata] 91 00:04:05,325 --> 00:04:06,400 -Voi pensate che stia scherzando? 92 00:04:06,400 --> 00:04:08,750 E 'proprio qui. 93 00:04:08,750 --> 00:04:12,110 Qual è il modo più efficace per ordinare un milione di numeri interi da quattro soldi? 94 00:04:12,110 --> 00:04:15,810 >> [Risata] 95 00:04:15,810 --> 00:04:18,260 >> -Beh, uh - 96 00:04:18,260 --> 00:04:19,029 >> -Mi dispiace. 97 00:04:19,029 --> 00:04:19,745 Forse dovremmo - 98 00:04:19,745 --> 00:04:21,000 >> -No, no, no, no, no. 99 00:04:21,000 --> 00:04:21,470 >> -Questo non è un - 100 00:04:21,470 --> 00:04:22,185 OK. 101 00:04:22,185 --> 00:04:25,328 >> -Penso che il bubble sort sarebbe essere il modo sbagliato di procedere. 102 00:04:25,328 --> 00:04:26,792 >> [Risata] 103 00:04:26,792 --> 00:04:28,510 >> [Applausi e applausi] 104 00:04:28,510 --> 00:04:31,211 >> -Andiamo, chi lo ha detto? 105 00:04:31,211 --> 00:04:32,155 OK. 106 00:04:32,155 --> 00:04:33,350 >> [FINE RIPRODUZIONE VIDEO] 107 00:04:33,350 --> 00:04:35,070 >> DAVID MALAN: Quindi il gioco è fatto. 108 00:04:35,070 --> 00:04:39,600 Così abbiamo cominciato a quantificare questi esecuzione volte, per così dire, con qualcosa 109 00:04:39,600 --> 00:04:43,480 chiamato notazione asintotica, che è riferisco solo alla nostra specie di svolta 110 00:04:43,480 --> 00:04:47,420 un occhio a quei fattori più piccoli e solo guardando il tempo di esecuzione, 111 00:04:47,420 --> 00:04:51,250 le prestazioni di questi algoritmi, quando n diventa veramente grande nel tempo. 112 00:04:51,250 --> 00:04:55,110 E così abbiamo introdotto grandi O. e grande O rappresentato qualcosa che abbiamo pensato 113 00:04:55,110 --> 00:04:57,000 di come un limite superiore. 114 00:04:57,000 --> 00:04:59,570 E in realtà, Barry, possiamo abbassare che il microfono un po '? 115 00:04:59,570 --> 00:05:01,040 >> Abbiamo pensato di tutto questo è un limite superiore. 116 00:05:01,040 --> 00:05:04,710 Così grande O di n mezzo al quadrato che in il caso peggiore, qualcosa come 117 00:05:04,710 --> 00:05:07,780 selection sort avrebbe preso n passi al quadrato. 118 00:05:07,780 --> 00:05:10,310 O qualcosa di simile insertion sort farebbe n passi al quadrato. 119 00:05:10,310 --> 00:05:15,150 Ora per qualcosa come l'inserimento sorta, quello che era il caso peggiore? 120 00:05:15,150 --> 00:05:18,200 Dato un array, qual è la cosa peggiore possibile scenario che si potrebbe trovare 121 00:05:18,200 --> 00:05:20,650 te di fronte a? 122 00:05:20,650 --> 00:05:21,860 >> E 'completamente indietro, giusto? 123 00:05:21,860 --> 00:05:24,530 Perché se è completamente all'indietro, devi fare un sacco di lavoro. 124 00:05:24,530 --> 00:05:26,420 Perché se sei completamente all'indietro, si sta andando a trovare la 125 00:05:26,420 --> 00:05:28,840 grande elemento qui, anche se essa appartiene laggiù. 126 00:05:28,840 --> 00:05:31,140 Quindi hai intenzione di dire, va bene, a questo momento nel tempo, si appartengono qui, 127 00:05:31,140 --> 00:05:32,310 così lo lasciano in pace. 128 00:05:32,310 --> 00:05:35,425 >> Poi ti rendi conto, oh, accidenti, devo spostare questo elemento leggermente più piccolo di 129 00:05:35,425 --> 00:05:36,470 sinistra di voi. 130 00:05:36,470 --> 00:05:38,770 Poi devo farlo di nuovo e ancora e ancora. 131 00:05:38,770 --> 00:05:41,410 E se ho camminato avanti e indietro, si potrebbe ordinare di sentire le prestazioni di 132 00:05:41,410 --> 00:05:45,540 tale algoritmo, perché costantemente sono io mischiare tutti gli altri verso il basso nella 133 00:05:45,540 --> 00:05:46,510 matrice per fare spazio per essa. 134 00:05:46,510 --> 00:05:47,750 Ecco, questo è il caso peggiore. 135 00:05:47,750 --> 00:05:48,570 >> Per contrasto - 136 00:05:48,570 --> 00:05:50,320 e questo era un cliffhanger ultima volta - 137 00:05:50,320 --> 00:05:54,065 abbiamo detto che insertion sort era un omega di che cosa? 138 00:05:54,065 --> 00:05:57,530 Qual è il miglior esecuzione nel caso tempo di insertion sort? 139 00:05:57,530 --> 00:05:58,520 Quindi è in realtà n. 140 00:05:58,520 --> 00:06:00,980 Quello era il vuoto che abbiamo lasciato sulla scheda ultima volta. 141 00:06:00,980 --> 00:06:03,160 >> Ed è omega di n perché perché? 142 00:06:03,160 --> 00:06:06,630 Ebbene, proprio nel migliore dei casi, ciò che è insertion sort sta per essere consegnato? 143 00:06:06,630 --> 00:06:09,830 Beh, un elenco che è completamente allineati già, minimo lavoro da fare. 144 00:06:09,830 --> 00:06:12,460 Ma ciò che è semplice di insertion sort è che perché inizia qui e 145 00:06:12,460 --> 00:06:15,340 decide, oh, tu sei il numero uno, sei dei nostri. 146 00:06:15,340 --> 00:06:16,970 Oh, che fortuna. 147 00:06:16,970 --> 00:06:17,740 >> Tu sei il numero due. 148 00:06:17,740 --> 00:06:19,030 È inoltre appartieni qui. 149 00:06:19,030 --> 00:06:21,010 Numero tre, ancora meglio, tu appartieni qui. 150 00:06:21,010 --> 00:06:25,210 Non appena si arriva alla fine della pseudocodice lista, per l'inserimento di specie 151 00:06:25,210 --> 00:06:28,010 che abbiamo raggiunto attraverso verbalmente ultima volta, è fatta. 152 00:06:28,010 --> 00:06:32,790 Ma per selezione, per contrasto, tenuto a fare che cosa? 153 00:06:32,790 --> 00:06:35,260 >> Continuava a scorrere l'elenco ancora e ancora e ancora. 154 00:06:35,260 --> 00:06:39,160 Perché l'intuizione fondamentale solo ci fosse una volta che hai guardato fino alla 155 00:06:39,160 --> 00:06:42,500 fine della lista si può essere certi che l'elemento selezionato è stato 156 00:06:42,500 --> 00:06:45,560 infatti l'elemento attualmente più piccolo. 157 00:06:45,560 --> 00:06:48,920 Quindi questi diversi modelli mentali fine per cedere alcuni molto del mondo reale 158 00:06:48,920 --> 00:06:53,130 differenze per noi, così come questi differenze teoriche asintotici. 159 00:06:53,130 --> 00:06:56,910 >> Quindi, solo per ricapitolare, quindi, grande O di n quadrato, abbiamo visto un paio di tale 160 00:06:56,910 --> 00:06:58,350 algoritmi finora. 161 00:06:58,350 --> 00:06:59,580 Big O di n? 162 00:06:59,580 --> 00:07:02,870 Che cosa è un algoritmo che potrebbe dire di essere grande O di n? 163 00:07:02,870 --> 00:07:06,930 Nel peggiore dei casi, richiede una serie lineare di passi. 164 00:07:06,930 --> 00:07:07,810 >> OK, ricerca lineare. 165 00:07:07,810 --> 00:07:10,470 E, nel caso peggiore, dove è la elemento che stai cercando, quando 166 00:07:10,470 --> 00:07:12,950 l'applicazione di ricerca lineare? 167 00:07:12,950 --> 00:07:14,680 >> OK, nel caso peggiore, non è nemmeno lì. 168 00:07:14,680 --> 00:07:17,000 O nel secondo caso peggiore, e ' fino alla fine, che è 169 00:07:17,000 --> 00:07:18,880 più-o-meno una differenza di un solo passaggio. 170 00:07:18,880 --> 00:07:21,180 Così alla fine della giornata, possiamo dire che è lineare. 171 00:07:21,180 --> 00:07:23,910 Big O di n sarebbe ricerca lineare, perché nel caso peggiore, la 172 00:07:23,910 --> 00:07:26,610 elemento non è ancora lì o è fino alla fine. 173 00:07:26,610 --> 00:07:29,370 >> Beh, grande O di log di n. 174 00:07:29,370 --> 00:07:32,760 Non abbiamo parlato con dovizia di particolari su questo, ma abbiamo visto questo prima. 175 00:07:32,760 --> 00:07:36,840 Ciò che viene eseguito nella cosiddetta logaritmica tempo, nel caso peggiore? 176 00:07:36,840 --> 00:07:38,500 >> Già, ricerca in modo binario. 177 00:07:38,500 --> 00:07:42,930 E la ricerca binaria nel caso peggiore potrebbe avere l'elemento in qualche parte 178 00:07:42,930 --> 00:07:45,640 la metà, o da qualche parte all'interno della matrice. 179 00:07:45,640 --> 00:07:48,040 Ma a trovare solo una volta che si dividere la lista a metà, in 180 00:07:48,040 --> 00:07:48,940 metà, a metà, a metà. 181 00:07:48,940 --> 00:07:50,200 E poi voilà, è lì. 182 00:07:50,200 --> 00:07:52,500 O ancora, nel peggiore dei casi, non è nemmeno lì. 183 00:07:52,500 --> 00:07:56,770 Ma non sai che non c'è fino a quando si ordina di raggiungere quell'ultimo 184 00:07:56,770 --> 00:08:00,470 bottom-maggior parte degli elementi di dimezzare e il dimezzamento e dimezzamento. 185 00:08:00,470 --> 00:08:01,400 >> Big O di 1. 186 00:08:01,400 --> 00:08:03,540 Così potremmo grande O di 2, O grande di 3. 187 00:08:03,540 --> 00:08:06,260 Ogni volta che si desidera solo un numero costante, abbiamo appena sorta di appena semplificare 188 00:08:06,260 --> 00:08:07,280 che come O grande di 1. 189 00:08:07,280 --> 00:08:10,440 Pur se realisticamente, ci vuole 2 o anche 100 passi, se si tratta di un 190 00:08:10,440 --> 00:08:13,680 numero costante di passi, diciamo solo grande O di 1. 191 00:08:13,680 --> 00:08:15,930 Che cosa è un algoritmo che è in grande O di 1? 192 00:08:15,930 --> 00:08:18,350 >> AUDIENCE: Trovare la lunghezza di una variabile. 193 00:08:18,350 --> 00:08:21,090 >> DAVID MALAN: Trovare il lunghezza di una variabile? 194 00:08:21,090 --> 00:08:23,870 >> PUBBLICO: No, la lunghezza se è già ordinato. 195 00:08:23,870 --> 00:08:24,160 >> DAVID MALAN: Buono. 196 00:08:24,160 --> 00:08:27,850 OK, in modo da trovare la lunghezza di qualcosa se la lunghezza che qualcosa, come 197 00:08:27,850 --> 00:08:30,020 una matrice, viene memorizzato in qualche variabile. 198 00:08:30,020 --> 00:08:33,380 Perché si può solo leggere la variabile, o stampare la variabile, o 199 00:08:33,380 --> 00:08:34,960 basta accedere generalmente quella variabile. 200 00:08:34,960 --> 00:08:37,299 E voilà, che richiede tempo costante. 201 00:08:37,299 --> 00:08:38,909 >> Al contrario, pensare di nuovo a zero. 202 00:08:38,909 --> 00:08:42,460 Ripensate alla prima settimana di C, chiamare solo printf e stampa 203 00:08:42,460 --> 00:08:46,240 qualcosa sullo schermo è senza dubbio costante di tempo, perché ci vuole solo 204 00:08:46,240 --> 00:08:50,880 certo numero di cicli di CPU per mostrare che il testo sullo schermo. 205 00:08:50,880 --> 00:08:52,720 O aspettare - lo fa? 206 00:08:52,720 --> 00:08:56,430 Altrimenti come potremmo modellare la prestazioni di printf? 207 00:08:56,430 --> 00:09:00,420 Qualcuno come non essere d'accordo, che forse non è il tempo davvero costante? 208 00:09:00,420 --> 00:09:03,600 In che senso potrebbe printf è in esecuzione tempo, in realtà la stampa di una stringa su 209 00:09:03,600 --> 00:09:05,580 lo schermo, sia qualcosa di diversa costante. 210 00:09:05,580 --> 00:09:07,860 >> AUDIENCE: [incomprensibile]. 211 00:09:07,860 --> 00:09:08,230 >> DAVID MALAN: Già. 212 00:09:08,230 --> 00:09:09,300 Quindi dipende dalla nostra prospettiva. 213 00:09:09,300 --> 00:09:13,390 Se noi pensiamo che in realtà l'ingresso in modo printf come la corda, e 214 00:09:13,390 --> 00:09:16,380 quindi si misura la dimensione di tale ingresso per la sua lunghezza - quindi chiamiamolo 215 00:09:16,380 --> 00:09:17,780 che la lunghezza n, come pure - 216 00:09:17,780 --> 00:09:21,990 discutibilmente, printf è di per sé grande O di n perché sta andando a prendere n passi 217 00:09:21,990 --> 00:09:24,750 per stampare ciascuna di quelle n personaggi, molto probabilmente. 218 00:09:24,750 --> 00:09:27,730 Almeno nella misura in cui si suppone che forse si sta usando un ciclo for 219 00:09:27,730 --> 00:09:28,560 sotto la cappa. 220 00:09:28,560 --> 00:09:30,860 >> Ma dovremmo guardare quella codice per capire meglio. 221 00:09:30,860 --> 00:09:33,650 E infatti, una volta che voi ragazzi cominciate analizzare i propri algoritmi, si 222 00:09:33,650 --> 00:09:34,900 letteralmente fare proprio questo. 223 00:09:34,900 --> 00:09:37,765 Sorta di bulbo oculare tuo codice e pensare circa - tutto bene, ho questo anello 224 00:09:37,765 --> 00:09:41,870 qui o ho un cicli annidati qui, che sta per fare n cose N volte, 225 00:09:41,870 --> 00:09:46,050 ed è possibile ordinare il vostro senso della ragione attraverso il codice, anche se è 226 00:09:46,050 --> 00:09:47,980 pseudocodice e non il codice vero e proprio. 227 00:09:47,980 --> 00:09:49,730 >> E per quanto riguarda omega di n al quadrato? 228 00:09:49,730 --> 00:09:53,582 Quello che era un algoritmo che nella migliore caso, ancora preso n passi quadrati? 229 00:09:53,582 --> 00:09:54,014 Sì? 230 00:09:54,014 --> 00:09:54,880 >> AUDIENCE: [incomprensibile]. 231 00:09:54,880 --> 00:09:55,900 >> DAVID MALAN: selezione Così sorta. 232 00:09:55,900 --> 00:09:59,150 Perché in quel problema davvero ridotto per il fatto che ancora una volta, non lo so 233 00:09:59,150 --> 00:10:02,600 Ho trovato la corrente più piccolo fino a quando Ho controllato tutti gli elementi maledettamente. 234 00:10:02,600 --> 00:10:08,050 Così omega di, diciamo, n, appena si avvicinò con uno. 235 00:10:08,050 --> 00:10:09,300 Insertion sort. 236 00:10:09,300 --> 00:10:12,370 Se la lista sembra essere ordinati già, nel migliore dei casi non ci resta che 237 00:10:12,370 --> 00:10:15,090 per fare un passaggio attraverso di essa, a che punto siamo sicuri. 238 00:10:15,090 --> 00:10:17,890 E allora che si potrebbe dire ad essere lineare, di sicuro. 239 00:10:17,890 --> 00:10:20,570 >> Che dire di omega di 1? 240 00:10:20,570 --> 00:10:23,790 Quali sono, nel migliore dei casi, potrebbe prendere un numero costante di passi? 241 00:10:23,790 --> 00:10:27,220 Ricerca in modo lineare, se basta avere fortuna e l'elemento che stai cercando 242 00:10:27,220 --> 00:10:31,000 è proprio all'inizio della lista, se è lì che si sta iniziando la vostra 243 00:10:31,000 --> 00:10:33,070 lineare di attraversamento di tale elenco. 244 00:10:33,070 --> 00:10:35,180 >> E questo è vero di un certo numero di cose. 245 00:10:35,180 --> 00:10:37,660 Per esempio, anche binario ricerca è omega di 1. 246 00:10:37,660 --> 00:10:40,310 Perché quello che se si ottiene davvero maledettamente fortunato e smack-limanda nel mezzo di 247 00:10:40,310 --> 00:10:42,950 la matrice è il numero stai cercando? 248 00:10:42,950 --> 00:10:45,730 Così si può avere fortuna lì, così. 249 00:10:45,730 --> 00:10:49,190 >> Questo, infine, omega di n log n. 250 00:10:49,190 --> 00:10:52,573 Così n log n, non abbiamo davvero parlare ancora, ma - 251 00:10:52,573 --> 00:10:53,300 >> AUDIENCE: merge sort? 252 00:10:53,300 --> 00:10:53,960 >> DAVID MALAN: merge sort. 253 00:10:53,960 --> 00:10:56,920 Questo è stato il colpo di scena della scorsa volta, dove abbiamo proposto, e abbiamo dimostrato 254 00:10:56,920 --> 00:10:58,600 visivamente, che esistono algoritmi. 255 00:10:58,600 --> 00:11:02,470 E merge sort su un solo tale algoritmo che è fondamentalmente più veloce 256 00:11:02,470 --> 00:11:03,450 che alcuni di questi altri ragazzi. 257 00:11:03,450 --> 00:11:07,800 Infatti, unire breve è non solo nella caso migliore n log n, nel peggiore 258 00:11:07,800 --> 00:11:09,460 caso n log n. 259 00:11:09,460 --> 00:11:14,540 E quando si ha questa coincidenza di Omega e la grande O di essere la stessa cosa? 260 00:11:14,540 --> 00:11:17,310 In realtà possiamo descrivere che come ciò che è chiamato theta, anche se è un 261 00:11:17,310 --> 00:11:18,220 po 'meno comune. 262 00:11:18,220 --> 00:11:21,730 Ma questo significa che solo i due limiti, in questo caso, sono gli stessi. 263 00:11:21,730 --> 00:11:25,770 >> Così merge sort, che cosa fa questo davvero bollire fino a per noi? 264 00:11:25,770 --> 00:11:27,000 Beh, ricordare la motivazione. 265 00:11:27,000 --> 00:11:30,340 Permettetemi di tirare su un altro animazione che noi non guardiamo l'ultima volta. 266 00:11:30,340 --> 00:11:33,390 Questo, stessa idea, ma è un po 'più grande. 267 00:11:33,390 --> 00:11:36,160 E ho intenzione di andare avanti e sottolineare prima - abbiamo insertion sort su 268 00:11:36,160 --> 00:11:39,410 a sinistra in alto, poi selection sort, bubble sort, un paio di altri tipi - 269 00:11:39,410 --> 00:11:42,670 guscio e veloce - che non abbiamo parlato circa, e heap e merge sort. 270 00:11:42,670 --> 00:11:47,090 >> Così almeno cercare di concentrare i vostri occhi su i primi tre a sinistra e poi 271 00:11:47,090 --> 00:11:49,120 merge sort quando clicco questa freccia verde. 272 00:11:49,120 --> 00:11:51,900 Ma vi svelo tutti loro gestita, solo per vi darà un senso di diversità dei 273 00:11:51,900 --> 00:11:53,980 algoritmi che esistono nel mondo. 274 00:11:53,980 --> 00:11:56,180 Ho intenzione di lasciare che questa corsa per pochi secondi. 275 00:11:56,180 --> 00:11:59,640 E se si concentrano gli occhi - scegliere un algoritmo, si concentrano su di essa solo per un 276 00:11:59,640 --> 00:12:02,970 secondi - si comincia a vedere la modello che è attuazione. 277 00:12:02,970 --> 00:12:04,530 >> Merge sort, avviso, è fatto. 278 00:12:04,530 --> 00:12:06,430 Heap sort, quick sort, shell - 279 00:12:06,430 --> 00:12:09,480 così sembra abbiamo introdotto il tre peggiori algoritmi scorsa settimana. 280 00:12:09,480 --> 00:12:12,960 Ma questo è un bene che siamo qui oggi per guarda merge sort, che è uno dei 281 00:12:12,960 --> 00:12:16,500 quelli più facili è da guardare, anche anche se probabilmente sarà piegare la tua mente 282 00:12:16,500 --> 00:12:17,490 solo un po '. 283 00:12:17,490 --> 00:12:21,130 Qui possiamo vedere solo quanto selection sort schifo. 284 00:12:21,130 --> 00:12:24,600 >> Ma il rovescio della medaglia, è veramente facile da implementare. 285 00:12:24,600 --> 00:12:28,160 E forse per P Set 3, che è uno dei algoritmi si è scelto di implementare 286 00:12:28,160 --> 00:12:28,960 per l'edizione standard. 287 00:12:28,960 --> 00:12:30,970 Perfettamente bene, perfettamente corretto. 288 00:12:30,970 --> 00:12:35,210 >> Ma ancora una volta, come n diventa grande, se si scegliere di implementare un algoritmo più veloce 289 00:12:35,210 --> 00:12:39,020 come merge sort, probabilità sono a grandi e ingressi più grandi, il codice è solo 290 00:12:39,020 --> 00:12:39,800 andare a correre più veloce. 291 00:12:39,800 --> 00:12:41,090 Il tuo sito web sta andando a lavorare meglio. 292 00:12:41,090 --> 00:12:42,650 Gli utenti stanno per essere più felici. 293 00:12:42,650 --> 00:12:45,280 E così ci sono questi effetti della realtà dando 294 00:12:45,280 --> 00:12:47,350 noi un po 'di più profondo pensiero. 295 00:12:47,350 --> 00:12:49,990 >> Quindi diamo un'occhiata a ciò che si fondono specie è in realtà tutto. 296 00:12:49,990 --> 00:12:52,992 La cosa interessante è che si fondono specie è proprio questo. 297 00:12:52,992 --> 00:12:56,300 Si tratta, ancora una volta, quello che abbiamo chiamato pseudocodice, essere pseudocodice 298 00:12:56,300 --> 00:12:57,720 Sintassi simile all'inglese. 299 00:12:57,720 --> 00:12:59,890 E la semplicità è sorta di affascinante. 300 00:12:59,890 --> 00:13:02,840 >> Quindi, su input di n elementi - in modo che Significa solo, ecco un array. 301 00:13:02,840 --> 00:13:04,000 E 'ottenuto n oggetti in esso. 302 00:13:04,000 --> 00:13:05,370 Questo è tutto quello che stiamo dicendo qui. 303 00:13:05,370 --> 00:13:07,560 >> Se n è minore di 2, ritornare. 304 00:13:07,560 --> 00:13:08,640 Ecco, questo è proprio il caso banale. 305 00:13:08,640 --> 00:13:12,580 Se n è minore di 2, poi ovviamente è 1 o 0, nel qual caso la cosa 306 00:13:12,580 --> 00:13:14,780 è già ordinato o inesistenti, quindi basta tornare. 307 00:13:14,780 --> 00:13:15,900 Non c'è niente da fare. 308 00:13:15,900 --> 00:13:18,360 Ecco, questo è un semplice caso di cogliere off. 309 00:13:18,360 --> 00:13:20,110 >> Altrimenti, abbiamo tre gradini. 310 00:13:20,110 --> 00:13:23,650 Ordinare la metà sinistra degli elementi, specie la metà destra degli elementi, 311 00:13:23,650 --> 00:13:26,650 e quindi unire le due metà ordinate. 312 00:13:26,650 --> 00:13:29,400 La cosa interessante qui è che Sono una specie di punting, giusto? 313 00:13:29,400 --> 00:13:32,300 C'è una specie di definizione circolare a questo algoritmo. 314 00:13:32,300 --> 00:13:35,986 In che senso questo algoritmo di circolare definizione? 315 00:13:35,986 --> 00:13:37,850 >> AUDIENCE: [incomprensibile]. 316 00:13:37,850 --> 00:13:41,670 >> DAVID MALAN: Sì, il mio algoritmo di ordinamento, due dei suoi passaggi sono "specie 317 00:13:41,670 --> 00:13:44,640 qualcosa. "E così che pone la domanda, beh, cosa posso usare 318 00:13:44,640 --> 00:13:46,460 di ordinare la metà sinistra e la metà di destra? 319 00:13:46,460 --> 00:13:49,600 E la bellezza qui è che anche se ancora una volta, questo è il mind-bending 320 00:13:49,600 --> 00:13:54,030 parte potenzialmente, si può usare lo stesso algoritmo per ordinare la metà sinistra. 321 00:13:54,030 --> 00:13:54,700 >> Ma aspettate un minuto. 322 00:13:54,700 --> 00:13:57,070 Quando ti si dice di ordinare la metà sinistra, quali sono i due 323 00:13:57,070 --> 00:13:58,240 passi per essere il prossimo? 324 00:13:58,240 --> 00:14:00,550 Ci penseremo la metà sinistra del metà sinistra e destra 325 00:14:00,550 --> 00:14:01,420 metà della metà sinistra. 326 00:14:01,420 --> 00:14:04,430 Accidenti, come faccio a ordinare quei due metà, o quarti, ora? 327 00:14:04,430 --> 00:14:05,260 >> Ma va bene così. 328 00:14:05,260 --> 00:14:07,830 Abbiamo un algoritmo di ordinamento qui. 329 00:14:07,830 --> 00:14:10,660 E anche se si potrebbe preoccuparsi in primo luogo si tratta di una specie di infinito 330 00:14:10,660 --> 00:14:12,780 ciclo, è un ciclo che non è mai andando a finire - che sta per 331 00:14:12,780 --> 00:14:15,770 fine una volta che cosa succede? 332 00:14:15,770 --> 00:14:16,970 Una volta che n è minore di 2. 333 00:14:16,970 --> 00:14:19,180 Che alla fine sta per accadere, perché se si mantiene il dimezzamento e 334 00:14:19,180 --> 00:14:23,020 dimezzando in dimezzare queste metà, sicuramente alla fine si sta andando a finire 335 00:14:23,020 --> 00:14:25,350 con solo 1 o 0 elementi. 336 00:14:25,350 --> 00:14:28,500 A quel punto, questo algoritmo dice che si è fatto. 337 00:14:28,500 --> 00:14:31,020 >> Quindi, la vera magia di questa algoritmo sembra essere in 338 00:14:31,020 --> 00:14:33,470 il passo finale, la fusione. 339 00:14:33,470 --> 00:14:37,190 Questa semplice idea basta fondere due cose, è quello che sta succedendo in ultima analisi 340 00:14:37,190 --> 00:14:40,920 per permetterci di ordinare un array di, diciamo, otto elementi. 341 00:14:40,920 --> 00:14:44,410 Così ho più otto palline antistress up qui, otto pezzi di carta, e uno 342 00:14:44,410 --> 00:14:45,500 Google Glass - 343 00:14:45,500 --> 00:14:46,140 che riesco a mantenere. 344 00:14:46,140 --> 00:14:46,960 >> [Risata] 345 00:14:46,960 --> 00:14:48,970 >> DAVID MALAN: Se potessimo prendere otto volontari, e vediamo se possiamo 346 00:14:48,970 --> 00:14:51,430 giocare a questo fuori, così. 347 00:14:51,430 --> 00:14:52,500 Wow, OK. 348 00:14:52,500 --> 00:14:53,565 L'informatica è sempre divertente. 349 00:14:53,565 --> 00:14:54,320 D'accordo. 350 00:14:54,320 --> 00:14:57,770 Così come su voi tre, grande mano lassù. 351 00:14:57,770 --> 00:14:58,580 Quattro nella parte posteriore. 352 00:14:58,580 --> 00:15:02,220 E per quanto riguarda noi faremo voi tre in questa riga? 353 00:15:02,220 --> 00:15:03,390 E quattro nella parte anteriore. 354 00:15:03,390 --> 00:15:04,920 Quindi otto, andiamo su. 355 00:15:04,920 --> 00:15:12,060 >> [Risata] 356 00:15:12,060 --> 00:15:13,450 >> DAVID MALAN: In realtà sono non so che cosa sia. 357 00:15:13,450 --> 00:15:14,810 E 'le palle dello stress? 358 00:15:14,810 --> 00:15:16,510 Le lampade da tavolo? 359 00:15:16,510 --> 00:15:18,650 Il materiale? 360 00:15:18,650 --> 00:15:19,680 Internet? 361 00:15:19,680 --> 00:15:20,160 >> OK. 362 00:15:20,160 --> 00:15:21,310 Quindi forza up. 363 00:15:21,310 --> 00:15:22,310 Chi vorrebbe - 364 00:15:22,310 --> 00:15:23,570 continuano a venire su. 365 00:15:23,570 --> 00:15:24,240 Vediamo. 366 00:15:24,240 --> 00:15:26,460 E questo ti mette in posizione - 367 00:15:26,460 --> 00:15:27,940 siete in posizione uno. 368 00:15:27,940 --> 00:15:28,670 Uh-oh, aspetta un minuto. 369 00:15:28,670 --> 00:15:30,760 1, 2, 3, 4, 5, 6, 7 - Oh, bene. 370 00:15:30,760 --> 00:15:31,310 Va bene, siamo a posto. 371 00:15:31,310 --> 00:15:35,130 Va bene, così tutti hanno una sede, ma non sulla lastra di Google. 372 00:15:35,130 --> 00:15:36,475 Lasciatemi fare la fila questi. 373 00:15:36,475 --> 00:15:37,115 Qual è il tuo nome? 374 00:15:37,115 --> 00:15:37,440 >> MICHELLE: Michelle. 375 00:15:37,440 --> 00:15:38,090 >> DAVID MALAN: Michelle? 376 00:15:38,090 --> 00:15:42,000 Va bene, si arriva a guardare come il geek, se va bene. 377 00:15:42,000 --> 00:15:44,625 Beh, lo faccio anche, suppongo, solo per un momento. 378 00:15:44,625 --> 00:15:45,875 D'accordo, di attesa. 379 00:15:45,875 --> 00:15:48,510 380 00:15:48,510 --> 00:15:50,950 Abbiamo cercato di trovare un utilizzare caso per Google Glass, e noi 381 00:15:50,950 --> 00:15:53,750 pensato che sarebbe stato divertente fare solo questo quando le persone sono sul palco. 382 00:15:53,750 --> 00:15:57,120 Noi registreremo il mondo dal loro punto di vista. 383 00:15:57,120 --> 00:15:58,410 D'accordo. 384 00:15:58,410 --> 00:15:59,830 Non è forse quello che Google intende. 385 00:15:59,830 --> 00:16:02,260 Va bene, se non ti dispiace indossare questo per i prossimi minuti imbarazzanti, 386 00:16:02,260 --> 00:16:03,150 che sarebbe meraviglioso. 387 00:16:03,150 --> 00:16:08,620 >> Va bene, così abbiamo qui una serie di elementi, e che la matrice, come da 388 00:16:08,620 --> 00:16:11,480 pezzi di carta in queste persone ' mani, è attualmente non differenziati. 389 00:16:11,480 --> 00:16:12,050 >> MICHELLE: Oh, è così strano. 390 00:16:12,050 --> 00:16:12,810 >> DAVID MALAN: E 'più o meno casuale. 391 00:16:12,810 --> 00:16:15,760 E in un attimo, stiamo andando a provare implementare merge sort insieme 392 00:16:15,760 --> 00:16:17,950 e vedere dove questa intuizione fondamentale è. 393 00:16:17,950 --> 00:16:21,970 E il trucco con il merge sort è qualcosa che non abbiamo ancora assunto. 394 00:16:21,970 --> 00:16:24,030 Abbiamo veramente bisogno di un po 'di spazio aggiuntivo. 395 00:16:24,030 --> 00:16:26,650 Così che cosa sta andando essere particolarmente interessante di questo è che questi 396 00:16:26,650 --> 00:16:29,270 ragazzi stanno per muoversi un po ' po ', perché ho intenzione di assumere che 397 00:16:29,270 --> 00:16:31,880 c'è una serie extra di spazio, dire, proprio dietro di loro. 398 00:16:31,880 --> 00:16:34,570 >> Quindi, se sono dietro la loro sedia, che è l'array secondario. 399 00:16:34,570 --> 00:16:36,960 Se sono seduti qui, questo è la matrice primaria. 400 00:16:36,960 --> 00:16:40,170 Ma questa è una risorsa che noi abbiamo non sfruttato finora con bolla 401 00:16:40,170 --> 00:16:42,040 specie, con ordinamento per selezione, con insertion sort. 402 00:16:42,040 --> 00:16:44,600 Ricordiamo la scorsa settimana, tutti appena tipo di mescolate a posto. 403 00:16:44,600 --> 00:16:46,840 Non hanno usato la memoria aggiuntiva. 404 00:16:46,840 --> 00:16:49,310 Abbiamo fatto spazio per persone da spostamento di persone in giro. 405 00:16:49,310 --> 00:16:50,580 >> Quindi questa è una intuizione fondamentale, anche. 406 00:16:50,580 --> 00:16:53,410 C'è questo trade-off, in generale, in informatica, di risorse. 407 00:16:53,410 --> 00:16:55,800 Se si vuole accelerare qualcosa come il tempo, si sta andando a 408 00:16:55,800 --> 00:16:56,900 pagare un prezzo. 409 00:16:56,900 --> 00:17:00,750 E uno di questi prezzi è molto spesso spazio, la quantità di memoria o hard 410 00:17:00,750 --> 00:17:01,700 spazio su disco che si sta utilizzando. 411 00:17:01,700 --> 00:17:03,640 Oppure, francamente, l'importo del programmatore orario. 412 00:17:03,640 --> 00:17:06,700 Quanto tempo ti porta, l'umano, effettivamente attuare alcune di più 413 00:17:06,700 --> 00:17:07,829 algoritmo complicato. 414 00:17:07,829 --> 00:17:09,760 Ma per oggi, il trade-off è il tempo e lo spazio. 415 00:17:09,760 --> 00:17:11,930 >> Quindi, se voi ragazzi poteste semplicemente tenere il vostro numeri così possiamo vedere che sei 416 00:17:11,930 --> 00:17:15,839 anzi corrispondenza 4, 2, 6, 1, 3, 7, 8. 417 00:17:15,839 --> 00:17:16,599 Eccellente. 418 00:17:16,599 --> 00:17:19,520 Quindi ho intenzione di cercare di orchestrare cose, se voi ragazzi può solo 419 00:17:19,520 --> 00:17:21,800 seguire la mia guida qui. 420 00:17:21,800 --> 00:17:26,650 >> Quindi ho intenzione di implementare, in primo luogo, la primo passaggio del pseudocodice, che è 421 00:17:26,650 --> 00:17:29,440 su input di n elementi, se n è meno di 2, per poi tornare. 422 00:17:29,440 --> 00:17:31,370 Ovviamente, ciò non Applica, quindi passiamo. 423 00:17:31,370 --> 00:17:33,340 Così ordinare la metà sinistra degli elementi. 424 00:17:33,340 --> 00:17:36,220 Quindi questo significa che ho intenzione di concentrare la mia l'attenzione per un attimo su queste 425 00:17:36,220 --> 00:17:37,310 quattro ragazzi qui. 426 00:17:37,310 --> 00:17:39,774 Bene, che cosa devo fare dopo? 427 00:17:39,774 --> 00:17:40,570 >> AUDIENCE: ordinare la metà sinistra. 428 00:17:40,570 --> 00:17:42,780 >> DAVID MALAN: Quindi ora devo ordinare la metà sinistra di questi ragazzi. 429 00:17:42,780 --> 00:17:45,580 Perché ancora una volta, assumere a te stesso la obiettivo è quello di ordinare la metà sinistra. 430 00:17:45,580 --> 00:17:46,440 Come si fa a farlo? 431 00:17:46,440 --> 00:17:49,140 Basta seguire le istruzioni, anche se stiamo facendo di nuovo. 432 00:17:49,140 --> 00:17:50,160 Così ordinare la metà sinistra. 433 00:17:50,160 --> 00:17:52,030 Ora sto ordinamento questi due ragazzi. 434 00:17:52,030 --> 00:17:53,563 Che cosa viene dopo? 435 00:17:53,563 --> 00:17:54,510 >> AUDIENCE: ordinare la metà sinistra. 436 00:17:54,510 --> 00:17:55,460 >> DAVID MALAN: ordinare la metà sinistra. 437 00:17:55,460 --> 00:18:00,680 Così ora questi, questo posto qui, è una lista di dimensione 1. 438 00:18:00,680 --> 00:18:01,365 E tu come ti chiami? 439 00:18:01,365 --> 00:18:02,390 >> PRINCIPESSA MARGHERITA: Principessa Daisy. 440 00:18:02,390 --> 00:18:03,690 >> DAVID MALAN: Principessa Daisy è qui. 441 00:18:03,690 --> 00:18:07,470 E così lei è già ordinato, perché l'elenco è di dimensioni 1. 442 00:18:07,470 --> 00:18:09,490 Cosa devo fare dopo? 443 00:18:09,490 --> 00:18:13,680 OK, tornare, perché quella lista è di dimensione 1, che è meno di 2. 444 00:18:13,680 --> 00:18:14,320 Allora qual è il prossimo passo? 445 00:18:14,320 --> 00:18:17,490 E ora si deve tipo di marcia indietro nella vostra mente. 446 00:18:17,490 --> 00:18:19,340 >> Ordinare la metà di destra, che è - 447 00:18:19,340 --> 00:18:19,570 come ti chiami? 448 00:18:19,570 --> 00:18:20,220 >> LINDA: Linda. 449 00:18:20,220 --> 00:18:20,980 >> DAVID MALAN: Linda. 450 00:18:20,980 --> 00:18:23,210 E allora che cosa facciamo ora che abbiamo una lista di dimensione 1? 451 00:18:23,210 --> 00:18:24,440 >> AUDIENCE: Return. 452 00:18:24,440 --> 00:18:24,760 >> DAVID MALAN: Attento. 453 00:18:24,760 --> 00:18:29,540 Torniamo prima, e ora il terzo passo - e se io tipo di rappresentarlo con 454 00:18:29,540 --> 00:18:33,490 abbracciando i due sedili ora, ora mi devono unire questi due elementi. 455 00:18:33,490 --> 00:18:35,530 Così ora, purtroppo, gli elementi sono fuori uso. 456 00:18:35,530 --> 00:18:39,920 Ma è qui che il processo di fusione inizia a ottenere convincente. 457 00:18:39,920 --> 00:18:42,410 >> Quindi, se voi ragazzi poteste stare in piedi per poco un momento, ho bisogno di te, in un 458 00:18:42,410 --> 00:18:44,170 momento, al passaggio dietro la sedia. 459 00:18:44,170 --> 00:18:46,480 E se Linda, poiché 2 è più piccolo di 4, perché non fare 460 00:18:46,480 --> 00:18:48,130 si arriva intorno prima? 461 00:18:48,130 --> 00:18:48,690 Rimani lì. 462 00:18:48,690 --> 00:18:50,520 Così Linda, si arriva intorno prima. 463 00:18:50,520 --> 00:18:53,820 >> Ora, in realtà, se si tratta solo di un array potremmo semplicemente il suo muoversi in tempo reale 464 00:18:53,820 --> 00:18:55,360 da questa sedia a questo punto. 465 00:18:55,360 --> 00:18:57,770 Quindi immaginate che ha avuto una costante numero di punti 1. 466 00:18:57,770 --> 00:18:58,480 E ora - 467 00:18:58,480 --> 00:19:01,490 ma abbiamo bisogno di mettere in la prima posizione qui. 468 00:19:01,490 --> 00:19:03,930 >> E ora, se tu potessi venire in giro, così, stiamo andando a 469 00:19:03,930 --> 00:19:06,300 essere in posizione due. 470 00:19:06,300 --> 00:19:09,120 E anche se questo si sente come se fosse prendere un po ', cosa c'è di bello ora è 471 00:19:09,120 --> 00:19:14,710 che la metà sinistra del metà di sinistra è ora ordinato. 472 00:19:14,710 --> 00:19:18,010 Così che cosa è stato il passo successivo, se ora riavvolgere ulteriormente nella storia? 473 00:19:18,010 --> 00:19:18,980 >> AUDIENCE: la metà destra. 474 00:19:18,980 --> 00:19:19,900 >> DAVID MALAN: Suddividere la metà di destra. 475 00:19:19,900 --> 00:19:21,320 Quindi, voi ragazzi avete per fare questo, come bene. 476 00:19:21,320 --> 00:19:23,510 Quindi, se si poteva stare in piedi solo per un momento? 477 00:19:23,510 --> 00:19:25,192 E qual è il tuo nome? 478 00:19:25,192 --> 00:19:25,540 >> JESS: Jess. 479 00:19:25,540 --> 00:19:25,870 >> DAVID MALAN: Jess. 480 00:19:25,870 --> 00:19:29,720 OK, Jess è ora la sinistra la metà della metà di destra. 481 00:19:29,720 --> 00:19:31,400 E così lei è un elenco di dimensioni 1. 482 00:19:31,400 --> 00:19:32,380 Lei è ovviamente allineati. 483 00:19:32,380 --> 00:19:33,070 E il tuo nome? 484 00:19:33,070 --> 00:19:33,630 >> MICHELLE: Michelle. 485 00:19:33,630 --> 00:19:35,340 >> DAVID MALAN: Michelle è ovviamente una lista di dimensione 1. 486 00:19:35,340 --> 00:19:36,050 Ha già ordinato. 487 00:19:36,050 --> 00:19:38,690 Così ora la magia accade, il processo di fusione. 488 00:19:38,690 --> 00:19:39,790 Allora, chi sta andando a venire prima? 489 00:19:39,790 --> 00:19:41,560 Ovviamente Michelle. 490 00:19:41,560 --> 00:19:43,280 Quindi, se tu potessi venire in giro indietro. 491 00:19:43,280 --> 00:19:47,090 Lo spazio che abbiamo a disposizione per lei ora è proprio dietro questa sedia qui. 492 00:19:47,090 --> 00:19:51,580 E ora se potessi tornare indietro, come pure, ora abbiamo, per essere chiari, due 493 00:19:51,580 --> 00:19:53,810 due metà, ognuna di dimensioni 2 - 494 00:19:53,810 --> 00:19:57,090 e solo per amor di rappresentazione, se si potrebbe fare un po 'di spazio - 495 00:19:57,090 --> 00:19:59,780 uno a sinistra a metà qui, uno mezzo proprio qui. 496 00:19:59,780 --> 00:20:01,160 >> Riavvolgere ulteriormente nella storia. 497 00:20:01,160 --> 00:20:02,270 Che cosa è prossimo passo? 498 00:20:02,270 --> 00:20:03,030 >> AUDIENCE: Unisci. 499 00:20:03,030 --> 00:20:04,160 >> DAVID MALAN: Quindi ora dobbiamo unire. 500 00:20:04,160 --> 00:20:07,490 Quindi OK, ora, per fortuna, abbiamo appena liberato quattro sedie. 501 00:20:07,490 --> 00:20:11,480 Quindi abbiamo usato il doppio della memoria, ma possiamo dare flip-flopping tra 502 00:20:11,480 --> 00:20:12,330 i due array. 503 00:20:12,330 --> 00:20:14,190 Quindi, quale numero deve venire prima? 504 00:20:14,190 --> 00:20:14,850 Così Michelle, ovviamente. 505 00:20:14,850 --> 00:20:16,680 Allora venite in giro e prendere il tuo posto qui. 506 00:20:16,680 --> 00:20:19,120 E quindi il numero 2 è ovviamente successivo, in modo da venire qui. 507 00:20:19,120 --> 00:20:21,520 Numero 4, numero 6. 508 00:20:21,520 --> 00:20:23,390 E di nuovo, anche se c'è un po 'di camminare coinvolti, 509 00:20:23,390 --> 00:20:26,010 in realtà, questi potrebbero accadere istantaneamente, spostando uno - 510 00:20:26,010 --> 00:20:26,880 OK, ben suonato. 511 00:20:26,880 --> 00:20:28,350 >> [Risata] 512 00:20:28,350 --> 00:20:29,680 >> DAVID MALAN: E ora siamo in buona forma. 513 00:20:29,680 --> 00:20:34,910 La metà sinistra di tutta ingresso è stato ora risolto. 514 00:20:34,910 --> 00:20:37,370 Va bene, quindi questi ragazzi aveva il vantaggio della mia - 515 00:20:37,370 --> 00:20:40,340 come ha fatto a finire tutte le ragazze sul a sinistra e tutti i ragazzi di destra? 516 00:20:40,340 --> 00:20:42,450 >> OK, ragazzi 'girano adesso. 517 00:20:42,450 --> 00:20:44,680 Così non si attraversa questi passaggi. 518 00:20:44,680 --> 00:20:46,550 Vedremo se possiamo riapplicare la stessa pseudocodice. 519 00:20:46,550 --> 00:20:50,050 Se si vuole andare avanti e stare in piedi, e voi ragazzi, lasciate che vi dia il microfono. 520 00:20:50,050 --> 00:20:52,990 Vedi se non è possibile replicare ciò che abbiamo appena fatto qui sulla 521 00:20:52,990 --> 00:20:53,880 altra estremità della lista. 522 00:20:53,880 --> 00:20:59,530 Chi ha bisogno di parlare per primo, base all'algoritmo? 523 00:20:59,530 --> 00:21:03,210 Quindi spiegare che cosa si sta facendo prima di apportare eventuali movimenti del piede. 524 00:21:03,210 --> 00:21:05,930 >> SPEAKER 1: Va bene, così da Sono la metà sinistra del 525 00:21:05,930 --> 00:21:07,790 metà sinistra, torno. 526 00:21:07,790 --> 00:21:08,730 Giusto? 527 00:21:08,730 --> 00:21:09,250 >> DAVID MALAN: Buono. 528 00:21:09,250 --> 00:21:10,350 >> SPEAKER 1: E poi - 529 00:21:10,350 --> 00:21:11,800 >> DAVID MALAN: Chi fa il microfono va al successivo? 530 00:21:11,800 --> 00:21:12,920 >> SPEAKER 1: numero successivo. 531 00:21:12,920 --> 00:21:14,720 >> SPEAKER 2: Quindi sono la metà di destra della metà sinistra del 532 00:21:14,720 --> 00:21:17,830 metà sinistra, e torno. 533 00:21:17,830 --> 00:21:18,050 >> DAVID MALAN: Buono. 534 00:21:18,050 --> 00:21:18,550 Si ritorna. 535 00:21:18,550 --> 00:21:21,855 Così ora che cosa è il prossimo per voi due? 536 00:21:21,855 --> 00:21:23,740 >> SPEAKER 2: Vogliamo vedere chi è più piccolo. 537 00:21:23,740 --> 00:21:24,200 >> DAVID MALAN: Esattamente. 538 00:21:24,200 --> 00:21:24,940 Noi vogliamo unire. 539 00:21:24,940 --> 00:21:27,590 Lo spazio che andremo a utilizzare per unire si in, anche se sono 540 00:21:27,590 --> 00:21:30,250 ovviamente ordinato già, stiamo andando a seguire lo stesso algoritmo. 541 00:21:30,250 --> 00:21:31,560 Quindi chi va in dietro prima? 542 00:21:31,560 --> 00:21:35,720 Così 3, e poi 7. 543 00:21:35,720 --> 00:21:38,570 E ora il microfono passa a questi ragazzi, OK? 544 00:21:38,570 --> 00:21:43,590 >> SPEAKER 3: Quindi io sono la metà destra del metà sinistra, e il mio n è inferiore 545 00:21:43,590 --> 00:21:45,048 1, quindi sono solo andando a passare - 546 00:21:45,048 --> 00:21:46,380 >> DAVID MALAN: Buono. 547 00:21:46,380 --> 00:21:49,450 >> SPEAKER 4: Sono la metà destra del metà destra la metà destra, e io sono 548 00:21:49,450 --> 00:21:51,740 anche una sola persona, quindi sono intenzione di tornare. 549 00:21:51,740 --> 00:21:52,990 Così ora ci fondiamo. 550 00:21:52,990 --> 00:21:55,140 551 00:21:55,140 --> 00:21:56,150 >> SPEAKER 3: Allora torniamo indietro. 552 00:21:56,150 --> 00:21:57,160 >> DAVID MALAN: Così si va nella parte posteriore. 553 00:21:57,160 --> 00:21:59,200 Quindi 5 va in primo luogo, poi 8. 554 00:21:59,200 --> 00:22:01,240 E ora pubblico, che è l' un passo che dobbiamo ora tornare indietro 555 00:22:01,240 --> 00:22:02,200 back to nella nostra mente? 556 00:22:02,200 --> 00:22:02,940 >> AUDIENCE: Unisci. 557 00:22:02,940 --> 00:22:07,270 >> DAVID MALAN: Unire metà sinistra e destra metà della metà dell'originale sinistra. 558 00:22:07,270 --> 00:22:08,840 Così ora - 559 00:22:08,840 --> 00:22:10,520 e giusto per chiarire questo punto, fare un po 'di spazio 560 00:22:10,520 --> 00:22:11,690 tra voi due ragazzi. 561 00:22:11,690 --> 00:22:13,800 Quindi, ora che è le due liste, sinistra e destra. 562 00:22:13,800 --> 00:22:18,320 Quindi, come possiamo ora fondiamo voi ragazzi in la prima fila di posti a sedere di nuovo? 563 00:22:18,320 --> 00:22:19,600 >> 3 va prima. 564 00:22:19,600 --> 00:22:20,850 Poi 5, ovviamente. 565 00:22:20,850 --> 00:22:23,110 566 00:22:23,110 --> 00:22:27,330 Poi 7, e ora 8. 567 00:22:27,330 --> 00:22:28,710 OK, e ora siamo? 568 00:22:28,710 --> 00:22:29,650 >> AUDIENCE: Non fatto. 569 00:22:29,650 --> 00:22:32,440 >> DAVID MALAN: non fatto, perché ovviamente, c'è un passo dalla fine. 570 00:22:32,440 --> 00:22:35,720 Ma ancora una volta, la ragione per cui sto usando questo gergo come "rewind nella vostra mente" 571 00:22:35,720 --> 00:22:37,160 è perché è davvero cosa sta succedendo. 572 00:22:37,160 --> 00:22:39,610 Stiamo andando attraverso tutti questi passaggi, ma noi siamo una sorta di pausa di un 573 00:22:39,610 --> 00:22:42,480 momento, le immersioni più in profondità nel algoritmo, fermandosi per un attimo, 574 00:22:42,480 --> 00:22:45,840 immersioni più in profondità l'algoritmo, e ora dobbiamo ordinare di rewind nel nostro 575 00:22:45,840 --> 00:22:49,430 menti e annullare tutti questi livelli che abbiamo una sorta di messa in attesa. 576 00:22:49,430 --> 00:22:51,790 >> Così ora abbiamo due liste di dimensione 4. 577 00:22:51,790 --> 00:22:54,790 Se voi ragazzi poteste stare in piedi per l'ultima volta e fare un po 'di spazio qui per 578 00:22:54,790 --> 00:22:57,230 chiarire che questa è la sinistra metà dell'originale, la 579 00:22:57,230 --> 00:22:58,620 a destra la metà di quello originale. 580 00:22:58,620 --> 00:23:01,060 Chi è il primo numero che abbiamo bisogno di tirare nella parte posteriore? 581 00:23:01,060 --> 00:23:01,870 Michelle, naturalmente. 582 00:23:01,870 --> 00:23:03,230 >> Così abbiamo messo Michelle qui. 583 00:23:03,230 --> 00:23:05,080 E chi ha il numero 2? 584 00:23:05,080 --> 00:23:06,440 Numero 2 arriva sulla schiena. 585 00:23:06,440 --> 00:23:07,800 Numero 3? 586 00:23:07,800 --> 00:23:08,510 Eccellente. 587 00:23:08,510 --> 00:23:16,570 Numero 4, Numero 5, Numero 6, numero 7, e il numero 8. 588 00:23:16,570 --> 00:23:18,850 >> OK, si sentiva come un sacco di passi, di sicuro. 589 00:23:18,850 --> 00:23:22,390 Ma ora vediamo se non possiamo confermare sorta di intuitivamente che questa 590 00:23:22,390 --> 00:23:26,190 algoritmo fondamentalmente, in particolare per quanto n diventa veramente grande, come abbiamo visto 591 00:23:26,190 --> 00:23:29,170 con le animazioni, è sostanzialmente più veloce. 592 00:23:29,170 --> 00:23:33,400 Quindi io sostengo questo algoritmo, nel peggiore caso e anche nel caso migliore, 593 00:23:33,400 --> 00:23:36,160 è grande O di n volte log n. 594 00:23:36,160 --> 00:23:39,160 Cioè, c'è qualche aspetto di questo algoritmo che prende in n passi, ma 595 00:23:39,160 --> 00:23:43,110 c'è un altro aspetto da qualche parte in che iterazione, che looping, che 596 00:23:43,110 --> 00:23:44,410 prende log n passi. 597 00:23:44,410 --> 00:23:49,154 Possiamo mettere il dito su ciò che quelle due numeri si riferiscono a? 598 00:23:49,154 --> 00:23:51,320 Beh, dove - 599 00:23:51,320 --> 00:23:54,160 dov'e il microfono va? 600 00:23:54,160 --> 00:23:58,660 >> SPEAKER 1: Sarebbe il log N sia ci rompere in due - 601 00:23:58,660 --> 00:23:59,630 dividendo per due, essenzialmente. 602 00:23:59,630 --> 00:24:00,120 >> DAVID MALAN: Esattamente. 603 00:24:00,120 --> 00:24:03,000 Ogni volta che vediamo in ogni algoritmo così Finora, non c'è stato questo modello di 604 00:24:03,000 --> 00:24:04,200 dividere, dividere, dividere. 605 00:24:04,200 --> 00:24:05,700 Ed è tipicamente ridotto a qualcosa che è 606 00:24:05,700 --> 00:24:07,100 logaritmica, log base 2. 607 00:24:07,100 --> 00:24:10,180 Ma potrebbe davvero essere qualsiasi cosa, ma log base 2. 608 00:24:10,180 --> 00:24:11,330 >> Ora, per quanto riguarda il n? 609 00:24:11,330 --> 00:24:14,550 Vedo che abbiamo tipo divisi voi ragazzi - divisi voi, divisi, 610 00:24:14,550 --> 00:24:15,910 diviso voi, diviso. 611 00:24:15,910 --> 00:24:18,760 Da dove viene il termine viene? 612 00:24:18,760 --> 00:24:19,810 >> Quindi è la fusione. 613 00:24:19,810 --> 00:24:20,610 Perché pensarci. 614 00:24:20,610 --> 00:24:25,420 Quando si uniscono otto persone insieme, per cui la metà di loro sono una serie di quattro 615 00:24:25,420 --> 00:24:27,770 e l'altra metà sono un altro serie di quattro, come si fa 616 00:24:27,770 --> 00:24:28,820 di fare la fusione? 617 00:24:28,820 --> 00:24:30,830 Beh, che avete fatto è abbastanza intuitivo. 618 00:24:30,830 --> 00:24:34,140 >> Ma se io invece facevo un po 'di più metodicamente, avrei puntato 619 00:24:34,140 --> 00:24:38,090 la persona più a sinistra prima con la sinistra mano, indicò la persona più a sinistra 620 00:24:38,090 --> 00:24:42,080 di che la metà con la mano destra, e solo successivamente attraversato il 621 00:24:42,080 --> 00:24:46,990 elenco, indicando l'elemento più piccolo ogni volta, spostando il dito sopra e 622 00:24:46,990 --> 00:24:48,970 oltre necessarie durante l'intero elenco. 623 00:24:48,970 --> 00:24:51,890 Ma ciò che è fondamentale per questa fusione processo è che sto confrontando queste coppie 624 00:24:51,890 --> 00:24:53,460 degli elementi. 625 00:24:53,460 --> 00:24:57,270 Dalla metà di destra e da sinistra la metà, non sono mai una volta backtracking. 626 00:24:57,270 --> 00:25:00,570 >> Quindi l'unione si sta prendendo non più di n passi. 627 00:25:00,570 --> 00:25:03,250 E quante volte ho avuto per farlo fondere? 628 00:25:03,250 --> 00:25:07,150 Beh, non più di n, e abbiamo appena visto che con la fusione finale. 629 00:25:07,150 --> 00:25:13,120 E così se fai qualcosa che prende log n passi n volte, o viceversa, 630 00:25:13,120 --> 00:25:15,210 sta andando a darci n volte log n. 631 00:25:15,210 --> 00:25:16,310 >> E perché è meglio? 632 00:25:16,310 --> 00:25:19,600 Beh, se sappiamo già che log n è meglio che n - giusto? 633 00:25:19,600 --> 00:25:22,590 Abbiamo visto nella ricerca binaria, la rubrica telefonica esempio, log n è stato sicuramente 634 00:25:22,590 --> 00:25:23,760 meglio che lineare. 635 00:25:23,760 --> 00:25:28,420 Quindi che significa n volte log n è sicuramente meglio di n volte un altro 636 00:25:28,420 --> 00:25:30,390 n, AKA n quadrato. 637 00:25:30,390 --> 00:25:32,400 Ed è quello che ci sentiamo in definitiva. 638 00:25:32,400 --> 00:25:34,928 >> Così grande applauso, se Potremmo, per questi ragazzi. 639 00:25:34,928 --> 00:25:38,920 >> [Applausi] 640 00:25:38,920 --> 00:25:41,550 >> DAVID MALAN: E i tuoi doni di commiato - si può mantenere i numeri, 641 00:25:41,550 --> 00:25:44,010 se si desidera. 642 00:25:44,010 --> 00:25:45,620 E il tuo regalo d'addio, come al solito. 643 00:25:45,620 --> 00:25:47,290 Oh, e vi invieremo il filmato, Michelle. 644 00:25:47,290 --> 00:25:48,343 Grazie. 645 00:25:48,343 --> 00:25:49,250 D'accordo. 646 00:25:49,250 --> 00:25:50,400 Aiutare se stessi a una palla di stress. 647 00:25:50,400 --> 00:25:54,110 >> E mi permetta di tirare su, nel frattempo, il nostro amico Rob Bowden per offrire 648 00:25:54,110 --> 00:25:59,520 prospettiva alquanto diversa su questa, dato che si può pensare a questi 649 00:25:59,520 --> 00:26:01,280 passaggi che avvengono in un po ' modo diverso. 650 00:26:01,280 --> 00:26:04,750 Infatti, il set-up per ciò Rob è circa per mostrarci presuppone che abbiamo 651 00:26:04,750 --> 00:26:09,030 già fatto la suddivisione del grande elenco in otto piccole liste, 652 00:26:09,030 --> 00:26:10,570 ciascuno di dimensione 1. 653 00:26:10,570 --> 00:26:13,350 >> Quindi stiamo cambiando il pseudocodice un po 'solo per una sorta di arrivare al 654 00:26:13,350 --> 00:26:15,320 idea di base di come la fusione funziona. 655 00:26:15,320 --> 00:26:17,600 Ma il tempo di esecuzione di ciò che che sta per fare è ancora 656 00:26:17,600 --> 00:26:19,110 andando ad essere lo stesso. 657 00:26:19,110 --> 00:26:23,540 E ancora, il set-up è che lui è iniziato con otto liste di dimensione 1. 658 00:26:23,540 --> 00:26:27,730 Quindi ti sei perso la parte in cui lui è effettivamente fatto il log n, log n, log n 659 00:26:27,730 --> 00:26:31,205 dividendo dell'ingresso. 660 00:26:31,205 --> 00:26:32,120 >> [RIPRODUZIONE VIDEO] 661 00:26:32,120 --> 00:26:33,615 >> -Questo è tutto per il punto uno. 662 00:26:33,615 --> 00:26:38,270 Per la fase due, più volte unisce coppie di liste. 663 00:26:38,270 --> 00:26:39,210 >> DAVID MALAN: Hm. 664 00:26:39,210 --> 00:26:41,270 Solo l'audio è in arrivo fuori dal mio computer. 665 00:26:41,270 --> 00:26:42,520 Proviamo di nuovo. 666 00:26:42,520 --> 00:26:45,330 667 00:26:45,330 --> 00:26:48,310 >> -Basta scegliere arbitrariamente quale - Ora abbiamo quattro liste. 668 00:26:48,310 --> 00:26:51,590 669 00:26:51,590 --> 00:26:52,120 Imparare prima. 670 00:26:52,120 --> 00:26:53,040 >> DAVID MALAN: Ci andiamo. 671 00:26:53,040 --> 00:27:00,510 >> -Unione di 108 e 15, finiamo con l'elenco 15, 108. 672 00:27:00,510 --> 00:27:07,170 Unione di 50 e 4, si finire con 4, 50. 673 00:27:07,170 --> 00:27:12,990 Unione di 8 e 42, si finire con 8, 42. 674 00:27:12,990 --> 00:27:19,970 E la fusione 23 e 16, si finire con 16, 23. 675 00:27:19,970 --> 00:27:23,270 >> Ora tutte le nostre liste sono di dimensione 2. 676 00:27:23,270 --> 00:27:26,690 Notare che ciascuno dei quattro elenchi vengono ordinati. 677 00:27:26,690 --> 00:27:29,450 Così possiamo iniziare la fusione coppie di liste di nuovo. 678 00:27:29,450 --> 00:27:38,420 Unione di 15 e 108 e 4 e 50, si prendere la prima 4, poi il 15, poi 679 00:27:38,420 --> 00:27:41,500 il 50, allora il 108. 680 00:27:41,500 --> 00:27:50,610 Unione di 8, 42 e 16, 23, per prima cosa prendiamo l'8, poi il 16, poi il 23, 681 00:27:50,610 --> 00:27:52,700 poi il 42. 682 00:27:52,700 --> 00:27:57,600 >> Così ora abbiamo solo due liste di dimensioni 4, ciascuno dei quali è ordinato. 683 00:27:57,600 --> 00:28:01,170 Così ora fondiamo queste due liste. 684 00:28:01,170 --> 00:28:11,835 In primo luogo, prendiamo il 4, poi prendiamo la 8, poi prendiamo la 15, poi 16, poi 685 00:28:11,835 --> 00:28:19,456 23, poi 42, poi 50, poi 108. 686 00:28:19,456 --> 00:28:19,872 >> [FINE RIPRODUZIONE VIDEO] 687 00:28:19,872 --> 00:28:23,430 >> DAVID MALAN: Anche in questo caso, si noti, non ha mai toccato un dato coppa più di una volta 688 00:28:23,430 --> 00:28:24,860 dopo l'avanzamento di là di esso. 689 00:28:24,860 --> 00:28:26,200 Quindi non ha mai ripetere. 690 00:28:26,200 --> 00:28:29,850 Quindi lui è sempre in movimento di lato, ed è lì che abbiamo ottenuto il nostro n. 691 00:28:29,850 --> 00:28:33,290 >> Perché non mi permetta di tirare su una animazione che abbiamo visto in precedenza, ma questa volta 692 00:28:33,290 --> 00:28:35,110 concentrandosi solo su merge sort. 693 00:28:35,110 --> 00:28:38,030 Lasciami andare avanti e Zoom in su questo qui. 694 00:28:38,030 --> 00:28:42,530 In primo luogo mi permetta di scegliere un ingresso casuale, magnificare questo, e si può ordinare di vedere 695 00:28:42,530 --> 00:28:46,600 quello che abbiamo preso per scontato, in precedenza, merge sort sta effettivamente facendo. 696 00:28:46,600 --> 00:28:50,330 >> Quindi notare che si ottiene queste metà o questi quartieri o questi ottavi di 697 00:28:50,330 --> 00:28:53,140 problema che improvvisamente iniziare a prendere forma. 698 00:28:53,140 --> 00:28:57,070 E poi finalmente, si vede a alla fine che bam, 699 00:28:57,070 --> 00:28:58,860 tutto si fuse insieme. 700 00:28:58,860 --> 00:29:01,690 >> Quindi questi sono solo tre diversi assume la stessa idea. 701 00:29:01,690 --> 00:29:05,980 Ma l'intuizione fondamentale, proprio come spartiacque e conquistare nella prima classe, 702 00:29:05,980 --> 00:29:10,640 era che abbiamo deciso di dividere in qualche modo il problema in qualcosa di grande, in 703 00:29:10,640 --> 00:29:14,760 qualcosa sorta di identico nello spirito, ma più piccolo e più piccolo 704 00:29:14,760 --> 00:29:15,660 e più piccoli. 705 00:29:15,660 --> 00:29:18,420 >> Ora un altro modo divertente per ordinare di pensare di questi, anche se non lo e ' 706 00:29:18,420 --> 00:29:20,520 per darvi la stessa intuitiva comprensione, è 707 00:29:20,520 --> 00:29:21,640 la seguente animazione. 708 00:29:21,640 --> 00:29:25,400 Quindi questo è un video di qualcuno mettere insieme quello associato diverso 709 00:29:25,400 --> 00:29:29,970 suoni con le varie operazioni di insertion sort, per merge sort, e 710 00:29:29,970 --> 00:29:31,150 per un paio di altri. 711 00:29:31,150 --> 00:29:32,330 Quindi, in un momento, sto andando a colpire Play. 712 00:29:32,330 --> 00:29:33,600 Si tratta di circa un minuto a lungo. 713 00:29:33,600 --> 00:29:37,410 E anche se è ancora possibile vedere la modelli accadendo, questa volta si può 714 00:29:37,410 --> 00:29:41,420 anche sentire come questi algoritmi sono eseguendo differente e con 715 00:29:41,420 --> 00:29:43,950 un po 'diversi modelli. 716 00:29:43,950 --> 00:29:45,830 >> Questo è insertion sort. 717 00:29:45,830 --> 00:29:50,400 >> [TONI GIOCANO] 718 00:29:50,400 --> 00:29:52,400 >> DAVID MALAN: E 'ancora una volta sta cercando inserire ogni elemento 719 00:29:52,400 --> 00:29:52,900 in cui essa appartiene. 720 00:29:52,900 --> 00:29:54,628 Questo è il bubble sort. 721 00:29:54,628 --> 00:30:10,097 >> [TONI GIOCANO] 722 00:30:10,097 --> 00:30:13,630 >> DAVID MALAN: E si può ordinare di tatto come relativamente poco lavoro che sta facendo 723 00:30:13,630 --> 00:30:15,834 ad ogni passo. 724 00:30:15,834 --> 00:30:20,470 Questo è ciò che noia sembra. 725 00:30:20,470 --> 00:30:21,472 >> [TONI GIOCANO] 726 00:30:21,472 --> 00:30:25,222 >> DAVID MALAN: Questo è ordinamento per selezione, dove selezioniamo l'elemento che vogliamo da 727 00:30:25,222 --> 00:30:28,845 passando ancora e ancora e ancora e metterlo all'inizio. 728 00:30:28,845 --> 00:30:37,674 >> [TONI GIOCANO] 729 00:30:37,674 --> 00:30:43,970 >> DAVID MALAN: Questo è merge sort, che si può davvero iniziare a sentire. 730 00:30:43,970 --> 00:30:51,810 >> [TONI GIOCANO] 731 00:30:51,810 --> 00:30:54,770 >> [Risata] 732 00:30:54,770 --> 00:30:58,395 >> DAVID MALAN: qualcosa chiamato gnome sorta, che non abbiamo guardato. 733 00:30:58,395 --> 00:31:13,630 >> [TONI GIOCANO] 734 00:31:13,630 --> 00:31:17,910 >> DAVID MALAN: Allora fammi vedere, ora, distratto, come si spera, sei dal 735 00:31:17,910 --> 00:31:21,110 musica, se riesco a scivolare un po ' po 'di matematica qui. 736 00:31:21,110 --> 00:31:24,850 Quindi c'è un quarto modo che possiamo pensare a ciò che significa questi 737 00:31:24,850 --> 00:31:29,210 funzioni per essere più veloce di quelli che abbiamo visto prima. 738 00:31:29,210 --> 00:31:32,470 E se sei venuta al corso da uno sfondo di matematica, si 739 00:31:32,470 --> 00:31:36,030 in realtà sapere forse già che si può schiaffo un termine su questa tecnica - 740 00:31:36,030 --> 00:31:40,400 ricorsione cioè, una funzione che si fa chiamare in qualche modo. 741 00:31:40,400 --> 00:31:44,780 >> E ancora una volta, ricordare che merge sort pseudocodice è ricorsiva, nel senso 742 00:31:44,780 --> 00:31:48,460 che uno dei passaggi del merge sort era quello di chiamare sorta - 743 00:31:48,460 --> 00:31:49,740 cioè, se. 744 00:31:49,740 --> 00:31:52,480 Ma per fortuna, perché abbiamo tenuto chiamando sorta, o merge sort, 745 00:31:52,480 --> 00:31:55,880 specificamente, in una più piccola e la lista più piccola, alla fine abbiamo 746 00:31:55,880 --> 00:32:00,005 toccato il fondo grazie a quello che chiameremo un caso base, il caso a livello di codice che 747 00:32:00,005 --> 00:32:04,270 detto se l'elenco è piccolo, inferiore a 2 in tal caso, basta restituire immediatamente. 748 00:32:04,270 --> 00:32:07,550 Se non avessimo questo caso particolare, la algoritmo avrebbe mai toccare il fondo, 749 00:32:07,550 --> 00:32:11,010 e si potrebbe davvero entrare in un ciclo infinito veramente per sempre. 750 00:32:11,010 --> 00:32:14,330 >> Ma supponiamo che abbiamo voluto mettere ora alcuni numeri su questo, ancora una volta, utilizzando n 751 00:32:14,330 --> 00:32:15,660 come la dimensione dell'input. 752 00:32:15,660 --> 00:32:18,680 E volevo chiedere a voi, che cosa è il tempo totale coinvolti nella 753 00:32:18,680 --> 00:32:19,800 esecuzione merge sort? 754 00:32:19,800 --> 00:32:22,960 O più in generale, ciò che è il costo di esso nel tempo? 755 00:32:22,960 --> 00:32:24,730 >> Beh, è ​​abbastanza facile da misurare tale. 756 00:32:24,730 --> 00:32:29,010 Se n è minore di 2, il tempo coinvolto a ordinare n elementi, 757 00:32:29,010 --> 00:32:30,480 dove n è 2, è 0. 758 00:32:30,480 --> 00:32:31,410 Perché abbiamo appena torniamo. 759 00:32:31,410 --> 00:32:32,510 Non c'è lavoro da fare. 760 00:32:32,510 --> 00:32:35,660 Ora forse, forse è un passo o due passi per capire la quantità di 761 00:32:35,660 --> 00:32:38,420 funziona, ma è abbastanza vicino a 0 che Sto solo andando a dire che nessun lavoro è 762 00:32:38,420 --> 00:32:40,940 richiesto se l'elenco è così piccola essere poco interessante. 763 00:32:40,940 --> 00:32:42,580 >> Ma questo caso è interessante. 764 00:32:42,580 --> 00:32:47,320 Il caso ricorsivo era il ramo di lo pseudocodice che detto altrimenti, specie 765 00:32:47,320 --> 00:32:52,000 la metà sinistra, ordinare il giusto metà, unire le due metà. 766 00:32:52,000 --> 00:32:55,530 Ora, perché fa questa espressione rappresentare questa spesa? 767 00:32:55,530 --> 00:32:58,690 Beh, T di n significa solo la tempo per ordinare n elementi. 768 00:32:58,690 --> 00:33:03,070 E poi sul lato destro del segno di uguale c'è, la T di n diviso 769 00:33:03,070 --> 00:33:06,600 da 2 si riferisce al costo di che cosa? 770 00:33:06,600 --> 00:33:07,570 Ordinamento della metà sinistra. 771 00:33:07,570 --> 00:33:10,990 L'altra T di n diviso 2 è presumibilmente riferibile al costo di 772 00:33:10,990 --> 00:33:12,390 ordinare la metà di destra. 773 00:33:12,390 --> 00:33:14,590 >> E poi il più n? 774 00:33:14,590 --> 00:33:15,420 È la fusione. 775 00:33:15,420 --> 00:33:19,120 Perché se si dispone di due liste, una di dimensione n 2 sopra e un altro di dimensione n 776 00:33:19,120 --> 00:33:22,580 più di 2, si deve toccare essenzialmente ciascuno di tali elementi, proprio come Rob 777 00:33:22,580 --> 00:33:24,990 toccato ciascuna delle coppe, e appena come abbiamo sottolineato a ciascuno dei 778 00:33:24,990 --> 00:33:26,310 volontari sul palco. 779 00:33:26,310 --> 00:33:28,790 Quindi n è la spesa di fusione. 780 00:33:28,790 --> 00:33:31,780 >> Ora, purtroppo, questa formula è anche per sé ricorsiva. 781 00:33:31,780 --> 00:33:36,390 Quindi, se posto la domanda, se n è, diciamo, 16, se ci sono 16 persone sul palco 782 00:33:36,390 --> 00:33:40,670 o 16 tazze nel video, quanti totale passi ci vuole per ordinarli 783 00:33:40,670 --> 00:33:41,550 con merge sort? 784 00:33:41,550 --> 00:33:45,790 In realtà non è una risposta ovvia, perché ora si deve ordinare di 785 00:33:45,790 --> 00:33:48,500 ricorsivamente rispondere a questa formula. 786 00:33:48,500 --> 00:33:51,190 >> Ma va bene, perché mi permetta di proporre che facciamo la seguente. 787 00:33:51,190 --> 00:33:56,670 Il tempo necessario per ordinare 16 persone o 16 tazze sta per essere rappresentati 788 00:33:56,670 --> 00:33:58,020 generalmente come T di 16. 789 00:33:58,020 --> 00:34:01,400 Ma che equivale, secondo la nostra precedente formula, 2 volte la quantità 790 00:34:01,400 --> 00:34:04,780 di tempo necessario per ordinare 8 tazze più 16. 791 00:34:04,780 --> 00:34:08,590 E ancora, più 16 è il momento di unire, e il due volte T di 8 è il 792 00:34:08,590 --> 00:34:10,790 tempo per ordinare la metà sinistra e metà a destra. 793 00:34:10,790 --> 00:34:11,989 >> Ma ancora una volta, questo non è sufficiente. 794 00:34:11,989 --> 00:34:13,210 Dobbiamo fare immersioni in profondità. 795 00:34:13,210 --> 00:34:16,409 Questo significa che dobbiamo rispondere alla domanda, che cosa è T di 8? 796 00:34:16,409 --> 00:34:19,610 Beh T di 8 è a soli 2 volte T di 4 più 8. 797 00:34:19,610 --> 00:34:20,520 Beh, cosa c'è di T di 4? 798 00:34:20,520 --> 00:34:23,780 T su 4 è a soli 2 volte T di 2 più 4. 799 00:34:23,780 --> 00:34:25,489 Beh, cosa c'è di T di 2? 800 00:34:25,489 --> 00:34:29,030 T dei 2 si trova a soli 2 volte T di 1 più 2. 801 00:34:29,030 --> 00:34:31,940 >> E ancora, siamo un po 'ottenere bloccato in questo ciclo. 802 00:34:31,940 --> 00:34:34,790 Ma è in procinto di colpire che cosiddetto caso base. 803 00:34:34,790 --> 00:34:37,310 Perché ciò che è di T 1, abbiamo pretendiamo? 804 00:34:37,310 --> 00:34:37,810 0. 805 00:34:37,810 --> 00:34:39,730 Così ora finalmente, siamo in grado di lavorare a ritroso. 806 00:34:39,730 --> 00:34:44,290 >> Se T di 1 è 0, ora posso tornare indietro di un allinearsi a questo ragazzo qui, e posso 807 00:34:44,290 --> 00:34:46,330 presa in 0 per T di 1. 808 00:34:46,330 --> 00:34:51,770 Quindi, questo significa che è uguale a 2 volte a zero, altrimenti noto come 0, più 2. 809 00:34:51,770 --> 00:34:53,739 E in modo che tutta l'espressione è 2. 810 00:34:53,739 --> 00:34:58,740 >> Ora, se prendo la T di 2, la cui risposta è 2, collegarlo alla linea di mezzo, T 811 00:34:58,740 --> 00:35:02,740 di 4, che mi dà 2 volte 2 più 4, così 8. 812 00:35:02,740 --> 00:35:07,080 Se poi mi collego a 8 al precedente linea, che mi dà 2 volte 8, 16. 813 00:35:07,080 --> 00:35:12,470 E se poi continuiamo che con la 24, aggiungendo in 16, abbiamo finalmente una 814 00:35:12,470 --> 00:35:13,820 valore di 64. 815 00:35:13,820 --> 00:35:18,480 >> Ora che in sé e per sé una sorta di parla nulla alla notazione n, la 816 00:35:18,480 --> 00:35:20,700 O grande, l'omega che abbiamo state parlando. 817 00:35:20,700 --> 00:35:24,890 Ma si scopre che il 64 è davvero 16, la dimensione dell'input, 818 00:35:24,890 --> 00:35:27,110 log base 2 di 16. 819 00:35:27,110 --> 00:35:30,200 E se questo è un po sconosciuto, basta ripenso, e si tornerà 820 00:35:30,200 --> 00:35:30,700 a voi alla fine. 821 00:35:30,700 --> 00:35:33,775 Se questo è il logaritmo in base 2, è come 2 elevato a quello che ti dà 16? 822 00:35:33,775 --> 00:35:36,380 Oh, questo è 4, quindi è 16 volte 4. 823 00:35:36,380 --> 00:35:39,380 >> E ancora, non è un grosso problema se questa è una sorta di memoria confusa ora. 824 00:35:39,380 --> 00:35:43,720 Ma per ora, prendere sulla fede che il 16 log 16 è 64. 825 00:35:43,720 --> 00:35:46,590 E così in effetti, con questa semplice sanity controllare, abbiamo confermato - 826 00:35:46,590 --> 00:35:48,250 ma non dimostrata formalmente - 827 00:35:48,250 --> 00:35:52,800 che il tempo di esecuzione di merge specie è infatti n log n. 828 00:35:52,800 --> 00:35:53,790 >> Quindi, non è male. 829 00:35:53,790 --> 00:35:57,260 E 'sicuramente meglio che la algoritmi che abbiamo visto finora, e 830 00:35:57,260 --> 00:36:00,710 è perché abbiamo sfruttato, uno, una tecnica chiamata ricorsione. 831 00:36:00,710 --> 00:36:03,880 Ma più interessante di quello che nozione di dividere e conquistare. 832 00:36:03,880 --> 00:36:07,460 Anche in questo caso, veramente settimana 0 roba che anche ora è ricorrente in un 833 00:36:07,460 --> 00:36:08,740 modo più convincente. 834 00:36:08,740 --> 00:36:11,750 >> Ora un po 'di esercizio divertente, se hai mai fatto - e probabilmente 835 00:36:11,750 --> 00:36:14,660 non avrebbe, perché sorta di normale la gente non pensa di fare questo. 836 00:36:14,660 --> 00:36:20,650 Ma se vado a google.com e se Voglio imparare qualcosa su 837 00:36:20,650 --> 00:36:22,356 ricorsione, Enter. 838 00:36:22,356 --> 00:36:25,106 839 00:36:25,106 --> 00:36:29,058 >> [Risata] 840 00:36:29,058 --> 00:36:32,030 [Altre risate] 841 00:36:32,030 --> 00:36:33,385 DAVID MALAN: scherzo di cattivo gusto lentamente diffondendo. 842 00:36:33,385 --> 00:36:34,450 [Risata] 843 00:36:34,450 --> 00:36:36,970 DAVID MALAN: Solo nel caso, è lì. 844 00:36:36,970 --> 00:36:38,710 Non ho Spell sbagliato, e c'è la battuta. 845 00:36:38,710 --> 00:36:40,810 D'accordo. 846 00:36:40,810 --> 00:36:42,950 Spiegare alla gente accanto a voi se non è abbastanza appena ancora cliccato. 847 00:36:42,950 --> 00:36:47,650 Ricorsione ma, più in generale, si riferisce al processo di una funzione chiamante 848 00:36:47,650 --> 00:36:51,430 stesso, o più in generale, dividendo un problema in qualcosa che può essere 849 00:36:51,430 --> 00:36:56,220 risolto frammentario risolvendo identico problemi di rappresentanza. 850 00:36:56,220 --> 00:36:58,400 >> Bene, vediamo di cambiare marcia solo per un momento. 851 00:36:58,400 --> 00:37:00,840 Ci piace concludere su alcuni cliffhanger, Quindi partiamo per impostare 852 00:37:00,840 --> 00:37:05,870 il palco, per alcuni minuti, su un'idea molto semplice - 853 00:37:05,870 --> 00:37:07,620 quella di scambiare due elementi, vero? 854 00:37:07,620 --> 00:37:10,040 Tutti questi algoritmi che abbiamo passato parlando degli ultimi due 855 00:37:10,040 --> 00:37:12,420 lezioni comportano una qualche sorta di swapping. 856 00:37:12,420 --> 00:37:14,630 Oggi è stato visualizzato da loro ottenendo fino dalle loro sedie e 857 00:37:14,630 --> 00:37:18,570 in giro, ma in codice, ci sarebbe basta prendere un elemento da un array 858 00:37:18,570 --> 00:37:20,370 e plop in un altro. 859 00:37:20,370 --> 00:37:21,880 >> Quindi, come possiamo fare per fare questo? 860 00:37:21,880 --> 00:37:24,850 Beh, mi permetta di andare avanti e scrivere un rapido programma qui. 861 00:37:24,850 --> 00:37:31,600 Ho intenzione di andare avanti e fare questo come il seguente. 862 00:37:31,600 --> 00:37:33,910 Chiamiamo questo - 863 00:37:33,910 --> 00:37:38,070 cosa vogliamo chiamare questo? 864 00:37:38,070 --> 00:37:38,650 >> In realtà, no. 865 00:37:38,650 --> 00:37:39,420 Permettetemi di riavvolgimento. 866 00:37:39,420 --> 00:37:41,220 Io non voglio farlo ancora Cliffhanger. 867 00:37:41,220 --> 00:37:42,270 Sarà rovinare il divertimento. 868 00:37:42,270 --> 00:37:43,600 Facciamo questo, invece. 869 00:37:43,600 --> 00:37:47,430 >> Supponiamo che io voglia scrivere un po 'di programma e che ora abbraccia questa 870 00:37:47,430 --> 00:37:48,700 idea della ricorsione. 871 00:37:48,700 --> 00:37:50,370 Ho avuto sorta di avanti di me lì. 872 00:37:50,370 --> 00:37:51,420 Io vado a fare quanto segue. 873 00:37:51,420 --> 00:38:00,220 >> In primo luogo, una rapida includono di serie io.h, così come un include di cs50.h. 874 00:38:00,220 --> 00:38:03,200 E poi ho intenzione di andare avanti e dichiarare int void main 875 00:38:03,200 --> 00:38:04,360 nel solito modo. 876 00:38:04,360 --> 00:38:07,920 Mi sono reso conto che ho erroneamente chiamata il file, in modo da vorrei solo aggiungere un'estensione. c qui così 877 00:38:07,920 --> 00:38:09,510 che siamo in grado di compilarlo correttamente. 878 00:38:09,510 --> 00:38:10,970 Avviare la funzione. 879 00:38:10,970 --> 00:38:13,290 >> E la funzione che ho voglia di scrivere, piuttosto semplicemente, è uno che chiede la 880 00:38:13,290 --> 00:38:16,210 all'utente un numero e poi aggiunge tutti i numeri tra tale 881 00:38:16,210 --> 00:38:19,920 numero e, diciamo, 0. 882 00:38:19,920 --> 00:38:22,510 Così prima ho intenzione di andare avanti e dichiarare int n. 883 00:38:22,510 --> 00:38:24,760 Poi copio un codice che abbiamo usato per un po '. 884 00:38:24,760 --> 00:38:26,660 Mentre qualcosa è vero. 885 00:38:26,660 --> 00:38:28,000 Tornerò a che in un attimo. 886 00:38:28,000 --> 00:38:29,010 >> Cosa voglio fare? 887 00:38:29,010 --> 00:38:33,460 Voglio dire printf positivo integer prego. 888 00:38:33,460 --> 00:38:36,130 E poi ho intenzione di diciamo n diventa ottenere int. 889 00:38:36,130 --> 00:38:38,800 Quindi, di nuovo, un po 'di codice standard che abbiamo usato prima. 890 00:38:38,800 --> 00:38:40,810 E ho intenzione di fare questo mentre n è minore di 1. 891 00:38:40,810 --> 00:38:44,120 Quindi questo farà sì che l'utente mi dà un numero intero positivo. 892 00:38:44,120 --> 00:38:45,490 >> E ora ho intenzione di fare quanto segue. 893 00:38:45,490 --> 00:38:51,020 Voglio sommare tutti i numeri tra 1 e ed n, o 0 e n, 894 00:38:51,020 --> 00:38:52,570 equivalentemente, per ottenere la somma totale. 895 00:38:52,570 --> 00:38:55,100 Così il grande simbolo sigma che si potrebbe ricordare. 896 00:38:55,100 --> 00:38:59,050 Quindi ho intenzione di fare questo prima convocazione una funzione chiamata sigma, 897 00:38:59,050 --> 00:39:06,030 passando a n, e quindi ho intenzione di printf dire, la risposta è proprio lì. 898 00:39:06,030 --> 00:39:08,180 >> Così, in breve, ricevo e int da parte dell'utente. 899 00:39:08,180 --> 00:39:09,280 Mi accerto che sia positivo. 900 00:39:09,280 --> 00:39:12,700 Dichiaro una variabile chiamata risposta tipo int e conservare in esso il ritorno 901 00:39:12,700 --> 00:39:15,610 valore di sigma, passando come input n. 902 00:39:15,610 --> 00:39:17,060 E poi si stampa fuori quella risposta. 903 00:39:17,060 --> 00:39:19,550 >> Purtroppo, anche se sigma suoni come qualcosa che potrebbe essere in 904 00:39:19,550 --> 00:39:24,040 il file math.h, la sua dichiarazione, in realtà non è. 905 00:39:24,040 --> 00:39:24,690 Ecco, questo è OK. 906 00:39:24,690 --> 00:39:26,170 Posso implementare questo me stesso. 907 00:39:26,170 --> 00:39:29,160 Ho intenzione di implementare una funzione chiamata sigma, e sta andando a prendere un 908 00:39:29,160 --> 00:39:29,900 parametro - 909 00:39:29,900 --> 00:39:32,100 diciamo solo chiamano m, appena quindi è diverso. 910 00:39:32,100 --> 00:39:35,910 E poi qui, sto per dire, bene, se m è minore di 1 - questo è un 911 00:39:35,910 --> 00:39:38,180 programma molto interessante. 912 00:39:38,180 --> 00:39:41,700 Quindi ho intenzione di andare avanti e immediatamente restituire 0. 913 00:39:41,700 --> 00:39:45,920 Semplicemente non ha senso sommare tutti i numeri tra 1 e m se m 914 00:39:45,920 --> 00:39:48,470 è essa stessa 0 o negativo. 915 00:39:48,470 --> 00:39:50,900 >> E poi ho intenzione di andare avanti e di farlo molto iterativo. 916 00:39:50,900 --> 00:39:53,090 Ho intenzione di fare questo genere di vecchia scuola, e ho intenzione di andare avanti 917 00:39:53,090 --> 00:39:57,150 e dire che ho intenzione di dichiarare una somma pari a 0. 918 00:39:57,150 --> 00:39:59,630 Poi ho intenzione di avere un ciclo di int - 919 00:39:59,630 --> 00:40:02,820 e lascia fare a me Tabellino nostro codice di distribuzione, in modo da avere una copia 920 00:40:02,820 --> 00:40:07,500 a casa. int i ottiene 1 a un massimo di i è minore di o uguale a m. 921 00:40:07,500 --> 00:40:09,430 i plus plus. 922 00:40:09,430 --> 00:40:11,430 E poi all'interno di questo ciclo for - 923 00:40:11,430 --> 00:40:12,440 ci siamo quasi - 924 00:40:12,440 --> 00:40:15,810 somma ottiene somma più 1. 925 00:40:15,810 --> 00:40:17,670 E poi ho intenzione di restituire la somma. 926 00:40:17,670 --> 00:40:19,420 >> Così ho fatto questo in modo rapido, piuttosto è vero. 927 00:40:19,420 --> 00:40:22,775 Ma ancora una volta, la funzione principale è abbastanza semplice, sulla base di codice che abbiamo 928 00:40:22,775 --> 00:40:23,190 scritto finora. 929 00:40:23,190 --> 00:40:25,610 Utilizza il doppio loop per ottenere un positivo int da parte dell'utente. 930 00:40:25,610 --> 00:40:29,870 Ho poi passare che int ad una nuova funzione chiamato sigma, chiamandolo, ancora una volta, n. 931 00:40:29,870 --> 00:40:33,100 E devo conservare il valore di ritorno, la risposta dalla scatola nera attualmente 932 00:40:33,100 --> 00:40:35,460 noto come sigma, in una variabile chiamata risposta. 933 00:40:35,460 --> 00:40:36,580 Poi la stampo. 934 00:40:36,580 --> 00:40:39,090 >> Se noi ora continuare la storia, come viene implementato sigma? 935 00:40:39,090 --> 00:40:40,840 Io propongo di attuare nel modo seguente. 936 00:40:40,840 --> 00:40:43,560 In primo luogo, un po 'di controllo degli errori fare in modo che l'utente non è 937 00:40:43,560 --> 00:40:46,480 scherzi con me e passando qualche valore negativo o 0. 938 00:40:46,480 --> 00:40:49,710 Poi Dichiaro una variabile chiamata riassumere e impostarlo a 0. 939 00:40:49,710 --> 00:40:55,910 >> E ora comincio a passare da i è uguale a 1 tutta la strada fino al m, 940 00:40:55,910 --> 00:41:00,130 perché voglio includere tutte le numeri da uno a m, compreso. 941 00:41:00,130 --> 00:41:04,350 E all'interno di questo ciclo for, io faccio solo somma ottiene tutto ciò che è ora, più il 942 00:41:04,350 --> 00:41:08,900 valore di i. 943 00:41:08,900 --> 00:41:10,370 Inoltre il valore di i. 944 00:41:10,370 --> 00:41:14,090 >> Per inciso, se non avete visto questo prima, c'è un po 'di zucchero sintattico 945 00:41:14,090 --> 00:41:14,870 per questa linea. 946 00:41:14,870 --> 00:41:21,120 Posso riscrivere questo come più uguale a i, solo per salvare me stesso pochi tasti 947 00:41:21,120 --> 00:41:22,570 e di guardare un po 'più fresco. 948 00:41:22,570 --> 00:41:23,140 Ma questo è tutto. 949 00:41:23,140 --> 00:41:24,660 E 'funzionalmente la stessa cosa. 950 00:41:24,660 --> 00:41:26,710 >> Sfortunatamente, questo codice di non andare a compilare ancora. 951 00:41:26,710 --> 00:41:31,600 Se corro fare sigma 0, come am Ho intenzione di ottenere sgridato? 952 00:41:31,600 --> 00:41:33,473 Che cosa sta andando a non piacere? 953 00:41:33,473 --> 00:41:35,740 >> AUDIENCE: [incomprensibile]. 954 00:41:35,740 --> 00:41:37,800 >> DAVID MALAN: Sì, non mi dichiaro la funzione di sollevamento in alto, giusto? 955 00:41:37,800 --> 00:41:40,590 C è una specie di stupido, è solo in quel fa quello che gli si dice di fare, e si 956 00:41:40,590 --> 00:41:41,880 hanno a che fare in questo ordine. 957 00:41:41,880 --> 00:41:45,910 E così, se ho colpito Inserisci qui, ho intenzione di Ottengo un avviso circa sigma implicita 958 00:41:45,910 --> 00:41:46,860 dichiarazione. 959 00:41:46,860 --> 00:41:48,120 >> Oh, non è un problema. 960 00:41:48,120 --> 00:41:50,370 Posso andare fino in cima, e posso dire, va bene, aspetta un minuto. 961 00:41:50,370 --> 00:41:54,240 Sigma è una funzione che restituisce un int e che si aspetta un 962 00:41:54,240 --> 00:41:56,620 int come input, virgola. 963 00:41:56,620 --> 00:41:59,550 Oppure potrei mettere l'intera funzione sopra principale, ma in generale, avevo 964 00:41:59,550 --> 00:42:02,260 raccomandare contro questo, perché è bello avere sempre principale nella parte superiore in modo da 965 00:42:02,260 --> 00:42:06,310 è possibile immergersi in pieno e sapere che cos'è un programma sta facendo con la lettura principale prima. 966 00:42:06,310 --> 00:42:07,930 >> Così ora mi permetta di cancellare lo schermo. 967 00:42:07,930 --> 00:42:09,330 Remake sigma 0. 968 00:42:09,330 --> 00:42:10,340 Tutto sembra controllare. 969 00:42:10,340 --> 00:42:11,970 Lasciami correre sigma 0. 970 00:42:11,970 --> 00:42:12,770 Tra positivo. 971 00:42:12,770 --> 00:42:15,580 Ho deciso di dargli il numero 3 di mantenerlo semplice. 972 00:42:15,580 --> 00:42:18,710 In modo che mi dovrebbe dare 3 più 2 più 1, quindi 6. 973 00:42:18,710 --> 00:42:20,750 Entrare, e infatti ottengo 6. 974 00:42:20,750 --> 00:42:21,820 >> Posso fare qualcosa di più grande - 975 00:42:21,820 --> 00:42:24,080 50, 12, 75. 976 00:42:24,080 --> 00:42:27,690 Proprio come una tangente, ho intenzione di fare qualcosa di ridicolo come un davvero grande 977 00:42:27,690 --> 00:42:30,375 numero, Oh, che in realtà ha funzionato - 978 00:42:30,375 --> 00:42:31,600 eh, non credo che sia giusto. 979 00:42:31,600 --> 00:42:32,810 Vediamo. 980 00:42:32,810 --> 00:42:34,060 Facciamo davvero pasticciare con essa. 981 00:42:34,060 --> 00:42:37,150 982 00:42:37,150 --> 00:42:38,400 >> Questo è un problema. 983 00:42:38,400 --> 00:42:43,180 984 00:42:43,180 --> 00:42:44,970 Che cosa sta succedendo? 985 00:42:44,970 --> 00:42:46,050 Il codice non è poi così male. 986 00:42:46,050 --> 00:42:48,470 E 'ancora lineare. 987 00:42:48,470 --> 00:42:50,810 Fischiare è un buon effetto, però. 988 00:42:50,810 --> 00:42:52,060 Che cosa sta succedendo? 989 00:42:52,060 --> 00:42:54,700 990 00:42:54,700 --> 00:42:55,620 >> Non sono sicuro se l'ho sentito. 991 00:42:55,620 --> 00:42:57,620 Così si scopre - e questo è come un a parte. 992 00:42:57,620 --> 00:42:59,400 Questo non è fondamentale per la idea della ricorsione. 993 00:42:59,400 --> 00:43:02,480 Si scopre, perché sto cercando di rappresentare un numero così grande, più 994 00:43:02,480 --> 00:43:06,980 probabilmente si tratta di essere male interpretato da C come un numero non positivo, 995 00:43:06,980 --> 00:43:09,980 ma numero negativo. 996 00:43:09,980 --> 00:43:12,690 >> Non abbiamo parlato di questo, ma è che vi sono numeri negativi 997 00:43:12,690 --> 00:43:14,210 nel mondo in aggiunta ai numeri positivi. 998 00:43:14,210 --> 00:43:16,290 E il mezzo con cui è possibile rappresentare un numero negativo 999 00:43:16,290 --> 00:43:19,530 è essenzialmente, si utilizza uno po 'speciale per indicare 1000 00:43:19,530 --> 00:43:20,400 positivo nel negativo. 1001 00:43:20,400 --> 00:43:22,950 E 'un po' più complesso di così, ma questa è l'idea di base. 1002 00:43:22,950 --> 00:43:26,740 >> Così, purtroppo, se C è fonte di confusione uno di questi bit come in realtà significa, 1003 00:43:26,740 --> 00:43:30,790 oh, questo è un numero negativo, il mio ciclo qui, per esempio, è in realtà mai 1004 00:43:30,790 --> 00:43:31,740 andando a terminare. 1005 00:43:31,740 --> 00:43:33,850 Quindi, se io fossi davvero qualcosa di stampa ancora e ancora, ci sarebbe 1006 00:43:33,850 --> 00:43:34,650 vedere un bel po '. 1007 00:43:34,650 --> 00:43:36,220 Ma ancora una volta, questo è oltre il punto. 1008 00:43:36,220 --> 00:43:38,590 Questo è in realtà solo una sorta di curiosità intellettuale che verremo 1009 00:43:38,590 --> 00:43:39,550 tornare alla fine. 1010 00:43:39,550 --> 00:43:43,400 Ma per ora, questa è una corretta realizzazione se si assume che il 1011 00:43:43,400 --> 00:43:45,970 utente fornirà int che si adattano all'interno di int. 1012 00:43:45,970 --> 00:43:49,370 >> Ma io sostengo che questo codice, francamente, si potrebbe fare molto di più semplice. 1013 00:43:49,370 --> 00:43:54,060 Se l'obiettivo a portata di mano è quello di prendere un numero come m e sommare tutte le 1014 00:43:54,060 --> 00:43:59,510 numeri tra esso e 1, o viceversa tra 1 e, rivendico 1015 00:43:59,510 --> 00:44:03,380 che posso prendere in prestito questa idea che si fondono sorta aveva, che stava prendendo un problema 1016 00:44:03,380 --> 00:44:05,660 di queste dimensioni e dividendola in qualcosa di più piccolo. 1017 00:44:05,660 --> 00:44:09,875 Forse non la metà, ma più piccolo, ma rappresentativo della stessa. 1018 00:44:09,875 --> 00:44:12,130 Stessa idea, ma un problema minore. 1019 00:44:12,130 --> 00:44:15,470 >> Quindi sono in realtà - mi permetta di salvare questo file con un numero di versione diversa. 1020 00:44:15,470 --> 00:44:17,670 Chiameremo questa versione 1 invece di 0. 1021 00:44:17,670 --> 00:44:20,790 E mi sostenere che io in realtà può reimplementare questo in questa sorta di 1022 00:44:20,790 --> 00:44:22,160 mind-bending modo. 1023 00:44:22,160 --> 00:44:23,710 >> Ho intenzione di lasciare una parte di esso da solo. 1024 00:44:23,710 --> 00:44:27,710 Sto per dire se m è minore di o addirittura uguale a 0 - 1025 00:44:27,710 --> 00:44:29,280 Sto solo andando a essere un po ' più anale questa volta 1026 00:44:29,280 --> 00:44:30,520 con il mio controllo degli errori - 1027 00:44:30,520 --> 00:44:33,190 Ho intenzione di andare avanti e di restituire 0. 1028 00:44:33,190 --> 00:44:34,490 Questo è arbitraria. 1029 00:44:34,490 --> 00:44:37,500 Sto semplicemente decidendo se l'utente mi dà un numero negativo, io sono 1030 00:44:37,500 --> 00:44:41,490 ritorno 0, e che avrebbero dovuto leggere la documentazione più da vicino. 1031 00:44:41,490 --> 00:44:42,170 >> Altro - 1032 00:44:42,170 --> 00:44:44,070 accorgo di quello che ho intenzione di fare. 1033 00:44:44,070 --> 00:44:49,260 Altra cosa ho intenzione di tornare m plus - 1034 00:44:49,260 --> 00:44:51,010 ciò che è sigma di m? 1035 00:44:51,010 --> 00:44:56,710 Beh, sigma di m più m meno 1, più m meno 2, più m meno 3. 1036 00:44:56,710 --> 00:44:58,030 Non voglio scrivere tutto questo fuori. 1037 00:44:58,030 --> 00:44:59,120 Perché non solo punt? 1038 00:44:59,120 --> 00:45:05,080 Ricorsivamente definirmi con un po ' problema più piccolo, punto e virgola, 1039 00:45:05,080 --> 00:45:06,840 e chiamare un giorno? 1040 00:45:06,840 --> 00:45:07,040 >> Giusto? 1041 00:45:07,040 --> 00:45:10,980 Ora, anche qui, si potrebbe sentire o preoccuparsi che questo è un ciclo infinito che io sono 1042 00:45:10,980 --> 00:45:15,450 indurre, per cui io sono l'attuazione sigma chiamando il sigma. 1043 00:45:15,450 --> 00:45:20,342 Ma questo è perfettamente OK, perché io pensiero avanti un aggiunto che le linee? 1044 00:45:20,342 --> 00:45:22,600 >> AUDIENCE: [incomprensibile]. 1045 00:45:22,600 --> 00:45:25,430 >> DAVID MALAN: da 23 a 26, che è la mia se la condizione. 1046 00:45:25,430 --> 00:45:28,390 Perché ciò che è bello circa la sottrazione qui, perché continuo 1047 00:45:28,390 --> 00:45:31,180 distribuendo sigma problemi più piccoli, più piccoli problemi, più piccolo - non è 1048 00:45:31,180 --> 00:45:31,870 la metà. 1049 00:45:31,870 --> 00:45:34,380 E 'solo un passo più piccolo bambino, ma va bene così. 1050 00:45:34,380 --> 00:45:38,050 Perché alla fine, lavoreremo la nostra strada fino a 1 o 0. 1051 00:45:38,050 --> 00:45:41,630 E una volta che abbiamo raggiunto 0, sigma non è andando a chiamare più se stessa. 1052 00:45:41,630 --> 00:45:43,590 E 'intenzione di tornare immediatamente 0. 1053 00:45:43,590 --> 00:45:47,960 >> Così l'effetto, se si ordina di vento questo nella tua mente, è quello di aggiungere M PLUS 1054 00:45:47,960 --> 00:45:52,740 m meno 1, più m meno 2, più m meno 3, più punti, punto, punto, m meno 1055 00:45:52,740 --> 00:45:57,820 m, alla fine ti dà 0, e la effetto è in ultima analisi, per aggiungere tutti 1056 00:45:57,820 --> 00:45:59,070 queste cose insieme. 1057 00:45:59,070 --> 00:46:02,380 Quindi noi non abbiamo, con la ricorsione, risolto il problema che ci 1058 00:46:02,380 --> 00:46:03,470 non potrebbe risolvere prima. 1059 00:46:03,470 --> 00:46:06,840 Anzi, versione 0 di questo, e ogni problema fino ad oggi, è stato risolvibile 1060 00:46:06,840 --> 00:46:09,980 con il solo utilizzo di loop o mentre loop o costrutti simili. 1061 00:46:09,980 --> 00:46:13,150 >> Ma ricorsione, oserei dire, ci dà un modo diverso di pensare 1062 00:46:13,150 --> 00:46:17,010 problemi, per cui se si può prendere un problema, dividerlo da qualcosa 1063 00:46:17,010 --> 00:46:22,340 piuttosto grande in qualcosa alquanto più piccolo, sostengo che possiamo risolverli 1064 00:46:22,340 --> 00:46:26,040 forse un po 'più elegante, in termini del disegno, con meno codice, 1065 00:46:26,040 --> 00:46:30,980 e forse anche risolvere i problemi che si essere più difficile, come vedremo alla fine 1066 00:46:30,980 --> 00:46:33,280 vedere, la soluzione puramente iterativo. 1067 00:46:33,280 --> 00:46:35,980 >> Ma il colpo di scena che ho fatto vuole lasciare a noi su questo stato. 1068 00:46:35,980 --> 00:46:40,720 Lasciami andare avanti e aprire un file da - 1069 00:46:40,720 --> 00:46:44,300 in realtà, lasciami andare e farlo in fretta. 1070 00:46:44,300 --> 00:46:46,875 Lasciami andare avanti e propongo il seguente. 1071 00:46:46,875 --> 00:46:51,160 1072 00:46:51,160 --> 00:46:54,785 Tra il codice di oggi è questo file qui. 1073 00:46:54,785 --> 00:47:01,090 1074 00:47:01,090 --> 00:47:03,050 Questo qui, noswap. 1075 00:47:03,050 --> 00:47:06,260 >> Quindi questo è un piccolo programma stupido che Ho scatenato che afferma di fare 1076 00:47:06,260 --> 00:47:06,940 il seguente. 1077 00:47:06,940 --> 00:47:10,140 Nel principale, dichiara in primo luogo un int chiamati x e lo assegna 1078 00:47:10,140 --> 00:47:11,100 il valore di 1. 1079 00:47:11,100 --> 00:47:13,520 Poi si dichiara un y int e assegna il valore 2. 1080 00:47:13,520 --> 00:47:15,310 Poi esso stampa quello che x e y è. 1081 00:47:15,310 --> 00:47:17,781 Poi si dice, lo swapping, puntini puntini. 1082 00:47:17,781 --> 00:47:21,670 >> Poi dice di chiamare una funzione chiamato swap, passando x e 1083 00:47:21,670 --> 00:47:24,290 y, la cui idea è che auspicabilmente x e y torneranno 1084 00:47:24,290 --> 00:47:25,620 differente, il contrario. 1085 00:47:25,620 --> 00:47:27,110 Poi pretendono scambiato! 1086 00:47:27,110 --> 00:47:28,420 con un punto esclamativo. 1087 00:47:28,420 --> 00:47:30,190 Poi esso stampa xe y. 1088 00:47:30,190 --> 00:47:33,480 >> Ma si scopre che proprio questo semplice dimostrazione giù 1089 00:47:33,480 --> 00:47:35,570 qui è in realtà buggy. 1090 00:47:35,570 --> 00:47:38,870 Anche se sto dichiarando una temporanea variabile e temporaneamente mettere un a 1091 00:47:38,870 --> 00:47:42,010 esso, allora sono riassegnando un valore di b - 1092 00:47:42,010 --> 00:47:45,080 che si sente ragionevole, perché ho salvato una copia di un in temperatura. 1093 00:47:45,080 --> 00:47:48,410 Poi mi aggiorno b deve essere uguale tutto ciò che era in temperatura. 1094 00:47:48,410 --> 00:47:51,610 Questa sorta di gioco delle tre carte di spostamento di un in b e b in una utilizzando questo 1095 00:47:51,610 --> 00:47:54,360 mezzo-uomo di nome Temp sente perfettamente ragionevole. 1096 00:47:54,360 --> 00:47:57,270 >> Ma io sostengo che quando eseguo questo codice, come farò ora - 1097 00:47:57,270 --> 00:47:59,490 mi permetta di andare avanti e di incollarlo in qui. 1098 00:47:59,490 --> 00:48:01,995 Chiamerò questo noswap.c. 1099 00:48:01,995 --> 00:48:05,630 E come suggerisce il nome, questo non è sarà un programma corretto. 1100 00:48:05,630 --> 00:48:09,460 Fai noswap. / No swap. 1101 00:48:09,460 --> 00:48:12,110 x è 1, y 2, swapping, scambiato. 1102 00:48:12,110 --> 00:48:14,220 x è 1, y è 2. 1103 00:48:14,220 --> 00:48:16,920 Questo è fondamentalmente sbagliato, anche se questo sembra perfettamente 1104 00:48:16,920 --> 00:48:17,730 ragionevole per me. 1105 00:48:17,730 --> 00:48:21,330 E c'è una ragione, ma non siamo intenzione di rivelare il motivo appena ancora. 1106 00:48:21,330 --> 00:48:24,610 >> Per ora il secondo colpo di scena che volevo lasciarvi con questo, un 1107 00:48:24,610 --> 00:48:27,120 annuncio di sorta sui codici promozionali. 1108 00:48:27,120 --> 00:48:31,590 La nostra innovazione con giorni di ritardo quest'anno ha provocato un numero non banale 1109 00:48:31,590 --> 00:48:33,830 delle domande, che era non è nostra intenzione. 1110 00:48:33,830 --> 00:48:36,590 L'intenzione di questi codici promozionali, per cui se fai parte del problema 1111 00:48:36,590 --> 00:48:39,850 set iniziale, ottenendo in tal modo un giorno in più, era davvero aiutare voi aiuto ragazzi 1112 00:48:39,850 --> 00:48:42,420 te rapido avvio, specie di incentivare da voi. 1113 00:48:42,420 --> 00:48:44,880 Ci aiuta a distribuire il carico tra orario di ufficio meglio così che 1114 00:48:44,880 --> 00:48:45,740 è una specie di win-win. 1115 00:48:45,740 --> 00:48:48,860 >> Purtroppo, credo che le mie istruzioni non sono stati, ad oggi, molto chiaro, in modo da 1116 00:48:48,860 --> 00:48:52,230 Sono tornato in questo fine settimana e aggiornato le specifiche in grande, testo ardita per 1117 00:48:52,230 --> 00:48:53,600 spiegare proiettili come questi. 1118 00:48:53,600 --> 00:48:56,900 E proprio per dirlo più pubblicamente, da predefinite, insiemi di problemi sono dovuti Giovedi 1119 00:48:56,900 --> 00:48:58,400 a mezzogiorno, per il programma. 1120 00:48:58,400 --> 00:49:02,030 Se si inizia presto, finendo parte di il problema posto da Mercoledì alle 12:00 1121 00:49:02,030 --> 00:49:05,170 PM, la parte che si riferisce a un coupon codice, l'idea è che si può estendere 1122 00:49:05,170 --> 00:49:07,710 il vostro termine per la P impostato fino a Venerdì. 1123 00:49:07,710 --> 00:49:10,890 Cioè, un po 'fuori una piccola parte del P impostate rispetto a ciò che è tipicamente la 1124 00:49:10,890 --> 00:49:13,200 grande problema, e si acquista voi stessi un giorno in più. 1125 00:49:13,200 --> 00:49:15,190 Ancora una volta, si ottiene pensando il problema insieme, si ottiene per 1126 00:49:15,190 --> 00:49:16,380 orario di ufficio prima. 1127 00:49:16,380 --> 00:49:20,670 Ma il problema codice coupon è ancora richiesto, anche se non si sottopone. 1128 00:49:20,670 --> 00:49:23,340 >> Ma più convincente è questa. 1129 00:49:23,340 --> 00:49:26,520 (STAGE WHISPER) E quelle persone lasciando sono presto ti pentirai. 1130 00:49:26,520 --> 00:49:28,620 Come sono le persone sul balcone. 1131 00:49:28,620 --> 00:49:32,510 Mi scuso in anticipo per la gente su balcone per ragioni che saranno 1132 00:49:32,510 --> 00:49:33,920 cancellare in un attimo. 1133 00:49:33,920 --> 00:49:37,050 >> Così abbiamo la fortuna di avere uno dei Ex capo compagni di insegnamento di CS50 a 1134 00:49:37,050 --> 00:49:39,302 una società denominata dropbox.com. 1135 00:49:39,302 --> 00:49:45,500 Essi hanno molto generosamente donato un codice coupon qui per questo molto spazio, 1136 00:49:45,500 --> 00:49:48,180 che è su dal solite 2 gigabyte. 1137 00:49:48,180 --> 00:49:51,740 Quindi quello che ho pensato che avremmo fatto in questo nota finale è fare un po 'di un giveaway, 1138 00:49:51,740 --> 00:49:55,380 per cui in un momento, ci rivelerà il vincitore e chi ha una cedola 1139 00:49:55,380 --> 00:49:57,980 codice che è possibile quindi andare al loro sito web, digitarlo nella, e voilà, ottenere un 1140 00:49:57,980 --> 00:50:01,370 molto di più per il vostro spazio Dropbox apparecchio e per i tuoi file personali. 1141 00:50:01,370 --> 00:50:05,690 >> E in primo luogo, che vorrebbe partecipare in questo disegno? 1142 00:50:05,690 --> 00:50:09,630 OK, ora che lo rende ancora più divertente. 1143 00:50:09,630 --> 00:50:14,010 La persona che riceve questo 25 gigabyte codice coupon - che è molto 1144 00:50:14,010 --> 00:50:16,150 più convincente rispetto alla fine degli anni giorni ormai, forse - 1145 00:50:16,150 --> 00:50:20,620 è colui che è seduto sulla cima di un cuscino sotto cui c'è 1146 00:50:20,620 --> 00:50:21,620 che il codice coupon. 1147 00:50:21,620 --> 00:50:23,480 Ora puoi guardare sotto il vostro cuscino. 1148 00:50:23,480 --> 00:50:28,710 1149 00:50:28,710 --> 00:50:29,680 >> [RIPRODUZIONE VIDEO] 1150 00:50:29,680 --> 00:50:31,620 >> -Uno, due, tre. 1151 00:50:31,620 --> 00:50:35,015 >> [GRIDA] 1152 00:50:35,015 --> 00:50:35,985 >> -È possibile ottenere una macchina! 1153 00:50:35,985 --> 00:50:36,670 Si ottiene una macchina! 1154 00:50:36,670 --> 00:50:37,970 >> DAVID MALAN: Vedremo si il Mercoledì. 1155 00:50:37,970 --> 00:50:38,904 >> -È possibile ottenere una macchina! 1156 00:50:38,904 --> 00:50:39,371 Si ottiene una macchina! 1157 00:50:39,371 --> 00:50:40,305 Si ottiene una macchina! 1158 00:50:40,305 --> 00:50:41,706 Si ottiene una macchina! 1159 00:50:41,706 --> 00:50:43,107 Si ottiene una macchina! 1160 00:50:43,107 --> 00:50:45,530 >> DAVID MALAN: persone Balcone, vieni qui al fronte, 1161 00:50:45,530 --> 00:50:46,866 dove abbiamo comparse. 1162 00:50:46,866 --> 00:50:50,282 >> -Ognuno ottiene una macchina! 1163 00:50:50,282 --> 00:50:52,234 Ognuno ottiene una macchina! 1164 00:50:52,234 --> 00:50:52,722 >> [FINE RIPRODUZIONE VIDEO] 1165 00:50:52,722 --> 00:50:54,590 >> NARRATORE: Al prossimo CS50 - 1166 00:50:54,590 --> 00:51:00,374 >> SPEAKER 5: Oh my gosh cribbio cribbio cribbio cribbio cribbio cribbio cribbio cribbio cribbio - 1167 00:51:00,374 --> 00:51:02,106 >> [GIOCHI Ukelele]