SPEAKER: V redu, to je CS50. To je konec tritedenskega, in če niste izkoristili že, vem, da bo kosilo ta petek, kot je običajno, kadar boste lahko uživali dober pogovor in hrane na Fire and Ice z nekaterimi CS50 je osebje in sošolci. Glavo na tem URL tukaj. 

Zdaj se morda spomniš, ali si lahko kmalu seznanjeni z, te stvari tukaj, ki so podani na koncu semestra za mnoge razrede. Tako imenovani izpit modre knjige, v kateri napišete svoje odgovore na izpite. Zdaj imam tukaj 26, kot modre knjige, na vsakem od njih je napisano ime, A do Z. In celo imena so tako preproste, skozi Z. In eden cilji pri roki danes se bo za naprej, kaj smo začeli v ponedeljek, ki je ni Toliko gledaš kodo, ampak res gledaš idej in reševanje problemov. Eden od ciljev in obljube o tem tečaju je, da te nauči, da razmišljajo bolj previdno, bolj načrtno, in za bolj učinkovito reševanje problemov. In res, kar lahko naredimo, da res celo brez dotika kode. Torej imam nekaj slonov do danes, oranžna in modra, če bi lahko dobili enega prostovoljca, Mogoče od dlje nazaj kot ponavadi. Kaj pa tam, pridi dol. Cilj, ki se bo na pomagal plus upravlja ta izpit tukaj. Kako ti je ime? 

OBČINSTVO: Mary Beth. SPEAKER: Mary Beth, pridi gor. Naj vzamem mikrofon tukaj za vas. Lepo, da sva se spoznala. 

OBČINSTVO: Me veseli. SPEAKER: V redu, tako da sem moral Tukaj blue knjig do Z, in bom pretvarjal, da Imam enega od študentov, in oni, ki prihajajo v nekoliko naključno na koncu triurni izpit blok, tako oni končali v nekaj semi-naključnem zaporedju, kot je ta. Sedaj je vaša naloga, v trenutku se dogaja da bilo-- to je pravzaprav, kako so dobili Izkazalo se je ob koncu leta razred, najverjetneje. Vaša naloga zdaj se bo precej preprosto, razvrstiti te modre knjige za nas od A do Z. 

OBČINSTVO: Oh, to je bo večno traja. 

SPEAKER: In bomo gledal kot ste to storili, ni pritiska. OBČINSTVO: Ne, nobenega pritiska ali kaj podobnega. 

SPEAKER: In za zabavo, kaj je dal gor timer. 

OBČINSTVO: Tako zelo zabavno, tako zabavno. 

SPEAKER: Lahko držite mikrofon za vas. V redu, smo samo podvojili hitrost. Torej, v tem času, mi predstavljajo, kaj je bo vprašanje, Mary Beth je, kaj počne, kako je ona bo o reševanju tega? In v resnici, morda nimate kdaj razmišljal o nečem tako preprosta, kot takrat, ko ste izbrali do 26 knjig, kot je ta, ki imajo naravno naročanje na njih. Kakšen je postopek da ste dejansko uporabo? Je dokaj random samo obiranje prvo kar vidite in ga je dala v svojem mestu? Ali najprej premakniti roke okoli išče potem išče B? Ali ste si ogledali par od njih ob bok in samo reči, počakaj malo, to ni v redu, nato pa zamenjali vrstni red? Videli smo že v ponedeljek da obstaja več načinov v katerem lahko to stori, in res, kot smo blizu konca tukaj, Jaz bi se seznanijo morda česa Mary Beth počne. Imamo nekaj kupi kot se zdi, Večji ena, tri manjše. 

OBČINSTVO: Jaz sem jih naročanje ko sem našel dve pismi da vem, so mi skupaj v zaporedju, Sem jih dal skupaj, tako da ne vem treba skrbeti za ohranjanje tir celo vrsto knjig. To je samo, oh, je prva, Imam ta kup tukaj. SPEAKER: Torej, skoraj kot puzzle kosov, ki imajo pravo obliko za ujemajo med seboj. OBČINSTVO: Precej, ja. SPEAKER: OK, odlično. In zdaj vsako od teh Piloti se verjetno razporejene? 

OBČINSTVO: Ja. 

SPEAKER: Dobro, skozi Z. All Dobro, čestitam, uspelo ti je. Imate izbiro. Blue? V redu, hvala ti za to. Torej, Mary Beth je predlagala kaj je njen pristop je bil, ampak tisto, kar je še en pristop, kako vas bi šel okoli sortiranje te stvari? Kaj bi vi storili? Zapis premagati, bi bilo eno minuto in 50 sekund ali tako, plus tisti, pozabil sem, da računajo. Kaj bi vi storili? Ja? OBČINSTVO: Vzemi kup. Začeti od začetka. Preverite svoje dokumente. In če je vrh enega višja kot, morda, so, dno ena višje, nato pa jih vključite. 

SPEAKER: OK, da se začne na vrhu in na dnu, in potem delajo svojo pot navznoter, kot da jih je zamenjala? OK, tako malo podobna v duhu mehurček vrste, vendar izbiri ekstreme ni sosednji pari. Ampak kratko o tem je, da obstaja gotovo kup različnih načinov bi lahko to storili, in Iskreno se vam zdi nekako sprejela nekaj pristopov, kajne? Ste naredili nekakšen štirih sortiranih pilotov in nato pa jih učinkovito združila skupaj. In to je, si trditi, drugo Tehnika v celoti. Nisi ga obravnava kot en velik kup, si razdelili problem v štiri štirikolesniki, če hočete, in potem nekako jih združili na koncu. 

Torej, kaj menijo, končno, kako drugače bi lahko to storimo. Formalizirana smo pojem mehurčkov razvrščanja zadnjem času, in bubble sort odpoklic je bil algoritem, ki smo vizualizirali z osem vaših sošolcev do tu, navidez naključno razporejene na prvi. In potem smo se odločili po parih, če dva elementa sta v okvari, preprosto jih swap. Torej, štiri, dva pa sta očitno v okvari, tako da ti dve sošolci zamenjal igralno mesto. In potem smo ponovili s štiri in šest, nato pa šest in osem na vsaki ponovitvi premika v desno. 

