[MUSIC PLAYING] 

DAVID J. MALAN: Va bene. Quindi bentornato. Questo è CS50, ed è il la fine della terza settimana. 

Quindi richiamare nelle ultime settimane, abbiamo passato un po 'di tempo su C, sulla programmazione, sulla sintassi. Ed è abbastanza normale, se siete ancora alle prese con il problema di Set 2, per essere sbattere la testa contro il muro. Si tratta di messaggi di errore criptico-looking e gli insetti che si non riesco a inseguire. Perché, stare tranquilli, che in appena un tempo qualche settimana ti guarderai indietro cose come Cesare, e [? V-genair,?] forse anche Crack, e rende conto fino a che punto siete arrivati in un breve periodo di tempo. Quindi, se questo è di consolazione, appendere in là, per ora. 

Oggi, però, cominciamo a transizione a cose livello superiore. E cominciamo a dare per scontato che voi sapete come programmare, o almeno gli inizi di che il livello di comfort. E cominceremo a considerare come possiamo andare sulla progettazione di programmi di più efficacemente. Come possiamo fare per ottimizzare l' efficienza dei nostri algoritmi, e in genere la soluzione più problemi interessanti. E cominciando a dare per scontato che, se volessimo, potremmo codificare fino qualsiasi degli esempi che abbiamo in mente. Così oggi, non toccare la tastiera per qualsiasi forma di codice. Sarà livello molto più alto, e in ultima analisi, di problem-solving. 

Quindi, per arrivare a quel punto, mi propongo che le seguenti sette rettangoli rappresentano sette porte, dietro che sono un insieme di i numeri, tra i quali è il numero 50. Lasciatemi proietto questo su questo schermo anche qui. E proponiamo che abbiamo bisogno di un volontario per aiutarmi a trovare un numero davanti internet qui per vedere. Vieni su, in rosa. D'accordo. Qual è il tuo nome? 

JENNIFER: [incomprensibile] 

DAVID J. MALAN: Sorry? 

JENNIFER: Jennifer. 

DAVID J. MALAN: Jennifer. D'accordo, Jennifer. Lieto di vederla. Andiamo su. Quindi questi qui sono sette porte, e cosa Mi piacerebbe che tu faccia per noi qui, di fronte a tutti i tuoi compagni di classe, ci si trova il numero, 50. Per trovare un numero, è possibile sbirciare dietro una di queste porte semplicemente toccando su una delle porte, e rivelerà il suo numero. E vediamo quanto velocemente si riesce a trovare noi il numero, il 50. 

15. 16. 50. Ben fatto. D'accordo. Applauso per Jennifer. 

[Applausi] 

D'accordo. Così che cosa è stata la tua strategia per trovando il numero, 50? 

JENNIFER: Uhm, ho pensato che forse se - [Incomprensibile] 

DAVID J. MALAN: Oh. Dategli un secondo. Quindi è stata la tua strategia per trovando il numero, 50? 

JENNIFER: Così ho appena iniziare a cominciando a vedere ciò che il primo numero ero, e poi ho pensato, forse se stanno ordinati, mi limiterò a continuare toccando più in alto? 

DAVID J. MALAN: OK. E ci sembra di aver trovato che essere il caso. Anche se, cerchiamo di staccare gli strati solo un po ', e si vuole andare avanti e rivelare le altre porte avresti potuto scegliere? 

JENNIFER: Oh, cara. 

DAVID J. MALAN: Ah. 

JENNIFER: Così ho semplicemente fortunato. 

DAVID J. MALAN: Così avete ottenuto fortunato. D'accordo. Quindi, non è male. Ma questo è un interessante intuizione, giusto? Se si presume, e avete fatto ottenere, in effetti, un po 'fortunati lì. Ma se si presume che i numeri erano allineati, si può essere più precisi di come tale influenzato il tuo comportamento? 

JENNIFER: Quindi, se sono stati ordinati, ho pensato che forse più piccolo al più grande. 

DAVID J. MALAN: OK. 

JENNIFER: O se questo ha finito per essere davvero grande, quindi più grande al più piccolo. 

DAVID J. MALAN: OK. Così grande al più piccolo, o più piccolo al più grande. Ma lasciate che propongo, si supponga di avere ottenuto sfortunato, e supporre che essi non sono stati, infatti, selezionati, quanti di quelle porte hai provato a sbirciare dietro in quel caso peggiore? 

JENNIFER: Tutti. 

DAVID J. MALAN: Tutti. Quindi cerchiamo di generalizzare che come n. Ci capita di essere 7, ma cerchiamo di più in genere ci dicono di N. porte sul schermata qui. Quindi, nel caso peggiore, si avrebbe di guardare dietro sette porte, o porte n. E così questo è davvero, è un po 'di fortuna oggi, ma è davvero un lineare algoritmo di sorta, anche se si erano tipo di saltare in giro. E 'giusto? 

JENNIFER: Già. 

DAVID J. MALAN: Beh, fammi vedere se il vostro cambiamenti di strategia, se ci mi muovo il nostro secondo esempio qui con 7 diverse porte. Stessi numeri, ma questo volta che sono allineati. Qual è la vostra strategia qui sta per essere, cercando di mettere fuori di testa che cosa gli altri numeri erano - 

JENNIFER: OK. 

DAVID J. MALAN: - prima? 

JENNIFER: Partiamo con il primo. 

DAVID J. MALAN: Va bene. Iniziare con la prima. 4. Ora dove hai intenzione di andare, e perché? 

JENNIFER: 4 è davvero piccolo. Quindi, se sono specie forse più piccolo al più grande, dovrebbe essere il doppio, e -. 

DAVID J. MALAN: OK. Vediamo, che ne pensi? 

JENNIFER: Prova l'ultimo. Nizza. 

DAVID J. MALAN: Molto ben fatto. D'accordo. 

[Applausi] 

DAVID J. MALAN: OK. Quindi, si sta effettivamente facendo questo orribilmente, perché sei facendo molto bene. Il che ci lascia incapaci di fare alcuni punti. Allora proviamo a rotolare di nuovo qui. 

JENNIFER: OK. 

DAVID J. MALAN: molto bene fatto, comunque. Quindi hai iniziato all'inizio, hai visto che era 4, poi si spostato alla fine. Ma supponiamo che non hai avuto fortuna lì, e supponiamo 50 era da qualche altra parte. Che la tua terza fase sono stati? 

JENNIFER: torna all'inizio. 

DAVID J. MALAN: Tornate all'inizio. OK, così avresti toccato questo porta, che era 8. D'accordo. Quindi questo non è 50. Dove avresti guardato il prossimo? 

JENNIFER: Se non l'ho fatto sanno hanno risolto. 

DAVID J. MALAN: Corretto. Beh, se lo sapessi sono stati ordinati - 

JENNIFER: Oh, lo sapevo, sì. 

DAVID J. MALAN: - Ma non hai sapere dove 50 era ancora? 

JENNIFER: Basta andare avanti. 

DAVID J. MALAN: Va bene. OK. Continua ad andare. OK, che posso lavorare. 

JENNIFER: OK. 

DAVID J. MALAN: Ora, se sei solo Continueremo a correre, qual è la tua algoritmo devolvendo sostenuto in. 

JENNIFER: Il lineare -. 

