[Muzikos grojimo] 

PROFESORIUS: Visos deÅ¡inÄ. Tai yra, ir tai yra CS50 savaitÄ nuo trijÅ³ pabaigos. Taigi mes Äia Å¡iandien, o ne Sanders Teatras, o ne Ä¯ WEIDNER bibliotekoje. Kurio viduje yra studija Å¾inomas kaip Hauser Studio, arba sakome Studio H, arba mes say-- Jei jums patiko Å¡Ä¯ juokelÄ¯, tai tikrai iÅ¡ klasiokas, Å¾enklas, internete, kuris pasiÅ«lÄ kiek per "Twitter". Dabar kas kietas apie kad Äia studijoje yra tai, kad aÅ¡ apsupta tai Å¾alia sienos, Å¾alia ekranas arba chromakey, taip sakant, tai reiÅ¡kia, kad CS50 s gamybos komanda, neÅ¾inant mane dabar, gali bÅ«ti iÅ¡leisti man dauguma visame pasaulyje, geriau ar blogiau. 

Dabar, kas laukia priekyje, problema nustatyti du yra jÅ«sÅ³ rankose Å¡iÄ savaitÄ, bet su problema nustatyti tris Å¡iÅ³ metÅ³ savaitÄ Jums bus uÅ¾ginÄyti su vadinamasis Å¾aidimas 15 senas Å¡alis palankumÄ, kad jums gali prisiminti gavimo kaip vaikas, kad turi visa krÅ«va skaiÄiÅ³, kad gali skaidrÄ aukÅ¡tyn, Å¾emyn, kairÄ ir Ä¯ deÅ¡inÄ, ir ten vienas tarpas per galvosÅ«kÄ¯, Ä¯ kurÄ¯ iÅ¡ tikrÅ³jÅ³ galite skaidrÄ tuos Ä¯spÅ«dÄ¯. GalÅ³ gale jÅ«s gaunate tai dÄlionÄs kai pusiau atsitiktine tvarka, ir tikslas yra rÅ«Å¡iuoti, iÅ¡ virÅ¡aus Ä¯ apaÄiÄ, kairÄs Ä¯ deÅ¡inÄ, iÅ¡ vienos visÄ keliÄ iki per 15. 

Deja, Ä¯gyvendinimas jÅ«s turÄsite po ranka bus programinÄ Ä¯ranga pagrindu, ne fiziÅ¡kai. JÅ«s iÅ¡ tikrÅ³jÅ³ teks raÅ¡yti kodas, su kuriuo studentas arba vartotojas gali Å¾aisti 15 rungtynes. Ir iÅ¡ tikrÅ³jÅ³, hakeris leidimas Å¾aidimas 15 jums bus iÅ¡Å¡Å«kis Ä¯gyvendinti, ne tik Å io seno mokykloje vienodos Å¾aidimas, bet veikiau sprendimas jo, Ä¯gyvendinant Dievo reÅ¾imas, taip sakant, kad iÅ¡ tikrÅ³jÅ³ iÅ¡sprendÅ¾ia galvosÅ«kÄ¯ uÅ¾ Å¾mogaus, suteikiant jiems uÅ¾uomina, po uÅ¾uominÄ, po uÅ¾uominÄ. Taigi daugiau apie tai kitÄ savaitÄ. Bet tai, kas laukia priekyje. 

Nes dabar priminti, kad anksÄiau Å¡iÄ savaitÄ mes turÄjome Å¡Ä¯ Ä®spÅ«dingos filmÄ, jei norite, kuriuo geriausia, kÄ veikÄte rÅ«Å¡iavimas IÅ¡minÄius buvo virÅ¡utinÄ riba didelis O n kvadrato. Kitaip tariant, burbulas rÅ«Å¡iuoti, pasirinkimas rÅ«Å¡iuoti, Ä¯terpimo rÅ«Å¡iuoti, visi iÅ¡ jÅ³, tuo tarpu skirtingi jÅ³ Ä¯gyvendinimÄ, perduotos Ä¯ n kvadratu veikia Laikas labai blogiausiu atveju. Ir mes paprastai manome, kad labai blogiausiu atveju rÅ«Å¡iavimo yra vienas, kad jÅ«sÅ³ indÄlis yra visiÅ¡kai atgal. Ir iÅ¡ tiesÅ³, jis paÄmÄ nemaÅ¾ai priemoniÅ³, Ä¯gyvendinti kiekviena iÅ¡ Å¡iÅ³ algoritmo. 

Dabar paÄioje pabaigoje klasÄs Prisiminkite, mes palyginti burbulas rÅ«Å¡iuoti prieÅ¡ atrankos rÅ«Å¡iuoti prieÅ¡ vienÄ kitÄ kad mes vadinami suliejimo rÅ«Å¡iuoti tuo metu, ir siÅ«lau, kad tai atsiÅ¾velgiant privalumas nuo savaitÄs pamokÄ nulis, skaldyk ir valdyk. Ir kaÅ¾kaip pasiekti tam tikrÄ rÅ«Å¡Ä¯ logaritminÄ bÄganÄio laiko, galiausiai, vietoj kaÅ¾kÄ tai grynai kvadratinÄ. Ir tai ne visai logaritminÄ, tai Å¡iek tiek daugiau nei tai. Bet jei jÅ«s prisimenate iÅ¡ klasÄs, tai buvo daug, daug greiÄiau. Leiskite paÅ¾velgti, kur mes baigÄte iÅ¡vaizdÄ. 

Burbulas rÅ«Å¡iuoti, palyginti atrankos RÅ«Å¡iuoti palyginti merge rÅ«Å¡iuoti. Dabar jie visi veikia, yra teorija, tuo paÄiu metu. CPU veikia tuo paÄiu greiÄiu. Bet jÅ«s galite pajusti, kaip nuobodu tai labai greitai taps, ir tiesiog, kaip greitai, kai mes Å¡virkÅ¡ti visÄ savaitÄ Zero algoritmÅ³ tiek, mes galime pagreitinti. 

Taigi Å¾enklas RÅ«Å¡iuoti atrodo nuostabi. Kaip mes galime iÅ¡naudoti jÄ¯, kad greiÄiau rÅ«Å¡iuoti numerius. Na pagalvokime atgal komponentui, kad mes turÄjo grÄ¯Å¾ti Ä¯ nulinÄ savaitÄ, kad ieÅ¡koti kÄ nors Ä¯ telefonÅ³ knygÄ, ir priminti, kad Pseudocode, kad mes pasiÅ«lÄme, per kurÄ¯ mes galime rasti kaÅ¾kas panaÅ¡aus Mike Smith, atrodÄ Å¡iek tiek kaÅ¾kÄ panaÅ¡aus Ä¯ tai. 

Dabar imtis ypaÄ iÅ¡vaizdÄ eilutÄje 7 ir 8, ir 10 ir 11, kurios sukelia tÄ kilpÄ, kuriÄ mes nuolat grÄ¯Å¾ta Ä¯ linijÄ 3 vÄl, ir vÄl, ir vÄl. TaÄiau paaiÅ¡kÄja, kad mes galime pamatyti Å is algoritmas, Äia Pseudocode, Å¡iek tiek daugiau holistiÅ¡kai. TiesÄ sakant, tai, kÄ aÅ¡ ieÅ¡kote bent Äia ekrane, yra paieÅ¡kai algoritmas Mike Smith tarp kai kuriÅ³ puslapiÅ³ rinkiniu. Ir iÅ¡ tiesÅ³, mes galime supaprastinti Å¡Ä¯ algoritmas tose 7 ir 8 linijÅ³, ir 10 ir 11, tiesiog pasakyti, kad tai, kurios aÅ¡ Äia pateikiama geltonai. Kitaip tariant, jei Mike Smith anksÄiau knygoje, mums nereikia nurodyti Å¾ingsnis po Å¾ingsnio, dabar, kaip eiti jo rasti. Neturime nurodyti grÄ¯Å¾ti Ä¯ linijÄ 3 KodÄl ne mes tiesiog vietoj to, tarkim, apskritai, ieÅ¡koti Mike Ä¯ kairÄ pusÄ knygos. 

