SPEAKER: Va bene, questo è CS50. Questa è la fine di tre settimane, e se non avete approfittato già, sanno che ci sarà il pranzo questo Venerdì, come al solito, dove si può godere di buona conversazione e cibo a Fire and Ice con alcuni dei CS50 di personale e compagni di classe. Andate a questo URL qui. 

Ora si può ricordare, o si potrebbe presto essere a conoscenza, queste cose qui, che sono riportati alla fine del semestre per molte classi. Il cosiddetto esame blu libri, in cui scrivete le vostre risposte agli esami. Ora ho qui 26 tale libri blu, su ciascuno di essi è scritto un nome, da A a Z. E infatti i nomi sono così semplici, A attraverso Z. E uno dei gli obiettivi a portata di mano oggi sta per essere quello di continuare quello abbiamo iniziato il Lunedi, che non è tanto guardando il codice, ma in realtà guardando idee e di problem solving. Uno degli obiettivi e promesse di questo corso è quello di insegnare a pensare in modo più attenzione, più metodicamente, e per risolvere i problemi più efficiente. E infatti, possiamo farlo davvero senza nemmeno toccare una riga di codice. Così ho un paio di elefanti qui oggi, arancione e blu, se potessimo ottenere un volontario, forse da più indietro del solito. Che ne dite proprio lì, vieni giù. L'obiettivo di cui sta per essere a aiutare più amministrare questo esame qui. Come ti chiami? 

PUBBLICO: Mary Beth. SPEAKER: Mary Beth, vieni su. Mi permetta di ottenere il microfono qui per voi. Piacere di conoscerti. 

PUBBLICO: Piacere di conoscerti. SPEAKER: Va bene, così ho qui i libri blu da A a Z, e ho intenzione di far finta che Ho uno degli studenti, e stanno arrivando in qualche modo casuale alla fine di un blocco esame tre ore così che stanno finendo in qualche ordine semi-casuale come questo. Ora il vostro lavoro in un attimo sta andando essere-- questo è in realtà il modo in cui ottengono trasformato in alla fine di la classe, più probabile. Il tuo lavoro ora sta per essere, piuttosto semplicemente, di ordinare questi libri blu per noi dalla A alla Z. 

PUBBLICO: Oh, questo è andando a prendere per sempre. 

SPEAKER: E guarderemo come si esegue questa operazione, nessuna pressione. PUBBLICO: No, nessuna pressione o nulla. 

SPEAKER: E per il divertimento, mettiamo un timer. 

PUBBLICO: Tanto divertimento, tanto divertimento. 

SPEAKER: Posso tenere il microfono per voi. Va bene, abbiamo appena raddoppiato la nostra velocità. Così, nel frattempo, mi permetta di pongo che cosa è andando ad essere la domanda per Mary Beth è quello che sta facendo, come è lei va di risolvere questo? E in effetti, si potrebbe non avere mai pensato a qualcosa così semplice come quando si sceglie up 26 libri come questo, che non hanno una naturale ordinando a loro. Qual è il processo che effettivamente utilizzati? E 'abbastanza casuale solo scegliere il primo che si vede e metterlo al suo posto? Sei tu prima di spostare le mani intorno Alla ricerca di un poi cerca di B? Non si prende un'occhiata a un coppia di loro affiancati e dire, aspetta un minuto, questo non è giusto, e poi scambiare l'ordine? Abbiamo visto già il Lunedi che c'è un certo numero di modi in cui possiamo farlo, e anzi come ci avviciniamo alla fine qui, Vorrei prendere nota forse di ciò che Mary Beth sta facendo. Abbiamo un paio di pali sembra, un più grande, tre più piccoli. 

PUBBLICO: Li sto ordinando quando trovo due lettere che io conosco sono insieme in una sequenza, Li ho messi insieme in modo che io non lo faccio devono preoccuparsi di mantenere traccia di un'intera fila di libri. E 'solo, oh, A è prima, Ho questo stack qui. SPEAKER: Così, quasi come pezzi di un puzzle che hanno la forma giusta per combaciare con l'altro. PUBBLICO: Praticamente, sì. SPEAKER: OK, eccellente. E ora ciascuno di questi pali è presumibilmente ordinati? 

PUBBLICO: Sì. 

SPEAKER: Va bene, dalla A alla Z. Tutti a destra, complimenti, avete fatto. Avete la vostra scelta. Blue? Va bene, vi ringrazio per questo. Così Mary Beth ha proposto quello che il suo approccio è stato, ma ciò che è un altro approccio come si potrebbe andare sull'ordinamento queste cose? Che cosa avresti fatto? Il record da battere sarebbe stato un minuto e 50 secondi o giù di lì, oltre a quelli che ho dimenticato di contare. Che cosa avresti fatto? Sì? PUBBLICO: Prendere la pila. Inizia dall'inizio. Controllare i documenti. E se quella superiore è maggiore che, forse, sono, quello inferiore è superiore, quindi cambiare. 

SPEAKER: OK, quindi iniziare nella parte superiore e la parte inferiore, e poi lavorare il vostro senso verso l'interno così, scambiando loro? OK, quindi un po 'simile in spirito di bubble sort, ma scegliendo gli estremi Non le coppie adiacenti. Ma il corto di esso è che non c'è sicuramente un sacco di modi diversi potremmo fare questo, e francamente, penso che tipo di adottato un paio di approcci, giusto? Hai fatto una sorta di quattro pali ordinati, e poi effettivamente li fuse insieme. E questo è, oserei dire, un altro tecnica del tutto. Non hai trattata come una grande pila, si è diviso il problema in quattro quad, se si vuole, e quindi in qualche modo li fuse alla fine. 

Quindi consideriamo, in ultima analisi, in quale altro modo potremmo farlo. Abbiamo formalizzato la nozione di bubble sort ultima volta, e bubble sort richiamo è stato un algoritmo che abbiamo visualizzato con otto dei tuoi compagni di classe qui, apparentemente ordinati in modo casuale in un primo momento. E poi abbiamo deciso due a due, se due elementi sono in ordine, semplicemente scambiare. Quindi, quattro e due sono ovviamente fuori uso, così quei due compagni di classe scambiato posizione. E poi abbiamo ripetuto con quattro e sei, poi sei e otto, ad ogni iterazione, spostando verso destra. 