DAVID J. MALAN: E 'tipo di lineare. Ma lasciate che propongo, lasciare mi ha messo sul posto. Permettetemi di aggiornare la pagina. stesso numero, stessa disposizione, porte stesse. Ma ripensare a quel primo giorno in classe quando abbiamo strappato una rubrica telefonica in la metà, più o meno, e quello che era la nostra strategia di là? 

JENNIFER: Iniziare a metà. 

DAVID J. MALAN: OK. Così inizia a metà. Quindi andiamo avanti e simulare quello. Iniziare al centro di rivelando che porta. Quindi il numero 16. Quindi quale sarebbe il forte ragazzo hanno fatto, che strappò il libro di telefono a metà, per arrivare al prossimo indovinare? 

JENNIFER: Andate in questo mezzo. 

DAVID J. MALAN: E perché a destra? 

JENNIFER: se fossero una sorta di piccolo al più grande, poi il 50 dovrebbe essere a quella estremità. 

DAVID J. MALAN: Buono. Assolutamente ragionevole. Così come una rubrica telefonica, si va al destra rispetto alla sinistra, ma qui è il takeaway chiave. Ora è possibile buttare via, o strappare, metà di questo problema, non lasciando con 7 porte, ma in realtà con solo 3. Che è circa la metà del dimensione del problema. D'accordo. Così ora quello che si avrebbe fatto dopo si va a destra? 

JENNIFER: Quindi 16 è ancora piuttosto piccolo, rispetto al 50, quindi forse ci proverò, come, questa. 

DAVID J. MALAN: Va bene. 42. Bene, così ora qual è la tua l'istinto che ti dice? 

JENNIFER: posso buttare via questo e poi basta - 

DAVID J. MALAN: OK. Buono, si può buttare via la metà sinistra. 

JENNIFER: - scegliere questo. 

DAVID J. MALAN: E la destra. 

JENNIFER: Già. 

DAVID J. MALAN: Quindi, anche se è difficile di vedere, forse, quando c'è solo 7 porte, pensare, ora, la consistenza del algoritmo appena applicato. Nel caso precedente, l'avete fatto fortunato, che era fantastico. Ma hai fatto usare una euristica, Direi. Hai usato una sorta di tuo istinto, e saperlo allineati, se è abbastanza piccola all'inizio, ovviamente, abbiamo avuto modo di andare più a destra. Ma in un certo senso, è stato fortunato, perché forse questo era il numero 100, e forse 50 era più al centro. Forse 50 era ancora qui. 

Ma quello che ha fatto un po 'diverso questa volta è stato, hai fatto la stessa cosa ancora e ancora. E direi che quello che hai appena ha, seppur influenzato dal telefono esempio libro, è qualcosa di molto più algoritmico, e molto meno speciale carter. Molto meno istintiva. Così, alla fine della giornata, come sarebbe descrivi l'efficienza del primo algoritmo, dove si è andato sinistra a destra, rispetto al secondo algoritmo qui? 

JENNIFER: questo dovrebbe, come, forse dimezzare il tempo, o anche di più, sì. 

DAVID J. MALAN: OK, forse anche di più. Cerchiamo di spingere un po 'più difficile su questo. Ciò che davvero, se continuiamo questo logica, abbiamo sicuramente dimezzato il tempo di esecuzione con questo secondo algoritmo gettando via la metà del numeri, ma quello che abbiamo fatto sul prossimo iterazione, quando Jennifer ha rivelato il secondo numero? 

Abbiamo dimezzato il numero di porte di nuovo. E allora che cosa abbiamo fatto dopo che, se c'erano più porte con cui giocare? Vorremmo dimezzare loro, e di nuovo, e ancora, e ancora. E questo era proprio come voi ragazzi tutto in piedi fino alla prima settimana di classe, la metà di voi seduti, la metà di voi seduti, la metà di voi seduti, fino a quando uno solitario anima era in piedi. E abbiamo detto che il tempo di esecuzione di che, il numero di passi impiegato era sull'ordine di che cosa? 

SPEAKER 1: [incomprensibile] 

DAVID J. MALAN: Quindi log base 2 di n, o solo più semplicemente, log di n. Quindi qualcosa logaritmica. E il grafico non era una linea retta che appena sempre peggio, è stato questa curva interessante che non ha fatto ottenere così male nel tempo. Quindi cerchiamo di tenere a questa idea. Ringraziamo Jennifer. Grazie mille per essere venuto in su. E, un secondo. Nessun lampade da tavolo oggi, ma noi non avere CS50 palline antistress. 

JENNIFER: Yay. 

DAVID J. MALAN: Va bene, ecco. Grazie per incorrere voi lo stress qui. D'accordo. Quindi vediamo se possiamo non ora formalizzare questo un po 'di più. Così ancora una volta, quello che abbiamo appena fatto è stato essenzialmente la stessa cosa, come abbiamo fatto in quella prima settimana. Ma piuttosto che finiscono con un semplice lineare algoritmo, che abbiamo dipinti un in precedenza come tale retta, per cui, se abbiamo messo più di una porta per lo schermo, poi Jennifer sarebbe hanno dovuto cercare, potenzialmente, più dietro una porta. Se mettiamo altre due porte, che potrebbe avere di guardare dietro altre due porte. 

E così, c'era questo lineare rapporto tra la dimensione della problema, diciamo, l'asse x, e la quantità di tempo necessario per risolvere il y. Ma il quadro che stavo alludendo in precedenza era presente linea verde. Verde volutamente, perché Mi sembrava meglio. In teoria, l'algoritmo, quando abbiamo fatto con la rubrica, quando abbiamo fatto con voi ragazzi contare l'altro, e nel secondo caso, quando Jennifer basta lo ha fatto qui, era sorta di decisamente migliore. Perché non è stato solo due volte più veloce. Non è stato addirittura quattro volte più veloce. E 'stato del tutto dipende da ciò che il dimensioni dell'input era, per quante passi che in ultima analisi ha preso. 

E così questa semplice idea che tutti abbiamo preso per scontato con la rubrica telefonica, può essere applicato similmente a qualcosa di simile a questo. E questo potrebbe essere più casualmente noto come, come si potrebbe immaginare, dividere e conquistare. Non diversamente da quello che abbiamo fatto, naturalmente, con l'elenco telefonico. 

Ma lo pseudocodice, richiamo, era questo. Quindi non lo faremo di nuovo, a meno di ricordare che la prima settimana, tutti noi si alzò e poi la metà di voi seduti, la metà dei si sedette, la metà di voi si sedette. Questo algoritmo è stato implementato in un po 'un modo barare, in questo, è stato non solo uno dei me conteggio, fondamentalmente, più efficiente. In quel caso, stavo facendo leva una risorsa secondaria. Una specie, più CPU, più cervelli, più persone intelligenti nel stanza stavano aiutando a ottenere da qualcosa lineare a qualcosa logaritmica, da qualcosa rosso a qualcosa di verde. 

