[RIPRODUZIONE DI BRANI MUSICALI] IL PROFESSORE: Va bene. Questo è CS50 e questo è la fine della terza settimana. Quindi siamo qui oggi, non in Sanders Teatro, invece di Weidner Biblioteca. All'interno di cui è uno studio conosciuta come Hauser Studio, o diciamo Studio H, o sono noi say-- se ti è piaciuto quello scherzo, in realtà è da compagno di classe, Mark, in linea, che ha suggerito il più via Twitter. Ora, ciò che è cool essere qui in uno studio è che sono circondato da questi verde pareti, uno schermo verde o chromakey, per così dire, il che significa che CS50 di team di produzione, a mia insaputa in questo momento, potrebbe essere messa più mi in qualsiasi parte del mondo, nel bene e nel male. Ora quello che ci aspetta, impostare problema due è nelle vostre mani per questa settimana, ma con il problema set tre la prossima settimana, sarete sfidati con la cosiddetta partita a 15, un vecchio partito favore che si potrebbe ricordare che riceve come un bambino che ha un sacco di numeri che possono scorrere su, giù, a destra ea sinistra, e c'è un divario all'interno del puzzle, in cui si può effettivamente fare scorrere i pezzi del puzzle. In definitiva si riceve questo Puzzle in qualche ordine casuale semi, e l'obiettivo è quello risolverlo, dall'alto in basso, da sinistra a destra, da una tutta la strada fino a 15. Sfortunatamente, l'implementazione avrete a portata di mano sta per essere software basato, non fisicamente. Si sta effettivamente andando ad avere per scrivere codice con il quale uno studente o un utente può giocare il gioco del 15. Ed infatti, nel l'hacker edizione del gioco del 15, sarai una sfida per l'attuazione, Non solo la riproduzione di questa vecchia scuola gioco, ma piuttosto la soluzione di esso, attuare modalità di Dio, per così dire, che in realtà risolve il puzzle per l'umano, fornendo loro suggerimento, dopo suggerimento, dopo suggerimento. Quindi più che la prossima settimana. Ma questo è quello che ci aspetta. Per ora ricordare che all'inizio di questa settimana abbiamo avuto questo colpo di scena, se si vuole, per cui la migliore che stavamo facendo la cernita saggio è stato un limite superiore di grande o di n quadrato. In altre parole, bubble sort, selection sort, insertion sort, tutti loro, mentre differente nella loro attuazione, devoluto in una n quadrato esecuzione tempo nel caso peggiore. E generalmente si assume che il caso peggiore per l'ordinamento è uno che gli ingressi sono completamente all'indietro. E in effetti, ci sono voluti parecchi passi per attuare ciascuna di tali algoritmi. Ora, alla fine della classe richiamo, abbiamo confrontato bubble sort contro la selezione sorta contro un altro che abbiamo chiamato merge sort, al momento, e propongo che sta prendendo vantaggio di una lezione di settimana pari a zero, divide et impera. E in qualche modo raggiungere un qualche tipo di logaritmico tempo di esecuzione in ultima analisi, invece di qualcosa questo è puramente quadratica. E non è del tutto logaritmica, è un po 'più di questo. Ma se vi ricordate dalla classe, era molto più velocemente. Diamo uno sguardo a dove avevamo lasciato. Bubble sort contro selezione specie contro merge sort. Ora sono tutti in esecuzione, in teoria, allo stesso tempo. La CPU gira alla stessa velocità. Ma si può sentire che noia questo sta molto rapidamente sta per diventare, e quanto velocemente, quando iniettiamo un po 'di algoritmi settimana Zero, possiamo accelerare le cose. Così sorta marchio sembra incredibile. Come possiamo sfruttare essa, al fine Per ordinare i numeri più rapidamente. Beh pensiamo indietro a un ingrediente che avevano nel settimana zero, cioè di alla ricerca di qualcuno in una rubrica telefonica, e ricordare che la pseudocodice che abbiamo proposto, attraverso il quale possiamo trovare uno come Mike Smith, sembrava un po 'qualcosa di simile. Ora date un'occhiata in particolare alla linea 7 e 8, e 10 e 11, che inducono quel ciclo, per cui abbiamo mantenuto tornando alla linea 3 ancora, e ancora, e ancora. Ma si scopre che siamo in grado di visualizzare questo algoritmo, qui in pseudocodice, un po 'di più olistico. In realtà, quello che sto cercando a qui sullo schermo, è un algoritmo per la ricerca di Mike Smith tra un insieme di pagine. E in effetti, si potrebbe semplificare questo algoritmo in quelle linee 7 e 8, e 10 e 11 per dire solo questo, che ho presentato qui in giallo. In altre parole, se Mike Smith è in precedenza nel libro, non abbiamo bisogno di specificare passo passo ora come andare a trovare. Non abbiamo specificare per tornare alla linea 3, perché non solo, invece, per esempio, più in generale, cercare Mike nel la metà sinistra del libro. Al contrario, se è Mike in realtà più avanti nel libro, perché non solo citiamo ricerca unquote per Mike nella metà destra del libro. In altre parole, perché non facciamo solo sorta di punt a noi stessi dicendo, cercare Mike in questo sottoinsieme del libro, e lasciare al nostro attuale algoritmo per dirci come cercare Mike in che la metà sinistra del libro. In altre parole, il nostro algoritmo funziona se è una rubrica di questo spessore, di questa spessore, o qualsiasi spessore di sorta. In modo che possiamo in modo ricorsivo definire questo algoritmo. In altre parole, sulla schermo qui, è un algoritmo per la ricerca di Mike Smith tra le pagine di un libro di telefono. Quindi, in linea 7 e 10, diamo solo dire esattamente questo. E io uso questo termine un momento fa, e anzi, la ricorsione è la parola d'ordine, per ora, ed è questo processo di fare qualcosa di ciclico da qualche modo utilizzando il codice che hai già, e chiamarlo di nuovo, e ancora, e ancora. Ora che sta per essere importante che noi in qualche modo inferiore fuori, e non farlo infinitamente lungo. In caso contrario, stiamo andando a hanno infatti un ciclo infinito. Ma vediamo se siamo in grado di prendere in prestito questa idea di una ricorsione, facendo qualcosa di nuovo e ancora e ancora, per risolvere il problema di ordinamento tramite merge sorta, tanto più efficiente. Quindi io do merge sort. Diamo un'occhiata. Così qui è pseudocodice, con che potremmo implementare l'ordinamento, usando questo algoritmo chiamato merge sort. Ed è semplicemente questo. Su ingresso di n elementi, in altre parole, se siete dato n elementi e numeri e lettere o qualunque sia l'ingresso è, se sei dato n elementi, se n è inferiore a 2, solo ritorno. Destra? Perché se n è minore di 2, che significa che la mia lista di elementi o è di dimensione 0 o 1, e in entrambi i casi banali, la lista è già ordinato. Se non esiste un elenco, è ordinato. E se c'è una lista di lunghezza 1, è ovviamente risolto. Quindi l'algoritmo deve solo davvero fare qualcosa di interessante, se abbiamo due o più Elementi dato a noi. Quindi diamo un'occhiata alla magia allora. Altrimenti ordinare la metà sinistra degli elementi, quindi ordinare la metà destra di elementi, quindi unire le due metà ordinati. E che una specie di rompicapo qui, è che io non faccio davvero sembrano avervi detto nulla appena ancora, giusto? Tutto quello che ho detto è, data una lista di n elementi, ordinare la metà sinistra, poi la metà destra, poi unire le due metà ordinati, ma dove è la salsa segreto reale? Dov'è l'algoritmo? Beh, si scopre che quelle due righe prima, la metà sinistra sorta di elementi, e specie metà destra di elementi, sono chiamate ricorsive, per così dire. Dopo tutto, in questo punto nel tempo, devo un algoritmo con cui ordinare un sacco di elementi? Sì. E 'proprio qui. E 'proprio qui sullo schermo, e modo da poter utilizzare la stessa serie di passaggi per ordinare la metà sinistra, come posso la metà destra. E in effetti, ancora, e ancora. Quindi un modo o nell'altro, e faremo presto vedere questo, la magia di merge sort è incorporato in quella finale linea, fondendo le due metà ordinate. E questo sembra abbastanza intuitivo. Si prende due metà, e tu, in qualche modo, si fondono insieme, e vedremo questo concretamente in un attimo. Ma questo è un algoritmo completo. E vediamo esattamente perché. Beh, supponiamo che ci è dato questi stessi otto elementi qui sullo schermo, uno attraverso otto, ma sono in ordine apparentemente casuale. E l'obiettivo è a portata di mano per ordinare questi elementi. Beh, come posso fare per farlo utilizzando, di nuovo, merge sort, di cui al presente pseudocodice? E ancora, radicato in questo la tua mente, solo per un momento. Il primo caso è abbastanza banale, se è inferiore a 2, solo ritorno, non c'è lavoro da fare. Quindi, in realtà c'è solo tre misure per tenere davvero in mente. Ancora una volta, e di nuovo, io sono andando a voler avere per ordinare la metà sinistra, ordinare la metà destra, e poi una volta loro due metà sono ordinati, Voglio fondersi insieme in una lista ordinata. Modo da tenere a mente. Quindi, ecco la lista originale. Cerchiamo di trattare questo come un array, come abbiamo iniziato a in seconda settimana, che è un blocco contiguo di memoria. In questo caso, contenente otto numeri, back to back to back. E diciamo ora riferimento merge sort. Così Prima di tutto voglio ordinare la metà sinistra di questo elenco, e facciamo, quindi, concentrarsi su 4, 8, 6, e 2. Ora, come posso fare per l'ordinamento di un elenco di dimensioni 4? Beh devo prendere in considerazione ora classificare sinistra della metà sinistra. Ancora una volta, facciamo riavvolgere solo per un momento. Se il pseudocodice è questo, e mi sono dato otto elementi, 8 è ovviamente maggiore o uguale a 2. Quindi, con il primo caso non si applica. Quindi, per ordinare otto elementi, in primo luogo ho ordinare la metà sinistra di elementi, poi a ordinare la metà destra, poi mi fondo le due metà ordinate, ciascuno di dimensioni 4. OK. Ma se hai appena detto a me, ordinare la metà di sinistra, che ora è di dimensioni 4, Come faccio a ordinare la metà di sinistra? Beh, se ho un ingresso di quattro elementi, Io Ordina sinistra due, poi il diritto a due, e poi io li fondono insieme. Quindi, di nuovo, diventa un po ' di un rompicapo gioco qui, perché, specie di, devono ricordare dove siete nella storia, ma alla fine della giornata, dato un qualsiasi numero di elementi, si desidera prima di ordinare la metà sinistra, poi la metà destra, poi unirle insieme. Cominciamo a fare esattamente questo. Ecco l'ingresso di otto elementi. Ora stiamo guardando la metà sinistra qui. Come faccio a ordinare quattro elementi? Beh, ho ordinare la metà di sinistra. Ora come faccio a ordinare la metà di sinistra? Beh mi è stata data da due elementi. Quindi cerchiamo di ordinare questi due elementi. 2 è maggiore o pari a 2, ovviamente. In modo che primo caso non si applica. Così ora ho ordinare sinistra metà di questi due elementi. La metà sinistra, naturalmente, è solo 4. Allora, come faccio a ordinare un elenco di un elemento? Bene, ora, quella speciale caso base up superiore, per così dire, si applica. 1 è inferiore a 2, e la mia lista è infatti di dimensioni 1. Così ho appena ritorno. Io non faccio nulla. E infatti, guardare a ciò che ho fatto, 4 è già ordinato. Come se fossi già parzialmente successo qui. Ora che sembra un po 'stupido di rivendicare, ma è vero. 4 è un elenco di dimensioni 1. E 'già ordinato. Questa è la metà di sinistra. Ora io a ordinare la metà destra. Mio ingresso è un elemento, 8 allo stesso modo, già ordinati. Stupido, troppo, ma ancora una volta, questo principio di base sta per permetterci di costruire ora in cima a questa con successo. 4 ordinati, 8 è ordinato, ora che cosa era che ultimo passo? Quindi la terza e ultima fase, qualsiasi ora si sta ordinare una lista, richiamo, è stato quello di unire le due metà, sinistra e destra. Quindi cerchiamo di fare esattamente questo. My metà sinistra è, ovviamente, 4. La mia metà destra è 8. Quindi cerchiamo di fare questo. Per prima cosa ho intenzione di stanziare memoria aggiuntiva, che io rappresento qui, come solo una matrice secondaria, che è abbastanza grande da contenere questo. Ma si può immaginare che si estende quel rettangolo tutta la lunghezza, se abbiamo bisogno di più in seguito. Come faccio a prendere 4 e 8, e unire questi due elenchi di dimensioni 1 insieme? Anche in questo caso, piuttosto semplice. 4 viene prima, poi arriva 8. Perché se voglio ordinare la metà sinistra, poi la metà destra, e quindi unire queste due metà insieme, in modo ordinato, 4 viene prima, poi arriva 8. Quindi ci sembra di fare progressi, anche se non ho fatto alcun lavoro effettivo. Ma ricordate dove siamo nella storia. Abbiamo preso in origine otto elementi. Abbiamo risolto la metà di sinistra, che è 4. Poi abbiamo ordinato la metà sinistra della metà sinistra, che era 2. E qui andiamo. Abbiamo finito con quel passo. Quindi, se abbiamo risolto il lasciato metà del 2, ora siamo deve ordinare la metà destra 2. Quindi la metà destra 2 è questi due valori qui, 6 e 2. Quindi cerchiamo di prendere ora un input di dimensione 2, e ordinare la metà sinistra, e poi la metà destra, e poi unirle insieme. Bene come si ordina un elenco di dimensioni 1, contenente solo il numero 6? Ho già fatto. Tale elenco di dimensioni 1 è ordinato. Come faccio a ordinare un altro elenco di formato 1, il cosiddetto metà destra. Beh, troppo, è già ordinato. Il numero 2 è solo. Così ora ho due metà, a sinistra e a destra, ho bisogno di fondersi insieme. Lasciatemi mi dò qualche spazio in più. E mettere 2 in là, poi 6 in là, così l'ordinamento tale elenco, a destra ea sinistra, e la fusione insieme, in ultima analisi. Quindi sono in forma leggermente migliore. Non ho finito, perché chiaramente 4, 8, 2, 6 non è l'ordinamento finale che voglio. Ma ora ho due liste di dimensioni 2, che hanno entrambi, rispettivamente stati ordinati. Così ora se si riavvolge nella vostra mente di occhio, dove ha fatto che ci lascia? Ho iniziato con otto elementi, poi ho whittled giù alla metà sinistra di 4, poi la metà sinistra di 2, e poi la metà destra di 2, Ho finito, dunque, l'ordinamento sinistra mezzo di 2, e la metà destra di 2, quindi qual è il terzo e ultimo passo qui? Devo fondersi insieme due elenchi di dimensioni 2. Quindi cerchiamo di andare avanti. E sullo schermo qui, dare me qualche memoria aggiuntiva, se tecnicamente, notato che ho ha ottenuto un sacco di spazio vuoto sulla parte superiore Là. Se voglio essere particolarmente spazio efficiente saggio, Potrei iniziare a muoversi gli elementi avanti e indietro, sopra e sotto. Ma solo per chiarezza visiva, Ho intenzione di mettere giù in basso, per mantenere le cose belle e pulite. Così ho due elenchi di dimensioni 2. Il primo elenco è dotato di 4 e 8. La seconda lista ha 2 e 6. Cerchiamo di unire quelli insieme in modo ordinato. 2, ovviamente, viene prima, poi 4, poi 6, poi 8. E ora ci sembra di essere sempre da qualche parte interessante. Metà Ora ho risolto del lista, e per coincidenza, è tutti i numeri pari, ma che è, infatti, solo una coincidenza. Ed ora ho ordinato la sinistra mezzo, in modo che sia 2, 4, 6, e 8. Niente è fuori uso. Che si sente come il progresso. Ora ci si sente come ho state parlando per sempre ora, così quello che resta da vedere se questo algoritmo è, infatti, più efficiente. Ma stiamo attraversando super metodicamente. Un computer, naturalmente, farebbe così. Allora, dove siamo? Abbiamo iniziato con otto elementi. Ho risolto la metà sinistra del 4. Mi sembra di essere fatto con questo. Così ora il passo successivo è quello di ordinare la metà destra della 4. E questa parte possiamo andare attraverso un po 'più rapidamente, anche se sei benvenuto per riavvolgere o mettere in pausa, semplicemente pensare attraverso di essa a proprio ritmo, ma cosa che abbiamo ora è l'occasione per fare la stessa algoritmo su quattro numeri diversi. Quindi cerchiamo di andare avanti, e concentrarsi su la metà destra, che siamo qui. La metà sinistra di tale metà destra, e ora il metà sinistra della sinistra metà di quella metà destra, e come faccio a ordinare un elenco di dimensioni 1 contenente solo il numero 1? È già fatto. Come posso fare lo stesso per la lista di dimensioni 1 contenente solo 7? È già fatto. Fase tre per questo mezzo poi è quello di unire questi due elementi in un nuovo elenco di dimensioni 2, 1 e 7. Non sembrano aver fatto tutto che molto lavoro interessante. Vediamo cosa succede dopo. Ho appena risolto la metà sinistra del a destra la metà del mio ingresso originale. Ora cerchiamo di ordinare il giusto mezzo, che contiene 5 e 3. Diamo ancora un'occhiata a sinistra mezzo, ordinato, metà di destra, ordinato, e unire quei due insieme, in qualche spazio aggiuntivo, 3 viene prima, poi arriva 5. E così ora, abbiamo ordinato il metà sinistra della metà destra del problema originale, e la metà destra della metà destra del problema originale. Qual è il terzo e ultimo passo? Beh di fondere queste due metà insieme. Così mi permetta di ottenere un po 'di me stesso spazio in più, ma, ancora una volta, io potrebbe essere utilizzando lo spazio sulla parte superiore di ricambio. Ma stiamo andando a tenere semplice visivamente. Permettetemi di fondere in ora 1, e poi 3, e poi 5 e quindi 7. In tal modo lasciandomi ora con il metà destra del problema originale che è perfettamente ordinato. Allora, cosa rimane? Mi sento come se continuo a dire il cose stesse di nuovo, e di nuovo, ma questo è riflettente del fatto che stiamo utilizzando la ricorsione. Il processo di utilizzo di un algoritmo ancora, e ancora, su piccoli sottoinsiemi di il problema originale. Così ora ho un sinistro ordinato metà del problema originale. Ho una mezza ordinato destra del problema originale. Qual è il terzo e ultimo passo? Oh, è la fusione. Allora, facciamo così. Facciamo un po 'di destinare aggiuntivo memoria, ma il mio dio, noi potrebbe mettere ovunque ora. Abbiamo così tanto spazio a disposizione a noi, ma noi terremo le cose semplici. Invece di andare avanti e avanti con la nostra memoria originale, facciamo solo fare visivamente giù qui sotto, per finire la fusione metà sinistra e la metà destra. Quindi attraverso la fusione, che cosa devo fare? Voglio prendere gli elementi in ordine. Così guardando la metà sinistra, Vedo il primo numero è 2. Guardo la metà destra, Vedo il primo numero è 1, quindi ovviamente che numero Voglio cogliere fuori, e mettere al primo posto nella mia lista finale? Naturalmente, 1. Ora voglio fare la stessa domanda. Sulla metà sinistra, ho ancora ottenuto il numero 2. Sulla metà destra, Ho il numero 3. Quale voglio scegliere? Naturalmente, il numero 2 e ora notare i candidati 4 sono a sinistra, 3 a destra. Diamo, naturalmente, scegliere 3. Ora i candidati sono 4 su sinistra, 5 a destra. Noi, naturalmente, scegliere 4. 6 a sinistra, a destra 5. Noi, naturalmente, scegliere 5. 6 sulla sinistra, 7 sulla destra. Scegliamo 6, e poi noi scegliete 7, e quindi scegliamo 8. Voila. Così un enorme numero di parole successiva, abbiamo hanno ordinato questo elenco di otto elementi in un elenco di uno a otto, che è in aumento ad ogni passo, ma quanto tempo ha fatto ci vuole noi a farlo. Beh, io ho deliberatamente cose disposte Pittoricamente qui, in modo che possiamo tipo di vedere o apprezzare la divisione a conquistare che sta succedendo. Infatti, se si guarda indietro alla veglia funebre, Ho lasciato tutte queste linee tratteggiate in segnaposti, è possibile, tipo di vedere, in ordine inverso, se è sorta di guardare indietro a la storia ora, la mia lista originale è, ovviamente, di dimensioni 8. E poi in precedenza, sono stato si tratta di due elenchi di dimensioni 4, e poi quattro liste di dimensioni 2, e poi otto liste di dimensioni 1. Così che cosa fa questo, tipo di, vi ricorderà? Ebbene, infatti, qualsiasi gli algoritmi ABBIAMO guardato finora dove siamo dividere, e si dividono, e dividere, continuare ad avere le cose di nuovo, e di nuovo, in questa idea generale. E quindi c'è qualcosa logaritmica succedendo qui. E non è del tutto log n, ma c'è una componente logaritmica a quello che abbiamo appena fatto. Consideriamo ora come che in realtà è. Così accedere di n, ancora una volta è stato un grande tempo di esecuzione, quando abbiamo fatto qualcosa di simile ricerca binaria, come noi ora chiamiamo, la strategia divide et impera via che abbiamo trovato Mike Smith. Ora tecnicamente. Ecco logaritmo in base 2 di n, anche anche se nella maggior parte delle classi di matematica, 10 è di solito la base che si assume. Ma gli scienziati informatici quasi sempre pensare e parlare in termini di base 2, quindi generalmente solo dire di registro n, invece di logaritmo in base 2 di n, ma sono esattamente uno e il stesso nel mondo di calcolatore la scienza, e come una digressione, c'è un fattore costante differenza tra i due, quindi è Moot comunque, per motivi formali. Ma per ora, ciò che ci preoccupa circa è questo esempio. Quindi cerchiamo di non dimostrare con l'esempio, ma a utilizzare almeno un esempio dei numeri a portata di mano come un controllo di integrità, se si vuole. Così in precedenza la formula era logaritmo in base 2 di n, ma ciò è n in questo caso. Ho avuto i numeri n originali, o 8 del numero originale appositamente. Ora è stato un po ' mentre, ma sono abbastanza Assicurarsi che logaritmo in base 2 del valore 8 è 3, e in effetti, cosa c'è di bello di questo è 3 che è esattamente il numero di volte che è possibile dividere un lista di nuovo, e ancora di lunghezza 8, e ancora, fino a quando si è lasciato con liste di appena formato 1. Destra? 8 va a 4, va a 2, va a 1, e questo è riflettente esattamente questo immagine abbiamo avuto solo un momento fa. Quindi un po 'di buon senso controllare da dove il logaritmo è effettivamente coinvolto. Così ora, che altro è coinvolto qui? n. Così notare che ogni volta ho diviso la lista, anche se in ordine inverso nella storia qui, stavo ancora facendo cose n. Questo passo ha richiesto che la fusione Tocco ognuno dei numeri, per farlo scorrere in la sua posizione appropriata. Quindi, anche se l'altezza di questo diagramma è di dimensioni del registro n di n o 3, specificamente, in altre parole, Ho fatto tre divisioni qui. Quanto lavoro ho fatto orizzontalmente lungo questo grafico ogni volta? Beh, ho fatto n passi di lavorare, perché se ho ottenuto quattro elementi e quattro elementi, e ho bisogno di fondersi insieme. Ho bisogno di passare attraverso questi quattro e questi quattro, in ultima analisi, per unirle torna in otto elementi. Se al contrario ho otto dita qui, che non lo faccio, e otto fingers-- sorry-- Se ho ottenuto quattro dita qui, che faccio, quattro dita qui, che faccio, poi è la stessa esempio di prima, se lo faccio hanno otto dita anche se in totale, che posso, di tipo, fare. Posso esattamente fare qui, allora posso certamente unire tutti questi elenchi di dimensioni 1 insieme. Ma certamente devo guardare ad ogni elemento esattamente una volta. Quindi l'altezza di questo processo è log n, la larghezza di questo processo, per così dire, è n, per cui ciò che ci sembra di avere, in ultima analisi, è un tempo di esecuzione di dimensione n volte log n. In altre parole, abbiamo diviso l'elenco, registro n volte, ma ogni volta che abbiamo fatto, abbiamo avuto toccare ognuno degli elementi al fine di unire i loro tutti insieme, che fu n per passo, in modo da avere n volte il log n, o come un informatico direbbe, asintoticamente, che sarebbe la parola grossa per descrivere la tomaia vincolato su un tempo di esecuzione, ci sono in esecuzione in una grande o di log n tempo, per così dire. Ora, questo è significativo, perché ricordano quello che i tempi di esecuzione sono stati con bubble sort, e la selezione ordinare e insertion sort, e anche un paio di altri che esistono, n quadrato era dove eravamo. E si può, un po ', questa qui. Se n è ovviamente quadrato n volte n, ma qui abbiamo n volte log N, e sappiamo già da settimana zero, cioè log n, logaritmico, è meglio di qualcosa lineare. Dopo tutto, ricordare l'immagine con il rosso e il giallo e le linee verdi che abbiamo disegnato, il Linea logaritmica verde era molto più basso. E quindi, molto meglio e più velocemente che le linee gialle e rosse diritte, n volte il log-n è, infatti, una migliore di n volte n o n squadrato. Quindi ci sembra di avere identificato un algoritmo di unione tipo che viene eseguito in tanto tempo più veloce, e in effetti, è per questo che, all'inizio di questa settimana, quando abbiamo visto che gara tra bolla sort, selection sort, e unire Ordina, merge sort davvero, davvero vinto. E in effetti, non abbiamo neanche aspettare per bubble sort e ordinamento per selezione finire. Ora diamo un altro passaggio a questo, da un po 'più punto di vista formale, proprio in caso, questo risuona meglio quella discussione livello superiore. Quindi, ecco di nuovo l'algoritmo. Proviamo a chiederci, ciò che il tempo di esecuzione è di questo algoritmi varie fasi? Dividiamo in primo caso e il secondo caso. L'IF e l'altro nel caso in cui, Se n è inferiore a 2, appena di ritorno. Si sente come costante di tempo. E ', specie di, come due fasi, Se n è inferiore a 2, per poi tornare. Ma come abbiamo detto il Lunedi, costante di tempo, o grande o di 1, possono essere due, tre passi passi, anche 1.000 gradini. Ciò che conta è che è un numero costante di passi. Così il giallo evidenziato pseudocodice qui corre in, che chiameremo, costante di tempo. Quindi più formalmente, e stiamo andando a-- questo sarà la misura in cui formalizzare questo diritto now-- T di n, il tempo di esecuzione di un problema che prende n quarantina come input, equivale grosso o di uno, Se N è inferiore a 2. Quindi è subordinata tale. Quindi, per essere chiaro, se n è inferiore a 2, abbiamo una lista molto breve, quindi il tempo di esecuzione, T di n, dove n è 1 o 0, in questo caso molto specifico, è solo sarà tempo costante. Sta andando a prendere uno passo, due passi, qualunque cosa. Si tratta di un numero fisso di passaggi. Così la parte succosa deve essere sicuramente in l'altro caso in pseudocodice. Il caso ELSE. Ordina metà sinistra di elementi, tipo giusto la metà di elementi, si fondono metà ordinati. Quanto dura ciascuno di questi passi prendere? Ebbene, se il funzionamento tempo per ordinare n elementi è, chiamiamolo molto genericamente, T di n, allora l'ordinamento sinistra metà degli elementi è, un po ', come dire, T di n diviso 2, e similmente classificare la metà destra di elementi è, un po ', come dire, T di n diviso 2, e poi fondendo le due metà ordinati. Beh, se ho un po ' numero di elementi qui, come quattro, e qualche numero di elementi qui, come quattro, e devo unire ciascuno di questi quattro in, e ciascuno di questi quattro, uno dopo l'altra, in modo che in ultima analisi, ho otto elementi. Ci si sente come questo è grande o di n passi? Se ho n dita e ciascuno di li deve essere fusi in luogo, che è come un altro n passi. Così infatti formulaically, possiamo esprimere questo, anche se un po spaventosamente in un primo momento sguardo, ma è qualcosa che cattura esattamente questa logica. Il tempo di esecuzione, T di n, n IF è maggiore o uguale a 2. In questo caso, il caso ELSE, è T di n diviso 2, oltre a T di N diviso 2, più grande o di n, un po ' Numero lineare di passi, forse esattamente n, forse 2 volte n, ma è grosso modo, ordine di n. In modo che, anche, è come possiamo esprimere questo formulaically. Ora non si sa questo meno avete registrato nella vostra mente, o cercarlo nella indietro di un libro di testo, che potrebbe avere un po ' cheat sheet, alla fine, ma questa è, in effetti, andando ci danno una grande o di n log n, perché la ricorrenza che che vedete qui sullo schermo, se effettivamente fatto fuori, con un numero infinito di esempi, o avete fatto formulaically, si farebbe vedere che questo, perché questa formula si è ricorsivo, con t n sopra qualcosa sulla destra, e t di n sopra sulla sinistra, questo può effettivamente essere espressa, in ultima analisi, grande andare log n n. Se non convinto, che è bene per ora, solo prendere sulla fede, quella che è, in effetti, cosa che porta alla recidiva, ma questo è solo un po 'più di un approccio matematico a guardare al tempo di esecuzione di merge sort in base alla sua pseudocodice solo. Ora diamo un po 'di sfiato da tutto questo, e dare un'occhiata a un certo ex senatore, che potrebbe apparire un po 'familiare, che si sedette con Google Eric Schmidt, qualche tempo fa, per un colloquio sul palco, di fronte a un sacco di persone, parlare in ultima analisi su un argomento, che è abbastanza ormai familiare. Diamo un'occhiata. Eric Schmidt: ora senatore, tu sei qui a Google, e mi piace pensare al presidenza come un colloquio di lavoro. Ora è difficile trovare un lavoro come presidente. Il presidente Obama: Giusto. Eric Schmidt: E tu sei intenzione di fare [incomprensibile] ora. E 'anche difficile ottenere un lavoro presso Google. Il presidente Obama: Giusto. Eric Schmidt: Abbiamo domande, e chiediamo ai nostri candidati domande, e questo è da Larry Schwimmer. PRESIDENTE OBAMA: OK. Eric Schmidt: Che cosa? Voi ragazzi che io stia scherzando? E 'proprio qui. Qual è il modo più efficace per ordinare un milione di numeri interi a 32 bit? PRESIDENTE OBAMA: Well-- Eric Schmidt: A volte, forse mi dispiace, maybe-- Il presidente Obama: No, no, no, no, no, io think-- Eric Schmidt: Che non è it-- PRESIDENTE OBAMA: I pensare, credo che la bolla specie sarebbe il modo sbagliato di procedere. Eric Schmidt: Andiamo. Chi lo ha detto questo? OK. Non ho l'informatica on-- PRESIDENTE OBAMA: ABBIAMO ottenuto nostre spie in là. IL PROFESSORE: Va bene. Lasciamo dietro di noi ora il mondo teorico di algoritmi nell'analisi asintotica dello stesso, e tornare a alcuni argomenti dalla settimana zero e uno, e inizio per rimuovere alcune ruote di formazione, se vuoi. In modo che si capisce davvero in ultima analisi, da zero, ciò che è succedendo sotto il cofano, quando si scrivere, compilare, ed eseguire programmi. Ricordiamo in particolare, che questo era il primo programma C abbiamo guardato, una canonica semplice programma, di sorta, relativamente parlando, in cui, stampa, Ciao Mondo. E ricordo che ho detto, il processo che il codice sorgente passa attraverso è esattamente questo. Prendete il vostro codice sorgente, passa attraverso un compilatore, come Clang, e viene fuori codice oggetto, che potrebbe apparire come questo, zero e uno che la CPU del computer, centrale unità di elaborazione o il cervello, in ultima analisi, capisce. Si scopre che questo è un po 'di una semplificazione eccessiva, che siamo ora in una grado di prendere in giro a parte per capire che cosa è veramente stato succedendo sotto il cofano ogni volta che si esegue Clang, o più in generale, ogni volta che si effettua un programma, utilizzando Marca e CF 50 IDE. In particolare, cose del genere questa sarà subito generato, quando si compila il programma. In altre parole, quando si prendere il codice sorgente e compilarlo, ciò che è prima essendo uscita dal Clang è qualcosa di noto come codice assembly. E infatti, sembra esattamente come questo. Ho eseguito un comando al linea di comando in precedenza. Ciao.c Clang precipitare capitale s, e questo ha creato un file per me chiamati hello.s, all'interno del quale erano esattamente questi contenuti, e un po 'più sopra e poco più sotto, ma ho messo il più succosi informazioni qui sullo schermo. E se si guarda da vicino, vedrete almeno alcune parole chiave familiare. Abbiamo principale in alto. Abbiamo printf nel mezzo. E abbiamo anche ciao mondo backslash n tra virgolette sottostanti. E tutto il resto qui è istruzioni molto basso livello che la CPU del computer capisce. Istruzioni della CPU che si muovono memoria intorno, che le stringhe di carico dalla memoria, e in ultima analisi, la stampa le cose sullo schermo. Ora, cosa succede se dopo questo codice assembly viene generato? In ultima analisi, si fa, infatti, ancora generare codice oggetto. Ma i passi che hanno veramente sta succedendo sotto il cofano guardare un po 'più simile a questo. Il codice sorgente diviene codice assembly, che poi diviene codice oggetto, e le parole chiave qui è che, quando si compila il codice sorgente, viene fuori codice assembly, e poi quando si assemblano il codice assembly, viene fuori codice oggetto. Ora Clang è super sofisticato, come un sacco di compilatori, e lo fa tutti questi passaggi insieme, e non necessariamente Uscita qualsiasi intermedio i file che si può anche vedere. Compila solo le cose, che è il termine generale che descrive l'intero processo. Ma se si vuole veramente essere particolare, c'è molto più in corso anche lì. Ma consideriamo anche ora che anche che super semplice programma, hello.c, detta funzione. Si chiama printf. Ma non ho scritto printf, infatti, che viene fornito con c, per così dire. E 'un richiamo funzione che è dichiarato in io.h standard, che è un file di intestazione, che è un argomento che sarà in realtà immergersi più in profondità in breve tempo. Ma un file di intestazione è tipicamente accompagnato da un file di codice, file di codice sorgente, in modo molto simile esiste io.h. norma Qualche tempo fa, qualcuno, o qualcuno, ha anche scritto un file chiamato io.c standard in che le definizioni attuali, o implementazioni di printf, e mazzi di altre funzioni, sono effettivamente scritti. Quindi, dato che, se si considera che ha qui a sinistra, ciao.c, che quando compilato, ci dà hello.s, anche se Clang non si preoccupa di risparmio in un posto possiamo vedere, e che codice assembly viene assemblato in hello.o, che è, infatti, il nome di default data ogni volta che si compila fonte codificare in codice oggetto, ma non sono abbastanza pronto per eseguirlo ancora, perché un altro passo deve accadere, e ha sta accadendo per il passato poche settimane, forse a tua insaputa. In particolare da qualche parte in CS50 IDE, e questo, troppo, sarà un po 'di un semplificazione per un momento, vi è, o era un tempo, un file chiamato io.c standard che qualcuno compilato in io.s standard o l'equivalente, che qualcuno poi assemblati in io.o di serie, o risulta in un lima leggermente diverso formato che può avere un diverso file di estensione del tutto, ma in teoria e concettualmente, esattamente tali passaggi dovevano accadere in qualche forma. Vale a dire, che ora quando sto scrivendo un programma, hello.c, che dice basta, ciao mondo, e sto utilizzando il codice di qualcun altro come printf, che una volta era su un tempo, in un file chiamato io.c standard quindi in qualche modo devo prendere il mio codice oggetto, i miei e quelli, zero e l'oggetto di quella persona codice, o zero e uno, e in qualche modo collegarli insieme in un file finale, chiamato ciao, che ha tutti gli zeri e quelli di mia funzione principale, e tutti gli zeri e quelli per printf. E in effetti, che l'ultimo processo è chiamato, collegando il vostro codice oggetto. L'uscita di cui è un file eseguibile. Quindi, in tutta onestà, al fine della giornata, niente è cambiato da una settimana, quando abbiamo prima ha iniziato la compilazione di programmi. Infatti, tutto questo è stato accade sotto il cofano, ma ora siamo in una posizione dove possiamo realmente tease oltre questi vari passaggi. E infatti, alla fine del giorno, siamo ancora sinistra con zero e uno, che è in realtà un grande segue ora a un'altra capacità di C, che non abbiamo dovuto sfruttare più probabile fino ad oggi, noto come operatori bit a bit. In altre parole, finora, in qualsiasi momento abbiamo affrontato con i dati in C o variabili in C, abbiamo avuto le cose come caratteri e carri allegorici e ins e anela e doppie e simili, ma tutti questi sono almeno otto bit. Non abbiamo mai potuto ancora manipolare i singoli bit, anche se un singolo bit, abbiamo so, può rappresentare uno 0 e un 1. Ora si scopre che in C, è possono ottenere l'accesso ai singoli bit, se si conosce la sintassi, con cui arrivare a loro. Quindi, diamo uno sguardo a operatori bit a bit. Quindi, nella foto qui sono alcuni simboli che abbiamo, una sorta di, una sorta di, visto prima. Vedo una e commerciale, un verticale bar, e alcuni altri, nonché, e ricordare che commerciale e commerciale è qualcosa che abbiamo visto prima. L'operatore logico AND, dove si ha due insieme, o l'OR logico operatore, dove si avere due barre verticali. Operatori bit a bit, di cui parleremo vedere operare su pezzi individualmente, basta usare un singolo commerciale, un barra verticale singolo, il simbolo di inserimento viene dopo, il piccolo tilde, e poi a sinistra staffa sinistra staffa o Staffa destra parentesi destra. Ognuno di questi hanno significati diversi. In realtà, diamo uno sguardo. Andiamo oggi vecchia scuola, e l'uso un touch screen da ieri, conosciuto come un bordo bianco. E questa scheda bianca sta per permetterci per esprimere alcuni simboli abbastanza semplici, o meglio alcune formule abbastanza semplici, che possiamo quindi in ultima analisi leva, al fine per accedere ai singoli bit all'interno di un programma C. In altre parole, cerchiamo di fare questo. Parliamo prima per un momento su e commerciale, che è l'operatore AND bit a bit. In altre parole, si tratta un operatore che permette me avere una variabile sinistra tipicamente, e una variabile a destra, o un valore individuale, che se E insieme, mi dà un risultato finale. Così che cosa voglio dire? Se in un programma, si dispone di una variabile che memorizza uno di questi valori, o teniamolo semplice, e basta scrivere zero e uno individuale, Ecco come funziona l'operatore commerciale. 0 0 e commerciale sta per uguale a 0. Ora perché? E 'molto simile a Espressioni booleane, che abbiamo discusso finora. Se si pensa che, dopo tutto, la 0 è falso, 0 è falso, falso e falso è, come abbiamo discusso logicamente, anche falso. Così otteniamo 0 anche qui. Se si prende 0 e commerciale 1, bene che, anche, sta per essere 0, perché per questo espressione di sinistra sia vero o 1, che avrebbe bisogno di essere vero e vero. Ma qui abbiamo falso e vero, o 0 e 1. Ora di nuovo, se abbiamo 1 e commerciale 0, che, anche, sta per essere 0, e se abbiamo 1 e commerciale 1, finalmente abbiamo un 1 bit. Quindi, in altre parole, non stiamo facendo qualcosa di interessante con questo operatore appena ancora, questo operatore commerciale. E 'l'operatore AND bit a bit. Ma questi sono gli ingredienti attraverso il quale si può fare cose interessanti, come vedremo presto. Ora diamo un'occhiata a solo il singolo barra verticale sopra qui a destra. Se ho un po 'e io 0 O con il bit per bit OR operatore, un altro po '0, che sta per darmi 0. Se prendo un po '0 e OR con un 1 po ', poi ho intenzione di ottenere 1. Ed infatti, solo per chiarezza, lasciami andare indietro, in modo che le mie barre verticali non vengono scambiati per 1 di. Permettetemi di riscrivere tutti il mio 1 è un po 'di più chiaramente, così che noi vediamo il prossimo, se io hanno un 1 o 0, che sta per essere un 1, e se ho un 1 o 1 che, Anche, sta per essere un 1. Così si può vedere logicamente che l'OR operatore si comporta in modo molto diverso. Questo mi dà 0 O 0 0 mi dà, ma ogni altra combinazione mi dà 1. Finché ho un 1 nel formula, il risultato sarà 1. In contrasto con AND operatore, la e commerciale, solo se ho due 1 nella equazione, posso effettivamente ottenere un 1 fuori. Ora c'è un pochi altri operatori. Uno di loro è un po 'più complicato. Quindi lasciami andare avanti e cancelli questo per liberare un po 'di spazio. E diamo uno sguardo al simbolo di inserimento, solo per un momento. Questo è tipicamente un carattere è possibile digitare sulla Maiusc detenzione tastiera e allora uno dei numeri in cima vostro Uniti tastiera. Quindi questo è l'esclusiva Operatore OR, OR esclusivo. Così abbiamo appena visto l'operatore OR. Questo è l'esclusivo operatore OR. Qual è realmente la differenza? Beh diciamo basta guardare la formula, e usare questo come ingredienti in definitiva. 0 XOR 0. Io vado a dire è sempre 0. Questa è la definizione di XOR. 0 XOR 1 sarà 1. 1 XOR 0 sta per essere 1, e 1 XOR 1 sta per essere? Sbagliato? O destra? Non lo so. 0. Ora che cosa sta succedendo qui? Beh, pensare al il nome di questo operatore. OR esclusivo, così come la nome, tipo di, suggerisce, la risposta è solo andare a essere un 1 se gli ingressi sono esclusivi, esclusivamente diverso. Così qui gli ingressi sono il stesso, quindi l'uscita è 0. Qui gli ingressi sono il stesso, quindi l'uscita è 0. Qui ci sono le uscite sono diverse, sono esclusivi, e quindi l'uscita è 1. Quindi è molto simile a E, è molto simile, o meglio, è molto simile a O, ma solo in modo esclusivo. Questo non è un 1, perché abbiamo due di 1, e non esclusivamente, solo uno di loro. Tutto ok. E gli altri? Beh, la tilde, nel frattempo, è davvero bello e semplice, per fortuna. E questo è un unario operatore, il che significa è applicato ad un solo ingresso, un operando, per così dire. Non a sinistra e destra. In altre parole, se si prende di tilde 0, la risposta sarà l'opposto. E se si prende tilde di 1, il risposta ci sarà l'opposto. Così l'operatore tilde è un modo di negare un po ', o capovolgere un po 'da 0 a 1, o da 1 a 0. E che ci lascia finalmente con solo due operatori finali, il cosiddetto spostamento a sinistra, e la cosiddetto operatore di spostamento a destra. Diamo un'occhiata a come quelli di lavoro. L'operatore spostamento a sinistra, scritta con due parentesi angolari del genere, il seguente. Se il mio ingresso, o il mio operando, a sinistra operatore di spostamento è semplicemente un 1. E io allora dico il computer per spostamento a sinistra che 1, dico sette posti, il risultato è come se io prendere quel 1, e spostarla sette piazzole su al sinistra, e per impostazione predefinita, stiamo andando a supporre che lo spazio a destra sta per essere riempito con gli zeri. In altre parole, uno spostamento a sinistra 7 sta andando per darmi quel 1, seguito da 1, 2, 3, 4, 5, 6, 7 zeri. Quindi, in un certo senso, ti permette di prendere un numero piccolo come 1, e chiaramente fare molto molto, molto più grande in questo modo, ma realmente stiamo andando a vedere approcci più intelligenti per lo invece, pure, Tutto ok. Questo è tutto per tre settimane. Ci vediamo la prossima volta. Questo è stato CS50. [RIPRODUZIONE DI BRANI MUSICALI] SPEAKER 1: E 'stato presso lo snack bar a mangiare un hot fudge sundae. Ha avuto tutto il suo viso. Indossa che il cioccolato come una barba SPEAKER 2: Che cosa stai facendo? SPEAKER 3: Hmmm? Che cosa? SPEAKER 2: hai appena double dip? È doppio immersi chip. SPEAKER 3: Mi scusi. SPEAKER 2: immersi il chip, è ha preso un morso, e hai immerso di nuovo. SPEAKER 3: SPEAKER 2: Ecco come mettere destra bocca tutto in tuffo. La prossima volta che si prende un chip, basta immergerlo una volta, e alla fine di esso. SPEAKER 3: Sai una cosa, Dan? Immergete il modo in cui si desidera immergersi. Mi tuffo il modo in cui voglio immergere.