[SCRÂȘIT] [FOȘIT] [CLIC] PROFESORUL: Bine, oameni buni. Cred că este timpul să începem. Vă mulțumesc băieți pentru că ați ajuns la sesiunea noastră cu probleme și cred că am vorbit cu mulți dintre voi virtual, având în vedere numărul de oameni din sală. Dar asta e perfect. Dreapta. Deci suntem în sesiunea cu probleme numărul doi pentru 6.006. Sperăm că sunteți cu toții în locul potrivit. Eu sunt Justin. Mă uitam la o mică foaie de calcul cu cine învață ce, și cred că sunteți blocați cu mine în multe dintre aceste sesiuni cu probleme, ceea ce, cred că, în ceea ce privește orele de video, înseamnă că sunteți blocați să- mi ascultați vocea cel mai mult. Îmi pare rău în avans. Dar, în orice caz, este întotdeauna distractiv să faci astfel de lucruri. Și mi-a dat ocazia să fac teme, pe care nu le-am mai făcut de foarte mult timp. Așa că aseară, am rezolvat toate aceste probleme și am venit cu propriile mele răspunsuri hacked-together pentru acestea, care, din fericire, au fost mai mult sau mai puțin de acord cu ceea ce era în cheia de răspuns, pe care le am și tu nu. Cred că lansăm pe... deci există o mică eroare cunoscută în 6.006, și anume că acest instructor are un scris de mână oribil. Lucrez la asta. Am fost la clasă și am exersat zilele trecute. Dar, între timp, există note oribile scrise de mână care sunt postate în modulul de învățare, cel puțin pe durata discuției de astăzi. Și vom decide dacă vrem să le lăsăm sau nu pentru că nu sunt super incitante. Doar ca să te asiguri că poți urma asta, scriu pe tablă. Și ca și înainte, dacă există vreodată ceva ce nu poți citi, oprește-mă. Și voi repara cu plăcere. Misto. Deci, așa că sperăm, toată lumea are o copie a problemelor? Va arăta puțin diferit de asta. Lucrurile verzi sunt răspunsurile. Eu le primesc, iar tu nu. Sau îmi pare rău, pun mereu această întrebare când predau și nu primești niciodată un răspuns. Nu are cineva o copie a problemelor și a sesiunii cu probleme? Fabulos. BINE. Dacă nu, există o grămadă de fișe aici sus. Aici, o să-ți iau unul. Da. Grozav. Așadar, scopul de bază al sesiunilor de probleme este să trecem peste o grămadă de exemple de probleme, care cred că sunt în mare parte ridicate din temele și examenele din anii trecuți, și să analizăm cum ne-am gândit la ele și o soluție sau cel puțin pur și simplu amabil. de schiță suficient încât să fim încrezători că puteți completa spațiile libere ale unei soluții, având în vedere timpul limitat pe care îl avem împreună. Dreapta. Și, desigur, una dintre plăcerile de a preda această sesiune problematică este că aceasta nu este în mod normal clasa pe care o predau. Deci, acestea sunt într-adevăr probleme pe care nu le-am văzut până acum. Și într-adevăr, aseară, în miezul nopții , m-am trezit și mi-am dat seama că răspunsul meu la ultima problemă era total greșit. Deci, dacă te simți așa uneori, sentimentul este reciproc. Deci, în orice caz, există patru probleme pe fișa dumneavoastră care, în general, cred că sunt în corespondență cu lucrurile pe care le-am predat în ultima săptămână sau cam asa ceva. Deci prima problemă implică recidive. Al doilea implică Infinity Stones. Al treilea implică un fel de structură de stivă de coadă. Iar al patrulea implică tot felul de lucruri care vorbesc între ele într-un mod în care am greșit. Deci, cred că, în lipsa unui lucru mai creativ, vom trece prin acești tipi în ordine. Și în esență, aceasta ar trebui să fie o sesiune interactivă, deși nu arată chiar așa. Dar din moment ce voi sunteți cei din cameră, aveți avantajul că mă puteți opri în clipa în care eu, A, greșesc sau, B, spun ceva care vă derutează. Și mă bazez pe tine pentru a face asta, bine? Dă din cap. Asta e afacerea noastră de azi. Un fel de recunoaștere. Se scoate nasul din laptopuri, poate, pentru o secundă. Misto. Mulțumesc. Vezi, degetul mare în sus. Asta caut. BINE. Bine, oameni buni. Corect, deci să începem cu problema numărul unu aici. Deci problema numărul unu este rezolvarea recurențelor, care este modalitatea noastră preferată de a tortura studenții la cursurile de algoritmi în primele două săptămâni. Și în special, aplicarea acestei teoreme magistrale. Așa că am crezut că am petrecut aproximativ 82 de secunde revizuind teorema principală, deoarece acesta este un fel de baros uriaș pentru rezolvarea recurențelor fără a înțelege de ce ai primit răspunsul pe care l-ai primit. Și apoi pentru fiecare dintre aceste probleme, în mod convenabil, această problemă a temei vă cere să faceți fiecare lucru mare O de două ori, nu? Odată ce ai folosit teorema principală pentru a te obișnui cu aplicarea acestui mic set de reguli, care este un fel de cea mai eficientă modalitate de a rezolva recurențe. Îți oferă doar o formulă la care să te uiți. În plus, desenați un arbore de calcul și numărați numărul de calcule pe care le faceți. Deci primele două sunt practic aplicații simple ale teoremei principale. Al treilea necesită puțină gândire. Așa că, firește, am rămas blocat și am pierdut o oră ieri încercând să mă conving că răspunsul a fost corect. BINE. Deci, pentru o mică recenzie, știu că ați făcut asta și în recitare. Dar nu poate strica să- l ridic din nou. Amintește-ți acea teoremă principală-- cred că „maestrul” este într-adevăr doar pentru că este general, nu? Nu există un tip numit Maestru, dar observ că a fost scris foarte mult în notele de curs. Dar, în orice caz, ideea de bază este că are o oarecare recurență care arată ca următorul, care este T din n egal cu aT din n/b plus f din n. Deci, de exemplu, în sortarea de îmbinare, pentru o mică analiză, amintiți-vă că ne-am împărțit în două părți. Deci, atât a cât și b în sortarea de îmbinare ar fi 2. Da. Și cantitatea de muncă pe care o fac în pasul de îmbinare este cam ca n. Așa e cum să completezi aceste constante diferite acolo. Și întrebarea este, asimptotic, cum arată această funcție? Și, desigur, nu este total evident din această formulă pentru că am definit T în termeni în sine, nu? Și asta e genul de parte enervantă a rezolvării recurențelor. Așadar, teorema principală și vă voi lăsa să vă revizuiți notele de secțiune despre cum se dovedește acest lucru, în esență împărțit în trei cazuri. Și numerele relevante de aici sunt următoarele, nu? Există un a, un b și un f. Și deci a este un fel ca un factor de ramificare, nu? Deci, dacă vă amintiți arborele de calcul, ca în sortarea de îmbinare, v-ați împărțit în două părți, nu? Deci acel număr este un fel de a. Este numărul de împărțiri pe care le faci, nu? b este cantitatea pe care dimensiunea problemei tale o reduce atunci când mergi la fiecare dintre acele frunze. Și apoi, în sfârșit, f este cantitatea de muncă pe care o faci la fiecare nod. Da, așa că sperăm că limbajul de bază are sens. Și, în esență, ceea ce înveți din teorema principală este că există trei cazuri. Primul este că f din n arată ca... apropo, în notele de recitare, dintr-un motiv oarecare, este scris oarecum invers. Ei dau răspunsul la teorema de master și apoi condiția. Am de gând să scriu în cealaltă ordine. Dreapta. Arată ca următorul, care este n față de baza logaritmică b a unui epsilon minus pentru un epsilon pozitiv. Voi încerca să fiu foarte conștiincios în a-mi citi scrisul cu voce tare în timp ce îl scriu. În regulă. Și în acest caz, ceea ce găsim este că observăm că există ceva un fel de magie aici, și anume că aceasta este doar o limită superioară. Nu există nicio teta aici. Deci este în regulă dacă f este sub acest lucru. Dar, în orice caz, concluzia este că T din n este mare teta a lui n față de baza logaritmică b a lui a. E cam misto dacă te gândești la asta. Aveți doar o limită superioară pentru f, dar obțineți o limită theta bună pentru T, ceea ce este destul de grozav. Motivul pentru aceasta este, în esență, f-ul este oarecum nesemnificativ în raport cu munca de a parcurge în sus și în jos copac. Acesta este cazul unu. Cazul doi -- Voi încerca să las acest lucru pe tablă, deoarece rezolvăm de fapt aceste probleme -- este următorul, care este f din n este teta mare a lui n la baza logaritmică b a înmulțită cu log la k-a putere a lui n. Aceasta este o formă super ciudată , dar, de exemplu, este perfect kosher să luați k egal cu 0, caz în care începe să arate ca primul caz, nu? Pentru unele k pozitive sau nenegative, mai degrabă, caz în care ceea ce învățăm este că T din n este theta lui n față de baza logaritmică b a unui ori log față de k plus 1 din n. Puteți vedea de ce nu ne place să aplicăm această teoremă în acest curs, deoarece simt că doar să mă uit la aceste formule este total neluminant. Dar este un baros uriaș pentru rezolvarea rapidă a recurențelor. Și apoi, în sfârșit, cazul trei-- Voi aluneca placa în sus și o voi aluneca înapoi în jos pentru că nu vreau să mă aplec. OK-- este următorul, care este f din n este omega, corect, ceea ce înseamnă că este limitat mai jos de n la baza logaritmică b a unui epsilon plus pentru un epsilon mai mare decât 0. Și aveam nevoie de un al doilea caz. Cum se numeste? af de n peste b este mai mic decât cfn pentru unele c între 0 și 1. Și care este concluzia acolo? Apoi se dovedește că un fel de termen f domină și ceea ce obținem este că T din n este theta pentru f din n. BINE. Deci, în esență, aceasta acoperă trei cazuri majore pe care le vedeți în recurențe. Există și alte versiuni mai generice ale teoremei principale unde, în esență, mai degrabă decât să aibă un singur termen cu T în el, poate folosiți mai mult de un termen cu un T în el. Nu cred că acestea sunt acoperite în această clasă. Întotdeauna încurc numele celui mai general. Vreau să spun că este Arzela-Ascoli, dar știu că asta e din analiză funcțională. Teorema [INAUDIBILĂ], dacă doriți să căutați asta pe Google, aflați mai multe. Dar, în orice caz, asta va fi suficient pentru majoritatea recurențelor la care ne pasă în 006. Așa că cel puțin am notat condițiile noastre. Și acum vor sta în partea stângă, în timp ce facem trei exemple de probleme pentru a arăta cum apar în practică. Există întrebări despre ceea ce ne spune această teoremă despre viață sau cum să o aplicăm? Nu vorbiți toți deodată acum. Da. PUBLIC: Îmi pare rău, am o întrebare despre scris de mână. PROFESORUL: Nicio problemă. PUBLIC: Ce urmează după „unii”, ultimul rând? PROFESORUL: Oh, pentru niște c în 0, 1, nu inclusiv. Intrebare fabuloasa. Oricare altii? BINE. Deci, hai să facem un exemplu de problemă aici. Deci să facem partea a. Deci, în partea a, vă oferă o recurență, care nu este deloc diferită de sortarea de îmbinare sau de oricare dintre celelalte. Arata cam asa . T din n este egal cu 2T din n/2 plus-- și apoi au un alt termen, despre care nu vă spun nimic dincolo de faptul că este O mare de rădăcină pătrată a lui n. Apropo, asta ar putea însemna că de fapt comanda 1 funcționează, nu? Trebuie doar să fie mărginită superioară de o rădăcină pătrată a lui n. Acesta este singurul lucru care îți spune problema. Voi continua să conduc acasă în acel punct, deoarece cred că toată lumea, inclusiv eu, devine foarte neglijentă, cum ar fi, când este O? Când este theta? Când este omega? Și așa că de fiecare dată când scrii una dintre acele scrisori , ar trebui să te dai înapoi 50 de picioare și să te uiți la ea și să te gândești, cum ar fi, am făcut asta corect? Sau am scris doar o scrisoare grecească, nu? Și asigură-te că te gândești la asta logic. BINE. Deci, când aplic teorema principală în viața mea de zi cu zi, ceea ce îmi place să fac este să spun, OK, cumva, cantitatea cu adevărat cheie în teorema principală este acest tip, corect, n la baza logaritmică b a lui a. El continuă să apară în toate aceste cazuri diferite. Așa că aș putea la fel de bine să-mi dau seama ce este pentru recurența mea, da, și apoi să-l conectez și să verific în ce caz mă aflu. Are sens? Deci hai să facem asta. Deci, în primul rând, ce este pentru această recidivă anume? PUBLIC: 2. PROFESOR: 2. Ce este b? Mă omori, băieți. Pe 3. 1, 2, 3. PUBLIC: 2. PROFESOR: OK. Entuziasmul este copleșitor. OK, și ce știm despre funcția f? PUBLIC: [INAUDIBIL] PROFESOR: Da, este O mare a rădăcinii n. Nu știm că este egal cu rădăcina n. Dar știm că este cel mult mărginit de ceva care seamănă cu rădăcina n. Eric mi-a dat o lecție întreagă despre această cretă și încă nu reușesc. BINE. Deci, asta ne oferă tot ce avem nevoie pentru a calcula n la baza logaritmică b a lui a. O vom face pe aceasta foarte încet, iar apoi o vom face pe următoarea puțin mai repede, mai repede. Deci n la baza logaritmică b a lui a. Ei bine, asta este n pentru baza logaritmică 2 din 2. Are cineva o idee? Care este baza logaritmică 2 din 2? PUBLIC: 1. PROFESOR: 1. OK, voi accepta de data asta. BINE. Dreapta. Și atunci, ce vă spune teorema magistrală? Ei bine, într-un anumit sens, vreau să știu ce este f, care în acest caz arată ca rădăcina pătrată a lui n, în comparație cu ceea ce este acesta, n cu primul. Da? Acum, în primul rând, care dintre aceste două lucruri crește mai repede? Tipul ăsta, nu? Deci ceea ce știm este că f este într-adevăr mărginit superior de acest n aici. „Margini superioare” nu este chiar termenul potrivit, deoarece O mare permite un anumit spațiu de mișcare, dar asimptotic. Sper că voi înțelegeți acest concept. OK, deci în special, să vedem. Așa că amintiți-vă că f of-- să-l scriem din nou. Deci f din n este O mare al rădăcinii pătrate a lui n. Dar să scriem asta într-un mod sugestiv ca n la 1/2. Da. În special, aceasta este egală cu O mare a lui n cu 1 minus 1/2. Este lucrul frumos despre 1/2. Da. Dar ce este n la 1? Ei bine, acesta este n pentru baza logaritmică b a lui a, nu? Asta tocmai am arătat aici, nu? Deci, acesta este într-adevăr O din n la log b al lui a-- acesta este un mod complicat de a scrie numărul 1, dreapta-- minus 1/2. Să dăm și jumătate un nume special, în timp ce suntem la asta. Să-i spunem epsilon sau ea, da, unde luăm epsilon equals... vezi ce am făcut acolo? Acum, ce îmi spune? Există trei cazuri diferite de teoremă principală. Și uită-te la ceea ce tocmai am arătat. Am arătat că f din n este egal cu O mare a lui n cu baza logaritmică b a unui epsilon minus pentru un epsilon care este egal cu 1/2. Lucrul frumos despre 1/2 este că este mai mare decât 0. Da. Așa că cred că am verificat oarecum laborios că suntem într-un caz. Vreun dizidenți aici? Fabulos. BINE. Deci, în acest caz, teorema principală, practic, tocmai ai terminat, nu? Deci care este concluzia? PUBLIC: T din n este theta din n. PROFESORUL: Exact. Deci T din n este teta lui n față de baza logaritmică b a lui a. Dar am arătat deja că este egal cu n. Deci am terminat. În regulă. Aveți întrebări despre cum aplicăm teorema principală aici? BINE. Așa că acum iată treaba cu teorema principală. Am învățat ceva despre ceea ce face această funcție recursivă ? Nu, tocmai am făcut o grămadă de muncă, am introdus câteva simboluri grecești și a ieșit o mare teta. Da. Deci, ceea ce am putea dori să facem în schimb este să folosim o metodă pe care încă o învăț eu însumi, pentru că nu sunt obișnuit să o prezint în acest fel, dar este în regulă, și anume să desenăm arborele de calcul. Da. Deci, să facem asta de fapt. Deci, să presupunem că îmi numesc funcția T de n. Deci, ce face T din n? Ei bine, într-un anumit sens, funcționează așa cum arată ca rădăcina pătrată a lui n, corect, și apoi face două apeluri de funcție, fiecare dintre ele având n/2 cantitate de date. Da. Deci, să desenăm cum arată asta. Deci, primul lucru pe care l- ar putea face funcția mea este să lucreze rădăcina pătrată a lui n mult. Vom pune o mică rădăcină pătrată a lui n acolo. Și acum face două apeluri de funcție. Și câtă muncă lucrează fiecare dintre acești tipi? Deci, când se numește T, ce se întâmplă în T? n/2. PUBLIC: Deci rădăcină pătrată a lui n/2. PROFESORUL: Exact. Deci efectuează rădăcina pătrată a n/2 cantități de lucru la fiecare dintre aceste două noduri. Asta are sens? PUBLIC: Asta este determinat de numărul de ramificare, nu? PROFESORUL: Trebuie să fii atent. Deci numărul de ramificare, în acest caz, sa întâmplat să fie același. Următoarea problemă pe care o facem, vor fi diferite. Deci sunt amândoi 2 aici. Exteriorul 2 se referă la faptul că sunt doi copii. PUBLIC: Da, nu contează. PROFESOR: Și în interiorul 2 se referă la faptul că am împărțit la 2. Este o întrebare fabuloasă pentru că este exact ce am greșit când am făcut această problemă. BINE. Așa că acum fiecare dintre acești tipi își cheamă unul dintre copiii lor. Da. Și din nou, datele se împart la 2. Deci acum am rădăcina pătrată a lui n/4, așa. Da. Dacă vă întrebați, în interiorul fiecăruia dintre aceste cercuri, scrie rădăcina pătrată a lui n/4. BINE. Deci, să spunem că - deci acum, între timp, în arborele nostru de apeluri de funcții de aici, câte noduri sunt doar în primul nivel, în partea de sus? Unul, nu? Doar tipul ăsta. Da. Un singur nod. Câte noduri sunt în al doilea nivel? Două. Sau dacă vrem, 2 la 1 noduri. Aici, sunt patru, da, care sunt 2 noduri pătrate și așa mai departe. BINE. Deci acum avem o reprezentare picturală a ceea ce se întâmplă în interiorul recurenței noastre. Dacă te uiți la notele de curs pe care le-am scris, am mai scris un strat doar pentru distracție și profit. Deci acum să vedem cum ne ajută acest lucru să ne rezolvăm de fapt recurența. Deci ce știm? Câte niveluri sunt în acest arbore? Ei bine, algoritmul nostru se oprește când intrarea în T arată ca 1, nu? Deci, deoarece aceasta se împarte la 2 de fiecare dată, arborele are baza logaritmică 2 de n niveluri în arbore. Da. Și cât de mult funcționează fiecare nivel? Asa ca fii atent. Deci fiecare nivel... să-i numim acel nivel l, nu? Deci vom spune că l este egal cu 0, l este egal cu 1 și așa mai departe. Deci sunt două lucruri diferite de care trebuie să luăm în considerare atunci când luăm în considerare munca la acest nivel. Unul este rădăcina pătrată a lui n/2 într-un singur nod. Și celălalt este faptul că există două noduri diferite în nivel. Deci, la nivelul l, deci cantitatea de muncă din nivelul l este egală cu produsul acestor două lucruri. Deci câte noduri sunt la nivelul l? 2 la l, da? BINE. Și câtă muncă face fiecare dintre aceste noduri? Este ca n/2 față de l. Deci, un mod diferit de a scrie, care este rădăcina pătrată a lui n ori 2 la minus l, așa. Acesta este doar n/2 față de l. Fabulos. Așa că acum avem tot ce ne trebuie pentru a găsi cu adevărat soluția noastră la recurență. BINE. Da? PUBLIC: Ce spune asta? PROFESOR: Acesta este de n ori 2 la minus l. Apreciez [INAUDIBIL]. Voi lucra mai mult la asta. Și de aceea îl distribui și online. Notele scrise de mână sunt... aceasta este literalmente o scanare a paginii pe care o țin în fața mea. BINE. Deci, dacă vrem cantitatea totală de muncă din arborele nostru, corect, dacă vrem să luăm în considerare tot T din n, atunci ce vom face? Ei bine, trebuie să însumăm începând de la nivelul 0. Folosesc l în loc de i pentru că sunt o persoană de analiză și i este rădăcina pătrată a minusului 1. Și nu îmi place i în algoritmi mei. Dar, în orice caz, câte niveluri totale există în arborele meu? Ei bine, știm că există baza logaritmică 2 a lui n, nu? Și acum trebuie să însumăm această cantitate pentru toate acele niveluri. 2 la l, rădăcina pătrată de n ori 2 la minus l, așa. BINE. Și apoi, ce știm în secret din teorema principală este că bănuim că acesta va fi theta lui n, nu? Deci asta e tot ce avem de verificat. OK, deci hai să facem asta foarte repede. Deci, în primul rând, observați că acest n termen nu depinde de sumand. Deci pot să le scot, nu? Deci aceasta este într-adevăr rădăcina pătrată a lui n ori suma peste l este egală cu 0 cu log 2 din n a ce? Ah, și există o greșeală în notele mele. Oh omule. Oh, nu, acesta este... PUBLIC: [INAUDIBIL] PROFESORUL: Oh, corect, duh. BINE. Deci aveți 2 la l și aveți o rădăcină pătrată de 2 la minus l. Deci, acesta este într-adevăr 2 la minus l/2. Deci ai l minus l/2. Și această cantitate este într-adevăr 2 la l/2, așa. Are sens? Deci acestea sunt doar proprietăți ale exponenților din clasa de liceu. Și de fapt, nu-mi place asta pentru că este l/2 și vreau să aplic orbește o formulă fără să mă gândesc la asta. Și, desigur, aceasta este într-adevăr aceeași cu rădăcina pătrată a lui 2 la puterea l-a. Acestea sunt doar proprietățile exponenților. BINE. Deci, cum se numește această sumă? Recunoști asta? Deci există o constantă aici. O duci la a-a putere și apoi o însumezi peste cea a lui. Aceasta se numește o serie geometrică, nu? Deci ar fi ca 1 plus x plus x pătrat plus x la al treilea și punct punct punct, x la, cred că în acest caz, baza logaritmică 2 a lui n. Da? În mod convenabil, există o formulă de serie geometrică . Am notat-o ​​în notele scrise de mână, dar poate deocamdată, pentru că mă mișc încet ca întotdeauna, așa că vom sări peste acea parte. Și ceea ce ați putea este după cum urmează, că aceasta este rădăcina pătrată a lui n, corect -- asta este doar această parte exterioară -- ori -- iar interiorul va obține rădăcina pătrată a lui 2 la baza logaritmică 2 a lui n plus 1 minus 1 împărțit la rădăcina pătrată a lui 2 minus 1. Și aceasta este formula seriei geometrice. Așa că vă încurajez să vă întoarceți acasă și să căutați pe Google pe acesta dacă ați uitat. Da. PUBLIC: Stai, de ce calculăm suma seriei? PROFESORUL: Pentru că ceea ce încercăm să facem este să aflăm cantitatea totală de muncă din acest arbore, nu? Deci, ceea ce am făcut până acum, știm că un singur nivel din acest arbore este această valoare. Și acum trebuie să însumăm toate nivelurile de la 0 la baza logaritmică 2 a lui n. PUBLIC: OK, și pentru ce folosim acest număr? PROFESORUL: Pentru că încercăm să aproximăm sau măcar să legăm T din n, nu? Și T din n este suma tuturor acestor valori. PUBLIC: Oh, bine. Și theta lui n nu este o limită suficientă. PROFESORUL: Este o legătură suficientă. Am primit-o dintr- un mod cam plictisitor. Acesta este un al doilea mod prin care am fi putut demonstra aceeași formulă. PUBLIC: Oh, bine. PROFESORUL: Da. Văd o întrebare aici. PUBLIC: Puteți trece peste rădăcina n, 2 minus l? Înțeleg că de la 2 la l este numărul de noduri a doua parte. Functioneaza? PROFESORUL: Oh. OK, acesta este numărul de noduri. Aceasta este cantitatea din interiorul cercului. Deci, observați că este rădăcina pătrată a lui n și apoi rădăcina pătrată a lui n/2 și apoi rădăcina pătrată a lui n/4 și apoi rădăcina pătrată a lui n/8, nu? Deci 2 la minus l aici este ca 1/2 și apoi 1/4 și apoi 1/8. Da. Fabulos. Alte intrebari? Da. PUBLIC: Deci, dacă avem niveluri de bază log 2n și am început indexarea la 0, nu se trece de la l egal 0 la l egal cu 2n minus 1? PROFESORUL: Oh, băiete. Sunt prost la chestiile astea. Fara drept? Cred că acest lucru este corect. Să vedem. Deci, să presupunem că am n egal cu 2, nu? Atunci ce se va întâmpla? Da, nu, este corect. Așadar, ca o verificare a minții, gândiți-vă la n egal cu 2. Deci câte niveluri ar trebui să fie? Ar trebui să treacă de la l egal cu 0 și apoi l egal cu 1. Apoi am terminat pentru că am T. Și apoi cred că-- da, deci baza logaritmică 2 din 2 este 1. Deci, da, această formulă se verifică. OK, alte întrebări? Toate acestea sunt întrebări grozave. Băieți, mă mențineți sincer. BINE. Deci avem această expresie urâtă uriașă aici. Așadar, ultima noastră sarcină aici este doar să o simplificăm. Asta este. Și apoi ceea ce vom descoperi este că acesta este în secret doar theta lui n. Puțin surprinzător, având în vedere că asta e cam urât. BINE. Și apropo, acestea au fost doar constantele. Deci acest termen de pe numitor nu va ajunge să conteze pentru calculul nostru asimptotic. BINE. Misto. Deci haideți să vedem aici. Deci, amintiți-vă că rădăcina pătrată a lui 2 este de la 2 la 1/2. Da. Așa că pot face un pic de remaniere a formulei noastre. Și ceea ce voi găsi este că aceasta este exact rădăcina pătrată a lui n ori 1 peste rădăcina pătrată a lui 2 minus 1. Aceasta este doar această constantă aici. Acum trebuie doar să fac față acestui termen amuzant aici. Am de gând să fac următoarele. O să spun, ei bine, rădăcina pătrată a lui 2 este aceeași cu 2 la 1/2. Așa că o să scriu asta mutând acea jumătate la etaj aici, nu? Deci, ce voi obține la sfârșitul zilei este că acesta este același cu 2 la baza logaritmică 2 a lui n plus 1 și toate astea-- hopa, plus 1/2, corect, pentru că există 1/ 2 exponent care a fost înmulțit cu 1-- minus 1. Deci aceasta este doar o expresie identică cu aceasta. Tot ce am făcut a fost să mut 1/2 la etaj. Și în sfârșit, acum există o anumită ordine în univers, pentru că cât este 2 la baza logaritmică 2 a lui n? PUBLIC: n. PROFESOR: n, exact. Acesta este un mod foarte complicat de a scrie n. Deci, aceasta este egală cu rădăcina pătrată a lui n ori 1 peste rădăcina pătrată a lui 2 minus 1, care este doar o constantă. Văd mâna ta. Am de gând să scriu și apoi te voi ajunge din urmă. Și acum toată această cantitate este de n ori rădăcina pătrată a lui 2, nu? Hopa, așteaptă. PUBLIC: [INAUDIBIL] PROFESOR: Oh, îmi pare rău. Ar trebui să fie... corect, pentru că am mutat 1/2 în exponent și nu am luat în calcul. Deci aceasta este rădăcina pătrată a lui n înmulțită cu rădăcina pătrată a lui 2. PUBLIC: [INAUDIBIL] PROFESOR: Ce este asta? PUBLIC: Ar fi n/2 la rădăcina pătrată a lui n. PROFESOR: n/2 la rădăcina pătrată a lui n. Nu, cred că este corect. PUBLIC: Oh, scuze. PROFESORUL: Da. Băieți, mă faceți nervos. OK, așa că în sfârșit, acum putem începe să vedem că marele O iese, nu? Pentru că acum avem rădăcina pătrată de n ori în sine plus alte lucruri, care, evident, vor crește mai lent decât termenii rămași aici. Deci suntem buni. Dacă vă întrebați, soluțiile oficiale sunt de fapt incorecte. Și ei înțeleg asta puțin greșit. O să repar asta în seara asta și apoi le vom posta pentru voi băieți. Și, din păcate, acesta este genul de lucru pe care îl faci foarte mult, în cazul în care îți vei duce copacul. Scrieți această formulă de copac uriaș aici. Scrieți o serie geometrică de un fel și apoi începeți să delimitați termenii până când ajungeți la expresia dorită. Deci acum puteți vedea de ce teorema magistrală poate este oarecum valoroasă, deoarece vă scutește de o mulțime de dureri de cap. Da. PUBLIC: Când ne scriem seturile de piese și trebuie să scriem astfel de copaci, putem să le desenăm manual și să facem poze? PROFESORUL: Da, nu văd de ce nu. Nu trebuie să- l deseneze în Dixie sau așa ceva. PUBLIC: Puteți face fotografii diagramelor atâta timp cât matematica nu [INAUDIBIL].. PROFESOR: Da. Cred că dacă doar îți scrii matematica, îi faci o fotografie și apoi, cum ar fi, bara oblică inversă include grafica fotografiei tale... da. Dar doar pentru cifră, cred că e în regulă. PUBLIC: [INAUDIBIL] PROFESOR: Da. De fapt, când scriu lucrări de cercetare, așa fac până la schița finală. Da. BINE. Deci, în esență, ce am făcut tocmai în această problemă, care face parte dintr-o singură problemă, este în esență arătat două moduri diferite de a rezolva recurența, nu? Unul este barosul care este foarte eficient, dar nu foarte ilustrativ. Celălalt este într-adevăr să elaboreze toată munca care se întâmplă la fiecare nivel al arborelui nostru, să facă o sumă uriașă și apoi să obțină de fapt formula potrivită. Și ambele sunt doar moduri diferite de a jupui aceeași pisică. Este o frază ciudată? Nu știu. BINE. Așa corect, așa că de fapt, partea a doua, cred, ajunge să fie mai ușoară printr-o întâmplare amuzantă, deși pare că este mai greu. Deci hai să facem asta mai departe aici. Deci, voi lăsa teorema principală în partea stângă. Chiar vreau să spun „teorema maestrului”, dar cred că nu este corect. Voi lăsa teorema principală în partea stângă. Doar faceți problema aici. O voi face pe asta puțin mai repede pentru că prefer să nu petrec întreaga sesiune cu o singură problemă. BINE. Dar cred că merită să petreci câteva minute să treci peste această teoremă și cum să o aplici cu atenție, pentru că, ei bine, altfel, nu o vei face. BINE. Bine, oameni buni. Este un antrenament aici sus. Deci, în partea b, avem o versiune în care factorul de ramificare și cantitatea pe care o reduce munca nu sunt aceleași. Deci acum trebuie să fim puțin mai atenți în modul în care aplicăm teorema principală, nu? Deci, acum, în partea b, avem că T din n aici este egal cu 8T din n/4 plus-- și acum în problemă, ei scriu O mare de n ori rădăcina pătrată a lui n. Suntem toți adulți aici. Este la fel ca O mare a lui n la 3/2. Da. Asta e doar aritmetică. BINE. Deci, mai întâi, să aplicăm teorema principală. Să vedem. Deci, ce este n față de baza logaritmică b a lui a, în acest caz? Ei bine, ce este b? 4. Ce este un? 8. Știe cineva baza logaritmică 4 din 8? PUBLIC: 3/2. PROFESORUL: Uau, ești bun. Da, deci acesta este egal cu n cu 3/2. Și observați că aceste două lucruri sunt de acord acum. Da. Deci, în care dintre cele trei cazuri ale teoremei principale ne aflăm? Suntem în primul, unde unul din acest fel de pitici celălalt? Nu. Suntem în cazul doi, corect, unde amândoi se comportă în mod similar. Da. Deci acesta este cazul doi. Și care este valoarea lui k pentru cazul doi care este relevantă aici? Am nevoie de un factor de logare? Nu, acești doi termeni sunt la fel, nu? Ambele sunt n la 3/2. Deci, acesta este cazul doi cu k este egal cu 0. Și în special, imediat, obținem că T din n este -- să vedem. Suntem în cazul doi, deci avem teta lui n la baza logaritmică b a unui log de ori la k plus 1 a lui n. Deci trebuie să luați în considerare termenul respectiv, așa că este. Are sens, cum am aplicat teorema principală în acest caz? Da. PUBLIC: Deci, cum putem aplica cazul doi dacă este mare O și nu teta mare? PROFESORUL: Cum putem aplica cazul doi dacă f din n este O mare și nu teta mare? Ei bine, asta vine de la un student absolvent. Așadar, de ce nu le trimit înapoi studenților din clasă în loc să-mi răspund singur? PUBLIC: Puteți repeta întrebarea? PROFESORUL: Sigur. Deci, să spunem că avem doar un O mare. Nu avem o teta mare aici. Sau cel puțin un răspuns simplu, care poate este cel pe care îl cauți. Deci ce știm? În acest caz, știm că f din n ar putea crește mai lent decât această funcție. Dar nu crește mai repede decât chestia asta. Da. PUBLIC: T din n ar fi doar O mare în loc de teta mare? PROFESORUL: Exact așa este. Așa că poți înlocui teta mare cu O mare, și asta e perfect. Deci nu știu dacă acesta este răspunsul pe care îl cauți. Dar măcar vei obține o legătură liberă în acest fel. Da. PUBLIC: Probabil că ar trebui să scrieți O mare în răspuns atunci. PROFESORUL: Hopa. Oh, îmi pare rău. Înțeleg. Suntem pedanți. BINE. Îmi poți spune doar dacă am greșit. S-a întâmplat. Cred că este corect în notele mele. Este. BINE. Deci, motivul pentru care colegul nostru o aduce în spate este că am făcut o ușoară greșeală, și anume că acesta este un O mare, nu o teta mare, nu? În acest caz, singurul lucru pe care îl pot desena aici este că acesta este și un O mare. Așa că am făcut exact greșeala pe care v- am spus să o evitați înainte. Da. PUBLIC: Deci acolo, ar fi și aceia O mare? PROFESORUL: Nu. Da, acum am reușit să vă încurc. Asta e corect. Toată această afirmație a teoremei principale, presupunând că am copiat-o corect, este corectă. Dar este o mică diferență. Amintiți-vă, am vrut să aplicăm cazul doi. Și uită-te la cazul doi. Deci există o teta aici. Dar în problemă, în problema temelor, au fost smecheri. Și au spus doar că f din T este O mare a ceva. Deci, amintiți-vă, care este diferența dintre marele O și marele theta? Ei bine, intuitiv, marele theta spune că funcția mea chiar arată ca tipul ăsta. Cumva, este delimitat deasupra și dedesubt, pe măsură ce merg suficient de departe. În O mare, există doar o limită deasupra, nu? Deci asta este cumva mai liber. Și astfel, modalitatea de a aplica teorema principală în acest caz este să spunem, ei bine, cel puțin f din n este mărginit superior. Arata cam asa . Deci, cel mai bun lucru pe care îl pot face este să-l înlocuiesc pe acest tip și cu o limită superioară. Da. E o întrebare grozavă. PUBLIC: Deci motivul pentru care ați ales două este că construcția [INAUDIBILĂ] a matematicii este similară cu [INAUDIBILĂ]? PROFESORUL: Exact. Trebuie să stai pe spate și să-ți miști puțin ochii, să te asiguri că se potrivește. Dar cu siguranță, este cazul că celelalte două părți ale acestei teoreme nu se aplică. Deci am putea încerca la fel de bine să stoarcem această parte în forma potrivită. În regulă. Deci, să facem versiunea arborescentă a acestui lucru. Și apoi cred că ceea ce vom face este să omitem partea a treia pentru moment a acestei probleme, deoarece este mai degrabă un tip distractiv de problemă vectorială, mai degrabă decât ceva care de fapt va ajuta la înțelegerea algoritmilor. Și apoi, dacă avem timp la sfârșit, vom reveni la asta. BINE. În regulă. Așa că acesta a fost modalitatea ușoară de a rezolva problema. Acum să o facem pe cea dureroasă unde desenăm copacul. Nu ar trebui să spun asta pentru că cred că este ceva pe care vrem să-l încurajăm... versiunea mai iluminatoare, da? Așa că acum, în vârful copacului meu, fac treaba 3/2. Și acum câți copii are tipul ăsta? PUBLIC: [INAUDIBIL] PROFESOR: Atenție. Ai 1 din 2 sanse, fie 8, fie 4. 8, nu? Deci coeficientul exterior este numărul de copii pentru că este ca și numărul de apeluri de funcții pe care le faci, nu? Acesta este modul de a gândi, nu? Deci sunt opt ​​dintre acești tipi. BINE. Și fiecare dintre acești tipi... Voi face doar un nivel din acestea. Stai, nu ar trebui să fie conectat -- cât de mult funcționează? Ei bine, amintiți-vă că aici este împărțit la 4, nu? Deci arată ca n/4 față de 3/2. Are sens, cum am obținut această imagine din recurența noastră? Lasă-mă să trec la o altă bucată de cretă. BINE. Dreapta. Deci, cu alte cuvinte, dacă mă uit la nivelul l al arborelui meu, presupunând că vom indexa de la 0 în partea de sus, câte noduri sunt în nivelul l? Amintiți-vă, se ramifică cu 8 de fiecare dată. Deci are 8 la nodurile l. Da. Și câtă muncă face fiecare? Ei bine, la fiecare nivel, împart la 4, nu? Deci, acesta va arăta ca de n ori 1/4 la l la 3/2. Dreapta. Unde sunt? Iată-ne. Deci este de n ori 4 la minus l. Aceasta este o notație fantastică pentru 1/4 la l la 3/2. Observați că acesta este exact același model ca problema anterioară. Doar conectez niște constante diferite. Da. PUBLIC: Am o întrebare despre diagramă. Dacă aveți un a cu adevărat mare și încercați să faceți metoda arborelui recursiv, acest tip de lucru este în regulă în cazul în care aveți... PROFESOR: Dacă v-aș nota lucrările, ar fi. Dar probabil că ar trebui să verificați cu AT-urile de pe Piazza despre asta. PUBLIC: Bine. PROFESORUL: Dar mi-am învățat licența. Nu sunt sigur că voi ați făcut-o încă. Și, de asemenea, nu sunt sigur că am. Bine, oameni buni. Deci acum trebuie să ne facem toată munca aici, nu? Deci câte niveluri sunt aici în arborele nostru? Ei bine, cantitatea de date se împarte la 4 de fiecare dată. Și când cantitatea de date este 1, atunci am terminat, nu? Deci numărul total de niveluri este egal cu baza logaritmică 4 a lui n. Lucrul de bază pentru a fi corect în această problemă este exact unde ar trebui să fie 4 și unde ar trebui să fie 8. BINE. Deci acum ce am de gând să fac? Ei bine, din nou, așa cum subliniază colegul nostru din spate, avem doar O mare. Așa că ne putem limita munca doar de sus. Dar munca noastră în arbore este mai mică sau egală cu... într-adevăr, există o proporție aici, deoarece aceasta este doar până la un multiplu. Bănuiesc că de aceea, în note, au pus un mic c în față, ceea ce pot face. Hai să facem c așa. Ei bine, vom avea suma de la l egală cu 0 până la baza logaritmică 4 a lui n exact a cantității, tipul ăsta. Înmulțiți-l cu numărul de noduri din rând. Da. PUBLIC: Este motivul pentru care ați făcut din această funcționare o inegalitate din cauza... PROFESORUL: Din cauza lui mare O. Este exact. Da. BINE. În regulă. Deci ce primesc aici? Ei bine, haideți să scriem mai întâi pe calea urâtă. Deci, acesta este de n ori 4 față de minus l. Aceasta este la 3/2. Și apoi aceasta este înmulțită cu 8 la l. Dar cine a creat această problemă a fost într-adevăr smecher, nu? Deci, cât este 4 la minus l la 3/2? Orice presupuneri? PUBLIC: 8 la minus l. PROFESORUL: Da, acesta este exact 8 la minus l dacă lucrăm prin toată aritmetica exponenților dumneavoastră. Da. De ce contează asta? Ei bine, anulează exact acest termen 8 la l aici. Acesta este de fapt exact cazul doi din teorema principală încearcă să surprindă. Deci toată chestia asta este egală cu, într-adevăr, doar n la 3/2 de la l este egal cu 0 la baza logaritmică 4 a lui n. Toate aceste constante dispar. Nu e frumos? Da. PUBLIC: Întrebare rapidă despre copac din nou. PROFESORUL: Nicio problemă. Uh-huh. PUBLIC: Deci oamenii le folosesc vreodată pentru optimizare în ceea ce privește încercarea de a scrie un algoritm mai bun, încercând să minimizeze munca pe nivel? Da, sunt doar curios dacă este o aplicație care... PROFESORUL: Sigur, cred că da. Adică, aceasta este cumva o vizualizare a modului în care algoritmul tău face costuri pentru funcții, nu? Deci, fiecare nod de aici arată ca un apel la fragmentul tău de cod. Deci, de fiecare dată când faci unul nou, este ca și cum ai efectua un apel. Și apoi diviziunea aici este un fel de cantitatea de date care intră în acel apel de funcție. Deci, cred că aceasta este o modalitate utilă de a vizualiza ce se întâmplă în interiorul codului tău. Și apoi, dacă încercați să vă optimizați codul, încercați să reduceți practic numărul de noduri și/sau cantitatea de muncă pe care o face fiecare nod, nu? Da. Deci, aceasta este doar o modalitate frumoasă de a vizualiza ce se întâmplă într-un algoritm recursiv. Da. Mare întrebare. În regulă. Deci iată un lucru foarte frumos. Depinde n la 3/2 de l? Fara drept? Deci toată chestia asta este egală cu c ori n cu 3/2. Și colegul meu din spate mă va prinde dacă nu fac aici eroarea de 1 off. Deci aceasta este baza logaritmică 4 din n plus 1, deoarece suma mea a început la 0. Da. Și observați că acesta este exact O mare de n la 3/2 log n, ceea ce este de acord cu ceea ce am făcut într-un caz mult mai ușor cu teorema principală. Are sens? Da. PUBLIC: Deci, dacă fac limita exactă, putem spune că este theta lui n la [INAUDIBIL]? PROFESORUL: O, grozavă întrebare. Aici această notație va fi înșelătoare. Această expresie în vid este teta a acestei valori. Dar motivul pentru care am scris O mare este pentru că am doar o inegalitate până aici. Deci, dacă sunt îngrijorat de limitarea acestei lucrări, nu există niciun motiv să scriu un theta acolo, deoarece îmi spune doar un fel de informație intermediară. Da. OK, fabulos. Deci da. PUBLIC: Contează baza busteanului? PROFESORUL: Contează baza busteanului? Ah. Aceasta este o formulă frumoasă aici. Deci, amintiți-vă că baza de log b a lui a este aceeași cu log a peste log b, dacă am înțeles bine. Da. Deci baza jurnalului atunci când vine vorba de O mare nu contează pentru că este un factor constant. Da. BINE. Deci aceasta este partea a doua a acestei probleme. Partea a treia este puțin enervantă, deoarece are două ramuri în ea. Am scris o soluție atentă. Nu aplică teorema principală pentru că este irelevantă, cel puțin versiunea pe care o cunoaștem în această clasă. Așa că vom sări peste asta pentru moment, pentru că nu cred că este îngrozitor de relevant pentru majoritatea algoritmilor pe care îi vom vedea în 6.006. Dar vom reveni la asta dacă avem timp. Da. PUBLIC: Putem face ca o limită inferioară și o limită superioară folosind teorema principală, știind că T de n/4 este mai mic decât T de n/3? PROFESORUL: Vă voi referi la soluții în loc să vorbesc despre această problemă chiar acum. Da. Bine, in regula. În regulă. Așa aplicați teorema principală, care este ușor dureroasă. Vestea bună este că restul acestui set de probleme, de fapt, consider că este mult mai ușor decât primul, motiv pentru care cred că este în regulă să petreci puțin timp în plus aici, deoarece cred că aceste lucruri sunt confuze pentru a fi corecte. Mai ales pentru mine, și sper că v-am transmis confuzia mea celorlalți. BINE. Deci hai să ștergem asta. Și în timp ce facem asta, de ce nu citiți problema numărul doi? Deci, una dintre abilitățile mari pe care trebuie să le acoperim în 6.83-- nu 6.837, 6.006 și 6.837, dar nu sunt chiar la fel de rău în această clasă-- este următoarea, adică ați citit o problemă. Și din anumite motive, instructorii tăi au un simț al umorului bolnav. Și îl codifică în acest limbaj total ciudat și prost care, într-un fel, pentru un teoretician, face ca problema ta să pară mai practică. Deci, în orice caz, când citiți tot acest paragraf, prima abilitate pe care trebuie să o faceți este să vă dați seama, OK, ca aceasta este o notație drăguță și este vorba despre Infinity Stones. Și dacă mă uit la Războiul Stelelor sau orice altceva, aș ști ce înseamnă asta. Dar în orice caz, ceea ce contează cu adevărat este înțelegerea, OK, dar algoritmic, ce întreabă ei? Da. Așa că voi încerca să vorbesc despre această problemă în timp ce șterg placa. Așa că cred, ce, cum ar fi, Mickey Mouse sau orice are o grămadă, are o planetă pe care o caută. Am de gând să deschid problema acum. Corect, e o super ticălosă într-o căutare. Ea caută o piatră pe o planetă, iar planeta are un indice k. Și, din păcate pentru noi, numărul planetelor este destul de mare. Este infinit, de fapt, pentru că este Piatra Infinitului. Sau, scuze, am spus asta? Cred că e telefonul Infinity sau ceva de genul ăsta. Am uitat. Dar, în orice caz, singurul lucru pe care îl poți face când aterizezi pe o planetă este să întrebi un oracol, este indicele planetei mele mai mare sau mai mic decât indicele planetei pe care mă aflu, nu? Și atunci întrebarea este în log k timp unde k este indicele planetei. Observați că este deja puțin ciudat, deoarece nu este dimensiunea datelor dvs., chiar. Poți găsi planeta? Acum, ce înseamnă acest tip de problemă, cum ar fi, ce țipă pentru tine să folosești? Vedeți un jurnal k. Cauți ceva. PUBLIC: Bisecție. PROFESORUL: Bisectie, nu? PUBLIC: Căutare binară. PROFESORUL: Sau căutare binară. Este absolut corect. Acestea sunt ambele răspunsuri grozave. Dar există o mică problemă, și anume că numărul de planete este nelimitat. Nu știm câte planete sunt în acest mic univers pe care îl pune la cale problema 1.2. Da. Deci intuiția noastră este că vrem să folosim căutarea binară. Dar pentru a face căutare binară, trebuie să am o parte stângă și una dreaptă și să împart și nu am latura dreaptă. Deci ce pot face? Cum poate un supercriminal să rezolve această problemă? Ei bine, amintiți-vă că fiecare planetă are un oracol pe ea care îmi spune. E ceva în stânga sau în dreapta mea? Da. Așa că aș putea începe de la planeta numărul unu și aș putea să încep să merg de la planeta unu la planeta doi la planeta trei, planeta patru și să întreb, sunt deja acolo? Sunt încă acolo? Cât timp va dura? PUBLIC: Infinit, în cele din urmă. PROFESORUL: De fapt, nu va dura un timp infinit. Te-am prins. Cât timp va dura? Când mă voi opri? Când am lovit planeta k, corect, pentru că știu că planeta k este acolo undeva. Adevarul este acolo. Și când îl găsesc și îl calc, mă opresc. Și am făcut exact k pași, poate k minus 1, în funcție de cum numărați. Dar avem nevoie de un algoritm log k. Da. Deci ce pot face? PUBLIC: Începi de la un k, iar apoi dacă e în dreapta ta, înmulți cu un alt k? PROFESORUL: Înmulțiți cu încă k. PUBLIC: [INAUDIBIL] perceput în esență de alte k planete. Deci parcă ai fi la indicele k pătrat. PROFESORUL: Interesant. Hmm. PUBLIC: Nu ai putea trece de la i la i pătrat? PUBLIC: Da. PROFESORUL: Bine, deci ai avut dreptate... ești în biserica potrivită, banca greșită aici. Deci, intuiția de bază aici este că a păși câte o planetă nu calcă suficient de repede. Dacă descoperiți detaliile despre acesta, veți descoperi că veți ajunge cu un timp de execuție care merge încă puțin prea repede în k aici. Într-un anumit sens, dacă ar fi să faci o inginerie inversă a acestei probleme, care nu este cu adevărat o modalitate grozavă de a seta probleme, chiar te aștepți să existe puteri de 2 în fiecare pas al algoritmului tău. Da. PUBLIC: Ați putea să faceți căutarea binară și să începeți de la mijloc și apoi să întrebați oracolul dacă este mai mare sau mai jos și apoi [INAUDIBIL]? PROFESORUL: Este intuiția corectă. Dar am o întrebare filozofică pentru tine, care este, care este mijlocul unui set infinit de planete? PUBLIC: infinit. PROFESORUL: Infinit, exact. E o problemă. Da. PUBLIC: Ne-ar putea folosi... și nu știu cine a fost acolo în spate care a sugerat să se facă i pătrat -- cu excepția faptului că face i pătrat, înlocuiți-l cu 2 la i. PROFESORUL: Exact așa este. E o intuiție grozavă. Așa că haideți să oficializăm puțin, ceea ce înseamnă că aș putea face căutare binară dacă aș avea partea dreaptă. Am partea stângă pentru că este 1. Deci, ceea ce voi face, voi continua să încerc partea dreaptă. Și oracolul o să- mi spună, aceasta este o parte dreaptă validă, corect, pentru că oracolul îmi spune, este o planetă în stânga mea? Da. Deci iată ce am de gând să fac. Din nou, nu-mi place indexul i. În soluția oficială, există un i. Dar voi folosi litera m pentru că pot... care este următorul. Mă duc să vizitez... Urăsc să predau. Nu, nu este adevărat. Îmi place să predau. Pur și simplu nu-mi place creta. Voi vizita planeta 2 la m pentru fiecare m începând cu m egal cu 0 și, în esență, până când... amintiți-vă că k este indicele planetei pe care o caut. Deci, în cele din urmă, voi ajunge în punctul în care k este mai mic sau egal cu 2 cu m. Și știu că îmi pot interoga oracolul, iar ei îmi vor spune când va fi așa. Deci, cât timp durează asta? Așa că voi încerca planeta 1 și apoi planeta 2 și apoi planeta 4 și apoi 8 și 16 până la k. PUBLIC: Log k. PROFESORUL: Deci va dura log k timp. PUBLIC: Nu puteți avea și o limită mai puternică sau inferioară acum la m minus 1? PROFESORUL: Da, cam așa este . Corect, deci în cele din urmă, ceea ce se va întâmpla când te oprești aici este că 2 la m minus 1 va fi mai mic sau egal cu k. Acesta este egal cu 2 la m deoarece aceasta este condiția pentru oprire. Aceasta este o condiție pentru a nu opri. Deci, când te oprești pe k, acest mic sandviș este adevărat. Da. Deci, dacă iau jurnalul, în esență, ceea ce am arătat este că am luat, corect-- pentru că m este numărul de pași din această parte a algoritmului meu. Deci, dacă iau jurnalul, voi descoperi că am făcut log k pași. Da, dă din cap, recunoaștere. Da. BINE. Și apoi, ei bine, acum am o limită superioară și una inferioară. Deci acum ce pot face? PUBLIC: Căutare binară. PROFESORUL: Da. Acum pot căuta binară. Și asta necesită, de asemenea, log k timp. PUBLIC: Este de 2 ori log k [INAUDIBIL]? PROFESORUL: Exact așa este. Hopa! Deci acum am pasul doi este și căutare binară. Și este, de asemenea, un timp log k, iar problema noastră este rezolvată. Deci problema numărul doi nu este atât de grea. Sunt toți cu mine? Aveți întrebări despre asta? Asta e una rapidă. BINE. Acum, problema trei mi-a vorbit cu adevărat ca profesor de grafică pe computer . Dreapta. Deci acum conduc Fadobe. Colaborez foarte mult cu Fadobe Fresearch. Dreapta. Așa că Fadobe încearcă să creeze un program pentru editarea imaginilor. Și ce face software-ul meu ? Ei bine, imaginea mea, sau cred că documentul meu, constă dintr-o grămadă de imagini care sunt suprapuse una cu cealaltă. BINE. Și, în esență, ceea ce se întâmplă în interiorul software-ului este că vreau să păstrez toate imaginile în ordine de sus în jos, OK, pentru că atunci când îmi redau fotografia, ce fac? Îl redau pe cel de jos și apoi pe următorul și așa mai departe și doar le aranjez unul peste altul, ca și cum ați jucat vreodată cu PowerPoint sau Photoshop sau cred că orice nume fals îl dau aici. Aceasta este o interfață de utilizator destul de comună de întâlnit. Și, așadar, ceea ce ți-au cerut să faci este să vină, în esență, cu o structură de date. Și structura dvs. de date trebuie să suporte câteva operațiuni diferite. În special, trebuie să puteți face un document, să importați o imagine și apoi să o lipiți deasupra, afișare, care returnează toate ID-urile în ordinea în care le-ați stocat. Și apoi există adevăratul kicker, și anume că trebuie să poți lua unul dintre straturi și să-l lipesți sub altul. Dar trebuie să faci asta în log n time. Este acel „dar” care face ca toată această problemă să fie o durere în tuchus. Da. Dreapta. Deci, din nou, aici operațiunile noastre. Trebuie să facem un document gol. Aceasta ar trebui să preia comanda 1 dată. Vom importa, care adaugă un x deasupra și că acest lucru ar trebui să ia ordine n timp. Observați că acest lucru este deja puțin suspect. Dacă aș încerca să-mi diagnosticez profesorii din punct de vedere psihologic, m-aș uita la această ordine n cu niște... ca, cu o sprânceană ridicată, pentru că probabil ce ai avea în minte dacă vorbești despre teancuri de fotografii? Ar fi o stivă sau o coadă sau o structură de date ca asta. Dar apoi inserarea ar fi ca o comandă de 1 dată. Deci, în mod clar se întâmplă ceva puțin mai complicat . BINE. Ceea ce este numărul trei este afișajul. Acest lucru trebuie să se întâmple în ordinea n timp. Acesta are sens, corect, pentru că, pentru a afișa n lucruri, vă așteptați să aveți cel puțin n timp. Și apoi, în sfârșit, trebuie să ne mutăm mai jos. Și acest lucru trebuie să ia jurnalul de comenzi n timp. Și acesta va fi declanșatorul, corect, pentru că într- adevăr... acest lucru nu este cumva total evident din modul în care ne-am pus problema. Deci toată lumea înțelege configurarea problemei până acum? Continuăm să adăugăm obiecte cu ID-uri și trebuie să putem să le inserăm în partea de sus și apoi să le reordonăm. Și problema v-a oferit timp de rulare pentru fiecare dintre aceste operațiuni diferite. BINE. Dreapta. Deci iată chestia. Există un fel de aspect de secvență pentru problema noastră și un fel de aspect de set pentru problema noastră. Are sens? Aspectul secvenței problemei noastre este că va trebui să afișăm lucrurile în ordine de timp, nu? Trebuie să repetăm întreaga noastră listă, să punem lucruri deasupra și așa mai departe. Și aspectul setat este că ne-ar plăcea să mutăm lucrurile unul peste altul în timp de înregistrare. Și motivul pentru care spun că acesta este cumva aspectul setat este că trebuie să pot pune orice x sub orice y, ceea ce înseamnă că trebuie să pot găsi rapid în ce strat se află x și y. Orice idee cum putem rezolva aceasta problema? Ce zici de la niște oameni de la care nu am auzit încă? Da. PUBLIC: [INAUDIBIL] PROFESOR: Da, este o idee foarte grozavă. Așa că poate voi menține... deci amintiți-vă, am vorbit despre... să vedem. În prelegerea mea de acum două prelegeri, ne-am gândit la o listă sortată ca la o structură de date setată. Deci da, este o idee fabuloasă. De ce nu, pentru partea setată a problemei noastre -- vom stoca în special o matrice sortată de -- și, deocamdată, să ne gândim la asta ca la o matrice sortată de x-uri. Și astfel, acest lucru ne va putea ajuta să răspundem la întrebări precum, acest ID este în setul meu de imagini sau nu? Dar va exista și o a doua parte a problemei mele, care este în plus față de aceasta, trebuie să pot păstra o ordine diferită, în afară de a fi doar ordonată de x, care este ordinea în care sunt desenate pe ecran, nu? Este diferit de ordinea documentelor de identitate. Deci pentru asta... AUDIENTA: Întrebare rapidă. Vom construi o matrice sortată fără nimic în ea și va fi O de n log n timp. Dar asta e nedefinit. Deci putem construi o matrice sortată fără nimic în ea? PROFESORUL: Hmm. BINE. Nu, nu sunt sigur că o urmăresc. PUBLIC: Construiește o matrice sortată goală O de n log n timp, care este O de 0 log 0 timp. Și log 0 timp [INAUDIBLE]. PUBLIC: Matrice sortată goală? PROFESORUL: Da, construirea unui ceva gol care durează o dată. PUBLIC: Oh. PROFESORUL: Da. PUBLIC: OK, cool. PROFESORUL: Cool. În regulă. Deci, pe lângă aceasta, avem un aspect de secvență al problemei noastre. Și pentru asta, poate vom folosi o listă legată, nu? Aceasta este o structură de date secvență destul de rezonabilă. Și, de fapt, să ne gândim o secundă. Acum, vom avea nevoie de această mișcare de sub operațiune, nu? Deci, lista noastră legată va stoca ordinea imaginilor în documentul nostru. Pentru a muta ceva sub altceva, va trebui să îmbinam o imagine între alți doi tipi. Deci, pentru comoditate, poate avem o listă dublu legată, astfel încât să ne putem deplasa înapoi și înainte, astfel încât să putem introduce lucruri. Da. Deci vom avea o listă dublu legată. BINE. Dreapta. Deci, să începem să ne rezolvăm problema și apoi să ne gândim unde vor merge prost lucrurile cu configurarea noastră aici. Deci, în primul rând, nu cred că trebuie să scriem ceva pentru prima parte, deoarece a face un ceva gol este un algoritm destul de ușor. Pe teme, desigur, ar trebui să scrieți asta și să ne spuneți că este nevoie de o comandă. Acum, ce zici de importul unui obiect? Amintiți-vă, asta îl pune în partea de sus a listei noastre legate. Și trebuie să-l inserăm în matricea noastră sortată, nu? Deci, când facem asta, algoritmul nostru de inserare este super simplu, nu? Vom adăuga x la set, despre care am vorbit în clasă pentru o matrice sortată. Cât durează acest lucru pentru ca o matrice sortată să adauge ceva? PUBLIC: Comanda n timp. PROFESORUL: Exact, comanda n timp. Dar asta este de fapt în regulă pentru că acesta este criteriul nostru pentru numărul doi. Da. Și în plus , vom pune x în partea de sus a listei legate, nu? Aceasta este comanda de 1 dată. Asta e ușor. Adaug spațiu pentru că vom vedea că am făcut o ușoară greșeală și că va trebui să ne modificăm puțin algoritmul pentru a rezolva această problemă. OK, deci cum afișăm? Cred că este cel mai simplu, nu? Voi repeta întreaga listă legată și, unul câte unul, voi scoate ordinea pentru că, amintiți-vă, scopul listei legate este să țin evidența tuturor documentelor noastre în ordine. Așadar, afișați, tot ce trebuie să faceți este să treceți peste lista legată. BINE. Și adevăratul kicker este ultima parte, nu, care este cum muți ceva dedesubt? Deci hai să ne gândim un minut. Ce va presupune mutarea de mai jos ? Deci va afecta setul de chei care sunt în documentul meu? Nu, de fapt, nu? Doar le schimbă ordinea, dar ambele chei sunt deja acolo. Da. Deci singurul lucru pe care îl va face este să efectueze acolo unde sunt în secvență. Dar e ceva cu adevărat, foarte enervant. Cum găsesc ceva în această secvență? Să spunem că vă spun că documentul 75 trebuie să se deplaseze sub documentul 352. Ei bine, până acum în structura mea de date, care este singura mea opțiune? Îmi spune setul ceva despre unde se află lucrurile în lista legată? Nu. Deci cât timp îmi va lua să găsesc o cheie? PUBLIC: Ordinul nr. PROFESOR: Comanda n, corect, pentru că trebuie să parcurg toată această listă legată și să găsesc elementul care îmi lipsește. Este permis? Nu, problema îmi spune că trebuie să fac asta pentru a înregistra n timp. Deci, într-un fel, în mintea noastră, ar trebui să ne gândim, OK, ei bine, vrem să folosim acest set aici pentru a ne ajuta să găsim lucruri în lista dublu legată. Are sens, acea intuiție? Deci, iată cum o vom face. De fapt, înainte să fac asta, vreo idee? Cum putem rezolva asta? Da. PUBLIC: Poate [INAUDIBIL]. PROFESORUL: Este o idee fabuloasă. Deci iată ce am de gând să fac. Amintiți-vă că atunci când facem un set, nu trebuie doar să sortăm cheile. Putem atașa date la cheile noastre. Da. Și în special, voi atașa un indicator în lista mea legată . Răspuns cu adevărat furtun. Deci, să spunem că am... hai să facem un exemplu rapid. Deci, să presupunem că am documentele mele sunt 1, 5, 3, 2 și 7, așa. Deci lista mea legată va fi foarte simplă. Este dublu legat. Vezi, sunt două săgeți aici, exact așa, nu? Și acum matricea mea sortată va stoca toate cheile în ordine. Să vedem dacă pot face asta cu mine. 1, 2, 3, 5, 7, nu? Deci aceasta este lista mea legată. Și iată matricea mea sortată va fi 1, 2, 3, 5, 7. Dar apoi, ceea ce voi atașa fiecăruia dintre acești tipi este un pointer către elementul listei legate, nu? Deci, el va conține în plus o săgeată aici. Cele 2 vor conține o săgeată acolo. Cele 3 vor conține o săgeată acolo. Cei 5-- asta e urât, îmi pare rău. Acum, iată chestia. Să zicem că elimin acest 3 aici. Asta afectează de fapt indicatorul lui 7? Fara drept? Deci, aceste indicații rămân valabile chiar dacă editez alte părți ale listei. Truc cu adevărat furiș. BINE. Deci, aceasta va fi soluția noastră la această problemă este să stocăm nu doar matricea sortată de x-uri, ci și x-uri și pointeri. Deci acum trebuie să modificăm puțin, nu? Și acum ce putem face pentru a muta ceva dedesubt? Ei bine, se va întâmpla în trei pași, nu? Deci primul nostru pas, ei bine, trebuie să găsim mai întâi cheile x și y, nu? Deci vom găsi x, vx și y, vy în mulțime. Cât durează asta? Acum o putem face în căutare binară, nu? Exact. Deci acesta este O, așa. Și acum care este următorul meu pas? Ei bine, amintiți-vă, mutarea de sub operator elimină un fel de x de unde se află în prezent și apoi îl pune sub y, nu? Și ambele sunt ca operațiuni de editare a listelor legate, nu? Așa că voi cam... dacă am o listă legată, cum ar fi 1, 2, 3, 4, corect, și să zicem că vreau să șterg pe 2, cred că voi ați codificat asta la un moment dat. în viețile voastre. Atunci ce voi face este să adaug link-uri de genul ăsta, ceea ce pot face pentru că mă pot deplasa înainte și înapoi în listă, nu? Și, în mod similar, dacă vreau să adaug ceva, atunci voi șterge link-urile, le voi pune acolo și voi actualiza link-urile. Cât timp durează asta? Este doar o comandă , corect, pentru că acum că am indicatorii către aceste două locații, fac doar o mulțime de recablari în lista mea legată. Dar sunt tot felul de chestii locale. Dacă codificați în C, aici se întâmplă scurgerea de memorie și compania dvs. este piratată. BINE. Așa că asta vom face în continuare este să actualizăm lista legată. Și asta necesită o comandă. Pe teme, dacă scrieți răspunsul dvs., ar trebui să aveți un răspuns mai apropiat de ceea ce am scris pe pagina mea decât de cele două cuvinte pe care le-am scris pe tablă aici. Și apoi, în cele din urmă, la pasul trei-- ei bine, de fapt, nu există pasul trei pe care l-am scris aici. Îmi pare rău. Există de fapt două părți pentru actualizarea listei legate, nu? Una este să eliminați vechea poziție x și apoi să o introduceți în poziția corectă, nu? Și când fac asta, s-a produs întreaga mea actualizare. Observați că există ceva interesant în această mișcare de mai jos, și anume că am editat setul? Fara drept? Acest tip are sens, deoarece setul este doar un set de chei din documentul meu. Și doar prin modificarea comenzii, nu afectează ceea ce este în documentul meu. Deci, într-un fel, este o verificare a minții că asta funcționează. Deci, tot acest algoritm durează? Ei bine, există jurnalul de comenzi n. Există ordinea 1. Și există o altă ordine 1. Deci toată treaba este log n. Și viața este bună pentru problema noastră aici. Da. PUBLIC: Deci, cum putem pune astfel de indicii în viața reală? PROFESOR: Cum introducem un astfel de punct-- PUBLIC: [INAUDIBIL] ca un set cu indicatori în el în viața reală? PROFESORUL: Am înțeles. Deci știu doar versiunea C++ a acesteia. O să înțeleg greșit pentru Python. Dar nu sunt sigur că am înțeles bine întrebarea. Deci este la fel ca indicatorii oriunde altundeva în viața reală. Deci, cred că în Python, ceea ce veți face este să creați un nou, corect-- pe măsură ce adăugați acești tipi la setul dvs., veți crea un nou obiect aici. Și în plus , veți crea un nou vx pe care îl adăugați la lista legată. Și indicatorul este doar o adresă în memorie, nu? Deci, în esență, ceea ce veți stoca-- PUBLIC: [INAUDIBLE] nodurile listelor legate sunt indicatorii. PROFESORUL: Nodurile listei legate sunt perechi, o pereche de o valoare x și a-- ei bine, oh, îmi pare rău. Da, de fapt, cred că este corect. Nu. Lista legată conține doar o listă lungă de x-uri, nu? Dar nu trebuie să fie în memoria contiguă. Asta e singura diferenta. Așa că le creați câte un element de listă conectat o dată. Dar este ca și cum ai construi orice altă listă legată. Da. De fapt, există pseudocod în soluțiile care sunt distribuite. Deci poți arunca o privire acolo. Da. PUBLIC: Da, vorbind despre care, pentru implementarea acestor operațiuni de baze de date, putem pseudocoda algoritmii pentru ei? PROFESOR: Cred că răspunsul oficial este nu, că într-adevăr ar trebui să scrieți în cuvinte ceea ce face treaba dvs. Acum, există o zonă gri ciudată, desigur, și anume că cuvintele pe care le scrii vor arăta foarte mult ca pseudocod. Dar ar trebui să depui un efort să încerci să-l scrii puțin sub formă de paragraf, să fii descriptiv. Aceasta este o abilitate bună de învățat. La începutul acestui curs, cred că se va simți puțin pedant la anumite puncte. Și asta e bine pentru că ar trebui și ar trebui să te descurci cu asta. Da. Dar într-adevăr, încercați să scrieți lucrurile într-un mod care să surprindă logica dvs., mai degrabă decât doar codul Python. Da. Misto. În regulă. Deci, să vedem. Mai avem aproximativ 17 minute la clasă, adică aproximativ 1/8 din timpul necesar pentru a găsi soluția la această ultimă problemă a temelor. Dar vom începe. Și am scris un răspuns atent pentru că, în esență, în problema patru, m-am trezit blocat în câteva detalii. Și așa m-am gândit că modul în care scriu micul meu răspuns online la zgârietura de pui scris de mână a fost să vă ofer, practic, un dialog intern al creierului meu și cum am rezolvat aceste lucruri și toate pașii greșiți stupidi pe care le-am făcut. Da. Pentru că cred că asta este de fapt destul de valoros. În esență, deseori vezi în aceste sesiuni de probleme la fel ca, oh, iată o problemă. Iată răspunsul. Iată o problemă. Iată răspunsul. Dar realitatea este că chiar și profesorul tău, mai ales că s-a obișnuit să se gândească la randare, se confundă ocazional cu aceste probleme de algoritmi, mai ales când sunt scrise sincer într-un mod puțin confuz. Și am auzit niște povești de război despre această problemă fiind de fapt pe teme. Aparent, sunt într-o companie bună. Deci, să aruncăm o privire la această ultimă problemă de teme, 1-4. Deci, aceasta este pe suflarea cărămizilor. Și acesta este un exercițiu grozav de a aborda o problemă care este descrisă într-un limbaj cu adevărat lung, urât, inutil și apoi de a extrage cele două cuvinte care contează. Apropo, fac o glumă despre asta. Vă pot spune că aproximativ 82% din timpul meu ca profesor îl petrec cu oameni din industrie vizitându-mi biroul exact cu acest tip de scenariu în care are un lucru cu adevărat complicat. De ani de zile se gândesc la problema lor de construcție și au toate aceste detalii, tabele și diagrame de flux. Și apoi se dovedește că problema lor poate fi surprinsă în aproximativ două propoziții. Deci este o abilitate bună de a avea și una care vă poate aduce mulți bani ca consultant. Deci este unul care merită să exersăm în această clasă, chiar dacă o facem pentru Porkland cu un lup care suflă doar spre est. BINE. Deci, ce se întâmplă în această problemă? Există un lup, iar lupul poate sufla în case. Dar din anumite motive, lupului îi place să sufle în dreapta. Și ca să îngreuneze și mai mult lucrurile, cine a scris această problemă a comandat uneori lucrurile de la est la vest și alteori le-a comandat de la vest la est. Dacă aș fi fost instructorul tău la acea vreme, asta, cel puțin aș fi scăpat de asta pentru că e doar răutăcios. Dar, în orice caz, cred că povestea merge așa cum povestea apocrifă a lupului de porc, pe care o cunoaștem și o iubim cu toții din copilărie, este că există un șir de case, fiecare având un număr diferit de cărămizi. Da. Și acum este un vânt care bate de la vest la est. Îmi amintesc toate acestea pentru că m-am uitat la el azi dimineață în biroul meu. Și, în esență, lupul, fiind lupul mare și rău care este, spune, aha, dacă și eu suflă de la vest la est, pot doborî mai multe case mai eficient pentru că vântul mă ajută. Nu vrei să sufli în vânt. Îți dai scuipat în față. Bine, deci lupul face asta. Și apoi, ceea ce se întâmplă este că lupul nu numai că dărâmă casa peste care suflă lupul, ci și toate casele de la est de acea casă care au mai puține cărămizi. De ce, ați putea întreba? Nu știu, pentru că cine a scris problema asta era un prost. Dar aceasta este configurația de bază a acestei probleme. Și puteți vedea că, în esență, acesta este doar un mod lung și complicat de a descrie ceva destul de simplu. Și astfel, la sfârșitul zilei, lupul, fiind un fel de lup adversar, vrea să arunce în aer cât mai multe cărămizi. Și îi oferim lupului instrumentele analitice necesare pentru a face acest lucru. Da. Deci, în cazul în care nu credeai că am acoperit ceva practic în 6.006, acum știi că de fapt facem analize de ultimă generație a porcilor de suflare a cărămizilor de lup. BINE. Dreapta. Deci haideți să facem un exemplu pentru că acest lucru este ciudat de complicat. Deci, în prima parte a problemei, vă cere să faceți doar un exemplu. Și cred că dacă aș fi diagnosticat psihologic persoana care a scris această problemă, probabil motivul este că s-a retras și a spus că nimeni nu va înțelege asta dacă nu o oblig să facă un exemplu cu mâna. Dreapta? Și așa că problema de bază este să întreb, aș putea alege să sufle pe fiecare casă. Pe care ar trebui să aleg pentru a provoca cele mai multe daune? Sau, de fapt, ei pun de fapt o problemă puțin diferită, și anume, dacă ar fi să suflă pe fiecare casă, câte pagube aș provoca? OK, deci haideți să trecem prin problemă. Așa că vă oferă un exemplu, un set de numere, 34, 57, 70, 19, 48, 2. De fapt, să ne oprim aici. Nu cred că există niciun motiv să facem o listă cu un milion de numere ca în problemă. A fost exact ca, cu cât o faci de mai multe ori, cu atât te convingi cât de inutil este 6.006. BINE. Dreapta. Deci cât de multe daune provoacă suflarea casei numărul unu? Ei bine, hai să facem o măsuță. Așa că dacă suflă pe casa numărul unu, doar implicit, casa numărul unu cade. O să trag un x acolo, adică l-am aruncat peste cap. Și atunci regula este orice casă din dreapta care are mai puține cărămizi -- fizica acestei probleme mă înnebunește. M-am gândit destul de mult timp la asta și nu mă pot gândi la un vânt care să aibă de fapt această proprietate. Dar orice casă care are mai puține cărămizi și se află la est este, de asemenea, dărâmată. Deci 57 nu, nu? Este mai mare decât 34. La fel și pentru 70. Aha, 19 merge cu vântul. 48 e mai mare, iar 2 merge, nu? Deci elementul numărul unu al matricei mele ar fi 3, nu? Trei lucruri sunt aruncate în aer. OK, pentru următorul tip, nu? Deci 57 este aruncat în aer. Nu sufla peste 34 pentru ca lupul meu stie doar sa sufle in dreapta. Uh. Deci nu suflă peste 70. Suflă peste 19. Suflă peste 48. Da, nu? Deci, aici, ar fi un 4. Aceste numere nu se potrivesc cu cele din note, deoarece aceasta este o listă mai scurtă de numere, ar trebui să subliniez. OK, hai să mai facem una și apoi ne vom opri pentru că este laborios și plictisitor. Deci cei 70 bat peste tot. Da. Dar numai totul la dreapta, pentru că, după cum știm cu toții, lupii sufla doar la... OK, voi tace. Deci sunt patru lucruri care sunt aruncate în aer aici. Dar voi înțelegeți ideea, nu? Și, în esență, această problemă vă cere să completați matrice care arată astfel pentru problema dvs. Toți sunt de acord cu problema? Acum, observați că doar în virtutea faptului că facem acest exemplu, să ne gândim la asta în mod abstract, deoarece cred că aceasta este o problemă care este doar codificată în atâtea cuvinte și un gunoi TA ciudat inventat. Dar, la sfârșitul zilei, această problemă ca problemă algoritmică nu este atât de rea. În esență, ceea ce vă cer să faceți este să mă uit la acel 57 și să mă uit în dreapta și să număr câte lucruri sunt mai mici decât 57. Și îi adaug 1. Și acesta este numărul care ar trebui să intre în acel element din matrice. Așa că observați că acele trei paragrafe, asta e ceea ce comunică. Nu aveai nevoie de lupi care sufla și vânturi și copaci și case și Dorothy și tot felul de chestii. Da. Dreapta. Deci, la sfârșitul zilei, aceasta este problema la care ne putem gândi. Și nu trebuie să ne mai gândim niciodată la Porkland. BINE. Deci, poate în restul de 10 minute aici, cred că putem face fezabil partea b. Și atunci partea c este o extensie a părții b. M-am încurcat în partea c, așa că soluțiile scrise de mână au un răspuns incorect, apoi un hopa și apoi un răspuns corect. Deci puteți vedea unde logica mea a mers prost. Pentru a fi corect, știam deja răspunsul complet și le-am scris pe ambele pentru că am crezut că este util. BINE. Deci, în cazul în care problema noastră nu a fost suficient de concepută, îi vom adăuga puțină condiție. Și apoi, ceea ce vom vedea în partea c este că este cumva o piatră de temelie spre rezolvarea problemei mai mari . Deci, în partea c, se spune că o casă din Porkland este specială dacă are una dintre cele două proprietăți. Fie nu are vecin de est, adică este doar casa cea mai din dreapta, fie vecinul său adiacent la est conține cel puțin la fel de multe cărămizi ca și el. Dreapta. Deci, ce înseamnă asta în ceea ce privește această listă de numere? Care dintre acești tipi este special? Deci tipul din est este special. Știm asta în mod implicit. Și în afară de asta, această proprietate specială spune că tipul imediat din dreapta are un număr mai mare sau cel puțin egal sau mai mare cu cel din dreapta lui. Da. Deci 57 este mai mare decât 34, deci tipul ăsta este special. Apropo, problema nu îți cere să faci asta ca exemplu. Dar aș face-o pe deplin dacă aș rezolva asta. Da. 70 este mai mare decât 57, deci este special. 19 este mai mic decât 70, deci nu este special. Îmi pare rău. 40 este mai mare decât 19. Și cred că 2 este special doar pentru că lucrurile din dreapta sunt speciale. OK, deci primim cu toții definiția? Fabulos. Deci, în această problemă, acum ceea ce ni se oferă este că bănuiesc, ce, lupul nostru rău se plimbă pe bloc și se uită la... numără numărul de cărămizi din fiecare casă. Și el sau ea face o observație, și anume că toate, cu excepția unei case, sunt speciale. Acum, să ne gândim la ce înseamnă asta. Să ne gândim la structura matricei noastre. Deci, ce se întâmplă când merg pe dreapta mea? Dacă o casă este specială, ce știu despre următoarea casă? PUBLIC: Nu va fi aruncat în aer dacă arunci o casă specială. PROFESORUL: Este adevărat, dar rezolvăm deja problema acolo. Să ne gândim calitativ o secundă, ca doar în ceea ce privește numărul de cărămizi, nu? Merg pe stradă. Caut. Și numărul cărămizilor crește până ajung la singura casă care nu este specială. PUBLIC: [INAUDIBIL] PROFESOR: Și apoi scade, potențial, sau este ultimul. Și apoi începe să crească din nou. Da. Deci, cu alte cuvinte, matricea mea arată ca următorul, adică are practic două bucăți diferite care sunt ambele sortate. Da. Asta spune acest lung paragraf. Se spune să presupunem că lista de case este sortată, cu excepția unui singur lucru. Da. Așa ai fi putut să spui. OK, deci iată un exemplu. Deci poate avem 1, 2, 3, 4 și apoi, nu știu, 2, 3, 4, 5. Deci toate astea sunt speciale, cu excepția acestui tip, din păcate pentru el. Și așa se întâmplă o mică linie de despărțire, la stânga căreia este sortată și la dreapta. Da. OK, și atunci întrebarea este, putem prezice pagubele pentru fiecare casă pe baza acestor informații? Așa că vreau ca rezultat în codul meu o matrice care spune: acest tip provoacă atât de multe daune, acest tip provoacă atât de multe daune și așa mai departe. Și vreau să-l iau în ordine n timp. Să ne gândim o secundă. Deci cum vom face asta? Așa că comanda n timp înseamnă că nu-mi permit să fac sortare și tot felul de chestii de lux. Deci, practic, tot ce pot face este să merg în sus și în jos prin matrice. Așa că ar trebui să ne gândim puțin la ce are special special... bine. Ce este special la această configurație pe care în mod normal nu am avea-o? PUBLIC: Orice lucru înainte de nodul nespecial ar trebui să aibă același... sau îmi pare rău. PROFESORUL: Nu chiar. PUBLIC: Totul după nodul nespecial provoacă o singură daune. PROFESORUL: Da, deci să ne gândim cu atenție la asta. Cred că este corect, dar sunt prost la analizarea propozițiilor. Amintiți-vă că suflă mereu spre dreapta și suflă doar lucruri scurte. Deci, dacă suflu pe acest 2 aici, ceva înainte de acea linie verticală va fi explodat vreodată? Nu, pentru că prin proprietatea de a fi special, știm că lista crește. Dar trebuie să scadă pentru a arunca ceva în aer. Asta are sens? Deci, pentru fiecare dintre acești tipi, singurele lucruri pe care le putem arunca sunt în a doua matrice. Are sens? Așa că am făcut o observație. Observați că este special pentru structura pe care am dat-o problemei noastre. Da. Și mai mult, în ambele părți ale acestei probleme, vom analiza două părți ale unei matrice și apoi le vom îmbina într-un mod inteligent. Să ne uităm în partea dreaptă. Are vreunul din aceste lucruri... dacă suflă peste oricare dintre aceste case, care este paguba pe care o fac? 1. Vezi asta? Pentru că aceasta este o listă din ce în ce mai mare , suflă doar spre dreapta și trebuie să se scurteze. Da. Deci, dacă vreau credit parțial pentru problema temei mele -- probabil foarte puțin credit parțial, dar spiritual, este jumătate din creditul tău -- știm că a doua jumătate a matricei mele este doar o grămadă de 1. De altfel, un detaliu pe care pun pariu că ar avea un minus 1 la tema, nu ți-am spus asta... tot ce ți-am spus este că există o casă care nu era specială, dar nu ți-am spus care dintre ele. . Dar observați că îl pot găsi în ordine în timp, nu? Pot să merg de-a lungul matricei mele și să găsesc primul loc în care scade, și asta este o casă specială. Așa că pot să presupun că știu unde este această linie. Asta e cușer. Deci, singura întrebare este, cum îmi completez matricea aici? Cum număr... și deci să ne gândim la asta matematic pentru că porcurile și suflarea și alte chestii sunt cam confuze. Deci, să ne gândim la asta în ceea ce privește această matrice. În esență, ce încerc să fac? Deci, pentru acest 2, încerc să caut în a doua jumătate a matricei mele și să găsesc toate numerele de aici care sunt mai mici de 2, nu? În esență, asta vă cere această problemă să faceți. Vezi asta? BINE. Voi face unul - deci iată un fel simplu de algoritm n pătrat, nu, și anume, aș putea să iterez peste fiecare element de aici și să fac bucla aici și să număr numărul de lucruri care sunt mai mici decât atât, nu? Aceasta este o buclă for dublă, fiecare dintre acestea putând fi până la n. Deci este n pătrat. Asta contravine regulilor. Nu pot face asta. Deci avem nevoie de încă o observație suplimentară. BINE. Să ne gândim la asta o secundă. Să zicem că sunt lupul, lupul care sufla porc. Și merg dintr-o casă în alta. Și țin evidența caselor aruncate aici. Acum, ce se întâmplă? Pe măsură ce merg de la o casă la alta pe partea stângă, ei doar cresc, nu? Asta înseamnă să fii special. Deci casele care sunt aruncate în aer aici, setul acestora crește doar mai mult. Are sens? Pentru că, pe măsură ce tipii ăștia devin mai înalți, mai multe lucruri cad pe partea dreaptă. E ca și cum un nebun a vorbit despre această problemă. Mai mult, acești băieți sunt în ordine. Da. Deci, ceea ce se va întâmpla este că, întotdeauna, există doar un interval de case care se dărâmă. Deci, de exemplu, cele 4 lovituri peste 2 și 3, cred. Observați că începe întotdeauna din partea stângă. Și asta pentru că acești tipi sunt sortați. 3 doar suflă peste 2, care este un fel de subset al celor 4. Acesta nu este un exemplu grozav pentru că primii doi tipi nu suflă peste nimic. Asta are sens? Vreo idee? Cum aș putea folosi această observație pentru a face un algoritm de ordine n pentru numărarea daunelor provocate de suflare? Am auzit multe de la tine. Să auzim de la unii dintre ceilalți colegi de aici. Alta persoana. Da. PUBLIC: Căutare binară. PROFESOR: Căutare binară. Spune-mi mai multe. Ce aș căuta? PUBLIC: Deci, să presupunem că ai 4 și te miști singur din dreapta, luați indexul acestuia și apoi luați numărul. PROFESORUL: Este o intuiție interesantă. Și are dreptate în proporție de 82%. Deci, pentru a repeta sugestia colegului nostru , care este una bună și vă va face codul mult mai rapid - de fapt, în termeni practici, probabil ar fi cam la fel. Ar fi că mă voi muta de la stânga la dreapta, dacă nu există un cartier foarte mare de porci. Mă voi muta prin această matrice. Voi căuta în binar această parte cealaltă și voi găsi prima casă care nu ar trebui să fie aruncată în aer sau așa ceva. Și acum știu numărul total de lucruri care sunt aruncate în aer. Acum, din păcate pentru tine, care este durata de rulare a acelui algoritm? n log n, nu? Pentru că pentru fiecare tip de aici, fac o căutare binară acolo, care este log n time. Deci ești în biserică, greșit banca aici. Dar există o observație pe care nu am folosit-o încă, și anume, pe măsură ce mă deplasez spre dreapta, aceste numere cresc. Da. Deci, ce se va întâmpla cu indexul lucrurilor care sunt aruncate în aer? Mereu se va mișca așa. Se va muta vreodată la stânga? Nu. Deci există un termen pe care l-am folosit în două prelegeri în urmă, care este un termen pe care nu l-am mai auzit până acum, dar îmi place. Se numește algoritm cu două degete. Da. Ce face algoritmul cu două degete? Arata asa. Doua degete. Da. Deci, ceea ce voi face este să țin degetul pe dreapta, arătând chiar primul lucru care nu este aruncat în aer. BINE. Deci iată, corect, 1 nu suflă peste nimic. Deci rămâne aici. Am de gând să repet la următorul tip. Cei 2 suflă peste ceva? Nu, apropo, problema este scrisă. Acum o să-l mut pe tipul ăsta aici. Ei bine, acum cele 3 lovituri peste cele 2 de aici. Așa că voi muta degetul drept un lucru spre dreapta și voi muta tipul la 4. Nici 4 nu suflă peste nimic și apoi cred că am terminat. Dar punctul de bază aici este că voi crește întotdeauna două indicatori diferite și voi muta la dreapta. Și ce am de gând să fac? Dacă numesc acest deget i și acest deget j, i sau j vor scădea vreodată? Nu. Deci, dacă algoritmul meu face buclă peste toți acești tipi și aceștia ating o singură dată fiecare dintre acești indici, voi obține o tehnică de ordine n. Da. Și acesta va fi trucul de bază pentru a rezolva această problemă. Acum, am reușit să mă vorbesc în afara timpului. Dar, practic, asta este. Deci ceea ce voi face dacă avem 10 secunde în plus este că voi inițializa. În esență, pentru fiecare i, voi crește j până când numărul de cărămizi de la j este mai mare decât numărul de cărămizi de la i. Bănuiesc că ar trebui să fie mai mare sau egal cu. Dreapta? Și motivul pentru a face asta este că acum numărul de case care sunt aruncate în aer este doar acest indice j minus indicele primului tip, nu? Și apoi voi crește i și voi continua. Are vreun sens? Fabulos. Așa că am reușit printr-un miracol să ajung aproape la sfârșitul acestui set de probleme minus o parte dintr-o problemă. Desigur, aceasta este cea mai grea parte a întregului set de probleme. Dar există un răspuns scris unde, în esență, acum întrebarea este, puteți face exact același algoritm, dar nu vă dau această presupunere specială că crește și apoi scade? Și va fi practic o extensie a acestei idei, deoarece vom folosi acest lucru plus un pic de sortare de îmbinare. BINE. Deci, cu asta, ne vedem săptămâna viitoare. Este întotdeauna o plăcere. Și da, un weekend minunat.