Ma in questo caso, solo può Jennifer migliorare sostanzialmente sulla prestazioni del suo primo algoritmo da, ancora una volta, solo a pensarci un po 'più difficile. E ora, quando arriva il momento di implementare queste cose, cercare di capire quali linee di codice si può scrivere come che è possibile ripetere di nuovo, e ancora, e ancora, una sorta di in maniera ciclica. Perché tu non hai intenzione di avere il lusso, come Jennifer ha fatto in un primo momento, a basta avere un sacco di se e dire: hmm, se questo primo numero è 4, mi permetta di saltare tutta la strada fino alla fine. Ooh, se quel numero è troppo grande, mi permetta di spostare arbitrariamente indietro al secondo elemento. Troverete che si sta andando ad essere molto più difficile da formalizzare ciò che noi umani dare per scontato come molto ragionevole euristica, ma un computer è solo intenzione di fare quello che gli si dice di fare. 

Ora questo è molto interessante implicazioni. Questo grafico è una sorta di significato per ordinare di sopraffare visivamente, ma preavviso, dove è la linea retta in questo grafico? Dove si trova il grafico lineare che noi chiamiamo N? Beh, è ​​una sorta di verso la parte inferiore di questo quadro, giusto? Quindi tutto quello che abbiamo fatto è che abbiamo una sorta di zoom out per l'asse x e l' asse y per cercare di ottenere un senso di ciò che altri tipi di curve assomigliano. 

E le specifiche della matematica espressioni oggi non importa così molto, a meno di notare che c'è un sacco di algoritmi che sono molto peggiori di qualcosa che è lineare. Anzi, n cubetti sembra piuttosto male. 2 al n sembra piuttosto male. n quadrato sembra piuttosto male. E vedremo che alcuni di quelli potrebbe essere in realtà di oggi. E log n non si sente così male, ma meglio che n è log in base 2 di n. Ma si sa, sarebbe stato anche più sorprendente se Jennifer, o se vogliamo, che la prima settimana, si era messo a qualcosa che è log di registro di n. 

Quindi, in altre parole, c'è questo intero gamma di possibili soluzioni a problemi, ma anche qui, avviso quello che sta per accadere. Quando ho zoom out, che di queste curve sta per dimostrare di essere l'assoluto peggio di quelli sullo schermo adesso? Così n cubetti sembra piuttosto male in questo momento. Ma se lo zoom indietro e vedere di più del x e l'asse y, che sta per dominare in definitiva? Quindi risulta in realtà che 2 alla n, e si può capirlo solo da collegando in qualche sempre più grande numeri, e vedrai che 2 alla n, in effetti, diventa più grande molto più veloce. Se davvero lo zoom indietro, a 2 al algoritmo n schifo assolutamente. Insomma si tratta di andare a prendere un po 'di tempo per la computer a sfornare attraverso. 

Ma si vedrà nel tempo, soprattutto con i futuri set di problema e anche progetti finali, sono i tuoi dati insieme diventa grande, va bene? Anche nella prima versione di Facebook, come il numero di amici, e la numero di utenti registrati ha ottenuto grande, è possibile ordinare di telefono dentro e realizzare qualcosa con ricerca lineare, o un semplice smistamento algoritmo, come vedremo oggi. Devi iniziare a pensare più duro e più difficile di questi problemi. E i tipi di problemi posti come Facebook e Google, e Microsoft, e gli altri lavorano è esattamente questi sorta di grande tipo di dati di domande sempre più in questi giorni. 

D'accordo. Quindi il successo di Jennifer in quel secondo algoritmo, francamente, ha fatto incredibilmente bene la prima volta, ma ti permette di scriverlo come la fortuna in modo che si possono rendere questo punto. Nel secondo caso, si leva un algoritmo che ripete ancora e di nuovo, ma lei ha preso per scontato un certo presupposto che abbiamo permesso , ma lei sfruttata qualche dettaglio il seconda volta che lei non ha avuto il prima volta. Che era che cosa? 

Che l'elenco è stato risolto. Quindi, non appena la lista è stato risolto, abbiamo sostengono che Jennifer è stata in grado di fare fondamentalmente meglio. 7 porte, sì, non è poi così interessante, ma suppongo che siamo 7 milioni di porte. Log di n è sicuramente per eseguire molto, molto più veloce nel lungo periodo. Ma lei doveva avere il Porte Ordina per lei. Ora, mi sono preso la libertà di fare quello anticipatamente sullo schermo del computer qui, ma supponiamo che Jennifer doveva farlo se stessa? Supponiamo che le porte in questione dati rappresentati in un database, o amici iscritti per Facebook, o le pagine web su internet che vari siti web potrebbe essere necessario per indice o ricerca con. 

Supponiamo che si è appena conclusa a dati grezzi impostato e si è lasciata a voi, o per Jennifer farlo ordinamento? Che, anzi, richiede che noi rispondiamo la questione, così, quanto tempo avrebbe preso Jennifer, o anche me, per ordinare quei numeri in anticipo così che avrebbe potuto approfittare di questo? Giusto? Poiché l'implicazione, naturalmente, è se mi ci vuole un po 'di tempo per ordinare i numeri, che il diavolo se ne frega che si riesce a trovare un numero come 50 così in fretta, come nel caso di Jennifer, se abbiamo più di travolto la quantità di tempo totale ha preso di classificare le cose in anticipo? 

Quindi cerchiamo di vedere se non possiamo la dipingere il quadro qui. Ho un sacco di più lo stress palle, se questo aiuta rompere il ghiaccio qui. E se non ti dispiace, abbiamo bisogno di sette volontari - su, OK. Wow. Quindi non dobbiamo spendere su lampade da tavolo, a quanto pare. D'accordo. Così come su voi due davanti. Che ne dici di due ragazzi nella schiena. Ecco, questo è quattro. Come su di te di fronte cinque, sei e sette. Proprio lì. Il tuo amico ti sta sottolineando, in modo da ottenere il premio. 

D'accordo. Andiamo su. E perché non abbiamo voi ragazzi Vieni qui. Io vado a dare ciascuno un numero. E andare avanti e organizzare voi stessi identico a ciò che è rappresentata sullo schermo. 

[Interponendo VOCI] 

DAVID J. MALAN: Oop, mi dispiace. Bug. D'accordo. Bene, ci siamo. Numero cinque. Numero sei. Uno, due, tre, quattro, cinque, sei, sette. Oh, questo è imbarazzante. 

SPEAKER 2: Prendo un -. 

DAVID J. MALAN: Buon affare. D'accordo. Grazie per aver partecipato. 

[Applausi] 

OK. D'accordo. Quindi abbiamo quattro, due, sei, uno, tre, sette, cinque. Perfetto così abbiamo sette volontari qui che sono uguale alla larghezza del array che stiamo giocando con la precedente. E ho scelto sette per ragioni che sarà solo conveniente in un po '. E ho intenzione di proporre prima che siamo impegnati a risolvere questi sette volontari. Se vuoi, in primo luogo, per dire ciao però. Dal momento che questo sta andando essere un scomode diversi minuti. Presentatevi. 

GRACE: Ciao, sono Grazia. Sono al secondo anno in Leverett House. 

BRANSON: Ciao. Sono Branson. Io sono una matricola in Weld. 

GABE: Ciao. Sono Gabe. Sono una junior a Cabot. 

NEIL: Sono Neil. Sono una matricola a Matthews. 

JASON: Sono Jason. Io sono una matricola in Greenough. 

MIKE: Io sono Mike. Io sono una matricola in Grays. 