Quindi, dato otto persone, quante coppie paragoni Ho fatto mentre si cammina da sinistra a destra in una tale iterazione? Quanti paragoni? Sette, giusto? Perché se ci sono otto persone, ma avete la coppia loro e si mantiene in movimento un salto a destra, non stai andando ad avere otto paragoni perché non si può confrontare un elemento contro se stessa, o sarebbe solo essere inutile, in modo da avere sette. Oppure più in generale, se abbiamo n persone, abbiamo fare n meno 1 confronti con bubble sort. 

Quindi prendiamo in considerazione ora come buono o male bubble sort realtà era, e provare per dare a noi stessi vocabolario con che agli algoritmi critica come questa, e presto la nostra. Quindi il primo passaggio attraverso bubble sort, la prima volta Ho camminato da sinistra a destra attraverso il fase, me n meno 1 confronti preso. E questo sta andando essere il mio unità di misura, giusto? Ero un po 'a parlare e passeggiare, un po 'veloce, un po' lento, così contare il mio numero di secondi non è particolarmente significativo, ma contando il numero di operazioni che ho fatto il Lunedi, confronto tra due persone, che si sente come una bella unità di misura. 

Così n meno 1 passi la prima volta, ma poi che cosa è successo dopo? Qual è il vantaggio di un solo passaggio attraverso una lista a pena di non ordinato? Cosa mi puoi raccontare l'elemento che era tutta la strada laggiù? Sì? Questo è stato l'elemento più grande, giusto? Numero otto, anche se lei iniziato qui, ogni volta che il suo rispetto nei confronti un vicino di casa, ha mantenuto gorgogliare a destra lato della lista. E infatti, ecco dove l'algoritmo prende il nome. 

Ora da questa logica, il numero di confronti bisogno Faccio la seconda volta Faccio che passa da sinistra a destra? n meno 2, giusto? Sarebbe solo sprecando il mio tempo, se mi mantenere il confronto otto contro qualcuno altro perché sappiamo già lei era nel posto giusto. Ecco, questo è un po 'un ottimizzazione, in modo che il passaggio successivo sta per essere più n meno di due passi, dove n è il numero di persone. Ora è possibile tipo di estrapolare, anche se non sei un informatico, come finirà. Alla fine di questo algoritmo, presumibilmente hai solo un confronto a sinistra. Dovete tipo di fissare la inizio della lista nel caso di due e uno sono fuori ordine e dovrebbe essere uno e due, quindi questa battuta fuori a più 1 confronto finale. 

Ora il dot, dot, dot tipo di onde è mani in alcuni dei dettagli più succosa, ma facciamo solo andare avanti e semplificare. Se vi ricordate da alta scuola, francamente, molti di voi avuto libri di matematica che aveva un piccolo foglietto sulla copertina anteriore o il coperchio posteriore che vi ha mostrato sommatorie che serie come questo in ultima analisi, ha aggiunto fino a. Nel caso generale, se si dispone di un variabile come n, e in effetti questo, se hai guardato il tuo vecchia scuola libro di matematica, si vedrebbe che questo in realtà aggiunge a questa somma qui, n volte n meno 1 tutto diviso 2. Quindi per ora lasciatemi stipula le questo è vero, quindi su un atto di fede, che è ciò che questo riassume fino a, e abbiamo potuto dimostrare che in un caso più generale. Ma ora cerchiamo di espandere questo fuori. Quindi cerchiamo di moltiplicare questo fuori, così che è n squadrato, meno n, tutto diviso per 2. Questo è davvero n al quadrato, diviso per 2, meno n sopra 2, così che è tutto bello e interessante. Ma cosa succede se si ora plug-in di un valore? Supponiamo che io non avevo otto persone, ma dicono un milione. E un milione solo perché si tratta di un numero abbastanza grande, cerchiamo di spina che in e vediamo cosa succede. Quindi, se io inserisco un milione in quella formula Ho intenzione di ottenere un milione quadrato, diviso 2, meno una milioni di euro, diviso per 2. Ora che cosa è che sta per eguagliare? Quindi 500 miliardi, meno di 500.000. E se io in realtà faccio che la matematica, significa che che l'ordinamento di un milione le persone con il bubble sort mi potrebbe prendere 499.999.500.000 passi o confronti, alla fine, stiamo solo estrapolando. 

Che si sente abbastanza lento, ma francamente misura un ingresso particolare in questo modo, non è tutto ciò che racconto. Ma infatti suggerisce che come n diventa sempre più grande, questo algoritmo tipo di sente peggio e peggio, o si ha realmente cominciare a sentire il dolore di quella elevamento a potenza, che n al quadrato, che aggiunge abbastanza veloce. E questo dettaglio non è perso su persone, infatti alcuni anni fa, un certo senatore che era campagna, si sedette per un colloquio con Google Eric Schmidt, CEO al momento, ed è stato sfidato con una domanda proprio come stiamo esplorando oggi. Diamo uno sguardo. 

[RIPRODUZIONE VIDEO] 

-Senator, Tu sei qui a Google, e mi piace pensare di presidenza come un colloquio di lavoro. Ora, è difficile ottenere un lavoro come presidente, e si sta andando attraverso i rigori adesso. E 'anche difficile ottenere un lavoro presso Google. Abbiamo domande, e noi chiedere ai nostri candidati domande, e questo è da Larry Schwimmer. Cosa-- pensate voi ragazzi che sono scherzo, è proprio qui. Qual è il modo più efficace per ordinare un milione di numeri interi a 32 bit? 

-Well-- 

Mi dispiace, maybe-- 

No, no, no. Penso che il bubble sort sarebbe il modo sbagliato di procedere. 

-Dai, Che gli ha detto questo? Non ho visto del computer scienza nel vostro sfondo. 

-We've Ottenuto le nostre spie in là. 

-OK, Chiediamo un diverso domanda intervista. 

[FINE RIPRODUZIONE VIDEO] 

SPEAKER: Così parlando numeri specifici, però, non sta per essere tutto ciò che utile. Non è una lezione di vita che bolla tipo, data un milione di ingressi, potrebbe richiedere fino a 500 miliardi di passi. Non si può davvero generalizzare Anche efficacemente da quella e prendere buone decisioni di progettazione durante la scrittura dei programmi. Quindi concentriamoci però su come potremmo semplificare questo risultato. 

