[Muzikavimo] Davidas Malan: Gerai. Gerai, pasveikinti atgal. Taigi tai yra 4 savaitÄ, pradÅ¾ia jo, jau. Ir jums priminti, kad praÄjusiÄ savaitÄ, mes Ä¯dÄti kodÄ skirta tik Å¡iek tiek ir mes pradÄjome kalbÄti Å¡iek tiek daugiau aukÅ¡to lygio, apie tokius dalykus kaip paieÅ¡kos ir rÅ«Å¡iavimo, kuris nors Å¡iek tiek paprastÅ³ idÄjÅ³, yra atstovas problemÅ³ klasei jÅ«s pradÄsite sprÄsti ypaÄ kaip jums pradÄti galvoti apie galutinÄ¯ projektai ir Ä¯domiÅ³ sprendimÅ³ jÅ«s gali tekti realaus pasaulio problemas. Dabar burbulas tarsi buvo vienas iÅ¡ paprasÄiausiÅ³ tokie algoritmai, ir tai dirbo turÄdami Å¡iuos maÅ¾us numerius sÄraÅ¡e arba masyvo rÅ«Å¡ies burbulas savo keliÄ Ä¯ virÅ¡Å³, ir didelis skaiÄius perkelti savo keliÄ Å¾emyn Å io sÄraÅ¡o pabaigoje. 

Ir priminti, kad mes galime vizualizuoti burbulas rÅ«Å¡iuoti maÅ¾ai kaÅ¾kas panaÅ¡aus Ä¯ tai. Taigi leiskite man eiti Ä¯ priekÄ¯ ir spustelÄkite PradÄti. AÅ¡ iÅ¡ anksto pasirinkti burbulas rÅ«Å¡iuoti. Ir jei jÅ«s prisimenate, kad aukÅ¡tesni mÄlyna linijos sudaro didelis skaiÄius, maÅ¾as mÄlynos linijos sudaro nedidelis skaiÄius, kaip mes pereiti per tai vÄl ir vÄl, ir vÄl, lyginant dvi juostas viena Å¡alia kitas raudonai, mes ketiname apsikeitimo didÅ¾iausias ir maÅ¾iausias jei jie yra ne iÅ¡ eilÄs. 

Taigi, tai bus eiti ir eiti ir eiti Ä¯jungtas, ir jÅ«s pamatysite, kad didesnis elementai yra padaryti savo keliÄ Ä¯ sugebÄjimus ir maÅ¾esni elementai padaryti savo keliÄ Ä¯ kairÄ. Bet mes pradÄjo kiekybiÅ¡kai efektyvumas, kokybÄ Å¡Ä¯ algoritmÄ. Ir mes pasakÄme, kad blogiausia atveju Å¡is algoritmas buvo maÅ¾daug kiek Å¾ingsniÅ³? 

Taigi n kvadratu. Ir tai, kas buvo n? 

Auditorija: ElementÅ³ skaiÄius. 

Davidas Malan: Taigi n buvo skaiÄius elementÅ³. Ir taip mes padarysime tai daÅ¾nai. Bet kuriuo metu mes norime kalbÄti apie dydÄ¯ problema arba dydÅ¾io Ä¯Äjimas, arba kiek laiko uÅ¾trunka gaminti produkcijÄ, mes tiesiog apibendrintas kokia indÄlis yra kaip n. Taigi atgal Ä¯ savaitÄ 0, skaiÄius puslapiai telefonÅ³ knygoje buvo n. StudentÅ³ skaiÄius patalpoje buvo n. Taigi Äia taip pat, mes po kad modelis. 

Dabar n kvadratu ne itin greitai, todÄl mes bandÄme padaryti geriau. Ir taip mes paÅ¾velgÄ porÄ kiti algoritmai, tarp kuriÅ³ buvo pasirinkimas rÅ«Å¡iuoti. Taigi atranka tarsi buvo Å¡iek tiek kitoks. Tai buvo beveik paprasÄiau, drÄ¯stu pasakyti, kai aÅ¡ pradÄjau prie pradÅ¾ios sÄraÅ¡as iÅ¡ mÅ«sÅ³ savanoriÅ³, ir aÅ¡ tiesiog dar kartÄ ir vÄl ir vÄl iÅ¡gyveno sÄraÅ¡as, skynimas iÅ¡ maÅ¾iausiÅ³ elementas metu ir iÅ¡leisti jÄ¯ arba jÄ prie sÄraÅ¡o pradÅ¾ioje. 

TaÄiau tai taip pat, kai mes pradÄjome galvoti per matematikos ir didesnio paveikslÄlÄ¯, pagalvojau apie tai, kiek kartÅ³ AÅ¡ buvau ketinate pirmyn ir atgal ir atgal ir atgal, mes pasakÄme, blogiausiu atveju, pasirinkimas rÅ«Å¡iuoti, taip pat buvo kÄ? n kvadratu. Dabar realiame pasaulyje, ji gali iÅ¡ tikrÅ³jÅ³ Å¡iek tiek greiÄiau. Nes vÄl, aÅ¡ neturÄjau iÅ¡laikyti atsitraukia kartÄ aÅ¡ surÅ«Å¡iuoti smulkiausi elementai. Bet jei mes galvojame apie labai didelis n ir jei tarsi daryti iÅ¡ matematikos kaip AÅ¡ ant lentos, su n kvadratu atÄmus kaÅ¾kas, visa kita be to, n kvadratu, kartÄ n bus tikrai didelis, nÄra tikrai nesvarbu kiek. Taigi, kaip kompiuteriÅ³ specialistÅ³, mes rÅ«Å¡iuoti uÅ¾merkti akis Ä¯ maÅ¾esnius veiksniai ir sutelkti dÄmesÄ¯ tik Ä¯ veiksnys iÅ¡raiÅ¡ka, kuri ketina padaryti DidÅ¾iausias skirtumas. 

Na, galiausiai, mes paÅ¾velgÄ ne Ä¯terpimo rÅ«Å¡iuoti. Ir tai nuotaika buvo panaÅ¡i Ä¯, bet o ne eiti per keletÄ kartÅ³ ir pasirinkite maÅ¾iausiÄ elementÄ vienÄ kartÄ, aÅ¡ vietoj paÄmÄ rankÄ, kad aÅ¡ buvo nagrinÄjamas, ir aÅ¡ nusprendÅ¾iau, visi Gerai, jÅ«s priklausote Äia. Tada aÅ¡ persikÄlÄ Ä¯ kitÄ elementÄ ir nusprendÄ, kad jis arba ji priklausÄ Äia. Ir tada aÅ¡ persikÄlÄ ir. Ir aÅ¡ gali tam, pakeliui, perkelti Å¡ie vaikinai siekiant padaryti vietos jiems. Taigi, tai buvo tarsi psichikos atstatymo Atrankos rÅ«Å¡iuoti, kad mes vadinama Ä¯terpimo rÅ«Å¡iuoti. 

Taigi Å¡ios temos pasitaiko realiame pasaulyje. Vos prieÅ¡ kelerius metus, kai tam tikros senatorius buvo paleisti Ä¯ prezidentus, Ericas Schmidtas, tuo metu, kai generalinis direktorius "Google", iÅ¡ tikrÅ³jÅ³ turÄjo galimybÄ apklausti jÄ¯. Ir mes manome, kad mes norime pasidalinti Å¡ia YouTube klipas jums Äia, jei galÄtume riesti apimtis. 

[VIDEO PLAYBACK] 

-Dabar, senatorius, jÅ«s Äia "Google" ir man patinka galvoti apie pirmininkavimo kaip darbo interviu. 

[Juokas] 

-Dabar tai sunku gauti kaip prezidentas darbas. Ir jÅ«s ketinate per sÄstingis dabar. Taip pat sunku gauti "Google" darbÄ. Mes turime klausimus ir mes klausiame mÅ«sÅ³ kandidatai klausimai. Ir tai vienas iÅ¡ Larry Schwimmer. 

[Juokas] -Vaikinai manau, kad aÅ¡ juokauju? Tai Äia. Kas yra efektyviausias bÅ«das rÅ«Å¡iuoti milijono dviejÅ³ bitÅ³ sveikÅ³jÅ³ skaiÄiÅ³? 

[Juokas] 

-Na, na - 

-I 'm sorry. Gal mes turÄtume - 

-Ne, ne, ne, ne, ne. 

-Tai ne - Gerai. 

-Manau, kad burbulas tarsi bÅ«tÅ³ bÅ«ti neteisingas kelias. 

[Juokas] 

[Giedras ir plojimai] 

-Nagi, kas jam Å¡Ä¯? Gerai. 

[PABAIGA VIDEO PLAYBACK] 

Davidas Malan: Taigi jÅ«s turite jÄ¯. Taigi mes pradÄjome kiekybiÅ¡kai tai veikia kartÅ³, taip sakant, su kaÅ¾kuo vadinamas asymptotic Å¾ymÄjimas, kuris yra tik nuoroda Ä¯ mÅ«sÅ³ rÅ«Å¡ies tekinimo aklas akis tiems maÅ¾esniÅ³ veiksniÅ³ ir tik Å¾iÅ«ri Ä¯ vaÅ¾iavimo laikas, Å iÅ³ algoritmÅ³ efektyvumÄ, kaip n bus tikrai didelis laikui bÄgant. Ir taip mes pristatÄme didelis O. ir didelis O atstovaujama kaÅ¾kas, kad mes manome, kad AS virÅ¡utinÄ riba. Ir iÅ¡ tiesÅ³, Barry, mes galime sumaÅ¾inti nei mikrofono truputÄ¯? 

ManÄme, kad tai yra virÅ¡utinÄ riba. Taigi didelis O nuo n kvadratu, reiÅ¡kia, kad Blogiausiu atveju, kaÅ¾kas panaÅ¡aus pasirinkimas rÅ«Å¡iuoti uÅ¾truktÅ³ n kvadratu veiksmus. Ar kaÅ¾kas panaÅ¡aus Ä¯terpimo rÅ«Å¡iuoti bÅ«tÅ³ n kvadratu Å¾ingsniai. Dabar kaÅ¾kÄ panaÅ¡aus budas rÅ«Å¡iuoti, kas blogiausiu atveju? AtsiÅ¾velgiant Ä¯ tai, masyvas, kas blogiausia galimas scenarijus, kad jÅ«s galite rasti sau susiduria su? 

Tai visiÅ¡kai atgal, tiesa? Nes jei tai visiÅ¡kai atgal, jÅ«s turite padaryti visai daug darbo. Nes jei jÅ«s esate visiÅ¡kai atgal, jÅ«s ketinate rasti didÅ¾iausias elementas Äia, nors ji priklauso ten. Taigi jÅ«s ketinate pasakyti, gerai, bent tai laiko momentas, jÅ«s priklausote Äia todÄl jÅ«s palikti jÄ¯ ramybÄje. 

Tada jÅ«s suprasite, oh, velnias, ir aÅ¡ turiu perkelti Å¡Ä¯ Å¡iek tiek maÅ¾esnis elementas jus Ä¯ kairÄ. Tada aÅ¡ turiu daryti, kad vÄl ir vÄl ir vÄl. Ir jei aÅ¡ vaikÅ¡Äiojo pirmyn ir atgal, jÅ«s bÅ«tÅ³ tarsi jauÄia veikimÄ kad algoritmas, nes nuolat esu shuffling visi kiti Å¾emyn masyvas, kad paliktume jÄ¯. Å tai blogiausiu atveju. 

PrieÅ¡ingai - ir tai buvo Ä®spÅ«dingos filmÄ paskutinÄ¯ kartÄ - sakÄme, kad Ä¯terpimo rÅ«Å¡iuoti buvo, kÄ Omega? Kas geriausiu atveju veikia laikas Ä¯terpimo rÅ«Å¡iuoti? Taigi, tai tikrai n. Tai buvo tuÅ¡Äias, kad mes palikome ant lentos paskutinÄ¯ kartÄ. 