Ir atvirkÅ¡Äiai, jei Mike iÅ¡ tikrÅ³jÅ³ vÄliau knygoje, kodÄl ne mes tiesiog pacituoti citatos pabaiga paieÅ¡kÄ Mike deÅ¡inÄje pusÄje knygoje. Kitaip tariant, tai kodÄl gi ne mes tiesiog rÅ«Å¡iuoti punt sau sakydamas: ieÅ¡koti Mike Å¡iame poaibis knygos, ir palikite jÄ¯ Ä¯ mÅ«sÅ³ esamÅ³ algoritmas pasakykite mums Kaip ieÅ¡koti mike kad kairÄ pusÄ knygos. Kitaip tariant, mÅ«sÅ³ algoritmas veikia, ar tai telefono knyga tokio storio, tai storis, arba bet kokio storio kokia. Taigi, mes galime rekursyviai apibrÄÅ¾ti Å¡Ä¯ algoritmÄ. Kitaip tariant, dÄl ekranas Äia yra algoritmas paieÅ¡kai Mike Smith tarp telefono knygos puslapiuose. Taigi 7 ir 10 eilutÄ, tegul tiesiog pasakyti bÅ«tent tai. Ir aÅ¡ naudoju Å¡Ä¯ terminÄ akimirkai PrieÅ¡ ir iÅ¡ tiesÅ³, rekursija yra madingas terminas dabar, ir tai Å¡is procesas daro kaÅ¾kÄ cikliÅ¡ko iki kaÅ¾kaip naudojant kodÄ, kurÄ¯ jÅ«s jau turite, ir raginama jÄ¯ dar kartÄ, ir vÄl, ir vÄl. Dabar jis ketina bÅ«ti svarbi kad mes kaÅ¾kaip apaÄioje uÅ¾duotis, ir nereikia daryti, kad be galo ilgai. PrieÅ¡ingu atveju mes ketiname iÅ¡ tikrÅ³jÅ³ begalinis ciklas. Bet paÅ¾iÅ«rÄkime, ar mes galime skolintis Å¡iÄ idÄjÄ iÅ¡ rekursijos, daro kaÅ¾kÄ naujo ir vÄl, ir vÄl, sprÄsti rÅ«Å¡iavimo problema per suliejimo RÅ«Å¡iuoti, visi efektyviau. 

Taigi, aÅ¡ suteikti jums sujungti rÅ«Å¡iuoti. Leiskite paÅ¾velgti. Taigi Äia yra Pseudocode, su kuris galÄtume Ä¯gyvendinti rÅ«Å¡iavimo, naudojant Å¡Ä¯ algoritmÄ, pavadintÄ sujungti rÅ«Å¡iuoti. Ir tai paprasÄiausiai tai. Apie Ä¯vesties n elementÅ³, Kitaip tariant, jei esate suteikta n elementai ir numeriai bei laiÅ¡kus ar kokia Ä¯vestis, jei jums suteikta n elementÅ³, jei n yra maÅ¾iau nei 2, tiesiog grÄ¯Å¾ti. TeisÄ? Nes jei n yra maÅ¾iau nei 2, kad tai reiÅ¡kia, kad mano sÄraÅ¡as elementÅ³ yra arba dydÅ¾io 0 arba 1, ir tiek iÅ¡ tÅ³ nereikÅ¡mingÅ³ atvejÅ³, sÄraÅ¡as jau rÅ«Å¡iuojamos. Jei nÄra sÄraÅ¡e, tai rÅ«Å¡iuojamos. Ir jei ten ilgio sÄraÅ¡as 1, tai akivaizdÅ¾iai rÅ«Å¡iuojami. Taigi algoritmas turi tik tikrai padaryti kaÅ¾kÄ Ä¯domaus, jei mes turime du ar daugiau elementai mums duota. Taigi paÅ¾velkime Ä¯ magijos tada. Kita rÅ«Å¡iuoti kairÄ¯jÄ¯ pusÄ elementÅ³, tada rÅ«Å¡iuoti tinkamÄ pusÄ elementÅ³, tada sujungti surÅ«Å¡iuoti puses. Ir kas rÅ«Å¡ies proto lenkimo Äia yra, kad aÅ¡ tikrai ne Atrodo, kad jums sakiau, nieko nÄra, tiesa? Viskas, kÄ aÅ¡ sakiau yra, nes iÅ¡ sÄraÅ¡o n elementÅ³, rÅ«Å¡iuoti yra kairÄje pusÄje, tada Ä¯ deÅ¡inÄ pusÄ, tada sujungti rÅ«Å¡iuoti puses, Bet kur yra tikrasis slaptÄ padaÅ¾u? Kur yra algoritmas? Na paaiÅ¡kÄja, kad Å¡iÅ³ dviejÅ³ linijÅ³ Pirma, tarsi liko pusÄ elementÅ³, ir rÅ«Å¡iuoti teisÄ pusÄ elementÅ³, yra pasikartojantys skambuÄiai, taip sakant. 

GalÅ³ gale, ne tai momentas, turiu algoritmas, su kuria rÅ«Å¡iuoti visa krÅ«va elementÅ³? Taip. Tai Äia. Tai Äia ekrane ir todÄl galiu naudoti tÄ patÄ¯ rinkinÄ¯ Å¾ingsniÅ³ rÅ«Å¡iuoti yra kairÄje pusÄje, kaip aÅ¡ galiu teisÄ pusÄ. Ir iÅ¡ tiesÅ³, vÄl, ir vÄl. Taigi vienaip ar kitaip, ir mes netrukus pamatyti tai, apie merge rÅ«Å¡iuoti magija yra Ä¯dÄta, kad labai galutinis linija, sujungti surÅ«Å¡iuoti puses. Ir tai atrodo gana intuityvus. JÅ«s imtis dvi dalis, ir jÅ«s, kaÅ¾kaip, sujungti juos kartu, ir mes pamatyti, tai konkreÄiai per akimirkÄ. 

TaÄiau tai yra pilnas algoritmas. Ir paÅ¾iÅ«rÄkime tiksliai, kodÄl. Na manau, kad mes AtsiÅ¾velgiant Ä¯ Å¡iuos pats aÅ¡tuonios Äia elementus ekrane, vienas per aÅ¡tuoniÅ³, bet jie iÅ¡ paÅ¾iÅ«ros atsitiktine tvarka. Ir po ranka tikslas rÅ«Å¡iuoti Å¡iuos elementus. Na kaip aÅ¡ galiu eiti apie daro jÄ¯ naudoti, vÄlgi, sujungti rÅ«Å¡iuoti, kaip uÅ¾ Å¡io Pseudocode? Ir vÄl, Ä®sitvirtino tai jÅ«sÅ³ protas, nes tik akimirkÄ. Pirmasis atvejis yra gana trivialus, jei ji maÅ¾esnÄ kaip 2, tiesiog grÄ¯Å¾ti, nÄra nuveikti. Taigi tikrai ten tik trys Å¾ingsniÅ³, kad tikrai reikia nepamirÅ¡ti. VÄlgi, ir vÄl, aÅ¡ ketinate nori turÄti rÅ«Å¡iuoti yra kairÄje pusÄje, rÅ«Å¡iuoti tinkamÄ pusÄ, ir tada, kai jÅ³ dvi puselÄs yra rÅ«Å¡iuojami, Noriu sujungti juos kartu Ä¯ vienÄ rÅ«Å¡iuotÅ³ sÄraÅ¡Ä. Taigi keep that in mind. 

Taigi Äia originalus sÄraÅ¡Ä. Leiskite gydyti tai kaip masyvas, kaip mes pradÄjome dviejose savaitÄ, kuris yra ribotis blokas atminties. Å iuo atveju, kuriÅ³ sudÄtyje yra aÅ¡tuoni numeriai, atgal atgal Ä¯ nugarÄ. Ir tegul dabar taikomos suliejimo rÅ«Å¡iuoti. Taigi aÅ¡ pirmÄ norite rÅ«Å¡iuoti kairÄ pusÄ Å¡io sÄraÅ¡o, Ir tegul, todÄl sutelkti dÄmesÄ¯ Ä¯ 4, 8, 6 ir 2. 

Dabar kaip man eiti apie rÅ«Å¡iavimas nuo dydÅ¾io 4 sÄraÅ¡Ä? Na aÅ¡ turiu dabar mano rÅ«Å¡iavimas kairiojo pusmetÄ¯ kairÄje. VÄlgi, galime atsukti tik uÅ¾ akimirkÄ. Jei Pseudocode tai, ir aÅ¡ suteiktas aÅ¡tuoniÅ³ elementÅ³, 8 yra akivaizdÅ¾iai didesnis nei arba lygus 2. Taigi su pirmas atvejis netaikomas. Taigi rÅ«Å¡iuoti aÅ¡tuonis elementus, aÅ¡ pirmÄ kartÄ rÅ«Å¡iuoti kairÄ¯jÄ¯ pusÄ elementÅ³, tada aÅ¡ rÅ«Å¡iuoti tinkamÄ pusÄ, tada aÅ¡ sujungti du rÅ«Å¡iuotos pusÄs, kiekvienas iÅ¡ dydis 4. GERAI. 

Bet jei jÅ«s tiesiog man pasakÄ, rÅ«Å¡iuoti kairÄje pusÄje,, kuris yra dabar dydÅ¾io 4, Kaip rÅ«Å¡iuoti kairÄ¯jÄ¯ pusÄ? Na, jei aÅ¡ turÄti Ä¯Äjimas iÅ¡ keturiÅ³ elementÅ³, AÅ¡ rikiuoti Ä¯ kairÄ du, tada deÅ¡iniuoju du, ir tada aÅ¡ juos sujungti kartu. Taigi dar kartÄ, ji tampa Å¡iek tiek iÅ¡ proto lenkimo Å¾aidimÄ Äia nes jÅ«s, tipo, turi prisiminti, kur jÅ«s esate Ä¯ istorijÄ, bet tuo dienos pabaigoje, suteiktas joks elementÅ³ skaiÄiÅ³, pirmiausia noriu rÅ«Å¡iuoti kairÄ pusÄ, tada Ä¯ deÅ¡inÄ pusÄ, tada sujungti juos kartu. PradÄkime daryti bÅ«tent tai. Å tai aÅ¡tuoni elementÅ³ Ä¯vestis. Dabar mes ieÅ¡kome kairÄje pusÄje Äia. Kaip rÅ«Å¡iuoti keturis elementus? Na aÅ¡ rikiuoti yra kairÄje pusÄje. Dabar kaip man sutvarkyti kairÄ¯jÄ¯ pusÄ? Na aÅ¡ buvo suteikta du elementus. Taigi leiskite surÅ«Å¡iuoti Å¡iÅ³ dviejÅ³ elementÅ³. 2 yra didesnis arba lygus 2, Å¾inoma. Taigi, kad pirmas atvejis netaikomas. 

