1 00:00:00,000 --> 00:00:11,100 2 00:00:11,100 --> 00:00:12,300 >> SPEAKER 1: Ciao a tutti! 3 00:00:12,300 --> 00:00:13,890 Bentornato alla sezione. 4 00:00:13,890 --> 00:00:17,480 Così felice di vedere così tanti di voi sia qui, e tutti quelli che hanno la visione on-line. 5 00:00:17,480 --> 00:00:18,760 6 00:00:18,760 --> 00:00:20,920 Quindi, come al solito bentornato. 7 00:00:20,920 --> 00:00:24,360 Spero che abbiate passato una bella fine settimana, pieno di riposo, relax. 8 00:00:24,360 --> 00:00:26,026 E 'stato bello ieri fuori. 9 00:00:26,026 --> 00:00:27,525 Quindi, spero che vi sia piaciuto l'aria aperta. 10 00:00:27,525 --> 00:00:28,840 11 00:00:28,840 --> 00:00:30,610 >> Quindi, prima di un paio di annunci. 12 00:00:30,610 --> 00:00:31,920 13 00:00:31,920 --> 00:00:32,700 Di classificazione. 14 00:00:32,700 --> 00:00:37,350 Così, la maggior parte di voi dovreste aver ottenuto un e-mail da me sulla tua Pset Scratch, 15 00:00:37,350 --> 00:00:39,920 nonché Valutazione per Pset 1. 16 00:00:39,920 --> 00:00:41,000 17 00:00:41,000 --> 00:00:42,220 Quindi, solo un paio di cose. 18 00:00:42,220 --> 00:00:45,150 Assicurarsi di utilizzare check50 in style50. 19 00:00:45,150 --> 00:00:47,250 Queste sono destinate ad essere Risorse per voi ragazzi, 20 00:00:47,250 --> 00:00:50,660 per assicurarsi che stai ricevendo il maggior numero di punti possibile 21 00:00:50,660 --> 00:00:52,390 senza inutilmente perderle. 22 00:00:52,390 --> 00:00:54,407 Quindi, le cose come stile sono molto importanti. 23 00:00:54,407 --> 00:00:55,740 Stiamo andando a decollare per esso. 24 00:00:55,740 --> 00:00:58,115 Alcuni di voi potrebbero avere già notato che dal vostro Pset. 25 00:00:58,115 --> 00:00:58,920 26 00:00:58,920 --> 00:01:01,450 E check50 è solo un modo molto semplice per fare in modo 27 00:01:01,450 --> 00:01:05,050 che realmente stiamo tornando quello deve essere restituito all'utente, 28 00:01:05,050 --> 00:01:06,690 e che tutto sta funzionando correttamente. 29 00:01:06,690 --> 00:01:08,690 30 00:01:08,690 --> 00:01:12,040 >> Nella seconda nota, assicurarsi che il proprio caricamento cose nella cartella corretta. 31 00:01:12,040 --> 00:01:14,470 Rende la mia vita solo un po 'più difficile 32 00:01:14,470 --> 00:01:18,836 se si carica Pset 2 in 1 Pset perché quando si scarica le cose, 33 00:01:18,836 --> 00:01:20,085 non scarica correttamente. 34 00:01:20,085 --> 00:01:21,690 35 00:01:21,690 --> 00:01:24,560 E io so che è un po 'traballante in un sistema per abituarsi, 36 00:01:24,560 --> 00:01:26,950 ma solo essere super attenzione, se non altro per me, 37 00:01:26,950 --> 00:01:30,080 in modo che quando stai ricevendo messaggi di posta elettronica a come 02:00 e io sono la classificazione. 38 00:01:30,080 --> 00:01:33,710 Se non provocare devo guardare tutto per il vostro Pset. 39 00:01:33,710 --> 00:01:34,440 Freddo. 40 00:01:34,440 --> 00:01:37,270 >> So che è presto, ma io completamente ma ho preso alla sprovvista 41 00:01:37,270 --> 00:01:40,800 da un saggio che è dovuto questo Venerdì, che i miei professori erano proprio come, oh yeah. 42 00:01:40,800 --> 00:01:42,550 Ricordate, si dispone di un saggio a causa il Venerdì. 43 00:01:42,550 --> 00:01:45,780 Quindi, so che a nessuno piace pensare midterms, 44 00:01:45,780 --> 00:01:50,620 ma il tuo primo quiz è il 15 ottobre, ottobre che inizia questa settimana. 45 00:01:50,620 --> 00:01:53,290 Quindi, potrebbe essere presto del previsto è tutto. 46 00:01:53,290 --> 00:01:57,510 In modo che non sei gettato alla sprovvista quando Cito parte della prossima settimana che oh, 47 00:01:57,510 --> 00:02:00,560 il quiz prossima settimana, ho pensato Ti darei un po 'di più 48 00:02:00,560 --> 00:02:01,500 di un testa a testa ora. 49 00:02:01,500 --> 00:02:02,970 50 00:02:02,970 --> 00:02:04,660 >> Quindi, impostare il problema, numero tre. 51 00:02:04,660 --> 00:02:07,070 Come persone hanno letto il spec per curiosità? 52 00:02:07,070 --> 00:02:08,560 53 00:02:08,560 --> 00:02:09,199 Ok. 54 00:02:09,199 --> 00:02:10,229 Abbiamo ottenuto una coppia. 55 00:02:10,229 --> 00:02:12,320 Tipo di giù rispetto allo scorso settimana, ma va bene così. 56 00:02:12,320 --> 00:02:13,650 So che era bello fuori. 57 00:02:13,650 --> 00:02:15,120 58 00:02:15,120 --> 00:02:16,660 Così Break Out. 59 00:02:16,660 --> 00:02:21,010 Sicuramente dopo si ottiene fatto oggi letto il tuo spec almeno 60 00:02:21,010 --> 00:02:25,240 provare come il download codice distribuzione e funzionamento 61 00:02:25,240 --> 00:02:27,430 come la prima iniziale cosa che ti chiedono di. 62 00:02:27,430 --> 00:02:28,681 63 00:02:28,681 --> 00:02:32,590 Poiché stiamo usando codice di distribuzione e una biblioteca 64 00:02:32,590 --> 00:02:36,790 che siamo solo stati using-- --È è solo la seconda volta che abbiamo fatto questo Pset, 65 00:02:36,790 --> 00:02:38,650 cose folli possono accadere con il vostro apparecchio, 66 00:02:38,650 --> 00:02:41,370 e si vuole scoprire che adesso rispetto a tardi. 67 00:02:41,370 --> 00:02:45,570 >> Perché se è Giovedi notte o è Mercoledì sera e per qualche motivo 68 00:02:45,570 --> 00:02:48,912 l'apparecchio solo non lo fa voler eseguire con la libreria 69 00:02:48,912 --> 00:02:50,620 o con la distribuzione codice, che significa 70 00:02:50,620 --> 00:02:52,309 non si può nemmeno iniziare a fare la codifica. 71 00:02:52,309 --> 00:02:54,100 Poiché non è possibile controllare per vedere se funziona. 72 00:02:54,100 --> 00:02:55,975 Il tuo non sara 'in grado per vedere se si compila. 73 00:02:55,975 --> 00:03:00,500 Si vuole prendersi cura di coloro che all'inizio del settimana, quando è ancora possibile scrivermi 74 00:03:00,500 --> 00:03:03,100 o uno degli altri TF, e siamo in grado di ottenere quelli fissati. 75 00:03:03,100 --> 00:03:05,410 Perché quelli sono problemi che stanno andando a fermarti 76 00:03:05,410 --> 00:03:07,120 di fare un reale progresso. 77 00:03:07,120 --> 00:03:10,055 Non è come un bug, che si può solo tipo di saltare. 78 00:03:10,055 --> 00:03:10,712 79 00:03:10,712 --> 00:03:13,420 Se hai problemi con il tuo apparecchio o il codice di distribuzione, 80 00:03:13,420 --> 00:03:16,211 davvero si vuole ottenere che prese cura di più prima che poi. 81 00:03:16,211 --> 00:03:20,410 Quindi, anche se non riuscirai a realtà iniziare a scrivere codice, scaricare la distribuzione 82 00:03:20,410 --> 00:03:24,040 codice, leggere le specifiche, verificare che tutto è che vi lavorano. 83 00:03:24,040 --> 00:03:25,134 Ok? 84 00:03:25,134 --> 00:03:27,675 Se si può fare solo che, io promettere la vostra vita sarà più facile. 85 00:03:27,675 --> 00:03:28,800 86 00:03:28,800 --> 00:03:31,410 E così probabilmente stai andando a farlo adesso giusto? 87 00:03:31,410 --> 00:03:32,100 Ok. 88 00:03:32,100 --> 00:03:33,950 Quindi, tutte le domande lì? 89 00:03:33,950 --> 00:03:35,850 Tutte le cose logistici? 90 00:03:35,850 --> 00:03:36,910 Il bene di tutti? 91 00:03:36,910 --> 00:03:38,270 Ok. 92 00:03:38,270 --> 00:03:41,700 >> Dichiarazione di non responsabilità per quelli di si in camera e on-line. 93 00:03:41,700 --> 00:03:45,437 Io vado a cercare di cambiare tra PowerPoint nell'apparecchio 94 00:03:45,437 --> 00:03:47,270 perché stiamo andando come fare un po 'di codifica 95 00:03:47,270 --> 00:03:53,630 oggi dalla grande richiesta di anonimo suggerimento sondaggio ho inviato la settimana scorsa. 96 00:03:53,630 --> 00:03:55,480 Quindi, faremo un po 'di codifica. 97 00:03:55,480 --> 00:03:57,800 Quindi, se voi volete anche di accendere i vostri apparecchi, 98 00:03:57,800 --> 00:04:02,910 e si dovrebbe aver ricevuto una e-mail da me, con un file di esempio. 99 00:04:02,910 --> 00:04:04,310 Non esitate a farlo. 100 00:04:04,310 --> 00:04:07,340 >> Quindi, stiamo andando a parlare di GDB, che è un debugger. 101 00:04:07,340 --> 00:04:09,970 E 'intenzione di aiutarvi tipo di capire dove 102 00:04:09,970 --> 00:04:11,860 le cose vanno male nel codice. 103 00:04:11,860 --> 00:04:15,370 E 'davvero solo un modo per fare un passo tramite il codice come sta accadendo, 104 00:04:15,370 --> 00:04:19,100 ed essere in grado di stampare le variabili o vedere cosa sta realmente accadendo 105 00:04:19,100 --> 00:04:22,980 sotto il cofano versi il tuo programma solo in esecuzione, è come faglie, 106 00:04:22,980 --> 00:04:25,030 e tu sei come, idea quello che è appena successo qui. 107 00:04:25,030 --> 00:04:26,730 Non so quale linea non è riuscito a. 108 00:04:26,730 --> 00:04:29,040 Non so dove è andata male. 109 00:04:29,040 --> 00:04:31,280 Quindi, GDB sta per aiutarvi in ​​questo. 110 00:04:31,280 --> 00:04:35,240 Inoltre, se si decide di continuare sì, e prendere 61, 111 00:04:35,240 --> 00:04:38,430 sarà davvero, davvero essere la vostra migliore amico, perché io posso dire 112 00:04:38,430 --> 00:04:40,840 perché sto attraversando quella classe. 113 00:04:40,840 --> 00:04:43,620 >> Stiamo andando a guardare binario di ricerca, che, se voi ragazzi ricordo 114 00:04:43,620 --> 00:04:47,540 il grande esempio rubrica telefonica spettacolo dalla classe. 115 00:04:47,540 --> 00:04:50,620 Saremo applicazione di tale, e a piedi attraverso che un po 'di più, 116 00:04:50,620 --> 00:04:54,650 e poi stiamo attraversando quattro diversi tipi, che sono Bolla, 117 00:04:54,650 --> 00:04:56,285 Selezione, inserimento, e Merge. 118 00:04:56,285 --> 00:04:57,830 119 00:04:57,830 --> 00:04:58,330 Freddo. 120 00:04:58,330 --> 00:05:00,390 Quindi, GDB come ho detto, è un debugger. 121 00:05:00,390 --> 00:05:01,400 122 00:05:01,400 --> 00:05:09,370 E questi sono un po 'grande cose, le grandi funzioni o comandi 123 00:05:09,370 --> 00:05:13,240 utilizzare all'interno di GDB, e io camminerò attraverso una demo di esso in un secondo. 124 00:05:13,240 --> 00:05:15,360 >> Quindi, questo non è solo intenzione di rimanere astratto. 125 00:05:15,360 --> 00:05:18,000 Cercherò di fare come concreta possibile per voi ragazzi. 126 00:05:18,000 --> 00:05:19,870 Così, rompere. 127 00:05:19,870 --> 00:05:22,200 Sarà o sarà rottura come, un numero, che 128 00:05:22,200 --> 00:05:26,900 rappresenta una riga nel programma, oppure si può chiamare una funzione. 129 00:05:26,900 --> 00:05:30,150 Quindi, se si dice rompere principale, si fermerà a principale, 130 00:05:30,150 --> 00:05:32,400 e ti permettono di camminare attraverso quella funzione. 131 00:05:32,400 --> 00:05:36,350 >> Allo stesso modo, se avete un po 'esterna funzionare come Swap o Cube, 132 00:05:36,350 --> 00:05:38,450 che abbiamo visto la scorsa settimana. 133 00:05:38,450 --> 00:05:41,780 Se dici trasgredirà uno solo di questi, ogni volta che il programma che colpisce, 134 00:05:41,780 --> 00:05:44,290 che sarà vi aspetta a dirgli cosa fare. 135 00:05:44,290 --> 00:05:47,860 Prima sarà solo eseguito in modo da potrebbe effettivamente un passo all'interno della funzione 136 00:05:47,860 --> 00:05:49,020 e vedere cosa sta succedendo. 137 00:05:49,020 --> 00:05:50,370 138 00:05:50,370 --> 00:05:53,515 Quindi, la prossima, appena salta sopra il riga successiva, va oltre le funzioni. 139 00:05:53,515 --> 00:05:54,730 140 00:05:54,730 --> 00:05:55,560 Step. 141 00:05:55,560 --> 00:05:56,810 Questi sono tutti po 'astratto. 142 00:05:56,810 --> 00:06:00,530 Quindi, sto solo andando a correre attraverso di loro, ma li vedrete in uso in un secondo. 143 00:06:00,530 --> 00:06:01,810 >> Entra in una funzione. 144 00:06:01,810 --> 00:06:04,170 Quindi, come dicevo, come con Swap, sarebbe 145 00:06:04,170 --> 00:06:07,110 permettono di realtà come se sei come fisicamente fare un passo dentro, 146 00:06:07,110 --> 00:06:10,990 si può pasticciare con queste variabili, stampa che cosa sono, vedere cosa sta succedendo. 147 00:06:10,990 --> 00:06:12,140 148 00:06:12,140 --> 00:06:14,830 Elenco letteralmente basta stampare il codice circostante. 149 00:06:14,830 --> 00:06:17,570 Quindi, se si dimentica di genere dove siete nel vostro programma, 150 00:06:17,570 --> 00:06:19,880 o vi state chiedendo quello che sta succedendo intorno ad esso, 151 00:06:19,880 --> 00:06:23,790 questo sarà solo stampare un segmento di avere cinque o sei linee intorno ad esso. 152 00:06:23,790 --> 00:06:26,080 Quindi, è possibile ottenere orientato di dove siete. 153 00:06:26,080 --> 00:06:27,230 154 00:06:27,230 --> 00:06:28,650 >> Stampa qualche variabile. 155 00:06:28,650 --> 00:06:34,590 Quindi, se avete la chiave come in Cesare, che vedremo. 156 00:06:34,590 --> 00:06:36,220 Si può dire Tasto print in qualsiasi momento. 157 00:06:36,220 --> 00:06:40,070 E ti dirò che cosa il valore è così che, forse da qualche parte lungo la strada, 158 00:06:40,070 --> 00:06:42,070 sovrascritti per la vostra chiave. 159 00:06:42,070 --> 00:06:45,495 Si può effettivamente dire che, a causa si può effettivamente osservare tale valore. 160 00:06:45,495 --> 00:06:46,500 161 00:06:46,500 --> 00:06:48,780 >> In la gente del posto, solo stampe le vostre variabili locali. 162 00:06:48,780 --> 00:06:53,120 Così, ogni volta che sei all'interno di un ciclo, e si desidera solo per vedere come, oh. 163 00:06:53,120 --> 00:06:54,270 Qual è il mio io? 164 00:06:54,270 --> 00:06:57,020 Che cosa è questo valore della chiave che io inizializzare qui? 165 00:06:57,020 --> 00:06:58,537 Qual è il messaggio, a questo punto? 166 00:06:58,537 --> 00:07:00,370 E 'solo stampare tutto di questi, in modo che 167 00:07:00,370 --> 00:07:04,330 non devono singolarmente dire, Stampa I. Stampa Messaggio. 168 00:07:04,330 --> 00:07:04,970 Stampa Key. 169 00:07:04,970 --> 00:07:06,190 170 00:07:06,190 --> 00:07:07,700 E quindi su Schermo. 171 00:07:07,700 --> 00:07:10,370 Ciò che fa è, come si passo attraverso il programma, 172 00:07:10,370 --> 00:07:13,980 sarà solo fare in modo che sia la visualizzazione di un po 'di certa variabile 173 00:07:13,980 --> 00:07:14,780 in ogni punto. 174 00:07:14,780 --> 00:07:17,160 In modo che si also-- --è è una specie di scorciatoia in cui 175 00:07:17,160 --> 00:07:19,530 non devi andare avanti come, oh. 176 00:07:19,530 --> 00:07:23,150 Tasto Stampa o Stampa I. E 'appena lo farà automaticamente per voi. 177 00:07:23,150 --> 00:07:25,959 >> Così, con questo, stiamo andando per vedere come questo va. 178 00:07:25,959 --> 00:07:28,000 Io vado a cercare di interruttore verso l'apparecchio in uso. 179 00:07:28,000 --> 00:07:30,200 180 00:07:30,200 --> 00:07:31,271 Vedi se posso fare questo. 181 00:07:31,271 --> 00:07:31,770 Tutti. 182 00:07:31,770 --> 00:07:40,970 183 00:07:40,970 --> 00:07:42,370 Stiamo solo andando a specchio esso. 184 00:07:42,370 --> 00:07:44,530 Non c'è niente di pazzesco sul mio portatile in ogni modo. 185 00:07:44,530 --> 00:07:49,600 186 00:07:49,600 --> 00:07:50,100 Ok. 187 00:07:50,100 --> 00:07:57,030 188 00:07:57,030 --> 00:08:01,054 Questo deve essere questa. 189 00:08:01,054 --> 00:08:01,795 E 'così piccolo. 190 00:08:01,795 --> 00:08:03,730 191 00:08:03,730 --> 00:08:05,120 Vediamo se siamo in grado di farlo. 192 00:08:05,120 --> 00:08:09,970 193 00:08:09,970 --> 00:08:10,940 >> Ok. 194 00:08:10,940 --> 00:08:15,305 Alice è ovviamente in difficoltà qui solo un po ', 195 00:08:15,305 --> 00:08:17,995 ma ci arriveremo in un Momento. 196 00:08:17,995 --> 00:08:20,810 197 00:08:20,810 --> 00:08:22,020 Ok. 198 00:08:22,020 --> 00:08:25,900 Stiamo solo andando ad aumentare questo. 199 00:08:25,900 --> 00:08:28,770 200 00:08:28,770 --> 00:08:29,380 Ok. 201 00:08:29,380 --> 00:08:31,679 Tutti possono vedere che tipo di? 202 00:08:31,679 --> 00:08:32,470 Forse un po '? 203 00:08:32,470 --> 00:08:33,594 Lo so che è un po 'piccola. 204 00:08:33,594 --> 00:08:34,570 205 00:08:34,570 --> 00:08:37,530 Non riesco a capire come rendere questo più grande. 206 00:08:37,530 --> 00:08:38,350 Se qualcuno lo sa. 207 00:08:38,350 --> 00:08:40,309 Qualcuno sa come farlo più grande? 208 00:08:40,309 --> 00:08:40,932 Ok. 209 00:08:40,932 --> 00:08:42,140 Stiamo andando a rotolare con esso. 210 00:08:42,140 --> 00:08:45,801 Non importa comunque perché è solo questo è il codice che voi ragazzi dovrebbero 211 00:08:45,801 --> 00:08:46,300 avere. 212 00:08:46,300 --> 00:08:48,310 >> Che cosa è più importante è il terminale qui. 213 00:08:48,310 --> 00:08:52,840 214 00:08:52,840 --> 00:08:58,690 E abbiamo qui Perché è così piccolo? 215 00:08:58,690 --> 00:09:02,325 216 00:09:02,325 --> 00:09:02,825 Impostazioni. 217 00:09:02,825 --> 00:09:07,920 218 00:09:07,920 --> 00:09:08,420 Oh. 219 00:09:08,420 --> 00:09:09,500 Vero Ike. 220 00:09:09,500 --> 00:09:10,880 Come va questo? 221 00:09:10,880 --> 00:09:11,770 Fuori di lì. 222 00:09:11,770 --> 00:09:19,370 223 00:09:19,370 --> 00:09:21,810 Che è meglio per tutti? 224 00:09:21,810 --> 00:09:22,525 Ok ,. 225 00:09:22,525 --> 00:09:23,025 Freddo. 226 00:09:23,025 --> 00:09:25,830 227 00:09:25,830 --> 00:09:28,220 >> Avete presente quando siete in un CS classe di difficoltà tecniche 228 00:09:28,220 --> 00:09:32,971 sono tipo di parte di the-- Quindi, cerchiamo di chiarire questo. 229 00:09:32,971 --> 00:09:33,470 Ok. 230 00:09:33,470 --> 00:09:38,060 Così, proprio qui in sezione, che abbiamo avuto qui. 231 00:09:38,060 --> 00:09:40,830 Cesare è un file eseguibile. 232 00:09:40,830 --> 00:09:41,800 Così ho fatto. 233 00:09:41,800 --> 00:09:46,370 Quindi, una cosa da realizzare con GDB è che funziona solo su file eseguibili. 234 00:09:46,370 --> 00:09:48,040 Quindi, non è possibile eseguire su un Dotsy. 235 00:09:48,040 --> 00:09:50,532 Si deve effettivamente fare Assicurarsi che il codice venga compilato, 236 00:09:50,532 --> 00:09:51,865 e che può effettivamente essere eseguito. 237 00:09:51,865 --> 00:09:52,970 238 00:09:52,970 --> 00:09:56,186 >> Quindi, assicurarsi che se non lo fa compilarlo, farlo compilare, 239 00:09:56,186 --> 00:09:57,810 in modo da poter genere di correre attraverso di essa. 240 00:09:57,810 --> 00:10:04,590 Quindi, per iniziare GDB, tutto ciò che fai, Gloria tipo GDB, e quindi solo il 241 00:10:04,590 --> 00:10:06,250 file che si desidera. 242 00:10:06,250 --> 00:10:08,240 Ho sempre errori ortografici Cesare. 243 00:10:08,240 --> 00:10:11,730 Ma si vuole fare in modo dal momento che è un eseguibile, 244 00:10:11,730 --> 00:10:14,210 dot flash ti in modo che significa che si sta andando 245 00:10:14,210 --> 00:10:19,240 per eseguire CSI si sta andando ad eseguire questo file sia con il debugger. 246 00:10:19,240 --> 00:10:19,910 Ok. 247 00:10:19,910 --> 00:10:22,885 Quindi, tu che, si ottiene questo tipo di parole senza senso. 248 00:10:22,885 --> 00:10:24,250 249 00:10:24,250 --> 00:10:25,750 E 'solo tutte le cose su di debugger. 250 00:10:25,750 --> 00:10:28,200 In realtà non è necessario preoccuparsene adesso. 251 00:10:28,200 --> 00:10:31,460 E come vedete, abbiamo questo parentesi aperte, PIL, chiudere parentesi, 252 00:10:31,460 --> 00:10:34,690 e solo un po 'si presenta come la nostra linea di comando, giusto? 253 00:10:34,690 --> 00:10:37,010 >> Allora, che cosa vogliamo fare-- --quindi, La prima cosa 254 00:10:37,010 --> 00:10:39,570 è che vogliamo scegliere un posto per romperlo. 255 00:10:39,570 --> 00:10:42,332 Quindi, c'è un bug in questo programma di Cesare 256 00:10:42,332 --> 00:10:44,290 che presento, che che andremo a scoprire. 257 00:10:44,290 --> 00:10:45,330 258 00:10:45,330 --> 00:10:56,350 E 'ciò che fa è che ci vuole l'ingresso Barfoo in tutte le protezioni, e per qualche motivo 259 00:10:56,350 --> 00:11:01,950 non cambia A. Lascia solo da solo, tutto il resto è corretto, 260 00:11:01,950 --> 00:11:03,980 ma la seconda lettera A rimane invariata. 261 00:11:03,980 --> 00:11:07,120 Quindi, stiamo andando a cercare di capire perché. 262 00:11:07,120 --> 00:11:10,440 Quindi, la prima cosa che in genere vuole fare ogni volta che si avvia il GDB 263 00:11:10,440 --> 00:11:12,010 è capire dove romperlo. 264 00:11:12,010 --> 00:11:14,956 >> Così Cesare è un programma piuttosto breve. 265 00:11:14,956 --> 00:11:16,330 Non ci resta che una funzione, giusto? 266 00:11:16,330 --> 00:11:18,520 Qual è stata la nostra funzione in Cesare? 267 00:11:18,520 --> 00:11:19,590 268 00:11:19,590 --> 00:11:24,350 C'è solo una funzione, giusto principale? 269 00:11:24,350 --> 00:11:26,490 Principale è una funzione per tutti i vostri programmi. 270 00:11:26,490 --> 00:11:29,230 Se non aveste principale, potrei essere un po 'preoccupato in questo momento, 271 00:11:29,230 --> 00:11:31,000 ma spero abbiate passato principale in là. 272 00:11:31,000 --> 00:11:34,150 Allora, cosa possiamo fare è che possiamo basta rompere principale, proprio così. 273 00:11:34,150 --> 00:11:35,190 Così, si dice, OK. 274 00:11:35,190 --> 00:11:37,430 Abbiamo impostato il nostro unico punto di interruzione lì. 275 00:11:37,430 --> 00:11:42,870 >> Così, ora la cosa da ricordare è di Cesare prende un argomento della riga di comando di destra 276 00:11:42,870 --> 00:11:45,150 e non abbiamo nessuna parte ancora fatto. 277 00:11:45,150 --> 00:11:47,560 Quindi, ciò che si fa è quando si effettivamente andare a correre 278 00:11:47,560 --> 00:11:51,540 il programma, qualsiasi programma che si è esecuzione in GDB che ha bisogno della riga di comando 279 00:11:51,540 --> 00:11:55,010 argomenti, si sta andando a ingresso quando si inizia a eseguirlo. 280 00:11:55,010 --> 00:11:59,280 Quindi, in questo caso, facciamo Eseguire con una chiave di tre. 281 00:11:59,280 --> 00:12:00,770 282 00:12:00,770 --> 00:12:02,040 E sarà effettivamente iniziare. 283 00:12:02,040 --> 00:12:08,480 >> Quindi, se vedete qui, abbiamo Se RC non è uguale a 2. 284 00:12:08,480 --> 00:12:12,210 Quindi, se voi ragazzi tutti hanno il file che ho mandato su 285 00:12:12,210 --> 00:12:15,100 vedrai che è come il prima linea la nostra funzione principale, giusto? 286 00:12:15,100 --> 00:12:17,890 E 'il controllo per vedere se abbiamo il numero corretto di argomenti. 287 00:12:17,890 --> 00:12:20,620 Quindi, se vi state chiedendo se RC è corretta, 288 00:12:20,620 --> 00:12:23,250 si può fare qualcosa come stampa RC. 289 00:12:23,250 --> 00:12:24,380 290 00:12:24,380 --> 00:12:28,640 RC è due, che è quello che ci aspettavamo, giusto? 291 00:12:28,640 --> 00:12:32,010 >> Quindi, possiamo andare Avanti, e proseguire attraverso. 292 00:12:32,010 --> 00:12:33,200 Così, abbiamo qualche chiave lì. 293 00:12:33,200 --> 00:12:34,260 294 00:12:34,260 --> 00:12:37,090 E siamo in grado di stampare la nostra chiave per assicurarsi che sia corretto. 295 00:12:37,090 --> 00:12:38,380 296 00:12:38,380 --> 00:12:39,500 Interessante. 297 00:12:39,500 --> 00:12:41,210 Non è proprio quello che ci aspettavamo. 298 00:12:41,210 --> 00:12:44,810 Quindi, una cosa da realizzare con GDB inoltre, è 299 00:12:44,810 --> 00:12:49,000 che non è fino a che realmente ha colpito Avanti, che la linea che avete appena visto 300 00:12:49,000 --> 00:12:50,720 è effettivamente eseguito. 301 00:12:50,720 --> 00:12:53,870 Quindi, in questo caso Chiave non è stato ancora assegnato. 302 00:12:53,870 --> 00:12:57,050 Quindi, Key è un valore spazzatura che si vede sul fondo lì. 303 00:12:57,050 --> 00:13:03,680 Negativo $ 120-- --È di un miliardo e qualcosa di cose strane giusto? 304 00:13:03,680 --> 00:13:05,340 Non è la chiave che ci aspettavamo. 305 00:13:05,340 --> 00:13:10,720 Ma se ci ha colpito su Avanti, quindi siamo cercare di chiave di stampa, è tre. 306 00:13:10,720 --> 00:13:11,710 >> Ognuno vede che? 307 00:13:11,710 --> 00:13:13,780 Quindi, se si ottiene qualcosa che sei come, aspetta. 308 00:13:13,780 --> 00:13:15,540 Questo è completamente sbagliato, e io non lo so 309 00:13:15,540 --> 00:13:20,150 come questo possa accadere perché tutto quello che voglio fare è assegnare un numero, una variabile, 310 00:13:20,150 --> 00:13:22,900 provare a colpire Successivamente, provare a stampare di nuovo, e vedere se funziona. 311 00:13:22,900 --> 00:13:27,830 Perché è solo andando a eseguire e in realtà assegnare qualcosa dopo 312 00:13:27,830 --> 00:13:29,340 premere Avanti. 313 00:13:29,340 --> 00:13:30,336 Dare un senso a tutti? 314 00:13:30,336 --> 00:13:30,836 Uh huh? 315 00:13:30,836 --> 00:13:33,220 >> SPEAKER 2: Quando si casuale numeri che cosa significa? 316 00:13:33,220 --> 00:13:34,790 >> SPEAKER 1: E 'solo casuale. 317 00:13:34,790 --> 00:13:35,710 E 'solo spazzatura. 318 00:13:35,710 --> 00:13:38,320 E 'solo qualcosa che il vostro computer in modo casuale assegnare. 319 00:13:38,320 --> 00:13:39,721 320 00:13:39,721 --> 00:13:40,220 Freddo. 321 00:13:40,220 --> 00:13:45,760 Quindi, ora siamo in grado di muoversi attraverso, e così ora abbiamo questo testo GetString normale. 322 00:13:45,760 --> 00:13:48,600 Quindi, lasciatemi introdurre quello accadrà quando ci ha colpito Avanti qui. 323 00:13:48,600 --> 00:13:51,320 Il nostro tipo di GDB scompare, giusto? 324 00:13:51,320 --> 00:13:55,720 Questo perché GetString è ora di esecuzione, giusto? 325 00:13:55,720 --> 00:14:01,460 Così, quando abbiamo visto il testo normale è uguale GetString, parentesi aperte e parentesi, 326 00:14:01,460 --> 00:14:04,380 e ci ha colpito Avanti, che ha in realtà eseguito ora. 327 00:14:04,380 --> 00:14:06,580 Quindi, è in attesa di noi all'ingresso qualcosa. 328 00:14:06,580 --> 00:14:13,560 >> Quindi, stiamo andando per inserire il nostro cibo che è quello che è mancato come ti ho detto 329 00:14:13,560 --> 00:14:18,020 e che dice solo che è terminato l'esecuzione, che il chiuso 330 00:14:18,020 --> 00:14:19,980 staffa significa che è All'uscita da questo carico. 331 00:14:19,980 --> 00:14:21,170 332 00:14:21,170 --> 00:14:25,420 Quindi, siamo in grado di colpire Avanti, e ora, come io sono sicuro che siete tutti a conoscenza da parte di Cesare, 333 00:14:25,420 --> 00:14:27,260 questo è, che cosa è questa linea sta per fare. 334 00:14:27,260 --> 00:14:32,030 E 'per Int I è uguale a 0, N è uguale a Strlen, testo normale, e poi 335 00:14:32,030 --> 00:14:33,960 I è minore di n, io, più, più. 336 00:14:33,960 --> 00:14:35,210 Che cosa è questo ciclo intenzione di fare? 337 00:14:35,210 --> 00:14:37,900 338 00:14:37,900 --> 00:14:39,160 Aprire il messaggio. 339 00:14:39,160 --> 00:14:39,770 Freddo. 340 00:14:39,770 --> 00:14:41,330 Quindi, cominciamo a farlo. 341 00:14:41,330 --> 00:14:47,210 >> Quindi, qualora questa condizione corrispondere, per il nostro primo? 342 00:14:47,210 --> 00:14:52,250 Se si tratta di un B, è solo testo I. Noi possono ottenere informazioni sui nostri locali. 343 00:14:52,250 --> 00:14:53,610 344 00:14:53,610 --> 00:14:57,970 Così, I è pari a zero, e se sei, che ci aspettiamo, e la nostra chiave è di tre. 345 00:14:57,970 --> 00:14:59,227 Tutto ciò che ha senso, giusto? 346 00:14:59,227 --> 00:15:01,310 Questi numeri sono tutti esattamente quello che dovrebbe essere. 347 00:15:01,310 --> 00:15:02,590 348 00:15:02,590 --> 00:15:03,870 Così, canticchiare? 349 00:15:03,870 --> 00:15:05,620 SPEAKER 3: Ho numeri casuali per il mio. 350 00:15:05,620 --> 00:15:09,156 351 00:15:09,156 --> 00:15:12,030 SPEAKER 1: Beh, siamo in grado di check-- --dobbiamo si può parlare di che in un secondo. 352 00:15:12,030 --> 00:15:14,110 353 00:15:14,110 --> 00:15:15,750 Ma si dovrebbe essere sempre presente. 354 00:15:15,750 --> 00:15:17,700 355 00:15:17,700 --> 00:15:20,130 Quindi, se abbiamo un capitale B per il primo, 356 00:15:20,130 --> 00:15:22,080 questa condizione dovrebbe prenderlo, giusto? 357 00:15:22,080 --> 00:15:27,120 Quindi, se abbiamo colpito Avanti, vediamo che questo caso viene eseguito in realtà. 358 00:15:27,120 --> 00:15:29,220 Perché se stai seguendo avanti nel codice, 359 00:15:29,220 --> 00:15:33,460 questa linea qui, in cui il testo normale I è sostituito con questo aritmetica, 360 00:15:33,460 --> 00:15:35,720 esegue solo se il caso condizione è corretto giusto? 361 00:15:35,720 --> 00:15:36,905 362 00:15:36,905 --> 00:15:40,240 >> GDB è solo andare a mostrare cose che sono effettivamente in esecuzione. 363 00:15:40,240 --> 00:15:45,140 Quindi, se questa condizione se non è stata rispettata, è solo andando per passare alla riga successiva. 364 00:15:45,140 --> 00:15:46,540 Ok? 365 00:15:46,540 --> 00:15:48,510 Quindi, abbiamo che. 366 00:15:48,510 --> 00:15:51,171 Questa staffa significa che è chiuso da questo carico di ora. 367 00:15:51,171 --> 00:15:52,420 Quindi, che sta per iniziare di nuovo. 368 00:15:52,420 --> 00:15:54,760 369 00:15:54,760 --> 00:15:56,280 Proprio così. 370 00:15:56,280 --> 00:15:59,120 Quindi, che possiamo ottenere informazioni sulle nostre gente del posto qui, 371 00:15:59,120 --> 00:16:02,575 e vediamo che il nostro primo lettera è cambiata, giusto? 372 00:16:02,575 --> 00:16:05,150 Ora è una E, come dovrebbe essere. 373 00:16:05,150 --> 00:16:07,360 Quindi, possiamo continuare su. 374 00:16:07,360 --> 00:16:08,500 >> E noi abbiamo questo controllo. 375 00:16:08,500 --> 00:16:09,916 E questo controllo dovrebbe funzionare, giusto? 376 00:16:09,916 --> 00:16:12,570 È A. Si dovrebbe essere cambiato tre lettere in avanti. 377 00:16:12,570 --> 00:16:14,320 378 00:16:14,320 --> 00:16:16,530 Ma se si nota, si ottenere qualcosa di diverso. 379 00:16:16,530 --> 00:16:17,580 380 00:16:17,580 --> 00:16:22,860 Quindi, in questo caso fino qui, catturato esso, e quindi questa linea eseguita, 381 00:16:22,860 --> 00:16:28,620 che ha modificato il nostro B. Ma, in questo caso di specie, 382 00:16:28,620 --> 00:16:32,860 abbiamo che appena saltato, e andò al [? L SIFF. ?] 383 00:16:32,860 --> 00:16:34,660 Quindi, qualcosa sta succedendo lì. 384 00:16:34,660 --> 00:16:37,780 Cosa che si sta dicendo è che, sappiamo che si deve prendere qui, 385 00:16:37,780 --> 00:16:39,200 ma non lo è. 386 00:16:39,200 --> 00:16:42,210 Chiunque può vedere ciò che il nostro problema è in quella linea? 387 00:16:42,210 --> 00:16:45,380 388 00:16:45,380 --> 00:16:46,969 E 'una cosa molto minuto. 389 00:16:46,969 --> 00:16:48,510 E si potrebbe anche guardare il vostro codice. 390 00:16:48,510 --> 00:16:49,980 391 00:16:49,980 --> 00:16:54,940 E 'line-- anche dimenticare ciò che la linea è in there-- ma è in [incomprensibile]. 392 00:16:54,940 --> 00:16:55,480 Sì? 393 00:16:55,480 --> 00:16:58,639 >> SPEAKER 4: E 'il più grande di pagina se lo si legge nel libro. 394 00:16:58,639 --> 00:16:59,430 SPEAKER 1: Esattamente. 395 00:16:59,430 --> 00:17:02,620 Così, il debugger non poteva dire che, ma il debugger 396 00:17:02,620 --> 00:17:05,880 potrebbe arrivare fino a una linea che si sa non funziona. 397 00:17:05,880 --> 00:17:09,319 E a volte, quando in particolare più tardi nel semestre, quando 398 00:17:09,319 --> 00:17:12,910 hai a che fare con cento, centinaia di poche righe di codice, e si 399 00:17:12,910 --> 00:17:16,190 non so dove è in mancanza, questo è un ottimo modo per farlo. 400 00:17:16,190 --> 00:17:17,900 401 00:17:17,900 --> 00:17:18,989 Così, abbiamo trovato il nostro bug. 402 00:17:18,989 --> 00:17:21,530 È possibile risolvere il problema nel file, e allora si potrebbe correre di nuovo, 403 00:17:21,530 --> 00:17:23,029 e tutto avrebbe funzionato alla perfezione. 404 00:17:23,029 --> 00:17:24,970 405 00:17:24,970 --> 00:17:30,590 E la cosa più importante è questo può sembrare, OK. 406 00:17:30,590 --> 00:17:31,090 Sì. 407 00:17:31,090 --> 00:17:31,370 Freddo. 408 00:17:31,370 --> 00:17:32,744 Si sapeva che cosa stai cercando. 409 00:17:32,744 --> 00:17:34,910 Quindi, si sapeva che cosa fare. 410 00:17:34,910 --> 00:17:39,021 >> GDB può essere super disponibile, perché si può stampare tutte queste cose che si 411 00:17:39,021 --> 00:17:39,520 non lo farei. 412 00:17:39,520 --> 00:17:41,160 E 'molto più utile di printf. 413 00:17:41,160 --> 00:17:43,440 Quanti di voi usa come istruzioni printf 414 00:17:43,440 --> 00:17:46,200 per capire dove era un bug, giusto? 415 00:17:46,200 --> 00:17:48,450 Così, con questo, non è necessario deve andare avanti indietro, 416 00:17:48,450 --> 00:17:51,139 e come commentare in Printf, o commentando, 417 00:17:51,139 --> 00:17:52,930 e capire cosa si dovrebbe essere la stampa. 418 00:17:52,930 --> 00:17:55,670 Questo in realtà solo consente di scorrere, stampare le cose 419 00:17:55,670 --> 00:18:00,000 come stai passando, così, è possibile osservare come cambiano in tempo reale, 420 00:18:00,000 --> 00:18:02,190 come il programma è in esecuzione. 421 00:18:02,190 --> 00:18:04,390 >> E ci vuole un po ' po 'di tempo per abituarsi. 422 00:18:04,390 --> 00:18:07,850 Mi raccomando solo tipo di essere un po 'frustrato con esso 423 00:18:07,850 --> 00:18:08,930 per ora. 424 00:18:08,930 --> 00:18:13,450 Se si spendono un'ora sulla la prossima settimana per imparare a usare GDB, 425 00:18:13,450 --> 00:18:16,140 si salva te stesso tanto tempo successivamente. 426 00:18:16,140 --> 00:18:18,750 E letteralmente. diciamo questo per persone ogni anno, 427 00:18:18,750 --> 00:18:23,890 e mi ricordo quando ho preso il classe, ero come, mi andrà bene. 428 00:18:23,890 --> 00:18:24,700 No. 429 00:18:24,700 --> 00:18:27,030 Pset 6 è venuto su e mi è stato come, sto andando imparare 430 00:18:27,030 --> 00:18:29,500 come utilizzare GDB, perché non lo faccio sapere che cosa sta succedendo qui. 431 00:18:29,500 --> 00:18:32,940 >> Quindi, se si prende il tempo così usarlo su programmi più piccoli 432 00:18:32,940 --> 00:18:35,697 che si sta andando ad essere lavorando, come lavorare 433 00:18:35,697 --> 00:18:37,530 attraverso qualcosa di simile Visionare, come questo. 434 00:18:37,530 --> 00:18:38,800 435 00:18:38,800 --> 00:18:42,850 O se volete la pratica in più, ne sono sicuro Potrei venire con programmi buggy, 436 00:18:42,850 --> 00:18:45,300 per eseguire il debug, se vuoi. 437 00:18:45,300 --> 00:18:49,300 >> Ma se si prende un po 'di tempo per ottenere l'abitudine, basta giocare con essa, 438 00:18:49,300 --> 00:18:50,550 sarà davvero servirà bene. 439 00:18:50,550 --> 00:18:52,591 Ed è davvero una delle quelle cose che hai appena 440 00:18:52,591 --> 00:18:57,340 devono provare, e sporcarsi le mani con, prima che realmente capire. 441 00:18:57,340 --> 00:19:02,090 Ho davvero capito solo una volta Ho dovuto eseguire il debug di cose con esso, 442 00:19:02,090 --> 00:19:08,170 ed è molto più bello di avere un'idea di come eseguire il debug il più presto possibile. 443 00:19:08,170 --> 00:19:08,850 Ok. 444 00:19:08,850 --> 00:19:09,625 Freddo. 445 00:19:09,625 --> 00:19:12,960 So che è un po 'come un corso intensivo di GDB, 446 00:19:12,960 --> 00:19:16,400 e ci tornerò sicuramente lavorare per ottenere questi per sembrare più grandi la prossima volta. 447 00:19:16,400 --> 00:19:17,590 448 00:19:17,590 --> 00:19:18,280 Freddo. 449 00:19:18,280 --> 00:19:20,390 >> Quindi, se torniamo al nostro PowerPoint. 450 00:19:20,390 --> 00:19:27,194 451 00:19:27,194 --> 00:19:28,110 E 'questo di andare a lavorare? 452 00:19:28,110 --> 00:19:29,711 453 00:19:29,711 --> 00:19:30,210 Awh. 454 00:19:30,210 --> 00:19:31,101 Sì. 455 00:19:31,101 --> 00:19:31,600 Ok. 456 00:19:31,600 --> 00:19:35,480 Quindi, se mai hai bisogno di qualsiasi quelli di nuovo, c'è la lista. 457 00:19:35,480 --> 00:19:37,160 458 00:19:37,160 --> 00:19:40,830 Cerca Quindi binario, che tutti ricorda il grande spettacolo di David 459 00:19:40,830 --> 00:19:42,259 ripping rubriche a metà. 460 00:19:42,259 --> 00:19:44,050 Io davvero non capisco il rubriche più, 461 00:19:44,050 --> 00:19:46,530 perché come dove si fa ottenere rubriche in questi giorni? 462 00:19:46,530 --> 00:19:48,220 Io davvero non lo so. 463 00:19:48,220 --> 00:19:49,840 464 00:19:49,840 --> 00:19:50,590 La ricerca binaria. 465 00:19:50,590 --> 00:19:52,464 Qualcuno ricorda Come funziona binario di ricerca? 466 00:19:52,464 --> 00:19:54,380 467 00:19:54,380 --> 00:19:55,220 Chiunque a tutti? 468 00:19:55,220 --> 00:19:56,325 Sì? 469 00:19:56,325 --> 00:19:58,283 SPEAKER 5: Non si sa quando si guarda a cui la metà 470 00:19:58,283 --> 00:20:01,146 sarebbe in, base di questo, ed eliminare l'altra metà. 471 00:20:01,146 --> 00:20:01,896 >> SPEAKER 1 Esattamente. 472 00:20:01,896 --> 00:20:06,290 Così, la ricerca binaria, è una specie di a-- --dobbiamo piace chiamarlo divide et impera. 473 00:20:06,290 --> 00:20:09,170 Allora, che cosa farai è ti aspetto nel mezzo, 474 00:20:09,170 --> 00:20:11,990 e vedrete se corrisponde quello che stai cercando. 475 00:20:11,990 --> 00:20:15,420 E se non lo fa, quindi si tenta di capire, sta andando ad essere lasciato 476 00:20:15,420 --> 00:20:16,450 metà o la metà destra. 477 00:20:16,450 --> 00:20:19,325 Quindi, questo potrebbe essere se siete alla ricerca a qualcosa che è alfabetizzato, 478 00:20:19,325 --> 00:20:20,720 vedi, oh. 479 00:20:20,720 --> 00:20:22,750 Ha Allison viene prima M? 480 00:20:22,750 --> 00:20:23,250 Sì. 481 00:20:23,250 --> 00:20:25,030 Quindi, stiamo andando a guardare il primo tempo. 482 00:20:25,030 --> 00:20:26,450 >> Oppure potrebbe essere come con i numeri. 483 00:20:26,450 --> 00:20:28,830 Tutto ciò che si può confrontare, si può essere ordinato. 484 00:20:28,830 --> 00:20:29,920 485 00:20:29,920 --> 00:20:31,260 È possibile utilizzare la ricerca binaria su. 486 00:20:31,260 --> 00:20:32,340 487 00:20:32,340 --> 00:20:37,455 Così, qualcuno ricorda questo grafico o di cosa si tratta? 488 00:20:37,455 --> 00:20:39,520 E 'Complessità asintotica. 489 00:20:39,520 --> 00:20:42,830 Quindi, questo grafico solo descrive quanto tempo 490 00:20:42,830 --> 00:20:46,230 si porta a risolvere un problema come si aumenta il numero di cose 491 00:20:46,230 --> 00:20:47,090 che si sta utilizzando. 492 00:20:47,090 --> 00:20:51,260 >> Così, abbiamo N, che è il tempo lineare. 493 00:20:51,260 --> 00:20:54,560 Se N più di due, che è leggermente meglio, cresce ancora super veloce. 494 00:20:54,560 --> 00:20:58,360 E poi abbiamo il login, che è quello che noi consideriamo Ricerca binaria. 495 00:20:58,360 --> 00:21:03,630 Se notiamo, come il problema diventa molto più e molto più grande, 496 00:21:03,630 --> 00:21:06,600 il tempo necessario per risolverlo in realtà non aumenta più di tanto. 497 00:21:06,600 --> 00:21:09,010 E 'come paragonabile qui all'inizio. 498 00:21:09,010 --> 00:21:10,060 Sei come, OK. 499 00:21:10,060 --> 00:21:13,000 Tutto ciò che qui non lo fa davvero importa che uno si usa, 500 00:21:13,000 --> 00:21:16,220 ma si arriva ad un milione, un miliardo. 501 00:21:16,220 --> 00:21:20,010 Stai cercando di trovare some-- --you're cercando di trovare un ago in un pagliaio. 502 00:21:20,010 --> 00:21:21,550 >> Penso che si desidera questo problema. 503 00:21:21,550 --> 00:21:25,850 Volete questa complessità, non lineare perché per tutto quello che 504 00:21:25,850 --> 00:21:30,049 il vostro andando essere alla ricerca attraverso ogni singolo ago, cosa di fieno, 505 00:21:30,049 --> 00:21:31,340 cercando di cercare l'ago. 506 00:21:31,340 --> 00:21:34,730 E non è troppo divertente a mio parere. 507 00:21:34,730 --> 00:21:35,500 Mi piace veloce. 508 00:21:35,500 --> 00:21:36,620 Mi piace efficiente. 509 00:21:36,620 --> 00:21:40,450 E gli studenti come laboriosa voi ragazzi sono, si sa lavorare meglio, 510 00:21:40,450 --> 00:21:43,010 non di più tipo cosa, come si può compensare questi algoritmi. 511 00:21:43,010 --> 00:21:45,110 512 00:21:45,110 --> 00:21:47,910 >> Quindi, stiamo andando a camminare attraverso solo un esempio veloce. 513 00:21:47,910 --> 00:21:51,090 Penso che voi ragazzi dovreste avere una mano sulla ricerca binaria, 514 00:21:51,090 --> 00:21:54,352 ma nel caso qualcuno è un po ' fuzzy, vogliono rafforzarlo, 515 00:21:54,352 --> 00:21:56,310 stiamo per andare solo attraverso un esempio qui. 516 00:21:56,310 --> 00:21:59,490 Quindi, stiamo cercando se l'array contiene sette. 517 00:21:59,490 --> 00:22:00,540 518 00:22:00,540 --> 00:22:06,010 >> Quindi, prima cosa da fare è guardare in mezzo, giusto? 519 00:22:06,010 --> 00:22:09,340 E inoltre si sta andando ad essere la codifica Binary Cerca in appena un secondo. 520 00:22:09,340 --> 00:22:11,310 Quindi, che sta per essere divertente. 521 00:22:11,310 --> 00:22:13,710 Quindi guardiamo in medio piccole matrici 3. 522 00:22:13,710 --> 00:22:15,501 Ritiene 3 pari 7? 523 00:22:15,501 --> 00:22:16,000 Non lo fa. 524 00:22:16,000 --> 00:22:18,670 525 00:22:18,670 --> 00:22:19,550 Sono le sei. 526 00:22:19,550 --> 00:22:21,480 Quindi, è meno di o maggiore di sette? 527 00:22:21,480 --> 00:22:23,080 528 00:22:23,080 --> 00:22:23,960 Meno di. 529 00:22:23,960 --> 00:22:24,570 Sì. 530 00:22:24,570 --> 00:22:25,170 Ragazzi bel lavoro. 531 00:22:25,170 --> 00:22:25,569 532 00:22:25,569 --> 00:22:27,360 Mi sento come se dovessi avere caramelle perché 533 00:22:27,360 --> 00:22:29,460 voglia di buttare fuori nei cortili. 534 00:22:29,460 --> 00:22:30,270 E 'quello che ho intenzione di fare la prossima settimana. 535 00:22:30,270 --> 00:22:31,436 Manterrà voi ragazzi taglienti. 536 00:22:31,436 --> 00:22:32,560 537 00:22:32,560 --> 00:22:34,690 >> Così, gettiamo via che primo tempo, giusto? 538 00:22:34,690 --> 00:22:35,670 era inferiore. 539 00:22:35,670 --> 00:22:39,325 noi sappiamo che tutto ciò che su quella sinistra 540 00:22:39,325 --> 00:22:41,700 sta per essere inferiore a quello in realtà stiamo cercando. 541 00:22:41,700 --> 00:22:43,491 Quindi, non c'è bisogno di prestare attenzione ad esso. 542 00:22:43,491 --> 00:22:45,120 Basta non pensarci più. 543 00:22:45,120 --> 00:22:48,720 Così, ora guardiamo alla nostra destra, e guardiamo a metà laggiù, 544 00:22:48,720 --> 00:22:50,510 e ora è nove. 545 00:22:50,510 --> 00:22:55,510 Quindi, 9 è-- --Everyone? 546 00:22:55,510 --> 00:22:57,470 Maggiore di ciò che siamo cercando, giusto? 547 00:22:57,470 --> 00:22:59,860 Quindi, stiamo andando a buttare via tutto a destra. 548 00:22:59,860 --> 00:23:00,970 549 00:23:00,970 --> 00:23:01,940 Come quella. 550 00:23:01,940 --> 00:23:03,700 Ora, tutto quello che ci rimane è uno. 551 00:23:03,700 --> 00:23:07,760 Quindi controlliamo, è questo ciò che stiamo cercando? esso è. 552 00:23:07,760 --> 00:23:08,970 Abbiamo trovato quello che volevamo. 553 00:23:08,970 --> 00:23:10,440 554 00:23:10,440 --> 00:23:11,690 Così abbiamo finito. 555 00:23:11,690 --> 00:23:12,550 Bilineare ricerca. 556 00:23:12,550 --> 00:23:15,740 >> E se ci fate caso, abbiamo aveva sette ingressi lì. 557 00:23:15,740 --> 00:23:24,320 Ci sono voluti solo come tre volte, ma se si sta facendo come un miliardo, 558 00:23:24,320 --> 00:23:28,190 ragazzi sapere quanti passi sarebbe prendere se avessimo quattro miliardi di cose? 559 00:23:28,190 --> 00:23:29,940 560 00:23:29,940 --> 00:23:30,455 Qualche ipotesi? 561 00:23:30,455 --> 00:23:32,286 562 00:23:32,286 --> 00:23:33,960 Si tratta di 32. 563 00:23:33,960 --> 00:23:37,110 32 passi per trovare qualcosa in quattro miliardi 564 00:23:37,110 --> 00:23:39,650 elemento di un array a causa di potenze di due. 565 00:23:39,650 --> 00:23:43,550 Quindi due è a 32, è quello di quattro miliardi. 566 00:23:43,550 --> 00:23:50,430 >> Così come abbastanza pazzo sei ancora all'interno come un numero relativamente basso di passi 567 00:23:50,430 --> 00:23:52,650 di trovare qualcosa in quattro miliardi di elementi. 568 00:23:52,650 --> 00:23:55,730 Quindi, su questa nota, siamo andando a codificare questo 569 00:23:55,730 --> 00:23:58,950 così voi ragazzi può effettivamente tipo di vedere come funziona. 570 00:23:58,950 --> 00:24:01,520 Va bene, quindi voi potete codificare. 571 00:24:01,520 --> 00:24:04,100 Ho intenzione di lasciare che voi ragazzi parlare per un po '. 572 00:24:04,100 --> 00:24:07,970 Vieni a conoscere persone intorno a voi, che è quello che qualcuno voleva da ultima sezione. 573 00:24:07,970 --> 00:24:10,280 >> Quindi, per conoscere le persone intorno a voi. 574 00:24:10,280 --> 00:24:11,305 Parlare per un po '. 575 00:24:11,305 --> 00:24:12,580 576 00:24:12,580 --> 00:24:15,730 E tutto quello che voglio da te ragazzi in questo momento è solo 577 00:24:15,730 --> 00:24:17,575 cercare di creare una struttura di pseudocodice. 578 00:24:17,575 --> 00:24:18,075 Ok? 579 00:24:18,075 --> 00:24:20,825 580 00:24:20,825 --> 00:24:21,325 Whoa. 581 00:24:21,325 --> 00:24:23,320 582 00:24:23,320 --> 00:24:29,520 Tutto quello che voglio da voi ragazzi è che sei solo andando a riempire in questo caso, mentre. 583 00:24:29,520 --> 00:24:32,170 Quindi io ho posto questi superiore e limiti inferiori che 584 00:24:32,170 --> 00:24:35,250 rappresentare l'inizio e fine della nostra matrice. 585 00:24:35,250 --> 00:24:40,440 E si sta andando a realtà loop through e capire 586 00:24:40,440 --> 00:24:42,470 quello che stiamo facendo in questo ciclo while. 587 00:24:42,470 --> 00:24:45,810 >> Quindi, se si riesce a capire fuori-- ho un suggerimento there-- quali sono i casi 588 00:24:45,810 --> 00:24:46,640 che abbiamo qui? 589 00:24:46,640 --> 00:24:48,100 590 00:24:48,100 --> 00:24:51,560 Quindi, se si vuole capire il casi, ci saranno quelli pseudocodice 591 00:24:51,560 --> 00:24:53,350 e poi ci troveremo a loro codice. 592 00:24:53,350 --> 00:24:55,330 E sarà, io pensare, si spera che sarà 593 00:24:55,330 --> 00:24:56,788 essere un po 'più facile del previsto. 594 00:24:56,788 --> 00:24:57,554 595 00:24:57,554 --> 00:25:00,220 Perché non è che molto codice, in realtà, che è davvero cool. 596 00:25:00,220 --> 00:25:34,110 597 00:25:34,110 --> 00:25:35,018 >> Mm-hm? 598 00:25:35,018 --> 00:25:35,893 >> STUDENTE: [incomprensibile]? 599 00:25:35,893 --> 00:25:36,984 600 00:25:36,984 --> 00:25:37,650 ISTRUTTORE: Sì. 601 00:25:37,650 --> 00:25:38,595 C'era qualcosa trovare nel mezzo. 602 00:25:38,595 --> 00:25:39,552 >> STUDENTE: Quindi possiamo usare quella. 603 00:25:39,552 --> 00:25:39,770 Ok. 604 00:25:39,770 --> 00:25:40,603 >> ISTRUTTORE: Perfect. 605 00:25:40,603 --> 00:25:42,950 Ecco, questo è la prima cosa che dobbiamo fare. 606 00:25:42,950 --> 00:25:44,330 Quindi, trovare il centro. 607 00:25:44,330 --> 00:25:45,415 608 00:25:45,415 --> 00:25:45,915 Ottimo. 609 00:25:45,915 --> 00:25:47,770 610 00:25:47,770 --> 00:25:55,010 Così avete un'idea di come potremmo effettivamente trovare il mezzo con il codice? 611 00:25:55,010 --> 00:25:55,980 >> STUDENTE: Sì. 612 00:25:55,980 --> 00:25:57,000 n più di 2? 613 00:25:57,000 --> 00:25:58,500 614 00:25:58,500 --> 00:25:59,500 ISTRUTTORE: Quindi oltre 2 n. 615 00:25:59,500 --> 00:26:05,170 Quindi, una cosa da ricordare è che i tuoi limiti superiori e inferiori cambiano. 616 00:26:05,170 --> 00:26:08,110 Continuiamo costrizione parte della matrice che stiamo cercando di. 617 00:26:08,110 --> 00:26:11,970 Quindi n oltre 2 funziona solo per la prima cosa che facciamo. 618 00:26:11,970 --> 00:26:17,810 Quindi, prendendo superiore e inferiore in considerazione, come potremmo ottenere che elemento centrale? 619 00:26:17,810 --> 00:26:20,640 Perché vogliamo che il centro tra superiore e inferiore, giusto? 620 00:26:20,640 --> 00:26:21,730 621 00:26:21,730 --> 00:26:22,494 Mm-hm? 622 00:26:22,494 --> 00:26:23,369 >> STUDENTE: [incomprensibile]. 623 00:26:23,369 --> 00:26:26,170 624 00:26:26,170 --> 00:26:28,080 >> ISTRUTTORE: Così abbiamo un po 'di mezzo. 625 00:26:28,080 --> 00:26:32,730 E sarà superiore più basso su 2. 626 00:26:32,730 --> 00:26:34,740 627 00:26:34,740 --> 00:26:35,690 Impressionante. 628 00:26:35,690 --> 00:26:36,570 Ci andiamo. 629 00:26:36,570 --> 00:26:37,280 Una linea verso il basso. 630 00:26:37,280 --> 00:26:38,560 Voi ragazzi siete sulla buona strada. 631 00:26:38,560 --> 00:26:41,400 Quindi, ora che abbiamo la nostra mezzo, cosa vogliamo fare? 632 00:26:41,400 --> 00:26:45,050 633 00:26:45,050 --> 00:26:45,900 Proprio in generale. 634 00:26:45,900 --> 00:26:47,734 Non è necessario codificare esso. 635 00:26:47,734 --> 00:26:48,335 Sì. 636 00:26:48,335 --> 00:26:49,210 STUDENTE: [incomprensibile]? 637 00:26:49,210 --> 00:27:00,310 638 00:27:00,310 --> 00:27:10,310 ISTRUTTORE: Quindi è più perché sei calcolando la media tra i due 639 00:27:10,310 --> 00:27:10,810 di loro. 640 00:27:10,810 --> 00:27:11,890 641 00:27:11,890 --> 00:27:17,370 Quindi, se si pensa a loro come genere crescente dai lati, 642 00:27:17,370 --> 00:27:21,640 pensare a come ci si avvicina Al centro, si vuole così. 643 00:27:21,640 --> 00:27:27,150 Quindi, se si fosse su entrambi i lati del mezzo, e abbiamo come 5 e 7. 644 00:27:27,150 --> 00:27:31,440 Quando si aggiunge insieme si ottenere 12, si divide per 2, è di 6. 645 00:27:31,440 --> 00:27:33,726 >> A volte è difficile spiegare perché funziona, 646 00:27:33,726 --> 00:27:35,600 ma se si lavora attraverso un esempio talvolta, 647 00:27:35,600 --> 00:27:37,962 vi aiuterà a capire se dovrebbe essere più o meno. 648 00:27:37,962 --> 00:27:38,846 Sì. 649 00:27:38,846 --> 00:27:40,830 >> STUDENTE: [incomprensibile] esattamente al centro 650 00:27:40,830 --> 00:27:43,950 se avessero un caso in cui ci sono un sacco di numeri più piccoli 651 00:27:43,950 --> 00:27:45,860 e come un gran numero? 652 00:27:45,860 --> 00:27:49,750 >> ISTRUTTORE: Quindi tutto ciò che serve è al centro della matrice. 653 00:27:49,750 --> 00:27:53,010 Quindi, se si ha un gruppo di piccoli numeri e poi un numero molto grande 654 00:27:53,010 --> 00:27:54,799 alla fine, non importa. 655 00:27:54,799 --> 00:27:56,840 Tutto ciò che conta è che stanno ordinati, appena 656 00:27:56,840 --> 00:27:59,339 desiderare di guardare al centro del l'array perché sei ancora 657 00:27:59,339 --> 00:28:00,700 affettare il problema a metà. 658 00:28:00,700 --> 00:28:03,020 659 00:28:03,020 --> 00:28:03,680 Freddo. 660 00:28:03,680 --> 00:28:06,430 Quindi, ora che abbiamo la mezzo, cosa facciamo dopo? 661 00:28:06,430 --> 00:28:07,150 >> STUDENTE: Confronta. 662 00:28:07,150 --> 00:28:08,150 ISTRUTTORE: La confrontare. 663 00:28:08,150 --> 00:28:11,670 Quindi confrontare mezzo a value_wanted. 664 00:28:11,670 --> 00:28:14,300 665 00:28:14,300 --> 00:28:15,160 Freddo. 666 00:28:15,160 --> 00:28:17,950 Quindi, vedete qui abbiamo questo valore vogliamo qui. 667 00:28:17,950 --> 00:28:22,012 668 00:28:22,012 --> 00:28:23,095 Ricordate che questo è un array. 669 00:28:23,095 --> 00:28:24,100 670 00:28:24,100 --> 00:28:26,970 Quindi mezzo si riferisce all'indice. 671 00:28:26,970 --> 00:28:29,785 Così vogliamo fare i valori di centro. 672 00:28:29,785 --> 00:28:32,380 673 00:28:32,380 --> 00:28:35,650 Non dimenticare, se si desidera di confrontare, doppio uguale. 674 00:28:35,650 --> 00:28:38,250 Fate equivale esattamente singolo sei solo andando a riassegnare esso, 675 00:28:38,250 --> 00:28:41,090 e poi, naturalmente, è sarà il valore che si desidera. 676 00:28:41,090 --> 00:28:42,300 Quindi non farlo. 677 00:28:42,300 --> 00:28:44,350 >> Quindi stiamo andando a vedere se i valori a mezzo 678 00:28:44,350 --> 00:28:46,460 è uguale al valore che vogliamo. 679 00:28:46,460 --> 00:28:47,749 680 00:28:47,749 --> 00:28:48,790 Non dimenticare la tua parentesi. 681 00:28:48,790 --> 00:28:50,520 682 00:28:50,520 --> 00:28:52,235 Dropbox dovrebbe andare via. 683 00:28:52,235 --> 00:28:54,140 684 00:28:54,140 --> 00:28:56,200 Allora che cosa facciamo in questo caso? 685 00:28:56,200 --> 00:28:59,360 Se è quello che vogliamo tornare? 686 00:28:59,360 --> 00:29:01,510 687 00:29:01,510 --> 00:29:02,626 Stiamo cercando di dire. 688 00:29:02,626 --> 00:29:03,440 >> STUDENTE: stampare. 689 00:29:03,440 --> 00:29:05,314 >> ISTRUTTORE: Beh, abbiamo non si vuole stampare. 690 00:29:05,314 --> 00:29:08,220 Quindi questo è un bool qui, in modo da vuole restituire true o false. 691 00:29:08,220 --> 00:29:12,280 Noi stiamo dicendo, è questo numero un [? RRA? ?] Quindi, se lo è, 692 00:29:12,280 --> 00:29:13,788 abbiamo appena torniamo vero. 693 00:29:13,788 --> 00:29:16,780 694 00:29:16,780 --> 00:29:17,760 Se posso incantesimo vero. 695 00:29:17,760 --> 00:29:18,830 696 00:29:18,830 --> 00:29:20,805 >> STUDENTE: Perché non si restituire zero? 697 00:29:20,805 --> 00:29:22,930 ISTRUTTORE: così si potrebbe ritorno pari a zero se si voleva. 698 00:29:22,930 --> 00:29:26,780 Ma in questo caso, perché la nostra funzione restituisce un bool, 699 00:29:26,780 --> 00:29:28,962 abbiamo bisogno di tornare true o false. 700 00:29:28,962 --> 00:29:30,920 STUDENTE: Quando sei dicendo espressione booleana, 701 00:29:30,920 --> 00:29:33,450 puoi impostarlo uguale a falso? 702 00:29:33,450 --> 00:29:39,860 Come se voglio dire, se questa condizione non è soddisfatta, come è in alto è uguale a false. 703 00:29:39,860 --> 00:29:42,332 Sarà capire se solo mettere falso dall'altra parte? 704 00:29:42,332 --> 00:29:43,040 ISTRUTTORE: Sì. 705 00:29:43,040 --> 00:29:44,820 Quindi, in realtà, se siete mai fare qualcosa 706 00:29:44,820 --> 00:29:49,600 come è superiore o è inferiore, che restituisce true o false 707 00:29:49,600 --> 00:29:53,850 e in realtà è cattivo stile di diciamo uguale uguale vero o uguale 708 00:29:53,850 --> 00:29:54,840 è uguale a false. 709 00:29:54,840 --> 00:30:00,210 Si desidera utilizzare tale risultato come se stesso come il vostro controllo. 710 00:30:00,210 --> 00:30:04,720 711 00:30:04,720 --> 00:30:05,860 Non è quello che volevo. 712 00:30:05,860 --> 00:30:08,150 713 00:30:08,150 --> 00:30:09,240 Questo è quello che volevo. 714 00:30:09,240 --> 00:30:13,205 Quindi, nel caso di che stai chiedendo su qualcosa di simile a salvare questo in c. 715 00:30:13,205 --> 00:30:16,320 716 00:30:16,320 --> 00:30:25,150 >> Quindi, se abbiamo int main (void) e qualcosa di simile a questo. 717 00:30:25,150 --> 00:30:31,922 E si ha se è superiore di alcuni input e sei 718 00:30:31,922 --> 00:30:33,630 chiedendo se si può fare qualcosa di simile? 719 00:30:33,630 --> 00:30:35,010 720 00:30:35,010 --> 00:30:35,679 Giusto? 721 00:30:35,679 --> 00:30:37,470 STUDENTE: Stavo cercando per farlo [incomprensibile]. 722 00:30:37,470 --> 00:30:38,450 Perché se it's-- 723 00:30:38,450 --> 00:30:39,200 ISTRUTTORE: Giusto. 724 00:30:39,200 --> 00:30:41,197 Così si desidera che questo sia falso, giusto? 725 00:30:41,197 --> 00:30:41,780 STUDENTE: Sì. 726 00:30:41,780 --> 00:30:45,960 ISTRUTTORE: Quindi, in questo caso vogliono da eseguire se non è vero. 727 00:30:45,960 --> 00:30:50,510 Quindi la cosa interessante lì fare è questo. 728 00:30:50,510 --> 00:30:52,900 729 00:30:52,900 --> 00:30:55,650 Quindi ricorda esclamativo punto nega le cose? 730 00:30:55,650 --> 00:30:58,270 Dice [incomprensibile] non significa. 731 00:30:58,270 --> 00:31:03,590 Quindi, se guardiamo solo questa parte qui, che ci si 732 00:31:03,590 --> 00:31:05,740 dicono che restituisce falso come si desidera. 733 00:31:05,740 --> 00:31:06,790 734 00:31:06,790 --> 00:31:09,880 Non è falso è vero che significa che questo sarebbe eseguire. 735 00:31:09,880 --> 00:31:11,037 Questo fa senso? 736 00:31:11,037 --> 00:31:11,620 STUDENTE: Sì. 737 00:31:11,620 --> 00:31:12,453 ISTRUTTORE: Awesome. 738 00:31:12,453 --> 00:31:13,800 739 00:31:13,800 --> 00:31:14,300 Ok. 740 00:31:14,300 --> 00:31:16,330 Così abbiamo potuto solo tornare vero in questo caso. 741 00:31:16,330 --> 00:31:20,357 Così ora abbiamo due altri casi in questo caso. 742 00:31:20,357 --> 00:31:21,565 Quali sono i nostri altri due casi? 743 00:31:21,565 --> 00:31:31,610 744 00:31:31,610 --> 00:31:32,900 Diciamo solo farlo in questo modo. 745 00:31:32,900 --> 00:31:40,660 Quindi cominciamo con il resto se valori a mezzo 746 00:31:40,660 --> 00:31:43,230 è inferiore al valore che vogliamo. 747 00:31:43,230 --> 00:31:47,200 748 00:31:47,200 --> 00:31:52,020 Quindi il nostro valore nel mezzo è meno rispetto al valore che stiamo cercando. 749 00:31:52,020 --> 00:31:53,765 750 00:31:53,765 --> 00:31:56,720 >> Quindi, quale limite si fa pensiamo vogliamo aggiornare? 751 00:31:56,720 --> 00:31:57,870 752 00:31:57,870 --> 00:31:58,780 Superiore o inferiore? 753 00:31:58,780 --> 00:32:01,440 754 00:32:01,440 --> 00:32:01,940 Superiore? 755 00:32:01,940 --> 00:32:03,230 756 00:32:03,230 --> 00:32:06,470 Quindi quale lato della matrice abbiamo intenzione di essere alla ricerca di? 757 00:32:06,470 --> 00:32:07,500 >> STUDENTE: Più bassa. 758 00:32:07,500 --> 00:32:09,750 >> ISTRUTTORE: Noi stiamo andando essere guardando sinistra. 759 00:32:09,750 --> 00:32:11,120 Quindi, altrimenti se poco valore è inferiore. 760 00:32:11,120 --> 00:32:14,730 Così il vostro valore medio qui è inferiore a quello che vogliamo. 761 00:32:14,730 --> 00:32:17,202 Quindi, vogliamo prendere il lato destro della nostra matrice. 762 00:32:17,202 --> 00:32:18,910 Quindi stiamo andando a aggiornare il nostro limite inferiore. 763 00:32:18,910 --> 00:32:20,210 764 00:32:20,210 --> 00:32:23,020 Quindi dovremo riassegnare il nostro più bassa. 765 00:32:23,020 --> 00:32:25,221 E voi cosa ne pensate inferiore dovrebbe essere? 766 00:32:25,221 --> 00:32:26,304 STUDENTE: Il valore centrale? 767 00:32:26,304 --> 00:32:27,446 768 00:32:27,446 --> 00:32:28,820 ISTRUTTORE: Così il value-- mezzo 769 00:32:28,820 --> 00:32:30,136 STUDENTE: Plus 1. 770 00:32:30,136 --> 00:32:31,010 ISTRUTTORE: --plus 1. 771 00:32:31,010 --> 00:32:32,300 772 00:32:32,300 --> 00:32:34,380 Qualcuno può dirmi perché abbiamo che più 1? 773 00:32:34,380 --> 00:32:35,730 >> STUDENTE: [? Nessun valore?] è più uguale ad esso. 774 00:32:35,730 --> 00:32:36,120 >> ISTRUTTORE: Giusto. 775 00:32:36,120 --> 00:32:38,661 Perché sappiamo già che il valore medio non è uguale a 776 00:32:38,661 --> 00:32:42,750 e vogliamo escluderlo da tutte le ricerche successive. 777 00:32:42,750 --> 00:32:46,360 Se si dimentica che più 1, questo sarà come ciclo a tempo indeterminato. 778 00:32:46,360 --> 00:32:49,620 E devi semplicemente essere catturati in un ciclo infinito e poi ti segfault 779 00:32:49,620 --> 00:32:50,370 e le cose vanno male. 780 00:32:50,370 --> 00:32:54,780 Quindi, accertarsi sempre che non sei compreso il valore che avete appena 781 00:32:54,780 --> 00:32:55,380 guardato. 782 00:32:55,380 --> 00:32:58,530 Così ci prendiamo cura di che con un più 1. 783 00:32:58,530 --> 00:33:04,840 >> Così ora abbiamo la nostra ultima condizione che ho sempre per motivi di sicurezza 784 00:33:04,840 --> 00:33:12,664 è possibile controllare qui, altrimenti se il valore a il mezzo è maggiore del valore 785 00:33:12,664 --> 00:33:13,163 che vogliamo. 786 00:33:13,163 --> 00:33:16,260 787 00:33:16,260 --> 00:33:20,230 Ciò significa che vogliamo metà sinistra. 788 00:33:20,230 --> 00:33:21,350 789 00:33:21,350 --> 00:33:23,260 Quindi quale stiamo andando ad aggiornare? 790 00:33:23,260 --> 00:33:23,760 Superiore. 791 00:33:23,760 --> 00:33:25,470 792 00:33:25,470 --> 00:33:26,970 E qual è questo uno che va a pari? 793 00:33:26,970 --> 00:33:31,630 794 00:33:31,630 --> 00:33:33,690 Medio meno 1 perché, naturalmente, vogliamo 795 00:33:33,690 --> 00:33:38,370 per essere sicuri che non siamo guardando quel valore centrale di nuovo. 796 00:33:38,370 --> 00:33:41,830 797 00:33:41,830 --> 00:33:45,110 E allora noi ce l'abbiamo. 798 00:33:45,110 --> 00:33:45,610 Questo è tutto. 799 00:33:45,610 --> 00:33:46,820 Questo è tutto ciò di ricerca binaria è. 800 00:33:46,820 --> 00:33:48,190 Non è poi così male, vero? 801 00:33:48,190 --> 00:33:51,590 E 'come 10 linee di codice con uno spazio bianco. 802 00:33:51,590 --> 00:33:57,510 Quindi molto potente, molto utile, sarà essere di utilizzarlo in una delle tue p-set successivi. 803 00:33:57,510 --> 00:33:59,360 Forse non questo, ma più tardi. 804 00:33:59,360 --> 00:34:00,670 Quindi imparare. 805 00:34:00,670 --> 00:34:01,510 Lo adoro. 806 00:34:01,510 --> 00:34:02,980 Si tratterà bene. 807 00:34:02,980 --> 00:34:05,370 Così qualcuno ha qualche domande sul binario di ricerca? 808 00:34:05,370 --> 00:34:06,196 Sì. 809 00:34:06,196 --> 00:34:09,840 >> STUDENTE: Ha importanza se il n è pari o dispari? 810 00:34:09,840 --> 00:34:10,750 >> ISTRUTTORE: No. 811 00:34:10,750 --> 00:34:18,150 Perché abbiamo gettato al centro come un int, sarà solo troncherà esso. 812 00:34:18,150 --> 00:34:21,600 Quindi rimarrà un intero e sarà eventualmente ordinare attraverso tutto ciò. 813 00:34:21,600 --> 00:34:23,909 Quindi non dovete preoccuparvi di questo. 814 00:34:23,909 --> 00:34:24,580 Tutto bene? 815 00:34:24,580 --> 00:34:25,659 816 00:34:25,659 --> 00:34:26,850 Impressionante. 817 00:34:26,850 --> 00:34:27,919 Freddo. 818 00:34:27,919 --> 00:34:30,836 Così, voi ragazzi ha ottenuto questo. 819 00:34:30,836 --> 00:34:33,380 820 00:34:33,380 --> 00:34:33,880 Slideshow. 821 00:34:33,880 --> 00:34:35,719 822 00:34:35,719 --> 00:34:43,270 Così come stavamo parlando, lo so David menzionato runtime complessità. 823 00:34:43,270 --> 00:34:44,420 824 00:34:44,420 --> 00:34:50,340 >> Quindi, nel migliore dei casi, è solo uno, che noi chiamiamo costante di tempo. 825 00:34:50,340 --> 00:34:51,909 Qualcuno può dirmi il motivo che potrebbe essere? 826 00:34:51,909 --> 00:34:52,969 827 00:34:52,969 --> 00:34:55,800 Che tipo di scenario che comporterebbe? 828 00:34:55,800 --> 00:34:58,260 829 00:34:58,260 --> 00:34:58,760 Mm-hm. 830 00:34:58,760 --> 00:34:59,926 >> STUDENTE: [incomprensibile] first-- 831 00:34:59,926 --> 00:35:00,789 832 00:35:00,789 --> 00:35:03,830 ISTRUTTORE: Quindi la centrale è la primo elemento che veniamo a, giusto? 833 00:35:03,830 --> 00:35:08,167 Quindi, o una serie di uno o tutto ciò che stiamo cercando solo 834 00:35:08,167 --> 00:35:09,750 sembra essere nel bel mezzo. 835 00:35:09,750 --> 00:35:11,190 836 00:35:11,190 --> 00:35:13,380 Ecco, questo è il nostro migliore dei casi. 837 00:35:13,380 --> 00:35:17,540 Si ottiene in problemi reali, probabilmente non andando a raggiungere il [incomprensibile] che spesso. 838 00:35:17,540 --> 00:35:18,667 839 00:35:18,667 --> 00:35:19,750 E il nostro caso peggiore? 840 00:35:19,750 --> 00:35:21,270 Il nostro caso peggiore è log n. 841 00:35:21,270 --> 00:35:25,360 E questo ha a che fare con tutta la potenze di due cosa che ho parlato. 842 00:35:25,360 --> 00:35:30,930 >> Quindi, nel caso peggiore significherebbe che abbiamo dovuto tagliare la matrice verso il basso 843 00:35:30,930 --> 00:35:33,270 finché era un elemento di uno. 844 00:35:33,270 --> 00:35:34,810 845 00:35:34,810 --> 00:35:38,930 Così abbiamo dovuto tagliare verso il basso a metà il numero di volte che potevamo. 846 00:35:38,930 --> 00:35:41,430 Ecco perché è log n, perché basta tenere dividendo per due. 847 00:35:41,430 --> 00:35:42,890 848 00:35:42,890 --> 00:35:45,830 Così ipotesi, cose che voi bisogno di sapere se siete mai 849 00:35:45,830 --> 00:35:48,050 intenzione di usare una ricerca binaria. 850 00:35:48,050 --> 00:35:50,680 I suoi elementi devono essere ordinati. 851 00:35:50,680 --> 00:35:53,890 Devono essere ordinati perché questo è l'unico modo in cui si 852 00:35:53,890 --> 00:35:57,060 può sapere se si è in grado buttare via la metà di esso. 853 00:35:57,060 --> 00:36:00,260 >> Se hai avuto questa borsa confuso di numeri e che stai dicendo, 854 00:36:00,260 --> 00:36:05,380 OK, vado a controllare il mezzo numero e il numero che sto cercando 855 00:36:05,380 --> 00:36:08,510 è inferiore a quello, sto solo andando gettare arbitrariamente fuori una metà. 856 00:36:08,510 --> 00:36:11,130 Tu non sapere se il vostro numeri in detto altro mezzo. 857 00:36:11,130 --> 00:36:12,655 Il tuo elenco deve essere ordinato. 858 00:36:12,655 --> 00:36:14,030 859 00:36:14,030 --> 00:36:16,560 Inoltre, questo può essere andando avanti un po ', 860 00:36:16,560 --> 00:36:18,360 ma è necessario disporre di accesso casuale. 861 00:36:18,360 --> 00:36:21,940 È necessario essere in grado di solo andare a quel elemento centrale. 862 00:36:21,940 --> 00:36:25,110 Se si deve attraversare attraverso qualcosa 863 00:36:25,110 --> 00:36:28,630 o ci vogliono misure supplementari per arrivare a questo elemento centrale, 864 00:36:28,630 --> 00:36:31,750 non è più perché log n si aggiunge più lavoro in esso. 865 00:36:31,750 --> 00:36:34,800 E questo renderà un po ' più senso in due settimane, 866 00:36:34,800 --> 00:36:37,950 ma ho appena sorta di voluto premettere, voi ragazzi dare un'idea di ciò che è 867 00:36:37,950 --> 00:36:38,999 a venire. 868 00:36:38,999 --> 00:36:40,790 Ma questi sono i due presupposti importanti 869 00:36:40,790 --> 00:36:44,804 che è necessario per un elenco binario. 870 00:36:44,804 --> 00:36:45,720 Assicuratevi che sia risolto. 871 00:36:45,720 --> 00:36:47,920 Questo è il grande per ragazzi adesso. 872 00:36:47,920 --> 00:36:52,170 E su questo siamo in grado di andare in il resto della nostra specie. 873 00:36:52,170 --> 00:36:56,444 Così quattro bolla sorts--, l'inserimento, la selezione, e si fondono. 874 00:36:56,444 --> 00:36:57,485 Sono tutti i tipi di fresco. 875 00:36:57,485 --> 00:37:02,860 Se voi ragazzi decidono di prendere CS 124, imparerete a conoscere tutti i tipi di sorta. 876 00:37:02,860 --> 00:37:07,575 E se sei un fan di XKCD, ci è un fumetto davvero cool su 877 00:37:07,575 --> 00:37:11,530 come i tipi veramente inefficaci, che ho consigliamo di andare a guardare. 878 00:37:11,530 --> 00:37:16,170 Uno di loro è come il panico specie, che è come, oh no, tornare matrice casuale. 879 00:37:16,170 --> 00:37:16,991 Sistema di arresto. 880 00:37:16,991 --> 00:37:17,490 Lascia. 881 00:37:17,490 --> 00:37:19,070 882 00:37:19,070 --> 00:37:21,500 Così l'umorismo geek è sempre buona. 883 00:37:21,500 --> 00:37:22,620 884 00:37:22,620 --> 00:37:25,750 >> Così qualcuno si ricorda genere di come solo un'idea generale 885 00:37:25,750 --> 00:37:27,810 di come funziona bubble sort. 886 00:37:27,810 --> 00:37:31,130 887 00:37:31,130 --> 00:37:32,155 Ti ricordi? 888 00:37:32,155 --> 00:37:32,755 >> STUDENTE: Sì. 889 00:37:32,755 --> 00:37:33,970 >> ISTRUTTORE: Go for it. 890 00:37:33,970 --> 00:37:38,980 >> STUDENTE: Quindi stai passando e se è più grande, poi si scambiano i due. 891 00:37:38,980 --> 00:37:39,820 >> ISTRUTTORE: Mm-hm. 892 00:37:39,820 --> 00:37:40,564 Esattamente. 893 00:37:40,564 --> 00:37:41,730 Quindi basta eseguire iterazioni. 894 00:37:41,730 --> 00:37:43,050 Controllate due numeri. 895 00:37:43,050 --> 00:37:46,510 Se il precedente è più grande di quella successiva, 896 00:37:46,510 --> 00:37:50,230 appena li scambiano in modo che in in questo modo tutti i numeri superiori 897 00:37:50,230 --> 00:37:54,990 bolla verso la fine della lista e tutti i numeri inferiori bolla verso il basso. 898 00:37:54,990 --> 00:37:59,355 >> Ti ha mostrano ragazzi il fresco effetto sonoro di ordinamento video? 899 00:37:59,355 --> 00:38:00,480 È un po 'freddo. 900 00:38:00,480 --> 00:38:01,510 901 00:38:01,510 --> 00:38:05,200 Quindi, come ha appena detto Robert, l'algoritmo che hai appena passo attraverso la lista, 902 00:38:05,200 --> 00:38:07,930 scambiando i valori adiacenti se non sono in ordine. 903 00:38:07,930 --> 00:38:10,975 E poi basta continuare a ripetere fino a quando non si effettuano operazioni di swap. 904 00:38:10,975 --> 00:38:11,990 905 00:38:11,990 --> 00:38:12,740 Quindi non male, vero? 906 00:38:12,740 --> 00:38:14,080 907 00:38:14,080 --> 00:38:16,319 Quindi non ci resta che un esempio veloce qui. 908 00:38:16,319 --> 00:38:18,360 Quindi questo sta per ordinare li in ordine crescente. 909 00:38:18,360 --> 00:38:19,470 910 00:38:19,470 --> 00:38:23,470 Così, quando andiamo attraverso il primo tempo, guardiamo attraverso otto 911 00:38:23,470 --> 00:38:26,880 e sei non sono ovviamente in ordine, li scambiamo. 912 00:38:26,880 --> 00:38:27,985 >> Così guardare il prossimo. 913 00:38:27,985 --> 00:38:29,430 Otto e quattro non in ordine. 914 00:38:29,430 --> 00:38:30,450 Scambiarli. 915 00:38:30,450 --> 00:38:32,530 E poi otto e due, li scambiano. 916 00:38:32,530 --> 00:38:33,470 Ci andiamo. 917 00:38:33,470 --> 00:38:39,519 Così, dopo il primo passaggio, si sapere che il maggior numero 918 00:38:39,519 --> 00:38:41,810 sta per essere fino in fondo in alto perché è solo 919 00:38:41,810 --> 00:38:44,210 sta per essere costantemente più grande di tutto il resto 920 00:38:44,210 --> 00:38:46,810 ed è solo andando a bolla up fino alla fine lì. 921 00:38:46,810 --> 00:38:48,226 Non che abbia un senso per tutti? 922 00:38:48,226 --> 00:38:48,560 923 00:38:48,560 --> 00:38:49,060 Freddo. 924 00:38:49,060 --> 00:38:51,310 925 00:38:51,310 --> 00:38:53,920 >> Allora guardiamo al nostro secondo passaggio. 926 00:38:53,920 --> 00:38:54,980 Sei e quattro, l'interruttore. 927 00:38:54,980 --> 00:38:55,920 Sei e due, l'interruttore. 928 00:38:55,920 --> 00:38:58,700 E ora abbiamo un paio di cose in ordine. 929 00:38:58,700 --> 00:39:02,240 Quindi per ogni passo che abbiamo fare attraverso tutta la nostra lista, 930 00:39:02,240 --> 00:39:06,320 sappiamo che, come che molti numeri alla fine saranno state filtrate. 931 00:39:06,320 --> 00:39:07,690 932 00:39:07,690 --> 00:39:09,610 Quindi facciamo un terzo passaggio, che è uno scambio. 933 00:39:09,610 --> 00:39:10,860 934 00:39:10,860 --> 00:39:15,910 E poi il nostro quarto passare, abbiamo a zero slot. 935 00:39:15,910 --> 00:39:18,570 E così sappiamo che il nostro array è stato ordinato. 936 00:39:18,570 --> 00:39:20,900 >> E questo è il grande cosa con bubble sort. 937 00:39:20,900 --> 00:39:23,720 Sappiamo che quando abbiamo avere zero swap, che 938 00:39:23,720 --> 00:39:26,497 significa che tutto è in modo completo. 939 00:39:26,497 --> 00:39:27,580 È un po 'come controlliamo. 940 00:39:27,580 --> 00:39:28,740 941 00:39:28,740 --> 00:39:36,480 Così stiamo anche andando a codificare bolla che tipo, inoltre, non è poi così male. 942 00:39:36,480 --> 00:39:38,120 Nessuno di questi sono così male. 943 00:39:38,120 --> 00:39:40,210 So che può sembrare un po 'paura. 944 00:39:40,210 --> 00:39:42,124 So che quando ho preso la classe, anche quando 945 00:39:42,124 --> 00:39:44,290 insegnava la classe per la prima volta lo scorso anno, 946 00:39:44,290 --> 00:39:46,165 Ero come, come posso fare questo? 947 00:39:46,165 --> 00:39:48,540 Ha senso in teoria, ma come possiamo effettivamente fare questo? 948 00:39:48,540 --> 00:39:51,420 È per questo che voglio anche andare a piedi tramite il codice con voi qui. 949 00:39:51,420 --> 00:39:54,915 Così ho un pseudocodice per voi ragazzi questa volta. 950 00:39:54,915 --> 00:39:55,950 951 00:39:55,950 --> 00:39:58,970 Quindi basta tenere questo in mente come stiamo per passare oltre. 952 00:39:58,970 --> 00:40:04,210 Così abbiamo un po 'di contatore che tiene traccia dei nostri swap, 953 00:40:04,210 --> 00:40:08,370 perché abbiamo bisogno di fare in modo che stiamo controllando che. 954 00:40:08,370 --> 00:40:11,830 E iteriamo l'intero array come abbiamo appena fatto con questo esempio. 955 00:40:11,830 --> 00:40:12,900 956 00:40:12,900 --> 00:40:17,325 Se l'elemento prima è maggiore l'elemento dopo dove siamo, 957 00:40:17,325 --> 00:40:20,760 noi li scambiamo e incrementiamo il nostro contatore perché non appena ci scambiamo, 958 00:40:20,760 --> 00:40:23,850 vogliamo lasciare il nostro contatore sapere che. 959 00:40:23,850 --> 00:40:26,247 Tutte le domande lì? 960 00:40:26,247 --> 00:40:27,580 Qualcosa sembra divertente qui. 961 00:40:27,580 --> 00:40:29,225 962 00:40:29,225 --> 00:40:32,350 STUDENTE: Avete impostato il contatore a zero ogni volta che si passa attraverso il ciclo? 963 00:40:32,350 --> 00:40:34,339 Non andare avanti torna a zero ogni volta? 964 00:40:34,339 --> 00:40:35,505 ISTRUTTORE: Non necessariamente. 965 00:40:35,505 --> 00:40:39,710 Quindi, quello che succede è che andiamo di qui. 966 00:40:39,710 --> 00:40:43,830 Quindi fare mentre, ricordate, questo sarà eseguita una volta a colpo sicuro. 967 00:40:43,830 --> 00:40:46,480 Così sta andando a impostare la controvalore pari a zero, 968 00:40:46,480 --> 00:40:48,070 allora sta andando a scorrere. 969 00:40:48,070 --> 00:40:50,590 Mentre esegue un'iterazione, verrà aggiornato contatore. 970 00:40:50,590 --> 00:40:51,870 971 00:40:51,870 --> 00:40:56,900 Come si aggiorna il contatore, quando è fatto, quando viene raggiunta la fine dell'array, 972 00:40:56,900 --> 00:41:00,830 se il nostro elenco non è stato ordinato, contatore sono stati aggiornati. 973 00:41:00,830 --> 00:41:01,840 974 00:41:01,840 --> 00:41:07,150 >> Ecco che allora si verifica la condizione e dice, OK, è contatore maggiore di zero. 975 00:41:07,150 --> 00:41:09,290 Se lo è, farlo di nuovo. 976 00:41:09,290 --> 00:41:14,340 Si desidera ripristinare in modo che quando si passare attraverso, contatore è uguale a zero. 977 00:41:14,340 --> 00:41:18,240 Se si passa attraverso un ordinato array, non cambia nulla, 978 00:41:18,240 --> 00:41:21,355 questo non riesce e viene restituisce la lista ordinata. 979 00:41:21,355 --> 00:41:23,104 980 00:41:23,104 --> 00:41:24,020 Fa questo ha un senso? 981 00:41:24,020 --> 00:41:24,940 982 00:41:24,940 --> 00:41:26,356 STUDENTE: Potrebbe in un po '. 983 00:41:26,356 --> 00:41:27,147 ISTRUTTORE: OK. 984 00:41:27,147 --> 00:41:28,980 Se c'è un altro domanda che viene in su. 985 00:41:28,980 --> 00:41:30,180 986 00:41:30,180 --> 00:41:30,680 Sì. 987 00:41:30,680 --> 00:41:33,760 >> STUDENTE: Cosa sarebbe la funzione essere per scambiare gli elementi? 988 00:41:33,760 --> 00:41:36,900 >> ISTRUTTORE: Così possiamo effettivamente scrivere che se stiamo andando in questo momento. 989 00:41:36,900 --> 00:41:37,801 990 00:41:37,801 --> 00:41:38,300 Freddo. 991 00:41:38,300 --> 00:41:42,155 Quindi, su questa nota, Alison sta andando per tornare alla macchina. 992 00:41:42,155 --> 00:41:43,080 Sta andando essere divertente. 993 00:41:43,080 --> 00:41:45,170 994 00:41:45,170 --> 00:41:47,390 E noi abbiamo la nostra bella bubble sort cosa qui. 995 00:41:47,390 --> 00:41:50,800 Così ho già fatto in bicicletta attraverso l'array. 996 00:41:50,800 --> 00:41:53,030 Abbiamo i nostri swap che sono uguali a zero. 997 00:41:53,030 --> 00:41:54,480 998 00:41:54,480 --> 00:41:58,440 Quindi vogliamo scambiare adiacente elementi se sono fuori uso. 999 00:41:58,440 --> 00:42:03,020 Quindi la prima cosa abbiamo bisogno di non è scorrere la nostra gamma. 1000 00:42:03,020 --> 00:42:04,500 1001 00:42:04,500 --> 00:42:08,260 >> Quindi, come si fa a pensare che potrebbe scorrere la nostra gamma? 1002 00:42:08,260 --> 00:42:09,720 1003 00:42:09,720 --> 00:42:13,990 Abbiamo per e i è uguale a 0. 1004 00:42:13,990 --> 00:42:16,950 1005 00:42:16,950 --> 00:42:22,454 Vogliamo i per essere meno di n meno 1 meno k. 1006 00:42:22,454 --> 00:42:23,870 E ti spiego che in un secondo. 1007 00:42:23,870 --> 00:42:26,280 1008 00:42:26,280 --> 00:42:32,830 Quindi si tratta di una ottimizzazione qui dove, ricordare come ho detto dopo ogni passaggio 1009 00:42:32,830 --> 00:42:36,655 attraverso la matrice di noi sapere che tutto ciò che è on-- 1010 00:42:36,655 --> 00:42:43,590 1011 00:42:43,590 --> 00:42:46,295 >> Così, dopo un passaggio che so che questo è ordinato. 1012 00:42:46,295 --> 00:42:47,370 1013 00:42:47,370 --> 00:42:50,060 Dopo due passaggi che conosciamo che tutto questo è ordinato. 1014 00:42:50,060 --> 00:42:52,750 Dopo tre passaggi siamo sanno che è ordinato. 1015 00:42:52,750 --> 00:42:55,620 Quindi il modo in cui sto iterazione attraverso la matrice qui 1016 00:42:55,620 --> 00:43:01,090 è vero è fare in modo di andare solo attraverso quello che sappiamo è indifferenziati. 1017 00:43:01,090 --> 00:43:01,644 Ok? 1018 00:43:01,644 --> 00:43:02,810 Questo è solo una ottimizzazione. 1019 00:43:02,810 --> 00:43:04,430 1020 00:43:04,430 --> 00:43:08,210 Si potrebbe scrivere ingenuamente solo l'iterazione attraverso tutto ciò, 1021 00:43:08,210 --> 00:43:09,970 sarebbe solo necessario più tempo. 1022 00:43:09,970 --> 00:43:12,470 Con questo ciclo di quattro è solo una bella ottimizzazione 1023 00:43:12,470 --> 00:43:18,460 perché sappiamo che dopo ogni pieno un'iterazione attraverso l'array qui, 1024 00:43:18,460 --> 00:43:24,050 come ogni ciclo completo qui, sappiamo che uno più di questi elementi 1025 00:43:24,050 --> 00:43:25,760 sarà filtrate alla fine. 1026 00:43:25,760 --> 00:43:28,294 >> Quindi non dobbiamo preoccuparci di quelli. 1027 00:43:28,294 --> 00:43:29,710 Non che abbia un senso per tutti? 1028 00:43:29,710 --> 00:43:30,950 Questo piccolo trucco fresco? 1029 00:43:30,950 --> 00:43:32,060 1030 00:43:32,060 --> 00:43:37,270 Quindi, in questo caso, se stiamo scorrendo, 1031 00:43:37,270 --> 00:43:50,590 sappiamo che vogliamo verificare se matrice n ed n + 1 sono in ordine. 1032 00:43:50,590 --> 00:43:52,640 1033 00:43:52,640 --> 00:43:53,559 Ok. 1034 00:43:53,559 --> 00:43:54,600 Quindi, ecco la pseudocodice. 1035 00:43:54,600 --> 00:43:57,540 Vogliamo verificare se array di n ed n + 1 sono in ordine. 1036 00:43:57,540 --> 00:43:59,520 Che cosa potremmo fare lì? 1037 00:43:59,520 --> 00:44:01,090 1038 00:44:01,090 --> 00:44:03,120 Sta andando essere qualche condizionale. 1039 00:44:03,120 --> 00:44:04,220 Sarà un caso. 1040 00:44:04,220 --> 00:44:07,066 >> STUDENTE: Se array di n è meno di array di n + 1. 1041 00:44:07,066 --> 00:44:07,816 ISTRUTTORE: Mm-hm. 1042 00:44:07,816 --> 00:44:09,000 1043 00:44:09,000 --> 00:44:10,699 Ebbene, inferiore o superiore. 1044 00:44:10,699 --> 00:44:11,615 STUDENTE: Maggiore di. 1045 00:44:11,615 --> 00:44:15,850 1046 00:44:15,850 --> 00:44:17,620 Poi vogliamo scambiarle. 1047 00:44:17,620 --> 00:44:18,570 Esattamente. 1048 00:44:18,570 --> 00:44:23,570 Così ora arriviamo in quello che è il meccanismo per lo scambio di loro? 1049 00:44:23,570 --> 00:44:24,840 1050 00:44:24,840 --> 00:44:28,137 Così siamo andati attraverso questo breve, un tipo di funzione swap scorsa settimana. 1051 00:44:28,137 --> 00:44:29,595 Qualcuno ricorda come funzionava? 1052 00:44:29,595 --> 00:44:32,300 1053 00:44:32,300 --> 00:44:34,950 Quindi noi non possiamo semplicemente riassegnare, giusto? 1054 00:44:34,950 --> 00:44:36,640 Perché uno di loro andranno persi. 1055 00:44:36,640 --> 00:44:41,696 Se abbiamo detto A è uguale a B e poi B è uguale ad A, tutto ad un tratto entrambi 1056 00:44:41,696 --> 00:44:43,150 sono solo pari a B. 1057 00:44:43,150 --> 00:44:45,720 >> Quindi quello che dobbiamo fare è che avere una variabile temporanea che è 1058 00:44:45,720 --> 00:44:49,055 intenzione di tenere uno dei nostri, mentre siamo nel processo di scambio. 1059 00:44:49,055 --> 00:44:50,200 1060 00:44:50,200 --> 00:44:56,464 Quindi ciò che abbiamo è che avremo un po 'di int temperatura è uguale a-- è possibile assegnarlo 1061 00:44:56,464 --> 00:44:59,130 a seconda di quale quello che si desidera, basta assicuratevi di tenere traccia di it-- 1062 00:44:59,130 --> 00:45:01,840 quindi in questo caso, ho intenzione di assegnarlo a matrice n + 1. 1063 00:45:01,840 --> 00:45:03,360 1064 00:45:03,360 --> 00:45:07,674 In modo che sta andando a tenere tutto ciò che valore è in questo secondo blocco 1065 00:45:07,674 --> 00:45:08,590 che stiamo guardando. 1066 00:45:08,590 --> 00:45:09,700 1067 00:45:09,700 --> 00:45:13,240 >> E allora che possiamo fare è che possiamo andare avanti e serie Riassegna n + 1, 1068 00:45:13,240 --> 00:45:14,990 perché sappiamo che avere quel valore memorizzato. 1069 00:45:14,990 --> 00:45:16,645 1070 00:45:16,645 --> 00:45:19,270 Questo è anche uno dei grandi things-- Non so se qualcuno di voi 1071 00:45:19,270 --> 00:45:23,780 avuto problemi in cui se si passa a due righe di codice improvvisamente le cose funzionavano. 1072 00:45:23,780 --> 00:45:25,880 L'ordine è molto importante in CS. 1073 00:45:25,880 --> 00:45:29,450 Quindi assicuratevi di diagramma le cose, se possibile, 1074 00:45:29,450 --> 00:45:31,230 su ciò che sta realmente accadendo. 1075 00:45:31,230 --> 00:45:34,256 Così ora stiamo andando a riassegnare array di n + 1, 1076 00:45:34,256 --> 00:45:36,005 perché sappiamo che avere quel valore memorizzato. 1077 00:45:36,005 --> 00:45:37,090 1078 00:45:37,090 --> 00:45:41,560 >> E possiamo assegnare tale a matrice n o in questo caso matrice i. 1079 00:45:41,560 --> 00:45:50,540 1080 00:45:50,540 --> 00:45:51,465 Troppe variabili. 1081 00:45:51,465 --> 00:45:54,230 1082 00:45:54,230 --> 00:45:55,470 Ok. 1083 00:45:55,470 --> 00:46:01,500 Matrice Così ora abbiamo riassegnato i più 1 per eguagliare ciò che è in serie i. 1084 00:46:01,500 --> 00:46:08,240 Ed ora possiamo tornare indietro e assegnare serie i per che cosa? 1085 00:46:08,240 --> 00:46:10,680 1086 00:46:10,680 --> 00:46:11,180 Chiunque? 1087 00:46:11,180 --> 00:46:13,490 1088 00:46:13,490 --> 00:46:14,010 >> STUDENTE: 10. 1089 00:46:14,010 --> 00:46:14,680 >> ISTRUTTORE: 10. 1090 00:46:14,680 --> 00:46:15,180 Esattamente. 1091 00:46:15,180 --> 00:46:16,930 1092 00:46:16,930 --> 00:46:18,640 E un'ultima cosa. 1093 00:46:18,640 --> 00:46:21,840 Se abbiamo scambiato ora, che cosa dobbiamo fare? 1094 00:46:21,840 --> 00:46:23,740 Qual è l'unica cosa che sta per dirci 1095 00:46:23,740 --> 00:46:27,542 se mai terminiamo questo programma? 1096 00:46:27,542 --> 00:46:29,250 Che cosa ci dice che noi avere una lista ordinata? 1097 00:46:29,250 --> 00:46:31,560 1098 00:46:31,560 --> 00:46:33,750 Se non si esegue alcuna swap, giusto? 1099 00:46:33,750 --> 00:46:36,900 Se swap è pari a azzerare alla fine di questo. 1100 00:46:36,900 --> 00:46:42,975 Così ogni volta che si esegue uno swap, come noi appena fatto qui, vogliamo aggiornare swap. 1101 00:46:42,975 --> 00:46:45,002 1102 00:46:45,002 --> 00:46:47,210 E so che c'è stato un domanda precedente riguardo anche voi 1103 00:46:47,210 --> 00:46:49,689 utilizzare zero o uno invece di vero o falso. 1104 00:46:49,689 --> 00:46:50,980 Ed è quello che fa qui. 1105 00:46:50,980 --> 00:46:52,750 Quindi questo dice che se non swap. 1106 00:46:52,750 --> 00:47:01,310 Quindi, se swap è pari a zero, che è-- ho sempre mettere le verità ei miei falses mescolati. 1107 00:47:01,310 --> 00:47:03,960 Vogliamo di valutare di vero e non lo è. 1108 00:47:03,960 --> 00:47:07,680 1109 00:47:07,680 --> 00:47:09,630 Quindi, se è pari a zero, allora è falso. 1110 00:47:09,630 --> 00:47:12,560 Se si nega con un [? Bang?] diventa vero. 1111 00:47:12,560 --> 00:47:13,975 Allora questa linea esegue. 1112 00:47:13,975 --> 00:47:15,060 1113 00:47:15,060 --> 00:47:17,370 >> Verità e falsi e zero e uno impazzire. 1114 00:47:17,370 --> 00:47:20,690 Solo se si cammina lentamente attraverso di essa sarà un senso. 1115 00:47:20,690 --> 00:47:23,320 Ma questo è ciò che questo piccolo pezzo di codice qui fa. 1116 00:47:23,320 --> 00:47:26,490 Quindi questa verifica abbiamo fatto nessuna swap. 1117 00:47:26,490 --> 00:47:30,054 Quindi, se si tratta di qualche cosa oltre pari a zero, che sta per essere falso 1118 00:47:30,054 --> 00:47:31,970 e il tutto è andando a eseguire di nuovo. 1119 00:47:31,970 --> 00:47:33,150 1120 00:47:33,150 --> 00:47:33,650 Cool? 1121 00:47:33,650 --> 00:47:34,660 1122 00:47:34,660 --> 00:47:36,000 >> STUDENTE: Cosa pausa fare? 1123 00:47:36,000 --> 00:47:38,990 >> ISTRUTTORE: Rompere solo si rompe fuori dal giro. 1124 00:47:38,990 --> 00:47:41,570 Quindi in questo caso sarebbe proprio come terminare il programma 1125 00:47:41,570 --> 00:47:43,828 e si farebbe solo avere la vostra lista ordinata. 1126 00:47:43,828 --> 00:47:44,536 STUDENTE: Amazing. 1127 00:47:44,536 --> 00:47:48,094 1128 00:47:48,094 --> 00:47:49,010 ISTRUTTORE: Mi dispiace? 1129 00:47:49,010 --> 00:47:52,110 STUDENTE: Perché in precedenza abbiamo usato 1 scritto sopra scritto a zero 1130 00:47:52,110 --> 00:47:54,170 presentare che se che funzionerà o meno. 1131 00:47:54,170 --> 00:47:54,878 >> ISTRUTTORE: Sì. 1132 00:47:54,878 --> 00:47:56,410 Così si può tornare a zero o 1. 1133 00:47:56,410 --> 00:47:58,950 In questo caso, perché non siamo in realtà di fare qualsiasi cosa con la funzione, 1134 00:47:58,950 --> 00:48:00,150 vogliamo solo la rottura. 1135 00:48:00,150 --> 00:48:02,680 Noi in realtà non importa a questo proposito. 1136 00:48:02,680 --> 00:48:06,960 Freno è anche un bene se è utilizzato per scoppiare 1137 00:48:06,960 --> 00:48:10,710 di quattro loop o condizioni che non si desidera mantenere in esecuzione. 1138 00:48:10,710 --> 00:48:12,110 Ci vogliono appena fuori di essi. 1139 00:48:12,110 --> 00:48:13,587 1140 00:48:13,587 --> 00:48:14,795 E 'un po' di una cosa sfumatura. 1141 00:48:14,795 --> 00:48:16,737 1142 00:48:16,737 --> 00:48:18,445 Mi sento come se ci fosse un sacco di mano d'ondeggiamento, 1143 00:48:18,445 --> 00:48:19,740 come imparerete a conoscere questo presto. 1144 00:48:19,740 --> 00:48:20,955 >> Ma imparerete a conoscere questo presto. 1145 00:48:20,955 --> 00:48:21,500 Prometto. 1146 00:48:21,500 --> 00:48:22,670 1147 00:48:22,670 --> 00:48:23,170 Ok. 1148 00:48:23,170 --> 00:48:24,840 Quindi non tutti ottenere bubble sort? 1149 00:48:24,840 --> 00:48:25,550 Non troppo male. 1150 00:48:25,550 --> 00:48:31,910 Scorrere, le cose di swap usando un variabile TEMP, e stiamo tutti insieme lì? 1151 00:48:31,910 --> 00:48:32,960 Freddo. 1152 00:48:32,960 --> 00:48:34,080 Impressionante. 1153 00:48:34,080 --> 00:48:34,807 Ok. 1154 00:48:34,807 --> 00:48:35,765 Torna all'inizio PowerPoint. 1155 00:48:35,765 --> 00:48:38,140 1156 00:48:38,140 --> 00:48:40,130 Tutte le domande in generale su queste fino ad ora? 1157 00:48:40,130 --> 00:48:41,200 1158 00:48:41,200 --> 00:48:41,700 Freddo. 1159 00:48:41,700 --> 00:48:43,110 1160 00:48:43,110 --> 00:48:43,695 Mm-hm. 1161 00:48:43,695 --> 00:48:45,279 >> STUDENTE: [incomprensibile] int main solito. 1162 00:48:45,279 --> 00:48:46,695 Non si deve avere che per questo? 1163 00:48:46,695 --> 00:48:48,400 1164 00:48:48,400 --> 00:48:53,550 >> ISTRUTTORE: Così ci eravamo solo in cerca proprio sull'algoritmo ordinamento. 1165 00:48:53,550 --> 00:48:54,559 1166 00:48:54,559 --> 00:48:56,350 Se tu avessi entro come un programma più ampio, 1167 00:48:56,350 --> 00:48:57,891 si avrebbe un qualche luogo principale int. 1168 00:48:57,891 --> 00:49:00,070 1169 00:49:00,070 --> 00:49:02,880 A seconda di dove si utilizzare questo algoritmo, 1170 00:49:02,880 --> 00:49:05,860 sarebbe determinare ciò che è essere restituito da esso. 1171 00:49:05,860 --> 00:49:09,960 Ma per il nostro caso, noi siamo strettamente guardando come fa questo in realtà 1172 00:49:09,960 --> 00:49:11,300 scorrere un array. 1173 00:49:11,300 --> 00:49:12,570 Quindi non ti preoccupare. 1174 00:49:12,570 --> 00:49:14,150 1175 00:49:14,150 --> 00:49:19,830 >> Così stavamo parlando migliore dei casi e scenari peggiori per la ricerca binaria. 1176 00:49:19,830 --> 00:49:22,470 Quindi è anche importante fare che per ciascuno dei nostri sorta. 1177 00:49:22,470 --> 00:49:24,200 1178 00:49:24,200 --> 00:49:27,560 Allora, cosa pensi sia il peggiore caso di esecuzione di bubble sort? 1179 00:49:27,560 --> 00:49:29,560 1180 00:49:29,560 --> 00:49:30,700 Voi ragazzi ricordate? 1181 00:49:30,700 --> 00:49:31,784 >> STUDENTE: N meno 1. 1182 00:49:31,784 --> 00:49:32,700 ISTRUTTORE: N meno 1. 1183 00:49:32,700 --> 00:49:35,070 In modo che significa che ci sono n meno 1 confronti. 1184 00:49:35,070 --> 00:49:40,060 Quindi, una cosa da capire è che alla prima iterazione, 1185 00:49:40,060 --> 00:49:43,360 attraversiamo, mettiamo a confronto questi two-- così che è 1. 1186 00:49:43,360 --> 00:49:46,685 Questi due, tre, quattro. 1187 00:49:46,685 --> 00:49:48,070 1188 00:49:48,070 --> 00:49:55,050 Così, dopo una iterazione che già quattro i confronti. 1189 00:49:55,050 --> 00:49:58,230 Quando sto parlando di runtime e n. 1190 00:49:58,230 --> 00:50:04,680 N rappresenta il numero di confronti in funzione di quanti elementi 1191 00:50:04,680 --> 00:50:05,570 abbiamo. 1192 00:50:05,570 --> 00:50:06,430 Ok? 1193 00:50:06,430 --> 00:50:08,860 >> Quindi attraversiamo, abbiamo quattro. 1194 00:50:08,860 --> 00:50:11,780 La prossima volta che sai che non lo facciamo devono prendersi cura di questo. 1195 00:50:11,780 --> 00:50:15,140 Confrontiamo questi due, questi due, questi due, 1196 00:50:15,140 --> 00:50:20,050 e se non abbiamo avuto che l'ottimizzazione con i quattro loop che ho scritto, 1197 00:50:20,050 --> 00:50:22,750 si sarebbe confrontando qui comunque. 1198 00:50:22,750 --> 00:50:26,170 Quindi, si dovrebbe correre attraverso la matrice 1199 00:50:26,170 --> 00:50:34,380 e fare paragoni n n volte, perché ogni volta che 1200 00:50:34,380 --> 00:50:36,670 correre attraverso di essa noi ordiniamo una cosa. 1201 00:50:36,670 --> 00:50:38,300 1202 00:50:38,300 --> 00:50:41,475 >> E ogni volta si corre attraverso l'array, facciamo paragoni n. 1203 00:50:41,475 --> 00:50:42,920 1204 00:50:42,920 --> 00:50:46,330 Così il nostro tempo di esecuzione di questo è realtà n al quadrato, che 1205 00:50:46,330 --> 00:50:48,400 è molto peggio nel nostro log fine perché 1206 00:50:48,400 --> 00:50:51,965 significa che se avessimo quattro miliardi di elementi, è 1207 00:50:51,965 --> 00:50:55,260 andando a prendere noi quattro miliardi quadrato invece di 32. 1208 00:50:55,260 --> 00:51:01,240 Quindi non il migliore tempo di esecuzione, ma per alcune cose, 1209 00:51:01,240 --> 00:51:04,610 sai, se sei all'interno di una certa gamma di elementi 1210 00:51:04,610 --> 00:51:06,540 bubble sort può andare bene per l'uso. 1211 00:51:06,540 --> 00:51:07,530 >> Ok. 1212 00:51:07,530 --> 00:51:12,290 Così ora che cosa è il miglior runtime caso? 1213 00:51:12,290 --> 00:51:14,357 1214 00:51:14,357 --> 00:51:14,940 STUDENTE: Zero? 1215 00:51:14,940 --> 00:51:16,420 O 1? 1216 00:51:16,420 --> 00:51:18,140 >> ISTRUTTORE: 1 Così sarebbe uno confronto. 1217 00:51:18,140 --> 00:51:19,114 Destra. 1218 00:51:19,114 --> 00:51:20,002 >> STUDENTE: N meno 1? 1219 00:51:20,002 --> 00:51:21,380 1220 00:51:21,380 --> 00:51:22,320 >> ISTRUTTORE: Quindi, sì. 1221 00:51:22,320 --> 00:51:22,990 Quindi n meno 1. 1222 00:51:22,990 --> 00:51:26,510 Ogni volta che avete un concetto come n meno 1, tendiamo a cadere appena fuori 1223 00:51:26,510 --> 00:51:31,680 e abbiamo solo dire n perché avete per confrontare ciascuna di these-- ogni coppia. 1224 00:51:31,680 --> 00:51:36,470 Quindi sarebbe n meno 1, il quale avevamo appena diciamo è di circa n. 1225 00:51:36,470 --> 00:51:39,280 Quando hai a che fare con il tempo di esecuzione, tutto è in armonizza. 1226 00:51:39,280 --> 00:51:43,860 Fintanto che l'esponente è corretto, sei abbastanza bravo. 1227 00:51:43,860 --> 00:51:45,700 >> È così che abbiamo a che fare con esso. 1228 00:51:45,700 --> 00:51:47,410 1229 00:51:47,410 --> 00:51:51,780 In modo che il caso migliore è n, che significa che l'elenco è già ordinato, 1230 00:51:51,780 --> 00:51:54,320 e tutto quello che facciamo è gestito attraverso e verificare che sia risolto. 1231 00:51:54,320 --> 00:51:56,110 1232 00:51:56,110 --> 00:51:56,855 Freddo. 1233 00:51:56,855 --> 00:51:57,355 Bene. 1234 00:51:57,355 --> 00:51:58,980 1235 00:51:58,980 --> 00:52:01,920 Quindi, come vedete qui, noi basta avere più grafici. 1236 00:52:01,920 --> 00:52:02,660 Quindi n al quadrato. 1237 00:52:02,660 --> 00:52:03,780 1238 00:52:03,780 --> 00:52:05,120 Fun. 1239 00:52:05,120 --> 00:52:09,730 Molto peggio di n come si vede, e molto, molto peggio di registro 2n. 1240 00:52:09,730 --> 00:52:12,060 E poi si arriva anche in log logs. 1241 00:52:12,060 --> 00:52:18,020 E si prende 124, si entra in come stella di registro, che è come un matto. 1242 00:52:18,020 --> 00:52:20,172 Quindi, se siete interessati, stella di log di ricerca. 1243 00:52:20,172 --> 00:52:20,880 E 'una specie di divertimento. 1244 00:52:20,880 --> 00:52:22,800 1245 00:52:22,800 --> 00:52:24,220 Così abbiamo questa grande tabella. 1246 00:52:24,220 --> 00:52:25,360 1247 00:52:25,360 --> 00:52:28,720 Solo un testa a testa, questo un meraviglioso grafico di avere 1248 00:52:28,720 --> 00:52:31,350 per il medio termine perché noi a lungo per chiedere a voi queste si assottiglia. 1249 00:52:31,350 --> 00:52:36,090 Quindi, solo un testa a testa, hanno questo sul tuo a medio termine sul foglietto bello 1250 00:52:36,090 --> 00:52:36,616 Là. 1251 00:52:36,616 --> 00:52:37,990 Così abbiamo appena guardato bubble sort. 1252 00:52:37,990 --> 00:52:39,510 1253 00:52:39,510 --> 00:52:42,370 Nel peggiore dei casi, n squadrato, migliore dei casi, n. 1254 00:52:42,370 --> 00:52:43,367 1255 00:52:43,367 --> 00:52:44,950 E stiamo andando a guardare gli altri. 1256 00:52:44,950 --> 00:52:47,940 >> E come si può vedere, l'unico uno che fa davvero bene 1257 00:52:47,940 --> 00:52:50,910 è merge sort, di cui parleremo in perché. 1258 00:52:50,910 --> 00:52:52,690 1259 00:52:52,690 --> 00:52:55,215 Quindi stiamo per andare al prossimo qui-- selection sort. 1260 00:52:55,215 --> 00:52:56,360 1261 00:52:56,360 --> 00:52:58,420 Qualcuno ricorda come selezione lavorato genere? 1262 00:52:58,420 --> 00:53:05,200 1263 00:53:05,200 --> 00:53:05,700 Andare per esso. 1264 00:53:05,700 --> 00:53:08,210 >> STUDENTE: Fondamentalmente passare attraverso un ordine e creare un nuovo elenco. 1265 00:53:08,210 --> 00:53:11,001 E come si sta mettendo elementi in, metterli al posto giusto 1266 00:53:11,001 --> 00:53:11,750 nel nuovo elenco. 1267 00:53:11,750 --> 00:53:14,040 >> ISTRUTTORE: In modo che i suoni più come insertion sort. 1268 00:53:14,040 --> 00:53:15,040 Ma sei davvero vicino. 1269 00:53:15,040 --> 00:53:15,915 Sono molto simili. 1270 00:53:15,915 --> 00:53:17,440 Anche io confonderle volte. 1271 00:53:17,440 --> 00:53:18,981 Prima di questa sezione ho pensato, aspetta. 1272 00:53:18,981 --> 00:53:20,130 1273 00:53:20,130 --> 00:53:20,630 Ok. 1274 00:53:20,630 --> 00:53:24,141 Quindi, ciò che si vuole fare è ordinamento per selezione, 1275 00:53:24,141 --> 00:53:25,890 il modo in cui si può pensare su di esso e il modo 1276 00:53:25,890 --> 00:53:30,140 Mi assicuro che non cercare di ottenere li confondono, è passa attraverso 1277 00:53:30,140 --> 00:53:33,280 e seleziona il minor numero e 1278 00:53:33,280 --> 00:53:36,070 mette che all'inizio della vostra lista. 1279 00:53:36,070 --> 00:53:37,730 Si scambia con quel primo posto. 1280 00:53:37,730 --> 00:53:42,600 1281 00:53:42,600 --> 00:53:45,370 In realtà sono un esempio per me. 1282 00:53:45,370 --> 00:53:46,540 Impressionante. 1283 00:53:46,540 --> 00:53:50,130 Quindi, solo un modo di pensare di selezione it-- Ordina, selezionare il valore più piccolo. 1284 00:53:50,130 --> 00:53:51,940 E stiamo andando a correre attraverso un esempio 1285 00:53:51,940 --> 00:53:55,320 che penso aiuterà perché Penso immagini aiutano sempre. 1286 00:53:55,320 --> 00:53:58,510 Quindi si parte con qualcosa che è completamente indifferenziati. 1287 00:53:58,510 --> 00:54:00,730 Red sarà indifferenziati, verde verrà ordinata. 1288 00:54:00,730 --> 00:54:02,190 Sarà tutto un senso in un secondo. 1289 00:54:02,190 --> 00:54:08,950 >> Quindi attraversiamo e iteriamo dall'inizio alla fine. 1290 00:54:08,950 --> 00:54:12,320 E noi diciamo, OK, 2 è il nostro numero più piccolo. 1291 00:54:12,320 --> 00:54:15,680 Quindi stiamo andando a prendere 2 e stiamo andando per spostarlo verso la parte anteriore della nostra matrice 1292 00:54:15,680 --> 00:54:17,734 perché è il numero più piccolo che abbiamo. 1293 00:54:17,734 --> 00:54:19,150 Ecco, questo è ciò che questo sta facendo qui. 1294 00:54:19,150 --> 00:54:20,820 E 'solo andando a scambiare quei due. 1295 00:54:20,820 --> 00:54:21,850 1296 00:54:21,850 --> 00:54:25,450 Così ora abbiamo un ordinato parte e una parte non ordinato. 1297 00:54:25,450 --> 00:54:27,810 E ciò che è bene ricordare su ordinamento per selezione 1298 00:54:27,810 --> 00:54:30,690 è che stiamo selezionando solo dalla parte non differenziati. 1299 00:54:30,690 --> 00:54:32,220 1300 00:54:32,220 --> 00:54:34,527 >> La parte che avete appena ordinato lasciano in pace. 1301 00:54:34,527 --> 00:54:35,660 Mm-hm? 1302 00:54:35,660 --> 00:54:38,452 >> STUDENTE: Come fa a sapere che cosa è il più piccolo senza confrontarlo 1303 00:54:38,452 --> 00:54:39,868 ad ogni altro valore nella matrice. 1304 00:54:39,868 --> 00:54:41,250 ISTRUTTORE: Lo fa confrontarlo. 1305 00:54:41,250 --> 00:54:42,041 Ci piace saltato. 1306 00:54:42,041 --> 00:54:43,850 Questo è solo generale complessiva. 1307 00:54:43,850 --> 00:54:44,831 Sì. 1308 00:54:44,831 --> 00:54:47,205 Quando si scrive il codice sono sicuro che sarete più soddisfatti. 1309 00:54:47,205 --> 00:54:48,696 1310 00:54:48,696 --> 00:54:53,030 Ma si memorizza questa prima elemento come il più piccolo. 1311 00:54:53,030 --> 00:54:56,110 Si confrontano e si dire, OK, è più piccolo? 1312 00:54:56,110 --> 00:54:56,660 Sì. 1313 00:54:56,660 --> 00:54:57,460 Keep it. 1314 00:54:57,460 --> 00:54:58,640 Qui è più piccolo? 1315 00:54:58,640 --> 00:54:59,660 No? 1316 00:54:59,660 --> 00:55:02,510 >> Questo è il tuo più piccolo, riassegnare al tuo valore. 1317 00:55:02,510 --> 00:55:06,340 E sarai molto più felice quando andiamo attraverso il codice. 1318 00:55:06,340 --> 00:55:07,510 1319 00:55:07,510 --> 00:55:13,970 Quindi attraversiamo, ci scambiamo, così poi guardiamo a questa parte non differenziati. 1320 00:55:13,970 --> 00:55:15,810 Quindi stiamo andando a selezionare tre su. 1321 00:55:15,810 --> 00:55:18,890 Stiamo andando a metterlo su a la fine della nostra porzione ordinato. 1322 00:55:18,890 --> 00:55:20,267 1323 00:55:20,267 --> 00:55:23,100 E stiamo solo andando a continuare a fare che, facendo questo, e farlo. 1324 00:55:23,100 --> 00:55:24,130 1325 00:55:24,130 --> 00:55:27,420 Quindi questo è il nostro tipo di pseudocodice qui. 1326 00:55:27,420 --> 00:55:29,470 1327 00:55:29,470 --> 00:55:31,380 Ci codice che esso qui in un secondo. 1328 00:55:31,380 --> 00:55:34,140 1329 00:55:34,140 --> 00:55:37,270 Ma solo qualcosa a camminare attraverso su un livello alto. 1330 00:55:37,270 --> 00:55:40,275 Hai intenzione di andare da i uguale a 0 per n meno 2. 1331 00:55:40,275 --> 00:55:41,570 1332 00:55:41,570 --> 00:55:43,530 Questo è un altro di ottimizzazione. 1333 00:55:43,530 --> 00:55:45,020 Non preoccupatevi troppo su di esso. 1334 00:55:45,020 --> 00:55:46,620 Quindi, come dicevi tu. 1335 00:55:46,620 --> 00:55:49,660 1336 00:55:49,660 --> 00:55:54,406 Come Jacob stava dicendo, come facciamo tenere traccia di ciò che il nostro minimo è? 1337 00:55:54,406 --> 00:55:55,030 Come facciamo a saperlo? 1338 00:55:55,030 --> 00:55:57,060 Dobbiamo confrontare tutto nella nostra lista. 1339 00:55:57,060 --> 00:55:59,600 >> Così minima equivale i. 1340 00:55:59,600 --> 00:56:03,870 E 'solo che in questo caso l'indice del nostro valore minimo. 1341 00:56:03,870 --> 00:56:07,660 Allora sta andando a scorrere e va da j è pari a i + 1. 1342 00:56:07,660 --> 00:56:11,420 Quindi sappiamo già che questo è il nostro primo elemento. 1343 00:56:11,420 --> 00:56:13,240 Non abbiamo bisogno di confrontarlo con se stesso. 1344 00:56:13,240 --> 00:56:16,970 Così cominciamo a confronto con il prossimo quello che è il motivo per cui è i più 1 per n 1345 00:56:16,970 --> 00:56:20,110 meno 1, che è il fine dell'array lì. 1346 00:56:20,110 --> 00:56:25,090 E abbiamo detto in caso di array a j è minore di matrice min, 1347 00:56:25,090 --> 00:56:29,200 poi riassegnare dove i nostri indici minimi è. 1348 00:56:29,200 --> 00:56:37,470 >> E se min è diverso da i, come in cui siamo tornati qui. 1349 00:56:37,470 --> 00:56:38,950 1350 00:56:38,950 --> 00:56:41,790 Così come quando abbiamo fatto questo. 1351 00:56:41,790 --> 00:56:49,310 In questo caso, sarebbe cominciare zero, finirebbe per essere due. 1352 00:56:49,310 --> 00:56:53,010 Così min non sarebbe uguale i alla fine. 1353 00:56:53,010 --> 00:56:55,720 Che ci fa sapere che abbiamo bisogno di scambiarle. 1354 00:56:55,720 --> 00:56:57,420 1355 00:56:57,420 --> 00:57:00,470 Mi sento come un esempio concreto aiuterà molto più di questo. 1356 00:57:00,470 --> 00:57:04,970 Quindi io questo codice con voi ragazzi in questo momento e penso che sarà meglio. 1357 00:57:04,970 --> 00:57:07,380 1358 00:57:07,380 --> 00:57:11,350 >> Tipo tende a lavorare in questo modo in quanto spesso è meglio solo per vedere loro. 1359 00:57:11,350 --> 00:57:12,780 1360 00:57:12,780 --> 00:57:17,280 Quindi, quello che vogliamo fare è per prima cosa vogliamo che il più piccolo 1361 00:57:17,280 --> 00:57:19,890 elemento nella propria posizione nella matrice. 1362 00:57:19,890 --> 00:57:21,280 Esattamente quello che Jacob stava dicendo. 1363 00:57:21,280 --> 00:57:23,090 Hai bisogno di memorizzare che in qualche modo. 1364 00:57:23,090 --> 00:57:25,900 Quindi stiamo andando a iniziare da qui iterare su l'array. 1365 00:57:25,900 --> 00:57:28,970 Stiamo andando a dire che è il nostro prima solo per cominciare. 1366 00:57:28,970 --> 00:57:38,308 Quindi, stiamo andando ad avere int più piccolo è uguale a matrice a i. 1367 00:57:38,308 --> 00:57:40,500 1368 00:57:40,500 --> 00:57:45,050 >> Quindi una cosa da notare, ogni volta che questo ciclo viene eseguito, 1369 00:57:45,050 --> 00:57:48,550 stiamo iniziando un passo più avanti. 1370 00:57:48,550 --> 00:57:54,780 1371 00:57:54,780 --> 00:57:57,440 Quando cominciamo guardiamo questo. 1372 00:57:57,440 --> 00:58:00,840 La prossima volta che iterare, stiamo iniziando a questo 1373 00:58:00,840 --> 00:58:02,680 e assegnandogli il nostro valore più piccolo. 1374 00:58:02,680 --> 00:58:10,450 Quindi è molto simile a bubble sort dove sappiamo che dopo un passaggio, 1375 00:58:10,450 --> 00:58:11,700 quest'ultimo elemento è ordinato. 1376 00:58:11,700 --> 00:58:12,810 1377 00:58:12,810 --> 00:58:15,120 Con ordinamento per selezione, è esattamente l'opposto. 1378 00:58:15,120 --> 00:58:18,950 >> Ad ogni passo, sappiamo che il primo è ordinato. 1379 00:58:18,950 --> 00:58:21,360 Dopo il secondo passaggio, la secondo verrà ordinata. 1380 00:58:21,360 --> 00:58:26,470 E come avete visto con gli esempi di scorrimento, la nostra porzione ordinati continua a crescere. 1381 00:58:26,470 --> 00:58:34,020 Quindi, impostando il nostro unico piccolo agli array i, tutto quello che sta facendo 1382 00:58:34,020 --> 00:58:37,340 è costrizione cosa stiamo guardando in modo da 1383 00:58:37,340 --> 00:58:40,164 ridurre al minimo il numero di confronti che facciamo. 1384 00:58:40,164 --> 00:58:41,770 Questo fa senso per tutti? 1385 00:58:41,770 --> 00:58:42,920 1386 00:58:42,920 --> 00:58:46,380 Avete bisogno di me per correre attraverso quella ancora più lento o con parole diverse? 1387 00:58:46,380 --> 00:58:47,180 Sono felice di. 1388 00:58:47,180 --> 00:58:48,095 1389 00:58:48,095 --> 00:58:48,595 Ok. 1390 00:58:48,595 --> 00:58:50,060 1391 00:58:50,060 --> 00:58:55,540 >> Quindi stiamo memorizzare il Valore a questo punto, 1392 00:58:55,540 --> 00:58:57,840 ma vogliamo anche memorizzare l'indice. 1393 00:58:57,840 --> 00:59:01,010 Quindi stiamo andando a memorizzare il posizione del più piccolo 1394 00:59:01,010 --> 00:59:02,770 uno, che è solo sarà i. 1395 00:59:02,770 --> 00:59:04,357 1396 00:59:04,357 --> 00:59:05,440 Così ora Jacob è soddisfatto. 1397 00:59:05,440 --> 00:59:06,870 Abbiamo cose memorizzati. 1398 00:59:06,870 --> 00:59:08,240 1399 00:59:08,240 --> 00:59:11,870 E ora abbiamo bisogno di guardare attraverso la parte non ordinata dell'array. 1400 00:59:11,870 --> 00:59:18,170 Quindi in questo caso questa sarebbe la nostra indifferenziati. 1401 00:59:18,170 --> 00:59:20,980 1402 00:59:20,980 --> 00:59:22,462 Questo è i. 1403 00:59:22,462 --> 00:59:25,430 1404 00:59:25,430 --> 00:59:26,210 Ok. 1405 00:59:26,210 --> 00:59:30,040 >> Così che cosa stiamo andando a fare sta per essere per un ciclo. 1406 00:59:30,040 --> 00:59:32,066 Ogni volta che avete bisogno di scorrere un array, 1407 00:59:32,066 --> 00:59:33,440 la tua mente potrebbe andare in per un ciclo. 1408 00:59:33,440 --> 00:59:34,760 1409 00:59:34,760 --> 00:59:38,090 Così, per un po 'int k equals-- cosa pensiamo 1410 00:59:38,090 --> 00:59:39,700 k sta per essere uguale per iniziare? 1411 00:59:39,700 --> 00:59:41,580 1412 00:59:41,580 --> 00:59:44,766 Questo è ciò che abbiamo impostato come il nostro più piccolo valore e vogliamo confrontarlo. 1413 00:59:44,766 --> 00:59:47,090 Quello che vogliamo confrontarlo con? 1414 00:59:47,090 --> 00:59:48,730 E sarà questo prossimo, giusto? 1415 00:59:48,730 --> 00:59:53,200 Quindi vogliamo k da inizializzare per i più 1 per iniziare. 1416 00:59:53,200 --> 00:59:55,350 1417 00:59:55,350 --> 01:00:02,800 >> E vogliamo k in questo caso si già ha formato accumulato qui, 1418 01:00:02,800 --> 01:00:03,930 in modo che possiamo semplicemente usare dimensioni. 1419 01:00:03,930 --> 01:00:06,240 Dimensione è la dimensione della matrice. 1420 01:00:06,240 --> 01:00:09,620 E vogliamo solo aggiornare k di uno ogni volta. 1421 01:00:09,620 --> 01:00:17,410 1422 01:00:17,410 --> 01:00:17,910 Freddo. 1423 01:00:17,910 --> 01:00:19,650 1424 01:00:19,650 --> 01:00:23,430 Così ora abbiamo bisogno di trovare il più piccolo elemento qui. 1425 01:00:23,430 --> 01:00:24,470 1426 01:00:24,470 --> 01:00:31,380 Quindi, se iterare, abbiamo voglio dire, se a matrice k 1427 01:00:31,380 --> 01:00:37,080 è inferiore al nostro piccolo value-- è qui che siamo in realtà 1428 01:00:37,080 --> 01:00:42,950 tenere traccia di ciò che è il più piccolo qui-- 1429 01:00:42,950 --> 01:00:47,740 poi si vuole riassegnare qual è il nostro valore più piccolo è. 1430 01:00:47,740 --> 01:00:50,645 >> Ciò significa che, oh, siamo scorrendo qui. 1431 01:00:50,645 --> 01:00:51,699 1432 01:00:51,699 --> 01:00:53,740 Qualunque sia il valore è qui è non la nostra più piccola cosa. 1433 01:00:53,740 --> 01:00:54,448 Noi non lo vogliamo. 1434 01:00:54,448 --> 01:00:56,100 Vogliamo riassegnare esso. 1435 01:00:56,100 --> 01:01:02,050 Quindi, se siamo riassegnandolo, che cosa fare si pensa possa essere in questo codice qui? 1436 01:01:02,050 --> 01:01:04,160 Vogliamo riassegnare più piccolo e la posizione. 1437 01:01:04,160 --> 01:01:05,740 1438 01:01:05,740 --> 01:01:07,010 Così che cosa è più piccolo ora? 1439 01:01:07,010 --> 01:01:08,422 1440 01:01:08,422 --> 01:01:09,130 STUDENTE: Array k. 1441 01:01:09,130 --> 01:01:09,963 ISTRUTTORE: Array k. 1442 01:01:09,963 --> 01:01:13,480 1443 01:01:13,480 --> 01:01:15,956 E qual è la posizione in questo momento? 1444 01:01:15,956 --> 01:01:20,940 1445 01:01:20,940 --> 01:01:23,000 Cosa c'è di indici di il nostro valore più piccolo? 1446 01:01:23,000 --> 01:01:24,030 1447 01:01:24,030 --> 01:01:24,530 E 'solo k. 1448 01:01:24,530 --> 01:01:25,690 1449 01:01:25,690 --> 01:01:27,790 Così matrice k, k, si corrispondono. 1450 01:01:27,790 --> 01:01:31,670 1451 01:01:31,670 --> 01:01:33,120 Così abbiamo deciso di riassegnare tale. 1452 01:01:33,120 --> 01:01:34,390 1453 01:01:34,390 --> 01:01:39,950 E poi dopo abbiamo trovato il nostro piccolo, così alla fine di questo ciclo for 1454 01:01:39,950 --> 01:01:45,100 qui abbiamo trovato ciò che il nostro più piccolo valore è, quindi abbiamo appena scambiare esso. 1455 01:01:45,100 --> 01:01:47,100 1456 01:01:47,100 --> 01:01:50,816 In questo caso, come dire che la nostra valore più piccolo è qui. 1457 01:01:50,816 --> 01:01:51,940 Questo è il nostro valore più piccolo. 1458 01:01:51,940 --> 01:01:57,690 >> Vogliamo solo scambiarlo qui, che è cosa che funzione swap sul fondo 1459 01:01:57,690 --> 01:02:01,270 fatto, che abbiamo appena scritto su insieme un paio di minuti fa. 1460 01:02:01,270 --> 01:02:02,775 Così dovrebbe essere familiare. 1461 01:02:02,775 --> 01:02:04,320 1462 01:02:04,320 --> 01:02:08,030 E allora sarà solo scorrere attraverso fino a raggiungere fino 1463 01:02:08,030 --> 01:02:13,100 alla fine, il che significa che si avere zero elementi che sono indifferenziati 1464 01:02:13,100 --> 01:02:14,800 e tutto il resto è stato risolto. 1465 01:02:14,800 --> 01:02:16,216 1466 01:02:16,216 --> 01:02:16,715 Dare un senso? 1467 01:02:16,715 --> 01:02:18,010 1468 01:02:18,010 --> 01:02:19,280 Un po 'più concretamente? 1469 01:02:19,280 --> 01:02:19,990 La guida in codice? 1470 01:02:19,990 --> 01:02:21,720 1471 01:02:21,720 --> 01:02:26,410 >> STUDENTE: Per una dimensione, non hai mai davvero definirlo o modificarlo, 1472 01:02:26,410 --> 01:02:27,340 come fa a sapere? 1473 01:02:27,340 --> 01:02:32,380 >> ISTRUTTORE: Quindi una cosa da notare qui è la dimensione int. 1474 01:02:32,380 --> 01:02:35,680 Quindi stiamo dicendo in questo tipo sort-- è una funzione in questo case-- è 1475 01:02:35,680 --> 01:02:40,770 ordinamento per selezione, è passato con la funzione. 1476 01:02:40,770 --> 01:02:43,460 Quindi, se non è stato passato in, si dovrebbe fare qualcosa 1477 01:02:43,460 --> 01:02:47,840 come con la lunghezza della matrice o si dovrebbe scorrere 1478 01:02:47,840 --> 01:02:49,390 per trovare la lunghezza. 1479 01:02:49,390 --> 01:02:52,680 Ma perché è passato in, possiamo semplicemente usare. 1480 01:02:52,680 --> 01:02:55,720 Basta dare per scontato che l'utente ti ha dato una dimensione valida che 1481 01:02:55,720 --> 01:02:57,698 in realtà rappresenta una dimensione dell'array. 1482 01:02:57,698 --> 01:02:59,461 1483 01:02:59,461 --> 01:02:59,960 Cool? 1484 01:02:59,960 --> 01:03:01,610 1485 01:03:01,610 --> 01:03:05,870 >> Se voi ragazzi avete problemi con questi o vuole più pratica di codifica tipo 1486 01:03:05,870 --> 01:03:08,050 da soli, si dovrebbe andare a study.cs50. 1487 01:03:08,050 --> 01:03:11,560 1488 01:03:11,560 --> 01:03:12,670 Si tratta di uno strumento. 1489 01:03:12,670 --> 01:03:15,040 Hanno un controllo che si può effettivamente scrivere. 1490 01:03:15,040 --> 01:03:16,180 Fanno pseudocodice. 1491 01:03:16,180 --> 01:03:19,310 Hanno altri video e diapositive compresi quelli che uso qui. 1492 01:03:19,310 --> 01:03:23,150 Quindi, se siete ancora sentire un po 'confuso, provare che fuori. 1493 01:03:23,150 --> 01:03:25,670 Come sempre, venire a parlare con me, anche. 1494 01:03:25,670 --> 01:03:26,320 Domanda? 1495 01:03:26,320 --> 01:03:28,611 >> Studente: Stai dicendo che il dimensione viene definita in precedenza? 1496 01:03:28,611 --> 01:03:29,234 1497 01:03:29,234 --> 01:03:29,900 ISTRUTTORE: Sì. 1498 01:03:29,900 --> 01:03:35,570 Il formato è definito in precedenza su qui nella dichiarazione di funzione. 1499 01:03:35,570 --> 01:03:39,060 Quindi si assume che è stato approvato nel dall'utente, e per semplicità, 1500 01:03:39,060 --> 01:03:41,896 stiamo andando a supporre che la utente ci ha dato la dimensione corretta. 1501 01:03:41,896 --> 01:03:43,240 Freddo. 1502 01:03:43,240 --> 01:03:44,390 Ecco, questo è l'ordinamento per selezione. 1503 01:03:44,390 --> 01:03:45,590 1504 01:03:45,590 --> 01:03:47,640 Ragazzi, so che stiamo imparando molto oggi. 1505 01:03:47,640 --> 01:03:49,710 E 'un dato denso per la sezione. 1506 01:03:49,710 --> 01:03:51,880 1507 01:03:51,880 --> 01:03:57,340 Quindi, con questo, stiamo andando per andare a insertion sort. 1508 01:03:57,340 --> 01:04:01,550 1509 01:04:01,550 --> 01:04:02,510 >> Ok. 1510 01:04:02,510 --> 01:04:06,100 Quindi, prima che dobbiamo fare la nostra analisi runtime qui. 1511 01:04:06,100 --> 01:04:10,190 Quindi, nel migliore dei casi, concesso da quando ti ho mostrato 1512 01:04:10,190 --> 01:04:11,960 il tavolo ho già tipo di dato via. 1513 01:04:11,960 --> 01:04:15,430 Ma meglio runtime caso, cosa pensiamo? 1514 01:04:15,430 --> 01:04:17,310 1515 01:04:17,310 --> 01:04:18,130 Tutto risolto. 1516 01:04:18,130 --> 01:04:21,040 1517 01:04:21,040 --> 01:04:22,070 N al quadrato. 1518 01:04:22,070 --> 01:04:24,780 Qualcuno ha una spiegazione per il motivo per cui si pensa? 1519 01:04:24,780 --> 01:04:29,060 1520 01:04:29,060 --> 01:04:30,519 >> STUDENTE: si sta confrontando through-- 1521 01:04:30,519 --> 01:04:31,268 ISTRUTTORE: Giusto. 1522 01:04:31,268 --> 01:04:32,540 Si sta confrontando con. 1523 01:04:32,540 --> 01:04:35,630 Ad ogni iterazione, pur siamo decrementare questo per uno, 1524 01:04:35,630 --> 01:04:38,950 siete ancora alla ricerca attraverso tutto per trovare il più piccolo. 1525 01:04:38,950 --> 01:04:42,390 Quindi, anche se il valore più piccolo è qui all'inizio, 1526 01:04:42,390 --> 01:04:44,710 si sta ancora confrontandolo contro tutto il resto 1527 01:04:44,710 --> 01:04:46,550 per assicurarsi che sia la più piccola cosa. 1528 01:04:46,550 --> 01:04:49,820 Così si finirà che attraversa circa n volte quadrato. 1529 01:04:49,820 --> 01:04:51,090 1530 01:04:51,090 --> 01:04:51,590 Bene. 1531 01:04:51,590 --> 01:04:52,785 E qual è il caso peggiore? 1532 01:04:52,785 --> 01:04:54,350 1533 01:04:54,350 --> 01:04:57,980 Anche n al quadrato perché si sta andando di fare la stessa procedura. 1534 01:04:57,980 --> 01:05:01,670 Quindi, in questo caso, la selezione ha qualcosa tipo 1535 01:05:01,670 --> 01:05:04,010 che anche noi chiamiamo tempo di esecuzione previsto. 1536 01:05:04,010 --> 01:05:07,400 Quindi, in altri, sappiamo solo i limiti superiore e inferiore. 1537 01:05:07,400 --> 01:05:11,180 A seconda di come il nostro pazzo lista è o come misti sia, 1538 01:05:11,180 --> 01:05:15,350 variano tra n oppure n squadrato. 1539 01:05:15,350 --> 01:05:16,550 Non lo sappiamo. 1540 01:05:16,550 --> 01:05:22,820 >> Ma perché ordinamento per selezione ha lo stesso peggiore e migliore dei casi, che ci dice che 1541 01:05:22,820 --> 01:05:25,880 non importa quale tipo di input che hanno, che si tratti di tutto 1542 01:05:25,880 --> 01:05:29,130 ordinati o completamente invertire ordinato, è 1543 01:05:29,130 --> 01:05:30,740 andando a prendere la stessa quantità di tempo. 1544 01:05:30,740 --> 01:05:33,760 Quindi, in questo caso, se si ricordare dal nostro tavolo, 1545 01:05:33,760 --> 01:05:38,610 in realtà aveva un valore che questi due tipi non hanno, 1546 01:05:38,610 --> 01:05:40,390 che è tempo di esecuzione previsto. 1547 01:05:40,390 --> 01:05:43,350 Così sappiamo che ogni volta che corriamo ordinamento per selezione, 1548 01:05:43,350 --> 01:05:45,380 è garantito per eseguire un tempo n al quadrato. 1549 01:05:45,380 --> 01:05:46,630 Non c'è variabilità lì. 1550 01:05:46,630 --> 01:05:47,630 E 'solo previsto. 1551 01:05:47,630 --> 01:05:48,820 1552 01:05:48,820 --> 01:05:52,140 E, ancora una volta, se si vuole imparare più, prendere CS 124 in primavera. 1553 01:05:52,140 --> 01:05:55,370 1554 01:05:55,370 --> 01:05:56,712 Bene. 1555 01:05:56,712 --> 01:05:57,545 Abbiamo visto questo. 1556 01:05:57,545 --> 01:05:58,530 1557 01:05:58,530 --> 01:05:59,030 Freddo. 1558 01:05:59,030 --> 01:06:00,930 Sorta così l'inserimento. 1559 01:06:00,930 --> 01:06:03,330 E sto probabilmente andando a tracciare attraverso questo. 1560 01:06:03,330 --> 01:06:05,440 Non voglio che voi ragazzi codificarlo. 1561 01:06:05,440 --> 01:06:06,580 Cose da fare solo a piedi attraverso di essa. 1562 01:06:06,580 --> 01:06:10,500 Così insertion sort è una specie di simile a selection sort 1563 01:06:10,500 --> 01:06:14,460 in che abbiamo sia un non ordinato e filtrate parte della matrice. 1564 01:06:14,460 --> 01:06:20,260 >> Ma cosa c'è di diverso è che come andiamo attraverso uno per uno, 1565 01:06:20,260 --> 01:06:24,210 dobbiamo solo prendere qualunque sia il numero è il prossimo nella nostra indifferenziati, 1566 01:06:24,210 --> 01:06:28,507 e correttamente risolvere la nel nostro array ordinato. 1567 01:06:28,507 --> 01:06:30,090 Sarà più senso con un esempio. 1568 01:06:30,090 --> 01:06:31,140 1569 01:06:31,140 --> 01:06:35,430 Quindi, tutto ciò che inizia come indifferenziati, Proprio come con selection sort. 1570 01:06:35,430 --> 01:06:38,740 E abbiamo intenzione di risolvere la questione in ordine crescente come siamo stati. 1571 01:06:38,740 --> 01:06:40,360 1572 01:06:40,360 --> 01:06:43,340 Così il nostro primo passaggio prendiamo il primo valore 1573 01:06:43,340 --> 01:06:46,700 e si dice, OK, tu sei ora in un elenco da solo. 1574 01:06:46,700 --> 01:06:49,150 >> Perché ci si trova in un elenco da soli, si sono allineati. 1575 01:06:49,150 --> 01:06:52,460 Complimenti per essere il primo elemento di questa matrice. 1576 01:06:52,460 --> 01:06:54,800 Sei già ordinato tutto da solo. 1577 01:06:54,800 --> 01:06:58,900 Così ora abbiamo un ordinato e un array non ordinato. 1578 01:06:58,900 --> 01:07:01,760 Così ora si prende la prima. 1579 01:07:01,760 --> 01:07:05,600 Cosa succede tra qui e qui è che noi diciamo, 1580 01:07:05,600 --> 01:07:08,890 OK, stiamo andando a guardare il primo valore della nostra serie non ordinata 1581 01:07:08,890 --> 01:07:13,270 e abbiamo intenzione di inserire nel suo posto giusto nel array ordinato. 1582 01:07:13,270 --> 01:07:21,460 >> Quindi, quello che facciamo è prendiamo 5 e si dice, OK, 5 è maggiore di 3, 1583 01:07:21,460 --> 01:07:24,630 così abbiamo appena inseriamo giusto a destra di quello. 1584 01:07:24,630 --> 01:07:25,130 Siamo a posto. 1585 01:07:25,130 --> 01:07:26,200 1586 01:07:26,200 --> 01:07:28,420 Allora andiamo al nostro prossimo. 1587 01:07:28,420 --> 01:07:29,720 E prendiamo 2. 1588 01:07:29,720 --> 01:07:34,330 Diciamo, OK, 2 è meno di 3, quindi sappiamo che 1589 01:07:34,330 --> 01:07:36,220 deve essere al di fronte alla nostra lista ora. 1590 01:07:36,220 --> 01:07:41,800 Quindi, quello che facciamo è spingiamo 3 e 5 verso il basso e ci muoviamo 2 in quel primo slot. 1591 01:07:41,800 --> 01:07:42,990 1592 01:07:42,990 --> 01:07:45,870 Quindi stiamo solo inserendolo in il posto giusto dovrebbe essere. 1593 01:07:45,870 --> 01:07:46,960 1594 01:07:46,960 --> 01:07:49,470 >> Poi guardiamo al nostro prossimo, e diciamo 6. 1595 01:07:49,470 --> 01:07:53,620 OK, 6 è maggiore di tutto quanto in nostro array ordinato, 1596 01:07:53,620 --> 01:07:56,000 quindi abbiamo il tag fino alla fine. 1597 01:07:56,000 --> 01:07:56,960 E poi guardiamo 4. 1598 01:07:56,960 --> 01:07:58,130 1599 01:07:58,130 --> 01:08:03,020 4 è inferiore a 6, è meno al 5 ma è superiore a 3. 1600 01:08:03,020 --> 01:08:06,270 Così abbiamo appena inseriamo a destra in mezzo tra 3 e 5. 1601 01:08:06,270 --> 01:08:07,380 1602 01:08:07,380 --> 01:08:10,530 Quindi, per fare che un po ' po 'più concreto, 1603 01:08:10,530 --> 01:08:12,280 qui è una specie di idea di quello che è successo. 1604 01:08:12,280 --> 01:08:16,430 Quindi, per ogni elemento indifferenziato, abbiamo determinare dove nella porzione ordinata 1605 01:08:16,430 --> 01:08:17,090 esso è. 1606 01:08:17,090 --> 01:08:20,680 >> Quindi, tenendo conto della ordinato e non ordinato, 1607 01:08:20,680 --> 01:08:26,080 dobbiamo attraversare attraverso e figura dove si inserisce nel vettore ordinato. 1608 01:08:26,080 --> 01:08:31,460 E lo inseriamo spostando il elementi a destra giù. 1609 01:08:31,460 --> 01:08:34,910 E poi dobbiamo solo continuare scorrendo fino a quando non 1610 01:08:34,910 --> 01:08:39,270 avere una lista del tutto ordinato dove indifferenziati è ora pari a zero 1611 01:08:39,270 --> 01:08:41,720 e ordinato riprende il totalità della nostra lista. 1612 01:08:41,720 --> 01:08:43,146 1613 01:08:43,146 --> 01:08:45,854 Quindi, ancora una volta, per rendere le cose ancora più concreto, abbiamo pseudocodice. 1614 01:08:45,854 --> 01:08:47,979 1615 01:08:47,979 --> 01:08:52,410 >> Quindi, in pratica per i è uguale a 0 a n meno 1, 1616 01:08:52,410 --> 01:08:54,790 questo è solo la lunghezza del nostro array. 1617 01:08:54,790 --> 01:09:00,979 Abbiamo qualche elemento che è uguale a il primo array oi primi indici. 1618 01:09:00,979 --> 01:09:03,200 Abbiamo impostato j uguale a quello. 1619 01:09:03,200 --> 01:09:04,649 1620 01:09:04,649 --> 01:09:09,210 Così, mentre j è maggiore zero e la matrice, j meno 1 1621 01:09:09,210 --> 01:09:11,660 è maggiore del elemento, così tutto quello che sta facendo 1622 01:09:11,660 --> 01:09:17,479 è fare in modo che la tua j rappresenta davvero 1623 01:09:17,479 --> 01:09:20,010 la porzione indifferenziati dell'array. 1624 01:09:20,010 --> 01:09:30,745 >> Così, mentre ci sono ancora cose per ordinare e uno j meno è-- cosa 1625 01:09:30,745 --> 01:09:31,840 è l'elemento lei? 1626 01:09:31,840 --> 01:09:34,760 J non è mai stato definito qui. 1627 01:09:34,760 --> 01:09:35,677 È un po 'fastidioso. 1628 01:09:35,677 --> 01:09:36,176 Ok. 1629 01:09:36,176 --> 01:09:36,689 In ogni modo. 1630 01:09:36,689 --> 01:09:39,899 Così j meno 1, si sta controllando l'elemento prima. 1631 01:09:39,899 --> 01:09:46,460 Stai dicendo che, OK, è l'elemento prima che ovunque io am-- cerchiamo di 1632 01:09:46,460 --> 01:09:47,540 in realtà disegnare questo fuori. 1633 01:09:47,540 --> 01:09:52,580 1634 01:09:52,580 --> 01:09:56,830 Quindi diciamo che questo è come il nostro secondo passaggio. 1635 01:09:56,830 --> 01:09:59,525 Così ho sta per essere uguale a 1, che è qui. 1636 01:09:59,525 --> 01:10:03,310 1637 01:10:03,310 --> 01:10:06,025 >> Così ho sta per essere uguale a 1. 1638 01:10:06,025 --> 01:10:09,510 1639 01:10:09,510 --> 01:10:13,702 Questo sarebbe 2, 4, 5, 6, 7. 1640 01:10:13,702 --> 01:10:16,060 1641 01:10:16,060 --> 01:10:16,750 Bene. 1642 01:10:16,750 --> 01:10:20,945 Così il nostro elemento in questo caso sta per essere uguale a 4. 1643 01:10:20,945 --> 01:10:22,110 1644 01:10:22,110 --> 01:10:24,946 E abbiamo un po 'di j che è sta per essere uguale a 1. 1645 01:10:24,946 --> 01:10:29,770 1646 01:10:29,770 --> 01:10:30,971 Oh, j è decremento. 1647 01:10:30,971 --> 01:10:31,720 Questo è quello che è. 1648 01:10:31,720 --> 01:10:35,680 Così j è pari a i, quindi di cosa si tratta detto è che man mano che andiamo avanti, 1649 01:10:35,680 --> 01:10:37,530 stiamo solo facendo in modo che non siamo su 1650 01:10:37,530 --> 01:10:43,520 indicizzazione questo modo quando stiamo cercando per inserire le cose nella nostra lista ordinata. 1651 01:10:43,520 --> 01:10:49,850 >> Così, quando j è uguale a 1 nel caso di specie e matrice j meno tra-- così serie j meno 1 1652 01:10:49,850 --> 01:10:54,610 è 2 in questo case-- se questo è superiore dell'elemento, 1653 01:10:54,610 --> 01:10:57,700 allora tutto questo sta facendo si sta spostando le cose. 1654 01:10:57,700 --> 01:11:04,790 Quindi in questo caso, matrice j meno uno sarebbe matrice zero, che è 2. 1655 01:11:04,790 --> 01:11:08,430 2 non è superiore a 4, quindi questo non viene eseguito. 1656 01:11:08,430 --> 01:11:11,460 Quindi lo spostamento non si muove verso il basso. 1657 01:11:11,460 --> 01:11:18,790 Quello che fa qui è solo spostando il vettore ordinato verso il basso. 1658 01:11:18,790 --> 01:11:22,340 1659 01:11:22,340 --> 01:11:26,400 In questo caso, infatti, ci potrebbe fare-- facciamo questo 3. 1660 01:11:26,400 --> 01:11:28,080 1661 01:11:28,080 --> 01:11:31,970 Quindi, se vogliamo camminare con questo esempio, siamo ora qui. 1662 01:11:31,970 --> 01:11:32,740 Questo è ordinato. 1663 01:11:32,740 --> 01:11:34,492 1664 01:11:34,492 --> 01:11:35,200 Questo è indifferenziati. 1665 01:11:35,200 --> 01:11:39,090 1666 01:11:39,090 --> 01:11:39,860 Cool? 1667 01:11:39,860 --> 01:11:46,620 Così i è uguale a 2, in modo nostro elemento è uguale a 3. 1668 01:11:46,620 --> 01:11:47,920 1669 01:11:47,920 --> 01:11:52,270 E la nostra j è uguale a 2. 1670 01:11:52,270 --> 01:12:00,620 Quindi guardiamo attraverso e noi dire, OK, è un array j meno 1671 01:12:00,620 --> 01:12:03,470 superiore dell'elemento che stiamo guardando? 1672 01:12:03,470 --> 01:12:05,540 E la risposta è sì, giusto? 1673 01:12:05,540 --> 01:12:11,275 4 è maggiore di 3 e j è 2, quindi questo codice viene eseguito. 1674 01:12:11,275 --> 01:12:12,510 1675 01:12:12,510 --> 01:12:18,550 >> Così ora che cosa facciamo un array a 2, così proprio qui, li scambiano. 1676 01:12:18,550 --> 01:12:25,620 Quindi ci limitiamo a dire, OK, matrice a 2 è ora sta per essere 3. 1677 01:12:25,620 --> 01:12:28,130 1678 01:12:28,130 --> 01:12:32,340 E j sta per eguagliare j meno 1, che è 1. 1679 01:12:32,340 --> 01:12:34,590 1680 01:12:34,590 --> 01:12:37,200 Questo è orribile, ma voi ragazzi l'idea. 1681 01:12:37,200 --> 01:12:38,360 J è ora uguale a 1. 1682 01:12:38,360 --> 01:12:44,360 E la matrice j è solo andare a essere pari al nostro elemento, che era 4. 1683 01:12:44,360 --> 01:12:45,950 1684 01:12:45,950 --> 01:12:48,570 Ho cancellato qualcosa che non dovrebbe avere o miswrote qualcosa, 1685 01:12:48,570 --> 01:12:49,910 ma voi ragazzi ottiene l'idea. 1686 01:12:49,910 --> 01:12:50,640 >> Si muovono al n. 1687 01:12:50,640 --> 01:12:51,920 1688 01:12:51,920 --> 01:12:57,960 E poi se questo fosse, sarebbe cappio di nuovo e sarebbe dire, OK, j è 1 ora. 1689 01:12:57,960 --> 01:13:00,665 E la matrice j meno 1 ora 2. 1690 01:13:00,665 --> 01:13:01,750 1691 01:13:01,750 --> 01:13:03,760 2 è inferiore al nostro elemento? 1692 01:13:03,760 --> 01:13:04,540 No? 1693 01:13:04,540 --> 01:13:07,970 Questo significa che abbiamo inserito questo elemento 1694 01:13:07,970 --> 01:13:10,110 nel punto corretto nel nostro array ordinato. 1695 01:13:10,110 --> 01:13:14,400 Poi possiamo prendere questo e dire, OK, il nostro array ordinato è qui. 1696 01:13:14,400 --> 01:13:19,940 E ci sarebbe voluto il numero 6 ed essere come, OK, è 6 meno di questo numero? 1697 01:13:19,940 --> 01:13:20,480 No? 1698 01:13:20,480 --> 01:13:21,080 Freddo. 1699 01:13:21,080 --> 01:13:22,680 Stiamo bene. 1700 01:13:22,680 --> 01:13:23,530 >> Fallo di nuovo. 1701 01:13:23,530 --> 01:13:24,740 Diciamo 7. 1702 01:13:24,740 --> 01:13:29,010 È 7 inferiore alla fine del nostro array ordinato? 1703 01:13:29,010 --> 01:13:29,520 No. 1704 01:13:29,520 --> 01:13:30,430 Quindi stiamo bene. 1705 01:13:30,430 --> 01:13:32,760 Quindi questo sarebbe stato risolto. 1706 01:13:32,760 --> 01:13:38,610 In pratica tutto questo fa si sta dicendo prendere 1707 01:13:38,610 --> 01:13:42,060 il primo elemento di l'array non ordinato, 1708 01:13:42,060 --> 01:13:46,010 capire dove va nel tuo array ordinato. 1709 01:13:46,010 --> 01:13:48,780 E questo vuole solo cura di swap per farlo. 1710 01:13:48,780 --> 01:13:51,300 Stai fondamentalmente solo scambiando fino a quando è nel posto giusto. 1711 01:13:51,300 --> 01:13:53,600 1712 01:13:53,600 --> 01:13:56,990 L'immagine visiva è che sei spostando tutto dal farlo. 1713 01:13:56,990 --> 01:13:59,420 >> Quindi è come la metà bubble sort-esque. 1714 01:13:59,420 --> 01:14:02,280 1715 01:14:02,280 --> 01:14:03,420 Scopri studio 50. 1716 01:14:03,420 --> 01:14:06,000 Consiglio vivamente di provare per codificare da soli. 1717 01:14:06,000 --> 01:14:07,220 1718 01:14:07,220 --> 01:14:12,450 Se avete problemi o se si vuole vedi codice di esempio per un insertion sort, 1719 01:14:12,450 --> 01:14:13,750 Per favore mi faccia sapere. 1720 01:14:13,750 --> 01:14:14,500 Io sono sempre in giro. 1721 01:14:14,500 --> 01:14:16,600 1722 01:14:16,600 --> 01:14:20,200 Così peggiore runtime caso e meglio runtime caso. 1723 01:14:20,200 --> 01:14:30,700 Come ragazzo visto dalla tabella ho già si mostrò, che è sia n al quadrato e n. 1724 01:14:30,700 --> 01:14:35,590 >> Così gentile di andare fuori di ciò che abbiamo parlato in giro con i nostri tipi precedenti, peggiore 1725 01:14:35,590 --> 01:14:38,760 runtime caso è che se è completamente non ordinato, 1726 01:14:38,760 --> 01:14:42,530 dobbiamo confrontare tutti questi n volte. 1727 01:14:42,530 --> 01:14:47,020 Facciamo un sacco di confronti perché se è in ordine inverso, 1728 01:14:47,020 --> 01:14:50,360 stiamo andando a dire, OK, questo è la stessa, questo è buono, 1729 01:14:50,360 --> 01:14:54,650 e questo dovrà essere confrontato contro il primo ad essere spostato indietro. 1730 01:14:54,650 --> 01:14:56,710 E come abbiamo più verso la coda, abbiamo 1731 01:14:56,710 --> 01:14:59,440 per confrontare, confrontare, e confrontare contro tutto. 1732 01:14:59,440 --> 01:15:03,030 >> Così si finisce per essere circa n al quadrato. 1733 01:15:03,030 --> 01:15:09,510 Se è corretto, allora si dice, OK, 2, sei bravo. 1734 01:15:09,510 --> 01:15:11,330 3, il gioco è rispetto a 2. 1735 01:15:11,330 --> 01:15:12,310 Sei bravo. 1736 01:15:12,310 --> 01:15:14,150 4, si confronta solo alla coda. 1737 01:15:14,150 --> 01:15:14,990 Sei bravo. 1738 01:15:14,990 --> 01:15:17,140 6, confrontare fino alla coda, che stai bene. 1739 01:15:17,140 --> 01:15:20,870 Così, per ogni punto se è già ordinati, si sta facendo un confronto. 1740 01:15:20,870 --> 01:15:22,320 Quindi è solo n. 1741 01:15:22,320 --> 01:15:26,840 E perché abbiamo un migliore runtime caso di n e un tempo di esecuzione nel caso peggiore di n 1742 01:15:26,840 --> 01:15:28,680 quadrato, non abbiamo tempo di esecuzione previsto. 1743 01:15:28,680 --> 01:15:31,290 1744 01:15:31,290 --> 01:15:34,020 >> Dipende solo sul il caos della nostra lista lì. 1745 01:15:34,020 --> 01:15:35,860 1746 01:15:35,860 --> 01:15:39,530 E ancora, un'altra grafico e un altro tavolo. 1747 01:15:39,530 --> 01:15:41,170 Quindi, le differenze tra i tipi. 1748 01:15:41,170 --> 01:15:44,180 Sto solo andando a brezza attraverso, ho sentire come abbiamo parlato ampiamente 1749 01:15:44,180 --> 01:15:46,570 sul modo in cui tutti i tipi di variare e collegare tra loro. 1750 01:15:46,570 --> 01:15:50,564 Così merge sort è l'ultimo Io annoiarvi con ragazzi. 1751 01:15:50,564 --> 01:15:52,105 Noi abbiamo un quadro abbastanza colorato. 1752 01:15:52,105 --> 01:15:53,860 1753 01:15:53,860 --> 01:15:56,040 Così merge sort è un algoritmo ricorsivo. 1754 01:15:56,040 --> 01:15:59,910 Quindi, voi ragazzi sapete cosa una funzione ricorsiva è? 1755 01:15:59,910 --> 01:16:01,550 1756 01:16:01,550 --> 01:16:03,320 >> Chiunque vuole dire? 1757 01:16:03,320 --> 01:16:04,739 Vuoi provare? 1758 01:16:04,739 --> 01:16:07,280 Quindi una funzione ricorsiva è solo una funzione che si chiama. 1759 01:16:07,280 --> 01:16:08,570 1760 01:16:08,570 --> 01:16:11,590 Quindi, se voi siete a conoscenza con la sequenza di Fibonacci, 1761 01:16:11,590 --> 01:16:15,670 che è considerato ricorsiva perché si prende i due precedenti 1762 01:16:15,670 --> 01:16:17,530 e aggiungerli insieme per ottenere il vostro prossimo. 1763 01:16:17,530 --> 01:16:21,440 Così ricorsiva, penso sempre di ricorsione come come una spirale 1764 01:16:21,440 --> 01:16:24,430 quindi siete come la spirale verso il basso in esso. 1765 01:16:24,430 --> 01:16:27,150 Ma è solo una funzione che si chiama. 1766 01:16:27,150 --> 01:16:32,660 >> E, in realtà, molto velocemente mi in grado di mostrare cosa che sembra. 1767 01:16:32,660 --> 01:16:34,260 1768 01:16:34,260 --> 01:16:41,840 Così ricorsiva qui, se guardiamo, questo è il modo ricorsivo per riassumere su un array. 1769 01:16:41,840 --> 01:16:45,900 1770 01:16:45,900 --> 01:16:47,880 Quindi tutto ciò che facciamo è abbiamo funzione di somma 1771 01:16:47,880 --> 01:16:52,210 somma che prende una dimensione e una matrice. 1772 01:16:52,210 --> 01:16:55,210 E se ci fate caso, le dimensioni diminuisce di uno ogni volta. 1773 01:16:55,210 --> 01:17:00,365 E tutto ciò che fa è se x è uguale a zero-- quindi se la dimensione della matrice 1774 01:17:00,365 --> 01:17:02,710 è uguale zero-- restituisce zero. 1775 01:17:02,710 --> 01:17:10,440 >> In caso contrario, le somme per questo ultimo elemento della matrice, 1776 01:17:10,440 --> 01:17:14,790 e poi prende una somma di il resto della matrice. 1777 01:17:14,790 --> 01:17:17,555 Quindi è solo la rottura verso il basso in problemi sempre più piccoli. 1778 01:17:17,555 --> 01:17:18,990 1779 01:17:18,990 --> 01:17:21,890 Per farla breve, la ricorsione, funzione che chiama se stessa. 1780 01:17:21,890 --> 01:17:25,740 Se questo è tutto ciò che hai da questo, questo è ciò che una funzione ricorsiva è. 1781 01:17:25,740 --> 01:17:29,870 Se si prende 51, si otterrà molto, molto confortevole con la ricorsione. 1782 01:17:29,870 --> 01:17:31,110 1783 01:17:31,110 --> 01:17:32,370 E 'davvero cool. 1784 01:17:32,370 --> 01:17:34,660 Aveva senso a come 03:00 una notte fuori. 1785 01:17:34,660 --> 01:17:37,900 E mi sono detto, perché non ho mai usare questo? 1786 01:17:37,900 --> 01:17:39,170 1787 01:17:39,170 --> 01:17:42,430 >> Così per merge sort, in fondo che cosa sta andando a fare è che è 1788 01:17:42,430 --> 01:17:45,620 andando a rompere verso il basso e romperlo verso il basso fino a quando è solo elementi singoli. 1789 01:17:45,620 --> 01:17:47,570 I singoli elementi sono facili da ordinare. 1790 01:17:47,570 --> 01:17:48,070 Vediamo che. 1791 01:17:48,070 --> 01:17:50,760 Se si dispone di un elemento, è già considerato ordinato. 1792 01:17:50,760 --> 01:17:53,800 Quindi su un input di n elementi, se n è minore di 2, 1793 01:17:53,800 --> 01:17:58,120 solo tornare perché questo significa è 0 o 1, come abbiamo visto. 1794 01:17:58,120 --> 01:18:00,050 Coloro che sono considerati elementi ordinati. 1795 01:18:00,050 --> 01:18:02,170 >> In caso contrario, rompere a metà. 1796 01:18:02,170 --> 01:18:06,336 Ordina prima metà, ordinare la seconda metà, e poi unirli insieme. 1797 01:18:06,336 --> 01:18:07,460 Perché si chiama merge sort. 1798 01:18:07,460 --> 01:18:08,700 1799 01:18:08,700 --> 01:18:12,155 Così abbiamo qui ci risolveremo questi. 1800 01:18:12,155 --> 01:18:13,410 1801 01:18:13,410 --> 01:18:17,210 Così continuiamo averli fino a quando la dimensione della matrice è 1. 1802 01:18:17,210 --> 01:18:20,790 Così, quando si tratta di 1, abbiamo appena ritorniamo perché questo è un array ordinato, 1803 01:18:20,790 --> 01:18:23,940 e questo è un array ordinato, e questo è un array ordinato, siamo tutti allineati. 1804 01:18:23,940 --> 01:18:25,390 1805 01:18:25,390 --> 01:18:29,420 Allora quello che facciamo è che avviare la fusione insieme. 1806 01:18:29,420 --> 01:18:31,820 >> Quindi, il modo in cui è possibile pensare fusione è 1807 01:18:31,820 --> 01:18:36,240 basta rimuovere il più piccolo numero di ciascuna delle sub array 1808 01:18:36,240 --> 01:18:38,330 e basta aggiungerlo alla matrice emersa. 1809 01:18:38,330 --> 01:18:44,290 Quindi, se si guarda qui, quando abbiamo questi gruppi abbiamo 4, 6, e 1. 1810 01:18:44,290 --> 01:18:47,280 Quando vogliamo unire questi, guardiamo a questi primi due 1811 01:18:47,280 --> 01:18:50,730 e si dice, OK, 1 è più piccolo, va al fronte. 1812 01:18:50,730 --> 01:18:54,330 4 e 6, non c'è niente da confrontare a, solo Taggalo fino alla fine. 1813 01:18:54,330 --> 01:18:58,020 >> Quando si combinano questi due, abbiamo appena prendere il più piccolo di questi due, 1814 01:18:58,020 --> 01:18:59,310 quindi è 1. 1815 01:18:59,310 --> 01:19:01,690 E ora prendiamo il più piccolo di questi due, quindi 2. 1816 01:19:01,690 --> 01:19:03,330 Più piccolo di questi due, 3. 1817 01:19:03,330 --> 01:19:06,260 Più piccolo di questi due, 4, 5, 6. 1818 01:19:06,260 --> 01:19:08,630 Quindi, si sta solo tirando fuori questi. 1819 01:19:08,630 --> 01:19:11,210 E perché hanno stati ordinati in precedenza, 1820 01:19:11,210 --> 01:19:14,300 vi è solo un Confronto ogni tempo. 1821 01:19:14,300 --> 01:19:19,610 Quindi, più codice qui, solo rappresentazione. 1822 01:19:19,610 --> 01:19:24,410 Così si inizia a metà e si ordina di sinistra e destra 1823 01:19:24,410 --> 01:19:26,180 e poi basta unire quelli. 1824 01:19:26,180 --> 01:19:30,080 >> E noi non abbiamo il codice per unire proprio qui. 1825 01:19:30,080 --> 01:19:34,110 Ma, ancora una volta, se si va su studiare 50, sarà lì. 1826 01:19:34,110 --> 01:19:36,860 In caso contrario, venire a parlare con me se siete ancora confusi. 1827 01:19:36,860 --> 01:19:42,340 Quindi cosa interessante qui è che migliore dei casi, caso peggiore, e tempo di esecuzione previsto 1828 01:19:42,340 --> 01:19:46,250 sono tutti in log n, che è molto meglio di quanto abbiamo 1829 01:19:46,250 --> 01:19:48,000 visto per il resto della nostra specie. 1830 01:19:48,000 --> 01:19:51,840 Abbiamo visto n Squared e ciò che in realtà 1831 01:19:51,840 --> 01:19:54,380 arrivare qui è n log n, che è grande. 1832 01:19:54,380 --> 01:19:55,830 >> Guarda quanto migliore che è. 1833 01:19:55,830 --> 01:19:56,780 Tale una bella curva. 1834 01:19:56,780 --> 01:19:58,130 1835 01:19:58,130 --> 01:20:00,120 Tanto più efficiente. 1836 01:20:00,120 --> 01:20:03,510 Se è mai possibile, l'uso merge sort. 1837 01:20:03,510 --> 01:20:04,810 Essa vi consente di risparmiare tempo. 1838 01:20:04,810 --> 01:20:07,670 Poi di nuovo, come abbiamo detto, se sei giù in questa regione più bassa, 1839 01:20:07,670 --> 01:20:09,480 non fa che molta differenza. 1840 01:20:09,480 --> 01:20:11,360 È possibile ottenere fino a migliaia e migliaia di ingressi, 1841 01:20:11,360 --> 01:20:13,318 se lo desiderate un algoritmo più efficiente. 1842 01:20:13,318 --> 01:20:14,730 1843 01:20:14,730 --> 01:20:19,400 E, ancora una volta, il nostro bel tavolo di tutti tipi che voi ragazzi hanno imparato oggi. 1844 01:20:19,400 --> 01:20:21,157 >> Quindi io so che è stata una giornata densa. 1845 01:20:21,157 --> 01:20:23,490 Questo non è necessariamente andare per aiutarvi con il vostro pset. 1846 01:20:23,490 --> 01:20:28,250 Ma io voglio solo fare una dichiarazione di non responsabilità che la sezione non è solo p-set. 1847 01:20:28,250 --> 01:20:31,240 Tutto questo materiale è giusto gioco per i vostri elezioni di medio termine. 1848 01:20:31,240 --> 01:20:35,430 E anche se lo fai continuare con CS, questi sono fondamenti veramente importanti 1849 01:20:35,430 --> 01:20:37,870 che si avrebbe bisogno di sapere. 1850 01:20:37,870 --> 01:20:41,700 Così alcuni giorni saranno un po 'più di aiuto pset, 1851 01:20:41,700 --> 01:20:44,600 ma qualche settimana sarà molto più contenuto effettivo 1852 01:20:44,600 --> 01:20:46,600 che non può sembrare eccellente utile a voi in questo momento, 1853 01:20:46,600 --> 01:20:51,215 ma vi prometto se si continua su sarà molto, molto utile. 1854 01:20:51,215 --> 01:20:52,560 1855 01:20:52,560 --> 01:20:54,250 >> In modo che è tutto per sezione. 1856 01:20:54,250 --> 01:20:55,250 Giù per il filo. 1857 01:20:55,250 --> 01:20:56,570 L'ho fatto in un minuto. 1858 01:20:56,570 --> 01:20:58,262 1859 01:20:58,262 --> 01:20:58,970 Ma ci si va. 1860 01:20:58,970 --> 01:21:01,240 E avrò ciambelle o caramelle. 1861 01:21:01,240 --> 01:21:03,464 C'è qualcuno allergico a qualsiasi cosa, a proposito? 1862 01:21:03,464 --> 01:21:05,307 1863 01:21:05,307 --> 01:21:05,890 Uova e latte. 1864 01:21:05,890 --> 01:21:08,120 Così ciambelle sono un no? 1865 01:21:08,120 --> 01:21:09,400 1866 01:21:09,400 --> 01:21:10,160 Ok. 1867 01:21:10,160 --> 01:21:10,770 Bene. 1868 01:21:10,770 --> 01:21:12,120 No al cioccolato? 1869 01:21:12,120 --> 01:21:12,620 Starburst. 1870 01:21:12,620 --> 01:21:13,837 1871 01:21:13,837 --> 01:21:14,670 Starbursts sono buone. 1872 01:21:14,670 --> 01:21:15,170 Ok. 1873 01:21:15,170 --> 01:21:17,045 Stiamo per avere Starburst la prossima settimana poi. 1874 01:21:17,045 --> 01:21:18,240 Questo è quello che vado a prendere. 1875 01:21:18,240 --> 01:21:19,690 Voi ragazzi avete una grande settimana. 1876 01:21:19,690 --> 01:21:20,460 Leggi il tuo spec. 1877 01:21:20,460 --> 01:21:22,130 >> Fatemi sapere se avete domande. 1878 01:21:22,130 --> 01:21:25,300 PSET due gradi dovrebbero essere a voi da Giovedi. 1879 01:21:25,300 --> 01:21:28,320 Se avete domande di come mi Graded qualcosa 1880 01:21:28,320 --> 01:21:32,250 o perché ho classificato qualcosa che il mio modo di ha, prego email me, venire a parlare con me. 1881 01:21:32,250 --> 01:21:34,210 Sono un po 'questo pazzo settimana, ma prometto 1882 01:21:34,210 --> 01:21:36,340 Io ancora risponderemo entro 24 ore. 1883 01:21:36,340 --> 01:21:38,240 In modo da avere una grande settimana, tutti. 1884 01:21:38,240 --> 01:21:40,090 Buona fortuna per il tuo pset. 1885 01:21:40,090 --> 01:21:41,248