Ir tai omega n, nes kodÄl? Na, labai geriausiu atveju kas Ä¯terpimo rÅ«Å¡iuoti bus Ä¯teiktas? Na, sÄraÅ¡as, kurÄ¯ visiÅ¡kai rÅ«Å¡iuojami jau minimalus darbo padaryti. Bet kas, tvarkingas apie Ä¯terpimo rÅ«Å¡iuoti yra tas, kad jis prasideda Äia ir nusprendÅ¾ia, oi, jÅ«s numeris viena, jÅ«s priklausote Äia. O, kas laimÄs. 

JÅ«s numeris du. JÅ«s taip pat priklauso Å¡iai. Numeris trys, dar geriau, JÅ«s priklausote Äia. Kai tik jis gauna Ä¯ pabaigos sÄraÅ¡as, uÅ¾ Ä¯terpimo RÅ«Å¡iuoti anketa Pseudocode kad mes vaikÅ¡Äioti per Å¾odÅ¾iu paskutinÄ¯ kartÄ, tai daroma. Bet pasirinkimas rÅ«Å¡iuoti, prieÅ¡ingai, nuolat tai daryti, kÄ? 

Nuolat vyksta per sÄraÅ¡Ä vÄl ir vÄl ir vÄl. Kadangi pagrindinÄ Ä¯Å¾valga buvo tik kai jÅ«s paÅ¾velgÄ visÄ keliÄ iki pabaigoje sÄraÅ¡o galite bÅ«ti tikri, kad elementas pasirinkote buvo IÅ¡ tiesÅ³ Å¡iuo metu maÅ¾iausias elementas. Taigi tai skiriasi psichikos modeliai pabaiga iki duoda keletÄ labai realaus pasaulio skirtumai mums, taip pat Å¡iÅ³ teoriniai asimptotiniai skirtumai. 

Taigi tiesiog Priminti tada, DidelÄs O n langeliais, mes matÄme keletÄ tokiÅ³ algoritmai iki Å¡iol. DidelÄs O n? Kas yra algoritmas, kuris galÄtÅ³ bÅ«ti laikomas didelis O n? Blogiausiu atveju, ji trunka linijinis pakopÅ³ skaiÄius. 

Gerai, linijiniai paieÅ¡ka. O blogiausiu atveju, jei yra elementas jÅ«s ieÅ¡kote, kai taikant linijinÄ¯ ieÅ¡koti? 

Gerai, blogiausiu atveju, tai net ne ten. Arba antrÄja blogiausiu atveju, tai visi galÅ³ gale bÅ«das, kuris yra plius ar minus-vienas Å¾ingsnis skirtumas. Tad dienos pabaigoje, mes galime pasakyti, kad linijinÄ. DidelÄs O n bÅ«tÅ³ tiesinis paieÅ¡ka, nes blogiausiu atveju, elementas net ne ten, ar tai visi pabaigoje bÅ«das. 

Na, didelis O iÅ¡ Å¾urnalo n. Mes ne kalbÄti labai iÅ¡samiai apie tai, bet mes matÄme anksÄiau. KÄ veikia vadinamasis logaritminÄ laikas, blogiausiu atveju? 

Taip, taip, dvejetainis paieÅ¡kos. Ir dvejetainis paieÅ¡kos blogiausiu atveju gali turÄti elementÄ kaÅ¾kur viduryje, ar kaÅ¾kur viduje masyvo. Bet jÅ«s tik rasti jÄ¯, kai jÅ«s padalinti sÄraÅ¡Ä per pusÄ, Ä¯ pusÄ, per pusÄ, per pusÄ. Ir tada voila, tai ten. Arba vÄl, blogiausiu atveju, tai net ne ten. Bet jÅ«s neÅ¾inote, kad jo ten nÄra kol tarsi pasiekti, kad paskutinis apaÄios dauguma elementÅ³ perpus ir perpus ir perpus. 

DidelÄs O 1. Taigi, mes galime didelis O 2, didelis O 3. Anytime norite tik pastovÅ³ skaiÄiÅ³, mes tiesiog rÅ«Å¡iuoti tik supaprastinti kad didelis O 1. Nors jei realiai, tai trunka 2 ar net 100 laiptelius, jei tai pastovus pakopÅ³ skaiÄius, mes tiesiog pasakyti didelis O 1. Kas yra algoritmas, kuris yra dideliÅ³ O 1? 

PUBLIKA: IeÅ¡koti ilgÄ¯ iÅ¡ kintamÄjÄ¯. 

Davidas Malan: IeÅ¡koti ilgis kintamasis? 

Auditorija: Ne, ilgis jei jis jau rÅ«Å¡iuojamos. 

Davidas Malan: Geras. Gerai, kad rasti kaÅ¾kÄ ilgis jei tos kaÅ¾kÄ ilgis, kaip masyvas, yra saugomi tam tikru kintamuoju. Kadangi jÅ«s galite tik skaityti kintamÄjÄ¯, arba spausdinti kintamÄjÄ¯, arba tiesiog paprastai gauti tÄ kintamÄjÄ¯. Ir voila, kad mano pastovus laikÄ. 

PrieÅ¡ingai, manau, Ä¯ nulio. Prisiminkite pirmÄ savaitÄ C skambinti tik printf ir spausdinimas kaÅ¾kas ekrane yra neabejotinai pastovus laikas, nes ji tik mano kai procesoriaus ciklÅ³ skaiÄius, kurÄ¯ rodo kad ekrane tekstÄ. Arba laukti - Ar ji? Kaip kitaip galÄtume modeliuoti atlikimas printf? Ar kas nors norÄtÅ³ nesutikti, kad gal tai tikrai ne pastovus laikas? Kokia prasme gali printf bÄga laikas, iÅ¡ tikrÅ³jÅ³ spausdinimo juostelÄ ekranas, bÅ«ti kaÅ¾kas iÅ¡skyrus pastovus. 

Auditorija: [nesigirdi]. 

Davidas Malan: Taip. Taigi tai priklauso nuo mÅ«sÅ³ perspektyvos. Jei mes iÅ¡ tikrÅ³jÅ³ galvoti apie indÄlio printf kaip eilutÄ, ir TodÄl mes Ä¯vertinti, kad dydis Ä¯Äjimas jo ilgis - todÄl galime skambinti kad ilgis n, taip pat - be abejo, printf pati DidelÄs O n nes jis ketina imtis jums n Å¾ingsnius spausdinti kiekvienÄ iÅ¡ tÅ³ n Å¾enklai, greiÄiausiai. Bent tiek, kad mes manome, kad gal tai naudojant uÅ¾ kilpos po gaubtu. 

Bet mes turime paÅ¾velgti, kad Kodas NorÄdami suprasti geriau. Ir iÅ¡ tiesÅ³, kai vaikinai pradeda analizuoti savo algoritmus, jums tiesiog padaryti tik tai. RÅ«Å¡iuoti akies obuolio jÅ«sÅ³ kodas ir manau, apie - viskas gerai, aÅ¡ turiu Å¡Ä¯ kilpa Äia arba aÅ¡ turiu Ä¯dÄtos kilpos Äia tai ketinate daryti n dalykÅ³ n kartÅ³, ir jÅ«s galite rÅ«Å¡iuoti prieÅ¾asties savo keliÄ per kodÄ, net jei tai Pseudocode, o ne tikrasis kodas. 

Taigi, kÄ apie omega n kvadratu? Koks buvo algoritmas, kad geriausias atveju, vis dar buvo n kvadratu Å¾ingsniai? Taip? 

Auditorija: [nesigirdi]. 

Davidas Malan: Taigi pasirinkimas rÅ«Å¡iuoti. Kadangi Å¡ios problemos realiai sumaÅ¾ÄtÅ³ Ä¯ tai, kad vÄl, aÅ¡ neÅ¾inau, Radau dabartinÄ maÅ¾iausiÅ³ iki AÅ¡ patikrinti visus prakeiktus elementai. Taigi, omega, tarkim, n, mes tiesiog atÄjo su vienu. Ä®traukiama rÅ«Å¡iuoti. Jei sÄraÅ¡as atsitinka bÅ«ti rÅ«Å¡iuojami jau, geriausiu atveju mes tiesiog padaryti vienÄ praeiti pro jÄ¯, tuo momentu mes tikrai. Ir tada, kad galima teigti, yra linijinÄ, tikrai. 

KÄ apie omega 1? Kas, geriausiu atveju, gali trukti pastovus pakopÅ³ skaiÄius? Taigi linijinis paieÅ¡kos, jei jÅ«s tiesiog gauti pasisekÄ ir elementas jÅ«s ieÅ¡kote yra Ä¯ deÅ¡inÄ nuo sÄraÅ¡o pradÅ¾ios, jei tai, kur jÅ«s pradedate savo linijinis SankryÃ¾os Å¡io sÄraÅ¡o. 

Ir tai yra tiesa numeris dalykÅ³. PavyzdÅ¾iui, net dvejetainis paieÅ¡ka omega 1. Nes kÄ daryti, jei jums tikrai adyti pasisekÄ ir pliaukÅ¡telÄti-DAB viduryje JÅ«sÅ³ masyvas skaiÄius jÅ«s ieÅ¡kote? Taigi jÅ«s galite gauti pasisekÄ ten, taip pat. 

Tai vienas, galiausiai, omega n log n. Taigi n log n, mes nelabai kalbÄti apie dar, bet - 

Auditorija: Sujungti rÅ«Å¡iuoti? 

Davidas Malan: suliejimas rÅ«Å¡iuoti. Tai buvo paskutinÄ¯ kartÄ Ä®spÅ«dingos filmÄ, kur mes pasiÅ«lÄme, o mes parodÄme vizualiai, kad yra algoritmai. Ir sujungti tarsi tik vienas toks algoritmas, kuris iÅ¡ esmÄs yra greiÄiau nei kai kurie iÅ¡ Å¡iÅ³ kitÅ³ vaikinÅ³. TiesÄ sakant, sujungti trumpas yra ne tik geriausiu atveju n log n, blogiausiu Byla N log n. Ir kai jÅ«s turite Å¡Ä¯ sutapimas Omega ir didelis O yra tas pats? Mes iÅ¡ tikrÅ³jÅ³ gali apibÅ«dinti, kad tai, kas vadinama teta, nors tai Å¡iek tiek reÄiau. Bet tai tik reiÅ¡kia, dvi ribas, Å¡iuo atveju yra tas pats. 

Taigi sujungti rÅ«Å¡iuoti, kÄ tai tikrai skliautais mums? Na, prisimenu motyvacijÄ. Leiskite traukti dar vienÄ animacijÄ, kad mes ne paÅ¾velgti paskutinÄ¯ kartÄ. Tai vienas, pati idÄja, taÄiau tai Å¡iek tiek didesnis. Ir aÅ¡ ruoÅ¡iuosi eiti Ä¯ priekÄ¯ ir pabrÄÅ¾ti Pirmasis - mes turime Ä¯terpimo rÅ«Å¡iuoti virÅ¡uje, kairÄje, tada pasirinkimas rÅ«Å¡iuoti, burbulas rÅ«Å¡iuoti, kitÅ³ rÅ«Å¡iÅ³ pora - korpuso ir greitai - kad mes ne kalbÄjo apie, ir krÅ«va ir sujungti rÅ«Å¡iuoti. 

Taigi, bent pabandyti sutelkti savo akis trijÅ³ geriausiÅ³ Ä¯ kairÄ, tada Ä¯ sujungti rÅ«Å¡iuoti, kai aÅ¡ spustelÄkite tai Å¾alia rodyklÄ. Bet aÅ¡ tegul juos visus paleisti, tiesiog jums Ä¯vairovÄ jausmÄ, algoritmai, kurie egzistuoja pasaulyje. AÅ¡ ruoÅ¡iuosi leisti Å ios Ä¯sibÄgÄjimo vos kelias sekundes. Ir jei jums sutelkti savo akis - pasirinkti algoritmas, sutelkti dÄmesÄ¯ Ä¯ jÄ¯ tik s - jums pradÄti rodyti modelis, kad tai Ä¯gyvendinti. 

