SPEAKER 1: Hej vsem! Dobrodošli nazaj v oddelku. Tako vesel, da mnogi od vas, tako tu, Vsak, ki je gledal na spletu. Torej, kot je običajno zadnji dobrodošlice. Upam, da ste vsi imeli lepo vikend, poln počitka, sprostitve. Včeraj je bilo lepo ven. Torej, upam, da ste uživali na prostem. 

Torej, najprej nekaj objav. Razvrščanje. Torej, večina od vas bi bilo gotten email mi o vašem Scratch Pset, kakor tudi za razvrščanje Pset 1. Torej, samo nekaj stvari. Bodite prepričani, da uporabite check50 v style50. Ti so mišljeni kot sredstva za vaju, se prepričajte, da ste dobili čim več točk, kot si lahko ne da bi jih po nepotrebnem izgubili. Torej, stvari, kot so stil so zelo pomembni. Bomo vzlet za to. Nekateri od vas morda že opazili, da iz vašega Pset. In check50 je le zelo enostaven način, da se prepričajte, da smo dejansko vrača tisto, kar treba vrne uporabniku, in da je vse, kar je pravilno. 

Na drugi note, poskrbite, da nalaganje stvari v pravo mapo. To naredi življenje samo malo težje če si naložite Pset 2 v Pset 1 ker ko sem prenesti stvari, ne prenesete pravilno. In vem, da je malo deformiranega v sistemu, da se privadite, ampak je super Pazite, čeprav samo za mene, tako da, ko ste dobili e-pošto na podoben 02:00 in sem razvrščanje. Če ne povzroči moram pogledati vsem za vašo Pset. Cool. 

Vem, da je prezgodaj, ampak sem popolnoma si je vzletelo straže esej, ki je zaradi tega v petek, ta moji profesorji so samo všeč, oh yeah. Ne pozabite, da imate esej zaradi petek. Torej, vem, da nihče ne mara razmišljati o tem, kolokviji, vendar vaš prvi kviz je 15. oktobra ki oktober se začenja ta teden. Torej, bi bilo prej kot ste pričakovali, je vse. Tako da ne boš vrgla varovala, ko Sem omenil, da je odsek naslednji teden oh, tvoj kviz naslednji teden, sem mislil, Jaz bi dal malo več od glave gor zdaj. 

Torej, tvoj problem določiti, številka tri. Kako so ljudje berejo spec iz radovednosti? OK. Imamo nekaj. Vrsta navzdol od zadnjega teden, ampak to je v redu. Vem, da je bilo lepo ven. Torej Break Out. Definitivno ko boste dobili storiti danes prebral vaše spec vsaj poskusite kot nalaganje distribucija kodo in tek kot prva začetnica stvar, da vas prosim, da. Saj smo z distribucija kodo in knjižnica da smo šele using-- --It je samo drugič smo naredili to Pset, nore stvari, se lahko zgodi, z vašo napravo, in želite, da bi našli, da ven proti kasneje. 

Ker če je v četrtek zvečer ali pa je Sredo zvečer, in iz neznanega razloga vaša naprava samo ne želite zagnati s knjižnico ali z distribucijo Koda, da so sredstva ne moreš niti začeti početje kodiranje. Ker si ne more preveriti da vidim, če deluje. Vaše ne bo lahko da vidim, če se pripravlja. Želite, da bi poskrbeli za tiste, v začetku leta teden, ko lahko še vedno mi email ali eden od drugih TF, in bomo lahko dobili tiste fiksne. Zato, ker so to vprašanja da vas bodo prenehali s kakršnimi koli resničen napredek. To ni všeč eno napako, da lahko samo nekako preskočili. Če imate težave z vašim aparat ali distribucijo kode, si res želite, da bi dobili, da sprejmejo skrbi za raje prej kot kasneje. Torej, tudi če ne boš dejansko začetek kodiranje, prenos distribucije koda, preberite spec, poskrbite, vse, kar se tam delajo. OK? Če lahko samo to, da sem Obljubimo, vaše življenje bo lažje. In tako ste verjetno bo da to storite zdaj prav? OK. Torej, vsa vprašanja tam? Morebitne logistične stvari? Vsakdo je dobro? OK. 

Disclaimer za tiste, ste v prostoru in na spletu. Bom poskusila preklopiti med PowerPoint v aparatu saj se bomo biti delaš nekaj kodiranje danes popularen od anonimni predlog ankete sem poslala prejšnji teden. Torej, bomo počeli nekaj kodiranja. Torej, če želite tudi vi da ogenj vaše aparate, in ti naj bi dobili e-mail: od mene, z datoteko vzorca. Vas prosimo, da to storim. 

Torej, bomo govorili o GDB, ki je debugger. To se dogaja, da vam pomaga nekako ugotoviti, kje stvari gredo narobe v kodi. To je res samo način za vas, da korak s kodo, saj se dogaja, in lahko natisnete spremenljivk ali vidite, kaj se dejansko dogaja pod kapuco prehladna svoj program samo teče, to je kot izjalovljen, in ti si všeč, ne vem kaj se je zgodilo tukaj. Ne vem, kaj linija je spodletelo. Ne vem, kje je šlo narobe. Torej, GDB se dogaja, da vam pomaga s tem. Tudi, če se boste odločili za naprej ja, in sprejme 61, da bo res, res si najboljši prijatelj, ker sem lahko vam povem, ker sem šel skozi ta razred. 

Bomo pogled na binarno iskanje, ki bi, če vi spomnite Lep primer imenik spektakel iz razreda. Mi bomo za izvajanje tega, in hoja skozi to malo bolj, in potem gremo skozi štiri različne vrste, ki so Bubble, Izbor, vstavljanja in Merge. Cool. Torej, GDB, kot sem že omenil, je razhroščevalnik. In ti so nekako big stvari, velike funkcije ali ukaza ki jih uporabljate v GDB in bom hodil ste preko demo njega v sekundi. 

Torej, to ni samo bo ostal povzetek. Bom poskusil, in da bo, kot je beton kot je mogoče za vas. Torej, prekinil. To bo bodisi odmor kot so nekatere številke, ki predstavlja vrstico v vaš program, ali lahko poimenujete funkcijo. Torej, če ste rekli, glavni odmor, se bo ustavil na glavni, in vam sprehod skozi te funkcije. 

Prav tako, če imate nekaj zunanjega deluje kot Swap ali Cube, da smo pogledal na zadnji teden. Če rečeš kršil eno od teh, vsakič, ko vaš program hits, da da bom počakal, da povej, kaj naj naredim. Preden se bo to šele izvajati tako, da vam lahko dejansko korak znotraj funkcije in glej, kaj se dogaja. Torej, naslednjič, samo preskoči naslednjo vrstico, gre čez funkcij. Korak. To so vsi malo abstraktna. Torej, jaz sem samo tekoč teči skozi njih, vendar boste jih videli v uporabi na sekundo. 

Stopiti v funkcijo. Torej, kot sem rekel, kot pri Swap, bi bilo vam omogočajo, da dejansko, kot če ste kot fizično krepitev notranjosti, lahko igraš s temi spremenljivkami, print izvedeti, kaj so, kaj se dogaja. Seznam bo dobesedno samo tiskanje ven kodo obdaja. Torej, če ste nekako pozabil kje ste v vašem programu, ali ste se spraševala, kaj se dogaja okoli njega, bo to le izpisal segment od rada pet ali šest linij okoli njega. Torej, lahko se orientirali o tem, kje ste. 

Natisni kakšne spremenljivke. Torej, če imate ključ, kot pri cesarju, da bomo pogledali. Lahko rečemo, Print ključ na kateri koli točki. To vam bo povedal, kaj je vrednost, tako da, morda nekje na poti, ste prepisali ključ. Lahko dejansko povedal, da zato, ker lahko dejansko opazuje te vrednosti. 

V domačini, samo odtise iz vaših lokalnih spremenljivk. Torej, kadarkoli si v zanko, in si želite videti podobno, oh. Kaj je moj jaz? Kaj je to ključna vrednota da sem inicializacijo tukaj? Kaj je sporočilo v tem trenutku? Samo, da bo izpisal vse tistih, tako da vas ne bi bilo treba posebej pravijo, Print I. Natisni sporočilo. Print Key. In nato Prikaži. Kaj to pomeni je, kot ste korak v okviru programa, da bomo samo poskrbite, da je prikazovanje neke določene spremenljivke na vsaki točki. Tako da boste also-- --it je nekakšna bližnjica kjer vam ni treba, da se dogaja podobno, oh. Print Key ali Print I. To samo bo samodejno naredil za vas. 

Torej, s tem, da gremo da vidim, kako to gre. Bom poskusil in stikalo na mojo napravo. Vidim, če lahko to storite. Vse. Mi smo le, da bo to ogledalo. Nič ni nor na moj laptop nekako. OK. Ta mora biti to ena. To je tako majhen. Poglejmo, če lahko to storimo. 

OK. Alice je očitno borila tukaj samo malo, ampak ga bomo dobili v Momento. OK. Mi smo le, da bo to povečanje. OK. Lahko vsi nekako videli? Mogoče malo? Vem, da je malo majhen. Ne morete povsem ugotoviti, kako se bo to večji. Če kdo ve. Ali kdo ve, kako bi bilo večje? OK. Bomo roll z njo. Ni važno, nekako, ker je to samo To je številka, ki naj bi vidva imajo. 

Kaj je bolj pomembno Terminal je tukaj. In imamo tukaj Zakaj je tako majhna? Nastavitve. Oh. True Ike. Kako je to? Od tam. Je, da je bolje za vse? OK ,. Cool. 

Saj veš, ko ste v CS razred tehnične težave so nekako del the-- Torej, kaj je to jasno. OK. Torej, tukaj v oddelku, ki smo jih imeli tukaj. Cezar je izvršljiva datoteka. Tako da mi je uspelo. Torej, ena stvar, da se zavedaš, s GDB je da lahko deluje samo na izvršljive datoteke. Torej, ne morete zagnati na dotsy. Moraš dejansko narediti Prepričajte se, da vaša koda prevede, in da lahko dejansko treba izvesti. 