Così ho evidenziato in giallo qui il risultato di n al quadrato diviso per 2, così un milione quadrato diviso 2, e poi Ho evidenziato quello che la risposta definitiva è stata una volta che abbiamo sottratto off n diviso per 2. E la domanda che sto per fare oggi è, chi diavolo se ne frega se si sottrae off un po 'vecchio n sopra 2 quando il primo parte di questa formula è tanto più grande? Domina l'altro termine, n al quadrato diviso per 2 è così molto più grande, in modo chiaro, come n diventa grande come un milione, che c'è davvero una grande differenza a Alla fine della giornata tra 500 miliardi e 499.999.500.000? Non proprio. E così quello che stiamo andando a fare come gli informatici è ignorare quei termini di ordine inferiore e prendere qualcosa come questo e davvero solo di semplificare al termine che sta andando alla materia. I nostri più grandi insiemi di dati diventano, il più grande nostri database ottengono, le pagine web più dobbiamo cercare, il più amici che si hanno su Facebook. 

Come n diventa più grande, siamo davvero andando a prendersi cura del più grande termine in qualsiasi analisi di le nostre prestazioni di algoritmi. E ho intenzione di dire, sai cosa, bubble sort è dell'ordine di O grande, dell'ordine di n al quadrato. Non è esattamente n Squared come abbiamo visto, ma chi se ne frega davvero su quei termini più piccole, e francamente, che davvero se ne frega se dividiamo da 2? Questo è solo un fattore costante. Ed è 500 miliardi contro 250 miliardi davvero così grande di un affare? Potevo solo aspettare un anno, lasciare il mio computer portatile letteralmente ottenere due volte più veloce in hardware, e che tipo di differenza appena va via naturalmente nel tempo. 

Quello che ci interessa è l'espressione, la parte dell'espressione che sta per variare come il nostro ingresso diventa sempre più grande. E infatti, nel mondo reale, questo è ciò che sta accadendo sempre più è gli ingressi ai nostri problemi e algoritmi sono sempre più grande. Così grande O sarà la notazione, la notazione asintotica, che abbiamo appena utilizzare come gli informatici per descrivere le prestazioni, o il tempo di esecuzione, di un algoritmo. In modo che possiamo confrontare algoritmi su computer diversi scritti da persone diverse in base alcune metriche fondamentalmente simile come il numero di confronti che sei fare, o forse il numero di swap che stai facendo. 

Quello che non stiamo andando a conta è la quantità di tempo che passa l'orologio sulla parete tipicamente. Quello che non stiamo andando a preoccuparsi circa è la quantità di memoria si sta utilizzando oggi alle almeno, anche se questo è un'altra risorsa potremmo misurare. Stiamo andando a cercare di basare le nostre analisi solo su le operazioni di base, quelli, francamente, che potete vedere più visivamente. Quindi, con qualcosa come grande O di n quadrato, io sostengo che O di n al quadrato è un limite superiore sul cosiddetto tempo di bubble sort in esecuzione. In altre parole, se si voluto affermare che non c'è questo limite superiore al numero di passi un algoritmo può prendere, sta andando ad essere in grande O di n squadrato in questo caso, un limite superiore. 

Cosa succede se invece cambio il storia di essere non su bubble sort, ma questo limite superiore. Riuscite a pensare a un algoritmo che abbiamo esaminato già il cui limite superiore, massima misura del tempo o operazioni, sarebbe detto di essere delimitata da n, una funzione lineare, non un quadratica che è curvo? Che cosa è un algoritmo che prende sempre più che come n passi, o Passi 2n, 3n o gradini? Sì? 

PUBBLICO: Trovare il maggior numero in un elenco? 

SPEAKER: Perfetto, trovando il maggior numero in un elenco. Se mi sono dato una lista di persone per esempio, ciascuna di chi è in possesso di un numero, qual è il numero massimo di passi che dovrebbe prendere me, una persona abbastanza intelligente, per trovare la più grande persona in quella lista? n, giusto? Poiché nel caso peggiore, in cui potrebbe essere il più grande valore? Destra, tutto il senso alla fine. Quindi, nel caso peggiore limite superiore, potrei andare fino in fondo qui e di essere come, oh, ecco il numero otto, o qualsiasi altra cosa che il valore è. Ora sarebbe solo stupido se ho continuato ad andare, giusto? Cerco sempre di più elementi se l'ultimo di questi è laggiù? Quindi sicuramente, n è un limite superiore. Non ho bisogno di prendere più passaggi di quello. 

Così che cosa se invece ho proposto che esistono algoritmi in questo mondo che hanno un tempo di esecuzione che è delimitata da grande O di log n, log n? Dove abbiamo visto prima? Sì? 

PUBBLICO: Nel problema rubrica? SPEAKER: Come il problema rubrica. Qual è stata la misura di quanto molto tempo o quante lacrime it mi ha portato a trovare qualcuno come Mike Smith nella rubrica? Abbiamo sostenuto che era log n, e anche se non conosce o si è un po 'confuso ciò che un logaritmo o esponente era, basta ricordare che log n generalmente si riferisce al processo, in questo caso, di dividere qualcosa a metà ancora, e ancora, e ancora, e ancora, tale da diventa sempre più piccolo, come lo fai. 

Così log di n si riferisce, certo, per esempio la rubrica telefonica, di ricerca binaria in teoria, quando si aveva le porte virtuali sul tabellone, o quando Sean era alla ricerca di qualcosa. Se avesse usato la ricerca binaria, log n sarebbe il limite superiore della quantità tempo che prende. Ma quegli algoritmi che correvano in log n assunto quale chiave dettaglio? Che l'elenco è stato risolto, giusto? Il tuo algoritmo è sbagliato se l'input non è ordinato, e ancora si sta utilizzando qualcosa come la ricerca binaria perché si potrebbe saltare proprio sopra l'elemento senza rendersi conto che è davvero lì. 