Sujungti rÅ«Å¡iuoti, praneÅ¡ime, yra padaryta. Heap rÅ«Å¡iuoti, greitai rÅ«Å¡iuoti, kriaukliÅ³ - todÄl atrodo, kad mes pristatÄ tris blogiausia algoritmai praÄjusiÄ savaitÄ. Bet tai gerai, kad mes Äia Å¡iandien paÅ¾velgti suliejimo rÅ«Å¡iuoti, kuris yra vienas iÅ¡ tuo lengviau tie yra paÅ¾velgti, net nors ji tikriausiai bus lenkimo jÅ«sÅ³ protas tik truputÄ¯. Äia mes matome, kiek daug pasirinkimas rÅ«Å¡iuoti sucks. 

TaÄiau atvirkÅ¡tinÄ pusÄ, tai tikrai lengva Ä¯gyvendinti. Ir gal P Set 3, tai viena iÅ¡ algoritmai JÅ«s pasirinkote Ä¯gyvendinti uÅ¾ standartinÄ versijÄ. Puikiai gerai, puikiai teisinga. 

Bet vÄl, kaip n tampa didelis, jei nusprÄsti Ä¯gyvendinti greiÄiau algoritmÄ kaip sujungti rÅ«Å¡iuoti, Å¡ansai yra didesni ir DidesnÄs sÄnaudos, jÅ«sÅ³ kodas yra tik ketina paleisti greiÄiau. JÅ«sÅ³ svetainÄ ketina dirbti geriau. JÅ«sÅ³ vartotojai bus laimingesni. Ir taip yra Å¡ie poveikiai faktiÅ¡kai suteikiant mums kai giliau minties. 

Taigi galime paÅ¾velgti, kas sujungti iÅ¡vaizdÄ rÅ«Å¡iuoti yra iÅ¡ tikrÅ³jÅ³ visi apie. The cool dalykas yra tai, kad sujungti rÅ«Å¡iuoti yra tik tai. Tai, vÄlgi, kÄ mes vadinami Pseudocode, Pseudocode bÅ«tybÄ LietuviÅ³-kaip sintaksÄ. Ir paprastumas yra rÅ«Å¡iuoti Ä¯spÅ«dingi. 

Taigi ant Ä¯vesties n elementÅ³ - taip, kad tiesiog reiÅ¡kia, Å¡tai masyvas. Jis gavo n dalykÅ³ Ä¯ jÄ¯. Tai viskas, kÄ sakote ten. 

Jei n yra maÅ¾esnis nei 2, grÄ¯Å¾ti. Taigi, tai tik nereikÅ¡mingas atvejis. Jei n yra maÅ¾esnis nei 2, tada, Å¾inoma, ji yra 1 arba 0, tokiu atveju dalykas jau surÅ«Å¡iuotus arba neegzistuoja, tad tiesiog grÄ¯Å¾ti. NÄra nieko daryti. Å tai paprastas bylÄ roviau. 

Kitur, mes turime tris veiksmus. RÅ«Å¡iuoti kairÄje pusÄje, elementÅ³, rÅ«Å¡iavimo DeÅ¡inÄ pusÄ iÅ¡ elementÅ³, ir tada sujungti surÅ«Å¡iuoti puses. Kas Ä¯domu, kad Äia yra AÅ¡ tipo punting, tiesa? Yra rÅ«Å¡ies apskrito apibrÄÅ¾imo Å¡Ä¯ algoritmÄ. Kokia prasme tai algoritmo raiÅ¡kos apskritas? 

Auditorija: [nesigirdi]. 

Davidas Malan: Taip, mano rÅ«Å¡iavimo algoritmas, du jos Å¾ingsniai yra "rÅ«Å¡iuoti kaÅ¾kas. "Ir taip, kad kyla klausimas, gerai, kÄ aÅ¡ ketinate naudoti rÅ«Å¡iuoti kairÄ pusÄ ir Ä¯ deÅ¡inÄ pusÄ? Ir groÅ¾is Äia yra tai, kad nors VÄlgi, tai yra proto-lenkimo dalis potencialiai, galite naudoti tÄ patÄ¯ algoritmas rÅ«Å¡iuoti kairÄ pusÄ. 

Bet palauk. Kai jÅ«s pasakojo rÅ«Å¡iuoti kairÄ pusÄ, kas yra du veiksmai bus toliau? Mes rÅ«Å¡iuoti kairÄ pusÄ kairÄje pusÄje, ir deÅ¡inÄje pusÄ kairÄje pusÄje. Velnias, kaip man sutvarkyti tuos du pusÄs arba ketvirÄiai, o dabar? 

Bet tai gerai. Mes turime rÅ«Å¡iavimo algoritmÄ Äia. Ir nors jums gali nerimauti ne pirmas tai rÅ«Å¡ies begalinis kilpa, tai ciklas, kad niekada ketina baigti - ji ketina baigsis tada, kai kas atsitiks? Kai n yra maÅ¾iau nei 2. Kuris galiausiai nutiks, nes jei jÅ«s nuolat perpus sumaÅ¾inti ir perpus sumaÅ¾inti per pusÄ sumaÅ¾inti Å¡ias puses, be abejo, galÅ³ gale jÅ«s ketinate baigti iki vos 1 arba 0 elementus. Kuriuo Å¡is algoritmas sako viskas. 

Taigi reali magija tai algoritmas atrodo, kad galutinis Å¾ingsnis, sujungimo. Tai paprasta idÄja tiesiog sujungti du dalykÅ³, tai, kas galiausiai bus leisti mums rÅ«Å¡iuoti masyvas, tarkim, aÅ¡tuonis elementus. Taigi turiu aÅ¡tuonis daugiau streso kamuoliukus iki Äia aÅ¡tuoniÅ³ popieriaus lapÅ³, ir vienas "Google" Stiklas - kuris man iÅ¡saugoti. 

[Juokas] 

Davidas Malan: Jei mes galime imtis aÅ¡tuoniÅ³ savanoriai, ir paÅ¾iÅ«rÄkime, jei mes galime Å¾aisti Å¡Ä¯, ir todÄl. Oho, Gerai. KompiuteriÅ³ mokslas vis Ä¯domus. Gerai. Taigi, kaip apie jus tris, DidÅ¾iausias ranka ten. Keturi iÅ¡ nugaros. Ir kaip apie mes padarysime jus trys Å¡ios eilutÄs? Ant priekinÄs keturis. Taigi jÅ«s aÅ¡tuoneri, ateiti iki. 

[Juokas] 

Davidas Malan: AÅ¡ iÅ¡ tikrÅ³jÅ³ neÅ¾inote, kas tai yra. Ar tai stresas kamuoliukai? Stalo lempos? MedÅ¾iaga? Interneto? 

Gerai. Taigi atÄjo iki. Kas norÄtÅ³ - nuolat artÄja. PaÅ¾iÅ«rÄkime. Ir tai kelia jums vietoje - esate vietoje vienos. Uh-Oh, wait a minute. 1, 2, 3, 4, 5, 6, 7 - O, gerai. Gerai, mes geri. Gerai, kad kiekvienas turi savo vietÄ, bet ne "Google" stiklo. Leiskite man Ä¯ eilÄ Å ie padidintos. Koks tavo vardas? 

MICHELLE: Michelle. 

Davidas Malan: Michelle? Gerai, jums atrodys Geek, jei tai Gerai. Na, aÅ¡ taip pat manau, tik akimirkÄ. Viskas gerai, laukimo. Mes jau bando sugalvoti naudojimo atveju "Google Stiklas ir mes maniau, kad bÅ«tÅ³ smagu tiesiog tai, kai Å¾monÄs ant scenos. Mes Ä¯raÅ¡ysime pasaulÄ¯ iÅ¡ savo perspektyvos. Gerai. Ne tikriausiai, kÄ "Google paskirtÄ¯. Gerai, jei jÅ«s neprieÅ¡taraujate dÄvÄti ir ateinanÄius nepatogios minuÄiÅ³, kad bÅ«tÅ³ nuostabu. 

Gerai, kad mes turime Äia masyvas elementai, ir kad masyvo, pagal popieriaus gabaliukÅ³ Å¡iÅ³ Å¾moniÅ³ " rankas, Å¡iuo metu nerÅ«Å¡iuotos. 

MICHELLE: O, kad taip keistai. 

Davidas Malan: Tai gana daug atsitiktinai. Ir tik akimirkÄ, mes ketiname bandyti Ä¯gyvendinti sujungti rÅ«Å¡iuoti kartu ir pamatyti, kur tas raktas Ä¯Å¾valga. Ir triukas Äia suliejimo rÅ«Å¡iuoti yra kaÅ¾kas, kad mes ne prielaida dar. Mes iÅ¡ tikrÅ³jÅ³ reikia Å¡iek tiek papildomos vietos. Taigi, kas bus ypaÄ Ä¯domu tai, kad Å¡ie vaikinai ketinate judÄti maÅ¾ai tiek, nes aÅ¡ ruoÅ¡iuosi daryti prielaidÄ, kad ten papildomai masyvas erdvÄje, pasakyti, tiesiai uÅ¾ jÅ³. 

Taigi, jei jie uÅ¾ savo kÄdÄ, tai antrinÄ masyvo. Jei jie sÄdi Äia, tai pagrindinis masyvo. Bet tai iÅ¡tekliÅ³, kad mes turime nenaudoja finansinio sverto iki Å¡iol su burbulas rÅ«Å¡iuoti, su atrankos rÅ«Å¡iuoti, su prieraÅ¡u rÅ«Å¡iuoti. Prisiminkite, praeitÄ savaitÄ, visi tik rÅ«Å¡ies iÅ¡maiÅ¡ytos vietoje. Jie nebuvo naudoti bet kokiÄ papildomÄ atmintÄ¯. Mes padarÄme vietos Å¾mones judanÄiÅ³ Å¾moniÅ³ aplink. 

Taigi tai yra pagrindinis Ä¯Å¾valgos, taip pat. Yra tai kompromisas, apskritai Ä¯ kompiuteriÅ³ mokslas, iÅ¡teklius. Jei norite pagreitinti kaÅ¾kÄ kaip laiko, jÅ«s ketinate turi mokÄti kainÄ. Ir vienas iÅ¡ Å¡iÅ³ kainÅ³ yra labai daÅ¾nai erdvÄ, atminties kiekis ar sunku diske, kad jÅ«s naudojate. Arba, tiesÄ sakant, suma programuotojas metu. Kiek laiko uÅ¾trunka jums, Å¾mogaus, realiai Ä¯gyvendinti Å¡iek tiek daugiau sudÄtingas algoritmas. Bet Å¡iandien, kompromisas yra laikas ir erdvÄ. 

Taigi, jei jus vaikinai gali tiesiog telpa jÅ«sÅ³ numerius, mes galime pamatyti, kad esate iÅ¡ tiesÅ³ suderinti 4, 2, 6, 1, 3, 7, 8. Puikus. Taigi, aÅ¡ ruoÅ¡iuosi pabandyti muzikinÄs dalykÅ³, jei jus vaikinai gali tik sekti mano pavyzdÅ¾iu Äia. 

Taigi, aÅ¡ ketina Ä¯gyvendinti, visÅ³ pirma, Pirmasis Å¾ingsnis pseudocode, kuris yra Ä¯ Ä¯vesties n elementÅ³, jei n maÅ¾iau nei 2, tada grÄ¯Å¾ti. Akivaizdu, kad nÄra taikoma, todÄl mes judÄti pirmyn. Taigi rÅ«Å¡iuoti kairÄje pusÄje, elementai. Taigi, tai reiÅ¡kia aÅ¡ norÄÄiau sutelkti dÄmesÄ¯ mano dÄmesys tik Ä¯ tai metu Keturi vaikinai Äia. Viskas gerai, kÄ aÅ¡ kitÄ daryti? 

Auditorija: RÅ«Å¡iuoti kairÄ pusÄ. 