Torej, poskrbite, da če se to ne zgodi zbere, mi ga je prevesti, tako da lahko nekako teče skozenj. Torej, za začetek GDB, vse, kar storite, Gloria tip GDB, in potem samo datoteko, ki jo želite. Vedno sem misspell Cezarja. Vendar si želite zagotoviti saj je to izvedljivo, TI je dot bliskavice, tako da pomeni, da boš teči CSI boš izvršiti To datotek bodisi s razhroščevalnik. OK. Torej, vam, da boste dobili ta vrsta žlobudranje. To je samo vse stvari o debugger. Nimate zares skrbi zdaj. In kot vidite, smo to odprte parens BDP, blizu parens, in samo nekako izgleda naša ukazni vrstici, kajne? 

Torej, kaj želimo do-- --So, Prva stvar je, da smo želeli izbrati mesto za odmor. Torej, obstaja en hrošč v tem programu Caesar da se predstavim, da bomo izvedeli. To, kar počne, je, da traja vnos Barfoo v vseh kape, in iz neznanega razloga to ne spremeni A. To samo zapusti sama, je vse ostalo pravilno, vendar druga črka Ostane nespremenjena. Torej, bomo poskušali ugotovimo, zakaj je tako. Torej, prva stvar, ki jo običajno želite storiti, ko ste začeli na GDB je ugotoviti, kje bi ga zlomil. 

Torej Caesar je precej kratek program. Moramo le eno funkcijo, kajne? Kakšna je bila naša naloga v Cezarja? Obstaja samo ena funkcija, Main kajne? Prva je funkcija za vse programe. Če niste imeli Main, bom morda biti malo v skrbeh prav zdaj, vendar upam, da boste vsi imeli Main tam. Torej, kaj lahko storimo, je, da smo lahko le prekinil Main, kar tako. Torej, pravi, OK. Smo Ustavljanje eno tam nastavljen. 

Torej, zdaj stvar za zapomniti je Caesar traja eno ukazno vrstico argumenta pravice in nismo storili, da še nikjer. Torej, kaj morate storiti, je, ko si dejansko šel za vožnjo programa, vsak program, ki ste teče v GDB, da mora ukazno vrstico trditve, da boš vhod ko ste prvič začeli prikazovati. Torej, v tem primeru delamo Teči s ključem tri. In bo dejansko začel. 

Torej, če vidite, imamo Če je Rc ni enaka 2. Torej, če imajo vsi fantje da datoteka, ki sem poslala gor boste videli, da je to všeč Prva vrstica je naša glavna naloga, kajne? To je preverjanje, da vidim, če imamo pravilno število argumentov. Torej, če ste se spraševala, če RC je pravilna, lahko narediš nekaj, kar tako Print RC. RC je dva, ki je tisto, kar smo pričakovali, kajne? 

Torej, lahko gremo Naprej in nadaljuje skozi. Torej, imamo nekaj ključ tam. In smo lahko natisnete svoj ključ se prepričajte, da je pravilno. Zanimivo. Ne ravno to, kar smo pričakovali. Torej, ena stvar, za uresničitev z GDB tudi, je da to ni, dokler ne boste dejansko hit Dalje, da je linija, ki ste jo pravkar videli dejansko izvede. Torej, v tem primeru Key še ni dodeljena. Torej, ključ je nekaj smeti vrednost ki jih vidite na spodnji tam. Negativni $ 120-- --It je ena milijarda in nekaj nenavadnega stvari, kajne? To ni ključ, da smo pričakovali. Ampak, če smo zadeli Naprej in nato smo poskusite in tipka Print, to je tri. 

Vsi videli? Torej, če ste dobili nekaj da ste kot, počakaj. To je popolnoma narobe, in ne vem, kako bi se to zgodilo, ker si želim storiti, je dodeliti številko, spremenljivka, poskusite hitting Naprej, poskusite tiskati še enkrat, in videli, če to deluje. Saj je le, da bo za izvedbo in dejansko dodeliti nekaj po vas hit Naprej. Smisla za vsakogar? Uh huh? 

SPEAKER 2: Ko random številke, kaj to pomeni? 

SPEAKER 1: To je samo naključno. To je samo smeti. To je samo nekaj, da je vaš Računalnik bo naključno dodeliti. Cool. Torej, zdaj lahko gremo skozi, in tako Zdaj imamo to navaden tekst GetString. Torej, povej mi samo predstavim, kaj se bo zgodilo, ko bomo zadeli Naprej tukaj. Naša GDB nekako izgine, kajne? To je zato, ker GetString Zdaj izvršitve, kajne? Torej, ko smo videli golo besedilo je enako GetString, odprte parens in parens, in smo zadeli Naprej, da ima dejansko izvrši takoj. Torej, to je čakala nam vhodni nekaj. 

Torej, gremo na vhod našo hrano, ki je tisto, kar ga ni, kot sem ti rekel in da samo pravi, da je končal izvršitve, da je zaprt Nosilec pomeni, da je izhodu iz te zanke. Torej, lahko zadeti Next, in zdaj, ko sem prepričajte, da ste vsi seznanjeni s Cezarjem, to je, kaj je to linija storili. To je za Int I enak 0, je n enak Strlen, golo besedilo, in nato I je manjše od n, J, plus plus. Kaj je to zanka storili? Odprite sporočilo. Cool. Torej, začnimo s tem. 

Torej, če bi se ta pogoj ujemajo, za naš prvi? Če je B, to je golo besedilo I. smo lahko dobite informacije o naših domačinov. Torej, je nič, in če je šest, ki pričakujemo, naša ključna je tri. Vse to smisla, kajne? Te številke so vse točno to, kar bi moral biti. Torej, hum? SPEAKER 3: Imam naključnih števil za rudnik. SPEAKER 1: No, lahko --we check-- lahko klepetate o tem v sekundi. Vendar bi morali biti že to. Torej, če imamo kapital B za našo prvo, Ta pogoj naj bi ga ujeli, kajne? Torej, če smo zadeli Naprej, vidimo, da to Če dejansko izvaja. Ker če ste po skupaj v kodi, ta vrstica tu, kjer golo besedilo I se nadomesti s tem aritmetike, izvaja samo, če, če Pogoj je pravilno, kajne? 

GDB je samo še, da ti pokažem stvari, ki so dejansko izvršitve. Torej, če je to Če pogoj ni bil izpolnjen, saj je le, da bo preskok na naslednjo vrstico. OK? Torej, imamo to. To pomeni, da je nosilec dospel te zanke zdaj. Tako, da se bo ponovno zagnal. Kar tako. Tako, da bomo lahko dobili informacije o naših domačini tukaj, in vidimo, da je naša prva Pismo se je spremenilo, kajne? To je zdaj E, kot bi moralo biti. Torej, lahko nadaljujemo. 

In imamo ta pregled. In ta pregled je treba delati, kajne? Je A. Treba je spremeniti tri črke naprej. Ampak, če ste opazili, smo dobili nekaj drugačnega. Torej, v tem primeru tukaj, ujet je, in zato je ta linija izvršen, ki je spremenila naše B. Toda, v tem primeru tod moramo, da samo preskočila, in odšel v [? L Siff. ?] Torej, kaj se dogaja tam. Tisto, kar je povedal, je, da vemo, da mora ujeti tukaj, vendar to ni. Lahko vsakdo videti, kaj naše Problem je v tem skladu? To je zelo minute stvar. In si lahko ogledate tudi na kodo. Prav tako je line-- pozabili, kaj linija je v there-- vendar je v [neslišno]. Ja? 

SPEAKER 4: Je na več kot stran, če ga preberete v knjigi. SPEAKER 1: Točno tako. Torej, razhroščevalnik ni mogel povedati vi, ampak razhroščevalnik ti lahko prinese do črte da veste, ne deluje. In včasih, ko se še posebej kasneje v semestru, ko imate opravka s sto, a sto nekaj vrstic kode, in si Ne vem, kje je to ne, To je odličen način, da to storite. Torej, smo našli našo napako. Lahko ga popraviti v datoteki, in potem bi lahko znova teči, in vse, kar bi delovalo odlično. In največja stvar, ki je To se lahko zdi kot, OK. Ja. Cool. Vedela si, kaj iščete. Torej, boste vedeli, kaj storiti. 

GDB lahko zelo koristno, saj vas lahko natisnete vse te stvari, ki jih ne bi. To je veliko bolj uporaben kot printf. Koliko ste uporabili kot printf izjav da ugotovimo, kje je bila napaka, kajne? Torej, s tem ne boste morajo voditi vrača, in rad komentiral v Printf ali komentirate, in ugotoviti, kaj si je treba tiskati. To vam omogoča, da dejansko samo stopiti skozi izpiše stvari kot greš skozi, tako da, lahko opazovati, kako se spreminjajo v realnem času, kot vaš program teče. 

In to ne traja malo malo navaditi. Jaz bi zelo priporočam le nekako , da so malo razočarani z njim Za zdaj. Če ste porabili eno uro pred Naslednji teden učenje, kako uporabljati GDB, boste sami rešiti toliko časa kasneje. In dobesedno. pripovedujemo to, da ljudje vsako leto, in spomnim se, ko sem prevzel razred, sem si mislil, bom v redu. No. Pset 6 vstopil in bil sem podobno, bom naučiti kako uporabljati GDB, ker jaz ne vedeti, kaj se dogaja tukaj. 

Torej, če ste vzeli čas, da jo uporabite za manjše programe da si bo delajo na, kot delajo skozi nekaj podobnega Visionare, kot je ta. Ali če želite dodatne prakso, sem prepričan, Lahko bi prišli do Otroški voziček programov, za vas, za odpravljanje napak, če želite. 