Ora, che cosa potrebbe significare questo, grande O di uno? Questo non significa che il vostro algoritmo prende uno e un solo passo, significa solo che ci vuole un numero costante di passi. Forse è 1, forse è 10, forse è 1.000, ma è indipendente da la dimensione del problema. Non importa quanto grande sia n, un algoritmo di costante di tempo prende sempre lo stesso numero di passi. Così che cosa potrebbe essere un algoritmo abbiamo parlato o solo intuitivamente che viene a voi che corre sempre nella cosiddetta costante di tempo? Sì? 

PUBBLICO: Aggiungi due numeri. SPEAKER: Aggiungi due numeri, 2 più 2 uguale a 4, fatto. In modo che potrebbe funzionare, che altro? Che ne dite di mondo più reale, sì? 

PUBBLICO: Trovare il prima cosa in un elenco. SPEAKER: Trovare la prima elemento in un elenco, certo. Abbiamo effettivamente parlato circa già array, Come si ottiene al primo elemento di un array, non importa quanto tempo il array è in codice C? Basta utilizzare come supporto notazione a zero, bam, sei lì. E infatti gli array, come a parte, Supporto qualcosa di noto come accesso casuale, random access memoria, perché si può letteralmente saltare a qualsiasi luogo. Possiamo farlo ancora più semplicemente siamo in grado di riavvolgere a settimana a zero quando abbiamo fatto Scratch. Quanto tempo ci è voluto per la dire blocco Scratch da eseguire? Basta costante di tempo, giusto? Di 'qualcosa, dire qualcosa, non importa Quanto è grande Graffi mondo è, è sempre andando a prendere la stessa quantità di tempo semplicemente dire qualcosa. 

Ecco, questo è tempo costante, ma qual è il rovescio della medaglia? Se questo era superiore limiti, che cosa se vogliamo per descrivere i limiti inferiori dei nostri algoritmi tempo di esecuzione? Quasi un caso migliore potenzialmente, se si vuole, anche se questi termini potrebbero applicarsi al meglio casi, casi più gravi, casi medi più in generale, ma facciamo solo concentriamoci su limiti inferiori, più in generale. Che cosa è un algoritmo che ha un limite inferiore di n passi, o passi 2n, 3n o gradini? Alcuni fattore di n passi, questo è il suo limite inferiore. Sì? 

PUBBLICO: Bubble sort? 

SPEAKER: Bubble sort prende si minimamente n passi, perché? Perché? Perché che inizio a venire da voi intuitivamente, anche se non solo ancora? Sì? 

PUBBLICO: [incomprensibile]. SPEAKER: Esattamente. Nella migliore scenario possibile di bubble sort, e un sacco di algoritmi, se io ti consegno otto persone che sono già ordinati, sarebbe sciocco per voi, l'algoritmo, per andare avanti e indietro più di una volta, giusto? Perché non appena si camminare attraverso la lista una volta, si dovrebbe capire, oh, ho fatto nessun swap, questo elenco è ordinato, uscita. Ma che sta andando a prendere n passi. 

E viceversa, ciò che è un altro modo di pensarci? Bubble sort è un omega, per così dire, di n, perché se si guarda meno di n elementi, ciò è la questione fondamentale lì? Non sai se è ordinato, a destra. Noi esseri umani potrebbe sguardo alle otto persone e di essere come, oh, è ordinato, che non me n passi ha preso, ma lo ha fatto. I tuoi occhi, anche se si tipo di avere un grande campo visivo, hai guardato otto elementi, hai guardato otto persone, che è otto passi efficace. E solo se dovessi camminare in tutta la Lista do Mi rendo conto, sì, ordinato. Se mi fermo a pensare a metà strada, tutto a destra, è abbastanza ordinato finora, quali sono le probabilità non è ordinata? Che non Algoritmi sarà corretta. Potrebbe essere più veloce, ma non corretto. 

Così ora abbiamo un modo di descrivendo un limite inferiore, e che dire di costante di tempo? Che cosa è un algoritmo che ha un minore bound sul suo tempo di esecuzione di uno? 1 punto, 2 punti, 10 punti, ma costante, indipendente da n, la dimensione dell'input? Sì, in indietro. 

PUBBLICO: Printf? SPEAKER: Cosa e 'quello? PUBBLICO: Printf? SPEAKER: Printf. OK, certo. Quindi ci vuole un numero fisso di passaggi. E dovrei now-- ora che stiamo parlando di codice C e non Scratch, qualcosa come dire, con printf, dovremmo iniziare a ottenere attenzione. Perché printf fa prendere ingresso, si tratta di una stringa, e stringhe hanno tecnicamente lunghezza. Quindi, se ora vogliamo raccogliere su di te, se non ti dispiace, tecnicamente si potrebbe sostenere che printf non prendere un ingresso di lunghezza variabile, e sicuramente potrebbe richiedere più tempo per stampare una stringa questo lungo, di così lunga. 

Così che cosa se si considera solo il ordinamento e ricerca esempi? Che dire Mike Smith nel telefono libro, o binario di ricerca più in generale? Nel migliore dei casi, cosa potrebbe accadere? Apro la rubrica e, bam, c'è il numero di Mike Smith. Io lo posso chiamare subito. 

Fece un passo, forse due passi, ma un numero costante di passi se ho avuto fortuna. E, francamente, abbiamo visto in Lunedi il tuo compagno di classe ottenere abbastanza fortunato due volte di fila. E questo è stato davvero costante volta in limiti inferiori l'algoritmo in questione per reperire il numero 50 dietro quelle chiuse porte. 

Ora, come un a parte, se si scopre che sia grande O, il limite superiore, e l'omega, il limite inferiore, sono uno nello stesso, che è la stessa formula in parentesi, è anche possibile dire, solo per essere di fantasia, che qualcosa è in theta di n o theta di qualche altro valore. Ciò significa proprio quando grande O e omega sono uguali. Ora, che dire di ordinamento per selezione? Usiamo questo nuovo vocabolario. In selection sort, cosa stavamo facendo ancora, e ancora, e ancora? Stavo andando avanti e indietro attraverso l'elenco, in cerca di chi? Il numero più piccolo. 

Così come molti passi, come molti paragoni fatto io devono fare in modo di capire chi il più piccolo elemento della lista è? n meno 1, giusto? Perché se ho appena comincio con quello che sono dato e io comincio a lui o lei a confronto, allora lui o lei, lo o lei, lui o lei, io può abbinare solo elementi insieme n meno 1 volte. Quindi la selezione prende sorta simile n meno 1 passi la prima volta. 