Torej, glede na osem ljudi, koliko paroma Primerjave sem naredil med hojo od leve proti desni v eni taki ponovitvi? Koliko primerjave? Seven, kajne? Ker če obstaja osem ljudi, pa imate par jih in jih premikati en hop na desno, ti ne boš imel osem primerjave, ker ne moreš primerjati element proti sebi, da bi ali samo nesmiselno, tako da boste imeli sedem. Ali bolj splošno, če imamo n ljudi, smo narediti n minus 1 primerjav z mehurček vrste. 

Torej, kaj menijo, da je sedaj, kako dobro ali slaba bubble sort dejansko je, in poskusite da bi sami besedišča s za kritiko algoritmov, kot je ta, in kmalu je naša lastna. Torej prvem prehodu skozi mehurček sortiranje, prvič Hodil sem od leve proti desni po vsej oder, vzel me n minus 1 primerjav. In to se dogaja, da je moj merska enota, kajne? Nekako sem govoril in sprehodu, nekoliko hitro, nekoliko počasen, tako štetje moje število sekund ni posebej govoril, vendar štetje števila operacije, da sem storil v ponedeljek, primerjavo dveh ljudi, da se počuti kot lepo mersko enoto. 

Torej n minus 1 koraki prvič, pa vendar, kaj se je zgodilo po tem? Kaj je eno glavo enega priložnost skozi sicer nesortiranih seznamu? Kaj mi lahko poveste o tem elementu , ki je bil vse do tja? Ja? To je bil največji element, kajne? Številka osem, čeprav je začel sem vsakič, ko sem jo primerjamo z sosed, ona hranijo prepihavanje do desno z strani seznama. In res, da je, kjer algoritem dobil ime. 

Zdaj pa jih je ta logika, koliko primerjave Moram narediti za drugič Jaz bi to podajo iz leve proti desni? n minus 2, kajne? To bi bilo samo zapravljaš svoj čas, če I obdržati primerjavo osem proti nekomu sicer zato, ker smo že vedeli, je bila na pravem mestu. Tako da je malo optimizacija, tako da je naslednji akcije se bo n plus minus dva koraka, kjer je n število ljudi. Sedaj lahko nekako ekstrapolacijo, čeprav če niste računalniški znanstvenik, kako se to konča. Na koncu tega algoritma, predvidoma imaš samo eno primerjavo levo. Moraš nekako popraviti začetek seznama, v primeru dveh in eden v okvari in mora biti ena in dva, tako da je ta dna ven na plus 1 final primerjava. 

Zdaj dot, dot, dot vrste valov je roke na nekatere juicier podrobnosti ampak greva naprej in poenostaviti. Če se spomnite iz visoko šola, odkrito povedano, veliko vas imeli matematične knjige, ki so imele malo cheat sheet na naslovnici ali zadnji pokrov, ki vas je pokazala kaj serije summations kot to na koncu seštejejo. V splošnem primeru, če imate spremenljivka, kot n in dejansko ta, če si pogledal na vaš old school math knjiga, boste videli, da je to dejansko dodaja do te vsote tukaj n krat n minus 1 vse deljeno z 2. Za zdaj naj mi določajo to je res, da na preskok vere, da je tisto, kar v seštevku do, in smo lahko dokazati, da je v bolj splošnem primeru. Ampak zdaj pa razširiti to. Torej pomnožite to ven, tako da je n kvadrat, minus n, vse deliti z 2. To je res n kvadrat, deliti z 2, minus n več kot 2, tako da je vse lepo in zanimivo. Toda kaj se zgodi, če bomo zdaj plug-in v vrednosti? Recimo nisem imela osem ljudje, ampak pravijo milijon. In milijonov samo zato, ker to je precej velika številka, pa vtič, da je v in videli, kaj se bo zgodilo. Torej, če priključim milijonov v to formulo Jaz bom dobil milijon na kvadrat, deliti z 2, minus milijonov, deljeno s 2. Zdaj, kaj je, da bo enako? Torej, 500 milijard, minus 500.000. In če sem v resnici naredil da math ven, da se sredstva da sortiranje milijon ljudje z mehurček vrste mi lahko traja 499999500000 stopnice ali primerjave na koncu, smo samo ekstrapolacijo. 

Da se počuti precej počasen, vendar odkrito povedano merjenje eno posebno vhod kot je ta, ni vse tako zgovoren. Ampak res pa predlaga, da se kot n dobi večji in večji, ta algoritem vrsta počuti slabše in slabše, ali res začutite bolečino, ki potenciranje, da je n kvadratna , ki dodaja do precej hitro. In ta podrobnost ni izgubil na ljudi, v resnici Pred nekaj leti gotovo senator, ki je bil kampanje, je sedel na razgovor z Googla Eric Schmidt direktor takrat, in je izpodbijala z vprašanjem podobno kot smo danes raziskuje. Oglejmo pogled. 

[VIDEO PREDVAJANJE] 

-Senator, Da si tu na Googlu, in mi je všeč razmišljati o predsedovanju kot je razgovor za službo. Sedaj je težko dobiti delo kot predsednik, in greste skozi mrzlica zdaj. Prav tako je težko dobiti službo v Googlu. Imamo vprašanja, in mi Od naših kandidatov vprašanja, in to je eden od Larry Schwimmer. Kaj-- mislita, da sem hecam se, da je prav tukaj. Kaj je najbolj učinkovit način za razvrstiti milijon 32-bitnih celih števil? 

-Well-- 

Žal mi je, maybe-- 

Ne, ne, ne. Mislim, da je mehurček vrste bi bilo napačno pot. 

Daj no, kdo mu je to povedal? Nisem videl računalnika znanost v ozadju. 

-Mi Smo dobili naše vohune tam. 

-OK, Kaj je vprašal drugačen intervju vprašanje. 

[END VIDEO PREDVAJANJE] 

SPEAKER: Torej, govorimo o Določene številke čeprav, se ne bo vse to koristno. To ni življenjsko lekcijo, da bubble sort, saj milijon vložkov, Lahko traja tudi do 500 milijard korake. Vam ne morem posploševati Tudi učinkovito od in sprejemati dobre odločitve o oblikovanju Pri pisanju programov. Torej, kaj je osredotočiti, čeprav o tem, kako bomo lahko poenostavi ta rezultat. 