JESS: io sono Jess. Sono al secondo anno in Leverett. 

DAVID J. MALAN: Eccellente. D'accordo. Bene, grazie a tutti i nostri volontari qui finora. E la sfida a portata di mano ora sta andando di essere a ordinare di questi ragazzi, ma poi stiamo andando ad avere per pensare un po ' difficile di quanto siamo efficienti realtà loro ordinato. Quindi cerchiamo di prima provare questo. Voi ragazzi potete vedere i rispettivi numeri di semplicemente posizionando intorno agli angoli. Andare avanti e prendere un paio di secondi, e sorta voi stessi dal più piccolo al sinistra a grande sulla destra. Go. 

OK. Buono. E 'stato davvero maledettamente veloce. Ora qualcuno qui, che cosa era l'algoritmo che questi ragazzi applicate? 

SPEAKER 1: dal numero minore al maggiore. 

DAVID J. MALAN: OK. Piccolo al più grande è in realtà una sorta di obiettivo, ma non sono sicuro che è davvero un algoritmo. Piccolo al più grande non dice Mi passo per passo cosa fare. Sì? 

SPEAKER 1: [incomprensibile] 

DAVID J. MALAN: OK. Quindi, se vedete una persona minore di il tuo numero, per poi passare a loro destra. Ecco, questo è ormai sempre più espressiva, più simile a un algoritmo, perché si può dire, se questo, poi quello. Così abbiamo un qualche tipo di costrutto condizionale. E questi ragazzi sembrano fare che pochi volte, perché alcuni di voi sono trasferito un po ' di una distanza. Quindi c'era presumibilmente una sorta di looping succedendo nelle loro menti. 

Ma cerchiamo di formalizzare tale. Se voi ragazzi poteste reimpostare indietro a questo accordo. Vediamo se non siamo in grado di formalizzare questo un po ', e poi fare la domanda, appena come efficiente è questo? Naturalmente, quando lo facciamo più lentamente, sta andando a sentire come bene di un algoritmo, ma vediamo se possiamo mettere le dita sui punti precisi. 

Quindi voi due ragazzi sono quattro e due. Oppure è nell'ordine corretto o scorretto? Ovviamente non corretta. Così ci siamo scambiati. Ora ho intenzione di farsi da parte qui e dire, 4-6. Siete corretto o scorretto? 

GABE: Corretto. 

DAVID J. MALAN: Corretto. Sei mesi e un? Nope. Scambia. Ecco, questo è due swap. Sei e tre? Nope. Scambia. Sei e sette? Sembra buono. Sette e cinque? 

JESS: [incomprensibile] 

DAVID J. MALAN: OK, scambiare. E ordinati. D'accordo. Così, ovviamente no, giusto? Quindi non c'era più in corso. Ma, in effetti, questi ragazzi, anche solo istintivamente. mantenuto in movimento. Essi non solo smettere, una volta che corretto un problema. Così. Anzi, ho intenzione di avere a fare la stessa cosa. Ho intenzione di fare per ordinare di riavvolgere indietro per l'inizio di questo problema, o l'inizio di questa matrice di popolo, cominciamo a chiamarli. 

E ora che cosa dovrebbe il mio algoritmo al secondo passaggio sarà? 

SPEAKER 1: Stessa cosa. 

DAVID J. MALAN: Stessa cosa. E questo, sto iniziando a piacermi, giusto? Non appena si può trovare se stessi facendo la stessa cosa più e più volte, questo è diventando più simile a un algoritmo, e l'istinto meno umano. 

Così ora, ci risiamo. Due e quattro? No. Quattro e un? Ah, vi è stato effettivamente un po 'di lavoro ancora da fare. Per e tre? Buono. Quattro e sei? Sei e cinque? Sei e sette? OK, ora, fatto. OK, no. Devo tornare indietro. 

Così ora, ancora una volta, stiamo facendo questo un po 'più deliberatamente. E ora, c'è solo un cervello esecuzione di questo algoritmo. Una CPU, se si vuole. E, francamente, questa è l'unica risorsa stiamo andando ad avere accesso. E una volta che noi torniamo a una tastiera e di avere qualcosa come C a nostra disposizione, stiamo solo scrivendo un programma che si può fare una cosa alla volta. Considerando che, a questi ragazzi un momento fa, abbiamo leveraged loro intelligenza collettiva come voi avete fatto in settimana zero. Quindi cerchiamo di continuare a fare questo. 

Due e uno. Due e tre. Tre e quattro. Quattro e cinque. Cinque e sei. Sei e sette. Fatto? Così sono io, ma fammi giocare l'avvocato del diavolo. Faccio, il tipo di computer è che ha appena fatto un passaggio attraverso questa serie di persone, sanno che ho finito? 

SPEAKER 1: No. 

DAVID J. MALAN: Allora perché? Che cosa avrei dovuto fare per Concludo con decisione che mi sono fatto? Probabilmente uno più pass. Giusto? Perché tutto quello che so da quello precedente passaggio è che ho corretto un errore. E questo significa, forse c'è ancora un altro errore che ho bisogno di correggere. Quindi posso solo essere sicuro di riavvolgimento e quindi il controllo, 1-2, due e tre, tre e quattro, quattro e cinque, cinque e sei, sei e sette. OK, ora ho fatto nessun lavoro. 

Posso certamente ricordare che ho fatto non lavorare con qualcosa di simile a una variabile, come un int. Chiamatelo swap, e se gli swap è 0 volta ho arrivare qui, e ha cominciato a 0, allora Sarei stupido andare avanti avanti e indietro, controllando di nuovo, e ancora, e ancora, giusto? Perché ti trovi in ​​difficoltà in qualche tipo di ciclo infinito. Quindi, non appena c'è 0 swap, possiamo affermare che questa algoritmo è davvero completa. 

Ora, mettiamo un nome su questo. L'algoritmo che vi propongo che abbiamo appena implementata è una cosa chiamata bolla liste, nota come tale nel senso che i numeri che sono più grandi di tipo bolla la loro strada fino alla cima, o fino alla fine della matrice di numeri. Ma quanto efficiente fosse questo algoritmo? Quanti passi ho dovuto fisicamente prendere, per esempio, di ordinare questi sette gli esseri umani? 

Quattro o cinque? OK, troppi è in definitiva andando ad essere la risposta. Ma anche allora, il numero specifico non è così interessante. Cerchiamo di generalizzare come n. Quindi, se avessi n persone qui, e loro erano, sorta di, in ordine casuale al a cominciare, in questo ordine originale. Beh, quanti passi ho dovuto per prendere il primo passo? Era uno, due, tre, quattro, cinque, sei, e sono sette persone, in modo da questo è sette, sei -, così che è n meno uno passi la prima volta. 

Ora, quanti passi ho dovuto prendere quando ho riavvolto? Beh, potremmo effettivamente il doppio che se volevamo, ma per ora, sono solo andando a dire, va bene, un altro n meno 1. Così il n meno 1 sta per arrivare fastidioso per tenere traccia di, quindi cerchiamo di basta arrotondare leggermente. Così 2n passi. Quindi 14 passi, prendere o lasciare. 