Quanti passi non mi ci vuole per trovare il secondo elemento più piccolo? n meno 2, perché io sono di essere stupido se Continuo a guardare le stesse persone di nuovo se ho già lui selezionato o lei e metterli al loro posto. E il terzo passo, n meno 3, allora n meno 4. Abbiamo visto questo modello prima, e anzi ordinamento per selezione allo stesso modo ha un limite superiore di n al quadrato se lo facciamo su quella somma. Qual è il suo limite inferiore, ordinamento per selezione? Minimamente, quanto la selezione must tempo Ordina prendere, come lo abbiamo definito il Lunedi? Proporre due opzioni. Forse è n, come prima. Forse è n al quadrato, come è ora come limite superiore. 

PUBBLICO: n quadrato. SPEAKER: n quadrato. Perché? 

PUBBLICO: Perché hai per definire [incomprensibile]. 

SPEAKER: Esattamente. Almeno per quanto ho definito ordinamento per selezione era piuttosto ingenuo, andare avanti, trovare l'elemento più piccolo. Andare di nuovo, trovare l'elemento più piccolo. Andare di nuovo, trovare l'elemento più piccolo. Non c'è nessun tipo di ottimizzazione in là che potrebbe farmi abortire dopo a n o giù di lì passi. Così infatti, la selezione sorta, omega di n al quadrato. 

Che dire di insertion sort, dove ho preso che mi è stato dato, e poi lo lasciai o lei nel posto giusto? Poi ho proceduto alla seconda persona, lui o lei piazzati nel posto giusto. Poi la prossima persona, lasciò lui o lei nel posto giusto. Si noti che questo è molto lineare, per così dire. Io sono una linea retta, io sono non andare avanti e indietro, Non ho mai guardare indietro davvero, ma cosa succede quando lo inserisco o suo nell'inizio di l'elenco come abbiamo fatto il Lunedi? Cosa sta succedendo? Sì? PUBBLICO: [incomprensibile]. SPEAKER: Sì, che era la cattura, giusto? Si potrebbe ricordare da tuoi compagni di classe, se stavano facendo qualsiasi movimento con i loro piedi, che era un'operazione. Quindi, se ci fossero tre persone qui e la nuova persona apparteneva modo laggiù, su un palco lungo come questo, certo, egli o lei potrebbe semplicemente andare fino in fondo. Ma se stiamo pensando a un computer e un array di memoria, queste persone stanno andando di avere a mescolare su per fare spazio a quella persona. E così che n meno 1 stropiccii, n meno 2 stropiccii, n meno 3 stropiccii è solo tipo di succedendo dietro di me, non di fronte a me come prima, in un certo senso. Ora, come una parte, e come potreste vedere on-line se si avvia rovistando su tipi, ci sono così tanti quelli diversi là fuori, alcuni di essi meglio di altri. Infatti, è uno bogosort che una specie di divertente da guardare in alto. Bogosort prende un set di numeri o dire un mazzo di carte, le mescola in modo casuale, e controlla se sono ordinati. E se no, lo fa di nuovo. E se no, lo fa di nuovo. In caso contrario, lo fa di nuovo. Incredibilmente stupido. 

E in effetti, se leggi come l'articolo di Wikipedia, il suo soprannome è stupido sorta. E alla fine funzionerà, si spera, dato abbastanza tempo, ma quella quantità di tempo potrebbe richiedere molto tempo. Quindi, se potessi, di lasciare che le cose di velocità dal esempio di Mary Beth precedenza, avendo un paio di elementi, ma altri due processori. Due persone, se si Non mi dispiacerebbe unirsi a me. Come circa 1 qui, e cerchiamo di go-- nessuno laggiù? Nessuno laggiù? Ok. È con il nero camicia, sì, vieni giù. Va bene, qual è il tuo nome? 

PUBBLICO: Peter. 

SPEAKER: Cosa e 'quello? 

PUBBLICO: Peter. SPEAKER: Peter, David, piacere di conoscerti. Va bene, abbiamo Pietro qui, se si vogliono venire sul tavolo qui. E qual è il tuo nome? 

PUBBLICO: Elena. SPEAKER: Elena. OK, piacere di conoscerti. Elena incontrare Peter. Pietro, Elena. E avremo bisogno di Andrew up anche qui, per favore. E la vostra sfida è andare essere quello di ordinare un mazzo di carte. E se non familiare, ponte di carte dovrebbe in ultima analisi, essere ordinati un po 'qualcosa di simile questo dove faremo i club, poi le picche, poi i cuori e diamanti, da asso come uno, tutta la strada fino al re. 

Le carte ho intenzione di darvi stanno per essere 52 in quantità. Stiamo andando allo stesso modo volta che, in un attimo. Stiamo per lanciare Andrew sullo schermo qui, in modo da guardare come si esegue questa operazione. E così che tutto questo è tanto più visibile, queste sono le carte che ho ricevuto su Amazon. Quindi sono già in modo casuale risolto, e stiamo andando a volta che si. E stiamo andando a tenerlo reale questa volta, quindi stiamo andando a cercare di pressione si perché altrimenti questo otterrà noioso rapidamente. Se si potesse procedere a ordinare 52 elementi insieme tramite alcuni mezzi, ora. 

E ancora, come noi guardiamo questi ragazzi fanno quello che, alla fine, sta per produrre un evidente Di conseguenza, pensare davvero come stanno facendo ogni, come si potrebbe descrivere. Perché ancora, questi sono tutti i processi, gli algoritmi che diamo per scontato come un essere umano. Ma probabilmente hai avuto per lungo tempo intuizione, molto prima ancora di pensato di prendere una classe di scienze computer potrebbe aver avuto l'intuizione con che per risolvere problemi come questo. Ma una volta che si riconosce i modelli e cominciare per formalizzare i passi con i quali stai risolvere questi problemi, troverete che è possibile risolvere molto più interessante e molto più complessa rapidamente i problemi. Così qualcuno dal pubblico, che cosa è almeno un elemento dell'algoritmo che stanno usando qui? 