Ampak, če si vzemite nekaj časa, da bi dobili uporabljajo za to, samo igral z njim, bo zares dobro služijo. In to je res ena izmed tiste stvari, ki ste jo pravkar poskusiti in dobili vaše roke umazane s, preden jo zares razumeli. Res sem razumel le enkrat Moral sem debug stvari z njim, in to je veliko lepše, da imajo idejo kako debug raje prej kot kasneje. OK. Cool. Vem, da je nekako tako kot Seveda crash v GDB, in vsekakor se bom delo na pridobivanje ti, da si večji naslednjič. Cool. 

Torej, če se vrnemo k naši PowerPoint. Se bo to delovalo? AWH. Da. OK. Torej, če boste kdaj potrebovali katero koli tistih, ki si ne bodo seznam. Torej Binary Search, ki vsi zapomni velik spektakel Davidu Odličen imenikov na pol. Res ne dobijo imenikov več, ker je tako kot kadar kajne dobili telefonske knjige te dni? Res ne vem. Binary Search. Ali kdo spomnite kako Binary iskanja dela? Kdo sploh? Ja? SPEAKER 5: Veš, ko pogledaš na katerem polčasu da bi bilo v, Na podlagi tega in se znebite drugo polovico. 

SPEAKER 1 Točno. Torej, Binary Search, to je nekako a-- --we radi imenujemo razdeli in vladaj. Torej, kaj boste storili, je boste videti v sredini, in boste videli, če se ujema tisto, kar iščete. In če se to ne zgodi, potem poskusite ugotoviti, se dogaja, da se levo pol ali desno polovico. Torej, to je lahko, če iščete na nekaj, kar je po abecednem, vidite, oh. Ali Allison prišel pred M? Da. Tako, da bomo poglej prvi polovici. 

Ali bi bilo všeč, s številkami. Karkoli, da lahko jih primerjati je mogoče sortirati. Lahko uporabite binarni iskanje na. Torej, ne pozabite, kdo je to Graf ali kaj je to? To je asimptotska Complexity. Torej, ta graf samo opisuje, kako dolgo vas popelje rešiti problem, kot boste povečali število stvari ki ga uporabljate. 

Torej, imamo N, ki je linearni čas. Če je N čez dve, kar je nekoliko bolje, še vedno raste zelo hitro. In potem smo se Prijava, ki je kaj menimo Binarni iskanje. Če opazimo, kot je vaš problem dobi toliko in toliko večje, Čas je vas popelje, da ga rešiti v resnici ne poveča toliko. To je kot primerljiva tu na začetku. Ti si kot, OK. Kaj tu v resnici ne glede na to, katero bomo uporabili, vendar pa prideš ven na milijon, milijarda. Ste poskušali najti some-- --you're poskuša najti iglo v senu. 

Mislim, da si želite to težavo. Hočeš to kompleksnost, ne linearna, ker za vse vas poznate svoje bo treba iskati prek vsak posameznik igla, stvar sena, poskušam si za svoj iglo. In to ni preveč zabavno, po mojem mnenju. Všeč mi je hitro. Všeč mi je učinkovita. In ti kot pridni učenci fantje so, veš pametnejše delo, ne težje vrsta stvar, kako vas lahko do teh algoritmov. 

Torej, gremo na sprehod s samo hiter primer. Mislim, da fantje bi morali imeti roko na Binary Search, vendar v primeru, kdo je malo fuzzy, želijo, da ga okrepi, bomo pojdi skozi primer tukaj. Torej, iščemo, če Niz vsebuje sedem. 

Torej, prva stvar, ki mi je poglej v sredini, kajne? In tudi boš se kodiranje Binarno iskanje v samo sekundo. Torej, to bo zabavno. Torej gledamo v srednji mali nizi 3. Ali 3 enaka 7? Ne. To je šest. Torej, je to manj kot ali več kot sedem? Manj kot. Da. Lepi fantje zaposlitve. Čutim, rad bi jaz imajo sladkarije, ker sem želeli, da ga vrgel ven ladjedelnic. To je tisto, kar bom naredil naslednji teden. To vas bo fantje ostra. 

Torej, vržemo proč, da Prva polovica, kajne? to je manj kot. vemo, da je vse na tej levi strani se dogaja, da je manj od tistega, kar smo dejansko iščejo. Torej, ni potrebe, da bodite pozorni na to. Samo pozabi. Torej, zdaj gledamo na naši desni strani, in gledamo na sredini tam, in zdaj je devet. Torej, 9 is-- --Everyone? Večji od tistega, kar smo iskal, kajne? Torej, gremo, da mečejo stran vse na desni. Kot je ta. Zdaj ste vsi smo odšli z eno. Torej smo preveriti, ali je to ena, kar iščemo? je. Ugotovili smo, kar smo želeli. Tako da smo storili. Bilineamo Search. 

In, če ste opazili, smo imel sedem vhodov tam. To nam je všeč samo trikrat, ampak če delaš kot milijardo, veste, koliko korakov je bi da, če bi imeli štiri milijarde stvari? Kakršne koli ugibanja? To je 32. 32 korakov, da bi našli nekaj, v štiri milijarde element matrike zaradi pristojnosti dveh. Torej, dva je 32, je na štiri milijarde. 

Torej, precej noro, kako ste še vedno v kot dokaj majhno število korakov najti nekaj v štiri milijarde elementi. Torej na to opombo, da smo bo to kodo tako da fantje lahko dejansko nekako videli, kako to deluje. Vse je v redu, tako da lahko vidva kodo. Bom vama pustil govori malo. Spoznajte ljudi okoli vas, ki je kaj nekdo želel iz zadnjega poglavja. 

Tako spoznajo ljudi okoli vas. Govori malo. In vse, kar želim od tebe fantje, zdaj je le poskušajo ustvariti oris psevdokoda. OK? Vau. Vse, kar želim od vaju je, da ste le, da bo izpolnjevanje tega while primeru. Zato sem te določijo zgornjo in spodnje meje, ki predstavlja začetek in konec našega array. In boste dejansko zanko skozi in ugotovimo, kaj delamo v tem while. 

Torej, če lahko ugotovimo out-- imam namig there-- kaj so primeri da imamo tukaj? Torej, če želite, da ugotovimo, primeri, bomo psevdokoda tiste in potem bomo jih dejansko kodo. In to se dogaja, da sem mislim, upam, da bom je malo lažje, kot ste pričakovali. Ker to ni, da je veliko kode, pravzaprav, ki je res kul. 

Mm-hm? 

ŠTUDENT: [neslišno]? Inštruktor: Da. Nekaj ​​je bilo najti v sredini. 

ŠTUDENT: Tako smo lahko uporabite. OK. 

Inštruktor: Popolna. Tako da je prva stvar, ki jo morate storiti. Torej, najti sredino. Super. Torej imaš idejo, kako bi lahko dejansko našli na sredini s kodo? 

ŠTUDENT: Ja. n nad 2? Inštruktor: Torej n čez 2. Torej, ena stvar, da se spomnimo, da vaše zgornje in spodnje meje spremenijo. Hranimo plitvih del array iščemo za. Torej n več kot 2 deluje samo za prvo stvar naredimo. Torej pokazal zgornje in spodnje upoštevati, kako bi lahko dobili, da je srednji element? Ker želimo, da na sredini med zgornjim in spodnjim, kajne? Mm-hm? 

ŠTUDENT: [neslišno]. 

Inštruktor: Torej, imamo nekaj sredini. In to bo zgornja plus nižja več kot 2. Super. Tam gremo. Ena linija navzdol. Vi ste na vaši poti. Torej sedaj, da imamo srednji, kaj želimo narediti? Samo na splošno. Nimate za to kodo. Da. ŠTUDENT: [neslišno]? Inštruktor: Torej, to je plus, ker ste iskanje povprečje med dvema od njih. Torej, če mislite o njih, kot neke vrste povečanja od strani, razmišljati o tem, ko se približate srednji, hočeš tako. Torej, če ste bili na obeh straneh srednji in imamo kot 5 in 7. Ko jih dodate skupaj vas dobili 12, delite z 2, je 6. 

Včasih je težko pojasniti, zakaj to deluje, vendar če delate z Primer včasih, da bomo vam pomaga ugotoviti, če bi moral biti plus ali minus. Da. 

ŠTUDENT: [neslišno] točno v sredini če so imeli primer, ko je tam je veliko manjših številk in kot enega velikega števila? 

Inštruktor: Torej, vse, kar potrebujete je sredi polja. Torej, če ste imeli kup majhnih številkah nato pa eno res veliko število na koncu, to ni važno. Vse, kar je pomembno, je, da oni so razporejene, ki ste jo pravkar želeli videti na sredini matrika, ker ste še vedno rezanjem vaš problem na pol. Cool. Torej, zdaj, ko imamo srednji, kaj bomo zdaj? 

ŠTUDENT: Primerjaj. Inštruktor: primerjati. Torej primerjati sredini value_wanted. Cool. Torej vidite tukaj imamo ta vrednost želimo tu gor. Ne pozabite, to je matrika. Torej srednji nanaša na indeks. Zato smo želeli narediti vrednosti sredini. Ne pozabite, če želite Za primerjavo, dvojne enaka. Vam single enaka ste le, da bo to znova dodeliti, in nato, seveda, to je bo vrednost, ki jo želite. Torej, ne počni tega. 

Tako da bomo videli, če vrednosti pri sredini je enaka vrednosti, ki jo želimo. Ne pozabite na svoje naramnice. Dropbox moral oditi. Torej, kaj bomo naredili v tem primeru? Če je to tisto, kar si želimo, da se vrnete? Poskušamo povedati. 

ŠTUDENT: Natisni off. 

Inštruktor: No, ne želite natisniti off. Torej je to bool tukaj, zato smo želite vrniti true ali false. Mi pravite, je ta številka [? RRA? ?] Torej, če je, smo pravkar vrnil res. Če bom lahko črkovati res. 

