1 00:00:00,000 --> 00:00:11,100 >> [MUSIC PLAYING] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. MALAN: Va bene. 3 00:00:11,490 --> 00:00:12,170 Quindi bentornato. 4 00:00:12,170 --> 00:00:15,180 Questo è CS50, ed è il la fine della terza settimana. 5 00:00:15,180 --> 00:00:17,770 >> Quindi richiamare nelle ultime settimane, abbiamo passato un po 'di 6 00:00:17,770 --> 00:00:20,820 tempo su C, sulla programmazione, sulla sintassi. 7 00:00:20,820 --> 00:00:24,680 Ed è abbastanza normale, se siete ancora alle prese con il problema di Set 2, per essere 8 00:00:24,680 --> 00:00:25,950 sbattere la testa contro il muro. 9 00:00:25,950 --> 00:00:28,310 Si tratta di messaggi di errore criptico-looking e gli insetti che si 10 00:00:28,310 --> 00:00:29,220 non riesco a inseguire. 11 00:00:29,220 --> 00:00:32,310 Perché, stare tranquilli, che in appena un tempo qualche settimana ti guarderai indietro 12 00:00:32,310 --> 00:00:35,930 cose come Cesare, e [? V-genair,?] forse anche Crack, e 13 00:00:35,930 --> 00:00:40,050 rende conto fino a che punto siete arrivati in un breve periodo di tempo. 14 00:00:40,050 --> 00:00:43,670 Quindi, se questo è di consolazione, appendere in là, per ora. 15 00:00:43,670 --> 00:00:46,610 >> Oggi, però, cominciamo a transizione a cose livello superiore. 16 00:00:46,610 --> 00:00:49,820 E cominciamo a dare per scontato che voi sapete come programmare, o 17 00:00:49,820 --> 00:00:52,090 almeno gli inizi di che il livello di comfort. 18 00:00:52,090 --> 00:00:56,520 E cominceremo a considerare come possiamo andare sulla progettazione di programmi di più 19 00:00:56,520 --> 00:00:57,440 efficacemente. 20 00:00:57,440 --> 00:01:01,090 Come possiamo fare per ottimizzare l' efficienza dei nostri algoritmi, e 21 00:01:01,090 --> 00:01:03,110 in genere la soluzione più problemi interessanti. 22 00:01:03,110 --> 00:01:06,850 E cominciando a dare per scontato che, se volessimo, potremmo codificare fino qualsiasi 23 00:01:06,850 --> 00:01:08,350 degli esempi che abbiamo in mente. 24 00:01:08,350 --> 00:01:11,430 Così oggi, non toccare la tastiera per qualsiasi forma di codice. 25 00:01:11,430 --> 00:01:15,150 Sarà livello molto più alto, e in ultima analisi, di problem-solving. 26 00:01:15,150 --> 00:01:20,490 >> Quindi, per arrivare a quel punto, mi propongo che le seguenti sette 27 00:01:20,490 --> 00:01:24,290 rettangoli rappresentano sette porte, dietro che sono un insieme di 28 00:01:24,290 --> 00:01:26,340 i numeri, tra i quali è il numero 50. 29 00:01:26,340 --> 00:01:30,470 Lasciatemi proietto questo su questo schermo anche qui. 30 00:01:30,470 --> 00:01:36,770 E proponiamo che abbiamo bisogno di un volontario per aiutarmi a trovare un numero davanti 31 00:01:36,770 --> 00:01:38,140 internet qui per vedere. 32 00:01:38,140 --> 00:01:40,755 Vieni su, in rosa. 33 00:01:40,755 --> 00:01:43,050 D'accordo. 34 00:01:43,050 --> 00:01:43,930 Qual è il tuo nome? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [incomprensibile] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. MALAN: Sorry? 37 00:01:45,170 --> 00:01:45,860 >> JENNIFER: Jennifer. 38 00:01:45,860 --> 00:01:46,390 >> DAVID J. MALAN: Jennifer. 39 00:01:46,390 --> 00:01:46,980 D'accordo, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Lieto di vederla. 41 00:01:47,630 --> 00:01:48,370 Andiamo su. 42 00:01:48,370 --> 00:01:52,430 Quindi questi qui sono sette porte, e cosa Mi piacerebbe che tu faccia per noi qui, 43 00:01:52,430 --> 00:01:56,560 di fronte a tutti i tuoi compagni di classe, ci si trova il numero, 50. 44 00:01:56,560 --> 00:02:00,860 Per trovare un numero, è possibile sbirciare dietro una di queste porte semplicemente toccando 45 00:02:00,860 --> 00:02:03,030 su una delle porte, e rivelerà il suo numero. 46 00:02:03,030 --> 00:02:06,080 E vediamo quanto velocemente si riesce a trovare noi il numero, il 50. 47 00:02:06,080 --> 00:02:09,979 48 00:02:09,979 --> 00:02:11,229 >> 15. 49 00:02:11,229 --> 00:02:13,110 50 00:02:13,110 --> 00:02:14,360 16. 51 00:02:14,360 --> 00:02:16,270 52 00:02:16,270 --> 00:02:16,530 50. 53 00:02:16,530 --> 00:02:17,350 Ben fatto. 54 00:02:17,350 --> 00:02:18,040 D'accordo. 55 00:02:18,040 --> 00:02:19,906 Applauso per Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [Applausi] 57 00:02:21,530 --> 00:02:22,320 >> D'accordo. 58 00:02:22,320 --> 00:02:25,254 Così che cosa è stata la tua strategia per trovando il numero, 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Uhm, ho pensato che forse se - 60 00:02:27,222 --> 00:02:27,714 [Incomprensibile] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. MALAN: Oh. 62 00:02:28,206 --> 00:02:29,630 Dategli un secondo. 63 00:02:29,630 --> 00:02:32,420 Quindi è stata la tua strategia per trovando il numero, 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: Così ho appena iniziare a cominciando a vedere ciò che il primo numero 65 00:02:34,760 --> 00:02:38,590 ero, e poi ho pensato, forse se stanno ordinati, mi limiterò a continuare 66 00:02:38,590 --> 00:02:39,970 toccando più in alto? 67 00:02:39,970 --> 00:02:40,140 >> DAVID J. MALAN: OK. 68 00:02:40,140 --> 00:02:42,910 E ci sembra di aver trovato che essere il caso. 69 00:02:42,910 --> 00:02:45,670 Anche se, cerchiamo di staccare gli strati solo un po ', e si vuole andare 70 00:02:45,670 --> 00:02:47,640 avanti e rivelare le altre porte avresti potuto scegliere? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: Oh, cara. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. MALAN: Ah. 74 00:02:53,128 --> 00:02:54,280 >> JENNIFER: Così ho semplicemente fortunato. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. MALAN: Così avete ottenuto fortunato. 76 00:02:55,270 --> 00:02:55,710 D'accordo. 77 00:02:55,710 --> 00:02:56,795 Quindi, non è male. 78 00:02:56,795 --> 00:02:58,750 Ma questo è un interessante intuizione, giusto? 79 00:02:58,750 --> 00:03:01,870 Se si presume, e avete fatto ottenere, in effetti, un po 'fortunati lì. 80 00:03:01,870 --> 00:03:05,350 Ma se si presume che i numeri erano allineati, si può essere più precisi 81 00:03:05,350 --> 00:03:08,750 di come tale influenzato il tuo comportamento? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Quindi, se sono stati ordinati, ho pensato che forse più piccolo al più grande. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. MALAN: OK. 84 00:03:11,970 --> 00:03:15,260 >> JENNIFER: O se questo ha finito per essere davvero grande, quindi più grande al più piccolo. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. MALAN: OK. 86 00:03:15,540 --> 00:03:18,170 Così grande al più piccolo, o più piccolo al più grande. 87 00:03:18,170 --> 00:03:21,990 Ma lasciate che propongo, si supponga di avere ottenuto sfortunato, e supporre che essi 88 00:03:21,990 --> 00:03:26,840 non sono stati, infatti, selezionati, quanti di quelle porte hai provato a sbirciare 89 00:03:26,840 --> 00:03:28,590 dietro in quel caso peggiore? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Tutti. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. MALAN: Tutti. 92 00:03:30,420 --> 00:03:31,740 Quindi cerchiamo di generalizzare che come n. 93 00:03:31,740 --> 00:03:34,790 Ci capita di essere 7, ma cerchiamo di più in genere ci dicono di N. porte sul 94 00:03:34,790 --> 00:03:35,650 schermata qui. 95 00:03:35,650 --> 00:03:40,110 Quindi, nel caso peggiore, si avrebbe di guardare dietro sette porte, o porte n. 96 00:03:40,110 --> 00:03:44,140 E così questo è davvero, è un po 'di fortuna oggi, ma è davvero un lineare 97 00:03:44,140 --> 00:03:46,440 algoritmo di sorta, anche se si erano tipo di saltare in giro. 98 00:03:46,440 --> 00:03:47,080 E 'giusto? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Già. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. MALAN: Beh, fammi vedere se il vostro cambiamenti di strategia, se ci mi muovo 101 00:03:50,000 --> 00:03:52,190 il nostro secondo esempio qui con 7 diverse porte. 102 00:03:52,190 --> 00:03:55,240 Stessi numeri, ma questo volta che sono allineati. 103 00:03:55,240 --> 00:03:58,350 Qual è la vostra strategia qui sta per essere, cercando di mettere fuori di testa che cosa 104 00:03:58,350 --> 00:03:59,310 gli altri numeri erano - 105 00:03:59,310 --> 00:03:59,930 >> JENNIFER: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. MALAN: - prima? 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Partiamo con il primo. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. MALAN: Va bene. 109 00:04:03,540 --> 00:04:05,190 Iniziare con la prima. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 Ora dove hai intenzione di andare, e perché? 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4 è davvero piccolo. 113 00:04:10,040 --> 00:04:12,500 Quindi, se sono specie forse più piccolo al più grande, dovrebbe 114 00:04:12,500 --> 00:04:13,290 essere il doppio, e -. 115 00:04:13,290 --> 00:04:13,670 >> DAVID J. MALAN: OK. 116 00:04:13,670 --> 00:04:15,990 Vediamo, che ne pensi? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Prova l'ultimo. 118 00:04:19,050 --> 00:04:19,500 Nizza. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. MALAN: Molto ben fatto. 120 00:04:20,880 --> 00:04:21,860 D'accordo. 121 00:04:21,860 --> 00:04:23,010 >> [Applausi] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. MALAN: OK. 123 00:04:24,310 --> 00:04:26,790 Quindi, si sta effettivamente facendo questo orribilmente, perché sei 124 00:04:26,790 --> 00:04:27,700 facendo molto bene. 125 00:04:27,700 --> 00:04:31,150 Il che ci lascia incapaci di fare alcuni punti. 126 00:04:31,150 --> 00:04:32,565 Allora proviamo a rotolare di nuovo qui. 127 00:04:32,565 --> 00:04:34,560 >> JENNIFER: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. MALAN: molto bene fatto, comunque. 129 00:04:35,980 --> 00:04:39,060 Quindi hai iniziato all'inizio, hai visto che era 4, poi si 130 00:04:39,060 --> 00:04:40,240 spostato alla fine. 131 00:04:40,240 --> 00:04:42,320 Ma supponiamo che non hai avuto fortuna lì, e supponiamo 50 132 00:04:42,320 --> 00:04:42,890 era da qualche altra parte. 133 00:04:42,890 --> 00:04:46,190 Che la tua terza fase sono stati? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: torna all'inizio. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. MALAN: Tornate all'inizio. 136 00:04:48,320 --> 00:04:51,320 OK, così avresti toccato questo porta, che era 8. 137 00:04:51,320 --> 00:04:51,660 D'accordo. 138 00:04:51,660 --> 00:04:52,650 Quindi questo non è 50. 139 00:04:52,650 --> 00:04:55,380 Dove avresti guardato il prossimo? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: Se non l'ho fatto sanno hanno risolto. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. MALAN: Corretto. 142 00:04:57,005 --> 00:04:58,490 Beh, se lo sapessi sono stati ordinati - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Oh, lo sapevo, sì. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. MALAN: - Ma non hai sapere dove 50 era ancora? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Basta andare avanti. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. MALAN: Va bene. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Continua ad andare. 149 00:05:03,800 --> 00:05:05,270 OK, che posso lavorare. 150 00:05:05,270 --> 00:05:05,610 >> JENNIFER: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. MALAN: Ora, se sei solo Continueremo a correre, qual è la tua 152 00:05:07,210 --> 00:05:09,680 algoritmo devolvendo sostenuto in. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: Il lineare -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. MALAN: E 'tipo di lineare. 155 00:05:11,820 --> 00:05:13,480 Ma lasciate che propongo, lasciare mi ha messo sul posto. 156 00:05:13,480 --> 00:05:14,900 Permettetemi di aggiornare la pagina. 157 00:05:14,900 --> 00:05:17,120 stesso numero, stessa disposizione, porte stesse. 158 00:05:17,120 --> 00:05:21,350 Ma ripensare a quel primo giorno in classe quando abbiamo strappato una rubrica telefonica in 159 00:05:21,350 --> 00:05:25,480 la metà, più o meno, e quello che era la nostra strategia di là? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Iniziare a metà. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. MALAN: OK. 162 00:05:26,690 --> 00:05:27,610 Così inizia a metà. 163 00:05:27,610 --> 00:05:28,790 Quindi andiamo avanti e simulare quello. 164 00:05:28,790 --> 00:05:30,720 Iniziare al centro di rivelando che porta. 165 00:05:30,720 --> 00:05:31,660 Quindi il numero 16. 166 00:05:31,660 --> 00:05:35,290 Quindi quale sarebbe il forte ragazzo hanno fatto, che strappò il libro di telefono a metà, 167 00:05:35,290 --> 00:05:38,450 per arrivare al prossimo indovinare? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Andate in questo mezzo. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. MALAN: E perché a destra? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: se fossero una sorta di piccolo al più grande, poi il 50 dovrebbe essere 171 00:05:43,900 --> 00:05:44,720 a quella estremità. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. MALAN: Buono. 173 00:05:44,920 --> 00:05:45,390 Assolutamente ragionevole. 174 00:05:45,390 --> 00:05:48,380 Così come una rubrica telefonica, si va al destra rispetto alla sinistra, ma qui 175 00:05:48,380 --> 00:05:49,500 è il takeaway chiave. 176 00:05:49,500 --> 00:05:53,930 Ora è possibile buttare via, o strappare, metà di questo problema, non lasciando 177 00:05:53,930 --> 00:05:55,970 con 7 porte, ma in realtà con solo 3. 178 00:05:55,970 --> 00:05:57,870 Che è circa la metà del dimensione del problema. 179 00:05:57,870 --> 00:05:58,350 D'accordo. 180 00:05:58,350 --> 00:06:01,890 Così ora quello che si avrebbe fatto dopo si va a destra? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: Quindi 16 è ancora piuttosto piccolo, rispetto al 50, quindi forse ci proverò, 182 00:06:05,870 --> 00:06:06,700 come, questa. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. MALAN: Va bene. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Bene, così ora qual è la tua l'istinto che ti dice? 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: posso buttare via questo e poi basta - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. MALAN: OK. 188 00:06:12,360 --> 00:06:14,212 Buono, si può buttare via la metà sinistra. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - scegliere questo. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. MALAN: E la destra. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Già. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. MALAN: Quindi, anche se è difficile di vedere, forse, quando c'è solo 193 00:06:17,820 --> 00:06:21,320 7 porte, pensare, ora, la consistenza del 194 00:06:21,320 --> 00:06:22,620 algoritmo appena applicato. 195 00:06:22,620 --> 00:06:24,510 Nel caso precedente, l'avete fatto fortunato, che era fantastico. 196 00:06:24,510 --> 00:06:26,540 Ma hai fatto usare una euristica, Direi. 197 00:06:26,540 --> 00:06:29,150 Hai usato una sorta di tuo istinto, e saperlo allineati, se è abbastanza 198 00:06:29,150 --> 00:06:31,600 piccola all'inizio, ovviamente, abbiamo avuto modo di andare più a destra. 199 00:06:31,600 --> 00:06:34,990 Ma in un certo senso, è stato fortunato, perché forse questo era il numero 100, 200 00:06:34,990 --> 00:06:36,220 e forse 50 era più al centro. 201 00:06:36,220 --> 00:06:37,910 Forse 50 era ancora qui. 202 00:06:37,910 --> 00:06:40,960 >> Ma quello che ha fatto un po 'diverso questa volta è stato, hai fatto la stessa cosa 203 00:06:40,960 --> 00:06:42,150 ancora e ancora. 204 00:06:42,150 --> 00:06:45,310 E direi che quello che hai appena ha, seppur influenzato dal telefono 205 00:06:45,310 --> 00:06:48,100 esempio libro, è qualcosa di molto più algoritmico, e molto 206 00:06:48,100 --> 00:06:49,930 meno speciale carter. 207 00:06:49,930 --> 00:06:51,620 Molto meno istintiva. 208 00:06:51,620 --> 00:06:57,160 Così, alla fine della giornata, come sarebbe descrivi l'efficienza del 209 00:06:57,160 --> 00:07:00,530 primo algoritmo, dove si è andato sinistra a destra, rispetto al 210 00:07:00,530 --> 00:07:03,430 secondo algoritmo qui? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: questo dovrebbe, come, forse dimezzare il tempo, o anche di più, sì. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. MALAN: OK, forse anche di più. 213 00:07:07,320 --> 00:07:10,150 Cerchiamo di spingere un po 'più difficile su questo. 214 00:07:10,150 --> 00:07:13,030 Ciò che davvero, se continuiamo questo logica, abbiamo sicuramente dimezzato il 215 00:07:13,030 --> 00:07:15,830 tempo di esecuzione con questo secondo algoritmo gettando via la metà del 216 00:07:15,830 --> 00:07:18,470 numeri, ma quello che abbiamo fatto sul prossimo iterazione, quando Jennifer ha rivelato 217 00:07:18,470 --> 00:07:20,615 il secondo numero? 218 00:07:20,615 --> 00:07:22,830 >> Abbiamo dimezzato il numero di porte di nuovo. 219 00:07:22,830 --> 00:07:25,270 E allora che cosa abbiamo fatto dopo che, se c'erano più porte con cui giocare? 220 00:07:25,270 --> 00:07:27,520 Vorremmo dimezzare loro, e di nuovo, e ancora, e ancora. 221 00:07:27,520 --> 00:07:30,420 E questo era proprio come voi ragazzi tutto in piedi fino alla prima settimana di 222 00:07:30,420 --> 00:07:33,000 classe, la metà di voi seduti, la metà di voi seduti, la metà di voi 223 00:07:33,000 --> 00:07:35,440 seduti, fino a quando uno solitario anima era in piedi. 224 00:07:35,440 --> 00:07:39,050 E abbiamo detto che il tempo di esecuzione di che, il numero di passi impiegato era 225 00:07:39,050 --> 00:07:40,430 sull'ordine di che cosa? 226 00:07:40,430 --> 00:07:41,230 >> SPEAKER 1: [incomprensibile] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. MALAN: Quindi log base 2 di n, o solo più semplicemente, log di n. 228 00:07:43,970 --> 00:07:45,060 Quindi qualcosa logaritmica. 229 00:07:45,060 --> 00:07:48,380 E il grafico non era una linea retta che appena sempre peggio, è stato 230 00:07:48,380 --> 00:07:52,490 questa curva interessante che non ha fatto ottenere così male nel tempo. 231 00:07:52,490 --> 00:07:53,910 Quindi cerchiamo di tenere a questa idea. 232 00:07:53,910 --> 00:07:54,690 Ringraziamo Jennifer. 233 00:07:54,690 --> 00:07:56,150 Grazie mille per essere venuto in su. 234 00:07:56,150 --> 00:07:57,400 E, un secondo. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Nessun lampade da tavolo oggi, ma noi non avere CS50 palline antistress. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Yay. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. MALAN: Va bene, ecco. 239 00:08:04,410 --> 00:08:06,545 Grazie per incorrere voi lo stress qui. 240 00:08:06,545 --> 00:08:07,350 D'accordo. 241 00:08:07,350 --> 00:08:10,620 Quindi vediamo se possiamo non ora formalizzare questo un po 'di più. 242 00:08:10,620 --> 00:08:14,820 Così ancora una volta, quello che abbiamo appena fatto è stato essenzialmente la stessa cosa, come abbiamo fatto 243 00:08:14,820 --> 00:08:16,660 in quella prima settimana. 244 00:08:16,660 --> 00:08:23,780 Ma piuttosto che finiscono con un semplice lineare algoritmo, che abbiamo dipinti un 245 00:08:23,780 --> 00:08:27,210 in precedenza come tale retta, per cui, se abbiamo messo più di una porta per 246 00:08:27,210 --> 00:08:29,610 lo schermo, poi Jennifer sarebbe hanno dovuto cercare, potenzialmente, 247 00:08:29,610 --> 00:08:30,600 più dietro una porta. 248 00:08:30,600 --> 00:08:33,490 Se mettiamo altre due porte, che potrebbe avere di guardare dietro altre due porte. 249 00:08:33,490 --> 00:08:35,990 >> E così, c'era questo lineare rapporto tra la dimensione della 250 00:08:35,990 --> 00:08:39,059 problema, diciamo, l'asse x, e la quantità di tempo necessario per 251 00:08:39,059 --> 00:08:40,440 risolvere il y. 252 00:08:40,440 --> 00:08:43,330 Ma il quadro che stavo alludendo in precedenza era presente linea verde. 253 00:08:43,330 --> 00:08:45,970 Verde volutamente, perché Mi sembrava meglio. 254 00:08:45,970 --> 00:08:49,790 In teoria, l'algoritmo, quando abbiamo fatto con la rubrica, quando abbiamo fatto 255 00:08:49,790 --> 00:08:52,420 con voi ragazzi contare l'altro, e nel secondo caso, quando Jennifer basta 256 00:08:52,420 --> 00:08:55,250 lo ha fatto qui, era sorta di decisamente migliore. 257 00:08:55,250 --> 00:08:57,180 Perché non è stato solo due volte più veloce. 258 00:08:57,180 --> 00:08:58,870 Non è stato addirittura quattro volte più veloce. 259 00:08:58,870 --> 00:09:03,290 E 'stato del tutto dipende da ciò che il dimensioni dell'input era, per quante 260 00:09:03,290 --> 00:09:05,220 passi che in ultima analisi ha preso. 261 00:09:05,220 --> 00:09:08,040 >> E così questa semplice idea che tutti abbiamo preso per scontato con la rubrica telefonica, 262 00:09:08,040 --> 00:09:10,200 può essere applicato similmente a qualcosa di simile a questo. 263 00:09:10,200 --> 00:09:12,380 E questo potrebbe essere più casualmente noto come, come si potrebbe 264 00:09:12,380 --> 00:09:13,940 immaginare, dividere e conquistare. 265 00:09:13,940 --> 00:09:16,390 Non diversamente da quello che abbiamo fatto, naturalmente, con l'elenco telefonico. 266 00:09:16,390 --> 00:09:18,300 >> Ma lo pseudocodice, richiamo, era questo. 267 00:09:18,300 --> 00:09:21,800 Quindi non lo faremo di nuovo, a meno di ricordare che la prima settimana, tutti noi si alzò 268 00:09:21,800 --> 00:09:25,140 e poi la metà di voi seduti, la metà dei si sedette, la metà di voi si sedette. 269 00:09:25,140 --> 00:09:29,280 Questo algoritmo è stato implementato in un po 'un modo barare, in questo, 270 00:09:29,280 --> 00:09:32,870 è stato non solo uno dei me conteggio, fondamentalmente, più efficiente. 271 00:09:32,870 --> 00:09:35,830 In quel caso, stavo facendo leva una risorsa secondaria. 272 00:09:35,830 --> 00:09:39,470 Una specie, più CPU, più cervelli, più persone intelligenti nel 273 00:09:39,470 --> 00:09:42,740 stanza stavano aiutando a ottenere da qualcosa lineare a qualcosa 274 00:09:42,740 --> 00:09:45,190 logaritmica, da qualcosa rosso a qualcosa di verde. 275 00:09:45,190 --> 00:09:48,650 >> Ma in questo caso, solo può Jennifer migliorare sostanzialmente sulla 276 00:09:48,650 --> 00:09:52,370 prestazioni del suo primo algoritmo da, ancora una volta, solo a pensarci un po 'più difficile. 277 00:09:52,370 --> 00:09:56,650 E ora, quando arriva il momento di implementare queste cose, cercare di capire 278 00:09:56,650 --> 00:10:00,670 quali linee di codice si può scrivere come che è possibile ripetere di nuovo, e 279 00:10:00,670 --> 00:10:03,350 ancora, e ancora, una sorta di in maniera ciclica. 280 00:10:03,350 --> 00:10:06,370 Perché tu non hai intenzione di avere il lusso, come Jennifer ha fatto in un primo momento, a 281 00:10:06,370 --> 00:10:10,460 basta avere un sacco di se e dire: hmm, se questo primo numero è 4, 282 00:10:10,460 --> 00:10:11,800 mi permetta di saltare tutta la strada fino alla fine. 283 00:10:11,800 --> 00:10:14,180 Ooh, se quel numero è troppo grande, mi permetta di spostare arbitrariamente indietro 284 00:10:14,180 --> 00:10:15,220 al secondo elemento. 285 00:10:15,220 --> 00:10:18,210 Troverete che si sta andando ad essere molto più difficile da formalizzare ciò che noi umani 286 00:10:18,210 --> 00:10:21,270 dare per scontato come molto ragionevole euristica, ma un computer è solo 287 00:10:21,270 --> 00:10:23,260 intenzione di fare quello che gli si dice di fare. 288 00:10:23,260 --> 00:10:25,280 >> Ora questo è molto interessante implicazioni. 289 00:10:25,280 --> 00:10:29,950 Questo grafico è una sorta di significato per ordinare di sopraffare visivamente, ma preavviso, dove 290 00:10:29,950 --> 00:10:32,230 è la linea retta in questo grafico? 291 00:10:32,230 --> 00:10:35,330 Dove si trova il grafico lineare che noi chiamiamo N? 292 00:10:35,330 --> 00:10:37,580 Beh, è ​​una sorta di verso la parte inferiore di questo quadro, giusto? 293 00:10:37,580 --> 00:10:40,500 Quindi tutto quello che abbiamo fatto è che abbiamo una sorta di zoom out per l'asse x e l' 294 00:10:40,500 --> 00:10:44,780 asse y per cercare di ottenere un senso di ciò che altri tipi di curve assomigliano. 295 00:10:44,780 --> 00:10:47,760 >> E le specifiche della matematica espressioni oggi non importa così 296 00:10:47,760 --> 00:10:52,440 molto, a meno di notare che c'è un sacco di algoritmi che sono molto peggiori di 297 00:10:52,440 --> 00:10:53,470 qualcosa che è lineare. 298 00:10:53,470 --> 00:10:55,410 Anzi, n cubetti sembra piuttosto male. 299 00:10:55,410 --> 00:10:58,400 2 al n sembra piuttosto male. n quadrato sembra piuttosto male. 300 00:10:58,400 --> 00:11:01,630 E vedremo che alcuni di quelli potrebbe essere in realtà di oggi. 301 00:11:01,630 --> 00:11:05,430 E log n non si sente così male, ma meglio che n è log in base 2 di n. 302 00:11:05,430 --> 00:11:08,080 Ma si sa, sarebbe stato anche più sorprendente se Jennifer, o se vogliamo, 303 00:11:08,080 --> 00:11:12,910 che la prima settimana, si era messo a qualcosa che è log di registro di n. 304 00:11:12,910 --> 00:11:15,880 >> Quindi, in altre parole, c'è questo intero gamma di possibili soluzioni a 305 00:11:15,880 --> 00:11:18,570 problemi, ma anche qui, avviso quello che sta per accadere. 306 00:11:18,570 --> 00:11:22,910 Quando ho zoom out, che di queste curve sta per dimostrare di essere l'assoluto 307 00:11:22,910 --> 00:11:26,630 peggio di quelli sullo schermo adesso? 308 00:11:26,630 --> 00:11:28,680 Così n cubetti sembra piuttosto male in questo momento. 309 00:11:28,680 --> 00:11:32,470 Ma se lo zoom indietro e vedere di più del x e l'asse y, che sta per 310 00:11:32,470 --> 00:11:34,550 dominare in definitiva? 311 00:11:34,550 --> 00:11:37,120 Quindi risulta in realtà che 2 alla n, e si può capirlo solo da 312 00:11:37,120 --> 00:11:39,990 collegando in qualche sempre più grande numeri, e vedrai che 2 alla 313 00:11:39,990 --> 00:11:42,070 n, in effetti, diventa più grande molto più veloce. 314 00:11:42,070 --> 00:11:45,530 Se davvero lo zoom indietro, a 2 al algoritmo n schifo assolutamente. 315 00:11:45,530 --> 00:11:48,170 Insomma si tratta di andare a prendere un po 'di tempo per la 316 00:11:48,170 --> 00:11:49,460 computer a sfornare attraverso. 317 00:11:49,460 --> 00:11:52,500 >> Ma si vedrà nel tempo, soprattutto con i futuri set di problema e anche 318 00:11:52,500 --> 00:11:55,600 progetti finali, sono i tuoi dati insieme diventa grande, va bene? 319 00:11:55,600 --> 00:11:58,300 Anche nella prima versione di Facebook, come il numero di amici, e la 320 00:11:58,300 --> 00:12:01,840 numero di utenti registrati ha ottenuto grande, è possibile ordinare di telefono dentro e 321 00:12:01,840 --> 00:12:05,530 realizzare qualcosa con ricerca lineare, o un semplice smistamento 322 00:12:05,530 --> 00:12:07,030 algoritmo, come vedremo oggi. 323 00:12:07,030 --> 00:12:09,280 Devi iniziare a pensare più duro e più difficile di questi problemi. 324 00:12:09,280 --> 00:12:12,070 E i tipi di problemi posti come Facebook e Google, e Microsoft, 325 00:12:12,070 --> 00:12:16,350 e gli altri lavorano è esattamente questi sorta di grande tipo di dati di domande 326 00:12:16,350 --> 00:12:18,530 sempre più in questi giorni. 327 00:12:18,530 --> 00:12:18,900 >> D'accordo. 328 00:12:18,900 --> 00:12:23,800 Quindi il successo di Jennifer in quel secondo algoritmo, francamente, ha fatto incredibilmente 329 00:12:23,800 --> 00:12:26,110 bene la prima volta, ma ti permette di scriverlo come la fortuna in modo che si 330 00:12:26,110 --> 00:12:27,000 possono rendere questo punto. 331 00:12:27,000 --> 00:12:30,970 Nel secondo caso, si leva un algoritmo che ripete ancora e 332 00:12:30,970 --> 00:12:34,670 di nuovo, ma lei ha preso per scontato un certo presupposto che abbiamo permesso 333 00:12:34,670 --> 00:12:39,370 , ma lei sfruttata qualche dettaglio il seconda volta che lei non ha avuto il 334 00:12:39,370 --> 00:12:39,840 prima volta. 335 00:12:39,840 --> 00:12:41,800 Che era che cosa? 336 00:12:41,800 --> 00:12:43,050 >> Che l'elenco è stato risolto. 337 00:12:43,050 --> 00:12:46,350 Quindi, non appena la lista è stato risolto, abbiamo sostengono che Jennifer è stata in grado di fare 338 00:12:46,350 --> 00:12:47,480 fondamentalmente meglio. 339 00:12:47,480 --> 00:12:51,450 7 porte, sì, non è poi così interessante, ma suppongo che siamo 7 milioni di porte. 340 00:12:51,450 --> 00:12:54,080 Log di n è sicuramente per eseguire molto, molto 341 00:12:54,080 --> 00:12:55,610 più veloce nel lungo periodo. 342 00:12:55,610 --> 00:12:58,880 Ma lei doveva avere il Porte Ordina per lei. 343 00:12:58,880 --> 00:13:02,320 Ora, mi sono preso la libertà di fare quello anticipatamente sullo schermo del computer 344 00:13:02,320 --> 00:13:05,160 qui, ma supponiamo che Jennifer doveva farlo se stessa? 345 00:13:05,160 --> 00:13:10,120 Supponiamo che le porte in questione dati rappresentati in un database, o 346 00:13:10,120 --> 00:13:14,260 amici iscritti per Facebook, o le pagine web su internet che 347 00:13:14,260 --> 00:13:16,880 vari siti web potrebbe essere necessario per indice o ricerca con. 348 00:13:16,880 --> 00:13:20,940 >> Supponiamo che si è appena conclusa a dati grezzi impostato e si è lasciata a voi, o per 349 00:13:20,940 --> 00:13:23,010 Jennifer farlo ordinamento? 350 00:13:23,010 --> 00:13:26,950 Che, anzi, richiede che noi rispondiamo la questione, così, quanto tempo 351 00:13:26,950 --> 00:13:31,080 avrebbe preso Jennifer, o anche me, per ordinare quei numeri in anticipo così 352 00:13:31,080 --> 00:13:32,680 che avrebbe potuto approfittare di questo? 353 00:13:32,680 --> 00:13:32,880 Giusto? 354 00:13:32,880 --> 00:13:36,620 Poiché l'implicazione, naturalmente, è se mi ci vuole un po 'di tempo per ordinare 355 00:13:36,620 --> 00:13:40,800 i numeri, che il diavolo se ne frega che si riesce a trovare un numero come 50 così in fretta, 356 00:13:40,800 --> 00:13:44,850 come nel caso di Jennifer, se abbiamo più di travolto la quantità di tempo totale 357 00:13:44,850 --> 00:13:46,920 ha preso di classificare le cose in anticipo? 358 00:13:46,920 --> 00:13:49,320 >> Quindi cerchiamo di vedere se non possiamo la dipingere il quadro qui. 359 00:13:49,320 --> 00:13:51,370 Ho un sacco di più lo stress palle, se questo aiuta 360 00:13:51,370 --> 00:13:52,270 rompere il ghiaccio qui. 361 00:13:52,270 --> 00:13:55,690 E se non ti dispiace, abbiamo bisogno di sette volontari - 362 00:13:55,690 --> 00:13:57,060 su, OK. 363 00:13:57,060 --> 00:13:57,240 Wow. 364 00:13:57,240 --> 00:13:59,250 Quindi non dobbiamo spendere su lampade da tavolo, a quanto pare. 365 00:13:59,250 --> 00:13:59,690 D'accordo. 366 00:13:59,690 --> 00:14:01,530 Così come su voi due davanti. 367 00:14:01,530 --> 00:14:04,160 Che ne dici di due ragazzi nella schiena. 368 00:14:04,160 --> 00:14:04,870 Ecco, questo è quattro. 369 00:14:04,870 --> 00:14:09,890 Come su di te di fronte cinque, sei e sette. 370 00:14:09,890 --> 00:14:10,320 Proprio lì. 371 00:14:10,320 --> 00:14:13,260 Il tuo amico ti sta sottolineando, in modo da ottenere il premio. 372 00:14:13,260 --> 00:14:13,700 >> D'accordo. 373 00:14:13,700 --> 00:14:14,410 Andiamo su. 374 00:14:14,410 --> 00:14:17,120 E perché non abbiamo voi ragazzi Vieni qui. 375 00:14:17,120 --> 00:14:18,960 Io vado a dare ciascuno un numero. 376 00:14:18,960 --> 00:14:22,150 E andare avanti e organizzare voi stessi identico a ciò che è 377 00:14:22,150 --> 00:14:25,180 rappresentata sullo schermo. 378 00:14:25,180 --> 00:14:26,530 >> [Interponendo VOCI] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. MALAN: Oop, mi dispiace. 380 00:14:28,160 --> 00:14:30,210 Bug. 381 00:14:30,210 --> 00:14:32,180 D'accordo. 382 00:14:32,180 --> 00:14:32,750 Bene, ci siamo. 383 00:14:32,750 --> 00:14:34,180 Numero cinque. 384 00:14:34,180 --> 00:14:35,136 Numero sei. 385 00:14:35,136 --> 00:14:37,770 Uno, due, tre, quattro, cinque, sei, sette. 386 00:14:37,770 --> 00:14:39,410 Oh, questo è imbarazzante. 387 00:14:39,410 --> 00:14:41,210 >> SPEAKER 2: Prendo un -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. MALAN: Buon affare. 389 00:14:41,900 --> 00:14:43,130 D'accordo. 390 00:14:43,130 --> 00:14:44,611 Grazie per aver partecipato. 391 00:14:44,611 --> 00:14:47,200 >> [Applausi] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 D'accordo. 394 00:14:48,860 --> 00:14:51,970 Quindi abbiamo quattro, due, sei, uno, tre, sette, cinque. 395 00:14:51,970 --> 00:14:56,010 Perfetto così abbiamo sette volontari qui che sono uguale alla larghezza del 396 00:14:56,010 --> 00:14:57,430 array che stiamo giocando con la precedente. 397 00:14:57,430 --> 00:14:59,470 E ho scelto sette per ragioni che sarà solo 398 00:14:59,470 --> 00:15:00,840 conveniente in un po '. 399 00:15:00,840 --> 00:15:04,400 E ho intenzione di proporre prima che siamo impegnati a risolvere questi sette volontari. 400 00:15:04,400 --> 00:15:06,786 Se vuoi, in primo luogo, per dire ciao però. 401 00:15:06,786 --> 00:15:08,970 Dal momento che questo sta andando essere un scomode diversi minuti. 402 00:15:08,970 --> 00:15:10,370 Presentatevi. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Ciao, sono Grazia. 404 00:15:10,980 --> 00:15:14,190 Sono al secondo anno in Leverett House. 405 00:15:14,190 --> 00:15:14,620 >> BRANSON: Ciao. 406 00:15:14,620 --> 00:15:15,620 Sono Branson. 407 00:15:15,620 --> 00:15:16,920 Io sono una matricola in Weld. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> GABE: Ciao. 410 00:15:20,230 --> 00:15:21,040 Sono Gabe. 411 00:15:21,040 --> 00:15:22,300 Sono una junior a Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Sono Neil. 414 00:15:25,980 --> 00:15:29,090 Sono una matricola a Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Sono Jason. 416 00:15:29,550 --> 00:15:32,816 Io sono una matricola in Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Io sono Mike. 418 00:15:33,700 --> 00:15:37,360 Io sono una matricola in Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: io sono Jess. 420 00:15:37,990 --> 00:15:40,313 Sono al secondo anno in Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. MALAN: Eccellente. 422 00:15:41,300 --> 00:15:41,850 D'accordo. 423 00:15:41,850 --> 00:15:44,190 Bene, grazie a tutti i nostri volontari qui finora. 424 00:15:44,190 --> 00:15:47,110 E la sfida a portata di mano ora sta andando di essere a ordinare di questi ragazzi, ma poi 425 00:15:47,110 --> 00:15:50,250 stiamo andando ad avere per pensare un po ' difficile di quanto siamo efficienti realtà 426 00:15:50,250 --> 00:15:51,110 loro ordinato. 427 00:15:51,110 --> 00:15:52,580 Quindi cerchiamo di prima provare questo. 428 00:15:52,580 --> 00:15:55,970 Voi ragazzi potete vedere i rispettivi numeri di semplicemente posizionando intorno agli angoli. 429 00:15:55,970 --> 00:15:59,380 Andare avanti e prendere un paio di secondi, e sorta voi stessi dal più piccolo al 430 00:15:59,380 --> 00:16:01,240 sinistra a grande sulla destra. 431 00:16:01,240 --> 00:16:02,490 Go. 432 00:16:02,490 --> 00:16:07,010 433 00:16:07,010 --> 00:16:07,530 >> OK. 434 00:16:07,530 --> 00:16:08,030 Buono. 435 00:16:08,030 --> 00:16:09,370 E 'stato davvero maledettamente veloce. 436 00:16:09,370 --> 00:16:14,040 Ora qualcuno qui, che cosa era l'algoritmo che questi ragazzi applicate? 437 00:16:14,040 --> 00:16:14,900 >> SPEAKER 1: dal numero minore al maggiore. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. MALAN: OK. 439 00:16:15,000 --> 00:16:18,070 Piccolo al più grande è in realtà una sorta di obiettivo, ma non sono sicuro che è 440 00:16:18,070 --> 00:16:18,890 davvero un algoritmo. 441 00:16:18,890 --> 00:16:21,810 Piccolo al più grande non dice Mi passo per passo cosa fare. 442 00:16:21,810 --> 00:16:22,833 Sì? 443 00:16:22,833 --> 00:16:24,083 >> SPEAKER 1: [incomprensibile] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> DAVID J. MALAN: OK. 446 00:16:26,280 --> 00:16:28,920 Quindi, se vedete una persona minore di il tuo numero, per poi passare a 447 00:16:28,920 --> 00:16:29,680 loro destra. 448 00:16:29,680 --> 00:16:32,800 Ecco, questo è ormai sempre più espressiva, più simile a un algoritmo, perché si 449 00:16:32,800 --> 00:16:35,410 può dire, se questo, poi quello. 450 00:16:35,410 --> 00:16:37,050 Così abbiamo un qualche tipo di costrutto condizionale. 451 00:16:37,050 --> 00:16:39,700 E questi ragazzi sembrano fare che pochi volte, perché alcuni di voi sono trasferito un po ' 452 00:16:39,700 --> 00:16:40,420 di una distanza. 453 00:16:40,420 --> 00:16:43,410 Quindi c'era presumibilmente una sorta di looping succedendo nelle loro menti. 454 00:16:43,410 --> 00:16:44,610 >> Ma cerchiamo di formalizzare tale. 455 00:16:44,610 --> 00:16:47,540 Se voi ragazzi poteste reimpostare indietro a questo accordo. 456 00:16:47,540 --> 00:16:50,650 Vediamo se non siamo in grado di formalizzare questo un po ', e poi fare la domanda, appena 457 00:16:50,650 --> 00:16:51,580 come efficiente è questo? 458 00:16:51,580 --> 00:16:54,220 Naturalmente, quando lo facciamo più lentamente, sta andando a sentire come bene di 459 00:16:54,220 --> 00:16:57,210 un algoritmo, ma vediamo se possiamo mettere le dita sui punti precisi. 460 00:16:57,210 --> 00:16:58,670 >> Quindi voi due ragazzi sono quattro e due. 461 00:16:58,670 --> 00:17:01,020 Oppure è nell'ordine corretto o scorretto? 462 00:17:01,020 --> 00:17:01,900 Ovviamente non corretta. 463 00:17:01,900 --> 00:17:02,710 Così ci siamo scambiati. 464 00:17:02,710 --> 00:17:05,170 Ora ho intenzione di farsi da parte qui e dire, 4-6. 465 00:17:05,170 --> 00:17:06,240 Siete corretto o scorretto? 466 00:17:06,240 --> 00:17:06,599 >> GABE: Corretto. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. MALAN: Corretto. 468 00:17:07,180 --> 00:17:08,300 Sei mesi e un? 469 00:17:08,300 --> 00:17:08,609 Nope. 470 00:17:08,609 --> 00:17:09,630 Scambia. 471 00:17:09,630 --> 00:17:10,490 Ecco, questo è due swap. 472 00:17:10,490 --> 00:17:11,710 Sei e tre? 473 00:17:11,710 --> 00:17:11,980 Nope. 474 00:17:11,980 --> 00:17:13,000 Scambia. 475 00:17:13,000 --> 00:17:13,930 Sei e sette? 476 00:17:13,930 --> 00:17:14,630 Sembra buono. 477 00:17:14,630 --> 00:17:15,396 Sette e cinque? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [incomprensibile] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. MALAN: OK, scambiare. 480 00:17:17,089 --> 00:17:19,770 E ordinati. 481 00:17:19,770 --> 00:17:19,980 D'accordo. 482 00:17:19,980 --> 00:17:21,440 Così, ovviamente no, giusto? 483 00:17:21,440 --> 00:17:22,470 Quindi non c'era più in corso. 484 00:17:22,470 --> 00:17:24,920 Ma, in effetti, questi ragazzi, anche solo istintivamente. 485 00:17:24,920 --> 00:17:25,450 mantenuto in movimento. 486 00:17:25,450 --> 00:17:27,710 Essi non solo smettere, una volta che corretto un problema. 487 00:17:27,710 --> 00:17:27,839 Così. 488 00:17:27,839 --> 00:17:29,390 Anzi, ho intenzione di avere a fare la stessa cosa. 489 00:17:29,390 --> 00:17:32,720 Ho intenzione di fare per ordinare di riavvolgere indietro per l'inizio di questo problema, 490 00:17:32,720 --> 00:17:35,630 o l'inizio di questa matrice di popolo, cominciamo a chiamarli. 491 00:17:35,630 --> 00:17:38,366 >> E ora che cosa dovrebbe il mio algoritmo al secondo passaggio sarà? 492 00:17:38,366 --> 00:17:39,220 >> SPEAKER 1: Stessa cosa. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. MALAN: Stessa cosa. 494 00:17:39,940 --> 00:17:41,460 E questo, sto iniziando a piacermi, giusto? 495 00:17:41,460 --> 00:17:44,720 Non appena si può trovare se stessi facendo la stessa cosa più e più volte, questo è 496 00:17:44,720 --> 00:17:47,890 diventando più simile a un algoritmo, e l'istinto meno umano. 497 00:17:47,890 --> 00:17:48,680 >> Così ora, ci risiamo. 498 00:17:48,680 --> 00:17:49,870 Due e quattro? 499 00:17:49,870 --> 00:17:50,220 No. 500 00:17:50,220 --> 00:17:51,050 Quattro e un? 501 00:17:51,050 --> 00:17:53,380 Ah, vi è stato effettivamente un po 'di lavoro ancora da fare. 502 00:17:53,380 --> 00:17:53,620 Per e tre? 503 00:17:53,620 --> 00:17:54,572 Buono. 504 00:17:54,572 --> 00:17:56,000 Quattro e sei? 505 00:17:56,000 --> 00:17:58,380 Sei e cinque? 506 00:17:58,380 --> 00:17:59,470 Sei e sette? 507 00:17:59,470 --> 00:18:00,970 OK, ora, fatto. 508 00:18:00,970 --> 00:18:01,550 OK, no. 509 00:18:01,550 --> 00:18:02,710 Devo tornare indietro. 510 00:18:02,710 --> 00:18:05,130 >> Così ora, ancora una volta, stiamo facendo questo un po 'più deliberatamente. 511 00:18:05,130 --> 00:18:08,700 E ora, c'è solo un cervello esecuzione di questo algoritmo. 512 00:18:08,700 --> 00:18:10,290 Una CPU, se si vuole. 513 00:18:10,290 --> 00:18:13,090 E, francamente, questa è l'unica risorsa stiamo andando ad avere accesso. 514 00:18:13,090 --> 00:18:16,280 E una volta che noi torniamo a una tastiera e di avere qualcosa come C a nostra 515 00:18:16,280 --> 00:18:19,600 disposizione, stiamo solo scrivendo un programma che si può fare una cosa alla volta. 516 00:18:19,600 --> 00:18:22,900 Considerando che, a questi ragazzi un momento fa, abbiamo leveraged loro intelligenza collettiva 517 00:18:22,900 --> 00:18:24,180 come voi avete fatto in settimana zero. 518 00:18:24,180 --> 00:18:24,980 Quindi cerchiamo di continuare a fare questo. 519 00:18:24,980 --> 00:18:26,260 >> Due e uno. 520 00:18:26,260 --> 00:18:26,945 Due e tre. 521 00:18:26,945 --> 00:18:27,460 Tre e quattro. 522 00:18:27,460 --> 00:18:28,310 Quattro e cinque. 523 00:18:28,310 --> 00:18:28,620 Cinque e sei. 524 00:18:28,620 --> 00:18:30,510 Sei e sette. 525 00:18:30,510 --> 00:18:31,880 Fatto? 526 00:18:31,880 --> 00:18:34,560 Così sono io, ma fammi giocare l'avvocato del diavolo. 527 00:18:34,560 --> 00:18:37,950 Faccio, il tipo di computer è che ha appena fatto un passaggio attraverso questa serie di 528 00:18:37,950 --> 00:18:40,225 persone, sanno che ho finito? 529 00:18:40,225 --> 00:18:40,670 >> SPEAKER 1: No. 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. MALAN: Allora perché? 531 00:18:41,050 --> 00:18:46,900 Che cosa avrei dovuto fare per Concludo con decisione che mi sono fatto? 532 00:18:46,900 --> 00:18:48,230 Probabilmente uno più pass. 533 00:18:48,230 --> 00:18:48,430 Giusto? 534 00:18:48,430 --> 00:18:51,760 Perché tutto quello che so da quello precedente passaggio è che ho corretto un errore. 535 00:18:51,760 --> 00:18:53,920 E questo significa, forse c'è ancora un altro errore 536 00:18:53,920 --> 00:18:54,840 che ho bisogno di correggere. 537 00:18:54,840 --> 00:18:58,680 Quindi posso solo essere sicuro di riavvolgimento e quindi il controllo, 1-2, due e 538 00:18:58,680 --> 00:19:00,940 tre, tre e quattro, quattro e cinque, cinque e sei, sei e sette. 539 00:19:00,940 --> 00:19:02,510 OK, ora ho fatto nessun lavoro. 540 00:19:02,510 --> 00:19:05,990 >> Posso certamente ricordare che ho fatto non lavorare con qualcosa di simile a una variabile, 541 00:19:05,990 --> 00:19:06,975 come un int. 542 00:19:06,975 --> 00:19:12,490 Chiamatelo swap, e se gli swap è 0 volta ho arrivare qui, e ha cominciato a 0, allora 543 00:19:12,490 --> 00:19:15,520 Sarei stupido andare avanti avanti e indietro, controllando di nuovo, e 544 00:19:15,520 --> 00:19:16,450 ancora, e ancora, giusto? 545 00:19:16,450 --> 00:19:18,450 Perché ti trovi in ​​difficoltà in qualche tipo di ciclo infinito. 546 00:19:18,450 --> 00:19:21,250 Quindi, non appena c'è 0 swap, possiamo affermare che questa 547 00:19:21,250 --> 00:19:23,810 algoritmo è davvero completa. 548 00:19:23,810 --> 00:19:25,400 >> Ora, mettiamo un nome su questo. 549 00:19:25,400 --> 00:19:28,930 L'algoritmo che vi propongo che abbiamo appena implementata è una cosa chiamata bolla 550 00:19:28,930 --> 00:19:32,800 liste, nota come tale nel senso che i numeri che sono più grandi di tipo 551 00:19:32,800 --> 00:19:37,990 bolla la loro strada fino alla cima, o fino alla fine della matrice di numeri. 552 00:19:37,990 --> 00:19:40,270 Ma quanto efficiente fosse questo algoritmo? 553 00:19:40,270 --> 00:19:44,600 Quanti passi ho dovuto fisicamente prendere, per esempio, di ordinare questi 554 00:19:44,600 --> 00:19:45,850 sette gli esseri umani? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Quattro o cinque? 557 00:19:49,550 --> 00:19:51,420 OK, troppi è in definitiva andando ad essere la risposta. 558 00:19:51,420 --> 00:19:54,960 Ma anche allora, il numero specifico non è così interessante. 559 00:19:54,960 --> 00:19:56,670 Cerchiamo di generalizzare come n. 560 00:19:56,670 --> 00:20:00,520 Quindi, se avessi n persone qui, e loro erano, sorta di, in ordine casuale al 561 00:20:00,520 --> 00:20:02,180 a cominciare, in questo ordine originale. 562 00:20:02,180 --> 00:20:04,910 Beh, quanti passi ho dovuto per prendere il primo passo? 563 00:20:04,910 --> 00:20:09,810 Era uno, due, tre, quattro, cinque, sei, e sono sette persone, in modo da 564 00:20:09,810 --> 00:20:13,670 questo è sette, sei -, così che è n meno uno passi la prima volta. 565 00:20:13,670 --> 00:20:16,280 >> Ora, quanti passi ho dovuto prendere quando ho riavvolto? 566 00:20:16,280 --> 00:20:19,310 Beh, potremmo effettivamente il doppio che se volevamo, ma per ora, sono 567 00:20:19,310 --> 00:20:22,300 solo andando a dire, va bene, un altro n meno 1. 568 00:20:22,300 --> 00:20:25,240 Così il n meno 1 sta per arrivare fastidioso per tenere traccia di, quindi cerchiamo di 569 00:20:25,240 --> 00:20:26,400 basta arrotondare leggermente. 570 00:20:26,400 --> 00:20:27,770 Così 2n passi. 571 00:20:27,770 --> 00:20:29,310 Quindi 14 passi, prendere o lasciare. 572 00:20:29,310 --> 00:20:31,930 >> Quante volte mi prendo un passo la prossima volta? 573 00:20:31,930 --> 00:20:33,740 Beh, è ​​3n. 574 00:20:33,740 --> 00:20:34,510 davvero. 575 00:20:34,510 --> 00:20:37,920 E ora, nel peggiore dei casi, per esempio, quante volte avrei dovuto 576 00:20:37,920 --> 00:20:41,730 andato avanti e indietro, avanti e indietro, l'esecuzione di questo algoritmo, scambiando 577 00:20:41,730 --> 00:20:44,620 persone su ogni passaggio, approssimativamente? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 In realtà è N al quadrato, giusto? 580 00:20:50,010 --> 00:20:53,000 >> Perché nel peggiore dei casi, è possibile tipo di pensare a questo modo intuitivo, 581 00:20:53,000 --> 00:20:54,800 anche se potrebbe richiedere un po ' po 'di tempo per affondare dentro 582 00:20:54,800 --> 00:20:57,590 Nel peggiore dei casi, quali sarebbero questi sette persone hanno guardato come, in 583 00:20:57,590 --> 00:21:00,230 termini contrattuali del loro numero? 584 00:21:00,230 --> 00:21:01,460 Completamente indietro, giusto? 585 00:21:01,460 --> 00:21:02,815 E proprio per simulare che, ciò che è stato ancora una volta il suo nome? 586 00:21:02,815 --> 00:21:03,360 >> MIKE: Mike. 587 00:21:03,360 --> 00:21:03,640 >> DAVID J. MALAN: Mike? 588 00:21:03,640 --> 00:21:08,100 OK, Mike, si può solo unirsi a me nel corso qui per un solo secondo? 589 00:21:08,100 --> 00:21:08,880 In realtà, no. 590 00:21:08,880 --> 00:21:10,150 Mi dispiace Mike, rewind andiamo. 591 00:21:10,150 --> 00:21:10,910 Qual è il tuo nome? 592 00:21:10,910 --> 00:21:11,180 >> NEIL: Neil. 593 00:21:11,180 --> 00:21:11,640 >> DAVID J. MALAN: Neil. 594 00:21:11,640 --> 00:21:13,750 OK, Neil, tu vieni con me, se non ti dispiace. 595 00:21:13,750 --> 00:21:17,150 Quindi ho intenzione di proporre, solo per semplicità, che Neil è ora nella sua 596 00:21:17,150 --> 00:21:18,510 peggiore dei casi possibili. 597 00:21:18,510 --> 00:21:20,720 Ma ricordo come ho implementato il mio algoritmo. 598 00:21:20,720 --> 00:21:24,530 Sto confrontando, confronto, confronto, confronto, confronto, oh. 599 00:21:24,530 --> 00:21:26,640 Ora questi ragazzi sono fuori di ordine, in modo da posso correggere. 600 00:21:26,640 --> 00:21:27,980 Allora ragazzi swap. 601 00:21:27,980 --> 00:21:31,630 Ma considerare ora, quanto più lontano Neil non deve andare? 602 00:21:31,630 --> 00:21:32,690 Grosso n. 603 00:21:32,690 --> 00:21:33,570 Sai, non è in realtà n. 604 00:21:33,570 --> 00:21:36,040 E 'come, n meno 1, ma mi sto infastidito tenendo traccia del piccolo 605 00:21:36,040 --> 00:21:37,550 numero, quindi cerchiamo di appena lo chiamano n. 606 00:21:37,550 --> 00:21:42,860 >> Quindi, se Neil si sposta di un passo al massimo ogni tempo, e per spostare Neil un passo, 607 00:21:42,860 --> 00:21:46,580 Devo fare questo passo davvero noioso avanti e indietro, questo è approssimativamente 608 00:21:46,580 --> 00:21:52,080 In questo modo, n passi, per un totale di n volte, perché sta andando a prendere me 609 00:21:52,080 --> 00:21:55,820 che molti passi per ottenere Neil tutti il modo per cui appartiene. 610 00:21:55,820 --> 00:21:58,620 Per non parlare di tutti gli altri se voi ragazzi sono stati tutti mis-ordinato pure. 611 00:21:58,620 --> 00:22:01,100 >> Quindi chiamiamolo bubble sort n quadrato. 612 00:22:01,100 --> 00:22:04,860 Il tempo di esecuzione di questo algoritmo, la prestazioni di questo algoritmo, la 613 00:22:04,860 --> 00:22:07,120 efficienza di questo algoritmo, avremo solo descrivere più 614 00:22:07,120 --> 00:22:08,800 generalmente come n al quadrato. 615 00:22:08,800 --> 00:22:11,650 Il che è bello, perché ho potuto fare l' stesso esempio con otto persone, nove 616 00:22:11,650 --> 00:22:15,450 persone, un milione di persone, e che risposta non sta per cambiare. 617 00:22:15,450 --> 00:22:18,870 >> Quindi, se voi ragazzi non mi dispiacerebbe, diamo vi ripristinare al punto di partenza. 618 00:22:18,870 --> 00:22:22,510 E proviamo altri due approcci e vedere se non possiamo fare fondamentalmente 619 00:22:22,510 --> 00:22:23,820 meglio di questo. 620 00:22:23,820 --> 00:22:27,130 Così questa volta, ho intenzione di proporre una sorta di algoritmo diverso. 621 00:22:27,130 --> 00:22:29,950 Questo è stato molto intelligente di noi l'ultima volta, e voi ragazzi erano proprio per avere la 622 00:22:29,950 --> 00:22:32,470 giusti istinti di solo tipo di scambiare due a due. 623 00:22:32,470 --> 00:22:36,500 Ma se volevo davvero avvicinarsi a questo semplicemente, e il mio obiettivo è quello di spostare 624 00:22:36,500 --> 00:22:39,800 tutti i piccoli numeri in questo modo, e spingere tutti i grandi numeri che 625 00:22:39,800 --> 00:22:43,030 A proposito, perché non lo faccio e basta che nel più ingenuo modo possibile e vedere se io 626 00:22:43,030 --> 00:22:45,730 può fare meglio di quello che era un piuttosto complesso algoritmo? 627 00:22:45,730 --> 00:22:46,620 >> Quindi vediamo. 628 00:22:46,620 --> 00:22:48,940 Quattro è un numero abbastanza piccolo, quindi sono intenzione di lasciarvi vi momento. 629 00:22:48,940 --> 00:22:50,610 Ooh, il numero due è ancora meglio. 630 00:22:50,610 --> 00:22:52,230 Quindi, si può solo fare un passo avanti per un momento? 631 00:22:52,230 --> 00:22:55,670 Questo è attualmente il mio piccolo numerata candidato, e ho intenzione di ricordare 632 00:22:55,670 --> 00:22:57,000 che con, tipo, una variabile. 633 00:22:57,000 --> 00:22:57,930 Ma ho intenzione di mantenere il controllo. 634 00:22:57,930 --> 00:22:59,890 C'è qualcuno di cui numero è più piccolo? 635 00:22:59,890 --> 00:23:00,460 Sei, no. 636 00:23:00,460 --> 00:23:01,390 Oh, c'è di nuovo Neil. 637 00:23:01,390 --> 00:23:04,050 >> Quindi ho intenzione di spingere indietro sorta di concettualmente. 638 00:23:04,050 --> 00:23:05,120 Neil si farà avanti. 639 00:23:05,120 --> 00:23:08,440 E ora, la variabile che sto usando per tenere traccia di chi ha il più piccolo 640 00:23:08,440 --> 00:23:11,390 numero viene aggiornato per contenere Posizione di Neil. 641 00:23:11,390 --> 00:23:12,110 Bene, vediamo. 642 00:23:12,110 --> 00:23:13,960 Tre, sette, cinque. 643 00:23:13,960 --> 00:23:15,590 OK, so che Neil era il più piccolo. 644 00:23:15,590 --> 00:23:18,110 Qual è la cosa più semplice per me di fare ora? 645 00:23:18,110 --> 00:23:21,410 Non ho intenzione di sprecare il mio tempo da solo ribollimento Neil un posto a sinistra. 646 00:23:21,410 --> 00:23:25,350 Perché non appena messo Neil dove ha appartiene, che è ovviamente dove? 647 00:23:25,350 --> 00:23:26,160 >> Tutto il percorso all'inizio. 648 00:23:26,160 --> 00:23:27,720 Così Neil, vieni con me. 649 00:23:27,720 --> 00:23:28,910 E che cosa era di nuovo il tuo nome? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Grazia. 651 00:23:29,310 --> 00:23:29,710 >> DAVID J. MALAN: Grazia. 652 00:23:29,710 --> 00:23:29,920 OK. 653 00:23:29,920 --> 00:23:32,490 Così Grazia, purtroppo, si è tipo di intralcio. 654 00:23:32,490 --> 00:23:34,290 Quindi, come possiamo risolvere questo problema? 655 00:23:34,290 --> 00:23:34,490 Giusto? 656 00:23:34,490 --> 00:23:37,500 Se questo è un array, non c'è solo sette posizioni. 657 00:23:37,500 --> 00:23:40,830 Ricordiamo che, con Rob, abbiamo parlato dichiarando le età, e abbiamo avuto solo un 658 00:23:40,830 --> 00:23:41,740 numero finito di età? 659 00:23:41,740 --> 00:23:42,535 Stessa idea qui. 660 00:23:42,535 --> 00:23:44,300 Abbiamo solo un numero finito di int. 661 00:23:44,300 --> 00:23:47,590 Grazia è una specie di nel nostro modo, così come possiamo risolvere? 662 00:23:47,590 --> 00:23:49,555 >> Il modo più semplice è come, Grazia, mi dispiace. 663 00:23:49,555 --> 00:23:51,870 Stai andando ad avere per andare oltre c'è modo che possiamo fare spazio. 664 00:23:51,870 --> 00:23:55,290 Ora, se si pensa a questo, forse abbiamo appena fatto peggiorare il problema. 665 00:23:55,290 --> 00:23:58,510 E forse abbiamo fatto, perché ciò che se Grazia erano nel posto giusto? 666 00:23:58,510 --> 00:24:01,730 Ma sappiamo che non lo è, perché in caso contrario, sarebbe stata 667 00:24:01,730 --> 00:24:03,980 in piedi in avanti invece di Neil in questo momento, giusto? 668 00:24:03,980 --> 00:24:05,550 Abbiamo già fatto il check-out il suo numero. 669 00:24:05,550 --> 00:24:05,770 >> D'accordo. 670 00:24:05,770 --> 00:24:09,110 Così ora, Neil è al posto giusto, e Posso fare una leggera ottimizzazione. 671 00:24:09,110 --> 00:24:11,740 Per il prossimo minuto, ho intenzione di ignorare Neil tutti insieme, in modo da non 672 00:24:11,740 --> 00:24:15,280 sprecare il suo tempo, o accidentalmente lo scambiare il posto sbagliato. 673 00:24:15,280 --> 00:24:17,805 Così ora, come faccio a trovare il prossimo elemento che è più piccolo? 674 00:24:17,805 --> 00:24:18,480 Due. 675 00:24:18,480 --> 00:24:20,225 Questo è un buon numero, se si vuole fare un passo avanti e 676 00:24:20,225 --> 00:24:21,100 Mi ricorderò di te. 677 00:24:21,100 --> 00:24:21,980 Sei, non va bene. 678 00:24:21,980 --> 00:24:24,820 Quattro, tre, sette, cinque, non va bene. 679 00:24:24,820 --> 00:24:26,800 Quindi lasciate che muovo a il tuo posto giusto. 680 00:24:26,800 --> 00:24:28,470 E siamo solo stati fortunati questa volta. 681 00:24:28,470 --> 00:24:31,350 >> Ora, ho intenzione di ignorare questi due ragazzi, e ora fare un altro 682 00:24:31,350 --> 00:24:32,260 passare attraverso questo. 683 00:24:32,260 --> 00:24:33,490 Sei, che un numero abbastanza piccolo. 684 00:24:33,490 --> 00:24:34,300 Andiamo avanti. 685 00:24:34,300 --> 00:24:35,220 Oh, mi dispiace. 686 00:24:35,220 --> 00:24:37,640 Numero di Grace è meglio, così passo su avanti. 687 00:24:37,640 --> 00:24:38,260 Quattro. 688 00:24:38,260 --> 00:24:39,120 Siamo spiacenti, Grazia. 689 00:24:39,120 --> 00:24:39,950 Tornarci. 690 00:24:39,950 --> 00:24:41,550 Numero tre è meglio. 691 00:24:41,550 --> 00:24:42,290 Sette. 692 00:24:42,290 --> 00:24:42,720 Cinque. 693 00:24:42,720 --> 00:24:43,550 E ora che cosa è che ti chiami? 694 00:24:43,550 --> 00:24:44,000 >> JASON: Jason. 695 00:24:44,000 --> 00:24:44,420 >> DAVID J. MALAN: Jason. 696 00:24:44,420 --> 00:24:47,050 Così Jason è ora il più piccolo elemento che ho selezionato. 697 00:24:47,050 --> 00:24:49,160 Dove sta andando andare? 698 00:24:49,160 --> 00:24:50,380 Allora, dove sei è. 699 00:24:50,380 --> 00:24:51,210 E il tuo nome è nuovo? 700 00:24:51,210 --> 00:24:51,710 >> GABE: Gabe. 701 00:24:51,710 --> 00:24:52,340 >> DAVID J. MALAN: Gabe. 702 00:24:52,340 --> 00:24:53,220 Gabe è in mezzo. 703 00:24:53,220 --> 00:24:54,640 Qual è la cosa più facile da fare? 704 00:24:54,640 --> 00:24:58,390 Scambia questi due ragazzi e continuare. 705 00:24:58,390 --> 00:24:59,020 Così ora vediamo. 706 00:24:59,020 --> 00:25:00,170 Chi è il più piccolo? 707 00:25:00,170 --> 00:25:01,030 Quattro. 708 00:25:01,030 --> 00:25:01,990 Lasciami solo tipo di imbroglio. 709 00:25:01,990 --> 00:25:03,090 Cinque sta per essere il più piccolo. 710 00:25:03,090 --> 00:25:05,220 Trovo prossimo, se si vuole fare un passo in avanti, che cosa devo fare con 711 00:25:05,220 --> 00:25:06,820 questi ragazzi, con Gabe? 712 00:25:06,820 --> 00:25:08,450 Swap di nuovo. 713 00:25:08,450 --> 00:25:10,740 Così ora, ancora un po 'in ordine. 714 00:25:10,740 --> 00:25:14,140 Ho trovato Gabe per essere il più piccolo, in modo da Lo Pop Out, muovo ragazzi sopra. 715 00:25:14,140 --> 00:25:15,190 E fatto. 716 00:25:15,190 --> 00:25:17,200 >> Così risposta è la stessa. 717 00:25:17,200 --> 00:25:18,600 Il risultato finale è lo stesso. 718 00:25:18,600 --> 00:25:22,730 Quale di questi due algoritmi è meglio? 719 00:25:22,730 --> 00:25:23,500 Il secondo, ho sentito. 720 00:25:23,500 --> 00:25:24,252 Perché? 721 00:25:24,252 --> 00:25:25,900 >> SPEAKER 3: E 'n passi [incomprensibile]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. MALAN: E 'n passi in più. 723 00:25:27,600 --> 00:25:28,490 Interessante. 724 00:25:28,490 --> 00:25:30,610 Quindi è però? 725 00:25:30,610 --> 00:25:33,630 Così come ho trovato il elemento più piccolo? 726 00:25:33,630 --> 00:25:37,060 Quanti passi ho dovuto prendere il trovare l'elemento più piccolo? 727 00:25:37,060 --> 00:25:39,220 Ho dato un'occhiata in fondo alla fine, giusto? 728 00:25:39,220 --> 00:25:41,530 Perché in quel caso peggiore, quello che Neil se fosse qui? 729 00:25:41,530 --> 00:25:45,700 Quindi solo trovare il più piccolo elemento me n passi, o n meno 1 prende. 730 00:25:45,700 --> 00:25:46,100 Ma, OK. 731 00:25:46,100 --> 00:25:46,980 Quindi fissare Neil. 732 00:25:46,980 --> 00:25:48,740 Ricordate che, un minuto o così fa. 733 00:25:48,740 --> 00:25:51,680 >> Ma come ho fatto a trovare il prossimo elemento più piccolo? 734 00:25:51,680 --> 00:25:54,830 E 'n meno 1, meno 2 o n davvero, dal numero di passi. 735 00:25:54,830 --> 00:25:55,440 Quindi OK. 736 00:25:55,440 --> 00:25:57,390 Così ho fatto N meno 2. 737 00:25:57,390 --> 00:25:57,600 D'accordo. 738 00:25:57,600 --> 00:25:59,130 In modo che si sente un po 'meglio. 739 00:25:59,130 --> 00:25:59,730 D'accordo. 740 00:25:59,730 --> 00:26:03,270 Quanti passi la prossima volta per trovare il numero tre? 741 00:26:03,270 --> 00:26:04,420 Così n meno 4. 742 00:26:04,420 --> 00:26:07,670 Quindi è in diminuzione, uno in meno calpestare ogni iterazione. 743 00:26:07,670 --> 00:26:08,740 Quindi questo fa sentire meglio, giusto? 744 00:26:08,740 --> 00:26:13,450 Se l'ultima volta è stato circa N volte n, questa volta è n meno 1, più n meno 745 00:26:13,450 --> 00:26:16,500 2, più n meno 3, più n meno 4, punti, puntini, puntini. 746 00:26:16,500 --> 00:26:18,750 Ma se vi ricordate dal tuo liceo libri di testo, il piccolo trucchi 747 00:26:18,750 --> 00:26:24,380 pagina al fondo che ha formule, se si sommano questa serie di numeri, 748 00:26:24,380 --> 00:26:31,280 qual è il numero totale di passi sarà che prendo qui? 749 00:26:31,280 --> 00:26:36,580 >> Questo è uno di quelli, come, n meno 1, n volte, diviso per 2. 750 00:26:36,580 --> 00:26:39,040 Quindi, fammi vedere se riesco a tirare questo per un momento. 751 00:26:39,040 --> 00:26:42,230 E di nuovo, io sono una specie di arrotondamento alcuni numeri solo per mantenere la nostra vita semplice, 752 00:26:42,230 --> 00:26:47,830 ma se ricordo bene, è qualcosa di simile, se Faccio N meno 1 cose, allora n meno 753 00:26:47,830 --> 00:26:53,570 2, quindi n meno 3, e 'approssimativamente qualcosa di simile su 2, e se io 754 00:26:53,570 --> 00:26:55,510 moltiplicare questo fuori, questo è effettivamente quadrato n. 755 00:26:55,510 --> 00:26:58,940 Che non si sente troppo bene. n minus n sopra 2. 756 00:26:58,940 --> 00:27:00,350 >> Ma ecco la cosa. 757 00:27:00,350 --> 00:27:03,720 In informatica, quando i problemi inizia a farsi interessante è quando n 758 00:27:03,720 --> 00:27:04,700 diventa veramente grande. 759 00:27:04,700 --> 00:27:08,110 E quando n diventa molto grande, di cui questi valori sta per dominare tutto 760 00:27:08,110 --> 00:27:09,750 degli altri? 761 00:27:09,750 --> 00:27:10,990 E 'una specie di n al quadrato, giusto? 762 00:27:10,990 --> 00:27:13,340 Sì, dividendo per 2 è piuttosto buona. 763 00:27:13,340 --> 00:27:16,740 Ma se si parla di miliardi di pezzi di dati, o migliaia di miliardi di 764 00:27:16,740 --> 00:27:18,700 pezzi di dati, ok, quindi si è due volte più veloce. 765 00:27:18,700 --> 00:27:22,440 Ma chi se ne frega se quel numero grande, se questo fattore è quello che ottiene 766 00:27:22,440 --> 00:27:23,040 grande e più grande. 767 00:27:23,040 --> 00:27:25,990 E sicuramente, ha più di una differenza di questo ragazzo. 768 00:27:25,990 --> 00:27:29,120 Così, anche se voi siete giusto, il secondo algoritmo, che chiameremo 769 00:27:29,120 --> 00:27:32,970 ordinamento per selezione, è, nel mondo reale, un po 'più veloce potenzialmente, perché io sono 770 00:27:32,970 --> 00:27:35,360 prendendo sempre meno passaggi ogni volta. 771 00:27:35,360 --> 00:27:37,340 >> Non è davvero fondamentalmente più veloce. 772 00:27:37,340 --> 00:27:41,430 Perché se in realtà giochiamo questo per grandi valori di n, a fine 773 00:27:41,430 --> 00:27:44,750 il giorno, per n abbastanza grande, è ancora andando a sentire piuttosto lento. 774 00:27:44,750 --> 00:27:46,770 Beh, mi permetta di prendere una ultimo passaggio a questo. 775 00:27:46,770 --> 00:27:48,920 Questo è quello che io chiamerei selection sort. 776 00:27:48,920 --> 00:27:51,040 Can you guys azzerare voi per l'ultima volta? 777 00:27:51,040 --> 00:27:53,550 E in questo ultimo caso, io vado di proporre qualcosa 778 00:27:53,550 --> 00:27:54,970 chiamato insertion sort. 779 00:27:54,970 --> 00:27:57,470 Insertion sort essere, concettualmente, un po 'diverso. 780 00:27:57,470 --> 00:28:00,980 >> Piuttosto che andare avanti e indietro e selezionando l'elemento più piccolo, io sono 781 00:28:00,980 --> 00:28:05,030 solo andando a trattare con ciascuno di questi ragazzi come loro che incontro, e inserisco 782 00:28:05,030 --> 00:28:06,850 li nella loro corretta posizione. 783 00:28:06,850 --> 00:28:10,160 Quindi ho solo intenzione di iniziare con Grazia, e vedo che lei è il numero quattro. 784 00:28:10,160 --> 00:28:11,720 Da dove viene il numero quattro appartiene? 785 00:28:11,720 --> 00:28:14,940 Non ho iniziato smistamento nulla, così Grazia ottiene di rimanere lì. 786 00:28:14,940 --> 00:28:18,355 E ora ho intenzione di rivendicare, se si potesse fare un passo a destra, questo 787 00:28:18,355 --> 00:28:21,650 la mia lista ordinata, questo è il mio indifferenziati lista rimanente. 788 00:28:21,650 --> 00:28:23,260 Così ora ho intenzione di procedere prossimo, e qual è il tuo nome? 789 00:28:23,260 --> 00:28:23,700 >> : Branson. 790 00:28:23,700 --> 00:28:24,150 >> DAVID J. MALAN: Branson. 791 00:28:24,150 --> 00:28:25,375 Così Branson è il numero due. 792 00:28:25,375 --> 00:28:27,490 Quindi ho intenzione di portarvi fuori per un momento. 793 00:28:27,490 --> 00:28:30,940 E ora, dove si appartiene in questo array? 794 00:28:30,940 --> 00:28:32,360 Quindi, per il diritto di grazia. 795 00:28:32,360 --> 00:28:35,670 Quindi, di nuovo, siamo un po 'fare Grazia fare un sacco di lavoro qui. 796 00:28:35,670 --> 00:28:37,290 Dove ci metteremo? 797 00:28:37,290 --> 00:28:40,120 Quindi stiamo andando a scivolare voi la a sinistra, ed inserire Branson lì. 798 00:28:40,120 --> 00:28:41,680 Ma ora io sostengo che avete finito. 799 00:28:41,680 --> 00:28:43,240 Ma notate, non sto usando più spazio. 800 00:28:43,240 --> 00:28:45,130 E 'ancora due elementi qui, 5 qui. 801 00:28:45,130 --> 00:28:47,910 Dimensione totale dell'array è 7, quindi sono Non barare, va bene? 802 00:28:47,910 --> 00:28:51,950 >> Così ora abbiamo, con Gabe qui, il numero sei, dove appartieni? 803 00:28:51,950 --> 00:28:52,650 Hai avuto ancora fortuna. 804 00:28:52,650 --> 00:28:53,820 Così si arriva a stare lì. 805 00:28:53,820 --> 00:28:57,210 Basta prendere un leggero passo a destra solo per rendere chiaro che si sta ordinati. 806 00:28:57,210 --> 00:29:00,520 E ora abbiamo Neil nuovo, numero uno, dove vai? 807 00:29:00,520 --> 00:29:03,540 E adesso è qui che inizieremo a vedere che questo algoritmo, se su prima 808 00:29:03,540 --> 00:29:05,950 sguardo, si sente abbastanza intelligente, guardare quello che sta per accadere. 809 00:29:05,950 --> 00:29:07,370 Se si potesse fare un passo avanti. 810 00:29:07,370 --> 00:29:09,260 >> Dove vogliamo mettere Neil? 811 00:29:09,260 --> 00:29:11,830 Così, ovviamente qui, così come arriviamo Neil lì? 812 00:29:11,830 --> 00:29:12,970 Facciamo questo passo-passo. 813 00:29:12,970 --> 00:29:15,620 Gabe, dove devi andare? 814 00:29:15,620 --> 00:29:19,590 Yep, in modo da prendere un grande passo, o di due mezze misure per rendere 815 00:29:19,590 --> 00:29:20,820 un passo in là. 816 00:29:20,820 --> 00:29:21,750 Grazia, dove si va? 817 00:29:21,750 --> 00:29:22,510 Buono. 818 00:29:22,510 --> 00:29:23,500 Così un altro passo. 819 00:29:23,500 --> 00:29:24,960 E, infine, Branson? 820 00:29:24,960 --> 00:29:25,460 Un altro passo. 821 00:29:25,460 --> 00:29:27,190 E ora possiamo mettere Neil in posizione. 822 00:29:27,190 --> 00:29:28,440 >> Così ora, continuare questa logica. 823 00:29:28,440 --> 00:29:32,420 Anche se noi non stiamo spostando Neil oltre, e oltre, e oltre, per metterlo 824 00:29:32,420 --> 00:29:36,420 dove va, nel caso peggiore, la prossimo numero che possiamo incontrare potuto 825 00:29:36,420 --> 00:29:42,220 sia il numero, diciamo, c'era un numero zero, allora stiamo andando a spostare tutti 826 00:29:42,220 --> 00:29:42,730 questi ragazzi. 827 00:29:42,730 --> 00:29:44,950 Supponiamo che ci sia un numero negativo uno, allora dobbiamo spostare 828 00:29:44,950 --> 00:29:46,080 tutti questi ragazzi. 829 00:29:46,080 --> 00:29:48,500 Quindi siamo davvero solo tipo di capovolgimento il problema in giro, in modo tale che siamo 830 00:29:48,500 --> 00:29:52,620 trasferendo la spesa dal processo di selezione così l'inserimento 831 00:29:52,620 --> 00:29:56,930 processo, in modo che voi ragazzi ha appena avuto per spostare approssimativamente N meno qualcosa 832 00:29:56,930 --> 00:29:57,940 numero di passi. 833 00:29:57,940 --> 00:30:01,200 E che il numero di passi è solo andare ad aumentare, come posso selezionare più numeri, 834 00:30:01,200 --> 00:30:04,730 se devo continuare a spintoni voi ragazzi indietro, e indietro, e indietro. 835 00:30:04,730 --> 00:30:08,320 >> Quindi, la cosa triste ora è tutto questo algoritmi sono n al quadrato. 836 00:30:08,320 --> 00:30:10,570 Andiamo avanti e grazie a questi ragazzi, e visualizzare questi un po ' 837 00:30:10,570 --> 00:30:11,090 diversamente. 838 00:30:11,090 --> 00:30:12,312 Molto ben fatto. 839 00:30:12,312 --> 00:30:14,120 >> [Applausi] 840 00:30:14,120 --> 00:30:15,030 >> D'accordo. 841 00:30:15,030 --> 00:30:16,280 Ci si va. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Grazie per - 844 00:30:18,470 --> 00:30:19,190 >> BRANSON: [incomprensibile] mantenere i numeri. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. MALAN: No, si può mantenere i numeri pure. 846 00:30:21,990 --> 00:30:23,440 D'accordo. 847 00:30:23,440 --> 00:30:24,100 Ben fatto. 848 00:30:24,100 --> 00:30:25,300 D'accordo. 849 00:30:25,300 --> 00:30:30,510 Così vediamo se ora non possiamo riassumere più rapidamente, e più visivamente, 850 00:30:30,510 --> 00:30:33,410 esattamente quello che è appena successo qui come segue. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Ho intenzione di andare avanti e tirare su Firefox. 853 00:30:38,770 --> 00:30:41,310 Ci colleghiamo questa dimostrazione sul sito web del corso. 854 00:30:41,310 --> 00:30:43,870 Java è un po 'fastidioso per ottenere lavoro in alcuni browser in questi giorni. 855 00:30:43,870 --> 00:30:46,760 Quindi, se non giocate con questo a casa, rendi conto che potrebbe essere necessario utilizzare Firefox 856 00:30:46,760 --> 00:30:47,990 per farlo funzionare. 857 00:30:47,990 --> 00:30:50,440 E che cosa ho intenzione di fare con questo dimostrazione è la seguente. 858 00:30:50,440 --> 00:30:54,875 >> In fondo, ho un sacco di opzioni di menu, tra un inizio e una 859 00:30:54,875 --> 00:30:55,840 arresto. 860 00:30:55,840 --> 00:30:59,450 Inoltre, per inciso, sembra che ci sia un bug in questi programmi, per cui si 861 00:30:59,450 --> 00:31:03,720 non può effettivamente vedere l'avvio o di arresto a meno che non si tiene premuto il tasto Comando o Alt 862 00:31:03,720 --> 00:31:06,560 plus e lo zoom in, che curiosamente si mostra più pulsanti. 863 00:31:06,560 --> 00:31:09,090 Quindi, solo FYI se si gioca con questo a casa. 864 00:31:09,090 --> 00:31:12,870 Ora ho intenzione di fare clic su Avvia in appena un momento, dopo aver specificato un ritardo, 865 00:31:12,870 --> 00:31:16,810 come, a 200 millesimi di secondo qui, solo così possiamo vedere cosa succede. 866 00:31:16,810 --> 00:31:20,180 >> Quindi io sostengo che questa è una visualizzazione del primo algoritmo 867 00:31:20,180 --> 00:31:23,730 questi ragazzi hanno fatto, bubble sort, in base al quale ci siamo scambiati le persone pair-wise. 868 00:31:23,730 --> 00:31:27,490 L'intuizione fondamentale di questa visualizzazione è che l'altezza delle barre 869 00:31:27,490 --> 00:31:30,510 rappresenta la dimensione del numero. 870 00:31:30,510 --> 00:31:32,210 Così la più alta è la barra, grande il numero. 871 00:31:32,210 --> 00:31:33,680 Shorter al bar, più piccolo è il numero. 872 00:31:33,680 --> 00:31:38,630 E se ci fate caso, stiamo attraversando la prima iterazione di questo algoritmo, 873 00:31:38,630 --> 00:31:42,620 scambiando i numeri grandi e piccoli, in modo che il piccolo numero viene prima e 874 00:31:42,620 --> 00:31:44,280 il grande numero va a destra. 875 00:31:44,280 --> 00:31:48,770 >> E non appena si ottiene la fine della matrice di di molti più numeri di sette, siamo 876 00:31:48,770 --> 00:31:49,900 intenzione di andare di nuovo all'inizio. 877 00:31:49,900 --> 00:31:51,140 E anticipare questo. 878 00:31:51,140 --> 00:31:54,860 All'estrema sinistra, quel piccolo ragazzo sta andando per scambiare di lato, e questo 879 00:31:54,860 --> 00:31:56,010 processo si ripete. 880 00:31:56,010 --> 00:31:59,450 Ora questa visualizzazione diventa rapidamente noioso, così mi permetta di andare avanti e di fermo 881 00:31:59,450 --> 00:32:04,170 esso, cambiare il ritardo qualcosa di molto più veloce solo per ottenere ora, un'idea di 882 00:32:04,170 --> 00:32:05,060 questo algoritmo. 883 00:32:05,060 --> 00:32:07,840 >> Così, anche se ho accelerato in su, questo è come aggiornare il mio processore, l'acquisto di 884 00:32:07,840 --> 00:32:08,580 un nuovo computer. 885 00:32:08,580 --> 00:32:12,980 Non ho cambiato radicalmente la mia algoritmo, ma si può davvero vedere di più 886 00:32:12,980 --> 00:32:16,800 chiaramente che con gli esseri umani, che il grande numeri sono zampillante per la parte superiore, 887 00:32:16,800 --> 00:32:20,900 ed i piccoli numeri sono gorgogliare fino al fondo. 888 00:32:20,900 --> 00:32:22,390 E adesso questa cosa qui allineati. 889 00:32:22,390 --> 00:32:25,260 E per inciso, nelle piazze, non c'è solo alcuni contabilità lì a 890 00:32:25,260 --> 00:32:28,010 aiutano a contare quanti confronti, o quante swap hanno 891 00:32:28,010 --> 00:32:28,950 effettivamente stato fatto. 892 00:32:28,950 --> 00:32:30,750 >> Beh, proviamo uno di gli altri che abbiamo visto. 893 00:32:30,750 --> 00:32:37,116 Lasciatemi clicco su bubble sort qui, e mi permetta di scegliere, e questa pagina web intera 894 00:32:37,116 --> 00:32:38,936 è un po 'bacato. 895 00:32:38,936 --> 00:32:41,155 Consente di accettare il rischio ed eseguirlo nuovamente. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Ecco fatto. 898 00:32:45,030 --> 00:32:47,180 Allora, facciamo selection sort. 899 00:32:47,180 --> 00:32:49,140 Io non so perché il menu appare laggiù. 900 00:32:49,140 --> 00:32:54,070 Facciamo lo zoom per rimediare bug, cambiare questo a 50. 901 00:32:54,070 --> 00:32:56,020 Ah, facciamo effettivamente fare più velocemente. 902 00:32:56,020 --> 00:32:59,160 Cinque millisecondi o giù di lì, e iniziare. 903 00:32:59,160 --> 00:33:00,470 >> Quindi questo è il selection sort. 904 00:33:00,470 --> 00:33:03,070 Così ancora una volta, pensare a quello che abbiamo ha fatto con gli umani qui. 905 00:33:03,070 --> 00:33:08,490 Siamo passati attraverso l'array e selezionato l'elemento più piccolo di nuovo, 906 00:33:08,490 --> 00:33:09,250 e ancora, e ancora. 907 00:33:09,250 --> 00:33:11,110 Ora io affermo che era ancora piuttosto male. 908 00:33:11,110 --> 00:33:15,010 E 'stato ancora n quadrato, prendere o lasciare, ma era, nel mondo reale, un po ' 909 00:33:15,010 --> 00:33:18,280 più veloce, perché ero davvero prendendo leggermente meno passaggi ogni volta. 910 00:33:18,280 --> 00:33:19,800 Ma stiamo parlando solo quello? 911 00:33:19,800 --> 00:33:21,830 Forse 40 o giù di barre di qui? 912 00:33:21,830 --> 00:33:23,200 Non stiamo parlando di 40 milioni di euro. 913 00:33:23,200 --> 00:33:27,430 Quindi non è del tutto chiaro per me che era in effetti un guadagno significativo. 914 00:33:27,430 --> 00:33:32,530 >> Vorrei ora tornare indietro e cambiare il nostro terzo algoritmo, che è stato selezionare 915 00:33:32,530 --> 00:33:33,180 insertion sort. 916 00:33:33,180 --> 00:33:36,380 E ora è davvero bacato perché il Menu realtà non dovrebbe essere lì. 917 00:33:36,380 --> 00:33:40,840 Così ora ci scorrere indietro fino qui e iniziare questo algoritmo. 918 00:33:40,840 --> 00:33:43,270 Whoop, start e stop. 919 00:33:43,270 --> 00:33:47,160 Quindi questo tipo di ha un modello piuttosto ad essa, per cui siamo di nuovo 920 00:33:47,160 --> 00:33:50,240 inserendo gli umani, o in questo caso, le barre nella 921 00:33:50,240 --> 00:33:52,620 la loro posizione appropriata. 922 00:33:52,620 --> 00:33:55,430 Ed è già fatto prima Mi voltai. 923 00:33:55,430 --> 00:33:58,940 Ma anche questa, in teoria, è ancora n quadrato. 924 00:33:58,940 --> 00:34:01,430 >> Così vediamo se non siamo in grado di riassumere questi come segue. 925 00:34:01,430 --> 00:34:04,750 Ho intenzione di andare avanti e solo per dare noi una sorta di modo comune di parlare 926 00:34:04,750 --> 00:34:08,489 di queste cose, mi presento solo un po 'di notazione qui. 927 00:34:08,489 --> 00:34:12,480 Stai per vedere qualcosa chiamato big O, perché è letteralmente un grande 928 00:34:12,480 --> 00:34:16,320 O. E questo è un modo che un computer scienziato o un matematico usa anche 929 00:34:16,320 --> 00:34:19,230 per descrivere il tempo di esecuzione di qualche algoritmo. 930 00:34:19,230 --> 00:34:21,400 Quanti passi ci si effettivamente prendere? 931 00:34:21,400 --> 00:34:25,080 >> Ora ho intenzione di mettere in imbarazzo me stesso con la mia scrittura qui in un attimo. 932 00:34:25,080 --> 00:34:29,020 Ma mi permetta di andare avanti e dire che questa sarà la grande O qui. 933 00:34:29,020 --> 00:34:33,610 E mi permetta di introdurre un altro simbolo, un omega capitale. 934 00:34:33,610 --> 00:34:37,080 Omega sarà il contrario, essenzialmente, di grande O. considerando che la grande O 935 00:34:37,080 --> 00:34:40,790 mezzi, nel caso peggiore, quanto tempo potrebbe prendere qualche algoritmo, in 936 00:34:40,790 --> 00:34:43,480 termini di n, omega sta per essere quanto tempo si potrebbe 937 00:34:43,480 --> 00:34:45,409 prendere nel migliore dei casi. 938 00:34:45,409 --> 00:34:48,090 E vedremo che cosa intendiamo per migliore dei casi in un attimo. 939 00:34:48,090 --> 00:34:49,940 >> Quindi cerchiamo di iniziare qualcosa di semplice. 940 00:34:49,940 --> 00:34:54,719 Vorrei iniziare con una ricerca lineare. 941 00:34:54,719 --> 00:34:55,679 Quindi non smistamento. 942 00:34:55,679 --> 00:34:58,000 Chiameremo questa ricerca lineare. 943 00:34:58,000 --> 00:35:01,140 E ora, fare un po ' tavolo fuori. 944 00:35:01,140 --> 00:35:06,600 E ora, nel caso della ricerca lineare, nel peggiore dei casi, il numero di passi è 945 00:35:06,600 --> 00:35:11,770 andando a prendere me per trovare una numero di scelta arbitraria? 946 00:35:11,770 --> 00:35:14,540 E c'è n porte totali o n numeri totali. 947 00:35:14,540 --> 00:35:15,940 Caso peggiore. 948 00:35:15,940 --> 00:35:18,800 Quanti passi sto andando ad avere per prendere per trovare il numero 50 in un array 949 00:35:18,800 --> 00:35:20,830 di n porte? 950 00:35:20,830 --> 00:35:21,410 E perché? 951 00:35:21,410 --> 00:35:23,680 Perché potrebbe essere tutto il modo più sulla fine. 952 00:35:23,680 --> 00:35:27,120 Così tanto come Jennifer incontrato, il numero 50 era tutta la strada sopra, quindi in 953 00:35:27,120 --> 00:35:30,760 il peggior ricerca lineare caso è grande O di n, si dirà. 954 00:35:30,760 --> 00:35:33,430 >> E il caso migliore, se si ottiene veramente fortunati? 955 00:35:33,430 --> 00:35:36,200 E 'solo andando a fare un passo, o un numero costante di passi. 956 00:35:36,200 --> 00:35:37,830 Così si descrivono che, come 1. 957 00:35:37,830 --> 00:35:39,010 Quindi questo è abbastanza buono. 958 00:35:39,010 --> 00:35:41,210 Ora, cosa succede se abbiamo fatto qualcosa di come ricerca binaria? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Ricerca in modo binario, nel peggiore caso, ha preso quanto tempo? 961 00:35:47,846 --> 00:35:49,250 >> [Interponendo VOCI] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. MALAN: Quindi, in realtà, ho sentito in un paio di posti. 963 00:35:51,310 --> 00:35:56,390 Quindi in realtà è log n, prendere o lasciare, perché come si divide la lista in due 964 00:35:56,390 --> 00:36:00,730 ancora, e ancora, e ancora, siamo in grado di trovare, in ultima analisi, il valore, 965 00:36:00,730 --> 00:36:04,750 se è lì, ma vi è una cattura. 966 00:36:04,750 --> 00:36:08,590 Qual è il presupposto che dobbiamo dare per scontato per la ricerca binaria? 967 00:36:08,590 --> 00:36:09,700 Deve essere ordinato. 968 00:36:09,700 --> 00:36:12,770 Non è risolto, è possibile dividere la cosa a nuovo e di nuovo a metà, e si 969 00:36:12,770 --> 00:36:15,490 può andare a sinistra, e si può andare a destra, e si può andare a destra ea sinistra, ma sei 970 00:36:15,490 --> 00:36:18,070 non andare a trovare l'elemento se l'elenco non è ordinato, perché 971 00:36:18,070 --> 00:36:18,790 si potrebbe perdere. 972 00:36:18,790 --> 00:36:22,120 Perché la tua euristico, per andare a sinistra o di diritto sta per essere viziato se è 973 00:36:22,120 --> 00:36:23,420 infatti non ordinati. 974 00:36:23,420 --> 00:36:26,110 Quindi c'è una sorta di costo nascosto a utilizzare qualcosa di simile. 975 00:36:26,110 --> 00:36:29,250 >> Ora, andiamo nel nostro ordinamento algoritmi non ricerca - 976 00:36:29,250 --> 00:36:31,140 Oh, in realtà andiamo in questo vuoto. 977 00:36:31,140 --> 00:36:33,190 Ricerca binaria nel migliore dei casi? 978 00:36:33,190 --> 00:36:36,290 E 'anche uno se accade solo per essere nel molto centro della matrice, o 979 00:36:36,290 --> 00:36:37,810 al centro del libro di telefono. 980 00:36:37,810 --> 00:36:39,710 Ora facciamo bubble sort. 981 00:36:39,710 --> 00:36:42,570 Quindi, di nuovo, ora stiamo entrando nella specie, non le ricerche. 982 00:36:42,570 --> 00:36:47,220 >> Nel peggiore dei casi, quanti passi ci siamo pretesa bubble sort è andare a prendere? 983 00:36:47,220 --> 00:36:48,410 n al quadrato. 984 00:36:48,410 --> 00:36:49,200 Quindi ho intenzione di disegnare quella. 985 00:36:49,200 --> 00:36:51,710 Ooh, la mia scrittura sembra anche peggio quando è previsto che grande. 986 00:36:51,710 --> 00:36:52,510 D'accordo. 987 00:36:52,510 --> 00:36:53,570 Ecco, questo è n quadrato. 988 00:36:53,570 --> 00:36:59,460 E nel caso migliore di bubble sort, quanti passi sta andando a prendere? 989 00:36:59,460 --> 00:37:00,980 1, ho sentito. 990 00:37:00,980 --> 00:37:01,760 >> SPEAKER 1: n. 991 00:37:01,760 --> 00:37:03,286 >> DAVID J. MALAN: n, ho sentito. 992 00:37:03,286 --> 00:37:04,200 >> SPEAKER 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> DAVID J. MALAN: 2, ho sentito. 994 00:37:05,010 --> 00:37:06,670 Sento 3? 995 00:37:06,670 --> 00:37:07,080 D'accordo. 996 00:37:07,080 --> 00:37:11,390 Così ho sentito 1, n, 2, ma Riprendiamo a parte almeno il primo di quelli 997 00:37:11,390 --> 00:37:12,330 suggerimenti, 1. 998 00:37:12,330 --> 00:37:15,370 Non è un cattivo istinto, perché tipo segue un modello qui. 999 00:37:15,370 --> 00:37:19,670 Ma se ci vuole solo 1 passo, come nel mondo, ho potuto affermare che l'elenco 1000 00:37:19,670 --> 00:37:22,900 è ordinato, perché se sto solo permesso di prendere 1 passo, il numero di elementi 1001 00:37:22,900 --> 00:37:25,230 Potevo controllare per essere sicuri? 1002 00:37:25,230 --> 00:37:28,270 Beh, solo 1, che significa che c'è n meno 1 elementi che potrebbero essere fuori 1003 00:37:28,270 --> 00:37:31,310 ordine, e sto solo andando sulla fede dopo guardando 1 elemento che la 1004 00:37:31,310 --> 00:37:31,850 cosa è ordinato. 1005 00:37:31,850 --> 00:37:33,930 Quindi 1 non è corretto qui. 1006 00:37:33,930 --> 00:37:35,710 Così minimamente, quanti devo guardare? 1007 00:37:35,710 --> 00:37:36,680 >> [Interponendo VOCI] 1008 00:37:36,680 --> 00:37:40,160 >> DAVID J. MALAN: n meno 1, o in realtà, n, perché ho bisogno di guardare ogni 1009 00:37:40,160 --> 00:37:42,190 elemento per assicurarsi che non è fuori servizio. 1010 00:37:42,190 --> 00:37:44,750 Ma ancora una volta, saremo specie di onda nostra mani ai numeri più piccoli e 1011 00:37:44,750 --> 00:37:47,100 assumono che, come n diventa grande, sono poco interessante comunque. 1012 00:37:47,100 --> 00:37:48,380 Ecco, questo è bubble sort. 1013 00:37:48,380 --> 00:37:49,830 E ora, facciamo questi ultimi due. 1014 00:37:49,830 --> 00:37:53,520 L'ordinamento per selezione, e poi ci fare insertion sort. 1015 00:37:53,520 --> 00:37:57,160 E poi ci lascerà a bocca menti con qualcosa di molto 1016 00:37:57,160 --> 00:37:58,926 migliore di tutti questi. 1017 00:37:58,926 --> 00:38:00,410 D'accordo. 1018 00:38:00,410 --> 00:38:04,700 >> Che cosa è il caso peggiore in esecuzione momento della selezione sorta? 1019 00:38:04,700 --> 00:38:05,680 >> SPEAKER 4: n al quadrato. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. MALAN: piazza n, sto sentendo. 1021 00:38:06,710 --> 00:38:09,790 Ma perché n squadrato, intuitivamente? 1022 00:38:09,790 --> 00:38:11,170 >> SPEAKER 4: Perché abbiamo appena fatto. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. MALAN: Perché abbiamo appena fatto. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Buona risposta. 1026 00:38:13,380 --> 00:38:16,660 Ma intuitivamente, perché è la selezione tipo n al quadrato? 1027 00:38:16,660 --> 00:38:18,980 Che cosa abbiamo a che fare ancora e ancora? 1028 00:38:18,980 --> 00:38:22,570 Abbiamo dovuto tenere la scansione attraverso, sono la più piccola, sei l' 1029 00:38:22,570 --> 00:38:24,020 più piccolo, sei il più piccolo. 1030 00:38:24,020 --> 00:38:27,480 E concesso, siamo stati in grado di prendere n passi, allora N meno 1, quindi n meno 2. 1031 00:38:27,480 --> 00:38:30,700 Ma se si aggiungono quelli di tipo tutto in su, o prendere sul fede che ho aggiunto 1032 00:38:30,700 --> 00:38:34,810 loro in anticipo, otteniamo circa n quadrato meno alcuni numeri più piccoli. 1033 00:38:34,810 --> 00:38:36,730 Quindi ho intenzione di chiamare questo quadrato n. 1034 00:38:36,730 --> 00:38:39,530 Ma con selezione sorta nel migliore caso, quanti passi è 1035 00:38:39,530 --> 00:38:40,632 andando a prendere me? 1036 00:38:40,632 --> 00:38:41,840 >> SPEAKER 5: [incomprensibile] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. MALAN: E 'purtroppo ancora n al quadrato, giusto? 1038 00:38:44,350 --> 00:38:49,590 Perché se sto scegliendo il più piccolo elemento, e abbiamo avuto sette persone qui, 1039 00:38:49,590 --> 00:38:53,280 So solo che, una volta che ottengo il molto finale, che ho trovato il più piccolo 1040 00:38:53,280 --> 00:38:55,670 numero, dovunque lui o lei può essere stato. 1041 00:38:55,670 --> 00:38:58,820 Ma come faccio a trovare il prossimo numero più piccolo? 1042 00:38:58,820 --> 00:39:00,160 Devo fare un altro passaggio. 1043 00:39:00,160 --> 00:39:04,810 Quindi nel caso migliore, qual è la ingresso alla selezione sorta? 1044 00:39:04,810 --> 00:39:07,830 Si tratta di una lista già sorta, il numero uno, numero due, numero tre, numero quattro. 1045 00:39:07,830 --> 00:39:08,600 Ma io sono un computer. 1046 00:39:08,600 --> 00:39:10,190 Posso guardare soltanto ad un cosa alla volta. 1047 00:39:10,190 --> 00:39:12,465 Non posso ordinare di fare un passo indietro come un essere umano e dire, 1048 00:39:12,465 --> 00:39:14,030 ooh, questo sembra corretto. 1049 00:39:14,030 --> 00:39:17,580 >> Posso giudicare solo la correttezza in ordinamento per selezione selezionando il 1050 00:39:17,580 --> 00:39:18,370 numero più piccolo. 1051 00:39:18,370 --> 00:39:21,390 Ma anche se trovo il numero uno in primo luogo, se io non so niente altro circa 1052 00:39:21,390 --> 00:39:24,460 gli altri numeri, che non lo faccio, tutto quello che So che sono stato consegnato un array 1053 00:39:24,460 --> 00:39:27,930 o un insieme di porte dietro le quali sono numeri, l'unico modo che conosco che uno 1054 00:39:27,930 --> 00:39:28,680 era il più piccolo? 1055 00:39:28,680 --> 00:39:32,440 Se ho fin qui e mi rendo conto, accidenti, uno era davvero il più piccolo. 1056 00:39:32,440 --> 00:39:34,870 >> Ma come faccio quindi determinare che due è il prossimo più piccolo? 1057 00:39:34,870 --> 00:39:38,350 Facendo la stessa inefficienza ancora e ancora. 1058 00:39:38,350 --> 00:39:42,210 Così alla fine, con insertion sort, come, nel caso peggiore, 1059 00:39:42,210 --> 00:39:44,990 abbiamo detto si svolge? 1060 00:39:44,990 --> 00:39:49,100 Anch'esso è n quadrato. 1061 00:39:49,100 --> 00:39:53,020 E per quanto riguarda il caso migliore? 1062 00:39:53,020 --> 00:39:56,282 Lasceremo che come un cliffhanger. 1063 00:39:56,282 --> 00:40:00,090 Ci riempiamo in quel vuoto la prossima volta, ma prima vorrei propongo di 1064 00:40:00,090 --> 00:40:02,620 fondamentalmente fare meglio di tutti questi, va bene? 1065 00:40:02,620 --> 00:40:05,220 >> Quindi, pensare di persona ciò che l'inserimento sorta Sarà. 1066 00:40:05,220 --> 00:40:06,910 Beh, non era molto drammatico, perché io sono l'unico 1067 00:40:06,910 --> 00:40:08,970 che ha visto il cambiamento. 1068 00:40:08,970 --> 00:40:09,620 Wow. 1069 00:40:09,620 --> 00:40:10,420 OK. 1070 00:40:10,420 --> 00:40:12,615 Quindi qui abbiamo un po ' dimostrazione diversa. 1071 00:40:12,615 --> 00:40:16,580 Se io zoomare qui, vedrete che il sinistra abbiamo bubble sort, nel 1072 00:40:16,580 --> 00:40:20,740 mezzo abbiamo ordinamento per selezione, e il l'estrema destra, abbiamo qualcosa che 1073 00:40:20,740 --> 00:40:23,380 Non ho guardato ancora chiamata merge sort. 1074 00:40:23,380 --> 00:40:26,080 Ma consideriamo quello che siamo stati facendo qui finora oggi. 1075 00:40:26,080 --> 00:40:29,200 Quando Jennifer prima volta sul palco, siamo passati attraverso la matrice di numeri 1076 00:40:29,200 --> 00:40:33,750 ancora, e ancora, con la ricerca lineare, e abbiamo avuto tempo di esecuzione lineare, grande O 1077 00:40:33,750 --> 00:40:35,100 di n, per così dire. 1078 00:40:35,100 --> 00:40:41,000 >> Quando noi ora consideriamo la prima settimana di classe, quando avevamo dividere e conquistare, 1079 00:40:41,000 --> 00:40:43,740 e noi avevamo la rubrica strappo, e Jennifer, e noi collettivamente 1080 00:40:43,740 --> 00:40:47,500 sfruttato questa intuizione fondamentale, che era quello di ripetere te stesso più e più volte da 1081 00:40:47,500 --> 00:40:50,930 in qualche modo gettare via, buttare via, buttare via, metà del problema, o 1082 00:40:50,930 --> 00:40:55,320 generalmente, dividendo un problema a metà, e poi trattare il pezzo più piccolo di 1083 00:40:55,320 --> 00:40:59,630 il problema come concettualmente equivalente per l'altro, abbiamo in qualche modo fatto 1084 00:40:59,630 --> 00:41:00,910 fondamentalmente meglio. 1085 00:41:00,910 --> 00:41:04,720 Ma con bubble sort, con selezione specie, con insertion sort, abbiamo può 1086 00:41:04,720 --> 00:41:06,560 non tali intuizioni che Jennifer ha fatto. 1087 00:41:06,560 --> 00:41:10,220 Abbiamo praticamente appena tornati a piedi e via un sacco di volte, e abbiamo 1088 00:41:10,220 --> 00:41:12,650 cose modificato un po ', lo swapping in questo ordine, forse 1089 00:41:12,650 --> 00:41:13,730 l'inserimento o la selezione. 1090 00:41:13,730 --> 00:41:16,950 Ma alla fine della giornata, ho fatto un sacco di camminata goffa avanti e indietro. 1091 00:41:16,950 --> 00:41:21,160 Non abbiamo davvero qualcosa di leva intelligente come Jennifer ha fatto come dividendo 1092 00:41:21,160 --> 00:41:22,040 e conquistando. 1093 00:41:22,040 --> 00:41:25,620 >> Così merge sort, invece, che abbiamo non vedrà fino alla prossima settimana, sta andando 1094 00:41:25,620 --> 00:41:29,540 di sfruttare l'idea chiave dividendo l'ingresso, e poi dimezzare, e quindi 1095 00:41:29,540 --> 00:41:30,580 dimezzare, e poi dimezzare. 1096 00:41:30,580 --> 00:41:34,590 E ad ogni iterazione di tale ciclo, ordinamento la metà sinistra e destra 1097 00:41:34,590 --> 00:41:38,200 metà, poi la metà sinistra della metà sinistra, e la metà destra della sinistra, poi 1098 00:41:38,200 --> 00:41:40,990 la metà sinistra della metà destra, e la metà destra della metà destra. 1099 00:41:40,990 --> 00:41:42,840 E ripetendo più e più volte. 1100 00:41:42,840 --> 00:41:46,170 >> Così vedrete questo visivamente, ma questo è ciò che ci attende la prossima settimana. 1101 00:41:46,170 --> 00:41:49,760 E, in generale, quando si pensa un po ' po 'più difficile su tale problema. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Abbiamo n quadrato sulla sinistra, n quadrato nel mezzo, e n 1104 00:41:57,970 --> 00:41:59,400 log N sulla destra. 1105 00:41:59,400 --> 00:42:00,590 Quindi c'è il tuo vero colpo di scena. 1106 00:42:00,590 --> 00:42:02,040 Ci vediamo il Lunedi. 1107 00:42:02,040 --> 00:42:05,163 >> [Applausi]