Davidas Malan: Taigi, dabar turiu sutvarkyti kairÄ pusÄ Å¡iÅ³ vaikinai. Nes vÄl prisiimti sau Ä¯ tikslas rÅ«Å¡iuoti kairÄ pusÄ. Kaip tai padaryti? Tiesiog sekite instrukcijas, net nors mes darome jÄ¯ dar kartÄ. Taigi rÅ«Å¡iuoti kairÄ pusÄ. Dabar aÅ¡ rÅ«Å¡iavimo Å¡iuos du vaikinai. Kas toliau? 

Auditorija: RÅ«Å¡iuoti kairÄ pusÄ. 

Davidas Malan: RÅ«Å¡iuoti kairÄ pusÄ. Taigi, dabar jÅ³, Å¡i vieta Äia yra 1 dydÅ¾io sÄraÅ¡Ä. Ir kas tavo vardas? 

PRINCESS DAISY: princesÄ Daisy. 

Davidas Malan: princesÄ Daisy yra Äia. Ir taip ji jau rÅ«Å¡iuojamos, nes sÄraÅ¡as dydÅ¾io 1. KÄ man kitÄ daryti? Gerai, negrÄÅ¾inti, nes Å¡is sÄraÅ¡as yra 1 dydis, kuris yra maÅ¾iau nei 2. Tada kas sekantis Å¾ingsnis? Ir dabar jÅ«s turite rÅ«Å¡ies Atsitraukia savo mintis. 

RÅ«Å¡iuoti teisingÄ pusÄ, kuri yra - koks tavo vardas? 

LINDA: Linda. 

Davidas Malan: Linda. Ir taip, tai kÄ mes darome dabar, turime 1 dydÅ¾io sÄraÅ¡Ä? 

Auditorija: Atgal. 

Davidas Malan: Atsargiai. Mes vÄl pirmas, o dabar treÄioji Å¾ingsnis - ir jei aÅ¡ tipo vaizduoti jÄ¯ apimantis dvi vietas dabar, dabar aÅ¡ turi sujungti Å¡iuos du elementus. Taigi, dabar, deja, elementai yra ne iÅ¡ eilÄs. Bet tai kur sujungimo procesas pradeda gauti Ä¯tikinamos. 

Taigi, jei jus vaikinai gali atsistoti tik momentas, aÅ¡ ruoÅ¡iuosi reikia tavÄs, kad momentas, stiprindamas uÅ¾ savo kÄdÄs. O jei Linda, nes 2 yra maÅ¾esnis nei 4, kodÄl gi ne JÅ«s ateiti aplink pirmas? Ten pasilikti. Taigi Linda, jÅ«s ateiti aplink pirmas. 

Dabar iÅ¡ tikrÅ³jÅ³ jei tai tik matrica mes galime tiesiog perkelti jÄ realiu laiku iÅ¡ Å¡ios kÄdÄs Å¡ioje vietoje. Taigi, Ä¯sivaizduokite, kad paÄmÄ pastovus pakopÅ³ skaiÄius 1. O dabar - bet mes turime padÄti jums pirmoji vieta Äia. 

Ir dabar, jei gali ateiti aplink, kaip gerai, kad mes ketiname bÅ«ti vietoje dviejÅ³. Ir nors tai jauÄiasi tai atsiÅ¾velgiant Ä¯ laikÄ, kas malonu dabar kad kairÄ pusÄ kairÄje pusÄje, dabar rÅ«Å¡iuojamos. Taigi, kas buvo kitas Å¾ingsnis, jei mes dabar atgal toliau Ä¯ istorijÄ? 

Auditorija: DeÅ¡inÄ pusÄ. 

Davidas Malan: RÅ«Å¡iuoti tinkamÄ pusÄ. Taigi jus vaikinai tai padaryti, taip pat. Taigi, jei galite atsistoti tik akimirkÄ? Ir kas yra jÅ«sÅ³ vardas? 

JESS: Jess. 

Davidas Malan: Jess. Gerai, kad Jess dabar Ä¯ kairÄ pusÄ deÅ¡inÄje pusÄje. Ir taip ji dydÅ¾io 1 sÄraÅ¡as. Ji akivaizdÅ¾iai surÅ«Å¡iuoti. Ir tavo vardas? 

MICHELLE: Michelle. 

Davidas Malan: Michelle akivaizdÅ¾iai dydÅ¾io 1 sÄraÅ¡as. Ji jau sutvarkyti. Taigi dabar magija atsitiks, jungimosi procesÄ. Taigi, kas vyksta atÄjai, pirmas? Akivaizdu Michelle. Taigi, jei galite ateiti aplink atgal. ErdvÄ mes turime rasti jai dabar IÅ¡kart uÅ¾ Å¡ios kÄdÄ. Ir dabar, jei galÄtumÄte grÄ¯Å¾ti, taip pat, dabar mes turime, turi bÅ«ti aiÅ¡ku, du pusÄs, kiekvienas dydis 2 - ir tik vaizdavimas meilÄs, jei galÄtÅ³ Å¡iek tiek erdvÄje - vienas kairÄje pusÄ Äia vienas DeÅ¡inÄ pusÄ Äia. 

Atsukti toliau istorija. Kas Å¾ingsnis yra Å¡alia? 

Auditorija: Sujungti. 

Davidas Malan: Taigi dabar mes turime sujungti. Taigi Gerai, kad dabar, laimei, mes tiesiog atlaisvinti keturis kÄdÄs. Taigi mes naudojame dvigubai daugiau atminties, bet mes galime suteikti flip-flop'e tarp dvi matricas. Taigi, kuris skaiÄius yra atÄjai, pirmas? Taigi Michelle, Å¾inoma. Taigi ateiti aplink ir imtis JÅ«sÅ³ vieta Äia. Ir tada numeris 2 yra akivaizdÅ¾iai kitÄ, todÄl jÅ«s ateiti Äia. Numeris 4 numeris 6. Ir vÄl, nors ten Å iek tiek pÄsÄiÅ³jÅ³ dalyvauja, tikrai, tai gali Ä¯vykti akimirksniu, perkeldami vienÄ - Gerai, gerai grojo. 

[Juokas] 

Davidas Malan: O dabar mes gana geros formos. KairÄje pusÄje, visÄ Ä¯vesties jau rÅ«Å¡iuojamos. Gerai, kad Å¡ie vaikinai buvo iÅ¡ mano privalumas - kaip ji galÅ³ gale visus ant merginos Ä¯ kairÄ ir visi ant deÅ¡inÄs berniukai? 

Gerai, kad vaikinai "eilÄ dabar. Taigi aÅ¡ ne vaikÅ¡Äioti jus per Å¡iuos veiksmus. Mes pamatyti, jei mes galime iÅ¡ naujo pats Pseudocode. Jei norite eiti Ä¯ priekÄ¯ ir atsistoti, ir vaikinai, leiskite man duoti jums mikrofono. Å½r jeigu jÅ«s galite ne atkartoti tai, kÄ mes tiesiog padarÄ Äia kitas galas sÄraÅ¡o. Kas turi kalbÄti pirma, remiantis algoritmas? Taigi, paaiÅ¡kinti, kÄ darai prieÅ¡ jums jokiÅ³ pÄdÅ³ judesius. 

GARSIAKALBIS 1: Gerai, kad jau Esu kairÄ pusÄ kairÄje pusÄje, vÄl grÄ¯Å¡iu. TeisÄ? 

Davidas Malan: Geras. 

GARSIAKALBIS 1: Ir tada - 

Davidas Malan: Kas daro mic eiti toliau? 

GARSIAKALBIS 1 Kitas skaiÄius. 

SPEAKER 2: Taigi, aÅ¡ Ä¯ deÅ¡inÄ pusÄ iÅ¡ kairÄje pusÄje kairÄ pusÄ, ir aÅ¡ grÄ¯Å¾ti. 

Davidas Malan: Geras. GrÄ¯Å¡ite. Taigi dabar kas kitas uÅ¾ jus du? 

SPEAKER 2: Mes norime pamatyti, kas yra maÅ¾esnis. 

Davidas Malan: BÅ«tent. Mes norime sujungti. ErdvÄ mes ketiname naudoti sujungti jÅ«s Ä¯, nors jie Akivaizdu, surÅ«Å¡iuoti jau mes ketiname laikytis tos paÄios algoritmÄ. Taigi, kas eina atgal pirmiausia? Taigi 3, tada 7. Ir dabar mikrofono eina Å¡iÅ³ vaikinai, gerai? 

GARSIAKALBIS 3: Taigi, aÅ¡ Ä¯ deÅ¡inÄ pusÄ Ä¯ kairÄ pusÄ, o mano n yra maÅ¾esnis nei 1, todÄl aÅ¡ tik ketina perduoti - 

Davidas Malan: Geras. 

GARSIAKALBIS 4 AÅ¡ teisÄ pusÄ DeÅ¡inÄ pusÄ iÅ¡ deÅ¡inÄs pusÄs, ir aÅ¡ taip pat vienas asmuo, todÄl aÅ¡ ketina grÄ¯Å¾ti. Taigi dabar mes sulieti. 

GARSIAKALBIS 3: Taigi mes einame atgal. 

Davidas Malan: Taigi jÅ«s einate Ä¯ nugarÄ. Taigi 5 eina, tada 8. Ir dabar auditorijos, kuri yra Å¾ingsnis turime dabar atsukti atgal Ä¯ mÅ«sÅ³ protus? 

Auditorija: Sujungti. 

Davidas Malan: sujungimas kairÄje pusÄje, ir deÅ¡inÄje pusÄ pradinio kairÄ pusÄ. Taigi dabar - ir tiesiog padaryti tai aiÅ¡ku, padaryti Å¡iek tiek vietos tarp jÅ«sÅ³ du vaikinai. Taigi dabar, kad yra du sÄraÅ¡ai, kairÄ ir deÅ¡inÄ. Taigi, kaip mes dabar sujungti jus vaikinai Ä¯ priekinÄ sÄdyniÅ³ eilÄ naujo? 

3 eina pirma. Tada 5, Å¾inoma. Tada 7, o dabar 8. Gerai, dabar mes esame? 

Auditorija: Neatlikta. 

Davidas Malan: Ne padaryti, nes be abejo, yra vienas Å¾ingsnis liko. Bet vÄl, todÄl aÅ¡ naudoju tai Å¾argonas kaip "atsukti savo mintis", tai todÄl, kad tikrai kas vyksta. Mes ketiname per visus Å¡iuos veiksmus, bet mes tarsi pristabdÄ momentas, nardymas giliau Ä¯ algoritmas, pristabdÄ for a moment, nardymas giliau Ä¯ algoritmÄ ir dabar mes turime rÅ«Å¡iuoti atsukti mÅ«sÅ³ protus ir atÅ¡aukti visÅ³ Å¡iÅ³ sluoksniÅ³ kad mes tarsi uÅ¾laikomas. 

Taigi dabar mes turime du sÄraÅ¡us dydÅ¾io 4. Jei vaikinai galÄtÅ³ atsistoti paskutinÄ¯ kartÄ ir padaryti daug diske Äia aiÅ¡kiai nurodyti, kad tai yra kairÄje pusÄ originalus, DeÅ¡inÄ pusÄ iÅ¡ originalo. Kas pirmas skaiÄius, kad mes reikia traukti Ä¯ nugarÄ? Michelle, Å¾inoma. 

Taigi, mes Ä¯dÄti Michelle Äia. Ir kas yra skaiÄius 2? Numeris 2 ateina atgal taip pat. Numeris 3? Puikus. Numeris 4 numeris 5 numeris 6 numeris 7 ir skaiÄius 8. 

Gerai, kad ji jautÄsi kaip daug Å¾ingsniÅ³, tikrai. Bet dabar paÅ¾iÅ«rÄkime, jei mes negalime patvirtinti tarsi intuityviai, kad Å¡is algoritmas iÅ¡ esmÄs, ypaÄ n bus tikrai didelis, kaip matÄme su animacija, yra iÅ¡ esmÄs greiÄiau. Taigi galiu reikalauti Å¡Ä¯ algoritmÄ, kad blogiausia atveju ir net geriausiu atveju, yra didelis O n kartÅ³ log n. Tai yra, ten kai Å¡is aspektas algoritmas, kuris trunka n Å¾ingsniÅ³, taÄiau yra ir kitas aspektas kaÅ¾kur kad iteracija, kad apsisukimo, kad trunka log n Å¾ingsniÅ³. Mes galime Ä¯dÄti mÅ«sÅ³ pirÅ¡tu, kÄ tie du skaiÄiai omenyje? Na, kur - where'd mikrofono eiti? 