ŠTUDENT: Zakaj ne bi vrnil nič? Inštruktor: Torej si lahko vrne nič, če si hotel. Toda v tem primeru zato, ker naša funkcija vrne bool, moramo vrniti bodisi resnična ali neresnična. UČENEC: Ko ste rekoč boolean izraz, jo lahko nastavite enak false? Všeč mi je, če sem hotel povedati, če je ta pogoj ni izpolnjen, kot je zgornja enaka false. Bo razumel, če si čaka false na drugi strani? Inštruktor: Ja. Torej, dejansko, če ste kdaj delaš nekaj kot je zgornja ali spodnja, ki vrne true ali false in to je pravzaprav slaba slog recimo enaka enaka true ali enaka enaka false. Želite uporabiti tega rezultata kot je sama kot ček. Ni tisto, kar sem želel. To je tisto, kar sem želel. Torej, v primeru, da ste prosi o nečem, kot je ta prihranek v c. 

Torej, če imamo int main (praznino), in kaj takega. In imate, če je zgornja nekaterih vhodnih in ste sprašuje, če lahko to storite kaj takega? Kajne? ŠTUDENT: Poskušal sem da to storite [neslišno]. Ker če it's-- Inštruktor: Right. Torej hočeš, da je to napačna, kajne? ŠTUDENT: Ja. Inštruktor: Torej, v tem primeru želite, da se izvrši, če to ni res. Tako kul stvar, ki vam je to. Torej, ne pozabite vzklik točka zanika stvari? Piše [neslišno] ne pomeni. Torej, če pogledamo samo ta del tukaj, ki ste jo pravijo, da ocenjuje, da false, kot ste želeli. Ni napačna je res, ki pomeni, bi to izvesti. Ali to smiselno? ŠTUDENT: Ja. Inštruktor: Awesome. OK. Tako da smo lahko samo vrnitev velja v tem primeru. Torej, zdaj imamo dva druga primeri, v tem primeru. Kaj sta dve naši drugi primeri? Recimo, da na ta način pač. Torej začnimo z drugo če vrednosti na sredini je nižja od vrednosti, ki jo želimo. Torej, naša vrednost v sredini je manj od vrednosti, ki jih iščete. 

Torej, ki veže kajne mislim, da želite posodobiti? Zgornji ali spodnji? Zgornji? Torej, na kateri strani polja bomo se gledaš? 

ŠTUDENT: nižja. 

Inštruktor: Mi gremo da je treba videti na levi strani. Torej, če je še majhna vrednost manj. Torej srednjo vrednostjo tukaj je manj od tistega, kar si želimo. Zato želimo, da bi desna stran našega array. Tako bomo posodobiti naš spodnja meja. Torej bomo dodelite naše nižje. In kaj misliš, da bi morale biti nižje? ŠTUDENT: srednja vrednost? Inštruktor: Torej srednji value-- ŠTUDENT: Plus 1. Inštruktor: --plus 1. Mi lahko kdo pove, zakaj moramo, da je plus 1? 

ŠTUDENT: [? No vrednost?] je bolj enaka njo. 

Inštruktor: Right. Saj že vemo, da naša srednja vrednost ni enaka je in želimo, da ga izključijo od vseh nadaljnjih iskanj. Če ste pozabili, da je plus 1, to bo všeč zanke za nedoločen čas. In boste le ujeta v neskončna zanka in potem boste segfault in gredo stvari slabo. Zato vedno poskrbite, da niste vključno z vrednostjo, ki ste jo pravkar pogledal. Tako smo poskrbeli, da je pri plus 1. 

Torej, zdaj imamo zadnje stanje ki sem vedno za varnost zaradi si lahko ogledate tukaj, else if vrednost na srednji je večja od vrednosti želimo. To pomeni, da želimo levo polovico roke. Torej, katero bomo posodobiti? Zgornji del. In kaj je to ena bo enaka? Bližnji minus 1, ker Seveda, želimo se prepričajte, da nismo videti spet na tej srednji vrednosti. In potem smo jo imeli. To je to. To je vse, binarno iskanje je. To ni tako slabo, kajne? To je kot 10 vrstic koda z belim prostorom. Tako zelo močan, zelo uporaben, boste lahko ga uporabite v enem od svojih poznejših psets. Morda tega ne enega, ampak kasneje. Tako da se ga učijo. Je všeč. To vam bo zdravljenje dobro. Torej, ali ima kdo koli Vprašanja o binarnem iskanju? Da. 

ŠTUDENT: Ali je pomembno ali je vaš n celo ali liho? 

Inštruktor: No. Ker smo ga odda v sredini kot int, bo to samo skrajšajte. Torej bo ostal celo in bo sčasoma razvrstite skozi vse. Torej vam ni treba skrbeti za to. Vsi dobro? Super. Cool. Torej, fantje to dobil. Slideshow. Torej, kot smo govorili, vem David omenjeno kompleksnost runtimes. 

Torej v najboljšem primeru, to je samo ena, ki jo imenujemo konstantno časa. Mi lahko kdo pove, zakaj bi lahko bilo? Katera vrsta scenarija bi to pomenilo? Mm-hm. 

ŠTUDENT: [neslišno] first-- Inštruktor: Torej, srednji pa Prvi element, ki smo prišli, kajne? Torej bodisi niz enega ali vse, kar smo iskali le zgodi, da se zadah dab na sredini. Tako da je naša najboljša primera. Boste dobili v dejanskih težav, verjetno ne bo dosegel [neslišno], ki se pogosto. Kaj pa naši najslabšem primeru? Naša najslabšem primeru je log n. In da ima opraviti s celotnim Pooblastila dveh stvari, ki sem govoril. 

Torej, v najslabšem primeru bi to pomenilo, da smo imeli za sekanje array navzdol dokler ni bil element enega. Tako da smo morali sekanje dol na pol tolikokrat, kot vam morebiti lahko. To je razlog, zakaj je log n, ker si kar naprej delimo z dve. Torej predpostavke, stvari, ki jih morate vedeti, če ste kdaj boste uporabljali binarno iskanje. Vaši elementi morajo biti razporejene. Jih je treba sortirati, ker To je edini način, boste more vedeti, če ste sposobni vrgel ven polovico tega. 

Če ste imeli ta zamotana vrečko številk in praviš, OK, grem preveriti na sredini številka in številka iščem je manj kot to, da sem le, da bo samovoljno vrgel ven polovico. Saj ne bi vedeli, če je vaš Številke v tej drugi polovici. Vaš seznam je treba sortirati. Kot je dobro, je to lahko gre naprej malo, vendar morate imeti izbirni dostop. Moraš biti sposoben samo pojdite na ta srednji element. Če imate za prečkanje skozi nekaj ali je potrebno, vam dodatne ukrepe priti do tega srednjega elementa, to ni več, ker se prijavite n ste dodali več dela v njej. In bo to malo bolj občutek v dveh tednih, vendar sem nekako želel predgovor, vidva dala idejo o tem, kaj je da pridejo. Ampak to so dva Pomembnejše predpostavke da morate za binarne seznama. Prepričajte se, da je urejeno. To je ena velika za vi zdaj. In da lahko gremo v Preostali del naših vrst. Torej štiri sorts-- mehurček, vstavljanje, izbor in spajanje. Oni so vsi nekako kul. Če vi odločite za CS 124, boste izvedeli vse o vseh mogočih vrst. In če ste za xkcd ventilator, tam je res kul strip o kot je v resnici neučinkovitih vrst, ki sem jih Priporočam vam bo gledati. Eden od njih je, kot panično vrste, ki je všeč, oh ne, vrne naključno array. Zaustavitev sistema. Zapusti. Tako geeky humor je vedno dobro. 

Torej, ali ima kdo zapomniti vrste od kot le splošno idejo kako bubble nekako deluje. Se spomniš? 

ŠTUDENT: Ja. 

Inštruktor: Pojdi. 

ŠTUDENT: Torej greš skozi in če je večji, potem ste zamenjali dva. 

Inštruktor: Mm-hm. Točno tako. Torej ste pravkar Ponovil skozi. Morate preveriti dve številki. Če so pred eno večje od tistega po njem, jih samo zamenjali, tako da je v ta način vse višjimi številkami mehurček navzgor proti koncu seznama in vsi spodnji številke mehurček navzdol. 

Ti je pokazal fantje cool zvok učinek sortiranje video? To je nekako kul. Torej, kot je bilo pravkar omenjeno, Robert algoritma ki ste ga pravkar korak po seznamu, zamenjavo sosednjih vrednosti če nisi v redu. In potem samo ponavljajo dokler ne naredite nobene zamenjave. Torej ni slabo, kajne? Torej imamo samo na hitro primer tukaj. Torej, to se dogaja, da razvrstite jim v naraščajočem vrstnem redu. Torej, ko smo šli skozi prvo Tokrat si bomo ogledali preko osmih in šest očitno niso z namenom, da jih swap. 

Torej, poglej naslednjo. Osem in štiri niso v redu. Swap njih. In nato osem in dve, jih zamenjajte. Tam gremo. Torej, po prvi izvedel, si veste, da je vaš največje število se bo vse poti na vrhu, ker je samo bo nenehno večja kot vse ostalo in to je le, da bo balon navzgor vse do konca tam. Ali je to smiselno za vsakogar? Cool. 

Torej gledamo na našem drugem prehodu. Šest in štiri, stikalo. Šest let in dva stikala. In zdaj imamo še nekaj stvari v red. Torej, za vsako je izvedel, da smo da po celotnem seznamu vemo, da je, kot da je veliko število Na koncu so bili bodo razporejene. Torej naredimo tretji sredino, ki je ena swap. In potem na naš četrti opraviti imamo nič reže. In tako vemo, da je naš Niz je bil razvrščen. 