PUBBLICO: [incomprensibile] SPEAKER: Cosa e 'quello? PUBBLICO: Da vestito. SPEAKER: By vestito. Quindi, prima che si discostano tutti i diamanti insieme sembra, tutte le cuori insieme a quanto pare, e così via, senza rispetto per i numeri sulle carte. E ora appaiono, per esempio, da loro ordinamento per numero. Molto buona. 

Va bene, quindi che cosa sta per essere il passo finale, allora qui? Una volta che abbiamo quattro semi ordinati, cosa abbiamo bisogno di fare per i quattro pali al fine di realizzare uno ordinati ponte, molto semplicemente? Quindi abbiamo bisogno di unire di nuovo. 

Quindi c'è un'idea interessante che ancora una volta, oserei dire, è molto intuitivo anche se si potrebbe mai avere schiaffeggiato quel tipo di etichetta. Questa nozione fondamentale di divisione il problema non a metà questa volta, ma almeno in quattro pezzi. Risolvere praticamente problemi fondamentalmente identici isolatamente l'uno dall'altro, e poi la fusione dei risultati. E, eccellente, fatto. Va bene, una grande rotonda di applausi, se avessimo potuto. 

[Applausi] 

SPEAKER: Non ho idea di quello che ti fare con questi, ma qui si va. Vi ringrazio tanto. Vediamo quindi, a due minuti e otto secondi, se vuoi sfidare i tuoi amici. Che poi sta per essere un take away da questo che possiamo sfruttare più in generale? Beh, ripensare a questo array di numeri, e ripenso ora ad alcune delle pseudocodice abbiamo scritto in passato, e questo era il pseudocodice per risolvere il problema rubrica. Per cui in pseudocodice I enumerato un modo più metodico di descrivere come ho fatto molto intuitivo algoritmo umano di dividere il telefono libro a metà, ripetere, ripetere, ripetere, finché non trovo qualcuno come Mike Smith, se è davvero nella rubrica. 

Ma ho usato il tipo di quello che io chiamo un approccio molto iterativo qui, in particolare preavviso linea 8 e la linea 11. Queste sono prove di un iterativo approccio, un approccio looping, perché questo è esattamente il comportamento che inducono. Quelle linee entrambi dicono andare a linea tre, e si può tipo di pensare che nel tuo occhio della mente come un loop. Ti sta dicendo di tornare indietro fino al punto tre e ripetere, ancora, e ancora, e di nuovo. 

Ma cosa succede se facciamo leva una idea chiave qui che abbiamo fatto non l'ultima volta, e semplificare la linea 8 e linea 11 ei loro vicini come solo questo, in giallo. Non è fondamentale accorciare il pseudocodice molto, ma è fondamentalmente cambiando la natura del mio algoritmo. Quello che sto dicendo adesso al punto 7, al punto 10, sia per la ricerca di Mike nello stesso modo, ma solo nel fianco la metà o la metà destra. 

Quindi, in altre parole, se Parto dal punto uno, prendere rubrica, aperto a metà di rubrica, guardare i nomi, se Smith è tra Il nome di, chiamare Mike, altro se Smith è in precedenza nel libro, passo sette la ricerca di Mike nella metà sinistra del libro. Ma questo tipo di sente come mi sta lasciando appeso, giusto? In giallo, è un istruzione, ma come faccio cercare Mike a sinistra metà della rubrica? Dove devo un algoritmo con il quale ho può cercare per uno come Mike Smith? Beh, ci sta guardando in faccia. Posso letteralmente usare la stessa esatta programma effettivamente andare fino alla cima di nuovo e ri-esecuzione le stesse linee di codice. 

Così, anche se questo dovrebbe sentirsi come un po 'di una definizione ciclica dove si sta rispondendo di qualcuno domanda da appena sorta di chiedere di nuovo la stessa domanda, come perché, perché, perché? La realtà è perché abbiamo hardcoded un paio di linee speciali, punto 4, che è un caso, e il punto 12, che è effettivamente un altro ramo, perché abbiamo tali misure di ripiego, questo algoritmo terminerà se trovare Mike, o se non lo facciamo. Ma nel passo 7 e 10 ora, abbiamo quello che chiameremo un algoritmo ricorsivo. E ricorsione è infatti un potente idea che è un po 'rompicapo in un primo momento, che ora possiamo applicare come segue. 

Merge sort sarà l'ultimo tipo che guardiamo, almeno in classe formalmente. Ed è fondamentalmente diverso da quelle ultime tre, e certamente ultimi quattro se includiamo bogosort. Ecco lo pseudocodice per merge sort. Quando sull'ingresso di n elementi, così determinato un array di dimensione n, se n è minore di 2, ritorno. Allora perché devo che sanità mentale controllare in primo luogo? Qual è l'implicazione se ti consegno un array di lunghezza n è minore di 2? E 'già ordinato, ovviamente, giusto? Poiché l'elenco ha o un elemento, che è banalmente ordinato perché è l'unica cosa lì. Oppure, è di dimensioni pari a zero, che significa non c'è niente da ordinare, così per natura esso è ordinato. Non c'è proprio niente di male lì. Ecco, questo è il nostro cosiddetto caso base. 

Questo è simile nello spirito per quello che abbiamo fatto con Mike. Se Mike nella rubrica, lo chiamano. Se non è lì, rinunciare. È un cosiddetto caso base, per assicurarsi questo algoritmo alla fine della giornata si fermerà in determinate circostanze. 

Ma ecco il salto della fede oggi, altrimenti, ordinare la metà sinistra degli elementi, poi ordinare la destra metà degli elementi, e poi unire le due metà ordinate. E qui è dove ci si sente come stiamo copping fuori. Ti ho chiesto di ordinare n elementi, e sono dicendo: OK, non è di classificare la sinistra e l'ordinamento del diritto. Ma che sto dicendo una altra cosa, e questo è il tema chiave sembra nell'intuizione finora, c'è questa terza fase della fusione. Quale pur sembra così stupido in spirito, come solo unire le cose insieme, sembra di essere un passo fondamentale verso la riassemblaggio dei due problemi che sono stati divisi in definitiva a metà. 

