[Predvaja glasba] DAVID J. Malan: To je CS50. In to je začetek tritedenskega. Torej imamo veliko razburljivo Stvari za kritje danes. Veliko priložnosti za prostovoljci na odru. In končno, danes je Ne gre kode sploh. Ampak to je o idejah, in gre algoritmov, in dejansko prinaša nazaj nekatere smo se naučili od ničelne teden, kjer odpoklic smo uvedli to pošastnost. In zadolževanje navdih od tistega, za začetek za reševanje vedno bolj prefinjene Težave z algoritmom. Najprej pa nekaj objav. Torej, ena, če bi želeli, da se pridružijo Osebje in sošolci CS50 je na kosilu ta petek, tako tukaj kot v Cambridge, in v New Haven, obiščite tečaj je spletna stran, kjer je mogoče najti URL. Predavanje je to sreda bo ne bo tukaj v Sanders. To bo na spletu le, da uglasiti na spletni CS50 je, ali tukaj v Cambridgeu ali New Haven, kot tudi. In potem je problem določiti dva je že v vaših rokah. Če še niste končal v še, dovolite mi, ponuditi močno določa predlog da, še posebej zdaj, ko problem določa vnaprej, si res želite začeti zdaj, če ne Praćakati bit na vikend ali pred ko so prvič šla ven na Petkih, ker boste ugotovili, da oni niso nujno daljša ali bolj zahtevna na sebi. Mislim, da boste ugotovili, da je v splošno, se nagibajo k približno traja približno enakem času. Ampak to seveda odvisno od na študenta, in odvisno od miselnosti s katero se ji približati. Ampak vedno, si boste teči navzgor proti neki zid, in boš udaril nekateri bug, in ste pravkar ne bo lahko prebolela na neki točki. In to je zelo dragocen, da bi lahko odmakniti, pridi nazaj naslednji dan, pojdite na uradnih ur, post na CS50 Razprava ali podobno, da dejansko dobili deblokiranje. Tako da se vodijo v mislih. Začenši najzgodnejši možni meri je najboljša stvar, ki jo lahko narediš. Torej, tukaj je, kjer smo začeli razred, več kot v ničelni tednu. In lahko smo dobili prostovoljca tukaj, da mi pomaga najti mikrofoni? V REDU. Stoje že. Pridi gor. Ugani, to je, kako se bo na delo. Kako ti je ime? ALAN ESTRADA: Alan Estrada. DAVID J. Malan: Alan Estrada. Pridi gor. Me veseli. ALAN ESTRADA: Lepo vas je spoznati. DAVID J. Malan: In si tu pri nas v ničelno tednu, seveda. ALAN ESTRADA: sem bil. Sem bil. DAVID J. Malan: Torej lahko greš naprej in ugotovite, za nas Mike Smith, tako hitro, kot si lahko? Kakor hitro je mogoče. Dobesedno strga težave na pol, kot ga potrebujete, da. ALAN ESTRADA: Um. DAVID J. Malan: Dobesedno solzenje problem na pol. ALAN ESTRADA: Oh. Mm. Zelo dobro. DAVID J. Malan: OK. Dobro. Hvala. ALAN ESTRADA: Zelo dobro. V REDU. DAVID J. Malan: In zdaj, ste ga whittled navzdol polovici velikost problema. Zdaj smo do četrtine. Ali ste pozorni na na kateri strani smo vodenje? [Smeh] ALAN ESTRADA: Ja, jaz think-- DAVID J. Malan: Kaj oddelek smo v? ALAN ESTRADA: rute, tako. DAVID J. Malan: OK. Ampak Mike Smith se dogaja da bo po loncev. SO- [Smeh] V redu. ALAN ESTRADA: Kje smo iskali? DAVID J. Malan: Mike Smith. ALAN ESTRADA: Mike Smith. DAVID J. Malan: Zdaj smo v kirurški. Zdaj, zdravniki. Now-- ALAN ESTRADA: Let's- pojdimo z realnim. Real. DAVID J. Malan: Real. V REDU. Če potrebujete Real. Zdaj, v katero smer je Mike Smith? ALAN ESTRADA: Ta način. DAVID J. Malan: V katero smer? ALAN ESTRADA: Počakajte. M is-- kajne? Začeli smo with-- DAVID J. Malan: Ja. Oni so levo. Vaša pravica. ALAN ESTRADA: Ja. DAVID J. Malan: Torej, Mike je tukaj. ALAN ESTRADA: Kaj? [Smeh] Slab zgled, fantje. Žal mi je. DAVID J. Malan: To bo naučil vas, da skok iz svojega stola. ALAN ESTRADA: Oh. Oh. Imam te. Imam te. Oh. Oh. Ta is-- OK, imam te. Smith tukaj? DAVID J. Malan: Smith, hvala. Torej bom naprej iskal gor Smith? ALAN ESTRADA: Oh, ja. Ne ne ne. O, ne. To je moje. DAVID J. Malan: Oh, ti imaš Smith. V REDU. ALAN ESTRADA: Ja, dobil Smith tukaj. Oprostite, fantje. Mislil sem Michael-- smo iskali Mihaela. Žal mi je. DAVID J. Malan: To je v redu. Vse je v redu, zdaj smo v Paccini in Sons. ALAN ESTRADA: Paccini in sinovi. DAVID J. Malan: Samo ti in sem v zvezi s tem. V REDU. Najdi nam Mike Smith. Smith. ALAN ESTRADA: Smith. DAVID J. Malan: Smith. Mi smo v R za smeti. ALAN ESTRADA: Zanič. Oh. To bo trajalo nekaj časa. [Smeh] DAVID J. Malan: Čevlji. Mi smo v čevljih. ALAN ESTRADA: Zdaj smo gonna-- DAVID J. Malan: Lepo. ALAN ESTRADA: Which-- [Smeh] Oh, to je super. [Smeh] DAVID J. Malan: To je v redu. ALAN ESTRADA: Oh, to je dobro. Mislim, da ne bom imajo PSAT prijatelji po tem. DAVID J. Malan: Dobro. Sporting. ALAN ESTRADA: Sporting. Um, L, M, N, O, P. DAVID J. Malan: OK. Torej, kaj je trgati to na pol. To je v redu. Ta se konča slabo vseeno, ker Mike Smith ne bo v rumenih straneh. ALAN ESTRADA: Aw. DAVID J. Malan: Ne, to je v redu. Ampak kaj je pretvarjal, kot da je na tej strani. Torej sedaj, ko ste whittled problem navzdol na eni strani, in smo ugotovili, Mike Smith. [Vzklikati] OK, hvala. V REDU. To je bil izjemen. Ampak to je še vedno hitrejši kot linearno iskanje, kjer smo začeti izvajati začetek knjige, in gremo svojo pot od leve proti desni, sčasoma iščejo Mike Smith. In tako, če je telefon knjige imeli morda 1000 strani, Morda bi bilo treba nam 10 ali tako stran solze. Ampak ste morda vzvodom dotaknili domnevo Med vse to, kar pomeni, da je telefonski imenik vnaprej, kaj? OBČINSTVO: Urejeno. DAVID J. Malan: To je urejeno. Prav? To je urejeno po abecedi, zato da so vsi od teh imen in številk so razvrščene od A k Z-ih, in po abecedi vmes. Ampak danes, zdaj vprašati, Vprašanje, dobro, kako je Verizon ali telefon Družba je dobil v tej državi? Ker je to ena stvar za spodbuditev ta domneva, zato rešiti problem z Algoritem učinkoviteje. Ampak mi nikoli zares vprašal ničelno tednu, no, koliko je to storil stroški Verizon ali kdo drug da bi dobili ta telefonski imenik, v urejenem stanju? Prav? Ni važno, če je looking up Mike Smith je super hiter, če vas je potrebno leto za razvrščanje strani na začetku. Prav? Boste lahko tudi samo presejanje skozi randomizirani imeniku, če se dogaja, da je super drago, da ga rešiti. Torej, če imamo lahko še prostovoljca. Oglejmo si oglejte tukaj na kako might-- pridi up-- kako bomo morda lotili sortiranje teh. In če Jordanija bi dejansko Pridružite se nam tukaj na odru. Pridi gor samo za trenutek. Kako ti je ime? CAROLINE: Caroline. DAVID J. Malan: Caroline, pridi gor. In se boste pridružili mene in Jordanijo tukaj. Caroline, hvala. V redu. Torej, kaj imamo tukaj Caroline je 26 modrih knjig da FAS uporablja za upravljanje nekatere končne izpite. Ti so že težko najti, ampak, kaj smo naredili v vnaprej je, da smo dal ime nekoga na sprednji strani vsakega od njih, vendar smo hranijo preprosto s potem gašenju polna imena. Torej bi mi dal osebo z imenom L, D, J, B, vse od A do Z, ampak oni so v naključnem vrstnem redu. In tudi če bi jih, govoril Vaš pot skozi problem kot ti ne to, lahko greš naprej in razvrstiti ti za nas, od A do Ž OBČINSTVO: OK, tako da je L, kot je srednji. C se začenja. B. J pred L. B, Q. DAVID J. Malan: Drži, da je pomislili za eno sekundo. Ker v nasprotnem primeru je to le zanimivo, da ti, jaz in Jordanijo. Tam gremo. OBČINSTVO: [neslišno]. R. DAVID J. Malan: OK. Kaj delaš? CAROLINE: M prihaja po O. DAVID J. Malan: OK. CAROLINE: O. DAVID J. Malan: O, dober. CAROLINE: E. DAVID J. Malan: E, F. Ja. CAROLINE: T, U, V. DAVID J. Malan: V, T, U, V. Torej je Izgleda, da ste making-- nadaljuj. Izgleda, da delaš velik kup tukaj, in nekako velik kup tam. Torej, v prvi polovici abecede, Druga polovica abecede. V REDU. Dobro. Vrsta razdelitev problema na dva dela. M, N, X. Ja. CAROLINE: K. DAVID J. Malan: OK. K. Torej ste nekako izbiro jih enega za drugim, ga je dala levo ali desno, ali Z dogaja na tleh. V REDU. CAROLINE: Z dogaja na tleh. DAVID J. Malan: OK. Y se dogaja na tleh. Zdaj bomo lahko X. CAROLINE: G. DAVID J. Malan: G se dogaja levo. S se dogaja prav. Vredu, A bo vse tekme. CAROLINE: A, B, C, D. DAVID J. Malan: Zdaj, dobro. Imamo A, B, C. W dogaja tam dol. Vse je v redu, T. CAROLINE: H, J, J. DAVID J. Malan: H, I, J. Good. CAROLINE: V centru, sem gonna-- DAVID J. Malan: OK. Torej, zdaj, gremo na vrsto za združevanje teh različnih podporniki. Torej A do C, potem pa vidim, D, in E in F in G in H in I. Nica. J, K. In potem ta pile z glavo navzdol, ampak to je v redu. Sure. Režemo lahko nekatere kotičke. V REDU. In potem moramo W, X, Y, Z. CAROLINE: Ja. DAVID J. Malan: Odlično. Tako velika hvala Caroline za razvrščanje teh. [Vzklikati] Hvala. Najlepša hvala. Torej, zdaj pa menijo, za trenutek kako Caroline šla o tem, da je in kaj točno smo bili sposobni to-- kako smo mogli rešiti, da problem, ko smo bili tik saj cel kup naključnih vhodov. No, izgleda, da obstaja je bil malo sistema tam? Prav. Torej prejšnjih pismih v abecedi, ona je dajanje na levi, in slej črk v abecedi, ona je dajanje v desno. In takoj, ko je ugotovila, nekateri proksimalne pisma, tisti, da gremo desno drug poleg drugega, ona bi dal tistim v redu. In tako smo nekako imeli ti mali kupov sortiranih vložkov, ki se pojavljajo. In tako, da je precej všeč, kar večina od nas ljudi bi naredil. Mi bi nekako odbirati skozi njo, in sva nekako imajo mehanizem. Morda pa bi bilo težko napisati je določen v formuli po sebi. Se mu je zdelo malo bolj ekološki kot to. Torej, da vidimo, če bomo lahko zdaj veže problem z manj vložkov. Namesto, 26., dajmo nekaj narediti veliko manj s pravkar rekel, sedem, zadaj ta vrata, tako rekoč. Obstajajo le sedem številk? In če je cilj zdaj z je najti vrednost Poglejmo, kako učinkovito moremo iti o tem. In poglejmo, če bomo lahko zdaj začeti uporabljati nekaj številk, ali nekatere formule, ki opisuje učinkovitost našega imenika algoritem, naš izpit knjiga algoritem, in bolj splošno, iskanju informacij. Torej za to, naj gredo naprej, in na zaslonu na dotik tukaj, nepripravljena spletni brskalnik, ki ima točno teh sedem vrata. In če bi lahko dobil eno drugo prostovoljno pridi sem, Sem dal ta ista vrata tukaj. Hitro prostovoljec. Ta one-- demos se dogaja k hitrejši in hitrejši zdaj. Pridi dol. Kako ti je ime? TREVOR: Trevor. DAVID J. Malan: Trevor? V redu je, Trevor, pridi dol. Torej je Trevor tukaj prostovoljno narediti podoben problem, ampak tisti, ki je ožji obseg, in da se dogaja da nam omogočajo, da bi poskušali formalizirati zdaj postopek za sortiranje te številke. Torej, Trevor, lepo, da sva se spoznala. Torej, tukaj je niz, tako da govorijo, seznam sedmih vratih. Pojdi naprej in nam najti številko 50. In nato po dejstvu, nam je povedal, kako si ga našel. Morala be-- vso pravico. Ja, to je tista tukaj? Uh-oh. V REDU. Ste kliknili, da je eden. Dobro. In dobro. Zdaj ste kliknili, da je eden. In naj ti dam mikrofon, tako da ga imate v samo trenutek. Pojdi naprej in kliknite soseda, ki jih nameravate. Ja, dobro. TREVOR: Lahko sem unclick vrata? DAVID J. Malan: Ne, ne moreš unclick. TREVOR: OK. Tale. DAVID J. Malan: Kam želite iti? Kateri? TREVOR: To je ena. DAVID J. Malan: No. TREVOR: OK. Tale. DAVID J. Malan: Da. To je bilo dobro. V redu. Torej, kaj je bil tvoj algoritem ali Postopek za početje to, Trevor? TREVOR: sem šel skozi vrata, dokler sem našel 50. DAVID J. Malan: OK. Odlično algoritem. Tako da je v redu. Ker v bistvu, če sem razkril, kaj je v ozadju teh dveh drugih vratih, kaj bomo ugotovili, tukaj je, da imamo le naključno vhod. Tako da je bil dejansko kot dobra, kot bi lahko dobili. In v resnici, imaš boljši kot izčrpno iskanje celotno paleto, ker bi bilo res nesrečni, če bi zadeli številko 50 v zadnjem vrat. Toda kaj, če bomo namesto ti je dal predpostavko. Recimo, da sem nekako vse ta vrata vsem, tako da imate številke razporejene tokrat vendar tokrat je dejansko different-- ta čas, to je dejansko razporejene za vas. In zdaj je cilj pri roki je udaril številko 50. TREVOR: OK. DAVID J. Malan: Kaj je svoj algoritem bo? TREVOR: No, če je to razporejene, da je bodisi dogaja da be-- če največja do največjih, spušča, bo to prvi, ali če je nasprotno, bo zadnja. Torej, jaz bom samo izkoristiti ta vrata, in potem samo dotaknite zadnja vrata. DAVID J. Malan: Odlično. V redu. Tako smo ugotovili, številko 50. Torej takoj, ko boste vedeli, so bile razporejene smo bili sposobni vzvoda te predpostavke. Torej, oni preveč všeč primer telefonski imenik. Takoj, ko imate, tudi z majhen problem, kot je ta, vaši vložki vnaprej razporejene, smo lahko dejansko našli vrednost nedvomno učinkoviteje. In ti, če je ni povedal razporejene majhnih do velikih, ali velik, da majhne, in tako je bilo zelo smiselno začeti na enem koncu ali drugo da bi dejansko ugotovili, da ciljne vrednosti. Torej, hvala za Trevor kot dobro. In bom propose-- lepo naredil. Imamo malo posnetek, pravzaprav, da je med naših najljubših trenutkov v CS50, pri čemer včasih ti demos Ne čisto gredo po načrtu. In res zdaj sem potegnil napačen vmesnik s katero za uporabo zaslona na dotik. Tako da je bila moja krivda obstaja. Torej bo to za naslednje leto posnetek kot zakaj sem se tako, da kliknete na svojem zaslonu. Ampak kaj je na hitro pogledamo kaj se je zgodilo lani z Jay, ki je pritekel, veliko kot Trevor tukaj, prostovoljno, in v tem kratkem posnetku, boste videli, kako ta isti demo ni povsem razkrije enake naučili. [VIDEO PREDVAJANJE] -Vse Želim, da sedaj storiti je, najti zame in za nas, Res, številka 50 en korak naenkrat. -V Številka 50? -V Številka 50. In lahko pokažejo, kaj je za vsakim od teh vrat zgolj z dotikom s prstom. Prekleto. [Smeh] [END PREDVAJANJE] DAVID J. Malan: Torej, da je šlo zelo dobro. Tisti, ki so bili nerazvrščenih vrata. Jay seveda vse to našel prehitro. Trevor naredil veliko boljše delo v smislu teachable trenutku tako rekoč, letos v traja dlje, da ga najdejo. Seveda, nato pa smo dali Jay druga priložnost, pri čemer smo razporejene vrata, tako kot smo naredili za Trevor, in storil Trevor super tudi tokrat. Ampak Jay je to naredil pol tako hitro. [VIDEO PREDVAJANJE] -V Cilj zdaj je, da tudi nas najdete številko 50, ampak to algorithmically, in nam je povedal, kako boš o tem. -V REDU. In če boste ugotovili, da obdržite film. Če ga ne najdeš, jo dal nazaj. -Man. Oh! - [Neslišno] OK. Torej grem preveriti konce najprej ugotoviti, če there's-- Oh. [Aplavz] [END PREDVAJANJE] DAVID J. Malan: OK. Torej je jasno sortiranje vrata vodi k večji učinkovitosti. In tako, dvakrat hitreje je tisto, kar sem mislil tam. In tako Jay imaš srečo obakrat. In je prišel tudi srečo, da je zadnji leto, sem naročil nekaj Blu-ray diskov dejansko dati ven. Žal mi je letos smo niso imeli enake, Trevor. Ampak še vedno bolje, je bilo nekaj let nazaj. In nekateri od vas bi to vedeli, kolega, Sean, ki je, ko je bil v CS50, je izpodbijala z natančno isti problem, čeprav v SD, kot boste kmalu videli, nazaj v dan. In boste ugotovili, da ne samo, da je trajalo malo dlje, kot Jay, malo dlje, kot Trevor, je bilo dejansko je to čudovita priložnost da sodelujejo skoraj vsi v Množica a la Cena je desno, spodbujanje mu, da bi našli številko smo išče. Poglejmo. na hitro pogledamo. [VIDEO PREDVAJANJE] -V REDU. Torej, vaša naloga tukaj, Sean, je naslednja. Imam skriva ti vrata številka sedem. Ampak spravljen v nekaterih od teh vrat kakor tudi druge negativne številke. In vaš cilj je, da razmišljajo tega zgornji vrstici številk kot le niz, ali pa samo Zaporedje lističe s številkami stojijo za njimi. In vaš cilj je, da samo z uporabo vrh matrika tu našli mi številko sedem. In mi se potem dogaja, da kritika kako iti na to početje. -V redu. -Poišči Nam številko sedem, prosim. No. Pet, 19, 13. [Smeh] To ni trik vprašanje. Ena. [Smeh] Na tej točki, vaša ocena ni zelo dobro, tako da boste lahko tudi nadaljujem. Tri. [Smeh] Nadaljuj. Iskreno povedano, ne morem pomagati, ampak se sprašujem, kaj si celo razmišljal o tem, SO- [Smeh] Samo zgornji vrstici, tako imaš tri levo. Torej mi našli sedem. [Smeh] 17. Seven. [Aplavz] V redu. [END PREDVAJANJE] DAVID J. Malan: Torej smo lahko gledam te ves dan. In seveda, nekateri Letošnje demos morda bo sedaj končajo v naslednjem Letošnji video kot dobro. Torej, zdaj pa je dejansko osredotočiti na algoritmih tukaj, in videli, če ne moremo zdaj začeti formalizirati kako lahko gremo približno pridobivanje našo podatkov v tem stanju, da je to urejeno, tako da je na koncu, lahko smo dejansko je bolj učinkovito iskanje. In čeprav gremo uporabljati dokaj majhne podatkovne nize, kot osem številk mi imajo tukaj na krovu, končno posrečilo, da bi te iste ideje 1.000 vnosov, milijon vhodi, 4 milijarde vhodi, saj algoritmi se bodo v osnovi enaka. In zato je to naša zadnja priložnost za prostovoljce danes, vendar morda najbolj zahteven, za katerega smo potrebovali osem prostovoljcev da pridejo in nas sprehod skozi Proces razvrščanja, kar bo kmalu se na teh glasbe tu stoji. Naj začnem spet tukaj. Torej, ena v turquoise-- zelena je to? Ali si storila? Dva. Pridi dol. V REDU. Tri. Four. Naj me-- OK, pet. Bili ste imenuje svojega prijatelja. Šest, sedem in osem. Pridi gor. V redu. Najlepša hvala. Pridi gor. Pridi gor. V redu. Torej, kaj smo here-- in to imelo je med bolj nerodnih tiste, saj bo to zahtevajo, da humor me za samo malo časa. Vam mora biti številka ena. Kako ti je ime? ANNAN: Annan. DAVID J. Malan: Annan. David. Kako ti je ime? JOSEPH: Joseph. DAVID J. Malan: Joseph, ste številka dve. SERENA: Serena, številka tri. Stefan, številka štiri. Cynthia: Cynthia. DAVID J. Malan: Cynthia, številka pet. [Neslišno] DAVID J. Malan: [neslišno]. David, številka šest. MATT: Matt. DAVID J. Malan: Matt številka sedem. In? WAVERLY: Waverly. DAVID J. Malan: Waverly, številka osem. V redu. Če could-- Ops. Če vas vse, kar si Prvi izziv je osem glasbenih stojala tu sooča občinstvo. Če bi si dal svoje številke na ti glasba stoji na tak način, da ravnini s Iste številke na krovu. Torej bi sami videti kot da jih dajanje vaše številke na teh glasbe stoji tukaj. Odlično doslej. Odlično. V REDU. Torej sedaj, bomo vprašati Vprašanje v nekaj različnih načinov. Kako lahko gremo o sortiranje ti ljudje tu gor? Ker smo imeli nekaj pristopov prej, s čimer smo vrsta kar dve različni vedra. In potem smo bili na splošno piecing stvari skupaj. Takoj, ko smo videli dve številki ki je pripadal skupaj, smo jih skupaj. Dve črki, ki sodijo skupaj. Ampak poglejmo, če bomo ni mogoče formalizirati to, tako, da smo na koncu še nekaj psevdo-kodo, ki jo bo, s katero lahko rešili te probleme. Torej sedaj, gledam ven Na teh številkah tukaj. In vidim cel kup napak. Konec koncev, hočem ena na levo in osem na desni strani. In tako gledam ti dve, štiri in dve. In v čem je problem, seveda? Ja. So. Dva očitno pride pred štiri, tako da boste vedeli, kaj? Dovolite mi, da najprej sprejmejo požrešen pristop, Če bo, podobno kot problem nastavite one-- če se spomnimo iz Standard Edition problematičnih Set One, kjer sem samo lokalno rešiti problem da je prav tukaj pred mano in videli, kje me vodi. V REDU. Torej, dve leti in štiri, pusti me naprej in samo ti zamenjali dva. Če lahko fizično premikanje sami in vaš prispevek, Zdi se mi, da so gotten seznam v boljšem stanju. Zdaj, oni so dobri. Grem, da se premaknete naprej, štiri in šest, izgleda dobro. Ni problem. Šest in osem, OK. Osem in ena, še ena težava. Ker kaj je res približno osem in ena? Eden pride pred osem, in tako, kaj naj storimo? Oglejmo swap teh dveh. Ena in osem. In zdaj, bom nadaljuj. Grem, da pogled v prihodnost. In poglejmo, kaj se dogaja. Osem in tri, od Seveda je v okvari. Oglejmo swap. Osem in sedem, seveda. Ne deluje. Oglejmo swap. Osem pet, seveda, kaj je swap. V redu. Seznam je razvrščen. ja? OK, očitno ne. Ampak to je malo bolje, kajne? Ker je obvestilo, kaj se je zgodilo. Vsakič, ko smo izvedli zamenjavo, manjša Število vrsta prodrla na ta način, in večje število prodrla na ta način, ali pa bomo začetek rekoč mehurčkih na levo ali mehurčkih v desno. Zdaj, to ni dovolj, saj kvečjemu nekaj morda se premakne za eno mesto naprej, ali v najslabšem primeru število morda nadalje premakne za eno mesto. Torej, veste kaj, ta vrsta od delal precej dobro doslej. Naj samo poskusite znova. Dva in štiri, oni so OK. Štiri in šest, oni so OK. Šest in ena, v okvari. Torej, kaj je vaju zamenjali. In zdaj, opazili problem je se začne, da bi dobili boljše spet malo. Šest in tri, v okvari. Naj vaju zamenjali. Šest in sedem, da si dober. Sedem in pet, seveda v okvari. Sedem in osem, v redu. In zdaj, morda moram storite to še nekajkrat. In v resnici, mislim zase morda kolikokrat maksimalno Morda moram hoditi sem in tja? Vrnili se bomo na to. Torej, dve in štiri so še vedno v redu. Štiri in eno, nope. Torej, kaj je swap. In spet, opazili vizualno ena vrsta mehurčki na levi, če je treba. Štiri in tri swap. Štiri in šest. Šest in pet swap. Šest in sedem. Sedem in osem so dobri. Dobro. Mi smo dobili še boljši. Torej, poglejmo. Zdaj imamo dva in enega. Seveda, zamenjali. Dva in tri, tri in štiri, štiri in pet, šest in sedem, sedem in osem. Dobro. In veste kaj? Ker sem naredil eno spremembo tam, Naj narediti eno preverjanje prištevnosti. Naj gredo vse nazaj na začetek. V REDU. Eno, dvo Ja, vidiš? Nekaj ​​je bilo narobe. Tri, štiri, pet, šest, sedem, osem. In v tej zadnji priložnost, so ste zadovoljni z mojim zdaj ki zahtevajo je urejeno? V REDU. Vizualno, to je popolnoma res. Vendar funkcionalno, kaj se je tudi pravkar zgodilo V tem zadnjem priložnost, ki vam omogoča Za potrditev, da je ta seznam dejansko razporejene? Kaj sem naredil ali ne naredil to zadnjo točno? OBČINSTVO: ni bilo sprememb. DAVID J. Malan: Oprostite? OBČINSTVO: nobenih sprememb. DAVID J. Malan: ni bilo sprememb. Zato bi bilo neumno od mene, da narediti, da isti algoritem znova Če nisem, da vsaka spremeni prvič. In se je stanje ni spremenilo. Zagotovo ne bom, da bi koli spremeni drugič. In tako, da je zdaj varno povedati, je seznam razporejene. In res je to sedaj nekaj, kar bomo na splošno klic mehurček vrste, pri čemer paroma, ponovno popraviti napake, in spet, in spet, in vam nadaljuj naprej in nazaj, in naprej in nazaj, dokler vas da takšne zamenjave ne, na kateri točki ste lahko prepričani, ja končal določitvi vseh napak. Oglejmo reset in poskusite drug pristop. Če bi vidva segajo v vrstni red ste bili pred nekaj trenutki, ki je videti, kot je ta. Zdaj, vzemimo za pristop, malo več kot izpit knjigo, s katerim smo bili ves čas izberete črko abecede da smo nekako želeli da se ukvarjajo z naslednjo. Mogoče je bila visoka pismo, kot A, ali nizko črko Z. Torej, vsi se je vrnil v tem vrstnem redu. In sedaj mi je to naredil. Poglejmo, vem, da sem imel osem številk tukaj. Grem, da gredo naprej in samo namerno izberite najmanjši elementi. Prav? To se zdi intuitivno preveč. Zakaj ne najdem najmanjši element, ga dal, kamor spada, nato pa dobil naslednji najmanjši element, dal je, kamor spada, in ponovite. Ker intuitivno, da bi bilo preveč dela. Torej štiri, da je precej majhno število. Grem, da se spomnimo, kje je to. Počakaj minuto. Dva manjša. Naj se zdaj spomnim, kjer dva je, in pozabi na štiri. Bomo ukvarjajo s tem kasneje. Šest, me ne zanima. Osem, jaz ne zanima. Ena je moja nova majhna številka. Tako da bom, da se spomnimo, kjer je ena. Tri, me ne zanima. Seven, me ne zanima. Pet, me ne zanima. Torej, ne da bi padli oder letos, Grem, da zgrabite število one-- in kaj se vam je že ime? ANNAN: Annan. DAVID J. Malan: Annan. In če mi lahko pridružite na začetek seznama kaj je dal vam, kamor spadaš. Unfortunately-- kako ti je ime? STEFAN: Stefan. DAVID J. Malan: Stefan je na poti. Torej, preden Stefan reši to problem, kaj naj storimo? Kaj naj naredimo z Stefan? OBČINSTVO: [neslišno]. DAVID J. Malan: OK. Tako smo lahko storili. Mi lahko nekako vzeli Stefan in njegov štiri, in samo dal v spremenljivko in imajo na njej nekaj časa, s čimer se odpira prostor za eno številko. In to ni slabo. Jaz lahko predlagam, zakaj ne smo pravkar dal Stefan tukaj? Zakaj bi to kršilo eno idej smo začeli govorim o zadnjem trenutku, prejšnji teden? Ja? OBČINSTVO: [neslišno]. DAVID J. Malan: Ni indeks za to. Če menite, da o tem, res, kot matrika, to je kot negativnega, tako da ni pomnilnika dejansko tukaj, če je to res matrika, kot smo izjavil prejšnji teden v predavanju. Zato tega ne smemo storiti. Mi lahko ga shranite v spremenljivko. Ali veste, kaj? Slišal sem, da je nekdo drug jo predlagamo. Kaj lahko storimo z Stefan? Zakaj ne bi samo ga izselijo in ga postavil nad tem, kje je bil številka ena. Torej, če želite iti tja. In res je to zelo dobra rešitev. Zdaj pa na eni strani, sem imel nekako made problem slabše. Štiri je zdaj dlje od koder bi moralo biti. Moralo bi biti proti temu polovico. Ampak veš kaj? To bi lahko bila slaba sreča. Morda številka osem je bilo tukaj. In tako, mogoče mi bi gotten srečo, in potisnil osem bližje koncu. Torej, na koncu dneva, Nekako vsi povprečja ven. Mi ne potrebujemo približno štiri skrbi. Mene zanima zdaj je izbiro najmanjši element. In zdaj, kaj bom storiti je, da pozabi številka ena trajno, ker vem, da je seznam za mano je zdaj razporejene. Torej moj seznam je bil prej velikosti osem. Zdaj, to je velikosti sedem. Torej, moj problem je pridobivanje manjši, čeprav linearno. Torej sedaj, bom izberite Sedanji najmanjši element, dva. Šest, osem, štiri, tri, sedem, pet. To je bil najmanjši element. Torej, kaj sem storila with-- kaj vam je že ime? JOSEPH: Joseph. DAVID J. Malan: Joseph? Bomo zapustili Jožefa v mestu. Zdaj pa grem, da se pretvarjamo da ti fantje are-- dobro, Vem, da ti dve so že razporejene. Osredotočimo se zdaj na Preostanek seznama. Šest je trenutno najmanjši. Osem je večji. Štiri je zdaj trenutna najmanjša. Tri je zdaj trenutna najmanjša. In zdaj, bom izbrati tri, kdo is-- kaj je vaše ime? SERENA: Serena. DAVID J. Malan: Serena, če bi lahko zgrabite vašo številko in swap with-- KALSANG: Kalsang. DAVID J. Malan: Kalsang. Pridi nazaj, in smo bodo zamenjali tiste dva. In zdaj, kaj je dal to na avtopilot. Jaz bom šel in ga pustite, da vas fantje da izberete naslednjo najmanjšo elemente. Dun, dun, dun, dun. Številka štiri, kaj morate storiti? Odlično. Zdaj pa grem, da bi drugo sredino. Dun, dun, dun, dun. Vidim, pet je naslednji najmanjši. Zdaj bom vzeti drugo sredino. Dun, dun, dun, dun. Šest je najmanjši. Dobro. Sedem je najmanjši. Ni sprememb. Osem je najmanjši. Končano. Torej, kaj smo pravkar storili s ponavljajočim selekcioniranje enega elementa za drugim je izvajati nekaj, da smo dogaja, da formalizira kot izbirni vrste. In to je morda celo enostavneje razložiti, s tem, da dobesedno vse vas želite storiti, je samo vztrajati gre naprej in nazaj po seznamu izbiro, naslednji najmanjši element, dokler ste končali. Tako da je še lažje, morda intuitivno, kot zadnji. Poskusimo še zadnjič eno. Če bi vidva sami ponastaviti v naslednjih položajih eno končno čas, da vidimo, če ne moremo zdaj formalizirati en drug pristop. Pravzaprav bi nekdo tam rad predlagal kako še lahko gremo o tem? Brez premetavala iz Buzzwords ali vrste odgovorov, ki so že znane, samo intuitivno, kaj lahko storimo? OBČINSTVO: [neslišno]. DAVID J. Malan: Ja. Torej je bil odlični intuicija tam. Dobre stvari se zdi, da doslej zgodilo v računalništvu, ko delimo in osvojiti problem delitve je na pol in pol in pol. In tako v resnici smo lahko začnete, da to storim. In v resnici, da se dogaja, da se bomo glej, eden od naših najboljših rešitev še ni. Ampak kaj je prišel nazaj, da je pred dolgo. Dejstvo je, da bomo storili da je malo kasneje ta teden. Kaj še lahko storimo, da bi rešila to? Torej vsi tukaj v navidezno naključnem vrstnem redu. Veš kaj? Namesto da gredo naprej in nazaj, sem in tja, in nazaj vsakič, ta občutek Delam veliko hoje. Zakaj ne samo začeti na začetek seznama in samo dal štiri, kamor spada? Zato mi dovolite, prevzeti za trenutek, da moj seznam je samo to prvi element. Je štiri razporejene v tem trenutku, če je vse, kar sem mar je vse tukaj? To je nekako površno res, kajne? Tako kot seznam, ki vsebuje eno številko, in da je številka štiri je očitno razporejene. Torej, povej mi samo določi, da je ta seznam razporejene. Ampak zdaj imam preostanek tega seznama. Torej, zdaj, jaz srečati dva. Kje dva očitno pripadajo glede na štiri? Pred štirimi. Torej, kaj lahko storim tukaj? Kakšen je že ime? JOSEPH: Joseph. DAVID J. Malan: Joseph, če bi lahko korak nazaj za trenutek s svojo številko. In zdaj, kaj naj Stefan tukaj storiti? Oglejmo premik Stefana tukaj. In zdaj, kaj Joseph pridejo sem. In zdaj, mi zatrjujejo, da vse, tukaj je razvrščen. Torej, podoben rezultat, vendar bistveno drugačen pristop. Nisem niti pogledal, kaj je tam dol. Pravkar sem voditi ob elemente kot oni Izročil mi, in se z njimi spopasti. Torej sedaj, vidim številko šest. Kje številka šest pripada? Imamo dve, štiri, šest. Točno kje je zdaj. Torej, pustimo, da sam, in zdaj trdijo, da je ta del seznama je zdaj razporejene. In tako je to v osnovi meni razlikuje po tem, da sem samo premikanje po seznamu tukaj linearno, in jaz nikoli podvojitev nazaj. Da. V redu. Torej osem, kam spadaš? Točno tukaj. Popolna. Torej, zdaj, one. Uh-oh. To se počuti, kot da je bo drag. Sedaj v prejšnjem algoritem, Pravkar sem zamenjal ljudi. Torej, jaz bi mu dal vso pot na začetek, nato pa se preselil Jožefa. Ampak, če sem premakniti Jožefa, zdaj kaj se dogaja, da se motim? Zdaj, Sem nekako undone-- Sem sprejeti en korak naprej in nato en korak nazaj, ker zdaj Joseph bi bila v okvari. Torej, kaj je to. Če bi lahko številka ena in korak nazaj za trenutek. Kako lahko put-- kaj vam je že ime? ANNAN: Annan. DAVID J. Malan: Annan v mestu? Kaj se mora zgoditi v zvezi z na dve, štiri, šest, osem? Vsi morali preusmeriti. Torej, če osem bi želeli preusmeriti najprej, nato pa šest, nato štiri, nato pa dve. In potem Annan, če bi radi pridejo sem, dobro. Ampak tukaj, ki smo jih pravkar vrsta plačala ceno v neki določeni točki v algoritmu. Ker zadnjem času z izborom razvrščanje, in celo mehurček razvrščanje, Jaz sem hodil nazaj in naprej, naprej in nazaj, ki je vsekakor sešteva čas pametno in dobesedno postopno. Vstavljanje razvrščanje, sprva pogled, izgleda, da je super pametnejši, s tem, da sem samo tako počasen, postopen napredek, ampak ne bom to naprej in nazaj. Ampak, če je nekdo res od naročila, obvestila vse delo sem moral storiti. Sem imel, da se premaknete polovica seznama samo da bi naredili prostor za številko ena. Torej, to je isti znesek dela doslej ga meni, samo drugačna vrsta dela. Poglejmo naprej. Zdaj vemo, da je vsakdo med eno in osem so razporejene. Tukaj imam številko tri. Če vam je všeč, da poberem številka tri, korak nazaj eno. In kaj vi morate storiti? Ja. Torej, to je še ena, dva, tri korake. Tri enote časa, da je samo strošek mi, tako da tri Sedaj lahko fit. Končno, sedem. Pojdimo naprej in imajo boste naredili korak nazaj. To je samo nas bo stalo ena enota časa, ampak to je v redu. In zdaj, pet se dogaja, da je malo dražja. Če želite korak nazaj. Moramo se premakniti osem, sedem in šest. In potem se vsi zdaj razporejene. Tako velik roko našim prostovoljcem tukaj. Najlepša hvala. [Aplavz] Hvala vsem. Hvala vsem. Torej, kaj je zdaj vidim, kako dragi vsi so bili. Oglejmo si morda Najpreprostejša med njimi, mehurček nekako. In rečem najenostavnejši, samo zato, ker ga lahko rešili pohlepno jih pravkar popraviti parna problem tukaj. Fix parna težave tu, znova in znova in spet ponovimo toliko krat, kot si dejansko morali. Tako se izkaže, da z mehurček vrste, dobro, koliko korakov moram prevzeti prvi akcije tega algoritem? Jaz bi take-- dajmo see-- eno, dva, tri, štiri, pet, šest, sedem. In tam je tukaj osem elementov. Torej, to je, kot n minus 1 korakov do dobili od začetka seznama na koncu seznama. Toda z izbirnim vrste, se spomni, da sem znova izbiri elemente in spet, da je najmanjša, Jo bom v mestu, potem pa nisem videti spet za mano. Zato mislim, da je malo bolj jasno Takrat prvič, bom morda morali sprejeti vse n minus 1 korake najti najmanjši element. Potem sem jih dal v mestu, in jaz izselijo kdor je bil tu že prej. Ampak potem nimam za da gledamo na ta element, ker vem, da je že najmanjša. Torej, zdaj sem lahko ogledate na samo sedem elementi, nato šest elementov, nato pet elementov, nato štirje elementi. In tako matematično, če je n število elementov ali številk da smo začeli, si lahko predstavljate da je to isto kot n minus 1, plus n minus 2 koraka, plus n minus 3 koraki, plus n minus 4 koraki, vse pot navzdol na samo enem koraku. In jaz sem na moji zadnji osebo. In če se spomnimo, da je veliko od stats knjige ali math knjig imajo te formule, na Trde platnice nazaj ali pred njimi, se izkaže, da te serije lahko izrazimo bolj preprosto kot n-krat n minus 1 več kot 2. In to je v redu, če to ni v ospredju svojega uma. Ampak to je res. To je samo enostavnejši način pisanja. In potem, če menite, nazaj v osnovni šoli, ko ste šele začeli množenjem stvari, je to seveda, je le n kvadrat minus n deljeno z 2. Vse sem naredil, je razširila izrazi tam. In tako da je Reportaža to malo drugače. To je n kvadrat deljeno z 2 minus n / 2. Torej še enkrat, jaz sem samo nekako uporabe nekateri aritmetična pravila obstajajo. Ampak obvestilo, da zdaj največji izraz V tem izrazu, tako rekoč, je, da n kvadrat. Torej, ja, to je n kvadrat deljeno s 2, minus n / 2. Vendar na splošno, če je n bo veliko vrednost, Bom trdijo, da n kvadrat se bo prevladujoči faktor. To je le, da bo treba večji prispeva na število korakov od n / 2. Torej, kaj mislim s tem? Poskusimo preprost primer, celo čeprav je math dobi malo velik. Torej Predvidevam smo imeli 1 milijon ljudi na odru, ali 1 milijon stvari ki ga želimo rešiti. Oglejmo priključite milijon v natanko to formulo da vidite, koliko korakov je potrebnih skupaj razvrstiti milijon elemente uporabi recimo, Izbor vrste. Tako bi imeli isto formulo kot prej. Želel priključite milijon, tako da sem dobil milijon na kvadrat deljeno z 2, minus milijona deljeno z 2. Če naredim to math vnaprej Tu imamo 500 milijard minus 500.000, kar nam daje 499999500000, ki je precej darn velik. V bistvu, če primerjate zdaj 499000000000, 999000000, 500.000 zoper naše prvotne vrednosti, 500 milijard, to je tako prekleto blizu. Prav? n kvadrat deljeno z 2 daje us-- ali bolje, n kvadrat deljeno z 2 nam je dal 500 milijard. To je precej darn blizu da 499,999,500,000, kar pomeni, da se odšteje off 500.000, ali bolj splošno, odštevanjem off n kvadrat, ni res velik posel. N kvadrat si ti številke rastejo zelo hitro. Zdaj, da je to pomembno le, če kot mi, kot računalniški znanstveniki, se na splošno ne bo toliko skrbi o nianse teh formul in točno tisto, kar natančnih odgovorov. Želimo le, da je vseeno, veš kaj? Ob koncu dneva, ta formula je reda n razčetverjen. Ja, mi delimo z 2 noter. Ja, mi odšteje off n minus 2. Toda na koncu dneva, izraz da nas res boli in nas stane veliko stopnic je, da izraz kvadrat. In kaj računalniški znanstvenik se dogaja, da na splošno storiti se prezreti vse tiste manjše pogoji naročilo, in samo pogled na tisto, ki največ prispeva k stroškom. In to je lepo, ker smo lahko zdaj govori v veliko večji splošnosti o algoritmi, in jih lahko primerja. In dejstvo, da sem uporabo te O namerno. Ko sem rekel, o vrstnem redu o, sem posebej ki se nanaša na nekaj, imenovani veliki O. In big O je zapis da računalniški znanstvenik uporablja za opis zgornja vezan na nekaj. Torej, če ste rekli, da je algoritem je v velikem O n kvadrat, kot sem predlagal samo Trenutek nazaj, da sredstva da glede na njeno delovanje čas ali njeno učinkovitost, je potrebno na naročilo n kvadrat korake. Morda več, morda manj. Vendar je na red n kvadrat. In, da je zgornja meja. To se ne bo bolj boleče kot to. To se ne bo n kubikov ali 2 v N, ali nekaj veliko večjega. To je zgornja meja na vse, kar je ta strošek. Torej, glede na to, kaj je upoštevati le nekaj primerov. In to je samo končen seznam zelo pogosti tekoči časi za algoritme, ki je pomenilo, da je ponazarjajo nekatere stvari, ki smo jih že videli. Tako na primer, v primeru Izbor vrste, kaj jaz tukaj trdijo, je ta izbor Razvrsti je tek Čas je za vrstni red n kvadrat. V najslabšem primeru, bom imela cel kup naključnih števil tukaj. In kot smo videli matematično, če hodi po seznamu, skozi seznam, da izberete naslednjo manjšo znova in znova element, če I dejansko zapišite vse korake Vzela bom, kot sem predlagal formulaically pred tem, to je o vrstnem redu n kvadrat koraki, da sem jemljejo. In se izkaže, da je mehurček razvrščanje in vstavljanje sortiranje so prav tako počasi v najslabšem primeru. Razmislite, na primer, vstavljanje razvrščanje, zelo zadnja algoritem smo ga obravnavali, ki je imel nam pogled na elementu, in ga nato vstavite, kamor spada. In potem smo pogledal na naslednji element, in jo vstavili, kamor spada. Tako menijo najboljši možni scenarij. Recimo, da sem moji prostovoljci line up dobesedno, kot je ta, ena do osem, že razporejene. Koliko korakov je vstavljanje vrste bo trajalo, da razvrstite osem ljudi, če pridejo na odru videti takole? Osem ljudi je že urejeno. In uporabljam vstavljanje vrste. Ta zadnji algoritmov. No, dajmo reenact resnično hitro. Torej, če začnem tukaj, vidim enega. Kje nekdo pripada? Spada tukaj. Vidim dva. Kje dve pripadajo? Točno tukaj. Vidim tri. Kje tri pripada? Točno tukaj. Vidim štiri. Točno tukaj. Pet, šest, sedem, osem. Nobenega razloga ni, da se ponavljam. In tako, koliko korakov je, da v smislu n? To je velikostnega reda n koraki, kajne? n minus 1. Ampak sem vzel linearno številko stopnic, in zdaj sem naredil. Torej, to je najboljši primer, čeprav. Kaj najslabšem primeru? Kaj osem je bilo tam, in sedem bili tam dol, in ena in dva sta tukaj, tako da so seznam resnično obrnil? No, kaj se dogaja v resnici če je to število? In bomo naredili le nekaj primerov. Kaj pa, če, seveda, številka osem je tu, in number-- Ops. Pa kaj, če dejansko število osem je vso pot tja, in sem s pomočjo vstavljanja vrste? V REDU. Trdim, v trenutku, ko je na mestu. Toda zdaj, seven-- kje sedem iti? Seveda gre tukaj. Tako da sem moral premakniti osem več kot enem mestu. Zdaj šest, kjer ne gre? No, v redu. Zdaj pa moram premakniti osem več kraj in sedem več kot v mestu, in potem sem Pljuskanje navzdol šest. Torej prvič, je strošek me en korak popraviti stvari, potem me to stalo dva koraka popraviti stvari. Koliko korakov je bo trajalo, da se določi Stvari bi dal pet na pravem mestu? Tri. Ker zdaj moram premakniti en, dva, tri. Koliko korakov je bo trajalo postaviti štiri na pravem mestu? 4 plus 5, plus 6 plus 7. In tako je matematično enaka kar smo opisali v izbirnem vrste. Imamo to serijo da je samo povečuje. 1 plus 2 plus 3 plus 4, ali nasprotno, 7 plus 6 plus 5 plus 4 sešteje za današnjo namene, o vrstnem redu n kvadrat. Zato mi dovolite, določajo tudi, da bubble vrsta je tudi v n kvadrat. Ker z mehurček vrste, vsak ko sem šel skozi seznam, Jaz sem ob približno koliko korakov? Vsakič, ko sem dobesedno hoje od tam do tam? Približno n koraki. Ampak kolikokrat sem lahko morali iti skozi seznam? No, v grobem n čas. Mogoče n minus 1, vendar približno n krat. No, zakaj je to? No, z mehurček vrste, če začnemo z mehurček vrste, s seznama v najslabši možni Položaj, ki je spet v celoti nazaj, kaj se bo zgodilo? Sem šel skozi seznam in število eden pripada vso pot tja. Ampak s mehurček vrste, kako daleč pa eno premaknete na mojem prvem prehodu skozi seznamu? Koliko lise pa je dobil bližje na pravem mestu? Samo en. Torej, če vas nekako razlog skozi to, vsakič preko tega algoritma, Ob približno n korakov Davidovi. Toda koliko vozovnice skozi seznam je to bo trajalo za eno mehurček levo, kamor spada? Ima, da se premaknete, kot so, n prostori ta način. Torej samo narediti sortiranje seznama, Moram hoditi sem in tja n-krat. In vsakič, ko sem gledaš n elementov. Stori n stvari, n-krat na vrstni red n kvadrat. Zdaj pa bomo videli v nekaj od hlače, ki so vgrajeni v CS50 je naslednji problem nastavljen, drugačen pristop pri teh, vendar za zdaj, kaj je samo razmisliti nekatere druge takta še posebej, če sortiranje tisti sprejmejo malo časa, da se potopi v. Kaj je algoritem, ki smo jih že videli da je o vrstnem redu n korakov? Kaj naj bi linearno številko od korakov, ki smo jih videli doslej? Kaj je to? Iskanje telefon imenik. Prvi algoritem. Prav? Kje smo linearno išče Mike Smith? Prav zares. Od ničelne tednu, ko sem začel obrača eno stran naenkrat, in sem celo rekel, da je bila vrsta linearnega občutek algoritma in smo imeli tisto sliko na plošča z ravnimi rdečo črto in ravno rumena linijo, to so bili dejansko algoritmi, ki so v velikem O n. Ker, da bi našli Mike Smith v telefonu Knjiga n strani, v najslabšem primeru, me n korake lahko traja. Kaj pa ob navzočnosti? Ena dva tri štiri pet šest. Kaj je čas za to tekmovanje v teku Algoritem za sprejemanje udeležbo? Big O n, ker v teoriji sem morali izpostaviti vse v sobi. Zdaj kot prahi, kaj približno drugi optimizacija od ničelne teden? Dve, ​​štiri, šest, osem, 10, 12. Računalniški znanstvenik bi zavedaš, počakaj malo, da je o vrstnem redu n deljeno s dveh korakih. Prav? Ker delam dve osebi naenkrat. Ampak bomo prezreti ti nižje pogoji naročilo, in smo le, da bo mečejo razkoraka z 2, in samo reči, velik O n ta algoritmom, kot tudi. Kaj pa tale? Bomo preskočili nekatere od njih, ampak kaj je algoritem, ki je dnevnik n? To je trajalo približno log n korakov? Razkorak in vladaj. Točno tako. Tako kot na primer telefonskega imenika v nič teden in že danes, kjer smo razdelili problem znova in znova in znova. Jo narisal smo na ladji v tednu nič kot upognjena zelene črte, in mi je povedal, da je dan, da je logaritemski algoritem. In res se je število korakov je potrebno za opravljanje deli in vladaj, ali binarno iskanje, kot bomo začeti kliče, tako kot v telefonskem imeniku, je reda log in korakov. In to je malo čudno eno. Kaj je en korak, ali natančneje konstantno število korakov? Mogoče je dva, morda je tri, toda računalniški znanstvenik pravkar ga poenostavlja kot veliki O 1, nekateri konstantno število korakov. Kaj je nekaj, kar bi lahko storili, da je konstantno število korakov? Kaj je čas ploskati teče? Constant čas. Prav? Všeč, kaj je čas teče delaš karkoli, da ima samo eno delovanje, kot so tiskanje F Hello World. Da bi lahko rekli, da je stalen čas razen če je manj igralcev primeru s tiskalno F, kaj bi lahko čas teče tiska F dejansko? In zakaj? Kaj je merilna n v tem primeru? OBČINSTVO: [neslišno]. DAVID J. Malan: Točno tako. Število znakov želimo natisniti. Torej, to je zelo kontekstno občutljivi. Danes smo se osredotoča veliko na črke in številke tukaj na krovu. Ampak to je lahko tudi znaki v dejanskem nizu. Tako se izkaže, da je še ukrep, ki se bo začelo skrbeti, in da je nasprotno z velikim O, tako rekoč. To je omega zapis. Ker je velik O pomeni, kaj se je Zgornji vezani na svojem tekaškem času? Maksimalno, koliko časa Morda kaj vzeti? Omega-- Žal to vedno znova up-- je nasprotje tega, pri čemer je spodnja meja Količina časa nečesa lahko traja. So. na primer, kaj je algoritem da je vedno n Squared korake? No, eden od algoritmov, ki smo jih videli Danes, v resnici, morda tudi to. Izbor vrste. Izbor vrste je precej neumno. Tudi če algorithm-- žal, tudi če je matrika že razporejene, Izbor vrsta se bo hodi po seznamu se prepričajte, da ima najmanjši element znova in znova in znova. In čeprav ste ljudje v publika ve, da, počakaj malo, ste že opravili najmanjši element, računalnik ne ve, da dokler ne izgleda vse skozi seznam. Podobno nižjo mejo, ki lahko upoštevajo tudi lahko linearen čas. Koliko časa traja, da se sortiranje n elementov v najboljši primer s pomočjo nekaj podobnega mehurček vrste? Recimo, da vaš seznam je že urejeno. Rekli smo, mehurček nekako popelje na vrstni red n kvadrat korake. Ampak kaj, če ga je že urejeno? Kaj pa, če se zavedaš, po ena podaja skozi niz da ste naredili nobenih zamenjav? Ali morate hraniti izdelavo več prelazov? No. Torej nižja vezan na mehurček vrste bi lahko rekli, da je linearna. Omega n. In bomo lahko ogledate na drugi o njih, kot tudi. Torej, kaj je na hitro pogledamo na samo vizualizacijo tukaj da vidim, kako ti razlikovati sami. Jaz bom šel dol v to Stran, ki je na voljo na spletni strani C50 je, vendar pa bo bolečina priti delajo, saj uporablja tehnologijo z imenom Java programčki, ki je v veliki meri podprta v teh dneh, vsaj Chrome in nekaterih drugih. In naj me iti naprej in pospešila ta in razložiti, kaj se dogaja. To je dokaz balona nekako, prvi algoritem smo pogledal. In to je vizualizacija tem, da vsak teh palic predstavlja število. Večji kot je bar, večje število. Manjša kot je bar, manjše število. In kaj si lahko ogledate vizualno, čeprav čeprav to se dogaja, super hitro, je, da je rdeče bar, kot sem jaz, hoja naprej in nazaj določitev problemov. Vidite lahko, da je večji elementi so res prepihavanje do desne, in manjše elemente so prepihavanje navzgor na levi strani. In tukaj, če bomo dejansko bolj pozorno, bomo lahko dejansko štetje število primerjav in zamenjav ki so bile narejene. Toda namesto da bi si oglejmo na drugi algoritem smo pogledal prej z našimi prostovoljci, izbor sort. Vizualno, da ima zelo drugačen učinek. Ampak to je, še enkrat, zelo intuitivno, v da se držimo izberete naslednjo manjšo element, in imamo malo srečen. Ki bistveno hitreje počutil. Ampak, če bomo to spet in spet tekel in spet z veliko vhodov, bomo videli, da je to res še vedno v veliki O n kvadrat. Naredimo eno zadnjo tukaj, vstavljanje razvrščanje, ki je bil tretji algoritem smo pogledal in odpoklic da to imamo opravka z elementi, saj jim naleti, potem pa morda premiki stvari kot da bi naredili prostor, vstavljanje elementov, kamor sodijo. In tudi to konča, s katero se končni rezultat. Zdaj vsi trije tistih počutil precej hitro. In res, sem jih tekel na zelo dober posnetek. Ampak v bistvu, oni vse precej grozno, če sem iskren. Vse te algoritmov doslej da je vožnja v veliki O n kvadrat traja kar nekaj Čas je, da teče na koncu. In res, lahko vidimo, in občutek je to nazadnje če potegnem to tretji in zadnji demo. To je še en vizualizacija, ki se dogaja pokazati mehurček vrste na levi strani, Izbira nekako v sredini, in kaj, kot eden od naših ročno postavlja prej predlagal, združiti vrste na desni strani. Deli in vladaj Strategija na desni strani. In to je v resnici, kaj smo dogaja, da pogled na sredo. Ampak kaj je čas te teči vzporedno. To je približno enako število Elementi, vse teče istočasno. Bubble vrsta vs izbor Razvrsti vs zlivanjem. Zdaj, oni vse teče v teoriji hkrati. CPU teče pri enako hitrostjo, vendar pa lahko občutite, kako dolgočasno je to Zelo hitro bo postala, in kako hitro, ko vbrizgamo malo tedna algoritmi ZERO lahko smo pospešili stvari. In sedaj dajmo primerjati ti v eni zadnjem obliki. Grem, da gredo naprej na spletni strani CS50 je, kjer je imamo to končno povezavo za danes, kjer je nekdo na internetu vljudno dal skupaj video, ki ujame, kaj drugačnega razvrščanja algoritmi sliši. To je vstavljanje vrsta. [Piskajoči] S katerim ste uporabo frekvence ki temelji na višino bar vrat. To je mehurček vrste. [Zviti piskajoči] Prihaja naslednji is-- prihajajo up zraven is-- izbor vrste, kjer še enkrat, bomo izbiro Naslednji najmanjši element, in smo lahko videli, da raste od leve proti desni. Zlivanjem, naš zmagovalec doslej danes. Opazili, kako je to tako, da stvari v [neslišno] polovice in četrtine. Gnome vrste, ki smo jih imeli, ne govori, in ustvarja vizualno in audally malo drugačno obliko in zvok. Greš naprej in nazaj, čiščenje stvari. Tudi odjaviti Urejanje kopice na spletni Ta tip je. In to je to. Vam bomo videli naslednjič. [WHOOSHING IN MUSIC]