>> [Redarea muzicii]
DAVID MALAN: În regulă.
Bine, bine ai revenit.
Deci, aceasta este Săptămâna 4, la început acestuia, deja.
Și veți aminti că săptămâna trecută, am pus cod deoparte pentru doar un pic
și am început să vorbim un pic mai mult la nivel înalt, despre lucruri cum ar fi
căutarea și sortarea, care, deși idei oarecum simple, sunt
reprezentant al unei clase de probleme va începe să rezolve în special
cum începi să te gândești finală proiecte și soluții interesante pe care le
ar putea avea probleme din lumea reală.
Acum, un fel balon a fost una dintre cele mai simple astfel de algoritmi, și
lucrate de a avea aceste numere mici într-o listă sau într-un fel serie de
bule modul lor de până la partea de sus, și numere mari muta drumul lor până la
la sfârșitul acestei liste.
>> Și amintesc că am putea vizualiza bubble fel un pic
ceva de genul asta.
Așa că lasă-mă să merg mai departe și faceți clic pe Start.
Am preselectate fel bule.
Și dacă vă amintiți că albastru inalt Liniile reprezintă numere mari, mici,
liniile albastre reprezintă un număr mic, ca trecem prin asta din nou și din nou și
din nou, compararea a două bare de lângă fiecare altele în roșu, vom schimba
cel mai mare și cel mai mic în cazul în care ele sunt în ordine.
>> Deci, acest lucru va continua și du-te pe și du-te pe, și veți vedea că mai mare
Elementele fac drumul lor spre dreapta, iar elementele sunt mai mici
face drumul lor spre stânga.
Dar am început să cuantifice eficiența,
Calitatea acestui algoritm.
Și am spus că, în cel mai rău caz, acest algoritm luat
aproximativ câți pași?
>> Deci, n pătrat.
Și ce a fost n?
>> Audiența: Numărul de elemente.
>> DAVID MALAN: Deci, n fost număr de elemente.
Și așa vom face acest lucru de multe ori.
În orice moment vrem să vorbim despre dimensiunea a unei probleme sau dimensiunea unei
de intrare, sau cantitatea de timp este nevoie pentru a produce ieșire, vom doar
generalizată indiferent de intrare este ca n.
Deci, înapoi în Săptămâna 0, pagini numărul în cartea de telefon a fost n.
Numărul de studenți în cameră a fost n.
Deci, aici, de asemenea, suntem în urma ca model.
>> Acum n pătrat nu este deosebit repede, așa că am încercat să facem mai bine.
Și așa ne-am uitat la o pereche de alte algoritmi, printre care
au fost un fel de selecție.
Deci, un fel de selecție a fost un pic diferit.
Era aproape simplu, îndrăznesc să spun, prin care am început la începutul
Lista de voluntarii noștri și am din nou și din nou și din nou a trecut printr-
lista, smulgeau cel mai mic Elementul la un moment dat și punerea lui sau
ei la începutul listei.
>> Dar acest lucru, de asemenea, odată ce am început să mă gândesc prin matematica și mai mare
imagine, gândit de câte ori Am fost de gând înainte și înapoi și înapoi
și mai departe, am spus în cel mai rău caz, un fel de selecție, de asemenea, ceea ce a fost?
n patrat.
Acum, în lumea reală, s-ar putea de fapt, să fie marginal mai repede.
Pentru că din nou, nu am avut de a păstra revenire odată ce am sortat
mai mici elemente.
Dar dacă ne gândim foarte mare n, și Dacă aveți un fel de face din matematica ca
Am făcut-o de pe bord, cu pătrate n ceva minus, orice altceva
Pe langa n pătrat, o dată n devine foarte mare, nu
într-adevăr contează la fel de mult.
Deci, ca oameni de știință de calculator, am un fel de închide ochii la cel mai mic
factori și să se concentreze doar pe factorul de o expresie care va face
cea mai mare diferenta.
>> Ei bine, în cele din urmă, ne-am uitat la fel de inserție.
Și acest lucru a fost similară în spirit, dar mai degrabă decât trece prin iterativ și
selectați mai mic element unul la un timp, am luat în schimb de o parte că am
a fost ocupat, și am decis, toate Bine, e aici.
Apoi am trecut la urmatorul element și a decis că el sau
ea aparținea aici.
Și apoi m-am mutat pe și de pe.
Și eu s-ar putea să, de-a lungul drum, schimba astia, în scopul de a
face loc pentru ei.
Astfel că a fost un fel de inversare mentale de fel de selecție pe care le
numit un fel de inserare.
>> Astfel încât aceste subiecte să apară în lumea reală.
În urmă cu doar câțiva ani, atunci când o anumită Senatorul a fost de funcționare pentru președinte,
Eric Schmidt, în momentul în care CEO-ul de Google, de fapt a avut ocazia
să-l interviu.
Și ne-am gândit împărtășesc această YouTube clip pentru tine aici, dacă am putea întoarce
volum.
>> [Redare video]
>> -Acum, senator, esti aici de la Google, și îmi place să cred că a Președinției
ca un interviu de angajare.
>> [Râsete]
>> -Acum, este greu pentru a obține un loc de muncă în calitate de președinte.
Și te duci prin rigorile acum.
Este, de asemenea, greu pentru a obține un loc de muncă la Google.
Avem întrebări și vom cere noastre întrebări candidaților.
Și aceasta este de la Larry Schwimmer.
>> [Râsete]
-Voi credeți că glumesc?
Este chiar aici.
Care este cel mai eficient mod de a sorta un milion de numere întregi de doi bani?
>> [Râsete]
>> -Ei bine, uh -
>> -Îmi pare rău.
Poate ar trebui -
>> -Nu, nu, nu, nu, nu.
>> -Asta nu-i o -
OK.
>> -Cred că genul bubble ar fi fie în mod greșit de a merge.
>> [Râsete]
>> [Urale și aplauze]
>> -Haide, care l-a spus asta?
OK.
>> [END redare video]
>> DAVID MALAN: Deci nu-l ai.
Așa că am început să cuantifice aceste funcționare ori, ca să spunem așa, cu ceva
numită notația asimptotică, care este doar referindu-se la fel nostru de a transforma
ochii la aceste elemente mai mici și doar uita la timpul de execuție,
performanța acestor algoritmi, când n devine foarte mare în timp.
Și așa am introdus de mare O. Și Big O a reprezentat ceva ce ne-am gandit
a ca o limită superioară.
Și, de fapt, Barry, putem reduce decât MIC un pic?
>> Ne-am gândit acest lucru este o limită superioară.
Deci Big O de n mijloace pătrat care, în cel mai rău caz, ceva de genul
un fel de selecție va avea n pași pătrat.
Sau ceva de genul fel de inserare ar fi n pași pătrat.
Acum, pentru ceva de genul inserare un fel, ceea ce a fost cel mai rău caz?
Având în vedere o gamă largă, ceea ce e cel mai rău posibil scenariu pe care le-ar putea găsi
te confruntă cu?
>> Este complet invers, nu?
Pentru că dacă e complet invers, ce trebuie să faci o mulțime de muncă.
Pentru că dacă ești complet înapoi, ai de gând să găsească
Cel mai mare element de aici, chiar dacă acesta face parte acolo.
Deci, ai de gând să spui, bine, la acest moment în timp, vă aparțin aici,
astfel încât să-l lase în pace.
>> Apoi îți dai seama, oh, la naiba, trebuie să muta acest element ușor mai mici la
stânga de tine.
Atunci am să fac asta din nou și din nou și din nou.
Și dacă am mers înainte și înapoi, te ar fi un fel de simt performanței
că algoritmul, pentru că mereu sunt eu amestecarea oricine altcineva în
matrice pentru a face loc pentru ea.
Deci, asta e cel mai rau caz.
>> Prin contrast -
și acest lucru a fost un Cliffhanger ultima dată -
am spus că un fel de inserție a fost un omega de ce?
Ce-i de rulare cel mai bun caz timp de fel de insertie?
Deci, de fapt n.
Care a fost martor că am plecat pe placa de ultima dată.
>> Și e omega de n, deoarece de ce?
Ei bine, în cel mai bun caz, ceea ce este un fel de inserție va fi predat?
Ei bine, o lista care este complet sortat deja, lucrarea minimă a face.
Dar ceea ce este elegant, despre un fel de inserție este că, deoarece începe aici și
decide, oh, esti numărul unul, vă aparțin aici.
Oh, ce noroc.
>> Tu ești numărul doi.
De asemenea, ti-e locul aici.
Numărul trei, chiar mai bine, vă aparțin aici.
De îndată ce se ajunge la sfârșitul pseudocod lista, pe inserție fel de
că ne-am plimbat prin verbal ultima dată, sa terminat.
Dar un fel de selecție, prin contrast, continuat să fac ce?
>> Continuat prin lista din nou și din nou și din nou.
Deoarece perspectiva cheie nu a fost numai După ce am uitat tot drumul de a
sfârșitul listei poți fi sigur că elementul selectat a fost
într-adevăr, cel mai mic în prezent elementul.
Deci, aceste diferite modele sfârșitul mentale la cedarea unor foarte real lume
diferențe pentru noi, precum și aceste Diferențele teoretice asimptotice.
>> Deci, doar pentru recapitulare, apoi, Big O de n pătrat, am văzut o astfel de câteva
algoritmi de până acum.
Big O de n?
Ce este un algoritm care ar putea fi spus să fie Big O de n?
În cel mai rău caz, este nevoie de un număr liniar de pași.
>> OK, căutare liniară.
Și în cel mai rău caz, în cazul în care este Elementul sunteți în căutarea pentru atunci când
aplicarea căutare liniară?
>> OK, în cel mai rău caz, nu e chiar acolo.
Sau, în al doilea cel mai rău caz, e tot drumul în cele din urmă, care este
plus-sau-minus o diferență cu o singură etapă.
Deci, la sfârșitul zilei, putem spune că e liniar.
Big O de n-ar fi de căutare liniară, deoarece în cel mai rău caz,
Elementul nu e chiar acolo sau este tot drumul la final.
>> Ei bine, Big O de jurnal de n.
Nu am vorbit în detaliu despre acest lucru, dar am văzut acest lucru înainte.
Ceea ce se execută în așa-numitele logaritmică timp, în cel mai rău caz?
>> Da, de căutare, astfel binar.
Și binar de căutare în cel mai rău caz ar putea avea elementul undeva în
la mijloc, sau undeva în interiorul matrice.
Dar vi se pare doar o dată ce împărți lista în jumătate, în
jumătate, în jumătate, în jumătate.
Și apoi voila, e acolo.
Sau din nou, cel mai rău caz, nu e chiar acolo.
Dar tu nu știi că nu e acolo până când un fel de a ajunge la ultima
-cele mai de jos elemente prin înjumătățirea și reducerea la jumătate și înjumătățirea.
>> O mare de 1.
Deci, am putea Big O de 2, Big O de 3.
Oricand vrei doar un număr constant, am doar un fel de doar simplifica
că la fel de mare de O 1.
Chiar dacă în cazul realist, este nevoie de 2 sau chiar 100 de pași, dacă este un
număr constant de pași, spunem doar Big O de 1.
Ce este un algoritm care este în Big O de 1?
>> Audiența: Găsirea lungimea a unei variabile.
>> DAVID MALAN: Găsirea Lungimea unei variabile?
>> Audiența: Nu, lungimea în cazul în care este deja sortate.
>> DAVID MALAN: Bine.
OK, astfel încât găsirea lungimea de ceva dacă lungimea de acel ceva, cum ar fi
o matrice, este stocat în unele variabile.
Pentru că puteți citi doar variabila, sau imprima variabila, sau
doar acces în general, că variabila.
Și voila, care ia timp constant.
>> Prin contrast, cred că înapoi la zero.
Gandeste-te la prima săptămână a C, apel doar printf și imprimare
ceva de pe ecran este, fără îndoială, constanta de timp, deoarece este nevoie doar de
un număr de cicluri de CPU pentru a arăta că textul de pe ecran.
Sau așteptați - nu-i așa?
Cum altfel am putea modela performanța de printf?
Ar dori cineva să nu sunt de acord, că Poate că nu e timp foarte constanta?
În ce sens s-ar putea printf se scurge timp, imprimarea de fapt un șir pe
ecran, fie ceva altele decât constanta.
>> Audiența: [inaudibil].
>> DAVID MALAN: Da.
Deci, depinde de punctul nostru de vedere.
Dacă am de fapt, cred că de intrare a printf ca fiind șir, și
Prin urmare, măsura dimensiunea de care intrare prin lungimea sa - deci sa-i spunem
ca lungime n, precum și -
fără îndoială, printf este ea însăși Big O de n pentru că o să te n pașii luați
pentru a imprima fiecare dintre cei n personaje, cel mai probabil.
Cel puțin în măsura în care le presupune Poate că este folosind o buclă
sub capota.
>> Dar ne-ar trebui să te uiți la asta cod pentru a înțelege mai bine.
Și într-adevăr, odată ce voi începe analiza propriile algoritmi, vei
literalmente face doar asta.
Un fel de globului ocular codul și cred despre - în regulă, am această buclă
aici sau am un bucle imbricate aici, care va face n lucruri de n ori,
și se pot sorta de motiv drum prin cod, chiar dacă este
pseudocod și nu codul actual.
>> Deci, ce despre omega n pătrat?
Ce a fost un algoritm care, în cel mai bun caz, încă n luat măsuri pătrat?
Da?
>> Audiența: [inaudibil].
>> DAVID MALAN: Deci, un fel de selecție.
Pentru că în această problemă redus într-adevăr la faptul că, din nou, eu nu știu
Am gasit cel mai mic curent până Am verificat toate elementele darn.
Deci omega de, să zicem, n, noi tocmai a venit cu un singur.
Un fel de inserare.
Dacă lista se întâmplă să fie sortate deja, în cel mai bun caz avem doar
pentru a face o trecere prin ea, moment în care suntem siguri.
Și atunci care ar putea fi spus să fie liniar, pentru sigur.
>> Ce zici de omega 1?
Ceea ce, în cel mai bun caz, s-ar putea să ia un număr constant de pași?
Căutare atât de liniar, dacă ai noroc și elementul ce căutați
este chiar la începutul listei, în cazul în care este în cazul în care sunteți incepand dvs.
liniar traversarea acestei liste.
>> Și acest lucru este valabil de un număr de lucruri.
De exemplu, chiar binar căutare este de omega 1.
Pentru că ce dacă aveți într-adevăr darn noroc și jart-DAB în mijlocul
matrice este numărul ce căutați?
Deci, puteți obține noroc acolo, de asemenea.
>> Acesta, în cele din urmă, omega de log n.
Deci, n log n, nu am făcut într-adevăr vorbesc despre încă, dar -
>> Audiența: Merge fel?
>> DAVID MALAN: Merge fel.
Asta a fost Cliffhanger de ultima dată, unde ne-am propus, și am arătat
vizual, că există algoritmi.
Și un fel de doar un astfel de îmbinare algoritm care este fundamental mai rapid
decât unele dintre aceste alți tipi.
De fapt, îmbinare scurt este nu numai în cel mai bun caz, n n jurnal, în cel mai rău
cazul n n jurnal.
Iar atunci când aveți această coincidență de omega și mari O fi același lucru?
Putem descrie de fapt, că în ceea ce-i numit theta, deși este un
mai puțin frecvente.
Dar asta înseamnă că doar cele două limite, în acest caz, sunt aceleași.
>> Deci fuzioneze fel, ceea ce face acest lucru într-adevăr se reduce la pentru noi?
Ei bine, amintesc de motivație.
Permiteți-mi să trag un alt animație care nu ne-am uita la ultima dată.
Aceasta, aceeași idee, dar este un pic mai mare.
Și am de gând să merg mai departe și subliniază Primul - avem un fel de inserție pe
stânga sus, apoi un fel de selecție, fel balon, o serie de alte tipuri -
coajă și rapid - pe care nu am vorbit despre, și heap și îmbinarea fel.
>> Deci, cel puțin să încerce să se concentreze ochii pe primele trei din partea stângă și apoi
fuzioneze fel atunci când fac clic acest săgeată verde.
Dar voi lăsa toate acestea alerga, doar pentru a vă dau un sentiment al diversității
algoritmi care există în lume.
Am de gând să lase acest termen pentru doar câteva secunde.
Și dacă te concentrezi ochii - alege o algoritm, se concentreze pe ea pentru doar o
secunde - veți începe să vedeți model care este de punere în aplicare.
>> Merge fel, notificare, se face.
Sort Heap, un fel rapid, coajă -
deci se pare că am introdus trei mai grave algoritmi de săptămâna trecută.
Dar asta e bine că suntem aici, astăzi, pentru a uita-te la îmbinare fel, care este unul dintre
cele mai ușor este să se uite la, chiar deși, probabil, va indoi mintea ta
doar un pic.
Aici putem vedea cât de mult un fel de selecție e de rahat.
>> Dar, pe de alta parte, este foarte usor de implementat.
Și poate pentru Set P 3, care este unul din algoritmi ai ales să pună în aplicare
pentru ediția standard.
Foarte bine, perfect corect.
>> Dar, din nou, ca n devine mare, dacă aveți alege să pună în aplicare un algoritm mai rapid
ca fuzioneze fel, șansele sunt în mai mare și intrări mai mari, codul este doar
va alerga mai repede.
Site-ul dvs. va merge mai bine.
Utilizatorii vor fi mai fericit.
Și astfel există aceste efecte de fapt, oferindu-
ne unele gândit mai profund.
>> Deci, haideți să aruncăm o privire la ceea ce merge un fel este de fapt despre toate.
Lucrul interesant este faptul că fuzionarea fel este doar aceasta.
Acest lucru este, din nou, ceea ce am numit pseudocod, fiind pseudocod
Engleză-ca sintaxa.
Și simplitatea este un fel de fascinant.
>> Deci pe intrarea de n elemente - astfel încât înseamnă doar, aici e un tablou.
Are lucruri n în ea.
Asta e tot ce spui acolo.
>> Daca n este mai mic de 2, întoarce.
Deci, asta e doar cazul trivial.
Dacă n este mai mică de 2, atunci evident e 1 sau 0, caz în care lucru
este deja sortat sau inexistente, Deci, doar reveni.
Nu e nimic de făcut.
Deci, asta e un caz simplu de a smulge.
>> Altfel, avem trei etape.
Sorta jumătatea stângă a elementelor, un fel jumătatea din dreapta a elementelor,
și apoi îmbinați reprize sortate.
Ceea ce este interesant aici este faptul că Sunt un fel de punting, nu?
Există un fel de definiție circulară la acest algoritm.
În ce sens este acest algoritm circulară definiție?
>> Audiența: [inaudibil].
>> DAVID MALAN: Da, algoritmul meu de sortare, două dintre măsurile sale sunt "un fel
ceva. "Si astfel încât imploră întrebare, ei bine, ce am de gând să utilizeze
pentru a sorta jumătatea stângă și jumătatea din dreapta?
Și frumusețea aici este că, chiar dacă din nou, acest lucru este mintea-îndoire
parte potențial, puteți utiliza aceeași algoritm pentru a sorta jumătatea stângă.
>> Dar stai un minut.
Când ți se spune pentru a sorta jumătatea stângă, care sunt cele două
pași va fi următorul?
Vom sorta jumătatea stângă a jumătatea din stânga și din dreapta
jumătate din jumătatea stângă.
La naiba, cum pot sorta pe cei doi jumătăți, sau sferturi, acum?
>> Dar e în regulă.
Avem un algoritm de sortare aici.
Și chiar dacă s-ar putea face griji, la Primul este un fel de infinit
bucla, este un ciclu care este niciodată va termina - este de gând să
pune capăt o dată ce se întâmplă?
Odată n este mai mic de 2.
Care în cele din urmă se va întâmpla, pentru că dacă vă păstrați reducerea la jumătate și
reducerea la jumătate de înjumătățire aceste reprize, cu siguranță în cele din urmă ai de gând să se încheie
cu doar 1 sau 0 elemente.
La ce punct, acest algoritm spune că ești terminat.
>> Deci, adevărata magie în acest Algoritmul pare să fie în
acest pas final, care fuzionează.
Această idee simplă doar fuzionează două lucruri, asta e ceea ce se întâmplă în cele din urmă
pentru a ne permite să rezolve o serie de, să zicem, opt elemente.
Deci, am opt mai multe bile de stres sus aici, opt bucăți de hârtie, și unul
Google Glass -
care pot sa pastrez.
>> [Râsete]
>> DAVID MALAN: Dacă am putea avea opt voluntari, și să vedem dacă putem
juca acest lucru, așa.
Wow, OK.
Informatica devine distractiv.
Bine.
Deci, cum despre tine trei, Cea mai mare parte acolo.
Patru în spate.
Și cum despre vă vom face trei în acest rând?
Și patru în față.
Deci, opt, haide sus.
>> [Râsete]
>> DAVID MALAN: Sunt de fapt Nu sunt sigur ce este.
Este bile de stres?
Lămpile de birou?
Materialul?
Internetul?
>> OK.
Deci, vin pe sus.
Cine ar dori -
continua sa vina sus.
Să vedem.
Și acest lucru vă pune în locația -
sunteți într-o locație.
Uh-oh, așteptați un minut.
1, 2, 3, 4, 5, 6, 7 - oh, bine.
În regulă, suntem bine.
În regulă, deci toată lumea are un loc, dar nu pe sticlă Google.
Lasă-mă să coadă astea.
Care e numele tău?
>> MICHELLE: Michelle.
>> DAVID MALAN: Michelle?
Bine, ai să arate ca tocilar, dacă e în regulă.
Ei bine, eu nu prea, cred, pentru doar o clipă.
În regulă, așteptare.
Am fost încercarea de a veni cu un caz de utilizare pentru Google Glass, iar noi
gandit ca ar fi distractiv de a face doar acest lucru atunci când oamenii sunt pe scena.
Vom înregistra lumea din punctul lor de vedere.
Bine.
Nu este, probabil, ceea ce Google destinate.
Bine, dacă nu te superi poartă acest lucru pentru următorii minute incomode,
care ar fi minunat.
>> În regulă, deci avem aici o serie de elemente, și care matrice, conform
bucăți de hârtie din acesti oameni " mâini, este în prezent nesortat.
>> MICHELLE: Oh, asta e așa de ciudat.
>> DAVID MALAN: Este destul de mult la întâmplare.
Și într-o clipă, vom încerca pentru punerea în aplicare a fuziona fel împreună
și a vedea în cazul în care perspectiva cheie este.
Și truc aici cu îmbinare fel este ceva ce nu ne-am asumat încă.
Avem de fapt nevoie de spațiu suplimentar.
Deci, ce se întâmplă să fie deosebit de interesant despre acest lucru este faptul că acestea
baieti sunt de gând să se miște un pic bit, pentru că am de gând să presupunem că
există o serie suplimentară de spațiu, spune, chiar în spatele lor.
>> Deci, dacă ei sunt în spatele scaunului lor, că este matrice secundar.
Dacă sunt așezați aici, că e matrice primar.
Dar aceasta este o resursă pe care o avem nu de indatorare pana acum cu bule
fel, cu un fel de selecție, cu fel de insertie.
Recall săptămâna trecută, toată lumea doar fel de amestecate în loc.
Ei nu au folosit nici o memorie suplimentară.
Am făcut cameră pentru persoane cu oamenii se deplasează în jurul.
>> Deci, aceasta este o perspectiva cheie, de asemenea.
E un compromis, în general, în informatică, de resurse.
Dacă doriți să accelereze ceva ca timp, ai de gând să
trebuie să plătească un preț.
Iar una dintre aceste prețuri este foarte des spațiu, cantitatea de memorie sau hard-
spațiu pe disc pe care îl utilizați.
Sau, sincer, suma de timp programator.
Cât de mult timp este nevoie de tine, om, să pună în aplicare de fapt, unele mai mult
algoritm complicat.
Dar pentru ziua de azi, trade-off este timp și spațiu.
>> Deci, dacă voi putea ține doar în sus dvs. Numerele astfel încât să putem vedea că ești
într-adevăr, de potrivire 4, 2, 6, 1, 3, 7, 8.
Excelent.
Așa că am de gând să încerc să orchestreze lucruri, dacă voi putea doar
urmeze exemplul meu aici.
>> Așa că am de gând să pună în aplicare, în primul rând, Primul pas al pseudocod, care este
pe intrarea de n elemente, dacă n este mai puțin de 2, apoi să se întoarcă.
Evident, că nu aplică, așa că am muta pe.
Deci sorta jumătatea stângă a elementelor.
Asta înseamnă că am de gând să se concentreze meu atenție pentru o clipă la aceste
patru tipi aici.
Bine, ce fac viitoare fac?
>> Audiența: Sortarea jumătatea stângă.
>> DAVID MALAN: Deci, acum trebuie să-și rezolve jumătatea din stânga a acestor baieti.
Pentru ca din nou, presupune să te Scopul este de a sorta jumătatea stângă.
Cum faci asta?
Doar urmați instrucțiunile, chiar deși noi o facem din nou.
Deci sorta jumătatea stângă.
Acum, eu sunt de sortare acești doi tipi.
Ce urmează?
>> Audiența: Sortarea jumătatea stângă.
>> DAVID MALAN: sortează jumătatea stângă.
Deci, acum acestea, acest scaun aici, este o listă de dimensiune 1.
Și care e numele tău din nou?
>> PRINCESS DAISY: Printesa Daisy.
>> DAVID MALAN: Printesa Daisy este aici.
Și astfel ea este deja sortate, deoarece lista este de dimensiuni 1.
Ce trebuie să fac viitoare?
OK, se întoarcă, pentru că lista este de Dimensiunea 1, care este mai mică de 2.
Atunci, ce e următorul pas?
Și acum trebuie să fel de revină în mintea ta.
>> Sorta jumătatea din dreapta, care este -
Care e numele tău?
>> LINDA: Linda.
>> DAVID MALAN: Linda.
Și ce facem acum că avem o listă de dimensiune 1?
>> Audiența: retur.
>> DAVID MALAN: grijă.
Ne întoarcem în primul rând, iar acum a treia pas - și dacă am un fel de-l descrie prin
îmbrățișând cele două locuri acum, acum am Trebuie să fuzioneze aceste două elemente.
Deci, acum, din păcate, elementele sunt în ordine.
Dar asta e în cazul în care procesul de fuziune începe să devină convingătoare.
>> Deci, dacă voi putea sta în picioare pentru doar o clipă, am de gând să nevoie de tine, într-un
clipă, să-și intensifice în spatele scaunului.
Și dacă Linda, deoarece 2 este mai mici decât 4, de ce nu
ai venit în jurul primul?
Stai acolo.
Deci, Linda, ai venit în jurul primul.
>> Acum, în realitate, dacă e doar un tablou am putea să o mut în timp real
Din acest scaun la acest loc.
Imaginați-vă că a avut unele constante număr de pași 1.
Și acum -
dar avem nevoie pentru a pune în prima locatie aici.
>> Și acum, dacă ai putea veni în jurul, De asemenea, vom
fie în locație două.
Și chiar dacă acest lucru se simte ca este a lua un timp, ceea ce e frumos acum este
că jumătatea din stânga a jumătate din stânga este acum sortat.
Deci, ce a fost următorul pas, dacă ne acum înapoi mai departe în poveste?
>> Audiența: Jumătatea din dreapta.
>> DAVID MALAN: Sortarea jumătatea din dreapta.
Deci, voi avea de a face acest lucru, de asemenea.
Deci, dacă ai putea sta în picioare pentru o clipă?
Și care e numele tău?
>> JESS: Jess.
>> DAVID MALAN: Jess.
OK, deci Jess este acum la stânga jumătate din jumătatea dreaptă.
Și astfel ea este o listă de dimensiune 1.
E evident sortate.
Și numele tău din nou?
>> MICHELLE: Michelle.
>> DAVID MALAN: Michelle este, evident, o listă de dimensiune 1.
Ea deja sortate.
Deci, acum magia se întâmplă, procesul de fuziune.
Deci, cine o să vină mai întâi?
Evident, Michelle.
Deci, dacă ai putea veni în spate.
Spatiul pe care il avem la dispozitie pentru ea acum este chiar în spatele acest scaun aici.
Și acum, dacă ai putea veni înapoi, de asemenea, acum avem, să fie clar, două
jumătăți, fiecare de mărime 2 -
și doar de dragul descrierea lui, dacă aveți ar putea face un pic de spațiu -
o pe jumătate aici, o jumătate chiar aici.
>> Derula mai departe în poveste.
Ce pas este următorul?
>> Audiența: Merge.
>> DAVID MALAN: Deci, acum avem de a fuziona.
Deci OK, deci acum, din fericire, am doar eliberat patru scaune.
Deci, ne-am folosit de două ori la fel de mult de memorie, dar ne putem da flip-flop între
cele două matrice.
Deci, ce număr este de a veni în primul rând?
Deci Michelle, evident.
Deci, vin în jurul și să ia locul aici.
Și apoi numărul 2 este, evident, următor, astfel încât ai venit aici.
Numărul 4, numărul 6.
Și din nou, chiar dacă există o pic de mers pe jos implicat,
într-adevăr, acestea ar putea întâmpla instantaneu, prin mutarea unul -
OK, bine jucat.
>> [Râsete]
>> DAVID MALAN: Și acum suntem intr-o forma destul de buna.
Jumătatea din stânga a întregii de intrare a fost sortate.
În regulă, deci ăștia au avut avantajul de a mea -
Cum a ajuns la toate fetele de pe a plecat și toți băieții de pe dreapta?
>> OK, deci băieților întoarce acum.
Deci, nu te voi plimba prin acești pași.
Vom vedea dacă putem aplica din nou același pseudocod.
Dacă doriți să mergeți mai departe și se ridice în picioare, și voi, permiteți-mi să vă dau MIC.
Vezi dacă nu poți reproduce ceea ce ne-am facut aici, pe
celălalt capăt al listei.
Cine are nevoie să vorbească în primul rând, pe baza algoritmului?
Deci, explica ceea ce faci înainte de a face orice miscari picior.
>> SPEAKER 1: În regulă, deci din Sunt jumătatea stângă a
jumătatea din stânga, mă voi întoarce.
Dreapta?
>> DAVID MALAN: Bine.
>> SPEAKER 1: Și apoi -
>> DAVID MALAN: Cine face MIC du-te la următorul?
>> SPEAKER 1: numărul următor.
>> DIFUZOR 2: Deci, eu sunt jumătatea din dreapta din jumătatea stângă a
jumătatea din stânga, și mă voi întoarce.
>> DAVID MALAN: Bine.
Veți reveni.
Deci, acum ce e sus, lângă pentru voi doi?
>> DIFUZOR 2: Vrem vedem cine e mai mic.
>> DAVID MALAN: Exact.
Vrem să fuzioneze.
Spatiul pe care il vom folosi pentru a fuziona te în, chiar dacă ele sunt
evident sortat deja, vom să urmeze acelasi algoritm.
Deci, cine merge in spate prima?
Deci 3, și apoi 7.
Și acum MIC merge la tipii ăștia, bine?
>> SPEAKER 3: Deci, eu sunt jumătatea din dreapta a jumătatea din stânga, și n mea este mai mică decât
1, așa că eu sunt doar de gând să treacă -
>> DAVID MALAN: Bine.
>> DIFUZOR 4: Sunt jumătatea din dreapta a Jumătatea din dreapta a jumătatea din dreapta, și eu sunt
De asemenea, o singură persoană, așa că eu sunt O să se întoarcă.
Deci, acum am îmbinare.
>> SPEAKER 3: Deci, ne întoarcem.
>> DAVID MALAN: Deci, te duci în spate.
Deci 5 trece mai întâi, apoi 8.
Și acum public, care este pas trebuie să înapoi acum
înapoi în mințile noastre?
>> Audiența: Merge.
>> DAVID MALAN: Fuziunea jumătate la stânga și la dreapta jumătate din jumătatea stângă originale.
Deci, acum -
și doar pentru a face acest lucru clar, face un pic de spațiu
dintre voi doi.
Deci, acum că sunt cele două liste, stânga și dreapta.
Deci, cum putem acum te voi merge în primul rand de scaune din nou?
>> 3 merge primul.
Apoi, 5, evident.
Apoi, 7, 8 și acum.
OK, iar acum suntem?
>> Audiența: nu se face.
>> DAVID MALAN: Nu sa efectuat, deoarece evident, nu e un pas rămas.
Dar, din nou, motivul pentru care eu sunt, folosind acest jargon ca "înapoi în mintea ta,"
e pentru că e într-adevăr ceea ce se întâmplă.
Vom trece prin toate aceste etape, dar noi suntem un fel de pauză pentru o
clipă, mai adânc scufundare în algoritm, oprindu-se pentru o clipă,
scufundări adânc în algoritmul, și acum avem de a sorta de înapoi în noastre
mintea și anula toate aceste straturi că am un fel de pus în așteptare.
>> Deci, acum avem două liste de dimensiune 4.
Dacă voi putea sta în picioare pentru ultima dată și să facă un pic de spațiu aici pentru a
face clar că acest lucru este în stânga jumătate din original,
jumătatea dreaptă a originalului.
Cine e primul număr pe care le Trebuie să trage în spate?
Michelle, desigur.
>> Așa că am pus Michelle aici.
Și care are numărul 2?
Numărul 2 vine pe spate, de asemenea.
Numărul 3?
Excelent.
Numărul 4, numărul 5, numărul 6, numărul 7, și numărul 8.
>> OK, deci m-am simtit ca o mulțime de pași, pentru sigur.
Dar acum să vedem dacă nu putem confirma un fel de intuitiv ca aceasta
Algoritmul fundamental, în special în ceea n devine foarte mare, așa cum am văzut
cu animații, este fundamental repede.
Deci, eu susțin acest algoritm, în cel mai rău caz și chiar și în cel mai bun caz,
este mare O, de n ori log n.
Că este, există un aspect al acestei algoritm care are n trepte, dar
există un alt aspect undeva în că iterație, care looping, care
ia log n pasi.
Putem pune degetul pe ceea ce cei două numere se referă la?
Ei bine, în cazul în care -
Unde MIC merge?
>> SPEAKER 1: Ar n log fi de rupere-ne în sus, în două -
împărțirea la doi, în esență.
>> DAVID MALAN: Exact.
Orice timp vom vedea în orice algoritm astfel în prezent, nu a fost acest model de
divizare, divizare, divizare.
Și este de obicei redus a ceva care este
logaritmică, jurnal de bază 2.
Dar ar putea fi într-adevăr nimic, dar jurnal de bază 2.
>> Acum, ce putem spune despre n?
Văd că am un fel de tine divizat baieti - te divizat, te divizat,
ai împărțit, tu divizat.
În cazul în care se termină provin de la?
>> Deci, este fuziunea.
Deoarece cred despre el.
Când îmbinați opt oameni împreună, prin care jumătate din ele sunt un set de patru
iar cealaltă jumătate sunt încă set de patru, cum te duci
despre a face fuziunea?
Ei bine, ați făcut-o destul de intuitiv.
>> Dar, dacă am făcut-o în schimb un pic mai mult metodic, aș fi arătat la
persoana cea mai din stânga primul cu stânga mea parte, a subliniat la persoana din stânga
din care jumătate cu mâna dreaptă, și doar ulterior plimbat prin
lista, arătând la cel mai mic element de fiecare dată, se deplasează degetul meu de peste si
peste cum este necesar în întreaga listă.
Dar ceea ce este esențial despre această fuziune Procesul este am comparat aceste perechi
de elemente.
Din jumătatea dreaptă și pe partea stângă, jumătate, eu nu o dată backtracking.
>> Astfel încât fuziunea în sine este de a lua nu mai mult de n pași.
Și cum de multe ori am avea pentru a face ca fuziunea?
Ei bine, nu mai mult de N, și ne-am a văzut că cu îmbinare finală.
Și dacă faci ceva care are log n pasi n ori, sau invers,
o să ne n ori log n da.
>> Și de ce este asta mai bine?
Ei bine, dacă știm deja că log n este mai bună decât n - dreapta?
Am văzut în căutare binară, cartea de telefon de exemplu, log n a fost cu siguranta
mai bine decât liniară.
Asta înseamnă că n ori log n este cu siguranta mai bine decât de n ori un alt
n, AKA n pătrat.
Și asta este ceea ce în cele din urmă am simt.
>> Atât de mare rundă de aplauze, în cazul în care am putea, pentru tipii ăștia.
>> [Aplauze]
>> DAVID MALAN: Și darurile voastre despărțire - s-ar putea păstra numerele,
dacă doriți.
Și darul tău despărțire, ca de obicei.
Oh, și vă vom trimite imagini, Michelle.
Mulțumesc.
Bine.
Serviți-vă la o minge de stres.
>> Și lasă-mă să trageți în sus, în același timp, prietenul nostru Rob Bowden de a oferi
perspectivă oarecum diferită pe aceasta, deoarece vă puteți gândi la aceste
pași se întâmplă într-o oarecum mod diferit.
De fapt, set-up pentru ceea ce este Rob despre să ne arate presupune că ne-am
deja făcut până împărțirea a Lista mare în opt liste mici,
fiecare dintre mărimea 1.
>> Deci, suntem schimbarea pseudocod o pic doar pentru a sorta de a obține de la
Ideea de bază de modul în care funcționează fuziunea.
Dar timpul de funcționare a ceea ce e pe cale să facă este încă
va fi la fel.
Și din nou, set-up aici este că el este a început cu opt liste de dimensiune 1.
Deci ai ratat partea în care e de fapt făcut log n, n log, log n
împărțirea de intrare.
>> [Redare video]
>> -Asta pentru pas cuiva.
Pentru pasul doi, în mod repetat, fuzioneze perechi de liste.
>> DAVID MALAN: Hm.
Numai audio vine din computerul meu.
Să încercăm din nou.
>> -Doar arbitrar alege care - acum avem patru liste.
Aflați mai înainte.
>> DAVID MALAN: Acolo mergem.
>> -Fuziunea 108 și 15, ajungem cu lista de 15, 108.
Fuzionarea 50 și 4, am termina cu 4, 50.
Fuzionarea 8 și 42, am termina cu 8, 42.
Și fuzionează 23 și 16, am termina cu 16, 23.
>> Acum, toate listele noastre sunt de dimensiuni 2.
Observați că fiecare din patru liste sunt sortate.
Astfel încât să putem începe fuziunea perechi de liste din nou.
Fuzionarea 15 și 108 și 4 și 50, am Primul ia 4, apoi 15, apoi
50, apoi 108.
Fuzionarea 8, 42 și 16, 23, vom lua 8, apoi 16, apoi 23,
apoi 42.
>> Așa că acum avem doar două liste de dimensiuni 4, fiecare dintre care este sortat.
Deci, acum ne uni aceste două liste.
În primul rând, vom lua 4, apoi vom lua 8, atunci vom lua 15, apoi 16, apoi
23, apoi 42, apoi 50, apoi 108.
>> [END redare video]
>> DAVID MALAN: Din nou, notificare, el nu atins un anumit cupa mai mult de o dată
după avansarea dincolo de ea.
Deci, el nu a mai repeta.
Deci, el este mereu în mișcare la o parte, și că este în cazul în care ne-am n noastră.
>> De ce nu permiteți-mi trage o animație că am văzut mai devreme, dar de data aceasta
concentrându-se doar pe îmbinare fel.
Lasă-mă să merg mai departe și zoom în acest aici.
În primul rând permiteți-mi să aleagă o intrare aleator, amplifica aceasta, și se pot sorta a vedea
ceea ce am luat de la sine, mai devreme, fuzioneze fel este, de fapt face.
>> Astfel observa că veți obține aceste jumătăți sau aceste trimestre sau acestea optimi de
Problema care dintr-o dată începe să ia formă bună.
Și apoi în cele din urmă, veți vedea la la sfârșit că bam,
totul este fuzionat împreună.
>> Deci, acestea sunt doar trei diferite ia pe aceeasi idee.
Dar perspectiva cheie, la fel ca decalajul și cuceri în prima clasă,
a fost că ne-am decis să împartă cumva problema în ceva mare, în
ceva fel de identice în spirit, dar mai mici și mai mici și mai mici
și mai mici.
>> Acum, un alt mod distractiv de a sorta de cred despre acestea, chiar dacă nu este
gând să vă dau același intuitiv înțelegere, este
animația următoare.
Deci, acesta este un video de cineva a pus împreună ca asociat diferite
sunete cu diversele operațiuni de un fel de inserție, de îmbinare fel, și
pentru un cuplu de alții.
Deci, într-un moment, am de gând să lovit redare.
Este vorba despre un minut.
Și chiar dacă puteți vedea în continuare modele întâmplă, de data aceasta puteți
De asemenea, auzi cum aceste algoritmi sunt efectuarea în mod diferit și cu
oarecum diferite modele.
>> Aceasta este un fel de inserare.
>> [TONURI DE JOC]
>> DAVID MALAN: Se încearcă din nou pentru a insera fiecare element
în cazul în care acesta face parte.
Aceasta este un fel balon.
>> [TONURI DE JOC]
>> DAVID MALAN: Și tu poți un fel de simt cât de relativ putina munca se face
pe fiecare pas.
Aceasta este ceea ce plictiseala suna.
>> [TONURI DE JOC]
>> DAVID MALAN: Aceasta este un fel de selecție, în cazul în care vom selecta elementul ne-o dorim de
trece prin din nou și din nou și din nou și-l pune la început.
>> [TONURI DE JOC]
>> DAVID MALAN: Aceasta este îmbinarea fel, care puteți începe cu adevărat să se simtă.
>> [TONURI DE JOC]
>> [Râsete]
>> DAVID MALAN: Ceva numit gnome fel, care nu ne-am uitat la.
>> [TONURI DE JOC]
>> DAVID MALAN: Deci, lasă-mă să văd, acum, distras în timp ce sperăm sunt de
muzica, dacă pot aluneca un pic bit de matematica aici.
Deci, există un al patrulea mod în care putem cred despre ceea ce înseamnă acestea
funcții să fie mai rapid decât cele pe care le-am văzut înainte.
Și dacă vii la cursul de un fundal matematică, te
de fapt, știți probabil deja că poate palmă un termen pe aceasta tehnica -
anume recursivitate, o funcție care se numește cumva.
>> Și din nou, reamintească faptul că un fel îmbinare pseudocod a fost recursiv, în sensul
că una dintre etapele de îmbinare sortare lui a fost de a apela un fel -
care este, ea însăși.
Dar, din fericire, pentru că ne-am păstrat de asteptare fel, sau fuziona fel,
în mod specific, pe o mici și mai mici și lista mai mici, cele din urmă am
fund datorită ceea ce vom numi un caz de bază, în cazul hard-coded care
spus dacă lista este mic, mai puțin de 2 în acest caz, doar reveni imediat.
Dacă nu am avea acest caz special, Algoritmul nu ar fund afară,
și v-ar lua într-adevăr într-o buclă infinită cu adevărat pentru totdeauna.
>> Dar să presupunem că am vrut să pun acum unele numere pe aceasta, din nou, folosind n
ca mărimea de intrare.
Și am vrut să te întreb, ce-i timpul total implicate în
rulare fel merge?
Sau, mai general, ceea ce este Costul ei în timp?
>> Ei bine, este destul de ușor să evalueze.
Daca n este mai mic de 2, timpul implicat în sortarea n elemente,
în cazul în care n este 2, este 0.
Pentru că ne-am întoarce.
Nu e nici o lucrare de făcut.
Acum, fără îndoială, poate e cu un pas sau doi pași pentru a afla suma de
de lucru, dar e destul de aproape de 0, care Mă duc să spun nici o lucrare este
necesar dacă lista este atât de mic să fie neinteresante.
>> Dar acest caz este interesant.
Cazul recursiv a fost ramura de pseudocod care a spus altceva, un fel
jumătatea din stânga, sorta dreapta jumătate, fuzionarea celor două jumătăți.
Acum de ce face acest lucru expresie reprezinta acea cheltuiala?
Ei bine, T n înseamnă doar timp pentru a sorta n elemente.
Și apoi pe partea dreaptă a semnul egalității acolo, T de n divizat
de 2 se referă la costul de ce?
Sortarea jumătatea stângă.
Alte T de n împărțit la 2 este probabil cu referire la costul
sorta jumătatea din dreapta.
>> Și apoi n plus?
Este fuziunea.
Pentru că dacă aveți două liste, una dintre Dimensiunea n peste 2 și un alt de dimensiune n
peste 2, trebuie să atingeți în esență, fiecare dintre aceste elemente, la fel ca Rob
a atins fiecare dintre cupe, și doar așa cum am arătat la fiecare dintre
voluntari pe scena.
Deci, n este în detrimentul de a fuziona.
>> Acum, din păcate, această formulă Este, de asemenea, în sine recursiv.
Deci, dacă a pus întrebarea, dacă n este, spune, 16, în cazul în care există 16 de oameni de pe scena
sau 16 Cupe la film, câte totală măsuri este nevoie pentru a le sorta
cu îmbinare fel?
Nu este de fapt un răspuns evident, pentru că acum aveți pentru a sorta de
răspunde recursiv această formulă.
>> Dar asta e bine, pentru că lasă-mă să propună ce facem următoarele.
Timpul necesar pentru a sorta 16 de persoane sau 16 Cupe va fi reprezentat
în general, ca T de 16.
Dar care este egală, în conformitate cu nostru formula precedentă, de 2 ori valoarea
de timp este nevoie pentru a sorta 8 Cupe plus 16.
Și din nou, plus 16 este timpul să fuzioneze, și două ori T din 8 este
timp pentru a sorta jumătatea stângă și jumătate dreapta.
>> Dar, din nou, acest lucru nu este suficient.
Trebuie să se scufunde mai adânc.
Acest lucru înseamnă că trebuie să răspundă la întrebarea, ce este T de 8?
Ei bine, T de 8 este la doar 2 ori T de 4 plus 8.
Ei bine, ce-i T de 4?
T 4 este de doar 2 ori T de 2 plus 4.
Ei bine, ce-i T de 2?
T de 2 este de doar 2 ori T din 1 plus 2.
>> Și din nou, suntem un fel de a obține blocat în acest ciclu.
Dar este pe cale de a lovi că așa-numitul caz de bază.
Pentru că ce-i T de 1, am pretinde?
0.
Așa că acum, în sfârșit, putem lucra invers.
>> Dacă T din 1 este 0, eu pot merge acum înapoi o alinia la acest tip de aici, și eu pot
conectați la 0 pentru T de 1.
Deci, ceea ce înseamnă că este egală cu de 2 ori la zero, altfel cunoscut ca 0, plus 2.
Și astfel încât expresia întreg este 2.
>> Acum, dacă mă iau de T 2, al carei raspuns este de 2, conectați-l în linia de mijloc, T
de 4, care îmi dă de 2 ori 2 plus 4, deci 8.
Dacă atunci am conectați la 8 la precedenta linie, care îmi dă de 2 ori 8, 16.
Și dacă vom continua apoi că, odată cu 24, adăugând în 16, vom obține în final o
valoare de 64.
>> Acum, că, în sine, un fel de vorbește nimic la n notație,
Big O, omega care le-am vorbit despre.
Dar se pare că 64 este într-adevăr 16, mărimea de intrare,
jurnal de bază 2 din 16.
Și dacă acest lucru este un pic nefamiliar, doar cred că înapoi, și va veni înapoi
pentru tine în cele din urmă.
Dacă aceasta este baza log 2, e ca si cum 2 ridicat la ceea ce vă oferă 16?
Oh, e 4, deci este de 16 ori 4.
>> Și din nou, nu e mare lucru, dacă acest lucru este un fel de amintire încețoșată acum.
Dar pentru acum, să ia în credință că 16 log 16 este de 64.
Și astfel, într-adevăr, cu acest bun-simț simplu verifica, am confirmat -
dar nu s-au dovedit în mod formal -
că timpul de funcționare a merge fel este într-adevăr n log.
>> Deci, nu rău.
Este cu siguranta mai bine decat algoritmi care le-am văzut până acum, și
e pentru că am de indatorare, unul, o tehnica numita recursivitate.
Dar mai interesant decât atât, că noțiunea de divizare și cucerirea.
Din nou, cu adevărat saptamana 0 chestia asta chiar acum este recurente într-o
mod mult mai convingător.
>> Acum, un exercițiu pic de distracție, dacă ați nu făcut acest lucru - și, probabil,
nu ar trebui, din cauza fel de normale oamenii nu cred că pentru a face acest lucru.
Dar, dacă mă duc la google.com și dacă Vreau să învăț ceva despre
recursivitate, Enter.
>> [Râsete]
[Mai multe râsete]
DAVID MALAN: Bad glumă răspândirea încet.
[Râsete]
DAVID MALAN: Doar în cazul în care, e acolo.
Nu am scrie greșit, și nu e de glumă.
Bine.
Explicați-l la oamenii de lângă tine dacă ea nu a destul de apasat încă.
Dar recursivitate, în general, se referă la procesul de o funcție asteptare
în sine, sau, mai general, împărțind-o Problema in ceva ce poate fi
rezolvate treptat prin rezolvarea identice probleme reprezentative.
>> Ei bine, hai sa unelte schimbare pentru doar o clipă.
Ne place să se încheie la anumite clipe, Să începem de a stabili
etapă, timp de câteva minute, pe o idee foarte simplă -
că de pompare două elemente, nu?
Toate aceste algoritmi am fost vorbesc despre ultimii
prelegeri implica unele un fel de pompare.
Astăzi a fost vizualizat de ei obtinerea afară din scaunele lor și
de mers pe jos în jurul, dar în cod, ne-ar ia doar un element dintr-o matrice
și plop-l într-un alt.
>> Deci, cum putem merge despre a face acest lucru?
Ei bine, lasă-mă să merg mai departe și scrie un program de rapid aici.
Am de gând să merg mai departe și de a face aceasta ar fi următoarele.
Să numim asta -
ceea ce vrem să numim asta?
>> De fapt, nu.
Lasă-mă înapoi.
Nu vreau să fac asta Cliffhanger încă.
Acesta va strica distractia.
Să facem acest lucru în schimb.
>> Să presupunem că vreau să scriu un pic program și care îmbrățișează acum această
Ideea de recursivitate.
Am facut un fel de ajuns înainte de mine acolo.
Am de gând să faceți următoarele.
>> În primul rând, o scurtă includ standard io.h, precum și o includ de cs50.h.
Și apoi am de gând să merg mai departe și declare nul int main
în mod obișnuit.
Am realizat că am greșit în botezarea dosar, astfel încât permiteți-mi să adăugați o C extensie. aici atât de
că putem compila în mod corespunzător.
Începe această funcție.
>> Și funcția vreau să scriu, destul de pur și simplu, este una care cere
utilizator pentru un număr și apoi se adaugă în sus toate numerele dintre care
numărul și, să zicem, 0.
Deci, în primul rând am de gând să merg mai departe și declare n int.
Apoi am copia un cod care am folosit pentru un timp.
În timp ce ceva este adevărat.
Voi reveni la faptul că într-o clipă.
>> Ce vreau să fac?
Vreau să spun printf pozitiv întreg rog.
Și apoi am de gând să spune n se obține Int.
Deci, din nou, un cod șabloane pe care le-am folosit înainte.
Și am de gând să facă acest lucru în timp ce n este mai mic de 1.
Deci, acest lucru va asigura că utilizatorul dă-mi un număr întreg pozitiv.
>> Și acum am de gând să faceți următoarele.
Vreau să adune toate numerele între 1 și n și, sau 0 și n,
echivalent, pentru a obține suma totală.
Deci, mare simbolul Sigma pe care le-ar putea aminti.
Așa că am de gând să fac acest lucru de prima convocare o funcție numită sigma,
trecând-o în n, iar apoi am de gând să spune printf, raspunsul este chiar acolo.
>> Deci, pe scurt, mă și int de la utilizator.
Eu asigura că este pozitiv.
Declar o variabilă numită răspuns de tip int și se păstrează într-o retur
Valoarea Sigma, trece in n ca intrare.
Și apoi am imprima acest răspuns.
>> Din păcate, chiar dacă Sigma suna ca ceva care ar putea fi în
fișierul math.h, declarația sa, de fapt nu este.
Deci, asta e OK.
Pot pune în aplicare această eu.
Am de gând să pună în aplicare o funcție numită Sigma, și se va lua o
parametru -
să-i zicem doar m, doar așa că este diferit.
Și apoi aici, am de gând să spun, bine, dacă m este mai mică de 1 - aceasta este o
program foarte neinteresant.
Așa că am de gând să merg mai departe și reveni imediat 0.
Pur si simplu nu are sens pentru a aduna toate numere intre 1 si m, dacă m
este ea însăși 0 sau negativ.
>> Și apoi am de gând să merg mai departe și de a face acest lucru foarte iterativ.
Am de gând să fac acest fel de old-school, și am de gând să merg mai departe
și să spun că am de gând să declara o sumă să fie 0.
Apoi, am de gând să aibă o pentru buclă de Int -
și lasă-mă să o fac pentru a se potrivi noastre Codul de distribuție, astfel încât să aibă o copie
la domiciliu. int i se 1 la până la i este mai mică sau egală cu m.
I, plus, plus.
Și apoi în interiorul acestei pentru buclă -
suntem aproape acolo -
suma devine sumă, plus 1.
Și apoi am de gând să returneze suma.
>> Așa că am făcut acest lucru mai repede, destul Desigur.
Dar, din nou, funcția principală e destul de simplu, bazat pe cod ne-am
scris până acum.
Utilizează dublu bucla pentru a obține un rezultat pozitiv int de la utilizator.
Apoi trec ca int pentru o nouă funcție numita Sigma, numindu-l, din nou, n.
Și am stoca valoarea returnata, răspunsul de la cutia neagră în prezent
cunoscut ca sigma, într-o variabilă numit răspuns.
Apoi am imprima.
>> Dacă vom continua acum povestea, modul în care este pusă în aplicare Sigma?
Eu propun să pună în aplicare după cum urmează.
În primul rând, un pic de eroare de verificare pentru a vă asigura că utilizatorul nu este
încurcați cu mine și trece în o valoare negativă sau 0.
Apoi am declara o variabilă numită suma și setați-l la 0.
>> Și acum încep să se miște de la I este egal 1 tot drumul până la și inclusiv m,
pentru că vreau să includă toate Numerele de la unu la m, inclusiv.
Iar în interiorul acestei pentru buclă, eu doar fac suma devine orice este acum, plus
valoarea lui I.
Plus valoarea de i.
>> Ca o paranteza, dacă nu ați văzut acest lucru înainte, există unele zahăr sintactic
pentru această linie.
Pot să rescrie acest lucru ca pe plus i egali, doar pentru a mă salva câteva apăsări de taste
și să se uite un pic mai rece.
Dar asta e tot.
Este funcțional acelasi lucru.
>> Din păcate, acest cod de nu va compila încă.
Dacă I ​​a alerga fac Sigma 0, cum am Am de gând să se țipe la?
Ce va să nu vrea?
>> Audiența: [inaudibil].
>> DAVID MALAN: Da, nu am declarat funcția de ridicare de sus, dreapta?
C este un fel de prost, în sensul că numai face ceea ce spune să facă, și tu
trebuie să se facă în ordinea asta.
Și așa, dacă am lovit Introduceți aici, am de gând să primi un avertisment cu privire la Sigma implicită
declarație.
>> Oh, nu o problemă.
Eu pot merge până la partea de sus, și pot spun, bine, stai un minut.
Sigma este o funcție care returnează un întreg și se așteaptă o
Int ca intrare, punct și virgulă.
Sau am putea pune întreaga funcția sus principală, dar, în general, aș
recomanda împotriva că, deoarece este frumos de a avea întotdeauna principal în partea de sus, astfel
puteți arunca cu capul în dreapta și știu ce o Programul face prin citirea principală întâi.
>> Deci, acum, permiteți-mi clar pe ecran.
Remake-ul Sigma 0.
Totul pare pentru a verifica.
Permiteți-mi să ruleze Sigma 0.
Printre pozitiv.
Voi da numărul 3 să-l păstrați simplu.
Așa că ar trebui să-mi dea 3 plus 2 plus 1, deci 6.
Introduceți, și într-adevăr am lua 6.
>> Pot să fac ceva mai mare -
50, 12, 75.
La fel ca o tangentă, am de gând să fac ceva ridicol ca un foarte mare
număr, Oh, care de fapt a lucrat afară -
eh, eu nu cred că e bine.
Să vedem.
Să adevăr te pui cu el.
>> Asta-i o problemă.
Ce se întâmplă?
Codul nu e așa de rău.
Este încă liniar.
Fluierat este un efect bun, totuși.
Ce se întâmplă?
>> Nu sunt sigur dacă am auzit-o.
Deci, se dovedește - și aceasta este ca o paranteză.
Acest lucru nu este de bază pentru a Ideea de recursivitate.
Se pare, pentru că am încercat să reprezintă un astfel de număr mare, mai
probabil acesta fiind interpretat greșit prin C sub forma unui număr pozitiv nu,
dar număr negativ.
>> Nu am vorbit despre acest lucru, dar pare că există numere negative
în lume, în plus să numere pozitive.
Și mijloacele prin care se poate reprezintă un număr negativ
în esență, este, folosiți un bit special pentru a indica
pozitiv pe negativ.
Este un pic mai complex decât atât, dar asta e ideea de bază.
>> Deci, din păcate, în cazul în care C este confuz unul din aceste biți ca de fapt ceea ce înseamnă,
oh, acest lucru este un număr negativ, bucla mea aici, de exemplu, este de fapt niciodată
va termina.
Deci, dacă am fost de fapt de imprimare ceva din nou și din nou, ne-ar
vedea un întreg lot.
Dar, din nou, acest lucru este în afară de punctul.
Aceasta este de fapt doar un fel de curiozitate intelectuală care vom veni
înapoi în cele din urmă.
Dar pentru acum, aceasta este o corectă punerea în aplicare, dacă presupunem că
utilizatorul va furniza int care se potrivesc în int.
>> Dar eu susțin că acest cod, sincer, ar putea fi realizat atât de mult mai simplu.
În cazul în care obiectivul la îndemână este de a lua un număr ca m și aduna toate
numere între ea și 1, sau invers între 1 și-l, eu pretind
că pot împrumuta această idee că merge sortare a avut, care a fost de a lua o problemă
de această dimensiune și împărțind-o în ceva mai mic.
Poate că nu jumătate, dar mai mici, dar reprezentativ la fel.
Aceeași idee, dar o problemă mai mică.
>> Deci, eu sunt de fapt - lasă-mă să salvați acest fișier cu un număr de versiune diferit.
Vom numi această versiune 1 în loc de 0.
Și eu pretind că pot fapt reimplementa acest lucru în acest fel de
minte-îndoire fel.
>> Am de gând să lase o parte din ea singur.
Am de gând să spun dacă m este mai puțin mică sau chiar egală cu 0 -
Mă duc pentru a fi un pic mai mult anal acest moment
cu verificarea mea eroare -
Am de gând să merg mai departe și să se întoarcă 0.
Aceasta este arbitrară.
Eu pur și simplu a decide dacă utilizatorul dă-mi un număr negativ, eu sunt
întoarce 0, și ei ar fi trebuit să citească documentația mai îndeaproape.
>> Altele -
observa ceea ce am de gând să fac.
Mai am de gând să se întoarcă m plus -
ceea ce este Sigma de m?
Ei bine, Sigma de m plus m minus 1, plus minus 2 m, plus minus 3 m.
Nu vreau să scriu tot de asta.
De ce nu am punt?
Mă numesc recursiv cu un ușor Problema mai mic, punct și virgulă,
și-l numesc o zi?
>> Dreapta?
Acum, aici, de asemenea, s-ar putea simți sau vă faceți griji că aceasta este o buclă infinită care sunt
induce, prin care eu sunt de punere în aplicare Sigma sunand la Sigma.
Dar asta e perfect în regulă, pentru că am gândit înainte de a adăugat liniile care?
>> Audiența: [inaudibil].
>> DAVID MALAN: 23 to 26, care este meu dacă starea.
Pentru că ceea ce este frumos despre scădere aici, pentru că am păstra
predarea probleme sigma mici, mici probleme, mai mici - nu este
jumătate din dimensiunea.
Este doar un pas copil mic, dar asta e OK.
Pentru că în cele din urmă, vom lucra modul nostru de până la 1 sau 0.
Și odată ce ne-am lovit 0, sigma nu este O să se mai numesc.
O să se întoarcă imediat 0.
>> Astfel încât efectul, dacă aveți un fel de vânt aceasta in mintea ta, este de a adăuga m plus
m minus 1, plus minus 2 m, plus minus m 3, plus punct, punct, punct, m minus
m, în cele din urmă oferindu-vă 0, iar Efectul este în cele din urmă să se adauge toate
aceste lucruri împreună.
Deci, nu avem, cu recursivitate, rezolvat problema cu care ne
nu ar putea rezolva înainte.
Într-adevăr, versiunea 0 din prezenta, și fiecare Problema la data, a fost rezolvabil
cu doar folosind-o pentru bucle sau în timp ce bucle sau construcțiile similare.
>> Dar recursivitate, îndrăznesc să spun, ne dă un mod diferit de gândire despre
probleme, prin care, dacă putem lua o problema, împărțiți-l de la ceva
oarecum mare în ceva oarecum mai mici, eu pretind că putem rezolva
poate un pic mai elegant din punct de vedere de proiectare, cu mai puțin cod,
și poate chiar a rezolva problemele care ar să fie mai greu, așa cum vom în cele din urmă
a se vedea, rezolvarea pur iterativ.
>> Dar Cliffhanger pe care am făcut-o Vreau să ne lase în era aceasta.
Lasă-mă să merg mai departe și deschide un fișier de la -
de fapt, lasă-mă să merg și face acest lucru foarte repede.
Lasă-mă să merg mai departe și să propună următor.
Printre codul de astăzi este acest fișier aici.
Acest unul aici, noswap.
>> Deci, acesta este un program de prost mic, care Am bătut până ce pretenții să facă
următor.
În principal, se declară în primul rând o Int numit x și atribuie
valoarea 1.
Apoi se declară un Y Int și atribuie valoarea 2.
Apoi se imprimă ceea ce este x și y.
Apoi se spune, pompare, punct punct punct.
>> Apoi se pretinde a fi de asteptare o funcție numit de swap, trece în x și
y, dintre care ideea este că sperăm x și y vor veni înapoi
altfel, contrariul.
Apoi, ea pretinde schimbat!
cu un semn de exclamare.
Apoi se imprimă x și y.
>> Dar se pare că acest lucru foarte demonstratie simpla jos
aici este, de fapt buggy.
Chiar dacă am declara o temporar variabilă și punerea temporar o în
ea, apoi am realocarea o valoare a lui b -
care se simte rezonabil, pentru că am salvat o copie a unui in temp.
Apoi am actualiza b la egal tot ce a fost în temp.
Acest tip de joc coajă de mișcare a în b și b într-o prin folosirea acestui
-om de mijloc numit temp se simte perfect rezonabil.
>> Dar eu susțin că atunci când am rula acest cod, așa cum voi face acum -
lasă-mă să merg mai departe și lipiți-l aici.
Voi numi acest noswap.c.
Și, după cum sugerează și numele, acest lucru nu este Va fi un program corect.
Face noswap. / Nu de swap.
x este 1, y este 2, pompare, schimbat.
x este 1, y este 2.
Acest lucru este fundamental greșit, chiar deși acest lucru pare perfect
rezonabil pentru mine.
Și există un motiv, dar nu suntem de gând să dezvăluie motivul pentru care încă.
>> De acum doua Cliffhanger am vrut să vă las cu este aceasta, o
Anunțul de felul pe coduri promoționale.
Inovația noastră cu întârziere de zile din acest an a provocat un număr semnificativ
de întrebări, care a fost Nu intenția noastră.
Intenția acestor coduri promoționale, prin care, dacă faci parte din problemă
set devreme, obtinerea astfel o zi în plus, a fost într-adevăr pentru a ajuta la voi ajuta
vă începe devreme, un fel de către incentivizing tine.
Ne ajută să distribuie sarcina pe orelor de lucru mai bine, astfel încât
Este un fel de win-win.
>> Din păcate, cred că instrucțiunile mele nu au fost, până în prezent, foarte clar, așa
M-am întors în acest weekend și actualizate spec. în mare, obține un text la
explica gloanțe ca acestea.
Și doar să spun mai mult public, de implicite, seturi de probleme sunt datorate joi
la prânz, pe programa.
Dacă începe devreme, finisare parte din problema stabilit până miercuri la ora 12:00
PM, partea care se referă la un cupon cod, ideea este că puteți extinde
Termenul limită pentru P set pana vineri.
Că este, cam de pe o mică parte din P stabilit în raport cu ceea ce este de obicei
Problema mai mare, și de a cumpăra vă o zi în plus.
Din nou, acesta devine tu gândești Setul problema, să se
ore de birou mai devreme.
Dar problema cod promoțional este încă necesar, chiar dacă nu-l prezinte.
>> Dar mai convingător este aceasta.
(WHISPER trepte) și acei oameni părăsesc devreme vor regreta.
Ca sunt oameni pe balcon.
Îmi cer scuze în avans pentru cei de pe balcon, pentru motive care vor fi
șterge într-o clipă.
>> Deci, suntem norocosi sa avem unul din CS50 de semenii fostul predare cap la
o companie numita dropbox.com.
Ei au donat foarte generos o cod cupon aici pentru atât de mult spațiu,
care este de până la de obicei 2 gigabytes.
Deci, ceea ce am crezut că ne-ar face pe acest Nota finală este sa faci un pic de un chilipir,
prin care într-o clipă, ne va dezvălui câștigătorul și care are un cupon
cod pe care poti sa te duci apoi la lor site-ul, introduceți-l în, și voila, pentru a primi o
mult mai mult spațiu Dropbox pentru dvs. aparat și pentru fișierele personale.
>> Și în primul rând, care ar dori să participe în acest desen?
OK, acum că o face chiar mai distractiv.
Persoana care primește acest 25-gigabyte cod cupon - care este de departe
mai convingătoare decât la sfârșitul anilor zile de acum, probabil -
este cel care este așezat pe partea de sus a unui perna sub care nu există
că cod promoțional.
Puteti vedea acum sub perna de siguranta.
>> [Redare video]
>> -Unu, doi, trei.
>> [URLET]
>> -Ai o masina!
Ai o mașină!
>> DAVID MALAN: Vom vedea vă miercuri.
>> -Ai o masina!
Ai o mașină!
>> DAVID MALAN: oameni buni balcon, vin aici în față,
unde am extras.
>> -Toata lumea primeste o mașină!
Toată lumea devine o masina!
>> [END redare video]
>> NARATOR: La următoarea CS50 -
>> DIFUZOR 5: Oh, Doamne Dumnezeule Doamne Dumnezeule Doamne Doamne Doamne Doamne Doamne Dumnezeule -
>> [Ukelele joaca]