In to je velik stvar z mehurček vrste. Vemo, da ko smo imeti nič zamenjave, ki pomeni, da je vse je v popolnem redu. To je nekako, kako preveriti. Tako smo se tudi dogaja, da kodo mehurček vrsta, ki tudi ni tako slabo. Nobeden od teh, ki so slabe. Vem, da se lahko zdi nekoliko strašljivo. Vem, da ko sem prevzel razred, tudi ko sem je poučeval v razredu za prvič lani, Sem bil všeč, kako to storiti? Smiselno je v teoriji, ampak kako pravzaprav to? Zato sem prav tako želeli, da hodi skozi kodo z vami tukaj. Tako da imam psevdokoda za vas fantje tokrat. Torej, samo obdržati to v mislih, smo na tem, da prehod čez. Torej imamo nekaj števec, ki beleži naših zamenjav, saj moramo zagotoviti, da smo preverjanje, da. In smo Ponovil celotno paleto kot smo pravkar storil s tem primerom. Če preden je element večji od element potem, ko smo na, smo jih zamenjali in smo prirastek Nostra števec, ker takoj, ko bomo zamenjali, želimo pustiti naš števec veš. Vsa vprašanja tam? Nekaj ​​zdi smešno tukaj. ŠTUDENT: Ali ste nastavili števec na nič vsakič, ko greš skozi zanko? Ne boste nadaljuj nazaj na nič vsakič? Inštruktor: Ni nujno. Torej, kaj se zgodi, ko gremo skozi tukaj. To storijo, ko, ne pozabite, to se bodo izvajale enkrat ne da bi propadel. Tako se dogaja, da nastavite števec enak nič, potem se dogaja, da skozi ponovitev. Saj se ponovi, bo posodobitev števec. Saj posodobi števec, ko je to storil, ko je to dosegel konec matrike, če je naš seznam ni bil razvrščen, števec pa se bo posodobljen. 

Torej potem preverja stanje in ga pravi, OK, je števec večji od nič. Če je, še enkrat. Želite, da ko boste ponastavili iti skozi, števec enak nič. Če greš skozi sortirani matrika, se nič ne spremeni, to ne uspe, vi pa vrnitev razvrščen seznam. Ali je to smiselno? ŠTUDENT: To bi v malo. Inštruktor: OK. Če je katera koli druga Vprašanje, ki pride gor. Da. 

ŠTUDENT: Kaj bi funkcijo bo za zamenjavo elementov? 

Inštruktor: Torej lahko dejansko napisati da če bomo zdaj. Cool. Torej na to opombo, Alison se dogaja preklopiti nazaj na aparat. To bo zabavno. In imamo lepo bubble nekako stvar tukaj. Tako da sem že naredil kolesarjenje preko matrike. Imamo zamenjave, ki so enaki nič. Zato želimo, da bi zamenjali meji Elementi, če si pokvarjen. Torej prva stvar, moramo Ponovil se je skozi našo paleto. 

Torej, kako misliš, da bi lahko Ponovil skozi našo paleto? Imamo za in i enak 0. Želimo, i ne sme biti manjši kot n minus 1 minus k. In bom razložiti, da v sekundi. Torej, to je optimizacija tukaj, kjer Spominjam se, kako sem rekel po vsakem izvedel skozi array mi vem, da vse, kar je on-- 

Torej, po enem prehodu smo vedo, da je to urejeno. Po dveh prelazov vemo, da je vse to urejeno. Po treh prelazov smo vemo, da je urejeno. Tako mimogrede sem ponavljanjem preko matrike tod se je pazite, da le gre skozi tisto, kar vemo, je, razvrščeni. OK? To je samo za optimizacijo. Lahko bi jo napišite naivno samo ponavljanjem skozi vse, da bi le trajalo dlje. S tem štiri zanke je samo lepo optimizacija ker vemo, da po vsaki polni iteracija preko matrike tod kot vsako polno zanko tu, vemo, da ena od teh elementov bodo razporejene konec. 

Tako da nam ni treba skrbeti za tiste. Ali je to smiselno za vsakogar? To cool mali trik? Torej v tem primeru, če smo s ponavljanjem, vemo, da smo želeli preveriti, če matrika n in n + 1 v redu. OK. Torej, tukaj je psevdokoda. Želimo, da preverite, če matrika n in n + 1 v redu. Torej, kaj bi imeli tam? To se dogaja, da nekateri pogojno. To bo, če. 

UČENEC: Če matrika n manj kot matrika n plus 1. Inštruktor: Mm-hm. No, manjša ali večja od. ŠTUDENT: Večja kot. Potem smo želeli, da jih swap. Točno tako. Torej, zdaj smo prišli v kaj mehanizem za njihovo zamenjavo? Torej smo šli skozi to kratko, tip swap funkcijo prejšnji teden. Ali kdo spomnite, kako je delal? Zato ne moremo samo njihovo prerazporeditev, kajne? Ker je eden od njih boste izgubili. Če smo rekli, je enako B in nato B je enaka A, vse nenadna oba so samo enaka B. 

Torej, kaj moramo storiti, je, da smo imajo začasno spremenljivko, ki je dogaja, da imajo enega od naših časa smo v procesu zamenjavo. Torej, kaj imamo, je, da bomo imeli nekaj int Temperatura je enaka to-- jo lahko dodelite da tisti, ki ste želeli, samo poskrbite, da boste spremljate it-- tako da v tem primeru, jaz grem na dodelite niz n plus 1. Tako, da se dogaja, da imajo karkoli vrednost je v tem drugem bloku da gledaš. 

In potem lahko storimo, je lahko greva naprej in znova dodelite niz n + 1, saj vemo, so, da je vrednost, shranjeno. To je prav tako ena velika things-- Ne vem, če kdo od vas imeli vprašanja, pri katerih, če preklopite dva vrstic kode nenadoma stvari delal. Da je zelo pomembno v CS. Torej, poskrbite, da boste diagram stvari, če je to mogoče o tem, kaj se dejansko dogaja. Torej, zdaj bomo dodelite niz n + 1, saj vemo, so, da je vrednost, shranjeno. 

In bomo lahko določite, da niz n ali v tem primeru matriki i. Preveč spremenljivk. OK. Torej, zdaj smo prerazporedili matrika i plus 1 do enakega kaj je v matriki i. In zdaj se lahko vrnemo in dodelite niz I do česa? Kdorkoli? 

ŠTUDENT: 10. 

Inštruktor: 10. Točno tako. In še zadnja stvar. Če smo ga zamenjali zdaj, Kaj moramo storiti? Kaj je ena stvar, da se dogaja, da nam poveste če bomo kdaj odpove ta program? Kaj nam pove, da smo imajo razvrščen seznam? Če nam ne opravljajo nobene zamenjave, kajne? Če zamenjav je enaka nič ob koncu tega. Torej, ko izvedete zamenjavo, kot smo pravkar storil tukaj, želimo posodobiti zamenjavami. In vem, da je bilo Vprašanje prej o tem si lahko uporabljajte nič ali ena, namesto od true ali false. In to je tisto, kar ta počne tukaj. Tako da je ta pravi, če ne zamenjavami. Torej, če zamenjave je enaka nič, kar is-- sem vedno dobili moje resnice in moje falses pomešal. Želimo, da ocenimo da res in to ni. Torej, če je nič, potem je false. Če ga zanikajo z [? bang?] postane res. Torej ta vrstica izvede. 

Resnice in napačne in ničel in enic dobili nor. Samo, če počasi hodi skozi njo bo smisla. Ampak to je tisto, kar ta mali bit kode tu počne. Tako da to preveri, smo naredili nobene zamenjave. Torej, če je to vse, kar je poleg nič, da se dogaja, da so napačne in stvar je bo ponovno izvesti. Cool? 

ŠTUDENT: Kaj narediti premor? 

Inštruktor: Break samo vas izbruhne zanke. Torej, v tem primeru pa bi rad na koncu programa in vi bi samo imajo svoj sortira seznam. ŠTUDENT: Amazing. Inštruktor: Žal mi je? ŠTUDENT: Ker prej smo rabljeni napisan 1 nad napisal nič predstaviti, da če da bo delo ali ne. 

Inštruktor: Ja. Tako da se lahko vrnete nič ali 1. V tem primeru, ker smo dejansko ne delaš karkoli s funkcijo, smo samo želim, da bi prekinil. Mi pravzaprav ne skrbi o tem. Zavora je tudi dobro, če to je uporabljena za zlom štirih zank ali pogojev, ki ne želite, da izvršiteljica. Samo vas popelje iz njih. To je malo pomenski odtenki stvar. Počutim se, kot da je Veliko strani kodranje, kot boste izvedeli vse o tem kmalu. 

Vendar pa boste izvedeli vse o tem kmalu. Obljubim. OK. Torej ne vsi dobili mehurček vrste? Ni preveč slabo. Ponovil skozi, swap stvari, ki uporabljajo temp spremenljivka, in smo vsi tam nastavljen? Cool. Super. OK. Nazaj na PowerPoint. Vsa vprašanja v splošnem O teh tako daleč? Cool. Mm-hm. 

ŠTUDENT: [neslišno] int glavni običajno. Ali moraš imeti, da je za to? 

Inštruktor: Torej smo samo iščejo le ob dejanskem razvrščanje algoritem. Če jo je imel v kot večji program, bi imeli int glavno nekje. Odvisno od tega, kje ste uporabljajo ta algoritem, da bi ugotovili, kaj je se vrnil z njo. Toda za naš primer, smo strogo gledaš kako to dejansko Ponovil skozi paleto. Tako da ne skrbi. 

Tako smo govorili o najboljšem primeru in najslabšega scenarija za binarno iskanje. Zato je tudi pomembno, da se da za vsako od naših vrst. Torej, kaj misliš, da je najhujše Primer runtime mehurčkov vrste? Vi se spomnite? 