Taigi dabar aÅ¡ turiu rÅ«Å¡iuoti Ä¯ kairÄ pusÄ Å¡iÅ³ dviejÅ³ elementÅ³. KairÄje pusÄ, Å¾inoma, yra tik 4. Taigi, kaip man sutvarkyti iÅ¡ vieno elemento sÄraÅ¡Ä? Na, dabar, kad ypatingas bazinÄ¯ scenarijÅ³ iki virÅ¡aus, taip sakant, taikoma. 1 yra maÅ¾iau nei 2, ir savo sÄraÅ¡as yra iÅ¡ tiesÅ³ dydÅ¾io 1 d. Taigi aÅ¡ tiesiog grÄ¯Å¾ti. AÅ¡ nieko negaliu daryti. Ir iÅ¡ tiesÅ³, paÅ¾velgti, kÄ aÅ¡ padaryta, 4 jau rÅ«Å¡iuojamos. Kaip jau esu dalinai sÄkmingas Äia. 

Dabar, atrodo rÅ«Å¡ies kvailas reikalauti, bet tai tiesa. 4 yra 1 dydÅ¾io sÄraÅ¡as. Tai jau rÅ«Å¡iuojamos. Å tai kairÄ pusÄ. Dabar aÅ¡ rÅ«Å¡iuoti tinkamÄ pusÄ. Mano indÄlis yra vienas elementas, 8 Be to, jau rÅ«Å¡iuojamos. Kvailas, taip pat, taÄiau ir vÄl, Å is pagrindinis principas ketina leisti mums dabar statyti ant sÄkmingai tai. 4 rÅ«Å¡iuojamos, 8 rÅ«Å¡iuojamos, o dabar kas buvo, kad paskutinis Å¾ingsnis? Taigi, treÄiasis ir paskutinis Å¾ingsnis, bet kokia kartÄ jÅ«s rÅ«Å¡iavimo sÄraÅ¡as, prisiminti, buvo sujungti dvi puses, kairÄje ir deÅ¡inÄje. Taigi darykime bÅ«tent tai. Mano kairÄ pusÄ, Å¾inoma, 4. Mano teisÄ pusÄ yra 8. 

Taigi leiskite tai padaryti. Pirmiausia aÅ¡ ruoÅ¡iuosi skirti Kai kurios papildomos atminties, kad aÅ¡ atstovauti Äia kaip tik antrinis masyvas, tai pakankamai didelis, kad tilptÅ³ tai. Bet jÅ«s galite Ä¯sivaizduoti, iÅ¡pleÄiant kad staÄiakampis visas ilgis, jei mums reikia daugiau vÄliau. Kaip man imtis 4 ir 8, ir sujungti Å¡ie du sÄraÅ¡ai dydis 1 kartu? Äia taip pat gana paprasta. 4 ateina pirmas, tada ateina 8. Nes jei aÅ¡ noriu rÅ«Å¡iuoti kairÄ pusÄ, tada Ä¯ deÅ¡inÄ pusÄ, ir tada sujungti Å¡ias dvi puses kartu, iÅ¡rÅ«Å¡iuotÅ³ tam, 4 ateina pirmas, tada ateina 8. 

Taigi, mes, atrodo, daro paÅ¾angÄ, net nors aÅ¡ nepadariau jokio faktinio darbÄ. Bet atsiminkite, kur mes esame Ä¯ istorijÄ. Mes iÅ¡ pradÅ¾iÅ³ priÄmÄ aÅ¡tuonis elementus. Mes rÅ«Å¡iuojami kairÄ¯jÄ¯ pusÄ, kuri yra 4. Tada mes rÅ«Å¡iuojami kairÄ¯jÄ¯ pusÄ kairiojo pusÄje, kuri buvo 2. Ir Äia mes einame. Mes padaryti su tuo Å¾ingsnio. 

Taigi, jei mes surÅ«Å¡iuoti Ä¯ kairÄ pusÄ 2, dabar mes turi rÅ«Å¡iuoti tinkamÄ pusÄ 2. Taigi teisÄ pusÄ 2 Å¡iÅ³ dviejÅ³ verÄiÅ³ Äia, 6 ir 2. Tad dabar pats imtis iÅ¡ dydÅ¾io indÄlÄ¯ 2, ir rÅ«Å¡iuoti kairÄ¯jÄ¯ pusÄ, ir tada teisÄ pusÄ, ir tada sujungti juos kartu. Na kaip man sutvarkyti iÅ¡ dydÄ¯ sÄraÅ¡Ä 1, kuriÅ³ sudÄtyje yra tik skaiÄiÅ³ 6? AÅ¡ jau padaryta. Å is dydis 1 sÄraÅ¡as surÅ«Å¡iuotas. 

Kaip rÅ«Å¡iuoti kitÄ sÄraÅ¡Ä dydis 1, vadinamoji teisÄ pusÄ. Na tai irgi jau rÅ«Å¡iuojamos. SkaiÄius 2 yra vieni. Taigi dabar turiu dvi dalis, Ä¯ kairÄ ir Gerai, man reikia jas sujungti kartu. Leiskite man duoti sau Å¡iek tiek papildomos erdvÄs. Ir 2 Ä¯dÄti ten, tada 6 ten, taip rÅ«Å¡iavimas Å¡Ä¯ sÄraÅ¡Ä, Ä¯ kairÄ ir Ä¯ deÅ¡inÄ, ir sujungiant jÄ¯ kartu, galiausiai. Taigi, aÅ¡ Å¡iek tiek geresnÄs formos. AÅ¡ ne padaryta, nes aiÅ¡kiai 4, 8, 2, 6 nÄra galutinÄ uÅ¾sakymas, kad aÅ¡ noriu. Bet dabar aÅ¡ turiu du sÄraÅ¡us 2 dydÅ¾io, kad tiek, atitinkamai, rÅ«Å¡iuojami. Taigi dabar, jei atsukti savo proto akiÅ³, kur gi, kad palieka mus? AÅ¡ pradÄjau su aÅ¡tuoniÅ³ elementÅ³, tada aÅ¡ sutrumpino jÄ¯ Å¾emyn Ä¯ kairÄ pusÄ 4, tada kairÄje pusÄje, 2, ir tada Ä¯ deÅ¡inÄ pusÄ 2, AÅ¡ baigiau todÄl, rÅ«Å¡iavimas Ä¯ kairÄ pusÄ 2, ir teisÄ pusÄ 2, Taigi, kas yra treÄiasis ir paskutinis Å¾ingsnis Äia? Turiu sujungti kartu du sÄraÅ¡us 2 dydÅ¾io. Taigi eikime Ä¯ priekÄ¯. Ir ekrane Äia paraÅ¡Äs man kai papildoma atmintis, nors techniÅ¡kai, pastebÄsite, kad aÅ¡ turiu visa krÅ«va tuÅ¡Äioje vietoje iki virÅ¡aus ten. Jei aÅ¡ noriu bÅ«ti ypaÄ efektyvus plotas iÅ¡mintingi, GalÄÄiau tik pradÄti judÄti elementai pirmyn ir atgal, virÅ¡uje ir apaÄioje. Bet tik vizualiai aiÅ¡kumo, AÅ¡ ruoÅ¡iuosi Ä¯dÄti jÄ¯ Å¾emyn Å¾emiau, iÅ¡laikyti dalykÅ³ graÅ¾us ir Å¡varus. 

Taigi aÅ¡ turiu du sÄraÅ¡us 2 dydÅ¾io. Pirmasis sÄraÅ¡e yra 4 ir 8. Antrasis sÄraÅ¡e yra 2 ir 6. Leiskite sujungti tuos kartu rÅ«Å¡iuotÅ³ tvarka. 2, Å¾inoma, ateina pirma, tada 4, tada 6, tada 8. Ir dabar mes, atrodo, vis kaÅ¾kur Ä¯domu. Dabar aÅ¡ rÅ«Å¡iuojami pusÄ sÄraÅ¡Ä ir atsitiktinai, tai visi net numeriai, bet yra, tiesÄ sakant, tik sutapimas. Ir dabar aÅ¡ turiu rÅ«Å¡iuojami Ä¯ kairÄ pusÄ, taip, kad ji yra 2, 4, 6, ir 8. Nieko tai iÅ¡ eilÄs. Tai jauÄiasi paÅ¾angÄ. 

