[Halisi kucheza] DAVID Malan: zote haki. Haki wote, kuwakaribisha nyuma. Hivyo hii ni wiki ya 4, mwanzo yake, tayari. Na itabidi kukumbuka kwamba wiki iliyopita, sisi kuweka Kanuni kando kwa ajili ya kidogo kidogo tu na sisi kuanza kuzungumza zaidi kidogo ngazi ya juu, juu ya mambo kama kutafuta na kuchagua, ingawa kiasi fulani rahisi mawazo, ni mwakilishi wa darasa la matatizo utaanza kutatua hasa kama wewe kuanza kufikiri juu ya mwisho miradi na ufumbuzi kuvutia wanaweza kuwa na matatizo halisi ya dunia. Sasa Bubble aina alikuwa mmoja wa rahisi vile algorithms, na ni kazi kwa kuwa na namba hizi ndogo katika orodha au katika safu ya aina Bubble njia yao hadi juu, na idadi kubwa hoja njia yao chini mwisho wa orodha hiyo. Na kukumbuka kwamba tunaweza taswira Bubble aina kidogo kitu kama hiki. Hivyo basi mimi kwenda mbele na bonyeza Start. Nimekuwa preselected Bubble aina. Na kama wewe kukumbuka kuwa bluu mirefu mistari kuwakilisha idadi kubwa, ndogo mistari ya bluu kuwakilisha idadi ndogo, kama sisi kwenda kwa njia hii tena na tena na tena, kulinganisha baa mbili karibu na kila nyingine katika nyekundu, tunakwenda wabadilishane kubwa na ndogo kama wao ni nje ya utaratibu. Hivyo hii kwenda juu na kwenda juu na kwenda juu, na utaona kuwa kubwa mambo ni kufanya njia yao ya haki, na mambo madogo ni kufanya njia yao ya kushoto. Lakini tulianza kupima ufanisi, ubora wa algorithm hii. Na sisi alisema kwamba katika mbaya kesi, algorithm hii alichukua takribani ngapi hatua? Hivyo n squared. Na nini ilikuwa n? Watazamaji: Idadi ya vipengele. DAVID Malan: Hivyo n mara idadi ya vipengele. Na hivyo tutaweza kufanya hili mara nyingi. Wakati wowote tunataka kuzungumza juu ya ukubwa wa tatizo au ukubwa wa pembejeo, au kiasi cha muda inachukua kuzalisha pato, tutaweza tu wa jumla chochote pembejeo ni kama n. Hivyo nyuma katika Wiki 0, idadi ya kurasa katika kitabu cha simu mara n. idadi ya wanafunzi katika chumba ilikuwa n. Hivyo hapa, pia, sisi ni kufuatia kwamba mfano. Sasa n squared si hasa haraka, hivyo sisi alijaribu kufanya vizuri zaidi. Na hivyo sisi inaonekana katika michache ya nyingine algorithms, kati ya ambayo walikuwa uteuzi aina. Hivyo uteuzi aina alikuwa tofauti kidogo. Ilikuwa karibu rahisi, mimi kuthubutu kusema, ambapo mimi kuanza saa ya kuanza orodha ya kujitolea wetu na mimi tu tena na tena na tena safari kwa kupitia orodha, kukwanyua nje ndogo kipengele katika muda na kuweka naye au yake katika mwanzo wa orodha. Lakini hii pia, mara sisi kuanza kufikiri kupitia hesabu na kubwa picha, mawazo kuhusu ni mara ngapi Mimi kwenda na kurudi nyuma na na nje, sisi alisema katika kesi mbaya, uteuzi aina, pia, ilikuwa nini? n squared. Sasa katika ulimwengu wa kweli, ni nguvu kweli kuwa kidogo kwa kasi zaidi. Sababu tena, sikuwa na kuweka inafuatilia mara moja mimi alikuwa yamepangwa ndogo vipengele. Lakini kama sisi kufikiri juu ya n kubwa sana, na kama wewe aina ya kufanya math nje kama Mimi alifanya juu ya bodi, na squared n bala kitu, kila kitu kingine badala n squared, mara moja n anapata kweli kubwa, haina kweli jambo kama mengi. Hivyo kama wanasayansi wa kompyuta, sisi aina ya kugeuka vipofu ndogo mambo na lengo tu juu ya sababu katika kujieleza kwamba kwenda kufanya tofauti kubwa. Naam, Mwisho, sisi inaonekana katika aina kuingizwa. Na hii ilikuwa sawa katika roho, lakini badala ya kwenda kwa njia ya iteratively na kuchagua ndogo kipengele moja katika wakati, mimi badala yake akachukua mkono kwamba mimi alikuwa kushughulikiwa, na niliamua, kila haki, wewe ni hapa. Kisha mimi alihamia kwenye kipengele ijayo na kuamua kwamba yeye au yeye ni mali hapa. Na kisha mimi wakiongozwa na juu. Na mimi ili kwa, njiani, kuhama guys haya ili kufanya chumba kwa ajili yao. Hivyo kwamba ilikuwa ni aina ya mabadiliko ya akili wa aina uteuzi kwamba sisi kuitwa kuingizwa aina. Hivyo hizi mada kutokea katika ulimwengu halisi. Miaka michache tu iliyopita, wakati fulani seneta alikuwa akikimbia kwa rais, Eric Schmidt, wakati Mkurugenzi Mtendaji wa Google, kwa kweli alikuwa na nafasi ya kuwahoji naye. Na sisi mawazo tunatarajia kushiriki hii YouTube video kwa ajili yenu hapa, kama tunaweza kugeuka up kiasi. [Video avspelning] -Sasa, Seneta, uko hapa katika Google, na mimi kama kufikiri ya urais kama mahojiano ya kazi. [Kicheko] -Sasa ni vigumu kupata kazi kama rais. Na wewe ni kwenda kupitia rigours sasa. Ni pia vigumu kupata kazi saa Google. Tuna maswali na tunaomba yetu wagombea maswali. Na hii ni moja kutoka Larry Schwimmer. [Kicheko] -Wewe guys kufikiri mimi kidding? Ni haki hapa. Je, ni njia ya ufanisi zaidi kwa kutatua milioni integers mbili kidogo? [Kicheko] -Naam, uh - Nina-pole. Labda sisi lazima - -Hapana, hapana, hapana, hapana, hapana. -Hiyo si - OK. -Nadhani aina Bubble ingekuwa kuwa njia sahihi ya kwenda. [Kicheko] [Cheering na makofi] -Haya, ambaye alimwambia hii? OK. [MWISHO video avspelning] DAVID Malan: Hivyo kuna una hiyo. Hivyo tulianza kupima hizi mbio nyakati, hivyo kusema, na kitu kuitwa asymptotic nukuu, ambayo ni tu akimaanisha aina yetu ya kugeuka jicho kipofu kwa sababu hizo ndogo na tu kuangalia wakati mbio, utendaji ya algorithms haya, kama n kweli anapata kubwa zaidi ya muda. Na hivyo sisi ilianzisha kubwa O. Na kubwa O kuwakilishwa kitu ambacho tulidhani ya kama amefungwa juu. Na kweli, Barry, tunaweza kupunguza kuliko mic kidogo? Tulidhani ya hii ni amefungwa juu. Hivyo kubwa O ya njia n squared kwamba katika kesi mbaya, kitu kama uteuzi aina bila kuchukua n hatua squared. Au kitu kama aina ya kuingizwa ingekuwa n hatua squared. Sasa kwa ajili ya kitu kama kuingizwa aina, nini ilikuwa hali mbaya zaidi? Kutokana na safu, nini mbaya iwezekanavyo scenario kwamba unaweza kupata mwenyewe wanakabiliwa na? Ni kabisa nyuma, haki? Kwa sababu kama ni kabisa nyuma, una kufanya mengi yote ya kazi. Kwa sababu kama wewe ni kabisa nyuma, wewe ni kwenda kupata kubwa kipengele hapa, hata kama ni mali ya chini huko. Hivyo wewe ni kwenda kusema, haki ya wote, katika huu katika muda, wewe ni hapa, hivyo wewe kuondoka peke yake. Basi wewe kutambua, oh, damn, nina hoja hii ya kipengele kidogo kidogo kwa kushoto wa wewe. Basi mimi na kwa kufanya hivyo tena na tena na tena. Na kama mimi kutembea na kurudi, wewe itakuwa aina ya kujisikia ya utendaji wa algorithm kwamba, kwa sababu mara kwa mara mimi shuffling kila mtu mwingine chini katika safu kufanya chumba kwa ajili yake. Hivyo kwamba ni kesi mbaya. Kwa upande mwingine - na hii ilikuwa mwisho cliffhanger wakati - sisi alisema kwamba aina ya kuingizwa mara omega ya nini? Nini mbio bora kesi wakati wa aina kuingizwa? Hivyo ni kweli n. Hiyo ilikuwa tupu kwamba sisi kushoto juu ya bodi ya mwisho wakati. Na ni omega ya n sababu kwa nini? Naam, katika kesi bora sana, nini kuingizwa aina kwenda kuwa mitupu? Naam, orodha hiyo kabisa kutatuliwa tayari, ndogo kazi ya kufanya. Lakini nini nadhifu kuhusu aina ya kuingizwa ni kwamba kwa sababu ni kuanza hapa na anaamua, oh, wewe ni idadi moja, wewe ni hapa. Oh, nini bahati nzuri. Wewe ni namba mbili. Wewe pia ni mali hapa. Namba tatu, hata bora zaidi, wewe ni hapa. Haraka kama anapata hadi mwisho wa orodha, kwa kila aina ya kuingizwa pseudocode kwamba sisi kutembea kwa njia ya maneno mara ya mwisho, ni kosa. Lakini uteuzi aina, kwa kulinganisha, naendelea kufanya nini? Naendelea kwenda kupitia orodha tena na tena na tena. Kwa sababu ufahamu muhimu kulikuwa tu mara moja umefanya inaonekana njia yote ya mwisho wa orodha unaweza kuwa na uhakika kwamba kipengele wewe kuchaguliwa mara kweli kipengele sasa madogo. Hivyo haya mbalimbali ya akili mifano mwisho hadi kujitoa sana baadhi ya ulimwengu halisi tofauti kwa ajili yetu, kama vile hizi kinadharia asymptotic tofauti. Hivyo tu kwa kurejea, basi, kubwa O ya n squared, tumeona vile chache algorithms hivi sasa. Kubwa O ya n? Nini algorithm ambayo inaweza kuwa alisema kuwa kubwa O ya n? Katika hali mbaya zaidi, inachukua idadi linear ya hatua. OK, linear utafutaji. Na katika hali mbaya zaidi, ambapo ni kipengele wewe ni kuangalia kwa wakati kutumia tafuta linear? OK, katika kesi mbaya, ni hata huko. Au katika kesi ya pili mbaya zaidi, ni njia yote katika mwisho, ambayo ni pamoja na-au-bala tofauti hatua moja. Hivyo mwisho wa siku, tunaweza kusema ni linear. Kubwa O ya n itakuwa linear utafutaji, kwa sababu katika hali mbaya zaidi, kipengele hata si huko au ni njia yote mwishoni. Naam, kubwa O logi ya n. Hatukuwa majadiliano katika kina kubwa kuhusu hii, lakini tumeona hii kabla. Nini anaendesha katika kinachojulikana logarithmic wakati, katika kesi mbaya? Yeah, hivyo binary tafuta. Na kisha tafuta katika kesi mbaya wanaweza kuwa na kipengele mahali fulani katika katikati, au mahali fulani ndani ya safu. Lakini wewe tu kupata hiyo mara moja kugawanya orodha katika nusu, katika nusu, katika nusu, katika nusu. Na kisha voila, ni huko. Au tena, kesi mbaya, ni hata huko. Lakini huwezi kujua kwamba siyo kuna mpaka aina ya kufikia mwisho chini-wengi vipengele na kupunguza nusu ya na kupunguza nusu na nusu. Kubwa O ya 1. Hivyo tunaweza kubwa O ya 2, kubwa O ya 3. Wowote unataka tu ya simu mara kwa mara, sisi tu ya aina ya tu kurahisisha kwamba kama kubwa O ya 1. Hata ingawa kama realistically, inachukua 2 au hata 100 hatua, ikiwa ni mara kwa mara ya simu ya hatua, sisi tu kusema kubwa O ya 1. Nini algorithm kwamba katika kubwa O ya 1? Watazamaji: Kupata urefu ya kutofautiana. DAVID Malan: Kupata urefu wa kutofautiana? Watazamaji: Hapana, urefu kama ni tayari Iliyopangwa. DAVID Malan: Good. OK, hivyo kutafuta urefu wa kitu kama urefu wa kitu ambacho, kama safu, ni kuhifadhiwa katika variable fulani. Kwa sababu unaweza kusoma tu kutofautiana, au magazeti kutofautiana, au ujumla tu kupata kwamba kutofautiana. Na voilà, kwamba inachukua muda mara kwa mara. Kwa upande mwingine, kufikiri nyuma scratch. Fikiria nyuma kwenye wiki ya kwanza ya C, wito tu printf na uchapishaji kitu juu ya screen ni arguably wakati mara kwa mara, kwa sababu tu inachukua baadhi ya idadi ya mzunguko CPU kuonyesha kwamba maandishi kwenye screen. Au kusubiri - gani? Jinsi mwingine ili sisi mfano utendaji wa printf? Je, mtu kama hawakubaliani, kwamba labda si kweli mara kwa mara wakati? Kwa namna gani wanaweza printf mbio wakati, kwa kweli uchapishaji kamba juu ya screen, kuwa kitu chochote zaidi ya mara kwa mara. Watazamaji: [inaudible]. DAVID Malan: Yeah. Hivyo inategemea mtazamo wetu. Kama sisi kweli nadhani ya pembejeo kwa printf kama kuwa kamba, na hiyo sisi kupima ukubwa wa kwamba pembejeo na urefu wake - hivyo hebu piga kwamba urefu n pia - arguably, printf yenyewe ni kubwa O ya n kwa sababu ni kwenda kuchukua wewe n hatua magazeti nje ya kila aina ya wale n wahusika, uwezekano mkubwa. Angalau kwa kiasi kwamba sisi kudhani kwamba labda ni kutumia kwa kitanzi chini ya Hood. Lakini tunataka kuwa na kuangalia kwamba Kanuni kuelewa ni bora zaidi. Na kwa kweli, mara moja nyie kuanza kuchambua yako algorithms mwenyewe, itabidi literally kufanya tu. Aina ya mboni ya kanuni yako na kufikiri kuhusu - haki ya wote, nina hii kitanzi hapa au nina mizunguko Furushi hapa, kwamba kinaendelea kufanya mambo n n nyakati, na unaweza aina ya sababu njia yako kupitia kanuni, hata kama ni pseudocode na si halisi ya kanuni. Basi nini kuhusu omega ya n squared? Nini ilikuwa algorithm kwamba katika bora kesi, bado alichukua hatua squared n? Yeah? Watazamaji: [inaudible]. DAVID Malan: Hivyo uteuzi aina. Kwa sababu katika tatizo kwamba kweli kupunguzwa na ukweli kwamba tena, sijui Nimepata ndogo mpaka sasa Nimekuwa checked mambo yote darn. Hivyo omega ya, kusema, n, sisi alikuja tu na moja. Kuingizwa aina. Kama orodha kinachotokea ya kutatuliwa tayari, katika kesi bora sisi tu kufanya moja kupita njia hiyo, saa ambayo kumweka sisi ni uhakika. Na kisha hiyo inaweza kuwa alisema kuwa linear, kwa uhakika. Nini kuhusu omega ya 1? Nini, katika kesi bora, inaweza kuchukua simu mara kwa mara ya hatua? Hivyo linear tafuta, kama wewe tu kupata bahati na kipengele wewe ni kuangalia ni haki katika mwanzo wa orodha, kama hiyo ambapo wewe ni mapya yako linear traversal wa orodha hiyo. Na hii ni ya kweli ya idadi ya mambo. Kwa mfano, hata binary kutafuta ni omega ya 1. Kwa sababu nini kama wewe kupata kweli darn bahati na Smack-dab katika katikati ya safu yako ni idadi wewe ni kuangalia kwa? Hivyo unaweza kupata bahati huko, kama vile. Hii moja, mwishowe, omega ya n logi n. Hivyo n logi n, sisi si kweli majadiliano juu bado, lakini - Watazamaji: Merge aina? DAVID Malan: Merge aina. Hiyo ilikuwa cliffhanger ya wakati wa mwisho, ambapo sisi mapendekezo, na sisi ilionyesha kuibua, kwamba kuna algorithms. Na kuunganisha aina moja tu ya vile algorithm kwamba kimsingi ni kasi kuliko baadhi ya guys haya mengine. Kwa kweli, kuunganisha short siyo tu katika bora kesi n n logi, katika mbaya kesi n n gogo. Na wakati una hii bahati mbaya ya omega na kubwa O kuwa kitu kimoja? Tunaweza kweli kueleza kwamba kama nini kuitwa theta, ingawa ni kidogo chini ya kawaida. Lakini hiyo ina maana tu mipaka miwili, katika kesi hii, ni sawa. Hivyo kuunganisha aina, je, hii kweli jipu chini kwa ajili yetu? Naam, kukumbuka motisha. Hebu vuta hadi mwingine uhuishaji kwamba sisi hawakuwa kuangalia wakati wa mwisho. Hii moja, wazo moja, lakini ni kidogo kubwa. Na mimi nina kwenda mbele na kumweka nje kwanza - tuna aina kuingizwa kwenye upande wa juu kushoto, basi uteuzi aina, Bubble aina, ya wanandoa wa aina nyingine - shell na ya haraka - kwamba sisi si aliongea kuhusu, na chungu na kuunganisha aina. Hivyo angalau kujaribu kuzingatia macho yako juu tatu za juu upande wa kushoto na kisha kuunganisha aina wakati mimi bonyeza hii mshale kijani. Lakini mimi itabidi basi wao wote kukimbia, tu kukupa hisia ya utofauti wa algorithms ambazo zipo katika dunia. Mimi nina kwenda basi hii kukimbia kwa sekunde chache tu. Na kama wewe lengo macho yako - pick algorithm, kuzingatia ni kwa ajili tu ya sekunde - utasikia kuanza kuona mfano kwamba ni utekelezaji. Aina kuunganisha, ilani, ni kosa. Lundo aina, haraka aina, shell - hivyo inaonekana sisi ilianzisha tatu mbaya zaidi algorithms wiki iliyopita. Lakini hiyo ni nzuri kwamba sisi ni hapa leo kuangalia aina kuunganisha, ambayo ni moja ya ndio rahisi ni kuangalia, hata ingawa pengine bend akili yako kidogo tu. Hapa tunaweza kuona ni kiasi gani uteuzi aina sucks. Lakini kwa upande flip, ni kweli ni rahisi kutekeleza. Na labda kwa ajili ya P Set 3, hiyo ni moja ya algorithms alichagua kutekeleza kwa toleo la kawaida. Kikamilifu faini, kikamilifu sahihi. Lakini tena, kama n anapata kubwa, kama wewe kuchagua kutekeleza algorithm kasi kama kuunganisha aina, ni tabia mbaya katika kubwa na kubwa za pembejeo, code yako ni ya haki kwenda kukimbia kwa kasi zaidi. Tovuti yako ya kwenda kufanya kazi bora. Watumiaji yako ni kwenda kuwa furaha. Na hivyo kuna athari hizi ya kweli kutoa sisi baadhi undani mawazo. Basi hebu tuangalie nini kuunganisha aina ni kweli yote juu. jambo zuri ni kwamba kuunganisha aina ni tu hii. Hii ni, tena, kile ambacho tumekuwa aitwaye pseudocode, pseudocode kiumbe Kiingereza-kama syntax. Na unyenyekevu ni aina ya kuvutia. Hivyo juu ya pembejeo ya mambo n - ili njia tu, hapa ni safu. Ni got mambo n ndani yake. Kwamba wote sisi ni kusema huko. Kama n ni chini ya 2, kurudi. Hivyo kwamba ni tu kesi yasiyo na maana. Kama n ni chini ya 2, basi ni wazi ni 1 au 0, katika kesi ambayo kitu tayari yamepangwa au haipo, hivyo tu kurudi. Kuna kitu cha kufanya. Hivyo kwamba ni kesi rahisi kuvunja mbali. Mwingine, tuna hatua tatu. Kutatua nusu ya kushoto ya mambo, aina nusu haki ya vipengele, na kisha kuunganisha nusu Iliyopangwa. Nini kuvutia hapa ni kwamba Mimi nina aina ya punting, haki? Kuna aina ya ufafanuzi mviringo kwa algorithm hii. Katika maana gani ni hii ya algorithm ufafanuzi mviringo? Watazamaji: [inaudible]. DAVID Malan: Yeah, kuchagua yangu algorithm, mbili ya hatua yake ni "aina kitu ". Na hivyo kwamba anaomba swali, vizuri, je, Mimi naenda kutumia kutatua nusu ya kushoto na nusu ya haki? Na uzuri hapa ni kwamba hata kama tena, hii ni akili-bending sehemu uwezekano, unaweza kutumia moja algorithm kutatua nusu ya kushoto. Lakini kusubiri dakika. Wakati wewe ni aliiambia kutatua nusu ya kushoto, kile ni mbili hatua kwenda kuwa ijayo? Tutaweza kutatua nusu ya kushoto ya kushoto na kulia nusu nusu ya nusu ya kushoto. Damn, jinsi gani mimi aina hizo mbili nusu, au robo, sasa? Lakini hiyo ni sawa. Tuna algorithm kuchagua hapa. Na hata ingawa unaweza wasiwasi katika kwanza hii ni aina ya usio kitanzi, ni mzunguko kwamba kamwe kwenda mwisho - ni kwenda kukomesha mara moja nini hufanyika? Mara moja n ni chini ya 2. Ambayo hatimaye kinaenda kutokea, kwa sababu kama wewe kuweka hesabu za nusu na kupunguza nusu katika kupunguza nusu nusu hizi, hakika hatimaye wewe ni kwenda mwisho juu na tu 1 au 0 vipengele. Saa ambayo kumweka, hii algorithm anasema wewe ni kosa. Hivyo uchawi kweli katika hii algorithm inaonekana kuwa katika kwamba hatua ya mwisho, kuunganisha. Kwamba wazo rahisi tu kuunganisha mbili mambo, kwamba ni nini hatimaye kwenda kuruhusu yetu ya kutatua safu ya, hebu sema, mambo nane. Hivyo nina nane mipira mkazo zaidi juu hapa, nane vipande vya karatasi, na moja Google kioo - ambayo mimi kupata kushika. [Kicheko] DAVID Malan: Kama sisi inaweza kuchukua nane kujitolea, na hebu angalia kama tunaweza kucheza nje, hivyo. Wow, OK. Sayansi ya kompyuta ni kupata furaha. Wote haki. Hivyo vipi kuhusu wewe tatu, kubwa mkono hadi pale. Nne katika nyuma. Na vipi kuhusu tutaweza kufanya wewe tatu katika safu hii? Na nne mbele. Hivyo nane, kuja juu juu. [Kicheko] DAVID Malan: Mimi kwa kweli uhakika ni nini. Je, ni mipira ya dhiki? taa dawati? nyenzo? internet? OK. Hivyo kuja juu juu. Ambao wangependa - kuendelea kuja juu. Hebu angalia. Na hii unaweka katika eneo - uko katika eneo moja. Uh-oh, kusubiri dakika. 1, 2, 3, 4, 5, 6, 7 - oh, nzuri. Haki wote, sisi ni nzuri. Haki ya wote, hivyo kila mtu kuwa na kiti, lakini si kwa kioo Google. Hebu kwa foleni haya juu. Nini jina lako? MICHELLE: Michelle. DAVID Malan: Michelle? Wote haki, kupata na kuangalia kama geek, kama kwamba ni sawa. Naam, mimi pia, nadhani, kwa muda tu. Haki ya wote, kusubiri. Tumekuwa kujaribu kuja na kutumia kesi kwa ajili ya Google kioo, na sisi walidhani itakuwa furaha tu kufanya hii wakati watu ni onstage. Tutarekodi dunia kwa mtazamo wao. Wote haki. Si pengine kile Google yaliyokusudiwa. Haki ya yote, kama huna akili amevaa hili kwa dakika ijayo Awkward, kwamba itakuwa ya ajabu. Haki wote, hivyo sisi hapa safu ya mambo, na kwamba safu, kama kwa vipande vya karatasi katika folks hizi ' mikono, kwa sasa ni zisizochambuliwa. MICHELLE: Oh, hiyo ni kioja. DAVID Malan: Ni pretty much random. Na katika muda tu, sisi ni kwenda kujaribu kutekeleza kuunganisha aina pamoja na kuona ambapo kwamba ufahamu muhimu ni. Na hila hapa na aina kuunganisha ni kitu ambacho sisi si kudhani bado. Sisi kwa kweli haja ya baadhi ya ziada nafasi. Hivyo nini kinaendelea kuwa hasa kuvutia kuhusu hili ni kwamba hawa guys ni kwenda kuzunguka kidogo kidogo, kwa sababu mimi naenda kwa kudhani kwamba kuna safu ya ziada ya nafasi, kusema, haki ya nyuma yao. Hivyo kama wao uko nyuma ya mwenyekiti wao, hiyo ni safu ya sekondari. Kama uko ameketi hapa, hiyo ni safu ya msingi. Lakini hii ni rasilimali ya kwamba tuna si leveraged hivi sasa na Bubble aina, na aina ya uteuzi, na aina ya kuingizwa. Kukumbuka wiki iliyopita, kila mtu tu aina ya shuffled katika mahali. Hawakuwa na matumizi yoyote kumbukumbu ya ziada. Tukiwa na chumba kwa ajili ya watu na kuhamia watu duniani. Hivyo hii ni ufahamu muhimu, pia. Kuna hii biashara-off, kwa ujumla katika sayansi ya kompyuta, ya rasilimali. Kama unataka kuongeza kasi ya kitu kama muda, wewe ni kwenda na kulipa bei. Na moja ya bei hizo ni mara nyingi sana nafasi, kiasi cha kumbukumbu au ngumu disk nafasi ya kuwa unatumia. Au, kusema ukweli, kiasi ya muda programu. Kiasi gani wakati inachukua wewe, mwanadamu, kwa kweli kutekeleza baadhi ya zaidi ngumu algorithm. Lakini kwa leo, biashara-off ni muda na nafasi. Hivyo kama wewe guys inaweza kushikilia tu juu yako namba ili tuweze kuona kwamba wewe ni kweli vinavyolingana 4, 2, 6, 1, 3, 7, 8. Bora. Hivyo nina kwenda kujaribu orchestrate mambo, kama wewe guys unaweza tu kufuata kuongoza yangu hapa. Kwa hiyo mimi ni kwenda kutekeleza, kwanza, hatua ya kwanza ya pseudocode, ambayo ni juu ya pembejeo ya mambo n, ikiwa n ni chini ya 2, halafu arudi. Ni wazi, kwamba hana kuomba, hivyo sisi kuondoka. Hivyo kutatua nusu ya kushoto ya vipengele. Hivyo kwamba maana mimi nina kwenda kuzingatia yangu tahadhari kwa muda tu juu ya haya wanne guys hapa. Wote haki, je, mimi ijayo kufanya? Watazamaji: aina nusu ya kushoto. DAVID Malan: Basi sasa nina kutatua nusu ya kushoto ya guys haya. Sababu tena, kudhani na wewe mwenyewe lengo ni kutatua nusu ya kushoto. Jinsi gani unaweza kufanya hivyo? Tu kufuata maelekezo, hata ingawa sisi ni kufanya hivyo tena. Hivyo kutatua nusu ya kushoto. Sasa mimi nina kuchagua guys hizi mbili. Kile unakuja ijayo? Watazamaji: aina nusu ya kushoto. DAVID Malan: aina nusu ya kushoto. Hivyo sasa hivi, kiti hiki hapa, ni orodha ya kawaida ya 1. Na nini jina lako tena? PRINCESS DAISY: Princess Daisy. DAVID Malan: Princess Daisy ni hapa. Na hivyo yeye tayari ni Iliyopangwa, kwa sababu orodha ni ya kawaida ya 1. Je, mimi ijayo kufanya? OK, kurudi, kwa sababu orodha ya kwamba ni ya kawaida ya 1, ambayo ni chini ya 2. Kisha hatua gani ya baadaye? Na sasa una aina ya backtrack katika akili yako. Aina nusu haki, ambayo ni - nini jina lako? LINDA: Linda. DAVID Malan: Linda. Na hivyo tunafanya nini sasa kwamba tuna orodha ya kawaida ya 1? Watazamaji: Kurudi. DAVID Malan: Makini. Sisi kurudi kwanza, na sasa ya tatu hatua - na kama mimi aina ya depict hivyo kwa kumuunga viti mbili sasa, sasa mimi na kuunganisha mambo haya mawili. Hivyo sasa kwa bahati mbaya, mambo ni nje ya utaratibu. Lakini hilo ambapo mchakato kuunganisha kuanza kupata kulazimisha. Hivyo kama wewe guys inaweza kusimama kwa ajili tu ya sasa, mimi nina kwenda haja ya wewe, katika sasa, hatua ya nyuma ya kiti yako. Na kama Linda, kwa sababu ya 2 ni ndogo kuliko 4, kwa nini sio wewe kuja karibu ya kwanza? Kukaa huko. Hivyo Linda, wewe kuja duniani kwanza. Sasa katika hali halisi kama ni tu safu tunaweza tu hoja yake katika muda halisi kutoka kwa mwenyekiti hii na doa hili. Hivyo kufikiria kwamba alichukua baadhi ya mara kwa mara Idadi ya hatua 1. Na sasa - lakini tunahitaji kuweka wewe katika mahali ya kwanza hapa. Na sasa kama unaweza kuja karibu, kama vile, tunakwenda kuwa katika eneo mbili. Na hata kama hii anahisi kama ni kuchukua muda, nini ni nzuri sasa ni kwamba nusu ya kushoto ya nusu ya kushoto ni sasa Iliyopangwa. Hivyo kile ilikuwa hatua ya pili, kama sisi sasa rewind zaidi katika hadithi? Watazamaji: Haki nusu. DAVID Malan: aina ya nusu ya haki. Hivyo wewe guys kuwa kwa kufanya hivyo, kama vile. Hivyo kama unaweza kusimama kwa muda tu? Na nini jina lako? JESS: Jess. DAVID Malan: Jess. OK, hivyo Jess sasa ni kushoto nusu ya nusu ya haki. Na hivyo yeye ni orodha ya kawaida ya 1. Yeye ni wazi Iliyopangwa. Na jina yako tena? MICHELLE: Michelle. DAVID Malan: Michelle ni wazi orodha ya kawaida ya 1. Yeye ni tayari Iliyopangwa. Hivyo sasa uchawi ikitokea, mchakato wa kuunganisha. Hivyo nani kwenda aje kwanza? Ni wazi Michelle. Hivyo kama unaweza kuja kuzunguka nyuma. tuna nafasi ya kutosha kwa ajili yake sasa ni haki ya nyuma ya hii kiti hapa. Na sasa kama unaweza kuja nyuma kama vile, sisi sasa kuwa, kuwa wazi, mbili, nusu, kila aina ya ukubwa wa 2 - na kwa ajili tu ya picha ya Mungu ikiwa wewe inaweza kufanya kidogo ya nafasi - mtu wa kushoto nusu hapa, moja haki ya nusu hapa. Rewind zaidi katika hadithi. Nini ni hatua inayofuata? Watazamaji: Merge. DAVID Malan: Basi sasa tuna kuunganisha. Hivyo OK, hivyo kwa sasa, nashiriki, sisi tu huru hadi viti nne. Hivyo tumekuwa kutumika mara mbili kama kumbukumbu sana, lakini tunaweza kutoa flip-flopping kati ya arrays mbili. Hivyo ambayo idadi ni aje kwanza? Hivyo Michelle, ni wazi. Hivyo kuja karibu na kuchukua kiti yako hapa. Na kisha namba 2 ni wazi ijayo, hivyo kuja hapa. Namba 4, namba 6. Na tena, hata kama kuna kidogo kidogo ya kutembea wanaohusika, kweli, hizi inaweza kutokea mara moja, na kuhamia moja - OK, pia alicheza. [Kicheko] DAVID Malan: Na sasa tuko katika sura nzuri. nusu ya kushoto ya nzima pembejeo sasa imekuwa Iliyopangwa. Haki wote, hivyo hawa guys alikuwa faida ya yangu - jinsi gani kuishia wasichana wote juu ya kushoto na wavulana wote juu ya haki? OK, hivyo wavulana 'kugeuka sasa. Hivyo mimi si kutembea wewe kupitia hatua hizi. Tutaweza kuona kama tunaweza reapply pseudocode sawa. Kama unataka kwenda mbele na kusimama, na nyie, nikupe mic. Kuona kama unaweza si kuiga kile sisi tu alifanya hapa nyingine ya mwisho wa orodha. Ambaye anahitaji kusema ya kwanza, msingi algorithm? Hivyo waeleze nini unafanya kabla ya wewe kufanya harakati yoyote mguu. SPIKA 1: zote haki, hivyo tangu Mimi ni nusu ya kushoto ya nusu ya kushoto, mimi kurudi. Haki? DAVID Malan: Good. SPIKA 1: Na kisha - DAVID Malan: Nani anafanya mic kwenda ijayo? SPIKA 1: Next idadi. SPIKA 2: Kwa hiyo mimi nina haki ya nusu ya nusu ya kushoto ya kushoto nusu, na mimi kurudi. DAVID Malan: Good. Wewe kurudi. Hivyo sasa nini juu ijayo kwa ajili ya wewe mbili? SPIKA 2: Tunataka kuona nani vidogo vidogo. DAVID Malan: Hasa. Tunataka kuunganisha. nafasi tunakwenda kutumia kuunganisha wewe ndani, hata kama wao ni wazi yamepangwa tayari, tunakwenda kufuata algorithm sawa. Hivyo ambao unaendelea katika nyuma ya kwanza? Hivyo 3, na kisha 7. Na sasa mic huenda haya guys, OK? SPIKA 3: Kwa hiyo mimi nina haki ya nusu kushoto nusu, na n wangu ni chini ya 1, hivyo mimi nina kwenda tu kupita - DAVID Malan: Good. SPIKA 4: Mimi nina haki ya nusu haki ya nusu ya nusu ya haki, na mimi nina pia mtu mmoja, hivyo mimi nina kwenda na kurudi. Hivyo sasa sisi kuunganisha. SPIKA 3: Hivyo sisi kurudi nyuma. DAVID Malan: Hivyo wewe kwenda katika nyuma. Hivyo 5 huenda kwanza, basi 8. Na sasa watazamaji, ambayo ni hatua tuna sasa rewind nyuma na katika akili zetu? Watazamaji: Merge. DAVID Malan: Kuunganisha kushoto nusu na haki nusu ya nusu ya awali ya kushoto. Hivyo sasa - na tu kufanya hili wazi, kufanya kidogo wa nafasi ya kati ya wewe guys wawili. Hivyo sasa hiyo ni orodha mbili, kushoto na kulia. Hivyo ni jinsi gani sisi sasa kuunganisha guys katika mstari wa mbele wa viti tena? 3 huenda kwanza. Kisha 5, ni wazi. Kisha 7, na sasa 8. OK, na sasa sisi ni? Watazamaji: Si kosa. DAVID Malan: Si kosa, kwa sababu ni wazi, kuna hatua moja iliyobaki. Lakini tena, sababu mimi nina kutumia hii jargon kama "rewind katika akili yako," ni kwa sababu hiyo kwa kweli nini kinatokea. Tunakwenda kupitia hatua zote hizi, lakini sisi ni aina ya pausing kwa sasa, mbizi zaidi katika algorithm, pausing kwa muda, mbizi zaidi katika algorithm, na sasa tuna aina ya rewind katika yetu akili na kuondoa wote wa tabaka hizi kwamba tumekuwa aina ya kuweka juu ya umiliki. Basi sasa tuna orodha mbili ya ukubwa wa 4. Kama wewe guys inaweza kusimama mara moja ya mwisho na kufanya kidogo ya nafasi hapa kufanya wazi kuwa hii ni kushoto nusu ya awali, haki ya nusu ya awali. Ambaye ni idadi ya kwanza ya kwamba sisi haja ya kuvuta ndani ya nyuma? Michelle, bila shaka. Hivyo sisi kuweka Michelle hapa. Na ambaye ana idadi 2? Idadi 2 inakuja juu ya nyuma pia. Namba 3? Bora. Namba 4, namba 5, idadi ya 6, namba 7, na namba 8. OK, hivyo waliona kama mengi ya hatua, kwa uhakika. Lakini sasa hebu angalia kama hatuwezi kuthibitisha aina ya intuitively kwamba hii algorithm kimsingi, hasa kama n kweli anapata kubwa, kama tumeona na mifano kwa michoro, ni kimsingi kwa kasi zaidi. Hivyo mimi kudai hii algorithm, katika mbaya kesi na hata katika kesi bora, ni kubwa O ya n mara logi n. Hiyo ni, kuna baadhi ya nyanja ya hii algorithm kwamba inachukua hatua n, lakini kuna kipengele mwingine mahali fulani katika kwamba iteration, kwamba looping, kwamba inachukua hatua logi n. Tunaweza kuweka kidole wetu juu ya nini wale namba mbili ni akimaanisha? Naam, ambapo - ambapo 'd mic kwenda? SPIKA 1: Je logi n kuwa kuvunja sisi juu katika mbili - kugawa na mbili, kimsingi. DAVID Malan: Hasa. Wakati wowote tunaona yoyote algorithm hivyo mbali, kuna kuwa muundo huu wa kugawa, kugawa, kugawa. Na ni kawaida kupunguza kwa kitu ambacho ni logarithmic, logi msingi 2. Lakini inaweza kweli kuwa kitu chochote, lakini kuingia wigo 2. Sasa nini kuhusu n? Mimi naona kwamba sisi aina ya kugawanywa wewe guys - kugawanywa wewe, kugawanywa wewe, kugawanywa wewe, kugawanywa wewe. Ambapo haina mwisho kuja kutoka? Hivyo ni kuunganisha. Kwa sababu kufikiri juu yake. Wakati kuunganisha watu nane kwa pamoja, ambapo nusu yao ni seti ya nne na nusu nyingine ni mwingine seti ya nne, jinsi gani unaweza kwenda juu ya kufanya kuunganisha? Naam, wewe guys alifanya hivyo haki intuitively. Lakini kama mimi badala yake alifanya hivyo zaidi kidogo methodically, nipate alisema saa mtu leftmost kwanza na kushoto kwangu mkono, alisema katika mtu leftmost ya kwamba nusu kwa mkono wangu wa kulia, na tu hatimaye kutembea kwa njia ya orodha, akionyesha kipengele ndogo kila wakati, kusonga kidole yangu juu na zaidi kama inahitajika katika orodha. Lakini nini kuhusu hili muhimu kuunganisha mchakato ni mimi nina kulinganisha jozi hizi ya vipengele. Kutoka nusu kulia na kutoka upande wa kushoto nusu, mimi nina kamwe mara moja inafuatilia. Hivyo kuunganisha yenyewe ni kuchukua hakuna zaidi ya n hatua. Na mara ngapi alifanya nina kufanya hivyo kuunganisha? Naam, hakuna zaidi ya n, na sisi tu akaona ya kuwa na kuunganisha ya mwisho. Na hivyo kama wewe kufanya kitu kwamba inachukua kuingia hatua n n mara, au kinyume chake, ni kwenda kutupa n mara logi n. Na kwa nini hii ni bora? Naam, kama sisi tayari kujua kuwa logi n ni bora kuliko n - haki? Tuliona katika kutafuta binary, kitabu cha simu mfano, logi n ilikuwa dhahiri bora kuliko linear. Hivyo kwamba maana n mara logi n ni dhahiri zaidi ya mara n mwingine n, AKA n squared. Na kwamba ni nini sisi hatimaye kuhisi. Hivyo kubwa ya raundi ya makofi, kama tunaweza, kwa guys haya. [Makofi] DAVID Malan: Na zimefunguliwa zawadi yako - unaweza kuweka idadi, kama ungependa. Na zimefunguliwa wako zawadi, kama kawaida. Oh, na sisi kukutumia Footage, Michelle. Asante. Wote haki. Msaada mwenyewe kwa mpira wa dhiki. Na napenda kuvuta up, katika huo huo, rafiki yetu Rob Bowden kutoa mtazamo tofauti kwa kiasi fulani juu ya hili, tangu unaweza kufikiri kuhusu hizi yanayotokea katika hatua fulani njia tofauti. Kwa kweli, set-up kwa nini Rob kuhusu kutuonyesha akubali kwamba tumekuwa tayari amefanya kugawa juu ya kubwa orodha katika orodha nane ndogo, kila aina ya kawaida ya 1. Hivyo sisi ni kubadilisha pseudocode kidogo tu kwa aina ya kupata saa msingi wazo la jinsi ya kuunganisha matendo. Lakini wakati mbio ya kile yeye ni juu ya kufanya bado ni kwenda kuwa sawa. Na tena, set-up hapa ni kwamba yeye ni imeanza na orodha ya nane ya kawaida ya 1. Hivyo wameweza amekosa sehemu ambapo yeye ni kweli amefanya n logi, logi n, logi n kugawa wa pembejeo. [Video avspelning] -Hiyo ni kwa hatua moja. Kwa hatua mbili, kwa kurudia kuunganisha jozi ya orodha. DAVID Malan: Hm. Audio tu ni kuja nje ya kompyuta yangu. Hebu jaribu hii tena. -Tu kiholela pick ambayo - sasa tuna orodha nne. Kujifunza kabla. DAVID Malan: Kuna sisi kwenda. -Kuunganisha 108 na 15, sisi kumaliza na orodha 15, 108. Kuunganisha 50 na 4, sisi kuishia na 4, 50. Kuunganisha 8 na 42, sisi kuishia na 8, 42. Na kuunganisha 23 na 16, sisi kuishia na 16, 23. Sasa wetu orodha zote ni ya ukubwa wa 2. Taarifa kwamba kila moja ya orodha ya nne ni Iliyopangwa. Ili tuweze kuanza kuunganisha jozi ya orodha tena. Kuunganisha 15 na 108 na 4 na 50, sisi kwanza kuchukua 4, kisha 15, kisha 50, kisha 108. Kuunganisha 8, 42 na 16, 23, sisi kwanza kuchukua 8, kisha 16, kisha 23, kisha 42. Basi sasa tuna mbili tu orodha ya ukubwa 4, ambayo kila mmoja ni Iliyopangwa. Hivyo sasa sisi kuunganisha orodha hizi mbili. Kwanza, sisi kuchukua 4, basi sisi kuchukua 8, basi sisi kuchukua 15, kisha 16, basi 23, kisha 42, kisha 50, kisha 108. [MWISHO video avspelning] DAVID Malan: Tena, angalia, yeye kamwe kuguswa kikombe kupewa zaidi ya mara moja baada ya kuendeleza zaidi ya hilo. Hivyo yeye kamwe kurudia. Hivyo yeye daima kuhamia upande, na hiyo ambapo tulipata n wetu. Kwa nini basi mimi kuvuta up moja uhuishaji kwamba tuliona mapema, lakini wakati huu kulenga tu juu ya aina kuunganisha. Hebu kwenda mbele na kuvuta katika hii hapa. Kwanza napenda kuchagua pembejeo random, ukuu wa hii, na unaweza aina ya kuona nini sisi alichukua kwa nafasi, awali, kuunganisha aina ni kweli kufanya. Hivyo taarifa kwamba wewe kupata nusu hizi au hizi robo au haya eighths ya tatizo kwamba ghafla kuanza kuchukua sura nzuri. Na kisha hatimaye, unaweza kuona katika mwisho sana kwamba bam, kila kitu ni zimeunganishwa pamoja. Basi hizi ni baadhi tu ya tatu tofauti inachukua wazo moja. Lakini ufahamu muhimu, kama kugawanya na kushinda katika darasa ya kwanza kabisa, ilikuwa kwamba tuliamua namna fulani kugawanya tatizo katika jambo kubwa, ndani ya kitu aina ya kufanana katika roho, lakini na ndogo ndogo na ndogo na vidogo vidogo. Sasa mwingine njia ya kujifurahisha na aina ya kufikiri kuhusu hizi, ingawa si kwenda kukupa angavu huo uelewa, ni uhuishaji zifuatazo. Hivyo hii ni mtu video kuweka pamoja kwamba kuhusishwa tofauti sauti na shughuli mbalimbali kwa ajili ya kuingizwa aina, kwa ajili ya aina kuunganisha, na kwa wanandoa wa wengine. Hivyo katika wakati huu, mimi naenda kumtwanga Play. Ni kuhusu muda wa dakika. Na hata ingawa bado unaweza kuona chati kinatokea, wakati huu unaweza pia kusikia jinsi hawa algorithms ni kufanya tofauti na kwa tofauti chati. Hii ni kuingizwa aina. [Tani KUCHEZA] DAVID Malan: Ni tena ni kujaribu kuingiza kila kipengele ndani ambapo ni mali. Hii ni Bubble aina. [Tani KUCHEZA] DAVID Malan: Na unaweza aina ya kujisikia jinsi kiasi kidogo kazi ni kufanya juu ya kila hatua. Hii ni nini tediousness inaonekana kama. [Tani KUCHEZA] DAVID Malan: Hii ni uteuzi aina, ambapo sisi kuchagua kipengele tunataka na kwenda kupitia tena na tena na tena na kuweka mwanzoni. [Tani KUCHEZA] DAVID Malan: Hii ni kuunganisha aina, ambayo kweli unaweza kuanza kuhisi. [Tani KUCHEZA] [Kicheko] DAVID Malan: Kitu inaitwa mbilikimo aina, ambayo sisi si inaonekana saa. [Tani KUCHEZA] DAVID Malan: Hivyo basi mimi kuona sasa, aliwasihi kama wewe ni matumaini na muziki, kama naweza kuingizwa kidogo kidogo ya math katika hapa. Hivyo kuna njia nne kwamba tunaweza kufikiri juu ya nini maana ya haya kazi kuwa kasi zaidi kuliko wale wa kwamba tumekuwa kuona mbele. Na kama wewe ni kuja saa shaka kutoka background hisabati, wewe kweli kujua labda tayari kwamba unaweza kofi mfupi ya mbinu hii - yaani recursion, kazi kwamba kwa namna fulani wito yenyewe. Na tena, kukumbuka kwamba aina kuunganisha pseudocode alikuwa kujirudia kwa maana ya kwamba moja ya hatua ya kuunganisha aina ya mara kuwaita aina - kwamba ni, yenyewe. Bali nashiriki, kwa sababu sisi naendelea wito aina, au kuunganisha aina, hasa, juu na ndogo ndogo na ndogo orodha, sisi hatimaye bottomed nje shukrani kwa kile Tutamwita kesi ya msingi, kesi ngumu-coded kwamba alisema kama orodha ni ndogo, chini ya 2 katika kesi hiyo, tu kurudi mara moja. Kama hatukuwa na kwamba kesi maalum, algorithm ingekuwa kamwe chini nje, na wewe bila ya shaka kupata katika usio kitanzi kweli milele. Lakini tuseme kwamba sisi alitaka sasa kuweka baadhi ya idadi juu ya hili, tena, kwa kutumia n kama kawaida ya pembejeo. Na nilitaka kuuliza wewe, nini wakati jumla ya kushiriki katika mbio kuunganisha aina? Au zaidi kwa ujumla, nini gharama yake katika muda? Naam ni pretty rahisi kupima kwamba. Kama n ni chini ya 2, wakati husika katika kuchagua mambo n, ambapo n ni 2, ni 0. Kwa sababu sisi tu kurudi. Hakuna kazi kufanyika. Sasa arguably, labda ni hatua moja au mbili hatua kufikiri kiasi cha kazi, lakini ni karibu kutosha 0 kwamba Mimi tu kwenda kusema hakuna kazi ni required kama orodha ni ndogo kuwa uninteresting. Lakini kesi hii ni ya kuvutia. kesi ya kujirudia mara tawi la pseudocode kwamba alisema mwingine, aina nusu ya kushoto, aina ya haki nusu, kuunganisha nusu mbili. Sasa kwa nini msemo huu kuwakilisha kwamba gharama? Naam, T ya n tu ina maana wakati wa kuchambua mambo n. Na kisha upande wa kulia wa alama ya usawa huko, T ya n kugawanywa na 2 ni akimaanisha gharama ya nini? Uamuzi nusu ya kushoto. T nyingine ya n kugawanywa na 2 ni labda akimaanisha gharama kutatua nusu ya haki. Na kisha n pamoja? Ni kuunganisha. Kwa sababu kama una orodha mbili, moja ya ukubwa n zaidi ya 2 na mwingine wa kawaida n zaidi ya 2, una kimsingi kugusa kila moja ya mambo hayo, kama Rob kuguswa kila moja ya vikombe, na tu kama sisi alisema katika kila moja ya kujitolea juu ya hatua. Hivyo n ni gharama ya kuunganisha. Sasa kwa bahati mbaya, hii formula yenyewe pia ni kujirudia. Hivyo kama aliuliza swali, kama ni n, kusema, 16, kama kuna watu 16 juu ya hatua au 16 vikombe katika video, jinsi wengi taarifa hatua gani kuchukua aina yao na aina kuunganisha? Ni kweli si jibu wazi, kwa sababu sasa una aina ya recursively kujibu formula hii. Lakini hiyo ni sawa, kwa sababu napenda kupendekeza kwamba sisi kufanya yafuatayo. wakati husika kutatua watu 16 au 16 vikombe ni kwenda kuwa kuwakilishwa ujumla kama T ya 16. Lakini hiyo ni sawa, kwa mujibu wa wetu uliopita formula, 2 mara kiasi ya muda inachukua kutatua 8 vikombe pamoja na 16. Na tena, pamoja na 16 ni wakati wa kuunganisha, na T mara mbili ya 8 ni wakati kutatua nusu kushoto na nusu ya haki. Lakini tena, hii si ya kutosha. Tuna kwa kupiga mbizi katika zaidi. Hii ina maana tuna kujibu Swali, ni nini T ya 8? Vizuri Simu ya 8 ni 2 tu mara Simu ya 4 pamoja na 8. Vizuri, nini T ya 4? Simu ya 4 ni mara 2 T ya 2 plus 4. Vizuri, nini T ya 2? Simu ya 2 ni mara 2 T ya 1 plus 2. Na tena, sisi ni aina ya kupata kukwama katika mzunguko huu. Lakini ni kuhusu hit kwamba kinachojulikana msingi kesi. Kwa sababu nini T ya 1, gani sisi kudai? 0. Hivyo sasa hatimaye, tunaweza kufanya kazi kwa kurudi nyuma. Kama T ya 1 ni 0, mimi sasa wanaweza kwenda nyuma hadi moja kujipanga na guy hii hapa, na siwezi kuziba katika 0 kwa T ya 1. Hivyo kwamba maana yake ni sawa na mara 2 sifuri, inayojulikana kama 0, plus 2. Na ili kujieleza kwa ujumla ni 2. Sasa kama mimi kuchukua Simu ya 2, ambao jibu ni 2, kuziba ndani ya mstari wa katikati, T ya 4, kwamba anatoa mimi mara 2 2 pamoja na 4, hivyo 8. Kama mimi kisha kuziba katika 8 kwa uliopita mstari, kwamba anatoa mimi mara 2 8, 16. Na kama sisi kisha kuendelea kuwa na 24, na kuongeza katika 16, sisi hatimaye kupata thamani ya 64. Sasa kwa kuwa katika yenyewe aina ya anaongea chochote kwa nukuu n, kubwa O, omega kwamba tumekuwa imekuwa kuzungumza juu. Lakini zinageuka kuwa 64 kwa kweli ni 16, ukubwa wa pembejeo, kuingia wigo 2 ya 16. Na kama hii ni kidogo usio wa kawaida, tu kufikiri nyuma, na kutakuwa na kuja nyuma na wewe hatimaye. Kama hii ni kwa logi msingi 2, ni kama 2 kufufuka kwa nini anatoa wewe 16? Oh, hiyo ni 4, hivyo ni 16 mara 4. Na tena, siyo mpango kubwa kama hii ni aina ya kumbukumbu hazy sasa. Lakini kwa sasa, kuchukua imani kwamba 16 logi 16 ni 64. Na hivyo kweli kweli, na sanity hii rahisi kuangalia, tumekuwa alithibitisha - lakini si imeonekana rasmi - kwamba wakati mbio ya kuunganisha aina ni kweli n logi n. Hivyo si mbaya. Ni dhahiri bora kuliko algorithms tumeona hivi sasa, na ni kwa sababu tumekuwa leveraged, moja, mbinu inayoitwa recursion. Lakini ya kuvutia zaidi kuliko hiyo, ya kwamba dhana ya kugawa na mshindi. Tena, kweli wiki 0 mambo ambayo hata sasa ni mara kwa mara katika zaidi ya kulazimisha njia. Sasa furaha kidogo zoezi, kama wameweza kamwe kufanyika hii - na pengine bila kuwa, kwa sababu ya aina ya kawaida watu sidhani kufanya hili. Lakini kama mimi nenda google.com na kama Nataka kujifunza kitu kuhusu recursion, kuingia. [Kicheko] [ZAIDI kicheko] DAVID Malan: utani Bad polepole kueneza. [Kicheko] DAVID Malan: Tu katika kesi, ni huko. Sikuweza Spell ni makosa, na kuna mzaha. Wote haki. Kueleza ni watu wa karibu na wewe kama bado kabisa clicked bado tu. Lakini kujirudia, kwa ujumla zaidi, inahusu mchakato wa kazi ya wito yenyewe, au zaidi kwa ujumla, kugawa tatizo katika kitu ambacho unaweza kuwa kutatuliwa piecemeal na kutatua kufanana mwakilishi matatizo. Mabadiliko vizuri, hebu gia kwa muda tu. Sisi kama mwisho juu ya cliffhangers fulani, hivyo hebu kuanza kwa kuweka hatua, kwa dakika kadhaa, juu ya wazo rahisi sana - ile ya swapping mambo mawili, haki? Yote ya algorithms haya tumekuwa kuzungumza juu ya wanandoa wa zamani wa mihadhara kuhusisha baadhi ya aina ya swapping. Leo ilikuwa Aliwazia na wao kupata hadi nje ya viti vyao na kutembea karibu, lakini katika kanuni, tunataka tu kuchukua kipengele kutoka safu moja na plop ndani ya mwingine. Hivyo ni jinsi gani sisi kwenda juu ya kufanya hii? Naam, napenda kwenda mbele na kuandika mpango wa haraka hapa. Mimi nina kwenda mbele na kufanya hii kama yafuatayo. Hebu piga hii - je, tunataka kuwaita hii moja? Kweli, hakuna. Hebu rewind. Sitaki kufanya hivyo cliffhanger bado. Itakuwa nyara furaha. Hebu kufanya hivyo badala yake. Tuseme kwamba nataka kuandika kidogo mpango na kwamba sasa unadhihirisha hii wazo la kujirudia. Mimi aina ya got mbele ya mimi nikiwa huko. Mimi nina kwenda kufanya yafuatayo. Kwanza, ni pamoja na ya haraka ya kiwango io.h, vilevile ni pamoja na ya cs50.h. Na kisha mimi nina kwenda mbele na kutangaza int kuu utupu katika njia ya kawaida. Nilitambua nimekuwa misnamed faili, hivyo basi mimi tu kuongeza c. ugani hapa hivyo kwamba tunaweza kukusanya ni vizuri. Kuanza kazi huu mbali. Na kazi nataka kuandika, kabisa tu, ni moja kwamba anauliza mtumiaji kwa ajili ya simu na kisha anaongeza hadi idadi yote kati ya kuwa idadi na, kusema, 0. Hivyo kwanza mimi nina kwenda mbele na kutangaza n int. Kisha mimi nakala baadhi ya kanuni kwamba tumekuwa kutumika kwa muda. Wakati kitu ni kweli. Nitakuja nyuma na kwamba katika wakati huu. Nini mimi unataka kufanya nini? Mimi nataka kusema printf chanya integer tafadhali. Na kisha mimi naenda kusema n anapata kupata int. Hivyo tena, baadhi ya kanuni boilerplate kwamba tumekuwa kutumika kabla. Na mimi nina kwenda kufanya hili wakati n ni chini ya 1. Hivyo hii kuhakikisha kwamba mtumiaji anitiaye sifuri. Na sasa mimi naenda kufanya yafuatayo. Nataka kuongeza hadi wote wa idadi ya kati ya 1 na na n, au 0 na n, equivalently, kwa kupata jumla jumla. Hivyo kubwa sigma ishara kwamba unaweza kukumbuka. Hivyo nina kwenda kufanya hili na wito wa kwanza kazi kuitwa sigma, kupita katika n, na kisha mimi naenda kusema printf, jibu ni haki pale. Hivyo katika muda mfupi, na mimi kupata int kutoka kwa mtumiaji. Mimi kuhakikisha ni mazuri. Mimi kutangaza variable kuitwa jibu la aina int na kuhifadhi katika ni kurudi thamani ya sigma, kupita katika n kama pembejeo. Na kisha mimi magazeti nje kwamba jibu. Kwa bahati mbaya, hata ingawa sigma sauti kama kitu ambacho wanaweza kuwa katika faili math.h, tamko lake, ni kweli si. Hivyo hiyo ni sawa. Siwezi kutekeleza hili mwenyewe. Mimi nina kwenda kutekeleza kazi kuitwa sigma, na ni kwenda kuchukua parameter - hebu tu kuiita m, tu hivyo ni tofauti. Na kisha hadi hapa, mimi nina kwenda kusema, vizuri, kama m ni chini ya 1 - hii ni sana uninteresting mpango. Hivyo nina kwenda mbele na mara moja kurudi 0. Ni tu haina maana kufanya kuongeza hadi kila namba kati ya 1 na m kama m yenyewe ni 0 au hasi. Na kisha mimi nina kwenda mbele na kufanya hili sana iteratively. Mimi nina kwenda kufanya aina hii ya umri wa shule ya-, na mimi naenda kwa kwenda mbele na kusema kwamba mimi nina kwenda Jumla kutangaza kuwa 0. Basi mimi naenda kuwa kwa kitanzi cha int - na napenda kufanya hivyo kwa mechi yetu usambazaji kificho, hivyo una nakala nyumbani. int i anapata 1 juu hadi i ni chini ya au sawa na m. i pamoja plus. Na kisha ndani ya hii kwa kitanzi - tuko karibu huko - Jumla anapata Jumla pamoja na 1. Na basi mimi nina kwenda na kurudi jumla. Hivyo mimi alifanya hivyo haraka, admittedly kabisa. Lakini tena, kazi kuu pretty moja kwa moja, msingi juu ya kanuni tumekuwa imeandikwa hivi sasa. Anatumia kitanzi mbili kupata chanya int kutoka kwa mtumiaji. Mimi kisha kupita kwamba int kwa kazi mpya kuitwa sigma, wito ni, tena, n. Na mimi kuhifadhi thamani ya kurudi, jibu kutoka sanduku nyeusi sasa inayojulikana kama sigma, katika kutofautiana kuitwa jibu. Kisha mimi magazeti hayo. Kama sisi sasa kuendelea hadithi, ni jinsi gani sigma kutekelezwa? Napendekeza kutekeleza kama ifuatavyo. Kwanza, kidogo kidogo ya makosa ya kuangalia- kuhakikisha kwamba mtumiaji si messing na mimi na kupita katika baadhi ya thamani hasi au 0. Basi mimi kutangaza variable kuitwa sum na kuweka kwa 0. Na sasa mimi kuanza kutembea kutoka i sawa 1 njia yote hadi na pamoja na m, kwa sababu mimi nataka ni pamoja na kila idadi kutoka moja kwa njia ya m, umoja. Na ndani ya hii kwa kitanzi, mimi tu kufanya Jumla anapata chochote ni sasa, pamoja na thamani ya i. Plus thamani ya i. Kama kando, kama wameweza hawajaona hii kabla, kuna baadhi ya sukari kisintaksia kwa ajili ya mstari huu. Siwezi kuandika tena kama plus sawa i, tu kuokoa mwenyewe keystrokes chache na kuangalia baridi kidogo. Lakini hiyo yote. Ni functionally kitu kimoja. Bahati mbaya, hii kanuni ya si kwenda kukusanya bado. Kama mimi kukimbia kufanya sigma 0, jinsi am Mimi kwenda kupata yelled saa? Nini ni kwenda si kama? Watazamaji: [inaudible]. DAVID Malan: Yeah, mimi hakuwa kutangaza kazi juu juu, haki? C ni aina ya kijinga, kwa kuwa tu anafanya nini kuwaambia ni nini, na wewe kufanya hivyo ili. Na hivyo kama mimi hit Enter hapa, mimi naenda kupata onyo kuhusu sigma thabiti tamko. Oh, si tatizo. Naweza kwenda hadi juu, na siwezi kusema, haki ya wote, kusubiri dakika. Sigma ni kazi kwamba anarudi int na inatarajia int kama pembejeo semicolon,. Au mimi naweza kuweka kazi nzima juu kuu, lakini kwa ujumla, ningependa kupendekeza dhidi ya kwamba, kwa sababu ni nzuri daima kuwa na kuu kwa juu ili unaweza kupiga mbizi haki na kujua nini mpango anafanya kwa kusoma kuu ya kwanza. Hivyo sasa napenda wazi screen. Umerudiwa sigma 0. Yote inaonekana kuangalia nje. Basi mimi kukimbia sigma 0. Chanya inter. Mimi nitakupa ni idadi 3 kushika ni rahisi. Hivyo kwamba wanapaswa kunipa 3 plus 2 pamoja na 1, hivyo 6. Kuingia, na kwa kweli mimi kupata 6. Mimi siwezi kufanya jambo kubwa - 50, 12, 75. Tu kama tangent, mimi naenda kufanya kitu ujinga kama kweli kubwa simu, Oh, kwamba kweli kazi nje - eh, sidhani kwamba ni sahihi. Hebu angalia. Hebu kweli fujo na hivyo. Kwamba ni tatizo. Nini kinaendelea? kanuni ya kuwa mbaya. Ni bado linear. Whistling ni athari nzuri, ingawa. Nini kinaendelea? Uhakika kama mimi walisikia maneno hayo. Hivyo ni zamu nje - na hii ni kama kando. Hii si ya msingi na wazo la kujirudia. Ni zamu ya nje, kwa sababu mimi nina kujaribu kuwakilisha idadi kubwa kama hiyo, wengi uwezekano ni kuwa misinterpreted na C kama idadi si chanya, lakini hasi idadi. Sisi si aliongea kuhusu hili, lakini ni zinageuka kuna idadi hasi katika dunia kwa kuongeza kwa idadi chanya. Na njia ambayo unaweza kuwakilisha idadi hasi kimsingi ni, unaweza kutumia moja maalum kidogo zinaonyesha mazuri zaidi ya hasi. Ni kidogo ngumu zaidi kuliko kuwa, lakini hiyo ni wazo msingi. Hivyo kwa bahati mbaya, kama C ni utata moja ya wale bits kama kweli maana, oh, hii ni idadi hasi, kitanzi yangu hapa, kwa mfano, ni kweli kamwe kwenda kusitisha. Hivyo kama mimi walikuwa kweli kitu kuchapa tena na tena, tunataka kuona mengi nzima. Lakini tena, hii ni badala ya uhakika. Hii ni kweli tu aina ya miliki udadisi kwamba tutaweza kuja nyuma na hatimaye. Lakini kwa sasa, hii ni sahihi utekelezaji kama sisi kudhani kwamba mtumiaji itatoa ints kwamba inafaa ndani ints. Lakini mimi kudai kwamba kanuni hii, kusema ukweli, inaweza kufanyika hivyo zaidi tu. Kama lengo katika mkono ni kuchukua simu kama m na kuongeza hadi yote ya idadi kati yake na 1, au kinyume chake kati ya 1 na hayo, mimi kudai kwamba naweza kukopa wazo hili kwamba kuunganisha aina alikuwa, ambayo ilikuwa kuchukua tatizo hii ya kawaida na kugawa katika kitu kidogo. Labda si nusu, lakini vidogo, lakini representatively sawa. Same wazo, lakini tatizo kidogo. Hivyo mimi nina kweli - basi mimi kuokoa faili hii na idadi tofauti version. Tutamwita toleo hili 1 badala ya 0. Na mimi kudai kwamba naweza kweli reimplement hii katika aina hii ya akili-bending njia. Mimi naenda kuondoka sehemu ya peke yake. Mimi nina kwenda kusema kama m ni chini kuliko au hata sawa na 0 - Mimi tu kwenda kuwa kidogo zaidi anal wakati huu na makosa yangu kuangalia - Mimi nina kwenda mbele na kurudi 0. Hii ni holela. Mimi tu tu kuamua kama mtumiaji anitiaye simu hasi, mimi nina kurudi 0, na wao wanapaswa kuwa na kusoma nyaraka kwa karibu zaidi. Kingine - taarifa ya nini mimi nina kwenda kufanya. Mwingine mimi kwenda na kurudi m plus - ni nini sigma ya m? Naam, sigma ya m plus minus m 1, pamoja na m bala 2, pamoja na m bala 3. Sitaki kuandika yote ya nje kwamba. Kwa nini si mimi tu Punt? Recursively kuwaita mwenyewe na kidogo ndogo tatizo, semicolon, na kuiita siku? Haki? Sasa hapa, pia, unaweza kuhisi au wasiwasi kwamba hii ni kitanzi usio kwamba mimi nina inducing, ambapo mimi ni kutekeleza sigma na wito sigma. Lakini hiyo ni kikamilifu sawa, kwa sababu mimi walidhani mbele aliongeza mistari ambayo? Watazamaji: [inaudible]. DAVID Malan: 23 na 26, ambayo ni wangu kama hali hiyo. Kwa sababu nini ni nzuri kuhusu kutoa hapa, kwa sababu mimi kuendelea kuwapatia sigma ndogo matatizo, ndogo matatizo, ndogo - si ukubwa wa nusu. Ni hatua tu mtoto ndogo, lakini hiyo ni sawa. Kwa sababu hatimaye, tutaweza kazi njia yetu chini ya 1 au 0. Na mara moja sisi hit 0, sigma si kwenda kuwaita yenyewe tena. Ni kwenda mara moja kurudi 0. Hivyo athari, kama aina ya upepo huu juu katika akili yako, ni kuongeza m pamoja m minus 1, pamoja na m bala 2, pamoja na m bala 3, pamoja na dot, dot, dot, bala m m, hatimaye kutoa 0, na athari ni hatimaye kuongeza yote ya mambo haya kwa pamoja. Hivyo hatuna, na kujirudia, kutatuliwa tatizo kwamba sisi hakuweza kutatua kabla. Hakika, toleo 0 wa hii, na kila tatizo hadi sasa, imekuwa solvable na kutumia tu kwa tanzi au wakati mizunguko au constructs sawa. Lakini recursion, mimi daresay, inatupa njia tofauti wa kufikiri kuhusu matatizo, ambapo kama tunaweza kuchukua tatizo, kuigawanya kutoka kitu kubwa kiasi fulani katika kitu fulani ndogo, mimi kudai kwamba tunaweza kutatua hilo labda kidogo zaidi elegantly katika suala ya kubuni, na kanuni ya chini, na labda hata kutatua matatizo ambayo ingekuwa kuwa ngumu, kama tutaweza hatimaye kuona, kutatua rena iteratively. Lakini cliffhanger kwamba mimi wanataka kuondoka sisi juu ilikuwa hii. Hebu kwenda mbele na kufungua hadi faili kutoka - kweli, napenda kwenda na kufanya hivyo kwa haraka kweli. Hebu kwenda mbele na kupendekeza zifuatazo. Miongoni mwa kanuni ya leo ni faili hii hapa. Hii moja hapa, noswap. Hivyo hii ni ya kijinga kidogo mpango kwamba Mimi kuchapwa up kuwa madai ya kufanya zifuatazo. Katika kuu, ni ya kwanza anatangaza int kuitwa x na inateua ni thamani ya 1. Kisha inatangaza y int na inateua ni thamani 2. Basi ni Prints nje nini x na y ni. Kisha anasema, swapping, dot dot dot. Basi ni madai kuwa wito kazi kuitwa wabadilishane, kupita katika x na y, wazo la ambayo ni kwamba hopefully x na y atakuja tena tofauti, kinyume. Basi ni kudai walibadilishana! na kumweka Moderators. Basi ni Prints nje x na y. Lakini zinageuka kuwa hii sana rahisi maandamano chini hapa ni kweli Buggy. Hata mimi nina kutangaza muda kutofautiana na muda kuweka katika hivyo, basi mimi nina reassigning thamani ya b - ambayo anahisi nzuri, kwa sababu nimekuwa nakala ya kuokolewa katika temp. Kisha mimi update b sawa chochote kilichokuwa katika temp. Aina hii ya mchezo shell ya kusonga ndani ya b na b ndani ya hii kwa kutumia katikati-mtu mmoja aitwaye temp anahisi kikamilifu busara. Lakini mimi kudai kwamba wakati mimi kukimbia hii kanuni, kama mimi itabidi kufanya sasa - napenda kwenda mbele na kuweka katika hapa. Mimi nitakuita hii noswap.c. Na kama jina linavyosema, hii si kwenda kuwa mpango sahihi. Kufanya noswap /. Hakuna kubadilishana. x ni 1, y ni 2, swapping, walibadilishana. x ni 1, y ni 2. Kimsingi hili ni vibaya, hata ingawa hii inaonekana kikamilifu busara kwangu. Na kuna sababu, lakini sisi siyo kwenda yatangaza sababu bado tu. Kwa sasa cliffhanger pili nilitaka kuondoka na ni hii, tangazo la aina ya Coupon namba. Ubunifu wetu na siku mwishoni mwa mwaka huu umesababisha idadi zisizo yasiyo na maana ya maswali, ambayo ilikuwa Si nia yetu. Nia ya kanuni hizi Coupon, ambapo kama wewe kufanya sehemu ya tatizo kuweka mapema, na hivyo kupata siku ya ziada, alikuwa kweli kukusaidia guys kusaidia mwenyewe kuanza mapema, aina wa na incentivizing wewe. Inatusaidia kusambaza mzigo hela masaa ya ofisi bora ili ni aina ya kushinda na kushinda. Kwa bahati mbaya, nadhani maagizo yangu wamekuwa, hadi sasa, wazi sana, hivyo Mimi kurudi mwishoni mwa wiki hii na updated spec katika maandishi kubwa, bolder kwa kueleza risasi kama hizi. Na tu kusema hivyo zaidi ya hadharani, na default, tatizo seti ni kutokana Alhamisi saa sita mchana, kwa mtaala. Kama kuanza mapema, kumaliza sehemu ya tatizo kuweka na Jumatano saa 12:00 PM, sehemu ambayo inahusiana na Coupon kanuni, wazo ni kwamba unaweza kupanua tarehe ya mwisho yako kwa ajili ya P kuweka mpaka Ijumaa. Hiyo ni, kidogo mbali sehemu ndogo ya P kuweka jamaa na nini kawaida ni kubwa tatizo, na kununua mwenyewe siku ya ziada. Tena, anapata wewe kufikiria juu ya kuweka tatizo, anapata wewe masaa ya ofisi mapema. Lakini kanuni Coupon tatizo bado inavyotakiwa, hata kama huna kuwasilisha. Lakini zaidi compellingly ni hii. (STAGE Whisper) Na wale folks kuacha mapema ni gonna majuto. Kama ni folks kwenye balcony. Mimi kuomba msamaha mapema kwa folks juu ya balcony kwa sababu hiyo itakuwa wazi katika muda tu. Hivyo sisi ni bahati ya kuwa moja ya CS50 aliyekuwa mkuu mafundisho wenzake katika kampuni inayoitwa dropbox.com. Wao sana kwa ukarimu walichangia Coupon code hapa kwa ajili ya nafasi hii sana, ambayo ni juu kutoka kawaida 2 gigabytes. Hivyo nilifikiri nini tunataka kufanya juu ya hii kumbuka mwisho ni kufanya kidogo ya giveaway, ambapo katika muda tu, sisi itaonyesha mshindi na ambaye ana Coupon kificho kwamba unaweza kisha kwenda zao tovuti, aina yake katika, na voilà, kupata nzima mengi zaidi Dropbox nafasi kwa ajili yako appliance na kwa files yako binafsi. Na kwanza, ambao wangependa kushiriki katika picha hii? OK, sasa kwamba inafanya hata furaha zaidi. mtu ambaye anapata hii gigabyte 25- Coupon code - ambayo ni mbali zaidi ya kulazimisha kuliko marehemu siku sasa, labda - ni mmoja ambaye ni ameketi juu ya kiti cha mto zipitazo kuna kwamba kanuni Coupon. Unaweza sasa kuangalia chini ya kiti yako mto. [Video avspelning] -Moja, mbili, tatu. [WAKIPIGA KELELE] -Unaweza kupata gari! Unaweza kupata gari! DAVID Malan: Tutaona wewe juu ya Jumatano. -Unaweza kupata gari! Unaweza kupata gari! Unaweza kupata gari! Unaweza kupata gari! Unaweza kupata gari! DAVID Malan: Balcony folks, kuja chini hapa mbele, ambapo tuna extras. -Kila mtu anapata gari! Kila mtu anapata gari! [MWISHO video avspelning] NARRATOR: CS50 ijayo - SPIKA 5: Oh gosh wangu gosh gosh gosh gosh gosh gosh gosh gosh gosh - [UKELELE ina]