[Music kucheza] ANDI PENG: Karibu wiki 3 ya sehemu. Shukrani, nyie, kwa kuja kwa hii mapema muda wa kuanza leo. Sisi tumepewa nzuri, kidogo Kundi ionekane leo. Hivyo hopefully tutaweza kupata kumaliza, pengine, mapema, kidogo mapema leo. Kwa hiyo kwa haraka, tu baadhi matangazo kwa ajenda leo. Kabla ya kuanza, tuko kwenda tu kwenda juu ya baadhi ya masuala mafupi vifaa, pset maswali, kuwahoji, mambo kama hayo. Na kisha tutaweza kupiga mbizi haki katika. Tutaweza kutumia HatiJava aitwaye GDB kwa kuanza debunking kificho yetu, ambayo David alieleza katika hotuba siku nyingine. Tutaweza kwenda juu ya aina nne za kila aina. Tutaweza kwenda juu yao pretty haraka kwani wao ni pretty kubwa. Lakini tunajua kwamba slides yote na chanzo kanuni ni daima online. Ili kujisikia huru, katika perusal yako, kwa kurudi nyuma na kuangalia kwamba. Tutaweza kwenda kupitia asymptotic nukuu, ambayo ni njia tu ya dhana ya kusema "runtimes," ambapo tuna O kubwa, ambayo Daudi alieleza katika hotuba. Na sisi pia kuwa Omega, ambayo ni Runtime chini amefungwa. Na tutaweza kuzungumza kidogo zaidi kina kuhusu jinsi wale kazi. Na Mwisho, tutaweza kwenda juu tafuta binary, sababu mengi ya wewe ambao tayari akapiga katika psets yako pengine kujua kwamba kwamba ni swali hilo ni katika pset yako. Hivyo itabidi zote kuwa na furaha kwamba sisi cover hii leo. Na mwisho, kwa yako kifungu cha maoni, mimi kwa kweli kushoto dakika 15 katika mwisho tu kwenda juu ya vifaa ya pset3, maswali yoyote, labda kidogo ya uongozi, kama wewe, kabla ya kuanza programu. Basi hebu jaribu kupata kupitia nyenzo pretty haraka. Na kisha tunaweza kutumia muda kuchukua maswali zaidi kwa pset. SAWA. Haraka, hivyo chache tu matangazo kabla ya kuanza leo. Kwanza, kuwakaribisha kwa kufanya hivyo kwa njia mbili za psets yako. Mimi alichukua kuangalia your-- yeah, hebu kupata raundi ya applause kwa kuwa moja. Kwa kweli, nilikuwa kweli, kweli hisia. Mimi hadhi pset kwanza kwa nyie guys wiki na wewe mwisho walifanya ajabu. Mtindo alikuwa juu ya hatua badala maoni machache. Kuhakikisha uko daima kutoa maoni yako kanuni. Lakini psets yako yalikuwa juu ya hatua. Na kuendelea kuwa juu. Na ni nzuri kwa grader kwa kuona kwamba nyie ni kuweka katika kama juhudi kubwa katika mtindo wako na kubuni yako katika kanuni yako kwamba tungependa kwa wewe kuona. Hivyo mimi nina kupita pamoja shukrani zangu kwa ajili ya mapumziko ya TAS. Hata hivyo kuna maswali machache kuwahoji Mimi nataka tu kwenda juu kwamba zingeweza maisha yangu yote na mengine mengi ya TAS 'anaishi kidogo rahisi. Kwanza, nimekuwa niliona hii zamani week-- jinsi wengi wenu wamekuwa mbio check50 juu ya kanuni yako kabla ya kuwasilisha? SAWA. Hivyo kila mmoja anapaswa kuwa kufanya check50, because-- secret-- sisi kweli kukimbia check50 kama sehemu ya usahihi wetu maandiko kwa ajili ya kupima kanuni yako. Hivyo kama kanuni yako ni kushindwa check50, katika uwezekano wote, ni pengine ni kwenda kushindwa kuangalia wetu pia. Wakati mwingine nyie na majibu sahihi. Kama, katika tamaa, baadhi ya una idadi ya haki, wewe tu magazeti nje baadhi ya mambo ya ziada. Na mambo ambayo ziada kweli inashindwa kuangalia, kwa sababu ya kompyuta haina kweli kujua nini ni kutafuta. Na hivyo itakuwa tu kukimbia kupitia, kuona kwamba pato yako haina mechi nini tunatarajia jibu kuwa, na alama yake ni sahihi. Nami najua kuwa kilichotokea katika baadhi ya kesi yako wiki hii. Kwa hiyo mimi nikarudi na manually regraded kificho kila mtu. Katika siku zijazo ingawa, tafadhali, tafadhali kuhakikisha kwamba wewe ni mbio kuangalia 50 juu ya kanuni yako. Kwa sababu ni aina ya maumivu kwa TA kwa kuwa na kurejea na manually regrade kila pset moja kwa kila moja, kidogo amekosa mfano. Hivyo sikuweza kuchukua mbali pointi yoyote. Nadhani mimi alichukua mbali labda moja au mbili kwa ajili ya kubuni. Katika siku zijazo ingawa, kama wewe ni kushindwa check50, pointi zitachukuliwa mbali kwa usahihi. Aidha, psets ni kutokana Ijumaa saa sita mchana. Nadhani kuna saba dakika Mwishoni mwa kipindi cha neema kwamba sisi kukupa. Per Harvard muda, wao ni kuruhusiwa kuwa dakika saba mwishoni mwa mwezi kwa kila kitu. Hivyo hapa katika Yale, tutaweza kuambatana na kuwa vilevile. Lakini pretty much, saa 00:07, kama pset yako si katika, itakuja kuwa alama kama marehemu. Na hivyo wakati ni alama kama marehemu, TA-- mimi nina bado kwenda kuwa grading psets yako. Hivyo itabidi bado kuona daraja kuonekana. Hata hivyo, tunajua kwamba katika mwisho wa muhula, psets zote marehemu tu kuwa moja kwa moja alizungumzia zaidi hali ilivyo na kompyuta. Sisi kufanya hivyo kwa sababu mbili. Moja, wakati mwingine tunapata radhi, kama udhuru Mkuu wa, baadaye kwamba mimi sijui kuhusu bado. Kwa hiyo sisi kama ili kuhakikisha tuko grading kila kitu tu katika kesi, kama, mimi nina kukosa kisingizio Mkuu wa. Na pili, kuweka katika akili, bado unaweza kushuka pset moja kwamba ina pointi full wigo. Na hivyo sisi kama daraja wote wa psets yako tu kuhakikisha kuwa wigo wako kuna na wewe ni kujaribu yao. Hivyo hata kama ni marehemu, utasikia bado kupata mikopo kwa ajili pointi upeo, nadhani. Hivyo maadili ya hadithi ni, kufanya uhakika psets yako ni katika juu ya muda. Na kama wao si katika juu ya muda, kujua kwamba siyo kubwa. Yeah, kabla mimi kusonga mbele, haina mtu yeyote kuwa maswali yoyote kuhusu pset maoni? Naam. Watazamaji: Je, unaweza kusema sisi unaweza kuacha moja ya psets? ANDI PENG: Naam. Hivyo kuna psets tisa kwa ujumla katika kipindi cha muhula. Na kama una wigo points-- hivyo wigo ni haki, pretty much, ni wewe kujaribu tatizo, ni wewe kuweka katika muda, Unataka kuonyesha kwamba umefanya alionyesha umesoma spec. Hiyo ni wigo pretty much. Na kama wewe ni kutimiza pointi upeo, sisi unaweza kuacha chini mmoja kati ya wigo kamili. Hivyo hiyo ni katika faida yako kwa kukamilisha na kujaribu kila pset. Hata upload-- kama hakuna nao kazi, kuzipeleka wote. Na kisha tutaweza hopefully kuwa na uwezo wa kukupa baadhi ya mambo hayo nyuma. Baridi. Yoyote maswali mengine? Kubwa. Pili, ofisi hours-- chache maelezo ya haraka kuhusu masaa ya ofisi. Hivyo kwanza, kuja mapema katika wiki. Hakuna mtu ni milele katika masaa ya ofisi juu ya Jumatatu. Christabel alikuja masaa ya ofisi jana usiku. Naam, Christabel. Na nini tuna katika ofisi masaa jana usiku, Christabel? Watazamaji: Tulikuwa aiskrimu. ANDI PENG: Basi hiyo ni haki, tulikuwa na aiskrimu katika masaa ya ofisi jana usiku. Wakati Siwezi ahadi kwamba tutaweza kuwa aiskrimu katika masaa ya ofisi kila wiki, nini naweza ahadi yenu ni kwamba kutakuwa na kwa kiasi kikubwa bora mwanafunzi TA uwiano. Kama legit, ni kama 00:57. Wakati ambapo, kulinganisha kwamba kwa Alhamisi, nimepata kuhusu 150 kweli alisisitiza watoto na hakuna cream barafu. Na ni tu si za uzalishaji kwa mtu yeyote. Hivyo maadili ya hadithi ni, kuja mapema kwa masaa ya ofisi na mambo mema kitatokea. Pia, kuja tayari kuuliza maswali. Wajua? Bila kujali TAS, mimi kufikiri, wamekuwa wakisema, tumekuwa kupata wanandoa wanafunzi wanaokuja katika siku ya Alhamisi katika, kama, 10:50 si baada ya kusoma spec kuwa kama msaada kwangu, nisaidie. Kwa bahati mbaya katika hatua hiyo, kuna si mengi tunaweza kufanya ili kukusaidia. Hivyo tafadhali kuja mapema katika wiki. Kuja mapema ili masaa ya ofisi. Kuja tayari kuuliza maswali. Kuhakikisha kwamba, kama mwanafunzi, ni wapi unahitaji kuwa ili TAS wanaweza kuongoza wewe pamoja, ambayo ni masaa ya ofisi kile lazima kuwa kura kwa. Pili, hivyo najua maprofesa kama mshangao wetu na vipimo. Mimi nilikuwa profesa wale kama, yo, kwa njia, kukumbuka kwamba midterm una Jumatatu ijayo. Yeah, Sikujua kuhusu kwamba midterm. Hivyo mimi nina kwenda kuwa kwamba TA kwamba kuwakumbusha Jaribio kwamba wote 0-- kwa sababu, unajua, tuko CS. Sasa kwa kuwa tumekuwa arrays done, kupata kwa nini ni jaribio 0, si jaribio 1, eh? SAWA. Oh, I got baadhi chuckles juu ya kwamba moja. SAWA. Hivyo Jaribio 0 itakuwa Oktoba 14 kama uko katika sehemu Jumatatu-Jumatano na Oktoba 15 kama wewe ni katika Jumanne-Alhamisi sehemu. Hii haina yanahusu kwa wale wa wewe katika Harvard who-- Nadhani itabidi wote kuwa kuchukua Quizzes yako tarehe 14. Hivyo yeah, wiki ijayo, ikiwa David, katika hotuba, unaendelea, yeah, hivyo juu ya hilo Jaribio wiki ijayo, nyote hautakuwa kutishwa kwa sababu wewe alikuja sehemu na unajua kuwa wako Jaribio 0 ni katika wiki mbili. Na kutakuwa na mapitio vikao na kila kitu. Hivyo hakuna wasiwasi kuhusu kuwa na hofu kwa ajili hiyo. Maswali yoyote kabla, maswali yoyote katika kuhusu masuala yote vifaa, grading, masaa ya ofisi, sehemu? Naam. Watazamaji: Hivyo jaribio ni kwenda kuwa wakati wa hotuba? ANDI PENG: Naam. Hivyo jaribio, nadhani, ni 60 Dakika kura kwa kuwa yanayopangwa wakati kwamba utasikia tu kuchukua katika ukumbi. Hivyo huna kuja katika juu ya, kama, bila mpangilio 07:00. Ni wote nzuri. Naam. Baridi. Sawa. Hivyo sisi ni kwenda kwa kuanzisha dhana ya wewe wiki hii kwamba Daudi tayari aina ya kuguswa juu katika hotuba wiki hii iliyopita. Ni wito GDB. Na jinsi wengi wenu, wakati katika kozi ya kuandika psets yako, niliona kifungo kubwa kwamba anasema "Debug" juu ya IDE yako? SAWA. Hivyo sasa tutaweza kweli kupata unearth siri ya kile kifungo kwa kweli gani. Na Mimi kuhakikisha, ni nzuri, nzuri kitu. Hivyo hadi sasa, nadhani kumekuwa na mambo mawili wanafunzi wamekuwa kawaida kufanya wakati debugging psets. Moja, wao ama kuongeza katika printf () - hivyo kila mistari michache, wao kuongeza katika printf () - loo, ni nini kutofautiana hili? Ah, ni nini kutofautiana hii now-- na wewe aina ya kuona maendeleo ya kanuni yako kama ni anaendesha. Au njia ya pili ya watoto kufanya ni kwamba wao tu kuandika jambo zima na kisha kwenda kama hii mwishoni. Ni matumaini ni kazi. Mimi kuhakikisha, GDB ni bora kuliko wote wawili wa mbinu hizo. Naam. Hivyo hii itakuwa rafiki yako mpya bora. Kwa sababu ni jambo zuri kwamba kuibua maonyesho wote nini kanuni yako ni kufanya katika hatua mahususi ikiwa ni pamoja kile yote ya kama yako vigezo ni kufanya, kama kile maadili yao ni, katika hatua hiyo maalum. Na kwa njia hii, unaweza kweli kuweka breakpoints katika kanuni yako. Unaweza kukimbia kwa njia ya mstari kwa mstari. Na GDB tu na kwa wewe, kuonyeshwa kwa ajili yenu, nini wote wa vigezo yako ni nini wanafanya, nini kinaendelea katika kanuni. Na kwa namna, ni sana rahisi kuona nini kinatokea badala ya printf-ing au kuandika kauli yako. Hivyo tutaweza kufanya mfano wa hii baadaye. Hivyo hii inaonekana kidogo abstract. Hakuna wasiwasi, tutaweza kufanya mifano. Na hivyo kimsingi, tatu kubwa, wengi-kutumika kazi itabidi katika GDB ni Next, Vuka, na Hatua katika vifungo. Mimi nina kwenda kichwa juu pale, kwa kweli, hivi sasa. Hivyo unaweza nyie wote kuona kwamba au lazima mimi kuvuta kidogo? Katika nyuma, je, unaweza kuona kwamba? Je, mimi kuvuta? Kidogo tu? OK, baridi. Kuna sisi kwenda. SAWA. Hivyo nina, hapa, yangu utekelezaji kwa tamaa. Na wakati mengi ya nyie aliandika tamaa katika kitanzi wakati form-- kwamba Ni njia zinazokubalika kikamilifu kufanya it-- njia nyingine ya kufanya hivyo ni tu kugawanya katika modulo. Kwa sababu kisha unaweza kuwa na yako thamani na kisha kuwa salio yako. Na kisha unaweza tu kuongeza yote pamoja. Je, mantiki ya nini mimi kufanya hapa kufanya maana kwa kila mtu, kabla ya kuanza? Aina ya? Baridi. Kubwa. Ni pretty sexy kipande wa kanuni, napenda kusema. Kama nilivyosema, Daudi, katika hotuba, baada ya muda, wewe utakuwa zote kuanza kuona kificho kama kitu ambacho ni nzuri. Na wakati mwingine wakati unaweza kuona nzuri kanuni, ni hisia ya ajabu kama. Hivyo hata hivyo, wakati kanuni hizi ni sana nzuri, haina kazi vizuri. Basi hebu kukimbia check50 juu ya hili. Angalia 50 20-- OOP. 2? Ni kwamba pset2? Naam. Loo, pset1. SAWA. Hivyo sisi kukimbia check50. Na kama wewe guys unaweza kuona hapa, ni kushindwa michache ya kesi. Na kwa baadhi yenu, katika kozi ya kufanya seti tatizo lako, wewe ni kama, ah, kwa nini si hivyo kazi. Kwa nini ni kufanya kazi kwa baadhi maadili lakini si kwa wengine? Naam, GDB ni kwenda kukusaidia takwimu kwa nini pembejeo wale walikuwa si kazi. SAWA. Basi hebu angalia, mmoja wa hundi nilikuwa kushindwa katika check50 ilikuwa pembejeo thamani ya 0.41. Hivyo jibu sahihi kwamba unapaswa kuwa kupata ni 4. Lakini badala kile Mimi uchapishaji nje ni 3-n, ambayo ni sahihi. Basi hebu kukimbia tu hii mikono, tu kuhakikisha kwamba check50 ni kazi. Hebu kufanya ./greedy. Lo, nina kufanya tamaa. Kuna sisi kwenda. Sasa ./greedy. Kiasi gani zinadaiwa? Hebu kufanya 0.41. Na yep, tunaona hapa kwamba ni outputting 3 wakati jibu sahihi, kwa kweli, lazima 4. Basi hebu kuingia GDB na kuona ni jinsi sisi wanaweza kwenda juu ya fixing tatizo hili. Hivyo hatua ya kwanza katika Daima debugging kanuni yako ni kuweka breakpoint, au hatua ambayo wewe wanataka kompyuta au HatiJava ili kuanza kuangalia. Hivyo kama wewe si kweli kujua nini tatizo lako ni, Kwa kawaida, jambo kawaida tunataka kufanya ni kuweka breakpoint yetu katika kuu. Hivyo kama wewe guys unaweza kuona hii nyekundu kifungo haki pale, yep, kwamba alikuwa mimi kuweka breakpoint kwa kazi kuu. Mimi bonyeza hapo. Na kisha siwezi kwenda hadi Debug yangu kifungo. Mimi kugonga kwamba kifungo. Hebu zoom nyuma nje kama naweza. Kuna sisi kwenda. Hivyo tuna, hapa, jopo juu ya haki. Samahani, guys katika nyuma, wewe kweli hawezi ona vizuri. Lakini kimsingi, kila jopo hili kulia unafanya ni kuweka wimbo wa wote yalionyesha mstari, ambayo ni mstari wa kanuni kwamba kompyuta sasa mbio, kama vile wote wa vigezo yako chini hapa. Basi nimepata senti, sarafu, n, wote alitangaza kwa mambo mbalimbali katika hatua hii. Hakuna wasiwasi, kwa sababu tuna si kweli initialized yao kwa vigezo yoyote. Hivyo katika kompyuta yako, yako kompyuta ni kuona tu, loo, 32767 alikuwa kazi mwisho kutumika ya kwamba kumbukumbu nafasi katika kompyuta yangu. Na hivyo hapo ndipo senti kwa sasa ni. Lakini hakuna kwamba mara moja kukimbia kificho, ni lazima kuwa initialized. Basi hebu kwenda kupitia, mstari kwa line, nini kinaendelea hapa. SAWA. Hivyo hapa ni tatu vifungo kwamba mimi tu alielezea. Una kucheza, au kukimbia kazi, kifungo, una Hatua juu ya kifungo, na wewe pia Hatua katika kifungo. Na kimsingi, wote watatu wa nao tu kwenda kwa njia kificho yako na kufanya mambo mbalimbali. Hivyo kawaida, wakati wewe ni debugging, hatutaki kuikumba tu kucheza, kwa sababu kucheza itakuwa tu kukimbia kanuni yako kwa mwisho wake. Na kisha utakuwa si kweli kujua nini tatizo lako ni isipokuwa wewe kuweka breakpoints nyingi. Kama kuweka breakpoints nyingi, itakuwa tu moja kwa moja kukimbia kutoka breakpoint moja, ijayo, kwa ijayo. Lakini katika kesi hii tumekuwa tu kwamba moja, kwa sababu sisi wanataka kufanya kazi kwa njia yetu kutoka juu kwenda chini kwa chini. Hivyo sisi ni kwenda kupuuza kwamba kifungo sasa hivi kwa madhumuni ya mpango huu. Hivyo Hatua juu ya kazi tu hatua juu ya kila mstari moja na anakwambia nini kompyuta ni kufanya. Hatua katika kazi inakwenda ndani ya kazi halisi hiyo ni juu ya mstari yako ya kificho. Hivyo kwa mfano, kama printf (), kuwa ni kazi, haki? Kama nilitaka hatua kimwili ndani ya printf () kazi, Napenda kweli kwenda katika kipande cha kificho ambapo printf () iliandikwa na kuona nini kinaendelea huko. Lakini kwa kawaida, sisi kudhani kwamba kificho kwamba sisi kukupa kazi. Sisi kudhani printf () ni kazi. Sisi kudhani kwamba GetInt () ni kazi. Hivyo hakuna haja ya hatua ndani ya kazi hizo. Lakini kama kuna kazi kwamba kuandika mwenyewe kwamba unataka kuangalia nje nini kinaendelea, wewe unataka hatua ndani ya kazi hiyo. Hivyo sasa hivi tunakwenda tu hatua juu ya kipande cha kanuni. Basi hebu angalia. Oh, magazeti, "Oh hai, jinsi mabadiliko mengi zinadaiwa? " Hatujali. Tunajua kwamba kufanya kazi, hivyo sisi hatua juu yake. Hivyo n, ambayo ni kuelea yetu kwamba tumekuwa initialized-- au declared-- juu kwa juu, tuko sasa sawa na kwamba kwa GetFloat (). Basi hebu hatua ya juu hiyo. Na tunaona katika chini hapa, mpango ni kusababisha mimi pembejeo thamani. Basi hebu pembejeo thamani tunataka mtihani hapa, ambayo ni 0.41. Kubwa. Hivyo sasa n-- kufanya nyie ona hapa, katika bottom-- ni stored-- kwa sababu sisi si rounded bado, ni kuhifadhiwa katika hii kubwa kama kuelea kwamba ni 0.4099999996, ambayo ni karibu kutosha yetu madhumuni, sasa hivi, kwa 0.41. Na kisha tutaweza kuona baadaye, kama sisi kuendelea wanazidi juu ya mpango, baada ya hapa, n imekuwa rounded na senti imekuwa 41. Kubwa. Hivyo tunajua kwamba kazi rounding wetu. Tunajua kwamba tuna idadi sahihi ya senti, hivyo tunajua kwamba hiyo ni si kweli tatizo. Hivyo tunaendelea wanazidi juu ya katika mpango huu. Sisi kwenda hapa. Na hivyo baada ya mstari wa kanuni, sisi anapaswa kujua namna ya robo wengi tuna. Sisi hatua zaidi. Na unaona hatuwezi, kwa kweli, na moja robo kwa sababu tumekuwa subtracted 25 kutoka thamani yetu ya awali ya 41. Na tuna 16 kushoto kwa senti yetu. Je, kila mtu kuelewa jinsi mpango ni wanazidi kupitia na kwa nini senti sasa imekuwa 16 na kwa nini, sasa, sarafu imekuwa 1? Ni kila mtu kufuatia mantiki hiyo? Baridi. Hivyo kama ya hatua hii, kazi wa programu hiyo, sawa? Tunajua ni kufanya hasa nini tunataka. Na hatukuwa kweli na magazeti nje, loo, nini ni senti katika hatua hii, kile ni sarafu katika hatua hii. Tunaendelea kwenda kwa mpango. Hatua ya juu. Baridi. Sisi kwenda juu ya Dimes. Kubwa. Tunaona kwamba ni kuchukuliwa mbali $ 0.10 kwa dime. Na sasa tuna senti mbili. Hiyo ni sahihi. Sisi kwenda juu ya pennies na tunaona kwamba tumekuwa got kushoto juu ya senti. Hmm, hiyo ni ajabu. Hadi hapa katika mpango, mimi ilitakiwa kuwa subtracted pennies yangu. Labda mimi tu hakuwa kufanya hivyo mstari wa kulia. Na ole, unaweza kuona hapa, kwa sababu tunajua kwamba sisi ni wanazidi kupitia mistari 32 na 33, hapo ndipo mpango wetu vibaya na vigezo kukimbia. Ili tuweze kuangalia na kuona, loo, Mimi subtracting senti hapa, lakini mimi nina kweli kuongeza thamani wangu sarafu. Mimi na kuongeza kwa senti. Na sitaki kuongeza senti, nataka kuongeza sarafu. Hivyo kama sisi mabadiliko hayo kwa sarafu, sisi tumepewa mpango kazi. Siwezi kukimbia check50. Unaweza tu kujinasua kutoka katika GDB haki hapa na kisha kukimbia check50 tena. Mimi nilikuwa tu kufanya hivyo. Nina kufanya tamaa. 0.41. Na hapa, ni uchapishaji nje jibu sahihi. Hivyo kama wewe guys unaweza kuona, GDB ni kweli zana yenye nguvu kwa wakati tuna kificho sana kinachoendelea na vigezo hivyo wengi kwamba ni vigumu kwa ajili yetu, kama binadamu, kwa kuweka wimbo wa. Kompyuta, katika GDB HatiJava, ina uwezo kuweka wimbo wa kila kitu. Mimi najua, katika Visionaire, nyie pengine anaweza kuwa hit baadhi ya makosa segmentation kwa sababu wewe walikuwa wanakimbia nje ya mipaka ya safu yako. Katika mfano wa Kaisari, hiyo ni nini hasa nimekuwa kutekelezwa hapa. Hivyo mimi alisahau kuangalia kwa nini kitatokea kama mimi hawakuwa na mbili hoja mstari amri. I just hakuwa na kuweka katika kuangalia kwamba. Na hivyo kama mimi kukimbia Debug-- mimi kuweka breakpoint yangu kwa haki huko. Mimi kukimbia Debug. SAWA. Naam. Hivyo kweli, GDB ilitakiwa kwa wameniambia kuna kosa segmentation huko. Sijui nini kinachoendelea haki pale, lakini wakati mimi mbio hilo, ilikuwa kufanya kazi. Wakati kukimbia mstari wa kanuni kupitia na GDB ili tu ghafla kujiondoa juu yenu, kwenda juu na kuangalia nini makosa nyekundu ni. Ni nitakuambia, hey, wewe alikuwa segmentation kosa, ambayo ina maana kwamba alijaribu kupata nafasi katika safu kwamba hayupo. Naam. Hivyo katika tatizo ijayo kuweka wiki hii, nyie pengine kuwa na mengi ya vigezo yaliyo karibu. Wewe si kwenda kuwa na uhakika gani wote maana katika hatua fulani. Hivyo GDB itakuwa kweli kukusaidia katika kuhesabia nini wote ni sawa na na kuwa na uwezo wa kuona kwamba kuibua. Kuna mtu yeyote kuchanganyikiwa juu ya jinsi yoyote ya kuwa alikuwa akifanya kazi? Baridi. Sawa. Kwa hiyo baada ya kuwa, sisi ni kwenda kupiga mbizi haki ndani ya watu wanne tofauti aina ya aina ya wiki hii. Ni wangapi wenu, kwanza kabisa, kabla ya kuanza, wamesoma spec nzima kwa pset3? SAWA. Mimi nina fahari ya nyie. Hiyo ni kama nusu ya darasa, ambayo ni kwa kiasi kikubwa zaidi ya mara ya mwisho. Hivyo hiyo ni kubwa, kwa sababu wakati tunazungumzia kuhusu yaliyomo katika lecture-- au pole, katika section-- Mimi kama kuhusisha mengi ya kwamba nyuma kwa nini pset ni na jinsi gani unataka kutekeleza kwamba katika pset yako. Hivyo kama wewe kuja kuwa kusoma spec, ni itabidi kuwa rahisi sana kwa wewe kuelewa nini mimi kuzungumza kuhusu wakati mimi kusema, loo hey, hii inaweza kuwa kweli sehemu nzuri ya kutekeleza aina hii. Hivyo wale ambao wamesoma Spec kujua kwamba, kama sehemu ya pset yako, wewe ni kwenda kuwa na kuandika aina ya namna yo yote. Hivyo hii inaweza kuwa na manufaa sana kwa mengi ya leo. Hivyo tutaweza kuanza mbali na, kimsingi, aina rahisi zaidi cha aina, aina ya uteuzi. Algorithm ya kawaida kwa jinsi tunatarajia kwenda kuhusu hili is-- Daudi alikwenda kwa njia ya haya yote katika hotuba, hivyo mimi itabidi haraka hoja pamoja here-- ni kimsingi, wewe safu ya maadili. Na kisha kupata thamani ndogo zisizochambuliwa na wewe wabadilishane kwamba thamani na kwanza zisizochambuliwa thamani. Na kisha tu kuendelea kurudia na wengine wa orodha yako. Na hapa ni maelezo ya Visual jinsi ambavyo kazi. Hivyo kwa mfano, kama tulikuwa na kuanza na safu ya mambo matano, ripoti 0-4, na 3, 5, 2, 6, na 4 maadili kuwekwa katika array-- hivyo hivi sasa, sisi ni kwenda tu kwa kudhani kwamba wao ni wote zisizochambuliwa kwa sababu sisi si majaribio vinginevyo. Hivyo ni jinsi gani aina uteuzi kazi ni kwamba ingekuwa kwanza kukimbia kwa njia ya ukamilifu wa safu zisizochambuliwa. Itakuwa kubaini nje thamani ndogo. Katika kesi hiyo, 3, haki sasa, ni ndogo. Anapata hadi 5. Nope, 5 si mkuu than-- au pole, si chini than-- 3. Hivyo thamani ya chini ni bado 3. Na kisha kupata 2. Kompyuta anaona, loo, 2 ni chini ya 3. 2 ni lazima sasa kuwa thamani ya chini. Na hivyo 2 swaps na kwamba thamani kwanza. Kwa hiyo baada ya kupitisha moja, sisi kwa hakika ona kuwa 2 na 3 ni walibadilishana. Na sisi ni kwenda tu kuendelea kufanya hii tena na wengine wa safu. Hivyo sisi ni kwenda kukimbia kwa njia tu bahati minne iliyopita ya safu. Tutaweza kuona kwamba ni 3 ijayo kiwango cha chini thamani. Hivyo sisi ni kwenda wabadilishane kwamba pamoja na 4. Na kisha sisi ni kwenda tu kuweka mbio kwa njia mpaka hatimaye, wewe kupata safu Iliyopangwa ambao 2, 3, 4, 5, na 6 zote ni vyema. Je, kila mtu kuelewa mantiki jinsi aina uteuzi kazi? Wewe tu aina fulani ya thamani ya chini. Wewe ni kuweka wimbo wa nini kwamba ni. Na wakati wowote kupata hiyo, wewe wabadilishane na thamani ya kwanza katika array-- au, si value-- kwanza thamani pili katika safu. Baridi. Hivyo kama wewe guys aina ya aliona kutoka mtazamo kifupi, tunakwenda pseudocode hii nje. Hivyo kama wewe guys katika nyuma wanataka kuunda kikundi, kila mtu mezani huweza kutengeneza mpenzi kidogo, mimi nina kwenda kukupa guys kama dakika tatu tu kuzungumza kupitia mantiki, kwa Kiingereza, ya jinsi sisi kuwa na uwezo wa kutekeleza pseudocode kuandika aina uteuzi. Na kuna pipi. Tafadhali kuja na kupata pipi. Kama uko katika nyuma na unataka pipi, siwezi kutupa pipi saa wewe. Kwa kweli, kufanya you-- baridi. Oh, pole. SAWA. Hivyo kama tungependa, kama darasa, kuandika pseudocode kwa jinsi mtu anaweza mbinu tatizo hili, tu kujisikia huru. Mimi itabidi kwenda karibu na, ili, watake wanafunzi kwa mstari wa pili wa nini tunapaswa kufanya. Hivyo kama wewe guys unataka kuanza mbali, nini jambo la kwanza ni cha kufanya wakati wewe ni kujaribu kutekeleza njia ya kutatua mpango huu selectively aina orodha? Hebu tu kudhani sisi na safu, sawa? Watazamaji: Unataka kuunda baadhi aina ya [inaudible] kwamba wewe ni mbio kwa njia ya safu yako yote. ANDI PENG: Haki. Hivyo wewe ni kwenda kutaka iterate njia ya kila nafasi, haki? Kwa hiyo, kubwa. Kama wewe guys wanataka kunipa ijayo line-- yeah, katika nyuma. Watazamaji: Angalia yao zote kwa ndogo. ANDI PENG: Kuna sisi kwenda. Hivyo tunataka kwenda kwa njia na kuangalia kwa kuona nini thamani ya chini ni, sawa? Mimi nina kwenda abbreviate kwamba kwa "dk." Nini guys wanataka kufanya baada ya Nimepata thamani ya chini? Watazamaji: [inaudible] ANDI PENG: Hivyo wewe ni kwenda kutaka kubadili ni pamoja na ya kwanza ya kwamba safu, sawa? Hiyo ni mwanzo, mimi nina kwenda kusema. Sawa. Hivyo sasa kwamba umefanya swapped kwanza moja, unataka nini cha kufanya baada ya hayo? Hivyo sasa tunajua kwamba hii moja hapa lazima thamani ndogo, sivyo? Kisha una wengine ziada wa safu hiyo ni zisizochambuliwa. Kwa hiyo kile unataka kufanya hapa, kama wewe guys wanataka kunipa mstari baada ya hapo? Watazamaji: Hivyo basi unataka iterate kupitia salio ya safu. ANDI PENG: Naam. Na hivyo ni nini iterating kupitia aina ya kuashiria tutaweza pengine haja? Ni aina gani of-- Watazamaji: Oh, kutofautiana ziada? ANDI PENG: Pengine mwingine kwa kitanzi, haki? Hivyo sisi ni pengine atataka iterate through-- kubwa. Na kisha wewe ni kwenda kurudi nyuma na pengine kuangalia kiwango cha chini tena, sawa? Na wewe ni kwenda kuendelea kurudia hii, kwa sababu mizunguko kwenda tu kuweka mbio, sawa? Hivyo kama wewe guys unaweza kuona, sisi tu na pseudocode ujumla jinsi tunataka mpango huu kwa kuangalia. Iterate hii hapa, tunafanya nini kawaida haja ya kuandika katika kanuni zetu kama tunataka iterate kupitia safu, ni aina gani ya muundo? Nadhani Christabel tayari kusema hayo kabla. Watazamaji: A kwa kitanzi. ANDI PENG: A kwa kitanzi? Hasa. Hivyo hii pengine ni kwenda kuwa kwa kitanzi. Ni kuangalia hapa kwenda kuashiria nini? Kwa kawaida, kama unataka kuangalia kama kitu fulani ni kitu else-- Watazamaji: Kama. ANDI PENG: An kama, sawa? Na kisha wabadilishane hapa, tutaweza kwenda juu baadaye, kwa sababu Daudi safari kwa kupitia kwamba katika hotuba pia. Na kisha iterate pili implies-- Watazamaji: jingine kwa kitanzi. ANDI PENG: --another kwa kitanzi, hasa. Hivyo kama sisi ni kuangalia wakati huu kwa usahihi, sisi unaweza kuona kwamba tuko pengine kwenda haja nested kwa kitanzi na kauli masharti katika huko na kisha kipande halisi ya kificho hiyo ni kwenda wabadilishane maadili. Hivyo nimekuwa tu kwa ujumla imeandikwa pseudocode kificho hapa. Na kisha sisi ni kweli kwenda kimwili, kama darasa, kujaribu kutekeleza hili leo. Hebu kwenda nyuma katika IDE hii. Uh-oh. Kwa nini ni kwamba not-- huko ni. SAWA. Samahani, napenda kujaribu kuvuta kidogo zaidi. Kuna sisi kwenda. Wote mimi nina kufanya hapa ni Nimekuwa kuundwa mpango ujulikanao "uteuzi / sort.c." Nimekuwa kuundwa safu ya tisa maadili, 4, 8, 2, 1, 6, 9, 7, 5, 3. Hivi sasa, kama unaweza kuona, wao ni unordered. n ni kwenda kuwa idadi hiyo atakwambia kiasi cha maadili una katika safu yako. Katika kesi hiyo, tuna maadili tisa. Na nimekuwa tu got kwa kitanzi hapa kwamba Prints nje safu zisizochambuliwa. Na mwisho, nimekuwa pia alipata kwa kitanzi kwamba tu Prints nje tena. Hivyo kinadharia, ikiwa mpango huu ni kufanya kazi kwa usahihi, mwishoni, unapaswa kuona kuchapishwa kwa kitanzi ambao 1, 2, 3, 4, 5, 6, 7, 8, 9 ni yote kwa usahihi ili. Hivyo sisi tumepewa pseudocode wetu hapa. Je, mtu yeyote wanataka to-- Mimi tu kwenda kuomba volunteers-- kuniambia nini hasa aina ikiwa tunataka, kwanza, tu iterate njia ya mwanzo wa safu hii? Nini mstari wa kanuni mimi nina pengine ni kwenda haja hapa? Watazamaji: [inaudible] ANDI PENG: Yeah, kuhisi bure to-- pole, wewe hawana kusimama kujisikia up-- bure kuinua sauti yako kidogo. Watazamaji: Kwa int i sawa 0-- ANDI PENG: Yeah, nzuri. Watazamaji: i ni chini ya safu urefu. ANDI PENG: Hivyo kuweka katika akili hapa, kwa sababu sisi hawana kazi ambayo anatueleza urefu wa safu, tayari tuna thamani kwamba maduka hilo. Sawa? Kitu kingine kushika katika mind-- katika safu maadili tisa, bahati kile ni? Hebu tu kusema safu hii ilikuwa 0-3. Unaweza kuona kwamba mwisho ripoti ni kweli 3. Siyo 4, ingawa kuna maadili nne katika safu. Hivyo katika hapa, inabidi kuwa makini sana ya nini hali yetu kwa urefu ni kwenda kuwa. Watazamaji: Je, si ni n bala 1? ANDI PENG: Ni kwenda n bala 1, hasa. Je, hiyo mantiki, kwa nini ni n bala 1, kila mtu? Ni kwa sababu arrays ni sifuri indexed. Wao kuanza saa 0 na kuelekea kwenye n bala 1. Yeah, ni kidogo suala gumu. SAWA. Na then-- Watazamaji: Isnt'1 kwamba tayari kuchukuliwa huduma ya, ingawa, na sio tu kusema "chini ya au sawa na "na kusema tu" chini ya? " ANDI PENG: Hiyo ni mzuri swali. Kwa hiyo, ndiyo. Lakini pia, kwa njia hiyo tuko utekelezaji wa haki cheki, unahitaji kulinganisha maadili mbili. Kweli hiyo unataka kuondoka "na" tupu. Kwa sababu kama kulinganisha hii moja, wewe si kwenda kuwa na kitu chochote baada ya kwa kulinganisha na, sawa? Naam. Hivyo i ++. Hebu kuongeza mabano yetu katika. Whoops. Kubwa. Hivyo tuna mwanzo ya kitanzi yetu ya nje. Hivyo sasa sisi pengine wanataka kujenga kutofautiana kwa ajili ya kuweka wimbo wa thamani ndogo, sivyo? Je, mtu yeyote wanataka kunipa mstari wa kanuni hiyo inaweza kufanya hivyo? Je, tunahitaji kama sisi ni kwenda kutaka kuhifadhi kitu? Kulia. Labda jina bora kwa kuwa ingekuwa be-- "temp" works-- kabisa labda zaidi aptly aitwaye itakuwa, kama tunataka ndogo value-- Watazamaji: Min. ANDI PENG: dk, kuna sisi kwenda. dk itakuwa vizuri. Na hivyo hapa, tunafanya nini wanataka initialize kwa? Hii ni kidogo suala gumu. Kwa sababu sasa hivi katika mwanzo wa safu hii, wewe si inaonekana katika kitu chochote, sawa? Kwa hiyo kile, moja kwa moja, kama tuko tu juu ya i sawa 0, je, tunataka initialize kiwango cha chini yetu thamani kwanza kwa? Watazamaji: i. ANDI PENG: i, hasa. Christabel, kwa nini tunataka kwa initialize kwa i? Watazamaji: Kwa sababu, vizuri, sisi ni mapya na 0. Hivyo kwa sababu hatuna cha kulinganisha kwa, kiwango cha chini kuishia kuwa 0. ANDI PENG: Hasa. Hivyo yeye ni kweli kabisa. Kwa sababu tuna si kweli inaonekana katika chochote bado, sisi hawajui nini cha chini cha thamani yetu ni. Tunataka tu initialize kwa i, ambayo, kwa sasa, ni haki hapa. Na kama tunaendelea hoja chini safu hii, tutaweza kuona kwamba, na kila kupita ziada, i nyongeza. Na hivyo katika hatua hiyo, i pengine ni kwenda kutaka kuwa kiwango cha chini, kwa sababu itakuja kuwa chochote ni mwanzo wa safu zisizochambuliwa. Baridi. Hivyo sasa tunataka kuongeza a kwa kitanzi hapa kwamba kwenda iterate kupitia zisizochambuliwa, au maeneo mengine ya safu hii. Je, mtu yeyote wanataka kunipa mstari wa kanuni hiyo inaweza kufanya hivyo? Hint-- tunahitaji nini chini hapa? Nini kinaendelea kwenda katika hii kwa kitanzi? Naam. Watazamaji: Hivyo tunatarajia wanataka kuwa integer tofauti, kwa sababu sisi ni mbio kwa njia ya mapumziko wa safu badala ya i, hivyo labda j. ANDI PENG: Yeah, j sauti nzuri kwangu. Sawa? Watazamaji: Hivyo itakuwa i pamoja na 1, kwa sababu wewe ni kuanzia saa thamani ujao. Na kisha kwa end-- hivyo tena, j ni chini ya n bala 1, na kisha j ++. ANDI PENG: Mkuu. Na kisha katika hapa, sisi ni kwenda kutaka kuangalia ili kuona kama hali yetu ni alikutana, sawa? Sababu unataka mabadiliko ya thamani ya chini kama ni kweli ndogo kuliko yale wewe ni kulinganisha na, sawa? Kwa hiyo kile ni sisi kwenda kutaka katika hapa? Angalia kuona. Aina gani ya taarifa ni sisi pengine ni kwenda ti wanataka kutumia kama sisi unataka kuangalia kitu? Watazamaji: An kama taarifa. ANDI PENG: An kama taarifa. Hivyo if-- na nini kinaendelea kuwa masharti kwamba tunataka ndani ya ya kama kauli zetu? Watazamaji: Kama thamani ya j ni chini ya thamani ya i-- ANDI PENG: Hasa. Hivyo if-- hivyo safu hii inaitwa "safu." Kubwa. Hivyo kama array-- nini ilikuwa hivyo? Kusema kwamba tena. Watazamaji: Kama safu-j ni chini ya safu-i, basi tunataka mabadiliko dk. Hivyo dk itakuwa j. ANDI PENG: Je, hiyo mantiki? SAWA. Na sasa chini hapa, sisi kweli wanataka kutekeleza wabadilishane, sawa? Hivyo kukumbuka, katika hotuba, Daudi, wakati alikuwa anajaribu wabadilishane the-- nini ilikuwa it-- juisi ya machungwa na milk-- Watazamaji: Hiyo ilikuwa ni ya jumla. ANDI PENG: Yeah, kwamba ilikuwa ni aina ya jumla. Lakini ilikuwa nzuri dhana kuonyesha wakati. Hivyo kufikiri ya maadili yako hapa. Nimepata safu ya dk, safu ya i, au chochote sisi walikuwa wakijaribu wabadilishane hapa. Na pengine hawezi kumwaga yao katika kila mmoja kwa wakati mmoja, sawa? Kwa hiyo kile ni sisi kwenda kwa haja ya kuunda hapa ili wabadilishane maadili usahihi? Watazamaji: kutofautiana muda. ANDI PENG: kutofautiana muda. Basi hebu kufanya int temp. Angalia, hii itakuwa bora muda to-- Ho, nini ilikuwa hivyo? SAWA. Hivyo hii ingekuwa bora muda kwa jina kutofautiana "temp." Basi hebu kufanya int temp. Je, ni sisi kwenda kuweka temp sawa hapa? Watazamaji: Min? ANDI PENG: Ni kidogo suala gumu. Ni kweli haina jambo katika mwisho. Haijalishi nini Ili kuchagua wabadilishane katika muda mrefu kama wewe ni kuhakikisha uko kuweka wimbo wa nini wewe swapping. Watazamaji: Ni inaweza kuwa safu-i. ANDI PENG: Yeah, hebu kufanya safu-i. Na kisha nini mstari unaofuata wa kanuni tunataka kuwa na hapa? Watazamaji: safu-i sawa safu-j. ANDI PENG: Na mwisho? Watazamaji: safu-j sawa na safu-i. Watazamaji: Au safu-j sawa safu-temp-- au, temp. ANDI PENG: Sawa. Basi hebu kukimbia hii na kuona kama ni kwenda kufanya kazi. Ambapo ni kwamba kinachotokea? Oh, hiyo ni tatizo. Angalia, kwenye mstari 40, tuko kujaribu kutumia safu-j? Lakini wapi j tu zipo katika? Watazamaji: Katika kwa kitanzi. ANDI PENG: Haki. Kwa hiyo kile ni sisi kwenda haja ya kufanya? Watazamaji: Define yake nje the-- Watazamaji: Yeah, mimi nadhani una kutumia mwingine kama kauli, sawa? Hivyo kama, kama minimum-- sawa, basi mimi nadhani. ANDI PENG: Guys, jaribu kuchukua kuangalia Hebu kuona, nini kitu tunaweza kufanya hapa? Watazamaji: Sawa. Hivyo kama kiwango cha chini haina sawa j-- hivyo bado kama kiwango cha chini ni i-- kisha tunataka kuwa wabadilishane. ANDI PENG: Je, hiyo ni sawa i? Je, unataka kusema hapa? Watazamaji: Au ndiyo, ikiwa kiwango cha chini hana i si sawa, yeah. ANDI PENG: Sawa. Vizuri kwamba kutatua, aina ya matatizo yetu. Lakini hiyo bado haina kutatua tatizo la kile kinachotokea kama j-- tangu j haipo nje ya hiyo, ni nini je, tunataka kufanya hivyo? Kuyatangaza nje? Hebu jaribu mbio hii. Uh-oh. Aina yetu si kazi. Kama unaweza kuona, awali wetu safu alikuwa maadili hayo. Na baadaye ni lazima kuwa na wamekuwa katika 1, 2, 3, 4, 5, 6, 7, 8, 9. Siyo kazi. Ahh. Tufanye nini? Watazamaji: Debug. ANDI PENG: zote haki, tunaweza kujaribu kuwa. Tunaweza Debug. Kuvuta nje kidogo. Hebu kuweka breakpoint yetu. Hebu kwenda like-- sawa. Hivyo kwa sababu sisi tayari kujua kuwa mistari haya, 15 kwa njia ya 22 ni working-- kwa sababu wote mimi nina kufanya ni tu iterating kupitia na printing-- Siwezi kwenda mbele na ruka hiyo. Hebu kuanza katika mstari wa 25. OOP, napenda kujikwamua huo. Watazamaji: Hivyo breakpoint ya ambapo debugging kuanza? ANDI PENG: Au vituo. Watazamaji: Au vituo. ANDI PENG: Naam. Unaweza kuweka breakpoints nyingi na inaweza tu kuruka kutoka moja hadi nyingine. Lakini katika kesi hii hatujui ambapo kosa kinachotokea. Hivyo sisi tu wanataka kuanza kutoka juu kwenda chini. Yep. SAWA. Hivyo mstari huu hapa, tunaweza kuingilia kati. Unaweza kuona chini hapa, sisi tumepewa safu. Hayo ni maadili walio katika safu. Je, unaweza kuona kwamba, jinsi ripoti 0, ni sambamba na value-- loo, Mimi nina kwenda kujaribu kuvuta. Pole, ni vigumu kweli kwa see-- katika safu ripoti 0, tuna thamani ya 4 na kisha kadhalika na kadhalika. Tuna vigezo yetu ya ndani. Sasa hivi i ni sawa na 0, ambayo sisi unataka kuwa ni. Na hivyo hebu kuweka wanazidi kupitia. Kiwango cha chini yetu ni sawa na 0, ambayo sisi pia unataka kuwa ni. Na kisha sisi kuingia wa pili yetu kwa kitanzi, ikiwa safu-j ni chini ya safu-i, ambayo haikuwa hivyo. Hivyo, unaweza kuona jinsi gani kwamba skipped juu kwamba? Watazamaji: Hivyo lazima kama kiwango cha chini, kila that-- hawapaswi kuwa kuwa ndani ya kwanza kwa kitanzi? ANDI PENG: Hapana, kwa sababu wewe bado wanataka mtihani. Unataka kufanya kulinganisha kila muda, hata baada ya kukimbia kwa njia hiyo. Wewe hawataki tu ya kufanya hivyo siku ya kwanza kupita-kwa njia ya. Unataka kufanya hivyo kwa kupita kila ziada tena. Hivyo unataka kuangalia kwa hali yako ndani ya. Hivyo sisi ni kwenda tu kwa kuweka mbio kupitia hapa. Mimi nitakupa guys ladha. Ni ina nini na ukweli kwamba wakati wewe ni kuangalia masharti yako, wewe si kuangalia kwa ripoti sahihi. Hivyo sasa hivi uko kuangalia kwa safu ripoti ya j ni chini ya safu ripoti ya i. Lakini unafanya nini hadi saa mwanzo wa kwa kitanzi? Si wewe kuweka j sawa na i? Yeah, hivyo tunaweza kweli kujinasua HatiJava hapa. Basi hebu tuangalie pseudocode yetu. For-- tunakwenda kuanza saa i sawa 0. Tunakwenda kwenda n bala 1. Hebu angalia, je tuna kuwa sawa? Yep, kwamba alikuwa sahihi. Hivyo basi ndani ya hapa, tuko kwenda kujenga thamani ya chini na kuweka kwamba sawa na i. Je, sisi kufanya hivyo? Yep, alifanya hivyo. Sasa katika wetu wa ndani kwa kitanzi, tuko kwenda kufanya j sawa na i na n bala 1. Je, sisi kufanya hivyo? Kwa hakika, sisi alifanya hivyo. Hivyo hata hivyo, ni sisi kulinganisha hapa? Watazamaji: j pamoja na 1. ANDI PENG: Hasa. Na kisha wewe ni kwenda unataka kuweka kiwango cha chini yako sawa na j pamoja na 1 vilevile. Basi, mimi nikaenda kupitia kwamba kweli haraka. Je, guys kuelewa kwa nini ni j pamoja na 1? SAWA. Hivyo katika safu yako, katika kupita yako kwanza kwa njia, yako kwa kitanzi, kwa int i sawa 0, hebu tu kudhani hii haijawahi iliyopita bado. Tuna safu ya, kabisa, zisizochambuliwa mambo manne tu, sawa? Hivyo tunataka initialize i sawa na 0. Na i ni kwenda tu kukimbia kwa njia ya kitanzi hii. Na hivyo katika kupita kwanza, tunakwenda initialize variable kuitwa "dk" kwamba pia ni sawa na i, kwa sababu hatuna thamani ya chini. Hivyo hiyo ni sasa sawa na 0 vilevile. Na kisha tunakwenda kupitia. Na tunataka iterate tena. Sasa kwa kuwa tumekuwa kupatikana nini kiwango cha chini yetu ni, tunataka iterate kupitia tena ili kuona kama ni kulinganisha, sawa? Hivyo j, hapa, ni kwenda i sawa, ambayo ni 0. Na kisha kama safu j pamoja na i, ambayo ni moja kwamba ijayo juu, kama chini kuliko yale kiwango cha chini sasa wako thamani ya kitu, unataka wabadilishane. Basi hebu tu kusema tumekuwa got, kama, 2, 5, 1, 8. Hivi sasa, i ni sawa na 0 na j ni sawa na 0. Na hiyo ndiyo thamani yetu kiwango cha chini. Kama safu-j pamoja i-- hivyo kama moja hiyo ni baada ya moja sisi ni kuangalia ni mkubwa kuliko moja kabla yake, itakuja kuwa kiwango cha chini. Hivyo hapa tunaona kwamba 5 si chini ya hapo. Hivyo ni kwenda kwa kuwa 5. Tunaona kwamba 1 ni chini ya 2, sawa? Hivyo sasa tunajua kwamba kiwango cha chini yetu ni kwenda kuwa thamani index saa 0, 1, 2. Yeah? Na kisha wakati kupata chini hapa, unaweza wabadilishane maadili sahihi. Hivyo wakati nyie walikuwa kuwa tu j kabla, walikuwa hawaangalii moja baada yake. Wewe walikuwa kuangalia thamani sawa, ambayo Hii ndiyo sababu ni tu si kufanya kitu chochote. Je, hiyo mantiki kwa kila mtu, kwa nini sisi zinahitajika kuwa pamoja na 1 huko? SAWA. Sasa hebu kukimbia tu njia hiyo kufanya uhakika mapumziko ya kificho ni sahihi. Kwa nini kuwa kinachotokea? Ah, ni dk haki hapa. Tulikuwa kulinganisha thamani vibaya. Oh no. Oh yeah, chini hapa tulikuwa swapping maadili vibaya pia. Kwa sababu sisi walikuwa kuangalia i na j. Hao ndio tulikuwa kuangalia. Sisi kwa kweli unataka wabadilishane kiwango cha chini, kiwango cha chini ya sasa, na chochote nje moja ni. Na kama nyie unaweza kuona chini hapa, tuna safu Iliyopangwa. Ni tu alikuwa na kufanya na ukweli kwamba wakati tulikuwa kuangalia maadili tulikuwa kulinganisha, sisi si kuangalia maadili ya haki. Tulikuwa tukiangalia moja sawa hapa, si kweli swapping yake. Una kuangalia moja ijayo kwa hiyo na kisha unaweza wabadilishane. Hivyo kwamba ni nini ilikuwa ni aina ya bugging kificho yetu kabla. Na nini mimi hapa ni kila kitu HatiJava wangefanya kwa wewe Mimi tu alifanya hivyo juu ya bodi, kwa sababu ni rahisi kuona badala ya kujaribu kuvuta juu ya HatiJava. Je, hiyo mantiki kwa kila mtu? Baridi. Sawa. Tunaweza kuendelea na kuzungumza juu ya asymptotic nukuu, ambayo ni njia tu ya dhana ya kusema runtimes wa wote wa aina hii. Hivyo najua Daudi, katika hotuba, kuguswa juu runtimes. Katika safari hiyo alipitia fomula nzima ya jinsi ya mahesabu runtimes. Hakuna wasiwasi juu ya hilo. Kama wewe ni kweli wadadisi juu ya jinsi kazi, kujisikia huru kuzungumza na mimi baada ya sehemu. Tunaweza kutembea kwa njia ya kanuni kwa pamoja. Lakini nyie wote wana kwa kweli kujua ni kwamba n squared zaidi ya 2 ni kitu kimoja kama n squared. Kwa sababu idadi kubwa, exponent, kukua zaidi. Na hivyo kwa madhumuni yetu, zote sisi huduma ya juu ni kwamba idadi kubwa hiyo kuongezeka. Kwa hiyo kile ni bora kesi Runtime ya uteuzi aina? Kama wewe ni kwenda kuwa na iterate kupitia orodha na kisha iterate kupitia wengine wa orodha hiyo, mara ngapi ni wewe kwenda pengine, katika case-- mbaya zaidi katika bora kesi, sorry-- kukimbia kwa njia ya? Labda swali bora ni kuuliza, ni nini hali mbaya Runtime ya uteuzi aina. Watazamaji: n squared. ANDI PENG: Ni n squared, haki. Hivyo njia rahisi kufikiria hii ni kama, wakati wowote una mbili Furushi kwa tanzi, itakuja kuwa n squared. Kwa sababu ni wewe si tu mbio kwa njia ya mara nyingine tena, una kwenda nyuma karibu na kukimbia kwa njia hiyo kwa mara nyingine tena ndani ya kwa kila thamani. Hivyo katika kesi hiyo, wewe ni mbio n Mara n squared, ambayo is-- pole, n mara n, ambayo ni sawa na n squared. Na aina pia ni kidogo kipekee kwa maana kwamba haijalishi kama hizi maadili ni tayari kwa utaratibu. Ni bado kwenda kukimbia kupitia anyways. Hebu tu kusema hii ilikuwa 1, 2, 3, 4. Bila kujali kama au si ilikuwa ni katika Ili, bado ingekuwa mbio kwa njia ya na bado kuchunguzwa thamani ya chini. Ingekuwa na sawa idadi ya hundi kila wakati, hata kama ni hawakuwa kweli kugusa kitu chochote. Hivyo katika kesi hiyo, bora na mbaya zaidi runtimes ni kweli sawa. Hivyo Runtime inatarajiwa ya uteuzi aina, ambayo sisi mteule na ishara ya theta, theta, katika kesi hii, pia kuwa n squared. Yote matatu ya hizi itakuwa n squared. Ni kwa nini kila mtu wazi Runtime ni n squared? Sawa. Hivyo mimi nina kwenda tu haraka kukimbia njia ya mapumziko ya kila aina. Algorithm kwa Bubble sort-- kumbuka, hii ilikuwa ni moja ya kwanza Daudi akaenda ng'ambo katika hotuba. Kimsingi, hatua kupitia orodha nzima na wewe swap-- wewe tu kulinganisha mbili kwa wakati mmoja. Kama mtu ni mkubwa, kuliko wewe tu wabadilishane yao. Hivyo kama haya ni makubwa, ungekuwa wabadilishane. Mimi nimepata rasmi hapa hapa. Basi hebu tu kusema alikuwa na 8, 6, 4, 2. Wewe d kulinganisha 8 na 6. Wewe d haja ya kubadilishana nao. Ungependa kulinganisha 8 na 4. Wewe d haja ya kubadilishana nao. Kama una wabadilishane 8 na 2, kuwabadilisha pia. Hivyo kwa mantiki hiyo, unaweza kuona, kucheza nje kwa kipindi cha muda mrefu, jinsi maadili aina ya Bubble ncha, ambayo ni kwa nini sisi kuiita Bubble aina. Tunataka tu kukimbia kwa njia tena juu ya kupita wetu wa pili, na kupita wetu wa tatu, na kupita yetu ya nne. Kimsingi, Bubble anaendesha aina tu mpaka hatuwezi kufanya swaps yoyote zaidi. Hivyo kwa maana kwamba, hii ni pseudocode ujumla kwa ajili yake. Hakuna wasiwasi, haya yote itakuwa online. Hatuna kwa kweli kwenda juu ya hili. Sisi tu initialize kukabiliana kutofautiana kwamba kuanza saa 0. Na sisi iterate kupitia safu nzima. Na kama thamani moja is-- kama hii thamani ni mkubwa kuliko thamani ya kuwa, wewe ni kwenda wabadilishane yao. Na kisha wewe tu kwenda kuendelea. Na wewe ni kwenda kuhesabu. Na wewe ni kwenda tu kuendelea kufanya hii wakati kukabiliana ni mkubwa kuliko 0, ambayo ina maana kwamba kila wakati una wabadilishane, unajua unataka kwenda nyuma na kuangalia tena. Unataka kuweka kuangalia mpaka unajua kwamba huna wabadilishane tena. Kwa hiyo kile ni bora na mbaya zaidi kesi runtimes kwa Bubble aina? Na hint-- huu ni tofauti kutoka uteuzi aina katika akili kwamba baadhi ya majibu haya mawili si sawa. Fikiria juu ya nini kitatokea katika kesi kama hiyo ilikuwa tayari Iliyopangwa. Na kufikiri kuhusu nini kitafanyika kama ilivyokuwa katika kesi ambayo haikuwa yamepangwa. Na unaweza aina ya kuendesha kupitia kwa nini kinatokea. Mimi nitakupa guys, kama, 30 sekunde kufikiri kuhusu hilo. SAWA. Je, mtu yeyote kuwa na nadhani katika nini kesi mbaya Runtime ya Bubble aina ni? Naam. Watazamaji: Je, ni kuwa, kama, n mara n bala 1 au kitu kama hicho? Kama, kila wakati anaendesha, ni tu, kama, wabadilishane moja chini kwamba chochote hivyo. ANDI PENG: Yeah, hivyo wewe ni haki kabisa. Na hii ni kesi ambayo yako Jibu lilikuwa kweli ngumu zaidi ya moja tunahitaji kuwapa. Hivyo ni kwenda kwa run-- mimi nina kwenda kufuta yote haya hapa. Ni kila mtu mwema? Naweza kufuta hili? SAWA. Wewe ni kwenda kukimbia kwa njia ya n Mara kwa mara ya kwanza, sawa? Na wao wanaenda kukimbia kwa njia ya n bala 1 mara ya pili, sawa? Na kisha wewe ni kwenda kuweka kwenda, n yangu 2, nakadhalika. Daudi alifanya hivyo katika hotuba, ambapo, kama wewe aliongeza up maadili wale wote, kupata kitu ambacho ni like-- yeah-- zaidi ya 2, ambayo kimsingi tu inapunguza chini ya n squared. Wewe ni kwenda kupata sehemu weird katika huko. Na hivyo tu kujua kwamba n squared daima inachukua precedence juu ya sehemu. Na hivyo katika kesi hii, mbaya Runtime itakuwa n squared. Kama ilivyokuwa katika kushuka ili, kufikiri, wewe Una kufanya wabadilishane kila wakati. Nini itakuwa, uwezekano, bora kesi Runtime? Hebu sema tu, kama orodha alikuwa tayari ili, gani Runtime kuwa? Watazamaji: n. ANDI PENG: Ni n, hasa. Na kwa nini ni n? Watazamaji: Kwa sababu wewe tu kuwa na kuangalia juu ya kila mmoja. ANDI PENG: Hasa. Hivyo katika bora Runtime, kama orodha hii alikuwa tayari sorted-- hebu sema 1, 2, 3, 4-- wewe ingekuwa tu kwenda kwa njia ya, ungekuwa kuangalia, ungependa kuona, loo, wote sufuria nje. Sikuwa na wabadilishane. Nimemaliza. Hivyo katika kesi hiyo, ni tu n au idadi ya hatua wewe tu alikuwa na kuangalia katika orodha ya kwanza. Na baada, sisi sasa kugonga kuingizwa aina, ambapo algorithm kimsingi ni kwa mgawanyiko ndani yamepangwa na zisizochambuliwa sehemu. Na kisha moja kwa moja, maadili zisizochambuliwa ni kuingizwa katika sahihi zao vyeo katika mwanzo wa orodha. Hivyo kwa mfano, tuna orodha ya 3, 5, 2, 6, 4 tena. Tunajua kwamba ni sasa zisizochambuliwa kwa sababu tumekuwa tu kuanza kuangalia saa yake. Sisi kuangalia na tunajua kwamba thamani kwanza ni yamepangwa, sawa? Kama wewe ni tu kuangalia safu ya ukubwa moja, unajua kwamba ni yamepangwa. Hivyo basi tunajua kwamba wengine wanne ni zisizochambuliwa. Sisi kwenda kwa njia na tunaona thamani hiyo. Hebu kwenda nyuma. Kuona kwamba thamani ya 5? Sisi kuangalia yake. Sisi kulinganisha kwa 3. Tunajua kwamba ni mkubwa kuliko 3, hivyo tunajua kwamba hiyo ni vyema. Hivyo sisi sasa tunajua kuwa mbili ya kwanza ni vyema na mitatu iliyopita si. Sisi kuangalia 2. Sisi kwanza kuangalia ni kwa 5. Je, ni chini ya 5? Siyo. Hivyo tuna kuweka kuangalia chini. Basi angalia 2 mbali 3. Je, ni chini ya? Hakuna Hivyo unajua 2 ana kuingizwa ndani ya mbele na 3 na 5 wote wana kwa kusukuma nje. Kufanya hivyo tena na 6 na 4. Na sisi tu kuendelea kuangalia kimsingi, ambapo sisi tu kuangalia, kuangalia, kuangalia. Na mpaka ni katika haki msimamo, sisi aina ya tu kuingiza ndani ya nafasi ya haki, ambayo ni wapi jina la ulitoka. Hivyo hiyo ni algorithm, pseudocode per se, aina ya, juu ya jinsi gani tunataka kutekeleza kuingizwa aina. Pseudocode ni hapa. Ni wote online. Hakuna wasiwasi kama wewe guys ni kujaribu nakala hii chini. Hivyo mara nyingine tena, huo question-- nini Itakuwa bora na runtimes mbaya kwa kuingizwa aina? Ni sawa na swali la mwisho. Mimi nitakupa guys, kama, 30 sekunde kufikiri kuhusu huu pia. OK Je, mtu yeyote wanataka nipe mbaya Runtime? Naam. Watazamaji: n squared. ANDI PENG: Ni n squared. Na kwa nini ni n squared? Watazamaji: Kwa sababu katika ili reverse, una kwenda kwa nyakati n n, ambayo is-- ANDI PENG: Yeah, kwa uhakika. Jambo hivyo kama hicho katika aina Bubble. Kama orodha hii ni katika utaratibu wa kushuka, wewe ni kwenda na kuangalia mara moja kwanza. Na kisha kwa kila thamani ya ziada, wewe ni kwenda na kuangalia ni juu ya kila thamani moja, sawa? Na hivyo kabisa, wewe ni kwenda kufanya mara n kupita mwingine n kupita, ambayo ni n squared. Je kuhusu kesi bora? Naam. Watazamaji: N bala 1, kwa sababu Wa kwanza tayari mraba. ANDI PENG: Kwa hiyo, karibu. Jibu ni kweli n. Kwa sababu wakati mmoja kwanza ni yamepangwa, inaweza actually-- ni sisi tu lucked nje, katika mfano ile, 2 kilichotokea kwa kuwa idadi ndogo. Lakini hiyo si mara zote kuwa kesi. Kama 2 tayari Iliyopangwa katika mwanzo lakini ukiangalia na kuna 1 hapa, 1 ni kwenda mapema yake. Na ni kwenda mwisho up kuwa bumped anyways. Hivyo katika bora kesi, ni kweli tu kwenda kuwa n. Kama una 1, 2, 3, 4, 5, 6, 7, 8, uko kwenda kukimbia kupitia orodha hiyo nzima mara moja kuangalia ili kuona kama faini kila kitu. Ni kila mtu wazi juu ya mbio nyakati za uteuzi vile vile? Najua mimi nina kwenda kupitia hizi kweli kasi. Lakini tu kujua kwamba kama unajua dhana ujumla, unapaswa kuwa nzuri. SAWA. Hivyo mimi itabidi kukupa guys labda, kama, dakika ya kuzungumza na majirani wako juu ya nini ni baadhi tu ya tofauti kubwa kati ya aina hizi za kila aina. Tutaweza kwenda juu kwamba hivi karibuni. Watazamaji: Oh, Sawa. ANDI PENG: Naam. SAWA. Baridi, hebu kuitisha kama darasa. SAWA. Hivyo hii ilikuwa ni aina ya sifunge swali katika akili kwamba kuna kura ya majibu yao. Na tutaweza kwenda juu baadhi yao kwa ufupi. Mimi nilitaka kupata nyie kufikiri juu ya nini tofauti aina zote tatu za kila aina. Kisha nikasikia, pia, mkubwa question-- nini kuunganisha aina gani? Mkuu swali, kwa sababu hiyo nini sisi ni kufunika ijayo. Hivyo kuunganisha aina ni moja aina hiyo kazi tofauti sana kutoka aina nyingine. Kama wewe guys unaweza see-- Daudi kufanya hivyo demo ambako alikuwa yote ya baridi noises ya kuona jinsi kuunganisha aina mbio, kama, kubwa kasi zaidi kuliko nyingine aina mbili? SAWA. Hivyo hiyo ni kwa sababu kuunganisha aina ya zana kwamba mgawanyiko na kushinda dhana kwamba tumekuwa kuongelea mengi katika hotuba. Katika kwamba maana ya kwamba sisi kama kufanya kazi nadhifu, si vigumu, wakati wewe kugawanya na kushinda matatizo, na kuvunja yao chini, na kisha kuziweka pamoja, mambo mema daima kutokea. Hivyo njia kwamba kuunganisha aina kimsingi kazi ni kwamba mgawanyiko zisizochambuliwa safu katika nusu. Na kisha ni got nusu mbili za arrays. Na ni haki wale aina nusu mbili. Ni kuvaa tu kugawa katika nusu, katika nusu, katika nusu mpaka kila kitu ni yamepangwa na kisha recursively kuiweka wote kwa pamoja. Hivyo hiyo ni kweli abstract. Hivyo hii ni kidogo tu ya pseudocode. Je, hiyo mantiki katika njia ni mbio? Basi hebu tu kusema una safu ya vipengele n, haki? Kama n ni chini ya 2, unaweza kurudi. Kwa sababu unajua kwamba kama kuna jambo moja tu, ni lazima kutatuliwa. Kingine chochote, wewe kutatua nusu kushoto, na kisha kutatua nusu ya haki, na kisha kuunganisha. Hivyo wakati kwamba inaonekana kweli ni rahisi, katika hali halisi, kufikiri kuhusu ni aina ya magumu. Kwa sababu wewe ni kama, vizuri, hiyo ni aina ya mbio juu ya yenyewe. Sawa? Ni mbio juu ya yenyewe. Hivyo kwa maana kwamba, Daudi kuguswa juu ya kujirudia katika darasa. Na hiyo ndiyo dhana tutaweza majadiliano juu zaidi. Ni kwamba hii, mistari hizi mbili hapa, kwa kweli ni tu mpango kuwaambia ni kukimbia yenyewe na pembejeo mbalimbali. Hivyo badala ya kukimbia yenyewe na ukamilifu wa mambo n, unaweza kuvunja chini katika nusu kushoto na nusu haki na kisha kukimbia tena. Na kisha tutaangalia ni kuibua, kwa sababu mimi nina mwanafunzi Visual. Ni kazi bora kwa ajili yangu. Hivyo tutaangalia mfano Visual hapa. Hebu sema tuna safu, sita vipengele, 3, 5, 2, 6, 4, 1, si yamepangwa. Haki wote, kuna mengi kwenye ukurasa huu. Hivyo kama wewe guys unaweza kuangalia Hatua ya kwanza hapa, 3, 5, 2, 6, 4, 1, unaweza kupasuliwa katika nusu. Una 3, 5, 2, 6, 4, 1. Unajua kwamba hawa aren't-- wewe sijui kama wao ni yamepangwa au la, hivyo kuweka kuvunja yao chini, katika nusu, katika nusu, katika nusu, mpaka hatimaye, wewe tu na kipengele moja. Na kipengele moja daima ni vyema, sawa? Hivyo tunajua kwamba 3, 5, 2, 4, 6, 1, kwa wenyewe, ni vyema. Na sasa tunaweza kuziweka nyuma pamoja. Hivyo tunajua 3, 5. Sisi kuweka wale pamoja. Tunajua kwamba Iliyopangwa. Ya 2 bado yapo. Tunaweza kuweka 4 na 6 pamoja. Tunajua kwamba hiyo ni vyema, hivyo sisi kuweka kwamba pamoja. Na 1 ni huko. Na kisha tu kuangalia nusu hizi mbili hapa hapa. Una 3, 5, 2, 2, 3, 5. Unaweza tu kulinganisha mwanzo wa kila kitu. Kwa sababu unajua kwamba hii ni Iliyopangwa na unajua kwamba hiyo ni vyema. Hivyo basi huna hata kuwa na kulinganisha 5, wewe tu kulinganisha 3. Na 2 ni chini ya 3, hivyo unajua 2 lazima uende katika mwisho. Same kitu zaidi ya hapo. 1 lazima uende hapa. Na kisha wakati wewe kwenda kuweka wale maadili mbili kwa pamoja, unajua kwamba hii ni yamepangwa na unajua kwamba kwamba ni yamepangwa. Hivyo basi 1 na 2, 1 ni chini ya 2. Hiyo atakwambia kwamba 1 anatakiwa kwenda juu ya mwishoni mwa hii bila hata kuangalia 3 au 5. Na kisha 4, unaweza tu kuangalia, unaendelea haki katika hapa. Huwezi kuwa na kuangalia 5. Same kitu na 6. Unajua kwamba 6-- tu haina haja ya kuwa inaonekana. Na hivyo kwa njia hiyo, uko tu kuokoa mwenyewe mengi ya hatua wakati wewe ni kulinganisha. Huwezi kuwa na kulinganisha kila kipengele dhidi mambo mengine. Wewe tu kulinganisha dhidi ya wale kwamba unahitaji kulinganisha dhidi ya. Hivyo hiyo ni aina ya dhana ya kufikirika. Hakuna wasiwasi kama si kabisa kupiga wewe haki bado. Lakini kwa ujumla, hii ni jinsi aina kuunganisha kazi. Maswali, maswali ya haraka, kabla mimi hoja juu ya? Naam. Watazamaji: Hivyo wewe alisema kwamba kuchukua 1, na kisha 4, na 6 na kuziweka katika. Hivyo si those-- si wewe kuangalia yao kama mambo tofauti, si kwa ujumla? ANDI PENG: Naam. Hivyo nini kinatokea ni kwamba kimsingi ni kujenga bidhaa mpya safu. Hivyo, unajua kwamba, hapa, nina arrays wawili wa ukubwa 3, sawa? Hivyo, unajua kwamba safu yangu Iliyopangwa anahitaji kuwa na mambo sita. Hivyo tu kujenga Kiasi mpya wa kumbukumbu. Hivyo wewe ni aina ya kama kuwa fujo ya kumbukumbu, lakini hiyo haina jambo kwa sababu ni ndogo sana. Hivyo ukiangalia 1 na ukiangalia 2. Na unajua kwamba 1 ni chini ya 2. Hivyo, unajua kwamba unapaswa kwenda katika 1 mwanzo wa wale wote. Huwezi hata haja ya tuangalie 3 na 5. Hivyo unajua 1 unaendelea huko. Basi kimsingi Night mbali 1. Ni, kama, amekufa kwetu. Kisha sisi tu 2, 3, 5, na kisha 4 na 6. Na kisha, unajua kwamba, wewe kulinganisha 4 na 2, loo, 2 aende huko. Hivyo plop 2 chini, kuwakata ni mbali. Hivyo basi wewe tu na 3 na 5 katika 4 na 6. Na wewe tu kuendelea ukataji ni mbali mpaka akawapanga. Watazamaji: Hivyo wewe tu daima kulinganisha [inaudible]? ANDI PENG: Hasa. Hivyo kwa maana kwamba, wewe ni kulinganisha tu, kimsingi, namba moja dhidi namba nyingine. Na kwa sababu unajua kwamba ni vyema, wewe hawana kuangalia njia wote wa idadi. Wewe tu na kuangalia moja ya kwanza. Na kisha unaweza tu plop yao chini, kwa sababu unajua wao ni ambapo wao wanahitaji mali. Naam. Nzuri swali. Na kisha kama mmoja wenu ni kidogo kabambe, kujisikia huru na kuangalia kanuni hii. Hii ni kweli utekelezaji wa kimwili jinsi tunataka kuandika kuunganisha aina. Na unaweza kuona, ni mfupi sana. Lakini mawazo nyuma ni ni pretty ngumu. Hivyo kama wewe kujisikia kama kuchora hii nje katika kazi yako ya nyumbani usiku wa leo, kujisikia huru na. SAWA. Basi Daudi pia wakaenda upande wa pili huu katika hotuba. Je, ni kesi bora runtimes, kesi runtimes mbaya, na runtimes inatarajiwa ya kuunganisha aina? Sekunde kadhaa kufikiri. Hii ni vigumu, lakini aina ya Intuitive kama wewe kufikiri juu yake. Sawa. Watazamaji: Je, hali mbaya n logi n? ANDI PENG: Hasa. Na kwa nini ni n logi n. Watazamaji: Je, si ni sababu inakuwa exponentially kasi, hivyo ni kama kazi ya kwamba badala ya tu tu kuwa n mraba au kitu? ANDI PENG: Hasa. Hivyo sababu Runtime juu ya hii ni n logi n ni because-- wewe ni nini kufanya katika hatua zote hizi? Wewe ni tu ukataji katika nusu, sawa? Na hivyo wakati sisi ni kufanya kuingia, wote ni kufanya ni kugawa tatizo katika nusu, katika nusu, katika nusu, katika nusu zaidi. Na kwa maana hiyo, unaweza aina ya kuondoa mfano linear kwamba sisi tumekuwa kutumia. Kwa sababu wakati wewe kuwakata mambo katika nusu, ni gogo. Hiyo tu hisabati njia ya anayewakilisha hilo. Na kisha hatimaye, mwishoni, wewe ni maamuzi tu moja kupita jana kupitia kuweka wote ili, haki? Na hivyo kama wewe tu na kuangalia jambo moja, kwamba ni n. Na hivyo wewe ni aina ya kuzidisha pamoja mawili. Hivyo ni kama nimepata kuwa mwisho kuangalia kwa n chini hapa na logi ya n hapa. Na kama wewe kuzidisha yao, hiyo ni n logi n. Na hivyo kesi bora na mbaya zaidi kesi na inatarajiwa wote ni n logi n. Ni pia kama aina nyingine. Ni kama uteuzi aina kwa maana kwamba Haijalishi nini yako orodha ni, ni kwenda tu kufanya kitu kimoja kila wakati. SAWA. Hivyo kama wewe guys unaweza kuona, hata kama aina yake kuwa tumeenda through-- n mraba, siyo ufanisi sana. Na hata hii n n gogo ni si bora zaidi. Kama nyie ni wadadisi, kuna taratibu aina kwamba ni hivyo ufanisi kwamba wao ni karibu kimsingi gorofa katika Runtime. Nimepata baadhi logi n ya. Nimepata baadhi gogo logi n ya. Sisi wala kugusa juu yao katika darasa hili hivi sasa. Lakini kama nyie ni wadadisi, kujisikia huru na google, nini ufanisi zaidi kuchagua taratibu. Sijui, kuna baadhi ya wale kweli funny, like-- kuna baadhi kweli funny wale ambao watu kufanya. Na wewe ajabu jinsi milele mawazo ya kwamba. Hivyo google, kama una baadhi ya vipuri muda, juu ya nini ni baadhi ya njia funny kwamba people-- kama vile ufanisi watu ways-- wameweza kutekeleza aina. SAWA. Na hapa ni tu sehemu kidogo chati. Najua nyote, kabla ya kuwa jaribio 0, itakuwa katika chumba yako pengine kujaribu kukariri hiyo. Hivyo hiyo ni nzuri katika huko kwa nyie. Tu usisahau mantiki hiyo made-- kwa nini wale idadi yalikuwa yanatokea. Kama wewe ni daima waliopotea, tu kufanya uhakika unajua nini aina ni. Na unaweza kukimbia kwa njia ya nao katika akili yako kufikiri kwa nini wale majibu ni majibu hayo. Sawa. Hivyo sisi ni kwenda kutoa hoja juu ya, hatimaye, kwa kutafuta. Kwa sababu kama wale wa wewe ambao kusoma pset, kutafuta pia ni sehemu ya Tatizo wiki hii seti. Itabidi kuulizwa kutekeleza aina mbili za upekuzi. Moja ni kutafuta linear na moja ni la mapacha. Hivyo tafuta linear ni haki rahisi. Wewe tu unataka kutafuta kipengele ya orodha ya kuona kama wewe kupata hiyo. Wewe tu na iterate kupitia. Na kama ni sawa na kitu, unaweza tu kurudi, sawa? Lakini moja ambayo tuko wengi nia ya kuzungumza juu ya ni kutafuta binary, haki, ambayo ni kugawanya na kushinda utaratibu ambao Daudi alikuwa wakiandamana katika hotuba. Kumbuka kitabu cha simu mfano kwamba yeye anaendelea kulea, mtu yeyote kwamba yeye aina ya akihangaika kidogo juu ya mwaka uliopita, ambapo kugawanya tatizo katika nusu, katika nusu, katika nusu, tena na tena, mpaka kupata nini wewe kuangalia kwa? Na nimepata Runtime ya kuwa vilevile. Na unaweza kuona, ni kwa kiasi kikubwa ufanisi zaidi kuliko aina nyingine yoyote ya utafutaji. Hivyo njia kwamba tunataka kwenda juu utekelezaji wa tafuta binary ni, kama tulikuwa na safu, ripoti 0-6, mambo saba, tunaweza kuangalia katikati, right-- pole, ikiwa swali letu first-- kama tunataka kuuliza swali la, je safu vyenye kipengele cha 7, ni wazi, kuwa binadamu, na kuwa na kama safu ndogo, ni rahisi kwa sisi kusema ndiyo. Lakini njia ya kutekeleza mapacha search itakuwa kuangalia katikati. Tunajua kwamba ripoti ya 3 ni katikati, kwa sababu sisi kujua kuna mambo saba. Nini 7 kugawanywa na 2? Unaweza Night mbali kwamba ziada 1. Nimepata 3 katikati. Hivyo ni safu ya 3 sawa na 7? Sio, sawa? Lakini tunaweza kufanya michache ya hundi. Ni safu ya 3 chini ya 7 au ni safu ya 3 kubwa zaidi kuliko 7? Tunajua kwamba ni chini ya 7. Hivyo tunajua kwamba, loo, ni lazima kuwa katika nusu kushoto. Tunajua kwamba ni lazima katika nusu haki, sawa? Ili tuweze tu Night mbali nusu safu. Hatuwezi hata kuwa na kuangalia ni tena. Kwa sababu tunajua kwamba nusu ya problem-- yetu Tunajua kwamba jibu ni katika nusu haki ya tatizo letu. Hivyo sisi tu kuangalia kwamba sasa. Hivyo sasa sisi kuangalia katikati ya nini kushoto. Hiyo ripoti 5. Sisi kufanya kuangalia huo tena na tunaona kwamba ni ndogo. Hivyo sisi kuangalia kwa upande wa kushoto wa jambo hilo. Na kisha tunaona kuangalia kwamba. Ni safu thamani katika ripoti 4 sawa na 7? Ni. Ili tuweze kurudi kweli, kwa sababu tulikuta thamani katika orodha yetu. Je, njia nilikwenda kupitia kwamba mantiki watu wote? SAWA. Mimi nitakupa guys labda, kama, tatu, dakika nne kufikiri jinsi ya pseudocode hii katika. Hivyo kufikiria mimi aliuliza wewe kuandika kazi kuitwa search () kwamba alirudi thamani, thamani Boolean, hiyo ilikuwa kweli au false-- kama, kweli kama wewe kupatikana thamani, uongo kama wewe hakufanya hivyo. Na kisha ungekuwa kupita katika thamani wewe walikuwa wanatafuta katika maadili, ambayo ni array-- loo, mimi dhahiri kuweka kuwa katika mahali sahihi. SAWA. Anyways, kwamba wanapaswa kuwa na Imekuwa na haki ya maadili. Na kisha int n ni idadi ya vipengele katika safu hiyo. Jinsi gani unaweza kwenda kuhusu kujaribu kwa pseudocode kwamba tatizo katika? Mimi nitakupa guys kama dakika tatu kwa kufanya hivyo. Hapana, nadhani kuna only-- yeah, kuna moja haki hapa. Watazamaji: Je, mimi? ANDI PENG: Yeah, I got wewe. Ni kwamba kufanya kazi? OK, baridi. SAWA. Guys wote haki, tuko kwenda kwa nguvu dhidi yake katika. SAWA. Hivyo kudhani sisi tumepewa hii nzuri safu kidogo na N maadili ndani yake. Sikuwa kuteka mistari. Lakini jinsi gani sisi kwenda juu kujaribu kuandika hii? Je, mtu yeyote wanataka nipe mstari wa kwanza? Kama unataka nipe mstari wa kwanza wa pseudocode hii. Watazamaji: [inaudible] Watazamaji: Wewe d wanataka iterate through-- Watazamaji: Mwingine tu kwa kitanzi? Watazamaji: --for. ANDI PENG: Hivyo hii moja kidogo suala gumu. Fikiria about-- unataka kuweka mbio kitanzi hii tena na tena mpaka lini? Watazamaji: Hadi [inaudible] thamani ni sawa na thamani hiyo. ANDI PENG: Hasa. Hivyo unaweza kweli write-- tu tunaweza hata kurahisisha zaidi. Tunaweza tu kufanya kitanzi wakati, sawa? Hivyo unaweza tu loop-- Tunajua kwamba ni wakati. Lakini kwa sasa hivi, mimi nina kwenda kusema "kitanzi" - kupitia nini? Kitanzi until-- nini kuishia hali yetu? Nadhani walisikia maneno hayo. Mimi kusikia mtu kusema hayo. Watazamaji: Maadili sawa na katikati. ANDI PENG: Sema tena. Watazamaji: Au, mpaka thamani wewe ni kutafuta kwa ni sawa na thamani ya kati. ANDI PENG: Je, kama siyo katika huko? Nini kama wewe ni kutafuta thamani kwa kweli si katika safu hii? Watazamaji: kurudi 1. ANDI PENG: Lakini je, tunataka kitanzi mpaka kama tuna hali? Naam. Watazamaji: Hadi kuna thamani moja tu? ANDI PENG: Unaweza kitanzi until-- ili kujua kwamba wewe ni kwenda na thamani max, sawa? Na unajua kwamba wewe ni kwenda kuwa na dk thamani, sawa? Kwa sababu pia, hiyo ni kitu I forgot kusema hapo awali, kuwa kitu ambacho ni muhimu kuhusu tafuta binary ni kwamba safu yako tayari Iliyopangwa. Kwa sababu hakuna njia ya kufanya hii kama uko maadili tu bila mpangilio. Huwezi kujua kama mtu ni kubwa kuliko mengine, haki? Hivyo, unajua kwamba max yako na mins yako ni hapa, sawa? Kama ni kwenda kuwa kurekebisha max yako katika dakika yako na mid-- hebu tu kudhani yako Katikati thamani ya here-- haki wewe ni kwenda kimsingi kitanzi mpaka kiwango cha chini yako ni karibu sawa na max yako, haki, au kama max yako sio sawa na dk yako. Sawa? Kwa sababu wakati kinachotokea, unajua kwamba umefanya hatimaye kugonga thamani sawa. Kwa hiyo unataka kitanzi mpaka dk yako ni chini ya au sawa to-- oops, si chini ya au sawa na, njia nyingine around-- max ni. Je, hiyo mantiki? Mimi alichukua inajaribu wachache kupata haki hiyo. Lakini kitanzi mpaka max thamani yako kimsingi ni karibu chini kuliko au sawa na kiwango cha chini yako, sawa? Hapo ndipo unajua kwamba umefanya converged. Watazamaji: Wakati ingekuwa upeo yako thamani kuwa chini ya kiwango cha chini? ANDI PENG: Mkizishika kurekebisha hayo, ambayo ni nini sisi ni kwenda kuwa kufanya katika hili. Je, hiyo mantiki? Kiwango cha chini na max ni baadhi tu ya integers kwamba sisi ni pengine atataka kuunda kuweka wimbo wa ambapo sisi ni kuangalia. Kwa sababu safu ipo bila kujali nini sisi ni kufanya. Kama, sisi siyo kweli kimwili chopping off safu, sawa? Sisi ni kurekebisha tu ambapo sisi ni kuangalia. Je, hiyo mantiki? Watazamaji: Naam. ANDI PENG: Sawa. Hivyo kama hiyo ni sharti kwa kitanzi yetu, je, tunataka ndani ya kitanzi hii? Je, ni sisi kwenda kuwa kutaka kufanya? Hivyo sasa hivi, sisi tumepewa max na min, haki, pengine umba hapa mahali fulani. Tunakwenda pengine wanataka kupata katikati, sawa? Je ni vipi tuna kwenda kuwa uwezo wa kupata katikati? Nini mathematical-- Watazamaji: Max pamoja na dk kugawanywa na 2. ANDI PENG: Hasa. Je, hiyo mantiki? Na je, nyie kuona kwa nini sisi hakuwa tu use-- kwa nini sisi alifanya hivyo badala ya kufanya tu n kugawanywa na 2? Ni kwa sababu n ni thamani ambayo inaenda kukaa sawa. Sawa? Lakini kama sisi kurekebisha kiwango cha chini yetu na maadili ya kiwango cha juu, wao ni kwenda na mabadiliko. Na matokeo yake, katikati yetu ni kwenda na mabadiliko pia. Hivyo ndiyo sababu tunataka kufanya haki hii hapa. SAWA. Na kisha, kwa kuwa sasa tumekuwa kupatikana our-- yeah. Watazamaji: Tu question-- haraka unaposema dk na max, ni sisi kuchukua kwamba ni tayari Iliyopangwa? ANDI PENG: Yeah, hiyo ni kweli sharti kwa ajili ya kutafuta binary, kwamba una kujua ni yamepangwa. Ambayo ni kwa nini aina, wewe kuandika katika yako tatizo kuweka mbele utafutaji wako mapacha. SAWA. Hivyo sasa kwamba sisi kujua wapi midpoint yetu ni, je, unataka kufanya hapa? Watazamaji: Tunataka kulinganisha kwamba kwa mtu mwingine. ANDI PENG: Hasa. Hivyo wewe ni kwenda kulinganisha Katikati ya thamani, sawa? Na nini kwamba kuwaambia yetu wakati sisi kulinganisha? Je, tunataka kufanya baadaye? Watazamaji: Kama thamani ni kubwa kuliko katikati, tunataka ukate. ANDI PENG: Hasa. Hivyo kama thamani ni kubwa kuliko katikati, tuko atataka mabadiliko hayo kiwango cha chini na maxes, sawa? Je, tunataka mabadiliko? Hivyo, ikiwa tunajua thamani ya kitu mahali fulani humu, je wewe sisi kubadilika? Tunataka mabadiliko yetu kiwango cha chini kuwa katikati, sawa? Na kisha mwingine, ikiwa ni katika hii nusu, je tunataka mabadiliko? Watazamaji: upeo wako. ANDI PENG: Naam. Na kisha utaenda tu kuweka looping, sawa? Kwa sababu sasa, baada ya iteration moja kupitia, nimepata max hapa. Na kisha unaweza recalculate katikati. Na kisha unaweza kulinganisha. Na wewe ni kwenda kuendelea mpaka dakika na maxes kuwa kimsingi converged. Na kwamba wakati unajua kwamba umefanya kugonga mwisho wake. Na ama Nimepata ni au una si katika hatua hiyo. Je, hii maana kufanya kila mtu? SAWA. Hii ni pretty muhimu, kwa sababu itabidi kuandika hii katika kanuni yako usiku wa leo. Lakini wewe guys kuwa nzuri hisia ya kile unapaswa kufanya, ambayo ni nzuri. SAWA. Hivyo sisi tumepewa kuhusu saba Dakika kushoto sehemu. Hivyo sisi ni kwenda kuzungumza kuhusu pset hii kwamba tutaweza kuwa kufanya. Hivyo pset imegawanywa katika sehemu mbili. Nusu ya kwanza inahusisha utekelezaji wa kupata ambao kuandika tafuta linear, a tafuta binary, na algorithm kuchagua. Hivyo hii ni mara ya kwanza wakati katika pset ambapo tutaweza kuwa kutoa nyie kile kinachoitwa usambazaji kificho, ambayo ni kanuni kwamba tuna kabla ya kuandikwa, lakini tu kushoto baadhi ya vipande mbali kwa wewe kumaliza kuandika. Hivyo nyie, wakati ukiangalia hii kanuni, unaweza kupata kweli hofu. Kama wewe ni tu kama, ahh, mimi hawajui nini kwamba anafanya, Sijui, kama, ambayo inaonekana ngumu, ahh, kupumzika. Ni sawa. Kusoma spec. Spec kueleza kwa wewe hasa nini yote ya programu hizi ni kufanya. Kwa mfano, generate.c ni mpango kwamba atakuja na pset yako. Wewe si kweli kuwa na kugusa, lakini unapaswa kuelewa nini ni kufanya. Na generate.c, kila ni kufanya ni ama kuzalisha idadi random au unaweza kuwapa mbegu, kama prearranged idadi hiyo inachukua, na inazalisha idadi zaidi. Hivyo kuna njia mahususi kwa kutekeleza generate.c ambao unaweza tu kufanya rundo la idadi kwa wewe mtihani mbinu yako mengine juu ya. Hivyo kama alitaka, kwa mfano, mtihani kupata yako, wewe unataka kukimbia generate.c, kuzalisha rundo la idadi, na kisha kukimbia wasaidizi wako kazi. Wasaidizi wako kazi ni mahali ambapo wewe ni kweli kimwili kuandika kanuni. Na kufikiria wasaidizi kama jalada la maktaba wewe ni kuandika kwamba kupata ni wito. Na hivyo ndani ya helpers.c, utasikia kufanya kutafuta na kuchagua. Na kisha wewe ni kwenda kimsingi tu kuweka wote pamoja. Spec atakuambia jinsi ya kuweka kwamba katika mstari amri. Na wewe utakuwa na uwezo wa kupima kama au si aina yako na utafutaji ni kazi. Baridi. Kuna mtu yeyote tayari kuanza na matatizo yaliyojitokeza au maswali wao wana haki sasa na hili? SAWA. Watazamaji: Ngoja. Nina swali. ANDI PENG: Naam. Watazamaji: Hivyo mimi ilianza kufanya tafuta linear katika helpers.c Jambo hilo lilikuwa haifanyi kazi. Lakini kisha baadaye, nimeona sisi tu na kufuta na kufanya search binary. Hivyo jambo gani kama hana kazi? ANDI PENG: muda Jibu ni hapana. Lakini kwa kuwa tuko not-- Watazamaji: Lakini hakuna mtu kweli kuangalia. ANDI PENG: Tuko kamwe kwenda kuona kwamba. Lakini pengine wanataka kufanya uhakika utafutaji wako ni kazi. Kwa sababu kama linear yako search hana kazi, basi nafasi ni mapacha yako search si kwenda kufanya kazi pamoja. Kwa sababu una sawa mantiki Katika barua hizo mbili. Na hakuna, haina kweli jambo. Hivyo wale tu utasikia kugeuka katika ni aina na tafuta binary. Naam. Na pia, mengi ya watoto walikuwa kujaribu kukusanya helpers.c. Wewe si kweli kuruhusiwa kufanya hivyo, kwa sababu helpers.c hana kazi kuu. Na hivyo unapaswa tu kuwa kweli kuandaa kuzalisha na kupata, kwa sababu kupata wito helpers.c na kazi ndani yake. Hivyo kwamba inafanya debugging maumivu katika kitako. Lakini hiyo ni nini sisi kufanya. Watazamaji: Wewe tu kufanya yote, sawa? ANDI PENG: Unaweza tu kufanya yote pia, yeah. SAWA. Hivyo hiyo ni katika suala la nini pset ni kuuliza wewe wote kufanya. Kama una maswali yoyote, jisikie huru kuuliza mimi baada ya sehemu. Nitakuwa hapa kwa, kama, dakika 20. Na ndiyo, pset ya kweli siyo mbaya. Nyie lazima OK. Haya, tu kufuata miongozo. Aina ya kuwa na hisia ya, kifikra, nini lazima kuwa kinachotokea na wewe utakuwa na faini. Je, si kuwa pia hofu. Kuna mengi ya kificho tayari imeandikwa huko. Je, si kuwa pia hofu kama huna kuelewa nini yote ya kwamba maana. Kama ni mengi, ni kabisa faini. Na kuja saa za ofisi. Tutaweza kukusaidia kuangalia. Watazamaji: Kwa ziada kazi, je, sisi kuangalia wale up? ANDI PENG: Yeah, wale walio katika kanuni. Katika mchezo wa 15, nusu ya ni tayari imeandikwa kwa ajili yenu. Hivyo kazi hizo ni Tayari katika kanuni. Yep. Sawa. Naam, bora ya bahati. Ni siku disgusting. Hivyo hopefully nyie sijisikii pia mbaya kuhusu kukaa ndani na coding.