[TÓNLIST spila] Prófessor: Allt í lagi. Þetta er CS50 og þetta er í lok viku þrjú. Þannig að við erum hér í dag, ekki í Sanders Theater stað í Weldner Library. Inni sem er stúdíó þekktur sem Hauser Studio, eða eigum við að segja Studio H, eða eigum vér við say-- ef þú njóta að brandari, það er í raun frá bekkjarfélaga, Mark, á netinu, sem lagði eins mikið í gegnum Twitter. Nú er það kaldur um að vera hér í stúdíó er að ég er umkringdur þessum græna veggir, grænt skjár eða chromakey, svo að segja, sem þýðir að CS50 er framleiðslu lið, unbeknownst til mín núna, gæti verið að setja mig mest hvar sem er í heiminum, fyrir betri eða verri. Nú liggur það á undan, vandamál setja tvö er í höndum þínum fyrir þessa viku, en með Heimadæmi þrír þetta næstu viku, þú verður að vera áskorun með svokallaða leikur af 15, gamall aðila hag að þú might muna að fá sem barn sem hefur a heild búnt af tölum sem getur renna upp, niður, vinstri og hægri, og það er eitt bil innan ráðgáta, í sem þú geta í raun renna þessir ráðgáta stykki. Einhvern sem þú færð þetta þraut í sumum hálf handahófi, og markmiðið er að raða það, toppur til botn, vinstri til hægri, frá einu alla leið upp í gegnum 15. Því miður, framkvæmd þú munt hafa á hendi er að fara að vera hugbúnaður byggt, ekki líkamlega. Þú ert í raun að fara að þurfa að skrifa númer sem nemandi eða notandi getur spila leikinn 15. Og í raun, í spjallþráð útgáfa af leiknum af 15, þú munt vera erfitt að hrinda í framkvæmd, ekki bara að leika þetta gamla skólanum leikur, heldur leysa af því, að innleiða guð ham, svo að segja, sem í raun leysa þraut fyrir mönnum, því að veita þeim vott, eftir vott, eftir vísbending. Svo meira á því í næstu viku. En það er það sem er framundan. Fyrir nú muna að fyrr í þessari viku við höfðum þetta cliffhanger, ef þú vilt, þar sá besti sem við vorum að gera flokkun vitur var efri mörk stór eða n veldi. Með öðrum orðum, kúla raða, Val tegund, innsetning flokka, öllum þeim, en mismunandi í framkvæmd þeirra, dreifstýringu inn í n veldi gangi tími í mjög versta tilfelli. Og gerum við ráð almennt að mjög versta tilfelli fyrir flokkun er eitt sem inntak þitt eru alveg aftur á bak. Og reyndar, það tók alveg nokkur skref að framkvæma hvert þessara reiknirit. Nú á mjög lok bekknum muna, samanborið við kúla konar gegn Val tagi gegn einum öðrum sem við kölluðum mergesort á þeim tíma, og ég leggja til að það tekur Kosturinn við lexíu frá viku núll, skipta og sigra. Og einhvern veginn ná einhvers konar lógaritmískum hlaupandi tími lokum, í stað þess að eitthvað það er eingöngu stigs. Og það er ekki alveg lógaritmískum, það er dálítið meira en það. En ef þú manst frá bekknum, það var miklu, miklu hraðar. Við skulum taka a líta á þar sem við var horfið. Bubble konar móti vali konar móti sameiningu tagi. Nú þeir eru allir hlaupandi í kenning, á sama tíma. The CPU er í gangi á sama hraða. En þú getur fundið hvernig leiðinlegur þetta er mjög fljótt að fara að verða, og hversu hratt, þegar við sprauta smá viku núll er reiknirit, getum við að hraða hlutum upp. Svo árangur konar lítur ótrúlega. Hvernig getum við nýta það til þess að raða tölur hraðar. Jæja við skulum hugsa til baka að efnið sem við hafði aftur í viku núll, að af leita að einhverjum í símaskránni, og muna að sauðakóðanum sem við lagt, um sem við getum fundið einhver eins og Mike Smith, horfði smá eitthvað eins og this. Nú taka a líta einkum á línu 7 og 8, og 10 og 11, sem örva þessi lykkja, þar sem við haldið fara aftur til línu 3 aftur og aftur, og aftur. En það kemur í ljós að við getum skoðað Þetta reiknirit, hér í sauðakóða, aðeins meira heildrænt. Í raun, hvað ég er að leita á hér á skjánum, er reiknirit til að leita að Mike Smith meðal sumir setja af síðum. Og reyndar, gætum við einfalda þetta reiknirit í þeim línum 7 og 8, og 10 og 11 til að bara segja þetta, sem ég hef kynnt hér í gulum. Með öðrum orðum, ef Mike Smith er fyrr í bókinni, við þurfum ekki að tilgreina skref skref nú hvernig á að fara að finna hann. Við þurfum ekki að tilgreina til að fara aftur til línu 3, hvers vegna er það ekki bara í staðinn, segja, almennt, leita Mike í vinstri hluta bókarinnar. Hins vegar ef Mike er reyndar seinna í bókinni, Hvers vegna eigum við ekki að vitna bara unquote leit fyrir Mike í hægri hluta bókarinnar. Með öðrum orðum, hvers vegna er það ekki bara konar punt að okkur að segja, leita Mike í þessu hlutmengi af bókinni, og fara með hana til núverandi okkar reiknirit til að segja okkur hvernig á að leita að Mike í að vinstri hluta bókarinnar. Með öðrum orðum, okkar reiknirit virkar hvort sem það er a símaskrá þessa þykkt, þetta þykkt, eða þykkt af neinu tagi. Þannig að við getum endurkvæmt skilgreina þetta reiknirit. Með öðrum orðum, á skjár hér er reiknirit til að leita að Mike Smith meðal síðum símaskránni. Svo í línu 7 og 10, við skulum bara segja einmitt það. Og ég nota þetta hugtak í smá stund síðan, og reyndar, endurkvæmni er tískuorð nú, og það er þetta ferli um að gera eitthvað cyclical með einhvern veginn með kóða sem þú hefur nú þegar, og kalla það aftur, og aftur, og aftur. Nú það er að fara að vera mikilvægur sem við botn einhvern veginn út, og gera það ekki óendanlega lengi. Annars erum við að fara að hafa örugglega óendanlega lykkju. En við skulum sjá hvort við getum fengið lánað þessa hugmynd af endurkvæmni, gera eitthvað aftur og aftur og aftur, til að leysa flokkunarröðina vandamál með sameinast raða, allt skilvirkari. Þannig að ég gef þér Mergesort. Við skulum taka a líta. Svo er hér sauðakóðanum með sem við gætum framkvæma flokkun, nota þessa reiknirit sem kallast Mergesort. Og það er einfaldlega þetta. Á inntak n þætti, í öðrum orðum, ef þú ert gefið n þætti og númer og bréf eða hvað inntak er, ef þú ert að gefa n þætti, ef n er minna en 2, bara aftur. Ekki satt? Vegna þess að ef n er minna en 2 og þá þýðir að minn listi af þáttum er annað hvort af stærð 0 eða 1, og í báðum þessum léttvæg tilvikum, listinn er þegar raðað. Ef það er enginn listi, það er flokkað. Og ef það er listi af lengd 1, það er augljóslega flokkað. Svo reiknirit þarf aðeins að raunverulega gera eitthvað áhugavert, ef við höfum tvö eða fleiri þættir gefið okkur. Svo skulum líta á galdra þá. Else raða vinstri helming þætti, þá raða rétt helminginn af þáttum, síðan sameinað flokkuð helminga. Og hvað er góður af huga beygja hér, er að ég í raun ekki virðast hafa sagt þér eitthvað strax, ekki satt? Allt sem ég hef sagt er, fá lista yfir n þættir, raða vinstri helming, þá hægri helminginn, þá sameina flokkuð helminga, en þar er í raun leyndarmál sósu? Hvar er reiknirit? Jæja það kemur í ljós að þeim tveimur línum fyrst raða vinstri helmingi þætti, og svoleiðis hægri helminginn af þáttum, eru endurkvæma símtöl, svo að segja. Eftir allt saman, í þetta tímapunktur, ég hef reiknirit sem til raða a heild búnt af þætti? Já. Það er hérna. Það er hérna á skjánum, og svo ég geti notað það sama mengi skrefum að raða vinstri helming, og ég get hægri helminginn. Og reyndar, aftur, og aftur. Svo einhvern veginn eða annan, og við munum fljótlega sjá þetta, töfra mergesort er fellt í að mjög endanleg lína, sameina flokkuð helminga. Og það virðist nokkuð innsæi. Þú tekur tvo helminga, og þér, einhvern veginn, sameina þær saman, og við munum sjá þetta concretely í smá stund. En þetta er heill reiknirit. Og við skulum sjá nákvæmlega hvers vegna. Jæja ætla að við erum gefið þetta sama átta þættir hér á skjáinn einn til átta, en þeir eru í því er virðist af handahófi. Og markmiðið sem fyrir hendi er að raða þessum þætti. Jæja hvernig get ég farið um gera það með, aftur, Mergesort, eins og á þessari sauðakóðanum? Og aftur, ingrain þetta í hugur þinn, fyrir aðeins augnablik. Fyrsta tilfelli er nokkuð léttvæg, ef það er minna en 2, bara aftur, það er engin vinna að vera. Svo í raun er það bara þrír skref til að virkilega halda í huga. Aftur, og aftur, ég er fara til að vilja hafa að raða vinstri helming, raða rétt helminginn, og síðan einu sinni þeirra tvennt eru flokkuð, Ég vil sameina þá saman í eitt raðaða listanum. Svo halda að í huga. Svo hér er upprunalega lista. Skulum meðhöndla þetta sem array, eins og við byrjuðum að í viku tvö, sem er Samhangandi blokk af minni. Í þessu tilfelli, sem inniheldur átta tölur, aftur til baka til baka. Og við skulum nú eiga mergesort. Svo ég vil fyrst að raða vinstri helminginn af þessum lista, og við skulum því áherslu á 4, 8, 6, og 2. Nú hvernig get ég farið um flokkun lista yfir stærð 4? Jæja ég verð að íhuga nú flokkun vinstri á vinstri helming. Aftur, við skulum baka fyrir aðeins augnablik. Ef sauðakóðanum er þetta, og ég er að gefa átta þætti, 8 er augljóslega meiri en eða jafnt og 2. Svo með fyrsta tilfelli á ekki við. Svo til að raða átta þætti, ég fyrst raða vinstri helming þætti, þá er ég að raða rétt helminginn, þá er ég sameinast tveir röðuðu helminga, hver stærð 4. OK. En ef þú hefur bara sagt mér, raða vinstri helming, sem er nú á stærð 4, hvernig get ég raða vinstri helminginn? Jæja ef ég á inntak af fjórum þáttum, Ég raða fyrst vinstri Tveir, þá hægra tveir, og þá er ég sameinast þeim saman. Svo aftur, verður það svolítið af huga beygja leikur hér, vegna þess að þú, eins konar, að muna hvar þú ert í sögunni, en í lok dagsins, veitt nein fjölda staka, þú vilt fyrst að raða í vinstri helminginn og svo hægri helming, þá sameinast þeim saman. Við skulum byrja á að gera einmitt það. Hér er inntak átta þáttum. Nú erum við að horfa á vinstri helming hér. Hvernig get ég raða fjóra þætti? Jæja ég raða fyrsta vinstri helming. Nú hvernig ég raða vinstri helminginn? Jæja ég hef fengið tvo þætti. Svo skulum raða þessum tveimur þáttum. 2 er meiri en eða sama sem 2, að sjálfsögðu. Þannig að fyrsta tilfelli á ekki við. Þannig að ég hef nú að raða vinstri helmingur af þessum tveimur þáttum. Vinstri helmingur, auðvitað, er bara 4. Svo hvernig get ég raða lista yfir einn þáttur? Jæja nú, að sérstakt stöð tilfelli upp efst, svo að segja, gildir. 1 er minna en 2, og mín Listinn er reyndar í stærð 1. Svo ég aftur bara. Ég geri ekki neitt. Og reyndar, líta á það sem ég hef gert, 4 er þegar raðað. Eins og ég er nú þegar hluta vel hér. Nú virðist sem eins konar heimskur kröfu, en það er satt. 4 er listi af stærð 1,. Það er þegar raðað. Það er vinstri helmingur. Nú er ég að raða rétt helminginn. Inntak mitt er einn þáttur, 8 álíka, þegar raðað. Stupid, of, en aftur, þetta grundvallarregla er að fara að leyfa okkur að nú byggja ofan á þetta með góðum árangri. 4 flokkaður, 8 er raðað, nú hvað var það síðasta skrefið? Svo þriðja og síðasta skrefið, allir skipti sem þú ert að flokka lista, muna, var að sameina tvo helminga, vinstri og hægri. Svo skulum gera einmitt það. Vinstri helmingur mín er, að sjálfsögðu, 4. Hægri helming minn er 8. Svo skulum gera þetta. Fyrst ég ætla að úthluta sumir fleiri minni, að ég tákna hér, sem bara annar fylking, sem er nógu stór til að passa þetta. En þú getur ímyndað nær að rétthyrningur endilangri, ef við þurfum meira seinna. Hvernig tek ég 4 og 8, og sameinast þessir tveir listar stærð 1 saman? Hér líka, frekar einfalt. 4 kemur fyrst, þá kemur 8. Vegna þess að ef ég vil raða vinstri helminginn og svo hægri helming, og þá sameinast þessar tvær helminga saman, í raðaða röð, 4 kemur fyrst, þá kemur 8. Þannig að við virðast vera að framfarir, jafnvel þó að ég hafi ekki gert neina raunverulegu starfi. En muna þar sem við erum í sögunni. Við tók upphaflega átta þætti. Við raðað vinstri helming, sem er 4. Þá erum við flokkuð vinstri helming á vinstri hluta, sem var 2. Og hér erum við að fara. Við erum búin með þessi skref. Þannig að ef við höfum raðað í vinstri helmingi 2, nú erum við að raða rétt helminginn af 2. Svo er hægri helminginn af 2 þessi tvö gildi hér, 6 og 2. Svo skulum við taka nú inntak stærð 2, og raða vinstri helming, og þá hægri helminginn, og þá sameina þær saman. Jæja hvernig ég raða lista af stærð 1, sem inniheldur bara númer 6? Ég er nú þegar gert. Listinn yfir stærð 1 er raðað. Hvernig get ég raða annan lista af stærð 1, svonefnd hægri helminginn. Jæja það líka, er þegar raðað. Talan 2 er einn. Svo nú hef ég tvo helminga, vinstri og rétt, ég þarf að sameina þá saman. Leyfðu mér að gefa mér smá auka pláss. Og setja 2 í það, þá 6 í það, þannig flokkun þessi listi, vinstri og hægri, og sameina það saman, að lokum. Þannig að ég er í örlítið betra form. Ég er ekki búinn, því greinilega 4, 8, 2, 6 er ekki endanleg röðun sem ég vil. En ég hef nú tvo lista af stærð 2, sem hafa bæði, hver um sig, verið raðað. Svo nú ef þú til baka í huga þinnar auga, hvar did sem yfirgefa okkur? Ég byrjaði með átta þætti, svo ég tálga það niður á vinstri hluta 4, þá vinstri helminginn af 2, og þá hægri helminginn af 2, Ég kláraði því flokkun vinstri helmingur af 2, og hægri helminginn af 2, svo er það þriðja og síðasta skrefið hér? Ég verð að sameinast saman tveir listar stærð 2. Svo skulum við fara á undan. Og á skjánum hér, gefa mig sumir fleiri minni, þótt tæknilega, eftir að ég hef got a heild búnt af auðu plássi upp efst þar. Ef ég vil vera sérstaklega duglegur rúm vitur, Ég gæti bara byrja að færa þætti fram og til baka, efst og neðst. En bara fyrir sjón skýrleika, Ég ætla að setja það niður fyrir, að halda gott og hreint. Svo ég hef fengið tvo lista af stærð 2. Fyrsti listi er 4 og 8. Annað listi hefur 2 og 6. Skulum sameinast þeim saman í raðaða röð. 2, að sjálfsögðu, kemur fyrst, þá 4, þá 6, þá 8. Og nú erum við virðist vera að fá einhvers staðar áhugavert. Nú hef ég raðað helmingur lista, og tilviljun, það er allar sléttar tölur, en það er reyndar bara tilviljun. Og ég nú hafa raðað vinstri helmingur, þannig að það er 2, 4, 6 og 8. Ekkert er út af röð. Það er eins og framfarir. Nú er hún eins og ég hef verið að tala eilífu nú, svo er það að koma í ljós hvort þetta reiknirit er reyndar skilvirkari. En við erum að fara í gegnum það frábær skipulega. A tölva, að sjálfsögðu, myndi gera það svona. Svo Hvar erum við? Við byrjuðum með átta þætti. Ég flokkaður vinstri helming af 4. Ég virðist vera búinn með það. Svo nú er næsta skref að raða hægri helminginn af 4. Og þessi hluti sem við getum farið í gegnum smá meira fljótt, þótt þú ert velkomið að baka eða gera hlé, bara hugsa um það á eigin hraða, en það við höfum nú er tækifæri til að gera nákvæmlega sama reiknirit á fjórum mismunandi númer. Svo skulum við fara á undan, og leggja áherslu á hægri helminginn, sem við erum hér. Vinstri helmingur þess sem hægri helming, og nú vinstri helminginn af vinstri helmingur þess hægri hluta, og hvernig get ég raða lista af stærð 1 sem inniheldur bara númer 1? Það er nú þegar gert. Hvernig á ég að gera það sama fyrir lista af stærð 1, sem inniheldur bara 7? Það er nú þegar gert. Skref þrjú fyrir þennan hálfleik þá er að sameina þessar tvær þættir í nýja lista af stærð 2, 1 og 7. Virðast ekki hafa gert allt það mikið áhugavert að vinna. Við skulum sjá hvað gerist næst. Ég flokkaður bara vinstri helming af þeim hægri helminginn af upprunalegu inntak mína. Nú skulum raða rétt helmingur, sem inniheldur 5 og 3. Við skulum aftur líta á vinstri helmingur, raðað, hægri helming, raðað, og sameinast þessir tveir saman, í sumum viðbótarrými, 3 kemur fyrst, þá kemur 5. Og svo nú höfum við raðað í vinstri helminginn af hægri hluta af upprunalegu vandamál, og hægri helminginn af hægri hluta af upprunalegu vandamálinu. Hvað er þriðja og síðasta skrefið? Vel að sameina þessa tvo helminga saman. Svo láta mig fá mér nokkrar auka rúm, en, aftur, ég gæti verið að nota þessi vara rúm upp efst. En við erum að fara að halda það einfalt sjónrænt. Leyfðu mér að sameinast í núna 1 og þá 3, og síðan 5, og síðan 7. Þar yfirgefa mig nú með hægri helminginn af upprunalegu vandamálinu það er fullkomlega raðað. Svo er það? Mér finnst eins og ég halda að segja að sömu hlutina aftur og aftur, en það er hugsandi af staðreynd að við erum að nota endurkvæmni. Ferlið við að nota An reiknirit aftur, og aftur, á smærri hlutmengja í upprunalega vandamálið. Svo ég nú hafa vinstri flokkuð helmingur af upprunalegu vandamálinu. Ég er með rétt flokkaður helmingur af upprunalegu vandamálinu. Hvað er þriðja og síðasta skrefið? Oh, það er samruna. Svo skulum gera það. Skulum úthluta sumir viðbótar minni, en guð minn, við gæti sett það hvar sem nú. Við höfum svo mikið pláss í boði að okkur, en við munum halda það einfalt. Í stað þess að fara til baka og fram með upprunalegu minni okkar, við skulum bara gera það sjónrænt hérna fyrir neðan, til að ljúka upp sameina vinstri helminginn og hægri helminginn. Svo með því að sameina, hvað þarf ég að gera? Ég vil taka þætti í röð. Svo að horfa á vinstri helming, Ég sé fyrsta talan er 2. Ég lít á hægri hluta, Ég sé fyrstu töluna er 1, svo augljóslega sem Fjöldi ég vil að slíta út, og setja fyrst í endanlegri listanum mínum? Að sjálfsögðu, 1. Nú vil ég að biðja um að sömu spurningu. Á vinstri hluta, ég hef enn fékk númer 2. Á hægri hluta, Ég hef fengið fjölda 3. Hver einn vil ég að velja? Auðvitað, númer 2 og nú eftir frambjóðendur eru 4 til vinstri, 3 til hægri. Skulum auðvitað velja 3. Nú frambjóðendur eru 4 á vinstri, 5 á hægri. Við, að sjálfsögðu, að velja 4. 6 á vinstri, 5 til hægri. Við, að sjálfsögðu, að velja 5. 6 á vinstri, 7 hægri. Við valið 6, og þá erum við velja 7, og þá erum við að velja 8. Voila. Svo a gríðarstór tala af orðum síðar, við hafa raðað þessum lista yfir átta þætti inn lista af eitt gegnum átta, sem er vaxandi með hverju skrefi, en hversu mikill tími fór það taka okkur að gera það. Jæja ég hef vísvitandi sem mælt er fyrir það út á myndrænan hér, svo að við getum konar sjá eða meta skiptingu í sigra sem hefur verið að gerast. Reyndar ef þú horfir aftur á kjölfar, Ég hef skilið allar þessar punktalínurnar í stað eigenda, þú getur, konar, skoða, í öfugri röð, ef þú lítur svona aftur í Saga nú, upprunalega listanum mínum er, að sjálfsögðu, af stærð 8. Og þá áður, ég var að takast á við tveir listar stærð 4, og þá fjórar skrár yfir stærð 2, og þá átta listar stærð 1. Svo hvað þýðir þetta, konar, minna þig á? Jæja, reyndar eitthvað af reiknirit sem við höfum horfði á svona langt þar sem við skipta, og skipta, og skipta, halda að hafa hlutina aftur og aftur, leiðir í þessu almenna hugmynd. Og svo er það eitthvað lógaritmískum gerast hér. Og það er ekki alveg log n, en það er Logarythmiskur hluti að það sem við höfum bara gert. Nú skulum íhuga hvernig það í raun er. Svo log n, aftur var mikill hlaupandi tíma, þegar við gerðum eitthvað eins Tvíundarleit, eins og við nú kalla það, deilum og sigra stefnu um sem við fundum Mike Smith. Nú tæknilega. Það er Log stöð 2 af N, jafnvel þó í flestum stærðfræði bekkjum, 10 er yfirleitt grunn sem þú tekur. En tölva vísindamenn næstum alltaf hugsa og tala í skilmálar af grunn 2, þannig að við yfirleitt bara segja þig inn á n, í stað þess að log undirstaða 2 af N, en þeir eru nákvæmlega eitt og sama í heimi tölva vísindi, og eins og innskot, það er stöðug þáttur munur á milli tveggja, svo það er moot engu að síður, til að fá meiri formlega ástæðum. En nú, hvað við umönnun um er þetta dæmi. Svo skulum ekki sannað með fordæmi, en á kosti nota dæmi um tölur hendi sem andleg heilbrigði stöðva, ef þú vilt. Svo áður uppskrift var Log stöð 2 n, en það er n í þessu tilfelli. Ég hafði n upprunalega tölur, eða 8 af upprunalega númerið sérstaklega. Nú það hefur verið smá meðan, en ég er nokkuð viss um að skrá þig inn stöð 2 af verðmæti 8 er 3, og reyndar hvað er gott um það er að 3 er einmitt sá fjöldi skipta að þú getur deilt lista lengd 8 aftur og aftur, og aftur, þar til þú ert vinstri með lista af aðeins stærð 1. Ekki satt? 8 fer til 4, fer í 2, fer til 1, og það er hugsandi um nákvæmlega sem mynd sem við höfðum bara í smá stund síðan. Svo smá geðheilsan stöðva um hvar lógariþmi er í raun að ræða. Svo nú, hvað er að ræða hér? n. Svo eftir að hver þegar ég skipt á listanum, að vísu í öfugri röð í sögu hér, ég var enn að gera n hlutina. Sem sameina skref þarf að Ég snerti hver og einn af tölum, í því skyni að renna henni í viðeigandi stað. Svo jafnvel þótt hæð þessu skýringarmynd af stærð log n n eða 3, sérstaklega, með öðrum orðum, Ég gerði þrjú svið hér. Hversu mikið verk gerði ég lárétt eftir þessari töflu í hvert skipti? Jæja, ég gerði n þrep vinna, vegna þess að ef ég hef fékk fjóra þætti og fjóra þætti, og ég þarf að sameina þá saman. Ég þarf að fara í gegnum þessir fjórir og þessir fjórir, að lokum að sameina þá aftur í átta þáttum. Ef öfugt ég hef fengið átta fingur hérna, sem ég er ekki, og átta fingers-- sorry-- Ef ég hef fékk fjóra fingur hérna, sem ég, fjórir fingur hérna, sem ég geri, þá er það sama dæmi eins og áður, ef ég geri hafa átta fingur þó í alls, sem ég get, svona, gera. Ég er einmitt að gera hér, þá get ég örugglega Sameina öll af þessum listum af stærð 1 saman. En ég hef vissulega að líta á hverju frumefni nákvæmlega einu sinni. Svo er hæð þessa ferlis log n, breidd þessu ferli, svo að segja, er n, svo hvað við virðumst að hafa, að lokum er a hlaupandi tími stærð n sinnum log n. Með öðrum orðum, skipt við listi, Log n sinnum, en í hvert sinn sem við gerðum það, við höfðum að snerta hver og einn af þeim þáttum í því skyni að sameina þá allt saman, sem var n skref, þannig að við höfum n sinnum log n, eða eins og a tölva vísindamaður myndi segja, slík-, sem væri stórt orð til að lýsa efri bundið á keyra tíma, við erum að keyra í stóru o log n tíma, svo að segja. Nú er þetta mikilvæg, því muna hvað gangi sinnum voru með kúla tagi, og val flokka, og innsetning tegund, og jafnvel fáir aðrir sem eru til, n veldi var þar sem við vorum á. Og þú getur, eins konar, sjá þetta hér. Ef n veldi er augljóslega n sinnum n, en hér höfum við n sinnum log n, og við vitum nú þegar frá viku núll, það log n, vegna lógaritmískrar, er betra en eitthvað línuleg. Eftir allt saman, muna myndina með rauða og gula og græna línur sem við Drew, sem grænt lógaritmískum lína var mun lægra. Og þess vegna, miklu betur og hraðar en beinar gulu og rauðu línanna, n sinnum log n er reyndar betra, en n sinnum N, eða n veldi. Þannig að við virðast hafa bent reiknirit sameinast tagi sem keyrir í miklu festa tíma, og örugglega, þess vegna, fyrr í þessari viku, þegar Við sáum að keppni milli kúla tegund, val flokka, og sameinast raða, mergesort virkilega, virkilega unnið. Og reyndar, við vissum ekki einu sinni að bíða fyrir kúla flokka og val tagi að klára. Nú skulum taka eitt annað skot á þessu, frá örlítið meira formleg sjónarmið, bara í ræða, þetta endurómar betur en að hærra stigi umræðu. Svo hér er reiknirit aftur. Við skulum spyrja okkur hvað hlaupandi tími er þetta reiknirit ýmsar ráðstafanir? Skulum skipta því í fyrsta málið og annað mál. The EF og annað í IF ræða, Ef n er minna en 2, bara aftur. Líður eins föstu tíma. Það er, eins konar, eins tveimur skrefum, Ef n er minna en 2, síðan aftur. En eins og ég sagði á mánudag, föstu tíma, eða stór eða 1, getur verið tvö skref, þrjú skref, jafnvel 1.000 skrefum. Það sem skiptir máli er að það sé stöðug tala af skrefum. Svo gula hápunktur sauðakóðanum hér liggur í, við munum kalla það, fasti tími. Svo fleiri formlega og við erum að fara to-- þetta verður að hve miklu leyti við formlega þennan rétt now-- T frá n, gangi tími vandamál sem tekur n somethings sem inntak, jafngildir stór eða einn, Ef n er minna en 2 pm. Svo það er skilyrt á það. Svo til að vera skýr, ef n er minna en 2, við höfum mjög stuttan lista, þá gangi tíma, T af n, þar sem n er 1 eða 0, í þetta mjög sérstaka tilviki, það er bara að fara að vera stöðug tími. Það er að fara að taka einn stíga, tvö skref, hvað sem er. Það er ákveðinn fjölda af skrefum. Svo safaríkur hluti hlýtur að vera í hinn raunin í sauðakóðanum. The ELSE ræða. Raða eftir helmingur þætti, flokka rétt helmingur þætti, sameinast flokkuð helminga. Hversu langan tíma tekur hver af þeim skrefum taka? Jæja, ef keyra kominn tími til að raða n þætti er, við skulum kalla það mjög generically, T af N, þá flokka vinstri helmingur af þeim þáttum er góður af eins og að segja, T n deilt með 2, og álíka flokka rétt helminginn þætti er góður af eins og að segja, T af N skipt 2, og þá sameina flokkuð helminga. Jæja ef ég hef fengið nokkrar Fjöldi staka hér, eins fjögur og sumir tala þætti hér, eins og fjórir, og ég verð að sameinast hvert af þessum fjórum í, og hver af þessum fjórum í, einn á eftir öðrum, þannig að lokum Ég hef átta þætti. Mér finnst eins og það er stór eða af n skrefum? Ef ég hef fengið n fingur og hvert þá þarf að sameinast í stað, það er eins og önnur n skrefum. Svo reyndar formulaically, við getum tjáð þetta, að vísu smá skelfing í fyrstu sýn, en það er eitthvað sem fangar einmitt þessi rökfræði. Keyrslutíminn, T af N, að ef n er meiri en eða jafnt og 2. Í þessu tilviki, að annað tilfelli, er T n deilt með 2, auk T af N deilt með 2, auk stór O af N, sum línuleg tala af skrefum, kannski einmitt n, kannski 2 sinnum n, en það er um það bil, til n. Svo það líka er, hvernig við getum tjá þetta formulaically. Nú þú vildi ekki vita þetta nema þú hefur skráð það í huga þínum, eða líta upp í aftur á kennslubók, sem gæti hafa smá Cheat Sheet á enda, en þetta er reyndar að fara að gefa okkur a stór eða af n log n, vegna þess að endurkoma sem þú sérð hér á skjánum, ef þú gerðir í raun það út, með óendanlega mörg dæmi, eða þú gerðir það formulaically, þú myndir sjá að þetta, því þetta formúlu sjálft er endurkvæma, með t af n yfir eitthvað hægra megin, og t n yfir á vinstri, þetta getur í raun verið lýst, að lokum, eins stór fara af n log n. Ef ekki sannfærður, það er fínt fyrir nú, bara taka á trú, að það er, örugglega, hvað það endurkomu leiðir til, en þetta er bara aðeins meira af a stærðfræði nálgun til að leita á gangi þegar mergesort miðað sauðakóðanum þess einn. Nú skulum taka a hluti af a breather frá allt að, og taka a líta á a víst fyrrverandi öldungadeildarþingmaður, sem getur litið svolítið þekki, sem settist niður með Eiríki Google Schmidt, fyrir nokkru, fyrir viðtal á sviðinu, fyrir framan a heild búnt af fólki, tala á endanum um umræða, það er nokkuð núna þekki. Við skulum taka a líta. Eric Schmidt: Nú Senator, þú ert hér á Google, og ég eins og til hugsa af formennsku sem atvinnuviðtal. Nú er erfitt að fá vinnu sem forseti. PRESIDENT OBAMA: Hægri. Eric Schmidt: Og þú ert fara að gera [inaudible] nú. Það er líka erfitt að fá vinnu á Google. PRESIDENT OBAMA: Hægri. Eric Schmidt: Við hafa spurningar, og við biðjum frambjóðendur spurningum okkar, og þetta er frá Larry Schwimmer. PRESIDENT OBAMA: OK. Eric Schmidt: Hvað? Þú krakkar hugsa ég grínast? Það er hérna. Hvað er skilvirkasta leiðin til að raða milljón 32 bita heiltölur? PRESIDENT OBAMA: Well-- Eric Schmidt: Stundum, kannski Fyrirgefðu, maybe-- Obama forseti: Nei, nei, nei, nei, nei, think-- I Eric Schmidt: Það er ekki it-- PRESIDENT OBAMA: I held, ég held kúla raða væri röng leið til að fara. Eric Schmidt: Komdu. Hver sagði honum þetta? OK. Ég gerði ekki tölvunarfræði on-- PRESIDENT OBAMA: Við höfum fékk njósnara okkar í það. Prófessor: Allt í lagi. Við skulum fara á bak okkur nú fræðilega heim reiknirita í aðfelluþrýstingi greiningu þeirra, og aftur sumum efni frá viku núll og einn, og í byrjun að fjarlægja nokkur þjálfun hjól, ef þú vilt. Svo að þú skiljir virkilega lokum frá grunni, það er fara á undir hetta, þegar þér skrifa, safna saman og keyrt forrit. Muna einkum að þetta var fyrsta C program við skoðuðum, Canonical, einfalt forrit konar, tiltölulega séð, þar sem, það prentar, Hello World. Og muna að ég sagði, að þetta ferli að kóðinn fer í gegnum er nákvæmlega þetta. Þú tekur kóðann þinn, fara það í gegnum þýðanda, eins Clang, og út kemur mótmæla kóða, sem gæti litið svona út, núll og sjálfur að CPU í tölvunni, Mið vinnslu eining eða heila, lokum skilur. Það kemur í ljós að það er hluti af einföldun, að við erum nú í stöðu til að stríða í sundur að skilja hvað er í raun verið fara á undir hetta hvert skipti sem þú keyrir Clang, eða oftast hvert skipti sem þú gerir áætlun, nota Gera og CF 50 IDE. Einkum, efni eins þetta er fyrsta mynda, Þegar þú saman fyrst program. Með öðrum orðum, þegar þú taka kóðann þinn og þýða það, hvað er fyrsta að outputted með Clang er eitthvað þekktur sem samkoma kóða. Og í raun, það lítur út nákvæmlega eins og þetta. Ég rak stjórn á the stjórn lína fyrr. Clang DASH höfuðborgarsvæðisins hello.c, og þetta skapaði skrá fyrir mig heitir hello.s, inni sem var nákvæmlega þessi innihald og aðeins meira ofan og aðeins meira neðan, en ég hef sett juiciest upplýsingar hér á skjánum. Og ef þú lítur vel, munt þú sjá að minnsta kosti nokkur kunnugleg leitarorð. Við höfum helsta efst. Við höfum printf niður í miðju. Og við höfum líka halló heimur sviga n í gæsalöppum þarna fyrir neðan. Og allt annað hér er mjög lágt leiðbeiningar að CPU the tölva 'skilur. CPU leiðbeiningar sem færa minni um, að hlaða strengir frá minni, og að lokum, prenta sem er á skjánum. Nú gerist það þó eftir þetta samkoma kóða er mynda? Lokum, þú, örugglega, enn búa mótmæla kóða. En þau skref sem hafa í raun verið að fara á undir hetta líta aðeins meira eins og þetta. Kóðinn verður samkoma númer, sem þá verður mótmæla kóða, og aðgerðir orð hér eru að Þegar þú saman kóðann þinn, út kemur samkoma kóða, og þá þegar þú saman samkoma númerið þitt, út kemur mótmæla kóða. Nú er Clang frábær háþróuð, eins mikið af vistþýðendur, og það er öllum þessum skrefum saman, og það er ekki endilega framleiðsla allir millistig skrár sem þú getur jafnvel sjá. Það safnar bara hlutina, sem er almennt hugtak sem lýsir þessu öllu ferlinu. En ef þú vilt virkilega að vera sérstaklega, það er mikið meira að fara á það eins og heilbrigður. En við skulum íhuga nú einnig að jafnvel sem frábær einfalt forrit, hello.c, kallað virka. Það heitir printf. En ég hafði ekki skrifað printf, örugglega, sem kemur með c, svo að segja. Það er aðgerð muna það er lýst í venjulegu io.h, sem er haus skrá, sem er umræða sem við munum í raun kafa í meira dýpi áður en langur. En haus skrá er yfirleitt í fylgd með kóða skrá, kóðinn skrá, svo mikið eins og það er til staðlað io.h. Einhvern síðan, einhver, eða einhvers, skrifaði einnig skrá sem heitir staðall io.c, í sem í raun skilgreiningar, eða útfærslur printf, og bunches annarra aðgerðir, eru í raun skrifuð. Svo í ljósi þess, ef við teljum með hér á vinstri, hello.c, að þegar saman, gefur okkur hello.s, jafnvel þótt Clang ekki trufla sparnaður í stað við getum séð það, og að samkoma kóða fær saman í hello.o, sem er reyndar sjálfgefið nafn gefið þegar þú saman uppspretta kóða í hlut kóða, en eru ekki alveg tilbúin að framkvæma það enn, því eitt skref þarf að gerast, og hefur verið að gerast undanfarin vikur, kannski Unbeknownst þig. Sérstaklega einhversstaðar í CS50 IDE, og þetta, of, verður hluti af óákveðinn greinir í ensku einföldun um stund, það er, eða var á þeim tíma, skrá sem heitir staðall io.c, að einhver unnin í staðall io.s eða sem nemur, að einhver svo saman í venjulegu io.o, eða það kemur í ljós í a örlítið öðruvísi skrá snið sem geta haft mismunandi skrá eftirnafn öllu leyti, en í orði og eðli, nákvæmlega þeir stíga þurfti að gerast í einhverri mynd. Sem er að segja, að nú þegar ég er að skrifa forrit, hello.c, sem bara segir, halló heimur, og ég er að nota kóðann einhvers annars eins printf, sem var einu sinni á tími, í skrá sem kallast staðall io.c, þá einhvern veginn verð ég að taka minn mótmæla kóða, núll mínir og sjálfur, og hlut sem viðkomandi númeri, eða núll og sjálfur, og einhvern veginn tengja þá saman í Eitt síðasta skrá, sem heitir halló, sem hefur alla núll og sjálfur frá meginvirkni minn, og öllum núllum og sjálfur fyrir printf. Og reyndar, að síðustu ferli er kallað, tengir mótmæla kóðann þinn. Framleiðsla sem er executable skrá. Svo í sanngirni, á lok dagsins, ekkert hefur breyst síðan viku eitt, þegar við byrjaði fyrst að setja saman áætlanir. Reyndar, allt þetta hefur verið gerast undir hetta, en nú erum við í aðstöðu þar sem við getum í raun stríða í sundur þessar mismunandi skrefum. Og reyndar, í lok dagsins, við erum enn vinstri með núll og sjálfur, sem er í raun frábær segue nú til annars getu C, að við höfum ekki þurft að nýta líklegast hingað til, þekktur sem Bita rekstraraðila. Með öðrum orðum, svona langt, hvenær sem við höfum fjallað gögnum í C eða breytur í C, við höfum haft það eins stafir og flýtur og ins og þráir og tveggja manna og þess háttar, en Allir sem eru að minnsta kosti átta bitar. Við höfum aldrei tekist að vinna einstaka bita, jafnvel þótt einstaka hluti, við veist, getur táknað 0 og 1. Nú kemur í ljós að í C, þú Hægt er að fá aðgang að einstökum bitum, ef þú veist setningafræði, sem að fá á þá. Svo skulum taka a líta á Bita rekstraraðila. Svo á myndinni hér eru nokkur tákn sem við höfum, eins konar, eins konar, séð áður. Ég sé merkið, lóðrétt Bar, og sumir aðrir sem vel, og muna að merkið merkið er eitthvað sem við höfum séð áður. Rökrétt AND, þar sem þú þarft tveir þeirra saman, eða rökrétt OR rekstraraðila, þar sem þú hafa tvö lóðrétt bars. Bita rekstraraðila, sem við munum sjá starfa á bita fyrir sig, bara að nota einn merkið, a einn lóðrétt strik, sem bendillinn tákn kemur næst, litla tilda, og síðan til vinstri krappi vinstri krappi, eða hægri hornklofi hægri hornklofi. Hvert þessara hafa mismunandi merkingu. Í raun, við skulum taka a líta. Við skulum fara gamla skóla í dag, og nota a snerta skjár frá fyrra, þekktur sem hvítt borð. Og þetta tússtöflu er að fara að leyfa okkur að tjá nokkrar nokkuð einföld tákn, eða öllu heldur sumir nokkuð einföld uppskrift, að við getum þá á endanum skiptimynt, í því skyni til að fá aðgang einstaklingur bitar innan C program. Með öðrum orðum, við skulum gera þetta. Fyrsta tala skulum fyrir a stund um merkið, sem er Bita AND. Með öðrum orðum, þetta er rekstraraðili sem gerir mig að hafa vinstri-hönd breytu Venjulega, og hægri handar breytu, eða einstaklingur gildi, að ef við AND þá saman, gefur mér endanlega niðurstöðu. Svo hvað ég meina? Ef í forriti, þú þarft breytu sem geymir einn af þessum gildum, eða við skulum halda það einfalt, og bara skrifa út núll og sjálfur sig, hér er hvernig merkið rekstraraðila virkar. 0 merkið 0 er að fara að jafna 0. Nú er ástæðan fyrir því? Það er mjög svipað Boolean tjáning, sem við höfum rætt svona langt. Ef þú heldur að eftir allt, 0 er rangar, 0 er ósatt, falskur og falskur er, eins og við höfum rætt rökrétt, einnig rangar. Þannig að við fáum 0 hér eins og heilbrigður. Ef þú tekur 0 merkið 1, vel það líka, er að fara að vera 0, því að til þess vinstri hönd tjáning til að vera satt eða 1, það þyrfti að vera satt og rétt. En hér höfum við rangar og satt, eða 0 og 1. Nú aftur: Ef við höfum 1 merkið 0, það líka, er að fara að vera 0, og ef við höfum 1 merkið 1, loksins höfum við í 1 hluti. Svo í öðrum orðum, við erum ekki að gera eitthvað áhugavert við þetta rekstraraðila bara enn, þetta merkið rekstraraðila. Það er Bita AND. En þetta eru innihaldsefni um sem við getum gert áhugavert, eins og við munum sjá fljótlega. Nú skulum líta á bara einn lóðrétt strik hérna til hægri. Ef ég er með 0 hluti og ég OR það með, Bita OR rekstraraðila, annar 0 hluti, það er að fara að gefa mér 0. Ef ég tek í 0 hluti og eða það með 1 hluti, þá er ég að fara að fá 1. Og í raun, bara til skýrleika, láta mig fara aftur, þannig að lóðrétt barir mínir eru ekki skakkur fyrir 1 er. Leyfðu mér að umrita öll 1 mín er svolítið meira greinilega, svo að við sjáum næst, ef ég hafa a 1 eða 0, það er að fara til vera a 1, og ef ég er með 1 eða 1 sem, of, er að fara til vera a 1. Svo er hægt að sjá rökrétt að OR Rekstraraðili hegðar sér mjög öðruvísi. Þetta gefur mér 0 OR 0 gefur mér 0, en annan hvern samsetning gefur mér 1. Svo lengi sem ég hef eitt 1 á uppskrift, niðurstaðan er að fara að vera 1. Með því móti við og Rekstraraðili, merkið, ef ég hef tvær 1 er í jöfnu, ég fæ reyndar 1 út. Nú er það nokkur annar eins og þær eru vel. Einn af þeim er lítið annað að ræða. Svo láta mig fara á undan og eyða þetta til að losa upp pláss. Og við skulum taka a líta á the bendillinn tákn, fyrir aðeins augnablik. Þetta er yfirleitt eðli þú getur slegið á hljómborð halda Shift og þá einn af tölum topp Bandaríkjunum þinn hljómborð. Þannig að þetta er eingöngu OR rekstraraðila, einkarétt OR. Þannig að við sáum bara eða rekstraraðila. Þetta er eingöngu eða rekstraraðila. Hvað er í raun munurinn? Jæja við skulum líta bara á formúluna, og nota þetta sem hráefni lokum. 0 XOR 0. Ég ætla að segja er alltaf 0. Það er skilgreiningin á XOR. 0 XOR 1 er að fara að vera 1. 1 XOR 0 er að fara að vera 1, og 1 XOR 1 er að fara að vera? Rangt? Eða hægri? Ég veit það ekki. 0. Nú hvað er að gerast hér? Jæja hugsa um Nafn þessa rekstraraðila. Exclusive OR, svo sem nafn, svona bendir, svarið er bara að fara að vera 1 ef inntak eru einir, eingöngu öðruvísi. Svo hér inntak eru sama, þannig að framleiðsla er 0. Hér aðföngin eru sama, þannig að framleiðsla er 0. Hér eru útgangar eru mismunandi, þau eru einir, og svo að framleiðsla er 1. Svo það er mjög svipað og Og það er mjög svipuð, eða öllu heldur er það mjög svipað OR, en aðeins í sérstakri hátt. Þessi er ekki lengur 1, vegna þess að við höfum tvær 1 er, og ekki eingöngu, bara einn af þeim. Allt í lagi. Hvað um hina? Jæja tilda, á meðan er reyndar gott og einfalt, sem betur fer. Og þetta er unary rekstraraðila, sem þýðir það er beitt til aðeins einn inntak, einn operand, svo að segja. Ekki til vinstri og hægri. Með öðrum orðum, ef þú tekur Tilde af 0, svarið verður hið gagnstæða. Og ef þú tekur tilda af 1, Svarið verður hið gagnstæða. Svo er tilda rekstraraðila leið ávinnst aðeins, eða ósvífni aðeins frá 0 til 1, eða 1 til 0. Og það skilur okkur að lokum með aðeins tvo síðustu rekstraraðila, svokölluð vinstri Shift, og svokölluð hægri vakt rekstraraðila. Við skulum taka a líta á hvernig þeir vinna. Left Shift rekstraraðila, skrifað með tveimur horn sviga eins og þessi, starfar eins og hér segir. Ef inntak mín, eða operand minn, til vinstri breyting rekstraraðila er einfaldlega 1. Og ég segi þá tölva til vinstri vakt sem 1, segja sjö stöðum, niðurstaðan er eins og ég taka þessi 1 og færa það sjö stöðum á við vinstri, og við vanræksla, við erum að fara að gera ráð fyrir að pláss til hægri er að fara að vera bólstruð með núllum. Með öðrum orðum, 1 vinstri vakt 7 er að fara til að gefa mér að 1, fylgt eftir með 1, 2, 3, 4, 5, 6, 7 núll. Það á þann hátt, að það gerir þér kleift að taka fáeinum eins og 1, og greinilega gera það mikið miklu, miklu stærri á þennan hátt, en við erum í raun að fara að sjá meira snjall aðferðir fyrir það í staðinn, eins og heilbrigður, Allt í lagi. Það er það fyrir viku þrjú. Við munum sjá þig næst. Þetta var CS50. [TÓNLIST spila] Ræðumaður 1: Hann var á snarl bar borða heitan Fudge sundae. Hann hafði það allt yfir andlit hans. Hann er þreytandi að súkkulaði eins skegg Ræðumaður 2: Hvað ert þú að gera? Ræðumaður 3: Hmmm? Hvað? Ræðumaður 2: Vissir þú réttlátur tvöfaldur dýfa? Þú dýfði tvöfalt flís. Ræðumaður 3: Afsakaðu. Ræðumaður 2: Þú dýfði flís, þú tók bita, og þú dýfði aftur. Ræðumaður 3: Ræðumaður 2: Svo það er eins og að setja allt munninn rétt dýfa. Næst þegar þú tekur flís, bara dýfa einu sinni, og enda það. Ræðumaður 3: Þú veist hvað, Dan? Þú dýfa leið sem þú vilt að dýfa. Ég dýfa hvernig sem ég vil að dýfa.