Quante volte mi prendo un passo la prossima volta? Beh, è ​​3n. davvero. E ora, nel peggiore dei casi, per esempio, quante volte avrei dovuto andato avanti e indietro, avanti e indietro, l'esecuzione di questo algoritmo, scambiando persone su ogni passaggio, approssimativamente? In realtà è N al quadrato, giusto? 

Perché nel peggiore dei casi, è possibile tipo di pensare a questo modo intuitivo, anche se potrebbe richiedere un po ' po 'di tempo per affondare dentro Nel peggiore dei casi, quali sarebbero questi sette persone hanno guardato come, in termini contrattuali del loro numero? Completamente indietro, giusto? E proprio per simulare che, ciò che è stato ancora una volta il suo nome? 

MIKE: Mike. 

DAVID J. MALAN: Mike? OK, Mike, si può solo unirsi a me nel corso qui per un solo secondo? In realtà, no. Mi dispiace Mike, rewind andiamo. Qual è il tuo nome? 

NEIL: Neil. 

DAVID J. MALAN: Neil. OK, Neil, tu vieni con me, se non ti dispiace. Quindi ho intenzione di proporre, solo per semplicità, che Neil è ora nella sua peggiore dei casi possibili. Ma ricordo come ho implementato il mio algoritmo. Sto confrontando, confronto, confronto, confronto, confronto, oh. Ora questi ragazzi sono fuori di ordine, in modo da posso correggere. Allora ragazzi swap. Ma considerare ora, quanto più lontano Neil non deve andare? Grosso n. Sai, non è in realtà n. E 'come, n meno 1, ma mi sto infastidito tenendo traccia del piccolo numero, quindi cerchiamo di appena lo chiamano n. 

Quindi, se Neil si sposta di un passo al massimo ogni tempo, e per spostare Neil un passo, Devo fare questo passo davvero noioso avanti e indietro, questo è approssimativamente In questo modo, n passi, per un totale di n volte, perché sta andando a prendere me che molti passi per ottenere Neil tutti il modo per cui appartiene. Per non parlare di tutti gli altri se voi ragazzi sono stati tutti mis-ordinato pure. 

Quindi chiamiamolo bubble sort n quadrato. Il tempo di esecuzione di questo algoritmo, la prestazioni di questo algoritmo, la efficienza di questo algoritmo, avremo solo descrivere più generalmente come n al quadrato. Il che è bello, perché ho potuto fare l' stesso esempio con otto persone, nove persone, un milione di persone, e che risposta non sta per cambiare. 

Quindi, se voi ragazzi non mi dispiacerebbe, diamo vi ripristinare al punto di partenza. E proviamo altri due approcci e vedere se non possiamo fare fondamentalmente meglio di questo. Così questa volta, ho intenzione di proporre una sorta di algoritmo diverso. Questo è stato molto intelligente di noi l'ultima volta, e voi ragazzi erano proprio per avere la giusti istinti di solo tipo di scambiare due a due. Ma se volevo davvero avvicinarsi a questo semplicemente, e il mio obiettivo è quello di spostare tutti i piccoli numeri in questo modo, e spingere tutti i grandi numeri che A proposito, perché non lo faccio e basta che nel più ingenuo modo possibile e vedere se io può fare meglio di quello che era un piuttosto complesso algoritmo? 

Quindi vediamo. Quattro è un numero abbastanza piccolo, quindi sono intenzione di lasciarvi vi momento. Ooh, il numero due è ancora meglio. Quindi, si può solo fare un passo avanti per un momento? Questo è attualmente il mio piccolo numerata candidato, e ho intenzione di ricordare che con, tipo, una variabile. Ma ho intenzione di mantenere il controllo. C'è qualcuno di cui numero è più piccolo? Sei, no. Oh, c'è di nuovo Neil. 

Quindi ho intenzione di spingere indietro sorta di concettualmente. Neil si farà avanti. E ora, la variabile che sto usando per tenere traccia di chi ha il più piccolo numero viene aggiornato per contenere Posizione di Neil. Bene, vediamo. Tre, sette, cinque. OK, so che Neil era il più piccolo. Qual è la cosa più semplice per me di fare ora? Non ho intenzione di sprecare il mio tempo da solo ribollimento Neil un posto a sinistra. Perché non appena messo Neil dove ha appartiene, che è ovviamente dove? 

Tutto il percorso all'inizio. Così Neil, vieni con me. E che cosa era di nuovo il tuo nome? 

GRACE: Grazia. 

DAVID J. MALAN: Grazia. OK. Così Grazia, purtroppo, si è tipo di intralcio. Quindi, come possiamo risolvere questo problema? Giusto? Se questo è un array, non c'è solo sette posizioni. Ricordiamo che, con Rob, abbiamo parlato dichiarando le età, e abbiamo avuto solo un numero finito di età? Stessa idea qui. Abbiamo solo un numero finito di int. Grazia è una specie di nel nostro modo, così come possiamo risolvere? 

Il modo più semplice è come, Grazia, mi dispiace. Stai andando ad avere per andare oltre c'è modo che possiamo fare spazio. Ora, se si pensa a questo, forse abbiamo appena fatto peggiorare il problema. E forse abbiamo fatto, perché ciò che se Grazia erano nel posto giusto? Ma sappiamo che non lo è, perché in caso contrario, sarebbe stata in piedi in avanti invece di Neil in questo momento, giusto? Abbiamo già fatto il check-out il suo numero. 

D'accordo. Così ora, Neil è al posto giusto, e Posso fare una leggera ottimizzazione. Per il prossimo minuto, ho intenzione di ignorare Neil tutti insieme, in modo da non sprecare il suo tempo, o accidentalmente lo scambiare il posto sbagliato. Così ora, come faccio a trovare il prossimo elemento che è più piccolo? Due. Questo è un buon numero, se si vuole fare un passo avanti e Mi ricorderò di te. Sei, non va bene. Quattro, tre, sette, cinque, non va bene. Quindi lasciate che muovo a il tuo posto giusto. E siamo solo stati fortunati questa volta. 

Ora, ho intenzione di ignorare questi due ragazzi, e ora fare un altro passare attraverso questo. Sei, che un numero abbastanza piccolo. Andiamo avanti. Oh, mi dispiace. Numero di Grace è meglio, così passo su avanti. Quattro. Siamo spiacenti, Grazia. Tornarci. Numero tre è meglio. Sette. Cinque. E ora che cosa è che ti chiami? 

JASON: Jason. 

DAVID J. MALAN: Jason. Così Jason è ora il più piccolo elemento che ho selezionato. Dove sta andando andare? Allora, dove sei è. E il tuo nome è nuovo? 

GABE: Gabe. 

DAVID J. MALAN: Gabe. Gabe è in mezzo. Qual è la cosa più facile da fare? Scambia questi due ragazzi e continuare. Così ora vediamo. Chi è il più piccolo? Quattro. Lasciami solo tipo di imbroglio. Cinque sta per essere il più piccolo. Trovo prossimo, se si vuole fare un passo in avanti, che cosa devo fare con questi ragazzi, con Gabe? Swap di nuovo. Così ora, ancora un po 'in ordine. Ho trovato Gabe per essere il più piccolo, in modo da Lo Pop Out, muovo ragazzi sopra. E fatto. 

Così risposta è la stessa. Il risultato finale è lo stesso. Quale di questi due algoritmi è meglio? Il secondo, ho sentito. Perché? 