Dabar jis jauÄiasi aÅ¡ buvo kalbama amÅ¾inai dabar Taigi, kas dar turi bÅ«ti perÅ¾iÅ«rÄta, jei tai algoritmas yra, iÅ¡ tiesÅ³, efektyviau. Bet mes iÅ¡gyvena super metodiÅ¡kai. Kompiuteris, Å¾inoma, norÄÄiau tai padaryti, kaip kad. Taigi, kur mes esame? Mes pradÄjome su aÅ¡tuoniÅ³ elementÅ³. AÅ¡ rÅ«Å¡iuojami kairÄje pusÄje, 4. Man atrodo, kad reikia padaryti, kad. Taigi, dabar kitas Å¾ingsnis yra rÅ«Å¡iuoti tinkamÄ pusÄ 4. Ir Å¡i dalis mes galime eiti per Å¡iek tiek daugiau greitai, nors esate Sveiki atsukti arba sustabdyti, tiesiog manau, per jÄ¯ savo tempu, bet kÄ mes turime dabar yra galimybÄ padaryti tÄ patÄ¯ algoritmÄ keturiais su skirtingais numeriais. 

Taigi eikime Ä¯ priekÄ¯, ir sutelkti dÄmesÄ¯ Ä¯ teisÄ pusÄ, kuriÄ mes Äia. KairÄje pusÄje, kad teisÄ pusÄ, o dabar kairÄje pusÄje, kairÄje pusÄ Å¡ios teisÄs pusÄ, ir kaip man sutvarkyti iÅ¡ dydÄ¯ sÄraÅ¡Ä 1, kuriame yra tik 1 numeriu? Tai jau padaryta. Kaip aÅ¡ galiu padaryti dÄl sÄraÅ¡o pats dydÅ¾io 1, kuriame yra tik 7? Tai jau padaryta. TreÄias Å¾ingsnis Å¡iam pusÄ tada yra sujungti Å¡iuos du elementus Ä¯ naujÄ sÄraÅ¡o 2 dydÅ¾io, 1 ir 7. Ar neatrodo, kad padarÄme viskÄ kad daug Ä¯domus darbas. PaÅ¾iÅ«rÄkime, kas vyksta Å¡alia. AÅ¡ tik sutvarkyti kairÄ¯jÄ¯ pusÄ teisÄ pusÄ mano originalus indÄlis. Dabar galime rÅ«Å¡iuoti teisÄ pusÄ, kuri yra 5 ir 3. Leiskite dar kartÄ paÅ¾velgti Ä¯ kairÄ pusÄ, rÅ«Å¡iuojami, teisÄ pusÄ, rÅ«Å¡iuojami, ir sujungti tuos du kartu, Ä¯ tam tikrÄ papildomÄ erdvÄ, 3 ateina pirmas, tada ateina 5. Ir todÄl dabar, mes surÅ«Å¡iuoti kairÄje pusÄje, deÅ¡inÄs pusÄje pirminio problemÄ, ir teisÄ pusÄ deÅ¡inÄs pusÄje pirminio problemÄ. Kas treÄias ir paskutinis Å¾ingsnis? Na sujungti Å¡ias dvi puses kartu. Taigi leiskite man gauti sau kai papildomos vietos, bet, vÄlgi, aÅ¡ gali bÅ«ti naudoti, kad atsarginÄ¯ kosmoso iki virÅ¡aus. TaÄiau mes ketiname iÅ¡laikyti paprasta vizualiai. Leiskite sujungti dabar 1 ir tada 3, ir tada 5, ir tada 7. Paliekant man dabar su teisÄ pusÄ originalo problemos kad manimi puikiai rÅ«Å¡iuojami. 

Taigi, kas lieka? AÅ¡ jauÄiuosi kaip aÅ¡ nuolat sakydamas, kad tie patys dalykai vÄl, ir vÄl, bet tai neparodo Faktas, kad mes naudojame rekursija. IÅ¡ naudojate procesas algoritmas vÄl, ir vÄl, maÅ¾esniÅ³ pogrupiÅ³ originalus problema. Taigi dabar aÅ¡ turiu iÅ¡ kairÄs rÅ«Å¡iuojami pusÄ pradinio problemÄ. Turiu teisÄ rÅ«Å¡iuotÄ pusÄ pirminio problemÄ. Kas treÄias ir paskutinis Å¾ingsnis? Oi, tai sujungti. Taigi leiskite tai padaryti. Leiskite skirti kai papildoma atminties, bet mano Dieve, mes gali jÄ¯ visur dabar. Mes turime tiek daug laisvos vietos pas mus, bet mes keep it simple. Vietoj grÄ¯Å¾ta ir atgal su mÅ«sÅ³ originalios atminties, tegul tiesiog padaryk tai vizualiai Å¾emyn Äia Å¾emiau, baigti iki apjungiant kairÄ pusÄ ir teisÄ pusÄ. 

Taigi sujungus, kÄ man reikia daryti? Noriu imtis elementus tvarka. Taigi Å¾iÅ«ri kairÄje pusÄje, Matau pirmas skaiÄius yra 2. Å½iÅ«riu deÅ¡inÄje pusÄje, I Å¾r pirmÄjÄ¯ skaiÄiÅ³ yra 1, taigi akivaizdu, kad, kuri TaÅ¡kÅ³ aÅ¡ noriu iÅ¡plÄÅ¡ti, ir Ä¯dÄti pirmasis mano galutinÄ¯ sÄraÅ¡Ä? Å½inoma, 1. Dabar aÅ¡ noriu papraÅ¡yti, kad tÄ patÄ¯ klausimÄ. KairÄje pusÄje, aÅ¡ vis dar turiu 2 numeriu. DeÅ¡inÄje pusÄje, AÅ¡ turiu 3 numeriu. Kuris aÅ¡ noriu pasirinkti? Å½inoma, numeris 2 dabar pastebÄti kandidatus yra 4 kairÄje, 3 deÅ¡inÄje. Leiskite, Å¾inoma, pasirinkti 3. Dabar kandidatai yra 4 dÄl kairysis, 5 deÅ¡inÄje. Mes, Å¾inoma, pasirinkti 4. 6 kairÄje, 5 deÅ¡inÄje. Mes, Å¾inoma, pasirinkti 5. 6 kairÄje, 7 deÅ¡inÄje. RenkamÄs 6, ir tada mes pasirinkti 7, ir tada mes renkamÄs 8. Voila. 

Taigi didÅ¾iulis skaiÄius tariant vÄliau, mes surÅ«Å¡iuoti Å¡Ä¯ aÅ¡tuoniÅ³ elementÅ³ sÄraÅ¡Ä Ä¯ vienÄ sÄraÅ¡Ä per aÅ¡tuoniÅ³, kad manimi didÄja su kiekvienu Å¾ingsniu, bet kiek laiko darÄ tai uÅ¾truks mums tai padaryti. Na aÅ¡ sÄmoningai laid dalykÅ³ iÅ¡ pavaizduotomis piktogramo- Äia, kad galÄtume rÅ«Å¡ies matyti ar vertiname padalinÄ¯ uÅ¾kariauti kad buvo vyksta. 

IÅ¡ tiesÅ³, jei jÅ«s atsigrÄÅ¾ti Ä¯ tinklÄ, AÅ¡ paliktas visÅ³ Å¡iÅ³ punktyrinÄmis linijomis Ä¯diegtos turÄtojÅ³, galite, rÅ«Å¡ies, Å¾r atvirkÅ¡tine tvarka, jei rÅ«Å¡ies atsigrÄÅ¾ti Ä¯ istorija, dabar, mano originalus sÄraÅ¡as yra, Å¾inoma, dydÅ¾io 8 d. Ir tada anksÄiau buvau susiduriame su dviem sÄraÅ¡us dydis 4, ir tada keturi sÄraÅ¡ai dydis 2, ir tada aÅ¡tuoni sÄraÅ¡ai dydis 1 d. 

Taigi, kas tai daro, rÅ«Å¡ies, priminti jums? Na, iÅ¡ tiesÅ³, bet algoritmai mes paÅ¾velgÄ Å¡iol, kur mes skaldyk ir skaldyk ir atskirties, susilaukia dalykÅ³ ir vÄl vÄl atsiranda Å¡iame bendrÄ idÄjÄ. Ir taip yra kaÅ¾kas logaritminÄ vyksta Äia. Ir tai ne visai Å¾urnalas n, bet ten logaritminis komponentas kas mes kÄ tik padaryti. 

Dabar aptarkime, kaip kad iÅ¡ tikrÅ³jÅ³ yra. Taigi prisijunkite n, vÄl buvo puikus veikimo laikas, kai mes padarÄme kaÅ¾kÄ panaÅ¡aus dvejetainis paieÅ¡kos, kaip mes dabar vadiname, skaldyk ir valdyk strategija per kurÄ¯ mes nustatÄme, Mike Smith. Dabar techniÅ¡kai. Å tai Å¾urnalas bazÄ 2 n, net nors daugeliu matematikos klases, 10 daÅ¾niausiai bazinÄ kad jÅ«s prisiimate. Bet kompiuteriÅ³ mokslininkai beveik visada galvoti ir kalbÄti Kalbant apie pagrindÄ 2, todÄl mes paprastai tiesiog pasakyti Å¾urnalÄ n, o ne log bazÄs 2 n, bet jie tiksliai vienÄ ir tÄ pats Ä¯ kompiuterÄ¯ pasaulyje Mokslas ir kaip panaikinti, ten pastovus veiksnys skirtumas tarp Å¡iÅ³ dviejÅ³, todÄl inscenizacijos vistiek, daugiau formaliÅ³ prieÅ¾asÄiÅ³. 