ŠTUDENT: N minus 1. Inštruktor: N minus 1. Torej to pomeni, da obstaja n minus 1 primerjave. Torej, ena stvar, da zavedaš, da na prvi ponovitvi gremo skozi, moramo primerjati ti dvo tako da je 1. Ti dve, tri, štiri. Torej, po eni ponovitvi smo že štiri primerjave. Ko govorim o runtime in n. N predstavlja število primerjav kot funkcija koliko elementov imamo. OK? 

Torej, gremo skozi, imamo štiri. Naslednjič, ko boste vedeli, da ne skrbeti za to. Primerjamo ta dva, ta dva, ta dva, in če ne bi imeli te optimizacijo s štirimi zanko, da sem napisal, bi se primerjali tu nekako. Torej bi morali teči skozi polja in da n primerjave n krat, ker vsakič, ko teči skozi to zbiramo eno stvar. 

In vsakič, ko teče skozi matrika, naredimo n primerjave. Torej naš runtime za to je dejansko je n kvadrat, ki je precej slabše v našem log konca, saj da pomeni, da če bi imeli štiri Milijarde elementi, to je dogaja, da nam bo štiri milijarde kvadrat, namesto 32. Torej ni najboljši runtime, ampak za nekatere stvari, veste, če ste v določenega obsega elemente bubble nekako lahko v redu za uporabo. 

OK. Torej, zdaj, kaj je najboljši primer runtime? ŠTUDENT: Zero? Ali 1? 

Inštruktor: Torej 1 bi ena primerjava. Prav. 

ŠTUDENT: N minus 1? 

Inštruktor: Torej, ja. Torej n minus 1. Kadarkoli imate koncept, kot n minus 1, smo vajeni, da ga samo odložiš in smo pravkar rekli, n, ker imate Za primerjavo vsako these-- vsakega para. Torej bi bilo n minus 1, ki smo mi bi samo rekel približno n. Ko imate opravka z runtime, vse, kar je v ta približuje. Dokler je eksponent pravilno, da ste zelo dobro. 

Tako imamo opravka z njo. Tako da najbolje primeru je n, ki pomeni, da je seznam že razporejene, in vse, kar smo storili je teči skozi in preverite, da je to urejeno. Cool. Vse je v redu. Torej, kot vidite tu, Samo še nekaj grafov. Torej n kvadrat. Fun. Veliko slabše, kot n, kot smo videli, in veliko, veliko slabše kot log 2n. In potem dobite tudi v dnevniških hlodov. In ste vzeli 124, boste dobili v kot log zvezda, ki je kot nor. Torej, če vas zanima, lookup log zvezda. To je kar zabavno. Torej imamo to veliko grafikon. Le glave gor, to čudovito grafikon, da imajo za vaš srednjeročno, ker smo dolgo, da vas ta stanjša. Torej le glave gor, še to na vaš Vmesno na vaši lepi goljufija stanja tam. Tako smo samo pogledal mehurček vrste. V najslabšem primeru, n kvadrat, najboljši primer, n. In bomo pogled na druge. 

In kot vidite, samo tisti, ki res dobro je z zlivanjem, kar bomo dobili v zakaj. Tako smo šli na Naslednjič here-- izbor vrste. Ali kdo spomnite, kako Izbira vrste delal? Gre za to. 

ŠTUDENT: V bistvu iti skozi red in ustvariti nov seznam. In kot ste dajanje elementov v, jih postaviti na pravo mesto v novem seznamu. 

Inštruktor: Torej, da zvoki več kot vstavljanje vrste. Ampak ste res blizu. Oni so zelo podobni. Tudi jaz se jim pomešal včasih. Pred tem oddelku sem bil všeč, počakaj. OK. Torej, kaj hočete storiti, je izbira vrste, Tako si lahko misliš o njem, in način, Sem zagotovil, da sem poskusil, da ne bi dobili jih pomešal, je gre skozi in izbere Najmanjše število in navaja, da je na začetku svojega seznama. Jo zamenja s tem prvo mesto. Jih dejansko imajo zgled za mene. Super. Torej samo način, da razmišljajo o it-- izbor urejanje, izberite najmanjšo vrednost. In bomo teči skozi primer da mislim, da bo pomagal, ker Mislim, vizualne vedno pomaga. Tako smo začeli z nečim da je popolnoma razvrščeni. Red bodo razvrščeni, zelena bodo razporejene. To bo vse smisla v sekundi. 

Torej, gremo skozi in smo Ponovil od začetka do konca. In smo rekli, v redu, 2 naše najmanjše število. Torej bomo vzeti 2 in gremo da ga premaknete na sprednji strani našega polja ker je Najmanj, kar imamo. Torej, to je tisto, kar ta počne tukaj. To je le, da bo zamenjala tista dva. Torej, zdaj imamo urejeno del in razvrščeni del. In kaj je dobro, da se spomnimo glede izbire vrste je, da smo le, da izberete Iz nerazvrščene dela. 

Sortirani del, ki ga pustite pri miru. Mm-hm? 

ŠTUDENT: Kako vedeti, kaj je Najmanjši ne da bi ga primerjali za vse druge vrednosti v matriki. Inštruktor: To počne tako primerjavo. Radi ga preskočila. To je samo splošni skupni. Ja. Ko smo napisali kodo Jaz sem prepričan, da boste bolj zadovoljni. Vendar si shranite ta prvi Element najmanjša. Primerjajo in si reči, OK, je manjši? Da. Obdržati. Tukaj je manjši? Ne? 

To je tvoja najmanjša, ga prerazporedil na vaše vrednosti. In boste veliko srečnejši ko gremo skozi kode. Torej, gremo skozi, smo ga zamenjali, tako da potem gledamo na to nerazvrščene dela. Tako bomo izbrali tri out. Bomo, da je na na Konec našega sortirane odseka. In smo le, da bo vztrajati početje da delaš to, in s tem. Torej je to naša vrsta psevdokoda tukaj. Mi bomo to kodo tu gor na sekundo. Ampak samo nekaj, da hodi preko na visoki ravni. Boš šel iz i je enak 0 za n minus 2. To je že druga optimizacijo. Ne skrbite preveč o tem. Tako kot ste rekli. Kot Jacob je rekel, kako počnemo slediti, kaj naš minimum? Kako vemo? Moramo primerjati vse, kar je v našem seznamu. 

Torej minimum enak i. To je samo rekel, v tem primeru Indeks naše najmanjše vrednosti. Torej to se dogaja, ponovitev prek in gre iz j enak i plus 1. Tako že vemo, da To je naš prvi element. Nam ni treba primerjati s sebi. Tako smo začeli primerjavo z naslednjo ena, ki je razlog, zakaj je i plus 1 do n minus 1, ki je Konec niza tam. In mi je rekel, če matrika na j je manjša od diod min, potem dodelite kjer naše minimalne indeksi je. 

In če min ni enako i, kot v Ljubljani, kjer smo bili spet tukaj. Tako všeč, ko smo najprej naredili to. V tem primeru bi bilo začeti na nič, bi bilo na koncu pa dva. Torej min ne bi enako i na koncu. Upamo, da nam sporočite, da jih moramo zamenjati. Počutim se kot konkreten primer bo pomagalo veliko več kot to. Tako da bom to kodo z vami prav zdaj, in mislim, da bo bolje. 

Vrste ponavadi deluje na tak način, da v je pogosto bolje, samo da bi jih videli. Torej, kaj želimo storiti, je smo najprej želeli najmanjši element v svoji legi v matriki. Točno to, kar je rekel Jacob. Morate shraniti, da nekako. Torej bomo začeli tukaj ponavljanjem čez polja. Bomo rekli, da je naš Prva je samo za začetek. Torej bomo imeli int Najmanjše je enaka matriki na i. 

Torej, ena stvar, da obvestilo, vsak Čas ta zanka izvaja, začenjamo skupaj en korak naprej. Ko smo začeli smo poglej tole. Naslednjič, ko smo Ponovil skozi, začenjamo na tale in to je naša najmanjša vrednost dodelitev. Zato je zelo podoben mehurček vrste kjer vemo, da je po enem prehodu, Ta zadnji element je razvrščen. Z izbirnim vrste, to je ravno nasprotno. 

Na vsaki je izvedel, vemo, da Prva je razvrščen. Po drugem prehodu, Drugi pa bodo razvrščeni. In kot ste videli s primeri slide, naša razporejene del samo raste. Tako z določitvijo našo najmanjšo eno do nizi i, vse to počne je kaj plitvih iščemo na tako da se zmanjša število primerjav naredimo. Ali to smiselno za vsakogar? Me morali teči skozi, da spet počasneje, ali z drugimi besedami? Vesel sem, da. OK. 

Tako da smo shranjevanje vrednosti na tej točki, ampak želimo tudi shranjevanje indeks. Tako bomo za shranjevanje Položaj najmanjši ena, ki je pravkar bo i. Torej, zdaj Jacob je zadovoljen. Imamo stvari shranjene. In zdaj moramo odmisliti razvrščeni del matrike. Torej v tem primeru je to bi bilo naše razvrščeni. To je i. OK. 

Torej, kaj bomo storili se bo za zanko. Kadarkoli potrebujete Ponovil skozi paleto, vaš um lahko iti za zanko. Torej, za nekaj int k equals-- kaj mislimo k bo enaka za začetek? To je tisto, kar smo si zastavili, kot je naša najmanjša vrednost in ga želimo primerjati. Kaj želimo primerjati z? To se dogaja, da bi se ta naslednjič, kajne? Zato želimo k inicializirati k i plus 1 za zagon. 

In želimo, k smo v tem primeru že Velikost shranjeni tukaj, tako da bomo lahko šele raba velikost. Velikost čemer velikost matrike. In hočemo samo posodobiti k ene vsakič. Cool. Zdaj moramo najti najmanjši element tukaj. Torej, če smo Ponovil skozi, smo hočeš reči, če je matrika na k je manjši od našega najmanjšega value-- to je, če smo dejansko sledenja, kaj je najmanjši here-- Nato smo želeli prerazporeditev kakšna je naša najmanjša vrednost. 