Tako sem označen z rumeno barvo tukaj Rezultat n kvadrat deljeno z 2, tako na kvadrat milijonov deljeno z 2, in nato Sem izpostavila, kaj Končni odgovor je bil ko smo odšteli off n deljeno z 2. In trditev, bom, da je zdaj, kdo za vraga briga, če odštejemo off malo stara n kot 2, ko je prva del te formule je toliko večji? Dominira drugi Izraz, n kvadrat deljeno z 2 je toliko večji, je jasno, saj n postane velik kot milijon, da je res velika razlika v Konec dneva med 500 milijard in 499.999.500.000? Ni res. In kaj bomo storiti, saj je računalniški znanstveniki prezreti tiste nižje pogoje red in da kaj takega in res samo to poenostavi na Izraz, ki bo pomembno. Večje naši podatkovni nizi dobili, večji naše baze podatkov dobiti, več spletnih strani moramo iskati, bolj prijateljev imate na Facebooku. 

Kot n postane večja, smo zares dogaja, da skrbi za največje Izraz v vsakem takem analize naša algoritmi uspešnosti. In bom rekel, veš kaj, bubble sort je o vrstnem redu veliki O, o vrstnem redu n kvadrat. To ni ravno n kvadrati, kot smo videli, ampak kdo v resnici briga o teh manjših pogoji, in odkrito, ki resnično briga, če delimo z 2? To je samo konstantni faktor. In 500 milijard v primerjavi z 250 milijard res, da je velik za posel? Jaz bi samo čakati eno leto, Naj svoj laptop dobesedno dobili dvakrat hitreje v strojni opremi, in da je vrsta razlike samo izgine seveda sčasoma. 

Kar nas skrbi, je izraz, del izraza, ki se dogaja, da se razlikujejo kot naš input dobi večji in večji. In res, v realnem svetu, da je tisto, kar se dogaja vse pogosteje se vnosi za naše probleme in algoritmi so dobili večji. Tako velik O se bo zapis, asymptotic zapis, ki sva jih uporabite kot računalniški znanstveniki za opisovanje uspešnost ali čas teče, algoritma. Tako, da lahko primerjamo algoritme na različnih računalnikih pisnih z različnimi ljudmi, z uporabo nekateri v osnovi podobna metric kot števila primerjav ste odločitev, ali morda število zamenjav delaš. 

Kaj mi ne bo Število je količina časa da prehaja na uro na steni tipično. Kaj ne bomo skrbeti o tem, koliko pomnilnika ste danes uporabljajo na Vsaj, čeprav je to drug vir, bomo morda izmeriti. Bomo poskušali utemeljiti naše analize na samo osnovnih operacij, tisti, odkrito, da si lahko ogledate najbolj vizualno. Torej, z nekaj podobnega veliki O n kvadrat, Trdim, da O n kvadrat je zgornja vezan na tako imenovane čas mehurček vrste teče. Z drugimi besedami, če vas želel, da trdijo, da je ta zgornja meja, koliko koraka algoritma lahko traja, se dogaja, da se v veliki O n kvadrat v tem primeru zgornja meja. 

Kaj če bi namesto spremeniti Zgodba, da je ne gre mehurček vrste, ampak o tem zgornja meja. Lahko si misliš o algoritmu, da smo pogledal že katerih zgornja meja, največ merjenje časa ali operacij, bi lahko rekli, da se omejuje z n, linearna funkcija, ni kvadratna tista, ki je ukrivljena? Kaj je algoritem, ki vedno ne traja več kot kot n korakov oziroma 2N koraki, ali 3N koraki? Ja? 

OBČINSTVO: Iskanje največja številka v seznamu? 

SPEAKER: Popoln, iskanje največja številka v seznamu. Če sem dal seznam ljudje, na primer, vsaka, ki drži več, tisto, kar je največje število korakov naj bi me odpeljal, razumno pametna oseba, da bi našli največji osebo v tem seznamu? n, kajne? Ker v najslabšem primeru, če je Morda največja vrednost je? Dobro, tako na koncu. Torej v najslabšem primeru zgornjo mejo, bi lahko iti vso pot sem in se kot, oh, tukaj je številka osem, ali karkoli, da vrednost. Zdaj bi le bilo neumno če sem kar naprej dogaja, kajne? Išče vse več elementov če je zadnja od njih je tam? Torej zagotovo, n je zgornja meja. Ne rabim, da sprejmejo več korakov, kot je. 

Pa kaj, če namesto tega sem predlagal, da obstajajo algoritmi na tem svetu, ki imeti čas teče, ki je omejeno z velikim O log n log n? Kjer smo videli že prej? Ja? 

OBČINSTVO: Pri problemu telefonskega imenika? SPEAKER: Kot problem telefonskega imenika. Kaj je merilo, kako koliko časa oziroma koliko pretoĉenih vzel me je, da bi našli nekoga, kot Mike Smith v telefonskem imeniku? Smo trdili, da je log n in tudi če ne poznajo, ali pa je malo motna, kar logaritem ali eksponent je bilo, Zapomnite si, da log n Na splošno se nanaša na postopek, V tem primeru, delitve nekaj na pol spet in spet, in znova in znova, tako da postane bolj majhna, kot si to naredil. 

Torej, se prijavite z n sklicuje, seveda, na primer telefonski imenik, za binarno iskanje v teoriji, ko smo imeli virtualne vrata na krovu, ali ko je Sean iskanju nečesa. Če bi uporabili binarno iskanje, log n bi bila zgornja meja za koliko Čas je, da traja. Toda ti algoritmi, ki je potekal v log n domnevati kaj ključno podrobnost? To je seznam urejen, kajne? Vaš algoritem je narobe, če svoj vhod ni urejen, in še boste uporabljali nekaj takega kot binarno iskanje kajti lahko bi skočil desno čez element ne da bi dojel, da je res tam. 

Zdaj pa, kaj bi to lahko pomenilo, Big O enega? To ne pomeni, da je vaš algoritma traja en in samo en korak, to samo pomeni, da je potrebno konstantno število korakov. Mogoče je 1, morda je 10, morda je 1.000, ampak to je neodvisno od velikost problema. Ne glede na to, kako velik je n, stalen čas algoritem vedno v isto število korakov. Torej, kaj bi lahko algoritem smo se pogovarjali o tem, ali samo intuitivno, da pride k vam, da vedno izvaja v tako imenovanem konstantno času? Ja? 