Così merge sort, facciamo questo, se avrete umorismo me, con una dimostrazione in più, solo così che abbiamo qualche numeri per lavorare con. Posso scambiare otto lo stress palle per otto persone? Va bene, come su di voi tre, voi quattro in questa sezione, cinque, sei, e cerchiamo di do 7, 8, andiamo su. OK, sì OK. Minus 8, ci andiamo, più 1. Eccellente. Va bene andiamo su, andiamo dare rapidamente i numeri. Numero due, numero tre, numero quattro, numero cinque, sei, sette e otto. Ho fatto otto correttamente questa volta. 

OK, in modo da andare avanti se si potesse, e cerchiamo di ordinare in ordine originale che abbiamo avuto ieri che sembrava in questo modo, se non mi dispiacerebbe. E facciamolo davanti al tavolo. Va bene, così merge sort. Questo è dove sta andando per ottenere tipo di interessante, perché mi sembra di dare me stesso tanto meno informazioni oggi. 

Così merge sort prima di tutto su input di n elementi, e ovviamente non è inferiore a due, è otto, quindi ho qualche lavoro da fare. Così ora mentalmente siamo come una classe sono ora nel ramo altro, che significa tre passi. In primo luogo, devo ordinare il metà sinistra degli elementi. Allora, come posso fare per fare questo? Beh, io vado a tipo di suddividere mentalmente la lista qui, non avete a muovo fisicamente, e io sono andando a concentrarsi solo sul metà sinistra degli elementi qui. Allora, come posso fare per l'ordinamento un elenco ormai di dimensioni quattro? Qual è il mio algoritmo? Per prima cosa ho Check è n meno di due, no, così procedo al blocco altro ancora. Ordina lasciato la metà di elementi. 

Così ora di nuovo, mentalmente, ed è qui devi accumulare un sacco di storia mentale, se si vuole. Ora sto smistamento sinistra metà della metà sinistra. Va bene, così ora io chiamo il mio stesso tipo merge algoritmo di ordinamento, è n meno di due? No, è due, quindi devo ordinare la metà sinistra, e la metà destra. Quindi qui si va, ordinare la metà sinistra. Perché non basta fare un passo avanti. Come ti chiami? 

PUBBLICO: Darren. 

SPEAKER: Dan. Dan ha fatto un passo in avanti. 

PUBBLICO: Darren. SPEAKER: Darren, fatto. Hai detto Darren o Dan? 

PUBBLICO: Darren. 

SPEAKER: Darren. OK, Darren ha intensificato in avanti e lui è ora ordinato. E questo è quasi un affermazione inane, giusto? Non mi sembra davvero di essere il raggiungimento nulla, ma procediamo. Ora vorrei ordinare la giusta metà degli elementi. Come ti chiami? 

PUBBLICO: Luke. 

SPEAKER: Luke. Dai, un passo in avanti. Fatto, ho ordinato Luke. La metà di sinistra è ora ordinato e la metà destra è ora ordinato, ma ancora una volta, c'è un passo fondamentale qui. Di cosa ho bisogno di fare il prossimo? Unire le due metà ordinate. Ora stiamo andando ad avere solo tutti avanti e indietro in questo modo, perché ho tipo di bisogno po 'di spazio zero. E 'quasi come questi ragazzi sono su un tavolo, e ho bisogno di un certo spazio per spostarli in giro su. Quindi ho intenzione di fondere voi ragazzi, cercando nella metà di sinistra e la metà destra. E chi viene prima, ovviamente, metà sinistra o metà di destra? Così metà destra, quindi andiamo avanti Luke su qui alla posizione originale di Darren. E ora per unire loro metà sinistra, Darren sta per trasferirsi proprio lì. 

Così si sente come quasi un effetto bubble sort, ma il mio algoritmo fondamentale, molto diverso questa volta. Ma ora è dove le cose si fanno un po 'fastidioso perché si devono riavvolgere mentalmente dove ho lasciato fuori. Ho appena fuso le due metà ordinate, che significa che sono dove nel mio algoritmo? Devo ordinare la metà destra, giusto? 

Se si riavvolge, letteralmente sul video, ti vediamo che siamo arrivati ​​a questo punto di Luca e Darren di classificare sinistra metà della metà sinistra. Poi ci siamo fusi quelli metà ordinati, che significa che il passo successivo è sorta l' metà destra della metà sinistra. Va bene, quindi cerchiamo di farlo più rapidamente. Va bene, sei, ho intenzione di rivendicare si sono ora ordinati, andiamo avanti. Come ti chiami? 

PUBBLICO: Adriano. 

SPEAKER: Adriano. Adriano è ora ordinato. E qual è il tuo nome? 

PUBBLICO: Alex. 

SPEAKER: Alex è ora ordinato. La metà sinistra, metà di destra, qual è il passo finale? Unisci. Piuttosto banale, quindi sono andando a fondersi in sei, fare un passo indietro, otto, fare un passo indietro. E ora notate questo è un take-away utile, cosa ora è vero circa la metà sinistra del lista, a prescindere di come abbiamo cominciato? Si è ordinato. 

Ora non è ordinato in il grande schema delle cose, ma è ordinato in modo indipendente dell'altra metà. Ora, che cosa sono io passo su se continuo riavvolgimento come la storia ha cominciato? Ora devo ordinare la metà destra. Così ora siamo di ritorno al l'inizio della storia, e facciamolo più rapidamente. Quindi ho intenzione di ordinare la metà destra l'intero elenco. Qual è il prossimo passo? Ordina la metà sinistra della metà di destra. Ordina la metà sinistra del metà sinistra della metà destra. E qual è il tuo nome? 

PUBBLICO: Omar. 

SPEAKER: Omar, un passo in avanti, fatto. Metà sinistra è ordinato. E qual è il tuo nome? 

PUBBLICO: Chris. 

SPEAKER: Chris, fare un passo in avanti, si sono ora ordinati. Qual è il passo fondamentale adesso? Unisci. Così si sta per fondersi in posizione qui, se si potesse fare un passo indietro, e tre sta per fare un passo indietro, si fondono. Quindi la metà sinistra del metà di destra, è ora ordinato. Francamente, questo algoritmo si sente come noi stanno sprecando molto più tempo rispetto a prima, ma se abbiamo fatto questo in tempo reale, faremo vedere quello che i takeaway andando essere. Ora eccomi qui, a destra metà della metà destra, lasciami andare avanti e ordinare la metà sinistra. Passo in avanti, come ti chiami? PUBBLICO: Ramsey. SPEAKER: Ramsey è ora ordinato. Come ti chiami? 

