>> [MUSIC JOC]
>> ANDI Peng: Bine ati venit la săptămâna 3 din secțiunea.
Multumesc, voi, pentru toate provenind la acest timp de pornire mai devreme astăzi.
Avem un frumos, mic grup intim astăzi.
Deci sperăm că vom ajunge la finisaj, probabil, mai devreme,
un pic mai devreme astăzi.
Atât de repede, doar câteva anunțuri de pe ordinea de zi de astăzi.
Înainte de a începe, suntem de gând să merg peste
unele probleme logistice scurte, PSET întrebări, interogatoriu, lucruri de genul asta.
Și apoi ne vom arunca cu capul chiar în.
Vom folosi un program de depanare numit GDB la începe debunking codul nostru, care David
a explicat în curs de altă zi.
Vom trece peste cele patru tipuri de soiuri.
Vom merge peste ele destul de repede deoarece acestea sunt destul de intens.
Dar să știi că toate diapozitivele și codul sursă sunt întotdeauna on-line.
Deci nu ezitați, la examinare atentă dumneavoastră, pentru a du-te înapoi și să ia o privire la asta.
>> Vom merge prin notație asimptotică, care
este doar un mod de lux de a spune "runtime"
unde avem O mare, care David a explicat în curs.
Si ne-am, de asemenea, Omega, care este runtime legat de jos.
Și vom vorbi un pic mai mult în profunzime cu privire la modul în care aceste lucru.
Și, în fine, vom trece peste căutare binară, pentru că o mulțime dintre voi care au deja
se uită la psets dumneavoastră probabil știți că că este o întrebare care se află într-PSET ta.
Deci vei toții fericiți pe care le acoperă acest lucru astăzi.
>> Și, în fine, pe dumneavoastră feedback-ul secțiune, de fapt am
matureze circa 15 minute la la sfârșitul pentru a merge doar pe
logistica pset3, orice întrebări, poate un pic de orientare, dacă vreți,
înainte de a începe programarea.
Deci, haideți să încercați să obțineți prin materialul destul de repede.
Și apoi putem petrece ceva timp luând mai multe întrebări pentru PSET.
BINE.
>> Rapid, astfel încât doar câteva anunțuri înainte de a începe astăzi.
În primul rând, bun venit pentru a face se prin intermediul a două dintre psets tale.
Mi-am luat o privire la your-- Da, să obține o rundă de aplauze pentru că unul.
De fapt, am fost într-adevăr, într-adevăr impresionat.
Am clasificate prima PSET pentru voi săptămână și voi ultimele facut incredibil.
>> Stil a fost pe punctul de în afară de câteva comentarii.
Asigurați-vă că sunteți întotdeauna comentând codul.
Dar psets tale au fost pe punctul de.
Și păstrați-l în sus.
Și e bine pentru elev de clasa a vedea că voi sunt punerea
în măsura în efortul in stilul tau și design-ul în codul
care ne-ar dori pentru tine pentru a vedea.
Deci, eu sunt de-a lungul mod de recunoștința mea pentru restul AT.
>> Cu toate acestea, există o câteva întrebări interogatoriu
Vreau doar să merg peste care ar face atât viața mea
și o mulțime de altă parte AT "trăiește un pic mai ușor.
În primul rând, am observat acest lucru trecut week-- Câți dintre voi
au fost difuzate pe check50 codul înainte de a vă prezenta?
BINE.
Deci, toată lumea ar trebui să facă check50, because-- un secret-- am de fapt
rula check50 ca parte a corectitudinii noastre script-uri de testare codul.
Deci, dacă codul este lipsa check50, după toate probabilitățile,
este, probabil, va nu verificare nostru.
Uneori voi au răspunsurile corecte.
Cum ar fi, în lacomi, unele dintre aveți numerele corecte,
doar imprima unele chestii in plus.
Și că lucrurile în plus nu, de fapt, verificarea,
deoarece computerul nu știu cu adevărat ce este în căutarea pentru.
Și așa va rula doar prin, vedea că ieșire nu
potrivi ceea ce ne așteptăm răspunsul să fie, și marcați este greșit.
>> Și știu ce sa întâmplat în o parte din cazurile tale în această săptămână.
Deci, m-am întors și manual declasificat cod tuturor.
În viitor însă, Vă rog, vă rugăm să asigurați-vă că
pe care îl execută verifica 50 pe codul.
Pentru că este un fel de durere pentru AT de a avea pentru a merge înapoi și manual declasificare
fiecare PSET unic pentru fiecare singur, exemplu puțin ratat.
Așa că nu a luat de pe orice puncte.
Cred că mi-am scos poate una sau două pentru proiectare.
În viitor, deși, în cazul în care te în lipsa check50,
puncte vor fi luate off pentru corectitudinea.
>> Mai mult, sunt psets datorită vineri la prânz.
Cred că e un șapte de minute perioadă de grație târziu că vă oferim.
Pe timp Harvard, au voie să șapte minute întârziere la tot.
Deci, aici, la Yale, vom să adere la fel de bine.
Dar destul de mult, la 12:07, dacă PSET nu este în,
se va fi marcat ca târziu.
Și astfel în timp ce acesta este marcat ca târziu, TA-- sunt
încă de gând să fie clasificare psets tale.
Astfel încât veți vedea în continuare apare un grad.
Cu toate acestea, știu că la la sfârșitul semestrului,
toate psets întârziere va fi doar zero automat de către calculator.
>> Facem acest lucru din două motive.
Unul, uneori ajungem scuzat, ca scuze lui Dean,
mai târziu că nu știu despre încă.
Deci, ne place să ne asigurăm că te notare totul doar în cazul în, cum ar fi, eu sunt
lipsește scuza un Dean.
În al doilea rând, să păstreze în minte, puteți încă
picătură o PSET care Domeniul de aplicare are puncte complete.
Și așa ne place să grad toate psets tale doar
pentru a vă asigura că domeniul de aplicare dvs. de acolo și tu le încearcă.
Deci, chiar dacă e târziu, veți încă obține credit pentru puncte domeniul de aplicare, cred.
>> Deci, morală a poveștii este, face sigur psets dumneavoastră sunt în la timp.
Iar dacă acestea nu sunt de pe-timp, Știu că nu e mare.
Da, înainte de a mă muta mai departe, nimeni nu avea orice întrebări cu privire la feedback-ul PSET?
Da.
>> Audiența: Ai spus noi poate sa scada unul dintre psets?
>> ANDI Peng: Da.
Deci nu e nouă psets generală pe parcursul semestrului.
Și, dacă aveți domeniul de aplicare points-- astfel domeniul de aplicare este doar,
destul de mult, te a încerca problemă, te punerea în timp,
sunt vă arată care le-ați a demonstrat ce ați citit spec.
Asta e destul de mult domeniul de aplicare.
Și dacă se îndeplinesc Domeniul de aplicare de puncte, am
poate scădea cel mai mic unul afara domeniului de aplicare completă.
Deci, care este în avantajul dumneavoastră să completeze și să încerce fiecare PSET.
>> Chiar dacă nici unul dintre upload-- le de lucru, le încărcați.
Și apoi vom fi în măsură să sperăm vă dau unele dintre aceste puncte înapoi.
Misto.
Orice alte întrebări?
Grozav.
>> În al doilea rând, birou hours-- câteva note rapide despre ore de birou.
Deci în primul rând, veni mai devreme în săptămâna.
Nimeni nu este niciodată la orelor de program în zilele de luni.
Christabel a venit la orelor de noapte.
Da, Christabel.
Și ce-avem la birou ore noaptea trecută, Christabel?
>> Audiența: Am avut inghetata.
>> ANDI Peng: Deci ce-i drept, am avut inghetata la ore de birou aseară.
În timp ce eu nu-ți pot promite că vom avea înghețată la ore de birou
în fiecare săptămână, ceea ce pot să vă promit este că va exista o semnificativ
mai bine elev raport TA.
Ca și legal, e ca și cum trei-un.
Întrucât, contrast care cu Joi, ai aproximativ 150
într-adevăr a subliniat copii și nu înghețată.
Și nu este vorba doar productiv pentru oricine.
Deci, morală a poveștii este, veni mai devreme la ore de birou și lucruri bune
se va întâmpla.
>> De asemenea, vin pregătiți să pună întrebări.
Tu stii?
Indiferent de ceea ce TAs, am cred, au spus,
am fost obtinerea de câteva studenți care vin în, joi, la, cum ar fi, 10:50
nu au citit spec fiind ca ajută-mă, ajută-mă.
Din păcate, în acel moment, nu există nu de mult putem face pentru a vă ajuta.
Deci, vă rugăm veni mai devreme în săptămâna.
Vino devreme pentru a orelor de program.
Vino pregătit să pună întrebări.
Asigurați-vă că, în calitate de un student, în cazul în care sunt
aveți nevoie pentru a fi, astfel încât AT vă poate ghida de-a lungul,
care este ceea ce orelor de program Ar trebui să fie alocat pentru.
>> În al doilea rând, așa că știu profesori Vrei să ne surprindă cu teste.
Am avut un profesor cei cum ar fi, yo, de altfel,
amintiți-vă că intermediară ai lunea viitoare.
Da, nu am știut despre asta la mijlocul perioadei.
Deci, am de gând să fie că TA care vă reamintește că testul tot
0-- că, știi, suntem CS.
Acum, că ne-am matrice Done, veți obține de ce e test 0, nu quiz 1, nu-i așa?
BINE.
Oh, am niște chicotește pe asta.
BINE.
>> Deci test 0 va fi de 14 octombrie în cazul în vă aflați în secțiunea luni-miercuri
și 15 octombrie, dacă sunteți în secțiunea marți-joi.
Acest lucru nu se aplică pentru cei dintre voi la Harvard
who-- Cred că vei fi tot luarea de ajutorul testelor dvs. 14.
>> Deci da, săptămâna viitoare, în cazul în care David, în curs, se,
Da, așa încât despre test saptamana viitoare, voi toți
nu va fi șocat, deoarece ai venit la sectiunea
și știți că dumneavoastră test 0 este în două săptămâni.
Și vom avea recenzie sesiuni și totul.
Deci, nu vă faceți griji despre fiind speriat pentru asta.
Orice întrebări before-- orice întrebări la toate problemele logistice în ceea ce privește,
clasificare, ore de birou, secțiuni?
Da.
>> Audiența: Deci testul este Va fi timpul prelegere?
>> ANDI Peng: Da.
Deci testul, cred eu, este de 60 minute alocate în acest interval de timp
pe care le va lua doar în sala de curs.
Astfel încât să nu trebuie să vină în pe, cum ar fi, o întâmplare 07:00.
Totul este bine.
Da.
Misto.
>> In regula.
Așa că am de gând să introduce un concept pentru tine
în această săptămână că David are deja un fel de atins în curs în această săptămână trecut.
Se numește GDB.
Și câți dintre voi, în timp ce în cursul de scriere psets tale,
au observat un buton pe care scrie mare "Debug" pe partea de sus a IDE-ul?
BINE.
Deci, acum vom obține de fapt, pentru a descoperi misterul a ceea ce buton care de fapt
face.
Și vă garantez, este un frumos, lucru frumos.
>> Deci, până acum, cred că acolo a fost două lucruri
elevii au fost de obicei face atunci când depanare psets.
Unul, acestea se adaugă fie în printf () - astfel încât la fiecare câteva rânduri,
acestea se adaugă într-o printf () - Oh, ce este această variabilă?
Oh, ce este această variabilă now-- și un fel de a vedea evoluția
de codul ca ruleaza.
Sau a doua metodă de copii face este că ei scriu doar totul
și apoi du-te ca acest lucru la sfârșitul anului.
Să sperăm că funcționează.
Îți garantez, GDB este mai bine decât aceste două metode.
Da.
Deci, acest lucru va fi noul tău cel mai bun prieten.
Pentru că e un lucru frumos care afișează atât vizual
ceea ce codul este de a face la un anumit punct
precum și ceea ce toate dvs. variabile sunt transportă,
ca ceea ce valorile lor sunt, în acel moment specific.
Și în acest fel, puteți într-adevăr seta puncte de întrerupere din cod.
Puteți rula prin linie cu linie.
Și GDB va avea doar pentru te, afișate pentru tine,
ce toate variabilele sunt, ceea ce fac ei,
ce se întâmplă în codul.
Și în așa fel, e atât de mult mai ușor pentru a vedea
ceea ce se întâmplă în loc de printf-ing sau scriind declarațiile dumneavoastră.
>> Deci, vom face un exemplu de acest lucru mai târziu.
Deci, acest lucru pare un pic abstract.
Nu vă faceți griji, vom face exemple.
Și astfel, în esență, cele mai mari trei, cel mai folosit funcțiile veți avea nevoie în GDB
sunt următorii, Step peste, și Pășește în butoane.
Am de gând să peste cap de acolo, de fapt, chiar acum.
>> Deci poate voi vedea că tot sau ar trebui să mări un pic?
În partea din spate, puteți vedea că?
Ar trebui să zoom in?
Doar puțin?
Bine, in regula.
Nu mergem.
BINE.
>> Așa că am, aici, mi punere în aplicare pentru lacomi.
Și în timp ce o mulțime de voi scris lacomi în buclă în timp ce form-- care
este un mod perfect acceptabil de a face it-- un alt mod de a face este de a pur și simplu
împărți în modulo.
Pentru că atunci puteți avea dvs. valoare și apoi au restul dumneavoastră.
Și apoi puteți doar adăugați-l toate împreună.
Are logica a ceea ce fac aici sens pentru toată lumea,
înainte de a începe?
Cam?
Misto.
Grozav.
E o piesă destul de sexy de cod, aș spune.
Cum am spus, David, în prelegeri, după un timp,
veți începe să vadă toate cod ca ceva care este frumos.
Și, uneori, când veți vedea frumos cod, este un astfel de sentiment minunat.
>> Deci toate acestea, în timp ce acest cod este foarte frumos, nu funcționează în mod corespunzător.
Deci, haideți să ruleze check50 în acest sens.
Verificați 50 20-- oop.
2?
Este că pset2?
Da.
Oh, pset1.
BINE.
Deci, vom rula check50.
>> Și, după cum voi puteti vedea aici, este lipsa de câteva cazuri.
Și pentru unii dintre voi, în curs de a face seturi de probleme,
esti ca, ah, de ce nu-i așa de lucru.
De ce este de lucru pentru a putea Valorile dar nu pentru alții?
Ei bine, GDB este de gând să vă ajuta să figura de ce aceste intrări nu au fost de lucru.
>> BINE.
Să vedem, una dintre cele mai verificări am fost lipsa în check50
a fost valoarea de intrare a 0.41.
Deci răspunsul corect pe care ar trebui să fie obținerea este 4.
Dar, în loc ceea ce am imprimarea este 3-N, care este incorect.
Deci, hai să executați acest manual, doar asigurați-vă că check50 funcționează.
Să facem ./greedy.
Oops, am avea de a face lacomi.
Nu mergem.
Acum ./greedy.
>> Cât de mult se datorează?
Să facem 0.41.
Si da, vom vedea aici că este scoate 3
în cazul în care răspunsul corect, De fapt, ar trebui să fie de 4.
Așa că haideți să introduceți GDB și a vedea cum putem poate merge despre fixarea această problemă.
>> Deci, primul pas în depanarea întotdeauna codul
este de a stabili un punct de întrerupere, sau un punct de la care
Vrei computerul sau debugger pentru a începe căutarea de la.
Deci, dacă nu prea stiu care e problema ta,
de obicei, lucru tipic vrem să face este de a stabili breakpoint nostru la principal.
Deci, dacă voi puteți vedea aceasta butonul roșu acolo,
Da, că mi-a fost stabilirea unui limită privind funcția principală.
Am faceți clic pe asta.
>> Și apoi pot merge până la butonul meu de depanare.
Am lovit acel buton.
Lasă-mă să zoom înapoi dacă pot.
Nu mergem.
Deci avem, aici, un panou pe dreapta.
Îmi pare rău, băieți în spate, ai nu se poate vedea cu adevărat foarte bine.
Dar, în esență, toate acest panou drept este de a face
este urmărirea atât a evidențiat linie, care este o linie de cod
care computerul este în curs de desfășurare, precum și toate variabilele
aici jos.
>> Deci ai de cenți, monede, n, toate declarat lucruri diferite
in acest punct.
Nu vă faceți griji, pentru că avem de fapt, nu le inițializat la orice variabile încă.
Deci, în calculatorul dumneavoastră, dumneavoastră Computer doar văd,
oh, 32767 a fost ultima funcție second-hand de care spațiu de memorie în computerul meu.
Și așa că e în cazul în care în prezent este de cenți.
Dar nu că odată ce rula codul, aceasta ar trebui să devină inițializată.
>> Așa că haideți să treacă prin, linia de line, ce se întâmplă aici.
BINE.
Deci, aici sunt cele trei butoane care tocmai am explicat.
Aveți Play, sau funcția Run, buton, aveți pas peste buton,
și aveți, de asemenea, pas în butonul.
Și, în esență, toate cele trei le du-te prin codul
și de a face lucruri diferite.
>> Deci de obicei, atunci când sunteți depanare, noi nu vrem să lovi juca doar,
pentru că va rula doar Joaca codul de la sfârșitul anului acesta.
Și atunci nu va fi de fapt Știi care e problema ta
este dacă nu ați stabilit mai multe puncte de întrerupere.
Dacă setați mai multe puncte de întrerupere, se va doar în mod automat
a alerga de la un punct de întrerupere, la alta, la următorul.
Dar în acest caz ne-am doar că unul, pentru că am
doresc să lucreze drumul nostru de sus în jos în jos.
Așa că am de gând să ignore acel buton acum în scopul acestui program.
>> Deci, pas peste funcție doar pași peste fiecare linie
și vă spune ce computerul este de a face.
Pasul în funcțiune merge în funcția propriu-zisă
care e pe linia de cod.
Deci, de exemplu, cum ar fi printf (), că este o funcție, nu?
Dacă aș fi vrut să pas fizic în (funcția printf),
Mi-ar merge de fapt, în piesa de Cod în cazul în care printf () a fost scris și a vedea
ce se întâmplă acolo.
>> Dar de obicei, vom presupune că codul pe care vă oferim funcționează.
Vom presupune că printf () este de lucru.
Presupunem că getint () este de lucru.
Deci nu este nevoie să pas în aceste funcții.
Dar dacă nu e funcții care te scrie
pe care doriți să verificați ce se întâmplă,
ce-ar vrea să-și intensifice în această funcție.
>> Deci, acum suntem doar de gând să-și intensifice pe această bucată de cod.
Deci, să vedem.
Oh, print, "Oh hai, cum schimba prea mult se datorează? "
Noi nu le pasă.
Știm că funcționează, asa ca am pas peste el.
>> Deci n, care este float noastră ca ne-am initialized-- sau declared--
până la partea de sus, suntem acum egalând care să GetFloat ().
Deci, haideți să pas peste asta.
Si vom vedea la fund aici, programul
ma determinat pentru a introduce o valoare.
Deci, haideți să introduceți valoarea ne-o dorim pentru a testa aici, care este 0.41.
Grozav.
>> Deci, acum N- face voi vedea aici, la bottom-- e
stored-- că noi nu s-au rotunjit încă, e
În această colecție de gigant ca float, care este 0.4099999996,
care este destul de aproape de nostru scopuri, acum, la 0,41.
Și apoi vom vedea mai târziu, așa cum am continua pas cu pas peste program,
după aici, n a devenit rotunjite și cenți a devenit 41.
Grozav.
Deci, noi știm că de lucru rotunjirea nostru.
Știm că avem Numărul corect de cenți,
astfel știm că asta e nu într-adevăr problema.
>> Deci, vom continua pas cu pas pe în acest program.
Mergem aici.
Și astfel, după această linie de cod, am ar trebui să știe cât de multe trimestre avem.
Am pas peste.
Și veți vedea ce facem, de fapt, au un sfert pentru că ne-am scăzut 25
din valoarea noastra initiala a 41.
Și avem 16 de cenți pentru stângă noastre.
>> Are toată lumea să înțeleagă cum Programul își intensifică prin
si de ce cenți a devenit acum 16 si de ce, acum, monede a devenit 1?
Este toată lumea urmând ca logica?
Misto.
Deci, ca din acest punct, de lucru program, nu?
Știm că face exact ceea ce vrem să.
Și nu am făcut de fapt trebuie să imprime, oh, ce
este de cenți de la acest punct, ceea ce este de monede în acest moment.
>> Am continua merge prin intermediul programului.
Pas peste.
Misto.
Mergem peste Dimes.
Grozav.
Vedem că este luat off 0.10 $ pentru un ban.
Și acum avem două monede.
Este corect.
>> Mergem pe bani si vom vedea că am rămas peste cenți.
Hmm, asta e ciudat.
Până aici, la program, eu trebuia au scăzut mărunțiș mele.
Poate că pur și simplu nu a fost face acest drept linie.
Și vai, puteți vedea aici, pentru că știm
că suntem pas cu pas prin linii 32 și 33,
care este în cazul în care programul nostru a avut în mod necorespunzător variabile rula.
Astfel încât să putem uita și vedea, oh, Sunt scăderea cenți aici,
dar eu nu sunt de fapt adăugând la valoarea mea de monede.
Sunt adăugând la cenți.
Și nu vreau să adăugați la cenți, vreau să adăugați la monede.
Deci, dacă vom schimba asta monede, avem un program de lucru.
Pot rula check50.
Puteți ieși doar din GDB drept aici și apoi executați din nou check50.
Aș putea face doar asta.
Trebuie să lacomi.
0.41.
Și aici, e de imprimare raspunsul corect.
>> Deci, ca voi poate vedea, GDB este un instrument foarte puternic
pentru că atunci când ne-am atât de mult cod întâmplă și atât de multe variabile
că e greu pentru noi, ca un om, pentru a ține evidența.
Computerul, în GDB debugger, are capacitatea de
pentru a urmări tot.
Știu, în Visionaire, voi probabil ar fi lovit unele defecte de segmentare
pentru că au fost difuzate în afara limitelor de matrice dumneavoastră.
În exemplul de Cezar, care este exact ceea ce am implementat aici.
>> Așa că am uitat pentru a verifica ce s-ar întâmpla dacă am
nu au avut două argumente în linia de comandă.
Doar că nu am pus în control.
Și deci, dacă am alerga Debug-- am stabilit breakpoint mea chiar acolo.
I a alerga Debug.
>> BINE.
Da.
Deci, de fapt, ar fi trebuit GDB să mi-au spus acolo
a fost o eroare de segmentare acolo.
Nu știu ce se întâmplă chiar acolo, dar când l-am fugit,
a fost de lucru.
Când executați linii de cod, prin și GDB ar putea iesi doar dintr-o dată pe tine,
du-te în sus și uite ce eroarea roșu este.
Acesta să-ți spun, hei, tu a avut o eroare de segmentare,
ceea ce înseamnă că ați încercat să acces spațiu într-o matrice care nu exista.
Da.
>> Deci, în problema următoare stabilite în această săptămână, voi
va avea, probabil, o mulțime de variabile plutesc în jurul.
Nu vei fi sigur că ceea ce toate acestea înseamnă, la un moment dat.
Deci GDB vă va ajuta cu adevărat în imaginind ce sunt toate egală
și posibilitatea de a vedea că vizual.
Este cineva confuz cu privire la modul oricare dintre care a fost de lucru?
Misto.
In regula.
Deci, după care, suntem O să se arunca cu capul dreapta
în patru diferite tipuri de soiuri pentru această săptămână.
Câți dintre voi, în primul rând de toate, înainte de a începe,
au citit întregul spec pentru pset3?
BINE.
Sunt mândru de voi.
E ca și cum jumătate din clasă, care este semnificativ mai mult decât data trecută.
>> Așa că e minunat, pentru că atunci când vorbim despre conținutul
în lecture-- sau rău, în section-- Îmi place
să se refere o mulțime de care înapoi la ceea ce este PSET
și modul în care doriți să punerea în aplicare a care in PSET ta.
Deci, dacă vii cu citit spec, va
fi mult mai ușor pentru tine de a înțelege ce vorbesc despre atunci când spun,
Oh Hei, acest lucru ar putea fi un adevărat loc bun pentru a pune în aplicare acest tip.
Astfel încât cei dintre voi care au citit spec știu că, în calitate de parte a PSET dumneavoastră,
ai de gând să trebuie să scrie un tip de fel.
Deci, acest lucru poate fi foarte util pentru o mulțime de tine azi.
>> Deci, vom începe cu, în esență, tipul cel mai simplu
de fel, genul de selecție.
Algoritmul tipic pentru cum ne-ar merge cu privire la această
este-- David a trecut prin toate aceste în curs, așa că voi trece rapid de-a lungul
here-- este, în esență, tu au o serie de valori.
Și apoi găsi cea mai mică valoare nesortate
și te schimb ca valoarea cu prima valoare nesortate.
Și apoi doar repeta cu restul de lista.
>> Și aici o explicație vizual de modul în care care să funcționeze.
Deci, de exemplu, dacă ar fi să înceapă cu o serie de cinci elemente, indicele
0 la 4, cu 3, 5, 2, 6, și 4 valori plasate în array-- așa acum,
ne doar de gând să-și asume că toate sunt nesortate
pentru că nu am testat altfel.
>> Deci, cum ar fi un fel de selecție lucru este că va prima
alerga prin totalitatea de matrice nesortate.
Aceasta ar alege cea mai mică valoare.
În acest caz, 3, dreapta acum, este cel mai mic.
Se ajunge la 5.
Nu, 5 nu este mai mare than-- sau îmi pare rău, nu este mai puțin than-- 3.
Deci, valoarea minimă este încă 3.
Și apoi vei ajunge la 2.
Computerul vede, oh, 2 este mai mică de 3.
2 trebuie să fie acum valoarea minimă.
Și astfel 2 swap-uri cu care primul valoare.
>> Deci, după o pasă, noi nu vedem într-adevăr că 2 și 3 sunt schimbate.
Și noi suntem doar de gând să continue să facă acest nou cu restul matrice.
Deci vom rula doar prin ultimele patru indicii matrice.
Vom vedea că este 3 următoarea valoare minimă.
Deci vom schimba asta cu 4.
Și apoi vom merge doar pentru a păstra trece prin până când, în cele din urmă, ai
ajunge la o gamă sortat în care 2, 3, 4, 5, 6 și sunt toate sortate.
Are toată lumea să înțeleagă logica a modului în care funcționează un fel de selecție?
>> Trebuie doar un fel de o valoare minimă.
Ești urmărirea a ceea ce este asta.
Și ori de câte ori ai găsit, îl schimb cu prima valoare din array--
sau, nu, prima value-- următoarea valoare din matrice.
Misto.
>> Deci, ca voi fel de a văzut de la o scurtă privire,
vom pseudocod asta.
Deci, dacă voi în spate care doriți să formează un grup, toată lumea la o masă
poate forma un pic partener, am de gând pentru a vă oferi tipi ca trei minute
pentru a vorbi doar prin logica, în limba engleză,
de modul în care am putea fi în măsură să pună în aplicare pseudocod pentru a scrie un fel de selecție.
Și nu e bomboane.
Vă rugăm să vină și să bomboane.
Dacă sunteți în spate si doriti bomboane, pot arunca bomboane la tine.
De fapt, nu Tu-- rece.
Oh, scuze.
BINE.
>> Deci, dacă am dori să, ca o clasă, pseudocod scrie
pentru modul în care s-ar putea apropia de o această problemă, doar nu ezitați.
Mă duc doar în jurul și, în ordine, cere grupurilor
pentru următoarea linie de ceea ce ar trebui sa facem.
Deci, dacă vreți să începeți off, ceea ce este primul lucru pe care
să fac atunci când sunteți încercarea de a pună în aplicare un mod de a rezolva acest program
pentru a sorta selectiv o listă?
Să presupunem că au o matrice, bine?
>> Audiența: Doriți să creați unele un fel de [neauzit] că ești
trece prin întreaga matrice ta.
>> ANDI Peng: dreapta.
Deci ai de gând să doriți să repeta prin fiecare spațiu, nu?
Asa de bine.
Dacă vreți să-mi dea următor line-- Da, în spate.
>> Audiența: Verificați-le toate pentru cele mai mici.
>> ANDI Peng: Nu mergem.
Așa că vreau să merg prin și verificați vedea ce valoarea minimă este, nu?
Am de gând să abrevierea că la "min."
Ce vreți să faceți după ați găsit valoarea minimă?
>> Audiența: [inaudibil]
ANDI Peng: Deci ai de gând să doriți să porniți-l cu primul de care matrice,
dreapta?
Asta e de la început, am de gând să spun.
In regula.
Deci, acum că v-ați schimbat primul o, ce vrei să faci după aceea?
Deci, acum știm că asta aici trebuie să fie cea mai mică valoare, nu?
Atunci aveți o odihnă suplimentar de matrice care este nesortate.
Deci, ce vrei sa faci aici, dacă Vreți să-mi dea linia următoare?
Audiența: Deci vrei să repeta prin restul de matrice.
ANDI Peng: Da.
Și așa mai departe ce iterarea prin fel de probabil implica vom avea nevoie?
Ce tip de--
>> Audiența: Oh, o variabilă suplimentară?
ANDI Peng: Probabil alta pentru buclă, nu?
Așa că, probabil, va dori a repeta through-- mare.
Și apoi o să se întoarcă și să probabil verifica din nou minim,
dreapta?
Și ai de gând să repeta acest lucru, deoarece buclele doar de gând
a continua să fie difuzate, nu?
>> Deci, ca voi poate vedea, am doar un pseudocod generală
de modul în care ne-o dorim acest program să se uite.
Acest repeta aici, ce facem de obicei nevoie pentru a scrie în codul nostru
dacă vrem să repeta prin intermediul unei matrice, ce tip de structură?
Cred că Christabel spus deja acest lucru înainte de.
>> Audiența: A pentru buclă.
>> ANDI Peng: A pentru buclă?
Exact.
Deci aceasta este, probabil Va fi o pentru buclă.
Ce este o verificare aici va implica?
De obicei, în cazul în care doriți să verificați dacă ceva este ceva else--
>> Audiența: Dacă.
>> ANDI Peng: Un dacă, nu?
Și apoi swap aici, vom du-te peste mai târziu, pentru că David
a trecut prin faptul că, în curs, de asemenea.
Iar apoi a doua repeta implies--
>> Audiența: Un alt pentru bucla.
>> ANDI Peng: --another pentru bucla, exact.
Deci, dacă ne uităm la acest corect, am
se poate vedea că suntem, probabil, avea nevoie de o imbricat pentru buclă
cu o declarație condiționată acolo și apoi o piesă reală de cod care este
O să schimb valorile.
Așa că am scris doar în general, un cod pseudocod aici.
Și apoi vom merge de fapt la fizic, ca o clasă,
încercați să pună în aplicare acest lucru astăzi.
Să ne întoarcem în acest IDE.
>> Uh-oh.
De ce este că not-- acolo este.
BINE.
Ne pare rău, lasă-mă să încerc pentru a mări un pic mai mult.
Nu mergem.
Tot ce fac aici e că am creat un program numit "selecție / sort.c."
Am creat o serie de nouă Valorile, 4, 8, 2, 1, 6, 9, 7, 5, 3.
În prezent, după cum puteți vezi, ele sunt neordonate.
n va fi numărul care vă spune suma valorilor
aveți în matrice ta.
În acest caz, avem nouă valori.
Și eu doar am o buclă pentru aici că imprimă matrice nesortate.
>> Și la final, am, de asemenea, o pentru bucla care tocmai se imprimă din nou.
Deci teoretic, în cazul în care acest program funcționează corect, la sfârșitul anului,
ar trebui să vedeți o tipărite pentru buclă în care 1, 2, 3, 4, 5, 6, 7, 8,
9 sunt corect pentru.
>> Deci avem pseudocod aici.
Vrea cineva sa-- Sunt doar de gând să meargă cere volunteers--
spune-mi exact ce să tastați, dacă vrem să, în primul rând, doar repeta
prin începutul acestui tablou?
Care este linia de cod sunt probabil, va avea nevoie de aici?
>> Audiența: [inaudibil]
>> ANDI Peng: Da, simt gratuit sa-- Ne pare rău,
Nu trebuie să stea simt up-- libertatea de a ridica vocea un pic.
>> Audiența: Pentru int i egal 0--
>> ANDI Peng: Da, bine.
>> Audiența: i este mai mică decât lungimea matrice.
>> ANDI Peng: Deci păstrați în minte aici, pentru că noi
nu au o funcție care ne spune lungimea o matrice,
avem deja o valoare care stochează asta.
Dreapta?
Un alt lucru de a păstra în mind-- într-o matrice
de nouă valori, care sunt indicii?
Să spunem doar că aceasta matrice a fost 0-3.
Veți vedea că ultimul Indicele este, de fapt 3.
Nu e 4, chiar dacă nu e patru valori în matrice.
>> Deci aici, trebuie să fim foarte atenți de ceea ce starea noastră de lungimea
Va fi.
>> Audiența: N-ar fi n minus 1?
ANDI Peng: Va n minus 1, exact.
Are vreun sens, de ce e n minus 1, toată lumea?
Este pentru că matrice sunt indexate zero.
Ei încep de la 0 și a alerga până la n minus 1.
Da, e un pic complicat.
BINE.
Si atunci--
Audiența: Isnt'1 care deja grijă de, deși,
doar prin a spune nu ", mai mică sau egal cu "si doar că" mai puțin de? "
>> ANDI Peng: Acesta este un foarte bun întrebare.
Deci da.
Dar, de asemenea, modul în care suntem de punere în aplicare a dreptului de verificare,
aveți nevoie pentru a compara două valori.
Deci vrei de fapt să lăsați "la" gol.
Pentru că dacă veți compara asta, nu te duci
au nimic dupa ce a pentru a compara, nu?
Da.
Deci, i ++.
Să adăugăm paranteze noastre în.
Hopa.
Grozav.
Așa că avem la început de buclă nostru exterior.
Deci, acum, probabil, vrem să a crea o variabilă pentru păstrarea
evidența valoarea cea mai mică, nu?
Nimeni nu vrea să-mi dea linie de cod care ar face asta?
De ce avem nevoie, dacă vrem să doriți să stocați ceva?
>> Dreapta.
Poate un nume mai bun pentru că ar be-- "temp" total works--
poate o mai bună dreptate numit ar fi, dacă vrem cel mai mic value--
>> Audiența: Min.
ANDI Peng: min, acolo mergem.
min ar fi bine.
Și astfel aici, ce facem doriți să-l inițializa la?
Acesta este un pic complicat.
Pentru că acum, la începutul acestui tablou,
nu ați uitat la ceva, nu?
Deci, ceea ce, în mod automat, în cazul în care suntem doar pe i este egal cu 0,
ceea ce vrem pentru a inițializa prima noastră valoare minimă a?
Audiența: i.
ANDI Peng: i, exact.
Christabel, de ce vrem să-l inițializa la i?
>> Audiența: Pentru că, ei bine, suntem incepand cu 0.
Deci, pentru că nu avem nimic de a compara l, minimul va sfârși prin a fi 0.
>> ANDI Peng: Exact.
Deci, ea este exact corect.
Pentru ca avem de fapt, nu se uită la nimic încă,
nu știm ce valoare nostru minim este.
Vrem să-l inițializa la doar i, care, în prezent, este chiar aici.
Si ca vom continua sa deplasa în jos această matrice,
vom vedea că, cu fiecare pass suplimentar, i incrementează.
Și astfel, la acel moment, i este, probabil, va
să vrea să fie minim, pentru că va fi orice
este începutul matrice nesortate.
Misto.
>> Deci, acum vrem să adăugați o pentru buclă aici care este
O să repeta prin nesortate, sau restul acestui tablou.
Nimeni nu vrea să-mi dea un linie de cod care ar face asta?
Hint-- ce avem nevoie aici?
Ce se va merge în această buclă pentru?
Da.
Audiența: Deci am vrea să au un număr întreg diferit,
pentru că nu mai avem prin restul de matrice în loc de i, deci poate
J.
>> ANDI Peng: Da, J sună bine pentru mine.
Egal?
>> Audiența: Deci ar fi i, plus 1, pentru că începi la valoarea următoare.
Și apoi la end-- lucru din nou, j este mai puțin de n minus 1, și apoi j ++.
ANDI Peng: Great.
>> Și apoi aici, vom dori pentru a verifica pentru a vedea dacă starea noastră este îndeplinită,
dreapta?
Pentru că vrei să schimba valoarea minimă
dacă este de fapt mai mici decât ceea ce te-l in comparatie cu, nu?
Deci, ce vom vrea aici?
Verificați pentru a vedea.
Ce tip de declarație sunt, probabil, vom
TI doriți să utilizați, dacă doriți să verificați ceva?
>> Audiența: O if.
>> ANDI Peng: O if.
Deci if-- și ce va fi cu condiția ca ne-o dorim în interiorul
de if nostru?
>> Audiența: Dacă valoarea J este mai mică decât valoarea eu--
>> ANDI Peng: Exact.
Deci, așa if-- această matrice se numește "matrice".
Grozav.
Deci, dacă array-- ce a fost asta?
Spun asta din nou.
>> Audiența: Dacă array-j este mai mică de matrice-i, atunci ne-ar schimba min.
Deci min ar fi J.
>> ANDI Peng: Are vreun sens?
BINE.
Și acum aici, am de fapt, doresc să pună în aplicare swap, nu?
Deci amintesc, în curs, David, atunci când el a fost încercarea de a schimba ceea ce a fost the--
suc de portocale it-- și milk--
>> Audiența: Asta a fost brut.
>> ANDI Peng: Da, a fost un fel de brut.
Dar a fost un bun destul de Conceptul de timp demonstreze.
Deci, cred că de valorile tale aici.
Ai o serie de min, o serie de i,
sau orice am încercat să schimb aici.
Și, probabil, nu le poate turna în reciproc, în același timp, nu?
Deci, ce vom a trebui să creați aici
în scopul de a schimba valorile corect?
>> Audiența: O variabilă temporară.
>> ANDI Peng: O variabilă temporară.
Deci, hai sa facem Int temp.
Vezi, asta ar fi o mai bună timp sa-- Hei, ce a fost asta?
BINE.
Deci, aceasta ar fi fost mai bine timp pentru a denumi "temperatura". variabilă
Deci, hai sa facem Int temp.
Ce vom setat temp egală cu aici?
Audiența: Min?
ANDI Peng: Este un pic complicat.
Ea de fapt, nu contează în cele din urmă.
Nu contează ce Pentru alegeți să schimb în
atâta timp cât faci sigur că ești urmărirea ceea ce pompare.
>> Audiența: Ar putea fi matrice-i.
>> ANDI Peng: Da, hai sa facem matrice-i.
Și atunci ce e următoarea linie de cod vrem să avem aici?
Audiența: array-i este egal cu matrice-J.
ANDI Peng: Și, în fine?
Audiența: array-J este egal cu matrice-i.
Audiența: Sau array-j egali -matrice temp-- sau, temp.
>> ANDI Peng: OK.
Așa că haideți să ruleze acest lucru și a vedea în cazul în care va merge.
În cazul în care se întâmplă asta?
Oh, asta eo problemă.
Vezi, pe linia 40, suntem încearcă să folosească array-J?
Dar în cazul în care nu există doar în j?
>> Audiența: în buclă pentru.
ANDI Peng: dreapta.
Deci, ce vom trebuie să facem?
>> Audiența: Definirea l afara the--
Audiența: Da, cred că ai de a utiliza un alt if, nu?
Deci cum ar fi, în cazul în care minimum-- Bine, lasă-mă să gândesc.
>> ANDI Peng: Baieti, încercați să aruncăm o privire Să
vezi, ceea ce e ceva ce putem face aici?
>> Audiența: OK.
Deci, în cazul în care nu este egal cu minimul j-- Deci, dacă minimul este încă Eu--
atunci nu ar fi trebuit să schimbe.
>> ANDI Peng: Are ca egal i?
Ce vrei să spui aici?
>> Audiența: Da Sau, în cazul în care minim nu este egal cu i, da.
ANDI Peng: OK.
Ei bine, asta rezolvă, un fel de, problemele noastre.
Dar care încă nu rezolvă problemă de ceea ce se întâmplă în cazul în care de la J j--
nu există în afara de ea, ceea ce te vrem să facem cu ea?
Declare în afara?
Să încercați să rulați acest lucru.
Uh-oh.
Sortare nostru nu funcționează.
>> După cum puteți vedea, inițial nostru matrice a avut aceste valori.
Și după care ar trebui să aibă fost în 1, 2, 3, 4, 5, 6, 7, 8, 9.
Nu functioneaza.
Ahh.
Ce facem?
Audiența: Debug.
ANDI Peng: Bine, putem încerca asta.
Putem depana.
Micșora un pic.
Să setați breakpoint nostru.
Să mergem like-- OK.
>> Deci, pentru că știm deja că aceste linii, 15 prin 22,
sunt working-- că tot ce fac este doar iterarea prin și printing--
Eu pot merge mai departe și sari peste asta.
Să începem de la linia 25.
Oop, lasă-mă să scap de asta.
>> Audiența: Deci breakpoint de în cazul în care începe de depanare?
ANDI Peng: sau se opreste.
Audiența: sau se opreste.
ANDI Peng: Da.
Puteți seta mai multe puncte de întrerupere și se poate sari doar de la unul la altul.
Dar în acest caz nu știm în cazul în care eroarea se întâmplă.
Deci, vrem doar să începe de sus în jos.
Da.
BINE.
>> Deci, această linie de aici, putem interveni.
Puteți vedea aici, avem un tablou.
Acestea sunt valorile care sunt în matrice.
Nu vedeți că, cum indicele 0, aceasta corespunde value-- oh,
Am de gând să încerc pentru a mări.
Îmi pare rău, e foarte greu să see-- la index matrice 0,
avem o valoare de 4 și apoi așa mai departe și așa mai departe.
Avem variabilele locale.
Chiar acum i este egal cu 0, pe care ne-o dorim sa fie.
>> Și Să țină pas cu pas prin.
Minimă nostru este egal cu 0, care, de asemenea vrem să fie.
Și apoi vom intra în al doilea rând pentru noastre buclă, dacă array-j este mai mică de matrice-i,
care nu a fost.
Deci ai vedea cum care omit peste asta?
>> Audiența: Deci, dacă ar trebui să minim, toate that-- nu ar trebui ca
fie în interiorul primul pentru bucla?
ANDI Peng: Nu, pentru că mai vrei să testați.
Vrei să faci o comparație fiecare timp, chiar și după ce executați prin ea.
Nu vrei doar să o fac pe prima trecere-prin intermediul.
Vrei să o faci cu fiecare trecere suplimentar din nou.
Deci, doriți să verificați pentru starea dumneavoastră interior.
Deci, noi suntem doar de gând să continua să fie difuzate pe aici.
Îți dau un indiciu, băieți.
Ea are de a face cu faptul că atunci când te verificarea condiționată ta,
nu te verificarea pentru indicele corect.
Deci, acum ești de verificare pentru Indicele serie de j este mai mică de matrice
Indicele de i.
Dar ce faci de până la începutul a bucla for?
Ești setarea j egal cu i?
>> Da, astfel încât să putem, de fapt ieși debugger aici.
Deci, haideți să aruncăm o privire la pseudocod nostru.
For-- vom încep de la i este egal cu 0.
Vom merge până la n minus 1.
Să verificăm, am avea acest drept?
Da, asta a fost bine.
>> Deci, apoi în interiorul aici, suntem va crea o valoare minimă
și a stabilit că egală cu i.
Am făcut asta?
Da, a făcut asta.
Acum, în interiorul nostru pentru bucla, suntem de gând să faci j este egal cu I la n 1 minus.
Am făcut asta?
Într-adevăr, am făcut asta.
>> Deci toate acestea, ceea ce ne compară aici?
>> Audiența: J plus 1.
ANDI Peng: Exact.
Și apoi ai de gând să doriți să o setați minim dumneavoastră egal cu j plus 1, de asemenea.
Așa că am trecut prin asta foarte repede.
Înțeleg voi de ce e j plus 1?
BINE.
>> Deci, în matrice ta, în prima trecere prin,
pentru bucla, pentru Int i este egal cu 0, hai să
și asume acest lucru nu a fost schimbat încă.
Avem o serie de, complet, doar patru elemente nesortate, nu?
Deci, vrem să inițializa i egal cu 0.
Și am de gând să doar se alerga prin această buclă.
Și astfel, în prima trecere, vom pentru a inițializa o variabilă numită "min"
care, de asemenea, i este egal, pentru că nu avem o valoare minimă.
Așa că e în prezent egală cu 0, de asemenea.
Și apoi vom trece prin.
Și vrem să repeta din nou.
Acum, că ne-am găsit ceea ce minim nostru este, vrem să repeta prin
din nou, pentru a vedea dacă este comparat, nu?
Deci J, aici, se întâmplă la egal i, care este 0.
Și apoi, dacă j matrice plus I, care este cea care urmează peste, ca fiind mai puțin
decât ceea ce minim curentă valoare nu este, pe care doriți să schimb.
>> Deci, hai să spunem că am Trebuie, cum ar fi, 2, 5, 1, 8.
Acum, i este egal cu 0 și j este egal cu 0.
Și asta e valoarea noastră minimă.
Dacă array-j plus Eu-- Deci, dacă cel asta e, după cea ne uităm la
este mai mare decât cea în fața sa, se va deveni minim.
>> Deci, aici vom vedea că 5 nu este mai mică decât cea.
Așa că va nu fie 5.
Vedem că 1 este mai mică de 2, nu?
Deci, acum știm că minim noastră este va fi valoarea indicelui la 0, 1, 2.
Da?
Și apoi când ajungi aici, puteți schimba valorile corecte.
>> Așa că atunci când voi tocmai având j înainte, nu au fost cautati la cel
după el.
Te uitai la aceeași valoare, care
este motivul pentru care pur si simplu nu făcea nimic.
Asta face sens pentru toată lumea, de ce am nevoie de asta, plus 1 acolo?
BINE.
Acum hai să rulați prin ea pentru a face vă că restul de codul este corect.
De ce se întâmplă asta?
Ah, e chiar aici min.
Am fost compararea valorii greșit.
Oh nu.
>> Oh, da, aici am fost schimbarea valorile greșite, de asemenea.
Pentru că ne-am uitat la i și j.
Acestea sunt cele pe care le-au control.
Noi de fapt doresc să swap minim, minim actual,
cu oricare ar fi unul exterior este.
Și, după cum voi puteți vedea în jos aici, avem o gamă sortat.
Doar avut de a face cu faptul că atunci când
am fost de verificare Valorile ne-am comparat,
nu am fost uitat la valorile corecte.
Am fost uita la același cu cel aici, nu de fapt schimbarea.
Trebuie să se uite la următoarea să-l și apoi puteți schimba.
Deci asta e ceea ce a fost un fel de bugging codul nostru înainte.
Și ceea ce am făcut aici este totul debugger ar fi putut face pentru tine
Tocmai am făcut-o cu privire la bord, pentru că este mai ușor
pentru a vedea mai degrabă decât încercarea pentru a mări depanator.
Asta face sens pentru toată lumea?
Misto.
>> In regula.
Putem trece la a vorbi despre notație asimptotică, care
este doar un mod fantezist de a spune runtime de toate aceste tipuri.
Așa că știu pe David, în curs, atins runtime.
Și el a mers prin toată formula de modul de calculare a runtime.
Nu vă faceți griji despre asta.
Daca esti foarte curios cu privire la modul care funcționează,
nu ezitați să vorbească cu mine după secțiune.
Putem merge prin formulele împreună.
Dar toate voi avea într-adevăr să știu este că n pătrat peste 2
este același lucru ca n pătrat.
Deoarece cel mai mare număr, exponentul, crește cel mai mult.
Și astfel pentru scopurile noastre, tot ce ne pasă
este faptul că numărul uriaș care este în creștere.
>> Deci, ce este cel mai bun caz execuție de selecție fel?
Dacă aveți de gând să aibă a repeta printr-o listă
și apoi repeta prin restul de această listă,
De câte ori este Ai de gând să probabil,
în cel mai rău case-- în cel mai bun caz, sorry-- alerga prin?
Poate mai bine întrebarea este pentru a cere, ceea ce este cel mai rău caz
execuție de selecție fel.
Audiența: n pătrat.
ANDI Peng: E ​​n patrat, chiar.
Deci, o modalitate ușoară de a gândi de acest lucru este ca, în orice moment aveți două imbricate pentru bucle,
se va fi n pătrat.
Deoarece nu numai ca esti trece prin încă o dată,
trebuie să te întorci în jurul și a alerga prin ea
încă o dată, în interiorul pentru fiecare valoare.
Deci, în acest caz, rulați n ori n pătrat, care este-- Ne pare rău,
de n ori n, care este egal cu n pătrat.
>> Și un fel este, de asemenea, un pic unic, în sensul
că nu contează dacă acestea Valorile sunt deja în ordine.
Este încă în desfășurare pentru a rula prin intermediul oricum.
Să spunem doar că acest lucru a fost 1, 2, 3, 4.
Indiferent dacă este sau nu a fost în ordine, tot s-ar fi fugit prin
și încă verificat valoarea minimă.
Aceasta ar fi făcut Numărul de controale același
de fiecare dată, chiar dacă aceasta nu am atins nimic de fapt.
>> Deci, în acest caz, cel mai bun și mai rău runtime sunt de fapt echivalente.
Deci runtime așteptat de selecție fel,
pe care le desemnează prin simbolul de teta, theta, în acest caz,
de asemenea, ar fi n pătrat.
Toate cele trei dintre acestea ar fi n pătrat.
Este toată lumea clar pe ce runtime este n pătrat?
>> In regula.
Așa că am de gând doar pentru a rula rapid prin restul de soiuri.
Algoritmul de bubble sort-- amintiți-vă,
aceasta a fost prima David a trecut în curs.
În esență, vă pas prin întreaga listă
și tu ai doar swap-- compara două la un moment dat.
Și dacă unul e mai mare, decât doar le schimba.
Deci, dacă acestea sunt mai mari, v-ar schimba.
Am oficial aici.
>> Deci, hai să spunem că a avut 8, 6, 4, 2.
Te-ai compara 8 și un 6.
Ai avea nevoie de pentru a le schimba.
Te-ar compara 8 și 4.
Ai avea nevoie de pentru a le schimba.
Dacă trebuie să swap 8 și de 2, le modifica, de asemenea.
Deci, într-un astfel de sens, puteți vedea, jucat pe o perioadă lungă de timp,
cum un fel de valori cu bule la capete, motiv pentru care noi o numim
bubble sort.
>> Ne-ar alerga doar prin din nou pe doua trecere noastră, și a treia treci noastre,
și a patra trecere nostru.
În esență, bubble sort doar ruleaza până când nu face nici mai swap-uri.
Deci, în acest sens, aceasta este doar Pseudocodul general pentru ea.
Nu vă faceți griji, acestea vor fi toate on-line.
Noi nu trebuie să mergem de fapt, peste acest lucru.
>> Am inițializa doar un contor variabilă care începe la 0.
Și am repeta prin întreaga rețea.
Și dacă o valoare este-- dacă acest lucru Valoarea este mai mare decât această valoare,
ai de gând pentru a le schimba.
Și apoi ești O să continui.
Și ai de gând să conta.
Și tu doar de gând să continuăm să facem acest timp contorul este mai mare
decât 0, ceea ce înseamnă că de fiecare dată când trebuie să schimbe,
știi că vrei să mergi înapoi și verificați din nou.
Doriți să păstrați verificarea până când nu știți care nu trebuie să mai schimbe.
>> Deci, ce sunt cele mai bune și cele mai rele caz Runtime pentru bule fel?
Și hint-- aceasta este de fapt diferit de la fel de selecție, în sensul
că aceste două răspunsuri nu sunt la fel.
Gândiți-vă la ce se va întâmpla în un caz în cazul în care a fost deja sortate.
Și cred despre ceea ce s-ar întâmpla dacă ar fi fost
în cazul în care nu a fost sortate.
Și puteți rula un fel de prin ce se întâmplă asta.
Îți dau baieti, cum ar fi, 30 secunde să se gândească la asta.
>> BINE.
Are cineva o presupunere la ceea ce cel mai rău caz de execuție de bule fel este?
Da.
>> Audiența: ar fi, cum ar fi, de n ori n minus 1 sau ceva de genul asta?
Cum ar fi, de fiecare dată când se execută, este doar, cum ar fi, un schimb mai puțin
că orice ar fi fost.
>> ANDI Peng: Da, așa esti complet dreptate.
Și acesta este un caz în care dumneavoastră Răspuns fost de fapt mult mai complex
decât cea care avem nevoie pentru a da.
Deci o să run-- Sunt O să șterge toate astea aici.
Este toată lumea buna?
Pot să șterg acest lucru?
BINE.
Vei trece prin n ori prima dată, nu?
Și ei vor trece prin n minus 1 a doua oară, nu?
Și apoi ai de gând să păstreze merge, n mina 2, etc..
David a făcut acest lucru într-o conferință, în cazul în care, dacă ați adăugat la toate aceste valori,
ai ceva care este like-- yeah-- peste 2, care, în esență, doar reduce
până la n pătrat.
Vei obține un fracțiune ciudat acolo.
Și așa știu doar că N pătrat întotdeauna
are prioritate față fracțiunea.
Și astfel, în acest caz, cel mai rău execuție ar fi n pătrat.
Dacă ar fi fost în descendent ordine, cred că, vă
trebuie să facă un schimb de fiecare dată.
>> Care ar fi, eventual, cel mai bun caz de execuție?
Să spunem doar că, în cazul în care lista a fost deja în ordine, ceea ce ar fi runtime?
>> Audiența: n.
ANDI Peng: E ​​n, exact.
Și de ce este n?
Audiența: Pentru că doar Trebuie să verific fiecare dată.
ANDI Peng: Exact.
Deci, în cel mai bun Runtime posibil, dacă această listă a fost deja
sorted-- să zicem 1, 2, 3, 4-- te ar merge doar prin, ar trebui să verificați,
te-ar vedea, oh, toate pan afară.
Nu am avut de a schimba.
Am terminat.
Deci, în acest caz, e doar n sau numărul de pași pe care tocmai ați
a trebuit să verifice în prima listă.
>> Și după, am acum a lovit fel de inserție, în cazul în care
algoritmul este în esență de a împărți l într-o porțiune sortat și nesortate.
Și apoi unul câte unul, valorile sunt nesortate
introdus în cazul lor poziții la începutul listei.
>> Deci, de exemplu, avem un Lista de 3, 5, 2, 6, 4 nou.
Știm că este în prezent nesortate că Tocmai am
a inceput sa caute la ea.
Ne ia o privire și știm că prima valoare este sortata, nu?
Dacă sunteți doar uita la o serie de mărime unul, știi că e sortate.
>> Deci, atunci știm că alte patru sunt nesortate.
Mergem prin și vom vedea că valoarea.
Hai sa ne intoarcem.
Vezi că valoarea 5?
Ne ia o privire la ea.
Am compara cu 3.
Știm că este mai mare decât 3, astfel încât știm că e sortate.
Deci, noi știm acum că primele două sunt sortate, iar ultimele trei nu sunt.
>> Ne ia o privire la două.
În primul rând am verifica cu 5.
Este mai puțin de 5?
Nu e.
Așa că trebuie să continui să cauți în jos.
Apoi, va verifica 2 pe 3.
E mai puțin de?
Nu.
Deci știi un 2 trebuie să fie introdusă în partea din față și 3 și 5
ambele trebuie să fie împins afară.
Face acest lucru din nou cu 6 și 4.
Și ținem de verificare, în esență, în cazul în care ne-am verifica, verifica, verifica.
Și până când este în dreapta poziție, am un fel de doar
introduceți-l în poziția corectă, care este în cazul în care numele de a venit de la.
>> Deci asta e doar algoritmul, pseudocod în sine, un fel de,
de modul în care s-ar pune în aplicare un fel de introducere.
Pseudocod este aici.
Totul e on-line.
Nu vă faceți griji dacă voi sunt încercarea de a copia acest jos.
Deci, încă o dată, la fel question-- ce ar fi cel mai bun și cel mai rău runtime
pentru inserarea fel?
Este foarte similar cu ultima întrebare.
Îți dau baieti, cum ar fi, 30 secunde să se gândească la aceasta, de asemenea.
>> OK Vrea cineva să da-mi cel mai rău de execuție?
Da.
>> Audiența: n pătrat.
>> ANDI Peng: E ​​n pătrat.
Și de ce este n pătrat?
>> Audiența: Deoarece în ordine inversă, aveți
pentru a merge prin n ori n, care este--
ANDI Peng: Da, exact.
Deci, aceeași lucru ca și în genul bubble.
Dacă această listă este în ordine descrescătoare, ești
Va trebui să verificați mai întâi o dată.
Și apoi cu fiecare valoare suplimentară, ești
Va trebui să-l verifice împotriva fiecare valoare unică, nu?
Și astfel totul, ai de gând să facă un ori n trece un alt n trece, care
este n pătrat.
Ce despre cel mai bun caz?
Da.
>> Audiența: n minus 1, pentru că Primul este deja pătrat.
>> ANDI Peng: Deci, de aproape.
Răspunsul este, de fapt n.
Că în timp ce primul este sortate, nu se poate actually--
ne-am avut ghinion, în acest exemplu, că 2
sa întâmplat să fie cel mai mic număr.
Dar asta nu va fi întotdeauna cazul.
Dacă 2 este deja sortate la începutul dar te uiti și există o 1 aici,
de 1 o va ciocni.
Și se va termina prin a fi lovit oricum.
>> Deci, în cel mai bun caz, este de fapt doar de gând să fie n.
Dacă aveți 1, 2, 3, 4, 5, 6, 7, 8, ești
de gând să ruleze prin că întreaga listă dată
pentru a verifica pentru a vedea dacă totul e în regulă.
Este toată lumea clar pe care rulează ori de selecție, precum și?
Știu că voi prin acestea foarte repede.
Dar știu doar că, dacă știți concepte generale, ar trebui să fie bun.
BINE.
Așa că voi da doar voi poate, cum ar fi, un minut pentru a vorbi cu vecinii tăi
asupra a ceea ce sunt doar câteva din diferențele principale
între aceste tipuri de tipuri.
Vom trece peste asta în curând.
Audiența: Oh, OK.
ANDI Peng: Da.
BINE.
Rece, să se întrunească din nou ca o clasă.
BINE.
Deci asta a fost un fel de întrebare deschisă, în sensul
că există o mulțime de răspunsuri la ele.
Și vom trece peste unele dintre ele pe scurt.
Am vrut doar să te voi gândesc la ceea ce diferențiază
toate cele trei tipuri de soiuri.
Și am auzit, de asemenea, o mare question-- ce merge sort face?
Marea întrebare, pentru că asta e ceea ce ne acoperă următor.
>> Deci, merge sort este un fel care funcționează
foarte diferit de celelalte tipuri.
După cum voi puteți see-- a făcut David asta demo
unde a avut toate rece zgomote de a vedea cum merge
fel a fugit, cum ar fi, infinit mai repede decât celelalte două tipuri?
BINE.
Deci asta pentru ca merge pune în aplicare un fel care se divid
și cuceri concept care ne-am a vorbit despre o mulțime de curs.
În acest sens, care ne place să lucreze mai inteligent, nu mai greu, atunci când împărțiți
și cuceri probleme, și le sparge jos, iar apoi le-a pus împreună,
lucruri bune se întâmplă întotdeauna.
>> Deci felul în care merge Lucrari de sortare, în esență,
este faptul că împarte o matrice nesortate în jumătate.
Și apoi are două jumătăți de tablouri.
Și se sortează doar cele două jumătăți.
Doar ține împărțirea în jumătate, în pe jumătate, în jumătate până când totul este sortată
și apoi recursiv pune totul împreună.
>> Așa că e foarte abstract.
Deci, aceasta este doar un pic de pseudocod.
Asta face sens în modul în care aceasta rulează?
Deci, hai să spunem că aveți o matrice de n elemente, nu?
Dacă n este mai mică de 2, vă puteți întoarce.
Pentru că știi că dacă e doar un singur lucru, acesta trebuie să fie sortate.
Altfel, sortați jumătatea stângă, și apoi sortați jumătatea din dreapta,
și apoi îmbinați.
>> Deci, în timp care arata foarte usor, în realitate, gândindu-e
un fel de dificil. Pentru că ești ca, Ei bine, asta e un fel de a rula pe sine.
Dreapta?
Se rulează pe sine.
Deci, în acest sens, David atins la recursivitate în clasa.
Și că este un concept vom vorbi despre mai mult.
Este că acest fapt, aceste două linii aici, de fapt, este doar programul
spunandu-i sa se rula cu intrare diferite.
Deci, mai degrabă decât se rula cu totalitatea n elemente,
puteti rupe în jos, în jumătate stânga și jumătatea din dreapta
și apoi executați din nou.
>> Și apoi ne vom uita la ea vizual, pentru că eu sunt un elev vizual.
Acesta funcționează mai bine pentru mine.
Deci ne vom uita la un exemplu vizual aici.
>> Să presupunem că avem o gamă, șase Elemente, 3, 5, 2, 6, 4, 1, nu sortate.
Bine, există o mulțime de pe aceasta pagina.
Deci, dacă voi sa te uiti la primul pas aici, 3, 5, 2, 6, 4, 1,
puteti împărțită în jumătate.
Aveți 3, 5, 2, 6, 4, 1.
Știi că aceste tu aren't-- Nu știu dacă acestea sunt sortate sau nu,
astfel încât să păstrați de rupere le în jos, în jumătate, în jumătate, în jumătate, până în cele din urmă,
ai doar un element.
Și un element este întotdeauna sortate, nu?
>> Deci, noi știm că 3, 5, 2, 4, 6, 1, prin ele însele, sunt sortate.
Și acum putem le-a pus din nou împreună.
Deci, știm 3, 5.
Am pus cele impreuna.
Știm că e sortat.
Cele 2 anii încă acolo.
Putem pune 4 și 6 împreună.
Știm că ce se sortate, asa ca am pus ca impreuna.
Iar 1 este acolo.
>> Și apoi doar te uiți la aceste două jumătăți aici.
Ai 3, 5, 2, 2, 3, 5.
Puteți compara doar începând de tot.
Pentru că știi că acest lucru este sortate și știi că e sortate.
Deci atunci nu măcar nu trebuie să compara 5, comparați doar 3.
Iar 2 este mai mic de 3, așa Știi 2 trebuie să în cele din urmă.
>> Același lucru acolo.
De 1 trebuie să meargă aici.
Și când te duci pentru a pune aceste două valori împreună,
știți că acest lucru este sortati si știți că este sortată.
Deci atunci 1 și 2, 1 să fie mai mică de 2.
Care vă spune că 1 ar trebui să meargă la sfârșitul acestui
fără măcar să se uite la 3 sau 5.
Și apoi 4, puteți doar verifica, merge chiar aici.
Nu trebuie să se uite la 5.
Același lucru cu 6.
Știi că 6-- doar nu are nevoie să fie privit.
>> Și astfel, în acest fel, ești doar te de economisire
o mulțime de pași atunci când sunteți comparat.
Nu trebuie să compare fiecare Element împotriva altor elemente.
Trebuie doar compara cu cele care trebuie să-l compare cu.
Deci, asta e un fel de concept abstract.
Nu vă faceți griji dacă nu este destul de tine lovind încă dreptate.
Dar, în general, aceasta este cum un fel de lucrări de îmbinare.
Întrebări, întrebări rapide, înainte de a mă muta pe?
Da.
>> Audiența: Deci ați spus că luați pozițiile 1, iar apoi de 4, și 6
și le-a pus în.
Deci, nu sunt those-- nu sunt te uiți la ele
ca elemente separate, nu în ansamblul său?
ANDI Peng: Da.
Deci, ce se întâmplă este că de fapt
creează o gamă de brand nou.
Astfel încât să știți că, de aici, am două tablouri de dimensiuni 3, nu?
Deci știți că matrice mea sortat trebuie să aibă șase elemente.
Deci, doar să creați un nouă sumă de memorie.
Deci ești un fel de fiind risipă de memorie,
dar asta nu contează pentru că este atât de mic.
Deci te uiti la 1 și te uiți la 2.
Și știi că 1 este mai mică de 2.
Deci știi că ar trebui să meargă în 1 începutul tuturor celor.
>> Nici măcar nu trebuie să uita-te la 3 și 5.
Deci știi 1 merge acolo.
Apoi, va taie practic pe 1.
E, cum ar fi, mort pentru noi.
Apoi avem doar 2, 3, 5, și apoi 4 și 6.
Și apoi știi asta, compara 4 și 2,
oh, 2 ar trebui să meargă acolo.
Deci ai plop 2 jos, ai taie.
Deci, atunci doar ai 3 și 5 în 4 și 6.
Și vă păstrați tocare-l până când le-a pus în matrice.
>> Audiența: Deci tu ești doar mereu compararea [neauzit]?
>> ANDI Peng: Exact.
Deci, în acest sens, ești doar compararea, în esență,
un număr de împotriva celeilalte numărul.
Și pentru că știi că este sortate, tu
Nu trebuie să se uite prin toate numerele.
Trebuie doar să te uiți la prima.
Și apoi puteți plop doar le în jos, pentru că știi
din care fac parte în cazul în care au nevoie să aparțină.
Da.
Buna intrebare.
>> Și apoi, dacă vreunul dintre voi sunt un pic ambițios,
nu ezitați să se uite la acest cod.
Aceasta este de fapt implementarea fizică
de modul în care ne-ar scrie merge sort.
Și puteți vedea, este foarte scurt.
Dar ideile din spatele aceasta sunt destul de complexe.
Deci, dacă vă simțiți ca de desen asta în temele seara asta, nu ezitați să.
>> BINE.
David, de asemenea, a trecut acest lucru în curs.
Care sunt cel mai bun caz runtime, cele mai grave runtime caz,
și runtime așteptate ale merge fel?
Cateva secunde de a gândi.
Acest lucru este destul de greu, dar un fel de intuitiv dacă te gândești la asta.
In regula.
>> Audiența: Este cel mai rău caz, n log n?
ANDI Peng: Exact.
Și de ce este n log n.
>> Audiența: Nu este pentru că devine exponențial rapid,
deci este ca o funcție de care în loc de a fi pur și simplu n
pătrat sau ceva?
ANDI Peng: Exact.
Deci motivul pentru care rulare pe acest lucru este n Conectare
n este because-- ceea ce ești tu face în toate aceste etape?
Ești doar o tocare în jumătate, nu?
Și așa că atunci când că facem jurnal, tot ceea ce face
este divizarea o problemă în jumătate, în jumătate, în jumătate, în mai multe reprize.
Și în acest sens, puteți fel de a elimina modelul liniar
pe care le-am folosit.
Pentru că, atunci când taie lucruri în jumătate, este un jurnal.
Asta e doar matematic mod de a reprezenta aceasta.
>> Și apoi în cele din urmă, la sfârșitul anului, ești făcând doar o ultimă trecere prin
pentru a pune toate acestea în ordine, nu?
Și deci, dacă aveți doar să verifica un singur lucru, care este n.
Și așa ești un fel de înmulțirea cele două împreună.
Deci e ca si cum ai că finală verifica N aici cu un jurnal de n
Aici sus.
Și dacă multiplica le, care a n log n.
>> Și astfel cel mai bun caz și cel mai rău caz și de așteptat sunt toate n log n.
Este, de asemenea ca un alt fel.
E ca si cum un fel de selecție în sensul că acesta
nu conteaza ceea ce dvs. Lista este, e doar de gând
să facă același lucru de fiecare data.
BINE.
Deci, ca voi poate vedea, chiar dacă soiurile pe care le-am trecut through-- n
pătrat, nu e foarte eficient.
Și chiar acest n log n este nu cel mai eficient.
Dacă voi sunt curioși, există mecanisme de sortare
care sunt atât de eficient, care sunt aproape în esență, plat în timpul rulării.
>> Ai niște log n lui.
Ai niște log log n lui.
Noi nu atingeți asupra lor în această clasă acum.
Dar dacă voi sunteți curioși, nu ezitați să Google, ceea ce este
cele mai eficiente mecanisme de sortare.
Nu știu, există unele foarte amuzant,
like-- există unele foarte cele amuzante pe care oamenii fac.
Și te întrebi cum gândit vreodată la asta.
Deci Google, dacă aveți ceva de rezervă timp, pe, care sunt câteva modalități amuzante
că people-- precum și oameni ways-- eficiente
au fost în măsură să pună în aplicare felul.
BINE.
Și aici este doar un grafic la îndemână pic.
Știu că voi toți, înainte de asta test 0, va fi în camera ta, probabil, încearcă
să memoreze asta.
Așa că e frumos acolo pentru voi.
Doar nu uitați că logica made-- de ce aceste numere au fost loc.
Dacă sunteți mereu pierdut, face doar vă că știți ce tipuri sunt.
Și puteți rula prin le în mintea ta
să dau seama de ce cei răspunsurile sunt aceste răspunsuri.
>> In regula.
Deci vom să se mute pe, în cele din urmă, la căutarea.
Pentru că așa cum cei dintre voi care au citit PSET,
Căutarea este, de asemenea, parte din seturi problemă din această săptămână.
Vi se va cere să pună în aplicare două tipuri de căutări.
Una dintre ele este o căutare liniară și unul este o căutare binară.
>> Deci căutarea liniară este destul de ușor.
Tu vrei să element de căutare unei liste pentru a vedea dacă-l.
Trebuie doar să itera prin.
Și dacă este egal cu ceva, puteți doar întoarce, nu?
Dar cel pe care suntem cel mai interesat în a vorbi despre
este binar de căutare, dreapta, care este diviza și cuceri care mecanism
David a fost să demonstreze în curs.
>> Amintiți-vă de exemplu cartea de telefon că el continuă creșterea,
cel care a luptat de tip un pic pe acest an trecut,
în cazul în care împarte problema în jumătate, în jumătate, în jumătate, din nou și din nou,
până când găsiți ceea ce căutați pentru?
Și le-ați luat rulare de la fel de bine.
Și puteți vedea, e mult mai eficiente
decât orice alt tip de căutare.
>> Deci felul în care ne-ar merge cu privire la de punere în aplicare o căutare binară
este, dacă am fi avut o matrice, index 0 până la 6, șapte elemente,
putem să ne uităm la mijloc, right-- Ne pare rău, în cazul în care întrebarea noastră first--
dacă vrem să ne punem întrebarea de, nu matrice conține elementul de 7,
Evident, fiind oameni, și având o astfel de matrice mic, este ușor pentru noi
să spun da.
Dar modul de a pune în aplicare un binar căutare ar fi să se uite la mijloc.
>> Știm că indicele 3 este mijloc, pentru că noi
știu că sunt șapte elemente.
Ce 7 împărțit la 2?
Puteți taie la plus 1.
Ai 3 în mijloc.
Deci, este matrice de 3 egală cu 7?
Nu este, nu?
Dar putem face un cuplu de controale.
Este serie de 3 mai mică de 7 sau este matrice de 3 mai mare decât 7?
>> Și știm că este mai puțin de 7.
Deci, noi știm că, oh, aceasta trebuie să să nu fie în jumătatea stângă.
Știm că trebuie să fie în jumătatea dreaptă, nu?
Astfel încât să putem taie doar de pe jumătate din matrice.
Noi nu măcar nu trebuie să mai uita-te la ea.
Pentru ca stim ca jumătate din problem-- noastre
știm că răspunsul este în jumătatea dreaptă a problemei noastre.
Deci, ne-am uita la asta acum.
>> Deci, acum ne uităm la mijlocul a ceea ce a mai rămas.
Că indicele de 5.
Noi facem din nou aceeași verificarea și vom vedea că este mai mic.
Deci, ne uităm la stânga pe care.
Și apoi vom vedea că check.
Este valoarea la matrice index 4 egal cu 7?
Este.
Deci, putem întoarce adevărat, pentru că am gasit valoarea în lista noastră.
Are modul în care am trecut prin care face sens pentru toată lumea?
BINE.
Îți dau baieti poate, cum ar fi, trei, patru minute pentru a descoperi
Cum să pseudocod acest.
>> Deci imaginați-vă-am rugat să scrie o funcție numită căutare (), care a revenit
o valoare, o valoare Boolean, care a fost adevarat sau false-- ca,
adevărat dacă ai găsit valoare, false, dacă nu.
Și apoi ai fost a trecut în valoarea pe care
căutați în valori, care este array-- oh, mi-am pus cu siguranta
că în locul nepotrivit.
BINE.
Oricum, faptul că ar trebui să aibă fost în partea dreaptă a valorilor.
Și apoi int n este numărul de elemente în care matrice.
Cum te-ai duce despre încercarea să pseudocod această problemă în?
Îți dau tipi ca trei minute pentru a face asta.
Nu, cred că nu e only-- Da, nu e unul chiar aici.
Audiența: Pot?
ANDI Peng: Da, am ai.
Este că de lucru?
Bine, in regula.
>> BINE.
Toate baieti dreapta, suntem gând să-l țină în frâu.
BINE.
Deci presupunem că avem acest minunat mic tablou cu valori N în ea.
Nu am trage linii.
Dar cum ar fi să mergem despre încercarea de a scrie acest lucru?
Nimeni nu vrea să da-mi prima linie?
Dacă doriți să-mi dai prima linie de acest pseudocod.
>> Audiența: [inaudibil]
Audiența: Ai vrea a repeta through--
Audiența: Doar un alt pentru buclă?
Audiența: -Pentru.
>> ANDI Peng: Deci asta e un pic complicat.
Gândiți about-- vrei a continua să fie difuzate această buclă
de peste si peste din nou, până când?
>> Audiența: Până la [neauzit] valoare este egală cu această valoare.
ANDI Peng: Exact.
Astfel încât să puteți de fapt doar write-- putem chiar simplifica mai mult.
Putem face doar o buclă în timp ce, nu?
Astfel încât să puteți avea doar loop-- știm că este un timp.
Dar pentru acum, am de gând a spune "buclă" - prin ce?
Buclă until-- ceea ce este condiția noastră se încheie?
Cred că am auzit.
Am auzit pe cineva spun.
>> Audiența: Valorile egal de mijloc.
ANDI Peng: spune din nou.
Audiența: Sau, până la Valoarea sunteți în căutare
este egală cu valoarea de mijloc.
>> ANDI Peng: Ce se întâmplă dacă nu e acolo?
Ce se întâmplă dacă valoarea pe care căutați pentru că nu este, de fapt, în acest tablou?
Audiența: Reveniți 1.
>> ANDI Peng: Dar ce vrem să bucla până dacă avem o afecțiune?
Da.
>> Audiența: Până când nu este doar o valoare?
ANDI Peng: Puteți buclă until-- astfel încât să știți că ești
va avea o valoare maximă, nu?
Și știi că vei pentru a avea o valoare min, nu?
Pentru că, de asemenea, că e ceva Am uitat să spun înainte,
că ceva care este critice despre căutare binară
este faptul că matrice dvs. este deja sortate.
Pentru ca nu exista nici o modalitate de a face acest lucru, dacă acestea sunt valori doar aleatoare.
Nu știu dacă e nimeni mai mare decât celălalt, nu?
>> Astfel încât să știți că Max și min tale sunt aici, nu?
Dacă aveți de gând să fie de reglare max în minute tale si mid--
Să presupunem dvs. Valoarea mijlocul lunii este here-- corect
ai de gând să practic buclă până minimă este
aproximativ la fel ca max ta, dreapta, sau în cazul în care max nu este la fel ca dumneavoastră min.
Dreapta?
Pentru că atunci când acest lucru se întâmplă, știi că în cele din urmă le-ați lovit de aceeași valoare.
Deci vrei să bucla până min dvs. este mai mică sau egală sa-- oops,
Nu mai mică sau egală cu, în altă parte around-- max este.
>> Făcut asta face sens?
Am luat câteva încearcă să acest drept.
Dar buclă până când valoarea ta max este, în esență, aproape mai puțin
mic sau egal cu minimum, nu?
Asta e atunci când știi care le-ați convergente.
Audiența: Când doriți maxim dvs. Valoarea fie mai mică decât valoarea minimă?
ANDI Peng: Dacă vă păstrați ajustându-l, care
este ceea ce vom să faci în acest sens.
Are sens?
Minime și maxime sunt doar numere întregi care sunt, probabil, ne
O să doriți să creați pentru a menține evidența unde căutați.
Deoarece există matrice indiferent de ceea ce facem.
Cum ar fi, nu suntem de fapt fizic tocare de pe matrice, nu?
Noi doar ajustarea în cazul în care ne uităm.
Are sens?
>> Audiența: Da.
>> ANDI Peng: OK.
Deci, dacă asta e condiția pentru bucla noastră, ceea ce vrem interiorul această buclă?
Ce vom fi doresc să facă?
Deci acum, avem max si un min, drept,
probabil a creat aici pe undeva.
Vom dori, probabil, pentru a găsi un mijloc, nu?
Cum vom fi în stare să găsească mijlocul?
Care este mathematical--
Audiența: Max plus min împărțit la 2.
ANDI Peng: Exact.
Are sens?
Și nu voi vedea ce am nu doar use-- ce am făcut asta
în loc de a face doar n împărțit la 2?
Este pentru că n este o valoare care va rămâne la fel.
Dreapta?
Dar, așa cum ne-am adapta minim nostru și valori maxime, ei vor să se schimbe.
Și, ca urmare, de mijloc nostru se va schimba prea.
Deci, de aceea ne-o dorim pentru a face acest lucru chiar aici.
BINE.
>> Și apoi, acum, că am găsit our-- da.
>> Audiența: Doar un question-- rapid cand spui min și max,
suntem presupunând că este deja sortate?
>> ANDI Peng: Da, asta e de fapt o condiție prealabilă pentru o căutare binară,
că trebuie să știi este sortate.
Care este motivul pentru fel, vă scrie în ta problemă pusă înaintea căutarea binară.
BINE.
Deci, acum că știm unde punctul de mijloc nostru este, ce vrei să faci aici?
>> Audiența: Vrem să compare că la celălalt.
ANDI Peng: Exact.
Deci ai de gând să compare la mijlocul de valoare, nu?
Și ce spune asta noi atunci când vom compara?
Ce vrem sa facem după aceea?
>> Audiența: Dacă valoarea este mai mare decât la mijlocul, dorim să-l taie.
ANDI Peng: Exact.
Deci, în cazul în care valoarea este mai mare decât la mijlocul, suntem
va doriți să modificați aceste maxes minim și, nu?
Ce vrem să se schimbe?
Deci, dacă știm că valoarea este undeva aici, ceea ce nu-i putem pentru a schimba?
Vrem să schimbăm nostru minim pentru a fi la mijlocul, nu?
Și apoi altceva, dacă e în acest jumătate, ceea ce vrem să se schimbe?
>> Audiența: maxim ta.
ANDI Peng: Da.
Și apoi tu doar mergi pentru a păstra looping, nu?
Pentru că acum, după o iterație prin, ai un max aici.
Și apoi puteți recalcula un mid.
Și apoi puteți compara.
Și ai de gând să continui până la minute și a maxes
au convergente în esență.
Și atunci știi că ai lovit la sfârșitul anului acesta.
Și fie că ai găsit- sau nu ai în acel moment.
>> Are acest sens tuturor?
BINE.
Acest lucru este foarte important, pentru că veți avea
pentru a scrie acest lucru în seara asta cod dumneavoastră.
Dar voi aveți o destul de bine sentiment de ceea ce ar trebui sa facem,
care este bun.
BINE.
Deci avem despre șapte minute a plecat secțiune.
Deci vom vorbi despre acest PSET că vom face.
Deci PSET este împărțit în două jumătăți.
Prima jumătate implică de punere în aplicare o descoperire
în care scrie o căutare liniară, un căutare binară, și un algoritm de sortare.
>> Deci aceasta este prima timp într-un PSET unde
vom fi oferindu-vă voi ceea ce se numește cod de distribuție, care este codul
că ne-am pre-scris, dar tocmai a plecat câteva piese de pe
pentru tine de a termina de scris.
Deci, voi, atunci când te uiți la acest cod, s-ar putea obține cu adevărat speriat.
Dacă sunteți la fel ca, ahh, am Nu știu despre ce face,
Nu știu, cum ar fi, care pare atât de complicat, ahh, relaxați-vă.
E bine.
Citiți spec.
Spec va explica exact ce toate aceste programe fac.
>> De exemplu, generate.c este un program care va veni cu PSET ta.
Nu trebuie de fapt să-l atingă, dar tu ar trebui să înțeleagă ce face.
Și generate.c, tot ce este face fie generatoare de numere aleatoare
sau puteți da o sămânță, ca un Numărul prestabilite că este nevoie de,
și generează mai multe numere.
Deci, există o modalitate specifică punerea în aplicare a generate.c în care
puteți face doar o grămadă de numere pentru tine de a testa alte metode pe tine.
>> Deci, dacă ai vrut să, pentru exemplu, testați găsi dumneavoastră,
ce-ar vrea să rulați generate.c, genera o grămadă de numere,
și apoi executați funcția ajutoare.
Funcția dvs. ajutoare este în cazul în care sunteți de fapt, scrierea de cod fizic.
Și cred că de ajutoare ca un fișier bibliotecă te scris că descoperire este de asteptare.
Și astfel în helpers.c, veți face căutarea și sortarea.
>> Si apoi vei esență doar le pe toate la un loc.
Spec vă va spune cum să a pus că pe linia de comandă.
Și vei putea pentru a testa dacă sau nu un fel și de căutare sunt de lucru.
Misto.
Are cineva a început deja și problemele întâmpinate sau întrebări
ei au acum cu asta?
BINE.
>> Audiența: Așteaptă.
Am o intrebare.
>> ANDI Peng: Da.
>> Audiența: Așa că am început să fac căutarea liniară în helpers.c
și nu a fost într-adevăr de lucru.
Dar apoi mai târziu, am aflat ne-am trebuie să-l ștergeți și de a face căutare binară.
Deci, contează în cazul în care nu funcționează?
>> ANDI Peng: răspuns scurt este nu.
Dar din moment ce noi suntem not--
Audiența: Dar nimeni nu de fapt de verificare.
ANDI Peng: Noi niciodată nu suntem O să văd asta.
Dar, probabil, doriți să faceți vă că de căutare este de lucru.
Pentru că dacă liniar dvs. căutare nu funcționează,
atunci sunt șanse binar dvs. căutare nu este de gând să lucreze la fel de bine.
Pentru că aveți similare logică în ambele.
Și nu, nu contează.
Deci, singurele vei întoarce în fel și sunt de căutare binară.
Da.
>> Și, de asemenea, o mulțime de copii au fost încercarea de a compila helpers.c.
Nu esti de fapt este permis a face acest lucru, pentru că helpers.c
nu are o funcție principală.
Și așa trebuie doar fi de fapt compilarea
genera și pentru a găsi, pentru că a găsi apeluri helpers.c și funcțiile din cadrul acestuia.
Astfel încât face depanare o durere în fund.
Dar asta e ceea ce trebuie să facem.
Audiența: Tocmai ai face toate, nu?
ANDI Peng: Puteți doar face toate la fel de bine, da.
BINE.
Deci asta e, în termeni de ceea ce PSET cere ca toți să faci.
Dacă aveți orice întrebări, simt liber să mă întrebi după secțiune.
Voi fi aici pentru, cum ar fi, de 20 de minute.
>> Și da, PSET lui într-adevăr nu așa de rău.
Voi ar trebui să fie OK.
Acestea, urmați doar orientări.
Un fel de un sentiment de, în mod logic, ceea ce ar trebui să se întâmple și vei fi bine.
Nu fi prea frică.
Există o mulțime de cod deja scris acolo.
Nu fi prea speriați dacă nu să înțeleagă ce înseamnă toate astea.
În cazul în care o mulțime, e în regulă.
Și vin la ore de birou.
Vă vom ajuta să luați o privire.
>> Audiența: Cu extra funcții, ne crezi pe cei sus?
>> ANDI Peng: Da, acestea sunt în codul.
În jocul de 15, jumătate din este deja scris pentru tine.
Deci, aceste funcții sunt deja în codul.
Da.
In regula.
Ei bine, cel mai bun de noroc.
E o zi dezgustător.
Deci, sperăm că voi nu se simt prea rău stau în interiorul și codificare.