OBČINSTVO: Dodajte dve številki. SPEAKER: Dodamo dve številki, 2 plus 2 je enako 4, storjeno. Tako da bi lahko bilo delo, kaj? Kaj pa bolj realni svet, ja? 

OBČINSTVO: Iskanje Prva stvar na seznamu. SPEAKER: Iskanje prva element na seznamu, seveda. Mi smo dejansko govorimo O nizi že, kako si dobil na Prvi element v matriki, ne glede na to, kako dolgo matrika je v C kodo? Pravkar ste uporabili kot nosilec nič zapis, bam, da si tam. In res nizi, kot prahi, Podpora nekaj splošno znana kot bralno, bralno spomin, saj si lahko dobesedno skok na enem mestu. To lahko naredimo še bolj preprosto moremo previti nič teden ko smo naredili nič. Koliko časa je trajalo, da za pravijo blok v Scratch za usmrtitev? Samo konstanten čas, kajne? Nekaj ​​reči, pravijo, kaj, ni važno kako velike Praske svet, je vedno bo trajalo enako količino časa da preprosto reči. 

Torej, to je konstanta čas, ampak kaj je side flip? Če bi bila zgornja meje, kaj, če želimo opisati spodnje meje naših algoritmov teče čas? Skoraj najboljši primer lahko, če hočete, čeprav bi ti pogoji veljajo za najboljše primeri, najhujših primerov povprečne primerov več na splošno, temveč se posvetimo samo na nižjih meje bolj na splošno. Kaj je algoritem, ki ima spodnja meja n korakih, ali 2N koraki, ali 3N koraki? Nekateri faktor n korakih, da je njena spodnja meja. Ja? 

OBČINSTVO: Bubble sort? 

SPEAKER: Bubble sort traja ti minimalno n korakov, zakaj? Zakaj je tako? Zakaj naj bi, da je začetek, da pridejo do vas intuitivno, čeprav to ne samo še? Ja? 

OBČINSTVO: [neslišno]. SPEAKER: Točno tako. V najboljšem možnem scenariju bubble sort, in veliko algoritmov, če ti roko osem ljudi ki so že urejene, to bi bilo neumno za vas, algoritem, iti naprej in nazaj več kot enkrat, kajne? Zato, ker takoj, ko vas sprehod po seznamu enkrat, morate zavedati, oh, sem ne zamenjave, je ta seznam razporejene, izhod. Ampak to se dogaja, da vam n ukrepe sprejeti. 

In obratno, kar je še način razmišljanja o tem? Bubble sort je omega, tako rekoč, n, ker če pogledaš na manj kot n elementov, kar je temeljno vprašanje tam? Saj ne vem, če je to urejeno, prav. Smo ljudje morda pogled na osmih ljudje, in bo kot, oh, to je urejeno, da me n korakov ni upošteval, ampak je to storila. Tvoje oči, čeprav vas nekako o imajo veliko vidno polje, si pogledal na osem elementov, si pogledal osem ljudi, to je dejansko osem korakov. In samo če grem skozi celoten seznam moram zavedati, da, razporejene. Če neham pol razmišljal, vse V redu, to je precej doslej razporejene, Kakšne so možnosti, da se ni razvrščena? Da algoritmi ne bo pravilna. Morda hitreje, vendar napačno. 

Torej, zdaj imamo način Opisovanje spodnje meje, in kaj je s konstantnim časom? Kaj je algoritem, ki ima nižje vezan na vozno času enega? 1 korak 2 stopnici, 10 korakov, vendar konstanten, neodvisno od n, velikost vhoda? Ja, v hrbtu. 

OBČINSTVO: printf? SPEAKER: Kaj je to? OBČINSTVO: printf? SPEAKER: printf. OK, seveda. Torej je potrebno določeno število korakov. In moram sedaj-- zdaj, govorimo o C kodo in ne Scratch, nekaj kot pravijo, z printf, bi morali začeti, da bi dobili previdni. Ker printf ne bo input, to je niz, in godala pa tehnično imajo dolžino. Torej, če hočemo sedaj poberem na vas, če vas ne moti, tehnično bi lahko trdili, da printf ne bo spremenljivo vhod dolžine, in zagotovo bo trajalo več Čas je, da natisnete niz tako dolgo, od tega dolg. 

Pa kaj, če upoštevamo samo sortiranje in iskanje primerov? Kaj pa Mike Smith v telefonu knjiga ali binarno iskanje bolj na splošno? V najboljšem primeru, kaj se lahko zgodi? Odprem telefonski imenik in bam, tam je število Mike Smith. Lahko ga pokličem takoj. 

Je en korak, morda dveh korakih, vendar je konstantno število korakov če imam srečo. In odkrito povedano, smo videli na Ponedeljek tvoj sošolec dobili precej srečen dvakrat zapored. In to je bilo res konstantna Čas v nižjem igrišča o algoritmu zadevno za iskanje Številka 50 zaostaja zaprta vrata. 

Zdaj, kot prahi, če boste odkrili, da tako velik O, zgornja meja, in omega, spodnja meja, sta eno in isto, da je enako formulo v oklepaje, lahko tudi vi pravijo, samo, da je fancy, da je nekaj v theta n ali theta neke druge vrednosti. To samo pomeni, ko velika O in omega so enaki. Kaj pa izbirnem vrste zdaj? Izkoristimo to novo besedišče. V izbirnem vrste, kar smo ostali počne znova in znova in znova? Sem šel naprej in nazaj skozi Seznam, ki je videti za koga? Najmanjše število. 

Torej, koliko korakov, kako številne primerjave Sem morali narediti, da bi ugotovili, kdo najmanjši element na seznamu je? n minus 1, kajne? Ker, če sem začela z enim sem dana in začnem mu primerjavo, potem on ali ona, on ali ona, on ali ona, sem lahko seznanite samo elemente skupaj n minus 1 krat. Torej, izbira sort podobno traja n minus 1 koraki prvič. 

