[RIPRODUZIONE DI BRANI MUSICALI] DAVID J. MALAN: Questo è CS50. E questo è l'inizio di tre settimana. Quindi abbiamo un sacco di eccitante cose da coprire oggi. Un sacco di opportunità per i volontari sul palco. E alla fine, oggi è non si tratta di codice a tutti. Ma si tratta di idee, e si tratta di algoritmi, e in realtà riportando alcune delle le lezioni apprese dalla settimana pari a zero, quale richiamo, noi ha introdotto questa mostruosità. E indebitamento ispirazione questo, per iniziare per risolvere sempre più sofisticati problemi algoritmicamente. Ma prima, un paio di annunci. Quindi uno, se volete aderire Personale e compagni di classe del CS50 a pranzo questo Venerdì, sia qui che in Cambridge, ea New Haven, si prega di visitare il corso del sito web, dove un URL può essere trovato. Lezione questo Mercoledì sarà non essere qui a Sanders. Sarà solo online, così sintonizzarsi sul sito di CS50, se qui a Cambridge o New Haven pure. E allora il problema impostare due è già nelle vostre mani. Se non avete ancora tuffato in, mi permetta per offrire la suggestione parole forti che, soprattutto ora, come il problema pone anticipo, davvero si vuole da adesso, se non dilettarsi un po 'durante il fine settimana o prima quando in primo luogo escono su Venerdì, perché ti trovano che non sono necessariamente sempre più lungo o più impegnativo per se. Penso che troverete che, in generale, tendono ad assumere più o meno intorno stessa quantità di tempo. Ma dipende certamente lo studente, e dipende dalla mentalità con il quale ci si avvicina. Ma invariabilmente, si sta andando a correre contro qualche muro, e si sta andando a colpire alcuni bug, e sei solo non sarà in grado di ottenere su di esso ad un certo punto. Ed è estremamente prezioso per poter di allontanarsi, tornare il giorno successivo, andare in orario d'ufficio, post su CS50 Discutere o simili, per ottenere effettivamente sbloccato. Modo da tenere a mente. A partire prima possibile è la cosa migliore che puoi fare. Quindi, ecco dove siamo partiti la classe, oltre a settimana pari a zero. E possiamo ottenere un volontario qui per aiutarmi a trovare microfoni? OK. In piedi già. Vieni su. Indovinate che è così che sta andando a lavorare. Come ti chiami? ALAN ESTRADA: Alan Estrada. DAVID J. MALAN: Alan Estrada. Vieni su. Felice di conoscerti. ALAN ESTRADA: Piacere di conoscerti. DAVID J. MALAN: E lei fosse qui con noi in settimana a zero, naturalmente. ALAN ESTRADA: ero. Io ero. DAVID J. MALAN: Così si potrebbe andare avanti e trovare per noi Mike Smith, piu 'veloce che puoi? Piu 'veloce che puoi. Letteralmente strappando il problema a metà come si deve. ALAN ESTRADA: Uhm. DAVID J. MALAN: Letteralmente strappando il problema a metà. ALAN ESTRADA: Oh. Mm. Molto bene. DAVID J. MALAN: OK. Bene. Grazie. ALAN ESTRADA: Molto bene. OK. DAVID J. MALAN: E così ora, hai whittled giù alla metà della dimensione del problema. Ora, siamo giù a un quarto. Stai pagando attenzione da che parte stiamo mantenendo? [Ride] ALAN ESTRADA: Sì, io think-- DAVID J. MALAN: Che cosa siamo in sezione? ALAN ESTRADA: Silenziatori, così. DAVID J. MALAN: OK. Ma Mike Smith sta andando essere dopo Silenziatori. Così-- [Ride] Tutto ok. ALAN ESTRADA: Dove stiamo cercando? DAVID J. MALAN: Mike Smith. ALAN ESTRADA: Mike Smith. DAVID J. MALAN: Ora, siamo in chirurgico. Ora, i medici. Adesso-- ALAN ESTRADA: Let's- andiamo con reali. Real. DAVID J. MALAN: Real. OK. Se avete bisogno reale. Ora, da che parte è Mike Smith? ALAN ESTRADA: In questo modo. DAVID J. MALAN: Quale modo? ALAN ESTRADA: Aspetta. M è-- giusto? Abbiamo iniziato with-- DAVID J. MALAN: Sì. Sono lasciati. Destra. ALAN ESTRADA: Sì. DAVID J. MALAN: Così Mike qui. ALAN ESTRADA: Che cosa? [Ride] Cattivo esempio, ragazzi. Scusate. DAVID J. MALAN: Questo insegnerà di saltare dalla sedia. ALAN ESTRADA: Oh. Oh. Ti ho preso. Ti ho preso. Oh. Oh. Questo è-- OK, ti ho fatto. Smith proprio qui? DAVID J. MALAN: Smith, grazie. Quindi continuerò guardare Smith? ALAN ESTRADA: Oh, sì. No no no. Oh no. Questo è mio. DAVID J. MALAN: Oh, hai Smith. OK. ALAN ESTRADA: Sì, Smith ha ottenuto proprio qui. Scusate ragazzi. Ho pensato che Michael-- erano alla ricerca di Michael. Scusate. DAVID J. MALAN: Va bene. Va bene, ora siamo in Paccini e Figli. ALAN ESTRADA: Paccini e figli. DAVID J. MALAN: Solo tu e io siamo in su questo. OK. Dove siamo Mike Smith. Fabbro. ALAN ESTRADA: Smith. DAVID J. MALAN: Smith. Siamo in R per la spazzatura. ALAN ESTRADA: Rifiuti. Oh. Si tratta di andare a prendere un po '. [Ride] DAVID J. MALAN: Scarpe. Siamo in scarpe. ALAN ESTRADA: Ora stiamo gonna-- DAVID J. MALAN: Nizza. ALAN ESTRADA: Which-- [Ride] Oh, questo è grande. [Ride] DAVID J. MALAN: Va bene. ALAN ESTRADA: Oh, questo è buono. Non penso che ho intenzione di avere amici PSAT dopo questo. DAVID J. MALAN: Good. Sporting. ALAN ESTRADA: Sporting. Um, L, M, N, O, P. DAVID J. MALAN: OK. Quindi cerchiamo di distruggere questo a metà. Va bene. Questo finisce male comunque, perché Mike Smith non sarà nelle pagine gialle. ALAN ESTRADA: Aw. DAVID J. MALAN: No, va bene. Ma facciamo finta come lui è in questa pagina. Così ora, hai tagliuzzato il problema verso il basso ad una pagina, e abbiamo trovato Mike Smith. [INCORAGGIANTE] Bene grazie. OK. E 'stato straordinario. Ma era ancora più veloce di ricerca lineare, in cui si comincia a inizio del libro, e ci spostiamo il nostro modo da sinistra a destra, alla fine alla ricerca di Mike Smith. E così, se la rubrica telefonica aveva forse 1.000 pagine, forse ci sarebbe voluto noi 10 o giù di lì di pagina lacrime. Ma si può avere sfruttato toccato un presupposto Durante tutto questo, che vale a dire che la rubrica telefonica in anticipo era quello? PUBBLICO: Ordinato. DAVID J. MALAN: E 'ordinato. Destra? E 'in ordine alfabetico, in modo da che tutti questi nomi e numeri sono allineati dalla A di al Z di, e in ordine alfabetico in mezzo. Ma oggi, ci chiediamo ora la domanda, beh, come ha fatto Verizon o il telefono società lo fanno in quello stato? Perché è una cosa da sfruttare tale ipotesi, e quindi, risolvere un problema con un algoritmo più efficiente. Ma non abbiamo mai veramente ha chiesto in settimana a zero, beh, quanto costa Verizon o qualcun altro per ottenere che rubrica in modo ordinato? Destra? Non importa se guardando Mike Smith è super veloce, se si prende un anno per ordinare le pagine inizialmente. Destra? Si potrebbe anche solo vagliare attraverso una rubrica randomizzato, se sta andando essere super costoso a risolverlo. Quindi, se siamo in grado di avere un altro volontario. Diamo uno sguardo qui a come siamo arrivati ​​su up-- might-- come potremmo andare sull'ordinamento questi. E se la Giordania potrebbe effettivamente unirsi a noi qui sul palco. Andiamo per un attimo. Come ti chiami? CAROLINE: Caroline. DAVID J. MALAN: Caroline, andiamo su. E sarai unito da me e Giordania qui. Caroline, grazie. Tutto ok. Quindi quello che abbiamo qui per Caroline è di 26 azzurri libri che FAS utilizza per amministrare alcuni esami finali. Questi sono sempre difficili da trovare, ma quello che abbiamo fatto in anticipo è che abbiamo messo il nome di qualcuno sul fronte di ciascuno di questi, ma abbiamo mantenuto semplice da poi mettere i nomi completi. Così avremmo messo la persona con il nome L, D, J, B, tutto il percorso da A a Z, ma sono in ordine casuale. E così, se si farebbe, a parlare la vostra strada attraverso il problema, come si farlo, si può andare avanti e ordinare questi per noi, dalla A alla Z. PUBBLICO: OK, allora L è come, al centro. C sta cominciando. B. J prima di L. B, Q. DAVID J. MALAN: Mantenere questa pensato per un secondo. Perché altrimenti, questo è solo interessa a te, a me, e la Giordania. Ci siamo. PUBBLICO: [incomprensibile]. R. DAVID J. MALAN: OK. Che stai facendo? CAROLINE: M viene dopo O. DAVID J. MALAN: OK. CAROLINE: O. DAVID J. MALAN: O, Bene. CAROLINE: E. DAVID J. MALAN: E, F. Sì. CAROLINE: T, U, V David J. MALAN: V, T, U, V. Così sembra che sei making-- andare avanti. Sembra che si sta facendo una grande pila qui, e una specie di grande pila laggiù. Così la prima metà dell'alfabeto, seconda metà dell'alfabeto. OK. Bene. Tipo di dividere il problema in due. M, N, X. Già. CAROLINE: K. DAVID J. MALAN: OK. K. Quindi stai tipo di selezione una dopo l'altra, metterlo a destra oa sinistra, o Z sta succedendo pavimento. OK. CAROLINE: Z sta succedendo sul pavimento. DAVID J. MALAN: OK. Y sta sul pavimento. Ora possiamo mettere X. CAROLINE: G. DAVID J. MALAN: G andando a sinistra. S sta andando bene. Va bene, A sta andando fino in fondo a sinistra. CAROLINE: A, B, C, D. DAVID J. MALAN: Ora, bene. Abbiamo A, B, C W andare laggiù. Va bene, T. CAROLINE: H, I, J. DAVID J. MALAN: H, I, J. Good. CAROLINE: Nel centro, sto gonna-- DAVID J. MALAN: OK. Così ora, stiamo andando a tipo di unire questi vari pali. Quindi da A a C, poi vedo D, e E, e F, e G e H e I. piacevole. J, K. E poi, questo mucchio è a testa in giù, ma va bene. Certo. Siamo in grado di tagliare alcuni angoli. OK. E poi abbiamo bisogno di W, X, Y, Z. CAROLINE: Sì. DAVID J. MALAN: Eccellente. Quindi un grande grazie a Caroline per l'ordinamento questi. [INCORAGGIANTE] Grazie. Grazie mille. Così ora consideriamo per un attimo come Caroline è andato a fare che, e che cosa esattamente ci sono stati in grado a-- come erano in grado di risolvere il problema quando eravamo solo dato un sacco di input casuali. Beh, sembra che ci era un po 'di un sistema di lì? Destra. Così le lettere precedenti in alfabeto, lei era messa a sinistra, e la lettere successive dell'alfabeto, lei stava mettendo nel giusto. E non appena ha trovato alcune lettere prossimali, quelli che vanno a destra accanto all'altro, lei avrebbe messo quelle in ordine. E così abbiamo avuto tipo di questi piccoli mucchi di ingressi ordinati che si verificano. E così che è abbastanza simile a quello che la maggior parte di noi umani avrebbero fatto. Ci sarebbe una sorta di vagliare attraverso di essa, e ci piacerebbe sorta di avere un meccanismo. Ma potrebbe essere difficile da scrivere giù in una formula per sé. Sembrava un po 'più organico di quello. Quindi vediamo se possiamo ora legato il problema con un minor numero di ingressi. Invece di 26, diamo fare qualcosa di molto meno con solo dire, sette, dietro queste porte, per così dire. Ci sono solo sette numeri? E se l'obiettivo ora mano è quello di trovare un valore, vediamo come in modo efficiente siamo in grado di andare a fare questo. E vediamo se possiamo ora iniziare ad applicare alcuni numeri, o alcune formule con cui descrivere l'efficienza della nostra rubrica Algoritmo, il nostro algoritmo libro esame, e più in generale, la ricerca di informazioni. Quindi, per questo, mi permetta di andare avanti, e sul touch screen qui, mettere su un browser web che ha esattamente questi sette porte. E se avessimo potuto ottenere un altro volontariato a venire su qui, Ho messo queste stesse porte qui. Volontario rapido. Questo tra-- demo sono in corso di un sempre più veloce ora. Vieni giù. Come ti chiami? TREVOR: Trevor. DAVID J. MALAN: Trevor? Va bene, Trevor, vieni giù. Così Trevor si è offerto volontario qui per fare un problema simile, ma uno che è stretto nella portata, e che sta andando per permetterci di cercare di formalizzare ora il processo per ordinare questi numeri. Così Trevor, piacere di conoscerti. Così qui è un array, in modo da parlare, una lista di sette porte. Vai avanti e noi trovare il numero 50. E poi, dopo il fatto, raccontarci come lo avete trovato. Dovrebbe essere-- tutto bene. Sì, questo è quello qui? Uh Oh. OK. Si è scelto quello. Bene. E bene. Ora si è fatto clic che uno. E lasciate che vi dia il microfono, in modo da avere in un attimo. Andare avanti e fare clic sul della porta accanto che si intende. Si Bene. TREVOR: Posso deselezionare una porta? DAVID J. MALAN: No, non è possibile deselezionare. TREVOR: OK. Questo. DAVID J. MALAN: Dove vuoi andare? Quale? TREVOR: Quello. DAVID J. MALAN: No. TREVOR: OK. Questo. DAVID J. MALAN: Sì. Quello era buono. Tutto ok. Allora, qual è stato il tuo algoritmo o Procedura per fare questo, Trevor? TREVOR: Ho appena passato attraverso porte fino a quando ho trovato un 50. DAVID J. MALAN: OK. Ottimo algoritmo. Così va bene. Perché in effetti, se rivelo ciò che è dietro queste due porte, cosa troveremo qui è che abbiamo solo ingresso casuale. Così che era in realtà come buono come si potrebbe ottenere. E infatti, si ha meglio esaurientemente ricerca l'intero array, perché sarebbe stato davvero sfortunato se aveste colpire il numero 50 all'ultimo porta. Ma cosa succederebbe se invece ti ha dato una supposizione. Supponiamo che io sorta tutti queste porte intorno, in modo da avere il numeri ordinati questa volta, ma questa volta è in realtà un different-- questa volta, in realtà è ordinato per voi. E ora l'obiettivo a portata di mano è quello di colpire il numero 50. TREVOR: OK. DAVID J. MALAN: Che cosa è l'algoritmo sta per essere? TREVOR: Beh, se è ordinato, è sia in corso essere-- se più grande al più grande, decrescente, sarà il primo, o se è il contrario, sarà l'ultimo. Quindi mi limiterò a toccare questo porta, e quindi basta toccare l'ultima porta. DAVID J. MALAN: Eccellente. Tutto ok. Così abbiamo trovato il numero 50. Così, non appena si sapeva sono stati ordinati, abbiamo sono stati in grado di sfruttare questa ipotesi. Quindi sono troppo simili l'esempio rubrica telefonica. Non appena si hanno, anche con un piccolo problema come questo, gli ingressi pre-ordinati, possiamo effettivamente trovare il valore discutibilmente Più efficiente. E io non ti ho detto se era ordinati piccolo al grande, o grande a piccolo, e quindi era molto ragionevole iniziare ad un'estremità o dall'altra per scoprire che in realtà valore di destinazione. Quindi, grazie a Trevor pure. E io propose-- ben fatto. Abbiamo un po 'di clip, in realtà, che è tra i nostri momenti preferiti in CS50, per cui a volte queste demo non abbastanza andare secondo i piani. E infatti in questo momento, io tirato su l'interfaccia sbagliata con cui utilizzare il touch screen. Così che era colpa mia lì. Quindi, questo renderà per la clip del prossimo anno come motivo per cui stavo cliccando sul mio schermo. Ma diamo un rapido sguardo a quello che è successo l'anno scorso con Jay, che è venuto in su, molto come Trevor qui, volontariamente, e in questo breve filmato, vedrete come questa stessa demo non ha fatto abbastanza rivelano le stesse lezioni apprese. [RIPRODUZIONE VIDEO] -Tutti Io voglio fare ora è di trovare per me, e per noi, davvero, il numero 50 un passo alla volta. -il Numero 50? -il Numero 50. E si può rivelare ciò che è dietro ciascuna di queste porte semplicemente toccando con un dito. Accidenti. [Ride] [FINE RIPRODUZIONE] DAVID J. MALAN: Così che è andato molto bene. Quelli erano le porte non ordinati. E Jay, naturalmente, trovato tutto troppo in fretta. Trevor ha fatto un lavoro molto migliore in termini di un momento insegnabile, per così dire, in quest'anno prendendo più tempo per trovarlo. Certo, poi abbiamo dato Jay una seconda possibilità, per cui abbiamo ordinato le porte, proprio come abbiamo fatto per Trevor, e Trevor ha fatto super ben questo momento. Ma Jay ha fatto la metà rapidamente. [RIPRODUZIONE VIDEO] -Il Obiettivo ora è quello di anche noi trovare il numero 50, ma farlo algoritmicamente, e ci dicono come si sta andando su di esso. -OK. -E Se lo trovate, di mantenere il film. Se non lo trovate, si dà indietro. -man. -Oh! - [Incomprensibile] OK. Così sto andando a controllare le estremità prima per determinare se there's-- Oh. [Applausi] [FINE RIPRODUZIONE] DAVID J. MALAN: OK. Così l'ordinamento chiaramente porte porta ad una maggiore efficienza. E così, due volte più veloce è quello che volevo dire lì. E così Jay ha avuto fortuna entrambe le volte. E ha anche avuto fortuna in quell'ultima anno, ho ordinato alcuni dischi Blu-ray per dare realmente fuori. Mi dispiace di quest'anno, abbiamo non ha avuto la stessa, Trevor. Ma meglio ancora era qualche anno fa. E alcuni di voi potrebbe sapere questo compagno, Sean, che quando era in CS50, è stata contestata con l'esatta stesso problema, anche se in SD, come vedrete presto, back in the day. E troverete che non solo lui prendere un po 'più lungo di Jay, un po 'più lungo di Trevor, è stato in realtà questa meravigliosa opportunità di impegnarsi quasi tutti nel folla a la prezzo è giusto, incoraggiando lui trovare il numero che stavamo cercando. Andiamo. prendere una rapida occhiata. [RIPRODUZIONE VIDEO] -OK. Così il vostro compito qui, Sean, è il seguente. Ho nascosto dietro questi porte il numero sette. Ma nascosto in alcune di queste porte così sono altri numeri negativi. E il vostro obiettivo è quello di pensare di questa riga superiore di numeri come solo un array, o semplicemente sequenza di pezzi di carta con i numeri dietro di loro. E il vostro obiettivo è, utilizzando solo la parte superiore array di qui, mi troverete il numero sette. E stiamo andando poi a criticare come si fa a farlo. -Tutto ok. Noi -Trova il numero sette, per favore. No. Cinque, 19, 13. [Ride] Non è una domanda trabocchetto. Uno. [Ride] A questo punto, il punteggio non è molto bene, così si potrebbe anche andare avanti. Tre. [Ride] Andare avanti. Francamente, non posso fare a meno di chiedermi cosa stai ancora pensando, so-- [Ride] Solo la fila superiore, così Hai tre sinistra. Così mi trovare sette. [Ride] 17. Sette. [Applausi] Tutto ok. [FINE RIPRODUZIONE] DAVID J. MALAN: Così abbiamo potuto Guardate queste per tutto il giorno. E, naturalmente, alcuni dei demo di quest'anno forse sarà ora finire in prossimo Video anno pure. Così ora cerchiamo di realtà concentrarsi sugli algoritmi qui, e vedere se non possiamo ora inizia formalizzare come possiamo fare per ottenere i nostri dati in questo stato che è ordinato, così che alla fine, possiamo in realtà cercare in modo più efficiente. E anche se stiamo andando utilizzare piuttosto piccoli insiemi di dati, come l'otto numeri che avere qui sul bordo, in ultima analisi, queste stesse idee potevano applicare a 1.000 ingressi, un milione di ingressi, 4 miliardi ingressi, perché gli algoritmi stanno per essere fondamentalmente lo stesso. E così questo è il nostro ultimo opportunità per i volontari oggi, ma forse il più coinvolto, per il quale abbiamo bisogno di otto volontari a venire e noi a piedi attraverso la processo di smistamento quello che sarà presto essere su questi leggii qui. Permettetemi di iniziare di nuovo qui. Così uno nel verde turquoise-- è? Stai commettendo? Due. Vieni giù. OK. Tre. Quattro. Lasciate me-- OK, cinque. Sei stato nominato dal tuo amico. Sei, sette e otto. Vieni su. Tutto ok. Grazie mille. Vieni su. Vieni su. Tutto ok. Quindi quello che abbiamo qui-- e questo è tra i più difficili, dal momento che questo sarà necessario che si umorismo me per un po 'di tempo. Si deve essere il numero uno. Come ti chiami? ANNAN: Annan. DAVID J. MALAN: Annan. Davide. Come ti chiami? GIUSEPPE: Joseph. DAVID J. MALAN: Giuseppe, sei il numero due. SERENA: Serena, numero tre. Stefan, numero quattro. CYNTHIA: Cynthia. DAVID J. MALAN: Cynthia, numero cinque. [Incomprensibile] DAVID J. MALAN: [incomprensibile]. David, numero sei. MATT: Matt. DAVID J. MALAN: Matt numero sette. E? WAVERLY: Waverly. DAVID J. MALAN: Waverly, numero otto. Tutto ok. Se could-- whoops. Se tutto, come il tuo prima sfida, ci sono otto leggii qui di fronte al pubblico. Se si potesse mettere i numeri questi leggii in modo che siano allineati con il stessi numeri sul tabellone. Quindi fare voi stessi sembrano che mettere i numeri in questi musica sta qui. Ottimo finora. Eccellente. OK. Così ora, stiamo andando a chiedere il domanda in diversi modi. Come possiamo andare sull'ordinamento queste persone qui? Perché abbiamo avuto alcuni approcci in precedenza, per cui siamo stati tipo di fare due secchi diversi. E poi siamo stati in genere mettendo insieme le cose. Non appena abbiamo visto due numeri che apparteneva insieme, li abbiamo messi insieme. Due lettere che vanno insieme. Ma vediamo se siamo non può formalizzare questo, in modo da avere alla fine alcuni pseudo-codice si vuole, con cui è possibile risolvere questi problemi. Così ora, sto cercando fuori a questi numeri qui. E vedo un sacco di errori. In ultima analisi, voglio uno sulla sinistra e otto sulla destra. E così sto guardando questi due, quattro e due. E qual è il problema, ovviamente? Già. Così. Due viene ovviamente prima quattro, in modo da sapere che cosa? Permettetemi innanzitutto di prendere un approccio avido, se si vuole, molto problema come set tra-- se vi ricordate dal Standard Edition di Set problema Uno, dove ho appena risolvere localmente il problema che è proprio qui di fronte a me e vedere dove mi porta. OK. Così due e quattro, lasciami andare avanti e appena si scambiano due. Se si riesce a spostare fisicamente voi stessi e la vostra carta, Mi sembra di aver ottenuto la elencare in una condizione migliore. Ora, sono buone. Ho intenzione di andare avanti, quattro e sei, sembra buono. Non è un problema. Sei e otto, OK. Otto e uno, un altro problema. Perché ciò che è vero circa otto e uno? Uno viene prima delle otto, e così che cosa dobbiamo fare? Facciamo scambiano questi due. Uno e otto. E ora, ho intenzione di andare avanti. Ho intenzione di continuare a guardare avanti. E vediamo cosa succede. Otto e tre, di Certo, fuori uso. Facciamo swap. Otto e sette, naturalmente. Guasto. Facciamo swap. Otto e cinque, naturalmente, cerchiamo di swap. Tutto ok. Lista è ordinata. sì? OK, ovviamente non. Ma è un po 'meglio, giusto? Perché avviso quello che è successo. Ogni volta che abbiamo effettuato uno swap, una più piccola Numero tipo di percolato in questo modo, e un numero più grande percolato in questo modo, o faremo iniziare dicendo bolle al sinistra o verso destra gorgogliare. Ora, non è sufficiente, perché nel migliore dei casi un numero potrebbe si sono spostati uno spot in avanti, o nel peggiore dei casi, un numero potrebbe avere spostato più un punto. Così si sa che cosa, questo tipo di funzionato abbastanza bene finora. Vorrei solo provare di nuovo. Due e quattro, sono OK. Quattro e sei, sono OK. Sei e uno, fuori uso. Quindi cerchiamo di voi due swap. E ora, il problema del preavviso cominciando a diventare un po 'di nuovo meglio. Sei e tre, fuori uso. Diamo voi due swap. Sei e sette, sei buono. Sette e cinque, naturalmente, fuori ordine. Sette e otto, in ordine. E ora, potrei aver bisogno di fare questo un paio di volte. E infatti, pensare per voi stessi forse quante volte al massimo potrei camminare avanti e indietro? Torneremo a questo. Così due e quattro sono ancora OK. Quattro e uno, no. Quindi, andiamo swap. E ancora, notare visivamente uno è una specie di ribollimento a sinistra, dove dovrebbe essere. Quattro e tre swap. Quattro e sei. Sei e cinque swap. Sei e sette. Sette e otto sono buoni. Bene. Stiamo ottenendo ancora meglio. Quindi cerchiamo di vedere. Ora, abbiamo due e uno. Naturalmente, scambiare. Due e tre, tre e quattro, quattro e cinque, sei e sette, sette e otto. Bene. E sai una cosa? Perché ho fatto un cambio lì, mi permetta di fare un controllo di integrità. Lasciami andare fino in fondo torna all'inizio. OK. Uno, two-- yup, vedi? Qualcosa non andava. Tre, quattro, cinque, sei, sette, otto. E in questo ultimo passo, sono a vostro agio con la mia ora sostenendo che è ordinato? OK. Visivamente, questo è assolutamente vero. Ma funzionalmente, cosa ha anche appena capita in tale ultimo passo che permette per confermare che questa lista è davvero ordinati? Che cosa ho fatto o non fare questo ultimo passo? PUBBLICO: ci sono stati cambiamenti. DAVID J. MALAN: Siamo spiacenti? PUBBLICO: Nessuna modifica. DAVID J. MALAN: Non ci sono stati cambiamenti. Quindi sarebbe stupido da parte mia fare di nuovo quello stesso algoritmo se non ho fatto alcun cambia la prima volta. E lo Stato non è cambiata. Certo, io non ho intenzione di fare Eventuali modifiche per la seconda volta. E così, è sicuro ora per dire, elenco è ordinato. E in effetti, questo è ora qualcosa che faremo in generale chiamata bubble sort, per cui due a due, correggete ancora errori, e ancora, e ancora, e si andare avanti e indietro, e avanti e indietro, fino a che non rendere tali swap, a quel punto si può essere sicuri, sì, mi finito fissare tutti gli errori. Cerchiamo di reimpostare e cercare un altro approccio. Se voi ragazzi poteste tornare in l'ordine che fosse un momento fa, che si presentava così. Ora, prendiamo un approccio un po 'di più come il libro esame, per cui siamo stati costantemente selezionando la lettera dell'alfabeto che tipo di volevamo a che fare con il prossimo. Forse era un alto lettera, come A, o un basso lettera Z. Così tutti sono nuovo in questo ordine. E ora mi permetta di fare questo. Vediamo so di avere otto numeri qui. Ho intenzione di andare avanti e appena deliberatamente selezionare gli elementi più piccoli. Destra? Questo sembra troppo intuitiva. Perché non trovo il più piccolo elemento, messo a cui appartiene, quindi ottenere il successivo elemento più piccolo, mettere a cui appartiene, e sufficiente ripetere. Perché intuitivamente, che dovrebbe funzionare anche. Così quattro, che è un numero piuttosto piccolo. Io vado a ricordare dove questo è. Apetta un minuto. Due è più piccolo. Permettetemi ora di ricordare dove due è, e dimenticare quattro. Ce ne occuperemo più avanti. Sei, non mi interessa. Otto, io non sono interessato a. Uno è il mio nuovo numero di piccole dimensioni. Quindi ho intenzione di ricordare dove si è. Tre, non è interessato. Sette, non è interessato. Cinque, non è interessato. Così, senza cadere il palco quest'anno, Vado a prendere il numero tra-- e ciò che è stato di nuovo il tuo nome? ANNAN: Annan. DAVID J. MALAN: Annan. E se tu potessi venire con me a l'inizio della lista, mettiamo dove si appartiene. Unfortunately-- come ti chiami? STEFAN: Stefan. DAVID J. MALAN: Stefan è in mezzo. Quindi, prima di Stefan risolve questo problema, che cosa dobbiamo fare? Che cosa facciamo con Stefan? PUBBLICO: [incomprensibile]. DAVID J. MALAN: OK. Così potremmo farlo. Potremmo sorta di prendere Stefan e la sua quattro, e appena messo in una variabile e tenere su di esso per una certa quantità di tempo, rendendo così spazio per il numero uno. E questo non è male. Potrei suggerire, perché non fare abbiamo appena messo Stefan qui? Perché questo potrebbe violare uno delle idee che abbiamo iniziato parlando l'ultima volta, la settimana scorsa? Sì? PUBBLICO: [incomprensibile]. DAVID J. MALAN: Non c'è nessun indice per esso. Se pensate a questo, infatti, come un serie, questo è come uno negativo, quindi non c'è memoria realtà qui se questo è davvero un array, come abbiamo dichiarato la scorsa settimana a lezione. Quindi non dobbiamo farlo. Possiamo memorizzare in una variabile. O sai una cosa? Ho sentito qualcuno altro suggerire. Che altro potremmo fare con Stefan? Perché noi non solo lo sfrattare e lo ha messo su dove il numero uno era. Quindi, se volete andare là. E infatti, questo è un soluzione piuttosto buona. Ora, da un lato, ho genere di fatto il problema peggiore. Quattro è ora più lontana da dove dovrebbe essere. Dovrebbe essere verso questo mezzo. Ma sai cosa? Che avrebbe potuto essere la sfortuna. Forse numero otto era qui. E così, forse avremmo hanno ottenuto fortunato, e spinto otto più vicini alla fine. Così, alla fine della giornata, E 'sorta di tutte le medie fuori. Non abbiamo bisogno di preoccuparsi quattro. Tutto quello che interessa ora è selezionando l'elemento più piccolo. E ora, che cosa ho intenzione di fare è dimenticare il numero uno in modo permanente, perché so che il lista dietro di me è ora ordinato. Così la mia lista era già formato a otto. Ora, è di dimensioni sette. Quindi il mio problema è sempre più piccolo, seppur linearmente. Così ora, ho intenzione di selezionare il corrente elemento più piccolo, due. Sei, otto, quattro, tre, sette, cinque. Questo è stato l'elemento più piccolo. Così che cosa sono io intenzione di fare with-- quello che era di nuovo il tuo nome? GIUSEPPE: Joseph. DAVID J. MALAN: Giuseppe? Stiamo per lasciare Giuseppe a posto. Ora, ho intenzione di far finta che questi ragazzi are-- bene, So che questi due sono già ordinati. Passiamo ora concentriamoci sul resto della lista. Sei è la corrente più piccolo. Otto è più grande. Quattro è ora il più piccolo corrente. Tre è ora il più piccolo corrente. E così ora, ho intenzione di selezionare tre, che è-- cosa di nuovo il tuo nome? SERENA: Serena. DAVID J. MALAN: Serena, se potessi afferrare il vostro numero e di swap with-- Kalsang: Kalsang. DAVID J. MALAN: Kalsang. Vieni indietro, e siamo andare per scambiare quei due. E ora, mettiamo questo il pilota automatico. Ho intenzione di andare e lasciare a voi ragazzi per selezionare i prossimi elementi più piccoli. Dun, dun, dun, dun. Numero quattro, cosa si deve fare? Eccellente. Ora, ho intenzione di fare un altro passo. Dun, dun, dun, dun. Vedo cinque è il immediatamente inferiore. Ora, sto andando fare un altro passaggio. Dun, dun, dun, dun. Sei è il più piccolo. Bene. Sette è il più piccolo. Nessun cambiamento. Otto è il più piccolo. Fatto. Quindi quello che abbiamo appena fatto da iterativamente selezionando un elemento dopo l'altro è implementare qualcosa che siamo andare a formalizzare la selezione sorta. Ed è forse anche semplice da spiegare, in che letteralmente tutto quello che voglia di fare è mantenere andando avanti e indietro attraverso la lista la selezione, il prossimo elemento più piccolo, fino a quando il gioco è fatto. Quindi è ancora più semplice, forse intuitivamente, rispetto allo scorso. Proviamo un ultimo uno. Se voi ragazzi poteste ripristinare voi nelle seguenti posizioni un'ultima volta, vediamo se non possiamo ora formalizzare un altro approccio. In realtà, sarebbe qualcuno là fuori piace proporre in quale altro modo si potrebbe andare a fare questo? Senza tirare fuori parole d'ordine o tipo di risposte che sono già noti, solo intuitivamente, cosa potevamo fare? PUBBLICO: [incomprensibile]. DAVID J. MALAN: Sì. Quindi c'è qualche grande intuizione lì. Buone cose sembrano accadere finora in informatica quando ci dividiamo e conquistare il problema della divisione a metà e metà e metà. E così in effetti, abbiamo potrebbe iniziare a farlo. E infatti, che sta per essere, noi provvederemo vedere, uno dei nostri migliori soluzioni ancora. Ma torniamo a quel poco tempo. In realtà, stiamo andando a fare che un po 'più tardi questa settimana. Che altro potremmo fare per risolvere questo problema? Quindi, tutti qui sono in ordine apparentemente casuale. Sai cosa? Invece di andare avanti e indietro, avanti e indietro, avanti e indietro ogni volta, questo si sente come Sto facendo un sacco di camminare. Perché non appena comincio a l'inizio della lista, e appena messo quattro a cui appartiene? Permettetemi quindi di presumo per il momento che la mia lista è solo questo primo elemento. È quattro ordinati in questo momento nel tempo, se tutto mi interessa è tutto qui? Questa è una sorta di banalmente vero, giusto? Come l'elenco contenente un numero, e che il numero quattro è ovviamente ordinato. Quindi lasciatemi stipula le che questo elenco è ordinato. Ma ora ho il resto di questa lista. Così ora, ho incontrato due. Da dove viene, ovviamente, due appartenere rispetto a quattro? Prima di quattro. Cosa posso fare qui? Mi ricordi come ti chiami? GIUSEPPE: Joseph. DAVID J. MALAN: Giuseppe, se si potesse fare un passo indietro per un attimo con il vostro numero. E ora che cosa dovrebbe Stefan fare qui? Spostiamo Stefan qui. E ora, lascia Giuseppe venire qui. E ora, mi permetta di sostengo che tutto qui è ordinato. Quindi, risultato simile, ma una fondamentalmente diverso approccio. Non ho nemmeno guardato cosa c'è là sotto. Continuo a prendere gli elementi come sono consegnati a me, e trattare con loro. Così ora, vedo numero sei. Da dove viene il numero sei appartiene? Abbiamo due, quattro, sei. Esattamente dove si trova in questo momento. Quindi lasciamo che da sola, e ora affermare che questa parte della lista è ora ordinato. E così, questo si sente fondamentalmente diversa, in quanto io sono solo si muove attraverso la lista qui lineare, e sto mai raddoppio indietro. Sì. Tutto ok. Così otto, dove appartieni? Giusto qui. Perfetto. Così ora, uno. Uh Oh. Questo si sente come se fosse sta per essere costoso. Ora, nell'algoritmo precedente, Ho appena scambiato persone. Quindi perché lo mettere tutta la strada a all'inizio, ma poi si trasferisce Giuseppe. Ma se mi muovo Joseph, ora ciò che sta per essere sbagliato? Ora, ho una sorta di undone-- ho fatto un passo in avanti e poi un passo indietro, perché ora Joseph sarebbe fuori ordine. Quindi cerchiamo di fare questo. Se potessi prendere il numero uno e un passo indietro per un attimo. Come possiamo put-- cosa Era di nuovo il tuo nome? ANNAN: Annan. DAVID J. MALAN: Annan a posto? Che cosa deve accadere per quanto riguarda a due, quattro, sei, otto e? Tutti hanno bisogno di cambiare. Quindi, se otto vorrebbe spostare prima, poi sei, poi quattro, poi due. E poi Annan, se aveste piacerebbe venire qui, bene. Ma qui, abbiamo appena tipo di pagato un prezzo in un punto diverso nell'algoritmo. Mentre l'ultima volta con la selezione tipo, e anche bubble sort, Sto camminando avanti e indietro, avanti e indietro, che è certamente sommando tempo-saggio, e letteralmente graduale. Insertion sort, in un primo momento sguardo, sembra che sia super-intelligente, nel senso che io sono solo facendo lento, progressi incrementali, ma io non ho intenzione questo avanti e indietro. Ma se qualcuno è davvero fuori ordine, avviso tutto il lavoro che ho appena avuto a che fare. Ho dovuto spostare metà della lista solo per fare spazio a numero uno. Quindi è la stessa quantità del lavoro finora essa sente, solo un diverso tipo di lavoro. Continuiamo. Così ora sappiamo che tutti tra uno e otto sono allineati. Qui, ho numero tre. Se vi piace prendere numero tre, un passo indietro uno. E che voi ragazzi dovete fare? Yep. Ecco, questo è un altro, due, tre passi. Tre unità di tempo che proprio costano me, in modo che tre ora posso andare bene. Infine, sette. Andiamo avanti e avere si prende un passo indietro. Questo è solo andare a costarci una unità di tempo, ma questo è OK. E ora, cinque di andare a essere un po 'più costoso. Se vuoi fare un passo indietro. Dobbiamo muoverci otto, e sette, e sei. E poi ognuno è ora ordinato. Quindi una grande mano per i nostri volontari qui. Grazie mille. [Applausi] Grazie a tutti. Grazie a tutti. Vediamo quindi ora solo come costosa tutto questo è stato. Consideriamo forse il più semplice di questi, bolla sorta. E io dico semplice, solo perché si può risolvere semplicemente avidamente risolvere il problema a coppie qui. Risolvere il problema a coppie qui, ancora e ancora e ancora, ripetendo come molti volte è effettivamente necessario. Così si scopre che con una bolla di sorta, beh, quanti passi devo prendere su il primo passaggio di tale algoritmo? Potrei take-- andiamo see-- uno, due, tre, quattro, cinque, sei, sette. E c'è otto elementi qui. Quindi è come se n meno 1 passi ottenere dall'inizio della lista alla fine della lista. Ma con selezione tipo, ricordo che io sono selezionando ripetutamente gli elementi e ancora una volta che è più piccolo, Sto mettendo a posto, ma poi io non sono guardando dietro di me di nuovo. Quindi penso che sia un po 'più chiaro allora che la prima volta, potrei prendere ogni n meno 1 passi per trovare l'elemento più piccolo. Poi li ho messi a posto, e io sfrattare chiunque fosse qui in passato. Ma allora non c'è bisogno di continuare a guardare a questo elemento, perché so che è già il più piccolo. Così ora, posso guardare solo sette elementi, poi sei elementi, poi cinque elementi, poi quattro elementi. E così matematicamente, se n è il numero di elementi o numeri che abbiamo iniziato con, che potete immaginare che questo è lo stesso come n meno 1, più n meno 2 punti, più n meno 3 punti, inclusa n meno 4 passaggi, tutte le fino in fondo a un solo passo. E sono il mio ultimo persona. E se vi ricordate che un sacco di stats libri o libri di matematica avere quelle formule sul cartonato schiena o di fronte a loro, si scopre che questa serie può essere espresso più semplicemente come n volte n meno 1 su 2. E va bene se questo non è in prima linea nella tua mente. Ma questo è vero. Questo è solo un modo più semplice di scriverlo. E poi se si pensa torna a scuola elementare, quando si può lanciare moltiplicando cose fuori, questo naturalmente, è solo n squadrato minus n diviso 2. Tutto quello che ho fatto è espandere le espressioni lì. E quindi cerchiamo di riscrivere questo un po 'diverso. Questo è n al quadrato diviso per 2 meno n / 2. Quindi, di nuovo, io sono solo tipo di applicazione alcuni aritmetica governa lì. Ma si noti che ora il più grande termine in questa espressione, per così dire, è che n quadrato. Quindi sì, è n squared diviso 2, minus n / 2. Ma in generale, se n è sarà un grande valore, Ho intenzione di affermare che n quadrato sta per essere il fattore dominante. E 'solo andando essere un collaboratore più grande il numero di passi di n / 2. Così che cosa voglio dire con questo? Proviamo un semplice esempio, anche anche se la matematica diventa un po 'grande. Quindi supponiamo abbiamo avuto 1 milione di persone sul palco, o 1 milione di cose che vogliamo risolvere. Facciamo collegare un milione in esattamente quella formula per vedere quanti passi ci vuole totale per ordinare un milione di elementi utilizzando per esempio, selection sort. Così avremmo la stessa formula di prima. Mi piacerebbe inserisco un milione, in modo che ricevo un milione al quadrato diviso per 2, meno un milione diviso 2. Se lo faccio matematica in anticipo qui, abbiamo 500 miliardi meno 500.000, che ci dà 499.999.500.000, che è maledettamente grande. Infatti, se si confrontano ora 499 miliardi, 999 milioni, 500.000 contro il nostro valore originale, 500 miliardi, è così dannatamente vicino. Destra? n squadrato diviso per 2 dà noi-- o meglio, n squared diviso 2 ci ha dato 500 miliardi. Che è maledettamente vicino a 499.999.500.000, vale a dire sottraendo via 500.000, o più in generale, sottraendo off n al quadrato, non è un grosso problema. Il n quadrato rende questi numero cresce veramente veloce. Ora, questo è solo importante nella misura in cui come noi, come gli informatici, sono generalmente non andare a prendersi cura tanto circa le sfumature di queste formule e esattamente ciò che il risposte precise sono. Ci interessa solo che, sai cosa? Alla fine della giornata, questa formula è dell'ordine di n quadrato. Sì, stiamo dividendo per 2 in là. Sì, stiamo sottraendo off n meno 2. Ma alla fine della giornata, il termine che ci fa male e ci costa molto un sacco di passi è quel termine quadrato. E così quello che un informatico sta per fare in generale è ignorare tutti coloro termini di ordine più piccoli, e basta guardare quello che contribuisce maggiormente al costo. E questo è bello, perché possiamo ora parla in modo molto maggiore generalità di algoritmi, e in grado di confrontarli. E il fatto che io sono usando questo O è intenzionale. Quando dico sull'ordine di, io sono specificamente riferendosi a qualcosa chiamato grande O. E grande O è una notazione che un computer scienziato usa per descrivere un limite superiore su qualcosa. Quindi, se si dice che un algoritmo è in grande O di n al quadrato, come ho proposto solo un poco fa, che i mezzi che in termini di funzionamento tempo o la sua efficienza, prende sull'ordine n di passi quadrato. Forse di più, forse meno. Ma è dell'ordine di n quadrato. E questo è il limite superiore. Non sarà più doloroso di quello. Non sarà n cubetti, o 2 al n, o qualcosa di molto più grande. Questo è un limite superiore su qualunque che il costo è. Quindi, dato che, diciamo prendere in considerazione solo alcuni esempi. E questo è solo un elenco finito tempi di funzionamento di molto comuni per algoritmi che è destinata ad essere illustrativo di alcune cose che abbiamo già visto. Così, per esempio, nel caso di selezione tipo, quello che sto sostenendo qui è in esecuzione che la selezione di genere tempo è dell'ordine di n quadrato. Nel peggiore dei casi, ho intenzione di avere un sacco di numeri casuali qui. E come abbiamo visto matematicamente, se io continuo a camminare l'elenco, attraverso la lista, la selezione del immediatamente inferiore ripetutamente elemento, se in realtà scrivere tutti i passaggi Sto prendendo come ho proposto formulaically prima, è dell'ordine di n quadrata passi che sto prendendo. E si scopre che bolla ordinamento e insertion sort sono altrettanto lento nel caso peggiore. Si consideri, ad esempio, insertion sort, l'ultimo algoritmo ci siamo occupati, che ha avuto Osserviamo l'elemento, e poi inserirla in cui essa appartiene. E poi abbiamo guardato l'elemento successivo, ed inserito in cui essa appartiene. Quindi prendere in considerazione lo scenario migliore possibile. Supponiamo che io avevo i miei volontari in fila letteralmente come questo, da uno a otto, già ordinati. Quanti passi è insertion sort andando a prendere per ordinare otto persone, se arrivano sul palco cercando in questo modo? Otto persone già ordinati. E io uso insertion sort. Quest'ultima degli algoritmi. Bene, rivivere veloce reale. Quindi, se mi metto qui, ne vedo uno. Dove si appartiene? Appartiene proprio qui. Vedo due. Dov'è due appartengono? Giusto qui. Vedo tre. Dov'è tre appartengono? Giusto qui. Vedo quattro. Giusto qui. Cinque, sei, sette, otto. Non c'è motivo di ripetermi. E così, quanti passi è che in termini di n? È nell'ordine di n passi, giusto? n meno 1. Ma ho preso una serie lineare di di passi, e ora ho finito. Ecco, questo è il caso migliore, però. Che cosa circa il caso peggiore? Che otto erano là, e sette erano laggiù, e uno e due erano qui, così che l'elenco fosse veramente invertito? Ebbene, che cosa succede davvero se questo è il numero? E faremo solo un paio di esempi. Che cosa succede se, infatti, il numero otto è qui, e le urla number--. Che importa se, in effetti, il numero di otto è tutto fin qui, e sto usando insertion sort? OK. Io rivendico al momento è a posto. Ma ora, da dove viene seven-- sette va? Naturalmente, va qui. Quindi devo passare otto più di un posto. Ora sei, dove va a finire? Bene, tutto bene. Ora, devo passare otto sopra un luogo, e sette su un luogo, e poi mi plop giù sei. Così la prima volta, essa costo me un passo per sistemare le cose, poi mi è costato due passi per sistemare le cose. Quanti passi è andando a prendere per risolvere cose da mettere cinque nel posto giusto? Tre. Perché ora devo spostare uno, due, tre. Quanti passi sta andando a prendere di mettere quattro al posto giusto? 4 più 5, più 6, più 7. E così è matematicamente identico a quello che abbiamo descritto per la selezione sorta. Abbiamo questa serie questo è solo l'aumento. 1 più 2 più 3 più 4, o, al contrario, 7 più 6 oltre 5 più 4 aggiunge per oggi fini per l'ordine di n al quadrato. Permettetemi quindi di stipula le anche che bubble sort è anche n al quadrato. Perché con bubble sort, ogni volta che vado attraverso la lista, Sto prendendo approssimativamente quanti passi? Ogni volta che ho letteralmente a piedi da lì a là? Circa n passi. Ma quante volte potrei bisogno di passare attraverso la lista? Beh, più o meno il tempo n. Forse n meno 1, ma circa n volte. Beh, perché? Bene, con bubble sort, se si parte con bubble sort, con l'elenco nella peggiore possibile situazione, che è ancora completamente al contrario, che cosa succederà? Vado attraverso la lista, e il numero di uno appartiene tutto il modo là. Ma con bubble sort, fino a che punto si fa a passare il mio primo passaggio attraverso la lista? Quanti punti si procura più vicino al posto giusto? Solo uno. Quindi, se si tipo di ragione attraverso questo, ogni volta attraverso questo algoritmo, Che prendono circa n passi di David. Ma come molti passi l'elenco è andando a prendere per uno a bolla a sinistra cui appartiene? Ha avuto modo di muoversi come, n spazi in questo modo. Quindi, solo per fare l'ordinamento della lista, Devo camminare avanti e indietro n volte. E ogni volta, io sono guardando n elementi. Quindi, fare le cose n n volte su l'ordine di n quadrato. Ora, vedremo in qualche dei corti che sono incorporati in prossimo problema del CS50 set, un altro approccio a questi, ma per ora, diciamo solo in considerazione altre volte in esecuzione, soprattutto se quelli smistamento prendono un po 'di tempo per affondare dentro. Che cosa è un algoritmo che abbiamo visto già che assume dell'ordine di n passi? Quello che dovrebbe adottare una serie lineare di di passi che abbiamo visto fino ad ora? Che cos'è? La ricerca elenco telefonico. Il primo algoritmo. Destra? Dove siamo linearmente la ricerca di Mike Smith? Davvero. Da settimane a zero, quando ho iniziato girando una pagina alla volta, e ho anche detto che era una specie sensazione di un algoritmo lineare, e abbiamo avuto quella foto sulla scheda con la linea rossa retta e il giallo dritto linea, quelli erano davvero algoritmi che sono in grande O di n. Poiché trovare Mike Smith in un telefono libro di pagine n, nel caso peggiore, me n passi potrebbe prendere. Che cosa circa la presa di presenza? Uno due tre quattro cinque sei. Qual è il tempo di esecuzione di questo algoritmo per prendere la partecipazione? Big O di n, perché in teoria I devono puntare tutti nella stanza. Ora, come un a parte, per quanto riguarda il altro ottimizzazione di settimana pari a zero? Due, quattro, sei, otto, 10, 12. Uno scienziato di computer sarebbe realizzare, aspetta un minuto, questo è l'ordine di n diviso da due fasi. Destra? Perché sto facendo due persone alla volta. Ma stiamo andando a ignorare quei termini di ordine inferiore, e stiamo solo andando a buttare via la divisione per 2, e dire, grande O di n per tale algoritmo pure. Che dire di questa? Ci salteremo su alcuni di questi, ma cosa è un algoritmo che fosse registro di n? Che ha preso circa il log n passi? Il divide et impera. Esattamente. Come la rubrica esempio Settimana zero e prima di oggi, dove abbiamo diviso il problema ancora e ancora e ancora. Abbiamo disegnato sul tabellone a settimana zero come una linea verde curva, e abbiamo detto che giorno era un algoritmo logaritmica. E in effetti, il numero di passi che prende per eseguire divide et impera, o ricerca binaria come inizieremo definendolo, come nella rubrica telefonica, è dell'ordine di log e gradini. E questo è un po 'di uno strano. Che cosa fa un passo, o più specificamente un numero costante di passi? Forse è a due, forse è tre, ma uno scienziato informatico solo semplifica come grande O di 1, un numero costante di passi. Che cosa è qualcosa che si potrebbe fare che prende un numero costante di passi? Qual è il tempo di esecuzione di applausi? Tempo costante. Destra? Come, che cosa è il tempo di esecuzione fare qualsiasi cosa che richiede un solo operazione, come stampare F Ciao Mondo. Che potrebbe dire di essere costante di tempo, a meno che meno caso angolo con stampa F, quello che potrebbe essere il tempo di esecuzione di stampa F effettivamente essere? E perché? Qual è la misura n in quel caso? PUBBLICO: [incomprensibile]. DAVID J. MALAN: Esattamente. Il numero di caratteri vogliamo stampare. Quindi è molto sensibili al contesto. Oggi, ci siamo concentrati molto su lettere e numeri qui sul tabellone. Ma potrebbe anche essere caratteri in una stringa effettiva. Così si scopre c'è un altro provvedimento che inizierà preoccuparsi, e questo è il contrario di grande O, per così dire. Questa è la notazione omega. Mentre grande O vuol dire che cosa è, il limite superiore il tempo di esecuzione? Al massimo, quanto tempo potrebbe prendere qualcosa? Omega-- dispiace questo continua a venire up-- è l'opposto di quello, per cui si tratta di un limite inferiore al quantità di tempo qualcosa potrebbe prendere. Così. per esempio, che cosa è un algoritmo che prende passi sempre n quadrati? Ebbene, uno degli algoritmi che abbiamo visto oggi, infatti, potrebbe essere quello. Selection sort. Selezione una specie abbastanza stupido. Anche se il algorithm-- dispiace, anche se l'array è già ordinato, selection sort sta per tenere a ripercorrere la lista per assicurarsi che ha il più piccolo elemento ancora e ancora e ancora. E anche se gli esseri umani nel pubblico sa che, aspetta un minuto, hai già superato il elemento più piccolo, il computer non sa che fino a quando non appare tutto il percorso attraverso la lista. Analogamente, un limite inferiore che potrebbe anche essere presa in considerazione potrebbe essere tempo lineare. Quanto tempo ci vuole per Elementi tipo n nel migliore caso usando qualcosa come bubble sort? Supponiamo che la vostra lista è già ordinato. Abbiamo detto bubble sort assume l'ordine di n passi quadrato. Ma cosa succede se è già ordinato? Che cosa succede se ti rendi conto dopo un passaggio attraverso l'array che hai fatto non swap? Avete bisogno di continuare a fare più passaggi? No. Quindi un limite inferiore bubble sort potrebbe dirsi lineare. Omega di n. E possiamo guardare altri di questi. Quindi, diamo un rapido sguardo a solo una visualizzazione qui per vedere come queste si distinguono. Ho intenzione di andare giù qui in questo Pagina che è disponibile sul sito web di C50, ma sarà un dolore per arrivare a lavorare, dato che utilizza una tecnologia chiamata Applet Java, che è una in gran parte non supportata in questi giorni, almeno da Chrome e alcuni altri. E lasciatemi andare avanti e accelerare l'operazione e spiegare cosa sta succedendo. Questa è una dimostrazione di bolla tipo, il primo algoritmo che abbiamo guardato. Ed è una visualizzazione dal fatto che ciascun di queste barre rappresenta un numero. Più grande è il bar, il più grande è il numero. Più piccolo è il bar, minore è il numero. E che cosa si può vedere visivamente, anche anche se questo sta andando super veloce, è che la barra rossa è come me, camminare avanti e indietro, che fissa i problemi. Si può vedere che gli elementi più grandi sono infatti ribolle a destra, e gli elementi più piccoli sono gorgogliare verso sinistra. E qui, se si effettivamente guardare più da vicino, possiamo effettivamente contare il numero di confronti e swap che sono stati fatti. Ma invece, diamo un'occhiata al secondo algoritmo abbiamo guardato in precedenza con il nostro volontari, selezione di ordinamento. Visivamente, ha un effetto molto diverso. Ma è, ancora una volta, molto intuitivo, in che continuiamo a selezionare quello immediatamente inferiore elemento, e abbiamo ottenuto un po 'di fortuna. Che sentiva fondamentalmente più veloce. Ma se ci siamo imbattuti di nuovo e di nuovo e di nuovo con un sacco di input, ci piacerebbe vedere che è davvero ancora in grande O di n al quadrato. Facciamo un ultimo uno qui, insertion sort, che era il terzo algoritmo abbiamo guardato, e richiamo che questo occupa della Elementi come li incontra, Ma poi forse turni le cose per fare spazio, l'inserimento di elementi a cui appartengono. E anche questo finisce per dare il risultato finale. Ora tutti e tre questi sentivo abbastanza veloce. E infatti, io li imbattuto in un buon clip. Ma fondamentalmente, sono tutti piuttosto orribile, ad essere onesti. Tutti questi algoritmi finora che vengono eseguiti in grande O di n al quadrato prendere un po 'di tempo di esecuzione alla fine. E infatti, possiamo vedere e sentire questo, infine, se mi tiro su questa terza e ultima demo. Questa è un'altra visualizzazione che sta andando per mostrare bubble sort a sinistra, selezione sorta nel mezzo, e qualcosa, come uno dei nostri mano solleva in precedenza suggerito, merge sort sulla destra. Un divide et impera strategia sulla destra. E questo è, infatti, ciò che siamo andando a guardare il Mercoledì. Ma andiamo tempo queste per l'esecuzione in parallelo. È approssimativamente lo stesso numero di elementi, il tutto in esecuzione allo stesso tempo. Bubble sort vs selezione sorta vs merge sort. Ora, stanno tutti in esecuzione in teoria, allo stesso tempo. La CPU è in esecuzione al la stessa velocità, ma può sentire che noia questo è molto rapidamente sta per diventare, e quanto velocemente quando iniettiamo un po 'di settimane Gli algoritmi di zero può abbiamo accelerare le cose. E ora confrontiamo questi in un ultimo modulo. Ho intenzione di andare avanti Sito web CS50, dove abbiamo questo ultimo anello per oggi, dove qualcuno su internet gentilmente messo insieme un video che cattura ciò che diverso ordinamento algoritmi suonano come. Questo è insertion sort. [SEGNALE ACUSTICO] Per cui si sta applicando una frequenza in base all'altezza del bar bar. Questo è il Bubble sort. [ACUSTICO Warped] Prossimamente è-- venire accanto selezione è-- sorta, dove ancora una volta, stiamo selezionando il successivo elemento più piccolo, e possiamo vederlo crescere da sinistra a destra. Merge sorta, il nostro vincitore finora oggi. Notate come è dividere le cose in [incomprensibile] a metà e quarti. Sorta Gnome, che non abbiamo ha parlato, e crea visivamente e audally un po 'di forma e suono diverso. Andando avanti e indietro, pulire le cose. Verificate anche heapsort sul sito web di questo tipo. E questo è tutto. Ci vediamo la prossima volta. [Whooshing E MUSICA]