To pomeni, da, oh, smo ponavljanjem tu skozi. Ne glede na vrednost je tu ni naša najmanjša stvar. Mi tega ne želite. Želimo, da ga prerazporedil. Torej, če smo to prerazporeditev, kaj storiti misliš, da bi lahko v tem kodeksu tukaj? Želimo, da za dodelitev Najmanjši in položaj. Torej, kaj je sedaj najmanjši? ŠTUDENT: Array k. Inštruktor: Array k. In kaj je zdaj stališče? Kaj je indeksi naša najmanjša vrednost? To je samo k. Torej diod k, k, se ujemajo. Zato smo želeli, da je prerazporedil. In potem, ko smo ugotovili, naš najmanjši, tako da na koncu tega za zanke Tu smo ugotovili, kakšna je naša najmanjša vrednost, zato smo ga pravkar zamenjali. V tem primeru, kot pravijo Nostra Najmanjša vrednost je tukaj. To je naša najmanjša vrednost. 

Pravkar smo želeli zamenjati tukaj, ki je kaj je funkcija swap na dnu storili, kar smo pravkar napisala skupaj nekaj minut nazaj. Tako da bi bilo videti seznanjeni. In potem bo to šele Ponovil prek dokler ne doseže vso pot do konca, kar pomeni, da imeti nič elemente, ki so razvrščeni in vse ostalo je bilo urejeno. Smisla? Malo bolj konkretno? Koda pomoč? 

ŠTUDENT: Za velikosti, nikoli res določiti ali spremeniti, kako to veš? 

Inštruktor: Torej, ena stvar, Opazili tu je velikost int. Tako smo govoriš v tem sort-- vrste je funkcija v tem case-- je Izbira vrste, je to opravil ima funkcijo. Torej, če ne bi bil sprejet leta, bi vi storili nekaj kot z dolžino polja ali bi si ponovitev prek najti dolžino. Ampak zato, ker je minilo na, lahko smo samo uporabljati. Pravkar si domnevati, da uporabnik Vam je veljavno velikost, ki dejansko predstavlja velikost vašega array. Cool? 

Če imata vidva nobenih težav z njimi ali želijo več prakse kodiranja vrste sami, morate pojdite na study.cs50. To je orodje. Imajo skladiščnik, ki lahko dejansko napisati. Oni psevdokoda. Imajo več video posnetkov in diapozitivov vključno s tistimi, ki jih uporabljam tukaj. Torej, če ste še vedno občutek malo fuzzy, poskusite to. Kot vedno, pridi govoriti z menoj, preveč. Vprašanje? 

ŠTUDENT: Praviš velikost je definirano prej? Inštruktor: Da. Velikost je definirano prej gor tukaj v deklaraciji funkcije. Torej si domnevati, da je bil sprejet leta s strani uporabnika, in zavoljo enostavnosti je, bomo predvidevali, da Uporabnik nam je prave velikosti. Cool. Tako da je izbira vrste. Fantje, vem, da smo ogromno naučili danes. To je gosto podatki za oddelka. Torej, s tem se bomo iti vstavljanja vrste. 

OK. Torej, preden da moramo storiti naša runtime analize tukaj. Torej v najboljšem primeru, odobrena, saj sem ti pokazal miza sem že nekako ga dal proč. Ampak najboljši primer runtime, kaj mislimo? Je vse urejeno. N na kvadrat. Kdo pojasnilo zakaj misliš? 

ŠTUDENT: Ste primerjavo through-- Inštruktor: Right. Ste primerjali skozi. Na vsaki iteraciji, čeprav smo pomanjšanja to z enim, ste še vedno iščejo s pomočjo vse, da bi našli najmanjšo enega. Torej, tudi če je vaš najmanjša vrednost je tu na začetku, ste še vedno ga primerja proti vsem ostalim se prepričajte, da je najmanjša stvar. Tako da boste na koncu, ki teče skozi približno n kvadrat krat. Vse je v redu. In kaj je v najslabšem primeru? Tudi n kvadrat, ker boš da se delaš, da je isti postopek. Torej, v tem primeru, izbor vrsta ima nekaj da smo tudi pokličete pričakovani runtime. Torej, na ostalih pa smo samo vedeti zgornja in spodnja meja. Odvisno od tega, kako noro naše seznam ali kako razvrščeni je, se razlikujejo od n ali N razčetverjen. Ne vemo. 

Ampak zato, ker je izbira nekako enako najslabši in najboljši primer, ki nam pove, da ne glede na to, kakšne vrste vhodu smo imajo, ali je to popolnoma razporejene ali popolnoma povratne razporejene, da je bo trajalo enako količino časa. Torej, v tem primeru, če vas spomnite iz naše tabele, dejansko imela vrednost, ti dve vrsti nimajo, kar je pričakovano runtime. Torej vemo, da vsakič, ko tečemo za izbiro vrste, to je zagotovljeno, da teči n kvadrat čas. Ni variabilnost tam. To je samo pričakovati. In, še enkrat, če želite, da se naučijo več, da CS 124 v pomladi. Vse je v redu. Videli smo tole. Cool. Torej vstavljanje nekako. In sem verjetno bo Blaze skozi to. Ne bo vam fantje to kodo. Bomo le sprehod skozi to. Torej vstavljanje vrsta je vrsta za podobno izbire vrste s tem, da imamo tako razvrščeni in razporejene del matrike. 

Toda kaj je drugačna je, da ko gremo skozi enega po enega, smo vzemite karkoli številko je naslednji v naši razvrščeni, in ga pravilno razvrstiti v našem urejenem niz. To bo bolj smiselno s primerom. Torej vse, kar se začne kot neprebrani, Tako kot pri izbirnem vrste. In bomo rešiti to naraščajočem vrstnem redu, kot smo bili. Torej, na naši prvi izvedel vzamemo prvo vrednost in smo rekli, v redu, ste zdaj na seznamu, ki ga sami. 

Ker ste na seznamu sami, ste razvrščeni. Čestitke za to, da Prvi element v tem polju. Ste že razporejene vse na svoje. Torej, zdaj imamo urejeno in razvrščeni niz. Torej, zdaj bomo prvi. Kaj se zgodi med tukaj in tukaj je, da rečemo, OK, gremo pogledati Prva vrednost našega nerazvrščene niz in bomo vhod je v svojem pravilno mesto v urejenem array. 

Torej, kaj mi se bomo 5 in smo rekli, v redu, 5 je večja od 3, tako da smo samo vstavite desno na pravico do tega. Mi smo dobro. Torej gremo na našo naslednjo. In vzamemo 2. Smo rekli, v redu, 2 manj od 3, tako da vemo, da njim mora biti Sprednji del našega seznama zdaj. Torej, kaj moramo storiti, je potisnemo 3 in 5 dol in gremo 2 v tej prvi režo. Tako da smo pravkar jo vstavite pravilno mesto bi moralo biti. 

Potem pogledamo naše Naslednjič, in rečemo 6. OK, 6 je večja od vse, kar je v našem urejenem polju, zato smo samo označil do konca. In potem gledamo 4. 4 je manjša od 6, to je manj od 5, vendar je večji od 3. Tako smo samo vstavite naravnost v sredina med 3 in 5. Torej naj da malo nekoliko bolj konkreten, tukaj je nekako Ideja o tem, kaj se je zgodilo. Torej za vsako nerazvrščene element smo ugotoviti, kje v urejenem delu je. 

Torej, v obzir je razporejene in razvrščeni, moramo prečkati skozi in slika kam to paše v urejenem array. In jo vstavite s preusmeritvijo Elementi na desni strani jo. In potem smo samo vztrajati ponavljanjem skozi, dokler ne bomo imajo povsem razvrščen seznam kjer razvrščeni je zdaj nič in sortirani prevzame celota našem seznamu. Torej, še enkrat, da bi stvari še bolj konkretno, imamo psevdokoda. 

Torej v bistvu za i enaka 0 do n minus 1, da je samo dolžina naši array. Imamo nek element, ki je enaka Prvi niz ali prvi indeksi. Postavili smo j, ki je enaka. Torej, medtem ko je j večji od nič in matrika, j minus 1 je večja od element, tako da vse, kar počne je zagotoviti, da Vaše j res predstavlja razvrščeni del matrike. 

Torej, medtem ko je še vedno stvari razvrstiti in j minus ena is-- kaj je element ona? J ni bil nikoli definiran tukaj. To je nekako nadležno. OK. Nekako. Torej j minus 1, ste preverjanje element pred njim. Pravite, OK, je element preden kjerkoli sem am-- dovolimo, dejansko pripraviti to. Torej, recimo, da je to kot na našem drugem prehodu. Torej, jaz se bo enaka do 1, ki je tukaj. 

Torej, jaz se dogaja, da je enak 1. To bi bilo 2, 4, 5, 6, 7. Vse je v redu. Torej naš element v tem primeru se bo enak 4. In imamo nekaj j, ki je bo enaka 1. Oh, se j pomanjšanja. To je tisto, kar je. Torej je j enak i, kaj je to rekel je, da je, kot smo korak naprej, smo samo pazite, da nismo več indeksiranje na ta način, ko skušamo vstaviti stvari v našem seznamu razvrščeni. 

Torej, ko je j enak 1, v tem primeru in Niz j minus one-- tako matrika j minus 1 2 v tem case--, če je to večja od elementa, potem vse to počne seli stvari navzdol. Torej, v tem primeru, matrika j minus ena bo matrika nič, kar je 2. 2 ni večje od 4, tako da to ne izvede. Torej premik ne premakne navzdol. Kaj se tukaj to počne je le premik urejen paleto navzdol. V tem primeru, dejansko smo lahko do-- Naredimo to 3. Torej, če smo prehodili z ta primer, smo zdaj tu. To je urejeno. To je neprebrani. Cool? Torej i je enak 2, tako naša elementa enaka 3. In naša j je enaka 2. Torej gledamo skozi in smo reči, OK, je matrika j minus ena večja od elementa da gledaš? In odgovor je da, kajne? 4 je večji od 3 in j 2, tako da je ta koda izvede. 