GARSIAKALBIS 1: Ar prisijungti, kad n nesilaikantiems mus Ä¯ dvi - padalijus iÅ¡ dviejÅ³, iÅ¡ esmÄs. 

Davidas Malan: BÅ«tent. Bet kuriuo metu mes matome, bet algoritmas taigi kas ten buvo tai modelis dalijimas, dalijimas, dalijant. Ir tai paprastai sumaÅ¾inama Ä¯ kaÅ¾kÄ, kad logaritminÄ, prisijunkite bazÄ 2. Bet tai tikrai galÄjo bÅ«ti bet kas, bet prisijungti bazÄ 2. 

Dabar kÄ apie n? Matau, kad mes tipo suskirstyti jus vaikinai - suskirstyti jus, padalintas jums, suskirstyti jus, padalintas jums. Kur atÄjo galas iÅ¡? 

Taigi tai sujungti. Kadangi apie tai galvoti. Jei sujungti aÅ¡tuonis Å¾mones, kai pusÄ iÅ¡ jÅ³ yra keturiÅ³ rinkinys ir kita pusÄ yra vienas nustatyti iÅ¡ keturiÅ³, kaip tu apie tai sujungti? Na, vaikinai padarÄ gana intuityviai. 

Bet jei aÅ¡, o ne tai padarÄ Å¡iek tiek daugiau metodiÅ¡kai, aÅ¡ galÄjo nurodÄ kairiausias asmuo pirmÄ kartÄ su mano kairÄ Kita vertus, nurodÄ kairiausias asmeniui tos su mano deÅ¡inÄje pusÄje, ir tik vÄliau perÄjau sÄraÅ¡as, nurodant bent maÅ¾iausio elemento kiekvienÄ kartÄ, juda mano pirÅ¡tu per ir per kiek reikia visÄ sÄraÅ¡Ä. Bet kas svarbiausia apie tai sujungti procesas yra aÅ¡ Palyginus Å¡ias poras elementÅ³. IÅ¡ deÅ¡inÄs pusÄs ir iÅ¡ kairÄs pusÄ, aÅ¡ nÄ karto atsitraukia. 

Taigi sujungti pati imasi ne daugiau kaip n Å¾ingsniÅ³. Ir kiek kartÅ³ padarÄ Turiu padaryti, kad sujungus? Na, ne daugiau nei n, ir mes tiesiog pamatÄ, kad su galutiniu suliejimo. Ir todÄl, jei jÅ«s kÄ nors, kad mano log n Å¾ingsniÅ³ n kartÅ³, arba atvirkÅ¡Äiai, jis ketina duoti mums n kartÅ³ log n. 

Ir kodÄl tai yra geriau? Na, jei mes jau Å¾inome, kad Å¾urnalÄ n yra geriau nei n - tiesa? Mes matÄme dvejetainÄje paieÅ¡kÄ, telefono knyga PavyzdÅ¾iui, log n tikrai buvo geriau nei tiesinis. Taigi, tai reiÅ¡kia n kartÅ³ log n yra tikrai geriau nei n kartÅ³ kitÄ n AKA n kvadratu. Ir tai, kÄ mes galiausiai jaustis. 

Taigi didelis audringi plojimai, jei galÄtume, Å¡iÅ³ vaikinai. 

[Plojimai] 

Davidas Malan: Ir jÅ«sÅ³ atsisveikinimo dovanos - galite iÅ¡saugoti numerius, jei norÄtumÄte. Ir tavo atsisveikinimo dovana, kaip Ä¯prasta. Oh, ir mes atsiÅ³sime Jums filmuota medÅ¾iaga Michelle. AÄiÅ«. Gerai. PadÄti sau streso kamuolys. 

Ir leiskite man atsigriebti, tuo tarpu, mÅ«sÅ³ draugas Robas Bowden ir pasiÅ«lyti Å¡iek tiek kitoks poÅ¾iÅ«ris Ä¯ tai, nes jÅ«s galite galvoti apie tai veiksmai vyksta Å¡iek tiek kitaip. TiesÄ sakant, steigti, kas Rob apie parodyti mums, daroma prielaida, kad mes jau padaryta dalijant sudaro didelis sÄraÅ¡as Ä¯ aÅ¡tuonias maÅ¾Å³ sÄraÅ¡us, kiekvieno dydÅ¾io 1. 

Taigi, mes keiÄiasi pseudocode truputÄ¯ tik rÅ«Å¡iuoti gauti ne pagrindinÄ idÄja, kaip sujungti darbus. Bet vaÅ¾iavimo laikas, kÄ jis apie tai dar bus tas pats. Ir vÄl steigti Äia yra tai, kad jis prasidÄjo aÅ¡tuoniÅ³ sÄraÅ¡us dydis 1. Taigi jÅ«s praleidote dalÄ¯, kur jis iÅ¡ tikrÅ³jÅ³ padaryta log n, log n, log n dalijant iÅ¡ Ä¯vesties. 

[VIDEO PLAYBACK] 

-Å tai ir viskas uÅ¾ Å¾ingsnio. DÄl antro Å¾ingsnio, pakartotinai sujungti porÅ³ sÄraÅ¡us. 

Davidas Malan: Hm. Tik garso artÄja iÅ¡ mano kompiuterio. Pabandykime dar kartÄ. 

-Tiesiog savavaliÅ¡kai pasirinkti, kuris - dabar mes turime keturis sÄraÅ¡us. SuÅ¾inokite anksÄiau. 

Davidas Malan: Äia mes eiti. 

-Sujungimas 108 ir 15 straipsnius, mes galÅ³ su sÄraÅ¡as 15 108. Sujungus 50 ir 4, mes baigti su 4, 50. Sujungimas 8 ir 42 straipsnius, mes baigti su 8, 42. Ir sujungti 23 ir 16 straipsniuose, mes baigti su 16, 23. 

Dabar visi mÅ«sÅ³ sÄraÅ¡uose yra 2 dydÅ¾io. Atkreipkite dÄmesÄ¯, kad kiekviena keturi sÄraÅ¡ai yra rÅ«Å¡iuojama. Taigi, mes galime pradÄti sujungti porÅ³ sÄraÅ¡us dar kartÄ. Sujungus 15 ir 108 4 ir 50, mes pirmiausia reikia 4, tada 15, tada 50, tada 108. Sujungimas 8, 42 ir 16, 23, mes pirmiausia reikia 8, tada 16, tada 23, tada 42. 

Taigi dabar mes turime tik du sÄraÅ¡us dydÅ¾io 4, iÅ¡ kuriÅ³ kiekvienas yra rÅ«Å¡iuojama. Taigi dabar mes sujungti Å¡iuos du sÄraÅ¡us. Pirma, mes imame 4, tada mes 8, tada mes priimsime 15, tada 16, tada 23, tada 42, tada 50, tada 108. 

[PABAIGA VIDEO PLAYBACK] 

Davidas Malan: VÄlgi, praneÅ¡imas, jis niekada palietÄ tam tikrÄ taurÄ daugiau nei vienÄ kartÄ po priekÄ¯ uÅ¾ jos ribÅ³. Taigi jis niekada kartoti. Taigi, jis visada juda Ä¯ Å¡onÄ, ir tai, kur mes turime mÅ«sÅ³ n. 

KodÄl gi ne leiskite man atsigriebti vienÄ animacijÄ kad mes matÄme anksÄiau, bet Å¡Ä¯ kartÄ skirta tik suliejimo rÅ«Å¡iuoti. Leiskite man eiti Ä¯ priekÄ¯ ir priartinti ir apie tai Äia. Pirmiausia leiskite man pasirinkti atsitiktinÄ Ä¯vestÄ¯, paaÅ¡trins, ir jÅ«s galite rÅ«Å¡iuoti pamatyti kÄ mes paÄmÄ uÅ¾ suteiktas, anksÄiau, sujungti tarsi iÅ¡ tikrÅ³jÅ³ daro. 

Taigi, pastebÄsite, kad jÅ«s gaunate Å¡ias puses arba Å¡ie ketvirÄiais arba jÅ³ aÅ¡tuoniÅ³ iÅ¡ problema, kad visi staiga pradÄti imtis geros formos. Ir galiausiai, kaip matote ne labai pabaiga, kad bam viskas sujungta kartu. 

Taigi tai yra tik trijÅ³ skirtingÅ³ Ä¯gauna tÄ paÄiÄ idÄjÄ. Bet svarbiausia Ä¯Å¾valga, kaip ir atskirties ir uÅ¾kariauti paÄioje pirmoje klasÄje, buvo ta, kad mes nusprendÄme kaÅ¾kaip padalinti Ä¯ kaÅ¾kÄ didelis, Ä¯ problema kaÅ¾kas tarsi identiÅ¡ki dvasia, bet maÅ¾esni ir maÅ¾esni ir maÅ¾esni ir maÅ¾esnis. 

Dabar dar vienas Ä¯domus bÅ«das rÅ«Å¡iuoti mano, apie tai, nors tai nÄra norÄÄiau duoti jums tÄ patÄ¯ intuityvus supratimas, yra taip animacija. Taigi tai yra vaizdo Ä¯dÄti kÄ nors kartu kad susijÄs skiriasi garsai, turintys Ä¯vairiÅ³ operacijÅ³ Ä¯terpimo rÅ«Å¡iuoti, uÅ¾ suliejimo rÅ«Å¡iuoti, ir dÄl kitÅ³ pora. Taigi vienu metu, aÅ¡ ketina hit Atkurti. Tai apie minuÄiÅ³ ilgio. Ir net jei jÅ«s vis dar galite pamatyti modeliai vyksta, Å¡iuo metu galite taip pat iÅ¡girsti, kaip Å¡ie algoritmai atlieka skirtingai ir Å¡iek tiek skirtingi modeliai. 

Tai Ä¯terpimo rÅ«Å¡iuoti. 

[TONES PLAYING] 

Davidas Malan: Jis vÄl bando Ä¯terpti kiekvienÄ elementÄ Ä¯ kur jis priklauso. Tai burbulas rÅ«Å¡iuoti. 

[TONES PLAYING] 

Davidas Malan: Ir jÅ«s galite rÅ«Å¡iuoti jaustis kaip santykinai maÅ¾ai dirbti jis daro ant kiekvieno Å¾ingsnio. Tai, kÄ MonotoniÅ¡ka skamba. 

[TONES PLAYING] 

Davidas Malan: Tai pasirinkimas rÅ«Å¡iuoti, kur mes pasirinkite elementÄ norime pagal iÅ¡gyvena vÄl ir vÄl ir vÄl ir pradÄti jÄ¯ iÅ¡ pradÅ¾iÅ³. 

[TONES PLAYING] 

Davidas Malan: tai sujungti rÅ«Å¡iuoti, kuris tikrai galite pradÄti jaustis. 

[TONES PLAYING] 

[Juokas] 

Davidas Malan: KaÅ¾kas vadinamas gnome rÅ«Å¡iuoti, kurÄ¯ mes ne paÅ¾velgÄ. 

[TONES PLAYING] 

Davidas Malan: Taigi leiskite man pamatyti, kad dabar, iÅ¡siblaÅ¡kÄs, kaip jums tikiuosi, yra iÅ¡ muzikos, jei aÅ¡ galiu slydimo maÅ¾ai tiek matematikos Äia. Taigi, Äia yra ketvirtas bÅ«das, kad mes galime galvoti apie tai, kÄ reiÅ¡kia Å¡ie funkcijas, kurios bus greiÄiau nei tie, kad mes matÄme anksÄiau. Ir jei jÅ«s dar tuo metu iÅ¡ matematika fone, jÅ«s iÅ¡ tikrÅ³jÅ³ Å¾ino, galbÅ«t jau, kad jÅ«s gali slap terminÄ nuo Å¡io metodo - bÅ«tent rekursija, funkcija kad kaÅ¾kaip save vadina. 

