>> [MUSIC JOC]
>> David J. MALAN: Aceasta este CS50.
Și aceasta este începutul săptămânii trei.
Deci avem o mulțime de interesant lucruri pentru a acoperi astăzi.
O mulțime de oportunități pentru voluntari pe scena.
Și în cele din urmă, astăzi este nu despre codul deloc.
Dar este vorba despre idei, și este vorba despre algoritmi,
și de fapt, aducerea înapoi o parte din lecțiile învățate din săptămână la zero,
care amintesc, am a introdus acest monstruozitate.
Și inspirație de împrumut la care, pentru a începe
pentru a rezolva tot mai sofisticate Probleme algoritmic.
Dar mai întâi, o pereche de anunțuri.
Deci unul, dacă doriți să se alăture Personal și colegii lui la pranz CS50
vineri, atât aici, cât și în Cambridge, și în New Haven,
va rugam sa vizitati cursului site, în cazul în care un URL poate fi găsită.
Curs miercuri va să nu fie aici, în Sanders.
Acesta va fi doar online, astfel încât tune în la site-ul CS50 lui,
dacă aici în Cambridge sau New Haven, de asemenea.
>> Și apoi problemă stabilit două este deja în mâinile tale.
Dacă nu ați scufundat încă, permiteți-mi pentru a oferi sugestia puternic cuprins
că, mai ales acum, ca problema seturi avans,
tu chiar nu doriți să începeți acum, dacă nu se ocupa un pic pe week-end sau înainte
atunci când merg în primul rând pe Vineri, pentru că veți
constată că ei nu sunt în mod necesar obtinerea mai sau mai provocatoare pe
se.
Cred că veți descoperi că, în general, ele tind să ia aproximativ
în jurul valorii de aceeași perioadă de timp.
Dar aceasta depinde cu siguranță pe student, și
depinde de mentalitatea cu care l-ați apropie.
Dar invariabil, te duci pentru a rula împotriva unele perete,
și ai de gând să lovi unele bug, si tu esti doar
nu va fi în măsură să treci peste asta la un moment dat.
Și este extrem de valoros pentru a putea la pasul departe, întoarce a doua zi,
du-te la ore de birou, post pe CS50 Discuta sau altele asemenea, pentru a obține de fapt, deblocat.
Astfel încât să păstreze în minte.
Incepand mai devreme posibil este cel mai bun lucru care le puteți face.
Deci, aici e unde am plecat clasa, peste in saptamana zero.
Și putem obține un voluntar aici să mă ajute să găsească microfoane?
BINE.
Picioare deja.
Haide sus.
Cred că e modul în care aceasta va funcționa.
Care e numele tău?
ALAN ESTRADA: Alan Estrada.
David J. MALAN: Alan Estrada.
Haide sus.
Îmi pare bine să te cunosc.
ALAN ESTRADA: Mă bucur să te cunosc.
David J. MALAN: Și tu erai aici cu noi în săptămâna zero desigur.
ALAN ESTRADA: Am fost.
Am fost.
>> David J. MALAN: Deci ar putea merge înainte și de a găsi pentru noi Mike Smith,
la fel de repede ca tine poate?
La fel de repede ca tine poate.
Ruperea literalmente problema în jumătate ca ai nevoie sa.
>> ALAN ESTRADA: Um.
David J. MALAN: Literalmente ruperea problema în jumătate.
>> ALAN ESTRADA: Oh.
Mm.
Foarte bine.
>> David J. MALAN: OK.
Bine.
Multumesc.
ALAN ESTRADA: Foarte bine.
BINE.
>> David J. MALAN: Și așa acum, le-ați diminuate până
la jumătate din dimensiunea problemei.
Acum, suntem în jos la un sfert.
Ești atent la care parte suntem păstrarea?
>> [Rîzînd]
>> ALAN ESTRADA: Da, am think--
>> David J. MALAN: Ce secțiune suntem in?
ALAN ESTRADA: Amortizoare, așa.
>> David J. MALAN: OK.
Dar Mike Smith este de gând să fie după Amortizoare.
Asa ca--
>> [Rîzînd]
>> In regula.
ALAN ESTRADA: În cazul în care ne uităm?
David J. MALAN: Mike Smith.
ALAN ESTRADA: Mike Smith.
David J. MALAN: Acum, suntem în chirurgicale.
Acum, medicii.
Now--
>> ALAN ESTRADA: Let's- să mergem cu adevărat.
Real.
>> David J. MALAN: Real.
BINE.
Dacă aveți nevoie de Real.
Acum, ce fel este Mike Smith?
>> ALAN ESTRADA: acest fel.
>> David J. MALAN: Care drum?
ALAN ESTRADA: Stai.
M este-- corect?
Am început aplice:
>> David J. MALAN: Da.
Sunt plecat.
Dreapta ta.
>> ALAN ESTRADA: Da.
>> David J. MALAN: Deci lui Mike aici.
ALAN ESTRADA: Ce?
>> [Rîzînd]
>> Bad exemplu, băieți.
Scuze.
David J. MALAN: Aceasta va învăța să sari din scaun.
>> ALAN ESTRADA: Oh.
Oh.
Te-am prins.
Oh.
Acest este-- OK, te-am prins.
Smith aici?
>> David J. MALAN: Smith, vă mulțumesc.
Așa că voi ține uita în sus Smith?
>> ALAN ESTRADA: Oh, da.
Nu Nu NU.
Oh nu.
Aceasta este a mea.
>> David J. MALAN: Oh, ai Smith.
BINE.
>> ALAN ESTRADA: Da, am ajuns Smith chiar aici.
Îmi pare rău, băieți.
M-am gândit Michael-- ne au fost cautati pentru Michael.
Scuze.
>> David J. MALAN: E OK.
Bine, acum suntem în Paccini and Sons.
>> ALAN ESTRADA: Paccini și fiii.
David J. MALAN: Doar tu și cu mine suntem în asta.
BINE.
Găsiți-ne Mike Smith.
Smith.
>> ALAN ESTRADA: Smith.
>> David J. MALAN: Smith.
Suntem în R pentru gunoi.
ALAN ESTRADA: gunoi.
Oh.
Acest lucru se va lua un timp.
>> [Rîzînd]
David J. MALAN: incaltaminte.
Suntem în pantofi.
>> ALAN ESTRADA: Acum suntem gonna--
>> David J. MALAN: Nisa.
ALAN ESTRADA: Which--
[Rîzînd]
Oh, acest lucru este mare.
[Rîzînd]
>> David J. MALAN: E OK.
>> ALAN ESTRADA: Oh, acest lucru este bun.
Nu cred că am de gând să au prieteni PSAT după asta.
David J. MALAN: Bine.
Sporting.
ALAN ESTRADA: Sporting.
Um, L, M, N, O, P.
David J. MALAN: OK.
Așa că haideți să rupe acest în jumătate.
E bine.
Acest lucru se termină prost oricum, pentru că Mike Smith nu va fi în paginile galbene.
>> ALAN ESTRADA: Aw.
>> David J. MALAN: Nu, e în regulă.
Dar să pretindem ca e de pe această pagină.
Deci, acum, ai diminuate problema jos la o pagină, și am găsit pe Mike Smith.
>> [Aplauze]
Bine multumesc.
BINE.
Asta a fost extraordinar.
Dar era încă mai rapid decât căutarea liniară,
în care vom începe de la începutul cărții,
și ne-am muta modul nostru de la stânga la dreapta, în cele din urmă în căutarea Mike Smith.
Și astfel, în cazul în care cartea de telefon a avut, poate, 1.000 de pagini,
Poate că ar fi luat ne 10 sau cam asa ceva de pagini lacrimi.
>> Dar este posibil să fi efect de levier atins o presupunere
în timpul toate acestea, ceea ce este de a spune că cartea de telefon în prealabil a fost ce?
Audiența: Sortat.
David J. MALAN: E sortate.
Dreapta?
Este sortate în ordine alfabetică, astfel încât că toate aceste nume și numere
sunt clasificate în funcție de A la Lui Z, și în ordine alfabetică în între.
Dar astăzi, acum cerem întrebarea, bine,
cum a făcut Verizon sau telefonul companie-l în această stare?
>> Pentru că e un lucru să impulsioneze această presupunere, și prin urmare,
rezolva o problemă cu un algoritm mai eficient.
Dar noi niciodată cu adevărat întrebă în săptămâna zero,, ei bine,
cât de mult a costat Verizon sau altcineva
pentru a obține cartea de telefon, pentru sortat?
>> Dreapta?
Nu contează dacă uita în sus Mike Smith
este super rapid, în cazul în care aveți nevoie de un an pentru a sorta paginile inițial.
Dreapta?
Ai putea la fel de bine doar trece printr-o carte de telefon randomizat,
în cazul în care va fi super- scump să-l sorta.
Deci, dacă putem avea un alt voluntar.
Să aruncăm o privire aici la cum ne-am might-- haide up-- cum
am putea merge despre sortarea acestora.
>> Și dacă Jordan ar putea de fapt alaturi de noi aici pe scenă.
Haide pentru o clipă.
Care e numele tău?
CAROLINE: Caroline.
David J. MALAN: Caroline, haide sus.
Și veți fi uniți de mine și Iordania aici.
Caroline, vă mulțumesc.
In regula.
Deci, ce avem aici pentru Caroline este de 26 de cărți albastre
care FAS foloseste pentru a administra anumite examene finale.
Acestea devin greu de găsit, dar ceea ce am făcut în prealabil
este că ne-am pus numele cuiva pe partea din față a fiecăruia dintre aceste,
dar am păstrat-l simplu de apoi punerea în numele complete.
Asa ca am ar pune persoana cu numele L, D, J, B, tot drumul la A la Z,
dar sunt în ordine aleatorie.
Și așa că, dacă ar fi, vorbind dvs. drum prin problema ca tine
Do It, poate merge mai departe și sorta aceste pentru noi, de la A la Z.
>> Audiența: OK, deci L este ca, la mijloc.
C începe.
B. J înainte L. B, Q.
>> David J. MALAN: Ține care gândit pentru o secundă.
Deoarece în caz contrar, aceasta este doar interesant pentru tine, mă, și Iordania.
Nu mergem.
Audiența: [neauzit].
R.
David J. MALAN: OK.
Ce faci?
>> CAROLINE: M vine după O.
>> David J. MALAN: OK.
>> CAROLINE: O.
David J. MALAN: O, bine.
>> CAROLINE: E.
>> David J. MALAN: E, F. Da.
>> CAROLINE: T, U, V
>> David J. MALAN: V, T, U, V Deci, se pare ca esti making-- continui.
Se pare că faci o gramada mare aici,
și un fel de o grămadă mare acolo.
Deci prima jumătate a alfabetului, a doua jumătate a alfabetului.
BINE.
Bine.
Un fel de divizare a problemei în două.
M, N, X. Da.
CAROLINE: K.
David J. MALAN: OK.
K. Deci un fel de selectare le una după alta,
inscrie fie la stânga sau la dreapta, sau Z se întâmplă pe podea.
BINE.
>> CAROLINE: Z se întâmplă pe podea.
>> David J. MALAN: OK.
Y se întâmplă pe podea.
Acum putem pune X.
>> CAROLINE: G.
David J. MALAN: G au poftit la stânga.
S merge bine.
Bine, o va tot drumul din stânga.
>> CAROLINE: A, B, C, D.
>> David J. MALAN: Acum, bun.
Avem A, B, C. W se întâmplă acolo.
În regulă, T.
>> CAROLINE: H, I, J.
David J. MALAN: H, I, J bun.
CAROLINE: In centru, am gonna--
David J. MALAN: OK.
Deci, acum, vom fel de îmbinare aceste diferite hemoroizi.
Deci, o prin C, apoi văd D, și E, și F, și G, și H, și I. Nisa.
J, K. Și apoi, acest morman este cu susul în jos, dar e OK.
Sigur.
Putem reduce unele colțuri.
BINE.
Și apoi avem nevoie de W, X, Y, Z.
>> CAROLINE: Da.
>> David J. MALAN: Excelent.
Deci, un mare MULTUMESC pentru Caroline de sortare acestea.
>> [Aplauze]
>> Multumesc.
Multumesc foarte mult.
Deci, acum să ia în considerare pentru un moment cum Caroline a mers cu privire la a face asta,
si ce anume ne au putut sa-- cum am
au fost in masura pentru a rezolva această problemă atunci când am fost doar
dat o grămadă de intrări aleatoare.
>> Ei bine, se pare ca acolo a fost un pic de un sistem acolo?
Dreapta.
Deci, literele anterioare în alfabetul, ea
a fost punerea la stânga, și litere mai târziu în alfabetul,
ea a fost punerea în dreapta.
Și de îndată ce a aflat unele litere proximale, Ones
care merg chiar lângă celălalt, ea ar pune cele în ordine.
Și astfel am avut un fel de aceste mici grămezi de intrări sortate apar.
>> Și așa că e destul ca ceea ce cele mai multe dintre noi, oamenii ar face.
Ne-ar trece prin fel de ea, și am un fel de au un mecanism.
Dar ar putea fi greu să scrie l jos într-o formulă în sine.
M-am simtit un pic mai organic decât atât.
Așa că haideți să vedem dacă putem acum legat problema cu mai puține intrări.
>> În loc de 26, să face ceva mult mai putine
cu doar spun, șapte, în spatele aceste uși, ca să spunem așa.
Există doar șapte numere?
Și dacă obiectivul acum la mână este de a găsi o valoare,
să vedem cât de eficient putem merge despre a face acest lucru.
Și să vedem dacă putem acum începe să se aplice unele numere,
sau a unor formule cu care să descrie eficiența cartea nostru de telefon
algoritm, algoritmul nostru de carte examen, și mai general, găsirea informațiilor.
>> Deci, pentru aceasta, permiteți-mi să mergeți mai departe, și pe ecranul tactil aici,
pune un browser web care are exact aceste șapte uși.
Și dacă am putea obține un alt voluntar să vină pe aici,
Am pus aceleași uși aici.
Voluntar rapid.
>> Acest Unu demo-uri sunt de gând la o mai rapida si mai rapid acum.
Haide jos.
Care e numele tău?
TREVOR: Trevor.
>> David J. MALAN: Trevor?
Bine, Trevor, vino jos.
Deci, Trevor sa oferit voluntar aici pentru a face o problemă similară, dar una care este
restrânsă în domeniul de aplicare, și că se întâmplă pentru a ne permite să încercăm să formalizeze acum
procesul de sortare aceste numere.
>> Deci Trevor, bucur să te cunosc.
Deci, aici este o matrice, astfel încât să vorbesc, o listă de șapte uși.
Du-te și ne găsi numărul 50.
Și apoi, după faptul, spune-ne cum ai găsit-o.
Ar trebui să be-- în regulă.
Da, aceasta este cea de aici?
Uh-oh.
BINE.
Ați făcut clic asta.
Bine.
>> Și de bună.
Acum ați făcut clic pe asta.
Și permiteți-mi să vă dau microfonul, astfel încât să-l aibă într-o clipă.
Dă-i drumul și faceți clic pe alături pe care intenționați.
Da bine.
TREVOR: Pot debifați o ușă?
David J. MALAN: Nu, nu poți debifați.
TREVOR: OK.
Aceasta.
David J. MALAN: Unde vrei să mergi?
Care?
>> TREVOR: Asta.
>> David J. MALAN: Nu.
>> TREVOR: OK.
Aceasta.
>> David J. MALAN: Da.
A fost bine.
In regula.
Deci, ceea ce a fost algoritm sau Procedura pentru a face acest lucru, Trevor?
>> TREVOR: Am trecut prin Uși până când am găsit un 50.
David J. MALAN: OK.
Excelent algoritm.
Deci asta e bine.
Pentru că, de fapt, dacă aș dezvălui ceea ce este în spatele acestor două alte uși, ceea ce
vom găsi aici este faptul că avem doar de intrare aleatoare.
Astfel că a fost de fapt la fel de de bun ca ai putea lua.
Și, de fapt, ai mai bine decât căutarea exhaustiv întreaga matrice,
pentru că ar fi fost foarte ghinionist daca ai fi lovit numărul
50 în ultimul ușă.
Dar dacă am loc ți-a dat o presupunere.
Să presupunem că un fel de toate aceste uși în jurul valorii de,
astfel încât să aibă Numerele sortate de data aceasta,
dar de data aceasta este de fapt un different-- de data aceasta,
este de fapt sortate pentru tine.
Iar acum obiectivul la îndemână este de a lovi numărul 50.
>> TREVOR: OK.
>> David J. MALAN: Ce este algoritmul dvs. va fi?
>> TREVOR: Ei bine, dacă e sortate, e fie merge
a be-- dacă cel mai mare cel mai mare, descendent, va fi primul,
sau dacă este opusul, acesta va fi ultima.
Așa că vom atinge doar ușa, și apoi apăsați doar ultima ușă.
David J. MALAN: Excelent.
In regula.
Așa că am găsit numărul 50.
Deci, de îndată ce ai știut acestea au fost sortate, am
au fost capabili să impulsioneze această ipoteză.
Astfel încât acestea sunt prea mult ca exemplul cartea de telefon.
De îndată ce ai, chiar cu o mică problemă de acest fel,
intrările dvs. de pre-sortate, putem găsi de fapt, valoarea, fără îndoială,
mai eficient.
>> Și nu l-ai spune dacă era sortate mic la mare, sau de mare pentru a mici,
și așa a fost foarte rezonabil să înceapă la un capăt sau altul
pentru a găsi de fapt, această valoare-țintă.
Deci, mulțumesc pentru Trevor, de asemenea.
Și voi propose-- bine făcut.
Avem un mic clip, de fapt, că se numără printre momentele noastre preferate din CS50,
care, uneori, aceste demo-uri Nu prea merge conform planului.
Și într-adevăr, chiar acum, am tras în sus interfața greșit
cu care să utilizeze ecranul tactil.
Astfel că a fost vina mea acolo.
>> Deci, acest lucru va face pentru clip de anul viitor ca
de ce am fost clic pe cont propriu ecran.
Dar haideți să aruncăm o privire rapidă la ceea ce sa întâmplat anul trecut
cu Jay, care a venit, mai mult ca Trevor aici, sa oferit voluntar,
și în acest scurt clip, veți vedea cum același demo nu prea
dezvăluie aceleași lecțiile învățate.
[VIDEO PLAYBACK]
-Toate Vreau să faci acum este pentru a găsi pentru mine, și pentru noi,
într-adevăr, numărul 50 cu pasi marunti.
>> -Numărul 50?
>> -Numărul 50.
Și puteți dezvălui ceea ce este în spatele fiecare dintre aceste uși
pur și simplu prin atingerea cu un deget.
La naiba.
>> [Rîzînd]
>> [END PLAYBACK]
David J. MALAN: Așa că a mers foarte bine.
Acestea au fost ușile nesortate.
Și Jay, desigur, găsit-o prea repede.
Trevor a facut o treaba mult mai bine în ceea ce privește o clipă docil,
ca să spunem așa, în acest an, în durează mai mult să-l găsiți.
Desigur, atunci ne-am dat Jay a doua șansă,
prin care am sortat ușile, la fel cum am făcut-o pentru Trevor,
și Trevor a făcut super-bine de data asta.
Dar Jay a făcut pe jumătate la fel de repede.
[VIDEO PLAYBACK]
-cele Scopul este acum de a, de asemenea, ne găsi numărul 50,
dar o fac algoritmic, și spune-ne cum ai de gând cu privire la aceasta.
>> -BINE.
>> -Și Dacă îl găsiți, vă păstrați filmul.
Dacă nu-l găsiți, vă-l dea înapoi.
>> Omule.
>> Oh!
>> - [Neauzit] OK.
Deci, am de gând să verifice capete în primul rând pentru a stabili dacă there's-- Oh.
>> [Aplauze]
>> [END PLAYBACK]
David J. MALAN: OK.
Deci, în mod clar de sortare usi conduce la o mai mare eficiență.
Și astfel, două ori mai repede este ceea ce am vrut să spun acolo.
Și așa Jay avut noroc atât de ori.
Și el, de asemenea, avut noroc în ultima an, am comandat unele discuri Blu-ray
pentru a da de fapt afară.
Îmi pare rău în acest an, ne-am nu au avut la fel, Trevor.
Dar mai bine era cu câțiva ani în urmă.
Și unii dintre voi s-ar putea ști acest colegi, Sean, care când era în CS50,
a fost contestat cu exact aceeași problemă, deși în SD,
după cum veți vedea în curând, din nou în a doua zi.
Și veți găsi că nu numai că el ia un pic mai mult decât Jay,
un pic mai mult decât Trevor, a fost de fapt, această oportunitate minunata
de a se angaja aproape toată lumea în mulțimea a la prețul este corect, încurajând
l pentru a găsi numărul am fost în căutarea.
Să. arunca o privire rapidă.
>> [VIDEO PLAYBACK]
>> -BINE.
Deci, sarcina dumneavoastră aici, Sean, este următoarea.
Am ascuns în spatele acestor usi numărul șapte.
Dar ascuns în unele dintre aceste uși precum și alte numere negative.
Și de obiectivul dvs. este de a gândi din acest rând top de numere
ca doar o matrice, sau pur și simplu secvență de bucăți de hârtie
cu numere spatele lor.
Și obiectivul dvs. este, folosind doar partea de sus matrice aici, mi găsesc numărul șapte.
Și noi suntem de gând să critice apoi cum te duci despre a face aceasta.
-In regula.
Găsește-ne la numărul șapte, vă rugăm.
Nu.
Cinci, 19, 13.
>> [Rîzînd]
>> Nu este o întrebare capcană.
Unul.
>> [Rîzînd]
În acest moment, scorul nu este foarte bine, asa ca s-ar putea la fel de bine continua.
Trei.
>> [Rîzînd]
>> Continuă.
Sincer, eu nu pot ajuta, dar întreb la ce te gândești chiar, deci--
>> [Rîzînd]
Numai rândul de sus, astfel încât ai trei stângă.
Deci mă găsească șapte.
>> [Rîzînd]
17.
Șapte.
>> [Aplauze]
>> In regula.
>> [END PLAYBACK]
>> David J. MALAN: asa ca am putea viziona aceste lung toată ziua.
Și, desigur, unele dintre demo-uri din acest an, probabil,
se va termina acum în viitor video de an, precum.
Deci, acum să fapt concentreze asupra algoritmilor
aici, și să vedem dacă nu putem acum începe pentru a formaliza
cum putem merge cu privire la obținerea de date nostru în această stare, care este sortate,
astfel încât în ​​cele din urmă, putem de fapt căutare-l mai eficient.
Și chiar dacă vom pentru a folosi seturi de date destul de mici,
ca WE opt numere avem aici de pe bord,
în cele din urmă ar putea aplica aceleași idei la 1.000 de intrări, un milion de intrări,
4 miliarde de intrări, deoarece algoritmii vor fi fundamental la fel.
>> Și astfel încât acesta este ultimul nostru oportunitate pentru voluntari astăzi,
dar, probabil, cel mai implicat, pentru care avem nevoie de opt voluntari
de a veni și de mers pe jos ne prin proces de sortare ce va fi în curând
fie pe aceste muzică standuri aici.
Permiteți-mi să începe aici.
>> Deci, unul din verde turquoise-- este?
Ești comiterea?
Două.
Haide jos.
BINE.
Trei.
Patru.
Să mine-- OK, cinci.
Ești desemnat de prietenul tău.
Șase, șapte, opt.
Haide sus.
In regula.
Multumesc foarte mult.
Haide sus.
>> In regula.
Deci, ce avem here-- și acest este printre cele mai incomode,
deoarece acest lucru va necesita să umor mi doar un pic de timp.
Tu trebuie să fie numărul unu.
Care e numele tău?
>> Annan: Annan.
>> David J. MALAN: Annan.
David.
Care e numele tău?
>> JOSEPH: Joseph.
>> David J. MALAN: Joseph, ești numărul doi.
>> SERENA: Serena, numărul trei.
Stefan, numărul patru.
CYNTHIA: Cynthia.
David J. MALAN: Cynthia, numărul cinci.
[Inaudibil]
David J. MALAN: [neauzit].
David, numărul șase.
MATT: Matt.
David J. MALAN: Matt numărul șapte.
Și?
>> WAVERLY: Waverly.
>> David J. MALAN: Waverly, numărul opt.
In regula.
Dacă ați putea-- Hopa.
Dacă tot, ca dvs. în primul rând provocare, acolo
opt standuri de muzică aici se confruntă publicul.
Dacă ai putea pune numerele pe acestea muzică stă în așa fel
pe care le aliniază cu aceleași numere de pe bord.
Deci, asigurați-vă arăta așa de pune numerele de pe aceste muzică
standuri aici.
Excelent până acum.
>> Excelent.
BINE.
Deci, acum, vom cere întrebare în câteva moduri diferite.
Cum putem merge cu privire la sortarea acesti oameni aici?
Pentru că am avut câteva abordări mai devreme, prin care am fost
fel de a face două găleți diferite.
Și apoi am fost, în general, piecing lucruri împreună.
De îndată ce am văzut două numere care a aparținut, împreună,
am le-a pus împreună.
Două scrisori care aparțin împreună.
>> Dar să vedem dacă ne nu se poate formaliza acest lucru,
astfel încât să avem în cele din urmă unele pseudo-cod va fi,
cu care puteți rezolva aceste probleme.
Asa ca acum, caut afară la aceste numere de aici.
Și văd o grămadă de greșeli.
În cele din urmă, vreau una la stânga și opt pe dreapta.
>> Și așa mă uit la aceste două, patru și două.
Și care-i problema, în mod evident?
Da.
Asa ca.
Două evident vine înainte patru, astfel încât să știi ce?
Lasă-mă să ia mai întâi o abordare lacom, dacă vreți, la fel ca și problema
set Unu dacă vă amintiți de la Standard Edition problemei Set One,
în cazul în care doar am rezolva la nivel local problema care este chiar aici în fața mea
și a vedea unde mă duce.
>> BINE.
Deci, doi și patru, lasă-mă să merg înainte și pe care tocmai ați schimba doi.
Dacă puteți muta fizic voi înșivă și hârtie,
Se pare că au ajuns lista într-o stare mai bună.
>> Acum, ei sunt bine.
Am de gând să se mute departe, patru și șase, arată bine.
Nici o problema.
Șase și opt, OK.
Opt și unul, o altă problemă.
Pentru că ceea ce este adevărat despre opt și unul?
Vine înainte de opt, și așa mai departe ceea ce ar trebui să facem?
Să schimb aceste două.
Unul și opt.
Și acum, am de gând să continui.
Am de gând să continui să cauți mai departe.
Și să vedem ce se întâmplă.
Opt și trei, de Desigur, din ordine.
Să swap.
Opt și șapte, desigur.
Scos din uz.
Să swap.
Opt și cinci, desigur, să swap.
In regula.
Lista este sortata.
da?
>> OK, evident, nu.
Dar este un pic mai bine, nu?
Deoarece o notificare ce sa întâmplat.
De fiecare dată când am realizat un swap, un mic Numărul fel de filtrate în acest fel,
și un număr mai mare percolat acest fel, sau vom
începe spunând barbotat la la stânga sau la dreapta barbotat.
>> Acum, nu e de ajuns, pentru că cel mai bun la un număr s-ar putea
s-au mutat un singur loc înainte, sau în cel mai rău,
un număr ar putea avea mutat încă o pată.
Deci, știi ce, acest tip de lucrat destul de bine până acum.
Lasă-mă doar să încercați din nou.
Două și patru, sunt OK.
Patru și șase, sunt OK.
Șase și unul, în ordine.
Așa că haideți să vă doi schimb.
Și acum, observa problemei incepand de a obține un pic mai bine din nou.
Șase și trei, în ordine.
Să voi doi schimb.
Șase și șapte, ești bun.
Șapte și cinci, desigur, din ordine.
Șapte și opt, în ordine.
Și acum, s-ar putea nevoie pentru a face acest lucru de câteva ori mai mult.
Și, de fapt, cred că pentru voi înșivă probabil de câte ori maxim
s-ar putea am să meargă înainte și înapoi?
>> Vom reveni la asta.
Deci, două și patru sunt încă OK.
Patru și unu, nope.
Deci, să swap.
Și din nou, observa vizual unul este un fel de barbotare
la stânga, în cazul în care ar trebui să fie.
Patru și trei de swap.
Patru și șase.
Șase și cinci de swap.
Șase și șapte.
Șapte și opt sunt bune.
>> Bine.
Primim chiar mai bine.
Deci, să vedem.
Acum, avem două și unul.
Desigur, schimb.
Două și trei, trei si patru, patru și cinci, șase și șapte, șapte și opt.
Bine.
Și știi ce?
Pentru că am făcut o schimbare acolo, lasa-ma sa fac o verificare bun-simț.
Lasă-mă să merg până la capăt înapoi la început.
BINE.
Unul, two-- Da, vezi?
Ceva a fost greșit.
Trei, patru, cinci, șase, șapte, opt.
Și în această ultimă trecere, sunt vă confortabil cu meu acum
susținând că este sortata?
BINE.
Vizual, e absolut adevărat.
Dar funcțional, ce sa, de asemenea, se intampla doar
în ultimul pasă care vă permite să confirme că această listă este într-adevăr
sortate?
>> Ce am făcut sau nu acest ultim pasă?
Audiența: Nu au existat modificări.
David J. MALAN: Ne pare rău?
Audiența: Nici o schimbare.
David J. MALAN: Nu au existat modificări.
Deci, ar fi o prostie din partea mea să face din nou același algoritm
dacă nu am nici schimbă prima oară.
Iar statul nu sa schimbat.
Cu siguranță, eu nu am de gând să facă schimbă orice a doua oară.
Și așa, e sigur acum să spun, Lista este sortata.
>> Și într-adevăr, acest lucru este acum ceva că vom general
apel cu bule fel, prin perechi, te corecta greșelile din nou,
și din nou, și din nou, și tu mergi înainte și înapoi,
și înainte și înapoi, până când nu fac nici o astfel de swap-uri, la care punctul de
puteți fi sigur, da, terminat de stabilire toate greșelile.
Să reset și încerca o altă abordare.
Dacă voi putea întoarce în ordinea în care au fost în urmă cu o clipă,
care arata ca acest lucru.
Acum, haideți să aruncăm o abordare o pic mai mult ca carte examen,
prin care am fost în mod constant selectarea literă a alfabetului
pe care le fel de dorit pentru a face față în continuare.
Poate că a fost o scrisoare de mare, cum ar fi A, sau un Z. scăzut scrisoare
>> Astfel încât toată lumea sa întors în această ordine.
Și acum lasă-mă să fac asta.
Să vedem Știu că am opt numere aici.
Am de gând să merg mai departe și selectați doar în mod deliberat
cele mai mici elemente.
Dreapta?
Acest lucru pare intuitivă.
De ce nu mi se pare cel mai mic Element, pune-l în cazul în care acesta face parte,
apoi ajunge în următorii mai mic element, a pus aceasta în cazul în care acesta face parte, si doar se repetă.
>> Pentru că intuitiv, că ar trebui să funcționeze prea.
Deci patru, asta este un număr destul de mic.
Am de gând să-mi amintesc unde acest lucru este.
Asteapta un minut.
Două este mai mic.
Permiteți-mi să amintesc acum unde doi este, si uita de patru.
Ne vom ocupa de asta mai târziu.
Șase, nu mă interesează.
Opt, nu sunt interesat de.
Una dintre ele este noul meu număr mic.
Deci, am de gând să-mi amintesc unde unul este.
Trei, nu sunt interesat.
Șapte, nu sunt interesat.
Cinci, nu sunt interesat.
>> Deci, fără a cădea de pe etapa din acest an,
Am de gând să apuca numărul Unu și ceea ce a fost din nou numele tău?
>> Annan: Annan.
>> David J. MALAN: Annan.
Și dacă ai putea să mi se alăture la începutul listei,
Să te pun unde ți-e locul.
Unfortunately-- care e numele tău?
>> STEFAN: Stefan.
>> David J. MALAN: Stefan este in drum.
Deci, înainte de Stefan rezolvă această problemă, ceea ce ar trebui să facem?
Ce facem cu Stefan?
>> Audiența: [neauzit].
David J. MALAN: OK.
Deci, am putea face asta.
Am putea lua un fel de Stefan si lui patru, și doar a pus într-o variabilă
și țineți pe ea pentru o anumită cantitate de timp,
făcând astfel loc pentru numărul unu.
Și asta nu e rău.
Aș putea sugera, de ce nu ne-am pus Stefan aici?
De ce s-ar putea incalca aceasta din ideile pe care le au început
vorbesc despre ultima dată, săptămâna trecută?
Da?
>> Audiența: [neauzit].
>> David J. MALAN: Nu există index pentru ea.
Dacă credeți că de acest lucru, într-adevăr, ca un matrice, acest lucru este ca un negativ,
astfel încât nu există nici o memorie de fapt aici dacă acest lucru este într-adevăr un tablou,
ca și cum am declarat săptămâna trecută în curs.
Deci, noi nu trebuie să facem acest lucru.
S-ar putea stoca intr-o variabila.
>> Sau știi ce?
Am auzit pe cineva sa il sugeram.
Ce altceva am putea face cu Stefan?
De ce nu ne-am să-l evacueze și l-au pus pe unde numărul unu a fost.
Deci, dacă vrei să mergi acolo.
Și într-adevăr, aceasta este o soluție destul de bine.
Acum, pe de o parte, am un fel a făcut problema mai rău.
Patru este acum mai departe de unde ar trebui să fie.
Ar trebui să fie față de această jumătate.
>> Dar știi ce?
Care ar fi putut fi ghinion.
Poate număr de opt fost aici.
Și astfel, poate că ar fi au ajuns norocos,
și împins de opt mai aproape de capătul.
Deci, în final a zilei, un fel de toate mediile din.
Nu avem nevoie să aibă grijă cu privire la patru.
Totul mă interesează acum este selectarea cel mai mic element.
>> Și acum, ce am de gând să faci este uitați despre numărul unu
permanent, pentru că știu Lista spatele meu este acum sortate.
Deci lista mea a fost anterior dimensiune opt.
Acum, e de dimensiuni șapte.
Deci, problema mea este obtinerea mai mici, deși liniar.
Asa ca acum, am de gând pentru a selecta mai mic element curent, două.
Șase, opt, patru, trei, șapte, cinci.
Acesta a fost cel mai mic element.
Deci, ce am de gând să fac aplice: ceea ce a fost din nou numele tău?
>> JOSEPH: Joseph.
>> David J. MALAN: Joseph?
Vom lăsa în locul lui Iosif.
Acum, am de gând să mă prefac că tipii ăștia are-- bine,
Știu că aceste două sunt deja sortate.
Să acum se concentrează asupra restul listei.
Șase este cel mai mic curent.
Opt este mai mare.
Patru este acum cel mai mic curent.
Trei este acum cel mai mic curent.
Și așa acum, am de gând să selectați trei, care este-- ce e numele tău?
SERENA: Serena.
David J. MALAN: Serena, dacă ai putea apuca numărul și de swap aplice:
KALSANG: Kalsang.
David J. MALAN: Kalsang.
Vino înapoi, iar noi suntem O să schimb cei doi.
Și acum, să punem asta pe pilot automat.
Am de gând să meargă și lăsați-l la voi pentru a selecta următoarele elemente mai mici.
Dun, dun, dun, dun.
Numărul patru, ceea ce ar trebui să faci?
Excelent.
Acum, am de gând să facă o altă trecere.
Dun, dun, dun, dun.
Văd cinci este cel mai mic următoare.
Acum, am de gând să ia o altă trecere.
Dun, dun, dun, dun.
Șase este cel mai mic.
Bine.
Șapte este cel mai mic.
Nicio schimbare.
Opt este cel mai mic.
Efectuat.
>> Deci, ceea ce tocmai am făcut de iterativ selectarea unui element după alta
se pune în aplicare ceva ce suntem O să formalizeze ca selectarea fel.
Și e poate chiar simplu pentru a explica,
în care literalmente tot ce doriți să faceți este să păstreze doar
merge înainte și înapoi prin lista selectarea, următorul mai mic element,
până ați terminat.
>> Deci e mai simplu, poate intuitiv, decât ultima.
Să încercăm o ultima.
Dacă voi putea voi reseta în următoarele poziții
ultima oară, să vedem dacă nu putem formaliza acum o altă abordare.
De fapt, ar fi cineva acolo ca să propună
Cum altfel am putea merge despre a face acest lucru?
Fără clatina din buzzwords sau fel de răspunsuri care sunt deja cunoscute,
doar intuitiv, ceea ce am putea face?
>> Audiența: [neauzit].
David J. MALAN: Da.
Deci, există niște intuitie mare acolo.
Lucrurile bune par să se întâmple până în prezent în informatică, atunci când ne-am împărți
și cuceri problema de divizare l în jumătate și jumătate și jumătate.
Și astfel, într-adevăr, ne-am ar putea începe să facă asta.
Și, de fapt, că va fi, vom a se vedea, unul dintre cele mai bune soluții noastră încă.
Dar să revenim la asta înainte de mult timp.
De fapt, vom face că un pic mai târziu în această săptămână.
Ce altceva s-ar putea face pentru a rezolva noi acest lucru?
Astfel încât toată lumea de aici este în Pentru aparent aleatorie.
Știi ce?
Mai degrabă decât du-te înainte și înapoi, înainte și înapoi, înainte și înapoi
de fiecare dată, acest lucru se simte ca Fac o mulțime de mers pe jos.
De ce nu doar încep de la începutul listei,
și doar a pus patru în cazul în care acesta face parte?
Deci lasă-mă să presupunem pentru moment că lista mea este doar acest prim element.
Este de patru sortate în acest moment în timp, dacă tot mă interesează este totul aici?
Aceasta este un fel de trivial adevărat, nu?
Ca și lista conține un singur număr, și că numărul patru este, evident, sortate.
>> Deci, permiteți-mi să prevadă că această listă este sortată.
Dar acum am restul acestei liste.
Așa că acum, am întâlni două.
În cazul în care nu două, evident, aparțin în ceea ce privește patru?
Înainte de patru.
Deci, ce pot face aici?
Care e numele tău din nou?
>> JOSEPH: Joseph.
>> David J. MALAN: Joseph, daca ai putea pas înapoi
pentru o clipă cu numărul dumneavoastră.
Și acum ce ar trebui Stefan fac aici?
Să schimbe Stefan aici.
Și acum, să Joseph veni aici.
Și acum, permiteți-mi să susțin că totul aici este sortata.
Deci, rezultat similar, dar o abordare fundamental diferită.
Nici măcar nu am uitat ce e acolo.
Mă tot iau elementele ca acestea sunt predate la mine,
și să se ocupe cu ei.
>> Așa că acum, am vedea numărul șase.
În cazul în care nu numărul șase aparține?
Avem două, patru, șase.
Exact unde e acum.
Deci, haideți să plece că numai, iar acum susțin că această parte a listei
este acum sortate.
Și astfel, acest lucru se simte fundamental diferit în care eu sunt doar
miscandu-se prin lista de aici liniar, și mă niciodată dublarea înapoi.
Da.
In regula.
Deci opt, în cazul în care nu vă aparțin?
Chiar aici.
Perfect.
Deci, acum, unul.
Uh-oh.
Acest lucru se simte ca și cum ar O să fie scump.
Acum, în algoritmul anterior, Am schimbat oameni.
Deci, s-ar putea să-l pun tot drumul de la la început, dar apoi sa mutat Joseph.
Dar dacă am muta Iosif, acum ce se va fi greșit?
>> Acum, am un fel de undone-- Am luate un pas înainte și apoi
un pas înapoi, pentru că acum Joseph ar fi defect.
Deci, hai sa facem acest lucru.
Dacă ai putea lua numarul unu și pas înapoi pentru un moment.
Cum putem put-- ce a fost din nou numele tău?
>> Annan: Annan.
>> David J. MALAN: Annan in loc?
Ce trebuie să se întâmple cu respect la două, patru, șase, opt?
Ei au nevoie de toate pentru a comuta.
Deci, dacă opt-ar dori să schimbe în primul rând, apoi șase, apoi patru, apoi doi.
Și apoi Annan, dacă ai fi dori să vină aici, bine.
Dar aici, tocmai am un fel de plătit un preț
la un alt punct în algoritmul.
Întrucât ultima dată cu selecție sortare, și chiar cu bule de sortare,
Mă întorc și de mers pe jos mai departe, înainte și înapoi,
care este cu siguranță însumarea timp înțelept, și literalmente trepte.
>> Fel de inserție, la prima scurt, se pare ca e
super-inteligent, în care eu sunt doar face progrese lente, incremental,
dar eu nu am de gând această înainte și înapoi.
Dar dacă cineva este într-adevăr din ordin, aviz
toate lucrările am avut de a face.
A trebuit să se mute jumătate a listei doar pentru a face loc pentru numărul unu.
Deci e aceeași sumă de muncă până în prezent aceasta
se simte, doar un alt tip de muncă.
>> Hai sa continuăm.
Deci, acum știm că toată lumea între unul și opt sunt sortate.
Aici, am numărul trei.
Dacă vă place să ridic numărul trei, un pas înapoi un.
Și ce voi trebuie să faceți?
Da.
Deci asta e alta, doi, trei etape.
Trei unități de timp care costa doar ma, pentru ca trei pot potrivi acum.
În cele din urmă, șapte.
>> Să mergem mai departe și au luați un pas înapoi.
Aceasta este doar o să ne coste o unitate de timp, dar asta e în regulă.
Și acum, cinci de gând să fi un pic mai scump.
Dacă doriți să pas înapoi.
Avem nevoie pentru a muta opt, și șapte, și șase.
Și apoi toată lumea este acum sortate.
Deci, o mână mare de a voluntarilor noștri de aici.
Multumesc foarte mult.
>> [Aplauze]
>> Va multumesc tuturor.
Va multumesc tuturor.
Să vedem acum cât de costisitoare tot ce era.
Să considerăm, probabil, simplă dintre acestea, un fel de bule.
Și eu spun mai simplu, doar pentru că puteți rezolva cu lăcomie de doar
rezolva problema perechi aici.
Rezolva problema perechi aici, iar și iar
și din nou, repetând cât mai multe ori ca ai nevoie de fapt să.
>> Deci, se dovedește că cu un fel de bule, bine,
câți pași nu am să-și asume prima trecere de care algoritm?
S-ar putea să take-- see-- unul, doi, trei, patru, cinci, șase, șapte.
Și există opt elemente de aici.
Deci e ca și cum n minus 1 Pași pentru obține de la începutul listei
la sfârșitul listei.
>> Dar cu selecție fel, amintesc că eu sunt selectarea nou și din nou elementele
și din nou că este cel mai mic, Am o pune în loc,
dar atunci eu nu sunt cauta în spatele meu din nou.
Deci, eu cred că e un pic mai clar apoi că prima dată, am putea
trebuie să ia toate n minus 1 etape pentru a găsi cel mai mic element.
Apoi le-am pus în loc, și eu evacua oricine era aici anterior.
>> Dar atunci nu am să Ți privirea de la acest element,
pentru că știu că e deja cel mai mic.
Deci acum, mă pot uita la doar șapte Elemente, apoi șase elemente,
apoi cinci elemente, apoi patru elemente.
Și astfel matematic, dacă n este numărul de elemente sau numere
că am început cu, vă puteți imagina că aceasta este la fel ca n minus 1,
plus minus n 2 etape, plus minus 3 n trepte,
plus minus n 4 trepte, toate mod de până la doar un pas.
Și eu sunt pe ultima mea persoană.
>> Și dacă vă reamintesc faptul că o mulțime de Statistica cărți sau cărți matematica
au aceste formule pe Hardcover spate sau fata lor,
se dovedește că această serie poate fi exprimat mai simplu
ca de n ori n minus 1 peste 2.
Și este în regulă dacă nu e în fruntea mintea ta.
Dar acest lucru este adevărat.
Asta e doar un mod mai simplu de a scrie aceasta.
Și apoi, dacă credeți Înapoi la școală grad,
când doar începi înmulțirea lucrurile, această desigur,
este doar n pătrat minus n împărțit la 2.
Tot ce am făcut este extinde expresiile de acolo.
Și Să rescrie acest un pic diferit.
Asta pătrat n împărțit la 2 minus n / 2.
>> Deci, din nou, eu sunt doar un fel de a aplica unele aritmetică reguli acolo.
Dar observați acum că cea mai mare pe termen în această expresie, ca să spunem așa,
este că n pătrat.
Deci, da, e n pătrat împărțit la 2, minus n / 2.
>> Dar, în general, în cazul în care n este Va fi o valoare mare,
Am de gând să pretind că n pătrat va fi factorul dominant.
E doar de gând să fie o contribuție mai mare
la numărul de pași ca n / 2.
Deci, ce vreau sa spun prin asta?
Să încercăm un exemplu simplu, chiar deși matematica devine un pic mai mare.
>> Deci, să presupunem că am avut 1 milion de oameni pe scenă, sau 1 milion de lucruri
care ne-o dorim pentru a sorta.
Să conectați un milion în exact această formulă
pentru a vedea cât de multe etape este nevoie totale pentru a sorta un milion de elemente cu ajutorul zicem,
fel de selecție.
>> Deci, vom avea aceeași formulă ca înainte.
Aș conectați un milion, astfel că am obține un milion de pătrat împărțit la 2,
minus un milion împărțit la 2.
Dacă fac asta matematică în avans aici, avem 500 de miliarde
minus 500000, care ne dă 499999500000,
care este destul de darn mare.
>> De fapt, dacă veți compara acum 499000000000, 999000000,
500.000 împotriva valoarea noastră originală, 500 de miliarde de, e al naibii de aproape așa.
Dreapta? n pătrat împărțit la 2 dă us-- sau mai degrabă, n pătrat împărțit la 2
ne-a dat 500 de miliarde.
Asta e al naibii de aproape destul de la 499999500000,
adică scăderea off 500000, sau mai general, scăzând off
n pătrat, nu într-adevăr o afacere mare.
N pătrat face acestea Numerele cresc foarte repede.
>> Acum, aceasta este doar în măsura în care importantă ca noi, ca oameni de stiinta de calculator,
sunt, în general, nu se va pasa atat de mult despre nuante de aceste formule
și exact ceea ce răspunsuri precise sunt.
Ne pasă doar că, știi ce?
La sfârșitul zilei, această formulă este de ordinul a n pătrat.
>> Da, suntem împărțirea de 2 acolo.
Da, suntem scăzând off n minus 2.
Dar la sfârșitul zilei, termenul că într-adevăr ne doare și ne costă
o mulțime de pași este că termenul pătrat.
Și așa mai departe ceea ce un om de stiinta de calculator este de gând să facă, în general,
este ignora tuturor celor termeni de ordine mai mici,
și doar uita-te la cel care contribuie cel mai mult la costul.
>> Și acest lucru este frumos, pentru că putem acum vorbesc în mult mai mare de generalitate
despre algoritmi, și le poate compara.
Și faptul că eu sunt folosirea acestui O este deliberată.
Când spun pe ordinea de, sunt în mod special
referindu-se la ceva numita mare O. Și mare O
este o notație care un computer om de știință utilizează pentru a descrie
superioară o legat pe ceva.
>> Așa că, dacă spun că un algoritm este în mare O de n pătrat,
cum mi-am propus doar o clipă în urmă, înseamnă că
că, în ceea ce privește funcționarea sa timp sau eficiența,
este nevoie de pe ordinea de n pătrat pași.
Poate mai mult, poate mai puțin.
Dar este pe ordinea de n pătrat.
Și asta e hotarul de sus.
Nu va fi mai dureros decât atât.
Nu va fi n tocata, sau 2 la N, sau ceva mult mai mare.
Aceasta este legat un superior pe orice că cost este.
Deci dat fiind faptul că, hai să ia în considerare doar câteva exemple.
Și aceasta este doar o listă finită ori de foarte frecvente care rulează
pentru algoritmi care este menit să fie ilustrative unele lucruri le-am
văzut deja.
>> Deci, de exemplu, în cazul selecție fel, ceea ce eu pretind aici
este de rulare ca selectia fel de timpul este pe ordinea de n pătrat.
În cel mai rău caz, am de gând să aibă o grămadă de numere aleatoare aici.
Și, după cum am văzut matematic, dacă am păstra de mers pe jos
prin listă, prin lista, selectarea următoarea cea mai mică
element de nou și din nou, dacă îmi de fapt, scrie toate etapele
Iau ca mi-am propus formulaically înainte, e pe ordinea de n pătrat
măsuri care sunt luati. Am
>> Și se pare că bule sortare și sortare prin inserție
sunt la fel de lent în cel mai rău caz.
Luați în considerare, de exemplu, sortare prin inserție, ultimul algoritmul ne-am ocupat cu,
care a avut ne uităm la element, și apoi introduceți-l în cazul în care acesta face parte.
Și apoi ne-am uitat la elementul următor, și introdus în cazul în care acesta face parte.
>> Deci ia în considerare cel mai bun scenariu posibil.
Să presupunem că am avut de voluntari linia mea de până literalmente ca aceasta, o prin opt,
deja sortate.
Câți pași este sortare prin inserție de gând să ia pentru a sorta opt persoane,
în cazul în care sosesc pe scena aratand ca acest lucru?
>> Opt persoane sortate deja.
Și am folosi sortare prin inserție.
Că ultima a algoritmilor.
Ei bine, hai să reconstitui rapid reală.
Deci, dacă am începe aici, văd unul.
Unde se aparține?
Ea aparține chiar aici.
Văd două.
În cazul în care nu aparține doi?
Chiar aici.
Văd trei.
În cazul în care nu trei aparține?
Chiar aici.
>> Văd patru.
Chiar aici.
Cinci, șase, șapte, opt.
Nu e nici un motiv să mă repet.
Și astfel, cât de mulți pași este că, în ceea ce privește n?
E pe ordinea de n pași, nu? n minus 1.
Dar am luat o serie liniară de pași, iar acum am terminat.
Deci, asta e cel mai bun caz, totuși.
Ce despre cel mai rău caz?
Care opt au fost acolo, și șapte au fost acolo,
și unu și doi au fost aici, așa că lista a fost cu adevărat inversat?
>> Ei bine, într-adevăr, ceea ce se întâmplă dacă acest lucru este numărul?
Și vom face doar câteva exemple.
Ce se întâmplă dacă, într-adevăr, numărul opt este aici, iar Hopa number--.
Și ce dacă, într-adevăr, numărul opt este tot drumul până aici,
și eu sunt, folosind sortare prin inserție?
>> BINE.
Am susțin în acest moment este în loc.
Dar acum, seven-- cazul în care nu merge șapte?
Desigur, merge aici.
Așa că trebuie să se mute opt peste un loc.
Acum șase, unde se duce?
Ei bine, în regulă.
Acum, trebuie să se mute peste opt un loc, și șapte pe un loc,
și apoi am Plop în jos șase.
>> Deci, prima dată, costul mi un pas pentru a remedia lucrurile,
atunci ma costat două etape pentru a remedia lucrurile.
Câți pași este de gând să ia pentru a remedia
lucruri pentru a pune cinci în locul potrivit?
Trei.
Pentru că acum trebuie să muta unul, doi, trei.
Câte măsuri se merge să ia pentru a pune patru în locul potrivit?
4 plus 5, plus 6, plus 7.
>> Și așa e matematic identică cu ceea ce am descris pentru selectarea fel.
Avem această serie care este doar în creștere.
1 plus 2, plus 3 plus 4, sau invers, 7 plus 6
plus 5 plus 4 adaugă pentru astăzi scopuri, de ordinul a n pătrat.
>> Deci lasă-mă să stipuleze de asemenea, că bubble sort este, de asemenea, în n pătrat.
Deoarece cu bule fel, fiecare când mă duc prin lista,
Iau aproximativ cât de mulți pași?
De fiecare dată când literalmente de mers pe jos de acolo până acolo?
Aproximativ n pași.
Dar de câte ori s-ar putea să trebuie să treacă prin lista de?
>> Ei bine, aproximativ n timp.
Poate n minus 1, dar aproximativ de N ori.
Ei bine, de ce este asta?
Ei bine, cu bule fel, în cazul în care vom începe cu bule fel,
cu lista în cel mai rău posibil situație, care din nou este complet
înapoi, ce se va întâmpla?
Mă duc prin lista, și numărul o parte tot drumul de acolo.
>> Dar, cu bule fel, nu cât de departe unul muta pe prima mea trecere prin lista?
Câte locuri are el obține mai aproape de locul corect?
Doar unul.
Deci, dacă un fel de motiv, prin acest lucru, de fiecare dată, prin acest algoritm,
Luând aproximativ n pași lui David.
Dar cum de multe treceri prin lista este
de gând să ia pentru o să bule la stânga în cazul în care acesta face parte?
>> Are să se miște cum ar fi, n spații acest fel.
Deci, doar pentru a face sortarea listei, Trebuie să meargă înainte și înapoi de n ori.
Și de fiecare dată, sunt uita la n elemente.
Deci, nu n lucruri de N ori pe ordinea de n pătrat.
>> Acum, vom vedea într-un de pantaloni scurți care
sunt încorporate în viitor problema CS50 lui set, o altă abordare la aceste,
dar pentru moment, să ia în considerare doar a alteori de funcționare,
mai ales în cazul în care cele de sortare ia un pic de timp să se scufunde în.
Ce este un algoritm am văzut deja care ia pe ordinea de n pași?
>> Ce ar trebui să ia o serie liniară de pași pe care le-am văzut până acum?
Ce-i asta?
Căutare director de telefon.
Primul algoritm.
Dreapta?
În cazul în care suntem liniar căutarea Mike Smith?
Intr-adevar.
De la o săptămână la zero, atunci când am început de cotitură o pagină la un moment dat,
și am chiar a spus că a fost un fel unui algoritm sentiment liniar,
și am avut ca imaginea de pe bord cu linia roșie dreaptă
și drept galben line, acestea au fost într-adevăr
algoritmi care sunt în O mare de n.
>> Deoarece pentru a găsi Mike Smith într-un telefon carte de n pagini, în cel mai rău caz,
mi n pași s-ar putea lua.
Ce zici de a lua prezență?
Unu doi trei patru cinci șase.
Care este timpul de rulare a acestei algoritm pentru a lua participarea?
O mare de n, pentru că în teorie I Trebuie să subliniez toată lumea din sală.
>> Acum ca o paranteza, ceea ce despre alte optimizare de la zero, săptămâna?
Doi, patru, șase, opt, 10, 12.
Un om de stiinta de calculator ar realiza, așteptați un minut,
care este pe ordinea de n împărțit la doi pași.
Dreapta?
Pentru că fac doi oameni la un moment dat.
Dar am de gând să ignore acei termeni ordin inferior,
si noi suntem doar de gând să arunca decalajului de 2,
și doar spun, O mare de n pentru că algoritmul de asemenea.
>> Ce zici de asta?
Vom sari peste unele dintre acestea, dar ceea ce Acesta este un algoritm care a fost log de n?
Care a avut log aproximativ n pași?
Decalajului și să cucerească.
Exact.
Ca și exemplu de carte de telefon în săptămână zero și mai devreme,
în cazul în care ne-am impartit problema din nou și din nou și din nou.
Am atras de pe placa de saptamana zero, ca o linie verde curbat,
și am spus în acea zi a fost un algoritm logaritmică.
>> Și într-adevăr, numărul de pași IT ia pentru a efectua divide și stăpânește,
sau de căutare binară ca vom începe numindu-l, la fel ca în cartea de telefon,
este de ordinul a jurnalului și etape.
Și aceasta este un pic de un ciudat.
>> Ce face un pas, sau mai precis
un număr constant de pași?
Poate că e de două, poate e de trei, dar un om de stiinta de calculator doar
simplifică l ca O mare de 1, unele număr constant de pași.
Ce e ceva ce ar putea face asta ia un număr constant de pași?
>> Care este timpul de rulare a aclama?
Constantă de timp.
Dreapta?
Cum ar fi, ce-i timpul de rulare a face nimic care să ia doar o
operare, cum ar fi imprimarea F Hello World.
Care ar putea fi spus să fie timp constant, cu excepția cazului în mai puțin caz colț cu print F,
Ce ar putea timp de funcționare de imprimare F fi de fapt?
Și de ce?
Ce este n măsură în acest caz?
>> Audiența: [neauzit].
David J. MALAN: Exact.
Numărul de caractere vrem să imprimați.
Deci, este foarte sensibile la context.
Astăzi, ne-am concentrat foarte mult pe litere și numere de aici de pe bord.
Dar ar putea fi, de asemenea, caractere în un șir actuale.
Deci, se dovedește că un alt măsură care va începe pese,
și asta e opusul de mare O, ca să spunem așa.
>> Asta e notație Omega.
Întrucât mare O înseamnă ceea ce, The superior legat la timp de funcționare?
Maxim, cât de mult timp s-ar putea să ia ceva?
Omega-- pare rău acest lucru ține vine up-- este opusul care,
prin care este o limită inferioară, pe de perioada de timp ceva s-ar putea lua.
>> Asa ca. De exemplu, ceea ce este un algoritm care ia măsuri mereu n patrat?
Ei bine, unul dintre algoritmii am văzut astăzi, de fapt, s-ar putea să fie la fel de bine.
Fel de selecție.
Selecție fel e destul de prost.
Chiar dacă algorithm-- Ne pare rău, chiar dacă matricea este deja sortate,
Selecția fel se va păstrează de mers pe jos prin listă
pentru a vă asigura că are cel mai mic element de nou și din nou și din nou.
Și chiar dacă oameni in public stiu ca, așteptați un minut,
ai trecut deja cel mai mic element calculatorul
nu știe că până se pare tot drumul prin lista.
In mod similar, o limită inferioară care ar putea fi, de asemenea, luate în considerare
ar putea fi timpul liniar.
>> Cât timp este nevoie pentru a fel n elemente din cele mai bune
caz, folosind ceva de genul bubble fel?
Să presupunem că lista este deja sortate.
Am spus bubble sort ia pe ordinea de n pătrat pași.
Dar dacă e deja sortate?
Ce se întâmplă dacă îți dai seama după o singură trecere prin matrice
care le-ați făcut nici o swap-uri?
Ai nevoie pentru a păstra face mai multe treceri?
>> Nu.
Deci, o limită inferioară de pe bubble sort ar fi spus să fie liniar.
Omega de n.
Si ne putem uita la altele ale acestora, precum și.
Deci, haideți să aruncăm o privire rapidă la doar o vizualizare aici
pentru a vedea modul în care acestea se disting.
Am de gând să meargă în jos aici, în această Pagina care este disponibil pe site-ul C50 de,
dar va fi o durere pentru a obține de lucru, deoarece foloseste o tehnologie numita
Applet-uri Java, care este un în mare măsură neacceptat in aceste zile,
cel puțin de Chrome și anumite alții.
>> Și lasă-mă să merg mai departe și de a accelera acest și să explice ce se întâmplă.
Aceasta este o demonstrație de balon sortare, primul algoritm ne-am uitat la.
Și este un vizualizare în care fiecare din aceste bare reprezintă un număr.
Cu atât mai mare bar, cu atât mai mare numărul.
Mai mici la bar, este mai mic numărul.
Și ceea ce se poate vedea vizual, chiar deși acest lucru se întâmplă super rapid,
este faptul că bara de roșu este ca mine, de mers pe jos înapoi și de stabilire înapoi probleme.
Puteți vedea că elementele mai mari sunt într-adevăr barbotare până la dreapta,
și elementele mici sunt barbotare la stânga.
Și aici, dacă de fapt, uite mai atent,
putem conta, de fapt, Numărul de comparații și swap-uri
care au fost făcute.
>> Dar, în loc, să ne uităm la două algoritmul
ne-am uitat la mai devreme, cu noastre voluntari, de selecție de sortare.
Vizual, are o efect foarte diferit.
Dar e, din nou, foarte intuitiv, în că păstrăm selectarea următoarea cea mai mică
element și avem un pic de noroc.
Că a simțit fundamental mai repede.
Dar dacă am fugit acest nou și din nou și din nou cu o mulțime de intrări,
am vedea că este într-adevăr încă în O mare de n pătrat.
>> Să facem o ultimă unul aici, sortare prin inserție,
care a fost treilea algoritmul ne-am uitat la, și rechemare
că aceasta se referă la ca elemente le întâlnește,
dar apoi a, poate, schimburi lucruri pe pentru a face loc,
inserarea elemente de care apartin.
>> Și acest lucru se termină prea oferind rezultat final. Acum toate cele trei din cei
simțit destul de repede.
Și într-adevăr, le-am fugit la un clip destul de bine.
Dar fundamental, toate sunt destul de oribil, să fiu sincer.
Toate aceste algoritmi până acum care rulează în O mare de n pătrat
ia destul de un pic de timp pentru a rula în cele din urmă.
>> Și într-adevăr, putem vedea și în cele din urmă se simt acest
dacă am trage acest demo a treia și ultima.
Acesta este un alt vizualizare care va
pentru a arăta bubble sort pe stânga, sort de selecție în mijloc,
și ceva, ca unul dintre noastre mână ridică sugerat mai devreme,
merge sort pe dreapta.
O divizare și cucerire strategia pe dreapta.
Și asta e, de fapt, ceea ce suntem O să se uite la miercuri.
Dar să timp acestea să ruleze în paralel.
Este aproximativ același număr de Elemente, toate rulează în același timp.
Bubble sort vs selecție fel vs merge sort.
>> Acum, toate acestea sunt difuzate în teorie, în același timp.
Procesorul se execută la aceeași viteză, dar
pot simți cât de plictisitor este foarte repede va deveni,
și cât de repede atunci am injecta un pic de săptămână
algoritmi de zero lui poate am accelera lucrurile.
>> Și acum să comparăm acestea într-o formă trecut.
Am de gând să merg mai departe la site-ul CS50, unde
avem această legătură finală pentru ziua de azi, în cazul în care cineva de pe internet
amabilitate pune împreună un video care surprinde ceea ce diferit de sortare
algoritmi suna ca.
Aceasta este un fel de introducere.
>> [Bip]
>> Prin care aplici o frecvență bazate pe înălțimea barei bar.
Acest lucru este cu bule fel.
>> [Bip Warped]
>> Urmează este-- vine up următor este-- fel de selecție,
în cazul în care, din nou, ne selectarea următor mai mic element,
și putem vedea în creștere de la stânga la dreapta.
>> Merge fel, câștigătorul nostru până acum astăzi.
Observați cum se împarte lucrurile în [inaudibil] jumătate și sferturi.
Fel Gnome, care nu avem a vorbit despre, și creează vizual
și audally un pic de o diferite forme și sunet.
Merge înainte și înapoi, curățare lucrurile.
De asemenea, a verifica afară heapsort pe site-ul acestui tip.
>> Si asta e.
Vă vom vedea data viitoare.
>> [Whooshing ȘI MUZICĂ]