Torej, kaj zdaj počnemo niz na 2, tako da tukaj smo jih zamenjali. Tako smo samo reči, OK, matrika na 2 je zdaj bo 3. In j bo enaka j minus 1, ki je 1. To je grozno, ampak vi dobili idejo. J je sedaj enaka 1. In j matrika se pravkar bo enako naš element, ki je bil 4. I izbrisati nekaj, kar ne bi smel imajo ali miswrote nekaj, ampak vi dobili idejo. 

To se premaknete na n. In potem, če bi bila ta, da bi se zanka Ponovno bi bilo reči, OK, j je 1 zdaj. In niz j minus 1 je zdaj 2. Je 2 manj kot naš element? Ne? To pomeni, da smo jih Vstavi ta element v pravem mestu v naši sortirane array. Potem lahko to traja in smo rekli, OK, naša sortirani array je tukaj. In bi bilo potrebno to številko 6 in se všeč, OK, je 6 manj kot to številko? Ne? Cool. Mi smo v redu. 

Še enkrat. Pravimo, 7. Je 7 manj kot konec naše urejenem niz? No. Tako da smo v redu. Tako da bo to urejeno. V bistvu je vse to počne se govori vzemi Prvi element Vaše razvrščeni matrika, ugotoviti, kam gre v urejenem niz. In to samo skrbi zamenjav za to. Ti si v bistvu samo zamenjavo dokler ne bo na pravem mestu. Vizualna podoba je, da ste gibljejo vse navzdol s tem. 

Torej, to je, kot pol balona vrsta-posestnik. Oglejte si študijo 50. Toplo priporočam poskuša kodo to sami. Če imate kakršnakoli vprašanja ali želite glej vzorčno kodo za vstavljanje vrste, prosim povej mi. Jaz sem vedno okoli. Torej v najslabšem primeru runtime in najboljši primer runtime. Kot ste videli fant iz tabele sem že ti so pokazali, da je tako n kvadrati n. 

Tako nekako gredo dol, kaj smo se pogovarjali o z našimi prejšnjimi vrstami, najslabša Primer runtime je, da če to je popolnoma Nerazvrščene, moramo primerjati vse te n-kratne. Mi cel kup primerjav ker če je to v obratnem vrstnem redu, bomo rekli, v redu, to je isti, to je dobro, in to bo treba primerjati pred prvo se preselil nazaj. In ko pridemo k konec repa, imamo za primerjavo, primerjati in primerjati proti vsemu. 

Tako da konča se približno n kvadrat. Če je pravilna, potem ste reči, OK, 2, si dober. 3, ste v primerjavi z 2. Ste dobri. 4, ki ste jo pravkar primerjati z repom. Ste dobri. 6, primerjati z repom, da ste v redu. Torej, za vsako mesto, če je že razporejene, delaš eno primerjavo. Torej, to je samo n. In ker imamo najboljšo prakso runtime n in najslabši runtime n kvadrat, nimamo pričakovan čas delovanja. 

Odvisno je le od kaos našem seznamu tam. In še enkrat, drugo Graf in drugo mizo. Torej razlike med vrstami. Jaz sem le, da bo vetrič skozi, sem Počutim se, kot smo obširno govoril o tem, kako vse vrste lahko spreminja in povezati. Torej zlivanjem je zadnja Ti se rodila fantje s. Imamo precej barvito sliko. Torej zlivanjem je rekurzivni algoritem. Torej, fantje vedo, kaj rekurzivna funkcija? 

Kdo želel povedati? Želite poskusiti? Torej rekurzivna funkcija je samo funkcija, ki sebe imenuje. Torej, če ste fantje poznajo z Fibonaccijevega zaporedja, da se šteje, rekurzivna, ker ste vzeli prejšnji dve in jih dodajte skupaj da dobite naslednjo. Torej rekurzivni, sem vedno mislim rekurzije kot kot spiralo tako ste kot spirala navzdol vanj. Ampak to je samo funkcija ki sebe imenuje. 

In dejansko, res hitro sem Lahko ti pokažem, kaj to izgleda. Torej rekurzivna tukaj, če pogledamo, da je to rekurzivni način, da se sešteje v array. Torej vse, kar moramo storiti, je imamo funkcijo vsote Vsota, ki traja velikost in vrsto. In, če ste opazili, velikost postopno znižanje po enem vsakič. In vse kar naredi je, če je x enak zero-- tako da, če velikost polja je enako zero-- vrne nič. 

Sicer pa povzema to Zadnji element matrike, in potem traja vsoto Preostali del matrike. Torej, to je samo zrušijo v manjše in manjše težave. Skrajšam zgodbo, rekurzija, funkcija, ki sebe imenuje. Če je to vse kar imaš od tega, to je tisto, rekurzivna funkcija. Če ste vzeli 51, boste dobili zelo, zelo zadovoljni z rekurzije. To je res kul. Je bilo smiselno na podobno 03:00 eno noč ven. In sem si mislil, zakaj nisem nikoli uporabljati to? 

Torej za urejanje z zlivanjem, v bistvu kaj se dogaja, da storiti, je, da je tekoč, da ga razčleniti in ga zlomil navzdol, dokler je samo posamezni elementi. Se posamezni elementi so enostavno rešiti. Vidimo, da. Če imate samo en element, to je že šteje razvrščeni. Torej na vhod n elementov, če je n manj kot 2, Samo vrnejo ker ta sredstva to je lahko samo 0 ali 1, kot smo videli. Tistih, ki se štejejo za Urejeni elementi. 

V nasprotnem primeru ga zlomil na pol. Razvrstiti v prvi polovici, razvrščanje sekundo jih pol, in nato združi skupaj. Zakaj se imenuje zlivanjem. Torej imamo tu bomo rešiti te. Tako smo ostali jih imajo dokler velikost polja je 1. Torej, ko je 1, smo pravkar vrnil ker je to sortirani matrika, in to je sortirani matrika, in da je sortirani matrika, smo vsi razporejene. Torej, kaj moramo storiti, je nam jih začele združitvijo. 

Torej, kako si lahko pomislite spajanje ste pravkar odstranili manjše število vsakega izmed pod nizi in samo dodajte na pojavila array. Torej, če pogledaš tukaj, ko imamo ti sklopi imamo 4, 6 in 1. Ko želimo združiti ti, gledamo na teh prvih dveh in smo rekli, v redu, 1 manjša, gre za spredaj. 4 in 6, ni nič za primerjavo je, jo samo označite na koncu. 

Ko združimo ta dva, smo samo vzemite manjši eno od teh dveh, tako da je 1. In zdaj bomo manjši od teh dveh, SO 2. Manjši od teh dveh, 3. Manjši od teh dveh, 4, 5, 6. Torej ste pravkar potegnete teh. In ker oni ' bilo prej urejeno, imate le eno Primerjava vsakič tam. Zato bolj koda tukaj, samo predstavitev. Tako da začnete na sredini in si nekako levo in desno in potem samo združiti tiste. 

In nimamo kodo za spajanje tukaj. Ampak, še enkrat, če greste na študija 50, bo pa tam. V nasprotnem primeru pride govoriti z mano Če ste še vedno zmeden. Tako kul stvar tukaj je, da je najboljši primer, v najslabšem primeru, in pričakuje, runtime so vsi v dnevniku n, ki je veliko bolje, kot smo jih gledati do konca naših vrst. Smo videli n smo na kvadrat in kaj smo dejansko tu je n log n, kar je super. 

Poglejte, kako veliko bolje, da je. Takšno lepo krivuljo. Toliko bolj učinkovito. Če si kdaj lahko, uporaba zlivanjem. To vam bo prihranilo čas. Potem spet, kot smo rekli, če ste v tej spodnjem območju, to ne pomeni, da da veliko razliko. Prideš do tisoč in na tisoče vložkov, boste zagotovo želeli učinkovitejši algoritem. In, še enkrat, naša lepa tabela vse vrste, da vidva danes naučili. 

Torej, vem, da je bilo gosto dan. To se ne gredo nujno da vam pomaga z vašo pset. Ampak jaz samo želim, da bi odklonitev da oddelek ne gre le za psets. Vse to gradivo je pošteno Igra za vaše kolokviji. In tudi, če ne nadaljujemo s CS, to so res pomembne osnove da bi morali vedeti. Tako da bo nekaj dni bo malo več pset pomoč, vendar pa bo nekaj tednov se veliko bolj dejanska vsebina da se morda ne zdi super koristno za vas prav zdaj, ampak obljubim, če boste še naprej na bo zelo, zelo koristno. 

Torej, to je to za oddelek. Do žice. To sem naredil v eni minuti. Vendar pa greste. In imam krofe ali sladkarije. Je kdo alergičen na kaj, mimogrede? Jajca in mleko. Torej, krofi so no? OK. Vse je v redu. Čokolada ne? Zvezdnimi. Zvezdne so dobri. OK. Bomo imeli Eksplozija, nato pa naslednji teden. To je tisto, kar bom. Vi fantje so super teden. Preberite si spec. 

Pustite me, če imate kakršnakoli vprašanja. Pset dve stopnji mora biti da se vam do četrtka. Če imate vprašanja o tem, kako sem se razvrščajo nekaj ali zakaj sem se razvrščajo nekaj tako, kot sem tokrat, prosim email mi, pridi govoriti z mano. Jaz sem malo nor to teden, ampak obljubim Jaz bom še vedno odgovoriti v roku 24 ur. Torej imajo velik teden, vsem. Vso srečo na vaši pset.