[Powered by Google Translate] [Sehemu ya 3 - Zaidi Starehe]
[Rob Bowden - Chuo Kikuu cha Harvard]
>> [Hii ni CS50. - CS50.TV]
>> Hivyo swali la kwanza ni strangely kuchukuliwa.
GDB inakuwezesha "Debug" mpango, lakini, zaidi hasa, ni nini basi wewe kufanya?
Mimi itabidi kujibu kwamba mmoja, na mimi sijui nini hasa ilivyotarajiwa,
hivyo mimi nina guessing ni kitu pamoja na mistari ya inakuwezesha hatua kwa hatua
kutembea kwa njia ya mpango, kiutendaji na hivyo, mabadiliko ya vigezo, kufanya mambo haya yote -
kimsingi kabisa kudhibiti utekelezaji wa mpango
na kukagua sehemu yoyote aliyopewa ya utekelezaji wa mpango.
Hivyo wale makala basi wewe Debug mambo.
Sawa.
Kwa nini binary tafuta zinahitaji kwamba safu sorted?
Nani anataka kujibu?
[Mwanafunzi] Kwa sababu haifanyi kazi kama si Iliyopangwa. >> Yeah. [Kicheko]
Kama siyo sorted, basi ni vigumu kwa kupasuliwa katika nusu
na najua kuwa kila kitu kwa upande wa kushoto ni kidogo na kila kitu kwa haki
ni kubwa zaidi kuliko thamani ya kati.
Hivyo mahitaji sorted.
Sawa.
Kwa nini ni Bubble aina katika O ya n squared?
Je, mtu yeyote kwanza nataka kutoa haraka sana wa ngazi za juu picha ya nini Bubble aina ni?
[Mwanafunzi] Wewe kimsingi kupitia kila kipengele na wewe kuangalia kwanza vipengele chache.
Kama uko nje ya wapi byta yao, kisha wewe kuangalia ijayo mambo machache na kadhalika.
Wakati kufikia mwisho, basi, unajua kwamba kipengele kubwa ni kuwekwa katika mwisho,
hivyo kupuuza kwamba moja kisha wewe kuendelea kwenda kupitia,
na kila wakati wewe na kuangalia moja chini ya kipengele mpaka kufanya mabadiliko yoyote. >> Yeah.
Ni wito Bubble aina kwa sababu kama wewe flip safu upande wake hivyo ni juu na chini, wima,
kisha maadili kubwa itakuwa kuzama mpaka chini na maadili ndogo mapenzi Bubble hadi juu.
Hiyo ni jinsi got jina lake.
Na yeah, wewe tu kwenda kupitia.
Wewe kuendelea kwenda kupitia safu, swapping thamani kubwa
kupata maadili kubwa hadi chini.
>> Kwa nini ni O ya n squared?
Kwanza, haina mtu yeyote unataka kusema nini ni O ya n squared?
[Mwanafunzi] Kwa sababu kwa ajili ya kuendesha kila unaendelea mara n.
Unaweza tu kuwa na uhakika kwamba umechukua kipengele kubwa njia yote chini,
basi una kwamba kurudia kwa kama mambo mengi. >> Yeah.
Hivyo kukumbuka kile kubwa O ina maana na kile kubwa Omega njia.
O kubwa ni kama juu amefungwa juu ya jinsi polepole inaweza kweli kukimbia.
Hivyo kwa kusema ni O ya n squared, si O ya n au pengine itakuwa ni kuwa na uwezo wa kuendesha
katika wakati linear, lakini ni O ya n cubed
sababu ni imepakana na O ya n cubed.
Kama ni imepakana na O ya n squared, basi ni imepakana na pia n cubed.
Hivyo ni n squared, na katika kesi kabisa mbaya haiwezi kufanya vizuri zaidi kuliko n squared,
ambayo ni kwa nini ni O ya n squared.
Hivyo kuona math kidogo katika jinsi inakuja nje kuwa n squared,
kama tuna mambo matano katika orodha yetu, mara ya kwanza jinsi wengi swaps inaweza sisi uwezekano haja ya kufanya
ili kupata hii? Hebu kweli tu -
Wangapi swaps ni sisi kwenda na kufanya katika muda kwanza wa aina Bubble kupitia safu?
[Mwanafunzi] n - 1. >> Yeah.
>> Kama kuna vipengele 5, sisi ni kwenda haja ya kufanya n - 1.
Kisha juu ya moja ya pili jinsi wengi swaps ni sisi kwenda na kufanya?
[Mwanafunzi] n - 2. >> Yeah.
Na tatu ni kwenda kuwa n - 3, na kisha kwa urahisi nitaandika mawili ya mwisho
kama basi sisi ni kwenda haja ya kufanya swaps 2 na 1 byta.
Nadhani moja ya mwisho wanaweza au si kweli haja ya kutokea.
Je, ni byta? Mimi sijui.
Basi hizi ni jumla ya kiasi cha swaps au kulinganisha angalau una kufanya.
Hata kama huna wabadilishane, bado wanahitaji kulinganisha maadili.
Hivyo kuna n - kulinganisha 1 katika muda kwanza kupitia safu.
Kama upya mambo haya, hebu kweli kufanya ni mambo sita ili mambo stack up nicely,
na kisha mimi itabidi kufanya 3, 2, 1.
Hivyo tu rearranging sums hizi, tunataka kuona jinsi wengi kulinganisha sisi kufanya
katika algorithm nzima.
Hivyo kama sisi kuleta guys haya hapa chini,
basi bado tuko tu summing kulinganisha hata hivyo wengi kulikuwa.
Lakini kama sisi sum hizi na sisi sum hizi na sisi sum hizi,
bado ni tatizo moja. Sisi tu jumla ya makundi hayo fulani.
>> Hivyo sasa sisi ni summing 3 n wa. Siyo tu 3 n wa.
Ni daima itakuwa n / n 2 wa.
Hivyo hapa sisi kutokea kwa kuwa 6.
Kama tulikuwa na mambo 10, basi tunaweza kufanya hii kambi kwa jozi 5 tofauti ya mambo
na kuishia na n + n + n + n + n.
Basi, wewe ni daima kwenda kupata n / n 2, na hivyo hii tutaweza hata nukta hivyo nje n squared / 2.
Na hivyo hata kama ni sababu ya nusu, ambayo hufanyika kuja katika
sababu ya ukweli kwamba kwa njia ya kila iteration juu ya safu sisi kulinganisha 1 chini
hivyo kwamba ni jinsi gani sisi kupata zaidi ya 2, lakini bado ni n squared.
Sisi hawajali kuhusu sababu mara kwa mara ya nusu.
Hivyo mengi ya mambo makubwa O kama hii hutegemea aina tu ya kufanya aina hii ya math,
kufanya hesabu arithmetic na stuff kijiometri mfululizo,
lakini wengi wao katika kozi hii ni pretty moja kwa moja.
Sawa.
Kwa nini ni insertion aina katika Omega ya n? Nini maana ya omega?
[Wanafunzi wawili akizungumza katika moja - unintelligible] >> Yeah.
Omega unaweza kufikiria kama chini amefungwa.
>> Hivyo hakuna jambo jinsi ufanisi insertion yako aina algorithm ni,
bila kujali orodha hiyo kupita katika, daima ana kwa kulinganisha vitu angalau n
au ina iterate juu ya mambo n.
Kwa nini?
[Mwanafunzi] Kwa sababu kama orodha tayari Iliyopangwa, kisha kupitia iteration kwanza
unaweza tu kuhakikisha kwamba kipengele sana kwanza ni mdogo,
na iteration pili unaweza tu kuhakikisha mbili kwanza ni
kwa sababu hamjui kwamba mapumziko ya orodha ni Iliyopangwa. >> Yeah.
Kama kupita katika orodha kabisa Iliyopangwa, angalau sana una kwenda juu ya mambo yote
kuona kuwa hakuna haja ya kuwa wakiongozwa kuzunguka.
Hivyo kupita juu ya orodha na kusema oh, hii tayari Iliyopangwa,
haiwezekani kwa wewe kujua ni sorted mpaka wewe kuangalia kila kipengele
kuona kwamba wao ni ili Iliyopangwa.
Hivyo chini amefungwa juu ya aina insertion ni Omega ya n.
Nini hali mbaya mbio wakati wa aina kuunganisha,
kesi mbaya kuwa kubwa O tena?
Hivyo katika mazingira ya kesi mbaya, jinsi gani kuunganisha aina kukimbia?
[Mwanafunzi] N logi n. >> Yeah.
kasi ya jumla ya kuchagua algorithms ni n logi n. Huwezi kufanya vizuri zaidi.
>> Kuna matukio maalum, na kama tuna muda leo - lakini sisi pengine won't -
tunaweza kuona kwamba moja inafanya vizuri kuliko n logi n.
Lakini katika kesi ya jumla, unaweza kufanya bora kuliko n logi n.
Na kuunganisha aina hutokea kwa kuwa moja unapaswa kujua kwa kozi hii kwamba ni n logi n.
Na hivyo tutaweza kweli kuwa utekelezaji kwamba leo.
Na hatimaye, katika si zaidi ya tatu sentensi, jinsi gani uteuzi aina ya kazi?
Je, mtu unataka kujibu, na mimi itabidi kuhesabu sentensi yako
kwa sababu kama wewe kwenda juu ya 3 -
Je, mtu yeyote kumbuka uteuzi aina?
Uteuzi aina ni kawaida pretty rahisi kukumbuka tu kutoka jina.
Wewe tu iterate juu ya safu, kupata chochote thamani kubwa ni ndogo au -
chochote ili wewe ni kuchagua in
Basi hebu kusema sisi ni kuchagua kutoka wadogo na wakubwa.
Wewe iterate juu ya safu, kuangalia kwa chochote kipengele cha chini ni,
kuchagua, na kisha wabadilishane tu ni chochote ni katika nafasi ya kwanza.
Na kisha juu ya kupita juu ya safu ya pili, kuangalia kwa kipengele cha chini tena,
kuchagua, na kisha wabadilishane kwa nini katika nafasi ya pili.
Hivyo sisi ni tu kuokota na kuchagua kima cha chini cha maadili
na kuingiza yao ndani ya safu ya mbele ya mpaka ni Iliyopangwa.
Maswali juu ya hilo?
>> Hizi inevitably itaonekana katika fomu una kujaza wakati wewe ni kuwasilisha pset.
Wale ni kimsingi majibu hayo.
Sawa, hivyo sasa coding matatizo.
Mimi tayari kutumwa nje juu ya barua pepe - Je mtu si kupata kwamba barua pepe? Sawa.
Mimi tayari kutumwa nje juu ya barua pepe ya nafasi ya kuwa sisi ni kwenda kuwa na kutumia,
na kama wewe bonyeza juu ya jina langu - hivyo nadhani nina kwenda kuwa chini
kwa sababu ya r nyuma - lakini kama wewe bonyeza juu ya jina langu utaona marekebisho 2.
Marekebisho 1 inaenda mimi tayari kunakiliwa na pasted code katika Spaces
kwa kitu tafuta wewe ni kwenda na kutekeleza.
Na Revision 2 itakuwa jambo aina hiyo sisi kutekeleza baada ya hapo.
Hivyo unaweza bonyeza Revision yangu 1 na kazi kutoka huko.
Na sasa tunataka kutekeleza binary tafuta.
>> Je, mtu yeyote unataka kutoa tu pseudocode ngazi ya juu maelezo
wa nini tunakwenda kufanya kwa ajili ya kutafuta? Yeah.
[Mwanafunzi] Wewe tu kuchukua katikati ya safu na kuona kama nini wewe kutafuta kwa
ni kidogo kuliko au zaidi ya hapo.
Na kama ni kidogo, unaweza kwenda nusu kwamba chini,
na kama ni zaidi, unaweza kwenda nusu kwamba zaidi na wewe kurudia kwamba mpaka kupata tu jambo moja.
[Bowden] Yeah.
Ona kwamba idadi yetu safu tayari Iliyopangwa,
na hivyo ina maana kwamba tunaweza kuchukua faida ya kwamba na sisi inaweza kwanza kuangalia,
sawa, mimi nina kuangalia kwa idadi 50.
Hivyo siwezi kwenda katika katikati.
Kati ni vigumu kufafanua wakati ni idadi hata wa mambo,
lakini hebu sema tu tutaweza daima butu kwa katikati.
Hivyo hapa tuna mambo 8, hivyo katikati itakuwa 16.
Mimi nina kuangalia kwa 50, hivyo 50 ni kubwa kuliko 16.
Hivyo sasa naweza kimsingi kutibu safu yangu kama mambo haya.
Siwezi kutupa kila kitu kutoka 16 juu.
Sasa safu yangu ni ya haki haya mambo 4, na mimi kurudia.
Hivyo basi nataka kupata katikati tena, ambayo ni kwenda kuwa 42.
42 ni chini ya 50, hivyo siwezi kutupa mambo haya mawili.
Hii ni safu yangu iliyobaki.
Mimi naenda kupata katikati tena.
Nadhani 50 alikuwa ni mfano mbaya kwa sababu mimi mara zote kutupa mbali mambo ya kushoto,
lakini kwa kipimo sawa, kama mimi nina kuangalia kwa kitu
na ni chini ya kipengele Mimi sasa kuangalia,
basi mimi nina kwenda kutupa kila kitu kwa haki.
Hivyo sasa sisi haja ya kutekeleza hiyo.
Ona kwamba sisi haja ya kupita katika kawaida.
Tunaweza pia haja ya kawaida kwa bidii-code.
Hivyo kama sisi kujikwamua kwamba # define -
Sawa.
Ninawezaje nicely kufikiri nini ukubwa wa safu namba sasa ni?
>> Wangapi mambo ni katika safu namba?
[Mwanafunzi] Hesabu, mabano,. Urefu?
[Bowden] Hiyo haipo katika C.
Haja urefu..
Arrays hawana mali, hivyo hakuna mali urefu wa arrays
kwamba tu kukupa hata hivyo muda mrefu hutokea kwa kuwa.
[Mwanafunzi] Angalia kiasi gani kumbukumbu ina na kugawanya na kiasi gani - >> Yeah.
Hivyo ni jinsi gani tunaweza kuona ni kiasi gani kumbukumbu ina? >> [Mwanafunzi] Sizeof. >> Yeah, sizeof.
Sizeof ni operator ambayo inaenda kurudi ukubwa wa safu namba.
Na kwamba ni kwenda kuwa hata hivyo wengi integers kuna ukubwa wa mara integer
kuwa kwa kiasi gani kumbukumbu ni kweli kuchukua.
Hivyo kama nataka idadi ya mambo katika safu,
basi mimi nina kwenda kutaka kugawanya na ukubwa wa integer.
Sawa. Hivyo kwamba lets mimi kupita katika ukubwa hapa.
Kwa nini mimi haja ya kupita katika kawaida wakati wote?
Kwa nini siwezi tu kufanya up hapa ukubwa int = sizeof (haystack) / sizeof (int)?
Kwa nini hii si kazi?
[Mwanafunzi] Ni hazibadiliki kimataifa.
[Bowden] haystack ipo na sisi ni kupita kwa idadi kama haystack,
na hii ni aina ya kielelezo cha nini kuja. Yeah.
[Mwanafunzi] haystack ni kumbukumbu ya hivyo, hivyo ingekuwa kurudi jinsi kubwa akimaanisha kuwa ni.
Yeah.
Mimi shaka katika hotuba kwamba ve kuonekana stack bado kweli, haki?
Tumekuwa tu kusema kuhusu hilo.
Hivyo ni stack ambapo wote wa vigezo yako ni kwenda kuhifadhiwa.
>> Yoyote kumbukumbu hiyo zilizotengwa kwa vigezo mitaa ni kwenda katika stack,
na kazi ya kila anapata nafasi yake juu ya stack, stack yake mwenyewe frame ni nini ni wito.
Hivyo kuu ina stack yake frame, na ndani yake ni kwenda zipo hii safu namba,
na ni kwenda kuwa ya kawaida sizeof (idadi).
Ni kwenda na ukubwa wa idadi kugawanywa na ukubwa wa vipengele,
bali wote maisha ndani ya stack frame kuu ya.
Wakati sisi kuwaita tafuta, tafuta anapata stack yake mwenyewe frame,
nafasi yake ya kuhifadhi wote wa vigezo yake ya ndani.
Lakini hoja hizi - hivyo haystack si nakala ya safu hii nzima.
Sisi si kupita katika safu nzima kama nakala ndani ya utafutaji.
Ni tu hupita akimaanisha kwamba safu.
Hivyo tafuta wanaweza kupata namba hizi kwa njia ya kumbukumbu hii.
Ni bado kupata mambo ambayo kuishi ndani ya stack frame kuu ya,
lakini kimsingi, wakati sisi kupata kuyatumia, ambayo inapaswa kuwa hivi karibuni,
hii ni nini kuyatumia ni.
Kuyatumia ni tu marejeo ya mambo, na unaweza kutumia kuyatumia kupata mambo
kwamba ni katika muafaka mambo mengine 'stack.
Hivyo hata kama idadi ni mitaa kuu, bado tunaweza kupata hiyo kupitia pointer hii.
Lakini tangu ni tu pointer na ni tu ya kumbukumbu,
sizeof (haystack) tu anarudi ukubwa wa kumbukumbu yenyewe.
Ni haina kurudi ukubwa wa kitu ni akizungumzia.
Ni haina kurudi ukubwa halisi wa idadi.
Na hivyo hii si kwenda kufanya kazi kama sisi unataka kwa.
>> Maswali juu ya hilo?
Kuyatumia itakuwa wamekwenda kwa undani kwa kiasi kikubwa zaidi gory katika wiki ijayo.
Na hii ni kwa nini mambo mengi ambayo unaweza kuona, vitu zaidi ya utafutaji au mambo aina,
wao uko karibu wote kwenda haja ya kuchukua ukubwa halisi wa safu,
kwa sababu katika C, hatuna wazo nini ukubwa wa safu ni.
Unahitaji manually kupita in
Na huwezi kupita manually katika safu nzima kwa sababu wewe ni tu kupita katika kumbukumbu
na hivyo hawawezi kupata kawaida kutoka kumbukumbu.
Sawa.
Hivyo sasa tunataka kutekeleza yale zilielezwa kabla.
Unaweza kazi kwa dakika,
na huna na wasiwasi kuhusu kupata kila kitu kikamilifu 100% kazi.
Kuandika tu juu pseudocode nusu kwa jinsi gani na unafikiri ni lazima kazi.
Sawa.
Hakuna haja ya kuwa kabisa kufanyika kwa hii bado.
Lakini haina mtu yeyote kujisikia vizuri na kile walichonacho hivyo mbali,
kama kitu tunaweza kufanya kazi kwa pamoja?
Je, mtu yeyote unataka kujitolea? Au mimi Watapiga pick.
Haina kuwa njema na hatua ya kitu lakini tunaweza kurekebisha katika hali ya kufanya kazi.
[Mwanafunzi] Uhakika. >> Sawa.
Hivyo unaweza kujiokoa marekebisho kwa kubonyeza icon kidogo Save.
Wewe ni Ramya, haki? >> [Mwanafunzi] Yeah. >> [Bowden] Sawa.
Hivyo sasa naweza kuona marekebisho yako na kila mtu anaweza kuvuta marekebisho.
Na hapa tuna - Sawa.
Hivyo Ramya akaenda pamoja ufumbuzi kujirudia, ambayo ni dhahiri ufumbuzi halali.
Kuna njia mbili unaweza kufanya tatizo hili.
Unaweza kufanya hivyo aidha iteratively au recursively.
Matatizo zaidi kukutana ambayo yanaweza kufanyika recursively pia inaweza kufanyika iteratively.
Hivyo hapa tumekuwa kufanyika ni recursively.
>> Je, mtu unataka kufafanua nini maana ya kufanya kazi ya kujirudia?
[Mwanafunzi] Wakati una kazi kujiita
na kisha piga yenyewe mpaka hutoka nje na wa kweli na kweli. >> Yeah.
kazi ya kujirudia ni kazi ambayo wito yenyewe.
Kuna tatu kubwa mambo ambayo kazi ya kujirudia lazima.
kwanza ni wazi, ni wito yenyewe.
pili ni kesi ya msingi.
Hivyo katika baadhi ya uhakika kazi inahitaji kuacha wito yenyewe,
na kwamba ni nini kesi ya msingi ni kwa.
Hivyo hapa tunajua kwamba tuache, tunapaswa kutoa up katika search wetu
wakati kuanza sawa mwisho - na tutaweza kwenda juu ya nini maana ya.
Lakini hatimaye, jambo la mwisho kwamba ni muhimu kwa ajili ya kazi ya kujirudia:
kazi lazima kwa namna fulani mbinu kesi ya msingi.
Kama kama wewe si kweli uppdatering chochote wakati kufanya pili ya kujirudia wito,
kama wewe ni literally tu wito kazi tena na hoja hiyo
na hakuna vigezo kimataifa yamebadilika au kitu chochote,
wewe kamwe kufikia kesi ya msingi, katika kesi ambayo hiyo ni mbaya.
Itakuwa recursion usio na kufurika stack.
Lakini hapa tunaona kwamba update kinachotokea kwani sisi ni uppdatering kuanza + mwisho / 2,
sisi ni uppdatering hoja mwisho hapa, sisi ni uppdatering hoja kuanza hapa.
Hivyo katika simu zote kujirudia sisi ni uppdatering kitu. Sawa.
Je, unataka kutembea kwetu kupitia ufumbuzi wako? >> Uhakika.
Mimi nina kutumia SearchHelp ili kila wakati mimi kupiga simu hii kazi
Nina mwanzo wa ambapo mimi nina kuangalia kwa katika safu na mwisho
ya ambapo mimi nina kuangalia safu.
>> Kwa kila hatua ambapo ni kusema ni kipengele katikati, ambayo ni mwanzo wa mwisho + / 2,
ni sawa sawa kwa nini sisi ni kuangalia kwa?
Na kama ni, basi sisi kupatikana, na mimi nadhani kwamba anapata kupita hadi ngazi ya recursion.
Na kama kwamba si kweli, basi sisi kuangalia kama kwamba thamani ya katikati ya safu ni kubwa mno,
katika kesi ambayo sisi kuangalia nusu ya kushoto ya safu kwa kwenda kutoka mwanzo hadi index katikati.
Na vinginevyo sisi kufanya nusu ya mwisho.
[Bowden] Sawa.
Kwamba sauti nzuri.
Okay, kwa hivyo mambo ya wanandoa, na kwa kweli, hii ni kitu sana wa ngazi za juu
kwamba kamwe haja ya kujua kwa ajili ya kozi hii, lakini ni kweli.
Majukumu ya kujirudia, wewe daima kusikia kwamba wao ni mpango mbaya
kwa sababu kama wewe recursively wito mwenyewe mara nyingi sana, unaweza kupata stack kufurika
tangu, kama nilivyosema hapo kabla, kila kazi anapata stack yake mwenyewe frame.
Hivyo kila wito wa kazi ya kujirudia anapata stack yake mwenyewe frame.
Hivyo kama wewe kufanya wito 1000 kujirudia, unaweza kupata muafaka stack 1000,
na haraka wewe kusababisha kuwa wengi mno stack muafaka na mambo kuvunja tu.
Hivyo ndiyo sababu kazi ya kujirudia kwa ujumla mbaya.
Lakini kuna subset nzuri ya utendaji kazi ya kujirudia kuitwa mkia-kujirudia,
na hii hutokea kwa kuwa mfano wa moja ambapo kama mkusanyaji matangazo hii
na ni lazima, Nadhani - katika Clang kama wewe kupita-O2 bendera
basi itakuwa taarifa hii ni mkia kujirudia na kufanya mambo mema.
>> Itakuwa Suza huo stack frame tena na tena kwa kila simu ya kujirudia.
Na hivyo tangu unatumia huo stack frame, huna haja ya kuwa na wasiwasi kuhusu
milele stack ya kufurika, na wakati huo huo, kama wewe alisema kabla,
ambapo mara moja kurudi kweli, basi ina kurudi up yote ya muafaka haya stack
na wito kwa 10 SearchHelp ina kurudi 9, ina kurudi 8.
Hivyo kwamba haina haja ya kutokea wakati kazi ni mkia kujirudia.
Na hivyo hufanya nini hii mkia kazi kujirudia ni taarifa kwamba kwa yoyote wito aliopewa searchHelp
wito kujirudia kwamba ni kufanya ni nini ni kurudi.
Hivyo katika kwanza mwito kwa SearchHelp, sisi aidha mara moja kurudi uongo,
mara moja kurudi kweli, au sisi kufanya wito kujirudia kwa SearchHelp
ambapo nini tuko kurudi ni nini wito kwamba ni kurudi.
Na tunaweza kufanya hili kama sisi alifanya kitu kama int x = SearchHelp, kurudi x * 2,
baadhi tu ya mabadiliko random.
>> Hivyo sasa wito huu kujirudia, hii int x = SearchHelp kujirudia wito,
hakuna tena mkia kujirudia kwa sababu ni kweli gani kuwa kurudi
nyuma sura zilizotangulia stack ili kwamba wito kwa kazi uliopita
wanaweza kufanya kitu kwa thamani ya kurudi.
Hivyo hii si mkia kujirudia, lakini kile tulikuwa kabla ni nicely mkia kujirudia. Yeah.
[Mwanafunzi] Je, si pili kesi ya msingi kuwa checked kwanza
kwa sababu kuna inaweza kuwa hali ambapo wakati kupita hoja
una kuanza = mwisho, lakini ni thamani sindano.
Swali hatuwezi kukimbia katika kesi ambapo mwisho ni thamani sindano
au kuanza = mwisho, ipasavyo, kuanza = mwisho
na wewe si kweli kwamba checked thamani fulani bado,
kisha kuanza + mwisho / 2 ni kwenda tu kuwa thamani sawa.
Lakini tumekuwa tayari kurudi uongo na sisi kamwe kweli checked thamani.
Hivyo kwa uchache sana, katika wito wa kwanza, kama kawaida ni 0, kisha tunataka kurudi uongo.
Lakini kama kawaida ni 1, kisha kuanza si kwenda mwisho sawa,
na tutaweza angalau kuangalia kipengele moja.
Lakini nadhani ni haki katika kwamba tunaweza kuishia katika kesi ambapo kuanza + mwisho / 2,
kuanza kuishia kuwa sawa kama kuanza + mwisho / 2,
lakini sisi kamwe kweli checked kwamba kipengele.
>> Hivyo kama sisi kwanza kuangalia ni kipengele katikati thamani sisi ni kuangalia kwa,
basi tunaweza mara moja kurudi kweli.
Mwingine kama uko sawa, basi hakuna uhakika katika kuendelea
tangu tuko tu kwenda update kwa kesi ambapo sisi ni juu ya safu moja-kipengele.
Kama kwamba kipengele moja si moja sisi ni kuangalia kwa,
basi kila kitu ni makosa. Yeah.
[Mwanafunzi] jambo ni kwamba tangu ukubwa ni kweli kubwa kuliko idadi ya vipengele katika safu,
tayari kuna kukabiliana - >> Hivyo mapenzi kawaida -
[Mwanafunzi] Sema ikiwa safu ilikuwa kawaida 0, kisha SearchHelp kweli itakuwa kuangalia haystack ya 0
juu ya wito wa kwanza.
safu ina ukubwa 0, hivyo ni 0 - >> Yeah.
Kuna kitu kingine kwamba - inaweza kuwa nzuri. Hebu fikiria.
Hivyo kama safu alikuwa vipengele 10 na moja katikati tunakwenda kuangalia ni index 5,
hivyo sisi ni kuangalia 5, na hebu kusema kwamba thamani ni kidogo.
Hivyo sisi ni kutupa kila kitu mbali na kuendelea 5.
Hivyo kuanza + mwisho / 2 ni kwenda kuwa mwisho wetu mpya,
hivyo yeah, ni daima kwenda kukaa zaidi ya mwisho wa safu.
Kama ni kesi kama ilikuwa hata au isiyo ya kawaida, basi tunataka kuangalia, kusema, 4,
lakini bado tuko kutupa mbali -
Hivyo yeah, mwisho ni daima itakuwa ng'ambo ya mwisho halisi wa safu.
Hivyo mambo sisi ni kulenga, mwisho ni daima itakuwa moja baada ya hapo.
Na hivyo kama mwanzo gani milele mwisho sawa, sisi ni katika safu ya ukubwa 0.
>> Kitu nyingine mimi nilikuwa nafikiri ni sisi ni uppdatering kuanza kuwa kuanza + mwisho / 2,
hivyo hii ni kesi ya kwamba mimi nina matatizo na, ambapo kuanza + mwisho / 2
ni kipengele tuko kuangalia.
Hebu sema tulikuwa hii safu 10-kipengele. Chochote.
Hivyo kuanza + mwisho / 2 ni kwenda kuwa kitu kama hii moja,
na kama si kwamba thamani, kusema tunataka update.
thamani ni kubwa zaidi, hivyo tunataka kuangalia hii nusu ya safu.
Hivyo ni jinsi sisi ni uppdatering kuanza, sisi ni uppdatering mwanzo hadi sasa kuwa hii kipengele.
Lakini hii bado wanaweza kazi, au kwa uchache sana, unaweza kufanya kuanza + mwisho / 2 + 1.
[Mwanafunzi] Huna haja ya kuwa na kuanza + mwisho [inaudible] >> Yeah.
Sisi tayari checked hii ya kipengele na kujua si moja sisi ni kuangalia kwa.
Hivyo hatuna haja ya update kuanza kuwa hii kipengele.
Tunaweza tu ruka, na update kuanza kuwa hii kipengele.
Na ni pale milele kesi, hebu sema, kwamba hii ingekuwa mwisho,
hivyo kisha kuanza itakuwa hii, kuanza + mwisho / 2 itakuwa hii,
kuanza + mwisho - Yeah, nadhani unaweza kuishia katika recursion usio.
Hebu sema ni tu safu ya ukubwa 2 au safu ya kawaida ya 1. Nadhani hii kazi.
Hivyo kwa sasa, ni kwamba kipengele kuanza na mwisho ni zaidi ya 1 ni.
Hivyo kipengele kwamba sisi ni kwenda kuangalia ni hii moja,
na kisha wakati sisi update kuanza, sisi ni uppdatering kuanza kuwa 0 + 1/2,
ambayo inaenda kuisha sisi nyuma na kuanza kuwa hii kipengele.
>> Hivyo sisi ni kuangalia kipengele sawa juu na juu tena.
Hivyo hii ni kesi ambapo kila wito kujirudia lazima kweli update kitu.
Hivyo tunahitaji kufanya kuanza + mwisho / 2 + 1, au mwingine kuna kesi
ambapo sisi siyo kweli uppdatering mwanzo.
Kila mtu kuona kwamba?
Sawa.
Je, mtu yeyote kuwa na maswali juu ya ufumbuzi huu au maoni yoyote zaidi?
Sawa. Je, mtu yeyote kuwa iterative ufumbuzi kwamba sisi wote kuangalia?
Je sisi wote kufanya hivyo recursively?
Au pia mimi nadhani kama kufunguliwa kwake, basi unaweza kuwa na overridden moja yako ya zamani.
Je, ni moja kwa moja kuokoa? Mimi si chanya.
Je, mtu yeyote kuwa iterative?
Tunaweza kutembea kwa njia hiyo pamoja kama si.
wazo ni kwenda kuwa sawa.
Iterative ufumbuzi.
Sisi ni kwenda wanataka kimsingi kufanya wazo sawa
ambapo tunataka kuweka wimbo wa mwisho wa safu mpya na mwanzo mpya wa safu
na kufanya hivyo tena na tena.
Na kama nini tuko kuweka wimbo wa kama mwanzo na mwisho milele intersect,
kisha sisi hakuwa wanajikuta na tunaweza kurudi uongo.
Hivyo ni jinsi gani mimi kufanya hivyo? Mtu yeyote kuwa mapendekezo code au kwa ajili yangu ya kuvuta up?
[Mwanafunzi] Je kitanzi wakati. >> Yeah.
Wewe ni kwenda wanataka kufanya kitanzi.
>> Je una code mimi naweza kuvuta, au nini walikuwa wewe kwenda kupendekeza?
[Mwanafunzi] nadhani hivyo. >> Sawa. Hii hufanya mambo rahisi. Nini ilikuwa jina lako?
[Mwanafunzi] Lucas.
Marekebisho 1. Sawa.
Chini ni nini sisi inayoitwa kuanza kabla.
Hadi si kabisa nini sisi inayoitwa mwisho kabla.
Kweli, mwisho ni sasa ndani ya safu. Ni kipengele tunapaswa kuzingatia.
Hivyo chini ni 0, juu ni ya kawaida ya safu - 1,
na sasa sisi ni looping, na sisi ni kuangalia -
Nadhani unaweza kutembea kwa njia hiyo.
Nini ilikuwa mawazo yako kwa njia hii? Kutembea kwetu kupitia code yako.
[Mwanafunzi] Uhakika. Angalia katika thamani haystack katikati na kulinganisha kwa sindano.
Hivyo kama ni mkubwa kuliko sindano yako, basi unataka - oh, kwa kweli, kwamba wanapaswa kuwa nyuma.
Wewe ni kwenda unataka kutupa nusu kulia, na hivyo yeah, kwamba wanapaswa kuwa njia.
[Bowden] Basi hii inapaswa kuwa chini? Ni kwamba alisema nini? >> [Mwanafunzi] Yeah.
[Bowden] Sawa. Chini.
Hivyo kama nini sisi tunataka ni ndogo kuliko nini tunataka,
kisha yeah, tunataka kutupa nusu kushoto,
ambayo ina maana sisi ni uppdatering kila kitu sisi ni kuzingatia
na kusonga chini kuelekea kulia wa safu.
Hii inaonekana nzuri.
Nadhani ana suala moja kwamba sisi alisema mmoja uliopita,
ambapo kama ni ya chini na juu ni 0 1, kisha chini + up / 2 ni kwenda kuanzisha kuwa kitu kimoja tena.
>> Na hata kama si kwamba kesi, bado ni ufanisi zaidi kwa uchache sana
tu kutupa mbali kipengele sisi alimwangalia ambayo tunajua ni vibaya.
Hivyo chini + up / 2 + 1 - >> [mwanafunzi] Kwamba lazima njia nyingine.
[Bowden] Au hii lazima - 1 na nyingine moja lazima + 1.
[Mwanafunzi] Na kuwe mara mbili sawa na ishara. >> [Bowden] Yeah.
[Mwanafunzi] Yeah.
Sawa.
Na hatimaye, sasa kwamba tuna hii 1 + - 1 kitu,
ni - wanaweza kuwa - ni milele iwezekanavyo kwa ajili ya chini na kuishia na thamani kubwa zaidi kuliko up?
Nadhani njia pekee ambayo inaweza kutokea - Je, inawezekana? >> [Mwanafunzi] sijui.
Lakini kama anapata truncated na kisha anapata minus kwamba 1 na kisha - >> Yeah.
[Mwanafunzi] Ingekuwa uwezekano kupata messed up.
Nadhani ni lazima kuwa nzuri tu kwa sababu
kwa kuwa na kuishia chini wangeli kuwa sawa, nadhani.
Lakini kama ni sawa, basi sisi si wamefanya kitanzi wakati kuanza na
na sisi tu ingekuwa akarudi thamani. Hivyo nadhani sisi ni vizuri sasa.
Ona kwamba ingawa tatizo hili ni tena kujirudia,
aina moja ya mawazo kuomba ambapo tunaweza kuona jinsi hii kwa urahisi hivyo kunafaa
kwa ufumbuzi ya kujirudia na ukweli kwamba sisi ni tu uppdatering fahirisi tena na tena,
sisi ni kufanya tatizo na ndogo ndogo, tunalenga subset ya safu.
[Mwanafunzi] Ikiwa chini ni 0 na juu ni 1, wangeweza wote wawili kuwa 0 + 1/2, ambayo itakuwa kwenda 0,
na kisha moja itakuwa + 1, moja itakuwa - 1.
[Mwanafunzi] wapi sisi kuangalia usawa?
Kama kama moja katikati ni kweli sindano?
Sisi siyo sasa ya kufanya hivyo? Oh!
Kama it's -
Ndiyo. Hatuwezi tu kufanya mtihani chini hapa kwa sababu hebu sema katikati ya kwanza -
[Mwanafunzi] Ni kweli kama si kutupa amefungwa.
Hivyo kama wewe kutupa amefungwa, una kuangalia ni ya kwanza au chochote.
Ah. Yeah. >> [Mwanafunzi] Yeah.
Hivyo sasa tuna kutupwa mbali moja sisi sasa inaonekana katika,
ambayo ina maana sisi sasa wanahitaji pia kuwa
kama (haystack [(Asili + up) / 2] == sindano), basi tunaweza kurudi kweli.
Na kama mimi kuweka mwingine au tu kama, ina maana halisi kitu kimoja
kwa sababu hii ingekuwa akarudi kweli.
Basi, mimi itabidi kuweka mwingine ikiwa, lakini haijalishi.
>> Hivyo mwingine kama hii, pengine hii, na hili ni jambo la kawaida mimi kufanya
ambapo hata kama ni kesi ambapo kila kitu ni nzuri hapa,
kama chini hawezi kuwa mkuu kuliko juu, ni si thamani ya hoja kuhusu kama hiyo ni kweli.
Hivyo unaweza kusema kama vile wakati chini ni chini ya au sawa na
au wakati wa chini ni chini ya
hivyo kama wao ni milele sawa au chini kinachotokea kwa kupita juu,
basi tunaweza kuvunja nje ya kitanzi hii.
Maswali, hoja, maoni?
Sawa. Hii inaonekana nzuri.
Sasa tunataka kufanya aina.
Kama sisi kwenda kwa marekebisho yangu ya pili, tunaona idadi hayo,
lakini sasa hawawezi tena ili Iliyopangwa.
Na tunataka kutekeleza aina yoyote kutumia algorithm katika O ya n logi n.
Hivyo ambayo algorithm unafikiri sisi wanapaswa kutekeleza hapa? >> [Mwanafunzi] kuchanganya aina.
[Bowden] Yeah. Changanya aina ni O (n logi n), hivyo kwamba ni nini tunakwenda kufanya.
Na tatizo ni kwenda kuwa pretty sawa,
ambapo ni urahisi kunafaa kwa ufumbuzi kujirudia.
Tunaweza pia kuja na ufumbuzi iterative kama tunataka,
lakini recursion itakuwa rahisi hapa na tunapaswa kufanya recursion.
Nadhani sisi tutakwenda kwa njia ya aina kuunganisha kwanza,
ingawa kuna video lovely juu ya aina kuunganisha tayari. [Kicheko]
Hivyo kuunganisha aina kuna - I am kupoteza kiasi ya karatasi hii.
Oh, kuna moja tu kushoto.
Hivyo kuunganisha.
Oh, 1, 3, 5.
Sawa.
Kuunganisha inachukua wawili arrays tofauti.
Mmoja mmoja arrays wale wawili ni wawili Iliyopangwa.
Hivyo hii safu, 1, 3, 5, Iliyopangwa. Hii safu, 0, 2, 4, Iliyopangwa.
Sasa nini kuunganisha lazima kufanya ni kuchanganya yao katika safu moja ambayo ni yenyewe Iliyopangwa.
Hivyo tunataka safu ya ukubwa 6 kwamba ni kwenda kuwa mambo haya ndani yake
ili Iliyopangwa.
>> Na ili tuweze kuchukua faida ya ukweli kwamba arrays hizi mbili ni sorted
kufanya hivyo katika muda linear,
linear wakati maana ikiwa safu hii ni ya kawaida x na hii ni kawaida y,
kisha algorithm jumla lazima O (x + y). Sawa.
Hivyo mapendekezo.
[Mwanafunzi] Inawezekana sisi kuanza kutoka kushoto?
Hivyo itabidi kuweka 0 kwanza chini na kisha 1 na kisha hapa uko katika 2.
Hivyo ni aina ya kama una tab hiyo kusonga ya kulia. >> [Bowden] Yeah.
Kwa wote wa arrays haya ikiwa sisi tu kuzingatia kipengele leftmost.
Kwa sababu wote wawili arrays wanatenganishwa, tunajua kwamba haya mambo 2
ni ndogo vipengele katika safu aidha.
Hivyo hiyo ina maana kwamba 1 ya vipengele wale 2 lazima kipengele ndogo katika safu yetu enheten.
Ni tu hivyo hutokea kuwa ndogo ni moja kwa wakati haki hii.
Hivyo sisi kuchukua 0, kuingiza upande wa kushoto kwa sababu ni chini ya 0 1,
hivyo kuchukua 0, kuingiza katika nafasi yetu ya kwanza, na kisha sisi update hii
kwa sasa kuzingatia kipengele kwanza.
Na sasa sisi kurudia.
Hivyo sasa sisi kulinganisha na 2 1. 1 ni ndogo, hivyo tutaweza Insert 1.
Sisi update hii pointer na kumweka kwa guy.
Sasa sisi kufanya hivyo tena, hivyo 2. Hii update, kulinganisha haya 2, 3.
Hii updates, basi 4 na 5.
Hivyo kwamba ni kuunganisha.
>> Ni lazima pretty dhahiri kwamba ni linear wakati tangu sisi tu kwenda katika kila kipengele mara moja.
Na kwamba ni hatua kubwa kwa kutekeleza kuunganisha aina anafanya hili.
Na si kwamba ni vigumu.
mambo ya wanandoa na wasiwasi juu ya ni wacha kusema tulikuwa kuunganisha 1, 2, 3, 4, 5, 6.
Katika kesi hii sisi kuishia katika mazingira ambapo mmoja huu ni kwenda kuwa ndogo,
kisha sisi update hii pointer, mmoja huu ni kwenda kuwa ndogo, update hii,
moja hii ni ndogo, na sasa una kutambua
wakati umeweka kweli kukimbia nje ya mambo ya kulinganisha na.
Tangu sisi tayari kutumika hii safu nzima,
kila kitu katika safu hii ni sasa tu kuingizwa katika hapa.
Hivyo kama sisi milele kukimbia katika hatua ambapo moja ya arrays yetu ni kabisa ilijiunga tayari,
kisha sisi tu kuchukua mambo yote ya safu nyingine na Insert yao katika mwisho wa safu.
Hivyo tunaweza tu Insert 4, 5, 6. Sawa.
Hiyo ni jambo moja kuangalia nje kwa.
Kutekeleza kwamba wanapaswa kuwa hatua 1.
Changanya kuchambua kisha kuzingatia kwamba, ni hatua 2, 2 silly hatua.
Hebu tu kutoa hii safu.
Hivyo kuunganisha aina, hatua 1 ni recursively kuvunja safu ndani ya nusu.
Hivyo kupasuliwa hii safu ndani ya nusu.
Sisi sasa kuwa 4, 15, 16, 50 na 8, 23, 42, 108.
Na sasa sisi kufanya hivyo tena na sisi hawa umegawanyika katika halves.
Mimi itabidi kufanya hivyo kwa upande huu.
Hivyo 4, 15 na 16, 50.
Tunataka kufanya kitu kimoja hapa.
Na sasa sisi kupasuliwa ndani halves tena.
Na tuna 4, 15, 16, 50.
Hivyo kuwa ni msingi wetu kesi.
Mara arrays ni ya kawaida ya 1, basi sisi kuacha na kuigawanya halves.
>> Sasa tunafanya nini kwa hili?
Sisi kuishia hii pia kuvunja chini ndani ya 8, 23, 42, na 108.
Hivyo sasa kwamba sisi ni katika hatua hii, sasa hatua mbili za aina kuunganisha ni kuunganisha tu jozi orodha.
Hivyo tunataka kuunganisha haya. Sisi tu wito merge.
Tunajua kuunganisha haya kurudi ili Iliyopangwa.
4, 15.
Sasa tunataka kuunganisha haya, na kwamba atarudi orodha na wale ili Iliyopangwa,
16, 50.
Sisi kuunganisha wale - siwezi kuandika - 8, 23 na 42, 108.
Hivyo tuna jozi enheten mara moja.
Sasa sisi tu kuunganisha tena.
Ona kwamba kila moja ya orodha hizi ni Iliyopangwa katika yenyewe,
na kisha tunaweza tu kuunganisha orodha hizi na kupata orodha ya ukubwa 4 ambayo ni Iliyopangwa
na kuunganisha orodha hizi mbili na kupata orodha ya ukubwa 4 kwamba ni Iliyopangwa.
Na hatimaye, tunaweza kuunganisha orodha hizo mbili ya ukubwa 4 kupata orodha moja ya ukubwa 8 kwamba ni Iliyopangwa.
Hivyo kwa kuona kwamba hii ni jumla n n logi, sisi tayari kuona kwamba kuunganisha ni linear,
hivyo wakati sisi ni kushughulika na kuunganisha haya, hivyo kama gharama ya jumla ya kuunganisha
kwa orodha hizi mbili ni kwa sababu tu 2 -
Au vizuri, ni O ya n, lakini n hapa ni tu haya mambo 2, hivyo ni 2.
Na hawa 2 itakuwa 2 na hizi 2 itakuwa 2 na hizi 2 itakuwa 2,
hivyo katika yote ya huingiza kwamba tunahitaji kufanya, sisi kuishia kufanya n.
Kama 2 + 2 + 2 + 2 ni 8, ambayo ni n,
hivyo gharama ya kuunganisha katika kuweka hii ni n.
Na kisha kitu kimoja hapa.
Tutaweza kuunganisha hizi 2, basi hawa 2, na kila mmoja kuunganisha hii itachukua shughuli nne,
hii kuunganisha itachukua shughuli nne, lakini kwa mara nyingine tena, kati ya haya yote, kwa
sisi kuishia kuunganisha n mambo ya jumla, na hivyo hatua hii inachukua n.
Na hivyo kila ngazi inachukua vipengele n kuwa zimeunganishwa.
>> Na jinsi wengi ngazi ni huko?
Katika kila ngazi, safu yetu kukua kwa ukubwa 2.
Hapa arrays yetu ni ya kawaida ya 1, hapa wao ni wa kawaida 2, hapa wao ni wa kawaida 4,
na hatimaye, wao uko wa kawaida 8.
Hivyo kwa vile ni mara mbili, kuna kwenda kuwa jumla ya logi n ya hizi ngazi.
Hivyo kwa logi n ngazi, kila ngazi ya mtu binafsi kuchukua n shughuli jumla,
sisi kupata logi n n algorithm.
Maswali?
Je watu tayari alifanya maendeleo juu ya jinsi ya kutekeleza mpango huu?
Ni mtu yeyote tayari katika hali ambapo naweza tu kuvuta kanuni zao?
Siwezi kutoa dakika.
Moja hii ni ya kwenda kuwa mrefu.
Mimi sana kupendekeza chamka -
Huna kufanya recursion kwa kuunganisha
kwa sababu ya kufanya recursion kwa kuunganisha, utaenda kuwa na kupita rundo la ukubwa tofauti.
Unaweza, lakini ni annoying.
Lakini recursion kwa aina yenyewe ni rahisi pretty.
Wewe tu literally kuwaita aina ya nusu ya kushoto, aina ya nusu ya haki. Sawa.
Mtu yeyote kuwa kitu naweza kuvuta juu bado?
Au mwingine mimi nitakupa dakika.
Sawa.
Mtu yeyote kuwa kitu tunaweza kufanya kazi na?
Au mwingine tutaweza tu kazi na hili na kisha kupanua kutoka huko.
>> Mtu yeyote kuwa zaidi ya hii kwamba naweza kuvuta up?
[Mwanafunzi] Yeah. Unaweza kuvuta juu yangu. >> Sawa.
Ndiyo!
[Mwanafunzi] Kulikuwa na mengi ya hali ya. >> Oh, risasi. Je, unaweza -
[Mwanafunzi] nina atayaokoa. >> Yeah.
Hivyo sisi gani kufanya kuunganisha tofauti.
Oh, lakini siyo kuwa mbaya.
Sawa.
Hivyo ni aina yenyewe tu wito mergeSortHelp.
Tueleze nini mergeSortHelp gani.
[Mwanafunzi] MergeSortHelp pretty kiasi gani hatua mbili kuu,
ambayo ni ya kutatua kila nusu ya safu na kisha kuunganisha yao wote.
[Bowden] Sawa, hivyo nipe pili.
Nadhani hii - >> [mwanafunzi] nahitaji -
Yeah. Mimi kukosa kitu.
Katika kuunganisha, mimi kutambua kwamba mimi haja ya kuunda safu mpya
sababu sikuweza kufanya hivyo katika mahali. >> Ndiyo. Huwezi. Kusahihisha.
[Mwanafunzi] Basi mimi kujenga safu mpya.
Nimesahau mwisho wa kuunganisha kwa re-kubadilika.
Sawa. Tunahitaji safu mpya.
Katika aina kuunganisha, hii ni karibu daima kweli.
Sehemu ya gharama ya algorithm bora wakati-busara
ni karibu daima wanaohitaji kutumia kidogo zaidi kumbukumbu.
Hivyo hapa, hakuna jambo jinsi ya kufanya kuunganisha aina ya,
wewe bila shaka haja ya kutumia baadhi ya kumbukumbu ya ziada.
Yeye au yeye aliumba safu mpya.
Na kisha wewe sema mwishoni sisi tu haja ya nakala safu mpya katika safu ya awali.
[Mwanafunzi] Nadhani hivyo, yeah.
Mimi sijui kama kwamba kazi katika suala la kuhesabu kura kwa kumbukumbu au chochote -
Yeah, itakuwa kazi. >> [Mwanafunzi] Sawa.
Je kujaribu kuendesha hii? >> [Mwanafunzi] Hapana, bado. >> Sawa.
Jaribu mbio, na basi mimi itabidi kuzungumza juu yake kwa ajili ya pili.
[Mwanafunzi] nahitaji kuwa na prototypes wote kazi na kila kitu, ingawa, sawa?
prototypes kazi. Oh, maana kama - Ndiyo.
Panga wito mergeSortHelp.
>> Hivyo ili kwa aina kuwaita mergeSortHelp, mergeSortHelp lazima aidha wamekuwa defined
kabla ya aina au sisi tu haja ya mfano. Tu nakala na kuweka kwamba.
Na vile vile, mergeSortHelp wito kuunganisha,
lakini kuunganisha haijawahi defined bado, hivyo tunaweza kujua tu basi mergeSortHelp
kwamba kwamba ni nini kuunganisha ni kwenda kuangalia kama, na kwamba ni kwamba.
Hivyo mergeSortHelp.
Tuna suala hapa ambapo hatuna kesi ya msingi.
MergeSortHelp ni kujirudia, hivyo kazi yoyote ya kujirudia
ni kwenda haja ya baadhi ya aina ya kesi ya msingi ya kujua wakati kuacha recursively linalojiita.
Nini msingi wetu kesi kwenda kuwa hapa? Yeah.
[Mwanafunzi] Kama kawaida ni 1? >> [Bowden] Ndiyo.
Hivyo kama tuliona haki pale, sisi kusimamishwa arrays splitting
mara moja sisi got katika arrays ya kawaida ya 1, ambayo inevitably wanatenganishwa wenyewe.
Hivyo kama kawaida sawa na 1, tunajua safu tayari Iliyopangwa,
hivyo tunaweza tu kurudi.
>> Ona kwamba ni batili, hivyo hatuwezi kurudi chochote hasa, sisi tu kurudi.
Sawa. Basi hiyo ni msingi wetu kesi.
Nadhani msingi wetu kesi inaweza pia kuwa kama sisi kutokea kwa kuwa kuunganisha safu ya ukubwa 0,
sisi pengine unataka kuacha wakati fulani,
hivyo tunaweza kusema tu kawaida chini ya 2 au chini zaidi au sawa na 1
hivyo kwamba hii kazi kwa safu yoyote sasa.
Sawa.
Basi hiyo ni msingi wetu kesi.
Sasa unataka kutembea kwetu kupitia kuunganisha?
Nini kesi hizi zote maana?
Hadi hapa, sisi ni kufanya tu wazo huo, -
[Mwanafunzi] Mimi haja ya kuwa na kupita kawaida na simu zote mergeSortHelp.
Mimi aliongeza ukubwa kama msingi ya ziada na si huko, kama kawaida / 2.
[Bowden] Oh, ukubwa / 2, ukubwa / 2. >> [Mwanafunzi] Yeah, na pia katika kazi hapo juu pia.
[Bowden] Hapa? >> [Mwanafunzi] Tu kawaida. >> [Bowden] Oh. Ukubwa, kawaida? >> [Mwanafunzi] Yeah.
[Bowden] Sawa.
Hebu fikiria kwa pili.
Je, sisi kukimbia katika suala hilo?
Sisi ni daima kutibu kushoto kama 0. >> [Mwanafunzi] No
Hiyo ni vibaya mno. Sorry. Ni lazima kuanza. Yeah.
[Bowden] Sawa. Mimi kama kwamba bora.
Na mwisho. Sawa.
Hivyo sasa unataka kutembea kwetu kupitia kuunganisha? >> [Mwanafunzi] Sawa.
Mimi tu kutembea kupitia safu hii mpya kwamba nimepata kuundwa.
Kawaida yake ni ukubwa wa sehemu ya safu kwamba tunataka sorted
na kujaribu kutafuta kipengele kwamba mimi wanapaswa kuweka katika hatua mpya safu.
Hivyo kufanya hivyo, kwanza mimi nina kuangalia kama nusu ya kushoto ya safu inaendelea kuwa na vipengele yoyote zaidi,
na kama hana, basi wewe kwenda chini kwa sharti kwamba mwingine, ambayo tu anasema
sawa, ni lazima kuwa katika safu haki, na tutaweza kuweka kwamba katika ripoti ya sasa ya newArray.
>> Na kisha vinginevyo, mimi nina kuangalia kama upande wa kulia wa safu pia kumaliza,
katika kesi ambayo mimi tu ya kuweka katika kushoto.
Kwamba wanaweza kweli kuwa muhimu. Mimi nina uhakika.
Lakini anyway, na wengine wawili hundi ambayo ya mbili ni ndogo katika upande wa kushoto au kulia.
Na pia katika kila kesi, mimi nina incrementing yoyote placeholder mimi increment.
[Bowden] Sawa.
Hiyo inaonekana ni nzuri.
Je, mtu yeyote kuwa na maoni au hoja au maswali?
Hivyo kesi nne kwamba tuna kuleta mambo ndani tu kuwa - au inaonekana kama tano -
lakini tuna kufikiria kama safu ya kushoto ina kukimbia nje ya mambo tunahitaji kuunganisha,
kama safu haki ina kukimbia nje ya mambo tunahitaji kuunganisha -
Mimi nina akionyesha chochote.
Hivyo kama safu ya kushoto ina kukimbia nje ya mambo au safu haki ina kukimbia nje ya mambo.
Wale ni kesi mbili.
Tunahitaji pia kesi ya trivial kama kitu kushoto ni chini ya jambo sahihi.
Kisha tunataka kuchagua kitu kushoto.
Wale ni kesi.
Hivyo hii ilikuwa sahihi, hivyo ndiyo hiyo.
Array kushoto. Ni 1, 2, 3. Sawa. Hivyo yeah, hayo ni mambo nne sisi kutaka kufanya.
Na sisi si kwenda juu ya iterative ufumbuzi.
Napenda kupendekeza -
Changanya aina ni mfano wa kazi kuwa ni wa si mkia kujirudia,
si rahisi kufanya hivyo mkia kujirudia,
lakini pia si rahisi sana kufanya hivyo iterative.
Hii ni rahisi sana.
Hii utekelezaji wa aina kuunganisha,
kuchanganya, haijalishi wewe kufanya, wewe ni kwenda kujenga kuunganisha.
>> Hivyo kuunganisha aina umejengwa juu ya kuunganisha recursively ni tu hizi mistari mitatu.
Iteratively, ni zaidi annoying na zaidi vigumu kufikiri.
Lakini ona kwamba si mkia kujirudia tangu mergeSortHelp - wakati wito yenyewe -
bado anahitaji kufanya mambo baada anarudi hii kujirudia wito.
Hivyo hii frame stack lazima kuendelea kuwepo hata baada ya wito huu.
Na kisha wakati wewe piga hii, sura stack lazima kuendelea kuwepo
sababu hata baada ya wito kwamba, bado tunahitaji kuunganisha.
Na ni nontrivial kufanya mkia hii kujirudia.
Maswali?
Wote haki.
Hivyo kurejea kwa aina - oh, kuna mambo mawili nataka kuonyesha. Sawa.
Tukirudi kwenye aina, tutaweza kufanya hivyo haraka.
Au tafuta. Panga? Panga. Yeah.
Tukirudi kwenye mwanzo wa aina.
Tunataka kujenga algorithm kwamba kila safu kutumia yoyote algorithm
katika O ya n.
Hivyo jinsi hii inawezekana? Je, mtu yeyote kuwa na aina yoyote ya -
Mimi aligusia kabla saa -
Kama sisi ni juu ya kuboresha kutoka n logi n O ya n,
sisi kuwa kuboreshwa algorithm yetu wakati-busara,
ambayo ina maana nini sisi kwenda haja ya kufanya kwa ajili ya kufanya hivyo?
[Mwanafunzi] Space. >> Yeah. Sisi ni kwenda kuwa na kutumia nafasi zaidi.
Na si tu hata nafasi zaidi, ni exponentially nafasi zaidi.
Hivyo nadhani aina hii ya algorithm ni Pseudo kitu, Pseudo polynom -
Pseudo - siwezi kukumbuka. Pseudo kitu.
Lakini ni kwa sababu tunahitaji kutumia kiasi nafasi
kwamba hii ni mafanikio lakini si kweli.
>> Na jinsi gani sisi kufikia hili?
Tunaweza kufikia mafanikio haya kama sisi kuhakikisha kwamba yoyote ya kipengele fulani katika safu
ni chini ya ukubwa fulani.
Basi hebu tu kusema kwamba ukubwa ni 200,
yoyote ya kipengele katika safu ni chini ya kawaida 200.
Na hii ni kweli kweli sana.
Unaweza urahisi sana kuwa na safu kwamba unajua kila kitu ndani yake
ni kwenda kuwa chini ya idadi fulani.
Kama kama una baadhi ya vector kabisa mkubwa au kitu
lakini unajua kila kitu kinaenda kuwa kati ya 0 na 5,
basi ni kwenda kuwa kwa kiasi kikubwa kasi ya kufanya hili.
Na amefungwa juu ya yoyote ya vipengele ni 5,
hivyo hii amefungwa, kwamba ni kiasi gani kumbukumbu utaenda kutumia.
Hivyo amefungwa ni 200.
Katika nadharia daima kuna amefungwa tangu integer inaweza tu kuwa hadi bilioni 4,
lakini hiyo ni unrealistic tangu basi tunatarajia kuwa na kutumia nafasi
juu ya utaratibu wa bilioni 4. Basi hiyo ni unrealistic.
Lakini hapa tutaweza kusema amefungwa yetu ni 200.
hila ili kufanya hivyo katika O ya n ni sisi kufanya mwingine safu kuitwa makosa ya kawaida amefungwa.
Hivyo kweli, hii ni njia ya mkato kwa - Mimi kwa kweli sijui kama Clang gani hii.
Lakini katika GCC angalau sana - I'm kuchukua Clang gani pia -
hii tu initialize safu nzima kuwa sekunde 0.
Hivyo kama mimi sitaki kufanya hivyo, basi mimi naweza kufanya tofauti kwa ajili ya (i = 0 int;
i <BOUND; i + +) na makosa [i] = 0;
Hivyo sasa kila kitu ni initialized kwa 0.
Mimi iterate juu ya safu yangu,
na nini mimi kufanya ni mimi nina kuhesabu idadi ya kila - Hebu kwenda chini hapa.
Tuna 4, 15, 16, 50, 8, 23, 42, 108.
Nini mimi kuhesabu ni idadi ya matukio ya kila moja ya mambo hayo.
Hebu kweli kuongeza michache zaidi katika hapa kwa kurudia baadhi.
Hivyo thamani sisi hapa, thamani ya kwamba ni kwenda kuwa safu [i].
Hivyo Val inaweza kuwa 4 au 8 au chochote.
Na sasa mimi nina kuhesabu jinsi wengi wa thamani kwamba nimepata kuona,
hivyo makosa [Val] + +;
Baada ya hili ni kosa, makosa ni kwenda kuangalia kitu kama 0001.
Hebu kufanya makosa [Val] - amefungwa + 1.
>> Sasa kwa kuwa tu kuwajibika kwa ajili ya ukweli kwamba sisi ni kuanzia 0.
Hivyo kama 200 ni kwenda kuwa idadi yetu kubwa,
kisha 0-200 ni 201 mambo.
Hivyo makosa, hivyo itabidi kuangalia kama 00,001 kwa sababu sisi moja 4.
Kisha sisi itabidi 0001 ambapo tutaweza kuwa na 1 katika ripoti ya 8 ya kuhesabu.
Sisi itabidi 2 katika ripoti ya 23 ya kuhesabu.
Sisi itabidi 2 katika ripoti ya 42 ya kuhesabu.
Hivyo tunaweza kutumia kuhesabu.
Hivyo num_of_item = makosa [i].
Na hivyo kama num_of_item ni 2, kwamba maana tunataka Insert 2 ya idadi i
ndani ya safu yetu Iliyopangwa.
Hivyo tunahitaji kuweka wimbo wa jinsi mbali sisi ni katika safu.
Hivyo index = 0.
Array - mimi itabidi kuandika.
Makosa -
safu [index + +] = i;
Ni kwamba nini nataka? Nadhani hiyo ni nini nataka.
Ndiyo, hii inaonekana ni nzuri. Sawa.
Hivyo haina kila mtu kuelewa nini madhumuni ya safu yangu ni makosa?
Ni kuhesabu idadi ya matukio ya kila moja ya namba hizi.
Kisha Mimi iterating juu ya kwamba safu makosa,
na msimamo idh katika safu makosa
ni idadi ya i ni kwamba wanapaswa kuonekana katika safu yangu Iliyopangwa.
Hiyo ndiyo sababu ya makosa ya 4 ni kwenda kuwa 1
na makosa ya 8 ni kwenda kuwa 1, makosa ya 23 itakuwa ni 2.
Basi hiyo ni jinsi wengi wao nataka Insert katika safu yangu Iliyopangwa.
Kisha mimi tu kufanya hivyo.
Mimi inserting num_of_item i ni ndani ya safu yangu Iliyopangwa.
>> Maswali?
Na hivyo tena, hii ni linear wakati tangu sisi tu iterating juu ya hili mara moja,
lakini pia ni linear katika kile idadi hii hutokea kwa kuwa,
na hivyo sana unategemea nini amefungwa yako ni.
Pamoja na amefungwa ya 200, si kwamba kuwa mbaya.
Kama amefungwa yako ni kwenda kuwa 10,000, kisha hiyo kidogo mbaya,
lakini kama amefungwa yako ni kwenda kuwa bilioni 4, kwamba ni kabisa unrealistic
na safu hii ni ya kwenda kuwa ya kawaida bilioni 4, ambayo ni unrealistic.
Basi hiyo ni kwamba. Maswali?
[Inaudible mwanafunzi majibu] >> Sawa.
Nilitambua nyingine moja kitu, tulipokuwa tunakwenda kupitia.
Nadhani tatizo ni katika ya Lucas na pengine kila mmoja tumeona.
Mimi kabisa alisahau.
Kitu tu nilitaka kutoa maoni juu ni kwamba wakati wewe ni kushughulika na mambo kama fahirisi,
wewe kweli kamwe kuona hii wakati wewe ni kuandika kwa kitanzi,
lakini kitaalam, wakati wowote wewe ni kushughulika na fahirisi hizi,
unapaswa pretty much daima kukabiliana na integers unsigned.
Sababu hii ni wakati wewe ni kushughulika na integers saini,
hivyo kama una 2 integers saini na wewe kuongeza yao pamoja
na wanaishia kubwa mno, basi wewe kuishia na idadi hasi.
Hivyo kwamba ni nini kufurika integer ni.
>> Kama mimi kuongeza bilioni 2 na bilioni 1, mimi kuishia na hasi bilioni 1.
Hiyo ni jinsi integers kazi kwenye kompyuta.
Hivyo tatizo na kutumia -
Hiyo ni sawa ila ikiwa chini hutokea kwa kuwa na bilioni 2 hadi hutokea kwa kuwa bilioni 1,
basi hii itakuwa ni hasi bilioni 1 na kisha tunakwenda kugawanya kwamba kwa 2
na kuishia na hasi milioni 500.
Hivyo hii ni suala tu kama wewe kutokea kwa kuwa kutafuta njia ya safu
mabilioni ya mambo.
Lakini kama + chini juu kinachotokea kwa kufurika, basi hiyo ni tatizo.
Haraka kama sisi kufanya nao unsigned, basi bilioni 2 plus bilioni 1 ni bilioni 3.
Bilioni 3 kugawanywa na 2 ni bilioni 1.5.
Hivyo kwa haraka kama wao ni unsigned, kila kitu ni kamilifu.
Na hivyo pia kwamba suala wakati wewe kuandika yako kwa tanzi,
na kweli, basi pengine gani moja kwa moja.
Itakuwa kweli tu yell saa wewe.
Hivyo kama idadi hii ni kubwa mno kuwa katika tu integer lakini ingekuwa fit katika integer unsigned,
itakuwa yell katika wewe, hivyo ndiyo sababu wewe kamwe kweli kukimbia katika suala hilo.
Unaweza kuona kwamba index ni kamwe kwenda kuwa hasi,
na hivyo wakati uko juu ya iterating safu,
unaweza karibu daima kusema unsigned int i, lakini wewe si kweli kuwa kwa.
Mambo ni kwenda kufanya kazi pretty much tu kama vizuri.
Sawa. [Minong'ono] Ni saa?
Jambo la mwisho nilitaka kuonyesha - na mimi itabidi kufanya hivyo kweli haraka.
Unajua jinsi tuna # define ili tuweze # define MAX kama 5 au kitu?
Hebu si kufanya MAX. # Define amefungwa kama 200. Hiyo ni nini sisi alifanya mbele.
Kwamba amefafanua mara kwa mara, ambayo ni kwenda tu kunakiliwa na pasted
popote sisi kutokea kwa kuandika amefungwa.
>> Hivyo tunaweza kweli kufanya zaidi na # amefafanua.
Tunaweza # define kazi.
Wao ni si kweli kazi, lakini tutaweza kuwaita kazi.
itakuwa mfano kitu kama MAX (x, y) inaelezwa kama (x <y y:? x). Sawa.
Hivyo unapaswa kupata kutumika ternary syntax operator,
lakini ni chini ya x y? Kurudi y, mwingine kurudi x.
Hivyo unaweza kuona unaweza kufanya hii kazi tofauti,
na kazi inaweza kuwa kama bool MAX inachukua hoja 2, kurudi huu.
Hii ni moja ya ndio kawaida naona kufanyika kama hii. Sisi kuwaita macros.
Hii ni jumla.
Hii ni syntax kwa ajili yake.
Unaweza kuandika jumla ya kufanya chochote unataka.
Wewe mara nyingi kuona macros kwa debugging printfs na mambo ya ajabu.
Hivyo aina ya printf, kuna constants maalum katika C kama underscore LINE underscore,
2 underscores LINE underscore,
na pia kuna Nadhani 2 underscores func. Hiyo inaweza kuwa hivyo. Kitu kama hicho.
Hayo mambo itakuwa kubadilishwa kwa jina la kazi
au idadi ya mstari kwamba uko juu.
Mara kwa mara, wewe kuandika printfs debugging kwamba chini hapa mimi nilikuwa basi andika tu
Debug na itakuwa magazeti idadi line na kazi ya kuwa mimi kutokea kwa kuwa katika
kwamba wamekutana kwamba taarifa Debug.
Na unaweza pia magazeti mambo mengine.
Hivyo jambo moja unapaswa kuangalia kwa ni kama mimi kutokea kwa # define DOUBLE_MAX
kama kitu kama 2 * y * na 2 x.
Hivyo kwa sababu yoyote, wewe kutokea kwa kufanya hivyo mengi.
Hivyo kufanya hivyo jumla.
Hii ni kweli kuvunjwa.
Napenda kuiita kwa kufanya kitu kama DOUBLE_MAX (3, 6).
Basi nini kirejeshwe?
[Mwanafunzi] 12.
Ndiyo, 12 kirejeshwe, na 12 ni kurudi.
3 anapata kubadilishwa kwa x, 6 anapata kubadilishwa kwa y, na sisi kurudi 2 * 6, ambayo ni 12.
Sasa nini kuhusu hili? Nini kirejeshwe?
[Mwanafunzi] 14. >> Kimawazo, 14.
suala ni kwamba jinsi hash amefafanua kazi, kumbuka ni nakala halisi na kuweka
wa kila kitu pretty much, ili kile hii ni kwenda kufasiriwa kama
ni 3 chini ya 1 plus 6, 2 mara 1 plus 6, 2 mara 3.
>> Hivyo kwa sababu hii wewe daima karibu wrap kila kitu katika mabano.
Yoyote variable wewe daima karibu wrap katika mabano.
Kuna matukio ambapo wewe huna, kama mimi najua kuwa mimi si haja ya kufanya hivyo hapa
kwa sababu chini ya ni kiasi pretty daima tu kwenda kufanya kazi,
ingawa kwamba wanaweza hata kuwa kweli.
Kama kuna kitu kama ridiculous DOUBLE_MAX (1 == 2),
basi hiyo ni kwenda kupata kubadilishwa na 3 chini ya 1 ni sawa sawa na 2,
na hivyo basi ni kwenda kufanya 3 chini ya 1, 2 gani kwamba sawa,
ambayo ni nini tunataka.
Hivyo ili kuzuia mtu yeyote operator matatizo precedence,
daima wrap katika mabano.
Sawa. Na hiyo ni yake, 5:30.
Kama una maswali yoyote juu ya pset, tujulishe.
Ni lazima kuwa na furaha, na toleo la hacker pia ni kweli zaidi
kuliko toleo hacker ya mwaka jana, hivyo tunatarajia mengi ya wewe kujaribu.
Mwaka jana alikuwa sana balaa.
>> [CS50.TV]