1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> SPEAKER: Va bene, questo è CS50. 3 00:00:14,910 --> 00:00:19,020 Questa è la fine di tre settimane, e se non avete approfittato già, 4 00:00:19,020 --> 00:00:21,790 sanno che ci sarà il pranzo questo Venerdì, come al solito, dove 5 00:00:21,790 --> 00:00:25,430 si può godere di buona conversazione e cibo a Fire and Ice 6 00:00:25,430 --> 00:00:27,980 con alcuni dei CS50 di personale e compagni di classe. 7 00:00:27,980 --> 00:00:30,170 Andate a questo URL qui. 8 00:00:30,170 --> 00:00:33,420 >> Ora si può ricordare, o si potrebbe presto essere a conoscenza, 9 00:00:33,420 --> 00:00:35,970 queste cose qui, che sono riportati alla fine 10 00:00:35,970 --> 00:00:37,850 del semestre per molte classi. 11 00:00:37,850 --> 00:00:40,870 Il cosiddetto esame blu libri, in cui scrivete le vostre risposte agli esami. 12 00:00:40,870 --> 00:00:44,240 Ora ho qui 26 tale libri blu, su ciascuno di essi 13 00:00:44,240 --> 00:00:47,580 è scritto un nome, da A a Z. E infatti i nomi sono così semplici, A 14 00:00:47,580 --> 00:00:50,490 attraverso Z. E uno dei gli obiettivi a portata di mano oggi 15 00:00:50,490 --> 00:00:53,910 sta per essere quello di continuare quello abbiamo iniziato il Lunedi, che non è 16 00:00:53,910 --> 00:00:57,830 tanto guardando il codice, ma in realtà guardando idee e di problem solving. 17 00:00:57,830 --> 00:01:00,170 Uno degli obiettivi e promesse di questo corso 18 00:01:00,170 --> 00:01:02,985 è quello di insegnare a pensare in modo più attenzione, più metodicamente, 19 00:01:02,985 --> 00:01:05,400 e per risolvere i problemi più efficiente. 20 00:01:05,400 --> 00:01:09,526 E infatti, possiamo farlo davvero senza nemmeno toccare una riga di codice. 21 00:01:09,526 --> 00:01:12,150 Così ho un paio di elefanti qui oggi, arancione e blu, 22 00:01:12,150 --> 00:01:15,780 se potessimo ottenere un volontario, forse da più indietro del solito. 23 00:01:15,780 --> 00:01:18,070 Che ne dite proprio lì, vieni giù. 24 00:01:18,070 --> 00:01:24,180 L'obiettivo di cui sta per essere a aiutare più amministrare questo esame qui. 25 00:01:24,180 --> 00:01:24,935 Come ti chiami? 26 00:01:24,935 --> 00:01:25,768 >> PUBBLICO: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 SPEAKER: Mary Beth, vieni su. 28 00:01:27,560 --> 00:01:29,560 Mi permetta di ottenere il microfono qui per voi. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Piacere di conoscerti. 31 00:01:32,880 --> 00:01:34,005 >> PUBBLICO: Piacere di conoscerti. 32 00:01:34,005 --> 00:01:36,790 SPEAKER: Va bene, così ho qui i libri blu da A a Z, 33 00:01:36,790 --> 00:01:41,680 e ho intenzione di far finta che Ho uno degli studenti, 34 00:01:41,680 --> 00:01:45,770 e stanno arrivando in qualche modo casuale alla fine di un blocco esame tre ore 35 00:01:45,770 --> 00:01:49,400 così che stanno finendo in qualche ordine semi-casuale come questo. 36 00:01:49,400 --> 00:01:54,510 Ora il vostro lavoro in un attimo sta andando essere-- questo è in realtà il modo in cui ottengono 37 00:01:54,510 --> 00:01:56,820 trasformato in alla fine di la classe, più probabile. 38 00:01:56,820 --> 00:02:01,120 Il tuo lavoro ora sta per essere, piuttosto semplicemente, di ordinare questi libri blu per noi 39 00:02:01,120 --> 00:02:05,220 dalla A alla Z. 40 00:02:05,220 --> 00:02:08,400 >> PUBBLICO: Oh, questo è andando a prendere per sempre. 41 00:02:08,400 --> 00:02:13,747 >> SPEAKER: E guarderemo come si esegue questa operazione, nessuna pressione. 42 00:02:13,747 --> 00:02:15,330 PUBBLICO: No, nessuna pressione o nulla. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> SPEAKER: E per il divertimento, mettiamo un timer. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> PUBBLICO: Tanto divertimento, tanto divertimento. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> SPEAKER: Posso tenere il microfono per voi. 49 00:02:38,574 --> 00:02:40,240 Va bene, abbiamo appena raddoppiato la nostra velocità. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Così, nel frattempo, mi permetta di pongo che cosa è andando ad essere la domanda per Mary Beth 52 00:02:49,060 --> 00:02:51,540 è quello che sta facendo, come è lei va di risolvere questo? 53 00:02:51,540 --> 00:02:54,040 E in effetti, si potrebbe non avere mai pensato a qualcosa 54 00:02:54,040 --> 00:02:57,440 così semplice come quando si sceglie up 26 libri come questo, 55 00:02:57,440 --> 00:02:59,350 che non hanno una naturale ordinando a loro. 56 00:02:59,350 --> 00:03:01,335 Qual è il processo che effettivamente utilizzati? 57 00:03:01,335 --> 00:03:03,770 E 'abbastanza casuale solo scegliere il primo che si vede 58 00:03:03,770 --> 00:03:05,250 e metterlo al suo posto? 59 00:03:05,250 --> 00:03:09,680 Sei tu prima di spostare le mani intorno Alla ricerca di un poi cerca di B? 60 00:03:09,680 --> 00:03:11,722 Non si prende un'occhiata a un coppia di loro affiancati 61 00:03:11,722 --> 00:03:14,680 e dire, aspetta un minuto, questo non è giusto, e poi scambiare l'ordine? 62 00:03:14,680 --> 00:03:16,960 Abbiamo visto già il Lunedi che c'è un certo numero di modi 63 00:03:16,960 --> 00:03:22,140 in cui possiamo farlo, e anzi come ci avviciniamo alla fine qui, 64 00:03:22,140 --> 00:03:26,360 Vorrei prendere nota forse di ciò che Mary Beth sta facendo. 65 00:03:26,360 --> 00:03:30,040 Abbiamo un paio di pali sembra, un più grande, tre più piccoli. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> PUBBLICO: Li sto ordinando quando trovo due lettere 68 00:03:36,415 --> 00:03:39,540 che io conosco sono insieme in una sequenza, Li ho messi insieme in modo che io non lo faccio 69 00:03:39,540 --> 00:03:42,915 devono preoccuparsi di mantenere traccia di un'intera fila di libri. 70 00:03:42,915 --> 00:03:45,706 E 'solo, oh, A è prima, Ho questo stack qui. 71 00:03:45,706 --> 00:03:47,580 SPEAKER: Così, quasi come pezzi di un puzzle che 72 00:03:47,580 --> 00:03:49,860 hanno la forma giusta per combaciare con l'altro. 73 00:03:49,860 --> 00:03:51,026 PUBBLICO: Praticamente, sì. 74 00:03:51,026 --> 00:03:55,320 SPEAKER: OK, eccellente. 75 00:03:55,320 --> 00:03:59,850 E ora ciascuno di questi pali è presumibilmente ordinati? 76 00:03:59,850 --> 00:04:00,990 >> PUBBLICO: Sì. 77 00:04:00,990 --> 00:04:09,900 >> SPEAKER: Va bene, dalla A alla Z. Tutti a destra, complimenti, avete fatto. 78 00:04:09,900 --> 00:04:11,461 Avete la vostra scelta. 79 00:04:11,461 --> 00:04:11,960 Blue? 80 00:04:11,960 --> 00:04:13,530 Va bene, vi ringrazio per questo. 81 00:04:13,530 --> 00:04:16,679 Così Mary Beth ha proposto quello che il suo approccio è stato, 82 00:04:16,679 --> 00:04:19,720 ma ciò che è un altro approccio come si potrebbe andare sull'ordinamento queste cose? 83 00:04:19,720 --> 00:04:21,130 Che cosa avresti fatto? 84 00:04:21,130 --> 00:04:24,060 Il record da battere sarebbe stato un minuto e 50 secondi o giù di lì, 85 00:04:24,060 --> 00:04:26,039 oltre a quelli che ho dimenticato di contare. 86 00:04:26,039 --> 00:04:27,080 Che cosa avresti fatto? 87 00:04:27,080 --> 00:04:27,579 Sì? 88 00:04:27,579 --> 00:04:28,735 PUBBLICO: Prendere la pila. 89 00:04:28,735 --> 00:04:29,776 Inizia dall'inizio. 90 00:04:29,776 --> 00:04:32,284 Controllare i documenti. 91 00:04:32,284 --> 00:04:36,586 E se quella superiore è maggiore che, forse, sono, 92 00:04:36,586 --> 00:04:38,980 quello inferiore è superiore, quindi cambiare. 93 00:04:38,980 --> 00:04:41,300 >> SPEAKER: OK, quindi iniziare nella parte superiore e la parte inferiore, 94 00:04:41,300 --> 00:04:43,716 e poi lavorare il vostro senso verso l'interno così, scambiando loro? 95 00:04:43,716 --> 00:04:46,580 OK, quindi un po 'simile in spirito di bubble sort, 96 00:04:46,580 --> 00:04:49,160 ma scegliendo gli estremi Non le coppie adiacenti. 97 00:04:49,160 --> 00:04:52,080 Ma il corto di esso è che non c'è sicuramente un sacco di modi diversi 98 00:04:52,080 --> 00:04:54,210 potremmo fare questo, e francamente, penso che tipo di 99 00:04:54,210 --> 00:04:55,700 adottato un paio di approcci, giusto? 100 00:04:55,700 --> 00:05:00,567 Hai fatto una sorta di quattro pali ordinati, e poi effettivamente li fuse insieme. 101 00:05:00,567 --> 00:05:02,650 E questo è, oserei dire, un altro tecnica del tutto. 102 00:05:02,650 --> 00:05:06,950 Non hai trattata come una grande pila, si è diviso il problema in quattro quad, 103 00:05:06,950 --> 00:05:09,820 se si vuole, e quindi in qualche modo li fuse alla fine. 104 00:05:09,820 --> 00:05:13,410 >> Quindi consideriamo, in ultima analisi, in quale altro modo potremmo farlo. 105 00:05:13,410 --> 00:05:15,860 Abbiamo formalizzato la nozione di bubble sort ultima volta, 106 00:05:15,860 --> 00:05:18,780 e bubble sort richiamo è stato un algoritmo che abbiamo visualizzato 107 00:05:18,780 --> 00:05:22,640 con otto dei tuoi compagni di classe qui, apparentemente ordinati in modo casuale in un primo momento. 108 00:05:22,640 --> 00:05:26,110 E poi abbiamo deciso due a due, se due elementi sono in ordine, 109 00:05:26,110 --> 00:05:26,950 semplicemente scambiare. 110 00:05:26,950 --> 00:05:28,930 Quindi, quattro e due sono ovviamente fuori uso, 111 00:05:28,930 --> 00:05:31,080 così quei due compagni di classe scambiato posizione. 112 00:05:31,080 --> 00:05:35,390 E poi abbiamo ripetuto con quattro e sei, poi sei e otto, ad ogni iterazione, 113 00:05:35,390 --> 00:05:36,980 spostando verso destra. 114 00:05:36,980 --> 00:05:42,590 >> Quindi, dato otto persone, quante coppie paragoni Ho fatto mentre si cammina da 115 00:05:42,590 --> 00:05:45,220 sinistra a destra in una tale iterazione? 116 00:05:45,220 --> 00:05:48,410 Quanti paragoni? 117 00:05:48,410 --> 00:05:49,197 Sette, giusto? 118 00:05:49,197 --> 00:05:51,405 Perché se ci sono otto persone, ma avete la coppia 119 00:05:51,405 --> 00:05:53,880 loro e si mantiene in movimento un salto a destra, 120 00:05:53,880 --> 00:05:56,060 non stai andando ad avere otto paragoni perché non si può confrontare 121 00:05:56,060 --> 00:05:59,226 un elemento contro se stessa, o sarebbe solo essere inutile, in modo da avere sette. 122 00:05:59,226 --> 00:06:01,290 Oppure più in generale, se abbiamo n persone, abbiamo 123 00:06:01,290 --> 00:06:04,300 fare n meno 1 confronti con bubble sort. 124 00:06:04,300 --> 00:06:08,150 >> Quindi prendiamo in considerazione ora come buono o male bubble sort realtà era, e provare 125 00:06:08,150 --> 00:06:13,570 per dare a noi stessi vocabolario con che agli algoritmi critica come questa, 126 00:06:13,570 --> 00:06:14,430 e presto la nostra. 127 00:06:14,430 --> 00:06:16,970 Quindi il primo passaggio attraverso bubble sort, la prima volta 128 00:06:16,970 --> 00:06:20,909 Ho camminato da sinistra a destra attraverso il fase, me n meno 1 confronti preso. 129 00:06:20,909 --> 00:06:22,950 E questo sta andando essere il mio unità di misura, giusto? 130 00:06:22,950 --> 00:06:26,170 Ero un po 'a parlare e passeggiare, un po 'veloce, un po' lento, 131 00:06:26,170 --> 00:06:29,300 così contare il mio numero di secondi non è particolarmente significativo, 132 00:06:29,300 --> 00:06:32,260 ma contando il numero di operazioni che ho fatto il Lunedi, 133 00:06:32,260 --> 00:06:35,900 confronto tra due persone, che si sente come una bella unità di misura. 134 00:06:35,900 --> 00:06:40,980 >> Così n meno 1 passi la prima volta, ma poi che cosa è successo dopo? 135 00:06:40,980 --> 00:06:46,610 Qual è il vantaggio di un solo passaggio attraverso una lista a pena di non ordinato? 136 00:06:46,610 --> 00:06:49,840 Cosa mi puoi raccontare l'elemento che era tutta la strada laggiù? 137 00:06:49,840 --> 00:06:51,300 Sì? 138 00:06:51,300 --> 00:06:52,870 Questo è stato l'elemento più grande, giusto? 139 00:06:52,870 --> 00:06:55,710 Numero otto, anche se lei iniziato qui, ogni volta che 140 00:06:55,710 --> 00:06:57,860 il suo rispetto nei confronti un vicino di casa, ha mantenuto 141 00:06:57,860 --> 00:07:00,480 gorgogliare a destra lato della lista. 142 00:07:00,480 --> 00:07:02,710 E infatti, ecco dove l'algoritmo prende il nome. 143 00:07:02,710 --> 00:07:07,630 >> Ora da questa logica, il numero di confronti bisogno Faccio la seconda volta 144 00:07:07,630 --> 00:07:09,800 Faccio che passa da sinistra a destra? 145 00:07:09,800 --> 00:07:10,730 n meno 2, giusto? 146 00:07:10,730 --> 00:07:14,297 Sarebbe solo sprecando il mio tempo, se mi mantenere il confronto otto contro qualcuno 147 00:07:14,297 --> 00:07:16,630 altro perché sappiamo già lei era nel posto giusto. 148 00:07:16,630 --> 00:07:19,760 Ecco, questo è un po 'un ottimizzazione, in modo che il passaggio successivo 149 00:07:19,760 --> 00:07:23,899 sta per essere più n meno di due passi, dove n è il numero di persone. 150 00:07:23,899 --> 00:07:26,940 Ora è possibile tipo di estrapolare, anche se non sei un informatico, 151 00:07:26,940 --> 00:07:27,680 come finirà. 152 00:07:27,680 --> 00:07:31,259 Alla fine di questo algoritmo, presumibilmente hai solo un confronto a sinistra. 153 00:07:31,259 --> 00:07:33,800 Dovete tipo di fissare la inizio della lista nel caso di due 154 00:07:33,800 --> 00:07:36,540 e uno sono fuori ordine e dovrebbe essere uno e due, 155 00:07:36,540 --> 00:07:40,330 quindi questa battuta fuori a più 1 confronto finale. 156 00:07:40,330 --> 00:07:44,500 >> Ora il dot, dot, dot tipo di onde è mani in alcuni dei dettagli più succosa, 157 00:07:44,500 --> 00:07:46,452 ma facciamo solo andare avanti e semplificare. 158 00:07:46,452 --> 00:07:48,660 Se vi ricordate da alta scuola, francamente, molti di voi 159 00:07:48,660 --> 00:07:50,340 avuto libri di matematica che aveva un piccolo foglietto 160 00:07:50,340 --> 00:07:52,550 sulla copertina anteriore o il coperchio posteriore che vi ha mostrato 161 00:07:52,550 --> 00:07:56,400 sommatorie che serie come questo in ultima analisi, ha aggiunto fino a. 162 00:07:56,400 --> 00:07:59,600 Nel caso generale, se si dispone di un variabile come n, e in effetti questo, 163 00:07:59,600 --> 00:08:01,634 se hai guardato il tuo vecchia scuola libro di matematica, 164 00:08:01,634 --> 00:08:04,050 si vedrebbe che questo in realtà aggiunge a questa somma qui, 165 00:08:04,050 --> 00:08:07,970 n volte n meno 1 tutto diviso 2. 166 00:08:07,970 --> 00:08:11,172 Quindi per ora lasciatemi stipula le questo è vero, quindi su un atto di fede, 167 00:08:11,172 --> 00:08:12,880 che è ciò che questo riassume fino a, e abbiamo potuto 168 00:08:12,880 --> 00:08:14,341 dimostrare che in un caso più generale. 169 00:08:14,341 --> 00:08:15,590 Ma ora cerchiamo di espandere questo fuori. 170 00:08:15,590 --> 00:08:19,920 Quindi cerchiamo di moltiplicare questo fuori, così che è n squadrato, meno n, tutto diviso per 2. 171 00:08:19,920 --> 00:08:23,200 Questo è davvero n al quadrato, diviso per 2, meno n sopra 2, 172 00:08:23,200 --> 00:08:25,010 così che è tutto bello e interessante. 173 00:08:25,010 --> 00:08:27,060 Ma cosa succede se si ora plug-in di un valore? 174 00:08:27,060 --> 00:08:29,724 Supponiamo che io non avevo otto persone, ma dicono un milione. 175 00:08:29,724 --> 00:08:31,890 E un milione solo perché si tratta di un numero abbastanza grande, 176 00:08:31,890 --> 00:08:34,039 cerchiamo di spina che in e vediamo cosa succede. 177 00:08:34,039 --> 00:08:39,039 Quindi, se io inserisco un milione in quella formula Ho intenzione di ottenere un milione quadrato, 178 00:08:39,039 --> 00:08:42,868 diviso 2, meno una milioni di euro, diviso per 2. 179 00:08:42,868 --> 00:08:44,159 Ora che cosa è che sta per eguagliare? 180 00:08:44,159 --> 00:08:47,354 Quindi 500 miliardi, meno di 500.000. 181 00:08:47,354 --> 00:08:49,270 E se io in realtà faccio che la matematica, significa che 182 00:08:49,270 --> 00:08:53,920 che l'ordinamento di un milione le persone con il bubble sort 183 00:08:53,920 --> 00:09:01,800 mi potrebbe prendere 499.999.500.000 passi o confronti, alla fine, 184 00:09:01,800 --> 00:09:02,900 stiamo solo estrapolando. 185 00:09:02,900 --> 00:09:06,860 >> Che si sente abbastanza lento, ma francamente misura un ingresso particolare 186 00:09:06,860 --> 00:09:09,160 in questo modo, non è tutto ciò che racconto. 187 00:09:09,160 --> 00:09:14,050 Ma infatti suggerisce che come n diventa sempre più grande, questo algoritmo 188 00:09:14,050 --> 00:09:16,280 tipo di sente peggio e peggio, o si ha realmente 189 00:09:16,280 --> 00:09:20,450 cominciare a sentire il dolore di quella elevamento a potenza, che n al quadrato, 190 00:09:20,450 --> 00:09:21,770 che aggiunge abbastanza veloce. 191 00:09:21,770 --> 00:09:25,340 E questo dettaglio non è perso su persone, infatti 192 00:09:25,340 --> 00:09:29,640 alcuni anni fa, un certo senatore che era campagna, si sedette per un colloquio 193 00:09:29,640 --> 00:09:32,180 con Google Eric Schmidt, CEO al momento, 194 00:09:32,180 --> 00:09:36,380 ed è stato sfidato con una domanda proprio come stiamo esplorando oggi. 195 00:09:36,380 --> 00:09:38,468 Diamo uno sguardo. 196 00:09:38,468 --> 00:09:45,280 >> [RIPRODUZIONE VIDEO] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Tu sei qui a Google, e mi piace 198 00:09:48,560 --> 00:09:53,382 pensare di presidenza come un colloquio di lavoro. 199 00:09:53,382 --> 00:09:56,434 Ora, è difficile ottenere un lavoro come presidente, 200 00:09:56,434 --> 00:09:58,100 e si sta andando attraverso i rigori adesso. 201 00:09:58,100 --> 00:10:01,860 E 'anche difficile ottenere un lavoro presso Google. 202 00:10:01,860 --> 00:10:05,490 Abbiamo domande, e noi chiedere ai nostri candidati domande, 203 00:10:05,490 --> 00:10:09,770 e questo è da Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 Cosa-- pensate voi ragazzi che sono scherzo, è proprio qui. 205 00:10:14,760 --> 00:10:17,930 Qual è il modo più efficace per ordinare un milione di numeri interi a 32 bit? 206 00:10:17,930 --> 00:10:21,800 207 00:10:21,800 --> 00:10:24,350 >> -Well-- 208 00:10:24,350 --> 00:10:25,200 >> Mi dispiace, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> No, no, no. 210 00:10:27,400 --> 00:10:30,700 Penso che il bubble sort sarebbe il modo sbagliato di procedere. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> -Dai, Che gli ha detto questo? 213 00:10:38,180 --> 00:10:40,590 Non ho visto del computer scienza nel vostro sfondo. 214 00:10:40,590 --> 00:10:42,130 >> -We've Ottenuto le nostre spie in là. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Chiediamo un diverso domanda intervista. 217 00:10:48,444 --> 00:10:49,300 >> [FINE RIPRODUZIONE VIDEO] 218 00:10:49,300 --> 00:10:52,290 >> SPEAKER: Così parlando numeri specifici, però, 219 00:10:52,290 --> 00:10:53,890 non sta per essere tutto ciò che utile. 220 00:10:53,890 --> 00:10:56,810 Non è una lezione di vita che bolla tipo, data un milione di ingressi, 221 00:10:56,810 --> 00:10:58,590 potrebbe richiedere fino a 500 miliardi di passi. 222 00:10:58,590 --> 00:11:01,120 Non si può davvero generalizzare Anche efficacemente da quella 223 00:11:01,120 --> 00:11:03,560 e prendere buone decisioni di progettazione durante la scrittura dei programmi. 224 00:11:03,560 --> 00:11:07,070 Quindi concentriamoci però su come potremmo semplificare questo risultato. 225 00:11:07,070 --> 00:11:11,780 >> Così ho evidenziato in giallo qui il risultato di n al quadrato diviso per 2, 226 00:11:11,780 --> 00:11:14,330 così un milione quadrato diviso 2, e poi 227 00:11:14,330 --> 00:11:16,710 Ho evidenziato quello che la risposta definitiva è stata 228 00:11:16,710 --> 00:11:20,180 una volta che abbiamo sottratto off n diviso per 2. 229 00:11:20,180 --> 00:11:24,850 E la domanda che sto per fare oggi è, chi diavolo se ne frega se si sottrae off 230 00:11:24,850 --> 00:11:30,060 un po 'vecchio n sopra 2 quando il primo parte di questa formula è tanto più grande? 231 00:11:30,060 --> 00:11:33,910 Domina l'altro termine, n al quadrato diviso per 2 232 00:11:33,910 --> 00:11:37,510 è così molto più grande, in modo chiaro, come n diventa grande come un milione, 233 00:11:37,510 --> 00:11:41,450 che c'è davvero una grande differenza a Alla fine della giornata tra 500 miliardi 234 00:11:41,450 --> 00:11:45,730 e 499.999.500.000? 235 00:11:45,730 --> 00:11:46,349 Non proprio. 236 00:11:46,349 --> 00:11:48,640 E così quello che stiamo andando a fare come gli informatici è 237 00:11:48,640 --> 00:11:53,270 ignorare quei termini di ordine inferiore e prendere qualcosa come questo e davvero 238 00:11:53,270 --> 00:11:56,050 solo di semplificare al termine che sta andando alla materia. 239 00:11:56,050 --> 00:12:00,315 I nostri più grandi insiemi di dati diventano, il più grande nostri database ottengono, le pagine web più 240 00:12:00,315 --> 00:12:02,690 dobbiamo cercare, il più amici che si hanno su Facebook. 241 00:12:02,690 --> 00:12:07,340 >> Come n diventa più grande, siamo davvero andando a prendersi cura del più grande 242 00:12:07,340 --> 00:12:11,560 termine in qualsiasi analisi di le nostre prestazioni di algoritmi. 243 00:12:11,560 --> 00:12:16,230 E ho intenzione di dire, sai cosa, bubble sort è dell'ordine di O grande, 244 00:12:16,230 --> 00:12:18,060 dell'ordine di n al quadrato. 245 00:12:18,060 --> 00:12:20,090 Non è esattamente n Squared come abbiamo visto, 246 00:12:20,090 --> 00:12:22,060 ma chi se ne frega davvero su quei termini più piccole, 247 00:12:22,060 --> 00:12:24,390 e francamente, che davvero se ne frega se dividiamo da 2? 248 00:12:24,390 --> 00:12:25,870 Questo è solo un fattore costante. 249 00:12:25,870 --> 00:12:29,480 Ed è 500 miliardi contro 250 miliardi davvero così grande di un affare? 250 00:12:29,480 --> 00:12:32,190 Potevo solo aspettare un anno, lasciare il mio computer portatile letteralmente 251 00:12:32,190 --> 00:12:34,810 ottenere due volte più veloce in hardware, e che tipo di differenza 252 00:12:34,810 --> 00:12:36,650 appena va via naturalmente nel tempo. 253 00:12:36,650 --> 00:12:39,300 >> Quello che ci interessa è l'espressione, la parte 254 00:12:39,300 --> 00:12:42,489 dell'espressione che sta per variare come il nostro ingresso diventa sempre più grande. 255 00:12:42,489 --> 00:12:45,280 E infatti, nel mondo reale, questo è ciò che sta accadendo sempre più 256 00:12:45,280 --> 00:12:48,330 è gli ingressi ai nostri problemi e algoritmi sono sempre più grande. 257 00:12:48,330 --> 00:12:53,470 Così grande O sarà la notazione, la notazione asintotica, che abbiamo appena 258 00:12:53,470 --> 00:12:57,160 utilizzare come gli informatici per descrivere le prestazioni, o il tempo di esecuzione, 259 00:12:57,160 --> 00:12:58,130 di un algoritmo. 260 00:12:58,130 --> 00:13:00,800 In modo che possiamo confrontare algoritmi su computer diversi scritti 261 00:13:00,800 --> 00:13:04,170 da persone diverse in base alcune metriche fondamentalmente simile 262 00:13:04,170 --> 00:13:07,557 come il numero di confronti che sei fare, o forse il numero di swap 263 00:13:07,557 --> 00:13:08,140 che stai facendo. 264 00:13:08,140 --> 00:13:11,910 >> Quello che non stiamo andando a conta è la quantità di tempo 265 00:13:11,910 --> 00:13:13,981 che passa l'orologio sulla parete tipicamente. 266 00:13:13,981 --> 00:13:16,230 Quello che non stiamo andando a preoccuparsi circa è la quantità di memoria 267 00:13:16,230 --> 00:13:17,820 si sta utilizzando oggi alle almeno, anche se questo è 268 00:13:17,820 --> 00:13:19,370 un'altra risorsa potremmo misurare. 269 00:13:19,370 --> 00:13:23,610 Stiamo andando a cercare di basare le nostre analisi solo su le operazioni di base, quelli, 270 00:13:23,610 --> 00:13:25,930 francamente, che potete vedere più visivamente. 271 00:13:25,930 --> 00:13:30,700 Quindi, con qualcosa come grande O di n quadrato, io sostengo che O di n al quadrato 272 00:13:30,700 --> 00:13:35,820 è un limite superiore sul cosiddetto tempo di bubble sort in esecuzione. 273 00:13:35,820 --> 00:13:38,820 In altre parole, se si voluto affermare che non c'è 274 00:13:38,820 --> 00:13:41,370 questo limite superiore al numero di passi un algoritmo può prendere, 275 00:13:41,370 --> 00:13:46,240 sta andando ad essere in grande O di n squadrato in questo caso, un limite superiore. 276 00:13:46,240 --> 00:13:49,710 >> Cosa succede se invece cambio il storia di essere non su bubble sort, 277 00:13:49,710 --> 00:13:50,910 ma questo limite superiore. 278 00:13:50,910 --> 00:13:54,030 Riuscite a pensare a un algoritmo che abbiamo esaminato già 279 00:13:54,030 --> 00:13:59,530 il cui limite superiore, massima misura del tempo o operazioni, 280 00:13:59,530 --> 00:14:04,300 sarebbe detto di essere delimitata da n, una funzione lineare, 281 00:14:04,300 --> 00:14:07,260 non un quadratica che è curvo? 282 00:14:07,260 --> 00:14:10,780 Che cosa è un algoritmo che prende sempre più 283 00:14:10,780 --> 00:14:12,860 che come n passi, o Passi 2n, 3n o gradini? 284 00:14:12,860 --> 00:14:13,360 Sì? 285 00:14:13,360 --> 00:14:15,030 >> PUBBLICO: Trovare il maggior numero in un elenco? 286 00:14:15,030 --> 00:14:16,930 >> SPEAKER: Perfetto, trovando il maggior numero in un elenco. 287 00:14:16,930 --> 00:14:18,940 Se mi sono dato una lista di persone per esempio, 288 00:14:18,940 --> 00:14:21,440 ciascuna di chi è in possesso di un numero, qual è il numero massimo 289 00:14:21,440 --> 00:14:23,770 di passi che dovrebbe prendere me, una persona abbastanza intelligente, 290 00:14:23,770 --> 00:14:27,530 per trovare la più grande persona in quella lista? 291 00:14:27,530 --> 00:14:28,100 n, giusto? 292 00:14:28,100 --> 00:14:31,320 Poiché nel caso peggiore, in cui potrebbe essere il più grande valore? 293 00:14:31,320 --> 00:14:32,700 Destra, tutto il senso alla fine. 294 00:14:32,700 --> 00:14:34,575 Quindi, nel caso peggiore limite superiore, potrei 295 00:14:34,575 --> 00:14:36,450 andare fino in fondo qui e di essere come, 296 00:14:36,450 --> 00:14:39,170 oh, ecco il numero otto, o qualsiasi altra cosa che il valore è. 297 00:14:39,170 --> 00:14:41,330 Ora sarebbe solo stupido se ho continuato ad andare, giusto? 298 00:14:41,330 --> 00:14:43,840 Cerco sempre di più elementi se l'ultimo di questi è laggiù? 299 00:14:43,840 --> 00:14:45,340 Quindi sicuramente, n è un limite superiore. 300 00:14:45,340 --> 00:14:47,420 Non ho bisogno di prendere più passaggi di quello. 301 00:14:47,420 --> 00:14:51,580 >> Così che cosa se invece ho proposto che esistono algoritmi in questo mondo che 302 00:14:51,580 --> 00:14:57,750 hanno un tempo di esecuzione che è delimitata da grande O di log n, log n? 303 00:14:57,750 --> 00:15:00,390 Dove abbiamo visto prima? 304 00:15:00,390 --> 00:15:00,890 Sì? 305 00:15:00,890 --> 00:15:03,309 >> PUBBLICO: Nel problema rubrica? 306 00:15:03,309 --> 00:15:04,850 SPEAKER: Come il problema rubrica. 307 00:15:04,850 --> 00:15:07,754 Qual è stata la misura di quanto molto tempo o quante lacrime it 308 00:15:07,754 --> 00:15:10,170 mi ha portato a trovare qualcuno come Mike Smith nella rubrica? 309 00:15:10,170 --> 00:15:13,212 Abbiamo sostenuto che era log n, e anche se non conosce o si è 310 00:15:13,212 --> 00:15:15,170 un po 'confuso ciò che un logaritmo o esponente era, 311 00:15:15,170 --> 00:15:17,650 basta ricordare che log n generalmente si riferisce al processo, 312 00:15:17,650 --> 00:15:20,790 in questo caso, di dividere qualcosa a metà ancora, e ancora, 313 00:15:20,790 --> 00:15:25,790 e ancora, e ancora, tale da diventa sempre più piccolo, come lo fai. 314 00:15:25,790 --> 00:15:28,470 >> Così log di n si riferisce, certo, per esempio la rubrica telefonica, 315 00:15:28,470 --> 00:15:32,662 di ricerca binaria in teoria, quando si aveva le porte virtuali sul tabellone, 316 00:15:32,662 --> 00:15:34,370 o quando Sean era alla ricerca di qualcosa. 317 00:15:34,370 --> 00:15:37,374 Se avesse usato la ricerca binaria, log n sarebbe il limite superiore della quantità 318 00:15:37,374 --> 00:15:38,040 tempo che prende. 319 00:15:38,040 --> 00:15:44,027 Ma quegli algoritmi che correvano in log n assunto quale chiave dettaglio? 320 00:15:44,027 --> 00:15:45,360 Che l'elenco è stato risolto, giusto? 321 00:15:45,360 --> 00:15:47,789 Il tuo algoritmo è sbagliato se l'input non è ordinato, 322 00:15:47,789 --> 00:15:49,830 e ancora si sta utilizzando qualcosa come la ricerca binaria 323 00:15:49,830 --> 00:15:51,704 perché si potrebbe saltare proprio sopra l'elemento 324 00:15:51,704 --> 00:15:53,600 senza rendersi conto che è davvero lì. 325 00:15:53,600 --> 00:15:55,600 >> Ora, che cosa potrebbe significare questo, grande O di uno? 326 00:15:55,600 --> 00:15:59,117 Questo non significa che il vostro algoritmo prende uno e un solo passo, 327 00:15:59,117 --> 00:16:01,200 significa solo che ci vuole un numero costante di passi. 328 00:16:01,200 --> 00:16:04,060 Forse è 1, forse è 10, forse è 1.000, 329 00:16:04,060 --> 00:16:07,750 ma è indipendente da la dimensione del problema. 330 00:16:07,750 --> 00:16:10,850 Non importa quanto grande sia n, un algoritmo di costante di tempo 331 00:16:10,850 --> 00:16:12,747 prende sempre lo stesso numero di passi. 332 00:16:12,747 --> 00:16:15,080 Così che cosa potrebbe essere un algoritmo abbiamo parlato o solo 333 00:16:15,080 --> 00:16:20,418 intuitivamente che viene a voi che corre sempre nella cosiddetta costante di tempo? 334 00:16:20,418 --> 00:16:20,918 Sì? 335 00:16:20,918 --> 00:16:22,001 >> PUBBLICO: Aggiungi due numeri. 336 00:16:22,001 --> 00:16:25,320 SPEAKER: Aggiungi due numeri, 2 più 2 uguale a 4, fatto. 337 00:16:25,320 --> 00:16:27,227 In modo che potrebbe funzionare, che altro? 338 00:16:27,227 --> 00:16:28,560 Che ne dite di mondo più reale, sì? 339 00:16:28,560 --> 00:16:30,686 >> PUBBLICO: Trovare il prima cosa in un elenco. 340 00:16:30,686 --> 00:16:32,810 SPEAKER: Trovare la prima elemento in un elenco, certo. 341 00:16:32,810 --> 00:16:34,540 Abbiamo effettivamente parlato circa già array, 342 00:16:34,540 --> 00:16:36,540 Come si ottiene al primo elemento di un array, 343 00:16:36,540 --> 00:16:40,465 non importa quanto tempo il array è in codice C? 344 00:16:40,465 --> 00:16:43,090 Basta utilizzare come supporto notazione a zero, bam, sei lì. 345 00:16:43,090 --> 00:16:46,120 E infatti gli array, come a parte, Supporto qualcosa di noto 346 00:16:46,120 --> 00:16:49,240 come accesso casuale, random access memoria, perché si può letteralmente 347 00:16:49,240 --> 00:16:50,284 saltare a qualsiasi luogo. 348 00:16:50,284 --> 00:16:52,700 Possiamo farlo ancora più semplicemente siamo in grado di riavvolgere a settimana a zero 349 00:16:52,700 --> 00:16:53,900 quando abbiamo fatto Scratch. 350 00:16:53,900 --> 00:16:59,707 Quanto tempo ci è voluto per la dire blocco Scratch da eseguire? 351 00:16:59,707 --> 00:17:00,790 Basta costante di tempo, giusto? 352 00:17:00,790 --> 00:17:03,960 Di 'qualcosa, dire qualcosa, non importa 353 00:17:03,960 --> 00:17:07,359 Quanto è grande Graffi mondo è, è sempre andando a prendere la stessa quantità di tempo 354 00:17:07,359 --> 00:17:08,490 semplicemente dire qualcosa. 355 00:17:08,490 --> 00:17:11,089 >> Ecco, questo è tempo costante, ma qual è il rovescio della medaglia? 356 00:17:11,089 --> 00:17:13,030 Se questo era superiore limiti, che cosa se vogliamo 357 00:17:13,030 --> 00:17:17,089 per descrivere i limiti inferiori dei nostri algoritmi tempo di esecuzione? 358 00:17:17,089 --> 00:17:19,852 Quasi un caso migliore potenzialmente, se si vuole, 359 00:17:19,852 --> 00:17:23,060 anche se questi termini potrebbero applicarsi al meglio casi, casi più gravi, casi medi più 360 00:17:23,060 --> 00:17:26,359 in generale, ma facciamo solo concentriamoci su limiti inferiori, più in generale. 361 00:17:26,359 --> 00:17:31,920 Che cosa è un algoritmo che ha un limite inferiore di n passi, 362 00:17:31,920 --> 00:17:33,350 o passi 2n, 3n o gradini? 363 00:17:33,350 --> 00:17:36,241 Alcuni fattore di n passi, questo è il suo limite inferiore. 364 00:17:36,241 --> 00:17:36,740 Sì? 365 00:17:36,740 --> 00:17:37,910 >> PUBBLICO: Bubble sort? 366 00:17:37,910 --> 00:17:41,610 >> SPEAKER: Bubble sort prende si minimamente n passi, perché? 367 00:17:41,610 --> 00:17:42,279 Perché? 368 00:17:42,279 --> 00:17:45,320 Perché che inizio a venire da voi intuitivamente, anche se non solo 369 00:17:45,320 --> 00:17:46,530 ancora? 370 00:17:46,530 --> 00:17:47,030 Sì? 371 00:17:47,030 --> 00:17:47,990 >> PUBBLICO: [incomprensibile]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 SPEAKER: Esattamente. 374 00:17:52,360 --> 00:17:55,810 Nella migliore scenario possibile di bubble sort, e un sacco di algoritmi, 375 00:17:55,810 --> 00:17:58,769 se io ti consegno otto persone che sono già ordinati, 376 00:17:58,769 --> 00:18:00,560 sarebbe sciocco per voi, l'algoritmo, 377 00:18:00,560 --> 00:18:02,202 per andare avanti e indietro più di una volta, giusto? 378 00:18:02,202 --> 00:18:04,285 Perché non appena si camminare attraverso la lista una volta, 379 00:18:04,285 --> 00:18:08,090 si dovrebbe capire, oh, ho fatto nessun swap, questo elenco è ordinato, uscita. 380 00:18:08,090 --> 00:18:09,700 Ma che sta andando a prendere n passi. 381 00:18:09,700 --> 00:18:12,033 >> E viceversa, ciò che è un altro modo di pensarci? 382 00:18:12,033 --> 00:18:15,240 Bubble sort è un omega, per così dire, di n, 383 00:18:15,240 --> 00:18:19,050 perché se si guarda meno di n elementi, ciò 384 00:18:19,050 --> 00:18:23,009 è la questione fondamentale lì? 385 00:18:23,009 --> 00:18:24,550 Non sai se è ordinato, a destra. 386 00:18:24,550 --> 00:18:26,800 Noi esseri umani potrebbe sguardo alle otto persone e di essere come, oh, è ordinato, 387 00:18:26,800 --> 00:18:28,430 che non me n passi ha preso, ma lo ha fatto. 388 00:18:28,430 --> 00:18:30,810 I tuoi occhi, anche se si tipo di avere un grande campo visivo, 389 00:18:30,810 --> 00:18:33,184 hai guardato otto elementi, hai guardato otto persone, 390 00:18:33,184 --> 00:18:34,610 che è otto passi efficace. 391 00:18:34,610 --> 00:18:38,612 E solo se dovessi camminare in tutta la Lista do Mi rendo conto, sì, ordinato. 392 00:18:38,612 --> 00:18:41,320 Se mi fermo a pensare a metà strada, tutto a destra, è abbastanza ordinato finora, 393 00:18:41,320 --> 00:18:42,520 quali sono le probabilità non è ordinata? 394 00:18:42,520 --> 00:18:44,186 Che non Algoritmi sarà corretta. 395 00:18:44,186 --> 00:18:46,250 Potrebbe essere più veloce, ma non corretto. 396 00:18:46,250 --> 00:18:48,500 >> Così ora abbiamo un modo di descrivendo un limite inferiore, 397 00:18:48,500 --> 00:18:49,710 e che dire di costante di tempo? 398 00:18:49,710 --> 00:18:54,565 Che cosa è un algoritmo che ha un minore bound sul suo tempo di esecuzione di uno? 399 00:18:54,565 --> 00:18:58,350 1 punto, 2 punti, 10 punti, ma costante, indipendente da n, 400 00:18:58,350 --> 00:18:59,310 la dimensione dell'input? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Sì, in indietro. 403 00:19:04,600 --> 00:19:05,309 >> PUBBLICO: Printf? 404 00:19:05,309 --> 00:19:06,183 SPEAKER: Cosa e 'quello? 405 00:19:06,183 --> 00:19:07,184 PUBBLICO: Printf? 406 00:19:07,184 --> 00:19:07,850 SPEAKER: Printf. 407 00:19:07,850 --> 00:19:08,400 OK, certo. 408 00:19:08,400 --> 00:19:10,720 Quindi ci vuole un numero fisso di passaggi. 409 00:19:10,720 --> 00:19:13,170 E dovrei now-- ora che stiamo parlando di codice C 410 00:19:13,170 --> 00:19:16,040 e non Scratch, qualcosa come dire, con printf, 411 00:19:16,040 --> 00:19:17,710 dovremmo iniziare a ottenere attenzione. 412 00:19:17,710 --> 00:19:21,090 Perché printf fa prendere ingresso, si tratta di una stringa, 413 00:19:21,090 --> 00:19:23,220 e stringhe hanno tecnicamente lunghezza. 414 00:19:23,220 --> 00:19:25,530 Quindi, se ora vogliamo raccogliere su di te, se non ti dispiace, 415 00:19:25,530 --> 00:19:29,430 tecnicamente si potrebbe sostenere che printf non prendere un ingresso di lunghezza variabile, 416 00:19:29,430 --> 00:19:32,270 e sicuramente potrebbe richiedere più tempo per stampare una stringa questo lungo, 417 00:19:32,270 --> 00:19:33,560 di così lunga. 418 00:19:33,560 --> 00:19:36,570 >> Così che cosa se si considera solo il ordinamento e ricerca esempi? 419 00:19:36,570 --> 00:19:40,450 Che dire Mike Smith nel telefono libro, o binario di ricerca più in generale? 420 00:19:40,450 --> 00:19:42,220 Nel migliore dei casi, cosa potrebbe accadere? 421 00:19:42,220 --> 00:19:45,577 Apro la rubrica e, bam, c'è il numero di Mike Smith. 422 00:19:45,577 --> 00:19:46,660 Io lo posso chiamare subito. 423 00:19:46,660 --> 00:19:49,390 >> Fece un passo, forse due passi, ma un numero costante di passi 424 00:19:49,390 --> 00:19:50,230 se ho avuto fortuna. 425 00:19:50,230 --> 00:19:52,570 E, francamente, abbiamo visto in Lunedi il tuo compagno di classe 426 00:19:52,570 --> 00:19:54,710 ottenere abbastanza fortunato due volte di fila. 427 00:19:54,710 --> 00:19:57,050 E questo è stato davvero costante volta in limiti inferiori 428 00:19:57,050 --> 00:20:01,280 l'algoritmo in questione per reperire il numero 50 dietro quelle chiuse 429 00:20:01,280 --> 00:20:01,830 porte. 430 00:20:01,830 --> 00:20:06,400 >> Ora, come un a parte, se si scopre che sia grande O, il limite superiore, 431 00:20:06,400 --> 00:20:09,310 e l'omega, il limite inferiore, sono uno nello stesso, che 432 00:20:09,310 --> 00:20:11,830 è la stessa formula in parentesi, è anche possibile 433 00:20:11,830 --> 00:20:15,170 dire, solo per essere di fantasia, che qualcosa è in theta 434 00:20:15,170 --> 00:20:18,270 di n o theta di qualche altro valore. 435 00:20:18,270 --> 00:20:20,661 Ciò significa proprio quando grande O e omega sono uguali. 436 00:20:20,661 --> 00:20:21,910 Ora, che dire di ordinamento per selezione? 437 00:20:21,910 --> 00:20:23,400 Usiamo questo nuovo vocabolario. 438 00:20:23,400 --> 00:20:27,407 In selection sort, cosa stavamo facendo ancora, e ancora, e ancora? 439 00:20:27,407 --> 00:20:29,990 Stavo andando avanti e indietro attraverso l'elenco, in cerca di chi? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Il numero più piccolo. 442 00:20:34,730 --> 00:20:37,560 >> Così come molti passi, come molti paragoni fatto io 443 00:20:37,560 --> 00:20:43,250 devono fare in modo di capire chi il più piccolo elemento della lista è? 444 00:20:43,250 --> 00:20:44,437 n meno 1, giusto? 445 00:20:44,437 --> 00:20:47,770 Perché se ho appena comincio con quello che sono dato e io comincio a lui o lei a confronto, 446 00:20:47,770 --> 00:20:49,519 allora lui o lei, lo o lei, lui o lei, io 447 00:20:49,519 --> 00:20:52,010 può abbinare solo elementi insieme n meno 1 volte. 448 00:20:52,010 --> 00:20:55,630 Quindi la selezione prende sorta simile n meno 1 passi la prima volta. 449 00:20:55,630 --> 00:20:59,540 >> Quanti passi non mi ci vuole per trovare il secondo elemento più piccolo? 450 00:20:59,540 --> 00:21:02,920 n meno 2, perché io sono di essere stupido se Continuo a guardare le stesse persone 451 00:21:02,920 --> 00:21:06,280 di nuovo se ho già lui selezionato o lei e metterli al loro posto. 452 00:21:06,280 --> 00:21:09,270 E il terzo passo, n meno 3, allora n meno 4. 453 00:21:09,270 --> 00:21:11,020 Abbiamo visto questo modello prima, e anzi 454 00:21:11,020 --> 00:21:13,460 ordinamento per selezione allo stesso modo ha un limite superiore 455 00:21:13,460 --> 00:21:16,210 di n al quadrato se lo facciamo su quella somma. 456 00:21:16,210 --> 00:21:19,790 Qual è il suo limite inferiore, ordinamento per selezione? 457 00:21:19,790 --> 00:21:25,350 Minimamente, quanto la selezione must tempo Ordina prendere, come lo abbiamo definito il Lunedi? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Proporre due opzioni. 460 00:21:30,490 --> 00:21:32,360 Forse è n, come prima. 461 00:21:32,360 --> 00:21:35,040 Forse è n al quadrato, come è ora come limite superiore. 462 00:21:35,040 --> 00:21:35,874 >> PUBBLICO: n quadrato. 463 00:21:35,874 --> 00:21:36,664 SPEAKER: n quadrato. 464 00:21:36,664 --> 00:21:37,368 Perché? 465 00:21:37,368 --> 00:21:40,060 >> PUBBLICO: Perché hai per definire [incomprensibile]. 466 00:21:40,060 --> 00:21:41,510 >> SPEAKER: Esattamente. 467 00:21:41,510 --> 00:21:45,077 Almeno per quanto ho definito ordinamento per selezione era piuttosto ingenuo, andare avanti, 468 00:21:45,077 --> 00:21:46,160 trovare l'elemento più piccolo. 469 00:21:46,160 --> 00:21:47,770 Andare di nuovo, trovare l'elemento più piccolo. 470 00:21:47,770 --> 00:21:49,490 Andare di nuovo, trovare l'elemento più piccolo. 471 00:21:49,490 --> 00:21:51,700 Non c'è nessun tipo di ottimizzazione in là che 472 00:21:51,700 --> 00:21:54,350 potrebbe farmi abortire dopo a n o giù di lì passi. 473 00:21:54,350 --> 00:21:57,080 Così infatti, la selezione sorta, omega di n al quadrato. 474 00:21:57,080 --> 00:22:00,667 >> Che dire di insertion sort, dove ho preso che mi è stato dato, e poi lo lasciai 475 00:22:00,667 --> 00:22:01,750 o lei nel posto giusto? 476 00:22:01,750 --> 00:22:04,958 Poi ho proceduto alla seconda persona, lui o lei piazzati nel posto giusto. 477 00:22:04,958 --> 00:22:07,910 Poi la prossima persona, lasciò lui o lei nel posto giusto. 478 00:22:07,910 --> 00:22:10,537 Si noti che questo è molto lineare, per così dire. 479 00:22:10,537 --> 00:22:12,620 Io sono una linea retta, io sono non andare avanti e indietro, 480 00:22:12,620 --> 00:22:16,080 Non ho mai guardare indietro davvero, ma cosa succede quando lo inserisco 481 00:22:16,080 --> 00:22:20,302 o suo nell'inizio di l'elenco come abbiamo fatto il Lunedi? 482 00:22:20,302 --> 00:22:21,010 Cosa sta succedendo? 483 00:22:21,010 --> 00:22:21,510 Sì? 484 00:22:21,510 --> 00:22:23,122 PUBBLICO: [incomprensibile]. 485 00:22:23,122 --> 00:22:24,830 SPEAKER: Sì, che era la cattura, giusto? 486 00:22:24,830 --> 00:22:26,746 Si potrebbe ricordare da tuoi compagni di classe, se 487 00:22:26,746 --> 00:22:29,670 stavano facendo qualsiasi movimento con i loro piedi, che era un'operazione. 488 00:22:29,670 --> 00:22:33,610 Quindi, se ci fossero tre persone qui e la nuova persona apparteneva modo laggiù, 489 00:22:33,610 --> 00:22:37,360 su un palco lungo come questo, certo, egli o lei potrebbe semplicemente andare fino in fondo. 490 00:22:37,360 --> 00:22:40,074 Ma se stiamo pensando a un computer e un array di memoria, 491 00:22:40,074 --> 00:22:41,990 queste persone stanno andando di avere a mescolare su 492 00:22:41,990 --> 00:22:43,260 per fare spazio a quella persona. 493 00:22:43,260 --> 00:22:46,930 E così che n meno 1 stropiccii, n meno 2 stropiccii, n 494 00:22:46,930 --> 00:22:50,660 meno 3 stropiccii è solo tipo di succedendo dietro di me, non di fronte a me 495 00:22:50,660 --> 00:22:52,710 come prima, in un certo senso. 499 00:22:52,557 --> 00:22:54,640 Ora, come una parte, e come potreste vedere on-line 500 00:22:54,640 --> 00:22:57,699 se si avvia rovistando su tipi, ci sono così tanti quelli diversi 501 00:22:57,699 --> 00:22:59,490 là fuori, alcuni di essi meglio di altri. 502 00:22:59,490 --> 00:23:02,200 Infatti, è uno bogosort che una specie di divertente da guardare in alto. 503 00:23:02,200 --> 00:23:06,650 Bogosort prende un set di numeri o dire un mazzo di carte, 504 00:23:06,650 --> 00:23:09,870 le mescola in modo casuale, e controlla se sono ordinati. 505 00:23:09,870 --> 00:23:12,130 E se no, lo fa di nuovo. 506 00:23:12,130 --> 00:23:14,140 E se no, lo fa di nuovo. 507 00:23:14,140 --> 00:23:15,440 In caso contrario, lo fa di nuovo. 508 00:23:15,440 --> 00:23:17,060 Incredibilmente stupido. 509 00:23:17,060 --> 00:23:19,520 >> E in effetti, se leggi come l'articolo di Wikipedia, 510 00:23:19,520 --> 00:23:21,200 il suo soprannome è stupido sorta. 511 00:23:21,200 --> 00:23:25,180 E alla fine funzionerà, si spera, dato abbastanza tempo, 512 00:23:25,180 --> 00:23:28,240 ma quella quantità di tempo potrebbe richiedere molto tempo. 513 00:23:28,240 --> 00:23:31,650 Quindi, se potessi, di lasciare che le cose di velocità dal esempio di Mary Beth precedenza, 514 00:23:31,650 --> 00:23:35,150 avendo un paio di elementi, ma altri due processori. 515 00:23:35,150 --> 00:23:37,100 Due persone, se si Non mi dispiacerebbe unirsi a me. 516 00:23:37,100 --> 00:23:40,972 Come circa 1 qui, e cerchiamo di go-- nessuno laggiù? 517 00:23:40,972 --> 00:23:41,722 Nessuno laggiù? 518 00:23:41,722 --> 00:23:42,221 Ok. 519 00:23:42,221 --> 00:23:44,190 È con il nero camicia, sì, vieni giù. 520 00:23:44,190 --> 00:23:45,000 Va bene, qual è il tuo nome? 521 00:23:45,000 --> 00:23:45,720 >> PUBBLICO: Peter. 522 00:23:45,720 --> 00:23:46,100 >> SPEAKER: Cosa e 'quello? 523 00:23:46,100 --> 00:23:46,766 >> PUBBLICO: Peter. 524 00:23:46,766 --> 00:23:49,450 SPEAKER: Peter, David, piacere di conoscerti. 525 00:23:49,450 --> 00:23:53,670 Va bene, abbiamo Pietro qui, se si vogliono venire sul tavolo qui. 526 00:23:53,670 --> 00:23:54,550 E qual è il tuo nome? 527 00:23:54,550 --> 00:23:55,216 >> PUBBLICO: Elena. 528 00:23:55,216 --> 00:23:55,970 SPEAKER: Elena. 529 00:23:55,970 --> 00:23:57,030 OK, piacere di conoscerti. 530 00:23:57,030 --> 00:23:58,060 Elena incontrare Peter. 531 00:23:58,060 --> 00:23:59,170 Pietro, Elena. 532 00:23:59,170 --> 00:24:02,290 E avremo bisogno di Andrew up anche qui, per favore. 533 00:24:02,290 --> 00:24:06,107 E la vostra sfida è andare essere quello di ordinare un mazzo di carte. 534 00:24:06,107 --> 00:24:08,190 E se non familiare, ponte di carte dovrebbe in ultima analisi, 535 00:24:08,190 --> 00:24:11,064 essere ordinati un po 'qualcosa di simile questo dove faremo i club, poi 536 00:24:11,064 --> 00:24:13,660 le picche, poi i cuori e diamanti, da asso come uno, 537 00:24:13,660 --> 00:24:15,570 tutta la strada fino al re. 538 00:24:15,570 --> 00:24:20,890 >> Le carte ho intenzione di darvi stanno per essere 52 in quantità. 539 00:24:20,890 --> 00:24:23,160 Stiamo andando allo stesso modo volta che, in un attimo. 540 00:24:23,160 --> 00:24:26,410 Stiamo per lanciare Andrew sullo schermo qui, 541 00:24:26,410 --> 00:24:28,170 in modo da guardare come si esegue questa operazione. 542 00:24:28,170 --> 00:24:31,070 E così che tutto questo è tanto più visibile, 543 00:24:31,070 --> 00:24:33,490 queste sono le carte che ho ricevuto su Amazon. 544 00:24:33,490 --> 00:24:42,861 Quindi sono già in modo casuale risolto, e stiamo andando a volta che si. 545 00:24:42,861 --> 00:24:44,610 E stiamo andando a tenerlo reale questa volta, 546 00:24:44,610 --> 00:24:47,820 quindi stiamo andando a cercare di pressione si perché altrimenti questo otterrà noioso 547 00:24:47,820 --> 00:24:48,460 rapidamente. 548 00:24:48,460 --> 00:24:53,860 Se si potesse procedere a ordinare 52 elementi insieme tramite alcuni mezzi, ora. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> E ancora, come noi guardiamo questi ragazzi fanno quello che, alla fine, 551 00:25:07,180 --> 00:25:10,200 sta per produrre un evidente Di conseguenza, pensare davvero 552 00:25:10,200 --> 00:25:12,962 come stanno facendo ogni, come si potrebbe descrivere. 553 00:25:12,962 --> 00:25:15,045 Perché ancora, questi sono tutti i processi, gli algoritmi 554 00:25:15,045 --> 00:25:17,090 che diamo per scontato come un essere umano. 555 00:25:17,090 --> 00:25:22,349 Ma probabilmente hai avuto per lungo tempo intuizione, molto prima ancora di 556 00:25:22,349 --> 00:25:24,390 pensato di prendere una classe di scienze computer 557 00:25:24,390 --> 00:25:27,223 potrebbe aver avuto l'intuizione con che per risolvere problemi come questo. 558 00:25:27,223 --> 00:25:29,560 Ma una volta che si riconosce i modelli e cominciare 559 00:25:29,560 --> 00:25:32,407 per formalizzare i passi con i quali stai risolvere questi problemi, 560 00:25:32,407 --> 00:25:35,490 troverete che è possibile risolvere molto più interessante e molto più complessa 561 00:25:35,490 --> 00:25:39,190 rapidamente i problemi. 562 00:25:39,190 --> 00:25:42,351 Così qualcuno dal pubblico, che cosa è almeno un elemento dell'algoritmo 563 00:25:42,351 --> 00:25:43,350 che stanno usando qui? 564 00:25:43,350 --> 00:25:44,275 >> PUBBLICO: [incomprensibile] 565 00:25:44,275 --> 00:25:45,150 SPEAKER: Cosa e 'quello? 566 00:25:45,150 --> 00:25:47,062 PUBBLICO: Da vestito. 567 00:25:47,062 --> 00:25:47,770 SPEAKER: By vestito. 568 00:25:47,770 --> 00:25:50,630 Quindi, prima che si discostano tutti i diamanti insieme 569 00:25:50,630 --> 00:25:52,560 sembra, tutte le cuori insieme a quanto pare, 570 00:25:52,560 --> 00:25:56,520 e così via, senza rispetto per i numeri sulle carte. 571 00:25:56,520 --> 00:26:00,900 E ora appaiono, per esempio, da loro ordinamento per numero. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Molto buona. 574 00:26:08,910 --> 00:26:12,370 >> Va bene, quindi che cosa sta per essere il passo finale, allora qui? 575 00:26:12,370 --> 00:26:16,950 Una volta che abbiamo quattro semi ordinati, cosa abbiamo bisogno di fare per i quattro pali 576 00:26:16,950 --> 00:26:20,059 al fine di realizzare uno ordinati ponte, molto semplicemente? 577 00:26:20,059 --> 00:26:21,350 Quindi abbiamo bisogno di unire di nuovo. 578 00:26:21,350 --> 00:26:25,160 >> Quindi c'è un'idea interessante che ancora una volta, oserei dire, è molto intuitivo anche 579 00:26:25,160 --> 00:26:28,140 se si potrebbe mai avere schiaffeggiato quel tipo di etichetta. 580 00:26:28,140 --> 00:26:31,900 Questa nozione fondamentale di divisione il problema non a metà questa volta, 581 00:26:31,900 --> 00:26:33,410 ma almeno in quattro pezzi. 582 00:26:33,410 --> 00:26:36,810 Risolvere praticamente problemi fondamentalmente identici 583 00:26:36,810 --> 00:26:40,480 isolatamente l'uno dall'altro, e poi la fusione dei risultati. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 E, eccellente, fatto. 586 00:26:50,140 --> 00:26:52,140 Va bene, una grande rotonda di applausi, se avessimo potuto. 587 00:26:52,140 --> 00:26:56,480 >> [Applausi] 588 00:26:56,480 --> 00:26:59,740 >> SPEAKER: Non ho idea di quello che ti fare con questi, ma qui si va. 589 00:26:59,740 --> 00:27:01,690 Vi ringrazio tanto. 590 00:27:01,690 --> 00:27:04,660 Vediamo quindi, a due minuti e otto secondi, 591 00:27:04,660 --> 00:27:07,490 se vuoi sfidare i tuoi amici. 592 00:27:07,490 --> 00:27:12,160 Che poi sta per essere un take away da questo 593 00:27:12,160 --> 00:27:13,830 che possiamo sfruttare più in generale? 594 00:27:13,830 --> 00:27:16,080 Beh, ripensare a questo array di numeri, 595 00:27:16,080 --> 00:27:19,060 e ripenso ora ad alcune delle pseudocodice abbiamo scritto in passato, 596 00:27:19,060 --> 00:27:22,080 e questo era il pseudocodice per risolvere il problema rubrica. 597 00:27:22,080 --> 00:27:25,150 Per cui in pseudocodice I enumerato un modo più metodico 598 00:27:25,150 --> 00:27:28,400 di descrivere come ho fatto molto intuitivo algoritmo umano di dividere il telefono 599 00:27:28,400 --> 00:27:31,650 libro a metà, ripetere, ripetere, ripetere, finché non trovo qualcuno come Mike Smith, 600 00:27:31,650 --> 00:27:33,790 se è davvero nella rubrica. 601 00:27:33,790 --> 00:27:37,610 >> Ma ho usato il tipo di quello che io chiamo un approccio molto iterativo qui, 602 00:27:37,610 --> 00:27:42,160 in particolare preavviso linea 8 e la linea 11. 603 00:27:42,160 --> 00:27:46,750 Queste sono prove di un iterativo approccio, un approccio looping, 604 00:27:46,750 --> 00:27:49,040 perché questo è esattamente il comportamento che inducono. 605 00:27:49,040 --> 00:27:52,910 Quelle linee entrambi dicono andare a linea tre, e si può tipo di 606 00:27:52,910 --> 00:27:55,140 pensare che nel tuo occhio della mente come un loop. 607 00:27:55,140 --> 00:27:59,080 Ti sta dicendo di tornare indietro fino al punto tre e ripetere, ancora, e ancora, 608 00:27:59,080 --> 00:28:00,010 e di nuovo. 609 00:28:00,010 --> 00:28:04,410 >> Ma cosa succede se facciamo leva una idea chiave qui che abbiamo fatto non l'ultima volta, 610 00:28:04,410 --> 00:28:10,280 e semplificare la linea 8 e linea 11 ei loro vicini 611 00:28:10,280 --> 00:28:12,840 come solo questo, in giallo. 612 00:28:12,840 --> 00:28:16,480 Non è fondamentale accorciare il pseudocodice molto, 613 00:28:16,480 --> 00:28:20,530 ma è fondamentalmente cambiando la natura del mio algoritmo. 614 00:28:20,530 --> 00:28:24,220 Quello che sto dicendo adesso al punto 7, al punto 10, 615 00:28:24,220 --> 00:28:29,140 sia per la ricerca di Mike nello stesso modo, 616 00:28:29,140 --> 00:28:31,580 ma solo nel fianco la metà o la metà destra. 617 00:28:31,580 --> 00:28:33,420 >> Quindi, in altre parole, se Parto dal punto uno, 618 00:28:33,420 --> 00:28:36,150 prendere rubrica, aperto a metà di rubrica, guardare i nomi, 619 00:28:36,150 --> 00:28:39,010 se Smith è tra Il nome di, chiamare Mike, altro 620 00:28:39,010 --> 00:28:44,340 se Smith è in precedenza nel libro, passo sette la ricerca di Mike nella metà sinistra del libro. 621 00:28:44,340 --> 00:28:47,130 Ma questo tipo di sente come mi sta lasciando appeso, giusto? 622 00:28:47,130 --> 00:28:49,240 In giallo, è un istruzione, ma come faccio 623 00:28:49,240 --> 00:28:51,870 cercare Mike a sinistra metà della rubrica? 624 00:28:51,870 --> 00:28:54,210 Dove devo un algoritmo con il quale ho 625 00:28:54,210 --> 00:28:57,100 può cercare per uno come Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Beh, ci sta guardando in faccia. 627 00:28:58,980 --> 00:29:03,090 Posso letteralmente usare la stessa esatta programma effettivamente andare fino alla cima 628 00:29:03,090 --> 00:29:06,490 di nuovo e ri-esecuzione le stesse linee di codice. 629 00:29:06,490 --> 00:29:10,610 >> Così, anche se questo dovrebbe sentirsi come un po 'di una definizione ciclica 630 00:29:10,610 --> 00:29:13,480 dove si sta rispondendo di qualcuno domanda da appena sorta di chiedere 631 00:29:13,480 --> 00:29:15,990 di nuovo la stessa domanda, come perché, perché, perché? 632 00:29:15,990 --> 00:29:21,580 La realtà è perché abbiamo hardcoded un paio di linee speciali, punto 4, 633 00:29:21,580 --> 00:29:25,320 che è un caso, e il punto 12, che è effettivamente un altro ramo, 634 00:29:25,320 --> 00:29:30,120 perché abbiamo tali misure di ripiego, questo algoritmo terminerà se 635 00:29:30,120 --> 00:29:32,050 trovare Mike, o se non lo facciamo. 636 00:29:32,050 --> 00:29:36,810 Ma nel passo 7 e 10 ora, abbiamo quello che chiameremo un algoritmo ricorsivo. 637 00:29:36,810 --> 00:29:40,420 E ricorsione è infatti un potente idea che è un po 'rompicapo in un primo momento, 638 00:29:40,420 --> 00:29:42,500 che ora possiamo applicare come segue. 639 00:29:42,500 --> 00:29:46,600 >> Merge sort sarà l'ultimo tipo che guardiamo, almeno in classe formalmente. 640 00:29:46,600 --> 00:29:50,040 Ed è fondamentalmente diverso da quelle ultime tre, e certamente 641 00:29:50,040 --> 00:29:52,140 ultimi quattro se includiamo bogosort. 642 00:29:52,140 --> 00:29:54,810 Ecco lo pseudocodice per merge sort. 643 00:29:54,810 --> 00:30:00,170 Quando sull'ingresso di n elementi, così determinato un array di dimensione n, se n è minore di 2, 644 00:30:00,170 --> 00:30:01,040 ritorno. 645 00:30:01,040 --> 00:30:03,610 Allora perché devo che sanità mentale controllare in primo luogo? 646 00:30:03,610 --> 00:30:09,477 Qual è l'implicazione se ti consegno un array di lunghezza n è minore di 2? 647 00:30:09,477 --> 00:30:11,060 E 'già ordinato, ovviamente, giusto? 648 00:30:11,060 --> 00:30:13,640 Poiché l'elenco ha o un elemento, che è banalmente 649 00:30:13,640 --> 00:30:15,180 ordinato perché è l'unica cosa lì. 650 00:30:15,180 --> 00:30:18,138 Oppure, è di dimensioni pari a zero, che significa non c'è niente da ordinare, così per natura 651 00:30:18,138 --> 00:30:18,720 esso è ordinato. 652 00:30:18,720 --> 00:30:20,410 Non c'è proprio niente di male lì. 653 00:30:20,410 --> 00:30:22,310 Ecco, questo è il nostro cosiddetto caso base. 654 00:30:22,310 --> 00:30:24,440 >> Questo è simile nello spirito per quello che abbiamo fatto con Mike. 655 00:30:24,440 --> 00:30:26,023 Se Mike nella rubrica, lo chiamano. 656 00:30:26,023 --> 00:30:27,740 Se non è lì, rinunciare. 657 00:30:27,740 --> 00:30:31,240 È un cosiddetto caso base, per assicurarsi questo algoritmo alla fine della giornata 658 00:30:31,240 --> 00:30:33,540 si fermerà in determinate circostanze. 659 00:30:33,540 --> 00:30:37,890 >> Ma ecco il salto della fede oggi, altrimenti, ordinare la metà sinistra degli elementi, 660 00:30:37,890 --> 00:30:39,740 poi ordinare la destra metà degli elementi, 661 00:30:39,740 --> 00:30:41,189 e poi unire le due metà ordinate. 662 00:30:41,189 --> 00:30:43,230 E qui è dove ci si sente come stiamo copping fuori. 663 00:30:43,230 --> 00:30:46,900 Ti ho chiesto di ordinare n elementi, e sono 664 00:30:46,900 --> 00:30:50,712 dicendo: OK, non è di classificare la sinistra e l'ordinamento del diritto. 665 00:30:50,712 --> 00:30:52,420 Ma che sto dicendo una altra cosa, e questo 666 00:30:52,420 --> 00:30:55,530 è il tema chiave sembra nell'intuizione finora, 667 00:30:55,530 --> 00:30:57,380 c'è questa terza fase della fusione. 668 00:30:57,380 --> 00:31:00,430 Quale pur sembra così stupido in spirito, 669 00:31:00,430 --> 00:31:02,320 come solo unire le cose insieme, sembra 670 00:31:02,320 --> 00:31:05,380 di essere un passo fondamentale verso la riassemblaggio dei due problemi che 671 00:31:05,380 --> 00:31:07,330 sono stati divisi in definitiva a metà. 672 00:31:07,330 --> 00:31:12,090 >> Così merge sort, facciamo questo, se avrete umorismo me, con una dimostrazione in più, 673 00:31:12,090 --> 00:31:14,730 solo così che abbiamo qualche numeri per lavorare con. 674 00:31:14,730 --> 00:31:19,470 Posso scambiare otto lo stress palle per otto persone? 675 00:31:19,470 --> 00:31:29,320 Va bene, come su di voi tre, voi quattro in questa sezione, cinque, sei, e cerchiamo di 676 00:31:29,320 --> 00:31:30,720 do 7, 8, andiamo su. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 OK, sì OK. 679 00:31:36,520 --> 00:31:38,640 Minus 8, ci andiamo, più 1. 680 00:31:38,640 --> 00:31:39,150 Eccellente. 681 00:31:39,150 --> 00:31:42,000 Va bene andiamo su, andiamo dare rapidamente i numeri. 682 00:31:42,000 --> 00:31:50,800 Numero due, numero tre, numero quattro, numero cinque, sei, sette e otto. 683 00:31:50,800 --> 00:31:52,140 Ho fatto otto correttamente questa volta. 684 00:31:52,140 --> 00:31:56,390 >> OK, in modo da andare avanti se si potesse, e cerchiamo di ordinare in ordine originale 685 00:31:56,390 --> 00:31:59,810 che abbiamo avuto ieri che sembrava in questo modo, se non mi dispiacerebbe. 686 00:31:59,810 --> 00:32:03,620 E facciamolo davanti al tavolo. 687 00:32:03,620 --> 00:32:06,510 Va bene, così merge sort. 688 00:32:06,510 --> 00:32:08,820 Questo è dove sta andando per ottenere tipo di interessante, 689 00:32:08,820 --> 00:32:12,800 perché mi sembra di dare me stesso tanto meno informazioni oggi. 690 00:32:12,800 --> 00:32:15,149 >> Così merge sort prima di tutto su input di n elementi, 691 00:32:15,149 --> 00:32:18,440 e ovviamente non è inferiore a due, è otto, quindi ho qualche lavoro da fare. 692 00:32:18,440 --> 00:32:21,140 Così ora mentalmente siamo come una classe sono ora nel ramo altro, 693 00:32:21,140 --> 00:32:22,540 che significa tre passi. 694 00:32:22,540 --> 00:32:25,017 In primo luogo, devo ordinare il metà sinistra degli elementi. 695 00:32:25,017 --> 00:32:26,350 Allora, come posso fare per fare questo? 696 00:32:26,350 --> 00:32:28,950 Beh, io vado a tipo di suddividere mentalmente la lista qui, 697 00:32:28,950 --> 00:32:30,700 non avete a muovo fisicamente, e io sono 698 00:32:30,700 --> 00:32:33,180 andando a concentrarsi solo sul metà sinistra degli elementi qui. 699 00:32:33,180 --> 00:32:36,770 Allora, come posso fare per l'ordinamento un elenco ormai di dimensioni quattro? 700 00:32:36,770 --> 00:32:38,730 Qual è il mio algoritmo? 701 00:32:38,730 --> 00:32:42,580 Per prima cosa ho Check è n meno di due, no, così procedo al blocco altro ancora. 702 00:32:42,580 --> 00:32:43,900 Ordina lasciato la metà di elementi. 703 00:32:43,900 --> 00:32:45,608 >> Così ora di nuovo, mentalmente, ed è qui 704 00:32:45,608 --> 00:32:49,550 devi accumulare un sacco di storia mentale, se si vuole. 705 00:32:49,550 --> 00:32:51,940 Ora sto smistamento sinistra metà della metà sinistra. 706 00:32:51,940 --> 00:32:57,000 Va bene, così ora io chiamo il mio stesso tipo merge algoritmo di ordinamento, è n meno di due? 707 00:32:57,000 --> 00:33:00,590 No, è due, quindi devo ordinare la metà sinistra, e la metà destra. 708 00:33:00,590 --> 00:33:02,042 Quindi qui si va, ordinare la metà sinistra. 709 00:33:02,042 --> 00:33:03,750 Perché non basta fare un passo avanti. 710 00:33:03,750 --> 00:33:04,415 Come ti chiami? 711 00:33:04,415 --> 00:33:04,860 >> PUBBLICO: Darren. 712 00:33:04,860 --> 00:33:05,260 >> SPEAKER: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan ha fatto un passo in avanti. 714 00:33:06,040 --> 00:33:06,748 >> PUBBLICO: Darren. 715 00:33:06,748 --> 00:33:09,000 SPEAKER: Darren, fatto. 716 00:33:09,000 --> 00:33:10,090 Hai detto Darren o Dan? 717 00:33:10,090 --> 00:33:10,550 >> PUBBLICO: Darren. 718 00:33:10,550 --> 00:33:11,216 >> SPEAKER: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, Darren ha intensificato in avanti e lui è ora ordinato. 720 00:33:14,422 --> 00:33:16,130 E questo è quasi un affermazione inane, giusto? 721 00:33:16,130 --> 00:33:18,862 Non mi sembra davvero di essere il raggiungimento nulla, ma procediamo. 722 00:33:18,862 --> 00:33:20,820 Ora vorrei ordinare la giusta metà degli elementi. 723 00:33:20,820 --> 00:33:21,200 Come ti chiami? 724 00:33:21,200 --> 00:33:21,690 >> PUBBLICO: Luke. 725 00:33:21,690 --> 00:33:22,273 >> SPEAKER: Luke. 726 00:33:22,273 --> 00:33:23,400 Dai, un passo in avanti. 727 00:33:23,400 --> 00:33:25,640 Fatto, ho ordinato Luke. 728 00:33:25,640 --> 00:33:28,570 La metà di sinistra è ora ordinato e la metà destra è ora ordinato, 729 00:33:28,570 --> 00:33:30,770 ma ancora una volta, c'è un passo fondamentale qui. 730 00:33:30,770 --> 00:33:32,940 Di cosa ho bisogno di fare il prossimo? 731 00:33:32,940 --> 00:33:33,941 Unire le due metà ordinate. 732 00:33:33,941 --> 00:33:36,648 Ora stiamo andando ad avere solo tutti avanti e indietro in questo modo, 733 00:33:36,648 --> 00:33:38,620 perché ho tipo di bisogno po 'di spazio zero. 734 00:33:38,620 --> 00:33:40,411 E 'quasi come questi ragazzi sono su un tavolo, 735 00:33:40,411 --> 00:33:42,460 e ho bisogno di un certo spazio per spostarli in giro su. 736 00:33:42,460 --> 00:33:44,170 Quindi ho intenzione di fondere voi ragazzi, cercando 737 00:33:44,170 --> 00:33:45,960 nella metà di sinistra e la metà destra. 738 00:33:45,960 --> 00:33:48,740 E chi viene prima, ovviamente, metà sinistra o metà di destra? 739 00:33:48,740 --> 00:33:52,710 Così metà destra, quindi andiamo avanti Luke su qui alla posizione originale di Darren. 740 00:33:52,710 --> 00:33:57,640 E ora per unire loro metà sinistra, Darren sta per trasferirsi proprio lì. 741 00:33:57,640 --> 00:33:59,750 >> Così si sente come quasi un effetto bubble sort, 742 00:33:59,750 --> 00:34:02,482 ma il mio algoritmo fondamentale, molto diverso questa volta. 743 00:34:02,482 --> 00:34:04,815 Ma ora è dove le cose si fanno un po 'fastidioso perché si 744 00:34:04,815 --> 00:34:06,810 devono riavvolgere mentalmente dove ho lasciato fuori. 745 00:34:06,810 --> 00:34:09,893 Ho appena fuso le due metà ordinate, che significa che sono dove nel mio algoritmo? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Devo ordinare la metà destra, giusto? 748 00:34:13,770 --> 00:34:15,910 >> Se si riavvolge, letteralmente sul video, ti 749 00:34:15,910 --> 00:34:18,339 vediamo che siamo arrivati ​​a questo punto di Luca e Darren 750 00:34:18,339 --> 00:34:21,370 di classificare sinistra metà della metà sinistra. 751 00:34:21,370 --> 00:34:23,430 Poi ci siamo fusi quelli metà ordinati, che 752 00:34:23,430 --> 00:34:27,941 significa che il passo successivo è sorta l' metà destra della metà sinistra. 753 00:34:27,941 --> 00:34:29,649 Va bene, quindi cerchiamo di farlo più rapidamente. 754 00:34:29,649 --> 00:34:33,282 Va bene, sei, ho intenzione di rivendicare si sono ora ordinati, andiamo avanti. 755 00:34:33,282 --> 00:34:33,990 Come ti chiami? 756 00:34:33,990 --> 00:34:34,589 >> PUBBLICO: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> SPEAKER: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano è ora ordinato. 759 00:34:36,010 --> 00:34:36,450 E qual è il tuo nome? 760 00:34:36,450 --> 00:34:37,080 >> PUBBLICO: Alex. 761 00:34:37,080 --> 00:34:38,379 >> SPEAKER: Alex è ora ordinato. 762 00:34:38,379 --> 00:34:40,750 La metà sinistra, metà di destra, qual è il passo finale? 763 00:34:40,750 --> 00:34:41,250 Unisci. 764 00:34:41,250 --> 00:34:44,310 Piuttosto banale, quindi sono andando a fondersi in sei, 765 00:34:44,310 --> 00:34:46,930 fare un passo indietro, otto, fare un passo indietro. 766 00:34:46,930 --> 00:34:49,530 E ora notate questo è un take-away utile, cosa 767 00:34:49,530 --> 00:34:53,930 ora è vero circa la metà sinistra del lista, a prescindere di come abbiamo cominciato? 768 00:34:53,930 --> 00:34:55,090 Si è ordinato. 769 00:34:55,090 --> 00:34:57,750 >> Ora non è ordinato in il grande schema delle cose, 770 00:34:57,750 --> 00:35:00,250 ma è ordinato in modo indipendente dell'altra metà. 771 00:35:00,250 --> 00:35:04,100 Ora, che cosa sono io passo su se continuo riavvolgimento come la storia ha cominciato? 772 00:35:04,100 --> 00:35:05,680 Ora devo ordinare la metà destra. 773 00:35:05,680 --> 00:35:07,630 Così ora siamo di ritorno al l'inizio della storia, 774 00:35:07,630 --> 00:35:08,921 e facciamolo più rapidamente. 775 00:35:08,921 --> 00:35:11,320 Quindi ho intenzione di ordinare la metà destra l'intero elenco. 776 00:35:11,320 --> 00:35:13,060 Qual è il prossimo passo? 777 00:35:13,060 --> 00:35:15,840 Ordina la metà sinistra della metà di destra. 778 00:35:15,840 --> 00:35:18,715 Ordina la metà sinistra del metà sinistra della metà destra. 779 00:35:18,715 --> 00:35:19,590 E qual è il tuo nome? 780 00:35:19,590 --> 00:35:20,230 >> PUBBLICO: Omar. 781 00:35:20,230 --> 00:35:21,970 >> SPEAKER: Omar, un passo in avanti, fatto. 782 00:35:21,970 --> 00:35:22,860 Metà sinistra è ordinato. 783 00:35:22,860 --> 00:35:23,330 E qual è il tuo nome? 784 00:35:23,330 --> 00:35:23,820 >> PUBBLICO: Chris. 785 00:35:23,820 --> 00:35:25,620 >> SPEAKER: Chris, fare un passo in avanti, si sono ora ordinati. 786 00:35:25,620 --> 00:35:27,010 Qual è il passo fondamentale adesso? 787 00:35:27,010 --> 00:35:27,510 Unisci. 788 00:35:27,510 --> 00:35:30,509 Così si sta per fondersi in posizione qui, se si potesse fare un passo indietro, 789 00:35:30,509 --> 00:35:32,930 e tre sta per fare un passo indietro, si fondono. 790 00:35:32,930 --> 00:35:38,080 Quindi la metà sinistra del metà di destra, è ora ordinato. 791 00:35:38,080 --> 00:35:41,747 Francamente, questo algoritmo si sente come noi stanno sprecando molto più tempo rispetto a prima, 792 00:35:41,747 --> 00:35:44,830 ma se abbiamo fatto questo in tempo reale, faremo vedere quello che i takeaway andando essere. 793 00:35:44,830 --> 00:35:47,970 Ora eccomi qui, a destra metà della metà destra, 794 00:35:47,970 --> 00:35:50,170 lasciami andare avanti e ordinare la metà sinistra. 795 00:35:50,170 --> 00:35:51,482 Passo in avanti, come ti chiami? 796 00:35:51,482 --> 00:35:52,190 PUBBLICO: Ramsey. 797 00:35:52,190 --> 00:35:53,210 SPEAKER: Ramsey è ora ordinato. 798 00:35:53,210 --> 00:35:53,570 Come ti chiami? 799 00:35:53,570 --> 00:35:54,200 >> PUBBLICO: Marina. 800 00:35:54,200 --> 00:35:57,033 >> SPEAKER: Marina è ora ordinato come bene, se si prende un passo avanti. 801 00:35:57,033 --> 00:36:00,690 Punto chiave qui è ora unire, io sono andando a cogliere dai miei due liste, 802 00:36:00,690 --> 00:36:01,720 a destra ea sinistra. 803 00:36:01,720 --> 00:36:05,150 Cinque sta per venire prima, e sette sta per venire dopo. 804 00:36:05,150 --> 00:36:06,410 E di nuovo, questo è intenzionale. 805 00:36:06,410 --> 00:36:08,535 Il fatto che stanno prendendo passi in avanti e indietro 806 00:36:08,535 --> 00:36:12,997 si vuole rappresentare che non possiamo fare questo algoritmo in luogo facilmente 807 00:36:12,997 --> 00:36:15,830 come bubble sort e selection sort, e insertion sort, dove abbiamo appena 808 00:36:15,830 --> 00:36:16,960 mantenuto lo scambio di persone. 809 00:36:16,960 --> 00:36:19,940 Ho letteralmente bisogno di una sorta di carta zero in cui 810 00:36:19,940 --> 00:36:21,827 di mettere queste persone mentre io faccio la fusione, 811 00:36:21,827 --> 00:36:23,410 e poi posso metterle a posto. 812 00:36:23,410 --> 00:36:27,260 E questo è fondamentale perché sto utilizzando un nuova risorsa, lo spazio, non solo il tempo. 813 00:36:27,260 --> 00:36:28,270 >> OK, questo è incredibile. 814 00:36:28,270 --> 00:36:32,050 La metà sinistra è ordinato, la metà destra è ordinato, ora che la fusione chiave passo. 815 00:36:32,050 --> 00:36:33,450 Come faccio a fondere questo? 816 00:36:33,450 --> 00:36:35,470 Quindi, se seguirete il mio mano sinistra e la mano destra, 817 00:36:35,470 --> 00:36:38,930 Ho intenzione di puntare la mia mano sinistra a metà di sinistra, la mano destra 818 00:36:38,930 --> 00:36:42,680 a metà destra, e ora devo decidere passo dopo passo chi si fondono in. 819 00:36:42,680 --> 00:36:44,650 Chi viene ovviamente prima? 820 00:36:44,650 --> 00:36:45,150 Numero uno. 821 00:36:45,150 --> 00:36:47,327 Quindi vieni qui, ecco la nostra scratch pad. 822 00:36:47,327 --> 00:36:49,910 Così ora numero uno, e comunicazione cosa farò con la mia mano destra, 823 00:36:49,910 --> 00:36:54,152 Ho intenzione di muovere la mano destra una passo sopra al punto numero tre, 824 00:36:54,152 --> 00:36:55,860 e ora devo fare la stessa decisione. 825 00:36:55,860 --> 00:36:58,387 E in realtà stare proprio in davanti a Luca qui se si potesse, 826 00:36:58,387 --> 00:36:59,720 perché questo è il nostro scratch pad. 827 00:36:59,720 --> 00:37:00,610 Allora, chi viene dopo? 828 00:37:00,610 --> 00:37:05,000 Abbiamo Luke con il numero due o Chris con il numero tre. 829 00:37:05,000 --> 00:37:07,460 Ovviamente Luca, numero due, in modo da venire qui. 830 00:37:07,460 --> 00:37:11,270 >> Ma la mia mano sinistra ora sta per essere incrementato per puntare a Darren, 831 00:37:11,270 --> 00:37:15,160 e qui è la chiave di portare via con la fusione, ho intenzione di continuare a fare questo, 832 00:37:15,160 --> 00:37:17,340 ovviamente, se tipo di seguire la logica. 833 00:37:17,340 --> 00:37:19,670 Ma le mie mani non sono mai per andare indietro, 834 00:37:19,670 --> 00:37:23,861 il che significa che sono sempre e solo di trasferirsi a sinistra con il mio processo di fusione, 835 00:37:23,861 --> 00:37:26,360 e che sta per essere la chiave per la nostra analisi in un attimo. 836 00:37:26,360 --> 00:37:27,859 >> Così ora finiamo questo rapidamente. 837 00:37:27,859 --> 00:37:31,650 Così tre viene dopo, poi quattro viene dopo, 838 00:37:31,650 --> 00:37:38,750 e ora cinque viene dopo, poi sei, e sette, e poi finalmente otto. 839 00:37:38,750 --> 00:37:42,960 Si sente come l'algoritmo più lento ancora, ma non se abbiamo effettivamente 840 00:37:42,960 --> 00:37:45,510 eseguirlo allo stesso tipo di velocità di clock, in modo da 841 00:37:45,510 --> 00:37:48,106 parlare, con la stessa ticchettio dell'orologio come prima. 842 00:37:48,106 --> 00:37:48,605 Perché? 843 00:37:48,605 --> 00:37:51,100 Beh, Facciamo un guardare il risultato finale. 844 00:37:51,100 --> 00:37:56,990 >> Torniamo qui, mi permetta tirare su una dimostrazione visiva 845 00:37:56,990 --> 00:37:59,030 di quello che abbiamo appena fatto. 846 00:37:59,030 --> 00:38:06,110 Ingrandimento qui, su questo pagina qui, dicendo Firefox 847 00:38:06,110 --> 00:38:08,200 che vogliamo fare la coda in questa casella, cerchiamo di 848 00:38:08,200 --> 00:38:11,260 dire bubble sort, con la quale siamo ormai familiare, 849 00:38:11,260 --> 00:38:14,130 ordinamento per selezione, che è un altro piuttosto una semplice, 850 00:38:14,130 --> 00:38:18,250 e ora di oggi merge sort, che sarà la nostra finale culminante. 851 00:38:18,250 --> 00:38:21,530 La ragione per cui c'è voluto così tanto più qui con gli esseri umani e me verbalmente è, 852 00:38:21,530 --> 00:38:23,480 ovviamente, sto spiegando ogni passo. 853 00:38:23,480 --> 00:38:26,920 Ma se semplicemente esegue questo, molto come abbiamo fatto bubble sort e selezione 854 00:38:26,920 --> 00:38:30,890 sorta non solo visivamente, orologio quanta più efficiente 855 00:38:30,890 --> 00:38:33,330 questa leva di divisione e conquistare 856 00:38:33,330 --> 00:38:39,150 può essere se applicato a un insieme di dati che è nemmeno dimensione otto, ma anche molto, 857 00:38:39,150 --> 00:38:39,970 molto più grande. 858 00:38:39,970 --> 00:38:44,585 Io do merge sort, fianco a a fianco con questi altri algoritmi. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Questo sta per arrivare dolorosa rapidamente, e il finale 861 00:38:58,530 --> 00:39:00,890 non è particolarmente culminante, hanno appena finiscono ordinati. 862 00:39:00,890 --> 00:39:05,280 Ma la chiave da asporto è che Guarda come molto più veloce merge sort 863 00:39:05,280 --> 00:39:08,110 era, a meno che non pensi che io sia solo tipo di scherzi con voi. 864 00:39:08,110 --> 00:39:13,100 Se lo facciamo un'ultima volta, LET'S Ricarica questa, torniamo 865 00:39:13,100 --> 00:39:14,960 e scegliere bubble sort, e solo per i calci, 866 00:39:14,960 --> 00:39:17,330 scegliamo di inserimento specie, per buona misura. 867 00:39:17,330 --> 00:39:20,020 E anche questa volta, facciamo scegli merge sort e facciamo 868 00:39:20,020 --> 00:39:21,595 effettivamente eseguito questi fianco a fianco. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> E non è, infatti, un colpo di fortuna. 871 00:39:26,930 --> 00:39:31,140 Quello che ho effettivamente fatto è che ho diviso il mio ingresso a metà, di nuovo, 872 00:39:31,140 --> 00:39:32,240 e ancora, e ancora. 873 00:39:32,240 --> 00:39:35,590 E ci sono solo tante volte si può dividere l'input in due metà, a sinistra 874 00:39:35,590 --> 00:39:36,240 e destra. 875 00:39:36,240 --> 00:39:39,425 Qual è la formula che continuiamo a vedere che descrive la divisione a metà 876 00:39:39,425 --> 00:39:41,050 ancora, e ancora, e ancora, e ancora? 877 00:39:41,050 --> 00:39:41,890 >> PUBBLICO: Log n. 878 00:39:41,890 --> 00:39:42,760 >> SPEAKER: Log n. 879 00:39:42,760 --> 00:39:46,300 Ma poi c'è un altro passo fondamentale, questo algoritmo non è log n passi. 880 00:39:46,300 --> 00:39:48,992 Se fosse solo log n passi, saremmo nello stesso problema 881 00:39:48,992 --> 00:39:51,200 come prima, dove non possiamo essere che tutto sia risolto. 882 00:39:51,200 --> 00:39:54,480 Bisogna guardare minimamente al n elementi per essere sicuri che n elementi sono ordinati, 883 00:39:54,480 --> 00:39:55,950 altrimenti è un atto di fede. 884 00:39:55,950 --> 00:39:59,810 >> Quindi è minimamente log n passi, ma che dire di questo passo fusione chiave 885 00:39:59,810 --> 00:40:04,370 dove ho fuso la mia metà sinistra e destra metà e attraversò il palco? 886 00:40:04,370 --> 00:40:06,980 Quanti passi è quello di unire? 887 00:40:06,980 --> 00:40:10,150 E 'n, ma non l'ho fatto solo unire il tempo finale. 888 00:40:10,150 --> 00:40:15,089 Su ciascuna di queste chiamate nidificate, su ogni di quelle unioni nidificate, ho ancora risolto. 889 00:40:15,089 --> 00:40:18,380 Ho fuso questi due ragazzi, allora questi due ragazzi, allora questi due ragazzi e così via. 890 00:40:18,380 --> 00:40:19,955 >> Così ho fatto la fusione ancora, e ancora. 891 00:40:19,955 --> 00:40:20,580 Quante volte? 892 00:40:20,580 --> 00:40:23,510 Così ogni volta che ho diviso il list a metà, ho fatto un merge. 893 00:40:23,510 --> 00:40:25,460 Dividete la lista a metà, fare un merge. 894 00:40:25,460 --> 00:40:28,570 Quindi, se dividendo la lista si può fare log N volte, 895 00:40:28,570 --> 00:40:33,880 e la fusione prende in ultima analisi, n passi, quello che potrebbe essere ora il superiore 896 00:40:33,880 --> 00:40:37,000 vincolato sulla gestione tempo del nostro algoritmo? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> E in effetti, questo è ciò che abbiamo raggiunto qui. 899 00:40:40,560 --> 00:40:44,650 Quindi la sensazione che si vede visivamente quando queste tre cose corrono fianco a fianco 900 00:40:44,650 --> 00:40:47,930 è n quadrato contro la n quadrato contro log n n. 901 00:40:47,930 --> 00:40:51,010 Che fondamentalmente vedremo, non solo oggi ma anche in futuro, 902 00:40:51,010 --> 00:40:52,760 è molto, molto più veloce. 903 00:40:52,760 --> 00:40:56,010 Un applauso per questi ragazzi, Io li ricompenserà con le palle di stress. 904 00:40:56,010 --> 00:41:00,260 Facciamo aggiornare qui oggi, e ci vedremo il Lunedi. 905 00:41:00,260 --> 00:41:02,255