SPEAKER 3: E 'n passi [incomprensibile]. 

DAVID J. MALAN: E 'n passi in più. Interessante. Quindi è però? Così come ho trovato il elemento più piccolo? Quanti passi ho dovuto prendere il trovare l'elemento più piccolo? Ho dato un'occhiata in fondo alla fine, giusto? Perché in quel caso peggiore, quello che Neil se fosse qui? Quindi solo trovare il più piccolo elemento me n passi, o n meno 1 prende. Ma, OK. Quindi fissare Neil. Ricordate che, un minuto o così fa. 

Ma come ho fatto a trovare il prossimo elemento più piccolo? E 'n meno 1, meno 2 o n davvero, dal numero di passi. Quindi OK. Così ho fatto N meno 2. D'accordo. In modo che si sente un po 'meglio. D'accordo. Quanti passi la prossima volta per trovare il numero tre? Così n meno 4. Quindi è in diminuzione, uno in meno calpestare ogni iterazione. Quindi questo fa sentire meglio, giusto? Se l'ultima volta è stato circa N volte n, questa volta è n meno 1, più n meno 2, più n meno 3, più n meno 4, punti, puntini, puntini. Ma se vi ricordate dal tuo liceo libri di testo, il piccolo trucchi pagina al fondo che ha formule, se si sommano questa serie di numeri, qual è il numero totale di passi sarà che prendo qui? 

Questo è uno di quelli, come, n meno 1, n volte, diviso per 2. Quindi, fammi vedere se riesco a tirare questo per un momento. E di nuovo, io sono una specie di arrotondamento alcuni numeri solo per mantenere la nostra vita semplice, ma se ricordo bene, è qualcosa di simile, se Faccio N meno 1 cose, allora n meno 2, quindi n meno 3, e 'approssimativamente qualcosa di simile su 2, e se io moltiplicare questo fuori, questo è effettivamente quadrato n. Che non si sente troppo bene. n minus n sopra 2. 

Ma ecco la cosa. In informatica, quando i problemi inizia a farsi interessante è quando n diventa veramente grande. E quando n diventa molto grande, di cui questi valori sta per dominare tutto degli altri? E 'una specie di n al quadrato, giusto? Sì, dividendo per 2 è piuttosto buona. Ma se si parla di miliardi di pezzi di dati, o migliaia di miliardi di pezzi di dati, ok, quindi si è due volte più veloce. Ma chi se ne frega se quel numero grande, se questo fattore è quello che ottiene grande e più grande. E sicuramente, ha più di una differenza di questo ragazzo. Così, anche se voi siete giusto, il secondo algoritmo, che chiameremo ordinamento per selezione, è, nel mondo reale, un po 'più veloce potenzialmente, perché io sono prendendo sempre meno passaggi ogni volta. 

Non è davvero fondamentalmente più veloce. Perché se in realtà giochiamo questo per grandi valori di n, a fine il giorno, per n abbastanza grande, è ancora andando a sentire piuttosto lento. Beh, mi permetta di prendere una ultimo passaggio a questo. Questo è quello che io chiamerei selection sort. Can you guys azzerare voi per l'ultima volta? E in questo ultimo caso, io vado di proporre qualcosa chiamato insertion sort. Insertion sort essere, concettualmente, un po 'diverso. 

Piuttosto che andare avanti e indietro e selezionando l'elemento più piccolo, io sono solo andando a trattare con ciascuno di questi ragazzi come loro che incontro, e inserisco li nella loro corretta posizione. Quindi ho solo intenzione di iniziare con Grazia, e vedo che lei è il numero quattro. Da dove viene il numero quattro appartiene? Non ho iniziato smistamento nulla, così Grazia ottiene di rimanere lì. E ora ho intenzione di rivendicare, se si potesse fare un passo a destra, questo la mia lista ordinata, questo è il mio indifferenziati lista rimanente. Così ora ho intenzione di procedere prossimo, e qual è il tuo nome? 

: Branson. 

DAVID J. MALAN: Branson. Così Branson è il numero due. Quindi ho intenzione di portarvi fuori per un momento. E ora, dove si appartiene in questo array? Quindi, per il diritto di grazia. Quindi, di nuovo, siamo un po 'fare Grazia fare un sacco di lavoro qui. Dove ci metteremo? Quindi stiamo andando a scivolare voi la a sinistra, ed inserire Branson lì. Ma ora io sostengo che avete finito. Ma notate, non sto usando più spazio. E 'ancora due elementi qui, 5 qui. Dimensione totale dell'array è 7, quindi sono Non barare, va bene? 

Così ora abbiamo, con Gabe qui, il numero sei, dove appartieni? Hai avuto ancora fortuna. Così si arriva a stare lì. Basta prendere un leggero passo a destra solo per rendere chiaro che si sta ordinati. E ora abbiamo Neil nuovo, numero uno, dove vai? E adesso è qui che inizieremo a vedere che questo algoritmo, se su prima sguardo, si sente abbastanza intelligente, guardare quello che sta per accadere. Se si potesse fare un passo avanti. 

Dove vogliamo mettere Neil? Così, ovviamente qui, così come arriviamo Neil lì? Facciamo questo passo-passo. Gabe, dove devi andare? Yep, in modo da prendere un grande passo, o di due mezze misure per rendere un passo in là. Grazia, dove si va? Buono. Così un altro passo. E, infine, Branson? Un altro passo. E ora possiamo mettere Neil in posizione. 

Così ora, continuare questa logica. Anche se noi non stiamo spostando Neil oltre, e oltre, e oltre, per metterlo dove va, nel caso peggiore, la prossimo numero che possiamo incontrare potuto sia il numero, diciamo, c'era un numero zero, allora stiamo andando a spostare tutti questi ragazzi. Supponiamo che ci sia un numero negativo uno, allora dobbiamo spostare tutti questi ragazzi. Quindi siamo davvero solo tipo di capovolgimento il problema in giro, in modo tale che siamo trasferendo la spesa dal processo di selezione così l'inserimento processo, in modo che voi ragazzi ha appena avuto per spostare approssimativamente N meno qualcosa numero di passi. E che il numero di passi è solo andare ad aumentare, come posso selezionare più numeri, se devo continuare a spintoni voi ragazzi indietro, e indietro, e indietro. 

Quindi, la cosa triste ora è tutto questo algoritmi sono n al quadrato. Andiamo avanti e grazie a questi ragazzi, e visualizzare questi un po ' diversamente. Molto ben fatto. 

[Applausi] 

D'accordo. Ci si va. Grazie per - 

BRANSON: [incomprensibile] mantenere i numeri. 

DAVID J. MALAN: No, si può mantenere i numeri pure. D'accordo. Ben fatto. D'accordo. Così vediamo se ora non possiamo riassumere più rapidamente, e più visivamente, esattamente quello che è appena successo qui come segue. Ho intenzione di andare avanti e tirare su Firefox. Ci colleghiamo questa dimostrazione sul sito web del corso. Java è un po 'fastidioso per ottenere lavoro in alcuni browser in questi giorni. Quindi, se non giocate con questo a casa, rendi conto che potrebbe essere necessario utilizzare Firefox per farlo funzionare. E che cosa ho intenzione di fare con questo dimostrazione è la seguente. 

