[Music kucheza] DAVID J. Malan: Hii ni CS50. Na hii ni mwanzo wa wiki tatu. Hivyo sisi tumepewa mengi ya kusisimua mambo ili kufidia leo. Fursa nyingi kwa kujitolea juu ya hatua. Na hatimaye, leo ni si kuhusu kificho hata kidogo. Lakini ni kuhusu mawazo, na ni kuhusu algorithms, na kwa kweli kurejesha baadhi ya mambo ya kujifunza kutoka wiki sifuri, eti kukumbuka, sisi ilianzisha monstrosity hii. Na kukopa msukumo na kwamba, kuanza kutatua milele kisasa zaidi matatizo algorithmically. Lakini kwanza, michache ya matangazo. Hivyo moja, kama ungependa kujiunga Wafanyakazi CS50 na wanafunzi katika chakula cha mchana Ijumaa hii, wote hapa na katika Cambridge, na katika New Haven, tafadhali ziara kozi tovuti, ambapo URL yanaweza kupatikana. Hotuba hii Jumatano kuwa hapa katika Sanders. Itakuwa online tu, hivyo kutusikiliza katika tovuti CS50, kama hapa katika Cambridge au New Haven pia. Na kisha kuweka tatizo wawili Tayari ni katika mikono yako. Kama si dived katika bado, naomba kutoa maoni yenye maneno makali kwamba, hasa sasa, kama tatizo seti mapema, wewe kweli kufanya unataka kuanza sasa, kama si dabble kidogo juu ya mwishoni mwa wiki au kabla wakati wao wa kwanza kwenda nje ya Ijumaa, kwa sababu wewe utakuwa kupata kwamba wao ni si lazima kupata tena au zaidi changamoto kwa se. Nadhani utapata kwamba, katika ujumla, wao huwa na kuchukua takribani karibu sawa na kiasi cha muda. Lakini ni hakika inategemea juu ya mwanafunzi, na inategemea mawazo na ambayo wewe mbinu yake. Lakini invariably, wewe ni kwenda kuendesha dhidi baadhi ukuta, na wewe ni kwenda kugonga baadhi mdudu, na wewe tu si kwenda kuwa na uwezo wa kupata juu yake wakati fulani. Na ni hugely muhimu kwa kuwa na uwezo hatua mbali, kurudi siku inayofuata, kwenda masaa ya ofisi, baada ya juu CS50 Jadili au kama, kwa kweli kupata imefunguliwa. Hivyo kuendelea kuwa katika akili. Kuanzia mwanzo iwezekanavyo ni jambo bora unaweza kufanya. Hivyo hapa ni wapi sisi kuanza darasa, zaidi ya wiki sifuri. Na tunaweza kupata kujitolea hapa anisaidie kupata vipaza sauti? SAWA. Alisimama tayari. Kuja juu juu. Nadhani hiyo ni jinsi ni kwenda kufanya kazi. Jina lako ni nini? ALAN ESTRADA: Alan Estrada. DAVID J. Malan: Alan Estrada. Kuja juu juu. Vyema kukutana na wewe. ALAN ESTRADA: Nice kukutana na wewe. DAVID J. Malan: Na ungekuwa hapa na sisi katika wiki sifuri, bila shaka. ALAN ESTRADA: Nilikuwa. Nilikuwa. DAVID J. Malan: Hivyo inaweza kwenda mbele na kupata kwa ajili yetu Mike Smith, kama kufunga kama unaweza? Kama kufunga kama unaweza. Halisi kuchanika tatizo katika nusu kama unahitaji. ALAN ESTRADA: Um. DAVID J. Malan: Literally kuchanika tatizo katika nusu. ALAN ESTRADA: Oh. Mm. Vizuri sana. DAVID J. Malan: Sawa. Nzuri. Asante. ALAN ESTRADA: vizuri sana. SAWA. DAVID J. Malan: Na hivyo sasa, umefanya whittled chini kwa nusu ya ukubwa wa tatizo. Sasa, sisi ni chini ya robo. Je, wewe ni kulipa kipaumbele kwa ambayo upande sisi ni kuweka? [Akicheka] ALAN ESTRADA: Ndiyo, mimi think-- DAVID J. Malan: Je, ni sehemu sisi katika? ALAN ESTRADA: Mufflers, hivyo. DAVID J. Malan: Sawa. Lakini Mike Smith ni kwenda kuwa baada Mufflers. So-- [Akicheka] Sawa. ALAN ESTRADA: wapi sisi kuangalia? DAVID J. Malan: Mike Smith. ALAN ESTRADA: Mike Smith. DAVID J. Malan: Sasa, tuko katika upasuaji. Sasa, waganga. Now-- ALAN ESTRADA: Let's- twende kwa kweli. Halisi. DAVID J. Malan: Real. SAWA. Kama unahitaji Real. Sasa, njia ambayo ni Mike Smith? ALAN ESTRADA: Kwa njia hii. DAVID J. Malan: Ni njia? ALAN ESTRADA: Ngoja. M is-- haki? Tulianza with-- DAVID J. Malan: Yeah. Wao ni kushoto. Wako wa kulia. ALAN ESTRADA: Naam. DAVID J. Malan: Hivyo Mike katika hapa. ALAN ESTRADA: nini? [Akicheka] Mfano mbaya, nyie. Pole. DAVID J. Malan: hii kufundisha wewe ataruka nje ya mwenyekiti wako. ALAN ESTRADA: Oh. Loo. Nimekuelewa. Nimekuelewa. Loo. Loo. Hii is-- sawa, I got wewe. Smith hapa hapa? DAVID J. Malan: Smith, asante. Hivyo mimi itabidi kuweka kuangalia juu Smith? ALAN ESTRADA: Oh, yeah. Hapana, hapana, hapana. Oh, hakuna. Hii ni yangu. DAVID J. Malan: Oh, wewe got Smith. SAWA. ALAN ESTRADA: Yeah, mimi got Smith haki hapa. Samahani, nyie. Nilidhani Michael-- sisi walikuwa wanatafuta Michael. Pole. DAVID J. Malan: Ni sawa. Haki zote, sasa tuko ndani ya Paccini na Wana. ALAN ESTRADA: Paccini na wana. DAVID J. Malan: wewe tu na mimi ni katika juu ya hili. SAWA. Kupata sisi Mike Smith. Smith. ALAN ESTRADA: Smith. DAVID J. Malan: Smith. Tuko katika R kwa takataka. ALAN ESTRADA: Taka. Loo. Hii ni kwenda kuchukua muda. [Akicheka] DAVID J. Malan: viatu. Tuko katika viatu. ALAN ESTRADA: Sasa tuko gonna-- DAVID J. Malan: Nice. ALAN ESTRADA: Which-- [Akicheka] Oh, hii ni kubwa. [Akicheka] DAVID J. Malan: Ni sawa. ALAN ESTRADA: Oh, hii ni nzuri. Sidhani nina kwenda na marafiki PSAT baada ya hii. DAVID J. Malan: Mwema. Vifaa. ALAN ESTRADA: Vifaa. Um, L, M, N, O, P. DAVID J. Malan: Sawa. Basi hebu machozi huu katika nusu. Ni sawa. Hii kuishia vibaya anyway, kwa sababu Mike Smith haitakuwa katika kurasa njano. ALAN ESTRADA: Aw. DAVID J. Malan: Hapana, ni sawa. Lakini hebu kujifanya kama yeye ni juu ya ukurasa huu. Hivyo sasa, umefanya whittled tatizo chini kwa ukurasa mmoja, na sisi kupatikana Mike Smith. [Wakishangilia] Sawa, asante. SAWA. Hiyo ilikuwa ni ajabu. Lakini ilikuwa bado kasi kuliko tafuta linear, eti sisi kuanza saa mwanzo wa kitabu, na sisi hoja njia yetu kutoka kushoto kwenda kulia, hatimaye kutafuta Mike Smith. Na hivyo, kama kitabu cha simu alikuwa labda 1,000 kurasa, labda ingekuwa kuchukuliwa sisi 10 au hivyo ukurasa machozi. Lakini unaweza kuwa leveraged kuguswa na kudhani wakati yote hayo, ambayo ni kusema kwamba kitabu cha simu mapema ilikuwa nini? Watazamaji: Yamepangwa. DAVID J. Malan: Ni vyema. Sawa? Ni sorted alphabetically, hivyo kwamba wote wa majina hayo na namba ni sorted kutoka A kwa Z, na alphabetically katika kati ya. Lakini leo hii, sisi sasa kuuliza swali, vizuri, jinsi gani Verizon au simu kampuni kupata ndani ya hali hiyo? Kwa sababu ni jambo moja kujiinua dhana kwamba, na kwa hiyo, kutatua tatizo na algorithm kwa ufanisi zaidi. Lakini sisi kamwe kweli aliuliza katika wiki sifuri, vizuri, kiasi gani alifanya hivyo gharama Verizon au mtu mwingine kupata kwamba kitabu cha simu ili Iliyopangwa? Sawa? Haijalishi kama kuangalia juu Mike Smith ni super haraka, kama inachukua wewe mwaka wa kutatua kurasa awali. Sawa? Unaweza pia kuchuja tu kupitia randomized kitabu cha simu, ikiwa ni kwenda kuwa super ghali kwa aina yake. Hivyo kama tunaweza kuwa na kujitolea mwingine. Hebu kuchukua kuangalia juu hapa katika jinsi sisi might-- kuja juu up-- jinsi tupate kwenda juu ya kuchagua hawa. Na kama Jordan inaweza kweli kujiunga na sisi hapa juu ya hatua. Kuja juu juu kwa muda tu. Jina lako ni nini? CAROLINE: Caroline. DAVID J. Malan: Caroline, kuja juu juu. Na wewe utakuwa na kujiunga na na mimi na Jordan hapa. Caroline, asante. Sawa. Hivyo nini sisi hapa kwa Caroline ni bluu vitabu 26 kwamba FAS anatumia kusimamia baadhi ya mwisho mitihani. Hizi ni kupata vigumu kupata, lakini kile ambacho tumefanya mapema ni kwamba tumekuwa kuweka jina la mtu mbele ya kila moja ya haya, lakini tumekuwa naendelea ni rahisi na kisha kuweka nje majina kamili. Hivyo tunataka kuweka mtu kwa jina L, D, J, B, kila njia A kupitia Z, lakini wao ni katika mpangilio maalum. Na hivyo kama wewe ungekuwa, kuzungumza yako njia tatizo kama wewe kufanya hivyo, unaweza kwenda mbele na aina hizi kwa ajili yetu, kutoka kwa Z. Watazamaji: OK, hivyo L ni kama, kati. C ni mwanzo. B. J kabla L. B, SWALI: DAVID J. Malan: Hold kwamba wazo kwa ajili ya pili moja. Kwa sababu vinginevyo, hili ni tu kuvutia na wewe, mimi, na Jordan. Kuna sisi kwenda. Watazamaji: [inaudible]. R. DAVID J. Malan: Sawa. Unafanya nini? CAROLINE: M inakuja baada ya O. DAVID J. Malan: Sawa. CAROLINE: O. DAVID J. Malan: O, Good. CAROLINE: E DAVID J. Malan: E, F. Naam. CAROLINE: T, U, V. DAVID J. Malan: V, T, U, V. Hivyo ni Inaonekana kama wewe ni making-- kuendelea. Inaonekana kama wewe ni kufanya rundo kubwa zaidi ya hapa, na aina ya rundo kubwa zaidi ya hapo. Hivyo nusu ya kwanza ya alfabeti, nusu ya pili ya alfabeti. SAWA. Nzuri. Aina ya kugawanyika tatizo katika wawili. M, N, X. Naam. CAROLINE: K. DAVID J. Malan: Sawa. K. Hivyo wewe ni aina ya kuchagua nao mmoja baada ya mwingine, kuweka ama upande wa kushoto au kulia, au Z kwenda juu ya sakafu. SAWA. CAROLINE: Z kinaendelea sakafu. DAVID J. Malan: Sawa. Y kinachoendelea sakafu. Sasa tunaweza kuweka X. CAROLINE: G. DAVID J. Malan: G ya kwenda kushoto. S ni kwenda kulia. Haki wote, A ni kwenda njia yote kushoto. CAROLINE: A, B, C, D. DAVID J. Malan: Sasa, nzuri. Sisi tumepewa, B, C. W ya kwenda chini huko. Sawa, T. CAROLINE: H, I, J. DAVID J. Malan: H, I, J. Mwema. CAROLINE: Katikati, mimi nina gonna-- DAVID J. Malan: Sawa. Hivyo sasa, tunakwenda aina ya kuunganisha piles hizi mbalimbali. Hivyo kupitia C, kisha Mimi naona D, na E, na F, na G, H na, na mimi Nice. J, K. Na kisha, rundo huu ni kichwa chini, lakini hiyo ni sawa. Uhakika. Tunaweza kukata baadhi pembe. SAWA. Na kisha tunahitaji W, X, Y, Z. CAROLINE: Naam. DAVID J. Malan: Mufti. Hivyo kubwa asante kwa Caroline kwa ajili ya kuchagua hao. [Wakishangilia] Asante. Asante sana. Hivyo sasa hebu fikiria kwa muda jinsi Caroline alikuwa anakwenda kufanya hivyo, na nini hasa sisi waliweza to-- jinsi sisi walikuwa na uwezo wa kutatua kwamba Tatizo tulipokuwa tu kutokana na rundo zima la pembejeo random. Naam, inaonekana kama kuna ilikuwa kidogo ya mfumo wa huko? Kulia. Hivyo barua ya awali katika alfabeti, yeye Ilikuwa kuweka kwa upande wa kushoto, na barua baadaye katika alfabeti, yeye alikuwa kuweka katika haki. Na haraka kama yeye amepata baadhi ya barua kupakana, ndio kwamba kwenda kulia karibu na kila mmoja, angeweza kuweka wale katika utaratibu. Na hivyo sisi aina ya alikuwa hizi ndogo marundo ya pembejeo yamepangwa kutokea. Na hivyo ndiyo kabisa kama yale wengi wetu binadamu atafanya. Tunataka aina ya kuchuja hilo, na tunatarajia aina ya kuwa na utaratibu. Lakini inaweza kuwa vigumu kuandika chini katika fomula per se. Ilikuwa inaonekana kikaboni kuliko ile zaidi kidogo. Basi hebu angalia kama tunaweza sasa amefungwa tatizo na pembejeo wachache. Badala ya 26, hebu kufanya kitu mbali wachache kwa kusema tu, saba, nyuma ya milango hizo, hivyo kusema. Je, kuna idadi saba tu? Na kama lengo sasa katika mkono ni kupata thamani, hebu angalia jinsi ufanisi tunaweza kwenda juu ya kufanya hii. Na hebu angalia kama tunaweza sasa kuanza kuomba idadi ya baadhi, au baadhi ya kanuni ambazo kueleza ufanisi wa kitabu cha simu yetu algorithm, kitabu mtihani wetu algorithm, na kwa ujumla zaidi, kutafuta habari. Hivyo kwa hili, basi mimi kwenda mbele, na juu ya screen kugusa zaidi ya hapa, kuweka kivinjari ambayo ina hasa hawa milango saba. Na kama tunaweza kupata mtu mwingine kujitolea kuja juu zaidi ya hapa, Nimekuwa kuweka milango hizo hizo zaidi ya hapa. Haraka kujitolea. Hii demos one-- ni kwenda kwa wepesi na haraka sasa. Kuja juu chini. Jina lako ni nini? TREVOR: Trevor. DAVID J. Malan: Trevor? Haki wote, Trevor, kuja juu chini. Hivyo Trevor ina alijitolea hapa kufanya tatizo sawa, lakini hiyo ni moja nyembamba katika upeo, na kwamba itakuja kuruhusu sisi kujaribu kurasimisha sasa mchakato kwa ajili ya kuchagua namba hizi. Hivyo Trevor, ni vyema kukutana na wewe. Hivyo hapa ni safu, hivyo kusema, orodha ya milango saba. Kwenda mbele na kupata yetu idadi 50. Na kisha baada ya ukweli, kutuambia jinsi wewe kupatikana. Lazima be-- haki yote. Naam, hii ni moja hapa? Uh-oh. SAWA. Wewe clicked kwamba moja. Nzuri. Na nzuri. Sasa wewe clicked kwamba moja. Na nikupe kipaza sauti, ili una hiyo katika muda tu. Kwenda mbele na bonyeza mlango ijayo kwamba unakusudia. Ndiyo, nzuri. TREVOR: Je, mimi unclick mlango? DAVID J. Malan: Hapana, huwezi unclick. TREVOR: Sawa. Hii moja. DAVID J. Malan: wapi unataka kwenda? Ipi? TREVOR: moja Hiyo. DAVID J. Malan: Hapana TREVOR: Sawa. Hii moja. DAVID J. Malan: Ndiyo. Hiyo ilikuwa nzuri. Sawa. Kwa hiyo kile alikuwa algorithm yako au utaratibu wa kufanya hivyo, Trevor? TREVOR: I just akaenda kwa njia ya milango mpaka nimeona 50. DAVID J. Malan: Sawa. Bora algorithm. Hivyo hiyo ni nzuri. Kwa sababu kwa kweli, kama mimi yatangaza nini nyuma ya haya milango wengine wawili, nini tutaweza kupata hapa ni kwamba sisi tu random pembejeo. Ili kwamba ilikuwa kweli kama nzuri kama unaweza kupata. Na kwa kweli, wewe got bora kuliko vyema kutafuta safu nzima, kwa sababu ingekuwa ni kweli unlucky kama alikuwa na kugonga idadi 50 mlangoni ya mwisho. Lakini sisi kama badala yale aliwapa dhana. Nadhani aina zote za milango hizi pande zote, ili una nambari yamepangwa wakati huu, lakini wakati huu ni kweli a different-- wakati huu, ni kweli yamepangwa kwa ajili yenu. Na sasa lengo katika mkono ni kuikumba idadi 50. TREVOR: Sawa. DAVID J. Malan: Nini algorithm yako kwenda kuwa? TREVOR: Naam, ikiwa ni yamepangwa, ni ama kwenda kwa be-- ikiwa kubwa kwa kubwa, kushuka, utakuwa ni moja ya kwanza, au kama ni kinyume, itakuwa moja ya mwisho. Hivyo mimi itabidi tu bomba mlango huu, na kisha tu bomba mlango mwisho. DAVID J. Malan: Mufti. Sawa. Hivyo sisi kupatikana idadi 50. Hivyo kwa haraka kama wewe alijua walikuwa yamepangwa, sisi walikuwa na uwezo wa kujiinua dhana hii. Hivyo wao ni sana kama kitabu cha simu mfano. Mara tu una, hata kwa Tatizo dogo kama hili, pembejeo yako kabla ya yamepangwa, tunaweza kweli kupata thamani arguably ufanisi zaidi. Na sikuweza kukuambia kama ilivyokuwa yamepangwa ndogo kwa kubwa, au kubwa kwa wadogo, na hivyo ilikuwa nzuri sana kuanza mwishoni moja au nyingine kwa kweli kupata kwamba thamani ya lengo. Hivyo kuwashukuru kwa Trevor pia. Na mimi itabidi ya kupendekeza nicely kufanyika. Tuna kipande cha kidogo, kwa kweli, kwamba ni miongoni mwa nyakati zetu favorite katika CS50, ambapo wakati mwingine demos hayo hawana kabisa kwenda kulingana na mpango. Na hakika hivi sasa, mimi anapigiwa interface vibaya na ambayo kwa kutumia touch screen. Ili kwamba ilikuwa kosa langu huko. Hivyo hii itafanya kwa kipande cha mwaka ujao kama kwa nini nilikuwa kubonyeza kwenye screen yangu mwenyewe. Lakini hebu tuangalie kwa haraka nini kilitokea mwaka jana na Jay, ambao walifika, sehemu kubwa kama Trevor hapa, alijitolea, na katika kipande cha hii fupi, utaona jinsi demo hiyo haikuweza yatangaza masomo sawa kujifunza. [VIDEO avspelning] -All Nataka kufanya sasa ni kupata kwa ajili yangu, na kwa ajili yetu, kweli, idadi 50 hatua moja kwa wakati. -The Idadi 50? -The Idadi 50. Na unaweza yatangaza nini nyuma ya kila moja ya milango hizi tu kwa kugusa kwa kidole. Damn it. [Akicheka] [Mwisho avspelning] DAVID J. Malan: Hivyo kwamba ilienda vizuri sana. Wale walikuwa milango zisizochambuliwa. Na Jay, bila shaka, kupatikana yote haraka haraka. Trevor alifanya kazi bora zaidi katika suala la wakati sikivu, hivyo kusema, mwaka huu katika kuchukua muda mrefu kupata hiyo. Bila shaka, basi sisi alitoa Jay nafasi ya pili, ambapo sisi yamepangwa milango, tu kama tulivyofanya kwa Trevor, na Trevor alifanya super vizuri wakati huu. Lakini Jay alifanya hivyo nusu kwa haraka. [VIDEO avspelning] Lengo -The sasa ni pia kupata yetu idadi 50, lakini kufanya hivyo algorithmically, na kutuambia jinsi gani wanaenda kuhusu hilo. -SAWA. -Na Kama wewe kupata hiyo, kuweka movie. Kama huna kupata hiyo, wewe kuwapa nyuma. -Man. -Oh! - [Inaudible] Sawa. Hivyo nina kwenda kuangalia ncha kwanza ili kuamua kama there's-- Oh. [Makofi] [Mwisho avspelning] DAVID J. Malan: Sawa. Hivyo kuchagua milango wazi inaongoza kwa ufanisi mkubwa. Na hivyo, mara mbili kwa haraka ni nini mimi maana huko. Na hivyo Jay got bahati mara mbili. Naye pia alipata bahati kwa kuwa mwisho mwaka, mimi kuamuru baadhi rekodi Blu-ray kwa kweli kutoa nje. Nasikitika mwaka huu, sisi hawakuwa na huo, Trevor. Lakini bado bora ilikuwa miaka michache nyuma. Na baadhi yenu wanaweza kujua hii wenzake, Sean, ambaye alipokuwa katika CS50, ilikuwa changamoto kwa halisi tatizo moja, angalau katika SD, kama utasikia hivi karibuni kuona, nyuma katika siku. Na utapata kwamba si tu kwamba yeye kuchukua muda mrefu kidogo kuliko Jay, muda mrefu kidogo kuliko Trevor, ilikuwa kweli nafasi hii ya ajabu kujihusisha karibu kila mtu katika Umati la Bei ni Haki, na kuwahamasisha naye kupata idadi tulikuwa kutafuta. Hebu. tuangalie kwa haraka. [VIDEO avspelning] -SAWA. Hivyo kazi yako hapa, Sean, ni zifuatazo. I have siri nyuma hizi milango namba saba. Lakini zilizowekwa katika baadhi ya milango hizi pamoja ni idadi nyingine hasi. Na lengo ni kufikiri ya juu safu hii ya namba kama tu safu, au tu mlolongo wa vipande vya karatasi na namba nyuma yao. Na lengo ni, tu kutumia juu safu hapa, kupata mimi namba saba. Na sisi ni basi kwenda kukosoa jinsi ya kwenda juu ya kufanya hivyo. -Sawa. -Kupata Sisi namba saba, tafadhali. Hakuna Tano, 19, 13. [Akicheka] Siyo suala hila. Moja. [Akicheka] Katika hatua hii, alama yako si sana nzuri, hivyo unaweza pia kuendelea. Tatu. [Akicheka] Endelea. Kwa kweli, siwezi kusaidia lakini ajabu nini wewe hata kufikiria juu, so-- [Akicheka] Tu safu ya juu, hivyo nimepata tatu kushoto. Hivyo kupata mimi saba. [Akicheka] 17. Saba. [Makofi] Sawa. [Mwisho avspelning] DAVID J. Malan: Hivyo tunaweza kuangalia hizi mchana kutwa. Na bila shaka, baadhi ya demos mwaka huu labda sasa kuishia katika kipindi cha video wa mwaka pia. Hivyo sasa hebu kweli kuzingatia algorithms hapa, na kuona kama hatuwezi sasa kuanza kurasimisha jinsi gani tunaweza kwenda juu ya kupata takwimu zetu ndani ya hali hii kwamba ni yamepangwa, ili hatimaye, tunaweza kweli kutafuta ni ufanisi zaidi. Na hata kama tunakwenda kutumia seti haki ndogo data, kama idadi nane sisi na hapa kwenye bodi, hatimaye mawazo haya hilo linaweza kuomba pembejeo 1,000, milioni pembejeo, Pembejeo bilioni 4, kwa sababu algorithms ni kwenda kuwa kimsingi huo. Na hivyo hii ni mwisho wetu fursa kwa watu wa kujitolea leo, lakini labda moja zaidi wanaohusika, kwa ambayo tunahitaji watu wa kujitolea nane kuja na kutembea kwetu kupitia mchakato wa kuchagua kile hivi karibuni kuwa juu ya haya muziki anasimama hapa. Napenda kuanza nyuma hapa. Hivyo moja katika kijani turquoise-- ni nini? Je, wewe ni kufanya? Mbili. Kuja juu chini. SAWA. Tatu. Nne. Hebu ME sawa, tano. Wewe ni kuteuliwa na rafiki yako. Sita, saba, na wanane. Kuja juu juu. Sawa. Asante sana. Kuja juu juu. Kuja juu juu. Sawa. Kwa hiyo kile tuna here-- na hii ni miongoni mwa watu zaidi Awkward, tangu hii itahitaji kwamba ucheshi mimi kwa kidogo tu cha muda. Nanyi mtakuwa namba moja. Jina lako ni nini? ANNAN: Annan. DAVID J. Malan: Annan. David. Jina lako ni nini? JOSEPH: Joseph. DAVID J. Malan: Joseph, wewe ni namba mbili. SERENA: Serena, namba tatu. Stefan, namba nne. CYNTHIA: Cynthia. DAVID J. Malan: Cynthia, namba tano. [Inaudible] DAVID J. Malan: [inaudible]. David, idadi sita. MATT: Mathayo. DAVID J. Malan: Mathayo namba saba. Na? WAVERLY: Waverly. DAVID J. Malan: Waverly, namba nane. Sawa. Kama could-- whoops. Kama wote, kama yako Changamoto ya kwanza, kuna ni nane muziki anasimama hapa inakabiliwa na watazamaji. Kama unaweza kuweka namba yako juu ya hizi muziki anasimama kwa namna kuwa wao kujipanga kwa idadi sawa kwenye ubao. Hivyo kufanya wenyewe kuangalia kama kwamba kwa kuweka namba yako juu ya hizi muziki anasimama hapa. Bora hadi sasa. Bora. SAWA. Hivyo sasa, tunakwenda kuuliza swali katika njia kadhaa tofauti. Ni jinsi gani sisi kwenda juu ya kuchagua folks hizi hapa? Kwa sababu tulikuwa na mbinu chache mapema, ambapo tulikuwa aina ya kufanya ndoo mbili tofauti. Na kisha tulikuwa ujumla piecing mambo pamoja. Mara tu tuliona namba mbili aliyokuwa nayo pamoja, sisi kuziweka pamoja. Barua mbili ambazo ni pamoja. Lakini hebu angalia kama sisi hawezi kurasimisha hii, ili tuweze hatimaye kuwa baadhi Pseudo-kificho wewe, na ambayo unaweza kutatua matatizo haya. Hivyo sasa, mimi nina kuangalia nje katika namba hizi hapa. Na mimi kuona rundo zima la makosa. Hatimaye, nataka moja juu ya kushoto na nane juu ya haki. Na hivyo mimi nina kuangalia hizi mbili, nne na mbili. Na tatizo ni nini, ni wazi? Naam. So. Mbili ni wazi huja kabla ya nne, hivyo unajua nini? Hebu kwanza kuchukua mbinu tamaa, kama wewe, kiasi kama tatizo kuweka one-- kama unakumbuka kutoka Standard Edition wa kuweka tatizo moja, ambapo mimi ndani ya nchi tu kutatua tatizo hiyo ni haki hapa mbele yangu na kuona ambapo inaongoza yangu. SAWA. Hivyo mbili na nne, napenda kwenda mbele na tu wabadilishane wewe miwili. Kama unaweza kimwili hoja wenyewe na karatasi yako, Mimi kuonekana kuwa na kujipatia orodha katika hali bora zaidi. Sasa, wao ni nzuri. Mimi nina kwenda kusonga mbele, nne na sita, inaonekana ni nzuri. Si tatizo. Sita na nane, sawa. Nane na moja, tatizo jingine. Kwa sababu kile kweli kuhusu nane na moja? Mtu hawezi kuja kabla nane, na hivyo tunapaswa kufanya nini? Hebu wabadilishane hizi mbili. Moja na nane. Na sasa, nina kwenda kuendelea. Mimi nina kwenda kuendelea kutafuta mbele. Na hebu angalia nini kinatokea. Nane na tatu, ya Bila shaka, nje ya utaratibu. Hebu wabadilishane. Nane na saba, bila shaka. Nje ya utaratibu. Hebu wabadilishane. Nane na tano, bila shaka, hebu wabadilishane. Sawa. Orodha ni Iliyopangwa. ndiyo? OK, ni wazi si. Lakini ni kidogo bora, haki? Kwa sababu ilani kile kilichotokea. Kila wakati sisi kazi wabadilishane, ndogo idadi aina ya percolated kwa njia hiyo, na idadi kubwa zaidi percolated njia hii, au tutaweza kuanza akisema bubbled kwa kushoto au bubbled na haki. Sasa, ni haitoshi, kwa sababu saa bora idadi wapate wamehamia doa moja mbele, au saa mbaya, idadi anaweza kuwa wakiongozwa doa moja zaidi. Hivyo unajua nini, aina hii ya kazi pretty vizuri hadi sasa. Napenda tu kujaribu tena. Mbili na nne, wao ni sawa. Nne na sita, wao uko sawa. Sita na moja, nje ya utaratibu. Basi hebu wabadilishane wewe miwili. Na sasa, taarifa tatizo la mapya ya kupata kidogo bora tena. Sita na tatu, nje ya utaratibu. Hebu wabadilishane wewe miwili. Sita na saba, wewe ni vizuri. Saba na tano, bila shaka, nje ya utaratibu. Saba na nane, katika utaratibu. Na sasa, mimi haja ya kufanya hili mara kwa mara chache zaidi. Na kwa kweli, nadhani kwa wenyewe labda ni mara ngapi maximally Huenda nina kutembea na kurudi? Tutaweza kuja nyuma na kwamba. Hivyo mbili na nne bado ni sawa. Nne na moja, nope. Hivyo, hebu wabadilishane. Na tena, taarifa kuibua moja ni aina ya bubbling kwa upande wa kushoto, ambapo ni lazima. Nne na mitatu wabadilishane. Nne na sita. Sita na tano wabadilishane. Sita na saba. Saba na nane ni nzuri. Nzuri. Sisi ni kupata bora zaidi. Basi hebu angalia. Sasa, tuna mbili na moja. Bila shaka, wabadilishane. Mbili na tatu, tatu na nne, nne na tano, sita na saba, saba na nane. Nzuri. Na unajua nini? Kwa sababu mimi alifanya badiliko moja pale, napenda kufanya moja sanity hundi. Hebu kwenda njia yote nyuma ya mwanzo. SAWA. Moja, two-- yup, kuona kitu gani? Kitu ilikuwa na makosa. Tatu, nne, tano, sita, saba, nane. Na katika kupitisha hii ya mwisho, ni wewe starehe na sasa zangu kwa madai ni yamepangwa? SAWA. Kuibua, hiyo ni kweli kabisa. Lakini functionally, nini Je, pia tu kutokea kwa kuwa ufaulu mwisho kwamba utapata kuthibitisha kwamba orodha hii ni kweli yamepangwa? Je, mimi kufanya au kufanya hii kupita jana? Watazamaji: Hakukuwa na mabadiliko. DAVID J. Malan: Samahani? Watazamaji: Hakuna mabadiliko. DAVID J. Malan: Hakukuwa na mabadiliko. Hivyo itakuwa kijinga ya mimi kufanya algorithm kwamba kimoja tena kama sikuwa kufanya lolote mabadiliko mara ya kwanza. Na hali haujabadilika. Hakika, mimi si kwenda kufanya mabadiliko yoyote mara ya pili. Na hivyo, ni salama sasa kusema, orodha ni Iliyopangwa. Na hakika, huu ni sasa kitu ambacho tutaweza ujumla wito Bubble aina, ambapo pairwise, wewe kusahihisha makosa tena, na tena, na tena, na wewe kuweka kwenda na kurudi, na na kurudi, mpaka kufanya hakuna swaps hizo, ambapo kiwango unaweza kuwa na uhakika, ndiyo, mimi kumaliza fixing wote wa makosa. Hebu upya na kujaribu mbinu nyingine. Kama nyie naweza kurudi nyuma katika Ili ungekuwa wakati iliyopita, ambayo inaonekana kama hii. Sasa, hebu kuchukua mbinu a zaidi kidogo kama kitabu mtihani, ambapo tulikuwa mara kwa mara kuchagua barua ya alfabeti kwamba sisi aina ya alitaka kukabiliana na ijayo. Labda ilikuwa barua juu, kama A, au chini Z. barua Hivyo kila mtu ni nyuma katika utaratibu huu. Na sasa napenda kufanya hivyo. Hebu angalia Najua nina nambari nane hapa. Mimi nina kwenda kwenda mbele na tu kwa makusudi kuchagua ndogo vipengele. Sawa? Hii inaonekana Intuitive sana. Mbona mimi kupata ndogo kipengele, kuiweka ambapo ni mali, kisha kupata ijayo ndogo kipengele, kuweka ni ambapo ni mali, na tu kurudia. Kwa sababu shirikishi, kwamba wanapaswa kufanya kazi pia. Hivyo nne, hiyo ni idadi pretty ndogo. Mimi nina kwenda kukumbuka ambapo hii ni. Hebu subiri kidogo. Mbili ni ndogo. Napenda sasa kumbuka kuwa walipo wawili ni, na kusahau kuhusu nne. Tutaweza kukabiliana na kwamba baadaye. Sita, mimi si nia. Nane, mimi si nia ya. Moja ni yangu mpya idadi ndogo. Hivyo nina kwenda kukumbuka ambapo moja ni. Tatu, si nia. Saba, si nia. Tano, si nia. Hivyo bila kuanguka mbali hatua ya mwaka huu, Mimi nina kwenda kunyakua idadi one-- na ilikuwa ni nini jina yako tena? ANNAN: Annan. DAVID J. Malan: Annan. Na kama unaweza kujiunga na mimi katika mwanzo wa orodha, hebu kuweka wewe ambapo ni mali. Unfortunately-- nini jina lako? STEFAN: Stefan. DAVID J. Malan: Stefan ni katika njia. Hivyo kabla Stefan kutatua huu tatizo, tunapaswa kufanya nini? Tufanye nini na Stefan? Watazamaji: [inaudible]. DAVID J. Malan: Sawa. Hivyo tunaweza kufanya hivyo. Tuliweza aina ya kuchukua Stefan na wake nne, na tu kuiweka katika kutofautiana na kushikilia yake kwa baadhi ya kiasi cha muda, hivyo kufanya chumba kwa namba moja. Na si kwamba mbaya. Mimi naweza kupendekeza, kwa nini sio sisi tu ya kuweka Stefan hapa? Kwa nini huenda hii ni ukiukwaji wa moja mawazo tulianza kuzungumza juu ya mara ya mwisho, wiki iliyopita? Yeah? Watazamaji: [inaudible]. DAVID J. Malan: Hakuna ripoti ajili yake. Kama unafikiri ya hili, kwa kweli, kama safu, hii ni kama hasi moja, hivyo hakuna kumbukumbu kwa kweli hapa ikiwa huyu ndiye kweli safu, kama sisi alitangaza wiki iliyopita katika hotuba. Kwa hiyo, hatupaswi kufanya hivyo. Tunaweza kuhifadhi katika kutofautiana. Au unajua nini? Nilisikia mtu mwingine kupendekeza hilo. Nini kingine unaweza kufanya na Stefan? Mbona sisi tu kumfukuza na kumtia juu ya mahali pale namba moja alikuwa. Hivyo kama unataka kwenda zaidi ya hapo. Na hakika, huu ni nzuri ufumbuzi. Sasa kwa upande mmoja, nimekuwa aina ya kufanywa tatizo mbaya. Nne ni sasa mbali mbali kutoka ambapo ni lazima. Ni lazima kuelekea nusu huu. Lakini unajua nini? Ambazo zingeweza bahati mbaya. Labda namba nane alikuwa hapa. Na hivyo, labda tunataka waliopata bahati, na kusukuma nane karibu na mwisho. Hivyo katika mwisho wa siku, ni aina ya yote wastani nje. Hatuna haja ya huduma ya juu ya nne. Wote mimi huduma ya juu hivi sasa ni kuchagua kipengele ndogo. Na sasa, nini mimi kwenda kwa kufanya ni kusahau namba moja kudumu, kwa sababu ninajua orodha nyuma yangu sasa yamepangwa. Hivyo orodha yangu hapo awali ilikuwa na ukubwa nane. Sasa, ni ya kawaida saba. Hivyo tatizo langu ni kupata ndogo, angalau kwa mstari. Hivyo sasa, mimi nina kwenda kuchagua sasa ndogo kipengele, mbili. Sita, nane, nne, tatu, saba, watano. Hiyo ilikuwa ni kipengele ndogo. Kwa hiyo kile ni mimi kwenda kufanya with-- nini ilikuwa jina yako tena? JOSEPH: Joseph. DAVID J. Malan: Joseph? Tunakwenda kuondoka Joseph katika mahali. Sasa, mimi nina kwenda kwa kujifanya kwamba hawa guys are-- vizuri, Najua kwamba hizi mbili tayari Iliyopangwa. Hebu sasa kuzingatia salio ya orodha. Sita ni ndogo sasa. Nane ni kubwa. Nne sasa ni ndogo sasa. Tatu sasa ni ndogo sasa. Na hivyo sasa, mimi nina kwenda kuchagua tatu, ambao is-- nini jina lako tena? SERENA: Serena. DAVID J. Malan: Serena, kama unaweza kunyakua namba yako na wabadilishane with-- KALSANG: Kalsang. DAVID J. Malan: Kalsang. Kuja nyuma, na tuko kwenda wabadilishane hizo mbili. Na sasa, hebu kuweka hii juu ya autopilot. Mimi nina kwenda na kuondoka kwa nyie kuchagua ijayo mambo madogo. Dun, Dun, Dun, Dun. Idadi nne, unapaswa kufanya nini? Bora. Sasa, mimi nina kwenda kufanya kupita mwingine. Dun, Dun, Dun, Dun. Mimi naona tano ni ijayo ndogo. Sasa, mimi nina kwenda kuchukua pasi mwingine. Dun, Dun, Dun, Dun. Sita ni ndogo. Nzuri. Saba ni ndogo. Hakuna mabadiliko. Nane ni ndogo. Kufanyika. Kwa hiyo kile tumekuwa tu kufanyika kwa iteratively kuchagua kipengele moja baada ya nyingine ni kutekeleza jambo ambalo tuko kwenda kurasimisha kama uteuzi aina. Na ni pengine hata rahisi kueleza, kwa kuwa literally wote wanataka kufanya ni kuweka tu kwenda na kurudi kupitia orodha kuchagua, karibu ndogo kipengele, mpaka wewe ni kosa. Hivyo ni rahisi hata, pengine shirikishi, kuliko ya mwisho. Hebu jaribu moja iliyopita moja. Kama wewe guys inaweza upya wenyewe katika nafasi zifuatazo mara moja ya mwisho, hebu angalia kama hatuwezi sasa kurasimisha mbinu nyingine moja. Kwa kweli, ingekuwa mtu huko nje kama kupendekeza jinsi mwingine tunaweza kwenda juu ya kufanya hii? Bila msukosuko nje buzzwords au aina majibu kwamba tayari anajulikana, tu intuitively, nini inaweza sisi? Watazamaji: [inaudible]. DAVID J. Malan: Yeah. Hivyo kuna baadhi Intuition kubwa huko. Mambo mema wanaonekana kutokea hivi sasa katika sayansi ya kompyuta wakati sisi kugawanya na kushinda tatizo la kugawa katika nusu na nusu na nusu. Na hivyo kweli kweli, sisi inaweza kuanza kufanya hivyo. Na kwa kweli, kwamba kinaendelea kuwa, tutaweza kuona, moja ya ufumbuzi bora yetu bado. Lakini hebu kuja nyuma na kwamba kabla ya muda mrefu. Kwa kweli, sisi ni kwenda kufanya kuwa kidogo baadaye wiki hii. Nini kingine inaweza tufanye nini ili kutatua hili? Hivyo kila mtu hapa ni katika inaonekana random utaratibu. Unajua nini? Badala ya kwenda na kurudi, na kurudi, na kurudi kila wakati, hii anahisi kama Mimi nina kufanya mengi ya kutembea. Mbona mimi tu kuanza saa mwanzo wa orodha, na tu ya kuweka nne ambapo ni mali? Hivyo basi mimi kudhani kwa muda kwamba orodha yangu ni tu kipengele hiki cha kwanza. Ni nne yamepangwa katika wakati huu katika muda, kama wote najali ni kila kitu hapa? Hii ni aina ya trivially kweli, haki? Kama orodha zenye namba moja, na kuwa namba nne ni wazi yamepangwa. Hivyo basi mimi tu inasema kuwa orodha hii ni Iliyopangwa. Lakini sasa mimi kuwa na mapumziko ya orodha hii. Hivyo sasa, mimi kukutana miwili. Wapi mbili ni wazi mali na heshima kwa nne? Kabla ya nne. Hivyo nini naweza kufanya hapa? Nini jina yako tena? JOSEPH: Joseph. DAVID J. Malan: Joseph, kama unaweza kurudi nyuma kwa muda tu na namba yako. Na sasa nini unapaswa Stefan kufanya hapa? Hebu kuhama Stefan zaidi ya hapa. Na sasa, basi Joseph kuja hapa. Na sasa, napenda kudai kwamba kila kitu hapa ni Iliyopangwa. Kwa hiyo, matokeo sawa, lakini a mbinu tofauti kimsingi. Mimi si hata inaonekana nini chini huko. I just kushika kuchukua mambo kama wao ni mitupu kwangu, na kukabiliana nao. Hivyo sasa, naona idadi sita. Wapi namba sita ni mali? Tuna mbili, nne, sita. Hasa ambapo yeye ni sasa hivi. Basi hebu kuondoka kwamba peke yake, na sasa kudai kwamba sehemu hii ya orodha sasa yamepangwa. Na hivyo, hii anahisi kimsingi tofauti kwa kuwa mimi nina tu kusonga kupitia orodha hapa mstari, na mimi nina kamwe mara dufu nyuma. Ndiyo. Sawa. Hivyo nane, wapi wewe ni mali? Hapa hapa. Kamilifu. Hivyo sasa, moja. Uh-oh. Hii anahisi kama ni kwenda kuwa ghali. Sasa, katika algorithm uliopita, I just walibadilishana watu. Hivyo mimi ili kumtia njia zote kwa mwanzo, lakini kisha kuhamia Joseph. Lakini kama mimi hoja Joseph, sasa nini kinaendelea kuwa makosa? Sasa, nimekuwa aina ya undone-- nimekuwa kuchukuliwa hatua moja mbele na kisha hatua moja nyuma, kwa sababu sasa Joseph itakuwa nje ya utaratibu. Basi hebu kufanya hivyo. Kama unaweza kuchukua namba moja na kurudi nyuma kwa muda tu. Je, tunawezaje put-- nini ilikuwa jina yako tena? ANNAN: Annan. DAVID J. Malan: Annan katika mahali? Nini mahitaji ya kutokea kwa heshima kwa mbili, nne, sita, na nane? Wote unahitaji kuhama. Hivyo kama nane wangependa kuhama kwanza, basi sita, basi nne, kisha mbili. Na kisha Annan, kama wewe d kama kuja hapa, nzuri. Lakini hapa, tumekuwa tu aina ya kulipwa bei katika hatua mbalimbali katika algorithm. Wakati mara ya mwisho kwa uteuzi aina, na hata Bubble aina, Mimi kutembea nyuma na nje, na kurudi, ambayo ni hakika kuongeza hadi muda-busara, na literally stepwise. Kuingizwa aina, kwa mara ya kwanza mtazamo, inaonekana kama ni super nadhifu, kwa kuwa Mimi tu kufanya polepole, Unaozidi maendeleo, lakini mimi si kwenda huu na kurudi. Lakini kama mtu ni kweli nje ya utaratibu, ilani yote ya kazi mimi tu alikuwa na kufanya. Mimi nilikuwa na hoja nusu ya orodha tu kufanya chumba kwa namba moja. Hivyo kiasi kama hicho ni ya kazi hivi sasa ni anahisi, tu aina mbalimbali za kazi. Hebu kuendelea. Hivyo sasa tunajua kwamba kila mtu kati ya moja na nane ni vyema. Hapa, nina namba tatu. Kama wewe kama kuchukua namba tatu, kurudi nyuma moja. Na je, guys haja ya kufanya? Yep. Hivyo hiyo ni mwingine moja, mbili, hatua tatu. Vitengo tatu wa wakati huo gharama tu mimi, ili tatu sasa wanaweza fit. Hatimaye, watu saba. Hebu kwenda mbele na kuwa na wewe kuchukua hatua nyuma. Hii ni tu kwenda gharama sisi kitengo moja ya muda, lakini hiyo ni sawa. Na sasa, tano ya kwenda kuwa ni kidogo ghali zaidi. Kama Ningependa kurudi nyuma. Tunahitaji kwenda nane, na saba, na sita. Na kisha kila mtu ni sasa yamepangwa. Hivyo upande kubwa kwa kujitolea yetu hapa. Asante sana. [Makofi] Asante wote. Asante wote. Basi hebu angalia sasa tu jinsi gharama kubwa zote za iliyokuwa. Hebu fikiria labda rahisi ya hizi, Bubble aina. Na mimi kusema rahisi, tu kwa sababu unaweza kutatua hayo kwa pupa na tu kurekebisha tatizo pairwise hapa. Kurekebisha tatizo pairwise hapa, tena na tena na tena, kurudia kama wengi mara kama wewe kweli haja ya. Hivyo zinageuka kuwa na aina Bubble, vizuri, jinsi hatua nyingi kufanya mimi kuchukua juu ya kupita kwanza ya kwamba algorithm? Nipate take-- hebu see-- moja, mbili, tatu, nne, tano, sita, saba. Na kuna mambo nane hapa. Hivyo ni kama n bala 1 hatua za kupata tangu mwanzo wa orodha hadi mwisho wa orodha. Lakini pamoja na uteuzi aina, kukumbuka kwamba mimi nina kuchagua mambo tena na tena na tena hiyo ni ndogo, Mimi nina kuweka katika nafasi, lakini kisha Mimi sio kuangalia nyuma yangu tena. Hivyo nadhani ni kidogo zaidi ya wazi basi hiyo mara ya kwanza, mimi ili Una kuchukua zote n bala 1 hatua kupata kipengele ndogo. Kisha mimi kuziweka katika nafasi, na mimi kumfukuza yeyote alikuwa hapa awali. Lakini basi sina kwa kuweka kuangalia kipengele hiki, kwa sababu najua ni Tayari ndogo. Hivyo sasa, siwezi kuangalia saba tu mambo, basi mambo sita, kisha mambo matano, basi mambo manne. Na hivyo hesabu, ikiwa n ni idadi ya vipengele au namba kwamba sisi ilianza na, unaweza kufikiria kwamba hii ni sawa na n bala 1, pamoja n bala 2 hatua, pamoja n bala hatua 3, pamoja n bala 4 hatua, kila njia ya chini kwa hatua moja tu. Na mimi nina juu ya mtu yangu ya mwisho. Na kama unakumbuka kwamba mengi ya stats vitabu au vitabu math na kanuni hizo juu Hardcover nyuma au mbele yao, zinageuka kuwa mfululizo huu inaweza kuwa walionyesha kwa urahisi zaidi kama mara n n bala 1 zaidi ya 2. Na ni faini kama si kwamba mstari wa mbele katika akili yako. Lakini huyu ndiye kweli kweli. Hiyo ni njia tu rahisi ya kuandika hayo. Na kisha kama unadhani nyuma ya shule ya daraja, wakati wewe tu kuanza kuzidisha mambo ya nje, hii bila shaka, ni tu n squared minus n kugawanywa na 2. Wote mimi tumefanya ni kupanua Maneno huko. Na hivyo hebu upya huu tofauti kidogo. Hiyo n squared kugawanywa na 2 minus n / 2. Hivyo tena, mimi nina aina tu ya kutumia baadhi hesabu sheria huko. Lakini taarifa sasa kwamba kubwa mrefu katika msemo huu, hivyo kusema, ni kwamba n squared. Hivyo ndiyo, ni n squared kugawanywa na 2, bala n / 2. Lakini kwa ujumla, ikiwa n ni kwenda kuwa thamani kubwa, Mimi nina kwenda kudai kwamba n squared ni kwenda kuwa sababu kubwa. Ni tu kwenda kuwa mchangiaji mkubwa kwa idadi ya hatua ya n / 2. Basi je, maana na hili? Hebu jaribu mfano rahisi, hata ingawa hesabu anapata kubwa kidogo. Hivyo tuseme tulikuwa watu milioni 1 juu ya hatua, au mambo milioni 1 kwamba tunataka kutatua. Hebu kuziba milioni ndani ya hasa kwamba fomula kuona jinsi hatua nyingi inachukua jumla kutatua milioni mambo kwa kutumia kusema, uteuzi aina. Hivyo tunatarajia kuwa fomula sawa mbele. Ningependa kuziba milioni, ili niweze kupata milioni mraba kugawanywa na 2, bala milioni kugawanywa na 2. Kama mimi kufanya hivyo hesabu mapema hapa, tuna bilioni 500 bala 500,000, ambayo inatupa 499,999,500,000, ambayo ni pretty darn kubwa. Kwa kweli, kama kulinganisha sasa 499,000,000,000, milioni 999, 500,000 dhidi thamani yetu ya awali, Bilioni 500, ni hivyo damn karibu. Sawa? n squared kugawanywa na 2 huwapa us-- au tuseme, n squared kugawanywa na 2 alitupa bilioni 500. Hiyo ni pretty darn karibu kwa 499,999,500,000, ambayo ni kusema subtracting mbali 500,000, au zaidi kwa ujumla, kutoa mbali n squared, si kweli mpango kubwa. N squared hufanya hivi nambari kukua kwa kweli kasi. Sasa, hii ni muhimu tu kadiri kama sisi, kama wanasayansi wa kompyuta, kwa ujumla hataenda kujali sana kuhusu nuances ya kanuni hizi na nini hasa majibu sahihi ni. Sisi matunzo tu kwamba, unajua nini? Mwisho wa siku, utaratibu huu ni juu ya utaratibu wa n squared. Ndiyo, sisi ni kugawa na 2 katika huko. Ndiyo, sisi ni subtracting mbali n bala 2. Lakini mwisho wa siku, mrefu kwamba kweli machungu yetu na gharama sisi mengi ya hatua ni kwamba mraba mrefu. Na hivyo kile kompyuta mwanasayansi kinaenda kwa ujumla kufanya ni kupuuza wale wote Ili suala ndogo, na tu kuangalia moja kwamba inachangia zaidi kwa gharama yoyote. Na hii ni nzuri, kwa sababu tunaweza sasa kuzungumza katika ujumla kubwa sana kuhusu algorithms, na unaweza kulinganisha yao. Na ukweli kwamba mimi nina kutumia O hii ni makusudi. Wakati mimi kusema juu ya utaratibu ya, mimi nina hasa akimaanisha kitu aitwaye kubwa O. Na kubwa O ni nukuu kwamba kompyuta Mwanasayansi anatumia kuelezea juu amefungwa juu ya kitu fulani. Hivyo kama wewe kusema kwamba algorithm ni katika kubwa O ya n squared, kama mimi mapendekezo tu wakati iliyopita, kwamba maana yake kwamba katika suala la mgombea wake muda au ufanisi wake, inachukua juu ya utaratibu ya n squared hatua. Labda zaidi, labda kidogo. Lakini ni juu ya utaratibu wa n squared. Na hiyo ndiyo amefungwa juu. Ni si kwenda kuwa chungu zaidi kuliko hiyo. Ni si kwenda kuwa n cubed, au 2 kwa n, au jambo kubwa sana. Hii ni juu amefungwa juu ya gharama yoyote kwamba ni. Hivyo kutokana na kwamba, hebu kufikiria mifano michache tu. Na hii ni orodha mahususi ya kawaida sana mbio nyakati kwa algorithms kwamba maana ya kuwa unaonyesha baadhi ya mambo tumekuwa kuonekana tayari. Hivyo kwa mfano, katika kesi ya uteuzi aina, nini mimi kudai hapa ni kwamba uteuzi aina ya mbio muda ni juu ya utaratibu wa n squared. Katika hali mbaya zaidi, mimi nina kwenda na rundo zima la idadi random hapa. Na kama tuliona hesabu, kama mimi kuendelea kutembea kupitia orodha, kupitia orodha, kuchagua ijayo ndogo kipengele tena na tena, kama mimi kweli kuandika hatua zote Mimi kuchukua kama mimi mapendekezo formulaically kabla, ni juu ya utaratibu wa n squared hatua kwamba mimi nina kuchukua. Na zinageuka kuwa Bubble aina na kuingizwa aina ni kama mwepesi katika hali mbaya. Fikiria, kwa mfano, kuingizwa aina, algorithm mwisho kabisa sisi kushughulikiwa, ambayo ilikuwa na tuangalie kipengele, na kisha kuingiza ambapo ni mali. Na kisha sisi inaonekana katika kipengele ijayo, na kuingizwa yake ambapo ni mali. Hivyo kufikiria bora mazingira. Tuseme nilikuwa kujitolea yangu kujipanga halisi kama hii, kwanza hadi la nane, tayari Iliyopangwa. Jinsi hatua nyingi ni kuingizwa aina kwenda kuchukua kutatua watu nane, kama wao kufika katika jukwaa la kuangalia kama hii? Watu nane tayari Iliyopangwa. Na mimi kutumia kuingizwa aina. Hiyo ya mwisho ya algorithms. Naam, hebu kuigiza haraka kweli. Hivyo kama mimi kuanza hapa, naona moja. Ambapo gani mtu ni mali? Iko hapa hapa. Mimi naona mbili. Wapi mbili ni mali? Hapa hapa. Mimi naona tatu. Wapi tatu ni mali? Hapa hapa. Mimi naona nne. Hapa hapa. Tano, sita, saba, nane. Hakuna sababu ya kurudia mwenyewe. Na hatua hiyo, ni wangapi ni kwamba katika suala la n? Ni juu ya utaratibu wa n hatua, sawa? n bala 1. Lakini mimi alichukua idadi linear hatua, na sasa mimi nina kufanyika. Hivyo hiyo ni kesi bora, ingawa. Je kuhusu hali mbaya zaidi? Nini nane walikuwa huko juu, na saba waliokuwa pale chini, na moja na mbili zilikuwa zaidi ya hapa, hivyo kwamba orodha walikuwa kweli kuachwa? Naam, nini kinatokea kweli kama hii ni idadi? Na tutaweza kufanya michache tu ya mifano. Nini kama, kwa hakika, idadi nane ni hapa, na whoops number--. Basi nini kama, kwa hakika, idadi nane ni njia yote juu hapa, na mimi nina kutumia kuingizwa aina? SAWA. Mimi kudai kwa sasa ni katika mahali. Lakini sasa, seven-- wapi saba kwenda? Bila shaka, unaendelea zaidi ya hapa. Hivyo nina hoja nane juu ya sehemu moja. Sasa sita, yanakwenda wapi? Naam, haki zote. Sasa, nina hoja nane juu ya mahali, na saba mahali, na kisha mimi plop chini sita. Hivyo mara ya kwanza, gharama mimi hatua moja ya kurekebisha mambo, basi ni gharama mimi hatua mbili ili kurekebisha mambo. Jinsi hatua nyingi ni kwenda kuchukua kurekebisha mambo ya kuweka tano katika mahali sahihi? Tatu. Kwa sababu sasa nina hoja moja, mbili, tatu. Jinsi hatua nyingi ni kwenda kuchukua kuweka nne katika mahali sahihi? 4 pamoja na 5, pamoja na 6, pamoja na 7. Na hivyo ni hesabu kufanana na nini sisi kama ilivyoelezwa kwa uteuzi aina. Tuna mfululizo huu hiyo ni kuongeza tu. 1 plus 2 pamoja na 3 pamoja na 4, au kinyume chake, 7 pamoja na 6 pamoja na 5 pamoja na 4 zinafikia kwa leo madhumuni ya juu ya utaratibu wa n squared. Hivyo basi mimi inasema pia kwamba Bubble aina ni pia katika n squared. Kwa sababu kwa Bubble aina, kila wakati mimi kwenda kupitia orodha, Mimi kuchukua hatua takribani ngapi? Kila wakati mimi literally kutembea kutoka huko kwa huko? Takribani n hatua. Lakini ni mara ngapi anaweza mimi haja ya kwenda kwa orodha? Naam, takribani n huo. Labda n bala 1, lakini takribani n mara. Naam, kwa nini ni kwamba? Naam, na Bubble aina, ikiwa sisi kuanza na aina Bubble, na orodha katika mbaya iwezekanavyo hali hiyo, ambayo tena ni kabisa nyuma, nini kitatokea? Mimi kwenda kwa njia ya orodha, na idadi moja ni mali njia yote zaidi ya hapo. Lakini pamoja na aina Bubble, jinsi mbali anafanya moja hoja juu ya kupita yangu ya kwanza kupitia orodha? Jinsi maeneo mengi gani kupata karibu na mahali sahihi? Moja tu. Hivyo kama wewe aina ya sababu kwa njia hii, kila wakati kupitia algorithm hii, Kuchukua takribani n hatua Daudi. Lakini hupita wangapi kupitia orodha hiyo ni kwenda kuchukua kwa moja kwa Bubble kwa upande wa kushoto ambapo ni mali? Amepata hoja kama, nafasi n njia hii. Hivyo tu kufanya kuchagua ya orodha, Nina kutembea na kurudi mara n. Na kila wakati, mimi nina kuangalia n vipengele. Hivyo kufanya mambo n mara n juu ya utaratibu wa n squared. Sasa, tutaona katika baadhi ya kaptula kwamba ni iliyoingia katika CS50 tatizo ijayo kuweka, mbinu nyingine katika hizo, lakini kwa sasa, hebu tu kufikiria baadhi ya mbio Wakati mwingine, hasa kama wale wa kuchagua kuchukua muda kidogo kuzama katika. Nini algorithm tumeona tayari kwamba inachukua juu ya utaratibu wa hatua n? Nini inapaswa kuchukua idadi linear ya hatua kwamba tumekuwa kuonekana hivi sasa? Nini hiyo? Search directory simu. Algorithm kwanza. Sawa? Ambapo tuko mstari kwa ajili ya kutafuta Mike Smith? Hakika. Kutoka wiki sifuri, wakati mimi kuanza kugeuka ukurasa mmoja kwa wakati, na mimi hata alisema kuwa ilikuwa ni aina ya linear hisia algorithm, na tulikuwa na kwamba picha juu ya bodi na moja kwa moja line nyekundu na njano sawa mstari, wale walikuwa kwa hakika algorithms kwamba ni katika O kubwa ya n. Kwa sababu kupata Mike Smith katika simu kitabu cha kurasa n, katika hali mbaya zaidi, inaweza kuchukua yangu n hatua. Nini juu ya kuchukua mahudhurio? Moja, mbili, tatu, nne, tano, sita. Nini wakati mbio za hii algorithm kwa ajili ya kuchukua mahudhurio? Big O ya n, kwa sababu katika nadharia mimi kuwa na uhakika kila mtu katika chumba hicho. Sasa kama kando, nini kuhusu optimization nyingine kutoka wiki sifuri? Mbili, nne, sita, nane, 10, 12. Mwanasayansi kompyuta ingekuwa kutambua, kusubiri dakika, hiyo ni juu ya utaratibu wa n kugawanywa na hatua mbili. Sawa? Kwa sababu mimi nina kufanya watu wawili kwa wakati mmoja. Lakini tunakwenda kupuuza wale ili suala ya chini, na tunakwenda tu kwa kutupa kugawanya na 2, na tu kusema, O kubwa ya n kwa kuwa algorithm pia. Nini kuhusu hili? Tutaweza ruka juu baadhi ya haya, lakini kile ilikuwa algorithm kwamba alikuwa logi ya n? Hiyo alichukua takribani kuingia hatua n? Kugawanya na kushinda. Hasa. Kama kitabu cha simu mfano katika wiki sifuri na mapema leo, ambapo sisi kugawanywa tatizo tena na tena na tena. Sisi akauchomoa juu ya bodi katika wiki sifuri kama ikiwa na kijani line, na sisi alisema siku hiyo ilikuwa ni algorithm logarithmic. Na hakika, idadi ya hatua hiyo inachukua kufanya kugawanya na kushinda, au tafuta binary kama tutaweza kuanza kuiita, kama ilivyo katika kitabu cha simu, ni juu ya utaratibu wa gogo na hatua. Na hii ni kidogo ya moja weird. Nini inachukua hatua moja, au zaidi hasa idadi ya mara kwa mara ya hatua? Labda ni wawili, labda ni tatu, lakini kompyuta mwanasayansi tu simplifies kama O kubwa ya 1, baadhi idadi ya mara kwa mara ya hatua. Nini kitu unaweza kufanya hivyo inachukua idadi ya mara kwa mara ya hatua? Nini wakati mbio za kupiga makofi? Mara kwa mara wakati. Sawa? Kama, nini wakati mbio za kufanya jambo lolote ambalo huchukua moja tu operesheni, kama magazeti F Habari Duniani. Ambazo zinaweza kuwa alisema kuwa wakati mara kwa mara, isipokuwa chini kona kesi na magazeti F, nini huenda wakati mbio ya magazeti F kweli kuwa? Na kwa nini? N kupimia katika kesi hiyo ni nini? Watazamaji: [inaudible]. DAVID J. Malan: Hasa. Idadi ya wahusika tunataka magazeti. Hivyo ni sana mazingira-nyeti. Leo, tumekuwa kulenga mengi juu ya herufi na namba hapa kwenye ubao. Lakini inaweza pia kuwa wahusika katika kamba halisi. Hivyo ni zamu nje kuna mwingine hatua ambayo itaanza kujali juu, na kwamba kinyume ya kubwa O, hivyo kusema. Hiyo ni nukuu omega. Wakati kubwa O ina maana nini, juu amefungwa juu ya yako bomba? Maximally, ni kiasi gani wakati Huenda jambo kuchukua? Omega-- pole hii anaendelea kuja up-- ni kinyume cha hilo, ambapo ni chini amefungwa juu ya kiasi cha muda kitu inaweza kuchukua. So. Kwa mfano, nini algorithm kwamba inachukua hatua daima n squared? Naam, moja ya algorithms tumeona leo, kwa kweli, inaweza kuwa kwamba pia. Uteuzi aina. Uteuzi aina pretty kijinga. Hata kama pole algorithm, hata kama safu tayari Iliyopangwa, uteuzi aina ni kwenda kuendelea kutembea kupitia orodha kwa kuhakikisha ina ndogo kipengele tena na tena na tena. Na hata kama wewe binadamu katika watazamaji kujua kwamba, kusubiri dakika, wewe tayari kupita ndogo kipengele, kompyuta hajui kwamba mpaka inaonekana njia zote orodha. Vile vile, chini amefungwa kwamba inaweza pia kuwa imezingatia inaweza kuwa na muda linear. Muda kiasi gani gani kuchukua ili mambo aina n katika bora kesi kwa kutumia kitu kama Bubble aina? Tuseme orodha yako tayari Iliyopangwa. Tulisema Bubble aina inachukua utaratibu wa n squared hatua. Lakini nini kama ni tayari Iliyopangwa? Nini kama wewe kutambua baada ya moja kupita kupitia safu kwamba kiunda hakuna swaps? Je, unahitaji kuendelea kufanya zaidi hupita? Hakuna Hivyo chini amefungwa juu ya Bubble aina inaweza kuwa alisema kuwa linear. Omega wa n. Na tunaweza kuangalia wengine wa haya vilevile. Basi hebu tuangalie kwa haraka saa tu taswira hapa kuona jinsi haya kutofautisha wenyewe. Mimi nina kwenda chini hapa katika hii ukurasa hiyo inapatikana kwenye tovuti C50 wa, lakini itakuwa maumivu ya kupata kazi, tangu inatumia teknolojia iitwayo Applets Java, ambayo ni kiasi kikubwa haikubaliki siku hizi, angalau kwa Chrome na wengine kadhaa. Na napenda kwenda mbele na kasi hii up na kueleza nini kinaendelea. Hii ni maandamano ya Bubble aina, algorithm kwanza tuliyoyaangalia. Na ni taswira katika kwamba kila wa baa hizi inawakilisha idadi. Kubwa bar, kubwa idadi. Ndogo bar, ndogo idadi. Na nini unaweza kuona kuibua, hata ingawa hii ni kwenda super haraka, ni kwamba bar nyekundu ni kama mimi, kutembea na kurudi kutatua matatizo. Unaweza kuona kwamba mambo makubwa ni kweli inayobubujika ili haki, na mambo madogo ni inayobubujika wa kushoto. Na chini hapa, kama sisi kweli kuangalia karibu zaidi, sisi kweli unaweza kuhesabu idadi ya kulinganisha na swaps kwamba walikuwa kuwa alifanya. Lakini badala yake, hebu angalia katika algorithm pili sisi inaonekana katika mapema na yetu kujitolea, uteuzi aina. Kuibua, ina athari tofauti sana. Lakini ni, tena, Intuitive sana, katika kwamba sisi kuendelea kuchagua ijayo ndogo kipengele, na sisi got kidogo bahati. Hiyo waliona kimsingi kwa kasi zaidi. Lakini kama sisi mbio hii tena na tena na tena kwa kura ya pembejeo, tunataka kuona kwamba ni kweli bado katika O kubwa ya n squared. Hebu kufanya moja ya mwisho moja hapa, kuingizwa aina, ambayo ilikuwa algorithm tatu sisi inaonekana katika, na wanakumbuka kwamba hii moja inahusika na mambo kama atakutana nao, lakini basi labda mabadiliko mambo juu ya kufanya chumba, kuingiza mambo ambapo ni mali. Na hii pia kuishia kutoa matokeo ya mwisho. Sasa yote matatu ya wale waliona pretty kufunga. Na hakika, mimi mbio yao katika kipande cha nzuri sana. Lakini kimsingi, wao ni wote pretty kutisha, kwa kuwa waaminifu. Wote wa algorithms hizi hivi sasa kwamba kukimbia katika O kubwa ya n squared kuchukua kidogo kabisa ya muda wa kukimbia katika mwisho. Na hakika, tunaweza kuona na kuhisi hii mwishowe kama mimi kuvuta up demo hii tatu na ya mwisho. Hii ni mwingine taswira ambayo inaenda kuonyesha Bubble aina upande wa kushoto, uteuzi aina katikati, na kitu, kama moja ya yetu mkono inaibua mapema alipendekeza, kuunganisha aina juu ya haki. Kugawanya na kushinda mkakati juu ya haki. Na hiyo ndiyo, kwa kweli, ni nini tuko kwenda kuangalia juu ya Jumatano. Lakini hebu wakati hizi kwa kukimbia katika sambamba. Ni takribani idadi sawa ya vipengele, wote mbio kwa wakati mmoja. Bubble aina vs uteuzi aina vs kuunganisha aina. Sasa, wao ni wote kukimbia katika nadharia kwa wakati mmoja. CPU ni mbio katika kasi hiyo hiyo, lakini wewe Unaweza kuhisi jinsi boring huu ni haraka sana kwenda kuwa, na tu jinsi ya kufunga wakati sisi kuingiza kidogo ya wiki algorithms sifuri ya Unaweza sisi kasi ya mambo up. Na sasa hebu kulinganisha hizi kwa namna moja iliyopita. Mimi kwenda mbele na tovuti CS50, ambapo tuna kiungo huu wa mwisho kwa leo, ambapo mtu kwenye mtandao kindly kuweka pamoja video ambayo Ukamataji nini kuchagua mbalimbali algorithms kuonekana kama. Hii ni kuingizwa aina. [Beeping] Ambapo wewe ni kuomba mzunguko kulingana na urefu wa bar bar. Hii ni Bubble aina. [Warped beeping] Kuja juu ijayo is-- kuja up ijayo is-- uteuzi aina, ambapo mara ya pili, sisi ni kuchagua ijayo ndogo kipengele, na tunaweza kuona ni kuongezeka kutoka kushoto kwenda kulia. Kuunganisha aina, mshindi yetu hivi sasa leo. Taarifa ni jinsi gani kugawa vitu ndani ya [inaudible] nusu na robo. Gnome aina, ambayo sisi si kuongelea, na inajenga kuibua na audally kidogo ya sura tofauti na sauti. Kwenda na kurudi, kusafisha mambo up. Pia kuangalia nje heapsort kwenye tovuti guy huu. Na hiyo ni yake. Tutaona wewe wakati ujao. [WHOOSHING NA MUZIKI]