Ir vÄl priminti, kad suliejimo rÅ«Å¡iuoti Pseudocode buvo pakartotinÄ ta prasme, kad vienas iÅ¡ Merge sort Å¾ingsnius buvo paraginti rÅ«Å¡iuoti - tai yra pati. Bet, laimei, nes mes nuolat raginama rÅ«Å¡iuoti, arba sujungti rÅ«Å¡iuoti, Tiksliau, Ä¯ maÅ¾esnes ir maÅ¾esniÅ³ sÄraÅ¡as, mes galiausiai dugnÄ dÄka kÄ mes vadiname bazinÄ¯ scenarijÅ³, sunkiai koduojamÅ³ atvejis, sakÄ, kad jei sÄraÅ¡as yra maÅ¾as, maÅ¾iau nei 2 Tokiu atveju, tiesiog grÄ¯Å¾ti iÅ¡ karto. Jei mes ne turÄti, kad ypatingas atvejis, algoritmas niekada iÅ¡ apaÄios, ir jÅ«s iÅ¡ tikrÅ³jÅ³ gauti Ä¯ begalinis ciklas tikrai amÅ¾inai. 

Bet tarkime, kad mes norÄjome dabar Ä¯dÄti keletas patarimÅ³, tai numeriai, vÄlgi, naudojant n kaip Ä¯Äjimo dydÅ¾io. Ir aÅ¡ norÄjau paklausti, kas bendras laikas dalyvauja veikia suliejimo rÅ«Å¡iuoti? Ar apskritai kas jos sÄnaudos metu? 

Na tai gana lengva pamatuoti. Jei n yra maÅ¾esnis nei 2 metu dalyvauja rÅ«Å¡iavimo n elementÅ³, kur n yra 2, yra 0. Kadangi mes tiesiog grÄ¯Å¾ti. NÄra nuveikti. Dabar tikriausiai, o gal tai vienas Å¾ingsnis ar du Å¾ingsniai iÅ¡siaiÅ¡kinti sumÄ dirbti, bet tai pakankamai arti 0, kad AÅ¡ tik ketina pasakyti "ne" darbas bÅ«tinas, jei sÄraÅ¡as yra toks maÅ¾as, bÅ«ti neÄ¯domu. 

TaÄiau Å¡is atvejis Ä¯domus. Rekursywny byla buvo filialas Pseudocode tai sakÄ kitur, tarsi kairÄ pusÄ, rÅ«Å¡iuoti teisÄ pusÄ, sujungti dvi dalis. Dabar kodÄl Å¡i iÅ¡raiÅ¡ka atstovauja tai sÄskaita? Na, T n tiesiog reiÅ¡kia, laikas rÅ«Å¡iuoti n elementÅ³. Ir tada deÅ¡inÄje pusÄje lygybÄs Å¾enklÄ ten, n T suskirstyti pagal 2 nuoroda Ä¯ kokia kaina? RÅ«Å¡iavimas kairÄ pusÄ. Kitas T n dalijamas iÅ¡ 2 matyt, nuoroda Ä¯ iÅ¡laidÅ³ rÅ«Å¡iuoti tinkamÄ pusÄ. 

Ir tada plius n? Ar sujungus. Nes jei jÅ«s turite du sÄraÅ¡us, vienas iÅ¡ dydis n per 2 ir kitas dydis n per 2, turite iÅ¡ esmÄs paliesti kiekvienas iÅ¡ Å¡iÅ³ elementÅ³, kaip Rob palietÄ kiekvienÄ puodeliai, ir tik kaip paÅ¾ymÄjome kiekviename savanoriai scenoje. Taigi n yra sujungti sÄskaita. 

Dabar, deja, Å¡i formulÄ taip pat pati pakartotinÄ. Taigi, jei uÅ¾davÄ klausimÄ, jei n yra, tarkim, 16, jei yra 16 Å¾moniÅ³ scenoje arba 16 puodeliai vaizdo, kiek iÅ¡ viso Å¾ingsniai uÅ¾trunka juos surÅ«Å¡iuoti su suliejimo rÅ«Å¡iuoti? Tai iÅ¡ tikrÅ³jÅ³ nÄra akivaizdu, atsakymas, nes dabar jÅ«s turite rÅ«Å¡iuoti rekursyviai atsakyti Ä¯ Å¡Ä¯ formulÄ. 

Bet tai gerai, nes leiskite man pasiÅ«lyti kad mes atlikite Å¡iuos veiksmus. Å iuo metu dalyvauja rÅ«Å¡iuoti 16 Å¾moniÅ³ arba 16 puodeliai ketina atstovauti paprastai kaip T 16. Bet tai lygu pagal mÅ«sÅ³ Ankstesnis formulÄ, 2 kartus suma laiko uÅ¾trunka rÅ«Å¡iuoti 8 puodeliai plius 16. Ir vÄl, plius 16 yra laikas sujungti, ir du kartus T 8 yra laikas rÅ«Å¡iuoti kairÄ pusÄ ir Ä¯ deÅ¡inÄ pusÄ. 

Bet vÄl, tai nÄra pakankamai. Mes turime pasinerti giliau. Tai reiÅ¡kia, kad mes turime atsakyti klausimas, kas tai yra "T 8? Na T 8 yra tik 2 kartÅ³ T 4 plius 8. Na, kas T 4? T 4 yra tik 2 kartus t 2 plius 4. Na, kas T 2? T 2 "yra vos 2 kartus T 1 plius 2. 

Ir vÄl mes natÅ«ra gauti Ä¯strigo Å¡io ciklo. Bet tai apie pataikyti, kad vadinamasis bazinÄ¯ scenarijÅ³. Nes tai, kas yra T 1, tai mes reikalauti? 0. Taigi dabar, pagaliau, galime dirbti atgal. 

Jei T 1 yra 0, aÅ¡ dabar gali eiti atgal dar vienÄ iÅ¡sirikiuoti Å¡is vaikinas Äia, ir aÅ¡ galiu prijunkite 0, kai t 1. Taigi, tai reiÅ¡kia, kad ji yra lygi 2 kartus nulis, kitaip Å¾inomas kaip 0, plius 2. Ir kad visa iÅ¡raiÅ¡ka 2. 

Dabar, jei aÅ¡ su 2 T, kurio atsakymas yra 2, prijunkite jÄ¯ prie vidurio linijos, T 4, kuris suteikia man 2 kartus 2 plius 4, todÄl 8. Jei aÅ¡ tada prijungti 8 iki ankstesnio linija, kuri suteikia man 2 kartus 8, 16. Ir jei mes tÄskite, kad su 24, pridedant 16, mes pagaliau gauti vertÄ 64. 

Dabar, kad ir pati tarsi kalba nieko n Å¾ymÄjimÄ, DidelÄs O, omega, kad mes buvo kalbama apie. TaÄiau paaiÅ¡kÄja, kad 64 yra iÅ¡ tiesÅ³ 16, Ä¯Äjimas, dydis, prisijungti 16 2 bazÄ. Ir jei tai yra Å¡iek tiek susipaÅ¾inÄ, tiesiog prisiminkite, ir jis bus grÄ¯Å¾ti jums galÅ³ gale. Jei tai Å¾urnalas bazÄ 2, tai kaip 2 pakeltas, kas suteikia jums 16? O, tai 4, todÄl 16 kartÅ³ 4. 

Ir vÄl, tai ne baisi, jei tai yra tarsi miglotos atminties dabar. Bet dabar, imtis tikÄjimo kad 16 log 16 vertÄ yra 64. Ir taip iÅ¡ tiesÅ³, su Å¡ia paprasta sveiko proto patikrinti, mes patvirtino - bet neÄ¯rodÄ oficialiai - kad veikimo laikas suliejimÄ rÅ«Å¡iuoti yra iÅ¡ tiesÅ³ n log n. 

Taigi nÄra blogai. Tai tikrai geriau nei algoritmai mes matÄme iki Å¡iol, ir tai todÄl, kad mes pagausÄtÅ³, viena, technika vadinama rekursija. Bet Ä¯domesnis nei, kad sÄvoka dalijant ir uÅ¾kariauja. VÄlgi, tikrai savaitÄ 0 stuff, kad net ir dabar yra pasikartojimo daugiau Ä¯tikinamÅ³ bÅ«du. 

Dabar Ä¯domus maÅ¾ai pratimÅ³, jei jÅ«s niekada tai padarÄ - ir jÅ«s tikriausiai neturÄs, nes tarsi normalu Å¾moniÅ³ neturi galvoti kaip tai padaryti. Bet jei aÅ¡ einu Ä¯ google.com ir, jei Noriu suÅ¾inoti kÄ nors apie rekursija, Enter. 

[Juokas] [Daugiau juokas] Davidas Malan: Blogas pokÅ¡tas lÄtai plisti. [Juokas] Davidas Malan: Tik tuo atveju, tai ten. AÅ¡ ne aiÅ¡kiai tai negerai, ir ten pokÅ¡tas. Gerai. PaaiÅ¡kinti Å¾monÄms, Å¡alia tavÄs, jei ji ne visai paspaudÄte tik dar. Bet rekursija, apskritai, reiÅ¡kia su funkcija telefono proceso pati, ar apskritai dalijant problema Ä¯ kaÅ¾kÄ, kad gali bÅ«ti iÅ¡sprÄsta dalimis sprendÅ¾iant identiÅ¡kas atstovas problemos. 

Na, tegul perjungti pavaras tik akimirkÄ. Mes norÄtume uÅ¾baigti dÄl tam tikrÅ³ cliffhangers, todÄl galime pradÄti kurti etapas, keletÄ minuÄiÅ³, dÄl labai paprastÄ idÄjÄ - kad keiÄiant du elementus, tiesa? Visi Å¡ie algoritmai mes jau kalbame apie pastaruosius porÄ paskaitos Ä¯traukti kai kurie rÅ«Å¡iuoti Swapping. Å iandien ji buvo regimos juos gauti iki iÅ¡ savo kÄdÄs ir vaikÅ¡Äioti aplink, bet kodu, mes norÄtume tiesiog elementÄ iÅ¡ vieno masyvo ir pop jÄ¯ Ä¯ kitÄ. 

Taigi, kaip mes eiti apie tai daro? Na, leiskite man eiti Ä¯ priekÄ¯ ir raÅ¡yti Trumpa programa Äia. AÅ¡ ruoÅ¡iuosi eiti Ä¯ priekÄ¯ ir daryti tai kaip toliau. Tegul tai vadina - kÄ mes norime paraginti Å¡Ä¯ vienÄ? 

TiesÄ sakant, ne. Leiskite man atgal. AÅ¡ nenoriu to daryti Ä®spÅ«dingos filmÄ dar. Tai bus sugadinti Ä¯domus. Leiskite tai padaryti vietoj. 

Tarkime, kad aÅ¡ noriu raÅ¡yti maÅ¾ai programa ir kad dabar apima Å¡i idÄja rekursijos. I rÅ«Å¡ies gavo prieÅ¡ save ten. AÅ¡ ruoÅ¡iuosi atlikite Å¡iuos veiksmus. 

Pirma, greitai apima standartinÄs io.h, taip pat iÅ¡ cs50.h. apima Ir tada aÅ¡ ruoÅ¡iuosi eiti Ä¯ priekÄ¯ ir paskelbti int main negaliojanÄiu Ä¯prastu bÅ«du. Supratau, aÅ¡ misnamed failÄ, todÄl leiskite man tiesiog pridÄkite. c Papildomo Äia taip kad mes galime sudaryti tinkamai. PradÄti Å¡iÄ funkcijÄ iÅ¡jungti. 