Koliko korakov traja me najti drugo najmanjšo element? n minus 2, ker sem biti neumen če sem vedno gledaš istimi ljudmi še enkrat, če sem ga že izbrali ali njen in jih postaviti na svoje mesto. In tretji korak, n minus 3, potem je n minus 4. Videli smo ta vzorec prej, in dejansko Izbira nekako podobno je zgornja meja n kvadrat, če bomo do tega seštevanja. Kakšna je njegova spodnja meja, izbor sort? Minimalno, koliko časa je treba izbiro nekako sprejeti, kot smo ga opredelili v ponedeljek? Predlagala dve možnosti. Mogoče je n, kot prej. Mogoče je n kvadrat, saj Zdaj je, kot je zgornja meja. 

OBČINSTVO: n na kvadrat. SPEAKER: n na kvadrat. Zakaj? 

OBČINSTVO: Ker imate opredeliti [neslišno]. 

SPEAKER: Točno tako. Vsaj tako sem definirana izbora vrste je bilo precej naivno, nadaljuj, najti najmanjši element. Pojdi spet najti najmanjši element. Pojdi spet najti najmanjši element. Ni nekako Optimizacija tam, da Morda mi prekinitev po le n ali tako korakov. Torej res, izbor sort, omega n kvadrat. 

Kaj vstavitve vrste, kjer sem vzel , ki mi je bila dana, in potem sem ga plopped ali jo na pravem mestu? Potem sem nadaljeval na drugo osebo, mu plopped na pravem mestu. Potem naslednja oseba, plopped ga ali jo na pravem mestu. Obvestilo, da je to zelo linearna, tako rekoč. Sem premica, sem ne gre naprej in nazaj, Nikoli nisem ozrl nazaj res, pa kaj se dogaja, ko sem ga vstavite ali pa jo v začetku leta seznam, kot smo to storili v ponedeljek? Kaj se dogaja? Ja? OBČINSTVO: [neslišno]. SPEAKER: Ja, to je bil ulov, kajne? Morda se boste spomnili iz tvoji sošolci, če bili kar vsak premik z njihove noge, da je bila operacija. Torej, če so bili trije ljudje, tu in nova oseba pripadala pot tja, na dolgi fazi, kot je ta, seveda, je ali bi lahko bila pojdite do samega konca. Ampak, če razmišljate o Računalnik in vrsta spomina, ti ljudje gredo da imajo shuffle prek da bi naredili prostor za to osebo. In da n minus 1 shufflings, n minus 2 shufflings, n minus 3 shufflings je nekako dogaja za mano, ne pred mano kot prej, v nekem smislu. Zdaj, kot prahi, in kot ste morda opazili na spletu Če ste začeli drezati okoli okoli vrste, obstaja toliko različnih tisti tam, nekateri od njih boljši od drugih. Dejansko, bogosort je ena to je kar zabavno pogledati. Bogosort traja niz številke ali reči kart, jih naključno premeša, in preveri, če oni razporejene. In če ne, to počne znova. In če ne, to počne znova. Če ne, ga pa še enkrat. Neverjetno neumno. 

In res, če ste prebrali kot članek Wikipedia, njegov vzdevek je nekako neumno. To bo na koncu delovalo, upajmo, dovolj časa, vendar časa lahko traja kar nekaj časa. Torej, če bi lahko, kaj je hitrost stvari up od na primer Mary Beth je prej, ki jih ima nekaj več elementov, ampak dve procesorji. Dva človeka, če vas Ne bi se mi pridružil. Kako približno 1 tukaj, in dajmo tam-- nikogar tam? Nihče tam? OK. Vam s črno shirt, ja, pridi dol. V redu, kako ti je ime? 

OBČINSTVO: Peter. 

SPEAKER: Kaj je to? 

OBČINSTVO: Peter. SPEAKER: Peter, David, lepo, da sva se spoznala. Dobro, imamo Petra tukaj, če vas želijo priti na mizo tukaj. In kako ti je ime? 

OBČINSTVO: Elena. SPEAKER: Elena. OK, lepo, da sva se spoznala. Elena izpolnjujejo Petra. Peter, Elena. In potrebovali bomo Andrewa tukaj, kot tudi, prosim. In vaš izziv bo da se za razvrščanje kart. In če je ne poznajo, deck kartic naj bi v končni fazi razvrščeni malo nekaj podobnega to, če bomo storili klubih, nato pa lopatica, nato srca in diamanti, od asa kot eno, vse tja do kralja. 

Kartice bom dal se bo 52 v količini. Bomo podobno Čas vas, v samo nekaj trenutkov. Bomo vrgli Andrew na zaslonu tukaj tako, da vas gledam, kako to storiti. In da vse to je še toliko bolj vidna, To so kartice sem dobil na Amazon. Torej so že naključno razporejene in bomo čas. In bomo obdržati pravi tokrat, Tako bomo poskušali prisiliti ker drugače bo ta dobil dolgočasno hitro. Če bi lahko nadaljevali rešiti 52 elementi skupaj preko nekaterih sredstev, takoj. 

In spet, kot smo gledal to Fantje, kaj storiti, na koncu se dogaja, da dobimo jasno Rezultat, pomislite res kako oni vsak počne, kako bi to opisal. Ker enkrat, to so Vsi postopki, algoritmi da se nam zdi samoumevno, kot človeku. Vendar ste verjetno že dolgo intuicija, dolgo pred vami še razmišljala o čemer računalništva vam class Morda so imeli z intuicijo za reševanje problemov, kot je ta. Toda, ko boste prepoznali vzorci in začnejo za formaliziranje ukrepe, s katerimi ste reševanje teh problemov, boste ugotovili, da vam lahko reši veliko bolj zanimivo in veliko bolj kompleksna Težave hitro. Torej je nekdo iz občinstva, kar je vsaj en element algoritma da uporabljate tu? 

OBČINSTVO: [neslišno] SPEAKER: Kaj je to? OBČINSTVO: Z obleko. SPEAKER: Z obleko. Torej, najprej so razvrščene vse diamantov skupaj zdi se, vse srca skupaj kot se zdi, in tako naprej, ne glede Za številkami kartic. In zdaj se pojavijo, na primer, da se jih sortiranju po številu. Zelo dobro. 