Bet dabar, kas mums rÅ«pi apie tai pavyzdys. Taigi tegul ne Ä¯rodyti, pavyzdÅ¾iui, bet ne maÅ¾iau naudoti iÅ¡ numeriÅ³ pavyzdÄ¯ po ranka kaip normalumas patikrinti, jei bus. Taigi anksÄiau formulÄ buvo Prisijungti bazÄ 2 n, bet tai, kas yra n ir Å¡iuo atveju. AÅ¡ turÄjau n originalius numerius arba 8 originalaus skaiÄius specialiai. Dabar ji buvo Å¡iek tiek o, bet aÅ¡ esu gana Ä®sitikinkite, kad Å¾urnalas bazÄ 2 iÅ¡ vertÄs 8 yra 3, Ir iÅ¡ tiesÅ³, kas malonu apie tai kad 3 yra tiksliai kartÅ³ kad jÅ«s galite padalinti sÄraÅ¡Ä Ilgio 8 vÄl, ir vÄl, ir vÄl, kol jÅ«s liekate sÄraÅ¡us tik 1 dydÅ¾io. TeisÄ? 8 eina iki 4, eina iki 2, eina iki 1, ir kad tai atspindi bÅ«tent tai nuotrauka mes turÄjome vos prieÅ¡ akimirkÄ. Taigi Å¡iek tiek normalumas patikrinti, kur logaritmas yra faktiÅ¡kai dalyvauja. 

Taigi, dabar, kÄ dar dalyvauja Äia? n. Taigi pastebÄti, kad kiekvienas kartÄ aÅ¡ padalinti sÄraÅ¡Ä nors atvirkÅ¡tine tvarka istorijos Äia, aÅ¡ vis dar daro n dalykÅ³. Tai sujungimo Å¾ingsnis reikalaujama, kad LieÄiu kiekvienÄ numeriÅ³ vienÄ, tam, kad jÄ¯ Ä¯ skaidriÅ³ prireikus jo vieta. Taigi, nors Å¡is aukÅ¡tis schema yra matmenÅ³ daleliÅ³ log n n arba 3, KonkreÄiau, kitaip tariant, AÅ¡ tris padalinius Äia. Kiek darbo aÅ¡ padaryti horizontaliai kartu Å¡ios diagramos kiekvienÄ kartÄ? 

Na, aÅ¡ n Å¾ingsniÅ³ dirbti, nes jei aÅ¡ gavo keturis elementus ir keturis elementus, ir man reikia jas sujungti kartu. Man reikia eiti per Å ie keturi ir jie keturi, galiausiai sujungti jas Atgal Ä¯ aÅ¡tuonias elementais. Jei atvirkÅ¡Äiai, aÅ¡ turiu aÅ¡tuonis pirÅ¡tus Äionai, kurÄ¯ aÅ¡ ne, ir aÅ¡tuonios fingers-- sorry-- Jei aÅ¡ gavo keturis pirÅ¡tus per Äia kuri man daryti, keturi pirÅ¡tai Äionai, kuris man daryti, tada, kad tas pats pavyzdys, kaip ir anksÄiau, jei aÅ¡ turi aÅ¡tuonis pirÅ¡tus nors iÅ¡ viso, kurÄ¯ galiu, rÅ«Å¡ies, daryti. Galiu tiksliai padaryti Äia tada aÅ¡ tikrai gali sujungti visus Å¡iuos sÄraÅ¡us dydÅ¾io 1 kartu. Bet aÅ¡ tikrai turime ieÅ¡koti kiekvieno elemento tik vienÄ kartÄ. Taigi, Å¡io proceso aukÅ¡tis yra log n, Å io proceso plotis, taip sakant, yra n, tai, kÄ mes, atrodo, turÄti, galiausiai, yra bÄgimo laikas dydÅ¾io n kartÅ³ log n. 

Kitaip tariant, mes padalintas sÄraÅ¡as, Å¾urnalas n kartÅ³, bet kiekvienÄ kartÄ mes padarÄme, kad mes turÄjome paliesti kiekvienÄ iÅ¡ elementÅ³ vienÄ siekiant sujungti juos visi kartu, kuris buvo n Å¾ingsnis, todÄl mes turime n kartÅ³ log n, arba kaip kompiuteris mokslininkas pasakytÅ³, asimptotiÅ¡kai, kuris BÅ«tÅ³ didelis Å¾odis apibÅ«dinti virÅ¡utinÄ laikytis ant vaÅ¾iavimo laikas, mes veikia dideliame o RÄstÅ³ n metu, taip sakant. 

Dabar tai yra reikÅ¡minga, nes prisiminti kÄ veikia laikai buvo su burbulas rÅ«Å¡iuoti, ir atrankos RÅ«Å¡iuoti ir Ä¯terpimo rÅ«Å¡iuoti, ir net keli kiti, kurie egzistuoja, n kvadratu buvo, kai mes buvome. Ir jÅ«s galite, rÅ«Å¡ies, pamatyti tai Äia. Jei n kvadratu yra akivaizdÅ¾iai n kartÅ³ N, bet Äia mes turime n kartÅ³ log n, ir mes jau Å¾inome iÅ¡ savaitÄ nuliui, kad Å¾urnalas N, logaritminis, yra geriau nei kaÅ¾kas tiesinis. GalÅ³ gale, prisiminti paveikslÄlÄ¯ su raudona ir geltona ir Å¾alios linijos, kad mes atskleidÅ¾ianti, tuo Å¾alia logaritminÄ linija buvo daug maÅ¾esnis. Ir todÄl, daug geriau ir greiÄiau nei tiesios geltonos ir raudonos linijos, n kartÅ³ log n yra, tiesÄ sakant, geriau nei n kartÅ³, n, arba n kvadrato. 

Taigi, mes, atrodo, nustatÄ algoritmÄ suliejimÄ RÅ«Å¡iuoti kuri veikia daug greiÄiau laikas, ir iÅ¡ tiesÅ³, Å tai kodÄl, anksÄiau Å¡iÄ savaitÄ, kai Mes matÄme, kad tarp burbulas konkursas RÅ«Å¡iuoti atranka rÅ«Å¡iuoti, ir sujungti RÅ«Å¡iuoti, sujungti rÅ«Å¡iuoti tikrai, tikrai laimÄjo. Ir iÅ¡ tiesÅ³, mes net ne laukti Kramtomoji rÅ«Å¡iuoti ir atrankos rÅ«Å¡iuoti pabaigti. 

Dabar galime imtis vienÄ kitÄ perdavimo Ä¯ tai, iÅ¡ Å¡iek tiek daugiau formalus poÅ¾iÅ«ris, tik atveju, tai rezonuoja geriau negu aukÅ¡tesnio lygio diskusija. Taigi Äia algoritmas dar kartÄ. Paklauskime savÄs, kÄ veikia laikas yra tai algoritmai Ä¯vairius veiksmus? Leiskite padalinti jÄ¯ Ä¯ pirmÄ atveju ir antras atvejis. IF ir kitur IF atveju, N yra maÅ¾iau nei 2, tiesiog grÄ¯Å¾ti. JauÄia pastovaus laiko. Tai, tipo, kaip ir dviejÅ³ pakopÅ³, N yra maÅ¾iau nei 2, tada grÄ¯Å¾ti. Bet kaip mes sakÄme, pirmadienÄ¯, pastovus laikas, arba didelis O 1, gali bÅ«ti du Å¾ingsniai, trys Å¾ingsniai, net 1000 Å¾ingsniÅ³. Svarbu yra tai, kad pastovus skaiÄius Å¾ingsnius. Taigi geltona pabrÄÅ¾Ä Pseudocode Äia veikia, mes jÄ¯ vadiname, pastovus laikas. Taigi daugiau formaliai, ir mes ketiname to-- tai bus kiek mes formalizuoti Å¡iÄ teisÄ now-- T n, vaÅ¾iavimo laikas problema kad mano n septyniasdeÅ¡imties kaip Ä¯vestÄ¯, lygus didelis O vienas, N yra maÅ¾iau nei 2. Taigi, tai sÄlyga, kad. Taigi, norint bÅ«ti aiÅ¡ku, n yra maÅ¾iau nei 2, mes turime labai trumpÄ sÄraÅ¡Ä, tada filmo laikas, "T" n, kur n yra 1 arba 0, tai labai konkreÄiu atveju, tai tiesiog bus pastovus laikas. Ji ketina imtis vienÄ dÄti du Å¾ingsnius, nesvarbu. Tai fiksuotas skaiÄius Å¾ingsnius. 