In fondo, ho un sacco di opzioni di menu, tra un inizio e una arresto. Inoltre, per inciso, sembra che ci sia un bug in questi programmi, per cui si non può effettivamente vedere l'avvio o di arresto a meno che non si tiene premuto il tasto Comando o Alt plus e lo zoom in, che curiosamente si mostra più pulsanti. Quindi, solo FYI se si gioca con questo a casa. Ora ho intenzione di fare clic su Avvia in appena un momento, dopo aver specificato un ritardo, come, a 200 millesimi di secondo qui, solo così possiamo vedere cosa succede. 

Quindi io sostengo che questa è una visualizzazione del primo algoritmo questi ragazzi hanno fatto, bubble sort, in base al quale ci siamo scambiati le persone pair-wise. L'intuizione fondamentale di questa visualizzazione è che l'altezza delle barre rappresenta la dimensione del numero. Così la più alta è la barra, grande il numero. Shorter al bar, più piccolo è il numero. E se ci fate caso, stiamo attraversando la prima iterazione di questo algoritmo, scambiando i numeri grandi e piccoli, in modo che il piccolo numero viene prima e il grande numero va a destra. 

E non appena si ottiene la fine della matrice di di molti più numeri di sette, siamo intenzione di andare di nuovo all'inizio. E anticipare questo. All'estrema sinistra, quel piccolo ragazzo sta andando per scambiare di lato, e questo processo si ripete. Ora questa visualizzazione diventa rapidamente noioso, così mi permetta di andare avanti e di fermo esso, cambiare il ritardo qualcosa di molto più veloce solo per ottenere ora, un'idea di questo algoritmo. 

Così, anche se ho accelerato in su, questo è come aggiornare il mio processore, l'acquisto di un nuovo computer. Non ho cambiato radicalmente la mia algoritmo, ma si può davvero vedere di più chiaramente che con gli esseri umani, che il grande numeri sono zampillante per la parte superiore, ed i piccoli numeri sono gorgogliare fino al fondo. E adesso questa cosa qui allineati. E per inciso, nelle piazze, non c'è solo alcuni contabilità lì a aiutano a contare quanti confronti, o quante swap hanno effettivamente stato fatto. 

Beh, proviamo uno di gli altri che abbiamo visto. Lasciatemi clicco su bubble sort qui, e mi permetta di scegliere, e questa pagina web intera è un po 'bacato. Consente di accettare il rischio ed eseguirlo nuovamente. Ecco fatto. Allora, facciamo selection sort. Io non so perché il menu appare laggiù. Facciamo lo zoom per rimediare bug, cambiare questo a 50. Ah, facciamo effettivamente fare più velocemente. Cinque millisecondi o giù di lì, e iniziare. 

Quindi questo è il selection sort. Così ancora una volta, pensare a quello che abbiamo ha fatto con gli umani qui. Siamo passati attraverso l'array e selezionato l'elemento più piccolo di nuovo, e ancora, e ancora. Ora io affermo che era ancora piuttosto male. E 'stato ancora n quadrato, prendere o lasciare, ma era, nel mondo reale, un po ' più veloce, perché ero davvero prendendo leggermente meno passaggi ogni volta. Ma stiamo parlando solo quello? Forse 40 o giù di barre di qui? Non stiamo parlando di 40 milioni di euro. Quindi non è del tutto chiaro per me che era in effetti un guadagno significativo. 

Vorrei ora tornare indietro e cambiare il nostro terzo algoritmo, che è stato selezionare insertion sort. E ora è davvero bacato perché il Menu realtà non dovrebbe essere lì. Così ora ci scorrere indietro fino qui e iniziare questo algoritmo. Whoop, start e stop. Quindi questo tipo di ha un modello piuttosto ad essa, per cui siamo di nuovo inserendo gli umani, o in questo caso, le barre nella la loro posizione appropriata. Ed è già fatto prima Mi voltai. Ma anche questa, in teoria, è ancora n quadrato. 

Così vediamo se non siamo in grado di riassumere questi come segue. Ho intenzione di andare avanti e solo per dare noi una sorta di modo comune di parlare di queste cose, mi presento solo un po 'di notazione qui. Stai per vedere qualcosa chiamato big O, perché è letteralmente un grande O. E questo è un modo che un computer scienziato o un matematico usa anche per descrivere il tempo di esecuzione di qualche algoritmo. Quanti passi ci si effettivamente prendere? 

Ora ho intenzione di mettere in imbarazzo me stesso con la mia scrittura qui in un attimo. Ma mi permetta di andare avanti e dire che questa sarà la grande O qui. E mi permetta di introdurre un altro simbolo, un omega capitale. Omega sarà il contrario, essenzialmente, di grande O. considerando che la grande O mezzi, nel caso peggiore, quanto tempo potrebbe prendere qualche algoritmo, in termini di n, omega sta per essere quanto tempo si potrebbe prendere nel migliore dei casi. E vedremo che cosa intendiamo per migliore dei casi in un attimo. 

Quindi cerchiamo di iniziare qualcosa di semplice. Vorrei iniziare con una ricerca lineare. Quindi non smistamento. Chiameremo questa ricerca lineare. E ora, fare un po ' tavolo fuori. E ora, nel caso della ricerca lineare, nel peggiore dei casi, il numero di passi è andando a prendere me per trovare una numero di scelta arbitraria? E c'è n porte totali o n numeri totali. Caso peggiore. Quanti passi sto andando ad avere per prendere per trovare il numero 50 in un array di n porte? E perché? Perché potrebbe essere tutto il modo più sulla fine. Così tanto come Jennifer incontrato, il numero 50 era tutta la strada sopra, quindi in il peggior ricerca lineare caso è grande O di n, si dirà. 

E il caso migliore, se si ottiene veramente fortunati? E 'solo andando a fare un passo, o un numero costante di passi. Così si descrivono che, come 1. Quindi questo è abbastanza buono. Ora, cosa succede se abbiamo fatto qualcosa di come ricerca binaria? Ricerca in modo binario, nel peggiore caso, ha preso quanto tempo? 

[Interponendo VOCI] 

DAVID J. MALAN: Quindi, in realtà, ho sentito in un paio di posti. Quindi in realtà è log n, prendere o lasciare, perché come si divide la lista in due ancora, e ancora, e ancora, siamo in grado di trovare, in ultima analisi, il valore, se è lì, ma vi è una cattura. Qual è il presupposto che dobbiamo dare per scontato per la ricerca binaria? Deve essere ordinato. Non è risolto, è possibile dividere la cosa a nuovo e di nuovo a metà, e si può andare a sinistra, e si può andare a destra, e si può andare a destra ea sinistra, ma sei non andare a trovare l'elemento se l'elenco non è ordinato, perché si potrebbe perdere. Perché la tua euristico, per andare a sinistra o di diritto sta per essere viziato se è infatti non ordinati. Quindi c'è una sorta di costo nascosto a utilizzare qualcosa di simile. 

Ora, andiamo nel nostro ordinamento algoritmi non ricerca - Oh, in realtà andiamo in questo vuoto. Ricerca binaria nel migliore dei casi? E 'anche uno se accade solo per essere nel molto centro della matrice, o al centro del libro di telefono. Ora facciamo bubble sort. Quindi, di nuovo, ora stiamo entrando nella specie, non le ricerche. 