V redu, kaj se dogaja, da biti zadnji korak, potem tukaj? Ko imamo štiri razvrstite obleke, kaj storiti moramo storiti na štiri kupe za dosego enega razporejene krova, preprosto? Zato jih moramo ponovno združiti. 

Torej je zanimiva ideja, ki še enkrat, si trditi, je zelo intuitiven celo če bi si nikoli ne bi udaril da vrste etiket. Ta temeljni pojem delitve Problem ni v pol tem času, vendar vsaj na štiri dele. Reševanje precej v bistvu enaki problemi ločeno drug od drugega, in nato združitev rezultatov. In odlično, opravljeno. V redu, velik krog aplavz, če bi lahko. 

[APLAVZ] 

SPEAKER: Nimam pojma, kaj bom storiti z njimi, ampak tukaj imaš. Najlepša hvala. Pa poglejmo, dve minuti in osem sekund, Če želite izzvati svoje prijatelje. Kaj pa se dogaja, da lahko traja od tega da bomo lahko še povečala splošno? No, mislim nazaj ta niz številk, in mislim nazaj, zdaj z nekaterimi psevdokoda smo zapisali v preteklosti, in to je bil psevdokoda za reševanju problema iz telefonskega imenika. Pri čemer je v psevdokoda I naštel bolj metodičen način opisati, kako sem zelo intuitiven človeški algoritem deljenja telefon knjige na pol, ponovitev, ponavljam, ponavljam, dokler ne najdem nekoga, kot je Mike Smith, če je res, v telefonskem imeniku. 

Ampak sem nekako uporabiti, kaj bom poklical Zelo iterativni pristop tukaj, zlasti obvestila vrstica 8 in 11 črta. Tisti, ki so dokaz, ponavljajoč pristop, pristop zanka, ker to je točno Vedenje, ki ga povzroči. Te vrstice oba pravim, pojdi na tretja vrstica, in lahko nekako mislim, da je v vašem mislih kot zanka. To vam je povedal, da gredo nazaj v korak tri in ponavljam, znova in znova, in znova. 

Toda kaj, če bomo vzvod ključno idejo Tukaj smo, da ni zadnji čas, in poenostaviti linijo 8 in linija 11 in njihove sosede kot samo to, v rumeni barvi. To ni bistveno skrajšanje psevdokoda zelo veliko, vendar je bistveno spreminjajo naravo mojega algoritma. Kaj bom zdaj rekel, V koraku 7, v koraku 10, je iskanje Mika na točno enak način, ampak samo na levi strani pol ali desno polovico. 

Torej, z drugimi besedami, če Izhajam iz enega koraka, pick up telefonski imenik, odprta do sredine iz telefonskega imenika, poglej imen, če Smith je med Ime mi je, pokličite Mike, ostalo če Smith je že prej v knjigi, Sedmi korak iskanje Mike v levi polovici knjige. Ampak to nekako občutek to me zapusti visi, kajne? V rumeni barvi, je pouk, ampak kako narediti I iskanje Mike v levo polovica telefonskega imenika? Kje imam algoritem, s katerim sem Lahko poiščete nekoga, kot Mike Smith? No, to je nas strmel v obraz. Lahko dobesedno uporabite točno isto Program dejansko dogaja na vrh spet in ponovno tek enake vrstic kode. 

Torej, čeprav bi to moralo počutijo kot nekaj cikličnega opredelitve kjer si odgovorite, da je nekdo Vprašanje, ki ga je kar nekako prosi spet isto vprašanje, kot so, zakaj, zakaj, zakaj? Realnost je, ker smo težko kodirane Nekaj ​​posebnih linij, korak 4, , ki je, če in korak 12, ki je dejansko še ena veja, ker imamo tiste stopgap ukrepe, Ta algoritem se prekine, če bomo Ugotovijo, Mike, ali če tega ne storimo. Toda v koraku 7 in 10. Zdaj imamo kaj bomo klic rekurzivni algoritem. In rekurzija je res močna ideja da je malo um upogibanje na prvi, da bomo lahko zdaj uporabljajo, kakor sledi. 

Zlivanjem bo zadnja vrsta, ki gledamo, vsaj v razredu formalno. In to je bistveno drugačna od teh zadnjih treh, vsekakor pa zadnja štiri, če štejemo bogosort. Tukaj je psevdokoda za urejanje z zlivanjem. Ko se na vhodu n elementov, tako glede matrika velikosti n, če je n manj kot 2, vrniti. Torej, zakaj moram, da sanity najprej preveril? Kaj pa posledice, če bi ti roko polje, katerega dolžina je n manj kot 2? To je že urejeno, je očitno, kajne? Ker ima seznam bodisi en element, ki je trivially razporejene, saj je Edina stvar, ki obstaja. Ali je velikosti nič, ki pomeni ni nič za razvrščanje, tako da je po naravi je urejeno. Obstaja samo ni nič narobe. Torej, to je naša tako imenovana osnovna. 

To je podobno kot v duhu s tem, kar smo naredili z Mikom. Če Mike je v telefonskem imeniku, ga pokličite. Če ga ni tam, obupajte. To je tako imenovana osnovna, se prepričajte, Ta algoritem ob koncu dneva se bo ustavila v določenih okoliščinah. 

Ampak tukaj je preskok vere zdaj, drugega, razvrstiti levo polovico elementov, nato razvrstiti pravico polovica elementov, in nato združiti razvrščenih polovic. In tu je, če se mu zdi, kot smo copping ven. Sem te prosil, da razvrstite n elementov, in sem rekel, OK, ga s sortiranjem levo in sortiranje pravico. Ampak jaz govorim eno druga stvar, in to je ključna tema se zdi v intuicijo tako daleč, tam je tretji korak združevanja. Ki je, čeprav ji zdi tako neumno v duhu, kot samo združiti stvari skupaj, se zdi ključni korak k sestavljanje dveh problemov, ki so bili razdeljeni na koncu na pol. 

Torej zlivanjem, naredimo to, če boste humor me, z eno več demonstracij, samo zato, da imamo nekaj številke delati. Lahko zamenjam osem stres Žoge za osem ljudi? V redu, kaj pa vi trije, ti štirje v tem poglavju, pet, šest, in dajva ne 7, 8, pridi gor. OK, ja OK. Minus 8, tam gremo, plus 1. Odlično. Dobro pridi gor, dajva hitro vam številke. Drugič, število tri, številka štiri, Številka pet, šest, sedem, osem. Sem osem pravilno tokrat. 