Taigi sultinga dalis turi tikrai bÅ«ti kitas atvejis Pseudocode. Else atveju. RÅ«Å¡iuoti kairÄ pusÄ elementÅ³, rÅ«Å¡iuoti teisÄ pusÄ elementÅ³, sujungti surÅ«Å¡iuotas puses. Kiek kiekviena iÅ¡ Å¡iÅ³ Å¾ingsniÅ³ imtis? Na, jei veikia laikas rÅ«Å¡iuoti n elementÅ³ yra, tegul jÄ¯ vadina labai bendrine, T n, tada rÅ«Å¡iavimas Ä¯ kairÄ pusÄ iÅ¡ elementÅ³, yra, tipo, tarsi sakydamas, T n skirstomos 2, ir panaÅ¡iai rÅ«Å¡iavimo tinkamÄ pusÄ elementÅ³ yra, tipo, tarsi sakydamas, T n padalintas 2, ir tada Sujungiant surÅ«Å¡iuotus puses. Na, jei aÅ¡ turiu kai skaiÄius elementÅ³ Äia kaip keturi, ir Å¡iek tiek skaiÄiÅ³ elementÅ³ Äia, kaip ir keturiÅ³, ir aÅ¡ turiu sujungti kiekvienÄ iÅ¡ Å¡iÅ³ keturiÅ³ Ä¯, ir kiekvienas iÅ¡ jÅ³ keturi, vienÄ po kito, taip, kad galiausiai turiu aÅ¡tuonis elementus. Atrodo, kad tai didelis O n Å¾ingsniÅ³? Jei aÅ¡ turiu n pirÅ¡tus ir kiekviena iÅ¡ jiems turi bÅ«ti sujungtos Ä¯ vietÄ, tai kaip dar n Å¾ingsniÅ³. 

Taigi iÅ¡ tiesÅ³ formulaically, galime iÅ¡reikÅ¡ti tai, nors truputÄ¯ scarily per pirmÄjÄ¯ Å¾vilgsnis, bet tai yra kaÅ¾kas, kuri fiksuoja tiksliai tÄ logikÄ. Judamasis laikas, T n JEI N yra didesnis arba lygus 2. Å iuo atveju, kad ELSE atveju, yra T n padalintas iÅ¡ 2, plius t n padalytÄ iÅ¡ 2, plius DidelÄs O n, kai linijinis pakopÅ³ skaiÄius, gal lygiai n, gal 2 kartus N, bet tai maÅ¾daug, kad n. Taigi, kad per daug, tai, kaip mes galime iÅ¡reikÅ¡ti tai formulaically. Dabar jÅ«s neÅ¾inote, nebent JÅ«s Ä¯raÅ¡yti jÄ¯ Ä¯ savo protÄ, ar ieÅ¡koti jÄ¯ Ä¯ atgal vadovÄlis, kad gali turÄti Å¡iek tiek Cheat sheet pabaigoje bet tai, Å¾inoma, ketina Duok mums O n log n didelis, nes pasikartojimo, kad jÅ«s matote Äia ekrane, jei iÅ¡ tikrÅ³jÅ³ jÄ¯, su begalinis skaiÄius pavyzdÅ¾iÅ³, ar tu jÄ formulaically, darytumÄte matyti, kad tai, nes Å¡iÄ formulÄ savaime yra grÄ¯Å¾tamojo su t n per kaÅ¾kÄ deÅ¡inÄje, ir t n kairÄs, tai gali iÅ¡ tikrÅ³jÅ³ bÅ«ti iÅ¡reikÅ¡tas, galiausiai, tokie dideli Go n log n. Jei nÄra Ä¯sitikinÄs, kad tai gerai dabar, tik imtis tikÄjimo, kad tai, tiesÄ sakant, kÄ, kad pasikartos, veda Ä¯, taÄiau tai yra tik Å¡iek tiek daugiau matematinis metodas ieÅ¡kote tuo veikimo laikas merge rÅ«Å¡iuoti remiantis jos Pseudocode vieni. 

Dabar galime imtis Å¡iek tiek gurkÅ¡nis iÅ¡ visÅ³, kad ir paÅ¾velgti Ä¯ iÅ¡vaizdÄ tikras buvÄs senatorius, kuris gali atrodyti Å¡iek tiek paÅ¾Ä¯stamas, kuris atsisÄdo su "Google" Eric Schmidt prieÅ¡ kurÄ¯ laikÄ, interviu scenoje, prieÅ¡ais visa krÅ«va Å¾moniÅ³, kalbÄti apie galiausiai tema, tai gana dabar paÅ¾Ä¯stamas. Leiskite paÅ¾velgti. 

Ericas Schmidtas: Dabar senatorius, esate Äia Google, ir man patinka galvoti apie Pirmininkaujanti kaip darbo interviu. Dabar sunku gauti darbÄ, kaip prezidentas. Prezidentas B. Obama: DeÅ¡iniuoju. Ericas Schmidtas: Ir jÅ«s ketina daryti [nesigirdi] dabar. Taip pat sunku gauti darbÄ "Google". Prezidentas B. Obama: DeÅ¡iniuoju. 

Ericas Schmidtas: "Mes turime klausimÅ³, ir mes praÅ¡ome mÅ«sÅ³ kandidatÅ³ klausimus, ir tai vienas iÅ¡ Larry Schwimmer. 

Prezidentas B. Obama: "Gerai". 

Ericas Schmidtas: Kas? JÅ«s manote, aÅ¡ nejuokauju? Tai Äia. Kas yra efektyviausias bÅ«das rÅ«Å¡iuoti milijonÄ 32 bitÅ³ sveikÅ³jÅ³ skaiÄiÅ³? 

Prezidentas B. Obama: Well-- Ericas Schmidtas: Kartais gal aÅ¡ atsipraÅ¡au, maybe-- Prezidentas B. Obama: Ne, ne, ne, ne, ne, aÅ¡ think-- Ericas Schmidtas: Tai ne it-- Prezidentas B. Obama: "AÅ¡ manau, manau burbulas RÅ«Å¡iuoti bÅ«tÅ³ neteisingas bÅ«das eiti. Ericas Schmidtas: Nagi. Kas jam Å¡Ä¯ pasakÄ? GERAI. AÅ¡ ne informatikos on-- 

Prezidentas B. Obama: mes gavo mÅ«sÅ³ Å¡nipai ten. PROFESORIUS: Visos deÅ¡inÄ. Palikime uÅ¾ mus dabar Teorinis pasaulis algoritmai Ä¯ asimptotinÄje analizÄs dalÄ¯, ir grÄ¯Å¾ti Ä¯ kai kurias temas nuo nulio ir vienÄ savaitÄ, ir pradÅ¾ios paÅ¡alinti keletÄ mokymo ratus, jei bus. Taigi, kad jÅ«s tikrai suprasti, galiausiai iÅ¡ Å¾emÄs, kas vyksta po kapotu, kai jÅ«s raÅ¡yti, kaupti, ir vykdyti programas. Prisiminkite, ypaÄ, kad tai buvo pirmasis C programa, mes paÅ¾velgÄ, kanoniniu, paprasta programa nekaip, santykinai kalbant, kurioje jis spausdina, Hello World ". Ir prisiminti, kad pasakiau, kad procesas kad kodo eina per yra bÅ«tent tai. JÅ«s imtis savo kodÄ, perduoti tai per sudarytojas, kaip klingsÄti, ir iÅ¡ ateina objekto kodÄ, kad gali atrodyti taip, nuliÅ³ ir kad kompiuterio procesoriaus, centrinis apdorojimo blokas arba smegenÅ³, galiausiai supranta. 

Pasirodo, kad tai yra tiek kaip supaprastinimas, kad mes dabar yra pozicija erzinti iÅ¡skyrus suprasti, kas iÅ¡ tikrÅ³jÅ³ buvo vyksta po kapotu kiekvienÄ kartÄ paleidus KlingsÄti, arba apskritai, kiekvienÄ kartÄ jums padaryti programÄ, naudojant Padaryti CF 50 IDE. VisÅ³ pirma, stuff like tai visÅ³ pirma bÅ«tÅ³ sukuriami, kai pirmÄ kartÄ sudaryti savo programÄ. Kitaip tariant, kai jÅ«s imtis savo kodÄ ir kaupia jÄ¯, o kas pirmas yra iÅ¡vedamas pagal klingsÄti yra kaÅ¾kas Å¾inomas kaip surinkimo kodÄ. Ir iÅ¡ tiesÅ³, atrodo lygiai taip pat kaip tai. 

IÅ¡bÄgau komandÄ ne komandinÄs eilutÄs anksÄiau. KlingsÄti Dash sostinÄs s hello.c, ir tai sukÅ«rÄ failÄ man vadinamÅ³ hello.s, kurio viduje buvo lygiai Å ie turinÄ¯ ir Å¡iek tiek daugiau aukÅ¡Äiau, ir Å¡iek tiek daugiau Å¾emiau, bet aÅ¡ Ä¯dÄti Juiciest informacijos rasite Äia ekrane. Ir jei atidÅ¾iai, pamatysite bent keli paÅ¾Ä¯stami raktaÅ¾odÅ¾ius. Mes turime Pagrindinis virÅ¡uje. Mes printf Å¾emyn viduryje. Ir mes taip pat turime hello world Backslash n citatos apaÄioje. 

