[Powered by Google Translate] [Seksyon 3 - Higit kumportableng]
[Rob Bowden - Harvard University]
>> [Ito ay CS50. - CS50.TV]
>> Kaya ang unang tanong ay kakaiba worded.
GDB hinahayaan mo ang "i-debug" isang programa, ngunit, higit na partikular, kung ano ang sabihin gagawin mo?
Kukunin ko na answer na ang isa, at hindi ko alam kung ano ang eksaktong inaasahan,
kaya ako paghula ito ay isang bagay na kasama ang mga linya nito ay hinahayaan ka hakbang sa pamamagitan ng hakbang
maglakad sa pamamagitan ng programa, makipag-ugnayan sa mga ito, ang mga pagbabago variable, gawin ang lahat ng mga bagay na ito -
talaga ganap na kontrolin ang pagpapatupad ng isang programa
at siyasatin ang anumang ibinigay na bahagi ng pagpapatupad ng programa.
Kaya Hinahayaan ka ide-debug ang mga bagay ng mga tampok na iyon.
Okay.
Bakit ang binary paghahanap nangangailangan na ang isang array pinagsunod-sunod?
Sino ang nais sagutin iyon?
[Mag-aaral] Dahil hindi ito gumana kung hindi ito pinagsunod-sunod. >> Oo. [Tawa]
Kung hindi ito pinagsunod-sunod, pagkatapos imposibleng hatiin ito sa kalahati
at malaman na ang lahat sa kaliwa ay mas mababa at lahat sa kanan
ay mas malaki kaysa sa gitna halaga.
Kaya ito ay kinakailangan na pinagsunod-sunod.
Okay.
Bakit bubble uri sa O ng n squared?
Ba ang sinuman munang gusto mong magbigay ng isang napaka-mabilis na mataas na antas ng pangkalahatang-ideya ng kung ano ang bubble-uuri?
[Mag-aaral] mo talaga pumunta sa pamamagitan ng bawat elemento at suriin mo ang unang ilang mga elemento.
Kung hindi nila ito kung saan mong magpalit ang mga ito, pagkatapos ay mong suriin ang susunod na ilang mga elemento at iba pa.
Kapag naabot mo na ang katapusan, alam mo na ang pinakamalaking elemento ay nakalagay sa dulo,
kaya huwag pansinin na ang isa pagkatapos mong panatilihin sa pagpunta sa pamamagitan ng,
at sa bawat oras na mayroon kang upang suriin ang isa mas elemento hanggang sa magsagawa ka ng mga walang mga pagbabago. >> Oo.
Ito ay tinatawag na bubble-uuri dahil kung i-flip mo ang hanay sa tabi upang ito ay up at down, vertical,
ang malaking halaga ay tumining at ang maliit na halaga bubble sa itaas.
Kung paano nakuha ang pangalan nito.
At oo, pumunta lamang sa pamamagitan ng.
Mong patuloy na pagpunta sa pamamagitan ng array, pagpapalit ang mas malaking halaga
upang makuha ang pinakamalaking halaga sa ibaba.
>> Bakit ito O ng n squared?
Una, ang sinuman nais na sabihin kung bakit ito O ng n squared?
[Mag-aaral] Dahil para sa bawat run na ito napupunta n beses.
Maaari ka lamang maging sigurado na iyong kinuha ang pinakamalaking elemento lahat ng paraan,
pagkatapos ay mayroon kang upang ulitin na para sa maraming mga sangkap. >> Oo.
Kaya tandaan kung ano ang malaking O ay nangangahulugan at kung ano ang malaking Omega paraan.
Ang malaking O ay tulad ng sa itaas na nakatali sa kung paano mabagal ito aktwal na patakbuhin.
Kaya sa pamamagitan ng sinasabi ito ay O ng n squared, ito ay hindi O ng n o tao ay upang tumakbo
sa linear oras, ngunit ito ay O ng n nakakubo
dahil ito ay bounded sa pamamagitan ng O ng n nakakubo.
Kung ito ay bounded sa pamamagitan ng O ng n squared, pagkatapos ito ay bounded ng n nakakubo din.
Kaya n squared, at sa absolute pinakamasama kaso hindi ito maaaring gawin mas mahusay kaysa sa n squared,
na ang dahilan kung bakit O n squared.
Kaya upang makita ang bahagyang matematika sa kung paano ito ay n squared,
kung kami ay may limang bagay sa aming listahan, sa unang pagkakataon kung gaano karaming mga swaps kami potensyal na kailangan upang gumawa ng
upang makakuha ng ito? Natin ang aktwal na lamang -
Gaano karaming mga swaps ay namin upang gumawa ng sa unang pagtakbo ng bubble-uuri sa pamamagitan ng array?
[Mag-aaral] n - 1. >> Oo.
>> Kung may 5 elemento, kami ay pagpunta sa kailangan upang gumawa ng n - 1.
Pagkatapos sa ikalawang isa kung gaano karaming mga swaps ay namin upang gumawa?
[Mag-aaral] n - 2. >> Oo.
At third n - 3, at pagkatapos ay para sa kaginhawaan kong isulat ang huling dalawang mga
bilang kami ay kailangang gumawa ng mga 2 swaps at 1 makipagpalitan.
Hulaan ko ang huling isa ay maaaring o hindi maaaring aktwal na kailangang mangyari.
Ito sa isang makipagpalitan? Hindi ko alam.
Kaya ito ay ang kabuuang halaga ng mga swaps o hindi bababa sa paghahambing mayroon kang upang gumawa ng.
Kahit na hindi mo swap, kailangan mo pa rin upang ihambing ang mga halaga.
Kaya may mga n - 1 paghahambing sa unang pagtakbo sa pamamagitan ng array.
Kung mong isaayos muli ang mga bagay na ito, ipaalam sa aktwal na gawin itong anim na mga bagay upang ang mga bagay stack up mabuti,
at pagkatapos ay makikita ko 3, 2, 1.
Kaya lang rearranging mga sums ito, nais namin upang makita kung gaano karaming mga mga paghahambing na gumawa kami
sa buong algorithm.
Kaya kung dalhin namin mga guys down na dito,
pagkatapos pa namin lamang summing gayunpaman maraming mga paghahambing na may mga.
Ngunit kung namin sabihin sa ilang mga ito at nagtutuos namin ito at naming sabihin sa ilang mga,
ito ay pa rin ang parehong problema. Lang namin sabihin sa ilang mga partikular na mga grupo.
>> Kaya ngayon kami ay summing 3 n ng. Hindi lang 3 n ng.
Palagi itong pagpunta sa n / 2 n ng.
Kaya dito namin mangyari na magkaroon ng 6.
Kung tayo ay may 10 bagay, at pagkatapos ay maaari kaming gawin ang pagpapangkat na ito para sa 5 iba't ibang mga pares ng mga bagay
at nagtatapos sa n + n + n + n + n.
Kaya palagi ka pagpunta upang makakuha n / 2 n ng, at kaya ito ipapakita namin itala ito sa n squared / 2.
At kaya kahit ito ang kadahilanan ng kalahati, na mangyayari sa darating sa
dahil sa ang katunayan na sa pamamagitan ng bawat pag-ulit sa ibabaw ng array ihambing namin 1 mas
kaya na kung paano makuha namin ang sa 2, ngunit pa rin ito n squared.
Hindi namin pakialam tungkol sa pare-pareho ang salik ng kalahati.
Kaya ng maraming ng malaking O bagay tulad nito ay nakasalalay sa lamang uri ng paggawa ng ganitong uri ng matematika,
paggawa ng mga sums ng aritmetika at geometric serye bagay-bagay,
ngunit karamihan sa mga ito sa kursong ito ay medyo direkta.
Okay.
Bakit pagpapasok ng uri sa Omega ng n? Ano ang ibig sabihin ng wakas?
[Dalawang mag-aaral nagsasalita nang sabay-sabay - hindi maintindihan] >> Oo.
Omega mo ay maaaring sa tingin ng bilang sa mas mababang nakatali.
>> Kaya hindi mahalaga kung paano mahusay na ang iyong pagpapasok ng-uuri algorithm,
sa kabila ng listahan na nakapasa sa, palaging may upang ihambing ang hindi bababa sa n bagay
o upang umulit sa n bagay.
Bakit na?
[Mag-aaral] Dahil kung ang listahan na pinagsunod-sunod, at pagkatapos ay sa pamamagitan ng unang pag-ulit
maaari ka lamang ginagarantiya na ang unang elemento ay ang hindi bababa sa,
at ang pangalawang pag-ulit ka lamang ginagarantiya ang unang dalawang mga
dahil hindi mo alam na ang natitirang bahagi ng listahan ay pinagsunod-sunod. >> Oo.
Kung pumasa ka sa isang ganap na pinagsunod-sunod sa listahan, sa pinakadulo hindi bababa sa mayroon kang upang pumunta sa lahat ng mga elemento
upang makita na walang kailangang inilipat sa paligid.
Kaya pagpasa sa ibabaw ng listahan at sinasabi oh, ito ay na pinagsunod-sunod,
ito ay imposible para sa iyo na malaman ito pinagsunod-sunod hanggang mong suriin ang bawat elemento
upang makita na sila sa pinagsunod-sunod pagkakasunod-sunod.
Kaya ang mas mababang sumunod sa pagpapasok ng-uuri ay Omega ng n.
Ano ang pinakamasama kaso tumatakbo ang oras ng pagsasama-uuri,
pinakamasama kaso pagiging ang malaking O muli?
Kaya sa pinakamasama kaso sitwasyon, paano pagsasama-uuri tatakbo?
[Mag-aaral] N log n. >> Oo.
Ang pinakamabilis na pangkalahatang pag-uuri algorithm n log n. Hindi mo maaaring gawin mas mahusay.
>> May mga espesyal na mga kaso, at kung kami ay may oras ngayon - ngunit namin marahil won't -
maaari naming makita na gumagana ang mas mahusay kaysa sa n log n.
Ngunit sa pangkalahatang kaso, hindi mo maaaring gawin mas mahusay kaysa sa n log n.
At sumanib-uri-uriin ang mangyayari na ang isa na dapat mong malaman para sa kurso na n log n.
At kaya ipapakita namin aktwal na pagpapatupad na ngayon.
At sa wakas, sa hindi hihigit sa tatlong mga pangungusap, kung paano gumagana ang pagpili-uuri?
Gusto ba ang isang tao upang sagutin, at makikita ko ang bilang ng iyong mga pangungusap
dahil kung kang pumunta ng lagpas 3 -
Ba ang sinuman tandaan ang pagpili-uuri?
Ang Pinili-uuri ay karaniwang medyo madaling tandaan mula sa pangalan.
Mo lang umulit sa ibabaw ng array, hanapin ang anuman ang pinakamalaking halaga o pinakamaliit -
sa anumang pagkakasunod-sunod na iyong pag-uuri-uri.
Kaya sabihin nating namin ang pag-uuri-uri mula sa pinakamaliit sa pinakamalaking.
Kang umulit sa ibabaw ng array, na naghahanap para sa anumang ang minimum na elemento ay,
piliin ito, at pagkatapos lamang magpalitan anumang sa unang lugar.
At pagkatapos ay sa ikalawang pass sa ibabaw ng array, hanapin muli ang minimum na elemento,
piliin ito, at pagkatapos ay i-swap ang mga ito sa kung ano ang sa pangalawang posisyon.
Kaya lamang namin ay pagpili at pagpili ng ang minimum na halaga
at pagpasok sa mga ito sa harap ng array hanggang ito ay pinagsunod-sunod.
Mga tanong sa na?
>> Mga hindi maaaring hindi lumitaw sa form na mayroon kang upang punan kapag ikaw ay nagsusumite ang pset.
Iyon ang isa lamang na ang mga sagot sa mga.
Okay, kaya ngayon coding ng mga problema.
Ko na ipapadala sa pamamagitan ng email - ba sinuman na hindi makakuha ng email na iyon? Okay.
Ko na ipapadala sa email ang espasyo na kami ay pagpunta sa gumagamit,
at kung ikaw ay mag-click sa aking pangalan - kaya tingin ko ako pagpunta sa ibaba
dahil ng paurong r - ngunit kung nag-click ka sa aking pangalan makakakita ka ng 2 mga pagbabago.
Rebisyon 1 na ako na kopyahin at ilagay ang code sa espasyo
para sa mga bagay ng paghahanap ay pagpunta upang ipatupad.
At Rebisyon 2 ay ang uri ng bagay na namin ipatupad pagkatapos na.
Kaya maaari mong i-click sa aking Rebisyon 1 at gumana mula doon.
At ngayon ay gusto naming ipatupad ang binary paghahanap.
>> Ba ang sinuman nais lamang magbigay ng isang pseudocode mataas na antas na paliwanag
ng kung ano ang kami ay pagpunta sa gawin para sa paghahanap? Oo.
[Mag-aaral] mo lang sa gitna ng array at makita kung ano ang iyong hinahanap para sa
ay mas mababa kaysa sa o higit pa kaysa sa.
At kung ito ay mas kaunti, mas mong pumunta sa kalahati na mas,
at kung ito ay higit pa, pumunta ka sa kalahati na mas at ulitin mo na hanggang sa ikaw ay makakuha ng isang bagay.
[Bowden] Oo.
Pansinin na ang aming numero ng array na pinagsunod-sunod,
at sa gayon ay nangangahulugan na maaari naming samantalahin ng na at maaaring suriin muna namin,
okay, Naghahanap ako para sa bilang na 50.
Sa gayon ay maaari kong pumunta sa gitna.
Gitnang mahirap upang tukuyin kapag ito ay isang kahit na bilang ng mga bagay,
ngunit sabihin lamang sabihin lagi naming truncate sa gitna.
Kaya dito mayroon kaming 8 bagay, kaya gitna ay 16.
Naghahanap ako para sa 50, kaya 50 ay mas malaki kaysa sa 16.
Kaya ngayon ko talaga tinatrato ang aking array sa bilang ng mga sangkap na ito.
Ko itapon ang lahat mula 16 sa paglipas ng.
Ngayon ang aking array lamang ang 4 na elemento, at ulitin ko.
Kaya pagkatapos Gusto kong makahanap muli sa gitna, na kung saan ay pagpunta sa 42.
42 ay mas mababa sa 50, kaya ko itapon ang dalawang mga elemento.
Ito ang aking natitirang array.
Ako pagpunta upang mahanap muli ang gitna.
Hulaan ko 50 ay isang masamang halimbawa dahil palagi ko ay itsa bagay sa kaliwa,
ngunit sa pamamagitan ng ang parehong sukatan, kung ako naghahanap para sa isang bagay
at ito ay mas mababa kaysa sa elemento Kasalukuyan Naghahanap ako sa,
pagkatapos ay ako pagpunta upang itapon ang lahat sa kanan.
Kaya ngayon ay kailangan naming ipatupad na.
Pansinin na kailangan namin upang pumasa sa laki.
Maaari din namin hindi kailangan na hard-code na laki.
Kaya kung makuha namin mapupuksa ng na # tukuyin -
Okay.
Paano ko mabuti malaman kung ano ang laki ng array numero kasalukuyang?
>> Gaano karaming mga elemento sa array numero?
[Mag-aaral] Numero, bracket,. Haba?
[Bowden] Iyon ay hindi umiiral sa C.
Kailangan. Haba.
Array ay hindi magkaroon ng mga ari-arian, kaya may walang ari-arian ng haba ng array
na lang magbibigay sa iyo gayunpaman mahaba ang mangyayari upang maging.
[Mag-aaral] Tingnan kung gaano karaming memory mayroon itong at hatiin sa pamamagitan ng kung magkano - >> Oo.
Kaya kung paano namin makita kung gaano karaming memory mayroon itong? >> [Mag-aaral] Sizeof. >> Oo, sizeof.
Sizeof ay ang operator na ibalik ang laki ng array numero.
At na pagpunta sa gayunpaman maraming integer may mga beses ang laki ng isang integer
dahil na ang kung gaano karaming memory na aktwal na ito tumatagal.
Kaya kung gusto ko ang bilang ng mga bagay sa array,
pagkatapos ay ako pagpunta sa gusto mong hatiin ng laki ng isang integer.
Okay. Kaya na ay nagbibigay-daan sa akin pumasa sa laki dito.
Bakit ko kailangan upang pumasa sa laki sa lahat?
Bakit hindi ko lang gawin dito int laki = sizeof (mandala ng dayami) / sizeof (int)?
Bakit ito hindi gumagana?
[Mag-aaral] Ito ay hindi isang pandaigdigang variable.
Mandala ng dayami [Bowden] umiiral at kami ay pagpasa sa mga numero bilang mandala ng dayami,
at ito ay uri ng isang foreshadowing ng kung ano ang darating. Oo.
[Mag-aaral] mandala ng dayami ang reference dito, kaya ito bumalik kung paano malaki ang reference na.
Oo.
Pagdudahan ko sa panayam na nakita mo stack ang talaga, i-right?
Sinasalita namin ang tungkol dito.
Kaya stack ay kung saan ang lahat ng iyong mga variable ay pagpunta sa ay naka-imbak.
>> Anumang memory na inilalaan para sa mga lokal na variable ay pagpunta sa stack,
at mga function na ang bawat nakakakuha ng sarili nitong lugar sa stack, sariling stack frame nito ay kung ano ang tawag.
Kaya pangunahing may stack frame nito, at sa loob nito na umiiral ang mga numero ng array,
at ito ng laki sizeof (mga numero).
Ito ay pagpunta sa laki ng mga numero na hinati sa pamamagitan ng laki ng mga elemento,
ngunit na ang lahat ng buhay sa loob ng stack frame pangunahing.
Kapag tinatawag naming paghahanap, paghahanap nakakakuha ng sariling stack frame nito,
sarili nitong puwang upang mag-imbak ang lahat ng mga lokal na variable.
Ngunit ang mga argumento - kaya mandala ng dayami ay hindi isang kopya ng buong array na ito.
Hindi namin pumasa sa buong array bilang isang kopya sa paghahanap.
Mayroon lamang ang nagpapasa ng isang reference sa array na.
Kaya paghahanap ay maaaring ma-access ang mga bilang na ito sa pamamagitan ng reference.
Pa rin ito-access ang mga bagay na nakatira sa loob ng stack frame pangunahing,
ngunit isa lamang, kapag makuha namin sa mga payo, na dapat na sa lalong madaling panahon,
ito ay kung ano ang payo ay.
Payo lamang ang mga sanggunian sa mga bagay, at maaari mong gamitin ang mga payo upang ma-access ang mga bagay
na sa frame ng stack ng iba pang mga bagay '.
Kaya kahit numero lokal sa pangunahing, maaari pa rin namin itong ma-access sa pamamagitan ng pointer.
Ngunit dahil lamang pointer at ito ay isang reference lamang,
sizeof (mandala ng dayami) lamang nagbabalik ang laki ng sanggunian mismo.
Hindi ito ibalik ang laki ng bagay na ito na tumuturo sa.
Ito ay hindi ibalik ang aktwal na laki ng mga numero.
At kaya ito ay hindi pagpunta upang gumana bilang gusto naming ito sa.
>> Mga tanong sa na?
Ay nawala ang mga payo sa sa makabuluhang mas madugo detalye sa linggo darating.
At ito ay kung bakit ang isang maraming ng mga bagay na nakikita mo, karamihan sa mga search bagay o-uuri ng mga bagay,
sila ay halos lahat ng pagpunta sa kailangan ang aktwal na laki ng array,
dahil sa C, wala kaming ideya kung ano ang laki ng array ay.
Kailangan mo upang mano-manong pumasa ito.
At hindi manu-mano mong maaaring pumasa sa buong array dahil ka pagpasa sa ang reference
at hindi ito maaaring makuha ang laki mula sa reference.
Okay.
Kaya ngayon gusto naming ipatupad kung ano ay ipinaliwanag bago.
Maaari kang gumawa sa ito para sa isang minuto,
at hindi mo na kailangang mag-alala tungkol sa pagkuha ng lahat ng perpektong 100% gumagana.
Magsulat lamang ang kalahati pseudocode para sa kung paano sa tingin mo ito ay gagana.
Okay.
Hindi na kailangang ganap na tapos na ito.
Ngunit ang sinuman kumportable sa kung ano ang mayroon silang sa ngayon,
tulad ng isang bagay na kami sa sama-sama?
Ba ang sinuman nais magboluntaryo? O ko random pick.
Hindi ito sa pamamagitan ng anumang panukalang ngunit ang isang bagay na maaari naming baguhin sa estado ng nagtatrabaho.
[Mag-aaral] Oo naman. >> Okay.
Sa gayon maaari mong i-save ang mga rebisyon sa pamamagitan ng pag-click sa maliit na icon ng I-save.
Ikaw Ramya, karapatan? >> [Mag-aaral] Oo. >> [Bowden] Okay.
Kaya ngayon maaari kong tingnan ang iyong mga rebisyon at ang lahat ay maaaring hilahin ang rebisyon.
At dito mayroon kaming - Okay.
Kaya nagpunta Ramya ang recursive na solusyon, na kung saan ay talagang isang wastong solusyon.
Mayroong dalawang mga paraan na maaari mong gawin ito problema.
Maaari mong alinman sa gawin ito iteratively o recursively.
Ay maaari ring gawin ang mga Karamihan sa mga problema na iyong makakaharap na maaaring gawin recursively iteratively.
Kaya dito namin nagawa mo na ito recursively.
>> Ba ang may gusto na tukuyin kung ano ang ibig sabihin nito ay upang gumawa ng isang recursive function na?
[Mag-aaral] Kapag mayroon kang isang function tawagan mismo
at pagkatapos ay tumawag mismo hanggang ito ay sa totoo at tunay. >> Oo.
Isang recursive function na ay isang function na tawag sa mismong.
May tatlong malaking bagay na recursive function na ay dapat magkaroon ng.
Ang una ay malinaw naman, tawag mismo.
Ang pangalawa ay ang pangunahing kaso.
Kaya sa isang punto ang function ay kailangang tumigil sa pagtawag mismo,
at iyon ang kung ano ang base kaso ay para sa.
Kaya dito alam namin na dapat naming itigil, dapat naming magbigay sa aming paghahanap
kapag simula ay katumbas ng pagtatapos - at kami na pumunta sa kung ano ang nangangahulugan iyon.
Ngunit sa wakas, ang huling bagay na mahalaga para sa recursive function:
ang mga function ay dapat sa paanuman paparating ang pangunahing kaso.
Nais kung hindi ka aktwal na pag-update ng anumang bagay kapag gumawa ka ng pangalawang recursive tawag,
kung literal ka lang ng pagtawag sa function na muli gamit ang parehong mga argumento
at walang pangkalahatang variable ay nagbago o anumang bagay,
hindi mo maabot ang base kaso, kung saan ang kaso na masamang.
Ito ay isang walang-katapusang recursion at stack overflow.
Ngunit dito namin makita na update ay nangyayari dahil kami ay nag-a-update simulan + pagtatapos / 2,
naming ina-update ang katapusan argumento dito, nag-update kami sa simula ng argumento dito.
Kaya sa lahat ng recursive tawag Nag-a-update kami ng isang bagay. Okay.
Gusto mong maglakad sa amin sa pamamagitan ng iyong solusyon? >> Oo naman.
Gumagamit ako ng SearchHelp kaya na sa tuwing ako makagawa ng mga function na tawag na ito
Ko ang simula ng kung saan Naghahanap ako para sa array at sa katapusan
kung saan Naghahanap ako sa array.
>> Sa bawat hakbang na kung saan ito sinasabi ito sa gitna elemento, na simula + pagtatapos / 2,
ay na katumbas sa kung ano ang iyong hinahanap namin?
At kung ito ay, pagkatapos ay nakita namin ito, at hulaan ko na maipo pumasa sa ang mga antas ng recursion.
At kung na hindi totoo, pagkatapos naming suriin kung na gitnang halaga ng array ay masyadong malaki,
kung saan tinitingnan namin sa kaliwang kalahati ng array sa pamamagitan ng pagpunta mula sa simula sa gitna index.
At kung hindi man gawin namin ang kalahati ng pagtatapos.
[Bowden] Okay.
Maganda iyan.
Okay, kaya ang ilang ng mga bagay-bagay, at aktwal, ito ay isang napaka-mataas na antas na bagay
na hindi mo na kailangan malaman para sa kursong ito, ngunit ito ay totoo.
Recursive function, palagi kang marinig na hindi sila ng isang masamang pakikitungo
dahil kung tumawag ka recursively iyong sarili masyadong maraming beses, makakakuha ka ng stack overflow
dahil, bilang ko sinabi bago, ang bawat function na ay nakakakuha ng sarili nitong stack frame.
Kaya bawat tawag ng recursive function na nakakakuha ng sariling stack frame nito.
Kaya kung gumawa ka ng 1,000 recursive tawag, makakakuha ka ng 1,000 frame stack,
at mabilis na humantong sa pagkakaroon ng masyadong maraming mga stack frame at masira lang ang mga bagay.
Kaya na ang dahilan kung bakit recursive function pangkalahatang masamang.
Ngunit may ay isang magaling na subset ng mga recursive function na tinatawag buntot-recursive function,
at ito ang mangyayari sa isang halimbawa ng kung saan kung tagatala ang paunawa na ito
at dapat ito, tingin ko - kumalatong kung pumasa ka sa-O2 bandila
ito mapansin ito ay buntot recursive at gumawa ng mga bagay nang mahusay.
>> Ito ay muling gamitin ang parehong frame ng stack nang paulit-ulit para sa bawat recursive tawag.
At kaya dahil ginagamit mo ang parehong frame ng stack, hindi mo kailangang mag-alala tungkol
kailanman stack umaapaw, at sa parehong oras, tulad ng sinabi mo bago,
kung saan sa sandaling bumalik ka totoo, pagkatapos ito ay may upang bumalik ang lahat ng mga frame ng stack
at ang ika-10 na tawag sa SearchHelp ay bumalik sa ika-9, bumalik sa ika-8.
Sa gayon ay hindi kailangang mangyari kapag ang mga function buntot recursive.
At kaya kung bakit ito buntot recursive function na notice na para sa anumang naibigay na pagtawag sa searchHelp
recursive tawag na ito sa paggawa ng kung ano ang ito bumabalik.
Kaya sa unang tawag sa SearchHelp, hindi namin alinman kaagad bumalik false,
agad na nagbabalik ng tunay, o gumawa kami ng recursive tawag sa SearchHelp
kung saan kung ano ang namin ang bumabalik ay kung ano ang tawag na bumabalik.
At hindi namin maaaring gawin ito kung ginawa namin ang isang bagay tulad ng int x = SearchHelp, bumalik x * 2,
lamang ang ilang mga random na pagbabago.
>> Kaya ngayon ito recursive tawag, ito int x = SearchHelp recursive tawag,
hindi na buntot recursive dahil ang aktwal na ito upang bumalik
bumalik sa isang nakaraang stack frame sa gayon ay na nakaraang tawag sa function na
maaaring gawin ng isang bagay sa ang halaga ng return.
Kaya ito ay hindi buntot recursive, ngunit kung ano ang nagkaroon kami bago ay mabuti buntot recursive. Oo.
[Mag-aaral] ay hindi Kung naka-check ang pangalawang kaso base unang
dahil may isang sitwasyon kung saan kapag pumasa ka ito ang argumento
mo na simulan = pagtatapos, ngunit nila ang halaga ng karayom.
Ang mga tanong ay hindi namin maaaring tumakbo sa kaso kung saan pagtatapos ay ang halaga ng karayom
o simulan = pagtatapos, naaangkop, simulan = pagtatapos
at hindi mo aktwal na check sa partikular na halaga,
pagkatapos ay simulan ang + pagtatapos / 2 ay lamang pagpunta sa parehong halaga.
Ngunit na namin ibinalik mali at hindi namin aktwal check ang halaga.
Kaya sa pinakadulo hindi bababa sa, sa unang tawag, kung ang laki ay 0, pagkatapos ay nais naming upang bumalik false.
Ngunit kung ang laki ay 1, pagkatapos ng pagsisimula ay hindi pagpunta sa katumbas ng pagtatapos,
at kami na hindi bababa sa suriin ang isang elemento.
Ngunit tingin ko na ikaw ay pakanan sa maaari naming magtapos sa isang kaso kung saan simulan + pagtatapos / 2,
simula nagtatapos up ang parehong bilang simula + pagtatapos / 2,
ngunit hindi namin hindi aktwal na check elemento na.
>> Kaya kung namin suriin muna ang ang gitnang elemento ang halaga na kaming naghahanap ng mga,
maaari agad naming nagbabalik ng tunay.
Iba Pa kung sila ay pantay-pantay, at pagkatapos ay walang punto sa magpatuloy
dahil lamang namin ay pagpunta upang i-update sa isang kaso na kung saan kami ay sa isang solong-element array.
Kung iisang elemento ay hindi kaming naghahanap ng mga,
pagkatapos ay ang lahat ng bagay ay mali. Oo.
[Mag-aaral] bagay ay na dahil laki ay talagang mas malaki kaysa sa bilang ng mga elemento sa array,
ay offset - >> Kaya ay laki -
[Mag-aaral] Sabihin kung ang array ang laki 0, pagkatapos ang SearchHelp ang talagang suriin ang mandala ng dayami na 0
sa unang tawag.
Array ay may laki 0, kaya 0 ang - >> Oo.
Mayroong isa pang bagay na - maaari itong maging mahusay. Natin sa tingin.
Kaya kung ang array ay may 10 mga elemento at gitna na kami ay pagpunta upang suriin ang index 5,
kaya kami ay check 5, at sabihin nating ang halaga ay mas mababa.
Kaya namin ang ibinabato lahat ang layo mula sa 5 pasulong.
Kaya simulan ang + pagtatapos / 2 na ang aming bagong pagtatapos,
kaya oo, palagi itong pagpunta upang manatili higit sa dulo ng array.
Kung ito ang kaso kung ito ay kahit o kakaibang, pagkatapos ay namin check, sabihin nating, 4,
ngunit pa namin ang itsa -
Kaya oo, ang pagtatapos ay palaging pagpunta sa higit sa aktwal na dulo ng array.
Kaya ang mga elemento na kami ay tumututok sa, pagtatapos ay palaging ang isa pagkatapos na.
At kaya kung simula ginagawa kailanman katumbas ng pagtatapos, hindi namin sa isang hanay ng mga laki 0.
>> Ang iba pang mga bagay na ako ay nag-iisip Nag-a-update namin ang simula upang simulan ang + pagtatapos / 2,
kaya ito ang kaso na nagkakaroon ako ng problema sa, kung saan simulan + pagtatapos / 2
ang elemento Sinusuri namin.
Sabihin nating nagkaroon kami ang 10-elemento array. Anuman.
Kaya simulan ang + pagtatapos / 2 ay pagpunta sa isang bagay tulad ng isang ito,
at kung hindi iyon ang halaga, sabihin natin na gusto naming i-update.
Ang halaga ay mas mataas, kaya gusto naming upang tingnan ito kalahati ng array.
Kaya kung paano namin ina-update ang simula, kami ay nag-a-update simula ngayon ito elemento.
Ngunit ito ay maaaring pa rin gumagana, o sa pinakadulo hindi bababa sa, maaari mong gawin ng pagsisimula + pagtatapos / 2 + 1.
[Mag-aaral] Hindi mo na kailangan upang simulan ang + pagtatapos [hindi marinig] >> Oo.
Na namin ang check ang elementong ito at alam ito ay hindi kaming naghahanap ng mga.
Kaya hindi namin kailangan upang i-update ang pagsisimula ito elemento.
Maaari lang namin laktawan ang mga ito at i-update ang simulan na ito elemento.
At doon ay kailanman kaso ng, sabihin nating, na ito ay pagtatapos,
kaya pagkatapos simulan ito ay, simulan ang + pagtatapos / 2 ay ito,
simulan + pagtatapos - Oo, tingin ko ito magtapos sa walang hangganang recursion.
Ipagpalagay natin na ito ay isang hanay ng mga laki ng 2 o ng isang hanay ng mga laki 1. Tingin ko ito gagana.
Sa kasalukuyan, simula na elemento at pagtatapos ay 1 lampas ito.
Kaya ang elemento na kami ay pagpunta upang suriin ang isang ito,
at pagkatapos ay kapag update namin ang pagsisimula, kami ay nag-a-update simula sa 0 + 1/2,
na upang tapusin sa amin pabalik sa simula ito elemento.
>> Kaya Sinusuri namin ang parehong elemento nang paulit-ulit.
Kaya ito ang kaso kung saan ang bawat recursive tawag ay dapat aktwal na i-update ang isang bagay.
Kaya kailangan namin upang gawin ang simula + pagtatapos / 2 + 1, o iba pang may kaso
kung saan hindi namin aktwal na pag-update ng pagsisimula.
Makita ng lahat ang na?
Okay.
Ba ang sinuman katanungan sa ang solusyon na ito o ng anumang higit pang mga komento?
Okay. Ba ang sinuman na isang umuulit ng solusyon na maaari namin ang lahat ng tumingin sa?
Ba namin ang lahat ng gawin ito recursively?
O ring hulaan ko kung binuksan mo sa kanya, baka mayroon ka masapawan ang iyong nakaraang isa.
Ba awtomatikong i-save? Hindi ako positibo.
Ba ang sinuman na umuulit?
Maaari kaming maglakad sa pamamagitan nito kung hindi.
Ang ideya ay ang parehong.
Umuulit solusyon.
Kami ay pagpunta sa gusto sa isa lamang na gawin ang parehong ideya
kung saan gusto naming subaybayan ng bagong dulo ng array at ang bagong simula ng array
at gawin na paulit-ulit.
At kung kung ano ang namin ang pagpapanatiling track ng bilang sa simula at sa katapusan na magsalubong,
hindi namin ginawa mahanap ito at maaari naming bumalik false.
Kaya paano ang gagawin ko na? Sinuman ay may mga mungkahi o code para sa akin upang makuha ang?
[Mag-aaral] ba ng isang habang loop. >> Oo.
Pagpunta sa gusto mong gawin ang isang loop.
>> Mayroon ka ba code maaari kong makuha ang, o kung ano ang iyong pagpunta sa iminumungkahi?
[Mag-aaral] tingin ko ito. >> Lahat ng karapatan. Na ito ay gumagawa ng mga bagay na mas madali. Ano ang iyong pangalan?
[Mag-aaral] Lucas.
Rebisyon 1. Okay.
Mababang ay kung ano ang aming tinatawag na simulan ang bago.
Up ay hindi lubos kung ano ang aming tinatawag na pagtatapos bago.
Aktwal na, ang pagtatapos na ngayon sa loob ng array. Ang isang elemento na dapat naming isaalang-alang.
Kaya mababa 0, hanggang ang laki ng array - 1,
at ngayon kami ay looping, at kami ay check -
Hulaan ko maaari mong maglakad sa pamamagitan nito.
Ano ang iyong pag-iisip sa pamamagitan ng? Maglakad sa amin sa pamamagitan ng iyong code.
[Mag-aaral] Oo naman. Hanapin sa mandala ng dayami na halaga sa gitna at ihambing ang mga ito sa karayom.
Kaya kung ito ay mas mataas kaysa sa iyong karayom, pagkatapos gusto mo - oh, aktwal na, na dapat na paurong.
Ka na gusto mong itapon ang karapatan kalahati, at iba pa oo, na dapat na ang paraan.
[Bowden] Kaya ito ay dapat na mas mababa? Ay na kung ano ang sinabi mo? >> [Mag-aaral] Oo.
[Bowden] Okay. Kaunti.
Kaya kung ano ang namin ang pagtingin sa ay mas maliit kaysa sa kung ano ang gusto naming,
pagkatapos ay oo, gusto naming itapon ang kaliwang kalahati,
na nangangahulugan Nag-a-update namin ang lahat ng isinasaalang-alang namin
sa pamamagitan ng paglipat mababa sa kanan ng array.
Ito mukhang mahusay.
Tingin ko ito ay ang parehong isyu na sinabi namin sa nakaraang,
kung saan kung mababa ay 0 at up ay 1, pagkatapos mababa + up / 2 ay i-set up ang parehong bagay muli.
>> At kahit na hindi ito ang kaso, ito ay pa rin sa mas mahusay na sa pinakadulo hindi bababa sa
lang itapon ang sangkap lang namin tumingin sa kung saan alam namin ang mali.
Kaya mababa + up / 2 + 1 - >> [mag-aaral] Iyon ay dapat na sa iba pang mga paraan.
[Bowden] O ito ay dapat na - 1 at ang iba pang isa ay dapat + 1.
[Mag-aaral] At dapat ay may double equals sign. >> [Bowden] Oo.
[Mag-aaral] Oo.
Okay.
At sa wakas, ngayon na kami ay may ito + 1 - 1 bagay,
ito - maaaring hindi ito - ito kailanman posible para sa mababang upang tapusin na may isang halaga na mas malaki kaysa sa up?
Tingin ko ang tanging paraan na maaaring mangyari - posible? >> [Mag-aaral] Hindi ko alam.
Ngunit kung ito ay nakakakuha ng pinutol at pagkatapos ay nakakakuha ng minus 1 at pagkatapos - >> Oo.
[Mag-aaral] Ito posibleng makapag-messed up.
Tingin ko dapat ito ay mabuti lamang dahil
para dito upang tapusin ang mas mababang sila magiging katumbas, sa tingin ko.
Ngunit kung ang mga ito ay pantay-pantay, at pagkatapos ay hindi namin maaaring gawin habang loop upang simulan na may
at lamang namin ay ibinalik na halaga. Kaya tingin ko hindi namin magandang ngayon.
Pansinin na kahit na ang problemang ito ay hindi na recursive,
ang parehong uri ng mga ideya nalalapat kung saan maaari naming makita kung paano ito kaya lends mismo madali
sa isang recursive na solusyon sa pamamagitan ng katotohanan na lang namin-a-update ka sa mga indeks ng paulit-ulit,
ginagawa namin ang problema mas maliit at mas maliit, kami ay nakatuon sa isang subset ng array.
[Mag-aaral] Kung mababa ay 0 at hanggang ay 1, ang mga ito ay parehong 0 + 1/2, na kung saan ay pumunta sa 0,
at pagkatapos ay isa + 1, ay isa na - 1.
[Mag-aaral] Saan na tayo check ng pagkakapantay-pantay?
Gusto kung ang gitna ay aktwal na karayom?
Hindi namin kasalukuyang ginagawa na? Oh!
Kung it's -
Oo. Hindi lamang namin gawin ang mga pagsubok pababa dito dahil sabihin nating ang unang gitna -
[Mag-aaral] aktwal Ito ay bang hindi itapon ang bound.
Kaya kung itapon ang bound, mayroon kang suriin muna ito o anumang.
Ah. Oo. >> [Mag-aaral] Oo.
Kaya ngayon namin itinapon ang kasalukuyan naming tumingin sa,
na nangangahulugan na kailangan namin ngayon ay mayroon ding
kung (mandala ng dayami [(mababang + up) / 2] == karayom), pagkatapos ay maaari naming nagbabalik ng tunay.
At kung ko bang ilagay ang tao o lamang kung, ito ay nangangahulugan na literal ang parehong bagay
dahil ito ay ibinalik totoo.
Kaya makikita ko bang ilagay ang tao kung, ngunit hindi mahalaga.
>> Kaya tao kung ito, tao na ito, at ito ay isang karaniwang bagay na gagawin ko
kung saan kahit kung ito ay sa kaso kung saan ang lahat ng bagay ay handa na dito,
tulad ng mababa hindi kailanman maaaring maging mas malaki kaysa up, hindi nagkakahalaga ng pagdadahilan tungkol sa kung na totoo.
Kaya maaari mong pati na rin sabihin habang mababa ay mas mababa sa o katumbas ng
o habang mababa ay mas mababa sa
kaya kung ang mga ito ay kailanman katumbas o mababa ang mangyayari upang pumasa sa up,
maaari naming masira labas ng loop na ito.
Mga katanungan, mga alalahanin, mga komento?
Okay. Ito mukhang mahusay.
Ngayon gusto naming gawin-uuri.
Kung pumunta kami sa aking pangalawang rebisyon, makikita namin ang parehong mga numero,
ngunit ngayon ang mga ito ay hindi na sa pinagsunod-sunod pagkakasunod-sunod.
At gusto naming ipatupad ng-uuri sa paggamit ng anumang algorithm sa O ng n log n.
Kaya kung saan algorithm tingin mo dapat naming ipatupad dito? >> [Mag-aaral] magsamang bumaybay-uuri.
[Bowden] Oo. Pagsamahin-uuri ay O (n log n), kaya na kung ano ang kami ay pagpunta sa gawin.
At ang problema ay medyo katulad,
kung saan ito lends mismo madali sa isang recursive na solusyon.
Maaari din namin makabuo ng isang umuulit na solusyon kung gusto namin,
ngunit recursion ay madali dito at dapat namin gawin recursion.
Hulaan ko namin ang maglakad sa pamamagitan ng pagsasama-uuri unang,
kahit na mayroong isang magandang video sa pagsasama-uuri na. [Tawa]
Kaya sumanib-uuri may - aksaya ako kaya magkano ng ang papel na ito.
Oh, mayroon lamang isang kaliwa.
Kaya sumanib.
Oh, 1, 3, 5.
Okay.
Sumanib tumatagal ng dalawang magkahiwalay na array.
Indibidwal na mga dalawang array ay parehong pinagsunod-sunod.
Kaya ito array, 1, 3, 5, pinagsunod-sunod. Ito array, 0, 2, 4, pinagsunod-sunod.
Ngayon kung ano sumanib dapat gawin ay pagsamahin ang mga ito sa isang solong array na mismo pinagsunod-sunod.
Kaya gusto namin ang isang hanay ng mga laki 6 na pagpunta sa mga elementong ito sa loob nito
sa pinagsunod-sunod pagkakasunod-sunod.
>> At upang maaari naming samantalahin ng katotohanan na ang mga ito ng dalawang array ay pinagsunod-sunod
upang gawin ito sa linear oras,
linear oras kahulugan kung ang array na ito ay ang laki x at ito ang laki y,
pagkatapos ay ang kabuuang algorithm ay dapat na O (x + y). Okay.
Kaya mungkahi.
[Mag-aaral] ma namin simulan mula sa kaliwa?
Kaya makikita mo ilagay ang 0 down na una at pagkatapos ay ang 1 at pagkatapos dito sa 2.
Kaya ito ay uri ng tulad ng mayroon ka ng isang tab na lumilipat sa kanan. >> [Bowden] Oo.
Para sa parehong ng mga array kung tumuon lamang namin sa pinakakaliwa elemento.
Dahil parehong mga array ay pinagsunod-sunod, alam namin na ang mga 2 elemento
ay ang pinakamaliit na mga elemento sa alinman sa array.
Kaya na nangangahulugan na ang 1 ng mga 2 elemento ay dapat na ang pinakamaliit na elemento sa aming naka-merge na array.
Lang kaya ang mangyayari na ang pinakamaliit na ang isa sa tamang oras na ito.
Kaya tumagal namin 0, ipasok ito sa kaliwa dahil 0 ay mas mababa sa 1,
kaya tumagal 0, ipasok ito sa aming unang posisyon, at pagkatapos ay i-update namin ito
ngayon tumutok sa unang elemento.
At ngayon namin ulitin.
Kaya ngayon namin ihambing ang 2 at 1. 1 ay mas maliit, kaya ipapakita namin ipasok 1.
Naming i-update ang pointer upang ituro sa tao na ito.
Ngayon ginagawa namin itong muli, kaya 2. Na ito ay mag-a-update, ihambing ang mga 2, 3.
Ito update, pagkatapos ay 4 at 5.
Kaya na pagsasama.
>> Dapat ito ay medyo halata na ito ay linear oras dahil pumunta lamang namin ang buong bawat elemento nang isang beses.
At iyon ay ang pinakamalaking hakbang sa pagpapatupad ng pagsasama-uuri ay ginagawa ito.
At ito ay hindi na mahirap.
Ilang bagay na mag-alala tungkol Ipagpalagay natin na tayo ay pinagsasama ang 1, 2, 3, 4, 5, 6.
Sa kasong ito namin magtapos sa sitwasyon kung saan ang isang ito ay mas maliit,
pagkatapos naming i-update ang pointer, ang isang ito ay mas maliit, i-update ito,
ito ang mas maliit, at ngayon ay mayroon kang makilala
kapag aktwal na iyong maubusan ng mga elemento upang ihambing.
Dahil na namin ginagamit ang buong array,
lahat sa array na ito na ngayon lamang ipinasok sa dito.
Kaya kung namin tumakbo sa punto kung saan ang isa sa aming mga array ay ganap na Pinagsama,
pagkatapos lang ang dadalhin namin ang lahat ng mga elemento ng iba pang mga array at ipasok ang mga ito sa dulo ng array.
Upang maaari naming lamang magpasok ng 4, 5, 6. Okay.
Ito ay isang bagay upang panoorin ang para sa.
Pagpapatupad na dapat na hakbang 1.
Pagsamahin ang uri-uriin pagkatapos batay sa na, 2 hakbang, 2 ulok hakbang.
Sabihin lang bigyan ang array na ito.
Kaya sumanib-uuri, ang hakbang 1 sa recursively masira ang hanay sa mga halves.
Kaya nahati ang array na ito sa halves.
Na kami ngayon 4, 15, 16, 50 at 8, 23, 42, 108.
At ngayon ginagawa namin itong muli at hatiin namin ito sa halves.
Lamang ko makikita gawin ito sa bandang ito.
Kaya 4, 15 at 16, 50.
Gusto naming gawin ang parehong bagay sa paglipas dito.
At ngayon namin hatiin ito sa halves muli.
At mayroon kaming 4, 15, 16, 50.
Kaya na ang aming base kaso.
Kapag ang mga array ng laki 1, pagkatapos namin itigil ang paghahati ng pang-halves.
>> Ngayon kung ano ang namin na ito?
Kami magtapos ito ay masira sa 8, 23, 42, at 108.
Kaya ngayon na hindi namin sa puntong ito, ngayon hakbang dalawang ng pagsasama-uuri ay lamang pinagsasama ng mga pares sa listahan.
Kaya gusto namin upang sumanib mga. Lang namin tawagan sumanib.
Alam namin na ang pagsasama ay bumalik ito sa pinagsunod-sunod pagkakasunod-sunod.
4, 15.
Ngayon nais namin upang sumanib mga ito, at na ay magbabalik ng isang listahan sa mga pinagsunod-sunod pagkakasunod-sunod,
16, 50.
Bumaybay namin mga - hindi ako sumulat - 8, 23 at 42, 108.
Kaya mayroon kami ng mga naka-merge na pares sabay-sabay.
Ngayon lang namin sumanib muli.
Pansinin na ang bawat isa sa mga listahang ito ay pinagsunod-sunod sa mismong,
at pagkatapos ay maaari naming lamang sumanib ang mga listahang ito upang makakuha ng isang listahan ng mga laki 4 na pinagsunod-sunod
at sumanib sa dalawang mga listahan upang makakuha ng isang listahan ng mga laki 4 na pinagsunod-sunod.
At sa wakas, maaari naming sumanib sa mga dalawang mga listahan ng mga laki 4 upang makakuha ng isang listahan ng mga laki 8 na pinagsunod-sunod.
Kaya upang makita na ito ay pangkalahatang n log n, nakita namin na na pagsasama ay linear,
kaya kapag kami ay pagharap sa pinagsasama ang mga, kaya tulad ng ang kabuuang gastos ng pagsasama
para sa dalawang mga listahan ay 2 dahil -
O mahusay, ito O ng n, ngunit n dito ang 2 elemento, kaya ito ay 2.
At ang mga 2 ay 2 at mga 2 ay 2 at mga 2 ay 2,
ito sa lahat ng merges na kailangan namin upang gawin, magtapos namin ginagawa n.
Tulad ng 2 + 2 + 2 + 2 8, na n,
kaya ang gastos ng pagbubuklod sa set na ito ay n.
At pagkatapos ay ang parehong bagay dito.
Susubukan naming pagsamahin ang mga 2, pagkatapos mga 2, at kanya-kanyang sumanib ito ay tumagal ng apat na pagpapatakbo,
ito sumanib tumagal ng apat na pagpapatakbo, ngunit muli, sa pagitan ng lahat ng mga ito,
magtapos namin pinagsasama n kabuuang mga bagay, at kaya ang hakbang na ito ay tumatagal ng n.
At kaya antas ng bawat isa ay tumatagal ng n elemento na Pinagsama.
>> At kung gaano karaming mga antas?
Sa bawat antas, ang aming array ay lumalaki sa pamamagitan ng laki 2.
Narito aming array ng laki 1, dito sila ng laki 2, narito sila ng laki 4,
at sa wakas, sila ng laki 8.
Kaya dahil ito ay pagdodoble, may pagpunta sa isang kabuuan ng log n ng mga antas na ito.
Kaya sa pag-log n antas, ang bawat indibidwal na antas pagkuha n kabuuang pagpapatakbo,
makuha namin ang isang n log n algorithm.
Mga tanong?
Na-ng mga tao na gumawa ng progreso sa kung paano ipatupad ang?
Sinuman na sa isang estado na kung saan maaari ko lamang makuha ang kanilang mga code?
Maaari ko bang magbigay ng isang minuto.
Ito ay pagpunta sa na.
Ko lubos na inirerekomenda magbalik -
Hindi mo kailangang gawin ang recursion para sa pagsasama
dahil gawin recursion para sa pagsasama, ka upang pumasa ang isang grupo ng mga iba't ibang laki.
Maaari mong, ngunit ito ay nakakainis.
Ngunit recursion-uri-uriin mismo ay medyo madali.
Mo lang literal tumawag uri sa kaliwang kalahati,-uuri sa kanang kalahati. Okay.
Sinuman ay may anumang bagay na maaari kong makuha ang pa?
O tao Bibigyan kita ng isang minuto.
Okay.
Sinuman ay may isang bagay na maaari naming?
O kaya makikita lang namin na ito at pagkatapos ay palawakin mula doon.
>> Sinuman ay may higit pa kaysa sa na maaari kong makuha ang?
[Mag-aaral] Oo. Maaari mong makuha ang mina. >> Lahat ng karapatan.
Oo!
[Mag-aaral] May ng maraming ng mga kondisyon. >> Oh, shoot. Maaari mong -
[Mag-aaral] kailangan ko upang i-save ang mga ito. >> Oo.
Kaya ginawa namin gawin ang sumanib sa hiwalay.
Oh, ngunit ito ay hindi na masamang.
Okay.
Kaya-uuri ay mismo lamang pagtawag mergeSortHelp.
Ipaliwanag sa amin kung ano ang mergeSortHelp ginagawa.
[Mag-aaral] MergeSortHelp medyo magkano ang ipinapakita ng dalawang pangunahing mga hakbang,
na upang pag-uri-uriin ang bawat kalahati ng array at pagkatapos ay upang sumanib ang parehong sa kanila.
[Bowden] Okay, kaya ninyo ako ng isang segundo.
Sa tingin ko ito - >> [mag-aaral] Kailangan ko bang -
Oo. Ako nawawalang ng isang bagay.
Sa pagsasama, Napagtanto ko na kailangan ko upang lumikha ng isang bagong array
dahil hindi ko maaaring gawin ito sa lugar. >> Oo. Hindi ka maaari. Iwasto.
[Mag-aaral] Kaya kong lumikha ng isang bagong array.
Nakalimutan ko ang sa dulo ng sumanib muling baguhin.
Okay. Kailangan namin ng isang bagong array.
Sa pagsasama-uuri, ito ay halos palaging totoo.
Bahagi ng gastos ng isang mas mahusay na oras na matalino algorithm
ay halos palaging nangangailangan gamitin ng kaunti pang memory.
Kaya dito, kahit na kung paano ito gawin sumanib uri,
ay hindi maaaring hindi mo kailangan upang gamitin ang ilang dagdag na memorya.
Niya nilikha ang isang bagong array.
At pagkatapos ay sabihin sa dulo kailangan lang namin upang kopyahin ang bagong array sa orihinal na array.
[Mag-aaral] tingin ko ito, oo.
Hindi ko alam kung na gumagana sa mga tuntunin ng pagbibilang sa pamamagitan ng reference o anumang -
Oo, ito gumagana. >> [Mag-aaral] Okay.
Ang ibig mo bang subukang patakbuhin ito? >> [Mag-aaral] Hindi, hindi pa. >> Okay.
Subukang patakbuhin ito, at pagkatapos ay kukunin ko na makipag-usap tungkol dito para sa isang segundo.
[Mag-aaral] Kailangan ko ang lahat ng mga modelo ng function na at ang lahat, bagaman, i-right?
Ang mga modelo ng function na. Oh, ibig sabihin tulad ng - Oo.
-Uri-uriin ang pagtawag mergeSortHelp.
>> Kaya sa order para sa uri sa tawagan ang mergeSortHelp, mergeSortHelp dapat alinman na-tinukoy
bago-uuri o kailangan lang namin ang prototype. Kopyahin lamang at i-paste na.
At katulad, pagtawag ng mergeSortHelp ay pagsamahin
ngunit sumanib ay hindi pa tinukoy, sa gayon maaari naming ipaalam lamang sa mergeSortHelp alam
na iyon ang bumaybay ay pagpunta sa hitsura, at na na.
Kaya mergeSortHelp.
Mayroon kaming isang isyu dito kung saan mayroon kaming walang batayang kaso.
MergeSortHelp ay recursive, kaya ang anumang recursive function na
ay pagpunta sa kailangan ang ilang mga uri ng mga kaso ng base sa alam kapag upang itigil recursively pagtawag mismo.
Ano ang aming base kaso ng pagpunta sa na dito? Oo.
[Mag-aaral] Kung laki ay 1? >> [Bowden] Oo.
Kaya tulad ng nakita natin doon, huminto kami ng mga array paghahati ng pang-
sabay-sabay namin nakuha sa mga array ng laki 1, na kung saan ay hindi maaaring hindi pinagsunod-sunod ang kanilang mga sarili.
Kaya kung laki katumbas 1, alam namin array ay na pinagsunod-sunod,
upang maaari naming lamang bumalik.
>> Mapansin na walang bisa, kaya hindi namin bumalik anumang partikular, namin lamang bumalik.
Okay. Upang ang aming base kaso.
Ako hulaan ang aming base kaso maaari rin kung mangyari namin pinagsasama ang isang hanay ng mga laki 0,
marahil namin nais na huminto sa ilang mga punto,
upang maaari naming sabihin na ang laki mas mababa sa 2 o mas mababa sa o katumbas ng 1
kaya na ito ay gumana para sa anumang array sa ngayon.
Okay.
Upang ang aming base kaso.
Ngayon ang gusto mong maglakad sa amin sa pamamagitan ng pagsasama?
Ano ang ibig sabihin ng lahat ng mga kasong ito?
Up dito, kami ay paggawa ng parehong ideya, ang -
[Mag-aaral] Kailangan ko na pagpasa laki sa lahat ng mga tawag mergeSortHelp.
Nagdagdag ako laki bilang isang karagdagang pangunahing at hindi doon, tulad ng laki / 2.
[Bowden] Oh, laki / 2, laki / 2. >> [Mag-aaral] Oo, at din sa itaas function na pati na rin.
[Bowden] Narito? >> [Mag-aaral] lang laki. >> [Bowden] Oh. Laki, laki? >> [Mag-aaral] Oo.
[Bowden] Okay.
Hayaan akong-isip para sa pangalawang.
Ba naming tumakbo sa isang isyu?
Palagi kaming pagpapagamot sa kaliwa bilang 0. >> [Mag-aaral] No.
Na ang mali. Sorry. Dapat itong maging simula. Oo.
[Bowden] Okay. Gusto ko na mas mahusay.
At pagtatapos. Okay.
Kaya ngayon ang gusto mong maglakad sa amin sa pamamagitan ng pagsasama? >> [Mag-aaral] Okay.
Lang ako sa paglalakad sa pamamagitan ng bagong array na ito na aking nilikha.
Ang laki nito ay ang laki ng bahagi ng array na gusto namin na pinagsunod-sunod
at sinusubukan upang mahanap ang mga elemento na dapat kong ilagay sa bagong array hakbang.
Kaya upang gawin iyon, unang ako check kung ang kaliwang kalahati ng array ay patuloy upang magkaroon ng anumang higit pang mga elemento,
at kung ito ay hindi, pagkatapos mong pumunta down na pang tao na kondisyon, na lang sabi
okay, dapat ito ay sa tamang array, at maglalagay kami na sa kasalukuyang index ng newArray.
>> At pagkatapos ay kung hindi man, ako check kung ang kanang bahagi ng array din tapos,
kung saan ko lang ilagay sa kaliwa.
Na hindi maaaring aktwal na kinakailangan. Hindi ako sigurado.
Ngunit pa rin, ang iba pang dalawang check kung alin sa dalawang mas maliit sa kaliwa o kanan.
At din sa bawat kaso, ako incrementing alinman placeholder ko dagdagan.
[Bowden] Okay.
Na mukhang mabuti.
Ba ang sinuman na may mga komento o mga alalahanin o mga tanong?
Kaya ang apat na mga kaso na mayroon kaming upang dalhin ang mga bagay lamang pagiging - o mukhang limang -
ngunit mayroon kaming upang isaalang-alang kung ang kaliwang array ay maubusan ng mga bagay na kailangan namin upang sumanib,
kung ang kanan array ay maubusan ng mga bagay na kailangan namin upang sumanib -
Pagturo ako sa wala.
Kaya kung ang kaliwang array ay tumakbo na ng mga bagay o ang karapatan na array ay maubusan ng mga bagay.
Iyon ang dalawang mga kaso.
Kailangan din namin ang trivia kaso kung ang kaliwang bagay ay mas mababa ang mga tamang bagay.
Pagkatapos gusto naming pumili ng kaliwang bagay.
Iyon ang mga kaso.
Kaya ito ay karapatan, kaya na na.
Array natitira. 1, 2, 3. Okay. Kaya oo, mga sa apat na mga bagay na maaari naming nais gawin.
At hindi namin ay pumunta sa isang umuulit solusyon.
Hindi ko inirerekomenda -
Pagsamahin-uuri ay isang halimbawa ng isang function na ay parehong hindi buntot recursive,
hindi madaling ito buntot recursive,
kundi pati na rin ito ay hindi masyadong madaling upang gawin itong umuulit.
Ito ay napakadali.
Ang pagpapatupad ng pagsasama-uuri,
pagsamahin, hindi mahalaga kung ano ang ginagawa mo, ikaw ay pagpunta sa bumuo ng pagsasama.
>> Kaya sumanib recursively-uuri na itinayo sa tuktok ng pagsasama lamang ang tatlong linya.
Iteratively, ito ay mas nakakainis at mas mahirap na isipin ang tungkol.
Ngunit mapansin na ito ay hindi buntot recursive dahil mergeSortHelp - kapag ito tawag mismo -
pa rin ito kailangang gawin ang mga bagay pagkatapos ito recursive tawag babalik.
Kaya stack frame na ito ay dapat patuloy na umiiral kahit na matapos pagtawag na ito.
At pagkatapos ay kapag tumawag ka ito, ang stack frame ay dapat patuloy na umiiral
dahil kahit na pagkatapos na tawag, kailangan pa rin namin upang sumanib.
At ito ay nontrivial buntot ito recursive.
Mga tanong?
Ayos lang.
Kaya pagpunta bumalik upang ayusin - oh, mayroong dalawang mga bagay na gusto kong ipakita. Okay.
Pagpunta pagbukud-, makikita namin gawin ito mabilis.
O paghahanap. -Uri-uriin? Sort. Oo.
Pagpunta sa Beginnings ng-uuri.
Gusto naming lumikha ng isang algorithm na uri ang array gamit ang anumang algorithm
sa O ng n.
Kaya paano ito posible? Ba ang sinuman anumang uri ng -
Hinted ko bago sa -
Kung hindi namin upang mapabuti ang mula n log n sa O ng n,
napabuti namin ang ang aming algorithm oras-matalino,
na nangangahulugan na kung ano ang kami pagpunta sa kailangan upang gawin upang gumawa ng up para sa?
[Mag-aaral] Space. >> Oo. Kami ay pagpunta sa paggamit ng mas maraming espasyo.
At hindi kahit lamang ng mas maraming espasyo, exponentially mas maraming espasyo.
Kaya tingin ko ito uri ng algorithm ay palsipikado isang bagay, palsipikado polynom -
palsipikado - hindi ko matandaan. Palsipikado isang bagay.
Subalit dahil kailangan namin upang gamitin kaya magkano espasyo
na ito ay matamo ngunit hindi makatotohanang.
>> At kung paano namin makamit ito?
Maaari naming makamit ang kung gina-garantiya namin na ang anumang partikular na elemento sa array
ay sa ibaba sa isang tiyak na laki.
Kaya hayaan lang sabihin na laki ay 200,
anumang elemento sa isang array sa ibaba laki 200.
At ito ay talagang napaka-makatotohanang.
Maaari mong napaka madaling isang array na alam mo ang lahat ng nasa loob nito
ay pagpunta sa mas mababa kaysa sa ilang bilang.
Gusto kung mayroon kang ilang mga talagang napakalaking vector o isang bagay
ngunit alam mo ang lahat ng pagpunta sa pagitan ng 0 at 5,
ito makabuluhang mas mabilis na gawin ito.
At ang bound sa anumang ng mga elemento ay 5,
kaya ito bound, na kung gaano karaming memory ka pagpunta sa gumagamit.
Kaya ang bound ay 200.
Sa basal ay laging bound dahil may isang integer ay maaari lamang maging hanggang 4 na bilyong,
ngunit hindi makatotohanang dahil nais naming gumagamit espasyo
sa pagkakasunud-sunod ng 4 bilyong. Kaya na hindi makatotohanang.
Ngunit dito makikita namin sabihin ang aming bound ay 200.
Ang panlinlang upang gawin ito sa O ng n naming gumawa ng isa pang array na tinatawag na bilang ng laki bound.
Sa aktwal, ito ay isang shortcut para sa - aktwal ko hindi alam kung kumalatong ito.
Ngunit sa GCC sa pinakadulo hindi bababa sa - I'm ipagpalagay kumalatong ginagawa ito masyadong -
ito ay lamang initialize ang buong array na 0s.
Kaya kung hindi ko nais upang gawin iyon, pagkatapos maaari kong hiwalay para sa (int i = 0;
i <bound; i + +) at bilang [i] = 0;
Kaya ngayon lahat ay nasimulan sa 0.
Ako umulit sa paglipas ng aking array,
at kung ano ako paggawa ay pagbibilang ako ang bilang ng bawat - Hayaan ang pumunta pababa dito.
Mayroon kaming 4, 15, 16, 50, 8, 23, 42, 108.
Ano ako pagbibilang ay ang bilang ng mga pangyayari ng bawat isa sa mga elementong iyon.
Natin ang aktwal na magdagdag ng ilang mas in dito gamit ang ilang mga umuulit.
Kaya ang halaga na mayroon kami dito, ang halaga ng na pagpunta sa array [i].
Kaya Val ay maaaring 4 o 8 o anumang.
At ngayon ako pagbibilang kung gaano karaming ng halagang iyon Nakita ko na,
kaya bilang [Val] + +;
Pagkatapos ito ay tapos na, bilang ay pagpunta upang tumingin ng isang bagay tulad ng 0001.
Natin gawin bilang [Val] - Bound + 1.
>> Ngayon na lang sa account para sa ang katunayan na kami ay nagsisimula mula 0.
Kaya kung 200 ay pagpunta sa aming pinakamalaking bilang,
pagkatapos 0 sa 200 201 bagay.
Kaya bilang, ito hitsura ng 00,001 dahil mayroon kaming isang 4.
Pagkatapos ay magpapadala kami sa 0001 kung saan ipapakita namin magkaroon ng 1 sa ika-8 index ng bilang ng.
Magkakaroon kami ng 2 sa ika-23 na index ng bilang ng.
Magkakaroon kami ng 2 sa 42 index ng bilang ng.
Upang maaari naming gamitin bilang.
Kaya num_of_item = bilang ng [i].
At kaya kung num_of_item ay 2, na nangangahulugan na gusto naming upang ipasok ang 2 ng bilang i
sa aming pinagsunod-sunod array.
Kaya kailangan namin upang subaybayan kung gaano kalayo namin sa array.
Kaya index = 0.
Array - kukunin ko na lang magsulat dito.
Ibinibilang -
array [index + +] = i;
Ay na kung ano ang gusto kong? Tingin ko na kung ano ang gusto kong.
Oo, ito mukhang mahusay. Okay.
Kaya ang lahat maunawaan kung ano ang layunin ng aking mga bilang ng array ay?
Pagbibilang Ito ay ang bilang ng mga pangyayari ng bawat isa sa mga numerong ito.
Pagkatapos ako iterating sa paglipas na bilang ng array,
at ith posisyon sa array bilang
ay ang bilang ng mga i kung na dapat lumitaw sa aking pinagsunod-sunod array.
Iyon ang dahilan kung bakit ang bilang ng 4 ay magiging 1
at bilang na 8 ay pagpunta sa 1, ang mga bilang na 23 ay pagpunta sa 2.
Kaya na kung gaano karami sa mga ito ang gusto ko upang ipasok sa aking pinagsunod-sunod array.
Pagkatapos ko lang gawin iyon.
Ako pagpasok num_of_item i sa aking pinagsunod-sunod array.
>> Mga tanong?
At kaya muli, ito ay linear oras dahil lamang namin ay iterating sa paglipas ng ito sabay-sabay,
ngunit ito rin linear sa kung ano ang bilang na ito ay mangyayari upang maging,
at kaya mabigat ay depende sa kung ano ang iyong bound.
Na may isang bound ng 200, na hindi na masamang.
Kung ang iyong bound ay pagpunta sa 10,000, pagkatapos na ang isang maliit na mas masahol pa,
ngunit kung ang iyong bound ay pagpunta sa may 4 na bilyong, na ganap na hindi makatotohanang
at ang array na ito ng laki 4 bilyong, na hindi makatotohanang.
Kaya na na. Mga tanong?
[Hindi marinig na mag-aaral tugon] >> Okay.
Natanto ko isa pang bagay kapag kami ay pagpunta sa pamamagitan ng.
Tingin ko ang problema ay sa Lucas at marahil bawat solong nasaksihan namin.
Ako ganap na nakalimutan.
Ang tanging bagay na Nais kong magkomento sa ay na kapag ikaw ay pagharap sa mga bagay tulad ng mga indeks,
hindi mo talaga makikita ito kapag sumusulat ka ng para sa loop,
ngunit technically, sa tuwing ikaw ay pagharap sa mga indeks ng,
dapat mong medyo magkano palaging haharapin ang mga unsigned integer.
Ang dahilan para sa ay kapag ikaw ay pagharap sa sign integer,
kaya kung mayroon kang 2 sign integer at mong idagdag ang mga ito nang sama-sama
at magtapos sila masyadong malaki, pagkatapos mo magtapos sa isang negatibong numero.
Kaya na kung ano ang integer overflow.
>> Kung idagdag ko ang 2 bilyong at 1 bilyong, ako magtapos sa negatibong 1 bilyon.
Iyon ay kung paano gumagana ang mga integer sa mga computer.
Kaya ang problema sa gamit -
Iyon ay pinong maliban kung mababa ang mangyayari sa 2 bilyong at mangyayari hanggang 1 bilyon,
pagkatapos ito ay pagpunta sa negatibong 1 bilyon at pagkatapos kami ay pagpunta sa hatiin sa pamamagitan ng 2
at nagtatapos sa negatibong 500 milyong.
Kaya ito ay lamang ng isang isyu kung mangyari na naghahanap sa pamamagitan ng isang array
ng mga bilyun-bilyong ng mga bagay.
Ngunit kung mababa + up ang mangyayari sa pag-apaw, pagkatapos na ang isang problema.
Lalong madaling panahon na ginawa namin ang mga ito unsigned, pagkatapos 2 bilyong plus 1 bilyon ay 3 bilyong.
3 bilyong na hinati sa pamamagitan ng 2 ay 1.5 bilyong.
Ito sa lalong madaling sila unsigned, ang lahat ng bagay ay perpekto.
At kaya na rin ng isyu kapag sumusulat ka sa iyong para sa loop,
at aktwal na, marahil ito ginagawa ito awtomatiko.
Ito ay aktwal na lamang sumigaw sa iyo.
Kaya kung ang bilang na ito ay masyadong malaki upang maging sa isang integer lamang ngunit magkasya sa isang wala pang kontratang integer,
sumigaw sa iyo, kaya na ang dahilan kung bakit hindi mo talaga tumatakbo sa isyu.
Maaari mong makita na ang isang index ay hindi kailanman negatibo,
at kaya kapag ka iterating higit sa isang array,
maaari mong halos palaging sabihin unsigned int i, ngunit hindi mo talagang may sa.
Mga bagay ay gumagana medyo mas lamang pati na rin.
Okay. [Whispers] Anong oras na?
Ang huling bagay na Nais kong upang ipakita - at kukunin ko na lang gawin ito talagang mabilis.
Alam mo kung paano # namin na tukuyin upang maaari naming # tukuyin ang MAX bilang 5 o isang bagay?
Natin hindi gawin ng MAX. # Tukuyin bound ng 200. Kung ano ang ginawa namin bago.
Na tumutukoy sa isang pare-pareho, na kung saan ay lamang ang pagpunta sa kopyahin at ilagay
saanman mangyayari namin na magsulat bound.
>> Upang maaari naming aktwal na makagawa ng higit pa sa # tumutukoy.
Maaari naming # tukuyin ang mga function.
Hindi ito talagang pag-andar, ngunit kami tatawag sa kanila function.
Ang isang halimbawa ay ang isang bagay tulad ng MAX (x, y) ay tinukoy bilang (x <y y:? X). Okay.
Kaya dapat kang masanay sa tatluhan operator syntax,
ngunit x mas mababa sa y? Bumalik y, tao bumalik x.
Sa gayon maaari mong makita na maaari mong gawin ang isang hiwalay na function,
at ang function ay maaaring tulad ng bool MAX ay tumatagal ng 2 argumento, bumalik ito.
Ito ay isa sa mga pinaka-karaniwang mga nakikita ko ginawa tulad nito. Tinatawag namin ang mga ito macros.
Ito ay isang macro.
Ito ay ang syntax para dito.
Maaari kang magsulat ng isang macro upang gawin ang anumang gusto mong.
Ka madalas makita ang mga macros para sa pag-debug ng printfs at bagay-bagay.
Kaya isang uri ng printf, may mga espesyal na mga constants sa C tulad ng salungguhit LINE salungguhit,
2 underscore LINE salungguhit,
at mayroon ding tingin ko 2 underscore FUNC. Na maaaring maging ito. Isang bagay tulad na.
Mga bagay ay pinalitan ng ang pangalan ng function na
o ang bilang ng linya na ikaw ay nasa.
Madalas, isulat mo ang pag-debug ng mga printfs na pababa dito maaari kong magsulat lamang
DEBUG at ito ay i-print ang linya bilang at pag-andar na mangyari ko sa
Nakatagpo na DEBUG statement.
At maaari mo ring i-print ang iba pang mga bagay.
Kaya ang isang bagay na dapat mong panoorin para sa kung mangyayari kong # tukuyin ang DOUBLE_MAX
bilang isang bagay tulad ng 2 * y at 2 * x.
Kaya para sa anumang dahilan, mangyari ka upang gawin iyon ng maraming.
Kaya gawin itong isang macro.
Ito ay talagang nasira.
Gusto ko tawagan ang mga ito sa pamamagitan ng paggawa ng isang bagay tulad ng DOUBLE_MAX (3, 6).
Kaya ano ang dapat ibabalik?
[Mag-aaral] 12.
Oo, 12 dapat ibabalik, at 12 ay ibinalik.
3 ay makakakuha ng papalitan para sa x, 6 ay makakakuha ng papalitan para sa y, at bumalik kami ng 2 * 6, na kung saan ay 12.
Ngayon kung ano ang tungkol dito? Ano ang dapat na ibinalik?
[Mag-aaral] 14. >> May perpektong, 14.
Ang isyu ay kung paano hash tumutukoy sa trabaho, tandaan na ito ay isang literal na kopyahin at i-paste ang
ng medyo magkano ang lahat, kaya kung ano ito ay pagpunta sa kahulugan bilang
3 mas mababa sa 1 plus 6, 2 beses 1 plus 6, 2 beses 3.
>> Kaya para sa kadahilanang ito halos palaging I-wrap ang lahat sa panaklong.
Anumang variable halos palaging pambalot ng naka-panaklong.
May mga kaso kung saan hindi mo na kailangang, tulad ng alam ko na hindi ko kailangan upang gawin iyon dito
dahil mas mababa ay medyo mas laging lamang sa trabaho,
bagaman na hindi maaaring kahit na totoo.
Kung mayroong isang bagay na katawa-tawa tulad ng DOUBLE_MAX (1 == 2),
pagkatapos na pagpunta upang pinalitan ng 3 mas mababa sa 1 katumbas ng katumbas ng 2,
at kaya pagkatapos ito ay pagpunta sa gawin 3 mas mababa sa 1, ay na katumbas 2,
na hindi kung ano ang gusto namin.
Kaya upang maiwasan ang anumang mga problema sa operator mangingibabaw,
laging I-wrap sa panaklong.
Okay. At na, 5:30.
Kung mayroon kang anumang mga katanungan sa pset, ipaalam sa amin.
Dapat itong maging masaya, at ang Hacker edition din mas makatotohanang
kaysa sa Hacker edisyon ng nakaraang taon, kaya inaasahan namin na ng maraming iyo na subukan ito.
Ng nakaraang taon ay masyadong napakalaki.
>> [CS50.TV]