[Duke luajtur muzikë] DAVID Malan: Të gjithë të drejtë. Të gjithë të drejtë, të mirëpritur mbrapa. Pra, kjo është Java 4, fillimi tij, tashmë. Dhe ju do të kujtojnë se javën e kaluar, ne kemi vënë kodojnë mënjanë për vetëm pak dhe kemi filluar të flasim pak më shumë të nivelit të lartë, rreth gjëra të tilla si kërkimin dhe sorting, e cila edhe pse Idetë disi të thjeshta, janë përfaqësues i një klase të problemeve ju do të fillojnë për të zgjidhur veçanërisht si ju filloni të menduarit rreth final Projektet dhe zgjidhjet interesante që ju mund të ketë të vërtetë të botës problemeve. Tani lloj flluskë ishte një nga më të thjeshtë algoritme të tilla, dhe punuar duke pasur këto numra të vogla ne nje lista ose ne nje lloj vargut të flluskë rrugën e tyre deri në krye, dhe Numrat e mëdha të lëvizë në rrugën e tyre poshtë për të fundi i kësaj liste. Dhe kujtojnë se ne mund të parashikoj lloj flluskë pak diçka si kjo. Pra më lejoni të shkoj përpara dhe klikoni Start. Unë kam përzgjedhur lloj flluskë. Dhe në qoftë se ju kujtohet se blu shtatlartë Linjat përfaqësojnë numra të mëdha, të vogla Linjat e blu paraqesin numra të vogla, si ne do të shkojmë nëpër këtë përsëri dhe përsëri dhe përsëri, duke krahasuar dy bare pranë njëri- të tjera në të kuqe, ne jemi duke shkuar për të bie në ujdi më i madh dhe më i vogël nëse ata janë jashtë funksionit. Pra, kjo do të shkoj në dhe të shkoj në dhe të shkojnë on, dhe ju do të shihni se madhe Elementet janë duke bërë rrugën e tyre për të drejtë, dhe elementet më të vogla janë duke e bërë rrugën e tyre në të majtë. Por ne filluam të përcaktoj sasinë efikasitetit, Cilësia e këtij algoritmi. Dhe ne i thamë se në më të keq rasti, ky algoritëm mori afërsisht sa hapa? Pra, n katror. Dhe çfarë ishte n? Audienca: Numri i elementeve. DAVID Malan: Pra, ishte n Numri i elementeve. Dhe kështu që ne do të bëjmë këtë shpesh. Çdo herë që ne duam të flasim në lidhje me madhësinë e një problemi apo madhësinë e një input, apo sasia e kohës që merr për të prodhuar prodhimit, ne vetëm do të çfarëdo përgjithësuar input është si n. Pra, përsëri në Javën 0, numri faqet në librin e telefonit ishte n. Numri i nxënësve në dhomë u n. Kështu që këtu, gjithashtu, ne jemi duke ndjekur se model. Tani n katror nuk është veçanërisht i të shpejtë, kështu që ne u përpoqëm të bëjmë më mirë. Dhe kështu kemi shikuar në një çift të algoritme të tjera, ndër të cilat ishin të lloj përzgjedhje. Pra lloj zgjedhja ishte pak më ndryshe. Ajo ishte pothuajse e thjeshtë, unë guxoj të them, ku kam filluar në fillim të Lista e vullnetarëve tanë dhe unë vetëm përsëri dhe përsëri dhe përsëri shkoi nëpër lista, plucking jashtë vogël element në një kohë dhe të vënë atë apo saj në fillim të listës. Por kjo, gjithashtu, sapo kemi filluar të mendojmë përmes matematikë dhe më të mëdha foto, mendova rreth asaj se sa herë Unë kam qenë duke shkuar mbrapa dhe me radhë dhe mbrapa dhe me radhë, kemi thënë në rastin më të keq, lloj përzgjedhje, gjithashtu, ishte ajo? n katror. Tani në botën e vërtetë, ajo mund të në fakt të jetë pak më të shpejtë. Sepse përsëri, unë nuk kam për të mbajtur backtracking herë kisha renditura elemente të vogël. Por në qoftë se ne mendojmë për n shumë të mëdha, dhe në qoftë se ju lloj i bëni jashtë matematikë si I bërë në dërrasë, me katror n diçka minus, çdo gjë tjetër përveç katror n, dikur n merr me të vërtetë e madhe, nuk me të vërtetë rëndësi sa më shumë. Pra, si shkencëtarët kompjuterike, ne lloj nga të kthehet një sy qorr ndaj vogla faktorët dhe të përqëndrohet vetëm në faktorin e në një shprehje që do të bëjë Dallimi më i madh. E pra, së fundi, kemi shikuar në lloj futje. Dhe kjo ishte e ngjashme në frymë, por në vend se të shkojnë nëpër iteratively dhe zgjidhni një element të vogël në një herë, unë në vend mori dorën që unë u trajtuar, dhe unë vendosa, të gjithë drejtë, ju i përkasin këtu. Pastaj unë u zhvendos për në elementin e ardhshëm dhe vendosi që ai ose ajo i përkiste këtu. Dhe pastaj unë u zhvendos në dhe në. Dhe unë mund të, përgjatë rrugës, zhvendosë këto guys në mënyrë që të të bëjë vend për ta. Kështu që ishte lloj i anullimit mendor lloj i përzgjedhjes se ne quajtur lloj futje. Kështu që këto tema të ndodhin në botën reale. Vetëm disa vjet më parë, kur një farë Senatori u kandidon për president, Eric Schmidt, në atë kohë CEO i Google, në fakt kishte mundësi ta intervistonin atë. Dhe ne menduam se do të ndajnë këtë YouTube clip për ju këtu, në qoftë se ne mund të kthehet deri vëllimi. [Video playback] -Tani, senatori, ju jeni këtu në Google, dhe unë doja të mendoj se i presidencës si një intervistë pune. [Qeshura] -Tani është e vështirë për të marrë një punë si president. Dhe ju jeni duke kaluar nëpër masa të rrepta tani. Është gjithashtu e vështirë për të marrë një punë në Google. Ne kemi pyetje dhe ne kërkojmë Pyetjet kandidatët tanë. Dhe kjo është një nga Larry Schwimmer. [Qeshura] -Ju djema mendoni se unë jam kidding? Ajo është e drejtë këtu. Cila është mënyra më efikase për lloj milioni dy-bit integers? [Qeshura] -Epo, uh - -Me fal. Ndoshta ne duhet - -Jo, jo, jo, jo, jo. -Kjo nuk është një - OK. -Unë mendoj se lloj flluskë do të jetë mënyra e gabuar për të shkuar. [Qeshura] [Brohoritje dhe duartrokitje] -Come on, i cili i tha atij këtë? OK. [VIDEO END rishikim] DAVID Malan: Pra, nuk keni atë. Pra, kemi filluar për të përcaktoj sasinë këto running herë, kështu që të flasin, me diçka quajtur simbol asymptotic, e cila është vetëm duke iu referuar lloj tonë të kthyer një sy të verbër ndaj këtyre faktorëve të vogla dhe të vetëm në kërkim në kohë të rrjedhshëm, Ecuria e këtyre algoritmeve, si n merr me të vërtetë i madh me kalimin e kohës. Dhe kështu që ne kemi prezantuar madh O. And Big O diçka që ne kemi menduar të përfaqësuara e si një kufi i sipërm. Dhe në të vërtetë, Barry, mund të ulim mic se pak pak? Ne kemi menduar e kjo është një kufi i sipërm. O kaq i madh i mjeteve n katror se në Rasti më i keq, diçka si lloj përzgjedhje do të marrë n hapa në katror. Ose diçka si lloj futje do hapa n kuadratuar. Tani për diçka si futje lloj, çfarë ishte rasti më i keq? Duke pasur parasysh një grup, çka është më e keqja Skenari e mundur që ju mund të gjeni veten të përballur me të? Kjo është plotësisht prapa, të drejtë? Sepse në qoftë se kjo është plotësisht prapa, ju duhet të bëni një shumë e tërë e punës. Sepse në qoftë se ju jeni plotësisht prapa, ju jeni duke shkuar për të gjetur Elementi më i madh këtu, edhe pse ajo i takon atje poshtë. Pra, ju jeni duke shkuar për të thënë, të gjithë të drejtë, në ky moment në kohë, ju i përkisni këtu, kështu që ju lënë atë vetëm. Pastaj ju kuptojnë, oh, mallkuar, unë kam për të lëvizur këtë element paksa më të vogël në majtë prej jush. Pastaj unë kam për të bërë atë përsëri dhe përsëri dhe përsëri. Dhe në qoftë se unë eci mbrapa dhe me radhë, ju do lloj të ndjehen performancën e se algoritmi, sepse vazhdimisht jam unë shuffling të gjithë të tjerët poshtë në array për të bërë vend për të. Pra, kjo është rasti më i keq. Nga ana tjetër - dhe kjo ishte një cliffhanger hera e fundit - kemi thënë se lloj futje ishte një omega e kujt? Çfarë është e mirë-rasti running koha e lloj futje? Pra, kjo është n fakt. Kjo ishte bosh që ne e kemi lënë në bordin hera e fundit. Dhe kjo është e omega n sepse pse? E pra, në rastin shumë të mirë, çfarë është lloj futje do të dorëzohet? E pra, që është një listë të renditura tërësisht tashmë, puna minimale për të bërë. Por ajo që është i zoti për lloj futje është se për shkak se ajo fillon këtu dhe vendos, oh, ju jeni numri një, ju i përkisni këtu. Oh, çfarë një pasuri të mirë. Ju jeni numri dy. Ju gjithashtu përkasin këtu. Numri tre, edhe më të mirë, ju i përkisni këtu. Sa më shpejt që ajo merr deri në fund të pseudokod, lista per futje e Rendit se kemi ecur nëpër gojë Herën e fundit, ajo është bërë. Por lloj përzgjedhje, nga ana tjetër, mbahet duke bërë çfarë? Mbajtur shkuar nëpër lista përsëri dhe përsëri dhe përsëri. Sepse Insight kyç atje ishte vetëm një herë ju kam shikuar gjatë gjithë rrugës për fundi i listës mund të jenë të sigurt se elementi keni zgjedhur ishte me të vërtetë elementi aktualisht i vogël. Pra, këto modele të ndryshme mendore fundi up japin disa shumë të vërtetë të botës Dallimet për ne, si këto dallimet teorike asymptotic. Pra, vetëm për radhitje, pastaj, i madh o n katror, ​​ne kemi parë një të tillë pak Algoritme deri tani. Madhe O prej n? Çfarë është një algoritmi që mund të të thuhet të jetë i madh o n? Në rastin më të keq, ai merr një numër i hapave linear. OK, kërko lineare. Dhe në rastin më të keq, ku është Elementi ju jeni duke kërkuar për kur aplikoni kërkim linear? Rregull, ne rastin keq, kjo nuk është edhe atje. Ose në rastin e dytë më të keq, kjo është të gjitha rrugën në fund, e cila është -plus ose minus-një-hap ndryshim. Pra, në fund të ditës, ne mund të themi se është linear. Big O n do të jenë kërkim linear, sepse në rastin më të keq, element nuk është edhe atje apo kjo është të gjitha rrugën në fund. Well, Big O i log e n. Ne nuk flasim në hollësi të madhe në lidhje me këtë, por ne kemi parë këtë më parë. Çfarë shkon në të ashtuquajturat logaritmike kohë, në rastin më të keq? Yeah, kështu që kërko binar. Dhe kërko binar në rastin më të keq mund të ketë elementin diku në mesme, apo diku brenda vektorit. Por ju të gjeni vetëm atë një herë ju ndajnë listën në gjysmë, në gjysmë, në gjysmë, në gjysmë. Dhe pastaj voila, ajo është aty. Ose përsëri, rasti më i keq, kjo nuk është edhe atje. Por ju nuk e dini se kjo nuk është atje derisa ju lloj i të arrijnë që zgjasin bottom-shumica elemente nga përgjysmimi dhe përgjysmimi dhe pergjysmimin. Big O i 1. Kështu që ne mund madhe O 2 O, i madh prej 3. Çdoherë ju doni vetëm një numër konstant, Ne vetëm lloj të vetëm të thjeshtojë se si Big O i 1. Edhe pse në qoftë se realisht, ajo merr 2 apo edhe 100 hapa, në qoftë se kjo është një Numri i vazhdueshëm i hapave, ne vetëm të themi O e madhe e 1. Çfarë është një algoritmi që është në Big O e 1? Audienca: Gjetja gjatësinë e një variable. DAVID Malan: Gjetja gjatësia e një variable? Audienca: Jo, gjatësia në qoftë se ajo është renditur tashmë. DAVID Malan: Mirë. OK, kështu që gjetja gjatësinë e diçka nëse gjatësia e atij diçka, si një grup, është ruajtur në disa ndryshore. Sepse vetëm ju mund të lexoni ndryshore, ose printoni ndryshore, ose vetëm në përgjithësi të hyrë në këtë variabël. Dhe voila, që merr kohë konstante. Nga ana tjetër, mendoj se mbrapa për të zeroja. Mendoni përsëri për javën e parë të C, duke e quajtur vetëm printf dhe shtypje diçka në ekran është ndoshta Ora konstante, sepse ajo merr vetëm numrin e disa cikle CPU për të treguar se tekst në ekran. Apo prisni - e bën atë? Si tjetër mund të modelojnë ne Performanca e printf? Dikush do të donte të pajtohen, se ndoshta kjo nuk është hera e vërtetë konstante? Në çfarë kuptimi mund të printf është drejtimin e kohë, në të vërtetë shtypjen e një varg në ekran, të jetë diçka e përveç konstante. Audienca: [padëgjueshme]. DAVID Malan: Po. Pra, kjo varet nga këndvështrimi ynë. Nëse ne mendojmë në fakt e kontributit të printf si string, dhe prandaj ne të matur madhësinë e që input nga gjatësinë e saj - kështu që le ta quajmë se gjatësia n si edhe - ndoshta, printf është në vetvete O i madh n sepse ajo do të marrë ju n hapat të shtypura nga secili prej atyre n karaktere, më shumë gjasa. Të paktën në atë masë që ne supozojmë se ndoshta ajo është duke përdorur një për lak nën kapuç. Por ne do të duhet të shikojmë në se kod për të kuptuar atë më mirë. Dhe me të vërtetë, sapo ju të filloni djema analizimin algoritme tuaja, ju do të fjalë për fjalë të bëjë vetëm se. Lloj kokërdhok kodin tuaj dhe mendoni rreth - të gjithë të drejtë, unë kam këtë lak këtu, ose unë kam një sythe mbivendosur këtu, që do të bëjë gjëra N n herë, dhe ju mund të lloj i arsyes në rrugën tuaj me anë të kodit, edhe nëse ajo është pseudokod dhe jo kodin aktual. Pra, çka në lidhje me omega e n katror? Cila ishte një algoritmi që në më të mirë rasti, ende mori n hapa kuadratuar? Po? Audienca: [padëgjueshme]. DAVID Malan: lloj Pra përzgjedhjes. Sepse në atë problem të vërtetë të reduktohet për faktin se përsëri, unë nuk e di Unë e kam gjetur më të vogël deri tanishme Unë e kam kontrolluar të gjitha elementet e mallkuar. Pra, omega, të themi, n, ne ardhur vetëm me një. Lloj futje. Nëse lista ndodh të jenë të renditura sipas tashmë, në rastin më të mirë që ne sapo kemi të bëjë një të kalojë nëpërmjet saj, në të cilën pikë ne jemi të sigurt. Dhe pastaj që mund të thuhet të jetë linear, për sigurt. Po në lidhje me omega e 1? Çfarë, në rastin më të mirë, mund të marrë një numër konstant i hapave? Kërko Pra linear, në qoftë se ju vetëm të merrni me fat dhe elementi ju jeni në kërkim është e drejtë në fillim të listës, nëse kjo është ajo ku ju jeni tuaj duke filluar linear traversal e atë listë. Dhe kjo është e vërtetë për një Numri i gjërave. Për shembull, edhe binar kërko është omega e 1. Sepse çfarë nëse ju merrni të vërtetë i mallkuar fat dhe mu-çik në mes të array juaj është numri i ju jeni duke kërkuar për të? Kështu që ju mund të merrni me fat atje, si edhe. Kjo, së fundi, omega e n log n. Pra, n log n, ne nuk e bëri me të vërtetë flasim rreth ende, por - Audienca: Merge lloj? DAVID Malan: lloj Merge. Kjo ishte cliffhanger i kohës së fundit, ku kemi propozuar, dhe kemi treguar vizualisht, se nuk janë algoritme. Dhe të shkrihej vetëm një lloj të tillë algoritmi që është krejtësisht i shpejtë se disa prej këtyre guys tjera. Në fakt, shkrihen shkurtër është jo vetëm në Rasti më i mirë n log n, në më të keq Rasti n log n. Dhe kur ju e keni këtë rastësi e omega dhe të mëdha o të qenit e njëjta gjë? Ne fakt mund të përshkruajnë se sa ajo që është quajtur Theta, edhe pse kjo është një më pak të zakonshme. Por kjo vetëm do të thotë të dy kufijtë, në këtë rast, janë të njëjta. Pra bashkojë lloj, çfarë e bën këtë vërtetë të valoj poshtë për të për ne? E pra, kujtojnë motivimin. Më lejoni të tërheq lart një animacion që ne nuk e shohim në kohën e fundit. Kjo, të njëjtën ide, por kjo është një pak më të mëdha. Dhe unë jam duke shkuar për të shkuar përpara dhe të theksojnë parë - ne kemi lloj futje në lart majtas, pastaj lloj përzgjedhje, lloj flluskë, një çift i llojet e tjera - shell dhe të shpejtë - se ne nuk kemi biseduar rreth, dhe tog dhe të shkrihej lloj. Pra, të paktën të përpiqet të përqëndrohet sytë tuaj në lartë tre në majtë dhe pastaj bashkojë lloj kur unë klikoni kjo shigjetë e gjelbër. Por unë do të le të gjithë ata të kandiduar, vetëm për të t'ju japë një ndjenjë të diversitetit të algoritme që ekzistojnë në botë. Unë jam duke shkuar për këtë le të kandidojë për vetëm disa sekonda. Dhe në qoftë se ju të përqëndrohet sytë tuaj - marr një algorithm, të përqëndrohet në atë për vetëm një sekonda - ju do të fillojnë të shohin model që ajo zbaton. Merge lloj, njoftimi, është bërë. Lloj tog, të shpejtë, lloj shell - kështu që ajo duket ne kemi prezantuar tre Algoritme keq javën e kaluar. Por kjo është mirë që ne jemi këtu sot për të po në lloj bashkohen, e cila është një prej ato lehtë është që të shikojmë në të, madje edhe edhe pse ajo ndoshta do të bëj mendjen tuaj vetëm pak. Këtu ne mund të shohim se sa shumë lloj përzgjedhje sucks. Por në anën rrokullisje, kjo është të vërtetë e lehtë për t'u zbatuar. Dhe ndoshta për Set P 3, kjo është një nga Algoritme keni zgjedhur për të zbatuar për edicionin standard. Perfectly gjobë, të përkryer i saktë. Por përsëri, si n merr të mëdha, në qoftë se ju të zgjedhin për të zbatuar një algoritëm të shpejtë doja bashkojë lloj, shanset janë të mëdha dhe në inputeve të mëdha, kodi juaj është vetëm duke shkuar për të kandiduar më të shpejtë. Faqja juaj e internetit do të punojnë më mirë. Përdoruesit e juaj do të jetë i lumtur. Dhe kështu që nuk janë këto efekte e vërtetë duke i dhënë ne disa menduar thellë. Pra, le të marrin një vështrim në atë që bashkohen Rendit është në të vërtetë të gjithë rreth. Gjëja e ftohtë është që të bashkojë lloj është vetëm kjo. Kjo është, përsëri, ajo që ne e kemi quajtur pseudokod, qenia pseudokod Anglisht-si sintaksa. Dhe thjeshtësia është lloj i interesante. Pra, në futjen e elementeve n - kështu që thjesht do të thotë, këtu është një koleksion. Ajo e mori gjërat n në të. Kjo është e gjitha që ne jemi duke thënë atje. Nëse n është më pak se 2, kthehen. Pra, kjo është vetëm rasti i parëndësishëm. Nëse n është më pak se 2, atëherë padyshim që kjo është 0 ose 1, në të cilin rast gjë është renditur tashmë ose nuk ekzistojnë, kështu që vetëm të kthehen. Nuk ka asgjë për të bërë. Pra, kjo është një rast i thjeshtë të këpusin off. Tjetër, ne kemi tre hapa. Sort gjysmën e majtë të elementeve, lloj gjysma e drejta e elementeve, dhe pastaj të bashkojë gjysmave renditen. Ajo që është interesante këtu është se Unë jam natyrë e punting, e drejtë? Nuk është lloj i një përkufizim rrethore të këtij algoritmi. Në çfarë kuptimi është ky algoritëm të rrethore definicion? Audienca: [padëgjueshme]. DAVID Malan: Yeah, Algoritmi im sorting, dy hapat e saj janë "lloj diçka. "Dhe kështu që ngre pyetja, mirë, çfarë jam unë do të përdorin për të zgjidhur gjysmën e majtë dhe gjysma e drejtë? Dhe bukuria këtu është se edhe pse përsëri, kjo është mendje-bending Pjesa potencialisht, ju mund të përdorni të njëjtën algorithm për të zgjidhur gjysmën e majtë. Por, prit një minutë. Kur ju jeni duke thënë për të zgjidhur gjysma e majtë, çfarë janë dy Hapat do të jetë e ardhshme? Ne do të zgjidhur gjysmën e majtë të gjysma e majtë dhe të djathtë gjysma e gjysmës së majtë. Damn, si nuk kam zgjidhur ato dy gjysmave, apo lagjet, tani? Por kjo është OK. Ne kemi një algoritëm sorting këtu. Dhe, edhe pse ju mund të shqetësohen në parë kjo është lloj i një infinit loop, kjo është një cikël që kurrë nuk është duke shkuar për t'i dhënë fund - kjo do të të përfundojë një herë se çfarë ndodh? Pasi n është më pak se 2. E cila përfundimisht do të ndodhë, sepse në qoftë se ju mbani dhe pergjysmimin përgjysmimi i përgjysmuar në këto gjysmave, me siguri përfundimisht ju jeni do të përfundojë deri me vetëm 1 ose 0 elementeve. Në cilën pikë, ky algoritëm thotë se ju jeni bërë. Pra, magjia e vërtetë në këtë algorithm duket të jetë në se hapi final, bashkimi. Kjo ide e thjeshtë vetëm për bashkimin e dy gjërat, kjo është ajo që po ndodh në fund të fundit për të na lejuar për të zgjidhur një sërë, le të themi, tetë elemente. Pra, unë kam tetë më shumë topa stresit up këtu, tetë copa të letrës, dhe një Google Glass - që unë të marrë për të mbajtur. [Qeshura] DAVID Malan: Nëse ne mund të marrë tetë vullnetarë, dhe le të shohim nëse ne mund të luajë këtë jashtë, kështu. Wow, OK. Shkenca kompjuterike është duke fun. Dakord. Pra, si në lidhje me ju tre, dora më e madhe deri atje. Katër në shpinë. Dhe si për ne do të bëjmë ty tri në këtë rresht? Dhe katër në pjesën e përparme. Pra, ju tetë, vijnë më lart. [Qeshura] DAVID Malan: Unë jam në të vërtetë nuk jeni të sigurt se çfarë është ajo. A është kjo topat e stresit? Llambat tavolinë? Materiali? Internet? OK. Pra, vijnë më lart. Kush do të donte - të mbajtur të vijnë deri. Le të shohim. Dhe kjo ju vë në vend - ju jeni në një vend. Uh-oh, prit një minutë. 1, 2, 3, 4, 5, 6, 7 - Oh, mirë. Të gjithë të drejtë, ne jemi të mirë. Të gjithë të drejtë, kështu që të gjithë të kenë një vend, por jo në gotë Google. Më lejoni në radhë këto deri. Cili është emri juaj? MICHELLE: Michelle. DAVID Malan: Michelle? Të gjithë të drejtë, ju merrni për të duken si geek, nëse kjo është OK. E pra, unë bëj shumë, unë mendoj, për vetëm një moment. Të gjithë të drejtë, gatishmëri. Ne kemi qenë duke u përpjekur për të dalë me një përdorin rastin për Google qelqi, dhe ne menduar se do të jetë kënaqësi për të vetëm të bëjë kjo kur njerëzit janë në skenë. Ne do të regjistrojnë botën nga perspektiva e tyre. Dakord. Ndoshta jo atë që Google menduar. Të gjithë të drejtë, në qoftë se ju nuk do mend të veshur kjo për minutat e ardhshme vështirë, që do të jetë e mrekullueshme. Të gjithë të drejtë, kështu që ne kemi këtu një grup të elemente, dhe se array, si për copa të letrës në këto folks ' Duart, është Unsorted aktualisht. MICHELLE: Oh, kjo është aq i çuditshëm. DAVID Malan: Është shumë e shumë të rastit. Dhe në një moment të vetëm, ne jemi duke shkuar për të përpiqen për të zbatuar lloj bashkojë së bashku dhe të shohim se ku Insajt është çelësi. Dhe Mashtrim këtu me lloj Merge është diçka që ne nuk kemi marrë ende. Ne në të vërtetë nevojë për disa hapësirë ​​shtesë. Pra, çfarë do të jetë veçanërisht e interesante në lidhje me këtë është se këto djema jeni duke shkuar për të lëvizur rreth pak bit, sepse unë jam duke shkuar për të supozojmë se ka një grup shtesë e hapësirës, thonë, e drejtë pas tyre. Pra, nëse ata janë prapa karrige e tyre, kjo është array mesme. Nëse ata janë ulur këtu, kjo është array primar. Por kjo është një burim që kemi nuk leveraged deri tani me flluskë lloj, lloj me përzgjedhjes, me lloj futje. Kujtojnë javën e kaluar, të gjithë vetëm lloj riorganizoi në vend. Ata nuk përdorin asnjë memorie shtesë. Ne kemi bërë dhomë për njerëzit nga lëvizjen e njerëzve përreth. Pra, kjo është një pasqyrë kyç, too. Ka kjo tregti-off, në përgjithësi në shkenca kompjuterike, të burimeve. Nëse ju doni që të përshpejtojë diçka si kohë, ju do të jeni të duhet të paguajnë një çmim. Dhe një nga këto çmime është shumë shpesh , hapësirë ​​shuma e kujtesës ose të vështirë disk hapësirë ​​që ju jeni duke përdorur. Ose, sinqerisht, shuma e kohës programues. Sa kohë ju merr, njeriut, që në fakt të zbatojë disa më shumë algorithm e komplikuar. Por, për sot, trade-off është koha dhe hapësira. Pra, nëse ju djema mund vetëm të mbajë deri tuaj numrat në mënyrë që ne mund të shohim se ju jeni në të vërtetë përputhen 4, 2, 6, 1, 3, 7, 8. Excellent. Kështu që unë jam duke shkuar për të mundohet të orkestrojë gjërat, në qoftë se ju djema mund vetëm ndjekin shembullin tim këtu. Kështu që unë jam duke shkuar për të zbatuar, së pari, Hapi i parë i pseudokod, e cila është në informacionin e elementeve n, nëse n është më pak se 2, pastaj do të ktheheni. Natyrisht, kjo nuk e bën zbatohen, kështu që ne të lëvizë. Pra zgjidhur gjysmën e majtë të elementeve. Kështu që do të thotë që unë jam duke shkuar për Fokusi im Vëmendje për një moment të vetëm në këto katër djema këtu. Të gjithë të drejtë, çfarë unë bëj më tej? Audienca: Sort gjysmën e majtë. DAVID Malan: Deri tani unë kam për të zgjidhur gjysma e majtë të këtyre guys. Sepse përsëri, të marrë për veten e Qëllimi është për të zgjidhur gjysmën e majtë. Si do të bëni këtë? Vetëm ndiqni udhëzimet, madje edhe edhe pse ne jemi duke bërë atë përsëri. Pra zgjidhur gjysmën e majtë. Tani unë jam sorting këto dy djem. Çfarë vjen më pas? Audienca: Sort gjysmën e majtë. DAVID Malan: Sort gjysmën e majtë. Deri tani këto, ky vend këtu, eshte nje lista e madhësisë 1. Dhe çfarë është emri juaj përsëri? PRINCESS DAISY: Princesha Daisy. DAVID Malan: Princesha Daisy është këtu. Dhe kështu që ajo është e renditura tashmë, sepse lista është e madhësisë 1. Çfarë unë bëj tjetër? OK, të kthehen, për shkak se lista është e madhësi 1, e cila është më pak se 2. Atëherë çfarë është hapi tjetër? Dhe tani ju duhet të lloj backtrack në mendjen tuaj. Sort gjysmën e drejtë, e cila është - çfarë është emri juaj? LINDA: Linda. DAVID Malan: Linda. Dhe kështu që çfarë të bëjmë tani që ne kemi një listë të madhësisë 1? Audienca: Kthimi. DAVID Malan: Kujdes. Ne kthim parë, dhe tani e treta hap - dhe në qoftë se unë lloj i përshkruaj atë duke përqafuar dy vende tani, tani unë duhet të bashkojë këto dy elemente. Deri tani për fat të keq, elementet janë jashtë funksionit. Por kjo është ajo ku procesi i bashkimit fillon të marrë imponues. Pra, nëse ju djema mund të ngriteni për vetëm një moment, unë jam duke shkuar për nevojë për ty, në një moment, që të hap prapa karrige tuaj. Dhe në qoftë se Linda, 2 sepse është vogël se 4, pse nuk e bëjnë keni ardhur rreth e parë? Qëndro aty. Pra Linda, ju vijnë rreth e parë. Tani në realitet në qoftë se ajo është vetëm një koleksion Ne vetëm mund të lëvizin atë në kohë reale nga kjo karrige në këtë vend. Pra, imagjinoni se mori disa konstante Numri i hapa 1. Dhe tani - por ne kemi nevojë për të vënë ju në vendndodhja e parë këtu. Dhe tani, nëse ju mund të vijnë rreth, si dhe, ne jemi duke shkuar për të jetë në vend të dy. Dhe, edhe pse kjo ndjehet si ajo është marrjen e një kohë, se çfarë është e bukur tani është se gjysma e majtë e gjysma e majtë është renditur tani. Pra, çfarë ishte hapi i ardhshëm, në qoftë se ne tani Rewind më tej në histori? Audienca: gjysma e drejta. DAVID Malan: Sort gjysmën e duhur. Pra, ju djema keni për të bërë këtë, po ashtu. Pra, nëse ju mund të qëndrojnë deri për vetëm një çast? Dhe çfarë është emri juaj? Jess: Jess. DAVID Malan: Jess. OK, kështu që tani është Jess majtë gjysma e pjesës së djathtë. Dhe kështu që ajo është një listë e madhësisë 1. Ajo renditura qartë. Dhe emri juaj përsëri? MICHELLE: Michelle. DAVID Malan: Michelle është padyshim një listë e madhësisë 1. Ajo është renditur tashmë. Deri tani magji ndodh, Procesi i bashkimit. Pra, kush do të vijë më parë? Michelle Natyrisht. Pra, nëse ju mund të vijnë rreth mbrapa. Hapësirë ​​ne kemi në dispozicion për të tani është e drejtë pas kësaj karrige këtu. Dhe tani, nëse ju mund të vijnë mbrapa, si edhe, tani ne kemi, të jetë i qartë, dy gjysmave, secili prej madhësisë së 2 - dhe vetëm për hir të pikturim, nëse ju mund të bëjë një grimë të vogël e një hapësire - lënë një gjysmë këtu, një gjysma e drejtë këtu. Rewind më tej në histori. Cili është hapi tjetër? Audienca: Merge. DAVID Malan: Pra tani ne duhet të bashkohen. Pra, OK, kështu që tani, fatmirësisht, ne liruar vetëm deri katër karrige. Pra, ne kemi përdorur dy herë më shumë memorie, por ne mund të japim flip-flopping mes të dy vargjeve. Pra, numri i të cilëve është që të vijë më parë? Michelle Pra, natyrisht. Pra, të vijnë përreth dhe të marrë vendi juaj këtu. Dhe pastaj numri 2 është padyshim ardhshëm, kështu që ju vijnë këtu. Numri 4, numër 6. Dhe përsëri, edhe pse ka një pak e përfshirë në këmbë, me të vërtetë, këto mund të ndodhë menjëherë, duke lëvizur një - OK, luajti mirë. [Qeshura] DAVID Malan: Dhe tani ne jemi në formë mjaft të mirë. Gjysma e majtë të tërë input tani është renditura. Të gjithë të drejtë, kështu që këta njerëz kishin Përparësia e time - si e bëri atë të përfundojnë të gjitha vajzat në la dhe të gjithë djemtë në të djathtë? OK, kështu që djemtë e 'të kthehet tani. Kështu që unë nuk do të ecin ju nëpërmjet këto hapa. Ne do të shohim nëse ne mund të reapply pseudokod njëjtë. Nëse ju doni të shkoni përpara dhe të qëndrojë lart, dhe ju djema, më lejoni t'ju jap mic. Shih nëse ju nuk mund të përsëris atë që ne vetëm e bëri këtu në fund të tjera të listës. Kush ka nevojë të flasë i pari, bazuar në algorithm? Pra, të shpjegojë se çfarë jeni duke bërë para se të keni bërë ndonjë lëvizje këmbë. Kryetari 1: Të gjithë të drejtë, kështu që Unë jam gjysmën e majtë të gjysma majtas, unë të kthehem. E drejta? DAVID Malan: Mirë. Kryetari 1: Dhe pastaj - DAVID Malan: Kush bën mic shkoni në e ardhshëm? Kryetari 1: Numri Next. 2 Gjuha: Pra, unë jam gjysma e djathtë i pjesës majta e gjysma e majtë, dhe unë kthehem. DAVID Malan: Mirë. Ju ktheheni. Pra, çfarë është tani deri të ardhshëm për ju dy? KRYETARI 2: Ne duam të shohim kush është më i vogël. DAVID Malan: Pikërisht. Ne duam të bashkohen. Hapësira që ne jemi duke shkuar për të përdorur të bashkojë në ju, edhe pse ata janë renditura qartë tashmë, ne jemi duke shkuar të ndjekin algorithm njëjtë. Pra, kush shkon prapa në fillim? Pra, 3, dhe pastaj 7. Dhe tani mic shkon për këta njerëz, OK? Kryetari 3: Pra, unë jam gjysma e drejta e gjysma e majtë, dhe n im është më pak se 1, kështu që unë jam vetëm duke shkuar për të kaluar - DAVID Malan: Mirë. Kryetari 4: Unë jam gjysma e drejta e gjysma e drejta e gjysmës së djathtë, dhe unë jam edhe një person, kështu që unë jam do të kthehen. Deri tani ne bashkohen. Kryetari 3: Pra, ne kthehemi. DAVID Malan: Pra, ju shkoni në pjesën e prapme. Pra 5 shkon e parë, atëherë 8. Dhe tani audienca, e cila është hap ne kemi tani Rewind mbështetur në mendjet tona? Audienca: Merge. DAVID Malan: gjysma Bashkimi majtë dhe të djathtë gjysma e gjysmës origjinal majtë. Deri tani - dhe vetëm për të bërë këtë të qartë, të bëjë një grimë të vogël të hapësirës mes jush dy djemtë. Pra, tani që është dy listat, majtë dhe të djathtë. Deri sa nuk kemi tani bashkojë ju djema në radhën e parë të ulëseve përsëri? 3 shkon e parë. 5 Pastaj, natyrisht. Pastaj 7, dhe tani 8. OK, dhe tani jemi ne? Audienca: Nuk është bërë. DAVID Malan: Nuk është bërë, për shkak se Natyrisht, nuk është një hap i mbetur. Por përsëri, arsyeja që unë jam duke përdorur këtë zhargon si "Rewind në mendjen tuaj," kjo është për shkak se me të vërtetë çfarë po ndodh. Ne jemi duke shkuar nëpër të gjitha këto hapa, por ne jemi lloj i pushuar për një moment, thellë zhyten në algorithm, heshti për një çast, zhyten më thellë në algorithm, dhe tani ne kemi për të zgjidhur i Rewind në tonë Mendjet dhe të prish të gjitha këto shtresa se ne kemi lloj të vihet në pritje. Pra, tani ne kemi dy listat e madhësisë 4. Nëse ju djema mund të ngriteni për herë të fundit dhe të bëjë një grimë e hapësirë ​​këtu për bëjë të qartë se kjo është e majtë gjysma e, origjinal gjysma e drejta e origjinalit. Kush është numri i parë që ne duhet të tërheqë në anën e pasme? Michelle, natyrisht. Pra, ne kemi vënë Michelle këtu. Dhe kush e ka numrin 2? Numri 2 vjen mbrapa si. Numri 3? Excellent. Numri 4, Numri 5, numër 6, Numri 7, dhe numri 8. OK, kështu që ai ndjehet si një shumë i hapave, për sigurt. Por tani le të shohim nëse ne nuk mund të konfirmojmë lloj i intuitivisht se ky algorithm rrënjësisht, veçanërisht si n merr me të vërtetë e madhe, siç e kemi parë me animacione, është rrënjësisht të shpejtë. Kështu që unë pretendojnë këtë algorithm, në më të keq rast dhe madje edhe në rastin më të mirë, është i madh o N n herë log. Kjo është, ka disa aspekt i kësaj algorithm që merr hapa n, por ekziston një aspekt tjetër diku në se përsëritje, se looping, që merr hapa log n. Mund të kemi vënë gishtin tonë në atë që ata dy numra janë duke iu referuar? Mirë, ku - Ku mic shkoni? Kryetari 1: A do të jetë hyni n na thyer deri në dy - duke pjesetuar me dy, në thelb. DAVID Malan: Pikërisht. Çdo herë që ne shohim në çdo algorithm kështu më tani, nuk ka qenë ky model i ndarëse, ndarëse, ndarëse. Dhe kjo është reduktuar në mënyrë tipike për diçka që është logaritmike, log bazë 2. Por kjo mund të vërtetë të jetë çdo gjë, por hyni bazë 2. Tani çfarë lidhje n? Unë mund të shihni se ne lloj i ndarë ju djema - ju ndarë, të ndarë ju, ndarë ju, të ndarë me ju. Ku ka ardhur nga fundi? Pra, kjo është bashkimi. Sepse mendoni rreth saj. Kur ju të bashkojë tetë njerëz së bashku, ku gjysma e tyre janë një grup prej katër dhe gjysma tjetër janë një tjetër grup i katër, si mendoni ju të shkoni për të bërë bashkimin? E pra, ju djema e bëri atë mjaft intuitive. Por, nëse unë e bëri atë një vend pak më shumë metodike, unë mund të ketë vuri në Personi i pari nga e majta e parë me të majtë ime dora, vuri në personin pari nga e majta gjysmën e asaj me të djathtën time, dhe të vetëm më pas ecte nëpër listë, duke vënë në elementin më të vogël çdo herë, duke lëvizur gishtin tim mbi dhe mbi si të nevojshme në të gjithë listës. Por ajo që është çelësi për këtë shkrirja Procesi është Unë jam i krahasojmë këto çifte i elementeve. Nga gjysma e djathtë dhe nga e majta gjysma, unë kurrë nuk jam dikur backtracking. Pra, shkrihen në vetvete është duke marrë jo më shumë se n hapa. Dhe sa herë e bëri kam për të bërë që shkrirja? E pra, jo më shumë se n, dhe ne vetëm panë se me bashkimin përfundimtar. Dhe kështu që nëse ju bëni diçka që merr hyni hapa N n herë, ose anasjelltas, ajo do të na japë hyni Ñ Ñ herë. Dhe pse është kjo më mirë? E pra, në qoftë se ne tashmë e dimë se log n është më e mirë se n - e drejtë? Ne pamë në kërkim binar, librin e telefonit shembull, log n ishte patjetër mirë se linear. Kështu që do të thotë herë n log n është definitivisht më të mirë se sa herë një tjetër n n, AKA n katror. Dhe kjo është ajo që ne në fund të fundit të ndjehen. Raundi i madh i duartrokitje Pra, në qoftë se ne mund të, për këto guys. [Duartrokitje] DAVID Malan: Dhe dhuratat tuaja ikje - ju mund të mbani numrat, në qoftë se ju do të donte. Dhe dhurata juaj lamtumire, si zakonisht. Oh, dhe ne do të ju dërgojnë Videoja, Michelle. Falemnderit. Dakord. Ndihmë veten me një top stresit. Dhe më lejoni të tërheq lart, në ndërkohë, pershendetje Rob Bowden tonë për të ofruar Perspektiva disi ndryshe në këtë, që ju mund të mendoni në lidhje me këto hapa të ndodhin në një disi mënyrë të ndryshme. Në fakt, set-up për atë që është në lidhje me Rob për të na treguar supozon se ne kemi bërë tashmë deri ndarjen e lista e madhe në tetë listave të vogla, secili prej Siperfaqja 1. Pra, ne jemi duke ndryshuar një pseudokod pak vetëm për të zgjidhur të marrë në Ideja kryesore e se si shkrirja veprat. Por koha drejtimin e asaj ai është gati për të bërë është ende do të jetë e njëjtë. Dhe përsëri, set-up këtu është se ai është filluar me tetë listat e madhësisë 1. Pra, ju keni humbur pjesën ku ai është bërë në fakt, log n log n log n, ndarja e dhëna. [Video playback] -Kjo është ajo për një hap. Për hap dy në mënyrë të përsëritur bashkojë palë e listave. DAVID Malan: Hm. Audio Vetëm po vjen jashtë kompjuterin tim. Le të provoni këtë përsëri. -Vetëm të marr në mënyrë arbitrare e cila - tani ne kemi katër listat. Mësoni më parë. DAVID Malan: Nuk shkojmë. Bashkimi-108 dhe 15, ne fund deri me lista 15, 108. Bashkimi 50 dhe 4, ne përfundojnë me 4, 50. Bashkimi 8 dhe 42, ne të përfundojë me 8, 42. Dhe bashkimi 23 dhe 16, ne të përfundojë me 16, 23. Tani të gjitha listat tona janë të madhësisë 2. Njoftim që secili prej katër listat e renditura. Pra, ne mund të fillojë shkrirja palë e listave përsëri. Bashkimi 15 dhe 108 dhe 4 dhe 50, ne së pari të marrë 4, pastaj 15, pastaj 50, pastaj 108. Bashkimi 8, 42 dhe 16, 23, ne së pari të marrë 8, pastaj 16, pastaj 23, pastaj 42. Pra, tani ne kemi vetëm dy listat e madhësisë 4, secila prej të cilave është zgjidhet. Deri tani ne bashkojë këto dy lista. Së pari, ne kemi marrë 4, atëherë ne marrim 8, atëherë ne do të marrim 15, pastaj 16, pastaj 23, pastaj 42, pastaj 50, pastaj 108. [VIDEO END rishikim] DAVID Malan: Përsëri, njoftim, ai kurrë nuk preku një filxhan i dhënë më shumë se një herë pas avancimin e përtej tij. Kështu që ai kurrë nuk e përsëritur. Pra, ai është gjithmonë duke lëvizur në krah, dhe kjo është ajo ku kemi marrë n tonë. Pse nuk lejoni të tërheq lart një animacion që pamë më herët, por këtë herë duke u përqendruar vetëm në lloj bashkohen. Më lejoni të shkojnë përpara dhe zoom në për këtë këtu. Së pari më lejoni të zgjedhin një input të rastit, lartësoj këtë, dhe ju mund të lloj të shihni ajo që ne e mori për të dhënë, më herët, bashkojë lloj është në të vërtetë duke bërë. Pra, vëreni që ju të merrni këto gjysmave apo këto të katërtat ose këto eighths e Problemi se të gjitha një e papritur të fillojë të marrë formë të mirë. Dhe pastaj në fund, që ju shihni në Fundi shumë se bam, çdo gjë është shkrirë së bashku. Pra, këto janë vetëm tre të ndryshme merr në të njëjtën ide. Por depërtim kyç, ashtu si divide pushtuar dhe në klasë të parë, ishte se ne kemi vendosur që të ndajë disi Problemi në diçka të madhe, në lloj diçka e njëjtë në frymë, por më të vogla dhe të vogla dhe të vogla dhe të vogla. Tani një tjetër rrugë zbavitëse për lloj të mendojnë në lidhje me këto, edhe pse kjo nuk është do të ju jap intuitiv njëjtë të kuptuarit, është animacion vijim. Pra, kjo është një dikush video të vënë së bashku që shoqërohet ndryshme Dashuri me operacione të ndryshme për lloj futje, për lloj shkrihen, dhe për një çift të tjerëve. Pra, në një moment, unë jam duke shkuar për të goditur Luaj. Kjo është rreth një minutë të gjata. Dhe, edhe pse ju mund të shohin ende modelet ndodh, këtë herë ju mund të gjithashtu dëgjuar se si këto algoritme janë kryerjen ndryshe dhe me modelet disi të ndryshme. Kjo është lloj futje. [Tones PLAYING] DAVID Malan: Kjo përsëri është duke u përpjekur për të futur çdo element në aty ku i takon. Kjo është lloj flluskë. [Tones PLAYING] DAVID Malan: Dhe ju mund të lloj të ndjehen si relativisht pak punë është e bërë në çdo hap. Kjo është ajo që tingëllon si tediousness. [Tones PLAYING] DAVID Malan: Kjo është lloj përzgjedhje, ku ne selekto element ne duam nga duke shkuar nëpër përsëri dhe përsëri dhe përsëri dhe duke i vënë atë në fillim. [Tones PLAYING] DAVID Malan: Kjo është lloj bashkojë, të cilat ju mund të vërtetë të fillojë të ndjehen. [Tones PLAYING] [Qeshura] DAVID Malan: Diçka e quajtur gnome lloj, të cilën ne nuk e kemi shikuar. [Tones PLAYING] DAVID Malan: Pra më lejoni të shohim, tani, hutuar si ju janë shpresë nga music, në qoftë se unë mund të kaloj pak bit e math në këtu. Pra, nuk është një mënyrë e katërt që ne mund mendoni se çfarë do të thotë këto Funksione të jetë më shpejt se ato të që ne kemi parë më parë. Dhe në qoftë se ju jeni të vijnë në kurs nga një sfond matematikë, ju në fakt ndoshta tashmë e dini që ju mund të godasin një mandat në këtë teknikë - domethënë recursion, një funksion që në njëfarë mënyre e quan veten. Dhe përsëri, kujtojnë atë lloj bashkojë pseudokod ishte recursive në kuptimin se një nga hapat e Rendit Merge ishte për të thirrur lloj - që është, në vetvete. Por fatmirësisht, sepse ne kemi mbajtur lloj thirrje, ose të bashkohen lloj, konkretisht, në një të vogla dhe të vogla dhe lista të vogla, ne përfundimisht në sajë ndal në atë që ne do të thërrasë një rast bazë, hard-coded rasti që tha se nëse lista është e vogël, më pak se 2 në atë rast, vetëm të kthehet menjëherë. Nëse ne nuk kemi atë rast të veçantë, algorithm kurrë nuk do të poshtme jashtë, dhe ju do të vërtetë të marrë në një loop pafund të vërtetë përgjithmonë. Por mendoj se ne të kërkuar për të vënë tani disa numra në këtë, përsëri, duke përdorur n si me përmasat e dhëna. Dhe unë të kërkuar për të ju pyes, çfarë është Koha totale e përfshirë në running lloj shkrihet? Ose më në përgjithësi, çfarë është Kostoja e saj në kohë? E pra kjo është goxha e lehtë për të matur atë. Nëse n është më pak se 2, koha të përfshirë në klasifikim n elemente, ku n eshte 2, eshte 0. Sepse ne vetëm të kthehen. Nuk ka punë për t'u bërë. Tani ndoshta, ndoshta kjo është një hap ose dy Hapa të gjej shumën e të punojnë, por është mjaft afër se 0 Unë jam vetëm duke shkuar për të thonë se nuk ka punë nevojshme nëse lista është aq i vogël për t'u jointeresant. Por, ky rast është interesant. Rasti recursive ishte dega e pseudokod që tha tjetër, lloj gjysma e majtë, lloj drejtën gjysma, shkrihen dy gjysmave. Tani pse e bën këtë shprehje përfaqësojnë atë shpenzim? E pra, n T i vetëm do të thotë Koha për të zgjidhur elementet n. Dhe pastaj në anën e djathtë të barabartë shenjë atje, n T i ndarë nga 2 është duke iu referuar kostos së çfarë? Sorting gjysmën e majtë. T e tjera të n ndarë nga 2 është me sa duket duke iu referuar kostos për lloj gjysmën e duhur. Dhe pastaj plus n? Është bashkimi. Sepse në qoftë se ju keni dy lista, një nga n madhësia mbi 2 dhe një tjetër i madhësisë n mbi 2, ju duhet të në thelb prek secili prej këtyre elementeve, ashtu si Rob preku secilin nga gota, dhe vetëm si ne theksuar në secilin prej Vullnetarët në skenë. Kështu n eshte shpenzimeve të bashkimit. Tani për fat të keq, kjo formulë është edhe vetë rekursive. Pra, nëse pyetjen, nëse n është, të themi, 16, në qoftë se ka 16 njerëz në skenë ose 16 gota në video, sa përgjithshëm hapa nuk është marrë për të zgjidhur ato me lloj bashkojë? Kjo nuk është në fakt një përgjigje e qartë, sepse tani ju keni për të zgjidhur të Recursively të përgjigjem në këtë formulë. Por kjo është në rregull, sepse më lejoni të propozojnë që ne bëjmë në vijim. Ora përfshira për të zgjidhur 16 persona ose 16 gota do të jenë të përfaqësuara përgjithësisht si T i 16. Por që është e barabartë, sipas tonë Formula e mëparshme, 2 herë shumën e kohës që duhet për të zgjidhur 8 gota plus 16. Dhe përsëri, plus 16 është koha që të bashkojë, dhe dy herë T e 8 eshte Koha për të zgjidhur gjysmën e majtë dhe gjysmë të drejtë. Por përsëri, kjo nuk është e mjaftueshme. Ne kemi të zhyten në të thellë. Kjo do të thotë që ne duhet të përgjigjen pyetja, çfarë është T e 8? Well T i 8 është vetëm 2 T herë nga 4 plus 8. E pra, ajo që është e T 4? T i 4 është vetëm 2 herë T e 2 plus 4. E pra, ajo që është e T 2? T e 2 është vetëm 2 herë T e 1 plus 2. Dhe përsëri, ne jemi lloj i gjetjes mbërthyer në këtë cikël. Por kjo është gati për të goditur se ashtuquajturit rasti bazë. Sepse çfarë është e T 1, nuk kemi pretendojnë? 0. Deri tani në fund, ne mund të punojnë prapa. Nëse T e 1 është 0, unë tani mund të shkojë mbrapa deri një përputhje me këtë djalë këtu, dhe unë mund të plug në për T 0 e 1. Pra, do të thotë se ajo është e barabartë me 2 herë zero, i njohur ndryshe si 0, plus 2. Dhe kështu që shprehja e tërë është 2. Tani, nëse unë të marrë T e 2, të cilit përgjigje është 2, plug it në vijën e mesme, T e 4, që i jep më 2 herë 2 plus 4, kështu 8. Nëse unë pastaj plug në 8 për paraardhëse line, që më jep 2 herë në 8, 16. Dhe në qoftë se ne vazhdojmë pastaj se me 24, duke shtuar në 16, ne fund merrni një Vlera e 64. Tani që në vetvete lloj i flet gjë që e simbol n, O i madh, omega që ne kemi qenë duke folur rreth. Por kjo rezulton se 64 është me të vërtetë 16, madhësia e input, hyni bazë 2 prej 16. Dhe në qoftë se kjo është një pak të panjohura, vetëm mendoj se mbrapa, dhe ajo do të kthehet për ju përfundimisht. Nëse kjo është bazë log 2, kjo është si 2 ngritur në ajo që ju jep 16? Oh, kjo është 4, kështu që është 16 herë 4. Dhe përsëri, kjo nuk është një punë e madhe nëse kjo është lloj i një kujtim i mjegullt tani. Por tani për tani, të marrë besimin se 16 log 16 është 64. Dhe kështu me të vërtetë, me këtë mendje e shëndoshë të thjeshtë kontrolloni, ne kemi konfirmuar - por nuk provohet zyrtarisht - se koha drejtimin e bashkimin Rendit është me të vërtetë n log n. Pra, jo i keq. Është patjetër më mirë se Algoritmet e kemi parë deri tani, dhe kjo është për shkak se ne kemi leveraged, një, një teknikë të quajtur recursion. Por më interesant se kaq, se nocioni i ndarjes dhe pushtues. Përsëri, në të vërtetë javën 0 sende që edhe tani është përsëritur në një mënyrë më bindëse. Tani një ushtrim fun pak, në qoftë se ju keni bërë kurrë këtë - dhe ju ndoshta nuk do të ketë, sepse lloj normale njerëzit nuk mendojnë për të bërë këtë. Por në qoftë se unë po shkoj tek google.com dhe nëse Unë dua të mësojnë diçka rreth recursion, Enter. [Qeshura] [Qeshura MORE] DAVID Malan: shaka e keqe përhapur ngadalë. [Qeshura] DAVID Malan: Vetëm në rast, ajo është aty. Unë nuk shkruhet gabim, dhe nuk ka shaka. Dakord. Shpjegojnë atë njerëzve ardhshme për ju nëse ajo nuk ka klikuar mjaft vetëm ende. Por recursion, më në përgjithësi, i referohet në procesin e një funksioni të quajtur vetë, ose më në përgjithësi, duke e ndarë një Problemi në diçka që mund të jetë zgjidhen pak nga pak duke zgjidhur identike Problemet përfaqësuese. Ingranazhet pra, le të ndryshim për vetëm një moment. Ne të doja të përfundojë më cliffhangers të caktuara, kështu që le të fillojë për të vendosur fazë, për disa minuta, në një ide shumë të thjeshtë - që i shkëmbejnë dy elemente, e drejtë? Të gjitha këto algoritme ne kemi qenë duke folur rreth dy viteve të ligjërata të përfshijë disa lloj i shkëmbejnë. Sot ajo është visualized nga ata duke dorë nga karriget e tyre dhe ecin përreth, por në kod, ne do të marrë vetëm një element nga një grup dhe pllum atë në një tjetër. Pra, si do të shkojmë për të bërë këtë? E pra, më lejoni të shkoj përpara dhe të shkruajnë një program të shpejtë këtu. Unë jam duke shkuar për të shkuar përpara dhe të bëjë kjo si në vijim. Le ta quajmë këtë - çfarë ne duam ta quajmë këtë një të tillë? Në fakt, nuk ka. Më lejoni të Rewind. Unë nuk dua të bëj që cliffhanger ende. Ajo do të prishin fun. Le ta bëjmë këtë vend. Le të supozojmë se unë dua të shkruaj pak Programi dhe se tani përqafon këtë Ideja e recursion. Unë lloj i marrë përpara veten time atje. Unë jam duke shkuar për të bërë në vijim. Së pari, të përfshijë një të shpejtë të standardit io.h, si edhe një përfshijnë të cs50.h. Dhe atëherë unë jam duke shkuar për të shkuar përpara dhe e shpall të pavlefshme kryesore int në mënyrë të zakonshme. Kuptova unë kam sot quhet dosjen, kështu që më lejoni të vetëm të shtoni një zgjatje. c këtu në mënyrë që ne mund të përpilojnë atë siç duhet. Filloni këtë funksion off. Dhe funksioni unë dua të shkruaj, mjaft thjesht, eshte njeri qe kerkon shfrytëzues për një numër dhe pastaj shton deri të gjitha numrat që mes Numri dhe, të themi, 0. Pra, së pari unë jam duke shkuar për të shkuar përpara dhe të deklarojë n int. Pastaj unë kopjoni kodin që disa ne kemi përdorur për një kohë. Ndërsa diçka është e vërtetë. Unë do të kthehem në se në një moment. Çfarë doni të bëni? Unë dua të them printf pozitive integer ju lutem. Dhe atëherë unë jam duke shkuar për të thonë n merr merrni int. Pra, përsëri, disa kodin Boilerplate që ne kemi përdorur më parë. Dhe unë jam duke shkuar për të bërë këtë ndërsa n është më pak se 1. Pra, kjo do të sigurojë që përdoruesi më jep një numër i plotë pozitiv. Dhe tani unë jam duke shkuar për të bërë në vijim. Unë dua të shtoni deri të gjithë numrat e midis 1 dhe dhe n, ose 0 dhe n, ekuivalente, për të marrë shumën totale. Pra, simbol i madh sigma që ju mund të kujtojnë. Kështu që unë jam duke shkuar për të bërë këtë duke thirrur parë një funksion të quajtur sigma, duke kaluar atë në n, dhe pastaj unë jam duke shkuar për printf thonë, përgjigja është e drejtë atje. Pra me pak fjalë, unë të marrë dhe int nga përdoruesi. I siguruar se ajo është pozitive. Unë deklaroj një përgjigje të ndryshueshme të quajtur int lloji dhe dyqan në atë kthim Vlera e Sigma-n, duke kaluar n si input. Dhe pastaj unë të shtypura nga se përgjigje. Për fat të keq, edhe pse tingëllon sigma si diçka që mund të jetë në fotografi math.h, deklaratën e saj, kjo nuk është e vërtetë. Pra, kjo është OK. Unë mund të zbatojë këtë veten. Unë jam duke shkuar për të zbatuar një funksion të quajtur SIGMA, dhe ajo do të marrë një parametri - le të vetëm e quajti atë m, vetëm kështu që është e ndryshme. Dhe pastaj deri këtu, unë jam duke shkuar për të thënë, dhe, nëse M është më pak se 1 - ky eshte nje shumë jointeresant programin. Kështu që unë jam duke shkuar për të shkuar përpara dhe kthehen menjëherë 0. Ajo thjesht nuk ka kuptim që të shtoni deri gjitha numrat midis 1 dhe m nëse këtë m në vetvete është 0 ose negative. Dhe atëherë unë jam duke shkuar për të shkuar përpara dhe të bëjë këtë shumë iteratively. Unë jam duke shkuar për të bërë këtë lloj të vjetër-shkollën, dhe unë jam duke shkuar për të shkuar përpara dhe të them se unë jam duke shkuar për të deklarojë një shumë të jetë 0. Pastaj unë jam do të ketë një për lak e int - dhe më lejoni të bëjë atë për ndeshjen tonë Kodi shpërndarjes, kështu që ju keni një kopje në shtëpi. int I merr 1 on deri tek Unë është më pak se ose e barabartë me m. Unë plus plus. Dhe pastaj brenda kësaj për lak - ne jemi pothuajse atje - Shuma merr shumën plus 1. Dhe atëherë unë jam duke shkuar për të kthyer shumën. Kështu që unë e bëri këtë shpejt, mjaft dyshim. Por përsëri, funksioni kryesor është goxha drejtpërdrejtë, në bazë të kodit që kemi shkruar deri tani. Përdor lak të dyfishtë për të marrë një pozitiv int nga përdoruesi. Unë pastaj të kalojë atë int për një funksion të ri quhet sigma, duke e quajtur atë, përsëri, n. Dhe unë të ruajë vlerën e kthimit, përgjigje nga kutia e zezë aktualisht njohur si Sigma-n, në një variabël quajtur përgjigje. Pastaj unë të shtypura atë. Nëse ne tani vazhdojmë tregimin, si është zbatuar sigma? Unë propozoj për të zbatuar si më poshtë. Së pari, pak e gabimit-checking për të siguruar që përdoruesi nuk është messing me mua dhe kalimin në disa vlera negative ose 0. Pastaj unë të deklarojë një ndryshore të quajtur përmbledhur dhe e vendosi atë në 0. Dhe tani kam filluar të lëvizin nga i barabartë 1 të gjitha rrugën deri në dhe duke përfshirë m, sepse unë dua që të përfshijë të gjithë numrat nga njëra anë m, përfshirëse. Dhe brenda kësaj për lak, unë vetëm bëj Shuma merr çfarëdo qoftë ajo është tani, plus Vlera e i. Plus vlera e i. Si një mënjanë, në qoftë se ju nuk e keni parë këtë më parë, ka disa sheqeri sintaktik për këtë linjë. Unë mund të ndryshonin këtë si plus i barabartë, vetëm për të shpëtuar veten disa tasteve dhe për të kërkuar një pije freskuese pak. Por kjo është e gjitha. Kjo është funksionalisht e njëjta gjë. Për fat të keq, ky kod të nuk shkojnë për të hartuar ende. Nëse unë drejtuar bëjë SIGMA 0, Sa jam Unë do të merrni yelled at? Çfarë është ajo për të shkuar nuk i pëlqen? Audienca: [padëgjueshme]. DAVID Malan: Yeah, unë nuk e kanë deklaruar funksion deri të lartë, e drejtë? C eshte lloj i trashë, ne se ajo vetëm bën atë që ju them se për të bërë, dhe ju duhet të bëjë atë në atë mënyrë. Dhe kështu që nëse unë hit Enter këtu, unë jam duke shkuar për merrni një paralajmërim në lidhje me Sigma implicit Deklarata. Oh, nuk është një problem. I mund shkojnë deri në majë, dhe I mund thonë, të gjithë të drejtë, prit një minutë. Sigma është një funksion që kthen një int dhe ajo pret një int, pikëpresje si input. Ose unë mund të vënë në funksion të tërë më sipër kryesore, por në përgjithësi, unë do të rekomandoj kundër kësaj, sepse kjo është bukur që gjithmonë të ketë kryesor në krye kështu ju mund të zhyten në të drejtë dhe e di se çfarë një Programi është bërë nga leximi i parë kryesor. Pra, tani më lejoni të qartë në ekran. Remake SIGMA 0. Të gjitha duket të shikoni. Më lejoni të kandidojë SIGMA 0. Inter pozitive. Unë do të të jap numrin 3 për të mbajtur atë të thjeshtë. Kështu që duhet të jepni 3 plus 2 plus 1, pra 6. Enter, dhe me të vërtetë kam marrë 6. Unë mund të bëj diçka më të madhe - 50, 12, 75. Ashtu si një tangente, unë jam duke shkuar për të bërë diçka qesharake si një të vërtetë të madhe numrin, Oh, që në fakt ka punuar jashtë - eh, unë nuk mendoj se është e drejtë. Le të shohim. Le të vërtetë bela me të. Kjo është një problem. Çfarë po ndodh? Kodi nuk është edhe aq keq. Është ende lineare. Fishkëllimë është një efekt i mirë, pse. Çfarë po ndodh? Nuk jam i sigurt nëse kam dëgjuar atë. Pra, ajo rezulton jashtë - dhe kjo është si një mënjanë. Kjo nuk është thelbësore për të Ideja e recursion. Ajo rezulton, sepse unë jam duke u përpjekur për të përfaqësojnë një numër kaq të madh, më të ngjarë se është duke u keqinterpretuar nga C si një numër jo pozitiv, por numër negativ. Ne nuk kemi biseduar në lidhje me këtë, por ajo rezulton atje janë numra negative në botë përveç të numrave pozitiv. Dhe mjetet me të cilat ju mund të përfaqësojnë një numër negativ në thelb është, ju përdorni një bit të veçantë për të treguar pozitiv mbi negativ. Kjo është pak më komplekse se kaq, por kjo është ideja themelore. Pra, për fat të keq, në qoftë se C është konfuze njërin nga ato copa si në të vërtetë do të thotë, oh, ky është një numër negativ, loop ime këtu, për shembull, nuk është në të vërtetë do të përfundojë. Pra, në qoftë se unë ishin në fakt shtypje diçka përsëri dhe përsëri, ne do të shoh një shumë të gjithë. Por përsëri, kjo është përveç pikë. Kjo është me të vërtetë vetëm një lloj i kuriozitet intelektual që ne do të vijë për të mbështetur përfundimisht. Por tani për tani, kjo është një e saktë Zbatimi në qoftë se ne supozojmë se përdoruesi do të sigurojë ints që i përshtatet brenda ints. Por unë pohojnë se ky kod, sinqerisht, mund të bëhet shumë më shumë thjesht. Nëse qëllimi në dorë është për të marrë një numër të si m dhe të shtoni deri gjitha Numrat midis saj dhe 1, ose anasjelltas në mes të 1 dhe kjo, unë pretendojnë që unë mund të marrë hua këtë ide se bashkuar Rendit pasur, i cili ishte duke marrë një problem i këtij madhësisë dhe ndarë atë në diçka të vogël. Ndoshta jo gjysma, por më të vogla, por reprezentative njëjtë. Njëjtën ide, por një problem i vogël. Kështu që unë jam në të vërtetë - më lejoni të ruani këtë file me një numër të ndryshëm version. Ne do të quajmë këtë version 1 vend të 0. Dhe unë pretendojnë se unë në fakt mund të reimplement këtë në këtë lloj të mendje-bending mënyrë. Unë jam duke shkuar për të lënë pjesë e saj vetëm. Unë jam duke shkuar për të thonë se nëse është më pak m se, ose të barabartë edhe në 0 - Unë jam vetëm do të jetë pak më shumë anal këtë herë me kontrollin tim gabim - Unë jam duke shkuar për të shkuar përpara dhe të kthehen 0. Kjo është arbitrar. Unë jam vetëm thjesht të vendosë nëse përdoruesi më jep një numër negativ, unë jam 0 kthehen, dhe ata duhet të kenë lexuar Dokumentacioni më nga afër. Else - njoftim se çfarë unë jam duke shkuar për të bërë. Tjetër unë jam duke shkuar për t'u kthyer m plus - çfarë është sigma i m? E pra, sigma i m m plus minus 1, plus minus 2 m, plus minus 3 m. Unë nuk dua të shkruaj të gjithë se nga. Pse nuk e bëjnë vetëm unë vë bast? Recursively quajnë veten me një pak më të Problemi më i vogël, pikëpresje, dhe e quajti atë një ditë? E drejta? Tani këtu, gjithashtu, ju mund të ndjeni apo merak se kjo është një loop pafund që unë jam inducing, ku unë jam zbatimin e sigma duke telefonuar Sigma. Por kjo është në rregull të përkryer, sepse unë menduar përpara një shtohet cilat linja? Audienca: [padëgjueshme]. DAVID Malan 23 në 26, i cili është kusht, nëse im. Sepse çfarë është e bukur për zbritja këtu, sepse unë mbaj dorëzimin SIGMA probleme të vogla, të vogla Problemet, më të vogla - kjo nuk është gjysma e madhësisë. Kjo është vetëm një hap i vogël fëmija, por kjo është OK. Sepse përfundimisht, ne do të punojmë rruga jonë deri në 1 ose 0. Dhe dikur ne hit 0, sigma nuk do të thërrasë veten anymore. Ajo do të kthehen menjëherë 0. Pra efekti, në qoftë se ju lloj i erës kjo deri në mendjen tuaj, është për të shtuar m plus m minus 1, plus minus 2 m, m plus minus 3, plus dot, dot, dot, m minus M, eventualisht i dhënë ju 0, dhe efekti është në fund të fundit për të shtuar të gjithë këto gjëra së bashku. Pra, ne nuk kemi, me recursion, zgjidhur problemin që ne nuk mund të zgjidhë më parë. Në të vërtetë, ky version i 0, dhe çdo Problemi deri më sot, ka qenë i zgjidhshëm me vetëm duke përdorur për sythe ose derisa unazore apo ndërton ngjashme. Por recursion, unë guxoj të them, na jep një mënyrë të ndryshme të të menduarit në lidhje me Problemet, të cilit, nëse ne mund të marrë një Problemi, ndajnë atë nga diçka disi i madh në diçka disi të vogla, unë pretendojnë se ne mund ta zgjidhim atë ndoshta pak më elegante në aspektin i dizajnit, me kodin më pak, dhe ndoshta edhe zgjidhjen e problemeve që do të të jetë e vështirë, si ne përfundimisht do të shikoni, zgjidhjen thjesht iteratively. Por cliffhanger që kam bërë duan të na lënë në ishte kjo. Më lejoni të shkojnë përpara dhe të hapur deri një skedar nga - në fakt, më lejoni të shkoj dhe bëni këtë të shpejtë të vërtetë. Më lejoni të shkojnë përpara dhe të propozojë në vijim. Në mesin e kodit të sotëm është këtu këtë fotografi. Ky këtu, noswap. Pra, kjo është një program pak budalla se Unë whipped up që pretendon të bëjë në vijim. Në kryesore, ajo së pari shpall një int x thirri dhe i cakton atë Vlera e 1. Pastaj ai deklaron një int y dhe cakton vlerën 2. Pastaj ajo printon se çfarë x dhe y është. Pastaj ai thotë, shkëmbejnë, Dot dot dot. Atëherë ajo pretendon të jetë një funksion të quajtur quhet swap-in, duke kaluar në x dhe y, ideja e së cilës është që shpresojmë se x dhe y do të kthehen të ndryshme, të kundërta. Pastaj ai swapped pretendojnë! me një pikë thirrje. Pastaj ajo printon nga x dhe y. Por kjo rezulton se kjo shumë Demonstrata e thjeshtë poshtë këtu është në të vërtetë buggy. Edhe pse unë jam deklaruar një të përkohshme ndryshueshme dhe vënien përkohësisht në një kjo, atëherë unë jam ricaktimin një vlerë e B - e cila ndihet e arsyeshme, sepse unë kam ruajtur nje kopje te nje ne temp. Pastaj unë Përditëso b të barabartë çdo gjë ishte në temp. Ky lloj i lojës lëviz një shell të në b dhe b ne nje duke përdorur këtë mesme-njeri i quajtur temp ndjen krejtësisht e arsyeshme. Por unë pretendojnë se kur kam drejtuar këtë Kodi, si unë do të bëj tani - më lejoni të shkoj përpara dhe ngjitur atë në këtu. Unë do të thërrasë këtë noswap.c. Dhe, si emri sugjeron, kjo nuk është do të jetë një program i saktë. Bëni noswap. / Jo swap. x eshte 1, y eshte 2, shkëmbimi, swapped. x eshte 1, y eshte 2. Kjo është krejtësisht e gabuar, madje edhe edhe pse kjo duket të përkryer arsyeshme për mua. Dhe ka një arsye, por ne nuk jemi do të zbulojë arsyen vetëm ende. Tani për tani të cliffhanger dytë kam kërkuar të largohet nga ju me këtë është, një Shpallja e terezi të kodeve kupon. Risi jonë me ditët e vona këtë vit ka provokuar një numër jo të parëndësishëm e pyetjeve, e cila ishte nuk është qëllimi ynë. Synimi i këtyre kodeve kupon, të cilit, nëse ju bëni një pjesë e problemit vendosur në fillim, duke marrë një ditë shtesë, ishte me të vërtetë për të ndihmuar ju djema ndihmoni veten të fillojë herët lloj, i incentivizing nga ju. Na ndihmon për të shpërndarë ngarkesën nëpër zyra orë më mirë kështu se kjo është lloj i fitojë të fitojë. Për fat të keq, unë mendoj se udhëzimet e mia nuk kanë qenë, deri më sot, shumë i qartë, kështu që Unë shkova përsëri këtë fundjavë dhe të përditësuar spekulim në tekstin e mëdha, të guximshme në shpjegojë plumba si këto. Dhe vetëm për të thënë atë më shumë publikisht, duke , vendos parazgjedhura problemit janë pasojë e enjte në mesditë, në planin mësimor. Nëse ju filloni herët, duke përfunduar një pjesë të Problemi vendosur deri të mërkurën në ora 12:00 PD, pjesa që ka të bëjë me një kupon Kodi, ideja është se ju mund të zgjasë Afati i juaj për P vendosur deri të premten. Kjo është, pak off një pjesë e vogël e P të vendosur në lidhje me atë që është në mënyrë tipike Problemi më i madh, dhe ju blej veten një ditë shtesë. Përsëri, ajo ju merr të menduarit në lidhje set problem, ju merr në zyra orë më herët. Por kodin kupon problemi është ende nevojshme, edhe në qoftë se ju nuk e dorëzon atë. Por më shumë compellingly është kjo. (Whisper FAZA) dhe ata folks duke lënë herët janë gonna zhgenjeheni. Si janë folks në ballkon. Unë kërkoj falje paraprakisht folks në ballkon për arsye që do të jenë qartë në një moment të vetëm. Pra, ne jemi me fat që të ketë njërin prej Bursistët ish CS50 e mësimdhënies në kokë një kompani e quajtur dropbox.com. Ata kanë shumë bujarisht dhuruar një Kodi kupon këtu për këtë më shumë hapësirë, cili eshte lart nga zakonshme 2 gigabajt. Pra, ajo që unë mendova që ne do të bëjmë në këtë shënim i fundit është bërë një grimë e një dhuroj, ku në një moment të vetëm, ne do të zbulojë fitues dhe i cili ka një kupon kodin që atëherë ju mund të shkoni në e tyre Faqja e internetit, shkruani atë në, dhe voila, të merrni një tërësi shumë më tepër hapësirë ​​për Dropbox tuaj për aplikim dhe dosjet tuaja personale. Dhe së pari, që do të donte për të marrë pjesë në këtë vizatim? OK, tani që e bën atë edhe më shumë argëtim. Personi i cili merr këtë 25-Gigabyte Kodi kupon - e cila është larg më bindëse se vonë ditë tani, ndoshta - është ai i cili është ulur në majë të një jastëk vend nëpër të cilin ka se kodi kupon. Ju tani mund të duket nën jastëk tuaj vend. [Video playback] -Një, dy, tre. [Ulëritës] -Ju merrni një makinë! Ju merrni një makinë! DAVID Malan: Ne do të shohim ju të mërkurën. -Ju merrni një makinë! Ju merrni një makinë! Ju merrni një makinë! Ju merrni një makinë! Ju merrni një makinë! DAVID Malan: folks Ballkon, vijnë këtu poshtë në pjesën e përparme, ku ne kemi ekstra. -Gjithkush merr një makinë! Gjithkush merr një makinë! [VIDEO END rishikim] Transmetuesi: Në CS50 e ardhshëm - 5 Gjuha: Oh my gosh gosh gosh gosh gosh gosh gosh gosh gosh gosh - [Luan UKELELE]