Ir visa kita Äia yra labai Å¾emo lygio instrukcijos kad kompiuterio procesorius supranta. CPU instrukcijos, kad juda atminties aplink, kad apkrovos Ä¯sipareigojimÅ³ iÅ¡ atminties, ir galiausiai, spausdinti dalykÅ³ ekrane. Dabar, kas atsitinka, nors po Å¡i asamblÄja kodas generuojamas? GalÅ³ gale, jÅ«s, Å¾inoma, vis dar generuoja objekto kodÄ. Bet Å¾ingsniai, kurie turi tikrai vyksta po kapotu atrodo Å¡iek tiek daugiau, kaip Å¡is. Å altinis kodas tampa surinkimo kodas, kuris tada tampa objekto kodas, ir rezoliucinÄ Å¾odÅ¾iai Äia yra, kad kai jÅ«s surinkti savo kodÄ, iÅ¡ ateina surinkimo kodÄ ir kai jÅ«s surinkti savo surinkimo kodÄ iÅ¡ ateina objekto kodÄ. 

Dabar klingsÄti yra super sudÄtingas, tarsi sudarytojÅ³ daug, ir ji visus Å¡iuos veiksmus kartu, ir tai nereiÅ¡kia, kad iÅ¡vesties bet koks tarpinis failai, jÅ«s netgi galite pamatyti. Jis tiesiog kaupia daiktus, kuris yra bendras terminas, kad apibÅ«dina visÄ Å¡Ä¯ procesÄ. Bet jei jÅ«s tikrai norite bÅ«ti ypaÄ ten daug ten vyksta taip pat. 

Bet tegul taip pat mano, kad dabar, net kad super paprasta programa, hello.c, vadinama funkcija. Ji paragino printf. Bet aÅ¡ ne raÅ¡yti printf, tiesÄ sakant, kuris ateina su C, taip sakant. Tai funkcija Prisiminkite, kad tai paskelbta standartinio io.h, kuris yra antraÅ¡tÄs failas, kuris yra tema mes iÅ¡ tikrÅ³jÅ³ pasinerti Ä¯ daugiau gylio prieÅ¡ ilgas. Bet antraÅ¡tÄs failas yra paprastai lydi pagal kodÄ failÄ, kodo failÄ, panaÅ¡iai kaip egzistuoja standartinÄs io.h. 

KaÅ¾kada seniai, kaÅ¾kas, ar kaÅ¾kam, taip pat raÅ¡Ä failas vadinamas standartiniu io.c, Ä¯ kuriÅ³ faktinÄ apibrÄÅ¾imai, arba realizacijos printf, ir kekiÅ³ kitÅ³ funkcijÅ³, iÅ¡ tikrÅ³jÅ³ yra paraÅ¡yta. Taigi atsiÅ¾velgiant Ä¯ tai, jei mes manome, turintys Äia kairÄje, hello.c, kad kai parengta, suteikia mums hello.s, net jei KlingsÄti nesivargina taupymo vietoje galime matyti, ir kad surinkimo kodas gauna surinkti Ä¯ hello.o, kuris yra, iÅ¡ tiesÅ³, numatytasis pavadinimas teikiama, kai jÅ«s surinkti Å¡altinÄ¯ kodÄ Ä¯ objektiniu kodu, bet nÄra visai pasirengÄ jÄ¯ vykdyti dar, nes dar vienas Å¾ingsnis turi atsitikti, ir turi buvo daroma per pastaruosius keletÄ savaites, galbÅ«t neÅ¾inant jums. 

Tiksliau kaÅ¾kur Ä¯ CS50 IDE, ir tai, taip pat, bus kraÅ¡tui tiek supaprastinimas akimirkÄ, yra arba buvo ant metu, failas vadinamas standartiniu io.c, kad kaÅ¾kas surinkti Ä¯ standartiniai io.s arba lygiaverÄiai, kad kaÅ¾kas tada surinkti Ä¯ standartinÄ¯ io.o, arba paaiÅ¡kÄja iÅ¡ jo Å¡iek tiek skiriasi failÄ formatas, kuris gali turÄti skirtingas Rinkmenos plÄtinys apskritai, bet teoriÅ¡kai ir konceptualiai, tiksliai tie Å¾ingsniai turÄjo Ä¯vykti tam tikra forma. Kuris yra pasakyti, kad dabar kai aÅ¡ raÅ¡au programÄ, hello.c, kad tiesiog sako, hello world, ir aÅ¡ naudoju kaÅ¾kieno kodÄ kaip printf, kuris buvo kadaise laikas, faile vadinamas standartinis io.c, tada kaÅ¾kaip turiu imtis savo objekto kodas, mano nuliÅ³ ir, ir kad asmens objektas kodÄ arba nuliÅ³ ir, ir kaÅ¾kaip susieti juos kartu Ä¯ Vienas galutinis failas, vadinamas labas, kad turi visas nulio ir tie iÅ¡ mano pagrindinÄs funkcijos, ir visi nulio ir tie, printf. 

Ir iÅ¡ tiesÅ³, tai paskutinis procesas vadinamas, susiejimas savo objektÄ kodÄ. Ä®taisas, kurio iÅ¡Äjimas yra vykdomÄjÄ¯ failÄ. Taigi sÄÅ¾iningumo, ne pabaigoje dienÄ, nieko pasikeitÄ nuo savaitÄs viena, kai mes pirmÄ kartÄ pradÄjo sudarant programas. IÅ¡ tiesÅ³, visa tai buvo vyksta po gaubtu, bet dabar mes tokioje padÄtyje, kur mes galime iÅ¡ tikrÅ³jÅ³ erzinti, iÅ¡skyrus Å¡iuos Ä¯vairius veiksmus. Ir iÅ¡ tikrÅ³jÅ³, pabaigoje dienos, mes vis dar liko nuliÅ³ ir, kurie yra tikrai puikus Segue dabar Ä¯ kitÄ C galimybes, kad mes neturÄjome sverto greiÄiausiai iki Å¡iol Å¾inoma kaip Bitinis operatoriÅ³. Kitaip tariant, iki Å¡iol, bet kuriuo metu, mes nagrinÄjami duomenÅ³ C arba kintamÅ³jÅ³ C, mes jau tokius dalykus kaip simboliÅ³ ir plÅ«dÄs ir moduliai ir ilgisi ir dvivieÄiai ir pan, bet visi iÅ¡ jÅ³ yra bent aÅ¡tuonis bitai. Mes niekada dar galÄjo manipuliuoti atskirus bitus, nors individualaus tiek, mes Å¾inau, gali atstovauti 0 ir 1. Dabar paaiÅ¡kÄja, kad C, jums galite gauti prieigÄ prie atskirÅ³ bitÅ³, jei Å¾inote, sintaksÄ, su kuria gauti Ä¯ juos. 

Taigi leiskite paÅ¾velgti ne Bitinis operatoriÅ³. Taigi nuotraukoje Äia yra keletas simboliai mes, tipo, rÅ«Å¡iuoti, matÄs. Matau ampersendo, vertikalus Baras, ir kai kurie kiti, taip pat, ir prisiminti, kad Ampersand ampersendo yra kaÅ¾kas, kÄ mes matÄme anksÄiau. LogiÅ¡ka operatorius AND, kur jÅ«s turite du iÅ¡ jÅ³ kartu, arba loginis ARBA operatorius, kur jÅ«s turi dvi vertikalias juostas. Bitinis operatoriÅ³, kuris mes matyti veikti bitai individualiai, tiesiog naudoti vienÄ ampersendo A vieno vertikali juosta, Å½ymeklis simbolis ateina kitas, maÅ¾ai Tilde, tada Ä¯ kairÄ laikiklis paliko laikiklÄ¯ arba teisÄ laikiklis teisÄ laikiklis. Kiekvienas iÅ¡ jÅ³ turi skirtingas reikÅ¡mes. 

IÅ¡ tiesÅ³, tegul paÅ¾velgti. Vykime senosios mokyklos Å¡iandien ir naudojimas jutiklinis ekranas iÅ¡ praeities, Å¾inomas kaip baltos lentos. Ir tai balta lenta ketina leisti mums iÅ¡reikÅ¡ti keletÄ gana paprastÅ³ simbolius, ar veikiau kai gana paprastas formules, , kad mes galime tada galiausiai svertas, kad bÅ«tÅ³ prieiti prie atskirÅ³ bitai per C programa. Kitaip tariant, galime tai padaryti. Tegul pirmasis aptarimas dÄl momentas apie Å¾enklui, kuri yra Bitinis operatorius AND. Kitaip tariant, tai yra operatorius, kuris leidÅ¾ia man turÄti kairinis kintamasis Paprastai ir deÅ¡inÄ kintamasis, arba individualus vertÄ, tai jei mes IR juos kartu, suteikia man galutinÄ¯ rezultatÄ. Taigi, kÄ aÅ¡ turiu galvoje? Jei programoje, turite kintamÄjÄ¯ kuris saugo vienÄ iÅ¡ Å¡iÅ³ reikÅ¡miÅ³, arba tegul keep it simple, ir tik raÅ¡yti nuliÅ³ ir individualiai, Å tai kaip Ampersand operatorius veikia. 0 Ampersand 0 ketina lygus 0. Dabar, kodÄl taip yra? 