Ir funkcija noriu raÅ¡yti, gana tiesiog, yra vienas, kad praÅ¡o vartotojas uÅ¾ skaiÄiÅ³ ir tada iÅ¡auga iki visi Ä¯moniÅ³ tarpusavio, kad numeriai skaiÄius ir, tarkim, 0. Taigi, pirmiausia aÅ¡ ruoÅ¡iuosi eiti Ä¯ priekÄ¯ ir paskelbti int n. Tada aÅ¡ nukopijuoti tam tikrÄ kodÄ, kad mes naudojame tam tikrÄ laikÄ. Nors kaÅ¾kas yra tiesa. AÅ¡ sugrÄ¯Å¡iu Ä¯ tÄ, akimirkÄ. 

KÄ norite daryti? Noriu pasakyti printf teigiamas sveikasis skaiÄius praÅ¡om. Ir tada aÅ¡ ruoÅ¡iuosi pasakyti n gauna gauti int. Taigi dar kartÄ, kai Standartiniai kodas kad mes naudojamas anksÄiau. Ir aÅ¡ ruoÅ¡iuosi tai padaryti o n yra maÅ¾esnis nei 1. Taigi tai bus uÅ¾tikrinta, kad vartotojo suteikia man teigiamÄ sveikÄjÄ¯ skaiÄiÅ³. 

Ir dabar aÅ¡ ruoÅ¡iuosi daryti toliau. Noriu pridÄti visus numerius nuo 1 iki ir n-arba 0 ir n analogiÅ¡kai, jei norite gauti bendrÄ sumÄ. Taigi didelis sigma simbolis kad jums gali prisiminti. Taigi, aÅ¡ ruoÅ¡iuosi tai padaryti pirmÄ skambuÄiams funkcija vadinama sigma, perduoti jÄ Ä¯ n, ir tada aÅ¡ ruoÅ¡iuosi pasakyti printf, atsakymas yra teisÄ ten. 

Taigi trumpai tariant, man ir int nuo naudotojo. AÅ¡ uÅ¾tikrinti, kad ji yra teigiamas. AÅ¡ pareiÅ¡kiu, kintamasis vadinamas atsakymas tipas int ir laikyti jÄ¯ grÄÅ¾inti vertÄ sigma, einanÄios n kaip Ä¯vestÄ¯. Ir tada aÅ¡ atsispausdinti Å¡Ä¯ atsakymÄ. 

Deja, nors sigma skamba kaip kaÅ¾kas, kad gali bÅ«ti math.h failas, jo deklaracija, tai tikrai ne. Taigi, kad viskas OK. Galiu Ä¯gyvendinti Å¡Ä¯ save. AÅ¡ ruoÅ¡iuosi Ä¯gyvendinti funkcija vadinama sigma, ir ji ketina imtis parametras - galime tik jÄ¯ vadiname m, tiesiog todÄl skiriasi. Ir tada Äia aÅ¡ ruoÅ¡iuosi pasakyti, Na, jei m yra maÅ¾esnis nei 1 - tai labai neÄ¯domu programÄ. Taigi, aÅ¡ ruoÅ¡iuosi eiti Ä¯ priekÄ¯ ir nedelsiant grÄÅ¾inti 0. Jis tiesiog nÄra prasmÄs pridÄti iki visÅ³ tarp 1 ir M Jei m numeriai pati 0 arba neigiamas. 

Ir tada aÅ¡ ruoÅ¡iuosi eiti Ä¯ priekÄ¯ ir tai labai iteracijÅ³. AÅ¡ ruoÅ¡iuosi padaryti Å¡Ä¯ senosios mokyklos rÅ«Å¡iuoti, ir aÅ¡ ruoÅ¡iuosi eiti Ä¯ priekÄ¯ ir pasakyti, kad aÅ¡ ruoÅ¡iuosi deklaruoti sumÄ 0. Tada aÅ¡ ruoÅ¡iuosi uÅ¾ linijos int - ir leiskite man tai padaryti geriau atitiktÅ³ mÅ«sÅ³ paskirstymo kodas, todÄl jÅ«s turite kopijÄ namuose. int i gauna 1 m iki i yra maÅ¾esnÄ arba lygi m. i plius plius. Ir tada viduje tai uÅ¾ linijos - Mes beveik ten - suma gauna sumÄ, taip pat 1. Ir tada aÅ¡ ruoÅ¡iuosi grÄ¯Å¾ti sumÄ. 

Taigi aÅ¡ tai greitai, visai tiesa. Bet vÄl, pagrindinÄ funkcija yra gana paprasta, grindÅ¾iamas kodÄ mes paraÅ¡yta iki Å¡iol. Naudoja dvigubÄ kilpÄ gauti teigiami int nuo naudotojo. Tada aÅ¡ praeiti int Ä¯ naujÄ funkcijÄ vadinama sigma, vadindami jÄ¯, vÄlgi, n. Ir aÅ¡ laikyti sugrÄ¯Å¾imo vertÄ, atsakymas iÅ¡ juodosios dÄÅ¾Äs metu Å¾inomas kaip sigma, kad kintamasis vadinamas atsakymas. Tada aÅ¡ spausdinti. 

Jei mes dabar tÄsti istorijÄ, kaip yra sigma Ä¯gyvendinti? SiÅ«lau Ä¯gyvendinti taip. Pirma, Å¡iek tiek KlaidÅ³ tikrinimas Ä¯sitikinti, kad vartotojo nÄra Messing su manimi ir einanÄios kai neigiamas arba 0 vertÄ. Tada aÅ¡ pareiÅ¡kiu, kintamasis vadinamas Apibendrinant ir nustatykite 0. 

Ir dabar aÅ¡ pradedu judÄti iÅ¡ I lygus 1 visÄ keliÄ iki ir Ä¯skaitant m, nes noriu Ä¯traukti visus skaiÄiai nuo vieno iki m imtinai. Ir viduje tai uÅ¾ linijos, aÅ¡ tiesiog padaryti suma gauna kokia ji yra dabar, plius I vertÄ. Plius i vertÄ. 

Kaip panaikinti, jei nemaÄiau tai anksÄiau, yra keletas sintaksinis cukrus Å¡ios eilutÄs. Galiu perraÅ¡yti kaip plius lygus i, tik sutaupyti sau keletÄ klaviÅ¡Å³ ir atrodo Å¡iek tiek auÅ¡intuvas. Bet tai ir viskas. Tai funkciÅ¡kai tas pats. 

Deja, Å¡is kodas Å³jÅ³ nesiruoÅ¡ia sudaryti dar. Jei aÅ¡ paleisti, kad sigma 0, kaip am AÅ¡ ketina gauti suÅ¡uko? Kas ji ketina nepatinka? 

Auditorija: [nesigirdi]. 

Davidas Malan: Taip, aÅ¡ nedeklaravo iki virÅ¡uje, deÅ¡inÄje funkcija? C rÅ«Å¡ies kvailas, nes jis tik kÄ pasakyti tai padaryti, ir jÅ«s turite tai padaryti tokia tvarka. Ir todÄl, jei aÅ¡ paspauskite Enter Äia, aÅ¡ ruoÅ¡iuosi gauti apie sigma Ä¯spÄjimas numanoma deklaracija. 

O ne problema. Galiu eiti Ä¯ virÅ¡Å³, ir aÅ¡ galiu sako, viskas gerai, palauk. Sigma yra funkcija, kuri grÄÅ¾ina int ir tikisi, int kaip pirkimo, kabliataÅ¡kiu. Ar galÄÄiau Ä¯dÄti visÄ funkcijÄ virÅ¡ pagrindinis, bet apskritai, aÅ¡ rekomenduojame prieÅ¡ tai, nes tai malonu visada pagrindinis virÅ¡uje tt galite pasinerti teisÄ ir Å¾inoti, kÄ programa daro skaitant pagrindinÄ sritis. 

Taigi dabar leiskite man iÅ¡valyti ekranÄ. Perdarytas sigma 0. Viskas atrodo patikrinti. Leiskite man paleisti sigma 0. Teigiamas kita. AÅ¡ duosiu jam numerÄ¯ 3 keep it simple. Taigi, kad turÄtÅ³ duoti man 3 plius 2 plius 1, taigi 6. Ä®veskite, ir iÅ¡ tiesÅ³ aÅ¡ gausiu 6. 

Galiu padaryti kaÅ¾kÄ daugiau - 50, 12, 75. Tiesiog kaip liestinÄ, aÅ¡ ruoÅ¡iuosi daryti kaÅ¾kÄ juokinga kaip tikrai didelis skaiÄius, O, kad faktiÅ¡kai dirbo - eh, aÅ¡ nemanau, kad tai tiesa. PaÅ¾iÅ«rÄkime. Leiskite tikrai netvarka su juo. 

Tai problema. Kas vyksta? Kodas nÄra taip blogai. Jis vis dar tiesinis. Å vilpimas yra geras poveikis, nors. Kas vyksta? 

NeÅ¾inote jei aÅ¡ girdÄjau jÄ¯. Taigi paaiÅ¡kÄja, - ir tai kaip panaikinti. Tai ne core idÄja rekursijos. Pasirodo, nes aÅ¡ bandau sudaro tokÄ¯ didelÄ¯ skaiÄiÅ³, dauguma greiÄiausiai jis bus klaidingai sprendimu C kaip nÄra teigiamas skaiÄius, bet neigiamas skaiÄius. 

Mes ne kalbÄjo apie tai, bet jis Pasirodo, yra neigiami skaiÄiai Ä¯ be pasaulio su teigiamais skaiÄiais. Ir bÅ«dus, kuriais galite sudaro neigiamÄ skaiÄiÅ³ iÅ¡ esmÄs yra, jÅ«s naudojate vienÄ Specialusis tiek nurodyti teigiami per neigiamas. Tai Å¡iek tiek sudÄtingesnis nei, kad bet tai pagrindinÄ idÄja. 

Taigi, deja, jei C painu vienÄ iÅ¡ tÅ³ tikrÅ³jÅ³ reiÅ¡kia bitai, Oh, tai yra neigiamas skaiÄius, mano kilpa Äia, pavyzdÅ¾iui, iÅ¡ tikrÅ³jÅ³ niekada ketina nutraukti. Taigi, jei aÅ¡ iÅ¡ tikrÅ³jÅ³ buvo spausdinti kaÅ¾kÄ vÄl ir vÄl, mes norÄtume pamatyti visÄ partijÄ. Bet vÄl, tai be taÅ¡ko. Tai tikrai tiesiog tarsi intelektinÄs smalsumas, kad mes ateis atgal Ä¯ ilgainiui. Bet dabar, tai yra teisinga Ä¯gyvendinimas, jei mes manome, kad vartotojo teiks Ints kad tilptÅ³ Ints. 

Bet aÅ¡ teigia, kad Å¡is kodas, tiesÄ sakant, gali bÅ«ti padaryta tiek daug paprastai. Jei po ranka tikslas praeiti kelios kaip m, pridÄti visi numeriai tarp jo ir 1 arba atvirkÅ¡Äiai nuo 1 ir, galiu reikalauti kad galiu pasiskolinti Å¡iÄ idÄjÄ, kad sujungti rÅ«Å¡iuoti turÄjo buvo atsiÅ¾velgiant problemÅ³ tokio dydÅ¾io ir dalinant Ä¯ kaÅ¾kÄ maÅ¾esnio. Gal ir ne pusÄ, bet maÅ¾esnis, taÄiau tipiniai pats. Pati idÄja, bet maÅ¾esnÄ problema. 

Taigi, aÅ¡ iÅ¡ tikrÅ³jÅ³ - leiskite man iÅ¡saugoti Å¡Ä¯ failÄ su kitu versijos numerÄ¯. Mes vadiname Å¡iÄ versijÄ 1 vietoj 0. Ir galiu reikalauti, kad aÅ¡ iÅ¡ tikrÅ³jÅ³ galite reimplement Å¡iÄ rÅ«Å¡ies proto-lenkimo bÅ«du. 

