>> [MUSIC PLAYING]
DAVID MALAN: Va bene.
Va bene, bentornato.
Quindi questo è Settimana 4, l'inizio della stessa, già.
E vi ricordate che la scorsa settimana, abbiamo messo codificare a parte solo per un po '
e abbiamo iniziato a parlare un po 'di più di alto livello, di cose come
ricerca e l'ordinamento, che però le idee un po 'semplici, sono
rappresentativo di una classe di problemi si inizierà a risolvere in particolare
come si inizia a pensare finale progetti e soluzioni interessanti che si
potrebbe avere a problemi reali.
Ora bubble sort è stato uno dei più semplici tali algoritmi ed esso
lavorato avendo questi piccoli numeri in un elenco o in una matrice di tipo
bolla la loro strada fino alla cima, e il grandi numeri spostano la loro strada verso il basso per
la fine di quella lista.
>> E ricordiamo che potremmo visualizzare bubble sort un po '
qualcosa di simile a questo.
Quindi, mi permetta di andare avanti e fare clic sul pulsante Start.
Ho preselezionati bubble sort.
E se vi ricordate che il blu più alto linee rappresentano grandi numeri, piccolo
le linee blu rappresentano piccoli numeri, come passiamo attraverso questo nuovo e di nuovo e
nuovamente, confrontando due barre adiacenti altro in rosso, stiamo andando a scambiare la
più grande e il più piccolo, se sono fuori uso.
>> Quindi questo sarà andare avanti e andare avanti e andare su, e vedrete che il più grande
elementi stanno facendo la loro strada verso il destra, e gli elementi più piccoli sono
facendosi largo a sinistra.
Ma abbiamo cominciato a quantificare l'efficienza, la
qualità di questo algoritmo.
E abbiamo detto che nel peggiore caso, questo algoritmo ha preso
approssimativamente quanti passi?
>> Così n quadrato.
E che cosa era n?
>> AUDIENCE: numero di elementi.
>> DAVID MALAN: Quindi è stata la n numero di elementi.
E così lo faremo spesso.
Ogni volta che vogliamo parlare della dimensione di un problema o la dimensione di un
ingresso, o la quantità di tempo necessario per produrre un output, ci limiteremo a
qualunque sia generalizzata l'ingresso è come n.
Quindi torna alla Settimana 0, le pagine del numero nella rubrica era n.
Il numero di studenti nella stanza è stata di n.
Quindi anche qui, stiamo seguendo quel modello.
>> Ora n quadrato non è particolarmente veloce, quindi abbiamo cercato di fare di meglio.
E così abbiamo guardato un paio di altri algoritmi, tra cui
erano selection sort.
Quindi, ordinamento per selezione è un po 'diverso.
Era quasi più semplice, oserei dire, per cui ho iniziato all'inizio del
elenco dei nostri volontari e io di nuovo e ancora e ancora ha attraversato
la lista, pizzicando la più piccola elemento alla volta e mettendo lui o
lei all'inizio della lista.
>> Ma anche questo, una volta che abbiamo iniziato a pensare attraverso la matematica e più grande
immagine, ha pensato a quante volte Stavo andando avanti e indietro e indietro
e indietro, abbiamo detto, nel caso peggiore, selection sort, troppo, era quello che?
n al quadrato.
Ora, nel mondo reale, potrebbe realtà essere marginalmente più veloce.
Perché ancora una volta, non ho dovuto tenere backtracking una volta che avevo ordinato il
elementi più piccoli.
Ma se ci pensiamo molto grande N, e se si ordina di fare fuori la matematica come
Ho fatto sulla scheda, con il n quadrato qualcosa di meno, tutto il resto
oltre al n al quadrato, una volta n diventa veramente grande, non
importa tanto.
Così come gli informatici, abbiamo una sorta di chiudere un occhio per il più piccolo
fattori e concentrarsi solo sul fattore in un'espressione che sta andando a fare
la differenza più grande.
>> Bene, infine, abbiamo cercato a insertion sort.
E questo era simile nello spirito, ma piuttosto che passare attraverso iterativo e
selezionare l'elemento più piccolo uno alla tempo, ho invece preso la mano che mi
è stato trattato, e ho deciso, tutti a destra, tu appartieni qui.
Poi sono passato al prossimo elemento e ha deciso che lui o
lei apparteneva qui.
E poi mi sono spostato su e su.
E potrei a, lungo la strada, spostare questi ragazzi al fine di
fare spazio per loro.
Così che era una sorta di inversione mentale di ordinamento per selezione che abbiamo
chiamato insertion sort.
>> Quindi questi argomenti che si verifichi nel mondo reale.
Solo pochi anni fa, quando un certo senatore era candidato alla presidenza,
Eric Schmidt, al momento l'amministratore delegato di Google, in realtà ha avuto l'opportunità
per intervistarlo.
E abbiamo pensato di condividere questo YouTube Clip per voi qui, se potessimo alzare
il volume.
>> [RIPRODUZIONE VIDEO]
>> -Ora, il senatore, sei qui a Google, e mi piace pensare di presidenza
come un colloquio di lavoro.
>> [Risata]
>> -Ora è difficile da ottenere un lavoro come presidente.
E che stai passando i rigori ora.
E 'anche difficile ottenere un lavoro presso Google.
Abbiamo domande e chiediamo i nostri candidati domande.
E questo è da Larry Schwimmer.
>> [Risata]
-Voi pensate che stia scherzando?
E 'proprio qui.
Qual è il modo più efficace per ordinare un milione di numeri interi da quattro soldi?
>> [Risata]
>> -Beh, uh -
>> -Mi dispiace.
Forse dovremmo -
>> -No, no, no, no, no.
>> -Questo non è un -
OK.
>> -Penso che il bubble sort sarebbe essere il modo sbagliato di procedere.
>> [Risata]
>> [Applausi e applausi]
>> -Andiamo, chi lo ha detto?
OK.
>> [FINE RIPRODUZIONE VIDEO]
>> DAVID MALAN: Quindi il gioco è fatto.
Così abbiamo cominciato a quantificare questi esecuzione volte, per così dire, con qualcosa
chiamato notazione asintotica, che è riferisco solo alla nostra specie di svolta
un occhio a quei fattori più piccoli e solo guardando il tempo di esecuzione,
le prestazioni di questi algoritmi, quando n diventa veramente grande nel tempo.
E così abbiamo introdotto grandi O. e grande O rappresentato qualcosa che abbiamo pensato
di come un limite superiore.
E in realtà, Barry, possiamo abbassare che il microfono un po '?
>> Abbiamo pensato di tutto questo è un limite superiore.
Così grande O di n mezzo al quadrato che in il caso peggiore, qualcosa come
selection sort avrebbe preso n passi al quadrato.
O qualcosa di simile insertion sort farebbe n passi al quadrato.
Ora per qualcosa come l'inserimento sorta, quello che era il caso peggiore?
Dato un array, qual è la cosa peggiore possibile scenario che si potrebbe trovare
te di fronte a?
>> E 'completamente indietro, giusto?
Perché se è completamente all'indietro, devi fare un sacco di lavoro.
Perché se sei completamente all'indietro, si sta andando a trovare la
grande elemento qui, anche se essa appartiene laggiù.
Quindi hai intenzione di dire, va bene, a questo momento nel tempo, si appartengono qui,
così lo lasciano in pace.
>> Poi ti rendi conto, oh, accidenti, devo spostare questo elemento leggermente più piccolo di
sinistra di voi.
Poi devo farlo di nuovo e ancora e ancora.
E se ho camminato avanti e indietro, si potrebbe ordinare di sentire le prestazioni di
tale algoritmo, perché costantemente sono io mischiare tutti gli altri verso il basso nella
matrice per fare spazio per essa.
Ecco, questo è il caso peggiore.
>> Per contrasto -
e questo era un cliffhanger ultima volta -
abbiamo detto che insertion sort era un omega di che cosa?
Qual è il miglior esecuzione nel caso tempo di insertion sort?
Quindi è in realtà n.
Quello era il vuoto che abbiamo lasciato sulla scheda ultima volta.
>> Ed è omega di n perché perché?
Ebbene, proprio nel migliore dei casi, ciò che è insertion sort sta per essere consegnato?
Beh, un elenco che è completamente allineati già, minimo lavoro da fare.
Ma ciò che è semplice di insertion sort è che perché inizia qui e
decide, oh, tu sei il numero uno, sei dei nostri.
Oh, che fortuna.
>> Tu sei il numero due.
È inoltre appartieni qui.
Numero tre, ancora meglio, tu appartieni qui.
Non appena si arriva alla fine della pseudocodice lista, per l'inserimento di specie
che abbiamo raggiunto attraverso verbalmente ultima volta, è fatta.
Ma per selezione, per contrasto, tenuto a fare che cosa?
>> Continuava a scorrere l'elenco ancora e ancora e ancora.
Perché l'intuizione fondamentale solo ci fosse una volta che hai guardato fino alla
fine della lista si può essere certi che l'elemento selezionato è stato
infatti l'elemento attualmente più piccolo.
Quindi questi diversi modelli mentali fine per cedere alcuni molto del mondo reale
differenze per noi, così come questi differenze teoriche asintotici.
>> Quindi, solo per ricapitolare, quindi, grande O di n quadrato, abbiamo visto un paio di tale
algoritmi finora.
Big O di n?
Che cosa è un algoritmo che potrebbe dire di essere grande O di n?
Nel peggiore dei casi, richiede una serie lineare di passi.
>> OK, ricerca lineare.
E, nel caso peggiore, dove è la elemento che stai cercando, quando
l'applicazione di ricerca lineare?
>> OK, nel caso peggiore, non è nemmeno lì.
O nel secondo caso peggiore, e ' fino alla fine, che è
più-o-meno una differenza di un solo passaggio.
Così alla fine della giornata, possiamo dire che è lineare.
Big O di n sarebbe ricerca lineare, perché nel caso peggiore, la
elemento non è ancora lì o è fino alla fine.
>> Beh, grande O di log di n.
Non abbiamo parlato con dovizia di particolari su questo, ma abbiamo visto questo prima.
Ciò che viene eseguito nella cosiddetta logaritmica tempo, nel caso peggiore?
>> Già, ricerca in modo binario.
E la ricerca binaria nel caso peggiore potrebbe avere l'elemento in qualche parte
la metà, o da qualche parte all'interno della matrice.
Ma a trovare solo una volta che si dividere la lista a metà, in
metà, a metà, a metà.
E poi voilà, è lì.
O ancora, nel peggiore dei casi, non è nemmeno lì.
Ma non sai che non c'è fino a quando si ordina di raggiungere quell'ultimo
bottom-maggior parte degli elementi di dimezzare e il dimezzamento e dimezzamento.
>> Big O di 1.
Così potremmo grande O di 2, O grande di 3.
Ogni volta che si desidera solo un numero costante, abbiamo appena sorta di appena semplificare
che come O grande di 1.
Pur se realisticamente, ci vuole 2 o anche 100 passi, se si tratta di un
numero costante di passi, diciamo solo grande O di 1.
Che cosa è un algoritmo che è in grande O di 1?
>> AUDIENCE: Trovare la lunghezza di una variabile.
>> DAVID MALAN: Trovare il lunghezza di una variabile?
>> PUBBLICO: No, la lunghezza se è già ordinato.
>> DAVID MALAN: Buono.
OK, in modo da trovare la lunghezza di qualcosa se la lunghezza che qualcosa, come
una matrice, viene memorizzato in qualche variabile.
Perché si può solo leggere la variabile, o stampare la variabile, o
basta accedere generalmente quella variabile.
E voilà, che richiede tempo costante.
>> Al contrario, pensare di nuovo a zero.
Ripensate alla prima settimana di C, chiamare solo printf e stampa
qualcosa sullo schermo è senza dubbio costante di tempo, perché ci vuole solo
certo numero di cicli di CPU per mostrare che il testo sullo schermo.
O aspettare - lo fa?
Altrimenti come potremmo modellare la prestazioni di printf?
Qualcuno come non essere d'accordo, che forse non è il tempo davvero costante?
In che senso potrebbe printf è in esecuzione tempo, in realtà la stampa di una stringa su
lo schermo, sia qualcosa di diversa costante.
>> AUDIENCE: [incomprensibile].
>> DAVID MALAN: Già.
Quindi dipende dalla nostra prospettiva.
Se noi pensiamo che in realtà l'ingresso in modo printf come la corda, e
quindi si misura la dimensione di tale ingresso per la sua lunghezza - quindi chiamiamolo
che la lunghezza n, come pure -
discutibilmente, printf è di per sé grande O di n perché sta andando a prendere n passi
per stampare ciascuna di quelle n personaggi, molto probabilmente.
Almeno nella misura in cui si suppone che forse si sta usando un ciclo for
sotto la cappa.
>> Ma dovremmo guardare quella codice per capire meglio.
E infatti, una volta che voi ragazzi cominciate analizzare i propri algoritmi, si
letteralmente fare proprio questo.
Sorta di bulbo oculare tuo codice e pensare circa - tutto bene, ho questo anello
qui o ho un cicli annidati qui, che sta per fare n cose N volte,
ed è possibile ordinare il vostro senso della ragione attraverso il codice, anche se è
pseudocodice e non il codice vero e proprio.
>> E per quanto riguarda omega di n al quadrato?
Quello che era un algoritmo che nella migliore caso, ancora preso n passi quadrati?
Sì?
>> AUDIENCE: [incomprensibile].
>> DAVID MALAN: selezione Così sorta.
Perché in quel problema davvero ridotto per il fatto che ancora una volta, non lo so
Ho trovato la corrente più piccolo fino a quando Ho controllato tutti gli elementi maledettamente.
Così omega di, diciamo, n, appena si avvicinò con uno.
Insertion sort.
Se la lista sembra essere ordinati già, nel migliore dei casi non ci resta che
per fare un passaggio attraverso di essa, a che punto siamo sicuri.
E allora che si potrebbe dire ad essere lineare, di sicuro.
>> Che dire di omega di 1?
Quali sono, nel migliore dei casi, potrebbe prendere un numero costante di passi?
Ricerca in modo lineare, se basta avere fortuna e l'elemento che stai cercando
è proprio all'inizio della lista, se è lì che si sta iniziando la vostra
lineare di attraversamento di tale elenco.
>> E questo è vero di un certo numero di cose.
Per esempio, anche binario ricerca è omega di 1.
Perché quello che se si ottiene davvero maledettamente fortunato e smack-limanda nel mezzo di
la matrice è il numero stai cercando?
Così si può avere fortuna lì, così.
>> Questo, infine, omega di n log n.
Così n log n, non abbiamo davvero parlare ancora, ma -
>> AUDIENCE: merge sort?
>> DAVID MALAN: merge sort.
Questo è stato il colpo di scena della scorsa volta, dove abbiamo proposto, e abbiamo dimostrato
visivamente, che esistono algoritmi.
E merge sort su un solo tale algoritmo che è fondamentalmente più veloce
che alcuni di questi altri ragazzi.
Infatti, unire breve è non solo nella caso migliore n log n, nel peggiore
caso n log n.
E quando si ha questa coincidenza di Omega e la grande O di essere la stessa cosa?
In realtà possiamo descrivere che come ciò che è chiamato theta, anche se è un
po 'meno comune.
Ma questo significa che solo i due limiti, in questo caso, sono gli stessi.
>> Così merge sort, che cosa fa questo davvero bollire fino a per noi?
Beh, ricordare la motivazione.
Permettetemi di tirare su un altro animazione che noi non guardiamo l'ultima volta.
Questo, stessa idea, ma è un po 'più grande.
E ho intenzione di andare avanti e sottolineare prima - abbiamo insertion sort su
a sinistra in alto, poi selection sort, bubble sort, un paio di altri tipi -
guscio e veloce - che non abbiamo parlato circa, e heap e merge sort.
>> Così almeno cercare di concentrare i vostri occhi su i primi tre a sinistra e poi
merge sort quando clicco questa freccia verde.
Ma vi svelo tutti loro gestita, solo per vi darà un senso di diversità dei
algoritmi che esistono nel mondo.
Ho intenzione di lasciare che questa corsa per pochi secondi.
E se si concentrano gli occhi - scegliere un algoritmo, si concentrano su di essa solo per un
secondi - si comincia a vedere la modello che è attuazione.
>> Merge sort, avviso, è fatto.
Heap sort, quick sort, shell -
così sembra abbiamo introdotto il tre peggiori algoritmi scorsa settimana.
Ma questo è un bene che siamo qui oggi per guarda merge sort, che è uno dei
quelli più facili è da guardare, anche anche se probabilmente sarà piegare la tua mente
solo un po '.
Qui possiamo vedere solo quanto selection sort schifo.
>> Ma il rovescio della medaglia, è veramente facile da implementare.
E forse per P Set 3, che è uno dei algoritmi si è scelto di implementare
per l'edizione standard.
Perfettamente bene, perfettamente corretto.
>> Ma ancora una volta, come n diventa grande, se si scegliere di implementare un algoritmo più veloce
come merge sort, probabilità sono a grandi e ingressi più grandi, il codice è solo
andare a correre più veloce.
Il tuo sito web sta andando a lavorare meglio.
Gli utenti stanno per essere più felici.
E così ci sono questi effetti della realtà dando
noi un po 'di più profondo pensiero.
>> Quindi diamo un'occhiata a ciò che si fondono specie è in realtà tutto.
La cosa interessante è che si fondono specie è proprio questo.
Si tratta, ancora una volta, quello che abbiamo chiamato pseudocodice, essere pseudocodice
Sintassi simile all'inglese.
E la semplicità è sorta di affascinante.
>> Quindi, su input di n elementi - in modo che Significa solo, ecco un array.
E 'ottenuto n oggetti in esso.
Questo è tutto quello che stiamo dicendo qui.
>> Se n è minore di 2, ritornare.
Ecco, questo è proprio il caso banale.
Se n è minore di 2, poi ovviamente è 1 o 0, nel qual caso la cosa
è già ordinato o inesistenti, quindi basta tornare.
Non c'è niente da fare.
Ecco, questo è un semplice caso di cogliere off.
>> Altrimenti, abbiamo tre gradini.
Ordinare la metà sinistra degli elementi, specie la metà destra degli elementi,
e quindi unire le due metà ordinate.
La cosa interessante qui è che Sono una specie di punting, giusto?
C'è una specie di definizione circolare a questo algoritmo.
In che senso questo algoritmo di circolare definizione?
>> AUDIENCE: [incomprensibile].
>> DAVID MALAN: Sì, il mio algoritmo di ordinamento, due dei suoi passaggi sono "specie
qualcosa. "E così che pone la domanda, beh, cosa posso usare
di ordinare la metà sinistra e la metà di destra?
E la bellezza qui è che anche se ancora una volta, questo è il mind-bending
parte potenzialmente, si può usare lo stesso algoritmo per ordinare la metà sinistra.
>> Ma aspettate un minuto.
Quando ti si dice di ordinare la metà sinistra, quali sono i due
passi per essere il prossimo?
Ci penseremo la metà sinistra del metà sinistra e destra
metà della metà sinistra.
Accidenti, come faccio a ordinare quei due metà, o quarti, ora?
>> Ma va bene così.
Abbiamo un algoritmo di ordinamento qui.
E anche se si potrebbe preoccuparsi in primo luogo si tratta di una specie di infinito
ciclo, è un ciclo che non è mai andando a finire - che sta per
fine una volta che cosa succede?
Una volta che n è minore di 2.
Che alla fine sta per accadere, perché se si mantiene il dimezzamento e
dimezzando in dimezzare queste metà, sicuramente alla fine si sta andando a finire
con solo 1 o 0 elementi.
A quel punto, questo algoritmo dice che si è fatto.
>> Quindi, la vera magia di questa algoritmo sembra essere in
il passo finale, la fusione.
Questa semplice idea basta fondere due cose, è quello che sta succedendo in ultima analisi
per permetterci di ordinare un array di, diciamo, otto elementi.
Così ho più otto palline antistress up qui, otto pezzi di carta, e uno
Google Glass -
che riesco a mantenere.
>> [Risata]
>> DAVID MALAN: Se potessimo prendere otto volontari, e vediamo se possiamo
giocare a questo fuori, così.
Wow, OK.
L'informatica è sempre divertente.
D'accordo.
Così come su voi tre, grande mano lassù.
Quattro nella parte posteriore.
E per quanto riguarda noi faremo voi tre in questa riga?
E quattro nella parte anteriore.
Quindi otto, andiamo su.
>> [Risata]
>> DAVID MALAN: In realtà sono non so che cosa sia.
E 'le palle dello stress?
Le lampade da tavolo?
Il materiale?
Internet?
>> OK.
Quindi forza up.
Chi vorrebbe -
continuano a venire su.
Vediamo.
E questo ti mette in posizione -
siete in posizione uno.
Uh-oh, aspetta un minuto.
1, 2, 3, 4, 5, 6, 7 - Oh, bene.
Va bene, siamo a posto.
Va bene, così tutti hanno una sede, ma non sulla lastra di Google.
Lasciatemi fare la fila questi.
Qual è il tuo nome?
>> MICHELLE: Michelle.
>> DAVID MALAN: Michelle?
Va bene, si arriva a guardare come il geek, se va bene.
Beh, lo faccio anche, suppongo, solo per un momento.
D'accordo, di attesa.
Abbiamo cercato di trovare un utilizzare caso per Google Glass, e noi
pensato che sarebbe stato divertente fare solo questo quando le persone sono sul palco.
Noi registreremo il mondo dal loro punto di vista.
D'accordo.
Non è forse quello che Google intende.
Va bene, se non ti dispiace indossare questo per i prossimi minuti imbarazzanti,
che sarebbe meraviglioso.
>> Va bene, così abbiamo qui una serie di elementi, e che la matrice, come da
pezzi di carta in queste persone ' mani, è attualmente non differenziati.
>> MICHELLE: Oh, è così strano.
>> DAVID MALAN: E 'più o meno casuale.
E in un attimo, stiamo andando a provare implementare merge sort insieme
e vedere dove questa intuizione fondamentale è.
E il trucco con il merge sort è qualcosa che non abbiamo ancora assunto.
Abbiamo veramente bisogno di un po 'di spazio aggiuntivo.
Così che cosa sta andando essere particolarmente interessante di questo è che questi
ragazzi stanno per muoversi un po ' po ', perché ho intenzione di assumere che
c'è una serie extra di spazio, dire, proprio dietro di loro.
>> Quindi, se sono dietro la loro sedia, che è l'array secondario.
Se sono seduti qui, questo è la matrice primaria.
Ma questa è una risorsa che noi abbiamo non sfruttato finora con bolla
specie, con ordinamento per selezione, con insertion sort.
Ricordiamo la scorsa settimana, tutti appena tipo di mescolate a posto.
Non hanno usato la memoria aggiuntiva.
Abbiamo fatto spazio per persone da spostamento di persone in giro.
>> Quindi questa è una intuizione fondamentale, anche.
C'è questo trade-off, in generale, in informatica, di risorse.
Se si vuole accelerare qualcosa come il tempo, si sta andando a
pagare un prezzo.
E uno di questi prezzi è molto spesso spazio, la quantità di memoria o hard
spazio su disco che si sta utilizzando.
Oppure, francamente, l'importo del programmatore orario.
Quanto tempo ti porta, l'umano, effettivamente attuare alcune di più
algoritmo complicato.
Ma per oggi, il trade-off è il tempo e lo spazio.
>> Quindi, se voi ragazzi poteste semplicemente tenere il vostro numeri così possiamo vedere che sei
anzi corrispondenza 4, 2, 6, 1, 3, 7, 8.
Eccellente.
Quindi ho intenzione di cercare di orchestrare cose, se voi ragazzi può solo
seguire la mia guida qui.
>> Quindi ho intenzione di implementare, in primo luogo, la primo passaggio del pseudocodice, che è
su input di n elementi, se n è meno di 2, per poi tornare.
Ovviamente, ciò non Applica, quindi passiamo.
Così ordinare la metà sinistra degli elementi.
Quindi questo significa che ho intenzione di concentrare la mia l'attenzione per un attimo su queste
quattro ragazzi qui.
Bene, che cosa devo fare dopo?
>> AUDIENCE: ordinare la metà sinistra.
>> DAVID MALAN: Quindi ora devo ordinare la metà sinistra di questi ragazzi.
Perché ancora una volta, assumere a te stesso la obiettivo è quello di ordinare la metà sinistra.
Come si fa a farlo?
Basta seguire le istruzioni, anche se stiamo facendo di nuovo.
Così ordinare la metà sinistra.
Ora sto ordinamento questi due ragazzi.
Che cosa viene dopo?
>> AUDIENCE: ordinare la metà sinistra.
>> DAVID MALAN: ordinare la metà sinistra.
Così ora questi, questo posto qui, è una lista di dimensione 1.
E tu come ti chiami?
>> PRINCIPESSA MARGHERITA: Principessa Daisy.
>> DAVID MALAN: Principessa Daisy è qui.
E così lei è già ordinato, perché l'elenco è di dimensioni 1.
Cosa devo fare dopo?
OK, tornare, perché quella lista è di dimensione 1, che è meno di 2.
Allora qual è il prossimo passo?
E ora si deve tipo di marcia indietro nella vostra mente.
>> Ordinare la metà di destra, che è -
come ti chiami?
>> LINDA: Linda.
>> DAVID MALAN: Linda.
E allora che cosa facciamo ora che abbiamo una lista di dimensione 1?
>> AUDIENCE: Return.
>> DAVID MALAN: Attento.
Torniamo prima, e ora il terzo passo - e se io tipo di rappresentarlo con
abbracciando i due sedili ora, ora mi devono unire questi due elementi.
Così ora, purtroppo, gli elementi sono fuori uso.
Ma è qui che il processo di fusione inizia a ottenere convincente.
>> Quindi, se voi ragazzi poteste stare in piedi per poco un momento, ho bisogno di te, in un
momento, al passaggio dietro la sedia.
E se Linda, poiché 2 è più piccolo di 4, perché non fare
si arriva intorno prima?
Rimani lì.
Così Linda, si arriva intorno prima.
>> Ora, in realtà, se si tratta solo di un array potremmo semplicemente il suo muoversi in tempo reale
da questa sedia a questo punto.
Quindi immaginate che ha avuto una costante numero di punti 1.
E ora -
ma abbiamo bisogno di mettere in la prima posizione qui.
>> E ora, se tu potessi venire in giro, così, stiamo andando a
essere in posizione due.
E anche se questo si sente come se fosse prendere un po ', cosa c'è di bello ora è
che la metà sinistra del metà di sinistra è ora ordinato.
Così che cosa è stato il passo successivo, se ora riavvolgere ulteriormente nella storia?
>> AUDIENCE: la metà destra.
>> DAVID MALAN: Suddividere la metà di destra.
Quindi, voi ragazzi avete per fare questo, come bene.
Quindi, se si poteva stare in piedi solo per un momento?
E qual è il tuo nome?
>> JESS: Jess.
>> DAVID MALAN: Jess.
OK, Jess è ora la sinistra la metà della metà di destra.
E così lei è un elenco di dimensioni 1.
Lei è ovviamente allineati.
E il tuo nome?
>> MICHELLE: Michelle.
>> DAVID MALAN: Michelle è ovviamente una lista di dimensione 1.
Ha già ordinato.
Così ora la magia accade, il processo di fusione.
Allora, chi sta andando a venire prima?
Ovviamente Michelle.
Quindi, se tu potessi venire in giro indietro.
Lo spazio che abbiamo a disposizione per lei ora è proprio dietro questa sedia qui.
E ora se potessi tornare indietro, come pure, ora abbiamo, per essere chiari, due
due metà, ognuna di dimensioni 2 -
e solo per amor di rappresentazione, se si potrebbe fare un po 'di spazio -
uno a sinistra a metà qui, uno mezzo proprio qui.
>> Riavvolgere ulteriormente nella storia.
Che cosa è prossimo passo?
>> AUDIENCE: Unisci.
>> DAVID MALAN: Quindi ora dobbiamo unire.
Quindi OK, ora, per fortuna, abbiamo appena liberato quattro sedie.
Quindi abbiamo usato il doppio della memoria, ma possiamo dare flip-flopping tra
i due array.
Quindi, quale numero deve venire prima?
Così Michelle, ovviamente.
Allora venite in giro e prendere il tuo posto qui.
E quindi il numero 2 è ovviamente successivo, in modo da venire qui.
Numero 4, numero 6.
E di nuovo, anche se c'è un po 'di camminare coinvolti,
in realtà, questi potrebbero accadere istantaneamente, spostando uno -
OK, ben suonato.
>> [Risata]
>> DAVID MALAN: E ora siamo in buona forma.
La metà sinistra di tutta ingresso è stato ora risolto.
Va bene, quindi questi ragazzi aveva il vantaggio della mia -
come ha fatto a finire tutte le ragazze sul a sinistra e tutti i ragazzi di destra?
>> OK, ragazzi 'girano adesso.
Così non si attraversa questi passaggi.
Vedremo se possiamo riapplicare la stessa pseudocodice.
Se si vuole andare avanti e stare in piedi, e voi ragazzi, lasciate che vi dia il microfono.
Vedi se non è possibile replicare ciò che abbiamo appena fatto qui sulla
altra estremità della lista.
Chi ha bisogno di parlare per primo, base all'algoritmo?
Quindi spiegare che cosa si sta facendo prima di apportare eventuali movimenti del piede.
>> SPEAKER 1: Va bene, così da Sono la metà sinistra del
metà sinistra, torno.
Giusto?
>> DAVID MALAN: Buono.
>> SPEAKER 1: E poi -
>> DAVID MALAN: Chi fa il microfono va al successivo?
>> SPEAKER 1: numero successivo.
>> SPEAKER 2: Quindi sono la metà di destra della metà sinistra del
metà sinistra, e torno.
>> DAVID MALAN: Buono.
Si ritorna.
Così ora che cosa è il prossimo per voi due?
>> SPEAKER 2: Vogliamo vedere chi è più piccolo.
>> DAVID MALAN: Esattamente.
Noi vogliamo unire.
Lo spazio che andremo a utilizzare per unire si in, anche se sono
ovviamente ordinato già, stiamo andando a seguire lo stesso algoritmo.
Quindi chi va in dietro prima?
Così 3, e poi 7.
E ora il microfono passa a questi ragazzi, OK?
>> SPEAKER 3: Quindi io sono la metà destra del metà sinistra, e il mio n è inferiore
1, quindi sono solo andando a passare -
>> DAVID MALAN: Buono.
>> SPEAKER 4: Sono la metà destra del metà destra la metà destra, e io sono
anche una sola persona, quindi sono intenzione di tornare.
Così ora ci fondiamo.
>> SPEAKER 3: Allora torniamo indietro.
>> DAVID MALAN: Così si va nella parte posteriore.
Quindi 5 va in primo luogo, poi 8.
E ora pubblico, che è l' un passo che dobbiamo ora tornare indietro
back to nella nostra mente?
>> AUDIENCE: Unisci.
>> DAVID MALAN: Unire metà sinistra e destra metà della metà dell'originale sinistra.
Così ora -
e giusto per chiarire questo punto, fare un po 'di spazio
tra voi due ragazzi.
Quindi, ora che è le due liste, sinistra e destra.
Quindi, come possiamo ora fondiamo voi ragazzi in la prima fila di posti a sedere di nuovo?
>> 3 va prima.
Poi 5, ovviamente.
Poi 7, e ora 8.
OK, e ora siamo?
>> AUDIENCE: Non fatto.
>> DAVID MALAN: non fatto, perché ovviamente, c'è un passo dalla fine.
Ma ancora una volta, la ragione per cui sto usando questo gergo come "rewind nella vostra mente"
è perché è davvero cosa sta succedendo.
Stiamo andando attraverso tutti questi passaggi, ma noi siamo una sorta di pausa di un
momento, le immersioni più in profondità nel algoritmo, fermandosi per un attimo,
immersioni più in profondità l'algoritmo, e ora dobbiamo ordinare di rewind nel nostro
menti e annullare tutti questi livelli che abbiamo una sorta di messa in attesa.
>> Così ora abbiamo due liste di dimensione 4.
Se voi ragazzi poteste stare in piedi per l'ultima volta e fare un po 'di spazio qui per
chiarire che questa è la sinistra metà dell'originale, la
a destra la metà di quello originale.
Chi è il primo numero che abbiamo bisogno di tirare nella parte posteriore?
Michelle, naturalmente.
>> Così abbiamo messo Michelle qui.
E chi ha il numero 2?
Numero 2 arriva sulla schiena.
Numero 3?
Eccellente.
Numero 4, Numero 5, Numero 6, numero 7, e il numero 8.
>> OK, si sentiva come un sacco di passi, di sicuro.
Ma ora vediamo se non possiamo confermare sorta di intuitivamente che questa
algoritmo fondamentalmente, in particolare per quanto n diventa veramente grande, come abbiamo visto
con le animazioni, è sostanzialmente più veloce.
Quindi io sostengo questo algoritmo, nel peggiore caso e anche nel caso migliore,
è grande O di n volte log n.
Cioè, c'è qualche aspetto di questo algoritmo che prende in n passi, ma
c'è un altro aspetto da qualche parte in che iterazione, che looping, che
prende log n passi.
Possiamo mettere il dito su ciò che quelle due numeri si riferiscono a?
Beh, dove -
dov'e il microfono va?
>> SPEAKER 1: Sarebbe il log N sia ci rompere in due -
dividendo per due, essenzialmente.
>> DAVID MALAN: Esattamente.
Ogni volta che vediamo in ogni algoritmo così Finora, non c'è stato questo modello di
dividere, dividere, dividere.
Ed è tipicamente ridotto a qualcosa che è
logaritmica, log base 2.
Ma potrebbe davvero essere qualsiasi cosa, ma log base 2.
>> Ora, per quanto riguarda il n?
Vedo che abbiamo tipo divisi voi ragazzi - divisi voi, divisi,
diviso voi, diviso.
Da dove viene il termine viene?
>> Quindi è la fusione.
Perché pensarci.
Quando si uniscono otto persone insieme, per cui la metà di loro sono una serie di quattro
e l'altra metà sono un altro serie di quattro, come si fa
di fare la fusione?
Beh, che avete fatto è abbastanza intuitivo.
>> Ma se io invece facevo un po 'di più metodicamente, avrei puntato
la persona più a sinistra prima con la sinistra mano, indicò la persona più a sinistra
di che la metà con la mano destra, e solo successivamente attraversato il
elenco, indicando l'elemento più piccolo ogni volta, spostando il dito sopra e
oltre necessarie durante l'intero elenco.
Ma ciò che è fondamentale per questa fusione processo è che sto confrontando queste coppie
degli elementi.
Dalla metà di destra e da sinistra la metà, non sono mai una volta backtracking.
>> Quindi l'unione si sta prendendo non più di n passi.
E quante volte ho avuto per farlo fondere?
Beh, non più di n, e abbiamo appena visto che con la fusione finale.
E così se fai qualcosa che prende log n passi n volte, o viceversa,
sta andando a darci n volte log n.
>> E perché è meglio?
Beh, se sappiamo già che log n è meglio che n - giusto?
Abbiamo visto nella ricerca binaria, la rubrica telefonica esempio, log n è stato sicuramente
meglio che lineare.
Quindi che significa n volte log n è sicuramente meglio di n volte un altro
n, AKA n quadrato.
Ed è quello che ci sentiamo in definitiva.
>> Così grande applauso, se Potremmo, per questi ragazzi.
>> [Applausi]
>> DAVID MALAN: E i tuoi doni di commiato - si può mantenere i numeri,
se si desidera.
E il tuo regalo d'addio, come al solito.
Oh, e vi invieremo il filmato, Michelle.
Grazie.
D'accordo.
Aiutare se stessi a una palla di stress.
>> E mi permetta di tirare su, nel frattempo, il nostro amico Rob Bowden per offrire
prospettiva alquanto diversa su questa, dato che si può pensare a questi
passaggi che avvengono in un po ' modo diverso.
Infatti, il set-up per ciò Rob è circa per mostrarci presuppone che abbiamo
già fatto la suddivisione del grande elenco in otto piccole liste,
ciascuno di dimensione 1.
>> Quindi stiamo cambiando il pseudocodice un po 'solo per una sorta di arrivare al
idea di base di come la fusione funziona.
Ma il tempo di esecuzione di ciò che che sta per fare è ancora
andando ad essere lo stesso.
E ancora, il set-up è che lui è iniziato con otto liste di dimensione 1.
Quindi ti sei perso la parte in cui lui è effettivamente fatto il log n, log n, log n
dividendo dell'ingresso.
>> [RIPRODUZIONE VIDEO]
>> -Questo è tutto per il punto uno.
Per la fase due, più volte unisce coppie di liste.
>> DAVID MALAN: Hm.
Solo l'audio è in arrivo fuori dal mio computer.
Proviamo di nuovo.
>> -Basta scegliere arbitrariamente quale - Ora abbiamo quattro liste.
Imparare prima.
>> DAVID MALAN: Ci andiamo.
>> -Unione di 108 e 15, finiamo con l'elenco 15, 108.
Unione di 50 e 4, si finire con 4, 50.
Unione di 8 e 42, si finire con 8, 42.
E la fusione 23 e 16, si finire con 16, 23.
>> Ora tutte le nostre liste sono di dimensione 2.
Notare che ciascuno dei quattro elenchi vengono ordinati.
Così possiamo iniziare la fusione coppie di liste di nuovo.
Unione di 15 e 108 e 4 e 50, si prendere la prima 4, poi il 15, poi
il 50, allora il 108.
Unione di 8, 42 e 16, 23, per prima cosa prendiamo l'8, poi il 16, poi il 23,
poi il 42.
>> Così ora abbiamo solo due liste di dimensioni 4, ciascuno dei quali è ordinato.
Così ora fondiamo queste due liste.
In primo luogo, prendiamo il 4, poi prendiamo la 8, poi prendiamo la 15, poi 16, poi
23, poi 42, poi 50, poi 108.
>> [FINE RIPRODUZIONE VIDEO]
>> DAVID MALAN: Anche in questo caso, si noti, non ha mai toccato un dato coppa più di una volta
dopo l'avanzamento di là di esso.
Quindi non ha mai ripetere.
Quindi lui è sempre in movimento di lato, ed è lì che abbiamo ottenuto il nostro n.
>> Perché non mi permetta di tirare su una animazione che abbiamo visto in precedenza, ma questa volta
concentrandosi solo su merge sort.
Lasciami andare avanti e Zoom in su questo qui.
In primo luogo mi permetta di scegliere un ingresso casuale, magnificare questo, e si può ordinare di vedere
quello che abbiamo preso per scontato, in precedenza, merge sort sta effettivamente facendo.
>> Quindi notare che si ottiene queste metà o questi quartieri o questi ottavi di
problema che improvvisamente iniziare a prendere forma.
E poi finalmente, si vede a alla fine che bam,
tutto si fuse insieme.
>> Quindi questi sono solo tre diversi assume la stessa idea.
Ma l'intuizione fondamentale, proprio come spartiacque e conquistare nella prima classe,
era che abbiamo deciso di dividere in qualche modo il problema in qualcosa di grande, in
qualcosa sorta di identico nello spirito, ma più piccolo e più piccolo
e più piccoli.
>> Ora un altro modo divertente per ordinare di pensare di questi, anche se non lo e '
per darvi la stessa intuitiva comprensione, è
la seguente animazione.
Quindi questo è un video di qualcuno mettere insieme quello associato diverso
suoni con le varie operazioni di insertion sort, per merge sort, e
per un paio di altri.
Quindi, in un momento, sto andando a colpire Play.
Si tratta di circa un minuto a lungo.
E anche se è ancora possibile vedere la modelli accadendo, questa volta si può
anche sentire come questi algoritmi sono eseguendo differente e con
un po 'diversi modelli.
>> Questo è insertion sort.
>> [TONI GIOCANO]
>> DAVID MALAN: E 'ancora una volta sta cercando inserire ogni elemento
in cui essa appartiene.
Questo è il bubble sort.
>> [TONI GIOCANO]
>> DAVID MALAN: E si può ordinare di tatto come relativamente poco lavoro che sta facendo
ad ogni passo.
Questo è ciò che noia sembra.
>> [TONI GIOCANO]
>> DAVID MALAN: Questo è ordinamento per selezione, dove selezioniamo l'elemento che vogliamo da
passando ancora e ancora e ancora e metterlo all'inizio.
>> [TONI GIOCANO]
>> DAVID MALAN: Questo è merge sort, che si può davvero iniziare a sentire.
>> [TONI GIOCANO]
>> [Risata]
>> DAVID MALAN: qualcosa chiamato gnome sorta, che non abbiamo guardato.
>> [TONI GIOCANO]
>> DAVID MALAN: Allora fammi vedere, ora, distratto, come si spera, sei dal
musica, se riesco a scivolare un po ' po 'di matematica qui.
Quindi c'è un quarto modo che possiamo pensare a ciò che significa questi
funzioni per essere più veloce di quelli che abbiamo visto prima.
E se sei venuta al corso da uno sfondo di matematica, si
in realtà sapere forse già che si può schiaffo un termine su questa tecnica -
ricorsione cioè, una funzione che si fa chiamare in qualche modo.
>> E ancora una volta, ricordare che merge sort pseudocodice è ricorsiva, nel senso
che uno dei passaggi del merge sort era quello di chiamare sorta -
cioè, se.
Ma per fortuna, perché abbiamo tenuto chiamando sorta, o merge sort,
specificamente, in una più piccola e la lista più piccola, alla fine abbiamo
toccato il fondo grazie a quello che chiameremo un caso base, il caso a livello di codice che
detto se l'elenco è piccolo, inferiore a 2 in tal caso, basta restituire immediatamente.
Se non avessimo questo caso particolare, la algoritmo avrebbe mai toccare il fondo,
e si potrebbe davvero entrare in un ciclo infinito veramente per sempre.
>> Ma supponiamo che abbiamo voluto mettere ora alcuni numeri su questo, ancora una volta, utilizzando n
come la dimensione dell'input.
E volevo chiedere a voi, che cosa è il tempo totale coinvolti nella
esecuzione merge sort?
O più in generale, ciò che è il costo di esso nel tempo?
>> Beh, è ​​abbastanza facile da misurare tale.
Se n è minore di 2, il tempo coinvolto a ordinare n elementi,
dove n è 2, è 0.
Perché abbiamo appena torniamo.
Non c'è lavoro da fare.
Ora forse, forse è un passo o due passi per capire la quantità di
funziona, ma è abbastanza vicino a 0 che Sto solo andando a dire che nessun lavoro è
richiesto se l'elenco è così piccola essere poco interessante.
>> Ma questo caso è interessante.
Il caso ricorsivo era il ramo di lo pseudocodice che detto altrimenti, specie
la metà sinistra, ordinare il giusto metà, unire le due metà.
Ora, perché fa questa espressione rappresentare questa spesa?
Beh, T di n significa solo la tempo per ordinare n elementi.
E poi sul lato destro del segno di uguale c'è, la T di n diviso
da 2 si riferisce al costo di che cosa?
Ordinamento della metà sinistra.
L'altra T di n diviso 2 è presumibilmente riferibile al costo di
ordinare la metà di destra.
>> E poi il più n?
È la fusione.
Perché se si dispone di due liste, una di dimensione n 2 sopra e un altro di dimensione n
più di 2, si deve toccare essenzialmente ciascuno di tali elementi, proprio come Rob
toccato ciascuna delle coppe, e appena come abbiamo sottolineato a ciascuno dei
volontari sul palco.
Quindi n è la spesa di fusione.
>> Ora, purtroppo, questa formula è anche per sé ricorsiva.
Quindi, se posto la domanda, se n è, diciamo, 16, se ci sono 16 persone sul palco
o 16 tazze nel video, quanti totale passi ci vuole per ordinarli
con merge sort?
In realtà non è una risposta ovvia, perché ora si deve ordinare di
ricorsivamente rispondere a questa formula.
>> Ma va bene, perché mi permetta di proporre che facciamo la seguente.
Il tempo necessario per ordinare 16 persone o 16 tazze sta per essere rappresentati
generalmente come T di 16.
Ma che equivale, secondo la nostra precedente formula, 2 volte la quantità
di tempo necessario per ordinare 8 tazze più 16.
E ancora, più 16 è il momento di unire, e il due volte T di 8 è il
tempo per ordinare la metà sinistra e metà a destra.
>> Ma ancora una volta, questo non è sufficiente.
Dobbiamo fare immersioni in profondità.
Questo significa che dobbiamo rispondere alla domanda, che cosa è T di 8?
Beh T di 8 è a soli 2 volte T di 4 più 8.
Beh, cosa c'è di T di 4?
T su 4 è a soli 2 volte T di 2 più 4.
Beh, cosa c'è di T di 2?
T dei 2 si trova a soli 2 volte T di 1 più 2.
>> E ancora, siamo un po 'ottenere bloccato in questo ciclo.
Ma è in procinto di colpire che cosiddetto caso base.
Perché ciò che è di T 1, abbiamo pretendiamo?
0.
Così ora finalmente, siamo in grado di lavorare a ritroso.
>> Se T di 1 è 0, ora posso tornare indietro di un allinearsi a questo ragazzo qui, e posso
presa in 0 per T di 1.
Quindi, questo significa che è uguale a 2 volte a zero, altrimenti noto come 0, più 2.
E in modo che tutta l'espressione è 2.
>> Ora, se prendo la T di 2, la cui risposta è 2, collegarlo alla linea di mezzo, T
di 4, che mi dà 2 volte 2 più 4, così 8.
Se poi mi collego a 8 al precedente linea, che mi dà 2 volte 8, 16.
E se poi continuiamo che con la 24, aggiungendo in 16, abbiamo finalmente una
valore di 64.
>> Ora che in sé e per sé una sorta di parla nulla alla notazione n, la
O grande, l'omega che abbiamo state parlando.
Ma si scopre che il 64 è davvero 16, la dimensione dell'input,
log base 2 di 16.
E se questo è un po sconosciuto, basta ripenso, e si tornerà
a voi alla fine.
Se questo è il logaritmo in base 2, è come 2 elevato a quello che ti dà 16?
Oh, questo è 4, quindi è 16 volte 4.
>> E ancora, non è un grosso problema se questa è una sorta di memoria confusa ora.
Ma per ora, prendere sulla fede che il 16 log 16 è 64.
E così in effetti, con questa semplice sanity controllare, abbiamo confermato -
ma non dimostrata formalmente -
che il tempo di esecuzione di merge specie è infatti n log n.
>> Quindi, non è male.
E 'sicuramente meglio che la algoritmi che abbiamo visto finora, e
è perché abbiamo sfruttato, uno, una tecnica chiamata ricorsione.
Ma più interessante di quello che nozione di dividere e conquistare.
Anche in questo caso, veramente settimana 0 roba che anche ora è ricorrente in un
modo più convincente.
>> Ora un po 'di esercizio divertente, se hai mai fatto - e probabilmente
non avrebbe, perché sorta di normale la gente non pensa di fare questo.
Ma se vado a google.com e se Voglio imparare qualcosa su
ricorsione, Enter.
>> [Risata]
[Altre risate]
DAVID MALAN: scherzo di cattivo gusto lentamente diffondendo.
[Risata]
DAVID MALAN: Solo nel caso, è lì.
Non ho Spell sbagliato, e c'è la battuta.
D'accordo.
Spiegare alla gente accanto a voi se non è abbastanza appena ancora cliccato.
Ricorsione ma, più in generale, si riferisce al processo di una funzione chiamante
stesso, o più in generale, dividendo un problema in qualcosa che può essere
risolto frammentario risolvendo identico problemi di rappresentanza.
>> Bene, vediamo di cambiare marcia solo per un momento.
Ci piace concludere su alcuni cliffhanger, Quindi partiamo per impostare
il palco, per alcuni minuti, su un'idea molto semplice -
quella di scambiare due elementi, vero?
Tutti questi algoritmi che abbiamo passato parlando degli ultimi due
lezioni comportano una qualche sorta di swapping.
Oggi è stato visualizzato da loro ottenendo fino dalle loro sedie e
in giro, ma in codice, ci sarebbe basta prendere un elemento da un array
e plop in un altro.
>> Quindi, come possiamo fare per fare questo?
Beh, mi permetta di andare avanti e scrivere un rapido programma qui.
Ho intenzione di andare avanti e fare questo come il seguente.
Chiamiamo questo -
cosa vogliamo chiamare questo?
>> In realtà, no.
Permettetemi di riavvolgimento.
Io non voglio farlo ancora Cliffhanger.
Sarà rovinare il divertimento.
Facciamo questo, invece.
>> Supponiamo che io voglia scrivere un po 'di programma e che ora abbraccia questa
idea della ricorsione.
Ho avuto sorta di avanti di me lì.
Io vado a fare quanto segue.
>> In primo luogo, una rapida includono di serie io.h, così come un include di cs50.h.
E poi ho intenzione di andare avanti e dichiarare int void main
nel solito modo.
Mi sono reso conto che ho erroneamente chiamata il file, in modo da vorrei solo aggiungere un'estensione. c qui così
che siamo in grado di compilarlo correttamente.
Avviare la funzione.
>> E la funzione che ho voglia di scrivere, piuttosto semplicemente, è uno che chiede la
all'utente un numero e poi aggiunge tutti i numeri tra tale
numero e, diciamo, 0.
Così prima ho intenzione di andare avanti e dichiarare int n.
Poi copio un codice che abbiamo usato per un po '.
Mentre qualcosa è vero.
Tornerò a che in un attimo.
>> Cosa voglio fare?
Voglio dire printf positivo integer prego.
E poi ho intenzione di diciamo n diventa ottenere int.
Quindi, di nuovo, un po 'di codice standard che abbiamo usato prima.
E ho intenzione di fare questo mentre n è minore di 1.
Quindi questo farà sì che l'utente mi dà un numero intero positivo.
>> E ora ho intenzione di fare quanto segue.
Voglio sommare tutti i numeri tra 1 e ed n, o 0 e n,
equivalentemente, per ottenere la somma totale.
Così il grande simbolo sigma che si potrebbe ricordare.
Quindi ho intenzione di fare questo prima convocazione una funzione chiamata sigma,
passando a n, e quindi ho intenzione di printf dire, la risposta è proprio lì.
>> Così, in breve, ricevo e int da parte dell'utente.
Mi accerto che sia positivo.
Dichiaro una variabile chiamata risposta tipo int e conservare in esso il ritorno
valore di sigma, passando come input n.
E poi si stampa fuori quella risposta.
>> Purtroppo, anche se sigma suoni come qualcosa che potrebbe essere in
il file math.h, la sua dichiarazione, in realtà non è.
Ecco, questo è OK.
Posso implementare questo me stesso.
Ho intenzione di implementare una funzione chiamata sigma, e sta andando a prendere un
parametro -
diciamo solo chiamano m, appena quindi è diverso.
E poi qui, sto per dire, bene, se m è minore di 1 - questo è un
programma molto interessante.
Quindi ho intenzione di andare avanti e immediatamente restituire 0.
Semplicemente non ha senso sommare tutti i numeri tra 1 e m se m
è essa stessa 0 o negativo.
>> E poi ho intenzione di andare avanti e di farlo molto iterativo.
Ho intenzione di fare questo genere di vecchia scuola, e ho intenzione di andare avanti
e dire che ho intenzione di dichiarare una somma pari a 0.
Poi ho intenzione di avere un ciclo di int -
e lascia fare a me Tabellino nostro codice di distribuzione, in modo da avere una copia
a casa. int i ottiene 1 a un massimo di i è minore di o uguale a m.
i plus plus.
E poi all'interno di questo ciclo for -
ci siamo quasi -
somma ottiene somma più 1.
E poi ho intenzione di restituire la somma.
>> Così ho fatto questo in modo rapido, piuttosto è vero.
Ma ancora una volta, la funzione principale è abbastanza semplice, sulla base di codice che abbiamo
scritto finora.
Utilizza il doppio loop per ottenere un positivo int da parte dell'utente.
Ho poi passare che int ad una nuova funzione chiamato sigma, chiamandolo, ancora una volta, n.
E devo conservare il valore di ritorno, la risposta dalla scatola nera attualmente
noto come sigma, in una variabile chiamata risposta.
Poi la stampo.
>> Se noi ora continuare la storia, come viene implementato sigma?
Io propongo di attuare nel modo seguente.
In primo luogo, un po 'di controllo degli errori fare in modo che l'utente non è
scherzi con me e passando qualche valore negativo o 0.
Poi Dichiaro una variabile chiamata riassumere e impostarlo a 0.
>> E ora comincio a passare da i è uguale a 1 tutta la strada fino al m,
perché voglio includere tutte le numeri da uno a m, compreso.
E all'interno di questo ciclo for, io faccio solo somma ottiene tutto ciò che è ora, più il
valore di i.
Inoltre il valore di i.
>> Per inciso, se non avete visto questo prima, c'è un po 'di zucchero sintattico
per questa linea.
Posso riscrivere questo come più uguale a i, solo per salvare me stesso pochi tasti
e di guardare un po 'più fresco.
Ma questo è tutto.
E 'funzionalmente la stessa cosa.
>> Sfortunatamente, questo codice di non andare a compilare ancora.
Se corro fare sigma 0, come am Ho intenzione di ottenere sgridato?
Che cosa sta andando a non piacere?
>> AUDIENCE: [incomprensibile].
>> DAVID MALAN: Sì, non mi dichiaro la funzione di sollevamento in alto, giusto?
C è una specie di stupido, è solo in quel fa quello che gli si dice di fare, e si
hanno a che fare in questo ordine.
E così, se ho colpito Inserisci qui, ho intenzione di Ottengo un avviso circa sigma implicita
dichiarazione.
>> Oh, non è un problema.
Posso andare fino in cima, e posso dire, va bene, aspetta un minuto.
Sigma è una funzione che restituisce un int e che si aspetta un
int come input, virgola.
Oppure potrei mettere l'intera funzione sopra principale, ma in generale, avevo
raccomandare contro questo, perché è bello avere sempre principale nella parte superiore in modo da
è possibile immergersi in pieno e sapere che cos'è un programma sta facendo con la lettura principale prima.
>> Così ora mi permetta di cancellare lo schermo.
Remake sigma 0.
Tutto sembra controllare.
Lasciami correre sigma 0.
Tra positivo.
Ho deciso di dargli il numero 3 di mantenerlo semplice.
In modo che mi dovrebbe dare 3 più 2 più 1, quindi 6.
Entrare, e infatti ottengo 6.
>> Posso fare qualcosa di più grande -
50, 12, 75.
Proprio come una tangente, ho intenzione di fare qualcosa di ridicolo come un davvero grande
numero, Oh, che in realtà ha funzionato -
eh, non credo che sia giusto.
Vediamo.
Facciamo davvero pasticciare con essa.
>> Questo è un problema.
Che cosa sta succedendo?
Il codice non è poi così male.
E 'ancora lineare.
Fischiare è un buon effetto, però.
Che cosa sta succedendo?
>> Non sono sicuro se l'ho sentito.
Così si scopre - e questo è come un a parte.
Questo non è fondamentale per la idea della ricorsione.
Si scopre, perché sto cercando di rappresentare un numero così grande, più
probabilmente si tratta di essere male interpretato da C come un numero non positivo,
ma numero negativo.
>> Non abbiamo parlato di questo, ma è che vi sono numeri negativi
nel mondo in aggiunta ai numeri positivi.
E il mezzo con cui è possibile rappresentare un numero negativo
è essenzialmente, si utilizza uno po 'speciale per indicare
positivo nel negativo.
E 'un po' più complesso di così, ma questa è l'idea di base.
>> Così, purtroppo, se C è fonte di confusione uno di questi bit come in realtà significa,
oh, questo è un numero negativo, il mio ciclo qui, per esempio, è in realtà mai
andando a terminare.
Quindi, se io fossi davvero qualcosa di stampa ancora e ancora, ci sarebbe
vedere un bel po '.
Ma ancora una volta, questo è oltre il punto.
Questo è in realtà solo una sorta di curiosità intellettuale che verremo
tornare alla fine.
Ma per ora, questa è una corretta realizzazione se si assume che il
utente fornirà int che si adattano all'interno di int.
>> Ma io sostengo che questo codice, francamente, si potrebbe fare molto di più semplice.
Se l'obiettivo a portata di mano è quello di prendere un numero come m e sommare tutte le
numeri tra esso e 1, o viceversa tra 1 e, rivendico
che posso prendere in prestito questa idea che si fondono sorta aveva, che stava prendendo un problema
di queste dimensioni e dividendola in qualcosa di più piccolo.
Forse non la metà, ma più piccolo, ma rappresentativo della stessa.
Stessa idea, ma un problema minore.
>> Quindi sono in realtà - mi permetta di salvare questo file con un numero di versione diversa.
Chiameremo questa versione 1 invece di 0.
E mi sostenere che io in realtà può reimplementare questo in questa sorta di
mind-bending modo.
>> Ho intenzione di lasciare una parte di esso da solo.
Sto per dire se m è minore di o addirittura uguale a 0 -
Sto solo andando a essere un po ' più anale questa volta
con il mio controllo degli errori -
Ho intenzione di andare avanti e di restituire 0.
Questo è arbitraria.
Sto semplicemente decidendo se l'utente mi dà un numero negativo, io sono
ritorno 0, e che avrebbero dovuto leggere la documentazione più da vicino.
>> Altro -
accorgo di quello che ho intenzione di fare.
Altra cosa ho intenzione di tornare m plus -
ciò che è sigma di m?
Beh, sigma di m più m meno 1, più m meno 2, più m meno 3.
Non voglio scrivere tutto questo fuori.
Perché non solo punt?
Ricorsivamente definirmi con un po ' problema più piccolo, punto e virgola,
e chiamare un giorno?
>> Giusto?
Ora, anche qui, si potrebbe sentire o preoccuparsi che questo è un ciclo infinito che io sono
indurre, per cui io sono l'attuazione sigma chiamando il sigma.
Ma questo è perfettamente OK, perché io pensiero avanti un aggiunto che le linee?
>> AUDIENCE: [incomprensibile].
>> DAVID MALAN: da 23 a 26, che è la mia se la condizione.
Perché ciò che è bello circa la sottrazione qui, perché continuo
distribuendo sigma problemi più piccoli, più piccoli problemi, più piccolo - non è
la metà.
E 'solo un passo più piccolo bambino, ma va bene così.
Perché alla fine, lavoreremo la nostra strada fino a 1 o 0.
E una volta che abbiamo raggiunto 0, sigma non è andando a chiamare più se stessa.
E 'intenzione di tornare immediatamente 0.
>> Così l'effetto, se si ordina di vento questo nella tua mente, è quello di aggiungere M PLUS
m meno 1, più m meno 2, più m meno 3, più punti, punto, punto, m meno
m, alla fine ti dà 0, e la effetto è in ultima analisi, per aggiungere tutti
queste cose insieme.
Quindi noi non abbiamo, con la ricorsione, risolto il problema che ci
non potrebbe risolvere prima.
Anzi, versione 0 di questo, e ogni problema fino ad oggi, è stato risolvibile
con il solo utilizzo di loop o mentre loop o costrutti simili.
>> Ma ricorsione, oserei dire, ci dà un modo diverso di pensare
problemi, per cui se si può prendere un problema, dividerlo da qualcosa
piuttosto grande in qualcosa alquanto più piccolo, sostengo che possiamo risolverli
forse un po 'più elegante, in termini del disegno, con meno codice,
e forse anche risolvere i problemi che si essere più difficile, come vedremo alla fine
vedere, la soluzione puramente iterativo.
>> Ma il colpo di scena che ho fatto vuole lasciare a noi su questo stato.
Lasciami andare avanti e aprire un file da -
in realtà, lasciami andare e farlo in fretta.
Lasciami andare avanti e propongo il seguente.
Tra il codice di oggi è questo file qui.
Questo qui, noswap.
>> Quindi questo è un piccolo programma stupido che Ho scatenato che afferma di fare
il seguente.
Nel principale, dichiara in primo luogo un int chiamati x e lo assegna
il valore di 1.
Poi si dichiara un y int e assegna il valore 2.
Poi esso stampa quello che x e y è.
Poi si dice, lo swapping, puntini puntini.
>> Poi dice di chiamare una funzione chiamato swap, passando x e
y, la cui idea è che auspicabilmente x e y torneranno
differente, il contrario.
Poi pretendono scambiato!
con un punto esclamativo.
Poi esso stampa xe y.
>> Ma si scopre che proprio questo semplice dimostrazione giù
qui è in realtà buggy.
Anche se sto dichiarando una temporanea variabile e temporaneamente mettere un a
esso, allora sono riassegnando un valore di b -
che si sente ragionevole, perché ho salvato una copia di un in temperatura.
Poi mi aggiorno b deve essere uguale tutto ciò che era in temperatura.
Questa sorta di gioco delle tre carte di spostamento di un in b e b in una utilizzando questo
mezzo-uomo di nome Temp sente perfettamente ragionevole.
>> Ma io sostengo che quando eseguo questo codice, come farò ora -
mi permetta di andare avanti e di incollarlo in qui.
Chiamerò questo noswap.c.
E come suggerisce il nome, questo non è sarà un programma corretto.
Fai noswap. / No swap.
x è 1, y 2, swapping, scambiato.
x è 1, y è 2.
Questo è fondamentalmente sbagliato, anche se questo sembra perfettamente
ragionevole per me.
E c'è una ragione, ma non siamo intenzione di rivelare il motivo appena ancora.
>> Per ora il secondo colpo di scena che volevo lasciarvi con questo, un
annuncio di sorta sui codici promozionali.
La nostra innovazione con giorni di ritardo quest'anno ha provocato un numero non banale
delle domande, che era non è nostra intenzione.
L'intenzione di questi codici promozionali, per cui se fai parte del problema
set iniziale, ottenendo in tal modo un giorno in più, era davvero aiutare voi aiuto ragazzi
te rapido avvio, specie di incentivare da voi.
Ci aiuta a distribuire il carico tra orario di ufficio meglio così che
è una specie di win-win.
>> Purtroppo, credo che le mie istruzioni non sono stati, ad oggi, molto chiaro, in modo da
Sono tornato in questo fine settimana e aggiornato le specifiche in grande, testo ardita per
spiegare proiettili come questi.
E proprio per dirlo più pubblicamente, da predefinite, insiemi di problemi sono dovuti Giovedi
a mezzogiorno, per il programma.
Se si inizia presto, finendo parte di il problema posto da Mercoledì alle 12:00
PM, la parte che si riferisce a un coupon codice, l'idea è che si può estendere
il vostro termine per la P impostato fino a Venerdì.
Cioè, un po 'fuori una piccola parte del P impostate rispetto a ciò che è tipicamente la
grande problema, e si acquista voi stessi un giorno in più.
Ancora una volta, si ottiene pensando il problema insieme, si ottiene per
orario di ufficio prima.
Ma il problema codice coupon è ancora richiesto, anche se non si sottopone.
>> Ma più convincente è questa.
(STAGE WHISPER) E quelle persone lasciando sono presto ti pentirai.
Come sono le persone sul balcone.
Mi scuso in anticipo per la gente su balcone per ragioni che saranno
cancellare in un attimo.
>> Così abbiamo la fortuna di avere uno dei Ex capo compagni di insegnamento di CS50 a
una società denominata dropbox.com.
Essi hanno molto generosamente donato un codice coupon qui per questo molto spazio,
che è su dal solite 2 gigabyte.
Quindi quello che ho pensato che avremmo fatto in questo nota finale è fare un po 'di un giveaway,
per cui in un momento, ci rivelerà il vincitore e chi ha una cedola
codice che è possibile quindi andare al loro sito web, digitarlo nella, e voilà, ottenere un
molto di più per il vostro spazio Dropbox apparecchio e per i tuoi file personali.
>> E in primo luogo, che vorrebbe partecipare in questo disegno?
OK, ora che lo rende ancora più divertente.
La persona che riceve questo 25 gigabyte codice coupon - che è molto
più convincente rispetto alla fine degli anni giorni ormai, forse -
è colui che è seduto sulla cima di un cuscino sotto cui c'è
che il codice coupon.
Ora puoi guardare sotto il vostro cuscino.
>> [RIPRODUZIONE VIDEO]
>> -Uno, due, tre.
>> [GRIDA]
>> -È possibile ottenere una macchina!
Si ottiene una macchina!
>> DAVID MALAN: Vedremo si il Mercoledì.
>> -È possibile ottenere una macchina!
Si ottiene una macchina!
>> DAVID MALAN: persone Balcone, vieni qui al fronte,
dove abbiamo comparse.
>> -Ognuno ottiene una macchina!
Ognuno ottiene una macchina!
>> [FINE RIPRODUZIONE VIDEO]
>> NARRATORE: Al prossimo CS50 -
>> SPEAKER 5: Oh my gosh cribbio cribbio cribbio cribbio cribbio cribbio cribbio cribbio cribbio -
>> [GIOCHI Ukelele]