Tai labai panaÅ¡us Ä¯ BÅ«lio iÅ¡raiÅ¡kos, kad mes aptarÄ iki Å¡iol. Jei manote, galÅ³ gale, yra 0 klaidinga, 0 yra klaidinga, klaidinga ir neteisinga yra, kaip mes aptarti LogiÅ¡kai mÄstant, taip pat klaidinga. Taigi mes gauname 0 Äia taip pat. Pavartojus 0 ampersendo 1, gerai, kad, taip pat, bus 0, nes tai kairine iÅ¡raiÅ¡ka, kad bÅ«tÅ³ tiesa arba 1, ji turi bÅ«ti teisinga ir tikra. Bet Äia mes turime klaidinga ir tiesa, arba 0 ir 1. Dabar vÄl, jei mes turime 1 ampersendo 0, tai taip pat bus 0, ir jei mes turime 1 ampersendo 1, pagaliau mes turime 1 bitas. Taigi, kitaip tariant, mes ne daro nieko Ä¯domiau su Å¡iuo operatoriumi tik dar, tai Ampersand operatorius. Tai Bitinis operatorius AND. TaÄiau tai yra ingredientai per kurÄ¯ mes galime padaryti Ä¯domiÅ³ dalykÅ³, kaip mes netrukus pamatysite. 

Dabar paÅ¾velkime tik vienÄ vertikali juosta Äionai deÅ¡inÄje. Jei turiu 0 truputÄ¯ ir aÅ¡ Arba tai su ja Bitinis Arba operatorius, kitas 0 truputÄ¯, kad ketina suteikti man 0. Jei aÅ¡ imtis 0 truputÄ¯ ir ar IT su A 1 tiek, tada aÅ¡ ruoÅ¡iuosi gauti 1. Ir iÅ¡ tikrÅ³jÅ³, tik aiÅ¡kumas, leiskite man grÄ¯Å¾ti, kad mano vertikalios juostos nÄra klaidingai palaikyta 1 s. Leiskite man perraÅ¡yti visus mano 1 yra Å¡iek tiek daugiau aiÅ¡kiai, taip, kad mes kitÄ Å¾r, jei aÅ¡ turÄti 1 arba 0, kad ketina bÅ«ti 1, o jei turiu 1 arba 1, kad, taip pat ketina bÅ«ti 1. Taigi jÅ«s galite pamatyti logiÅ¡kai, kad AR operatorius elgiasi labai skirtingai. Tai suteikia man 0 arba 0 man duoda 0, taÄiau kiekvienas kitas derinys suteikia man 1. Kol turiu vienÄ 1 dalyje, formulÄ, rezultatas bus 1 d. 

Skirtingai nei paties ir operatorius, Ampersand, tik tada, jei turiu du 1, The lygtis, aÅ¡ iÅ¡ tikrÅ³jÅ³ gauti 1 iÅ¡. Dabar yra keletas kitÅ³ operatoriai, taip pat. Vienas iÅ¡ jÅ³ yra Å¡iek tiek daugiau Ä¯sitraukti. Taigi leiskite man eiti Ä¯ priekÄ¯ ir iÅ¡trinti tai atlaisvinti Å¡iek tiek vietos. Ir tegul ne iÅ¡vaizdÄ Å½ymeklis simboliu, tik akimirkai. Tai yra paprastai charakteris galite Ä¯vesti JÅ«sÅ³ klaviatÅ«ra laikymu Shift ir tada vienas ant savo JAV skaiÄiais klaviatÅ«ra. 

Taigi tai yra iÅ¡skirtinis Arba operatorius, arba iÅ¡imtines. Taigi mes tiesiog pamaÄiau arba operatorius. Tai yra iÅ¡imtinÄ arba operatorius. Kas iÅ¡ tikrÅ³jÅ³ skirtumas? Na tegul tiesiog paÅ¾velgti Ä¯ formulÄ, ir tai naudoti kaip ingredientus galiausiai. 0 XOR 0. AÅ¡ ruoÅ¡iuosi pasakyti visada 0. Å tai iÅ¡ XOR apibrÄÅ¾imas. 0 XOR 1 bus 1 d. 1 XOR 0 bus 1, ir 1 XOR 1 bus? Negerai? Arba tiesa? NeÅ¾inau. 0. Dabar tai, kas vyksta Äia? Na manau, kad apie Pavadinimas Å¡io operatoriaus. IÅ¡skirtinis ARBA, taip, kaip pavadinimas, rÅ«Å¡is ir, rodo, atsakymas tik bus A 1, jei indÄlis yra iÅ¡skirtinis, tik skirtingi. Taigi Äia Ä¯Äjimai yra pat, todÄl iÅ¡Äjimas yra 0. Äia Ä¯Äjimai yra pat, todÄl iÅ¡Äjimas yra 0. Äia yra iÅ¡Äjimai yra skirtingi, todÄl jie yra iÅ¡imtinÄs, todÄl produkcija yra 1. Taigi, tai labai panaÅ¡us Ä¯ IR, tai labai panaÅ¡Å«s, ar veikiau tai labai panaÅ¡us Ä¯ ARBA, bet tik iÅ¡skirtiniu bÅ«du. Tai vienas yra nebÄra 1, nes mes turime dvi 1-Å³jÅ³, ir ne iÅ¡imtinai, tik vienas iÅ¡ jÅ³. Gerai. KÄ apie kitus? Na tildÄs, tuo tarpu, yra iÅ¡ tikrÅ³jÅ³ graÅ¾us ir paprastas, laimei. Ir tai unarinÄ¯ operatoriaus, kuris reiÅ¡kia, jis taikomas tik vienÄ Ä¯vesties, vienas operandas, taip sakant. Ne iÅ¡ kairÄs ir deÅ¡inÄ. Kitaip tariant, jei vartojate tildÄs iÅ¡ 0, atsakymas bus prieÅ¡ingas. Ir jei jÅ«s imtis Tilde 1, The Atsakymas bus prieÅ¡ingas. Taigi tildÄs operatorius iÅ¡ paneigiant truputÄ¯ bÅ«das, arba prakeiktas nuo tiek 0-1, arba nuo 1 iki 0. 

Ir tai palieka mus pagaliau tik su dviem galutiniais operatoriÅ³, vadinamasis kairysis SHIFT ir Vadinamasis teisÄ perÄjimas operatorius. Paimkime, kaip tas darbas atrodo. Ataka perÄjimas operatorius, paraÅ¡yta su dviem lauÅ¾tiniuose skliaustuose, pavyzdÅ¾iui, kad veikia taip. Jei mano indÄlis, ar mano operandas, Ä¯ kairÄ perÄjimas operatorius paprasÄiausiai yra 1. Ir aÅ¡ tada pasakysiu kompiuterÄ¯ Ä¯ kairÄ, kad 1, pasakyti septyni vietos, rezultatas yra tarsi bÅ«Äiau imtis, kad 1, ir perkelti jÄ¯ septynios vietos perkelti Ä¯ kairysis, ir pagal nutylÄjimÄ, mes ketiname daryti prielaidÄ, kad erdvÄ Ä¯ deÅ¡inÄ ketina bÅ«ti su paminkÅ¡tinimu nuliai. Kitaip tariant, 1 paliktas poslinkio 7 vyksta duoti me, kad 1, po 1, 2, 3, 4, 5, 6, 7 nulio. Taigi tokiu bÅ«du, jis leidÅ¾ia jums imtis nedidelÄ¯ skaiÄiÅ³ kaip 1, ir aiÅ¡kiai padaryti jÄ¯ daug daug, daug didesnis Å¡iuo bÅ«du, bet mes iÅ¡ tikrÅ³jÅ³ ketiname pamatyti daugiau protingas poÅ¾iÅ«riai jÄ¯ vietoj to, taip pat, 

Gerai. Å tai jÄ¯ savaitÄ trys. Pamatysime, jums kitÄ kartÄ. Tai buvo CS50. 

[Muzikos grojimo] 

GARSIAKALBIS 1: Jis buvo tuo uÅ¾kandis bar valgyti karÅ¡tÄ fudge ledai. Jis turÄjo viskÄ per veidÄ. Jis dÄvi, kad kaip ir barzda Å¡okoladÄ SPEAKER 2: KÄ tu darai? GARSIAKALBIS 3: Hmmm? KÄ? 

SPEAKER 2: Ar jums tiesiog dukart DIP? JÅ«s dvigubai artimÅ³jÅ³ lustas. GARSIAKALBIS 3: Atleiskit. SPEAKER 2: JÅ«s artimÅ³jÅ³ lustas, jums paÄmÄ Ä¯kandimo, ir jÅ«s artimÅ³jÅ³ vÄl. GARSIAKALBIS 3: SPEAKER 2: Å tai kaip pradÄti Visa jÅ«sÅ³ burna tiesiai Ä¯ kritimo. KitÄ kartÄ iÅ¡gÄrÄte lustÄ, tik panirti jÄ¯ vienÄ kartÄ, ir jÄ baigti. 

GARSIAKALBIS 3: jÅ«s Å¾inote, kÄ Dan? JÅ«s panirti keliÄ, kurÄ¯ norite panirti. AÅ¡ panirti keliÄ, kad aÅ¡ noriu panirti.