[Muusika mängib] PROFESSOR: Okei. See on CS50 ja see on nädala lõpuks kolm. Nii et me oleme täna siin, mitte Sanders Teater, selle asemel Weidner raamatukogu. Mille sees on stuudio tuntakse Hauser Studio, või ütleme Studio H, või esitab me say-- Kui teile meeldis see nali, see on tegelikult pärit klassivend, Mark, online, kes soovitas nii palju kaudu Twitter. Nüüd sellest, mis on lahe umbes on siin stuudios on, et ma olen ümbritsetud need rohelised seinad, roheline ekraan või chromakey, niiöelda, mis tähendab, et CS50 on tootmise meeskond, teadmata mind just nüüd, võiks panna mulle kõige kõikjal maailmas, paremaks või halvemaks. Nüüd, mis ees ootab, probleem seatud kaks on teie kätes sel nädalal, kuid probleem seatud kolm tuleval nädalal siis tuleb väljakutse koos nn mängu 15 vana poole kasuks, et sa võiks meenutada, saavad nagu laps, et on terve hunnik Numbrite mida saab libistada üles, alla, vasakule ja paremale, ja seal on üks lõhe jooksul puzzle, millesse tõlgitakse võib tegelikult lükake need puzzle tükid. Lõppkokkuvõttes saate seda puzzle mõnel pool juhuslikus järjekorras, ja eesmärgiks on sortida, ülevalt alla, vasakult paremale, ühest kõik teed üles läbi 15. Kahjuks rakendamist sul on käepärast läheb tarkvara põhineb mitte füüsiliselt. Sa oled tegelikult läheb on kirjutada kood, mis üliõpilane või saab kasutaja mängu mängida 15. Ja tegelikult häkker väljaanne mängu 15 Teil on väljakutse rakendada, mitte ainult mängides seda vana kooli mängu, vaid lahendamine sellest, rakendades jumal režiimis niiöelda, et tegelikult lahendab puzzle inimese, pakkudes neile vihje, pärast vihje peale vihje. Nii rohkem, et järgmisel nädalal. Aga see, mis ees ootab. Praegu meenutavad, et varem sel nädalal meil oli see pinge, kui soovite, kusjuures parim, mida me teeme sorteerimine tark oli ülemine piir suur o n ruudus. Teisisõnu, mull sorteerida, valikut sorteerida, sisestamise sorteerida, Kõigi nende kui erinevad nende rakendamisel, detsentraliseeritud arvesse n ruudus töötab aega väga halvimat. Ja me üldiselt eeldada, et väga halvimal juhul sorteerimine on selline, et oma sisendid on täiesti tagurpidi. Ja tõepoolest, see võttis üsna vähe samme rakendada kõigis neis algoritme. Nüüd päris lõpus klassi Meenuta, me võrreldes mull omamoodi valikukriteeriumide omamoodi vastu üks teine et me kutsusime ühendamine omamoodi ajal, ja ma teen ettepaneku, et see võtab ära õppetund nädalas null, jaga ja valitse. Ja kuidagi saavutada mingi logaritmiline sõiduaega lõpuks selle asemel, et midagi see on puhtalt ruutu. Ja see ei ole päris logaritmiline see on natuke rohkem. Aga kui te mäletate klassi, see oli palju, palju kiiremini. Võtame pilk, kus pooleli jäime. Bubble omamoodi versus valikut Sorteeri versus ühendamine omamoodi. Nüüd on nad kõik töötavad, on Teoreetiliselt samaaegselt. Protsessor töötab sama kiirusega. Aga sa võid tunda, kuidas igav see on väga kiiresti hakkab muutuma, ja lihtsalt, kui kiiresti, kui me süstida natuke nädalal null algoritmid, saame asju kiirendada. Nii mark omamoodi näeb välja hämmastav. Kuidas me saame võimendada seda, et sorteeri numbrid kiiremini. Noh olgem mõelda tagasi koostisosale et me oli juba nädal null, mis otsides keegi telefoniraamatust, ja meelde tuletama, et pseudokoodi et tegime ettepaneku, mille kaudu saame teada keegi nagu Mike Smith, Vaatasin natuke midagi sellist. Nüüd vaatleme eriti real 7 ja 8, ning 10 ja 11, mis tekitavad selle kontuuri, millega me hoida naasmine line 3 uuesti ja uuesti, ja uuesti. Selgub aga, et meil on võimalik vaadata See algoritm, siin pseudokoodi, natuke rohkem terviklikult. Tegelikult, mida ma otsin kell siin ekraanil, on algoritm otsimiseks Mike Smith hulgast mõned lehekülgede hulk. Ja tõepoolest, me võiks seda lihtsustada algoritmi need read 7 ja 8, 10 ja 11 lihtsalt öelda seda, mis ma olen siin esitatud kollane. Teisisõnu, kui Mike Smith on varem broneerida, Me ei vaja täpsustada sammu sammult nüüd, kuidas edasi minna teda leida. Me ei pea täpsustada minna tagasi line 3, Miks me ei lihtsalt selle asemel, ütleme üldisemalt otsida Mike on Vasakul pool raamatut. Vastupidisel juhul, kui Mike on tegelikult hiljem raamatus, miks me lihtsalt ei tsiteerida lõppeb otsing Mike õiges poole raamatu. Teisisõnu, miks me lihtsalt ei omamoodi punt endale öelda, otsida Mike selles alagrupis raamat ja jätke meie olemasolevate algoritmi ütle meile kuidas otsida Mike et vasakul pool raamatut. Teisisõnu, meie algoritm töötab, kas see on telefoniraamat selle paksus, selle paksus, või mis tahes paksusega üldse. Nii saame rekursiivselt määratleda selle algoritmi. Teisisõnu, Euroopa ekraan siin on algoritm otsimiseks Mike Smith hulgast lehekülge telefoniraamat. Nii line 7 ja 10, olgem lihtsalt öelda, just nii. Ja ma kasutan seda mõistet hetkeks tagasi, ja tõepoolest, recursion on sõnakõlks nüüd, ja see on selle protsessi teha midagi tsükliline kuidagi kasutades kood, mis sul on juba, ja nimetades seda uuesti, ja uuesti ja uuesti. Nüüd saab olema oluline et me kuidagi alt välja, ja ei tee seda lõputult kaua. Muidu me ei kavatse on tõesti lõputu silmuse. Aga vaatame, kas me saame seda laenata idee on recursion, midagi jälle ja ikka ja jälle, et lahendada sorteerimise probleem kaudu ühendada sorteerida kõiki tõhusamalt. Nii et ma annan sulle liita omamoodi. Võtame pilk. Nii et siin on pseudokoodi koos mida me võiksime rakendada sorteerimise, kasutades seda algoritmi nimetatakse ühendamine omamoodi. Ja see on lihtsalt see. On sisend n elementi, Teisisõnu, kui sa oled antud n elementi ja numbrite tähed või mis iganes sisend on, kui sa oled andnud n elementi, kui n on alla 2, lihtsalt tagasi. Õigus? Sest kui n on alla 2, et tähendab, et minu elementide nimekirja on kumbki suurusega 0 või 1 ja nii nende triviaalne juhtudel, nimekiri on juba järjestatud. Kui ei ole nimekirjas, siis on järjestatud. Ja kui seal on nimekiri pikkus 1, siis on ilmselt järjestatud. Nii algoritm vajab ainult tõesti midagi huvitavat, kui meil on kaks või enam elemendid meile antud. Nii saab vaadata magic siis. Else sorteerida vasakul poolel elemendid, siis sorteerida õige pool elemente, Seejärel ühendada järjestatud pooleks. Ja mis on omamoodi meeles painutamine siin on see, et ma tõesti ei tundub, et on teile rääkinud midagi lihtsalt veel, eks? Kõik, mida ma olen öelnud on, antud nimekiri n elementi, sorteerida vasakul pool, siis paremal pool, siis ühendada järjestatud pooleks, aga kus on tegelik saladus kaste? Kus on algoritm? Noh selgub, et need kaks rida Esimene, omamoodi vasakule poole elemente, ja omamoodi õigus pooled elemendid, on rekursiivne kõned, kui nii võib öelda. Lõppude lõpuks on see ajahetkel, ma pean algoritmi, mille abil saaks sorteeri terve hulk elemente? Jah. See on siinsamas. See on siinsamas ekraanil, ja nii et ma ei kasuta, et samad sammud sorteeri vasakul pool, kui saan õige poole. Ja tõepoolest, uuesti ja uuesti. Nii ühel või teisel moel, ja me varsti vaata seda, maagia ühendamine omamoodi on põimitud väga lõplik line, ühendades sorteeritud pooleks. Ja see tundub üsna intuitiivne. Võtad kaks poolt, ja sa, kuidagi, liita need kokku, ja me näeme seda konkreetselt ühe hetkega. Kuid see on täielik algoritm. Vaatame, miks. Noh oletame, et me antud needsamad Kaheksa tegurid, ekraanil üks läbi kaheksa, kuid nad näiliselt juhuslikus järjekorras. Ja eesmärk käepärast on sorteeri need elemendid. Noh, kuidas ma saan minna tee seda kasutades jällegi liita omamoodi, vastavalt sellele pseudokoodi? Ja jälle, sünnipärane seda meelt, et üks hetk. Esimesel juhul on päris triviaalne, kui see on väiksem kui 2, lihtsalt tagasi, ei ole tööd teha. Nii et tõesti seal on vaid kolm samme tõesti meeles pidada. Taas ja jälle, ma olen läheb tahtnud sorteeri vasakul pool, sorteeri paremal pool, ja siis, kui nende kaheks pooleks on järjestatud, Ma tahan, et liita need kokku üheks sorteeritud nimekirja. Nii et hoidke seda silmas pidades. Nii et siin on originaal nimekirja. Olgem käsitleda seda kui massiiv, kui hakkasime nädalal kaks, mis on külgnevas ploki mälu. Sel juhul sisaldavad kaheksa numbrid, seljad tagasi. Ja olgem nüüd taotleda ühendamine omamoodi. Nii et ma esimest soovite sortida Vasakul pool sellest nimekirjast, ja olgem seetõttu keskenduda 4, 8, 6 ja 2. Nüüd, kui ma minna sorteerimine nimekirja size 4? Noh ma pean nüüd kaaluma sorteerimine vasakul vasakul poolel. Jällegi, olgem kerida hetkeks. Kui pseudokoodi on see, ja ma olen andnud kaheksa elemente, 8 on ilmselgelt suurem kui või võrdne 2. Nii esimese puhul ei kehti. Nii et sorteerida kaheksa elemente, ma esimest korda sorteeri vasakul pool elemente, siis ma sorteerida õige poole, siis ma ühineda Kahe sorditud poolitatud Kõik size 4. OKEI. Aga kui sa oled mulle öelnud, sorteerida vasakul poolel, mis on nüüd of size 4, kuidas ma sorteerida vasakule poole? Noh, kui mul on input neljast elemendist, Ma sorteeritakse vasakul kaks, siis kaks viimast, ja siis ma ühendada neid koos. Nii jälle, see muutub veidi on meeles painutamine mängu siin, sest sina, selline, pea mäletan, kuhu on lugu, kuid lõpus päeval, antud mis tahes mitmeid elemente, kõigepealt tahan sorteerida vasakul pool, siis paremal pool, siis liita need kokku. Alustame teha just nii. Siin on sisend kaheksa elemente. Nüüd me vaatame vasakul pool siin. Kuidas sorteerida neli elementi? Noh ma sorteeritakse vasakule poole. Nüüd, kui ma sorteerida vasakule poole? Noh ma olen saanud kaks elementi. Nii saab sortida need kaks elementi. 2 on suurem või võrdub 2, muidugi. Nii et esimese puhul ei kehti. Nii et ma nüüd sorteerida vasakul pooled nendest kahest elemendist. Vasakul pool, muidugi, on vaid 4. Niisiis, kuidas ma sortida nimekirja üks element? Noh nüüd, et erilist aluspõhimõtted up top, nii et rääkida, kehtib. 1 on alla 2, ja mu nimekiri on tõepoolest suurus 1. Nii et ma lihtsalt tagasi. Ma ei saa midagi teha. Ja tõepoolest, vaadata, mida ma olen tehtud, 4 on juba järjestatud. Nagu ma olen juba osaliselt edukas siin. Nüüd tundub tobe punktile, kuid see on tõsi. 4 on loetelu size 1. See on juba järjestatud. See on vasakul pool. Nüüd ma sorteerida õige pool. Minu panus on üks element, 8 Sarnaselt juba järjestatud. Stupid ka, aga jällegi, antud põhimõte läheb võimaldab meil nüüd ehitada Selle peale edukalt. 4 järjestatud, 8 järjestatud nüüd mis see oli viimane samm? Nii kolmas ja viimane etapp, mis tahes aega sa sorteerimine nimekirja, meenutada, eesmärk oli ühendada kaheks pooleks, vasakule ja paremale. Nii saab teha just nii. Minu vasakul pool on muidugi 4. Minu paremal pool on 8. Nii teeme seda. Esiteks ma lähen eraldada täiendavat mälu et ma esindan, lihtsalt teisejärguline massiiv, see on piisavalt suur, et mahtuda seda. Aga te võite ette kujutada laiendada ristkülik kogu pikkuses, Kui meil on vaja rohkem hiljem. Kuidas võtta 4 ja 8 ning ühendada Nende kahe nimekirjad suurus 1 koos? Ka siin üsna lihtne. 4 saabub varem, siis tuleb 8. Sest kui ma tahan sorteerida vasakul pool, siis paremal pool, ja siis liita need kaks poolt koos, sorteeritud järjekorras 4 saabub varem, siis tuleb 8. Nii me tundub, et edu, isegi kuigi ma ei ole teinud ühtegi tegelikku tööd. Kuid pidage meeles, kus me oleme selles loos. Me algselt võttis kaheksa elemente. Me järjestatud vasakult poole, mis on 4. Siis me järjestatud vasakul pool Vasaku poole, mis oli 2. Ja siin me läheme. Me teha, et samm. Nii et kui me oleme sorteeritud vasak pool 2, nüüd on sorteerida õige pool 2. Nii et õige pool 2 on Nende kahe väärtuse siin, 6 ja 2. Nii saab nüüd astuma sisend suurus 2 ja sortida vasakul pool, ja siis paremal pool, ja siis liita need kokku. Noh, kuidas ma sortida nimekirja suurus 1, mis sisaldab ainult number 6? Ma olen juba teinud. See nimekiri suurus 1 sorteeritakse. Kuidas sorteerida teise nimekirja size 1, niinimetatud paremal poolel. Aga see, liiga, on juba järjestatud. Number 2 on üksi. Nüüd mul on kaks poolt, vasakpoolne ja õige, ma pean liita need kokku. Annan endale mõned ekstra ruumi. Ja panna 2 sinna, siis 6 seal, seega sorteerimine selles nimekirjas, vasakule ja paremale, ja ühinevad selle kokku lõpuks. Nii et ma olen veidi paremas seisus. Ma ei teinud, sest selgesti 4, 8, 2, 6 ei ole lõplik tellimine mida ma tahan. Aga mul on nüüd kaks nimekirjad suurus 2, et on nii vastavalt sorteeritud. Nüüd, kui teil kerida oma vaimusilmas silma, kust see jäta meid? Hakkasin kaheksa elemente, siis ma whittled selle alla vasakule poole 4 Seejärel vasakul poolel 2 ja siis paremal pool 2, I lõppenud, seega sorteerimine vasakul pool 2 ja paremal pool 2, Mis siis kolmas ja viimane etapp siin? Mul on ühendada kokku kaks nimekirjad suurus 2. Nii lähme edasi. Ja ekraani siin anna mulle lisamälu kuigi tehniliselt, märkate, et ma olen on terve hunnik tühja ruumi up top seal. Kui ma tahan olla eriti tõhusa ruumi tark, Ma võiks lihtsalt hakata liikuma elemendid edasi-tagasi, üleval ja all. Aga just visuaalne selgus, Ma panen ta allapoole, hoida asjad kena ja puhas. Nii et ma sain kaks nimekirjad suurus 2. Esimene nimekiri on 4 ja 8. Teine nimekiri on 2 ja 6. Olgem ühendada need koos sorteeritud järjekorras. 2, muidugi, on esimene, siis 4, siis 6, siis 8. Ja nüüd me tundume mõnes huvitavas. Nüüd olen järjestatud poole nimekirja ja juhuslikult, see on kõik paarisarvud, kuid et on tõesti lihtsalt kokkusattumus. Ja mul on nüüd järjestatud vasakult poole, nii et see 2, 4, 6 ja 8. Midagi on korrast ära. See tunne edusamme. Nüüd tundub, nagu ma olen rääkinud igavesti nüüd, mis siis jääb üle oodata, kui see algoritm on tõesti tõhusam. Aga me läheme läbi see super metoodiliselt. Arvuti muidugi teeksin seda niimoodi. Nii et kui me oleme? Alustasime kaheksa elemente. Ma järjestatud vasakul pool 4. I tunduvad olevat teinud sellega. Nüüd on järgmiseks sammuks sorteeri paremal pool 4. Ja selles osas saame minna kaudu veidi rohkem kiiresti, kuigi sa oled Tere tulemast tagasi kerida või peatada, lihtsalt läbi mõelda seda omas tempos, kuid mida meil nüüd on võimalus teha täpselt sama algoritmi neljale erinevate numbrite puhul. Nii lähme edasi, ja keskendub paremal pool, mida me oleme siin. Vasakpoolne pool sellest paremal pool, ja nüüd vasakul poolel vasakul poole, et õige pool, ja kuidas ma sortida nimekirja suurus 1, mis sisaldab ainult number 1? See on juba tehtud. Kuidas teha sama nimekirja suurus 1, mis sisaldab ainult 7? See on juba tehtud. Kolmas etapp selle poole, siis on ühendada need kaks elementi uude nimekirja suurus 2, 1 ja 7. Kas ei tundu, et on teinud kõik et palju huvitavat tööd. Vaatame, mis juhtub järgmisena. Ma lihtsalt järjestatud vasakul pool paremal pool minu originaal sisend. Nüüd on omamoodi õigus poole, mis sisaldab 5 ja 3. Lähme jälle vaatama vasakule poole, sorteeritud, õige pool, sorteeritud, ja ühendada need kaks kokku, mõningaid lisaruumi, 3 esikohal, siis tuleb 5. Ja nii nüüd oleme sorteeritud Vasakul pool paremal pool algse probleem ja paremal pool õige poole algse probleemi. Mis on kolmas ja viimane etapp? Noh, et ühendada need kaks poolt kokku. Nii et lubage mul saada endale mõned lisaruumi, kuid jällegi, ma võiks kasutada, et vaba ruumi up top. Aga me ei kavatse hoida see lihtsalt visuaalselt. Lubage mul ühinevad nüüd 1 ja Seejärel 3 ja seejärel 5 ja seejärel 7. Jättes mulle nüüd koos paremal pool originaal probleem see on täiesti järjestatud. Mis jääb? Ma tunnen, et mul hoida öeldes samu asju uuesti ja uuesti, kuid see peegeldab Asjaolu, et me kasutame recursion. Protsessi kasutades algoritmi jälle ja jälle väiksemate alajaotused algne probleem. Nii et ma nüüd on vasak järjestatud poolel esialgse probleemiga. Mul on õigus sorteeritud poole algse probleemi. Mis on kolmas ja viimane samm? Oh, see on ühinevate. Nii teeme seda. Olgem eraldada täiendavat mälu, kuid mu Jumal, me võiks panna seda kõikjal nüüd. Meil on nii palju ruumi meile, aga me hoiame seda lihtne. Selle asemel, et minna tagasi edasi meie originaal mälu Lihtsalt tee seda visuaalselt siia alla, et lõpetada ühendamine vasakul pool ja paremal pool. Nii ühendades, mida ma pean tegema? Ma tahan elementide järjekorda. Nii vaadates vasakul pool, Näen esimene number on 2. Ma vaatan paremale poole, Ma näen esimest number on 1, nii ilmselt mille number ma tahan kiskuda, ja pane esimene minu lõplik nimekiri? Loomulikult 1. Nüüd ma tahan küsida, et sama küsimus. Vasakul pool, ma olen ikka sai number 2. Paremal pool, Mul arv 3. Kumba ma tahan valida? Muidugi, number 2 ja Nüüd märkate kandidaadid on 4 vasakule, 3 paremale. Olgem muidugi valida 3. Nüüd kandidaadid on 4 Vasakul 5 paremale. Me muidugi valida 4. 6 vasakule, 5 paremale. Me muidugi valida 5. 6 vasakule, 7 paremale. Valisime 6, ja siis me vali 7, ja siis me valime 8. Voila. Nii suur hulk sõnu hiljem, me on järjestatud selles nimekirjas kaheksa elemendid loendisse ühe läbi kaheksa, see on kasvav iga samm, kuid kui palju aega see meid seda tegema. Noh ma olen teadlikult laid asju piltlikult siin, et saaksime sellist vaata või hindame jagunemine vallutavad, mis on juhtunud. Tõepoolest, kui sa vaatad tagasi pärast, Ma jätsin kõik need kriipsjoontega olemas omanikud, saad, selline, vaata, vastupidises järjekorras, kui sa selline tagasi vaadata ajalugu nüüd, mu esialgne nimekiri on muidugi suuruse 8. Ja siis varem olin tegelevad kahe loetelu size 4, ja seejärel neli nimekirja suurusega 2, ja siis kaheksa nimekirjad suurus 1. Mida see, selline, tuletavad meelde? Noh, tegelikult, ükskõik algoritme me oleme vaatasin siiani, kus me lõhe ja lõhe, ja lõhe hoida võttes asju uuesti ja omakorda toob kaasa selle üldine idee. Ja nii on midagi logaritmiline siin toimub. Ja see ei ole päris log n, kuid seal on logaritmiline osa mida oleme lihtsalt teha. Nüüd Vaatleme, kuidas see tegelikult on. Nii logida n, jälle oli suur sõiduaega, kui me tegime midagi Kahendotsingupuu, nagu me nüüd nimetame seda, lõhe ja vallutada strateegia mille kaudu leidsime Mike Smith. Nüüd tehniliselt. See on samamoodi baasi 2 n, isegi kuigi enamikus matemaatika klassi, 10 Tavaliselt on aluseks, et sa oletad. Aga arvuti teadlased peaaegu alati mõelda ja rääkida nii base 2, nii me tavaliselt lihtsalt öelda logi n asemel log baasi 2 n, kuid nad on täpselt üks ja Sama maailmas arvutis Teaduse ja kui kõrvale, seal on konstandiks Erinevus nende kahe vahel, nii et see on vaieldav niikuinii rohkem formaalsetel põhjustel. Aga nüüd, mida me hoolime umbes on see näide. Nii et ärme tõestada eeskuju, kuid vähemalt kasutada näide numbrid käepärast kui mõistuse kontrolli, kui soovite. Nii varem valem oli samamoodi alus 2 n, aga mis on n sel juhul. Mul oli n originaal numbrite või 8 originaal number konkreetselt. Nüüd on see olnud natuke samas, aga ma olen päris Veenduge, et samamoodi baasi 2 väärtusest 8 on 3, ja tõepoolest, mis on tore, et on et 3 on täpselt, mitu korda et saate jagada nimekirja 8-se pikkusega jälle ja jälle ja jälle, kuni sa oled jäänud nimekirjad lihtsalt suurus 1. Õigus? 8 läheb 4, läheb 2, läheb 1, ja see on kajastavad täpselt, et Pildil oli just hetk tagasi. Nii vähe meelerahu vaadata, kuhu logaritm on tegelikult seotud. Nüüd, mida veel siin on tegemist? n. Nii märkate, et iga kord, kui ma lahku nimekirja, kuigi vastupidises järjekorras ajalugu siin, ma olin ikka teed n asju. See ühinevad samm vajalik, et Ma puutuda igaüks numbrid, et lükake Oma sobivas kohas. Nii et kuigi kõrgus käesoleva skeem on suuruse log n n või 3, Konkreetsemalt teisisõnu Ma tegin kolm osakonda siin. Kui palju tööd ma tegin horisontaalselt mööda seda tabelit iga kord? Noh, ma tegin n sammud töötada, sest kui ma olen sain nelja elemendi ja nelja elementi, ja mul on vaja liita need kokku. Ma pean minema läbi Nende nelja ja need neli, lõpuks liita need tagasi kaheksa elemente. Kui vastupidi mul kaheksa sõrme siin, mida ma ei ole, ja kaheksa fingers-- sorry-- Kui ma olen sain nelja sõrme siin, mis ma teen, neli sõrme siin, mis ma teen, siis see on sama Näiteks kui enne, kui ma on kaheksa sõrme kuigi kokku, mida ma võib sellist, mida teha. Võin täpselt teha siin, siis saan kindlasti ühendada kõik need nimekirjad suurus 1 koos. Aga ma kindlasti vaatama igal element täpselt üks kord. Nii kõrgus see protsess on log n, laius selles protsessis, nii et rääkida, on n, siis mida me ilmselt on lõppkokkuvõttes on käigu aja suuruse n korda sisse n. Teisisõnu, jaotasime nimekirja, log n korda, kuid iga kord, kui me tegime seda, pidime puudutada iga üks elemente et liita need kõik koos, mis oli n samm, nii et meil on n korda sisse n, või kui arvuti teadlane ütleks, asymptotically, mis Oleks suur sõna kirjeldamiseks ülemise seotud kohta sõiduaega, töötab meil on suur o log n korda, kui nii võib öelda. Nüüd on see märkimisväärne, sest meenutada, mida töötab ajad olid mull sorteerida, ja valik sorteerida ja sisestamise sorteerida, ja isegi mõned teised, mis on olemas, n ruudus oli, kus me olime. Ja saate, millist vaata seda siin. Kui n ruudus on ilmselt n korda n, kuid siin on meil n korda sisse n, ja me teame juba nädal null, et log n, logaritmiline, on parem kui midagi lineaarne. Lõppude lõpuks meelde pilt punane ja kollane ja rohelised jooned, mida me juhtis, siis roheline logaritmiline line oli palju väiksem. Ja seetõttu palju paremini ja kiiremini kui otse kollast ja punast joont, n korda sisse n on tõepoolest parem kui n korda n või n ruudus. Nii näib, et oleme tuvastatud algoritmi ühendamine Sorteeri et töötab palju kiirem aeg, ja tõepoolest, Sellepärast, varem sel nädalal, kui nägime, et võistlus mull Sorteeri valiku sorteerida ning ühendada sorteerida, liita omamoodi tõesti võitis. Ja tõepoolest, me isegi ei oodata mull sorteerida ning valikut omamoodi lõpetama. Nüüd võtame ühe teise pass selles, alates veidi ametliku perspektiivis ainult Juhul, see kõlab paremini kui kõrgema arutelu. Nii et siin on algoritm uuesti. Palume end, mida sõiduaega on selle algoritmi erinevate etappide? Olgem jagada see esimene juhul ja teisel juhul. IF ja mujal IF juhul, IF n on alla 2, lihtsalt tagasi. Tunne konstantset aega. See, millist, nagu kaks sammu, IF n on alla 2, siis tagasi. Aga kui me ütles esmaspäeval, konstantset aega, või suur o 1, võib olla kahe sammu, kolm sammud, isegi 1000 sammu. Oluline on, et see on pidev mitmeid samme. Nii kollane rõhutas pseudokoodi Siin jookseb, siis me nimetame seda, konstantset aega. Nii ametlikumalt ja me läheme mina-- seda saab millisel määral me vormistama selle õiguse now-- T n, Tööaja probleem mis võtab n midagid sisendiks võrdub suur o ühe, IF n on alla 2. Nii et see on tingimuseks, et. Nii olevat selge, IF n on väiksem kui 2, meil on väga lühike nimekiri, siis jooksva aja, T n, kus n on 1 või 0, selles väga konkreetsel juhul see on lihtsalt saab olema pidev aega. See saab olla üks samm, kaks sammu, mida iganes. See on kindel arv samme. Nii mahlane osa peab kindlasti olema Teisel juhul on pseudokoodi. Else puhul. Sorteeri vasakul pool elemente, sorteerida õige pool elemendid, ühendada sorteeritud pooleks. Kui kaua kõik need sammud võtta? Noh, kui jooksmine aega, et sortida n elemendid on, olgem kutsuvad seda väga üldmõistena, T n, Seejärel sorteerimine vasakul poolel elemendid on selline, nagu öelda, T n jagatuna 2, ja sarnaselt sorteerimine paremal pool elementide on selline, nagu öelda, T n jagatuna 2 ja seejärel liitmise järjestatud pooleks. Noh, kui mul on mõned elementide arv siin nagu neli, ja mõned number elementide siin, nagu neli, ja mul on ühendada kõik need neli in, ja iga nimetatud neli, üks teise järel, nii et lõppkokkuvõttes Mul on kaheksa elemente. Tundub nagu see on suur o n sammud? Kui mul n sõrmed ja iga neid on kavas liita koht, see on nagu teine ​​n samme. Nii tõesti formulaically, saame väljendada seda, kuigi veidi scarily esimesel lühidalt, kuid see on midagi, mis lööb täpselt, et loogika. Jooksuaeg, T n, IF n on suurem või võrdne 2. Sel juhul ELSE juhul on T n jagatuna 2 pluss T N jagatuna 2, plus big o n, mõned lineaarne mitmeid samme, võibolla täpselt n, võibolla 2 korda n, kuid see on umbes, et n. Nii et on ka see, kuidas me suudame väljendada seda formulaically. Nüüd sa ei tea seda, kui olete salvestatud seda meelt, või otsida see üles tagasi õpik, mis võib-olla natuke petma lehte lõpus, aga see on tõesti läheb anna meile suur o n log n, sest kordumise et näed siin ekraanil, kui sa tegelikult tegi seda välja, kus lõpmatu hulk näiteid, või sa tegid seda formulaically, siis oleks näha, et see, sest see valem ise on rekursiivne, kus t n üle midagi õigus, ja t N üle otsustada, seda saab tegelikult väljendatakse lõppkokkuvõttes kui suur go n log n. Kui ei ole veendunud, et see trahvi nüüd, lihtsalt võtma usu, et see on tõepoolest mida see kordub viib, aga see on lihtsalt natuke rohkem matemaatilist lähenemist otsin kell töötamise aeg ühendada omamoodi põhineb selle pseudokoodi üksi. Võtame nüüd natuke hingetõmbeaeg kõik see, ja võtta pilk Teatud endine senaator, kes võiks vaadata veidi tuttav, kes istus Google'i Eric Schmidt, mõni aeg tagasi, intervjuu laval ees terve hunnik inimesed, rääkides lõppkokkuvõttes teema, mis on päris nüüd tuttav. Võtame pilk. Eric Schmidt: Nüüd senaator, sa oled siin Google, ja mulle meeldib mõelda eesistujariik tööintervjuu. Nüüd on raske tööd saada presidendiks. President Obama: Right. Eric Schmidt: Ja sa oled kavatseb teha [kuuldamatu] nüüd. Samuti on raske saada tööd Google. President Obama: Right. Eric Schmidt: Meil ​​on küsimusi, ja küsime meie kandidaatide küsimusi, ja see on Larry Schwimmer. President Obama: OK. Eric Schmidt: Mis? Te arvan, et ma nalja? See on siinsamas. Mis on kõige tõhusam viis sorteerima miljonit 32- täisarvud? President Obama: Well-- Eric Schmidt: Mõnikord võibolla ma vabandan, maybe-- President Obama: Ei, ei, ei, ei, ei, ma think-- Eric Schmidt: See ei ole see-- President Obama: ma arvan, ma arvan, et mull Sorteeri oleks vale tee. Eric Schmidt: Tule. Kes ütles talle seda? OKEI. Ma ei arvutiteaduse nüüd-- President Obama: Me oleme sai meie spioonid seal. PROFESSOR: Okei. Jätkem meil nüüd teoreetiline maailma algoritme in asümptootiliseks analüüs selle, ja tagasi mõned teemad nädalast null ja üks, ja algus eemaldada mõned abirattad, kui soovite. Nii et sa tõesti aru lõpuks maast üles, mis on toimub all kapuuts, kui sa kirjutada, koostada ja täita programme. Meenuta eelkõige, et see oli Esimeses C programmi me vaatasime, kanooniline, lihtne programm kehvasti, on suhteliselt kus see prindib, Hello World. Ja meenub, et ma ütlesin, protsessi et lähtekoodi läbib on täpselt see. Te võtate oma lähtekoodi, edasi see läbi koostaja, nagu rõkkama, ja välja tuleb objekti kood, mis tunduda see, ühtede ja nullide et arvuti protsessor, tsentraalne töötlemise üksus või aju, lõpuks aru. Selgub, et see on natuke järeleandmisi, et me oleme nüüd on positsiooni tease peale mõista, mida on tõesti olnud toimub all kapuuts Iga kord, kui sa jooksed Rõkkama, või üldisemalt, Iga kord, kui programmi, kasutades Mark ja CF 50 IDE. Eelkõige asju see on esimene loodud, kui te esimest kompileerida programmi. Teisisõnu, kui võtta oma lähtekoodi ja kompileerida, mis on esimene seda poolt väljastatav rõkkama on midagi, mida tuntakse kokkupanek koodi. Ja tegelikult, see näeb välja täpselt nagu see. Jooksin käsk käsurea varem. Rõkkama kriips kapitali s hello.c, ja see on loodud faili minu nimega hello.s, mille sees olid täpselt Nende sisu ning veidi rohkem ülespoole ja veidi allpool aga ma panin juiciest info siin ekraanil. Ja kui sa vaatad tähelepanelikult, siis näete vähemalt paar tuttav märksõnu. Meil on peamine tipus. Oleme printf alla keskele. Ja meil on ka tere kurakriips n jutumärkides allapoole. Ja kõik muu siin väga madal juhiseid et arvuti protsessor saab aru. CPU juhiseid, et liikuda mälu ümber, et koormus stringid mälust, ja lõpuks, print asjad ekraanil. Nüüd, mis juhtub, kuigi pärast Selle kokkupanek kood genereeritakse? Lõppkokkuvõttes sa tõepoolest veel luua objekti kood. Aga sammud, mis on tõesti kestnud all kapuuts otsida veidi rohkem niimoodi. Lähtekood muutub montaaž koodi mis siis saab objekti kood, ja operatiivne sõna on siin, et kui sa kompileerida lähtekoodist, välja tuleb kokkupanek kood ja seejärel kui sa koguda oma kokkupanek koodi välja tuleb objekti kood. Nüüd rõkkama on super kogenud, nagu palju koostajad, ja ta teeb kõik need sammud kokku ja ei tähenda see tingimata väljund mõni vahepealne faile, mida saate isegi näha. See lihtsalt kogub asju, mis on üldine termin, mis kirjeldab kogu seda protsessi. Aga kui sa tõesti tahad olema eelkõige seal palju läheb seal hästi. Aga olgem kaaluma ka nüüd, et isegi et super lihtne programm, hello.c, nimetatakse funktsiooni. Ta kutsus printf. Aga ma ei kirjuta printf, tõepoolest, mis kaasas c, nii rääkida. See funktsioon meelde tuletada, et on deklareeritud standard io.h, mis on päisefailist, mis on teema me tegelikult sukelduda põhjalikumalt enne pikk. Aga päisefailist on Tavaliselt kaasneb koodi abil faili lähtekoodi faili, nii et palju nagu on olemas standard io.h. Millalgi tagasi, keegi, või kellegi, kirjutas ka fail nimega standard io.c, in mille tegelik mõisted, või rakenduste printf, ja kobarad muid funktsioone, tegelikult kirjutatud. Nii, arvestades, et juhul, kui arvame, võttes siin vasakul, hello.c, et kui koostatud, annab meile hello.s, isegi kui Rõkkama ei viitsinud kokkuhoid kohas Me näeme seda, ja et montaaži koodi saab kokku võtta hello.o, mis on tõepoolest vaikenimetus antakse alati kompileerida allikas kood objekti kood, kuid ei ole päris valmis täitma seda veel, sest järjekordne samm peab juhtuma, ja on toimunud viimastel nädalat, võib-olla teadmata teid. Täpsemalt kusagil in CS50 IDE, ja see, Ka on natuke järeleandmisi hetkeks, seal on, või oli ammu, fail nimega standard io.c, et keegi kompileeritud standard io.s või samaväärne, et keegi siis kokku pandud kirjakeele io.o, või selgub sisse veidi erinev faili vormi, mis võib olla erinev faililaiend kokku, kuid teoreetiliselt ja põhimõtteliselt täpselt need sammud pidi juhtuma mingi. Mis tähendab, et nüüd kui ma kirjutan programmi hello.c, et lihtsalt ütleb, tere, ja ma kasutan kellegi koodi nagu printf, mis oli Ükskord ajal, fail nimega standard io.c, siis kuidagi pean võtma minu objekti kood, minu ühtede ja nullide, ja et inimese objekti kood või ühtede ja nullide, ja kuidagi siduda need kokku ühte üks lõplik fail nimega hello, et on kõik nullid ja need on minu peamine funktsioon, ja kõik nullid ja need, printf. Ja tõepoolest, et viimane protsess on nimetatakse, sidudes oma objekti kood. Mille väljundiks on käivitatav fail. Nii õiglus, kell Lõppkokkuvõttes, midagi muutunud nädalal üks, kui me hakkas koostamise programme. Tõepoolest, kõik see on olnud toimub all kapuuts, kuid nüüd oleme olukorras kus me saame tegelikult tease peale nende erinevate etappide. Ja tõepoolest, lõpus Päeva oleme endiselt jäänud ühtede ja nullide, mis on tegelikult suur Segue nüüd teisele võime C, et meil ei olnud võimendada tõenäoliselt siiani tuntud bitwise ettevõtjad. Teisisõnu, seni, millal me oleme käsitletud andmete C või muutujate C, oleme olnud asjad tähemärki ja ujukite ja ins ja pikad ja kahekordistab jms, kuid Kõigil neil on vähemalt kaheksa biti. Me pole kunagi veel suutnud manipuleerida üksikute bittide, kuigi üksikute natuke, me teate, ei kujuta endast 0 ja 1. Nüüd selgub, et C, siis ei pääse individuaalsete bitti, kui sa tead, süntaks, millega saada neid. Võtame pilk kell bitwise ettevõtjad. Nii pildil siin on mõned sümbolid, oleme, selline, justkui, näinud. Näen ampersand, vertikaalne baari, ja mõned teised ka, ja meelde tuletada, et ampersand ampersand on midagi, mida me varem näinud. Loogiline JA operaator, kus teil on kahes kokku või loogilise OR operaator, kus te on püsttriipudele. Bitikaupa ettevõtjad, mida me tulen vaata tegutseda bitti individuaalselt, lihtsalt kasutada ühte ampersand, et vertikaalse riba, katus sümbolit tuleb järgmisena, väike tilde ja seejärel vasakule sulg Vasaksulg või õige sulg õigus sulg. Igaüks neist on erinev tähendus. Tegelikult võtame pilk. Lähme vana kooli täna ja kasutamine puutetundlik alates Läinud, tuntud kui valge tahvel. Ja see valge tahvel läheb võimaldab meil väljendada mõned üsna lihtne sümboleid, või pigem mõned üsna lihtne valemeid, et siis saame lõpuks finantsvõimendus, et juurdepääsu üksikisiku bittide C programmi. Teisisõnu, teeme seda. Vaatame kõigepealt rääkida jaoks hetkel umbes ampersand, mis on bitwise ja operaatorist. Teisisõnu, see on operaator, mis võimaldab mind on vasakpoolne muutuja tavaliselt ja parempoolne muutuja, või üksikisiku väärtus, et kui me ise need kokku, annab mulle lõpptulemus. Mida ma mõtlen? Kui programm, teil on muutuv mis talletab üks nendest väärtustest, või olgem hoida lihtsa ja lihtsalt kirjutada ühtede ja nullide individuaalselt, Siin on, kuidas ampersand operaator töötab. 0-märgiga 0 läheb võrdne 0. Nüüd, miks see nii on? See on väga sarnane Loogiline väljendeid, et me oleme arutanud siiani. Kui te arvate, ju 0 on vale, 0 on väär, vale ja vale on, nagu me oleme arutanud loogiliselt ka vale. Nii saame 0 ka siin. Kui te võtate 0 ampersand 1 hästi, et ka saab olema 0, sest sel vasakul väljendus, et olla tõsi või 1, oleks vaja, et olla tõsi ja tõsi. Aga meil on siin vale ja tõsi, või 0 ja 1. Nüüd jälle, kui meil on 1 ampersand 0, et ka saab olema 0, ja kui meil on 1 ampersand 1 Lõpuks on meil 1 bit. Nii teisisõnu, me ei tee midagi huvitavat selle operaatoriga lihtsalt veel, see ampersand operaator. See on bitwise ja operaatorist. Kuid need on koostisained mille kaudu me saame teha huvitavaid asju, nagu me varsti näha. Nüüd vaatame ainult ühe püstribale siin paremal. Kui mul on 0 natuke ja ma VÕI seda, BitWise Või käitaja muu 0 natuke, mis läheb mulle 0. Kui ma võtan 0 natuke ja OR seda 1 bit, siis ma lähen 1. Ja tegelikult, lihtsalt selgus, lubage mul tagasi minna, nii et minu püstribade ei eksi 1 s. Kirjutan kõik minu 1 on natuke rohkem selgelt, et me kõrval näha, kui ma on 1 või 0, et see saab olema 1, ja kui mul on 1 või 1, et Ka see saab olema 1. Nii et näete, loogiliselt, et OR operaator käitub väga erinevalt. See annab mulle 0 või 0 annab mulle 0, kuid Iga muu kombinatsioon annab mulle 1. Nii kaua, kui mul on üks 1 valem, tulemus saab olema 1. Erinevalt JA operaator, ampersand, ainult siis, kui mul on kaks 1-aasta võrrand, ma tegelikult saada 1 out. Nüüd on mõned muud ettevõtjad samuti. Üks neist on veidi rohkem kaasatud. Nii et lubage mul minna ja kustutada Selle vabastada ruumi. Ja võtame pilk Katus tähendab, et üks hetk. See on tavaliselt iseloomu saab kirjutada klaviatuuril Shift all hoides ja siis üks arvudest atop oma USA klaviatuuri. Nii et see on eksklusiivne Või käitaja välistav VÕI. Nii et me lihtsalt nägin OR operaatoriga. See on ainus või operaator. Mis tegelikult vahet seal on? Noh olgem lihtsalt vaadata valem, ja kasutada seda kui koostisosad lõpuks. 0 XOR 0. Ma ütlen alati 0. See määratlus XOR. 0 XOR 1 läheb 1. 1 XOR 0 saab olema 1, ja 1 XOR 1 läheb? Vale? Või eks? Ma ei tea. 0. Nüüd sellest, mis siin toimub? Noh mõelda nimi see operaator. Exclusive OR, nii nagu nimi, selline, näitab, Vastus on ainult kavatse olla 1, kui sisendid on eksklusiivne, ainult erinevad. Nii et siin sisendid on sama, nii väljund on 0. Siin sisendid on sama, nii väljund on 0. Siin on väljundid on erinevad, on eksklusiivne, seega väljund on 1. Nii et see on väga sarnane Ja see on väga sarnane, või pigem on see väga sarnane OR, kuid ainult eksklusiivne viis. See üks ei ole enam 1, sest meil on kaks 1-, ja mitte ainult, vaid üks neist. Hästi. Aga teised? Noh tilde, vahepeal on tegelikult kena ja lihtne õnneks. Ja see on unaarse operaatori, mis tähendab see on rakendatud ainult üks sisend, üks operand, kui nii võib öelda. Mitte vasakule ja paremale. Teisisõnu, kui te võtate tilde kohta 0, siis vastus on vastupidine. Ja kui te võtate tilde of 1 Vastus tekib vastupidine. Nii tilde operaator viis nullides natuke, või flipping natuke 0-1 või 1-0. Ja mis jätab meid lõpuks vaid kaks viimast ettevõtjad, niinimetatud nihutamist vasakule ja Niinimetatud õigus vahetuse operaator. Võtame pilk kuidas need tööd. Vasakpoolne vahetuse operaator, kirjutatud kahe noolsulgudes niimoodi, toimib järgnevalt. Kui minu sisend, või minu operandi, vasakule vahetuse operaator on lihtsalt 1. Ja ma siis ütlen, et arvuti vasakule nihe, et 1, ütleme seitsme koha, tulemus on nii, nagu ma võtta, et 1 ja liigutada seitsme koha üle Vasakul ja vaikimisi me läheme eeldada, et ruumi paremale läheb polsterdatud nulli. Teisisõnu, 1 vasakule nihe 7 läheb mulle, et 1, millele järgnes 1, 2, 3, 4, 5, 6, 7 nulle. Nii nii, siis saab võtta väike number nagu 1, ja selgelt oleks palju palju, palju suurem sel viisil, aga me tegelikult näeme targem lähenemisviise see asemel, samuti, Hästi. Ongi nädal kolm. Me näeme järgmine kord. See oli CS50. [Muusika mängib] SPEAKER 1: Ta oli suupiste baaris süüa kuuma sepitsus plombiir. Tal oli kõik üle tema näo. Ta kannab, et šokolaad nagu habe SPEAKER 2: Mida sa teed? SPEAKER 3: Hmmm? Mida? SPEAKER 2: Kas sa lihtsalt topelt dip? Sa topelt kasta kiip. SPEAKER 3: Vabandage mind. SPEAKER 2: Sa kasta kiip, siis võttis hammustada, ja sa kasta uuesti. SPEAKER 3: SPEAKER 2: Nii et nagu paneb kogu oma suu õige dip. Järgmine kord, kui te võtate chip, lihtsalt pane see kord, ja seda lõpetada. SPEAKER 3: Tead mis, Dan? Sa pane nii, et sa tahad pane. Ma kasta nii, et ma tahan pane.