AÅ¡ ruoÅ¡iuosi palikti dalÄ¯ jai paÄiai. AÅ¡ ruoÅ¡iuosi pasakyti, jei m yra maÅ¾iau nei ar net lygi 0 - AÅ¡ tiesiog bus maÅ¾ai daugiau analinis Å¡Ä¯ kartÄ su mano klaidÅ³ tikrinimas - AÅ¡ ruoÅ¡iuosi eiti Ä¯ priekÄ¯ ir grÄ¯Å¾ti 0. Tai savavaliÅ¡kai. AÅ¡ tiesiog nusprÄsti, ar vartotojo man duoda neigiamÄ skaiÄiÅ³, aÅ¡ grÄ¯Å¾ti 0, ir jie turÄjo skaityti dokumentacija labiau. 

Kita - pastebÄsite, kÄ aÅ¡ ruoÅ¡iuosi daryti. Kita aÅ¡ grÄ¯Å¾ti m plius - kas yra sigma M? Na, sigma iÅ¡ m plius m Â± 1, plius minus m 2 plius minus 3 m. AÅ¡ nenoriu raÅ¡yti visi, kad iÅ¡. KodÄl ne aÅ¡ tiesiog kamuolio iÅ¡muÅ¡imas iÅ¡ rankÅ³? Rekursyviai vadina save su Å¡iek tiek maÅ¾esnÄ problema, kabliataÅ¡kis, ir vadina jÄ¯ dienÄ? 

TeisÄ? Dabar Äia taip pat galite jaustis ar nerimauti kad tai yra begalinis ciklas, kad aÅ¡ skatina, kai aÅ¡ Ä¯gyvendinant sigma iÅ¡kvietus sigma. Bet tai visiÅ¡kai gerai, nes aÅ¡ maniau priekÄ¯ pridÄta Ä¯ kurias eilutes? 

Auditorija: [nesigirdi]. 

Davidas Malan: 23 uÅ¾, 26 kuri mano, jei sÄlyga. Nes tai, kas yra malonu apie atimtis Äia, nes aÅ¡ nuolat dalijamos sigma maÅ¾esniÅ³ problemÅ³, maÅ¾esniÅ³ problemÅ³, maÅ¾esniÅ³ - tai ne pusÄ dydÅ¾io. Tai tik kÅ«dikis Å¾ingsnis maÅ¾esnis, bet tai gerai. Nes, galÅ³ gale, mes dirbti mÅ«sÅ³ keliÄ Å¾emyn iki 1 arba 0. Ir kai mes paspauskite 0, sigma nÄra ketinate skambinti save daugiau. Ji ketina nedelsiant grÄÅ¾inti 0. 

Taigi poveikis, jei tarsi vÄjas tai iki savo mintis, yra Ä¯traukti m plius m, atÄmus 1, plius minus 2 m, plius m atÄmus 3, plius taÅ¡kas, taÅ¡kas, taÅ¡kas, m, atÄmus m, galiausiai suteikia jums 0, ir poveikis yra galiausiai pridÄti visus Å¡ie dalykai kartu. Taigi, mes turime ne, su rekursija, iÅ¡sprÄsti problemÄ, kad mes negalÄjo iÅ¡sprÄsti anksÄiau. IÅ¡ tiesÅ³, portalo 0 to, ir kiekvienas problema iki Å¡iol buvo iÅ¡sprendÅ¾iamas tik su naudojate kilpomis arba kai kilpos arba panaÅ¡iÅ³ stato. 

Bet rekursija, aÅ¡ Manyti, suteikia mums kitaip galvoti apie problemos, kuriÄ, jei mes galime imtis problema, padalinkite jÄ¯ nuo kaÅ¾ko Å¡iek tiek didelis, Ä¯ kaÅ¾kÄ Å¡iek tiek maÅ¾esnis, galiu reikalauti, kad mes galime jÄ iÅ¡sprÄsti galbÅ«t Å¡iek tiek daugiau elegantiÅ¡kai poÅ¾iÅ«riu konstrukcijos, su maÅ¾iau kodÄ, o gal net sprÄsti problemas, kad bÅ«tÅ³ bÅ«ti sunkiau, nes mes galÅ³ gale pamatyti, sprendÅ¾iant grynai keletÄ kartÅ³. 

Bet Ä®spÅ«dingos filmÄ, kad aÅ¡ nori palikti mums buvo tai. Leiskite man eiti Ä¯ priekÄ¯ ir atidaryti iki failÄ iÅ¡ - TiesÄ sakant, leiskite man eiti ir tai padaryti labai greitai. Leiskite man eiti Ä¯ priekÄ¯ ir pasiÅ«lyti taip. Tarp Å¡iandienos kodas yra Å¡Ä¯ failÄ Äia. Tai vienas Äia noswap. 

Taigi tai yra kvailas maÅ¾ai programa, kuri AÅ¡ plakta kuri teigia, kad daryti taip. IÅ¡ esmÄs, ji pirmÄ kartÄ pareiÅ¡kia, LC vadinamas x ir priskiria jÄ¯ vertÄ 1. Tada jis pareiÅ¡kia, int y ir jam priskiria reikÅ¡mÄ 2. Tada jis spausdina, kÄ x ir y yra. Tada ji sako, Swapping, dot dot dot. 

Tada ji teigia bÅ«ti raginama funkcijÄ vadinama swap, einanÄios Ä¯ x ir m, idÄja yra tai, kad tikiuosi x ir y sugrÄ¯Å¡ skirtingi, prieÅ¡ingai. Tada ji teigia pavertÄ! su Å¡auktuku. Tada jis spausdina x ir y. 

TaÄiau paaiÅ¡kÄja, kad tai labai paprastas demonstravimo Å¾emyn Äia iÅ¡ tikrÅ³jÅ³ yra klaidÅ³. Nors aÅ¡ skelbiantis laikinas kintama ir laikinai iÅ¡leisti Ä¯ tai, tada aÅ¡ perskirstymo vertÄ b - kurie jauÄiasi suprantama, nes aÅ¡ iÅ¡gelbÄti iÅ¡ TEMP kopijÄ. Tada aÅ¡ atnaujinti b, lygios kokia buvo temp. Å is lukÅ¡tais Å¾aidimas juda rÅ«Å¡iuoti Ä¯ B And B Ä¯ naudojant Å¡Ä¯ vidutinio Å½mogus, vadinamas temperatÅ«ros jauÄiasi visiÅ¡kai pagrÄ¯sta. 

Bet aÅ¡ teigia, kad kai aÅ¡ paleisti Å¡Ä¯ kodas, kaip aÅ¡ tai padaryti dabar - leiskite man eiti Ä¯ priekÄ¯ ir Ä¯klijuokite jÄ¯ Äia. AÅ¡ vadinu tai noswap.c. Ir kaip rodo pavadinimas, tai nÄra bus teisinga programa. Padaryti noswap. / Ne sukeisti. x 1, y 2, Swapping, pavertÄ. x 1, y 2. Tai yra iÅ¡ esmÄs neteisinga, net nors tai atrodo puikiai protingas man. Ir yra prieÅ¾astis, bet mes ne ketina atskleisti prieÅ¾astis, tik dar. 

Nes dabar antrÄ Ä®spÅ«dingos filmÄ norÄjau palikti jus su tai, paskelbimas rÅ«Å¡iÅ³ apie kuponÅ³ kodÅ³. MÅ«sÅ³ naujovÄs pavÄluotÄ dienÅ³ Å¡iemet jau iÅ¡provokavo ne trivialus skaiÄius klausimÅ³, kuris buvo nÄra mÅ«sÅ³ tikslas. Å iÅ³ kuponÅ³ kodÅ³ ketinimÄ, kuriÄ, jei jÅ«s problemos dalis nustatyti anksti, todÄl gauti papildomÄ dienÄ, buvo tikrai padÄti vaikinai padÄti sau pradÄti anksti, rÅ«Å¡iuoti apie kurÄ¯ skatinamÅ³jÅ³ jums. Padeda mums platinti apkrovÄ visoje Darbo laikas geriau todÄl, kad Tai tarsi laimi. 

Deja, manau, kad mano instrukcijas nebuvo iki Å¡iol labai aiÅ¡kiai, todÄl GrÄ¯Å¾au Å¡Ä¯ savaitgalÄ¯, ir atnaujinamas didesnÄje, drÄsiau tekstu spec paaiÅ¡kinti, kulkos, kaip Å¡ie. Ir tik pasakyti, kad tai daugiau vieÅ¡ai, pagal Numatytieji, problemÅ³ rinkiniai dÄl ketvirtadienis vidurdienÄ¯, uÅ¾ mokymo programas. Jei pradÄsite anksti, apdailos dalis problema nustatyti iki treÄiadienio 12:00 PM dalÄ¯, kuri susijusi su kuponu kodas, idÄja yra, kad jÅ«s galite iÅ¡plÄsti JÅ«sÅ³ terminas P, nustatytos iki penktadienio. Tai reiÅ¡kia, kad nukando maÅ¾a dalis P nustatyti, palyginti su tai, kas paprastai yra didesne problema, ir jums pirkti sau papildomÄ dienÄ. VÄlgi, tai bus jums galvoti apie problema rinkinys, paleidÅ¾iama jums Ä¯ darbo valandomis anksÄiau. Bet kuponas problema vis dar reikia, net jei jÅ«s neturite pateikti jÄ¯. 

Bet dar priverstinai tai. (ETAPAS "WHISPER) Ir tie Å¾monÄs palieka pradÅ¾ioje yra gonna gailÄtis. Kaip ir ant balkono Å¾monÄs. AtsipraÅ¡au iÅ¡ anksto Ä¯ Å¾moniÅ³ su dÄl prieÅ¾asÄiÅ³, kurios bus balkonas aiÅ¡ku, vos akimirkÄ. 

Taigi, mums pasisekÄ, kad vienas iÅ¡ CS50 buvÄs galvos mokymo biÄiuliÅ³ ne Ä¯monÄ vadinama dropbox.com. Jie labai dosniai paaukojo kuponas Äia tai daug vietos, kuri yra sudaryti iÅ¡ Ä®prasti 2 GB. Taigi, kÄ aÅ¡ maniau, mes galÄtÅ³ padaryti apie tai PaskutinÄ pastaba yra padaryti iÅ¡ dovanÅ³ tiek, , pagal kurÄ¯ tik akimirkÄ, mes atskleisti nugalÄtojas, o kas kuponÄ kodas, tada galite eiti Ä¯ savo Interneto svetainÄ, Ä¯veskite jÄ¯, ir voila, gauti daug daugiau ZMI vietos jÅ«sÅ³ prietaisas ir savo asmeninius failus. 

Ir pirmasis, kurie norÄtÅ³ dalyvauti Å iame pieÅ¡inyje? Gerai, kad dabar tampa dar smagiau. Asmuo, kuris gauna Å¡Ä¯ 25 gigabaitÅ³ kuponas - kuris yra daug patrauklesni nei vÄlai dienÅ³ dabar, galbÅ«t - yra tas, kuris sÄdi ant sÄdynÄs pagalvÄlÄs, Å¾emiau kurios yra kad kuponas. Dabar galite Å¾iÅ«rÄti po jÅ«sÅ³ sÄdynÄs pagalvÄlÄs. 

[VIDEO PLAYBACK] 

-Vienas, du, trys. 

[RÄkia] 

-JÅ«s gaunate automobilÄ¯! JÅ«s gaunate automobilÄ¯! 

Davidas Malan: Pamatysime JÅ«s treÄiadienÄ¯. 

-JÅ«s gaunate automobilÄ¯! JÅ«s gaunate automobilÄ¯! JÅ«s gaunate automobilÄ¯! JÅ«s gaunate automobilÄ¯! JÅ«s gaunate automobilÄ¯! 

Davidas Malan: Balkonas Å¾monÄs, ateik Å¾emyn Äia Ä¯ priekÄ¯, kur mes turime priedai. 

-Kiekvienas gauna automobilÄ¯! Kiekvienas gauna automobilÄ¯! 

[PABAIGA VIDEO PLAYBACK] 

Narrator: Kitame CS50 - 

GARSIAKALBIS 5: Oh my GOSH Gosh Gosh Gosh Gosh Gosh Gosh Gosh Gosh Gosh - 

[Ukelele vaidina]