SPEAKER 1: Hei toată lumea! Bine ați revenit la pct. Mă bucur să văd atât de mulți dintre voi amândoi aici, și toți cei care se uită on-line. Deci, ca de obicei înapoi bun venit. Sper că toate au avut un minunat week-end, plin de odihnă, relaxare. A fost frumos ieri. Așa că, sper că va plăcut în aer liber. Deci, în primul rând o pereche de anunțuri. Standard folosit. Așa că, cele mai multe dintre voi ar fi ajuns un e-mail de la mine despre PSET ta Scratch, precum și de clasificare pentru PSET 1. Așa că, doar câteva lucruri. Asigurați-vă că pentru a utiliza check50 în style50. Acestea sunt menite să fie Resurse pentru voi, pentru a vă asigura că sunteți obtinerea cât mai multe puncte ca tine poate fără a pierde inutil ele. Așa că, lucruri de genul stil sunt foarte importante. Vom lua off pentru ea. Unii dintre voi ar putea avea deja observat că de la PSET ta. Și check50 este doar un mod foarte ușor de a vă asigura că suntem de fapt revenirea ceea ce trebuie să fie returnat utilizatorului, și că totul funcționează corect. La a doua notă, asigurați-vă că dumneavoastră încărcarea lucruri în folderul corect. Aceasta face ca viața mea doar o pic mai dificil dacă încărcați PSET 2 în PSET 1 pentru că atunci când am descărca lucruri, ele nu se descarcă corect. Și știu că e un pic subred într-un sistem să se obișnuiască cu, ci doar să fie super- până la în cazul în care numai pentru mine, astfel încât atunci când sunteți de asistent e-mailuri la fel ca 2 A.M. si eu sunt de clasificare. Dacă nu pentru că am să te uiți peste tot în jurul pentru PSET ta. Rece. Știu că e devreme, dar eu total a fost luată cu garda jos de un eseu care este cauza aceasta vineri, că profesorii mei au fost la fel ca, oh da. Amintiți-vă, aveți un eseu datorită vineri. Așa că, știu că nu-i place să se gândească la examenele, dar primul test este în 15 octombrie, care se octombrie începând din această săptămână. Astfel, ar putea fi mai devreme decât v-ați așteptat este tot. Astfel că nu ești aruncat cu garda jos atunci când Menționez secțiune de săptămâna viitoare că oh, dvs. de test săptămâna viitoare, m-am gândit Ți-aș da un pic mai mult de un heads-up acum. Astfel, problema ta stabilite, numărul trei. Modul în care oamenii au citit spec din curiozitate? OK. Avem un cuplu. Un fel de jos din trecut săptămână, dar asta e OK. Știu că a fost mai frumos. Deci, Break Out. Categoric după ce te-ai făcut citește astăzi spec ta cu cel puțin încercați ca descărcarea Codul de distribuție și funcționare la fel ca prima inițială lucru pe care vă rog să. Pentru ca suntem cu ajutorul Codul de distribuție și o bibliotecă că am fost doar using-- --It e doar a doua oară am făcut acest PSET, lucruri nebunești se poate intampla cu aparatul, și doriți să găsiți că acum versus mai târziu. Pentru că dacă e joi seara sau e Miercuri noapte și pentru un motiv oarecare aparatul pur și simplu nu doresc să curgă de la biblioteca sau cu distribuția cod, că mijloacele nu poți începe să faci de codificare. Pentru că nu poți verifica pentru a vedea dacă funcționează. Dumneavoastră nu va fi capabil pentru a vedea dacă acesta compilează. Vrei să aibă grijă de cei care la începutul anului a săptămânii, atunci când se poate trimite un email pentru încă mă sau una dintre celelalte TFS, și putem obține cele fixe. Deoarece acestea sunt probleme care sunt de gând să te oprească de la a face orice progres real. Nu e ca un bug, care poti doar un fel de săriți peste. Dacă aveți probleme cu dvs. aparat sau cod de distribuție, chiar vrei să te că ia de îngrijire de mai devreme, mai degrabă decât mai târziu. Deci, chiar dacă nu ești de fapt o să începe de codificare, descarcati distribuție cod, citiți spec, asigurați-vă că totul merge acolo. OK? Dacă se poate face doar asta, am promit, viața voastră va fi mai ușor. Și așa ești, probabil, va să o fac chiar acum corect? OK. Așa că, orice întrebări acolo? Orice lucruri logistice? Toată lumea e bine? OK. Disclaimer pentru cei de te în cameră și on-line. Am de gând să fie încercarea de a comuta între PowerPoint în aparat pentru că am de gând să fie faci unele de codificare astăzi la cererea publicului de anonim poll sugestie am trimis săptămâna trecută. Așa că, vom face unele de codificare. Așa că, dacă voi dori, de asemenea pentru a porni aparatele dumneavoastră, și ar trebui să-au luat un e-mail de la mine, cu un fișier mostră. Vă rugăm să nu ezitați să fac asta. Așa că, vom vorbi despre GDB, care este un program de depanare. O să te ajute un fel de seama unde lucrurile nu merg bine în cod. Este într-adevăr doar o modalitate de a-și intensifice prin codul așa cum se întâmplă, și să fie capabil de a imprima variabile sau pentru a vedea ce se întâmplă de fapt sub capota versetele Program doar rulează, e ca si cum faulting, si tu esti ca, nici o idee ce sa întâmplat aici. Nu știu ce linie a eșuat la. Nu știu de unde a mers prost. Așa că, GDB este de gând să te ajut cu asta. De asemenea, dacă vă decideți să continuă da, și să ia 61, aceasta va într-adevăr, să fie într-adevăr ta cel mai bun prieten, pentru că eu pot să vă spun pentru că am de gând prin acea categorie. Ne vom uita la binar căutare, care, dacă voi aminti marele exemplu de carte de telefon spectacol de clasă. Vom fi de punere în aplicare, care, și mersul pe jos prin faptul că un pic mai mult, iar apoi vom trece prin patru diferite tipuri, care sunt bule, Selecție, Insertion, și Merge. Rece. Astfel, GDB cum am menționat, este un program de depanare. Și acestea sunt un fel de big lucruri, funcțiile mari sau comenzi pe care le utilizați în GDB, și voi umbla tu printr-un demo de ea într-o secundă. Așa că, acest lucru nu este doar O să stați abstract. Voi încerca și să-l ca beton este posibil pentru voi. Așa că, rupe. Va fi, fie pauză cum ar fi, unele număr, care reprezintă o linie în programul tău, sau poti numi o funcție. Așa că, dacă spui rupe principal, se va opri la principal, si lasa te plimbi prin această funcție. De asemenea, dacă aveți ceva extern functioneaza ca Swap sau Cube, că ne-am uitat la săptămâna trecută. Dacă spui rupe unul din cei, ori de câte ori programul dvs. ajunge la asta, se va aștepta pentru tine de a spune-l ce să facă. Înainte de a va executa doar ca să ar putea interveni de fapt in interiorul functiei și să vedem ce se întâmplă. Așa că, în continuare, doar sare peste linia următoare, trece peste funcțiile. Pas. Acestea sunt toate puțin abstract. Deci, am de gând doar pentru a rula prin intermediul lor, dar le vei vedea în uz într-o secundă. Pas într-o funcție. Deci, cum spuneam, cum ar fi cu Swap, ar fi vă permit să fapt ca daca esti ca pas cu pas fizic în interior, poți pune cu aceste variabile, imprimare ce sunt, să vedem ce se întâmplă. Listă doar literalmente imprima din codul înconjurător. Deci, dacă un fel de uitat în cazul în care vă aflați în programul tău, sau te intrebi ce se întâmplă în jurul lui, acest lucru va imprima doar un segment de place cinci sau șase rânduri în jurul ei. Deci, puteți obține orientate despre locul unde ești. Printeaza unele variabile. Așa că, dacă aveți cheia ca în Cezar, că ne vom uita la. Se poate spune Print cheie în orice moment. O să-ți spun ce valoarea este atât de care, poate undeva pe drum, ai suprascris cheia. Vă pot spune de fapt că, din cauza puteți observa că de fapt valoare. În localnicii, doar amprentele din variabilele locale. Așa că, oricând ești într-o buclă, si doriti doar pentru a vedea cum ar fi, oh. Ce este mea? Ce este această valoare cheie pe care am inițializa aici? Care este mesajul în acest moment? Se va imprima doar tot dintre acestea, astfel încât să Nu trebuie să individual spune, Print I. Print mesaj. Imprimare Key. Și apoi Afișare. Ceea ce nu este la fel de tine pas prin intermediul programului, se va face doar vă că este unde sunt afișate unele anumite variabile la fiecare punct. Astfel încât să also-- --it e un fel de scurtătură în cazul în care nu trebuie să continui ca, oh. Print cheie sau Print I. Pur și simplu se va face în mod automat pentru tine. Astfel, cu asta, vom pentru a vedea cum merge. Am de gând să încerc și comutator pe la aparat mea. Vezi dacă pot să fac acest lucru. Toate. Noi doar de gând să-l oglindă. Nu e nimic nebun pe laptop-ul meu oricum. OK. Acest lucru trebuie să fie acesta. E atât de mic. Să vedem dacă putem face acest lucru. OK. Alice este, evident, luptă aici doar un pic, dar o vom lua într-un momento. OK. Suntem doar de gând să crească asta. OK. Poate toată lumea un fel de a vedea asta? Poate un pic? Știu că e un pic mai mic. Nu puteți da seama modul de a face acest lucru mai mari. Dacă cineva știe. Stie cineva cum să facă mai mare? OK. Noi o să se rostogolească cu el. Nu conteaza oricum, pentru că e doar care este codul pe care voi trebuie au. Ce e mai important este terminalul aici. Și avem aici De ce este atât de mic? Setări. Oh. Adevărat Ike. Cum e asta? De acolo. E mai bine pentru toată lumea? OK ,. Rece. Știi când ești într-un CS dificultăți tehnice de clasă sunt un fel de parte de the-- Deci, să îndepărteze acest lucru. OK. Așa că, chiar aici, în secțiune, pe care am avut aici. Cezar este un fișier executabil. Așa că am făcut. Așa că, un lucru pentru a realiza cu GDB este că aceasta funcționează doar pe fișierele executabile. Deci, nu se poate rula pe o dotsy. Va trebui să facă de fapt sigur că codul dvs. compilează, și că aceasta poate fi de fapt rula. Așa că, asigurați-vă că în cazul în care nu compila, sa-l pentru a compila, astfel încât să puteți fel de a alerga prin ea. Așa că, pentru a începe GDB, tot ce faci, Gloria tip GDB, iar apoi doar fișier pe care doriți. Intotdeauna mi-am misspell Cezar. Dar doriți să vă asigurați că din moment ce este un executabil, dot rapidă ti, astfel încât înseamnă că va pentru a rula CSI ai de gând să execute acest fișiere, fie cu debugger. OK. Deci, nu asta, veți obține acest tip de păsărească. E doar toate lucrurile despre debugger. Nu trebuie într-adevăr să vă faceți griji despre asta chiar acum. Și, după cum vedeți, avem această parens deschise, PIB-ul, parens apropiate, și doar un fel de arata ca linia noastra de comanda, nu? Deci, ce vrem să do-- --So, Primul lucru este ne-o dorim pentru a alege un loc să-l rupe. Astfel, există un bug în acest program Cezar că eu prezint, că vom afla. Ea ceea ce face este dureaza de intrare Barfoo în toate capacele, și pentru un motiv oarecare aceasta nu se schimba A. Pur și simplu frunze l în pace, e orice altceva corect, dar a doua scrisoare O rămâne neschimbat. Așa că, vom încerca și dau seama de ce, care este. Așa că, primul lucru pe care în mod obișnuit vreau să fac de fiecare dată când începe GDB Este seama de unde să-l rupe. Deci, Cezar este un program destul de scurt. Doar avem o singură funcție, nu? Care a fost funcția noastră în Cezar? Există doar o singură funcție, chiar Main? Principal este o funcție pentru toate programele. Dacă nu ați avea principal, aș putea fi un pic ingrijorat acum, dar sper că toate au avut Main acolo. Deci, ce putem face este să putem doar rupe principal, la fel ca asta. Așa că, se spune, OK. Am stabilit un punct de întrerupere noastră acolo. Așa că, acum lucru de retinut este Cezar reușește o comandă argument linie dreaptă și nu am făcut asta încă nicăieri. Deci, ce faci este atunci când tu de fapt mergi pentru a rula programul, orice program care ești se execută în GDB care are nevoie de linie de comandă argumente, ai de gând să intrare atunci când începe primul rulează-l. Așa că, în acest caz, ne vom face Pornește cu o cheie de trei. Și va începe de fapt. Așa că, dacă vedeți aici, avem Dacă RC nu este egal cu 2. Deci, dacă voi avea tot care fișier pe care am trimis în sus veți vedea că e ca primul rând funcția noastră principală, nu? Este verificare pentru a vedea dacă avem numărul corect de argumente. Așa că, dacă vă întrebați în cazul în care RC este corectă, poti face ceva la fel ca Print RC. RC este doi, care este ceea ce ne-am așteptat, nu? Așa că, putem merge în continuare, și continuă prin. Deci, avem o cheie acolo. Și putem imprima cheia noastră pentru a vă asigura că este corect. Interesant. Nu este destul de ceea ce ne-am așteptat. Așa că, un singur lucru pentru a realiza cu GDB, de asemenea, este asta nu e până când de fapt lovit În continuare, că linia pe care tocmai l-ai văzut este, de fapt executat. Așa că, în acest caz Cheie nu a fost atribuit încă. Așa că, Key este o valoare gunoi pe care le vezi pe partea de jos acolo. Negativ $ 120-- --It de un miliard și ceva lucruri ciudate corect? Nu e cheia care ne-am așteptat. Dar dacă ne-am lovit pe Următorul, apoi ne încercați și tasta Print, e trei. Toată lumea poate vedea că? Așa că, dacă aveți ceva că tu ești ca, așteptați. Acest lucru este complet greșit, și eu nu știu cum acest lucru se va întâmpla pentru că tot ce vreau să faceți este să atribui un număr, o variabilă, încercați lovind Apoi, încercați să imprimați -o din nou, și a vedea dacă funcționează. Pentru ca este doar de gând să execute și atribuie de fapt ceva după tine lovit următor. Face sens pentru toată lumea? Uh huh? SPEAKER 2: Când aleatoare Numerele ce înseamnă asta? SPEAKER 1: E doar aleator. E doar gunoi. E doar ceva ce dvs. computer va atribui aleatoriu. Rece. Deci, acum ne putem deplasa prin, și așa acum avem acest getString text simplu. Așa că, lasă-mă să introducă ceea ce se va întâmpla atunci când am lovit pe Următorul aici. GDB nostru fel de dispare, nu? Asta pentru că getString acum este de executare, nu? Așa că, atunci când am văzut text simplu este egal GetString, parens deschise și parens, și ne-am lovit continuare, care are de fapt executat acum. Astfel, este de așteptare pentru ne la intrare ceva. Așa că, vom intrare hrana noastră care este ceea ce este în lipsa cum v-am spus și că doar spune că e a terminat de executare, că închis Suport înseamnă că este care iese din bucla asta. Astfel, ne putem lovi în continuare, și acum, așa cum am sigur că ești familiar de la Cezar, aceasta este, ceea ce este această linie de gând să faci. E pentru Int I este egal cu 0, N este egal Strlen, text simplu, și apoi I este mai mică decât n, I, plus, plus. Ce este această buclă de gând să faci? Deschideți mesajul tău. Rece. Deci, să începem a face asta. Așa că, ar trebui această condiție se potrivesc, pentru prima noastră o? Dacă e un B, e text simplu I. Noi pot obține informații despre localnici noastre. Așa că, eu este zero, iar în cazul în care șase, care ne așteptăm, iar cheia noastră este de trei. Tot ceea ce face sens, nu? Aceste numere sunt toate exact ce ar trebui să fie. Așa că, hum? SPEAKER 3: Eu am numere aleatoare pentru a mea. SPEAKER 1: Ei bine, putem --we check-- poate vorbi despre faptul că într-o secundă. Dar tu ar trebui să fie de asistent asta. Așa că, dacă avem un capital B pentru primul nostru este de această condiție ar trebui să-l prind, nu? Așa că, dacă ne-am lovit continuare, vom vedea că acest În cazul în care de fapt executa. Pentru că dacă ești următor de-a lungul în codul dvs., această linie de aici, unde text simplu I se înlocuiește cu această aritmetică, execută numai în cazul în care în cazul în care condiție este corect corect? GDB este doar de gând să-ți arăt lucruri care sunt de fapt de executare. Deci, în cazul în care această condiție cazul în care nu a fost îndeplinită, e doar de gând pentru a trece la următoarea linie. OK? Deci, avem asta. Această categorie înseamnă că este închis din care bucla acum. Așa că, o să înceapă din nou. La fel ca asta. Astfel, încât să putem obține multe informații despre localnici noastre aici, și vedem că primul nostru scrisoare sa schimbat, nu? Este acum un E, așa cum ar trebui să fie. Astfel, putem continua mai departe. Și avem această verificare. Iar această verificare ar trebui să lucreze, nu? E A. Ar fi schimbată trei litere înainte. Dar, dacă observați, noi a obține ceva diferit. Deci, în acest caz aici, a prins- ea, și așa mai departe această linie executat, care a modificat nostru B. Dar, în acest caz aici, avem că doar o omit, și a mers la [? L Siff. ?] Deci, ceva se întâmplă acolo. Ceea ce îți spune este că, știm că ar trebui să prind aici, dar nu este. Poate cineva sa vezi ce noastre problemă este aceea că linia? Este un lucru foarte minut. Și ai putea uita, de asemenea, la codul. Este, de asemenea line-- uita ce linia este în there-- dar se află într-[neauzit]. Da? SPEAKER 4: E pe cea mai mare decât pagina dacă l-ai citit în carte. SPEAKER 1: Exact. Așa că, debugger nu a putut spune tu asta, dar debugger ai putea să trecem la o linie care știți că nu funcționează. Și, uneori, când mai ales mai târziu, în semestrului, atunci când ai de a face cu o sută, o sute de câteva linii de cod, și te Nu știu unde e lipsa, aceasta este o modalitate foarte bună de a face acest lucru. Așa că, am găsit bug nostru. Puteți să-l repara în fișierul dvs., și apoi ai putea rula din nou, și totul va funcționa perfect. Și cel mai important lucru este acest lucru poate parea, OK. Da. Rece. Ai știut ceea ce căutați. Așa că, ai știut ce să facă. GDB poate fi foarte util pentru că poate imprima toate aceste lucruri pe care le nu ar fi. Este mult mai util decât printf. Câți dintre voi folosiți cum ar fi declarațiile printf pentru a descoperi în cazul în care un bug a fost, nu? Așa că, cu acest lucru, tu nu faci Trebuie să continui înapoi, și ca comentând în Printf, sau comentarea, și dau seama ce ar trebui să fie de imprimare. Acest fapt, doar vă permite să pas prin, imprima lucruri cum ai de gând prin, așa, puteți observa cum se schimbă în timp real, ca programul se execută. Și aceasta nu ia un pic bit de a fi utilizate pentru a. Mi-ar recomanda foarte doar un fel de a fi un pic frustrat cu ea pentru chiar acum. Daca petreci o oră de-a lungul săptămâna viitoare a învăța cum să folosească GDB, te va salva atât de mult timp mai târziu. Și literalmente. noi spunem acest oamenilor în fiecare an, și Îmi amintesc când am luat clasă, am fost ca, voi fi bine. Nu. PSET 6 intrat în și am fost cum ar fi, am să învețe modul de utilizare a GDB pentru că eu nu fac știu ce se întâmplă pe aici. Deci, dacă vă faceți timp pentru așa să-l utilizați pe programe mai mici care ai de gând să fie de lucru pe, cum ar fi de lucru prin ceva de genul Visionare, cum ar fi aceasta. Sau, dacă vrei practică în plus, sunt sigur Aș putea veni cu programe de buggy, pentru tine de a depana dacă doriți. Dar dacă luați doar ceva timp pentru a obține obișnuiești cu el, juca doar în jurul valorii de cu ea, ea va servi foarte bine. Și este într-adevăr una dintre acele lucruri pe care le pur și simplu trebuie să încerci, și ia-ți mâinile murdare cu, înainte de a vă într-adevăr înțeles. Am într-adevăr doar înțeles dată Am avut de a depana lucruri cu ea, și este mult mai plăcut de a avea o idee de cum de a depana mai devreme, mai degrabă decât mai târziu. OK. Rece. Știu că e un fel de un curs intensiv în GDB, și voi lucra cu siguranta pe asistent acestea să se uite mai mari data viitoare. Rece. Așa că, dacă ne întoarcem la PowerPoint nostru. Se întâmplă acest lucru la locul de muncă? AWH. Da. OK. Așa că, dacă ai nevoie vreodată de cei din nou, nu e pe lista. Căutare așa binară, care toată lumea își amintește mare spectacol a lui David ripping cărți de telefon în jumătate. Eu nu obține cu adevărat anymore cărți de telefon, pentru că așa cum în cazul în care faci a obține cărți de telefon în aceste zile? Eu chiar nu știu. Binary căutare. Are cineva aminte cum binare lucrări de cautare? Oricine la toate? Da? SPEAKER 5: Știi când te uiti la care jumătate ar fi în, Bazat pe faptul că, și a scăpa de cealaltă jumătate. SPEAKER 1 Exact. Așa că, căutare binară, e un fel de un-- --we place să numim diviza și cuceri. Deci, ce vei face este te vei uita la mijloc, și veți vedea dacă se potrivește ceea ce căutați. Și dacă nu o face, atunci când încercați să da seama, așa va fi lăsat jumătate sau jumătatea din dreapta. Așa că, acest lucru ar putea fi dacă sunteți în căutarea la ceva care este alfabetic, vezi tu, oh. Are Allison veni în fața M? Da. Așa că, vom uita-te la prima jumătate a anului. Sau ar putea fi ca cu numere. Orice lucru care puteți compara, acesta poate fi sortate. Puteți utiliza căutare binar pe. Așa că, oricine amintiți-vă acest grafic sau ce e asta? E Complexitatea asimptotice. Astfel, acest grafic doar descrie cât de mult te duce pentru a rezolva o problemă cât mai vă crește numărul de lucruri pe care îl utilizați. Deci, avem N, care este timpul liniar. Dacă N peste doi, care este ușor mai bine, încă se dezvoltă foarte rapid. Și apoi ne-am Autentifică-te, ceea ce este ceea ce noi considerăm de căutare binară. Dacă observăm, ca problema ta devine mult și mult mai mare, în momentul în care ai nevoie pentru a rezolva nu reprezintă cu adevărat crește atât de mult. E ca și cum comparabil aici, la început. Ești ca, OK. Nimic aici nu prea Indiferent care o vom folosi, dar tu ieși la un milion, un miliard. Sunteți încercarea de a găsi some-- --you're încercarea de a găsi un ac în carul cu fân. Cred că vrei această problemă. Vrei această complexitate, nu liniară pentru că pentru tot ce ai stiti voi tău trebuie să căutați prin fiecare ac individ, lucru de fân, încercând să uite pentru ac dumneavoastră. Și asta nu e prea distractiv, în opinia mea. Îmi place repede. Îmi place eficient. Și studenți în calitate de harnici te Voi sunteți, știți lucreze mai inteligent, nu mai greu lucru de tip, cum ai pot face acești algoritmi. Deci, noi vom umbla prin intermediul doar un exemplu rapid. Cred că voi ar trebui să aibă o mână pe Căutare binară, dar în cazul în care cineva este un pic neclare, să-l consolideze, vom merge doar printr-un exemplu aici. Așa că, căutăm în cazul în care matrice conține șapte. Așa că, primul lucru ce facem este uita-te la mijloc, nu? Și, de asemenea, ai de gând să fie de codificare Cauta binar în doar o secundă. Așa că, o să fie distractiv. Așa că ne uităm în tablouri mici de mijloc 3. Are 3 egală cu 7? Nu. E de șase. Deci, este mai mică de sau mai mare de șapte? Mai puțin de. Da. Baieti de locuri de muncă frumos. Simt Îmi place că ar trebui Trebuie bomboane pentru că am doriți să-l arunce în șantierele. E ceea ce am de gând să fac săptămâna viitoare. Acesta vă va ține băieți ascuțite. Așa că, ne-am arunca că prima repriză, nu? a fost mai mică. știm că tot pe care stanga va fi mai mică decât ceea ce suntem de fapt în căutarea pentru. Deci, nu este nevoie să acorde o atenție la ea. Doar uita despre asta. Deci, acum ne uităm la partea noastră dreaptă, și ne uităm la mijloc acolo, iar acum e nouă. Astfel, 9 este-- --Everyone? Mai mare decât ceea ce suntem cautati, nu? Așa că, vom arunca departe tot la dreapta. Ca asta. Acum, tot ce mai rămâne cu unul. Așa că am verifica, este aceasta ceea ce căutăm? ea este. S-au găsit ceea ce ne-am dorit. Deci, am terminat. Biliniare de căutare. Și dacă observați, noi a avut șapte intrări acolo. Ea doar ne-a luat ca de trei ori, dar dacă faci ca un miliarde de euro, voi ști câți pași ca ar fi ia dacă am fi avut patru miliarde de lucruri? Orice presupuneri? E 32. 32 pași pentru a găsi ceva într-o patru miliarde element de matrice din cauza puteri de două. Deci doi este la 32, este la patru miliarde. Cum așa destul de nebun ești încă în ca un număr destul de mic de etape pentru a găsi ceva în patru miliarde de elemente. Deci, pe această notă, suntem O să codul această astfel voi putea de fapt un fel de a vedea cum functioneaza aceasta. Bine, deci voi putea cod. Am de gând să vă voi lăsa vorbim de un pic. Ia să știu de oameni din jurul tau, care este ceea ce cineva a vrut de la ultima secțiune. Deci, ajunge să cunoască oamenii din jurul tău. Vorbesc pentru un pic. Si tot ce vreau de la tine baieti acum este doar încercați să creați o schiță de pseudocod. OK? Whoa. Tot ce vreau de la voi este că ești doar de gând să completați în acest caz în timp ce. Deci, am stabilit aceste superioară și limite inferioare care reprezintă începutul și la sfârșitul de oferta noastră. Și aveți de gând să efectiv bucla prin și dau seama ceea ce facem noi în această buclă în timp ce. Deci, dacă vă puteți da seama out-- am un indiciu there-- care sunt cazurile pe care le avem aici? Deci, dacă doriți să dau seama de cazuri, vom pseudocod cele și apoi le vom cod de fapt. Și aceasta va fi, eu cred, să sperăm că va fi un pic mai ușor decât vă așteptați. Pentru că nu e atât de mult cod, de fapt, ceea ce este foarte cool. Mm-hm? STUDENT: [inaudibil]? INSTRUCTOR: Da. Nu a fost ceva pentru a găsi în mijloc. STUDENT: Deci, putem folosi asta. OK. INSTRUCTOR: Perfect. Deci, asta e primul lucru pe care trebuie să facem. Deci, găsi pe centru. Mare. Deci, ai o idee despre cum am putea afla de fapt la mijloc cu codul? STUDENT: Da. n peste 2? INSTRUCTOR: Deci, n peste 2. Deci, un lucru de reținut este faptul că dvs. de limite superioare și inferioare se schimbe. Noi mereu constrictia partea de matrice suntem în căutarea de a. Deci, n peste 2 va funcționa numai pentru primul lucru pe care îl facem. Deci, luând superioara si inferioara în considerare, cum am putea obține acest element de mijloc? Pentru ca vrem pe centru între superior și inferior, dreapta? Mm-hm? STUDENT: [inaudibil]. INSTRUCTOR: Deci avem ceva de mijloc. Și va fi superioară plus de jos peste 2. Minunat. Acolo mergem. O linie în jos. Sunteți pe drumul tau. Deci, acum că ne-am nostru de mijloc, ce vrem să facem? Doar în general. Nu trebuie să-l cod. Da. STUDENT: [inaudibil]? INSTRUCTOR: Deci e plus pentru că ești găsirea media între cele două dintre acestea. Deci, dacă vă gândiți la ele ca natură de creștere de pe părțile laterale, gândiți-vă cum vă apropiați mijloc, vrei ca asta. Deci, dacă ai fost pe fiecare parte a de mijloc, și avem ca 5 și 7. Atunci când le adăugați împreună tine primi 12, împărțiți de 2, este de 6. Uneori este greu să explica de ce functioneaza, dar dacă lucrați prin un exemplu uneori, aceasta va ajuta să îți dai seama dacă ar trebui să fie de plus sau minus. Da. STUDENT: [inaudibil] exact în mijloc dacă au avut un caz în care există o mulțime de numere mai mici și ca un număr mare? INSTRUCTOR: Deci, tot ce ai nevoie este mijlocul matrice. Deci, dacă ați avut o grămadă de numere mici și apoi un număr cu adevărat mare la sfârșitul anului, nu contează. Tot ce contează e că acestea sunt sortate, doar vrea să se uite la mijlocul matrice pentru că ești încă retezarea problema în jumătate. Rece. Deci, acum că avem de mijloc, ce facem mai departe? STUDENT: Compara. INSTRUCTOR: comparare. Deci, compara mijloc de value_wanted. Rece. Deci, vedeți aici avem această valoare vrem aici. Amintiți-vă acest lucru este un tablou. Deci mijloc se referă la indicele. Așa că vrem să facem valori de mijloc. Nu uita, dacă doriți pentru a compara, egali duble. Tu faci egal singur ești doar de gând să le retrocedeze, și apoi, desigur, e va fi valoarea dorită. Deci, nu face asta. Deci, vom vedea dacă la valori, la mijloc este egal cu valoarea ne-o dorim. Nu uita aparatul dentar. Dropbox ar trebui să plece. Deci, ce facem in acest caz? Dacă e ceea ce vrem să se întoarcă? Încercăm să spun. STUDENT: Printeaza off. INSTRUCTOR: Ei bine, ne-am Nu doriți să imprimați off. Deci, aceasta este o bool aici, așa că am doresc să se întoarcă adevărat sau fals. Noi spunem, este acest număr o [? RRA? ?] Deci, dacă aceasta este, ne-am întoarce adevărat. Dacă aș putea scrie adevărat. STUDENT: De ce nu te-ai întoarce la zero? INSTRUCTOR: Deci, ai putea a reveni zero, dacă vrei. Dar, în acest caz, deoarece Funcția noastră returnează un bool, avem nevoie pentru a reveni fie adevărat sau fals. STUDENT: Când ești spunând expresie boolean, poți seta egală cu false? Ca și cum dacă vreau să spun, în cazul în care această condiție nu este îndeplinită, așa cum este superior este egal fals. Va înțelege dacă doar a pus false pe de altă parte? INSTRUCTOR: Da. Deci, de fapt, dacă sunteți vreodată să faci ceva ca este superior sau este mai mică, care returnează adevărat sau fals și e stilul de fapt rău pentru să zicem egal este egal cu adevărat sau egali este egal false. Doriți să utilizați acest rezultat la fel de sine ca cecul. Nu ceea ce am vrut. Asta e ceea ce am vrut. Deci, în cazul ceri despre ceva de genul salva aceasta în c. Deci, dacă avem int main (void) și ceva de genul asta. Și aveți dacă este superioară de unele de intrare și ești întreabă dacă poți să faci ceva de genul asta? Dreapta? STUDENT: Am încercat pentru a face o [inaudibil]. Pentru că dacă it's-- INSTRUCTOR: Corect. Deci vrei ca acest lucru să fie fals, nu? STUDENT: Da. INSTRUCTOR: Deci, în acest caz, doriți să-l execute, dacă nu e adevărat. Deci, cool thing faci este acest lucru. Deci, amintiți-vă de exclamare Punct neagă lucrurile? Se spune [inaudibil] nu înseamnă. Deci, dacă ne uităm la doar această parte aici, ai fi spun că se evaluează la fals așa cum doriți să. Nu fals este adevărat ceea ce înseamnă acest lucru ar executa. Asta face sens? STUDENT: Da. INSTRUCTOR: Awesome. OK. Deci, am putea reveni pur și simplu adevărat în acest caz. Deci, acum avem alte două cazuri în acest caz. Care sunt celelalte două cazuri noastre? Să-l în acest fel face. Așa că haideți să începem cu altceva dacă valorile de la centru este mai mică decât valoarea ne-o dorim. Deci, valoarea noastră în mijloc este mai puțin decât valoarea pe care-l căutăm. Deci, care leagă nu- cred ca ne-o dorim pentru a actualiza? Superior sau inferior? De sus? Deci, care parte a șirului vom fi uitat la? STUDENT: mai mică. INSTRUCTOR: Noi mergem să fi uitat la stânga. Deci, dacă mai mică valoare este mai mică. Deci, valoarea ta de mijloc aici este mai mică decât ceea ce ne dorim. Așa că ne-am dori să ia partea dreapta a oferta noastră. Așa că am de gând să actualiza legat nostru mai mic. Deci, vom realocați mai jos noastre. Și ce crezi că ar trebui să fie mai mic? STUDENT: valoarea de mijloc? INSTRUCTOR: Deci value-- de mijloc STUDENT: Plus 1. INSTRUCTOR: --plus 1. Poate cineva sa-mi spui de ce avem că plus 1? STUDENT: [? Nici o valoare?] este mai mult egală cu ea. INSTRUCTOR: Corect. Pentru că știm deja că Valoarea noastră de mijloc nu este egal cu ea și vrem să-l excludă din toate căutările ulterioare. Dacă uitați că plus 1, acest va place buclă pe termen nelimitat. Și veți fi doar prins într-o buclă infinită și apoi veți segfault și lucrurile merg prost. Deci, întotdeauna asigurați-vă că nu ești inclusiv valoarea pe care tocmai ați sa uitat la. Așa că am grijă de asta cu un plus de 1. Deci, acum avem ultima noastră condiție pe care am mereu pentru mai multă siguranță puteți verifica aici, altfel daca valoarea la la mijloc este mai mare decât valoarea ne-o dorim. Asta înseamnă că ne-o dorim jumătatea din stânga. Deci, pe care o vom actualiza? De sus. Și ce este aceasta o va egala? Orientul Mijlociu minus 1, deoarece, Desigur, ne dorim pentru a vă asigura că nu suntem cauta la valoarea de mijloc din nou. Și apoi îl avem. Asta e tot. Asta e tot binar de căutare este. Nu e așa de rău, nu? E ca și cum 10 de linii de cod cu spațiu alb. Deci, foarte puternic, foarte util, vă va fi, fie folosind-o într-una din psets mai târziu. Poate că acest lucru nu unul, ci mai târziu. Deci, să învețe. Place. Acesta vă va trata bine. Deci, are cineva vreo întrebări cu privire căutare binar? Da. STUDENT: Contează dacă n este par sau impar? INSTRUCTOR: Nu. Pentru că l-am aruncat la mijloc ca un int, aceasta se va trunchia doar. Deci, acesta va rămâne un număr întreg și se va în cele din urmă a sorta prin toate. Deci, nu trebuie să vă faceți griji cu privire la asta. Toată lumea bine? Minunat. Rece. Așa că, voi reușit acest lucru. Slideshow. Deci, ca am vorbit despre, știu David a menționat runtime complexitate. Deci, în cel mai bun caz, e doar unul, pe care o numim timp constant. Poate cineva sa-mi spui de ce ar putea fi? Ce tip de scenariu ar presupune asta? Mm-hm. STUDENT: [inaudibil] first-- INSTRUCTOR: Deci, centru fiind prim element care am ajuns, nu? Deci, fie o serie de una sau indiferent de căutăm doar se întâmplă să fie tamponare jart în mijloc. Deci, asta e cel mai bine cazul nostru. Tu nu intrăm în probleme reale, probabil, O să ajungă la [inaudibil] care de multe ori. Ce despre cel mai rău caz nostru? Cel mai rău caz noastra este log n. Și care are de a face cu întregul competențe de două lucru pe care am vorbit despre. Deci, în cel mai rău caz ar însemna care a trebuit să taie matrice jos până când a fost un element de una. Așa că a trebuit să-l taie în jumătate de câte ori este posibil, am putut. De aceea e log n că doar vă păstrați împărțirea la doi. Deci ipoteze, lucruri pe care le Trebuie să știu dacă ești vreodată de gând să utilizeze un binar de căutare. Elementele dvs. trebuie să fie sortate. Ei trebuie să fie sortate, deoarece că e singurul mod în care poate ști dacă sunt în măsură să arunce jumătate din ea. Dacă ați avut acest sac amestecate de numere și spui, OK, am de gând pentru a verifica mijloc Numărul și numărul caut este mai mică decât atât, eu sunt doar de gând pentru a arunca arbitrar pe jumătate. Tu nu ar ști dacă dumneavoastră numere în acel celălalt pe jumătate. Lista dvs. trebuie să fie sortate. De asemenea, acest lucru poate fi merge mai departe un pic, dar ai nevoie de acces aleator. Aveți nevoie pentru a fi în măsură să doar du-te la acest element de mijloc. Dacă trebuie să traverseze prin ceva sau e nevoie de tine masuri suplimentare pentru a ajunge la acel element de mijloc, aceasta nu mai că log n când adăugați mai mult de lucru în ea. Iar acest lucru va face un pic mai mult sens în două săptămâni, dar am doar un fel de a vrut să prefața, voi da o idee de ceea ce este să vină. Dar acestea sunt cele două ipoteze importante de care aveți nevoie pentru o listă binar. Asigurați-vă că este sortate. Asta e unul mare pentru voi chiar acum. Și pe care putem merge în restul felul noastre. Deci, patru bule sorts--, inserție, selecție și îmbinare. Sunt tot felul de rece. În cazul în care voi decide să ia CS 124, veți afla despre tot felul de felul. Si daca esti un fan xkcd, acolo este o cale de benzi desenate foarte misto cum ar fi într-adevăr felul ineficiente, pe care am recomandăm ai de gând să se uite la. Una dintre ele este ca un fel de panică, care este ca, oh nu, întoarce matrice aleatoare. Sistem de închidere. Lasă. Deci, umor geeky este întotdeauna bun. Deci, nimeni nu amintesc natură ca și cum doar o idee generală de modul în care funcționează bule fel. Îți amintești? STUDENT: Da. INSTRUCTOR: Du-te pentru ea. STUDENT: Deci, te duci prin și dacă e mai mare, atunci ai swap două. INSTRUCTOR: Mm-hm. Exact. Deci, doar tu repeta prin. Cameră cu două numere. În cazul în care cea dinainte este mai mare decât cea după aceea, tu doar le schimba, astfel încât în în acest fel toate numerele mai mari balon până spre sfârșitul listei și toate numerele mai mici bule jos. Te-a arăta baieti rece efect de sunet sortare video? E un fel de misto. Deci, așa cum am spus Robert, algoritmul pe care le pas tocmai prin lista, schimbarea valorilor adiacente în cazul în care nu sunt în ordine. Și apoi doar repeta până când nu face nici swap-urilor. Așa că nu-i rău, nu? Deci, avem doar un exemplu repede aici. Deci, acest lucru se întâmplă pentru a sorta le în ordine crescătoare. Așa că atunci când trecem prin primul timp, ne uităm prin opt și șase, evident, nu sunt în ordine, le schimb. Deci, uita-te la următoarea. Opt și patru nu în ordine. A le schimba. Și apoi opt și doi, a le schimba. Acolo mergem. Deci, după prima trecere, tu Știi că numărul dvs. de cea mai mare va fi până la capăt la partea de sus pentru că e doar va fi în mod constant mai mare decât orice altceva și este doar de gând să bule tot drumul până la sfârșit acolo. Are care are sens pentru toată lumea? Rece. Deci, atunci ne uităm la a doua trecere noastră. Șase și patru, comutator. Șase și doi, comutator. Și acum avem câteva lucruri în ordine. Deci, pentru fiecare adversari pe care le face prin întreaga listă noastra, știm că la fel ca că multe numere la sfârșitul va fi fost sortate. Așa că am făcut-o a treia trecere, care este una de swap. Și apoi pe al patrulea nostru trece, avem de zero sloturi. Și așa știm că nostru matrice a fost sortate. Și că este big lucru cu bule fel. Știm că atunci când ne au zero, swap-uri, care înseamnă că tot este în ordine completă. E un fel de modul în care ne verifica. Deci, suntem, de asemenea, de gând să codul bule care sortare, de asemenea, nu este așa de rău. Nici unul dintre acestea sunt chiar atât de rău. Știu că poate părea un pic înfricoșător. Știu că atunci când am luat clasa, chiar și atunci când am învăța clasa de prima dată anul trecut, Am fost cum ar fi, cum fac asta? Se face sens în teorie, dar cum facem de fapt acest lucru? Motiv pentru care eu, de asemenea, vreau sa merg prin cod cu voi aici. Deci, am un pseudocod pentru voi de data asta. Deci, chiar a păstra acest lucru în minte ca suntem pe cale de tranziție de peste. Deci avem ceva contra că ține evidența operațiunilor de swap noastre, pentru că avem nevoie să ne asigurăm că suntem verifica acest lucru. Și am repeta pentru întreaga rețea, așa cum ne-am facut cu acest exemplu. Dacă elementul înainte este mai mare decât elementul după ce, unde suntem la, le schimba și ne-am incrementa nostru contor pentru că de îndată ce vom schimba, Dorim să contra noastră știe că. Orice întrebări acolo? Ceva pare amuzant aici. STUDENT: Nu setați contorul la zero de fiecare dată când trece prin bucla? Nu-ți continui înapoi la zero de fiecare dată? INSTRUCTOR: Nu neapărat. Deci, ce se întâmplă este că mergem pe aici. Deci în timp ce, amintiți-vă, aceasta va executa o dată, fără a eșua. Deci, se va seta contra egale cu zero, apoi se va repeta prin. După cum se reiterează prin, acesta va fi actualizat contra. După cum se actualizează contra, atunci când este făcut, atunci când este atins la sfârșitul matrice, dacă lista noastră nu a fost sortate, contor va au fost actualizate. Deci, atunci se verifică starea și-l spune, OK, este contra mai mare decât zero. În cazul în care este, o fac din nou. Doriți să resetați, astfel încât, atunci când du-te prin, contra este egală cu zero. Dacă te duci printr-o sortat matrice, nu se schimbă nimic, aceasta nu reușește, și tu a reveni lista sortată. Are care face sens? STUDENT: S-ar putea într-un pic. INSTRUCTOR: OK. Dacă există orice altă Întrebarea care apare. Da. STUDENT: Ce ar fi funcția fie pentru schimbarea elementelor? INSTRUCTOR: Deci, putem scrie de fapt că dacă vom chiar acum. Rece. Deci, pe această notă, Alison se întâmplă pentru a comuta înapoi la aparatul. O să fie distractiv. Și avem frumos nostru bubble sort lucru aici. Așa că am făcut-o deja cu bicicleta prin matrice. Avem swap-uri noastre că sunt egale cu zero. Așa că vrem să schimb adiacent Elemente dacă sunt în ordine. Deci, primul lucru pe care trebuie să nu se repeta prin oferta noastră. Deci, cum crezi că s-ar putea itera prin oferta noastră? Avem pentru și i este egal cu 0. Ne dorim i să fie mai puțin decât n minus 1 minus k. Și vă voi explica că într-o secundă. Deci, aceasta este o optimizare aici în cazul în care, amintesc cum am spus, după fiecare trecere prin WE matrice știu că orice e on-- Deci, după o pasă noi știu că acest lucru este sortata. După două treceri știm că toate acestea sunt sortate. După trei treceri noi știu că e sortate. Deci, modul în care am iterarea prin matrice de aici, este este asigurându-vă că pentru a merge numai prin ceea ce știm este nesortate. OK? Asta e doar o optimizare. Ai putea scrie naivitate doar iterarea prin tot, ar fi nevoie de doar mai mult. Cu această patru buclă este doar o optimizare frumos pentru că știm că, după fiecare complet repetare prin matrice de aici, ca fiecare buclă click aici, știm că unul din aceste elemente vor fi sortate la sfârșitul anului. Deci, noi nu trebuie să vă faceți griji cu privire la acestea. Are care are sens pentru toată lumea? Că truc pic rece? Deci, în acest caz, în cazul în care suntem iterarea prin, știm că vrem să verificăm dacă matrice n și n plus 1 sunt în ordine. OK. Deci, aici e pseudocod. Ne dorim să verificăm dacă matrice n și n plus 1 sunt în ordine. Deci, ceea ce am putea avea acolo? O să fie ceva condiționată. Acesta va fi o dacă. STUDENT: Dacă matrice n este mai puțin de matrice n plus 1. INSTRUCTOR: Mm-hm. Ei bine, mai mică sau mai mare de. STUDENT: Mai mare. Apoi ne-am dori pentru a le schimba. Exact. Deci, acum ajungem la ceea ce este mecanism pentru schimbarea ei? Așa că am trecut prin acest scurt, un tip de funcție de swap săptămâna trecută. Are cineva aminte cum a mers? Astfel încât nu putem să le realoca doar, nu? Pentru că unul dintre ei se va pierde. Dacă am spus A este egal cu B, apoi B este egal cu A, toate dintr-o dată atât de ei sunt doar egal cu B. Deci, ceea ce trebuie să faceți este să ne au o variabilă temporară care este O să dețină una dintre timp ce al nostru suntem în procesul de pompare. Deci, ceea ce avem este că vom avea unele int Temperatura este egal sa-- puteti atribui pentru oricare o doriți, doar asigurați-vă că țineți evidența it-- astfel încât în ​​acest caz, am de gând să atribui o matrice de n plus 1. Așa că o să dețină orice Valoarea este aceea că al doilea bloc care ne uitam la. Și atunci ce putem face este să putem merge înainte și matrice realocați n plus 1, pentru că noi știm au ca valoarea stocată. Aceasta este, de asemenea, una din marile lucruri-- Nu știu dacă vreunul dintre voi a avut probleme în cazul în care, dacă trece doi de linii de cod dintr-o dată lucrurile s-au. Comanda este foarte important în CS. Deci, asigurați-vă că diagrama lucrurile dacă este posibil cu privire la ceea ce se întâmplă de fapt. Deci, acum vom realocați matrice n plus 1, pentru că noi știm au ca valoarea stocată. Și putem atribui care a matrice n sau, în acest caz matrice i. Prea multe variabile. OK. Matrice Deci, acum ne-am realocat i plus 1 pentru a egala ceea ce este în matrice i. Și acum ne putem întoarce și atribui matrice i pentru ce? Oricine? STUDENT: 10. INSTRUCTOR: 10. Exact. Și un ultim lucru. Dacă l-am schimbat acum, Ce trebuie să facem? Care este singurul lucru care ne va spune dacă am termina vreodată acest program? Ce ne spune că noi au o listă sortate? Dacă nu vom efectua nicio swap-uri, nu? În cazul în care swap-uri este egal cu zero, la sfârșitul acestei. Deci, ori de câte ori a efectua un schimb, așa cum am doar a facut aici, vrem să actualizați swap-uri. Și știu că a fost o întrebare mai devreme despre poti tine utilizați zero sau unu loc de adevărat sau fals. Și asta e ceea ce face acest lucru aici. Deci, aceasta spune că dacă nu swap-urilor. Deci, dacă swap-uri este zero, pe care am este-- mereu primi adevăruri mei și falses mele amestecat. Ne dorim să evaluăm pentru adevărat și nu e. Deci, dacă e zero, atunci e fals. Dacă îl neagă cu o [? bang-ului?] devine adevărat. Deci, atunci această linie se execută. Adevăruri și false și zero-uri și cele primi nebun. Doar dacă mergi încet prin ea se va face sens. Dar asta e ceea ce acest mic bit de cod aici nu. Deci, aceasta verifică am făcut nici un swap-urilor. Deci, dacă e ceva în afară de zero, aceasta va fi falsă și totul este O să execute din nou. Rece? STUDENT: Ce face pauză? INSTRUCTOR: Break doar te rupe din bucla. Deci, în acest caz, ar la fel ca termina programul și v-ar doar Lista ta sortate. STUDENT: Amazing. INSTRUCTOR: Îmi pare rău? STUDENT: Pentru ca anterior noi second scris 1 pe scris la zero să prezinte că, dacă care va funcționa sau nu. INSTRUCTOR: Da. Astfel încât să puteți returna zero sau 1. În acest caz, pentru că noi nu suntem de fapt a face ceva cu funcția, vrem doar pentru a rupe. Nu ne pasă cu adevărat despre el. De asemenea, este bine dacă frână este folosit pentru izbucnirii de patru bucle sau condiții care nu doriți să păstrați de executare. Este doar te scoate din ele. E un pic de lucru nuanță. Mă simt ca și cum nu există o mulțime de ondularea de mână, ca și cum veți afla despre acest curând. Dar veți afla despre acest curând. Promit. OK. Deci, nu toată lumea ajunge cu bule fel? Nu prea rău. Repeta prin, lucruri de swap folosind o variabila temp, și suntem gata acolo? Rece. Minunat. OK. Înapoi la PowerPoint. Orice întrebări, în general, despre acestea până acum? Rece. Mm-hm. STUDENT: [inaudibil] int principal de obicei. Nu trebuie să aveți că pentru acest lucru? INSTRUCTOR: Deci, am fost doar cauți doar la algoritmul actual de sortare. Dacă ați avea în ca un program mai mare, ai avea o undeva principal int. În funcție de unde folosesc acest algoritm, ar determina ceea ce este fiind returnat de aceasta. Dar pentru cazul nostru, suntem strict uita la modul în care face acest lucru de fapt itera printr-o serie. Deci, noi nu vă faceți griji despre asta. Așa că am vorbit despre cel mai bun caz și cele mai grave scenarii pentru căutare binare. Deci, este de asemenea important să se facă că pentru fiecare dintre tipurile noastre. Deci, ce credeți că este cel mai rău caz de execuție de bule fel? Voi aminti? STUDENT: N minus 1. INSTRUCTOR: N minus 1. Asta înseamnă că există n minus 1 comparatii. Deci, un singur lucru pentru a realiza este că pe prima iterație, ne trece prin, vom compara acestea two-- așa că e 1. Acestea două, trei, patru. Deci, după o iterație noi au deja patru comparații. Când vorbesc despre execuție și n. N reprezintă numărul de comparații în funcție de cât de multe elemente avem. OK? Așa că am trece prin, avem patru. Data viitoare când știi că nu trebuie să aibă grijă de asta. Vom compara aceste două, aceste două, acestea două, iar dacă nu am avut că de optimizare cu patru bucla pe care am scris, v-ar fi compararea aici oricum. Deci, va trebui să alerga prin matrice și de a face comparații n n ori, pentru că de fiecare dată ne alerga prin ea am un fel un lucru. Și de fiecare dată când trec prin matrice, facem n comparații. Deci, de execuție noastră pentru acest lucru este de fapt n patrat, care este mult mai rău în nostru jurnal final pentru că înseamnă dacă am fi avut patru miliarde de elemente, e O să ne ia patru miliarde pătrat în loc de 32. Deci, nu cel mai bun Runtime, dar pentru unele lucruri, știi, dacă ești în un anumit interval de elemente balon fel poate fi bine utilizat. OK. Și acum ce este cel mai bun Runtime caz? STUDENT: Zero? Sau 1? INSTRUCTOR: Deci, 1 ar fie o comparație. Dreapta. STUDENT: N minus 1? INSTRUCTOR: Deci, da. Deci, n minus 1. Ori de câte ori aveți un concept ca n minus 1, avem tendința de a doar o picătură off și spunem doar n pentru că ai pentru a compara fiecare dintre these-- fiecare pereche. Așa că ar fi n minus 1, pe care noi am spune pur și simplu este de aproximativ n. Când ai de a face cu timpul rulării, totul este în aproximate. Atâta timp cât exponentul este corect, ești destul de bun. Asta e modul în care avem de a face cu ea. Așa că cel mai bun caz este n, care înseamnă că lista este deja sortate, și tot ce faceți este să rulați prin și verificați că este sortate. Rece. Bine. Deci, după cum vedeți aici, Trebuie doar unele mai multe grafice. Deci, n pătrat. Fun. Mult mai rău decât n așa cum vom vedea, și mult, mult mai rău decât jurnal 2n. Și atunci veți obține, de asemenea, în busteni jurnal. Și vă voi lua 124, intri în cum ar fi stele din jurnal, care este ca un nebun. Deci, dacă sunteți interesat, căutare jurnal stele. E un fel de distracție. Deci avem acest mare grafic. Doar un heads-up, aceasta o diagramă minunat de a avea pentru termen mediu, deoarece noi mult timp să vă întreb aceste subtiaza. Deci, doar un heads-up, avea acest lucru asupra ta pe termen mediu pe foaia de ieftin frumos acolo. Așa că ne-am uitat la balon fel. În cel mai rău caz, n patrat, cel mai bun caz, n. Și ne vom uita la ceilalți. Și, după cum puteți vedea, singurul unul care într-adevăr bine este un fel de îmbinare, pe care o vom primi în ce. Deci, vom merge la următor un fel de selecție here--. Are cineva aminte cum selecție a lucrat fel? Du-te pentru ea. STUDENT: du-te Practic prin un ordin și de a crea o listă nouă. Și, la fel cum te inscrie elemente in, le-a pus în locul potrivit în noua listă. INSTRUCTOR: Așa că sunetele mai mult ca inserție fel. Dar ești foarte aproape. Sunt foarte asemănătoare. Chiar și eu să-i amestecat uneori. Înainte de această secțiune am fost ca, așteptați. OK. Deci, ce vrei să face este de selecție fel, modul în care vă puteți gândi cu privire la aceasta și modul în care Am asigurați-vă că nu încercați să obțineți le-a amestecat sus, este trece printr- și se selectează cel mai mic număr și-l pune că la începutul listei. Acesta se swap-uri cu acel prim loc. Ei au de fapt un exemplu pentru mine. Minunat. Deci, doar un mod de a gândi de selecție it-- sortare, selectați cea mai mică valoare. Și am de gând să executa printr-un exemplu care cred ca va ajuta pentru că Cred vizuale ajută întotdeauna. Deci, să începem cu ceva care este complet nesortate. Red va fi nesortate, verde vor fi sortate. Se va face toate sens într-o secundă. Așa că am trece prin noi și repeta de la început până la sfârșit. Și noi spunem, OK, 2 este numărul nostru mai mic. Așa că am de gând să ia 2 și noi te vom pentru al muta la partea din față a oferta noastră pentru că este cel mai mic număr avem. Deci, asta e ceea ce acest lucru este aici. E doar de gând să schimb cei doi. Așa că acum am o sortate parte și o parte nesortate. Și ceea ce e bine să-și amintească despre selecție de sortare Este suntem doar selectând din partea nesortat. Partea de sortat tocmai te lase în pace. Mm-hm? STUDENT: Cum se știe ce este cel mai mic fără comparandu-l pentru fiecare altă valoare în matrice. INSTRUCTOR: Aceasta nu se compara. Ne place omise. Acest lucru este pur și simplu globală generală. Da. Când ne-am scrie codul eu sunt sigur că vei fi mai mulțumiți. Dar magazin acest prim ca element mai mic. Tu comparati si tu spune, OK, e mai mic? Da. Păstrați-l. Aici este mai mic? Nu? Aceasta este cea mai mică tău, realocați-l la valoarea ta. Și vei fi mult mai fericit când vom merge prin cod. Așa că am trece prin, l-am schimb, astfel încât atunci ne uităm la această porțiune nesortate. Deci, vom selecta trei. Vom să-l puneți pe la sfârșitul porțiunii noastre sortat. Și suntem doar de gând să continuăm să facem că, făcând asta, și de a face asta. Deci, aceasta este un fel nostru de pseudocod aici. Vom cod aici într-o secundă. Dar doar ceva de mers pe jos printr-un nivel ridicat. Vei merge de la i este egal cu 0 la n minus 2. Asta e un alt optimizare. Nu vă faceți griji prea mult despre asta. Deci, după cum spuneai. Așa cum Iacov a spus, cum putem ține evidența a ceea ce minim nostru este? De unde știm? Trebuie să comparăm totul în lista noastră. Deci, minim i egal. E doar că în acest caz indicele de valoare noastre minim. Deci, atunci se va repeta prin și merge de la j i plus 1 egal. Deci, noi știm deja că asta e prima noastră elementului. Noi nu trebuie să-l compara cu ea însăși. Deci, vom începe o comparatie cu alta una care este de ce este i plus 1 la n minus 1, care este capăt al șirului acolo. Și am spus că dacă matrice la j este mai mică de matrice min, apoi ne-am realocați în cazul în care Indicii noastre minime sunt. Și dacă min nu este egal cu i, ca în cazul în care ne-am intors aici. Deci, ca atunci când am făcut prima dată această unul. În acest caz, se va incepe de la zero, aceasta s-ar sfârși prin a fi doi. Deci, min nu ar fi egal i în cele din urmă. Care ne permite să știu că avem nevoie pentru a le schimba. Mă simt ca un exemplu concret va ajuta mult mai mult decât aceasta. Așa că vom cod asta cu voi chiar acum și cred că va fi mai bine. Felul tendința de a lucra în acest fel, în care este de multe ori mai bine doar pentru a le vedea. Deci, ceea ce vrem să facem este ne-o dorim în primul rând cel mai mic elementul în poziția sa în matrice. Exact ceea ce Jacob spunea. Aveți nevoie pentru a stoca într-un fel. Deci, vom începe aici iterarea peste matrice. Noi o să spun că este nostru în primul rând o doar pentru a începe cu. Deci, vom avea int cel mai mic este egal cu matrice la i. Deci, un singur lucru pentru a observa, fiecare de data asta buclă executa, suntem incepand cu un pas mai departe de-a lungul. Când începem ne uităm la asta. Data viitoare vom repeta prin, suntem incepand de la acesta și o valoare mai mică nostru atribuire. Deci, este foarte similar cu bule de sortare unde știm că, după o pasă, acest ultim element este sortata. Cu selecție de sortare, e exact opusul. La fiecare trecere, știm că primul este sortat. După a doua trecere, al doilea va fi sortate. Și, după cum ați văzut cu exemple de diapozitive, porțiune nostru sortate doar continuă să crească. Deci, prin stabilirea una noastră cel mai mic pentru tablouri i, tot ce face este constricția ce ne uităm la astfel ca pentru a reduce numărul comparațiilor facem. Asta face sens pentru toată lumea? Ai nevoie de mine pentru a rula prin care din nou, mai lent sau cu alte cuvinte? Sunt fericit să. OK. Deci, suntem stochează Valoarea la acest moment, dar ne-am dori, de asemenea pentru a stoca index. Deci, vom stoca Poziția de cel mai mic unul, care este doar de gând să fi i. Deci, acum, Jacob este îndeplinită. Avem lucruri stocate. Și acum trebuie să privim prin partea nesortate din matrice. Deci, în acest caz, acest ar fi nesortate nostru. Acest lucru este i. OK. Deci, ce vom face va fi pentru o buclă. Ori de câte ori aveți nevoie pentru a itera printr-o serie, mintea ta ar putea merge la o buclă. Deci, pentru a putea int k equals-- ce credem noi k este de gând să egaleze pentru a începe cu? Aceasta este ceea ce ne-am stabilit ca cel mai mic noastre valoare și vrem să-l comparare. Ce vrem să-l compara cu? O să fie acesta următorul, nu? Așa că vrem k să fie inițializat la i plus 1 pentru a începe. Și ne dorim k în acest caz deja dimensiune stocate aici, astfel încât să putem folosi doar dimensiunea. Dimensiunea fiind dimensiunea matricii. Și vrem doar să actualizare k de unul de fiecare dată. Rece. Deci, acum trebuie să găsim cel mai mic element aici. Deci, dacă am repeta prin, noi vreau să spun, dacă matrice la k este mai mică decât cea mai mică value-- nostru acest lucru este în cazul în care suntem de fapt urmărirea a ceea ce este cel mai mic here-- apoi ne-am dori să realocați ce valoare mai mică nostru este. Acest lucru înseamnă că, oh, suntem iterarea pe aici. Oricare ar fi valoare nu este aici este nu mai mic lucru nostru. Noi nu-l vreau. Vrem să le retrocedeze. Deci, dacă suntem o realocare, ceea ce face credeți că ar putea fi în acest cod aici? Vrem să realocați cel mai mic și poziția. Deci, ceea ce este cea mai mică acum? STUDENT: Array k. INSTRUCTOR: Array k. Și care este poziția acum? Ce-i indicii de Valoarea noastră mai mic? E doar k. Deci, k matrice, k, se potrivesc. Așa că am vrut să realocați asta. Și apoi după ce am găsit cel mai mic noastre, astfel încât la sfârșitul acestei pentru buclă aici am gasit ceea ce cel mai mic noastre Valoarea este, deci ne-am l schimb. În acest caz, cum ar fi spus noastră cea mai mică valoare nu este aici. Aceasta este valoarea noastră mai mic. Vrem doar să-l schimb aici, ceea ce este ce această funcție schimb în partea de jos făcut-o, pe care tocmai am scris în sus împreună în urmă cu câteva minute. Deci, ar trebui să arate familiar. Și atunci se va repeta doar prin până când ajunge la capăt până la capăt, ceea ce înseamnă că avea zero elemente care sunt nesortate și orice altceva a fost sortate. Face sens? Un pic mai concret? Codul de ajutor? STUDENT: Pentru o dimensiune, pe care nu într-adevăr defini sau schimba-l, cum nu-l știți? INSTRUCTOR: Deci, un singur lucru a observa aici este dimensiunea int. Așa că am să spui că în acest fel sort-- este o funcție în acest case-- e selecție fel, e trecut în cu funcția. Deci, în cazul în care nu a fost trecut in, v-ar face ceva ca și cu lungimea unui array sau v-ar repeta prin pentru a găsi lungimea. Ci pentru că e trecut în, putem doar să-l folosească. Trebuie doar presupune că utilizatorul ți-a dat o dimensiune validă care reprezintă de fapt o dimensiune de matrice dumneavoastră. Rece? Dacă voi avea probleme cu acestea sau vrei mai multe practici de codificare felul pe cont propriu, ar trebui Mergi la study.cs50. Este un instrument. Ei au un verificator care puteți scrie de fapt. Ei fac pseudocod. Ei au mai multe videoclipuri și diapozitive inclusiv cele pe care le folosesc aici. Deci, dacă sunteți încă simți un pic neclare, încercați asta. Ca de obicei, vin să vorbească cu mine, de asemenea. Întrebare? STUDENT: Vrei să spui că mărime este definit ca mai înainte? INSTRUCTOR: Da. Dimensiunea este definit ca mai înainte în sus aici, în declarația funcției. Astfel încât să se presupună că aceasta a fost adoptată în de către utilizator, precum și din motive de simplificare, vom presupune că utilizator ne-a dat dimensiunea corectă. Rece. Așa că e de selecție fel. Băieți, știu că am învățat foarte mult astăzi. E un dens de date pentru secțiunea. Deci, cu asta, vom pentru a merge la inserarea fel. OK. Deci, înainte de asta trebuie să facem Analiza noastră rulare aici. Deci, în cel mai bun caz, acordată de când ți-am arătat tabelul I deja un fel de dat degajeze. Dar cel mai bun la rulare caz, ce credem noi? Totul sortate. N pătrat. Oricine are o explicație de ce crezi? STUDENT: Ești compararea through-- INSTRUCTOR: Corect. Ești compararea prin intermediul. La fiecare iterație, chiar dacă suntem decrementare aceasta de unul, aveți în continuare căutarea prin totul pentru a găsi cel mai mic. Deci, chiar dacă valoarea cea mai mică este aici, la început, aveți în continuare o comparare împotriva orice altceva pentru a vă asigura că este cel mai mic lucru. Deci, veți termina care trece prin aproximativ de n ori pătrat. Bine. Si ceea ce este cel mai rau caz? De asemenea, n patrat pentru că ai de gând pentru a face aceeași procedură. Deci, în acest caz, de selecție are ceva de sortare pe care o numim, de asemenea, de execuție de așteptat,. Deci, în celelalte, doar noi știm limitele superioare și inferioare. În funcție de cât de nebun nostru Lista este sau cât de nesortate este, acestea variază între n sau n patrat. Nu știm. Dar, pentru că de selecție fel are aceeași cel mai rău și cel mai bun caz, care ne spune că indiferent de ce tip de intrare noi au, fie că este vorba complet sortate sau complet inversa sortate, e de gând să ia aceeași cantitate de timp. Deci, în acest caz, dacă amintiți-vă de la masa noastră, a avut de fapt o valoare care aceste două tipuri nu au, care este de așteptat rulare. Deci, noi știm că ori de câte ori fugim de selecție fel, este garantat de rula un timp n pătrat. Nu există nici o variabilitate acolo. E doar de așteptat. Și, din nou, dacă vrei să înveți mai mult, ia CS 124 in primavara. Bine. Am văzut asta. Rece. Un fel atât de inserție. Și eu, probabil, va să ardă prin aceasta. Nu voi avea voi l cod. Vom merge pe jos doar prin ea. Deci, inserare fel este un fel de similar cu selecție de sortare în care avem atât un nesortate și sortate parte din matrice. Dar ceea ce este diferit este faptul că așa cum am trece prin unul câte unul, vom lua doar orice număr este următorul în nesortate noastră, și-l rezolve corect în oferta noastră sortat. Va face mai mult sens cu un exemplu. Deci, totul incepe ca nesortate, la fel ca și cu selecție de sortare. Și vom sorta acest lucru în ordine crescătoare așa cum am fost. Deci, la prima noastră trecere vom lua prima valoare și spunem, OK, esti acum într-o listă de unul singur. Pentru că vă aflați într-o listă de unul singur, pe care sunt sortate. Felicitări pentru a fi prim element în această matrice. Te sortate deja toate pe cont propriu. Așa că acum am o sortate și o serie nesortate. Deci, acum vom lua primul. Ce se întâmplă între aici și aici este că noi spunem, OK, ne vom uita la primă valoare de oferta noastră nesortate și vom intrare-l la ei locul corect în matrice sortat. Deci, ceea ce facem este să luăm 5 și spunem, OK, 5 este mai mare de 3, asa ca am doar o introduce drept la dreapta de care. Suntem bine. Deci, atunci vom merge pe una noastră viitoare. Și vom lua 2. Noi spunem, OK, 2 este mai puțin decât 3, astfel știm că trebuie să fie la fata de lista noastră de acum. Deci, ceea ce facem este ne împinge 3 și 5 jos și ne-am muta 2 în care primul fantă. Deci, noi doar îl introduceți în locul corect ar trebui să fie. Apoi ne uităm la noastre un viitor, și spunem 6. OK, 6 este mai mare decât totul în oferta noastră sortat, asa ca am doar o eticheta pe până la capăt. Și apoi ne uităm la 4. 4 este mai mic de 6, este mai puțin decât 5, dar este mai mare de 3. Așa că ne-am introduceți-l direct în mijloc între 3 și 5. Deci, pentru a face ca un pic ceva mai concret, aici este un fel de idee de ceea ce sa întâmplat. Deci, pentru fiecare element nesortate, ne-am determina în cazul în care în porțiunea de sortat ea este. Deci, păstrând în minte sortate și nesortate, avem de a traversa prin și figura de unde se potrivește în tabloul sortat. Și l-am introduce prin transferarea Elemente de la dreapta în jos. Și apoi ne-am păstra iterarea prin până la noi au o listă sortate complet în cazul în care nesortate este acum la zero și sortat preia toate elementele de pe lista noastră. Așa că, din nou, pentru a face lucrurile chiar mai concret, avem pseudocod. Deci, practic pentru i este egal cu 0 până la n minus 1, asta e doar lungimea de oferta noastră. Avem un element care este egală cu prima matrice sau primele indicii. Ne-am propus j egală cu asta. Deci, în timp ce j este mai mare decât zero și matrice, j minus 1 este mai mare decât Element, deci tot ce face este de a face sigur că j dumneavoastră reprezintă într-adevăr porțiunea nesortate de matrice. Deci, în timp ce există încă lucruri pentru a sorta și j minus un este-- ce este elementul ei? J nu a fost niciodată definit aici. E un fel de enervant. OK. Oricum. Deci, j minus 1, ești verificare elementul în fața sa. Vrei să spui, OK, este elementul înainte ori de câte ori am am-- să de fapt, trage asta. Așa că haideți să spun acest lucru este ca pe a doua trecere noastră. Deci, eu o să fie egal la 1, ceea ce este aici. Deci, eu va fi egal cu 1. Acest lucru ar fi 2, 4, 5, 6, 7. Bine. Deci, elementul nostru în acest caz va fi egal cu 4. Și avem ceva j care este va fi egal cu 1. Oh, J este decrementarea. Asta e ceea ce este. Deci, j este egal cu i, deci ce e asta spune este că, așa cum am merge mai departe, suntem doar asigurându-vă că nu suntem pe indexarea acest fel, atunci când noi încercăm pentru a introduce lucrurile în lista noastră sortate. Deci, atunci când j este egal cu 1 în acest caz și matrice j minus Unu atât de matrice j minus 1 este 2 în acest case-- dacă e mai mare decât elementul, atunci toate acestea se face se schimbă lucrurile în jos. Deci, în acest caz, matrice j minus una ar fi matrice de zero, care este de 2. 2 nu este mai mare de 4, deci acest lucru nu executa. Deci, schimbarea nu se mișcă în jos. Ce este acest lucru nu aici este doar mutarea matrice ta sortat jos. În acest caz, de fapt, ne-am ar putea do-- să facem acest 3. Deci, dacă vrem să umblăm prin cu acest exemplu, suntem acum aici. Aceasta este sortat. Acest lucru este nesortate. Rece? Deci i este egal cu 2, deci elementul nostru este egal cu 3. Și j noastră este egal cu 2. Așa că ne-am uita prin și noi spune, OK, este matrice j minus una mai mare decât elementul care ne uitam la? Iar răspunsul este da, corect? 4 este mai mare de 3 și j este 2, astfel încât acest cod execută. Și acum ce facem o serie de 2, deci chiar aici, le schimb. Deci, noi spunem doar, OK, matrice la 2 este acum va fi de 3. Și j este de gând să egaleze j minus 1, care este 1. Asta e oribil, dar voi prins ideea. J este acum egal cu 1. Și matrice j este doar de gând să fie egală cu elementul nostru, care a fost de 4. Am șters ceva ce nu-mi trebuie au sau ceva miswrote, dar voi prins ideea. Se muta la n. Și apoi, dacă acest lucru ar fi, ar fi bucla din nou și s-ar spune, OK, j este 1 acum. Și matrice j minus 1 este acum 2. Este mai mică de 2 elementul nostru? Nu? Asta înseamnă că ne-am introduce acest element în locul corect în oferta noastră sortat. Atunci putem lua acest lucru și spunem, OK, oferta noastră este sortat aici. Și ar fi nevoie de acest număr de 6 și de a fi cum ar fi, OK, este de 6 la mai puțin de acest număr? Nu? Rece. Suntem bine. Fă-o din nou. Noi spunem 7. Este mai puțin de 7 la sfârșitul din oferta noastră sortate? Nu. Deci, suntem bine. Deci, acest lucru ar fi sortate. Practic toate acest lucru nu Este o spune decolare primul element al matrice dumneavoastră nesortate, da seama unde se duce în matrice ta sortat. Și aceasta are doar grijă de swap-uri pentru a face asta. Ești practic doar schimbarea până când este în locul potrivit. Imaginea vizuală este că ești în mișcare totul de a face asta. Deci e ca și cum jumătate bubble sort-esque. Check out studiu 50. Am foarte recomandăm să încercați pentru a coda acest lucru pe cont propriu. Dacă aveți probleme sau doriți să a se vedea mostre de cod pentru un fel de introducere, vă rog să-mi spuneți. Eu sunt mereu în jurul valorii de. Deci, cel mai rău caz de execuție și cel mai bun caz rulare. După cum ați văzut tip din tabelul I deja ți-a arătat, e atât n pătrat și n. Deci, un fel de a merge în afara a ceea ce am discutat despre felul cu noastre anterioare, cel mai rău rulare caz este că, dacă este complet nesortate, trebuie să ne comparăm toate aceste n ori. Noi facem o mulțime de comparații pentru că dacă e în ordine inversă, vom spune, OK, acest este același, acest lucru este bun, iar acesta va trebui să fie comparate față de prima care urmează să fie mutat înapoi. Și cum vom ajunge spre coada, avem pentru a compara, compara, și compara împotriva a tot. Deci, se termină prin a fi aproximativ n pătrat. Dacă este corect, atunci spune, OK, 2, ești bun. 3, esti față de 2. Esti bun. 4, pe care tocmai ați compara cu coada. Esti bun. 6, compara cu coada, ești bine. Deci, pentru fiecare punct în cazul în care este deja sortate, faci o comparație. Deci, e doar n. Și pentru că avem o execuție cel mai bun caz de n și un caz de execuție cel mai rău de n- pătrat, nu avem nici o execuție de așteptat,. Este doar depinde de haos de pe lista noastră de acolo. Și din nou, o altă grafic și o altă masă. Deci, diferențele dintre soiuri. Mă duc să briza prin, eu simt ca am vorbit pe larg cu privire la modul în care acestea tot felul de varia și link-ul împreună. Deci, Merge sort este ultima Eu vă va plictisesc cu voi. Avem o imagine destul de colorat. Deci, îmbinare fel este un algoritm recursiv. Deci, nu știu voi ce o funcție recursivă este? Oricine vrea să spun? Vrei să încerci? Deci, o functie recursiva este doar o funcție care se numește. Deci, dacă voi sunt familiarizați cu șirul lui Fibonacci, care este considerat recursiv pentru că luați cele două precedent și adăugați-le împreună pentru a obține o următoare. Așa că recursiv, întotdeauna mă gândesc de recursivitate ca ca o spirală deci esti la fel ca în spirală în jos în ea. Dar e doar o funcție care se numește. Și, de fapt, foarte repede am vă pot arăta cum arată. Așa că recursiv aici, dacă ne uităm, aceasta este modul recursiv pentru a rezuma pe o matrice. Deci, tot ceea ce facem este avem funcția sumă suma care ia o dimensiune și o serie. Și dacă observați, dimensiune diminuări de către o de fiecare dată. Și tot ce face este dacă x este egal cu zero-- astfel încât în ​​cazul în care dimensiunea de matrice este egal cu zero-- revine la zero. În caz contrar, rezumă acest ultimul element al tabloului, și apoi ia o sumă de restul de matrice. Deci, e doar o rupere jos problemă ce mai mici. Pe scurt, recursivitate, funcție care se numește. Dacă asta e tot ce ai de acest lucru, asta e ceea ce o functie recursiva este. Dacă luați 51, veți primi foarte, foarte confortabil cu recursivitate. E foarte misto. Ea a făcut sens la fel ca 3 AM o noapte afară. Și am fost ca, de ce niciodată nu am folosi acest lucru? Deci, pentru îmbinare fel, practic ceea ce va face este că e O să-l rupe în jos și-l în jos până când este elemente doar de o persoană. Singurele elemente sunt ușor pentru a sorta. Vedem că. Dacă aveți un element, e deja luate în considerare sortat. Deci, pe o intrare de n elemente, dacă n este mai mică de 2, a reveni doar pentru că mijloacele e 0 sau 1 după cum am văzut. Acestea sunt considerate elemente sortate. În caz contrar, rupe în două. Sortare în prima jumătate a anului, sortare a doua jumătate, iar apoi îmbinați-le împreună. De ce se numește îmbinare fel. Deci avem aici ne vom sorta aceste. Așa că am ține cu ei până la dimensiunea matrice este 1. Deci, atunci când este 1, doar ne vom întoarce pentru că aceasta este o matrice sortat, și aceasta este o matrice sortat, și asta e o gamă sortat, suntem sortate toți. Deci, atunci ceea ce facem este noi începe comasarea lor împreună. Deci, modul în care se poate cred despre fuziune este doar să eliminați mai mici număr de fiecare dintre sub matricelor și doar adăuga la matrice a apărut. Deci, dacă te uiți aici, când ne-am aceste seturi avem 4, 6, și 1. Când vrem să fuzioneze acestora, ne uităm la aceste primele două și spunem, OK, 1 este mai mic, merge în față. 4 și 6, nu e nimic pentru comparare l, doar eticheta de pe până la capăt. Când ne-am combina aceste două, ne-am să ia cea mai mică dintre acestea două, asa ca e 1. Și acum vom lua mai mic de aceste două, așa 2. Micșorează dintre acestea două, trei. Mai mic de aceste două, 4, 5, 6. Deci, esti doar trăgând de pe acestea. Și pentru că am fost sortate în prealabil, trebuie doar un singur Compară de fiecare dată acolo. Deci, mai mult cod aici, reprezentare doar. Deci, tu încep de la mijloc și tu sortare stânga și dreapta și apoi doar să îmbinați cele. Și nu avem cod pentru a intra aici. Dar, din nou, dacă te duci pe studia 50, va fi acolo. În caz contrar, vin să vorbești cu mine dacă ești încă confuz. Deci, lucru misto aici este faptul că cel mai bun caz, cel mai rău caz, și de execuție de așteptat sunt toate în log n, care este mult mai bine decât ne-am văzut pentru restul de felul noastre. Am văzut n patrat și ceea ce suntem de fapt ajunge aici este n log n, care este mare. Uită-te la cât de mult mai bine, care este. O curbă frumos. Deci, mult mai eficient. Daca ai putea vreodată, utilizarea îmbinare fel. Se va economisi timp. Apoi, din nou, așa cum am spus, în cazul în care ești în această regiune mai mic, ea nu face asta de mult de o diferență. Ai până la mii și mii de intrări, vrei cu siguranta un algoritm mai eficient. Și, din nou, masa noastră minunat de toate felul asta voi învățat astăzi. Deci, eu știu că a fost o zi dens. Acest lucru nu este neapărat de gând pentru a vă ajuta cu PSET ta. Dar eu vreau doar să facă o declarație de renunțare această secțiune nu este doar despre psets. Toate acest material este corect joc pentru examenele tale. Și, de asemenea, dacă faci continua cu CS, acestea sunt fundamentale într-adevăr importante care le-ar trebui să știi. Deci, câteva zile va fi o puțin mai mult PSET ajutor, dar câteva săptămâni va fi conținut mult mai real care nu poate părea super- util pentru tine acum, dar îți promit, dacă veți continua pe va fi foarte, foarte util. Deci asta e pentru secțiunea. Jos pentru firul. Am făcut-o într-un minut. Dar acolo te duci. Și voi avea gogoși sau bomboane. Este cineva alergic la ceva, apropo? Ouă și lapte. Deci, gogoși sunt un nu? OK. Bine. Ciocolata nu? Explozii stelare. Starbursts sunt bune. OK. Vom avea Accelerarea săptămâna viitoare atunci. Asta e ceea ce voi primi. Voi avea o săptămână mare. Citește spec ta. Lasă-mă să știu dacă aveți întrebări. PSET două clase ar trebui să fie la tine de joi. Dacă aveți orice întrebări despre cum am sortat ceva sau de ce am clasificate ceva modul în care am a, vă rugăm să mi e-mail, vin să vorbească cu mine. Sunt un pic acest nebun săptămână, dar îți promit Voi răspunde în continuare în termen de 24 de ore. Deci, au o săptămână mare, toată lumea. Mult noroc pe PSET ta.