OK, tako da gredo naprej, če bi lahko, in pa razporedijo v prvotni vrstni red da smo imeli včeraj, ki je pogledal kot je ta, če ne bi motilo. In dajmo pred mizo. Vse v redu, tako da z zlivanjem. To je, če se bo da bi dobili vrsto zanimivih, ker se zdi, da sem kar toliko manj informacij danes. 

Torej zlivanjem najprej na vhodu n elementov, in očitno ne manj kot dva, je osem let, tako da sem imel nekaj več dela. Torej sedaj psihično smo kot razred so zdaj v drugega podružnice, kar pomeni tri korake. Najprej moram rešiti leva polovica elementov. Torej, kako naj grem o tem? No, bom nekako duševno razdeli seznam tukaj, vam ne bo treba fizično premakniti, in sem dogaja, da se osredotoči le na leva polovica elementov tukaj. Torej, kako naj grem o sortiranje seznam zdaj velikosti štirih? Kaj je moj algoritem? Najprej sem preveriti, je n manj kot dve, no, tako da sem spet nadaljuje na drug blok. Razvrsti levo polovico elementov. 

Torej, zdaj spet, duševno, in to je, če boste morali teči veliko duševno zgodovina, če hočete. Zdaj sem sortiranje levo polovica levi polovici. Dobro, zdaj sem poklical svojega isti spajanja sortiranje algoritem, je n manj kot dva? Ne, to je za dva, tako da sem moral rešiti levo polovico in desno polovico. Torej, gremo, levi polovici razvrstiti. Zakaj ne samo vzemite en korak naprej. Kako ti je ime? 

OBČINSTVO: Darren. 

SPEAKER: Dan. Dan je stopil naprej. 

OBČINSTVO: Darren. SPEAKER: Darren, opravljeno. Ste rekli Darrena ali Dan? 

OBČINSTVO: Darren. 

SPEAKER: Darren. OK, je Darren stopil naprej in se je sedaj urejeno. In to je skoraj Prazen trditev, kajne? Res ne zdi, da bi dosegli karkoli, vendar pa nadaljujmo. Zdaj pa me razvrstiti pravico polovica elementov. Kako ti je ime? 

OBČINSTVO: Luke. 

SPEAKER: Luke. Daj no, stopi naprej. Storjeno, sem razporejene Luke. Leva polovica je sedaj razporejene in desna polovica je sedaj urejen, ampak spet, tam je ključni korak tukaj. Kaj sem zraven morate storiti? Združiti razvrščenih polovic. Zdaj bomo morali vsi naprej in nazaj na ta način, ker sem nekako potrebujem nekaj prask prostora. To je skoraj tako kot ti Fantje so na mizi, in rabim malo prostora da jih premikate naprej. Torej bom, da se združijo vidva z iskanjem na levi polovici in desni polovici. In ki je očitno na prvem mestu, levo polovico ali desno polovico? Torej desno polovico, tako da gremo preko Luke tukaj, da prvotni položaj Darren je. In zdaj, da združijo svoje levo polovico leta, Darren se dogaja, da se premaknete tam. 

Torej, občutek skoraj bubble sort učinek, ampak moja temeljna algoritem, Zelo tokrat drugače. Ampak zdaj je, če se stvari malo siten, ker vas morajo duševno previjanje kje sem pustil off. Pravkar sem združila razvrstite polovic, kar pomeni, da sem kje v mojem algoritmu? Imam razvrstiti desno polovico, kajne? 

Če ste nazaj, dobesedno na video, boste vidite, da imamo za to točka Luke in Darrena s sortiranjem levo polovica levi polovici. Potem smo se združili s tistimi, Urejeni polovičke, ki pomeni naslednji korak je neke desno polovico levi polovici. Vse v redu, tako da je To naredite hitreje. V redu, šest, grem zahtevku ti so zdaj razporejene, pridi naprej. Kako ti je ime? 

OBČINSTVO: Adriano. 

SPEAKER: Adriano. Adriano je sedaj urejeno. In kako ti je ime? 

OBČINSTVO: Alex. 

SPEAKER: Alex je sedaj urejeno. Levo pol, desno polovico, kar je zadnji korak? Merge. Precej nepomembno, zato sem dogaja, da se združijo v šestih, stopiti korak nazaj, osem, korak nazaj. In zdaj opazil je to uporabno takeaway, kaj Zdaj je res o levi polovici seznam, ne glede na to, kako smo začeli? To je urejeno. 

Zdaj to ni urejeno v veliki načrt stvari, vendar je razvrščen neodvisno na drugi polovici. Kaj zdaj korak pa sem, če sem na vodi previjanje, kako se je začela zgodba? Zdaj moram rešiti desno polovico. Torej, zdaj smo pot nazaj začetek zgodbe, in naredimo to hitreje. Torej bom, da razvrstite desno polovico celotnega seznama. Kaj je naslednji korak? Razvrstimo levi polovici desni polovici. Razvrstite levo polovico levi polovici desni polovici. In kako ti je ime? 

OBČINSTVO: Omar. 

SPEAKER: Omar, korak naprej, narediti. Leva polovica je razvrščen. In kako ti je ime? 

OBČINSTVO: Chris. 

SPEAKER: Chris, naredimo korak naprej, sedaj ste razvrščeni. Kaj je ključni korak zdaj? Merge. Torej ga bo, da se združijo v mestu tukaj, če bi lahko naredili korak nazaj, in tri se bo naredili korak nazaj, združiti. Torej leva polovica desna polovica, je sedaj urejeno. Odkrito povedano, ta algoritem počuti kot mi izgubljamo tako več časa kot prej, če pa je to storila v realnem času, se bomo glej, kaj takeaways bo. Zdaj sem tu, kajne polovica desni polovici, Naj gredo naprej in razvrstiti levo polovico. Korak naprej, kako ti je ime? OBČINSTVO: Ramsey. SPEAKER: Ramsey je sedaj urejeno. Kako ti je ime? 

OBČINSTVO: Marina. 