Nel peggiore dei casi, quanti passi ci siamo pretesa bubble sort è andare a prendere? n al quadrato. Quindi ho intenzione di disegnare quella. Ooh, la mia scrittura sembra anche peggio quando è previsto che grande. D'accordo. Ecco, questo è n quadrato. E nel caso migliore di bubble sort, quanti passi sta andando a prendere? 1, ho sentito. 

SPEAKER 1: n. 

DAVID J. MALAN: n, ho sentito. 

SPEAKER 1: 2. 

DAVID J. MALAN: 2, ho sentito. Sento 3? D'accordo. Così ho sentito 1, n, 2, ma Riprendiamo a parte almeno il primo di quelli suggerimenti, 1. Non è un cattivo istinto, perché tipo segue un modello qui. Ma se ci vuole solo 1 passo, come nel mondo, ho potuto affermare che l'elenco è ordinato, perché se sto solo permesso di prendere 1 passo, il numero di elementi Potevo controllare per essere sicuri? Beh, solo 1, che significa che c'è n meno 1 elementi che potrebbero essere fuori ordine, e sto solo andando sulla fede dopo guardando 1 elemento che la cosa è ordinato. Quindi 1 non è corretto qui. Così minimamente, quanti devo guardare? 

[Interponendo VOCI] 

DAVID J. MALAN: n meno 1, o in realtà, n, perché ho bisogno di guardare ogni elemento per assicurarsi che non è fuori servizio. Ma ancora una volta, saremo specie di onda nostra mani ai numeri più piccoli e assumono che, come n diventa grande, sono poco interessante comunque. Ecco, questo è bubble sort. E ora, facciamo questi ultimi due. L'ordinamento per selezione, e poi ci fare insertion sort. E poi ci lascerà a bocca menti con qualcosa di molto migliore di tutti questi. D'accordo. 

Che cosa è il caso peggiore in esecuzione momento della selezione sorta? 

SPEAKER 4: n al quadrato. 

DAVID J. MALAN: piazza n, sto sentendo. Ma perché n squadrato, intuitivamente? 

SPEAKER 4: Perché abbiamo appena fatto. 

DAVID J. MALAN: Perché abbiamo appena fatto. OK. Buona risposta. Ma intuitivamente, perché è la selezione tipo n al quadrato? Che cosa abbiamo a che fare ancora e ancora? Abbiamo dovuto tenere la scansione attraverso, sono la più piccola, sei l' più piccolo, sei il più piccolo. E concesso, siamo stati in grado di prendere n passi, allora N meno 1, quindi n meno 2. Ma se si aggiungono quelli di tipo tutto in su, o prendere sul fede che ho aggiunto loro in anticipo, otteniamo circa n quadrato meno alcuni numeri più piccoli. Quindi ho intenzione di chiamare questo quadrato n. Ma con selezione sorta nel migliore caso, quanti passi è andando a prendere me? 

SPEAKER 5: [incomprensibile] 

DAVID J. MALAN: E 'purtroppo ancora n al quadrato, giusto? Perché se sto scegliendo il più piccolo elemento, e abbiamo avuto sette persone qui, So solo che, una volta che ottengo il molto finale, che ho trovato il più piccolo numero, dovunque lui o lei può essere stato. Ma come faccio a trovare il prossimo numero più piccolo? Devo fare un altro passaggio. Quindi nel caso migliore, qual è la ingresso alla selezione sorta? Si tratta di una lista già sorta, il numero uno, numero due, numero tre, numero quattro. Ma io sono un computer. Posso guardare soltanto ad un cosa alla volta. Non posso ordinare di fare un passo indietro come un essere umano e dire, ooh, questo sembra corretto. 

Posso giudicare solo la correttezza in ordinamento per selezione selezionando il numero più piccolo. Ma anche se trovo il numero uno in primo luogo, se io non so niente altro circa gli altri numeri, che non lo faccio, tutto quello che So che sono stato consegnato un array o un insieme di porte dietro le quali sono numeri, l'unico modo che conosco che uno era il più piccolo? Se ho fin qui e mi rendo conto, accidenti, uno era davvero il più piccolo. 

Ma come faccio quindi determinare che due è il prossimo più piccolo? Facendo la stessa inefficienza ancora e ancora. Così alla fine, con insertion sort, come, nel caso peggiore, abbiamo detto si svolge? Anch'esso è n quadrato. E per quanto riguarda il caso migliore? Lasceremo che come un cliffhanger. Ci riempiamo in quel vuoto la prossima volta, ma prima vorrei propongo di fondamentalmente fare meglio di tutti questi, va bene? 

Quindi, pensare di persona ciò che l'inserimento sorta Sarà. Beh, non era molto drammatico, perché io sono l'unico che ha visto il cambiamento. Wow. OK. Quindi qui abbiamo un po ' dimostrazione diversa. Se io zoomare qui, vedrete che il sinistra abbiamo bubble sort, nel mezzo abbiamo ordinamento per selezione, e il l'estrema destra, abbiamo qualcosa che Non ho guardato ancora chiamata merge sort. Ma consideriamo quello che siamo stati facendo qui finora oggi. Quando Jennifer prima volta sul palco, siamo passati attraverso la matrice di numeri ancora, e ancora, con la ricerca lineare, e abbiamo avuto tempo di esecuzione lineare, grande O di n, per così dire. 

Quando noi ora consideriamo la prima settimana di classe, quando avevamo dividere e conquistare, e noi avevamo la rubrica strappo, e Jennifer, e noi collettivamente sfruttato questa intuizione fondamentale, che era quello di ripetere te stesso più e più volte da in qualche modo gettare via, buttare via, buttare via, metà del problema, o generalmente, dividendo un problema a metà, e poi trattare il pezzo più piccolo di il problema come concettualmente equivalente per l'altro, abbiamo in qualche modo fatto fondamentalmente meglio. Ma con bubble sort, con selezione specie, con insertion sort, abbiamo può non tali intuizioni che Jennifer ha fatto. Abbiamo praticamente appena tornati a piedi e via un sacco di volte, e abbiamo cose modificato un po ', lo swapping in questo ordine, forse l'inserimento o la selezione. Ma alla fine della giornata, ho fatto un sacco di camminata goffa avanti e indietro. Non abbiamo davvero qualcosa di leva intelligente come Jennifer ha fatto come dividendo e conquistando. 

Così merge sort, invece, che abbiamo non vedrà fino alla prossima settimana, sta andando di sfruttare l'idea chiave dividendo l'ingresso, e poi dimezzare, e quindi dimezzare, e poi dimezzare. E ad ogni iterazione di tale ciclo, ordinamento la metà sinistra e destra metà, poi la metà sinistra della metà sinistra, e la metà destra della sinistra, poi la metà sinistra della metà destra, e la metà destra della metà destra. E ripetendo più e più volte. 

Così vedrete questo visivamente, ma questo è ciò che ci attende la prossima settimana. E, in generale, quando si pensa un po ' po 'più difficile su tale problema. Abbiamo n quadrato sulla sinistra, n quadrato nel mezzo, e n log N sulla destra. Quindi c'è il tuo vero colpo di scena. Ci vediamo il Lunedi. 

[Applausi]