PUBBLICO: Marina. 

SPEAKER: Marina è ora ordinato come bene, se si prende un passo avanti. Punto chiave qui è ora unire, io sono andando a cogliere dai miei due liste, a destra ea sinistra. Cinque sta per venire prima, e sette sta per venire dopo. E di nuovo, questo è intenzionale. Il fatto che stanno prendendo passi in avanti e indietro si vuole rappresentare che non possiamo fare questo algoritmo in luogo facilmente come bubble sort e selection sort, e insertion sort, dove abbiamo appena mantenuto lo scambio di persone. Ho letteralmente bisogno di una sorta di carta zero in cui di mettere queste persone mentre io faccio la fusione, e poi posso metterle a posto. E questo è fondamentale perché sto utilizzando un nuova risorsa, lo spazio, non solo il tempo. 

OK, questo è incredibile. La metà sinistra è ordinato, la metà destra è ordinato, ora che la fusione chiave passo. Come faccio a fondere questo? Quindi, se seguirete il mio mano sinistra e la mano destra, Ho intenzione di puntare la mia mano sinistra a metà di sinistra, la mano destra a metà destra, e ora devo decidere passo dopo passo chi si fondono in. Chi viene ovviamente prima? Numero uno. Quindi vieni qui, ecco la nostra scratch pad. Così ora numero uno, e comunicazione cosa farò con la mia mano destra, Ho intenzione di muovere la mano destra una passo sopra al punto numero tre, e ora devo fare la stessa decisione. E in realtà stare proprio in davanti a Luca qui se si potesse, perché questo è il nostro scratch pad. Allora, chi viene dopo? Abbiamo Luke con il numero due o Chris con il numero tre. Ovviamente Luca, numero due, in modo da venire qui. 

Ma la mia mano sinistra ora sta per essere incrementato per puntare a Darren, e qui è la chiave di portare via con la fusione, ho intenzione di continuare a fare questo, ovviamente, se tipo di seguire la logica. Ma le mie mani non sono mai per andare indietro, il che significa che sono sempre e solo di trasferirsi a sinistra con il mio processo di fusione, e che sta per essere la chiave per la nostra analisi in un attimo. 

Così ora finiamo questo rapidamente. Così tre viene dopo, poi quattro viene dopo, e ora cinque viene dopo, poi sei, e sette, e poi finalmente otto. Si sente come l'algoritmo più lento ancora, ma non se abbiamo effettivamente eseguirlo allo stesso tipo di velocità di clock, in modo da parlare, con la stessa ticchettio dell'orologio come prima. Perché? Beh, Facciamo un guardare il risultato finale. 

Torniamo qui, mi permetta tirare su una dimostrazione visiva di quello che abbiamo appena fatto. Ingrandimento qui, su questo pagina qui, dicendo Firefox che vogliamo fare la coda in questa casella, cerchiamo di dire bubble sort, con la quale siamo ormai familiare, ordinamento per selezione, che è un altro piuttosto una semplice, e ora di oggi merge sort, che sarà la nostra finale culminante. La ragione per cui c'è voluto così tanto più qui con gli esseri umani e me verbalmente è, ovviamente, sto spiegando ogni passo. Ma se semplicemente esegue questo, molto come abbiamo fatto bubble sort e selezione sorta non solo visivamente, orologio quanta più efficiente questa leva di divisione e conquistare può essere se applicato a un insieme di dati che è nemmeno dimensione otto, ma anche molto, molto più grande. Io do merge sort, fianco a a fianco con questi altri algoritmi. Questo sta per arrivare dolorosa rapidamente, e il finale non è particolarmente culminante, hanno appena finiscono ordinati. Ma la chiave da asporto è che Guarda come molto più veloce merge sort era, a meno che non pensi che io sia solo tipo di scherzi con voi. Se lo facciamo un'ultima volta, LET'S Ricarica questa, torniamo e scegliere bubble sort, e solo per i calci, scegliamo di inserimento specie, per buona misura. E anche questa volta, facciamo scegli merge sort e facciamo effettivamente eseguito questi fianco a fianco. 

E non è, infatti, un colpo di fortuna. Quello che ho effettivamente fatto è che ho diviso il mio ingresso a metà, di nuovo, e ancora, e ancora. E ci sono solo tante volte si può dividere l'input in due metà, a sinistra e destra. Qual è la formula che continuiamo a vedere che descrive la divisione a metà ancora, e ancora, e ancora, e ancora? 

PUBBLICO: Log n. 

SPEAKER: Log n. Ma poi c'è un altro passo fondamentale, questo algoritmo non è log n passi. Se fosse solo log n passi, saremmo nello stesso problema come prima, dove non possiamo essere che tutto sia risolto. Bisogna guardare minimamente al n elementi per essere sicuri che n elementi sono ordinati, altrimenti è un atto di fede. 

Quindi è minimamente log n passi, ma che dire di questo passo fusione chiave dove ho fuso la mia metà sinistra e destra metà e attraversò il palco? Quanti passi è quello di unire? E 'n, ma non l'ho fatto solo unire il tempo finale. Su ciascuna di queste chiamate nidificate, su ogni di quelle unioni nidificate, ho ancora risolto. Ho fuso questi due ragazzi, allora questi due ragazzi, allora questi due ragazzi e così via. 

Così ho fatto la fusione ancora, e ancora. Quante volte? Così ogni volta che ho diviso il list a metà, ho fatto un merge. Dividete la lista a metà, fare un merge. Quindi, se dividendo la lista si può fare log N volte, e la fusione prende in ultima analisi, n passi, quello che potrebbe essere ora il superiore vincolato sulla gestione tempo del nostro algoritmo? n log n. 

E in effetti, questo è ciò che abbiamo raggiunto qui. Quindi la sensazione che si vede visivamente quando queste tre cose corrono fianco a fianco è n quadrato contro la n quadrato contro log n n. Che fondamentalmente vedremo, non solo oggi ma anche in futuro, è molto, molto più veloce. Un applauso per questi ragazzi, Io li ricompenserà con le palle di stress. Facciamo aggiornare qui oggi, e ci vedremo il Lunedi.