SPEAKER: Marina je zdaj razvrščen kot No, če si vzamete en korak naprej. Ključni korak je tu zdaj združiti, sem bom odtrgal od mojih dveh seznamov, levo in desno. Pet se dogaja, da pridejo prvi, in sedem bo prišel naslednji. In spet, da je to namerno. Dejstvo, da so si ob koraka naprej in nazaj je mišljeno, da predstavljajo, da ne moremo storiti ta algoritem v mestu kot enostavno kot nekakšen mehurček in izbora vrste, in vstavljanje sort, kjer smo pravkar hranijo zamenjavo ljudi. Sem dobesedno potrebujejo neke za praske papirja, v katerem da se ti ljudje medtem ko jaz združitev, in potem sem jih dal nazaj na svoje mesto. In to je ključnega pomena, ker sem s pomočjo nov vir, prostor, ne samo enkrat. 

OK, to je neverjetno. Levo polovico razporejene, desna polovica je urejene tako, da je sedaj ključni korak združitev. Kako bom združiti to? Torej, če boste sledili moj levo roko in desno roko, Bom izpostaviti mojo levo roko na levi polovici, moja desna roka na desni polovici, in zdaj moram odloči, korak za korakom, na koga naj se stapljajo v. Ki je očitno na prvem mestu? Številka ena. Torej, pridi sem, Tukaj je naš scratch pad. Torej, zdaj številka ena, in obvestilo kaj bom naredil z mojo desno roko, Bom premakniti mojo desno eni strani stopite na točko številka tri, in zdaj moram narediti Enako odločitev. In dejansko stojijo pravico v front of Luke tukaj, če bi lahko, zato, ker je to naša scratch pad. Torej, kdo gre zraven? Imamo Luke z dvojko ali Chris s številko tri. Očitno Luke, število dva, tako da ste prišli sem. 

Ampak moja leva roka sedaj se dogaja, da se poveča do točke na Darrena, in tukaj je ključ odnese s združujejo, bom vztrajati početje to, seveda, če ste prijazni od slediti logiki. Ampak moje roke niso nikoli bo šel nazaj, kar pomeni, da sem samo kdaj se gibljejo na levo z mojim procesu priključevanja, in to se dogaja, da je ključ do naša analiza, v trenutku. 

Torej, zdaj pa je zapravil to zelo hitro. Torej tri pride zraven, nato štiri prihaja naslednji, in zdaj pet pride zraven, potem pa šest, in sedem, in nato končno osem. Počutim se kot najpočasnejšim algoritmom še ni, vendar ne, če smo dejansko teči hkrati vrste hitrosti ure, tako da govorijo, z enako tiktaka ura kot prej. Zakaj? No, vzemimo pogled na končni rezultat. 

Pojdimo nazaj sem, pustite me dvigni demonstracijo vizualno o tem, kaj smo pravkar naredili. Povečave tukaj, na tem stran tukaj, povedal Firefox da želimo, da se v vrsto v tem polju, dajva pravijo mehurček vrste, s katerimi zdaj smo dobro seznanjeni, izbira sort, kar je še en precej enostavno ena, in zdaj današnja merge sort, ki bo naš climactic konec. Razlog, da se je toliko več tukaj z ljudmi in me je verbalno, seveda, sem pojasnil na vsakem koraku. Ampak, če si preprosto izvršiti to, kar je precej kot smo bubble sort in izbor nekako ne le vizualno, watch kako veliko bolj učinkovito To vzvoda delitev in osvajanje če se lahko uporablja za vrsto podatkov, ki je Niti velikost osem, ampak tudi veliko, veliko večji. Dajem ti zlivanjem, z ramo ob stran s temi drugimi algoritmi. To se dogaja, da bi dobili boleče hitro in konec ni posebej podnebnih, so šele na koncu razporejene. Ampak ključ vzeti, je, da poglej koliko hitreje zlivanjem je, če misliš, da sem nekako zajebavam s tabo. Če to storimo en končni čas, Pojdimo osvežite to, vrnimo in izberite bubble vrste, in samo za brcne, dajmo izbrati vstavljanje sort, samo za dober ukrep. In tokrat spet, dajva izberite zlivanjem in dajva dejansko vodijo te bok. 

In to v resnici ni, krompir. Kar sem dejansko naredil, je imam razdeljen svoj prispevek na pol, še enkrat, in znova in znova. In tam je samo toliko časa si lahko razdeliti vaš vložek v polovici, levo in desno. Kakšna je formula, ki smo ostali vidimo , ki opisuje delitev na pol znova in znova in znova in znova? 

OBČINSTVO: Log n. 

SPEAKER: Log n. Ampak potem je tu še en drug ključni korak, Ta algoritem je ni log n korakih. Če bi bilo samo log n korakih, mi bi bili v istem problemu kot prej, kadar ne moremo prepričan je vse urejeno. Moraš minimalno poglej n elementov biti prepričani, n elementi so razporejene, drugače je preskok vere. 

Torej, to je minimalno log n korakih, vendar kaj pa ta ključni korak priključevanja kjer sem združila moja leva in desna polovica pol in se sprehodil po odru? Koliko korakov je, da združim? To je n, ampak nisem ravno združiti končni čas. Na vsakem od teh ugnezdene klicev, na vsaki teh ugnezdene spajanju, sem še vedno razporejene. Sem združila ta dva fanta, potem ti dve fantje, nato pa ta dva in tako naprej. 

Torej sem se združujejo spet in spet. Kolikokrat? Torej, vsakič, ko sem razdeljen seznam za polovico, sem spajanje. Razdelite seznam na pol, naredite spajanje. Torej, če je tako, da se seznam mogoče storiti dnevnik n-krat, in združitev na koncu prevzame n koraki, kaj bi bilo zdaj zgornja vezan na delovanje Čas našega algoritma? n log n. 

In res, da je kaj Tu smo dosegli. Tako občutek, da ste videli vizualno ko te tri stvari teči z ramo ob rami je n kvadrat pred n kvadrat pred n log n. Ki načeloma bomo videli, ne samo danes, ampak v prihodnje je še veliko, veliko hitreje. Aplavz za te fante, Jih bom nagradil z stresnih žogic. Pojdimo preložitvi danes tukaj, in vas bomo videli v ponedeljek.