SPIKA: All haki, hii ni CS50. Hii ni mwisho wa wiki tatu, na kama una si kuchukuliwa kwa faida tayari, kujua kuwa kutakuwa na chakula cha mchana Ijumaa hii kama kawaida, ambapo unaweza kufurahia mazungumzo mazuri na chakula katika Moto na Ice na baadhi ya CS50 ya wafanyakazi na wanafunzi. Kichwa na URL hii hapa. Sasa unaweza kukumbuka, au wewe hivi karibuni inaweza kuwa khabari na, mambo haya hapa, ambayo wanapewa mwishoni wa muhula kwa ajili ya madarasa mengi. Mtihani kinachojulikana bluu vitabu, katika ambayo wewe kuandika majibu yako kwa mitihani. Sasa nina hapa 26 kama vitabu bluu, juu ya kila mmoja wao imeandikwa jina, A njia ya Z. Na kweli majina ni kuwa rahisi, A kupitia Z. Na moja ya malengo upande leo ni kwenda kuwa kuendelea nini sisi ilianza siku ya Jumatatu, ambayo ni si sana kuangalia code, lakini kwa kweli kuangalia mawazo na utatuzi wa matatizo. Moja ya malengo na ahadi ya kozi hii ni kufundisha wewe kufikiri zaidi makini, zaidi methodically, na kutatua matatizo kwa ufanisi zaidi. Na hakika, tunaweza kufanya kwamba kweli bila hata kugusa mstari wa kanuni. Hivyo mimi kuwa wanandoa wa tembo up hapa leo machungwa, na bluu, kama tunaweza kupata kujitolea moja, labda kutoka mbali nyuma kuliko kawaida. Vipi kuhusu haki pale, kuja juu chini. lengo la ambayo ni kwenda kuwa kwa msaada pamoja na kusimamia mtihani huu hapa. Nini jina lako? Watazamaji: Mary Beth. SPIKA: Mary Beth, kuja juu up. Hebu kupata kipaza sauti hapa kwa ajili yenu. Nice kukutana na wewe. Watazamaji: Nice kukutana na wewe. SPIKA: zote haki, hivyo nina hapa bluu vitabu A kupitia Z, na mimi nina kwenda kwa kujifanya kuwa Nina mmoja wa wanafunzi, na wao ni kuja katika kiasi fulani nasibu mwishoni mwa saa tatu mtihani kuzuia, hivyo ni kuishia katika baadhi Ili nusu random kama hii. Sasa kazi yako katika muda tu ni kwenda kwa be-- hii ni kweli jinsi ya kupata akageuka katika mwishoni mwa darasa, uwezekano mkubwa. Kazi yako sasa ni kwenda kuwa, kabisa tu, kwa aina vitabu hizi za bluu kwa ajili yetu kutoka kwa Z. A Watazamaji: Oh, hii ni kwenda kuchukua milele. SPIKA: Na sisi kuangalia kama wewe kufanya hili, hakuna shinikizo. Watazamaji: Hapana, hakuna shinikizo au kitu chochote. SPIKA: Na kwa ajili ya kujifurahisha, hebu kuweka up timer. Watazamaji: furaha sana, furaha sana. SPIKA: naweza kushikilia mic kwa ajili yenu. Haki wote, tumekuwa tu mara mbili kasi yetu. Hivyo katika huo huo, napenda pose nini kwenda kuwa swali kwa Mary Beth ni nini yeye kufanya, ni jinsi gani yeye kwenda juu ya kutatua hili? Na kwa kweli, unaweza kuwa na milele mawazo kuhusu kitu rahisi sana kama wakati pick up 26 vitabu kama hii, ambao hawana kuwa na asili kuagiza kwao. Ni mchakato gani kweli kwamba unatumia? Je, ni haki random tu kuokota ya kwanza unaweza kuona na kuweka katika nafasi yake? Je, kwanza hoja mikono yako karibu kuangalia kwa basi kuangalia kwa B? Je, wewe kuangalia jozi yao upande kwa upande na tu kusema, kusubiri dakika, hii si sahihi, na kisha wabadilishane ili? Tuliona tayari juu ya Jumatatu kwamba kuna idadi ya njia ambayo tunaweza kufanya hivyo, na kweli kama sisi karibu na mwisho hapa, Napenda kuchukua note labda Mary Beth ya nini ni kufanya. Tuna piles chache inaonekana, a moja kubwa, tatu madogo. Watazamaji: Mimi kuagiza yao wakati mimi kupata barua mbili kuwa mimi najua ni pamoja katika mlolongo, Mimi kuweka yao kwa pamoja ili kwamba mimi si kuwa na wasiwasi juu ya kuweka wimbo wa zima mstari wa vitabu. Ni tu, oh, A ni ya kwanza, Mimi nimepata stack hii hapa. SPIKA: Kwa hiyo, karibu kama vipande puzzle kwamba kuwa na sura haki ya match up na kila mmoja. Watazamaji: Pretty much, yeah. SPIKA: Sawa, bora. Na sasa kila moja ya haya piles ni labda yamepangwa? Watazamaji: Yeah. SPIKA: zote haki, A njia ya Z. wote haki, pongezi, wewe alifanya hivyo. Una uchaguzi wako. Blue? Haki yote, asante kwa ajili hiyo. Hivyo Mary Beth hakuwa kupendekeza mbinu gani yake ilikuwa, lakini ni mbinu gani mwingine jinsi wewe wanaweza kwenda juu ya kuchagua mambo haya? Je, ungefanya nini kosa gani? rekodi ya kuwapiga ingekuwa dakika moja na sekunde 50 au hivyo, pamoja na wale I forgot kuhesabu. Je, ungefanya nini kosa gani? Yeah? Watazamaji: Chukua stack. Kuanza tangu mwanzo. Angalia karatasi yako. Na kama moja ya juu ni juu kuliko, labda, wao ni, moja chini ni juu, kisha kubadili yao. SPIKA: Sawa, hivyo kuanzia saa ya juu na chini, na kisha kufanya kazi kwa njia yako ndani kama kwamba, swapping yao? OK, hivyo kidogo sawa katika roho Bubble aina, lakini kuchagua extremes si jozi karibu. Lakini short yake ni kwamba kuna Hakika kundi la njia mbalimbali tunaweza kufanya hii, na kusema ukweli, nadhani wewe aina ya iliyopitishwa mbinu wanandoa, haki? Unaweza kufanywa aina ya nne piles sorted, na kisha kwa ufanisi zimeunganishwa pamoja. Na kwamba ni, daresay, mwingine mbinu kabisa. Wewe hakuwa na kutibu kama moja kubwa rundo, wewe kugawanywa tatizo katika quads nne, kama wewe, na kisha kwa namna fulani ilijiunga yao katika mwisho. Basi hebu fikiria, hatimaye, jinsi mwingine tupate kufanya hivyo. Sisi rasmi dhana ya Bubble aina mara ya mwisho, na Bubble aina kukumbuka mara algorithm kwamba sisi visualized na nane wa wanafunzi wako juu hapa, inaonekana nasibu sorted mara ya kwanza. Na sisi basi aliamua pairwise, kama mambo mawili ni nje ya utaratibu, tu wabadilishane yao. Hivyo nne na mbili ni wazi nje ya utaratibu, hivyo wale classmates mbili switched nafasi. Na kisha sisi mara kwa mara na nne na sita, kisha sita na nane, juu ya kila iteration, kuhamia na haki. Hivyo kutokana na watu nane, jinsi wengi pairwise kulinganisha mimi kufanya wakati kutembea kutoka kushoto na kulia katika moja iteration hayo? Jinsi kulinganisha wengi? Saba, haki? Kwa sababu kama kuna nane watu lakini una jozi yao na wewe kuendelea kusonga mbele moja hop na haki, wewe si kwenda kuwa na nane kulinganisha kwa sababu huwezi kulinganisha kipengele dhidi ya yenyewe, au ingekuwa tu kuwa pointless, hivyo una saba. Au zaidi kwa ujumla, kama tuna watu n, sisi kufanya n 1 minus kulinganisha na Bubble aina. Hivyo hebu fikiria sasa jinsi nzuri au mbaya Bubble aina kweli alikuwa, na kujaribu kutoa wenyewe msamiati kwa ambayo kwa kukosoa algorithms kama hii, na hivi karibuni yetu wenyewe. Hivyo kupita kwanza kwa njia ya Bubble aina, mara ya kwanza Mimi kutembea kutoka upande wa kushoto na haki katika hatua, alichukua yangu n 1 minus kulinganisha. Na kwamba ni kwenda kuwa wangu kitengo cha kipimo, haki? Mimi nilikuwa aina ya kuzungumza na matembezi, kiasi fulani kwa haraka, kwa kiasi fulani polepole, hivyo kuhesabu namba yangu ya sekunde si hasa kuwaambia, lakini kuhesabu idadi ya shughuli kwamba sikuwa juu ya Jumatatu, kulinganisha watu wawili, kwamba anahisi kama nzuri kitengo cha kipimo. Hivyo n 1 minus hatua mara ya kwanza, lakini kisha kile kilichotokea baada ya kwamba? Nini kichwa moja ya kupita moja kupitia orodha vinginevyo zisizochambuliwa? Nini unaweza kuniambia kuhusu kipengele ambaye alikuwa njia yote juu ya huko? Yeah? Hiyo ilikuwa kipengele kubwa, sawa? Idadi nane, ingawa yeye ilianza hapa, kila wakati mimi ikilinganishwa yake dhidi ya jirani, aliendelea bubbling up na haki mkono upande wa orodha. Na hakika, hiyo ambapo algorithm anapata jina lake. Sasa kwa mantiki kwamba, jinsi kulinganisha wengi haja mimi kufanya juu ya mara ya pili Mimi kufanya kupita kutoka kushoto kwenda kulia? n minus 2, haki? Ingekuwa tu kuwa na kupoteza muda wangu kama mimi kuweka kulinganisha nane dhidi ya mtu mwingine kwa sababu sisi tayari kujua yeye alikuwa katika mahali pa haki. Hivyo hiyo ni kidogo ya optimization, hivyo kupita ijayo ni kwenda kuwa pamoja na n minus hatua mbili, ambapo n ni idadi ya watu. Sasa unaweza aina ya extrapolate, hata kama wewe si mwanasayansi wa kompyuta, jinsi hii mwisho. Wakati wa mwisho wa algorithm hii, labda nimepata tu kulinganisha moja kushoto. Una aina ya kurekebisha mwanzo wa orodha katika kesi mbili na moja ni nje ya utaratibu na lazima moja na mbili, hivyo hii bottoms nje katika plus 1 mwisho kulinganisha. Sasa dot, dot, dot aina ya mawimbi ni mikono katika baadhi ya maelezo juicier, lakini hebu tu kwenda mbele na kurahisisha. Kama unakumbuka kutoka juu shule, kusema ukweli, mengi ya wewe alikuwa na vitabu math kwamba alikuwa kidogo kudanganya karatasi juu ya bima ya mbele au nyuma cover ambayo ilionyesha wewe summations mfululizo nini kama hii hatimaye aliongeza hadi. Katika kesi ujumla, kama una variable kama n, na kwa kweli hii moja, kama wewe inaonekana saa yako umri wa shule ya math kitabu, ungependa kuona kwamba hii kweli zinafikia kiasi hiki hapa, n mara n 1 minus kila kugawanywa na 2. Hivyo kwa sasa napenda tu inasema hii ni kweli, kadhalika leap ya imani, kwamba ni nini hii sums juu, na tunaweza kuthibitisha kwamba katika kesi zaidi kwa ujumla. Lakini sasa hebu kupanua hii nje. Basi hebu kuzidisha hii nje, hivyo hiyo ni n squared, minus n, kila kugawanywa na 2. Hiyo ni kweli n squared, kugawanywa na 2, minus n zaidi ya 2, hivyo kwamba wote nzuri na ya kuvutia. Lakini kile kinachotokea kama sisi sasa kuziba-katika thamani? Tuseme sikuwa na nane watu, lakini kusema milioni. Na kwa sababu tu milioni ni idadi kubwa pretty, hebu kuziba kwamba katika na kuona nini kinatokea. Hivyo kama mimi kuziba milioni katika formula kwamba Mimi nina kwenda kupata milioni mraba, kugawanywa na 2, minus a milioni, kugawanywa na 2. Sasa nini kwamba kwenda sawa? Hivyo bilioni 500, minus 500,000. Na kama mimi kwa kweli kufanya kwamba math nje, kwamba njia kwamba kuchagua milioni watu na aina Bubble inaweza kuchukua mimi 499,999,500,000 hatua au kulinganisha katika mwisho, sisi ni extrapolating tu. Kwamba anahisi pretty polepole, lakini kusema ukweli kupima hasa pembejeo moja kama hii, ni si kuwaambia kwamba wote. Lakini kwa kweli haina zinaonyesha kwamba kama n anapata kubwa na kubwa, hii algorithm aina ya anahisi mbaya na mbaya, au kweli kuanza kuhisi maumivu ya kwamba exponentiation, kwamba n squared, ambayo inaongeza up pretty kufunga. Na hii undani ni si waliopotea juu ya watu, kwa kweli baadhi ya miaka iliyopita senator fulani ambaye alikuwa kampeni, waliketi kwa ajili ya mahojiano na Eric Google Schmidt, Mkurugenzi Mtendaji wa wakati huo, na ilikuwa changamoto kwa swali kiasi kama sisi ni kuchunguza leo. Hebu tuangalie. [VIDEO avspelning] -Senator, Wewe ni hapa katika Google, na mimi kama kufikiri ya urais kama mahojiano ya kazi. Sasa, ni vigumu kupata kazi kama rais, na wewe ni kwenda kwa njia ya rigors sasa. Ni pia vigumu kupata kazi katika Google. Tuna maswali, na sisi kuuliza maswali wagombea wetu, na hii ni moja kutoka Larry Schwimmer. What-- guys kufikiri mimi nina kidding, ni haki hapa. Ni njia ya ufanisi zaidi kwa nini aina milioni integers 32-bit? -Well-- -I'm Sorry, maybe-- -Hakuna, Hapana, hapana. Nadhani aina Bubble itakuwa njia sahihi ya kwenda. -Come Juu, ambaye alimwambia hii? Sikuweza kuona kompyuta sayansi katika background yako. -We've Got wapelelezi wetu huko. -OK, Wacha tujiulize mbalimbali swali mahojiano. [END video avspelning] SPIKA: Kwa hiyo kuzungumza juu ya idadi maalum ingawa, si kwenda kuwa wote muhimu kwamba. Ni si maisha ya somo kwamba Bubble aina, kutokana na milioni pembejeo, inaweza kuchukua hatua kama wengi kama bilioni 500. Unaweza si kweli kujumlisha ufanisi pia kutoka kwamba na kufanya maamuzi design nzuri wakati wa kuandika mipango. Basi hebu kuzingatia ingawa juu ya jinsi tupate kurahisisha matokeo haya. Hivyo nimekuwa yalionyesha katika njano hapa matokeo ya n squared kugawanywa na 2, hivyo milioni mraba kugawanywa na 2, na kisha Nimekuwa yalionyesha nini jibu la mwisho ilikuwa mara moja sisi subtracted off n kugawanywa na 2. Na kudai mimi nina kwenda kufanya sasa ni, ambao heck anayejali kama wewe Ondoa off umri mdogo zaidi ya 2 n wakati wa kwanza sehemu ya formula hii ni hivyo kubwa sana? Ni dominates nyingine mrefu, n squared kugawanywa na 2 ni hivyo kubwa sana, kwa uwazi, kama n anapata kubwa kama milioni, kwamba ni kweli kuna tofauti kubwa katika mwisho wa siku kati ya bilioni 500 499,999,500,000 na? Si kweli. Na hivyo kile sisi ni kwenda kufanya kama wanasayansi wa kompyuta ni kupuuza wale suala chini ya amri, na kuchukua kitu kama hii na kwa kweli tu kurahisisha kwa mrefu ambayo inaenda jambo. kubwa data seti wetu kupata, kubwa database yetu kupata, kurasa zaidi ya mtandao sisi kuwa na kutafuta, zaidi marafiki una juu ya Facebook. Kama n anapata kubwa, sisi ni kweli kwenda kwa huduma ya juu kubwa mrefu katika uchambuzi wowote kama hiyo ya algorithms yetu ya utendaji. Na mimi nina kwenda kusema, unajua nini, Bubble aina ni juu ya utaratibu wa kubwa O, juu ya utaratibu wa n squared. Ni si hasa n mraba kama tumeona, lakini ambao kwa kweli wasiwasi kuhusu sheria hizo ndogo, na kusema ukweli, ambao kwa kweli anayejali kama sisi kugawanya na 2? Hiyo tu sababu mara kwa mara. Na ni bilioni 500 dhidi ya 250 bilioni kweli kwamba kubwa ya mpango huo? Mimi nilikuwa tu kusubiri mwaka mmoja, basi laptop yangu literally kupata mara mbili kwa haraka katika vifaa, na kwamba aina ya tofauti tu inakwenda mbali kawaida baada ya muda. Nini sisi huduma ya juu ni kujieleza, sehemu wa kujieleza kwamba kwenda kutofautiana kama pembejeo yetu anapata makubwa na kubwa. Na hakika, katika ulimwengu wa kweli, kwamba ni nini kinatokea inazidi ni pembejeo kwa matatizo yetu na algorithms ni kupata kubwa. Hivyo kubwa O ni kwenda kuwa nukuu, nukuu asymptotic, kwamba sisi tu kutumia kama kompyuta wanasayansi kuelezea utendaji, au wakati kukimbia, ya algorithm. Ili tuweze kulinganisha algorithms juu ya kompyuta mbalimbali zilizoandikwa na watu tofauti, kwa kutumia baadhi tani kimsingi sawa kama idadi ya kulinganisha wewe ni maamuzi, au labda ya simu ya swaps wewe ni kufanya. Nini sisi siyo kwenda kuhesabu ni kiasi cha muda kwamba hupita juu ya saa juu ya ukuta kawaida. Nini sisi siyo kwenda kuwa na wasiwasi kuhusu ni kiasi gani kumbukumbu unatumia leo katika uchache, ingawa hiyo ni rasilimali nyingine tupate kupima. Sisi ni kwenda kujaribu msingi uchambuzi wetu juu tu michakato ya msingi, juu ya wale kusema ukweli, kwamba unaweza kuona wengi kuibua. Hivyo, pamoja na kitu kama O kubwa ya n mraba, mimi kudai kwamba O ya n squared ni juu amefungwa juu ya kile kinachoitwa mbio wakati wa Bubble aina. Kwa maneno mengine, kama wewe alitaka kudai kwamba kuna hii ukomo wa juu juu ya jinsi wengi hatua algorithm inaweza kuchukua, ni kwenda kuwa katika O kubwa ya n mraba katika kesi hii, juu amefungwa. Nini kama mimi badala mabadiliko hadithi kuwa si juu ya Bubble aina, lakini kuhusu hili amefungwa juu. Je, unaweza kufikiria algorithm kwamba tumekuwa inaonekana katika tayari ambao juu amefungwa, na kiwango cha kupima wa muda au shughuli, itakuwa alisema kuwa imepakana na n, kazi linear, si quadratic moja kwamba ni curved? Nini algorithm kwamba daima inachukua hakuna zaidi kuliko kama hatua n, au Hatua 2n, au hatua 3N? Yeah? Watazamaji: Kupata idadi kubwa katika orodha? SPIKA: Perfect, kutafuta idadi kubwa katika orodha. Kama mimi nina kupewa orodha ya watu kwa mfano, kila la nani kufanya idadi, nini ni upeo wa idadi ya hatua ni lazima kuchukua yangu, mtu sababu smart, kupata mtu mkubwa katika orodha hiyo? n, haki? Kwa sababu katika hali mbaya zaidi, ambapo ili thamani kubwa kuwa? Right, njia yote mwishoni. Hivyo katika kesi mbaya juu amefungwa, mimi ili na kwenda njia yote zaidi ya hapa na kuwa kama, oh, hapa namba nane, au chochote thamani kwamba ni. Sasa ingekuwa tu kuwa kijinga kama mimi naendelea kwenda, haki? Kuangalia kwa ajili ya mambo zaidi na zaidi kama mwisho wao ni zaidi ya hapo? Hakika, n ni amefungwa juu. Mimi hawana haja ya kuchukua hatua zaidi kuliko hiyo. Basi nini kama mimi badala mapendekezo kwamba kuna algorithms katika dunia hii ambayo na mbio wakati hiyo ni imepakana na O kubwa ya logi n, kuingia n? Ambapo tumeona huu kabla? Yeah? Watazamaji: Katika tatizo kitabu cha simu? SPIKA: Kama tatizo kitabu cha simu. Ilikuwa ni hatua ya jinsi ya nini wakati gani au jinsi machozi ni wengi alichukua mimi kupata mtu kama Mike Smith katika kitabu cha simu? Sisi alidai ni logi n, na hata kama usio wa kawaida au ni ni hazy kidogo nini a logarithm au exponent mara, kumbuka tu kwamba n logi kwa ujumla inahusu mchakato, katika kesi hii, ya kugawa kitu katika nusu tena, na tena, na tena, na tena, kama kwamba anapata inazidi ndogo kama wewe kufanya hivyo. Hivyo kuingia ya n inahusu, hakika, kwa kitabu cha simu mfano, kwa search binary katika nadharia, wakati sisi alikuwa milango virtual juu ya bodi, au wakati Sean mara kwa ajili ya kutafuta kitu fulani. Kama yeye alikuwa kutumika search binary, logi n itakuwa amefungwa juu juu ya ni kiasi gani wakati kwamba inachukua. Lakini wale algorithms kwamba mbio katika logi n kudhani undani nini muhimu? Hiyo orodha ilikuwa yamepangwa, haki? Algorithm yako ni vibaya kama mchango wako ni si Iliyopangwa, na bado unatumia kitu kama search binary kwa sababu unaweza kuruka haki juu ya kipengele bila kutambua ni kweli kuna. Sasa nini kinaweza hii ina maana, big O ya moja? Hii haina maana kwamba algorithm yako inachukua moja na hatua moja tu, ni tu ina maana inachukua mara kwa mara idadi ya hatua. Labda ni 1, labda ni 10, labda ni 1,000, lakini ni huru ya ukubwa wa tatizo. Hakuna jambo jinsi kubwa ni n, mara kwa mara wakati algorithm daima inachukua idadi sawa ya hatua. Hivyo kile anaweza kuwa algorithm tumekuwa aliyesema kuhusu au tu intuitively kwamba inakuja kwamba daima anaendesha katika kinachojulikana wakati mara kwa mara? Yeah? Watazamaji: Kuongeza namba mbili. SPIKA: Kuongeza namba mbili, 2 plus 2 ni sawa na 4, kufanyika. Hivyo kwamba inaweza kufanya kazi, nini kingine? Vipi kuhusu dunia zaidi ya kweli, yeah? Watazamaji: Kupata Jambo la kwanza katika orodha. SPIKA: Kupata kwanza kipengele katika orodha, uhakika. Tumekuwa kweli wamekuwa wakizungumza kuhusu arrays tayari, jinsi gani unaweza kupata katika kipengele kwanza katika safu, bila kujali ni muda gani safu ni katika C kanuni? Wewe tu kutumia kama bracket zero nukuu, bam, wewe ni huko. Na hakika arrays, kama kando, msaada kitu kwa ujumla inayojulikana kama upatikanaji random, random kupata kumbukumbu, kwa sababu unaweza literally kuruka kwa mtu yeyote sehemu moja. Tunaweza kufanya hivyo hata zaidi tu tunaweza rewind kwa wiki zero wakati sisi alifanya Scratch. Muda kiasi gani alifanya hivyo kuchukua kwa kusema block katika Scratch kutekeleza? Tu wakati mara kwa mara, haki? Kusema kitu, kusema kitu, haijalishi jinsi Scratches kubwa dunia ni, mara nyingi ni kwenda kuchukua kiasi kama hicho cha wakati tu kusema kitu. Hivyo kwamba ni wakati mara kwa mara, lakini nini upande flip? Kama hiyo ilikuwa ya juu mipaka, nini kama tunataka kuelezea mipaka ya chini ya algorithms wetu mbio wakati? Karibu kesi bora uwezekano, kama wewe, ingawa maneno haya inaweza kuomba bora kesi, kesi mbaya, wastani wa kesi zaidi kwa ujumla, lakini hebu tu kuzingatia juu ya mipaka ya chini zaidi kwa ujumla. Nini algorithm ambayo ina amefungwa chini ya hatua n, au hatua 2n, au hatua 3N? Baadhi ya sababu ya hatua n, hiyo ni ya chini yake amefungwa. Yeah? Watazamaji: Bubble aina? SPIKA: Bubble aina inachukua wewe hatua ya chini n, kwa nini? Kwa nini ni kwamba? Kwa nini kwamba mwanzo kuja kwenu intuitively, hata kama hana tu bado? Yeah? Watazamaji: [inaudible]. SPIKA: Ndiyo hivyo. Katika bora mazingira ya Bubble aina, na mengi ya algorithms, kama mimi mkono wewe watu nane ambao tayari Iliyopangwa, ingekuwa ujinga kwa ajili yenu, algorithm, kwenda na kurudi zaidi ya mara moja, sawa? Kwa sababu kwa haraka kama wewe kutembea kwa njia ya orodha ya mara moja, unapaswa kutambua, oh, mimi alifanya hakuna swaps, orodha hii ni Iliyopangwa, exit. Lakini hiyo ni kwenda kuchukua wewe n hatua. Na kinyume chake, nini mwingine njia ya kufikiri kuhusu hilo? Bubble aina ni omega, hivyo kusema, ya n, kwa sababu kama ukiangalia katika chini ya n vipengele, nini ni suala la msingi huko? Huwezi kujua kama ni vyema, haki. Sisi binadamu nguvu mtazamo saa nane watu na kuwa kama, oh, ni sorted, kwamba hakuwa na kuchukua yangu n hatua, lakini ni gani. Macho yako, hata kama wewe aina ya kuwa na uwanja kubwa ya maono, wewe inaonekana saa vipengele nane, wewe inaonekana saa watu nane, hiyo ni hatua nane kwa ufanisi. Na tu kama mimi kutembea kwa njia ya zima orodha kufanya mimi kutambua, ndiyo, Iliyopangwa. Kama mimi kuacha nusu ya kufikiri, kila haki, ni pretty yamepangwa hadi sasa, nini tabia mbaya ni si yamepangwa ni? Hiyo algorithms si kwenda kuwa sahihi. Inaweza kuwa kwa kasi, lakini sahihi. Hivyo basi, tuna njia ya kuelezea mipaka ya chini, na nini kuhusu wakati mara kwa mara? Nini algorithm ambayo ina chini amefungwa juu ya mbio yake wakati wa moja? Hatua 1, 2 hatua, hatua 10, lakini mara kwa mara, huru ya n, ukubwa wa pembejeo? Yeah, katika nyuma. Watazamaji: printf? SPIKA: Nini hiyo? Watazamaji: printf? SPIKA: printf. OK, uhakika. Hivyo inachukua fasta idadi ya hatua. Na mimi lazima now-- sasa kwamba sisi ni kuzungumza juu ya C code na si Scratch, kitu kama kusema, kwa printf, tuanze kupata makini. Kwa sababu printf haina kuchukua pembejeo, ni kamba, na masharti wala kitaalam na urefu. Hivyo kama sisi sasa wanataka kuchukua juu yenu, kama wewe huna akili, kitaalam sisi anaweza kusema kwamba printf haina kuchukua variable urefu pembejeo, Na hakika inaweza kuchukua zaidi wakati magazeti string hii kwa muda mrefu, kuliko huu muda mrefu. Basi nini kama sisi kufikiria tu kuchagua na kutafuta mifano? Nini juu ya Mike Smith katika simu kitabu, or search binary zaidi kwa ujumla? Katika kesi bora, nini kinaweza kutokea? Mimi kufungua kitabu cha simu na, bam, kuna idadi Mike Smith ya. Siwezi kumwita haki mbali. Alichukua hatua moja, labda hatua mbili, lakini idadi ya mara kwa mara ya hatua kama mimi got bahati. Na kusema ukweli, tuliona juu ya Jumatatu classmate yako kupata bahati kabisa mara mbili mfululizo. Na kwamba kweli alikuwa mara kwa mara wakati katika mipaka ya chini juu ya algorithm katika swali kwa ajili ya kutafuta idadi 50 nyuma ya wale imefungwa milango. Sasa, kama kando, kama wewe kugundua kwamba wote O kubwa, huku amefungwa juu, na omega, chini amefungwa, ni moja katika huo huo, kwamba ni formula sawa katika mabano, unaweza pia kusema, tu kuwa dhana tu, kwamba kitu fulani ni katika theta ya n au theta ya baadhi thamani mengine. Hiyo ina maana tu wakati kubwa O na omega ni sawa. Sasa nini kuhusu uteuzi aina? Hebu kutumia msamiati hii mpya. Katika uteuzi aina, nini tulikuwa kufanya tena, na tena, na tena? Mimi nilikuwa kwenda na kurudi kwa njia orodha, kuangalia kwa nani? idadi ndogo. Hivyo ni jinsi hatua nyingi, jinsi kulinganisha ngapi mimi kufanya ili takwimu nje ambao kipengele ndogo katika orodha alikuwa? n minus 1, haki? Kwa sababu kama mimi tu kuanza na moja mimi nina aliyopewa na mimi kuanza kulinganisha kwake, kisha kwake, naye au wake, yeye au yake, mimi unaweza tu jozi mambo pamoja n 1 minus mara kwa mara. Hivyo uteuzi aina vile vile inachukua n minus 1 hatua mara ya kwanza. Jinsi hatua nyingi gani kuchukua mimi kupata kipengele pili madogo? n minus 2, kwa sababu mimi nina kuwa bubu kama mimi kuendelea kuangalia watu sawa tena kama nimekuwa tayari kuchaguliwa kwake au yake na kuziweka katika nafasi zao. Na hatua ya tatu, n minus 3, basi n minus 4. Tumeona muundo huu kabla ya, na kwa kweli uteuzi aina vile vile ina ya juu amefungwa ya n squared kama sisi kufanya up kwamba summation. Ni ya chini amefungwa, uteuzi aina yake nini? Minimally, ni kiasi gani wakati lazima uteuzi aina kuchukua, kama sisi ni inavyoelezwa Jumatatu? Kupendekeza njia mbili. Labda ni n, kama kabla. Labda ni n squared, kama ni sasa kama amefungwa juu. Watazamaji: n squared. SPIKA: n squared. Kwa nini? Watazamaji: Kwa sababu una kufafanua [inaudible]. SPIKA: Ndiyo hivyo. Angalau kama mimi inavyoelezwa uteuzi aina ilikuwa pretty naive, kuendelea, kupata kipengele ndogo. Kwenda tena, kupata kipengele ndogo. Kwenda tena, kupata kipengele ndogo. Hakuna aina ya optimization katika pale kwamba wanaweza basi mimi mimba baada ya tu n au hivyo hatua. Hivyo kweli, uteuzi aina, omega ya n squared. Nini juu ya insertion aina, ambapo mimi alichukua ambao nilipewa, na kisha mimi plopped naye au wake katika mahali sahihi? Kisha mimi aliendelea na mtu wa pili, plopped kwake katika mahali pa haki. Kisha mtu mwingine, plopped kwake katika mahali pa haki. Taarifa kwamba hii ni sana linear, hivyo kusema. Mimi nina line moja kwa moja, mimi nina si kwenda na kurudi, Sijawahi kuangalia nyuma kwa kweli, lakini nini kinatokea wakati mimi mtatizeni au wake katika mwanzo wa orodha kama tulivyofanya Jumatatu? Nini kinatokea? Yeah? Watazamaji: [inaudible]. SPIKA: Yeah, kwamba mara catch, haki? Unaweza kukumbuka kutoka classmates wako, kama walikuwa wakifanya harakati yoyote na miguu yao ili kwamba ilikuwa operesheni. Hivyo kama kulikuwa na watu watatu hapa na mtu mpya mali, kuna njia juu, juu ya hatua ya muda mrefu kama hii, hakika, yeye au yeye anaweza tu kwenda hadi mwisho. Lakini kama sisi ni kufikiri kuhusu kompyuta na safu ya kumbukumbu, watu hawa wanaenda kuwa na changa juu ya kufanya chumba kwa mtu huyo. Na ili n minus 1 shufflings, n minus 2 shufflings, n minus 3 shufflings ni aina tu ya kinachotokea nyuma yangu, si mbele yangu kama kabla, katika baadhi ya hisia. Sasa kama kando, na kama unaweza kuwa na kuonekana online kama wewe kuanza poking kuzunguka juu ya kila aina, kuna wale wengi mbalimbali huko nje, baadhi yao bora kuliko wengine. Hakika, bogosort ni moja hiyo ni aina ya furaha na kuangalia up. Bogosort inachukua seti ya namba au kusema staha ya kadi, nasibu shuffles yao, na hundi kama wao ni sorted. Na kama si, gani tena. Na kama si, gani tena. Kama siyo, anafanya hivyo tena. Incredibly kijinga. Na hakika, kama kusoma kama makala Wikipedia, jina la utani wake ni aina ya kijinga. Ni hatimaye kazi, hopefully, kutokana na muda wa kutosha, lakini kwamba kiasi cha muda inaweza kuchukua muda kabisa. Hivyo kama mimi naweza, hebu mambo kasi up kutokana na mfano Mary Beth ya awali, kwa kuwa chache mambo zaidi, lakini wasindikaji mbili zaidi. Watu wawili, kama wewe bila akili kujiunga na yangu. Vipi kuhusu 1 zaidi ya hapa, na hebu go-- hakuna mtu zaidi ya hapo? Hakuna mtu zaidi ya hapo? OK. Wewe na nyeusi shati, ndiyo, kuja juu chini. Haki wote, nini jina lako? Watazamaji: Peter. SPIKA: Nini hiyo? Watazamaji: Peter. SPIKA: Peter, David, nzuri ya kukutana na wewe. Zote haki, tuna Peter hapa, kama wewe wanataka kuja kwenye meza ya zaidi ya hapa. Na nini jina lako? Watazamaji: Elena. SPIKA: Elena. OK, nzuri ya kukutana na wewe. Elena kukutana na Peter. Peter, Elena. Na tutaweza haja Andrew up hapa kama vizuri, tafadhali. Na changamoto yako ni kwenda kuwa na aina staha ya kadi. Na kama usio wa kawaida, staha ya kadi lazima hatimaye kutatuliwa kitu kidogo kama hii ambapo tutaweza kufanya klabu, basi spades, basi mioyo na almasi, kutoka Ace kama moja, njia yote hadi mfalme. kadi mimi nina kwenda kukupa ni kwenda kuwa 52 katika wingi. Sisi ni kwenda vile vile muda, katika muda tu. Sisi ni kwenda kutupa Andrew juu ya screen hapa, ili kuangalia kama wewe kufanya hivyo. Na hivyo kwamba haya yote ni wazi zaidi, hizi ni kadi I got juu ya Amazon. Hivyo wao ni tayari nasibu Iliyopangwa, na sisi ni kwenda kwa mara wewe. Na tunakwenda kuitunza halisi wakati huu, hivyo sisi ni kwenda kujaribu kushinikiza wewe kwa sababu vinginevyo hii kupata tedious haraka. Kama unaweza kuendelea na aina 52 mambo pamoja kupitia baadhi ya njia, sasa. Na tena, kama sisi kuangalia hizi guys kufanya nini, katika mwisho ni kwenda kuzalisha dhahiri Matokeo yake, kufikiri juu ya kweli jinsi re kila kufanya hivyo, jinsi gani unaweza kuelezea. Kwa sababu tena, hizi ni taratibu zote, algorithms kwamba sisi kuchukua kwa nafasi kama binadamu. Lakini ve pengine kwa muda mrefu alikuwa Intuition, kwa muda mrefu kabla hata mawazo kuhusu kuchukua sayansi ya kompyuta darasa wewe anaweza kuwa na Intuition na ambayo kutatua matatizo kama hii. Lakini mara moja wewe kutambua mwelekeo na kuanza kurasimisha hatua ambayo wewe kutatua matatizo haya, utapata kwamba unaweza kutatua mengi zaidi ya kuvutia na tata zaidi matatizo ya haraka. Hivyo mtu kutoka watazamaji, ni nini kipengele angalau moja ya algorithm kwamba wao ni kutumia hapa? Watazamaji: [inaudible] SPIKA: Nini hiyo? Watazamaji: Kwa nyayo. SPIKA: Kwa nyayo. Hivyo kwanza wao ni kuunganisha yote ya almasi pamoja inaonekana, yote ya mioyo pamoja inaonekana, na kadhalika, bila heshima kwa idadi ya kadi. Na sasa wao kuonekana, kwa mfano, kuwa kuchagua yao na idadi. Nzuri sana. Haki zote, hivyo nini kinaendelea kuwa hatua ya mwisho basi hapa? Mara baada ya tuna nne suti sorted, nini kufanya sisi haja ya kufanya ili piles nne ili kufikia moja namna ya staha, kwa urahisi kabisa? Kwa hiyo, tunahitaji kuunganisha yao tena. Hivyo kuna wazo kuvutia ambayo tena, daresay, ni Intuitive sana hata kama unaweza kamwe kuwa slapped aina hiyo ya studio juu yake. Hii dhana ya msingi ya kugawa tatizo si katika wakati huu nusu, lakini angalau katika vipande nne. Kutatua pretty much matatizo ya kimsingi kufanana katika kutengwa wa kila mmoja, na kisha kuunganisha matokeo. Na, bora, kufanyika. Haki zote, pande zote kubwa ya applause, kama tunaweza. [Makofi] SPIKA: Mimi sijui nini utasikia kufanya na hayo, lakini hapa kwenda. Asante sana. Basi hebu angalia, dakika mbili na sekunde nane, kama Ningependa kutoa changamoto kwa rafiki yako. Ni nini basi ni kwenda kuwa kuchukua mbali na hii kwamba tunaweza kujiinua zaidi kwa ujumla? Naam, kufikiri nyuma safu hii ya idadi, na kufikiri nyuma sasa kwa baadhi ya pseudocode tumekuwa imeandikwa katika siku za nyuma, na hii ilikuwa pseudocode kwa kutatua tatizo kitabu cha simu. Ambapo katika pseudocode mimi enumerated njia zaidi methodical ya kuelezea jinsi mimi alifanya Intuitive sana algorithm binadamu wa kugawa simu kitabu katika nusu, kurudia, kurudia, kurudia, mpaka mimi kupata mtu kama Mike Smith, kama yeye ni kweli katika kitabu cha simu. Lakini mimi aina ya kutumika kile Mimi nitakuita mbinu iterative sana hapa, katika ilani hasa mstari wa 8 na line 11. Wale ni ushahidi wa iterative mbinu, mbinu looping, kwa sababu hiyo hasa tabia wao kushawishi. Wale wote mistari kusema kwenda kwa line tatu, na unaweza aina ya kufikiri ya kwamba katika yako macho ya akili ya kuwa kitanzi. Ni ninawaambieni kwa kwenda nyuma juu ya hatua tatu na kurudia, tena, na tena, na tena. Lakini nini kama sisi kujiinua wazo muhimu hapa kwamba hatukuwa mara ya mwisho, na kurahisisha line 8 na line 11 na majirani zao kama tu hii, katika njano. Ni si kimsingi shortening pseudocode sana, lakini ni kubadilisha kimsingi asili ya algorithm yangu. Nini mimi sasa kusema katika hatua 7, katika hatua 10, ni kutafuta kwa Mike katika halisi njia hiyo hiyo, lakini tu katika wa kushoto nusu au nusu ya haki. Hivyo kwa maneno mengine, kama Mimi kuanza kutoka hatua moja, kuchukua kitabu cha simu, wazi katikati za kitabu cha simu, kuangalia majina, kama Smith ni kati ya jina ya, piga Mike, mwingine kama Smith ni mapema katika kitabu, hatua saba kutafuta Mike katika nusu kushoto ya kitabu. Lakini hiyo aina ya anahisi kama ni kuondoka kwangu kunyongwa, haki? Katika njano, ni mafundisho, lakini jinsi gani mimi kutafuta Mike katika wa kushoto nusu ya kitabu cha simu? Wapi mimi na algorithm ambayo mimi Unaweza kutafuta kwa mtu kama Mike Smith? Naam, ni staring us uso kwa uso. Siwezi literally kutumia exact mpango kwa ufanisi kwenda hadi juu tena na re-mbio mistari hiyo ya kificho. Hivyo hata ingawa hii anatakiwa kujisikia kama kidogo ya ufafanuzi mzunguko ambapo wewe ni kujibu mtu ni swali na tu aina ya kuuliza swali moja tena, kama nini, kwa nini, kwa nini? Ukweli ni kwa sababu tumekuwa ngumu coded wanandoa wa mistari maalum, hatua ya 4, ambayo ni kama, na hatua 12, ambayo ni ufanisi mwingine tawi, kwa sababu tuna hatua hizo stopgap, algorithm hii kusitisha kama sisi kupata Mike, au kama sisi hawana. Lakini katika hatua 7 na 10 sasa, tuna nini tutaweza kuwaita algorithm kujirudia. Na kujirudia ni kweli wazo nguvu hiyo ni akili kidogo bending mara ya kwanza, kwamba sisi sasa wanaweza kuomba kama ifuatavyo. Kuunganisha aina itakuwa aina mwisho kwamba sisi kuangalia, angalau katika darasa rasmi. Na ni tofauti kimsingi kutoka kwa wale mitatu iliyopita, na kwa hakika mwisho nne ikiwa ni pamoja na sisi bogosort. Hapa ni pseudocode kwa kuunganisha aina. Wakati juu ya mchango wa mambo n, hivyo kutokana na safu ya ukubwa n, ikiwa ni n chini ya 2, kurudi. Hivyo kwa nini mimi kuwa na kwamba sanity kuangalia kwanza? Nini maana kama mimi mkono wewe safu ambaye urefu n ni chini ya 2? Ni tayari Iliyopangwa, ni wazi, haki? Kwa sababu orodha ama ina kipengele moja, ambayo ni trivially yamepangwa kwa sababu ni Kitu pekee huko. Au, ni ya kawaida sifuri ambayo ina maana kuna kitu kutatua, hivyo kwa asili ni Iliyopangwa. Kuna kitu tu makosa huko. Hivyo hiyo ni kesi yetu kinachojulikana msingi. Hiyo ni sawa katika roho kwa nini sisi alivyofanya kwa Mike. Kama Mike katika kitabu cha simu, kumwita. Kama yeye si huko, kutoa up. Ni kinachojulikana kesi ya msingi, ili kuhakikisha algorithm hii ifikapo mwisho wa siku kuacha katika mazingira fulani. Lakini hapa ni leap ya imani sasa, mwingine, aina nusu ya kushoto ya mambo, kisha kutatua haki nusu ya vipengele, na kisha kuunganisha halves Iliyopangwa. Na hapa ni ambapo anahisi kama sisi ni copping nje. Nimekuwa aliuliza wewe kutatua n vipengele, na mimi nina akisema, OK, kufanya hivyo kwa kuchagua kushoto na kuchagua haki. Lakini ninachosema moja Jambo jingine, na hii ni mandhari muhimu inaonekana katika Intuition hivi sasa, kuna hatua hii ya tatu ya kuunganisha. Ambayo hata kama ni inaonekana hivyo bubu katika roho, kama tu kuunganisha mambo pamoja, inaonekana kuwa hatua muhimu kuelekea reassembly ya matatizo mawili ambayo waligawanyika hatimaye katika nusu. Hivyo kuunganisha aina, hebu kufanya hili, kama wewe utakuwa ucheshi mimi, pamoja na moja zaidi maandamano, hivyo tu kwamba tuna baadhi ya namba kufanya kazi pamoja. Je, mimi kubadilishana stress nane mipira kwa watu nane? Zote haki, vipi kuhusu wewe tatu, nne katika sehemu hii, tano, sita, na hebu je 7, 8, kuja juu up. OK, yeah OK. Minus 8, kuna sisi kwenda, plus 1. Excellent. Haki zote kuja juu juu, hebu haraka kukupa idadi. Namba mbili, namba tatu, namba nne, namba tano, sita, saba, na wanane. Mimi nane kwa usahihi wakati huu. OK, hivyo kwenda mbele kama unaweza, na hebu kutatua ili awali kwamba tulikuwa jana ambayo inaonekana kama hii, kama isingekuwa akili. Na hebu kufanya hivyo mbele ya meza. Haki zote, hivyo kuunganisha aina. Hii ni pale ambapo ni kwenda kupata aina ya kuvutia, kwa sababu mimi wanaonekana kuwa kutoa mwenyewe sana habari chini leo. Hivyo kuunganisha aina ya kwanza ya yote juu ya mchango wa mambo n, na ni wazi si chini ya mbili, ni nane, hivyo mimi na baadhi ya kazi zaidi ya kufanya. Hivyo sasa kiakili sisi kama darasa ni sasa katika mwingine tawi, ambayo ina maana hatua tatu. Kwanza, mimi kuwa na aina kushoto nusu ya vipengele. Hivyo ni jinsi gani mimi kwenda juu ya kufanya hii? Naam, mimi nina kwenda aina ya kiakili kugawanya orodha hapa, huna kwa kimwili hoja, na mimi nina kwenda kuzingatia tu juu ya kushoto nusu ya mambo hapa. Hivyo ni jinsi gani mimi kwenda juu ya kuchagua orodha ya sasa ukubwa nne? Nini algorithm wangu? Kwanza mimi kuangalia ni n chini ya miaka miwili, hapana, hivyo mimi kuendelea na mwingine block tena. Aina kushoto nusu ya vipengele. Hivyo sasa tena, kiakili, na hii ni mahali ambapo una inaingia mengi ya historia ya akili, kama wewe. Sasa mimi nina kuchagua kushoto nusu ya nusu kushoto. Haki zote, hivyo sasa mimi wito kuunganisha yangu huo kuchagua algorithm, ni n chini ya miaka miwili? Hapana, ni mbili, hivyo nina kutatua kushoto nusu, na nusu ya haki. Hivyo hapa sisi kwenda, kutatua kushoto nusu. Kwa nini si wewe tu kuchukua hatua moja mbele. Nini jina lako? Watazamaji: Darren. SPIKA: Dan. Dan ina kupitiwa mbele. Watazamaji: Darren. SPIKA: Darren, kufanyika. Je, kusema Darren au Dan? Watazamaji: Darren. SPIKA: Darren. OK, Darren ameongeza mbele na yeye ni sasa Iliyopangwa. Na hii ni karibu inane madai, haki? Mimi si kweli wanaonekana kuwa kufikia kitu chochote, lakini hebu kuendelea. Sasa basi mimi aina haki nusu ya vipengele. Nini jina lako? Watazamaji: Luke. SPIKA: Luke. Kuja juu, hatua mbele. Kufanyika, mimi kuwa yamepangwa Luke. nusu kushoto ni sasa sorted na nusu haki ni sasa Iliyopangwa, lakini tena, kuna hatua muhimu hapa. Je, mimi ijayo haja ya kufanya? Kuunganisha halves Iliyopangwa. Sasa tunakwenda tu kila mtu na kurudi katika njia hii, kwa sababu mimi aina ya haja baadhi ya nafasi mwanzo. Ni karibu kama haya guys ni juu ya meza, na mimi haja ya baadhi ya chumba kwa hoja yao kote juu ya. Hivyo nina kwenda kwa kuunganisha you guys kwa kuangalia katika nusu kushoto na nusu wa kulia. Na ambaye ni wazi anakuja kwanza, kushoto nusu au nusu haki? Hivyo nusu haki, hivyo hebu hoja juu ya Luke hapa kwa Darren ya nafasi ya awali. Na sasa kwa kuunganisha nusu yao ya kushoto katika, Darren kinaendelea kwa hoja haki pale. Hivyo anahisi kama karibu Bubble aina athari, lakini algorithm yangu ya msingi, tofauti sana wakati huu. Lakini sasa ni ambapo mambo kupata kidogo annoying kwa sababu wewe kuwa na rewind kiakili wapi mimi kuondoka mbali. Nimekuwa tu ilijiunga halves sorted, ambayo ina maana mimi nina ambapo katika algorithm wangu? Nina kutatua nusu haki, haki? Kama wewe rewind, literally juu ya video, itabidi kuona kwamba sisi got hii hatua ya Luka na Darren na kuchagua kushoto nusu ya nusu kushoto. Kisha sisi ilijiunga wale halves sorted, ambayo ina maana hatua ya pili ni aina nusu haki ya nusu kushoto. Haki zote, hivyo hebu kufanya hivyo haraka zaidi. Haki wote, sita, mimi nina kwenda kudai wewe ni sasa yamepangwa, kuja juu mbele. Nini jina lako? Watazamaji: Adriano. SPIKA: Adriano. Adriano sasa ni Iliyopangwa. Na nini jina lako? Watazamaji: Alex. SPIKA: Alex sasa ni Iliyopangwa. Kushoto nusu, nusu haki, nini hatua ya mwisho? Kuunganisha. Pretty yasiyo na maana, hivyo mimi nina kwenda kuunganisha katika sita, kuchukua hatua nyuma, nane, kuchukua hatua nyuma. Na sasa taarifa hii ni takeaway muhimu, nini ni sasa kweli kuhusu nusu ya kushoto ya orodha, bila kujali jinsi sisi ilianza? Ni vyema. Sasa ni si vyema katika mpango kubwa ya mambo, lakini ni vyema kujitegemea ya nusu nyingine. Sasa nini hatua niko juu ya kama mimi kuweka rewinding jinsi hadithi alianza? Sasa nina kutatua nusu ya haki. Hivyo sasa sisi ni njia nyuma katika mwanzo wa hadithi, na hebu kufanya hivyo kwa kasi zaidi. Hivyo nina kwenda kwa aina nusu haki ya orodha nzima. Nini hatua ya pili? Aina kushoto nusu ya nusu ya haki. Aina kushoto nusu ya kushoto nusu ya nusu ya haki. Na nini jina lako? Watazamaji: Omar. SPIKA: Omar, hatua mbele, kufanyika. Nusu kushoto ni Iliyopangwa. Na nini jina lako? Watazamaji: Chris. SPIKA: Chris, kuchukua hatua mbele, wewe ni sasa Iliyopangwa. Nini hatua muhimu sasa? Kuunganisha. Hivyo mtu ni kwenda kuunganisha katika nafasi hapa, kama unaweza kuchukua hatua nyuma, na tatu ni kwenda kuchukua hatua nyuma, kuunganisha. Hivyo nusu ya kushoto ya nusu haki, sasa ni Iliyopangwa. Kwa kweli, algorithm hii anahisi kama sisi ni kupoteza muda njia zaidi kuliko kabla, lakini kama sisi alifanya hivyo katika muda halisi, tutaweza kuona nini takeaways kwenda kuwa. Sasa hapa mimi, haki nusu ya nusu haki, basi mimi kwenda mbele na aina nusu kushoto. Hatua ya mbele, nini jina lako? Watazamaji: Ramsey. SPIKA: Ramsey ni sasa Iliyopangwa. Nini jina lako? Watazamaji: Marina. SPIKA: Marina ni sasa yamepangwa kama vizuri, kama wewe kuchukua hatua moja mbele. Hatua muhimu ya hapa ni sasa kuunganisha, mimi nina kwenda kung'oa kutoka kwenye orodha ya wangu wawili, kushoto na kulia. Tano ni kwenda kuja kwanza, na saba ni kwenda kuja ijayo. Na tena, hii ni makusudi. ukweli kwamba wao ni kuchukua hatua mbele na nyuma ni maana ya kuwakilisha kwamba tunaweza si kufanya algorithm hii katika nafasi ya kama kwa urahisi kama Bubble aina, na uteuzi aina, na insertion aina ambapo sisi tu naendelea swapping watu. I literally haja aina karatasi ya mwanzo katika ambayo kuweka folks hizi wakati mimi kufanya kuunganisha, na kisha siwezi kuweka yao nyuma katika mahali. Na kwamba ni muhimu kwa sababu mimi nina kutumia rasilimali mpya, nafasi, si tu wakati. OK, hii ni ajabu. Kushoto nusu ni Iliyopangwa, nusu haki ni sorted, sasa kuwa muhimu kuunganisha hatua. Jinsi mimi kwenda kuunganisha hii? Hivyo kama wewe utakuwa kufuata yangu mkono wa kushoto na mkono wa kulia, Mimi nina kwenda kwa uhakika mkono wangu wa kushoto katika nusu ya kushoto, upande wangu wa kulia katika nusu haki, na sasa mimi kuwa na kuamua hatua kwa hatua nani wa kuunganisha katika. Ambaye ni wazi anakuja kwanza? Namba moja. Hivyo kuja juu zaidi ya hapa, hapa ni mwanzo wetu pedi. Hivyo sasa namba moja, na tangazo la nini la kufanya kwa mkono wangu wa kulia, Mimi nina kwenda kwa hoja upande wangu wa kulia moja hatua ya juu kwa uhakika namba tatu, na sasa nina kufanya uamuzi huo. Na kwa kweli kusimama haki katika mbele ya Luke hapa kama unaweza, kwa sababu hii ni mwanzo wetu pedi. Hivyo ajaye ijayo? Tuna Luke na namba mbili au Chris na idadi tatu. Ni wazi Luke, idadi mbili, hivyo kuja hapa. Lakini mkono wangu wa kushoto sasa ni kwenda kuwa incremented kwa kumweka katika Darren, na hapa ni muhimu kuchukua mbali na kuunganisha, mimi nina kwenda kuendelea kufanya hivyo, ni wazi, kama wewe aina ya kufuata mantiki. Lakini mikono yangu ni kamwe kwenda nyuma, ambayo ina maana mimi nina milele tu kuhamia kushoto na mchakato wangu kuunganisha, na kwamba itakuja kuwa muhimu kwa uchambuzi wetu katika muda tu. Hivyo sasa hebu kumaliza hii kwa kasi. Hivyo tatu huja ijayo, kisha nne huja ijayo, na sasa tano huja ijayo, basi sita, na saba, na kisha hatimaye nane. Anahisi kama algorithm slowest bado, lakini si kama sisi kweli kuendesha katika aina hiyo ya saa kasi, hivyo kusema, na huo Baada ya kuangalia saa kama kabla. Kwa nini? Naam, Hebu kuchukua kuangalia matokeo ya mwisho. Hebu kwenda nyuma zaidi ya hapa, basi mimi kuvuta up maandamano kuibua ya nini sisi tu hawakuwa. Zooming katika hapa, juu ya hili ukurasa hapa, kuwaambia Firefox kwamba tunataka foleni up katika sanduku hii, hebu kusema Bubble aina, na ambayo sisi ni sasa vizuri familiar, uteuzi aina, ambayo ni mwingine haki moja kwa moja moja, na sasa leo kuunganisha aina, ambayo itakuwa mwisho wetu climactic. sababu ilichukua muda mrefu sana hapa na binadamu na mimi kwa maneno ni, wazi, mimi nina akielezea kila hatua. Lakini kama wewe tu nitafanya hii, kiasi kama tulivyofanya Bubble aina na uteuzi aina si tu kuibua, kuangalia tu kiasi gani kwa ufanisi zaidi leveraging hii ya mgawanyiko na mshindi inaweza kuwa wakati kutumika kwa kuweka data hiyo ni hata ukubwa nane, lakini hata sana, kubwa sana. Mimi kukupa kuunganisha aina, kwa upande upande na algorithms hizi nyingine. Hii ni kwenda kupata chungu haraka, na mwisho si hasa climactic, wao tu kuishia Iliyopangwa. Lakini muhimu kuchukua ni kwamba kuangalia ni kiasi gani kwa kasi kuunganisha aina mara, isipokuwa wewe kufikiri mimi nina aina tu ya messing na wewe. Kama sisi kufanya wakati huu moja ya mwisho, Hebu upya hii, hebu kwenda nyuma na kuchagua Bubble aina, na tu kwa ajili ya mateke, hebu kuchagua insertion aina, tu kwa ajili ya hatua nzuri. Na wakati huu tena, hebu kuchagua kuunganisha aina na hebu kweli kuendesha upande haya kwa upande. Na si, kwa kweli, fluke. Kile nimepata kufanyika ni kwa ufanisi nimekuwa kugawanywa pembejeo yangu katika nusu, tena, na tena, na tena. Na kuna tu hivyo mara nyingi unaweza kugawanya mchango wako katika nusu, kushoto na kulia. Nini formula kwamba sisi kuendelea kuona kwamba inaeleza mgawanyiko katika nusu tena, na tena, na tena, na tena? Watazamaji: Ingia n. SPIKA: Ingia n. Lakini basi kuna hatua moja nyingine muhimu ni, algorithm hii si logi n hatua. Kama walikuwa tu logi n hatua, sisi itakuwa katika tatizo moja kama kabla ya ambapo hatuwezi kuwa kuhakikisha kila kitu ya Iliyopangwa. Una minimally kuangalia mambo n kuwa na uhakika n mambo ni vyema, vinginevyo ni leap ya imani. Hivyo ni ya chini logi n hatua, lakini nini kuhusu hili kuunganisha hatua muhimu ambapo mimi ilijiunga nusu wangu wa kushoto na kulia nusu na kutembea katika hatua? Jinsi hatua nyingi ni kwamba kwa kuunganisha? Ni n, lakini mimi si tu kuunganisha wakati wa mwisho. Juu ya kila ya simu hizo nested, juu ya kila ya huingiza wale nested, mimi bado Iliyopangwa. Mimi ilijiunga guys hizi mbili, kisha hizi mbili guys, basi guys hizi mbili na kadhalika. Hivyo mimi kuunganisha tena, na tena. Ni mara ngapi? Hivyo kila wakati mimi kugawanywa orodha katika nusu, mimi kuunganisha. Kugawanya orodha katika nusu, kufanya kuunganisha. Hivyo kama kugawa orodha kifanyike mara logi n, na kuunganisha hatimaye inachukua n hatua, nini inaweza kuwa sasa juu amefungwa juu ya mbio wakati wa algorithm yetu? n logi n. Na hakika, kwamba ni nini tumekuwa mafanikio hapa. Hivyo kujisikia kwamba unaweza kuona kuibua wakati mambo matatu kukimbia upande kwa upande ni n squared dhidi ya n mraba dhidi ya n logi n. Ambayo kimsingi tutaweza kuona, si tu leo ​​lakini katika siku zijazo, ni mengi, mengi zaidi. raundi ya applause kwa guys haya, Mimi malipo yao na mipira stress. Hebu kuahirisha hapa leo, na sisi kuona juu ya Jumatatu.