>> Tagapagsalita 1: Hey sa lahat!
Maligayang pagbabalik sa seksyon.
Kaya natutuwa upang makita kaya marami sa parehong mo rito, at lahat ng tao kung sino ang nanonood sa online.
Kaya, gaya ng dati pabalik maligayang pagdating.
Umaasa ako na ang lahat ay nagkaroon ng isang kaibig-ibig katapusan ng linggo, na puno ng pahinga, relaxation.
Ito ay maganda ang kahapon.
Kaya, Umaasa ako sa iyo Tatangkilikin ang labas.
>> Kaya muna ng isang pares ng mga anunsyo.
Grading.
Kaya, ang karamihan sa mga mo dapat nakuha ng isang -email sa akin tungkol sa iyong mga scratch Pset,
pati na rin ang grading para sa Pset 1.
Kaya, ang ilang mga bagay lamang.
Tiyaking gumamit check50 sa style50.
Ang mga ito ay sinadya upang maging mga mapagkukunan para sa iyo guys,
upang matiyak na nakakakuha ka ng ng maraming mga punto hangga't maaari
walang needlessly mawala ang mga ito.
Kaya, mga bagay tulad ng estilo Napakahalaga.
Pagpunta Kami ay gumawa ng off para dito.
Maaaring mayroon na ang ilan sa iyo Napansin iyon mula sa iyong Pset.
At check50 lamang talaga madaling paraan upang tiyakin
na aktwal na kami ay bumabalik sa kung ano ang Kailangang ibalik sa user,
at na ang lahat ng bagay na gumagana nang maayos.
>> Sa pangalawang tala, siguraduhin na ang iyong -upload ng mga bagay sa tamang folder.
Ito ay gumagawa ng aking buhay lamang Medyo mas mahirap
kapag nai-upload Pset 2 sa Pset 1 dahil kapag nag-download ako ng mga bagay,
hindi nila i-download nang tama.
At alam ko ito ay isang maliit na wonky sa isang system upang masanay sa,
ngunit maging sobrang lamang Mag-ingat, kung lamang para sa akin,
upang kapag nakakakuha ka ng mga e-mail sa tulad ng 2:00 at ako grading.
Kung hindi maging sanhi Mayroon akong upang tumingin lahat sa paligid para sa iyong Pset.
Ayos.
>> Alam ko ito nang maaga, ngunit ako ganap Kaka-kinuha off bantay
sa pamamagitan ng isang sanaysay na dahil ito Biyernes, na aking propesor ay nais lamang, oh oo.
Tandaan, mayroon kang isang sanaysay dahil sa Biyernes.
Kaya, alam ko walang sinuman ang may gusto mag-isip tungkol sa midterms,
ngunit ang iyong unang pagsusulit ay sa ika-15 ng Oktubre, na Oktubre ay nagsisimula sa linggong ito.
Kaya, maaari itong maging mas maaga kaysa sa iyong inaasahan ang lahat.
Nang sa gayon ay hindi ka itinapon off bantay kapag Banggitin ko seksyon sa susunod na linggo na oh,
ang iyong pagsusulit sa susunod na linggo, naisip ko Gusto ko magbibigay sa iyo ng kaunti higit pa
ng up ng mga ulo ngayon.
>> Kaya, itakda ang iyong problema, numero ng tatlong.
Paano mga tao na basahin ang spec out ng pag-usisa?
OK.
Nakakuha kami ng ilang.
Uri ng down na mula sa huling pag linggo ngunit na ang OK.
Alam ko ito ay magandang out.
Kaya Hatiin Out.
Talagang pagkatapos mong makakuha ng tapos ngayon basahin ang iyong mga spec ng hindi bababa sa
subukan tulad ng pag-download pamamahagi code at tumakbo
tulad ng una paunang bagay na tanungin ka nila sa.
Dahil kami ay gumagamit ng pamamahagi ng code at isang library
na lamang ang aming nai-using-- na --It lamang ang pangalawang pagkakataon na ginawa na namin ang Pset,
nakatutuwang bagay ang maaaring mangyari sa iyong appliance,
at gusto mong malaman na out na ngayon kumpara sa ibang pagkakataon.
>> Dahil kung ito ay Huwebes ng gabi o ito Miyerkules gabi at para sa ilang kadahilanan
iyong appliance gumagana lamang hindi gustong magpatakbo sa library
o sa pamamahagi code, na paraan
Hindi mo maaaring kahit simulan ang paggawa sa coding.
Dahil hindi mo maaaring tingnan upang makita kung ito gumagana.
Ang iyong hindi gonna magagawang upang makita kung compiles ito.
Gusto mong mag-ingat sa mga unang bahagi sa linggo, kapag maaari mo pa ring mag-email sa akin
o isa sa iba pang mga TFs, at maaari naming makakuha ng mga nakapirming.
Dahil ang mga ito ay mga isyu na pagpunta sa itigil mo ang
mula sa pagsasagawa ng anumang tunay na progreso.
Hindi ito gusto ang isa sa bug, na maaari mo lamang uri ng laktawan sa paglipas.
Kung nagkakaroon ka ng mga isyu sa iyong appliance o code na pamamahagi,
Talaga bang nais mong makakuha na kinunan pakialam ng mas maaga kaysa sa ibang pagkakataon.
Kaya kahit na hindi ka naka-gonna talaga simulan coding, i-download ang pamamahagi
code, basahin ang spec, tiyaking lahat ng bagay na gumagana doon.
OK?
Kung maaari mo lamang gawin iyon, ako nangangako ang iyong buhay ay magiging mas madali.
At kaya marahil na iyong pupuntahan upang gawin ito ngayon tama?
OK.
Kaya, anumang mga katanungan doon?
Anumang logistic bagay?
Ang bawat tao'y Magandang?
OK.
>> Disclaimer para sa mga mo sa kuwarto at sa online.
Pupunta ako sa sinusubukan upang lumipat sa pagitan ng PowerPoint sa appliance
dahil kami ay pagpunta maging ang paggawa ng ilang coding
ngayon sa pamamagitan ng sikat na pangangailangan ng hindi nakikilalang poll mungkahi ko ipapadala noong nakaraang linggo.
Kaya, ay ginagawa namin ang ilang mga coding.
Kaya, kung nais mo ring guys upang painitin ang iyong mga kasangkapan sa,
at dapat na mayroon ka ng isang email mula sa akin, na may sample na file.
Mangyaring huwag mag-atubiling upang gawin iyon.
>> Kaya, kami ay pagpunta sa makipag-usap tungkol sa GDB, na isang debugger.
Ito ay pagpunta upang makatulong sa iyo uri ng maisip kung saan
bagay ay pumunta mali sa iyong code.
Ito ay talagang lamang ng isang paraan para sa iyo sa hakbang sa pamamagitan ng iyong code bilang ito nangyayari,
at makakapag-print ang mga variable o kung ano ang aktwal na nangyayari
sa ilalim ng hood verses iyong programa tumatakbo lamang, tulad ng faulting,
at ikaw ay tulad ng, walang ideya kung ano lamang ang nangyari dito.
Hindi ko alam kung ano ang linya Nabigo ito sa.
Hindi ko alam kung saan ito nangyaring mali.
Kaya, GDB ay pupunta na tulungan ka sa na.
Gayundin, kung magpasya kang magpatuloy oo, at 61,
ito ay talagang, talagang maging pinakamatalik na kaibigan, dahilan ang maaari kong sabihin sa iyo
dahil ako pupunta sa pamamagitan ng klase na iyon.
>> Kami ay pagpunta sa tumingin sa binary paghahanap, na kung guys tandaan
ang mahusay na halimbawa phone book palabas mula sa klase.
Susubukan naming i-pagpapatupad na iyon, at paglalakad sa pamamagitan ng na ang isang kaunti pa,
at pagkatapos kami ay pagpunta sa pamamagitan ng apat na iba't ibang mga klase, na Bubble,
Pinili, Insertion, at Pagsamahin.
Ayos.
Kaya, GDB bilang ko nabanggit, ay isang debugger.
At ang mga ito ay uri ng malaki mga bagay, ang malaking function o utos
na gamitin mo sa loob ng GDB, at ako ay lumakad sa iyo sa pamamagitan ng isang demo ng ito sa isang segundo.
>> Kaya, ito ay hindi lamang titira abstract.
Kukunin ko subukan at gawin itong bilang kongkreto hangga't maaari para sa iyo guys.
Kaya, masira.
Ito alinman maging bakasyon tulad ng, ang ilang mga numero, na
ay kumakatawan sa isang linya sa iyong programa, o maaari mong pangalanan ang isang function.
Kaya, kung sinabi mo masira pangunahing, ito ay titigil sa pangunahing,
at hayaan ang ituturo sa iyo na function.
>> Gayundin, kung mayroon kang ilang mga panlabas na gumana tulad ng Pagpalitin o Cube,
na itinuturing namin ang nakaraang linggo.
Kung sinabi mong masira ang isa sa mga iyon, kailanman ang iyong programa sa mga hit na iyon,
Makikita ito maghintay para sa iyo upang sabihin dito kung ano ang gagawin.
Bago ito lamang isagawa kaya maaaring aktwal na hakbang sa loob ng function na
at tingnan kung ano ang nangyayari sa.
Kaya, Susunod, skips lamang sa ibabaw ng susunod na linya, napupunta sa ibabaw ng mga pag-andar.
Hakbang.
Ito ang lahat maliit na abstract.
Kaya, lang ako pagpunta upang patakbuhin sa pamamagitan ng mga ito, ngunit makikita mo ang mga ito sa paggamit sa isang segundo.
>> Hakbang sa isang function.
Kaya bilang sinasabi ko, tulad ng may Swap, gagawin ito
-daan sa iyo upang aktwal na bilang kung ikaw ay tulad ng pisikal na stepping sa loob,
maaari mong gulo sa mga variable, i-print kung ano ang mga ito, tingnan kung ano ang nangyayari sa.
Listahan ay literal na i-print lamang ang nakapalibot na code.
Kaya, kung uri ng kalimutan kung nasaan ka sa iyong programa,
o naka-iisip kung ano ang nangyayari sa paligid nito,
ito ay i-print lamang ang isang segment ng bang lima o anim na linya sa paligid nito.
Kaya, maaari kang makakuha ng nakatuon tungkol sa kung nasaan ka.
>> I-print ang ilang mga variable.
Kaya, kung mayroon kang mga key tulad ng sa Caesar, na titingnan namin.
Maaari mong sabihin I-print ang Key sa anumang punto.
Ito sabihin sa iyo kung ano ang halaga ay kaya iyon, marahil sa isang lugar sa kahabaan ng paraan,
mo ay sinulatan papatong sa iyong key.
Maaari mong aktwal na sabihin na dahil Maaari mong aktwal na obserbahan ang halaga.
>> Sa mga lokal, lamang ng mga kopya ang iyong lokal na variable.
Kaya, anumang oras ikaw ay sa loob ng loop, at gusto mo lamang makita tulad ng, oh.
Ano ang aking ko?
Ano ang key na ito halaga na-initialize ko dito?
Ano ang mensahe sa puntong ito?
Ay i-print ito lamang ang lahat ng mga, sa gayon ay
huwag nang paisa-isa kailangang sabihin, Print I. I-print ang mensahe.
I-print Key.
At pagkatapos ay Ipakita ang.
Ano na ang ginagawa ay tulad ng sa iyo magbasa-basa sa programa,
Makikita ito lamang tiyakin na ito na nagpapakita ng ilang mga tiyak na variable
sa bawat punto.
Kaya na also-- mo --it ang uri ng isang shortcut kung saan
Hindi mo na kailangang panatilihin ng pagpunta tulad ng, oh.
I-print Key o I-print I. ito lamang ay awtomatikong gawin ito para sa iyo.
>> Kaya, na may na, ipinapadala namin pagpunta upang makita kung paano ito napupunta.
Pupunta ako sa subukan at switch sa ibabaw sa aking appliance.
Tingnan kung maaari kong gawin ito.
Lahat.
Lamang kami ng pagpunta sa mirror ito.
Walang basag ang pula ay sa aking laptop pa rin.
OK.
Ito ay kailangang maging isang ito.
Ito ay kaya maliit na.
Tingnan natin kung maaari naming gawin ito Hayaan.
>> OK.
Alice ay malinaw naman struggling dito lamang nang kaunti,
ngunit susuriin namin ito sa isang momento.
OK.
Kami ay lamang ng pagpunta sa taasan ito.
OK.
Maaari lahat uri ng makita na?
Siguro kaunti?
Alam ko ito ay isang maliit na maliit.
Hindi ka maaaring masyadong malaman kung paano gawin ang mas malaking.
Kung alam ng sinuman.
May nakakaalam ba kung paano gawin itong mas malaking?
OK.
Kami ay pagpunta sa roll sa mga ito.
Hindi ba mahalaga pa rin dahil ito ay lamang na ang code na iyong guys dapat
Mayroon.
>> Ano ang mas mahalaga ay ang terminal dito.
At mayroon kaming dito Bakit ito ay kaya maliit?
Mga Setting.
Oh.
Ang tunay na Ike.
Paano ito?
Out ng doon.
Iyan ba ay mas mahusay para sa lahat?
OK ,.
Ayos.
>> Alam mo kapag ikaw ay nasa isang CS class na teknikal na problema
mga uri ng bahagi ng the-- Kaya, na i-clear ang ipaalam.
OK.
Kaya, dito mismo sa seksyon, na namin ay may dito.
Caesar ay isang executable file.
Kaya ginawa ko ito.
Kaya, isang bagay upang mapagtanto na may GDB ay na gagana lamang ito sa mga maipapatupad na file.
Kaya, hindi mo maaaring patakbuhin ito sa isang dotsy.
Kailangan mong aktwal na gumawa ng mga Tiyakin na ang iyong code compiles,
at maaari itong aktwal na patatakbuhin.
>> Kaya, tiyakin na kung hindi sumulat ng libro, kumuha ng mga ito upang makatipon,
upang maaari mong uri ng tumakbo sa pamamagitan nito.
Kaya, upang simulan ang GDB, ang lahat ng ginagawa mo, Gloria uri ng GDB, at pagkatapos lamang ng
-file na gusto mo.
Palagi akong bumaybay nang pamali Caesar.
Ngunit nais mong tiyakin dahil ito ay isang executable,
tuldok flash ti sa gayon na Nangangahulugan na iyong pupuntahan
upang magpatakbo ng CSI na iyong pupuntahan upang maisagawa ang mga file na alinman sa debugger.
OK.
Kaya, mo na, makakakuha ka ng ang ganitong uri ng walang kuwentang.
Ito ay lamang ng lahat ng bagay tungkol sa debugger.
Hindi mo ba talagang i- mag-alala tungkol dito sa ngayon.
At tulad ng nakikita mo, mayroon kaming ito bukas parens, GDP, malapit parens,
at lamang uri ng kamukha ang aming mga linya ng command, i-right?
>> Kaya, kung ano ang gusto naming do-- --So, Ang unang bagay na
ay nais naming piliin isang lugar upang masira ito.
Kaya, mayroong isang bug sa Caesar programa
na ipakilala ko, na kami ay pagpunta upang malaman.
Ito Ano ang ibig ito ay tumatagal ng pag-input Barfoo sa lahat ng mga pag-cap, at para sa ilang kadahilanan
hindi ito baguhin A. nag-iiwan ito lamang ito nag-iisa, Ay iba tama ang lahat ng bagay,
ngunit ang pangalawang sulat Isang nanatiling hindi nabago.
Kaya, kami ay pagpunta sa subukan at malaman kung bakit na.
Kaya, ang unang bagay na karaniwan mong nais gawin sa tuwing magsisimula ka sa GDB
ay malaman kung saan masira ito.
>> Kaya Caesar ay isang medyo maikling programa.
Mayroon lamang namin ang isa function, tama?
Ano ang aming mga sa Caesar?
Mayroon lamang isang function, Main tama?
Pangunahing ay isang function para sa lahat ng iyong mga programa.
Kung hindi ka magkaroon ng Main, maaari ko maging isang maliit na nag-aalala sa ngayon,
ngunit Umaasa ako mo ang lahat ay nagkaroon ng Main doon.
Kaya, ano ang maaari naming gawin ay namin masira lang Main, tulad ng iyon.
Kaya, sinasabi nito, OK.
Namin-set ang aming isa breakpoint doon.
>> Kaya, ngayon ang bagay na dapat tandaan ay Caesar tumatagal ng isang linya ng command argumento karapatan
at hindi pa kami tapos na kahit saan pa.
Kaya, ano ang gagawin mo ay kapag aktwal mong pumunta sa tumakbo
programa, ang anumang mga programa na ikaw ay tumatakbo sa GDB na nangangailangan ng command line
argumento, ka ng pagpunta sa pag-input noong una mong simulan ang pagpapatakbo nito.
Kaya, sa kasong ito, ang ginagawa namin Magpatakbo ng isang key ng tatlo.
At ito ay aktwal na magsimula.
>> Kaya, kung makita mo rito, mayroon kaming Kung Remote-controlled ay hindi kapantay sa 2.
Kaya kung guys ang lahat ng mayroon na file na aking ipinadala out hanggang
makikita mo na na tulad ng aming pangunahing pag-andar unang linya, i-right?
Ito ay pag-check upang makita kung kami ay ang tamang dami ng mga argument.
Kaya, kung ikaw ay nagtataka kung Remote-controlled ay tama,
maaari mong gawin ang isang bagay tulad ng Print Remote-controlled.
Remote-controlled ay dalawang, na kung ano ang inaasahan namin, tama?
>> Kaya, maaari naming pumunta Susunod, at magpatuloy sa pamamagitan ng.
Kaya, mayroon kaming ilang mga pangunahing doon.
At maaari naming i-print ang aming key upang matiyak na tama.
Kawili-wili.
Hindi masyadong kung ano ang inaasahan namin.
Kaya, isang bagay upang mapagtanto may GDB rin, ay
na hindi ito hanggang sa aktwal mong pindutin ang Susunod, na ang mga line na nakita mo lamang
ay aktwal na pinaandar.
Kaya, sa kasong ito Key Hindi pa nakatalaga.
Kaya, Key ay ilang mga halaga ng basura na nakikita mo sa ibaba doon.
Negatibong $ 120-- --It ng isang bilyon at ng kakaiba mga bagay na tama?
Hindi ito ang Key na aming inaasahan.
Ngunit kung pindutin namin ang Susunod, at pagkatapos ay namin subukan at I-print key, ito ay tatlo.
>> Ang bawat tao'y makita na?
Kaya, kung makakuha ka ng isang bagay na ikaw ay tulad, maghintay.
Ito ay ganap na mali, at hindi ko alam
kung paano ito mangyayari dahil gusto ko ang lahat gawin ay magtalaga ng isang numero, isang variable,
subukan ang pagpindot Susunod, subukan ang pag-print itong muli, at tingnan kung na gumagana.
Dahil itong ibang mapupuntahan kundi upang maisagawa at aktwal na magtalaga ng isang bagay na pagkatapos mong
pindutin ang Susunod.
Magkaroon ng kahulugan sa lahat?
Uh huh?
>> Tagapagsalita 2: Kapag nag-random mga numero kung ano ang ibig sabihin na?
>> Tagapagsalita 1: Ito ay lamang random.
Ito ay basura lamang.
Ito ay isang bagay lamang na iyong computer ay random na italaga.
Ayos.
Kaya, ngayon, maaari naming ilipat sa pamamagitan, at sa gayon ngayon ay mayroon kaming na ito plain text GetString.
Kaya, sabihin ipakilala sa akin kung ano ang ang mangyayari kapag pindutin namin Susunod dito.
Ang aming GDB uri ng mawala, tama?
Iyon ay dahil sa GetString ay isinasagawa ngayon, tama?
Kaya, kapag nakita namin ang plain text ay katumbas ng GetString, buksan ang parens at parens,
at pindutin namin Susunod, na may aktwal na isagawa ngayon.
Kaya, ito ay naghihintay para sa amin na input ng isang bagay.
>> Kaya, kami ay pagpunta sa input aming pagkain na ay kung ano ang hindi pagtupad ito bilang sinabi ko sa iyo
at na lamang ang sinasabi na ito tapos na e-execute, na ang nagsara
bracket ay nangangahulugan ito paglabas out sa na loop.
Kaya, maaari naming pindutin ang Susunod, at ngayon, bilang ako Tiyaking ikaw ay lahat ng mga pamilyar mula sa Caesar,
ito ay, kung ano ang linyang ito ng pagpunta sa gawin.
Ito ay para sa katumbas Int akong 0, N ay katumbas ng Strlen, plain na teksto, at pagkatapos ay
Ako ay mas mababa kaysa n, ko, plus, plus.
Ano ito loop pagpunta sa gawin?
Buksan ang iyong mensahe.
Ayos.
Kaya, magsimula ng paggawa na ipaalam.
>> Kaya, dapat ang kundisyong ito tumugma sa, para sa aming unang isa?
Kung ito ay isang B, ito ay plain text I. namin makakakuha ng impormasyon tungkol sa aming mga lokal.
Kaya, ako ay zero, at kung anim, na inaasahan namin, at ang aming key ay tatlong.
Lahat ng na magkaroon ng kahulugan, tama?
Ang mga numerong ito ay ang lahat ng nang eksakto kung ano ang dapat nilang maging.
Kaya, ugong?
Tagapagsalita 3: Mayroon akong random na numero para sa minahan.
Tagapagsalita 1: Well, maaari naming check-- --we maaaring makipag-chat tungkol na sa isang segundo.
Ngunit dapat ay nakakakuha ito.
Kaya, kung mayroon kaming kapital B para sa aming unang isa,
kondisyon na ito ay dapat mahuli ito, i-right?
Kaya, kung pindutin namin Susunod, makikita natin na ito Kung talagang executes.
Dahil kung sinusubaybayan mo kasama ang iyong code,
ang linyang ito dito, kung saan plain text ko ay pinalitan ng mga ito palatuusan,
executes lamang kung ang Kung kondisyon ay tama tama?
>> GDB ay pupunta lamang upang ipakita sa iyo mga bagay na aktwal na-e-execute.
Kaya kung ito Kung ang kondisyon ay hindi pa nakikilala, ito ay lamang ng pagpunta sa lumaktaw sa susunod na linya.
OK?
Kaya, mayroon kaming na iyon.
Bracket Ito ay nangangahulugan ito Sarado out sa na loop ngayon.
Kaya, ito ay pagpunta sa simulan muli.
Tulad na iyon.
Kaya, maaari naming makakuha ng impormasyon tungkol sa aming mga lokal dito,
at nakita namin na ang aming unang sulat nagbago, tama?
Ito ay ngayon isang E, pati na ito ay dapat.
Kaya, maaari naming magpatuloy sa.
>> At mayroon kaming ito tseke.
At ang check ay dapat na gumana, tama?
Ito ay A. Dapat itong baguhin tatlong titik pasulong.
Ngunit kung napansin mo, kami makakuha ng isang bagay na naiiba.
Kaya sa kasong ito dito, nahuli ito ito, at kaya ang linyang ito isagawa,
na-modify na aming B. Subalit, sa kasong ito dito,
mayroon kaming na nilaktawan lang ito dito, at nagpunta sa [? L siff. ?]
Kaya isang bagay na nangyayari sa doon.
Ano na nagsasabi sa iyo ay na, Alam namin na ito ay dapat mahuli dito,
pero hindi.
Maaari sinuman makita kung ano ang aming problema ay sa linya?
Ito ay isang napaka-minutong bagay.
At maaari ka ring tumingin sa iyong mga code.
Ito ay line-- rin kalimutan kung ano ang line ito sa there-- ngunit sa [hindi marinig].
Oo?
>> Tagapagsalita 4: Ito ay sa mas mataas kaysa sa pahina kung basahin mo ito sa aklat.
Tagapagsalita 1: Eksaktong.
Kaya, ang debugger ay hindi maaaring sabihin sa iyo na, ngunit ang debugger
makakuha ka pababa sa isang linya na alam mo ay hindi gumagana.
At kung minsan, kapag lalo na sa ibang pagkakataon sa semestre, kapag
ka pagharap sa isang daang, isang daang ilang linya ng code, at
hindi alam kung saan ito bagsak, ito ay isang mahusay na paraan upang gawin ito.
Kaya, nakita namin ang aming mga bug.
Maaari mong ayusin ito sa iyong file, at pagkatapos ay maaari mo itong patakbuhing muli,
at lahat ng bagay ay gumana nang perpekto.
At ang pinakamalaking bagay ay Maaari itong tila mas, OK.
Oo.
Ayos.
Alam mo kung ano ang iyong hinahanap.
Kaya, alam mo kung ano ang gagawin.
>> GDB ay maaaring maging napaka-kapaki-pakinabang dahil ikaw maaaring mag-print out ang lahat ng mga bagay na ito na
gagawin hindi.
Ito ay mas kapaki-pakinabang kaysa PrintF.
Ilan sa ginagamit mo tulad ng PrintF pahayag
upang malaman kung saan ang isang bug ay, i-right?
Kaya, sa ito, hindi mo gusto mayroon upang panatilihing bumabalik,
at i pagkomento sa PrintF, o pagkomento out,
at malaman kung ano dapat mong i-print.
Ang aktwal na lamang ay nagbibigay-daan sa iyo upang magbasa-basa, mag-print ng mga bagay
bilang ka ng pagpunta sa pamamagitan ng, sa gayon, maaari mong obserbahan kung paano baguhin ang mga ito sa real time,
bilang iyong programa ay tumatakbo.
>> At ito ay tumagal ng kaunti kaunting nagsisimula ginagamit upang.
Gusto ko lubos na inirerekomenda uri lamang ng pagiging isang maliit na bigo dito
para sa ngayon.
Kung gumastos ka ng isang oras sa ibabaw ng susunod na linggo sa pag-aaral kung paano gamitin ang GDB,
ay i-save mo ang iyong sarili kaya karaming oras sa ibang pagkakataon.
At literal. sabihin namin ito sa mga tao sa bawat taon,
at natatandaan ko noong kinuha ko ang klase, ako ay tulad ng, ako ay magiging multa.
Hindi.
Pset 6 ay dumating sa at ako ay tulad ng, gonna ako matuto
kung paano gamitin ang GDB dahil gagawin ko hindi malaman kung ano ang nangyayari sa dito.
>> Kaya kung maglaan ka ng oras upang gamitin ito sa mas maliit na mga programa
na kayo ay magiging nagtatrabaho sa, tulad ng pagtatrabaho
sa pamamagitan ng isang bagay tulad ng Visionare, tulad nito.
O kung gusto mo ba ng karagdagang kasanayan, ako sigurado Maaari akong makabuo ng maraming surot programa,
para sa iyo upang i-debug kung gusto mo.
>> Ngunit kung gagawin mo lang ng ilang oras upang makakuha ng ginagamit upang ito, i-play lamang sa paligid dito,
ito ay talagang maghatid sa iyo na rin.
At ito ay tunay na isa sa mga bagay na lamang
Mayroon subukan, at makuha ang iyong mga kamay marumi sa, bago mo ba talagang maunawaan ito.
Ko talaga maintindihan lamang ito nang isang beses Nagkaroon na ako upang i-debug ang mga bagay na may ito,
at ito ay magkano nicer upang magkaroon ng ideya kung paano i-debug ang mas maaga kaysa sa ibang pagkakataon.
OK.
Ayos.
Alam ko na uri ng tulad ng isang crash course sa GDB,
at ako ay siguradong gagana sa pagkuha ng ang mga ito upang tumingin mas malaki susunod na pagkakataon.
Ayos.
>> Kaya, kung pumunta namin pabalik sa aming mga PowerPoint.
Upang gumana ba ito ng pagpunta?
Awh.
Oo.
OK.
Kaya, kung sakaling kailangan mo ng alinman sa mga muli, mayroong sa listahan.
Kaya Binary Paghahanap, na lahat Natatandaan ang mahusay na tanawin ng David
sa nakagugulat aklat ng telepono sa kalahati.
Hindi ko talaga makuha ang mga libro na ngayon sa telepono,
dahil tulad ng kung saan gagawin mo makakuha ng mga araw na ito ng mga aklat ng telepono?
Ko talagang hindi alam.
Ang Binary Search.
Sinuman tandaan ang kung paano Binary Paghahanap gawa?
Sinuman sa lahat?
Oo?
Tagapagsalita 5: Alam mo kapag tumingin ka sa kung aling kalahati
magiging in, Batay sa na, at mapupuksa ang iba pang kalahati.
>> Tagapagsalita 1 Eksaktong.
Kaya, Binary Search, ito ay uri ng a-- i --we na tumawag ito hatiin at mapaglabanan.
Kaya, kung ano ang makikita mong gawin ay makikita mo tumingin sa gitna,
at makikita mo kung tumutugma ito kung ano ang iyong hinahanap.
At kung hindi, at pagkatapos ay subukang mong tayahin, ay ito pagpunta sa iwanang
kalahati o ang karapatan sa kalahati.
Kaya, ito ay maaaring maging kung naghahanap ka ng sa isang bagay na alphabetized,
na nakikita mo, oh.
Allison nagmumula ang bago M?
Oo.
Kaya, kami ay pagpunta sa tingnan ang unang kalahati.
>> O maaari itong maging tulad ng may mga numero.
Anumang bagay na maaari mong ihambing, maaari itong pinagsunod-sunod.
Maaari mong gamitin ang binary paghahanap sa.
Kaya, kahit sino tandaan na ito Ang graph o kung ano ito ay?
Ito ay Asymptotic Pagiging kumplikado.
Kaya, graph na ito lamang naglalarawan kung gaano katagal ito
magdadala sa iyo upang malutas ang problema bilang dagdagan mo ang bilang ng mga bagay
na ginagamit mo.
>> Kaya, mayroon kaming H, na kung saan ay linear oras.
Kung N higit sa dalawang, na kung saan ay bahagyang mas mahusay, lumalaki napakabilis pa rin.
At pagkatapos ay ang pag-login namin, na kung ano ang itinuturing namin Binary Search.
Kung napansin namin, pati na ang iyong problema nakakakuha ng mas at mas malaki,
ang oras na ginugugol mo upang malutas ito Hindi talaga taasan ang ganoong karaming.
Ito ay tulad maihahambing dito sa simula.
Ikaw ay tulad, OK.
Dito ay hindi talaga anumang bagay mahalaga kung aling isa na ginagamit namin,
ngunit makakakuha ka out sa isang milyong, isang bilyon.
Sinusubukan mong mahanap some-- --you're sinusubukan upang makahanap ng isang karayom ​​sa isang mandala ng dayami.
>> Sa tingin ko gusto mong problemang ito.
Gusto mong ito kumplikado, hindi linear dahil para sa lahat mo
alam ang iyong gonna ay naghahanap sa pamamagitan ng bawat indibidwal na karayom, bagay ng dayami,
sinusubukan mong hanapin ang iyong mga karayom.
At na hindi masyadong masaya sa aking opinyon.
Gusto ko mabilis.
Gusto ko mahusay.
At bilang hardworking mga mag-aaral mo guys ay, alam mong mas mahusay na makapagtrabaho,
Hindi mahirap uri ng bagay, kung paano mo ay maaaring gumawa ng up ng mga algorithm.
>> Kaya, kami ay pagpunta sa maglakad sa pamamagitan lamang ng isang mabilis na halimbawa.
Sa tingin ko mo guys ay dapat magkaroon isang kamay sa Binary Search,
ngunit kung sakaling sinuman ay isang maliit na malabo, nais upang palakasin ito,
kami ay pagpunta sa pumunta lamang sa pamamagitan ng isang halimbawa dito.
Kaya, kami ay naghahanap ng kung ang array ay naglalaman ng pitong.
>> Kaya, ang unang bagay na aming ginagawa ay tumingin sa gitna, tama?
At din na iyong pupuntahan ay coding Binary Hanapin sa isang segundo lang.
Kaya, ito ay magiging masaya.
Kaya tingnan natin sa gitna maliit na array 3.
Ang 3 katumbas 7?
Ay hindi.
Ito ay anim.
Kaya, ay itong mas mababa sa o mas mataas sa pitong?
Mas mababa sa.
Oo.
Nice guys trabaho.
Pakiramdam ko gusto ko dapat kong Mayroon kendi dahil ako
nais na dumura ito sa yarda.
Ito ay kung ano ako pagpunta sa gawin sa susunod na linggo.
Ito ay panatilihin kang guys matalim.
>> Kaya, itapon namin ang layo na unang kalahati, tama?
ito ay mas mababa kaysa.
Alam namin na ang lahat ng bagay sa na kaliwang bahagi
ay magiging mas mababa kaysa sa kung ano aktwal kaming naghahanap ng para sa.
Kaya, hindi na kailangang i- bigyang-pansin ito.
Makalimutan lang ang tungkol dito.
Kaya, ngayon tinitingnan namin ang aming kanang bahagi, at inaasahan naming sa gitna doon,
at ngayon ito ay siyam.
Kaya, 9 is-- --Everyone?
Mas mataas kaysa sa kung ano kami ay naghahanap ng, tama?
Kaya, kami ay pagpunta sa magtapon layo ng lahat ng bagay sa kanan.
Tulad na iyon.
Ngayon, ang lahat ng namin ang natitira sa ay isa.
Kaya naming suriin, ay ang isang ito kung ano ang kami iyong hinahanap? ito ay.
Nakita namin kung ano ang gusto naming.
Kaya tapos na kami.
Bilinear Search.
>> At kung napansin mo, kami nagkaroon ng pitong input doon.
Tatagal lamang sa amin tulad ng tatlong beses, ngunit kung gumagawa ka ng tulad ng isang bilyon,
ka guys malaman kung gaano karaming mga hakbang na gagawin ito tumagal kung nagkaroon kami 4000000000 bagay?
Ang anumang mga hula?
Ito ay 32.
32 mga hakbang upang makahanap ng isang bagay sa isang 4000000000
element ng array dahil sa kapangyarihan ng dalawa.
Kaya dalawang ay upang 32, ay sa apat na bilyon.
>> Kaya medyo mabaliw kung paano ka pa rin sa loob ng tulad ng isang medyo maliit na bilang ng mga hakbang
makahanap ng isang bagay sa 4000000000 elemento.
Kaya sa na tala, kami ay pagpunta sa code na ito
kaya ka guys maaari talagang uri ng makita kung paano ito gumagana.
Ang lahat ng mga karapatan, sa gayon ay maaari code na guys.
Pupunta ako upang ipaalam sa iyo guys makipag-usap para sa ilang sandali.
Kilalanin ang mga tao sa paligid mo, na kung saan ay kung ano ang isang tao Nais mula sa huling seksyon.
>> Kaya makakuha ng malaman ang mga tao sa paligid mo.
Makipag-usap para sa ilang sandali.
At lahat ng gusto ko mula sa iyo guys ngayon lamang
subukan upang lumikha ng isang balangkas ng pseudocode.
OK?
Whoa.
Lahat ng gusto ko mula sa iyo guys ay ikaw pagpunta lamang upang punan ang mga ito habang kaso.
Kaya ako nag-set ang mga mas mataas na at mas mababang mga hangganan na
Kumakatawan sa simula at pagtatapos ng aming array.
At pupunta ka sa aktwal loop sa pamamagitan ng at malaman
kung ano ang aming ginagawa sa loob ng ito habang loop.
>> Kaya kung maaari mong malaman out-- Mayroon akong isang pahiwatig there-- ano ang mga kaso
mayroon kaming dito?
Kaya kung nais mong malaman kung ang kaso, aalisin namin pseudocode mga
at pagkatapos ay gagamitin namin ang aktwal na code sa kanila.
At ito ay magiging, ako Sa tingin, sana ay idedetalye ito
maging isang maliit na mas madali kaysa sa iyong inaasahan.
Dahil ito ay hindi na magkano ang code, talaga, na talagang cool.
>> Mm-Hm?
>> MAG-AARAL: [hindi marinig]?
Instruktor: Oo.
Nagkaroon ng isang bagay hanapin sa gitna.
>> MAG-AARAL: Kaya maaari naming gamitin iyon.
OK.
>> Instruktor: Perpekto.
Kaya iyon ang unang bagay na kailangan naming gawin.
Kaya mahanap ang gitna.
Mahusay.
Kaya huwag kang magkaroon ng ideya kung paano namin maaari aktwal na mahanap ang gitna na may code?
>> MAG-AARAL: Oo.
n sa 2?
Instruktor: Kaya n sa 2.
Kaya isang bagay upang tandaan ay ang baguhin ang iyong mga upper at lower mga hangganan.
Patuloy naming constricting ang bahagi ng array kaming naghahanap sa.
Kaya n sa 2 Gagana lamang para sa unang bagay na aming ginagawa.
Kaya pagkuha ng upper at lower-alang, kung paano maaaring namin na gitnang elemento?
Dahil gusto naming gitna sa pagitan ng mga upper at lower, tama?
Mm-Hm?
>> MAG-AARAL: [hindi marinig].
>> Instruktor: Kaya mayroon kaming ilang gitna.
At makikita itong maging mas mataas na plus mas mababa sa 2.
Kahanga-hanga.
May pumunta namin.
Isang linya pababa.
Ikaw guys ay sa iyong paraan.
Kaya ngayon na mayroon namin ang aming gitna, ano ang gusto naming gawin?
In lamang pangkalahatang.
Hindi mo na kailangang mag-code ito.
Oo.
MAG-AARAL: [hindi marinig]?
Instruktor: Kaya plus dahil ikaw ay paghahanap ng average na sa pagitan ng dalawang
ng mga ito.
Kaya kung sa tingin mo ng mga ito bilang uri ng pagtaas sa mula sa gilid,
isipin ang tungkol ito habang paparating ka sa gitna, gusto mo ba ng mga iyon.
Kaya kung ikaw ay nasa magkabilang panig ng gitna, at mayroon kaming tulad ng 5 at 7.
Kapag nagdagdag ka ng mga iyon nang magkakasama sa iyo makakuha ng 12, hatiin mo sa pamamagitan ng 2, 6.
>> Minsan mahirap na kung bakit gumagana,
ngunit kung nagtatrabaho ka sa pamamagitan ng isang halimbawa kung minsan,
Makikita ito matulungan kang malaman kung dapat itong maging plus o minus.
Oo.
>> MAG-AARAL: [hindi marinig] nang eksakto sa gitna
kung mayroon sila ng isang kaso kung saan maraming ng mas maliit na mga numero
at tulad ng isang malaking bilang?
>> Instruktor: Kaya ang kailangan mo ay sa gitna ng array.
Kaya kung mayroon kang isang bungkos ng mga maliliit na mga numero at pagkatapos ay isang talagang malaking bilang
sa dulo, hindi ito mahalaga.
Lahat na mahalaga ay ang sila ay pinagsunod-sunod, tulad mo
Gusto upang tumingin sa gitna ng ang array dahil hindi mo pa rin
pagpipiraso ang iyong problema sa kalahati.
Ayos.
Kaya ngayon na mayroon kami sa gitna, ano ang gagawin namin susunod?
>> MAG-AARAL: Ihambing.
Instruktor: ihambing ang.
Kaya ihambing ang gitnang sa value_wanted.
Ayos.
Kaya nakikita mo dito mayroon kaming ang halaga na ito nais naming dito.
Tandaan na ito ay isang array.
Kaya gitna ay tumutukoy sa index.
Kaya gusto naming gawin ang mga halaga ng gitna.
Huwag kalimutan kung nais mong upang ihambing, i-double equals.
Gawin mong single katumbas ikaw ay lamang ng pagpunta sa reassign ito,
at pagkatapos, siyempre, ito ay magiging ang halaga na gusto mo.
Kaya huwag gawin iyon.
>> Kaya kami ng pagpunta upang makita kung ang mga halaga sa gitna
ay katumbas ng halaga na gusto namin.
Huwag kalimutan ang iyong brace.
Dropbox dapat pumunta ang layo.
Kaya ano ang gagawin natin sa kasong ito?
Kung ito ay kung ano ang nais naming ibalik?
Sinusubukan naming sabihin.
>> MAG-AARAL: I-print off.
>> Instruktor: Well, namin ayaw mong i-print.
Kaya ito ay isang bool dito, kaya kami Gusto upang bumalik true o false.
Sinasabi namin, ay ang bilang na ito isang [? RRA? ?] Kaya kung ito ay,
bumalik lang namin ito totoo.
Kung ang maaari kong spell totoo.
>> MAG-AARAL: Bakit hindi mo bumalik sa zero?
Instruktor: Kaya maaari mo bumalik sa zero kung ginusto mo.
Ngunit sa kasong ito dahil Ibinabalik ng aming mga isang bool,
kailangan namin upang bumalik alinman true o false.
MAG-AARAL: Kapag handa ka sinasabi boolean expression,
maaari mo itong itakda katumbas ng false?
Tulad kapag gusto kong sabihin, kung ang kundisyong ito Hindi nakilala, tulad ng ay katumbas ng mas mataas na false.
Maaapektuhan ba nito ang maunawaan kung mo lamang ilagay false sa kabilang panig?
Instruktor: Oo.
Kaya talagang kung ikaw ay kailanman paggawa ng isang bagay
tulad ay mas mataas o mas mababa, na nagbabalik totoo o hindi
at ito ay talagang maganda ang estilo sa sabihin nating katumbas ay katumbas ng totoo o equals
ay katumbas ng false.
Na gusto mong gamitin sa resultang iyon bilang sarili nito bilang iyong tseke.
Hindi kung ano ang nais ko.
Iyon ay kung ano ang nais ko.
Kaya sa kaso ng ka nagtatanong tungkol sa isang bagay tulad ng i-save ito sa c.
>> Kaya kung mayroon kaming int pangunahing (walang bisa) at isang bagay na katulad nito.
At mayroon kang kung ang itaas ng ilang mga input at ikaw ay
na nagtatanong kung maaari mong gawin isang bagay na tulad nito?
Mag-right?
MAG-AARAL: ako ay sinusubukan upang gawin ito [hindi marinig].
Dahil kung it's--
Instruktor: I-right.
Kaya gusto mo ito upang maging totoo, tama?
MAG-AARAL: Oo.
Instruktor: Kaya sa kasong ito sa iyo Gusto ito upang maisagawa kung ito ay hindi totoo.
Kaya ang mga cool na bagay na gagawin mo mayroong ito.
Kaya tandaan tandang point negates bagay?
Sinasabi nito [hindi marinig] ay nangangahulugang hindi.
Kaya kung tinitingnan namin ang lang ito bahagi dito, ikaw ay
sabihin na sinusuri upang false hangga't gusto mo.
Hindi totoo ay totoo na Nangangahulugan ito ay maisagawa.
Ay na magkaroon ng kahulugan?
MAG-AARAL: Oo.
Instruktor: Kahanga-hanga.
OK.
Kaya maaari naming ibalik lamang tunay na sa kasong ito.
Kaya ngayon ay mayroon kaming dalawang iba pang mga kaso sa kasong ito.
Ano ang aming dalawang iba pang mga kaso?
Hayaan gawin ito sa ganitong paraan ni lamang.
Kaya simulan na may iba ipaalam sa kung halaga sa gitna
ay mas mababa sa halaga na gusto namin.
Kaya ang aming halaga sa gitna Mababa kaysa sa halaga na kaming naghahanap ng para sa.
>> Kaya kung saan nakagapos gagawin mo Sa tingin gusto naming i-update?
Upper o mas mababa?
Upper?
Kaya kung aling mga bahagi ng array pupunta kami sa tumitingin ka sa?
>> MAG-AARAL: Ang mas mababa.
>> Instruktor: Aming kami makapupunta na tumitingin sa kaliwa.
Kaya iba kung maliit na halaga ay mas mababa.
Kaya ang gitnang halaga dito Mas mababa sa kung ano ang gusto namin.
Kaya gusto naming gawin ang kanang bahagi ng aming array.
Kaya kami ng pagpunta sa -update ang aming mas mababang bound.
Kaya gagamitin namin reassign aming mas mababa.
At kung ano ang iyong palagay mas mababang ay dapat na?
MAG-AARAL: Ang gitnang halaga?
Instruktor: Kaya gitna value--
MAG-AARAL: Plus 1.
Instruktor: --plus 1.
Maaari sinuman sabihin sa akin kung bakit mayroon kaming na plus 1?
>> MAG-AARAL: [? Walang halaga?] ay mas pantay-pantay dito.
>> Instruktor: I-right.
Dahil alam namin na ang aming gitnang halaga ay hindi katumbas ng
ito at gusto naming ibukod ito mula sa lahat ng mga kasunod na mga paghahanap.
Kung nakalimutan na plus 1, ito ay i loop walang katiyakan.
At makikita mo lamang ay nahuli sa isang walang katapusang loop at pagkatapos ay makikita mo segfault
at mga bagay maging masama.
Kaya laging tiyakin na ikaw ay hindi kabilang ang halaga na iyong lang
tumingin sa.
Kaya kami na ang bahala ng na ng plus 1.
>> Kaya ngayon ay may namin ang aming huling kondisyon na ako palagi para sa kapanan ng kaligtasan
maaari mong tingnan dito, iba kung halaga sa sa gitna ay mas malaki sa halaga
gusto naming.
Iyon ay nangangahulugan na gusto naming kaliwang kalahati.
Kaya kung saan ang isa ay namin pagpunta upang i-update?
Itaas.
At kung ano ang isang ito ng pagpunta sa kasing-halaga?
Gitnang minus 1 dahil, siyempre, gusto naming
upang matiyak na hindi kami ng pagtingin sa na halaga gitna muli.
At pagkatapos ay may namin ito.
Iyan na ang lahat.
Iyon lang ang binary paghahanap ay.
Hindi na masama, tama?
Ito ay tulad ng 10 mga linya ng code sa white space.
Kaya napaka-makapangyarihan, napaka-kapaki-pakinabang, ay sa iyo maging ang paggamit nito sa isa sa iyong ibang pagkakataon psets.
Siguro hindi ang isang ito, ngunit sa ibang pagkakataon.
Kaya matuto ito.
Pag-ibig ito.
Ito ay ituturing mo din.
Kaya ang sinuman ay may anumang tanong sa binary paghahanap?
Oo.
>> MAG-AARAL: ito mahalaga ba kung ang iyong n ay kahit na o kakaiba?
>> Instruktor: Hindi.
Dahil cast namin ito sa gitna ng isang int, ito ay pungusan lamang ito.
Kaya mananatili itong isang integer at magpo ito Sa kalaunan-uri-uriin sa pamamagitan ng lahat.
Kaya hindi mo kailangang mag-alala tungkol sa na.
Ang bawat tao'y magandang?
Kahanga-hanga.
Ayos.
Kaya, mo guys nakuha ko ito.
Slideshow.
Kaya bilang pakikipag-usap namin ay tungkol sa, alam ko Binanggit ni David ang pagiging kumplikado runtimes.
>> Kaya sa pinakamahusay na mga kaso, ito lamang isa, na tinatawag naming tuluy-tuloy na oras.
Maaari sinuman sabihin sa akin kung bakit na maaaring maging?
Anong uri ng sitwasyon ay nilalagay na?
Mm-Hm.
>> MAG-AARAL: [hindi marinig] first--
Instruktor: Kaya sa gitna pagiging unang elemento na nanggaling naming, tama?
Kaya alinman sa isang hanay ng mga isa o anumang kaming naghahanap ng para lamang
ang mangyayari sa maging bahagyang lasa magdutdot sa gitna.
Kaya na ang aming pinakamahusay na kaso.
Makakakuha ka sa tunay na problema, malamang na hindi pagpunta sa maabot [hindi marinig] na madalas.
Ano ang tungkol sa aming mga pinakamasamang sitwasyon?
Ang aming mga pinakamasamang sitwasyon ay log n.
At iyon ay gagawin sa buong kapangyarihan ng dalawang bagay na usapan ko ang tungkol.
>> Kaya sa mga pinakamasamang sitwasyon ay ito ibig sabihin na namin ay may upang tumaga ang array pababa
hanggang sa ito ay isang elemento ng isa.
Kaya nagkaroon kami upang tumaga ito pababa sa kalahati nang maraming beses hangga't posibleng namin ng dati.
Iyon ang dahilan kung bakit ito log n dahil panatilihin ang paghahati ng dalawang mo lamang.
Kaya pagpapalagay, bagay na kailangang malaman kung ikaw ay kailanman
pagpunta sa gumamit ng binary paghahanap.
Dapat na pinagsunod-sunod sa iyong mga elemento.
Ang mga ito ay na pinagsunod-sunod dahil iyon ang tanging paraan sa iyo
malalaman kung ikaw ay magagawang itapon ang kalahati nito.
>> Kung nagkaroon ka ng ito ginulo bag ng mga numero at iyong sinasabi,
OK, pupunta ako upang suriin ang gitnang number at ang numero Naghahanap ako
Mas mababa na, lamang pupunta ako sa nagkataon dumura isang kalahati.
Hindi mo malalaman kung ang iyong numero sa na ang ibang kalahati.
Ang iyong listahan ay dapat pinagsunod-sunod.
Pati na rin, maaaring ito ay pagpunta nang maaga nang kaunti,
ngunit kailangan mong magkaroon ng random na pag-access.
Kailangan mong magagawang lamang pumunta sa gitna na elemento.
Kung mayroon kang upang tumawid sa pamamagitan ng isang bagay
o ito ay magdadala sa iyo ng dagdag na hakbang upang makapunta sa gitna na elemento,
hindi ito mag-log n ngayon dahil nagdaragdag ka pang trabaho ito.
At ito ay gumawa ng isang maliit na higit pang kahulugan sa dalawang linggo,
ngunit ko lang ang uri ng nais na maglagay ng paunang salita, magbibigay sa iyo ng guys ng ideya ng kung ano ang
darating.
Ngunit ang mga ay ang dalawang Mahalaga pagpapalagay
na kailangan mo para sa isang binary listahan.
Tiyakin na ito ay pinagsunod-sunod.
Iyan ang malaking isa para sa ka guys ngayon.
At sa na maaari naming pumunta sa ang natitirang bahagi ng aming mga klase.
Kaya apat na sorts-- bubble, pagpapasok, pagpili, at pag-merge.
Ang mga ito ang lahat ng uri ng mga cool.
Kung guys magpasya upang kumuha ng CS 124, Matututunan mo ang tungkol sa lahat ng uri ng mga klase.
At kung ikaw ay isang XKCD fan, may ay isang talagang cool na comic tungkol sa
tulad ng talagang hindi epektibong mga uri, na aking lubos na inirerekomenda ka ng pagpunta sa tumingin sa.
Ang isa sa mga ito ay tulad ng sindak-uri-uriin, na ay tulad ng, oh hindi, bumalik random na array.
Pag-shutdown system.
Mag-iwan.
Kaya geeky katatawanan ay palaging mabuti.
>> Kaya ang tandaan sinuman uri ng tulad lamang ng isang pangkalahatang ideya
ng kung paano gumagana bubble-uuri.
Tandaan mo?
>> MAG-AARAL: Oo.
>> Instruktor: Pumunta para dito.
>> MAG-AARAL: Kaya ka ng pagpunta sa pamamagitan at kung ito ay mas malaki, pagkatapos ay i-swap mo ang dalawa.
>> Instruktor: MM-Hm.
Mismong.
Kaya umulit sa pamamagitan mo lamang.
Tingnan kang dalawang numero.
Kung ang isa bago ay mas malaki kaysa sa isa pagkatapos,
lamang-swap mo ang mga ito upang sa sa ganitong paraan ang lahat ng mga mas mataas na mga numero
bubble up patungo sa dulo ng listahan at ang lahat ng mga mas mababang mga bilang bubble pababa.
>> Ipakita mo ba siya guys ang cool na tunog ng epekto sa pag-uuri ng video?
Ito ay uri ng cool.
Kaya tulad ng sinabi ni Robert, ang algorithm na hakbang mo pa lamang sa listahan,
pagpapalit ang katabing mga halaga kung wala ang mga ito sa pagkakasunud-sunod.
At pagkatapos ay magpatuloy lang sa pag-uulit hanggang hindi mo na gumawa ng anumang mga swaps.
Kaya hindi masama, tama?
Kaya mayroon lang namin ng isang mabilis na halimbawa dito.
Kaya ito ay pagpunta sa uri-uriin ang mga ito sa pataas na pagkakasunod-sunod.
Kaya kapag pumunta kami sa pamamagitan ng mga unang panahon, inaasahan naming sa pamamagitan ng walong
at anim ay malinaw naman hindi sa pagkakasunud-sunod, swap namin ang mga ito.
>> Kaya tingnan ang susunod na isa.
Eight at apat na wala sa pagkakasunud-sunod.
Magpalit ang mga ito.
At pagkatapos ay walong at dalawang, magpalit ang mga ito.
May pumunta namin.
Kaya pagkatapos ng iyong unang pass, mo malaman na ang iyong pinakamalaking bilang
ay magiging lahat ng mga paraan sa itaas dahil ito ay lamang
magiging palagiang mas malaki kaysa sa lahat ng iba pa
at ito lamang ang pagpunta sa bubble hanggang ang lahat ng mga paraan sa dulo doon.
Sinusuportahan ba na saysay sa lahat?
Ayos.
>> Kaya pagkatapos ay tinitingnan namin ang aming ikalawang pass.
Anim at apat na, lumipat.
Anim at dalawang, lumipat.
At ngayon ay mayroon kaming ilang mga bagay sa pagkakasunud-sunod.
Kaya para sa bawat pass na namin gumawa sa pamamagitan ng aming buong listahan,
alam namin na tulad na maraming mga numero sa pagtatapos ay na-pinagsunod-sunod.
Kaya ang ginagawa namin sa isang third pass, na kung saan ay isa swap.
At pagkatapos ay sa aming ika-apat na pumasa, mayroon kaming zero slot.
At alam namin na ang aming array ay pinagsunod-sunod.
>> At iyon ay ang malaki bagay na may bubble-uuri.
Alam namin na kung kailan namin may zero swaps, na
ay nangangahulugan na ang lahat ng bagay ay nasa kumpletong order.
Ito ay uri ng kung paano namin tingnan.
Kaya tayo ay pupunta rin sa code ng bubble -uri-uriin na rin ay hindi na masama.
Wala sa mga ito ay na masama.
Alam ko maaari silang tila isang maliit na nakakatakot.
Alam ko noong kinuha ko klase, kahit na ako
ay nagtuturo ng klase para sa sa unang pagkakataon noong nakaraang taon,
Ako ay tulad ng, kung paano ang gagawin ko ito?
Nag-saysay sa teorya, ngunit paano namin talagang gawin ito?
Aling ang dahilan kung bakit gusto ko ring maglakad sa pamamagitan ng code sa iyo guys dito.
Kaya ba akong magkaroon ng isang pseudocode para sa iyo guys oras na ito.
Kaya panatilihin ito lamang sa isip bilang Ikinalulungkot namin na sa pagbabago sa paglipas.
Kaya mayroon kaming ilang mga sagot na Sinusubaybayan ng aming swaps,
dahil kailangan namin upang matiyak na na Sinusuri namin iyon.
At umulit namin ang buong array tulad ng ginawa lang namin sa halimbawang ito.
Kung ang elemento ng bago ay mas malaki sa ang elemento pagkatapos kung saan kami ay sa,
swap namin ang mga ito at kami dinagdagan aming counter dahil sa lalong madaling swap namin,
Gusto naming ipaalam sa aming mga counter alam na.
Ang anumang mga katanungan doon?
Isang bagay na tila nakakatawa sa paglipas dito.
MAG-AARAL: Huwag mong itakda ang counter sa zero sa tuwing pumupunta ka sa pamamagitan ng loop?
Huwag mong panatilihin ang pagpunta pabalik sa zero sa bawat panahon?
Instruktor: Hindi kinakailangan.
Kaya kung ano ang mangyayari ay pumunta kami sa pamamagitan dito.
Kaya gawin habang, tandaan, ito ay nagsasagawa ng isang beses nang walang mabibigo.
Kaya ito ang nangyayari upang itakda ang counter katumbas ng zero,
pagkatapos ito ay pagpunta upang umulit sa pamamagitan ng.
Bilang ito iterates sa pamamagitan ng, Maa-update ito counter.
Bilang ito ina-update ng counter, kapag ito ay tapos na, kapag naabot ang dulo ng array,
kung ang aming listahan ay hindi na pinagsunod-sunod, ay na-update counter.
>> Kaya gayon ito sumusuri ang kundisyon at ito sabi, OK, ang counter mas mataas sa zero.
Kung ito ay, gawin itong muli.
Gusto mong i-reset nang sa gayon ay kapag pumunta sa pamamagitan, ng counter ay katumbas ng zero.
Kung pumunta ka sa pamamagitan ng isang Pinagbukud-bukod array, walang magbabago,
ito nabigo, at ibalik ang pinagsunod-sunod na listahan.
Sinusuportahan ba na saysay?
MAG-AARAL: Ito maaari sa ilang sandali.
Instruktor: OK.
Kung mayroong anumang iba pang tanong na ito ay up.
Oo.
>> MAG-AARAL: Ano ang gagawin ang pag-andar maging para sa pagpapalit ng mga elemento?
>> Instruktor: Kaya maaari naming aktwal na magsulat na kung kami ay pagpunta sa ngayon.
Ayos.
Kaya sa na tala, Alison ay pagpunta upang bumalik sa appliance.
Ito ay magiging masaya.
At mayroon kaming magandang bubble-uri-uriin bagay dito.
Kaya na ginawa ko sa pagbibisikleta sa pamamagitan ng array.
Mayroon kaming aming swaps na ay katumbas ng zero.
Kaya gusto namin magpalit ng katabing mga elemento kung sila ay sira.
Kaya ang unang bagay na kailangan namin upang huwag ay umulit sa pamamagitan ng aming array.
>> Kaya kung paano sa tingin mo maaari naming umulit sa pamamagitan ng aming array?
Mayroon kaming para sa at i ay katumbas ng 0.
Gusto naming i upang maging mas mababa kaysa n minus 1 minus k.
At Ipapaliwanag ko na sa isang segundo.
Kaya ito ay isang pag-optimize dito kung saan, tandaan kung paano sinabi ko pagkatapos ng bawat pass
sa pamamagitan ng array namin malaman na ang kahit anong on--
>> Kaya pagkatapos ng isang pass namin malaman na ito ay pinagsunod-sunod.
Pagkatapos ng dalawang pass namin alam na ang lahat ng ito ay pinagsunod-sunod.
Pagkatapos ng tatlong pass namin Alam na pinagsunod-sunod.
Kaya ang paraan ako iterating sa pamamagitan ng array dito,
ay ang ginagawa itong bang pumunta lamang sa pamamagitan ng kung ano ang alam namin ay unsorted.
OK?
Iyon ang isang pag-optimize lamang.
Maaari mo itong isulat naively lamang iterating sa pamamagitan ng lahat ng bagay,
Gusto tumagal lamang nang mas matagal.
Gamit ang apat na loop ito lamang sa isang masarap na pag-optimize
dahil alam namin na pagkatapos ng bawat buong pag-ulit sa pamamagitan ng array dito,
tulad ng bawat buong loop dito, alam namin na ang isa higit pa sa mga elemento
ay pinagsunod-sunod sa dulo.
>> Kaya hindi namin kailangang mag-alala tungkol sa mga iyon.
Sinusuportahan ba na saysay sa lahat?
Iyon cool na maliit na nanlilinlang ng?
Kaya sa kasong iyon, kung kami ay iterating sa pamamagitan ng,
Alam namin na gusto naming suriin kung array n at n plus 1 ay nasa order.
OK.
Kaya narito ang pseudocode.
Gusto naming suriin kung array n at n plus 1 ay nasa order.
Kaya kung ano ang maaaring mayroon kaming doon?
Ito ay pagpunta sa ilang mga kondisyon.
Ito ay magiging isang kung.
>> MAG-AARAL: Kung array n ay mas mababa sa array n plus 1.
Instruktor: MM-Hm.
Well, mas mababa o mas mataas kaysa sa.
MAG-AARAL: Mas mataas sa.
Pagkatapos ay nais naming magpalit ang mga ito.
Mismong.
Kaya ngayon makuha namin sa kung ano ang mekanismo para sa pagpapalit ang mga ito?
Kaya nagpunta kami sa pamamagitan ng mabilis, isang uri ng swap function na noong nakaraang linggo.
Sinuman tandaan ba kung paano ito nagtrabaho?
Kaya hindi namin lamang ay maaaring reassign ang mga ito, i-right?
Dahil isa sa mga ito ay mawala.
Kung sinabi namin A ay katumbas ng B at pagkatapos ay B ay katumbas ng A, lahat ng pareho ng mga ito biglaang
ay pantay-pantay lang sa B.
>> Kaya kung ano ang dapat nating gawin ay namin may isang pansamantalang variable na
pagpunta upang i-hold ang isa sa atin habang kami ay nasa proseso ng pagpapalit.
Kaya kung ano ang mayroon kami ay makakakita kami ng ilang int temp ay katumbas to-- maaari mo itong magtalaga
sa alinman sa isa gusto mo, lamang tiyaking mong subaybayan it--
kaya sa kasong ito, pupuntahan ko italaga ito upang array n plus 1.
Kaya na pupuntahan pindutin nang matagal ang anumang halaga ay nasa ikalawang na bloke
na kaming naghahanap sa.
>> At pagkatapos ay maaari naming gawin ay maaari naming pumunta Magpatuloy at reassign array n plus 1,
dahil alam namin kami Mayroon na halaga na naka-imbak.
Ito ay din isa sa mga malaki things-- Hindi ko alam kung ang alinman sa iyo
Nagkaroon isyu kung saan kung lumipat ka ng dalawang linya ng code bigla bagay nagtrabaho.
Order ay napakahalaga sa CS.
Kaya tiyaking ang diagram sa iyo mga bagay kung posible
bilang sa kung ano ang aktwal na nangyayari.
Kaya ngayon kami ay pagpunta sa reassign array n plus 1,
dahil alam namin kami Mayroon na halaga na naka-imbak.
>> At kami ay maaaring magtalaga na sa array n o sa kasong ito array i.
Masyadong maraming mga variable.
OK.
Kaya ngayon na reassigned namin array i plus 1 upang pumatas kung ano ang sa array i.
At ngayon maaari naming bumalik at magtalaga array i upang ano?
Sinuman?
>> MAG-AARAL: 10.
>> Instruktor: 10.
Mismong.
At isa huling bagay.
Kung kami ay swapped ito ngayon, kung ano ang kailangan namin upang gawin?
Ano ang isang bagay na pupuntahan sabihin sa amin
kung wakasan namin kailanman programang ito?
Ano ang sinasabi sa atin na tayo magkaroon ng isang pinagsunod-sunod na listahan?
Kung hindi kami magsagawa ng anumang mga swaps, tama?
Kung swaps ay katumbas ng ZERO sa dulo ng ito.
Kaya sa tuwing kang magsagawa ng isang magpalitan, bilang namin ginawa lang dito, gusto naming i-update ang swaps.
At alam ko nagkaroon ng tanong mas maaga tungkol sa maaari mong
gamitin sa zero o isa sa halip ng totoo o hindi.
At iyon ang kung ano ang ginagawa dito.
Kaya ito ang sinasabi kung hindi swaps.
Kaya kung swaps ay zero, na is-- ako palagi ang aking katotohanan at ang aking falses halo-halong up.
Gusto naming suriin namin sa totoo at hindi.
Kaya kung ito ay zero, pagkatapos ito ay hindi totoo.
Kung magkaila mo ito gamit ang isang [? Bang?] ito ay nagiging totoo.
Kaya pagkatapos ay ang linyang ito executes.
>> Katotohanan at mali at mga zero at mga makakuha ng mabaliw.
Kung lang mo mabagal maglakad sa pamamagitan nito ito ay magkaroon ng kahulugan.
Ngunit iyon kung ano ito kaunti dito ang kaunting code.
Kaya ito sumusuri upang makita na namin nagawa ang anumang mga swaps.
Kaya kung ito ay anumang bagay bukod sa zero, ito ay magiging hindi totoo
at ang buong bagay ay pagpunta upang maisagawa muli.
Cool?
>> MAG-AARAL: Ano ang bakasyon gawin?
>> Instruktor: Hatiin lamang Pinaghihiwa-out ng loop sa iyo.
Kaya sa kasong ito gagawin ito gusto lang tapusin ang programa
at gagawin mo lang Mayroon iyong pinagsunod-sunod na listahan.
MAG-AARAL: kamangha-manghang.
Instruktor: Sorry?
MAG-AARAL: Dahil dati namin ginagamit ang nakasulat 1 sa paglipas ng nakasulat na zero
ipakita na kung na gagana o hindi.
>> Instruktor: Oo.
Kaya maaari kang bumalik sa zero o 1.
Sa kasong ito, dahil hindi namin talaga paggawa ng anumang bagay na may pag-andar,
nais lamang namin ito upang masira.
Hindi namin talagang pakialam tungkol dito.
Preno ay mabuti kung din ito ay ginagamit para breaking out
ng apat na mga loop o kundisyon na hindi mo nais na panatilihin ang e-execute.
Lamang Tatagal ka na ng mga ito.
Ito ay isang bit ng isang pananarinari bagay.
Nararamdaman kong mayroong ng maraming kamay waving,
tulad ng makikita mo matuto nang higit pa tungkol sa ito sa lalong madaling panahon.
>> Ngunit matutunan mo ang tungkol sa lalong madaling panahon.
Nangangako ako.
OK.
Kaya ang lahat makakuha ng bubble-uuri-uri?
Huwag masyadong masama.
Umulit sa pamamagitan, magpalitan ng mga bagay na gamit ang isang temp variable, at kami ay lahat ng set doon?
Ayos.
Kahanga-hanga.
OK.
Bumalik sa PowerPoint.
Ang anumang mga katanungan sa pangkalahatan tungkol sa mga ngayon?
Ayos.
Mm-Hm.
>> MAG-AARAL: [hindi marinig] int pangunahing karaniwang.
Mayroon ka bang magkaroon ng na para sa ito?
>> Instruktor: Kaya tayo ay naghahanap lamang lamang sa aktwal na-uuri-uri algorithm.
Kung nagkaroon ka ng ito sa loob ng tulad ng isang mas malaking programa,
magkakaroon ka ng isang int pangunahing lugar.
Depende sa kung saan mo gamitin ang algorithm na ito,
Gusto ito matukoy kung ano ang na ibinalik ng mga ito.
Ngunit para sa aming kaso, kami ay mahigpit na ng pagtingin sa kung paano gumagana ang aktwal na
umulit sa pamamagitan ng isang array.
Kaya naming huwag mag-alala tungkol dito.
>> Kaya tayo ay pakikipag-usap tungkol sa mga pinakamahusay na kaso at pinakamasamang sitwasyon kaso para sa binary paghahanap.
Kaya mahalaga ding gawin na para sa bawat isa sa aming mga klase.
Kaya kung ano ang tingin mo ay ang pinakamasamang kaso runtime ng bubble-uuri-uri?
Ikaw guys tandaan?
>> MAG-AARAL: N minus 1.
Instruktor: N minus 1.
Kaya nangangahulugan na mayroong n minus 1 paghahambing.
Kaya isang bagay upang mapagtanto ay na sa unang pag-ulit,
pumunta namin sa pamamagitan ng, ihambing namin mga two-- kaya na 1.
Ang mga dalawa, tatlo, apat.
Kaya pagkatapos ng isang pag-ulit namin Mayroon na apat na mga paghahambing.
Kapag ako pinag-uusapan ng runtime at n.
N kumakatawan sa bilang ng mga paghahambing bilang isang katangian ng kung gaano karaming mga elemento
mayroon kaming.
OK?
>> Kaya pumunta kami sa pamamagitan ng, mayroon kaming apat.
Ang susunod na oras na alam mo na hindi namin kailangang alagaan ito.
Inihambing namin ang dalawang, ang dalawang, ang dalawang,
at kung hindi namin ginawa magkaroon ng pag-optimize na may apat na loop na sinulat ni ko,
Gusto ka ng paghahambing in dito pa rin.
Kaya magkakaroon ka ng upang tumakbo sa pamamagitan ng array
at gumawa ng mga paghahambing n n beses, dahil sa tuwing namin
tumagos ito namin uri-uriin ang isang bagay.
>> At sa bawat oras na patakbuhin namin sa pamamagitan ng ang array, gumawa kami n mga paghahambing.
Kaya aming runtime para sa ito ay talaga n nakalapat, na
ay mas mas masahol pa sa aming pagtatapos dahil na mag-log
nangangahulugan kung nagkaroon kami ng apat na bilyon mga elemento, ito ay
pagpunta sa tumagal kami 4000000000 nakalapat sa halip na 32.
Kaya hindi ang pinakamahusay na runtime, ngunit para sa ilang mga bagay,
alam mo na, kung ikaw ay sa loob ng sa isang tiyak na hanay ng mga elemento
bubble-uuri-uri ay maaaring fine gamitin.
>> OK.
Kaya ngayon kung ano ang pinakamahusay na kaso runtime?
MAG-AARAL: Zero?
O 1?
>> Instruktor: Kaya 1 gagawin maging isa sa paghahambing.
I-right.
>> MAG-AARAL: N minus 1?
>> Instruktor: Kaya, oo.
Kaya n minus 1.
Sa tuwing mayroon kang isang konsepto tulad n minus 1, ay may posibilidad naming i-drop lang ito off
at kami sabihin lang n dahil mayroon kang upang ihambing ang bawat isa sa these-- bawat pares.
Kaya magiging n minus 1, na kung saan namin nais naming sabihin lamang ay humigit-kumulang n.
Kapag tapos ka pagharap sa runtime, ang lahat ng bagay ay nasa nagtataya.
Hangga't ang exponent ay tama, ikaw ay mahusay.
>> Iyon ay kung paano namin haharapin ang mga ito.
Kaya na ang pinakamahusay na kaso ay n, na ay nangangahulugan na ang listahan ay naka-pinagsunod-sunod,
at lahat ng aming ginagawa ay tumatakbo sa pamamagitan ng at suriin na ito ay pinagsunod-sunod.
Ayos.
Lahat ng karapatan.
Kaya bilang na iyong nakikita dito, namin Mayroon lamang ilan pang mga graph.
Kaya n nakalapat.
Masaya.
Karamihan mas masahol kaysa n tulad ng nakikita namin, at magkano, magkano ang mas masahol kaysa log 2n.
At pagkatapos mong makakuha rin sa mga log ng log.
At dadalhin ka 124, makakakuha ka sa tulad log star, na kung saan ay tulad ng nakatutuwang.
Kaya kung interesado ka, star paghahanap ng log.
Ito ay uri ng masaya.
Kaya mayroon kaming ito mahusay na chart.
Lang ng babala, ang isang kahanga-hangang chart upang magkaroon
para sa iyong mga mid-matagalang dahil namin mahaba upang hilingin sa iyo ng mga thins.
Kaya lamang babala, mayroon na ito sa iyong mid-terminong ginamit sa iyong maganda impostor sheet
doon.
Kaya kami ay tumingin lang sa bubble-uuri.
Pinakamahina ang kaso, n nakalapat, pinakamahusay na kaso, n.
At kami ay pagpunta sa tumingin sa iba.
>> At tulad ng nakikita mo, ang tanging isa na tunay na ginagawa rin
ay pag-uuri-merge, na susuriin namin kung bakit.
Kaya kami ay pagpunta sa pumunta sa sa tabi ng isa here---uri-uriin pagpipilian.
Sinuman tandaan ba kung paano pagpili ng uri-uriin nagtrabaho?
Pumunta para dito.
>> MAG-AARAL: talaga pumunta sa pamamagitan ng isang order at lumikha ng isang bagong listahan.
At tulad naglalagay ka ng mga elemento sa, ilagay ang mga ito sa tamang lugar
sa bagong listahan.
>> Instruktor: Kaya na tunog higit na katulad ng pag-uuri ng pagpapasok ng.
Ngunit kung ikaw talaga malapit.
Ang mga ito ay halos katulad na.
Kahit na makakuha ang mga ito halo-halong up minsan.
Bago ito seksyon ko ay tulad, maghintay.
OK.
Kaya kung ano ang nais mong gawin ay-uri-uriin pagpili,
ang paraan na maaari mong isipin ang tungkol dito at ang paraan ng
Ko masisiguro na sinusubukan kong hindi upang makakuha ng ang mga ito halo-halong up, ito napupunta sa pamamagitan ng
at ito pinipili ang pinakamaliliit na numero at ito
naglalagay na sa simula ng iyong listahan.
Swaps itong ito sa na unang puwesto.
Talaga mayroon silang isang halimbawa para sa akin.
Kahanga-hanga.
Kaya lamang ng isang paraan upang isipin ang it-- seleksyon uri, piliin ang pinakamaliit na halaga.
At kami ay pagpunta sa tumakbo sa pamamagitan ng isang halimbawa
na sa tingin ko ay makakatulong dahil Sa tingin ko laging makatulong visual.
Kaya magsimula kami sa isang bagay na ganap na unsorted.
Red ay unsorted, berde ay pinagsunod-sunod.
Ang lahat ng ito magkaroon ng kahulugan sa isang segundo.
>> Kaya pumunta kami sa pamamagitan ng at umulit namin mula sa simula hanggang sa dulo.
At sabihin namin, OK, 2 ay ang aming pinakamaliit na numero.
Kaya kami ay pagpunta sa tumagal ng 2 at kami ay pagpunta upang ilipat ito sa harap ng aming array
dahil ito ay ang pinakamaliliit na numero na mayroon kami.
Kaya na kung ano ang ginagawa ito dito.
Lamang Ito ay pagpunta sa swap ang dalawang.
Kaya ngayon kami ng pinagsunod-sunod bahagi at unsorted bahagi.
At kung ano ang mahusay na tandaan tungkol sa pag-uuri seleksyon
lamang kami ng pagpili mula sa unsorted bahagi.
>> Ang Pinagbukud-bukod bahagi iwanang mag-isa ka lamang.
Mm-Hm?
>> MAG-AARAL: Paano malaman kung ano ang ang pinakamaliit na walang paghahambing nito
sa bawat iba pang mga halaga sa array.
Instruktor: Ginagawa ihambing ito.
Namin gustong nilaktawan ito.
Ito ay pangkalahatang lamang sa pangkalahatan.
Oo.
Kapag isulat namin ang code na ako ay Tiyaking makikita mo maging mas nasiyahan.
Ngunit una kang i-store na ito elemento bilang na ang pinakamaliit na.
Ihambing mo at mo sabihin, OK, ito sa mas maliliit?
Oo.
Panatilihin itong.
Narito ang mas maliit na ito?
Walang?
>> Ito ang iyong pinakamaliit, reassign ito sa iyong halaga.
At magagawa mong mas mas masaya kapag pumunta namin sa pamamagitan ng code.
Kaya pumunta kami sa pamamagitan ng, swap namin ito, kaya pagkatapos tinitingnan namin ang ito unsorted bahagi.
Kaya kami ay pagpunta upang piliin ang tatlong out.
Kami ay pagpunta sa ilagay ito sa sa Sa dulo ng aming pinagsunod-sunod na bahagi.
At lamang kami ng pagpunta sa panatilihin ang paggawa na, kapag ginawa iyon, at ginagawa iyon.
Kaya ito ay ang aming uri ng pseudocode dito.
Susubukan naming code ito dito sa isang segundo.
Ngunit isang bagay lamang upang maglakad sa pamamagitan ng sa isang mataas na antas.
Na iyong pupuntahan upang pumunta mula sa i ay katumbas ng 0 hanggang n minus 2.
Iyon ang isa pang pag-optimize.
Huwag mag-alala masyadong maraming tungkol dito.
Kaya bilang na iyong sinasabi.
Tulad ng sinasabi ni Jacob, kung paano ginagawa namin subaybayan kung ano ang aming minimum ay?
Paano ko malalaman namin?
Mayroon kaming upang ihambing lahat ng bagay sa aming listahan.
>> Kaya minimum na katumbas ng i.
Lamang Ito ay nagsasabi sa kasong ito sa index ng aming pinakamaliit na halaga.
Kaya pagkatapos ito ay pagpunta upang umulit sa pamamagitan ng at ito napupunta mula sa j katumbas i plus 1.
Kaya alam namin na na aming unang elemento.
Hindi namin kailangang ihambing ito sa sarili nito.
Kaya magsisimulang namin paghahambing nito sa susunod na isa siyang dahilan kung bakit ito ay i plus 1 sa n
minus 1, na kung saan ay ang dulo ng array doon.
At sinabi namin kung array sa j ay mas mababa sa array min,
pagkatapos namin reassign kung saan sa aming minimum na mga indeks ay.
>> At kung min ay hindi kapantay sa i, bilang sa kung saan kami ay bumalik sa paglipas dito.
Kaya gusto noong una naming ginawa ng isang ito.
Sa kasong ito, ito ay magsisimula sa zero, ito ay nagtatapos up pagiging dalawa.
Kaya min gagawin hindi katumbas i sa dulo.
Na hinahayaan alam sa amin na ang kailangan naming i-swap ang mga ito.
Pakiramdam ko ay tulad ng isang kongkreto halimbawa ay makakatulong sa higit pa kaysa ito.
Kaya makikita ko ang code na ito up sa iyo guys ngayon at sa tingin ko makikita itong maging mas mahusay.
>> Mga uri ay may posibilidad na gumana ang na paraan sa na ito ay madalas na mas mahusay na lamang upang makita ang mga ito.
Kaya kung ano ang gusto naming gawin ay muna naming gusto na ang pinakamaliit na
sangkap sa posisyon nito sa array.
Kung ano mismo ang sinasabi ni Jacob.
Kailangan mong mag-imbak na kahit papaano.
Kaya kami ay pagpunta sa simulan dito iterating sa ibabaw ng array.
Kami ay pagpunta sa sabihin ito sa aming una upang simulan lamang sa.
Kaya pupunta kaming magkaroon int pinakamaliit ay katumbas ng array sa i.
>> Kaya isang bagay na napansin, ang bawat oras na ito loop executes,
ay nagsisimula kami ng isang hakbang sa karagdagang kasama.
Kapag sinimulan namin tinitingnan namin ang isang ito.
Sa susunod na umulit namin sa pamamagitan ng, kami ay nagsisimula sa isang ito
at nagtatalaga ito sa aming pinakamaliit na halaga.
Kaya ito ay halos kapareho sa bubble-uuri-uri kung saan alam namin na pagkatapos ng isang pass,
ang huling elemento ay pinagsunod-sunod.
Sa pag-uuri ng pagpili, ito lamang ng kabaligtaran.
>> Sa bawat pass, alam namin na ang una ay pinagsunod-sunod.
Matapos ang pangalawang pass, ang pangalawang isa ay pinagsunod-sunod.
At bilang na nakita mo sa mga halimbawang slide, ang aming pinagsunod-sunod na bahagi ay nagpapanatili lamang lumalaki.
Kaya sa pamamagitan ng pagtatakda ng aming pinakamaliit na isa sa array ko, ang lahat ng mga ito ang ginagawa
ay constricting kung ano naghahanap kami sa gayon ay
upang i-minimize ang bilang ng paghahambing ginagawa namin.
Ay na magkaroon ng kahulugan sa lahat?
Kailangan ba ninyo sa akin upang tumakbo sa pamamagitan ng na muli mas mabagal o sa ibang salita?
Ikinagagalak kong.
OK.
>> Kaya naka-iimbak ng namin ang halaga sa puntong ito,
ngunit gusto rin naming iimbak ang index.
Kaya kami ay pagpunta upang mag-imbak ang posisyon ng pinakamaliit
isa, na kung saan ay lamang ng pagpunta sa maging i.
Kaya ngayon Jacob ay nasiyahan.
Mayroon kaming mga bagay na naka-imbak.
At ngayon ay kailangan naming pag-isipan sa pamamagitan ng ang unsorted bahagi ng array.
Kaya sa kasong ito na ito ay magiging aming unsorted.
Ito ay i.
OK.
>> Kaya kung ano ang namin ang pagpunta sa gawin ay magiging para sa isang loop.
Sa tuwing kailangan mong umulit sa pamamagitan ng isang array,
ang iyong isip ay maaaring pumunta sa para sa isang loop.
Kaya para sa ilang mga int k equals-- ano ang sa tingin namin
k ay pagpunta sa katumbas na magsimula sa?
Ito ay kung ano ang itinakda namin ang aming pinakamaliit halaga at namin nais na ihambing ito.
Ano ang gusto namin upang ihambing ang mga ito sa?
Ito ay magiging ang susunod na isa, i-right?
Kaya gusto namin k na nasimulan upang i plus 1 upang magsimula.
>> At gusto naming k sa kasong ito namin nai laki na nakaimbak dito,
upang maaari naming lamang gamitin ang laki.
Sukat ng pagiging ang laki ng array.
At gusto lang namin sa -update k sa pamamagitan ng isa sa bawat oras.
Ayos.
Kaya ngayon ay kailangan naming hanapin ang pinakamaliit na elemento dito.
Kaya kung umulit namin sa pamamagitan ng, namin gustong sabihin, kung array sa k
Mababa sa aming pinakamaliit na value-- ito ay kung saan kami ay talagang
pagpapanatili ng track ng kung ano ang ang pinakamaliit na here--
pagkatapos ay nais naming reassign kung ano ang aming pinakamaliit na halaga ay.
>> Nangangahulugan ito na, oh, kami ay iterating sa pamamagitan dito.
Anuman ang halaga ay dito ay Hindi aming pinakamaliit na bagay.
Hindi namin gusto ito.
Gusto naming reassign ito.
Kaya kung kami ay reassigning ito, kung ano ang ginagawa tingin mo ay maaaring maging sa code na ito dito?
Gusto naming reassign pinakamaliit at posisyon.
Kaya kung ano ang pinakamaliit na ngayon?
MAG-AARAL: Ang array k.
Instruktor: Ang array k.
At kung ano ang posisyon ngayon?
Ano ang mga indeks ng ang aming pinakamaliit na halaga?
Ito ay k lamang.
Kaya array k, k, tutugma ang mga ito.
Kaya gusto naming reassign iyon.
At pagkatapos ay pagkatapos naming nakita ng aming mga pinakamaliliit na, kaya sa dulo ng ito para sa loop
dito nakita namin kung ano ang aming pinakamaliit halaga ay, upang magpalit namin ito lamang.
Sa kasong ito, tulad ng sinasabi ng ating pinakamaliit na halaga ay wala dito.
Ito ang aming pinakamaliit na halaga.
>> Gusto lang namin na magpalit ito dito, na ano na magpalitan ng function sa ibaba
ginawa, na nagsulat up namin lamang -sama ng ilang minuto ang nakalipas.
Kaya dapat itong pamilyar.
At pagkatapos ay lamang umulit sa pamamagitan ng hanggang umabot sa lahat ng mga paraan
sa dulo, na nangangahulugan na ang mo may zero na mga elemento na unsorted
at lahat ng iba pa ay pinagsunod-sunod.
Magkaroon ng kahulugan?
Isang kaunti pa concretely?
Ang code na tulong?
>> MAG-AARAL: Para sa isang sukat, hindi ka talagang tukuyin ito o baguhin ito,
kung paano ang kilala ito?
>> Instruktor: Kaya ang isang bagay sa mapansin dito ay ang laki ng int.
Kaya namin ang iyong sinasabi sa sort-- pag-uuri ay isang pagpapaandar sa case-- ito
-uri pagpipilian, ito ay lumipas na in gamit ang pag-andar.
Kaya kung hindi ito pumasa sa sa, gusto mong gawin ang isang bagay
tulad ng haba ng array o gusto mong umulit sa pamamagitan ng
upang mahanap ang haba.
Ngunit dahil ito ay lumipas na in, maaari naming gamitin lamang ito.
Ipagpalagay mo lang na ang gumagamit nagbigay sa iyo ng wastong laki na
aktwal na kumakatawan sa isang laki ng iyong array.
Cool?
>> Kung guys ay may anumang problema sa mga o gusto ng higit pang mga kasanayan sa coding uri
sa iyong sarili, dapat mong pumunta sa study.cs50.
Ito ay isang tool.
Ang mga ito ay isang checker na Maaari mong aktwal na magsulat.
Ginagawa nila pseudocode.
Ang mga ito ay higit pang mga video at mga slide kabilang ang mga ginagamit ko dito.
Kaya kung nararamdaman pa rin ng isang maliit na malabo, subukan na out.
Tulad ng nakasanayan, ay makipag-usap sa akin, masyadong.
Tanong?
>> MAG-AARAL: Sigurado ka sinasabi sa laki ay dati nang tinukoy?
Instruktor: Oo.
Laki ay dati nang tinukoy up dito sa function na pagpapahayag.
Kaya ipagpalagay mo na itong ma-ipinasa sa sa pamamagitan ng user, at alang-alang sa pagiging simple, ang
kami ay pagpunta sa ipinapalagay na ang nagbigay sa amin ng gumagamit ang tamang laki.
Ayos.
Kaya na-uri-uriin pagpipilian.
Guys, alam ko namin ang pag-aaral ng maraming ngayon.
Ito ay isang siksikan na data para seksyon.
Kaya sa na, kami ay pagpunta upang pumunta sa pag-uuri ng pagpapasok ng.
>> OK.
Kaya bago na mayroon kaming gawin aming runtime pag-aaral dito.
Kaya sa pinakamahusay na kaso, Binigyan dahil nagpakita ako sa iyo
ang talahanayan na ako uri ng ibinigay ito ang layo.
Ngunit pinakamahusay na kaso runtime, ano ang gagawin namin sa tingin?
Pinagsunod-sunod ang lahat.
Nakalapat N.
Kahit sino ay may isang paliwanag para sa kung bakit ang iyong palagay?
>> MAG-AARAL: Nagpapatakbo ka ng paghahambing through--
Instruktor: I-right.
Naghahambing ka sa pamamagitan ng.
Sa bawat pag-ulit, kahit na naka-decrementing namin ito sa pamamagitan ng isa,
pa rin naghahanap ka sa pamamagitan ng lahat ng bagay upang mahanap ang pinakamaliit na isa.
Kaya kahit na ang iyong pinakamaliit na halaga Nandito sa simula,
naghahambing ka pa rin ito laban sa lahat ng iba pa
upang tiyakin na ito ay ang pinakamaliit na bagay.
Kaya makakapunta ka tumatakbo sa pamamagitan ng humigit-kumulang n nakalapat ulit.
Lahat ng karapatan.
At ano ang pinakamasamang sitwasyon?
Gayundin n nakalapat dahil na iyong pupuntahan na ginagawa na parehong pamamaraan.
Kaya sa kasong ito, seleksyon -uri-uriin ay may isang bagay
na tinatawag din namin inaasahang runtime.
Kaya sa iba, alam namin lamang ang upper at lower mga hangganan.
Depende sa kung paano mabaliw ang aming list o kung paano unsorted ito ay,
mag-iba ang mga ito sa pagitan ng n o n nakalapat.
Hindi namin alam.
>> Ngunit dahil sort pagpili ay may parehong pinakamasama at pinakamahusay na kaso, na sinasabi sa atin na
kung ano man ang uri ng pag-input namin mayroon, kung ito ay ang ganap na
pinagsunod-sunod o ganap na baligtarin pinagsunod-sunod, ito ay
pagpunta sa gawin ang parehong dami ng oras.
Kaya sa kasong iyon, kung tandaan mula sa aming mga talahanayan,
ito talaga ay nagkaroon ng isang halaga na ang dalawang uri ay walang,
na kung saan ay inaasahan runtime.
Kaya alam namin na sa tuwing nagsasagawa kami ng pag-uuri ng pagpili,
ito ay garantisadong magpatakbo ng isang n nakalapat oras.
Walang pagbabagu-bago doon.
Lamang Ito ay inaasahan.
At, muli, kung gusto mong matuto nang higit pa, kumuha ng CS 124 sa Spring.
Lahat ng karapatan.
Nakita namin na ang isang ito.
Ayos.
-Uri-uriin Kaya pagpapasok.
At marahil ako pupunta sa pamamagitan ng alab na ito.
Hindi ko ay magkakaroon ka guys code ito.
Makikita lang namin maglakad sa pamamagitan nito.
Kaya pag-uuri ng pagpapasok ng uri ay ng mga katulad na uri-uriin seleksyon
sa na mayroon kami ng parehong unsorted at pinagsunod-sunod na bahagi ng array.
>> Ngunit kung ano ang iba't ibang ay na bilang pumunta kami sa pamamagitan ng isa isa,
tumagal lamang namin ang anumang bilang ang susunod sa aming unsorted,
at tama ang uri-uriin ito sa aming pinagsunod-sunod array.
Ito gawing mas kamalayan sa isang halimbawa.
Kaya lahat ay nagsisimula bilang unsorted, nais lamang na may-uri-uriin pagpipilian.
At kami ay pagpunta sa uri-uriin ito sa Pataas na pagkakasunud-sunod ng aming naging.
Kaya sa aming mga unang pass kumuha namin ang unang halaga
at sabihin namin, OK, ikaw ay ngayon sa isang listahan sa pamamagitan ng iyong sarili.
>> Dahil ikaw ay nasa isang listahan sa pamamagitan ng iyong sarili, ikaw ay pinagsunod-sunod.
Binabati kita sa pagiging ang unang elemento sa array.
Ginagamit mo na pinagsunod-sunod sa lahat sa inyong sarili.
Kaya ngayon kami ng pinagsunod-sunod at isang unsorted array.
Kaya ngayon kumuha namin ang unang.
Ano ang mangyayari sa pagitan dito at dito ay ang sasabihin namin,
OK, kami ay pagpunta sa tumingin sa unang halaga ng aming unsorted array
at kami ay pagpunta sa pag-input na ito sa sarili tamang lugar sa Pinagbukud-bukod ng array.
>> Kaya ano ang gagawin namin ay nagsasagawa kami ng 5 at sabihin namin, OK, 5 ay mas malaki kaysa sa 3,
kaya magpasok lamang namin ito ng tama sa kanan ng iyon.
Humihingi kami ng mabuti.
Kaya pagkatapos ay pumunta sa kami sa aming susunod na isa.
At nagsasagawa kami ng 2.
Sabihin namin, OK, 2 Mababa sa 3, upang malaman namin na ito
kailangang maging sa harap ng aming listahan ngayon.
Kaya kung ano ang ginagawa namin ay itulak namin ang 3 at 5 pababa at ilipat namin 2 sa ang unang slot.
Kaya namin ang pagpapasok lamang ito sa tamang lugar dapat itong maging.
>> Pagkatapos ay tinitingnan namin ang aming sa tabi ng isa, at sabihin namin 6.
OK, 6 ay mas malaki sa lahat ng bagay sa aming pinagsunod-sunod array,
kaya i-tag namin lang ito sa sa dulo.
At pagkatapos ay tinitingnan namin ang 4.
4 ay mas mababa sa 6, ito ay mas mababa sa 5 ngunit ito ay mas malaki kaysa sa 3.
Kaya ipasok namin lang ito pakanan papunta sa gitna sa pagitan ng 3 at 5.
Kaya upang gumawa ng na ang isang maliit na kaunti pa kongkreto,
narito ang uri ng ideya ng kung ano ang nangyari.
Kaya para sa bawat unsorted elemento, namin matukoy kung saan sa Pinagbukud-bukod bahagi
ito ay.
>> Kaya isinasaisip ang pinagsunod-sunod at unsorted,
mayroon kaming upang tumawid sa pamamagitan ng at figure kung saan ito umaangkop sa Pinagbukud-bukod ng array.
At ipasok namin ito sa pamamagitan ng paglilipat ng mga mga elemento sa kanan ng ito pababa.
At pagkatapos naming panatilihin lamang iterating sa pamamagitan ng hanggang namin
magkaroon ng isang ganap na pinagsunod-sunod na listahan kung saan unsorted ngayon ay zero
at Pinagbukud-bukod tumatagal ng hanggang sa kabuuan ng aming listahan.
Kaya, muli, upang gumawa ng mga bagay kahit na higit pa kongkreto, mayroon kaming pseudocode.
>> Kaya isa lamang para i ay katumbas ng 0 hanggang n minus 1,
ito lamang ay ang haba ng aming array.
Mayroon kaming ilang mga elemento na katumbas ng ang unang array o unang mga indeks.
Itinakda namin j katumbas na iyon.
Kaya habang j ay mas malaki sa zero at ang array, j minus 1
ay mas malaki sa elemento, kaya ang lahat na ang ginagawa
ay tinitiyak na talaga kumakatawan sa iyong j
ang unsorted bahagi ng array.
>> Kaya habang mayroong mga bagay pa rin upang pagbukud-bukurin at j minus isa is-- kung ano
ay siya ng elemento?
J ay hindi kailanman tinukoy dito.
Ito ay uri ng nakakainis.
OK.
Pa rin.
Kaya j minus 1, naka-check ang elemento bago ito.
Sinasabi mo, OK, ay ang elemento bago nasaan ako am-- sabihin
talaga gumuhit ito.
Kaya sabihin nating ito ay tulad ng sa aming ikalawang pass.
Kaya i ay magiging katumbas sa 1, na kung saan ay dito.
>> Kaya i ay magiging katumbas ng 1.
Ito ay magiging 2, 4, 5, 6, 7.
Lahat ng karapatan.
Kaya aming mga elemento sa kasong ito ay magiging katumbas ng 4.
At mayroon kaming ilang j na magiging katumbas ng 1.
Oh, j ay decrementing.
Iyon ay kung ano ito.
Kaya j ay katumbas ng i, kaya kung ano ito ay sinasabi ay ang bilang ilipat naming inaabangan ang panahon,
ginagawa lang namin sigurado na hindi namin sa paglipas ng
pag-index ng paraang ito kung kailan namin sinusubukan magpasok ng mga bagay sa aming pinagsunod-sunod na listahan.
>> Kaya kapag j ay katumbas ng 1 sa kasong ito at array j minus one-- kaya array j minus 1
2 sa case-- kung na mas malaki kaysa sa elemento,
pagkatapos ang lahat ng ito ay ginagawa ay nagbabagong mga bagay pababa.
Kaya sa kasong ito, array j minus isa magiging array zero, na kung saan ay 2.
2 ay hindi mas mataas kaysa sa 4, kaya ito ay hindi maisagawa.
Kaya hindi ilipat ang shift pababa.
Ano ang ginagawa dito ay lamang paglipat ng iyong Pinagbukud-bukod array pababa.
Sa kasong ito, talaga, namin maaaring do-- gumawa ng ang 3 ipaalam.
Kaya, kung hindi kami upang maglakad sa pamamagitan ng sa halimbawang ito, hindi namin ngayon dito.
Ito ay pinagsunod-sunod.
Ito ay unsorted.
Cool?
Kaya i ay katumbas ng 2, kaya ang aming elemento ay katumbas ng 3.
At ang aming j ay katumbas ng 2.
Kaya umaasa kaming sa pamamagitan at kami sabihin, OK, ay array j minus isa
mas malaki kaysa sa elemento na kaming naghahanap sa?
At ang sagot ay oo, tama?
4 ay mas mataas kaysa sa 3 at j 2, kaya executes ang code na ito.
>> Kaya ngayon kung ano ang ginagawa namin ang isang array sa 2, kaya dito mismo, swap namin ang mga ito.
Kaya sabihin lang namin, OK, array sa 2 ay pupunta na ngayon upang maging 3.
At j ay pagpunta upang pumatas j minus 1, na kung saan ay 1.
Iyon ay kasindak-sindak, ngunit mo guys makakuha ng ideya.
J ay katumbas ng 1 ngayon.
At array j ay lamang ng pagpunta sa maging katumbas ng aming mga elemento, na kung saan ay 4.
Mabubura ko ng isang bagay na hindi ko dapat mayroon o miswrote isang bagay,
ngunit guys makuha ang ideya.
>> Ito ilipat sa n.
At pagkatapos ay kung ito ay, gagawin ito loop muli at nais itong sabihin, OK, j ay 1 ngayon.
At array j minus 1 2 ngayon.
2 mas mababa sa aming mga elemento?
Walang?
Nangangahulugan iyon na hindi namin Ipinasok ang elementong ito
sa tamang lugar sa aming pinagsunod-sunod array.
Pagkatapos ay maaari naming tumagal ito at sabihin namin, OK, ang aming pinagsunod-sunod array ay dito.
At nais itong tumagal ito bilang 6 at maging tulad ng, OK, 6 na mas mababa ang bilang na ito?
Walang?
Ayos.
Humihingi kami ng multa.
>> Gawin itong muli.
Sabihin namin 7.
7 mas mababa sa dulo sa aming mga Pinagbukud-bukod array?
Hindi.
Kaya hindi namin pinong.
Kaya ito ay pinagsunod-sunod.
Talaga ginagawa ang lahat ng ito ay nagsasabing ito ay tumagal
sa unang elemento ng ang iyong unsorted array,
malaman kung saan ito napupunta sa iyong Pinagbukud-bukod ng array.
At ito lamang ay tumatagal ng pag-aalaga ng swaps upang gawin iyon.
Talaga ka lamang pagpapalit hanggang sa ito ay nasa tamang lugar.
Ang visual na imahe ay na ikaw ay paglipat ng lahat ng bagay down na sa pamamagitan ng paggawa na.
>> Kaya tulad ng kalahati ng bubble-uuri-esque.
Tingnan ang pag-aaral 50.
Masidhing kong inirerekumendang sinusubukan sa code na ito sa iyong sariling.
Kung mayroon kang anumang mga isyu o nais mong makita ang mga sample code para sa isang pag-uuri ng pagpapasok ng,
mangyaring ipaalam sa akin.
Ako ay palaging sa paligid.
Kaya pinakamasama kaso runtime at pinakamahusay na kaso runtime.
Habang ikaw tao Nakita mula sa talahanayan ko na Nagpakita sa iyo, ito ay pareho n nakalapat at n.
>> Kaya uri ng pagpunta off ng kung ano ang namin ang usapan tungkol sa aming mga nakaraang mga uri, pinakamalala
kaso runtime ay kung ganap na ito ay unsorted,
mayroon kaming upang ihambing ang lahat ng mga oras na ito n.
Ginagawa namin ang isang buong maraming mga paghahambing dahil kung ito ay sa reverse pagkakasunud-sunod,
kami ay pagpunta sa sabihin, OK, ito ay pareho, ito ay mabuti,
at ang isang ito ay magkakaroon upang maihambing laban sa unang isa upang ilipat pabalik.
At bilang makuha namin patungo sa ang huli, mayroon kaming
upang ihambing, ihambing, at ihambing kumpara sa lahat ng bagay.
>> Kaya ito ay nagtatapos up pagiging humigit-kumulang n nakalapat.
Kung ito ay tama pagkatapos mong sabihin, OK, 2, ikaw ay mabuti.
3, naka-kumpara sa 2.
Kayo ay mabuti.
4, ihambing mo lamang na ang buntot.
Kayo ay mabuti.
6, nakakasabay sa likod o hulihan, ikaw ay multa.
Kaya para sa bawat lugar kung ito ay nasa pinagsunod-sunod, nagsasagawa ka ng isang paghahambing.
Kaya n lamang.
At dahil mayroon kaming pinakamahusay na kaso runtime ng n at isang pinakamasama kaso runtime ng n
nakalapat, wala kaming inaasahang runtime.
>> Depende lang ito sa kaguluhan ng aming listahan doon.
At muli, isa pang graph at isa pang table.
Kaya pagkakaiba sa pagitan ng mga uri.
Lamang ako ng pagpunta sa Breeze sa pamamagitan, ako parang na-usapan natin ang malawakan
tungkol sa kung paano nila ang lahat ng uri ng mag-iba at i-link nang magkasama.
Kaya magsamang bumaybay-uri-uriin na ang huli Dapat kong mayamot mo guys sa.
Kami ay may kaakit-akit na makulay na larawan.
Kaya sumanib-uuri ay isang recursive algorithm.
Kaya alam mo kung ano ang guys isang recursive function ay?
>> Sinuman gustong sabihin?
Gusto mong subukan?
Kaya isang recursive function ay lamang isang function na tawag mismo.
Kaya kung guys ay pamilyar sa pagkakasunud-sunod Fibonacci,
na itinuring na recursive dahil Dadalhin ka sa nakaraang dalawang
at idagdag ang mga ito nang sama-sama upang makuha ang iyong susunod na isa.
Kaya recursive, ako palaging tingin ng Rekursiyon bilang tulad ng isang spiral
kaya ikaw ay tulad ng spiraling down sa mga ito.
Ngunit ito ay isang function na lamang na pagtawag mismo.
>> At, talaga, talagang mabilis ako maaaring ipakita sa iyo kung ano na kamukha.
Kaya recursive dito, kung tiningnan namin, ito ay ang recursive na paraan upang sabihin sa ilang sa ibabaw ng isang array.
Kaya lahat na ginagawa namin ay mayroon kaming kabuuan ng function
kabuuan na tumatagal ng isang sukat at isang array.
At kung napansin mo, laki decrements sa pamamagitan ng isa sa bawat oras.
At lahat ng ginagawa nito ay kung ang x ay katumbas ng zero-- kaya kung ang laki ng array
ay katumbas ng zero-- ay nagbalik ito sa zero.
>> Kung hindi man sums ito sa ganitong huling elemento ng array,
at pagkatapos ay tumatagal ng isang kabuuan ng ang natitirang bahagi ng array.
Kaya lang nagbabagang ito pababa sa mas maliit at mas maliit na problema.
Long kuwento maikli, Rekursiyon, function na tawag mismo.
Kung iyon ang lahat na nakuha sa labas ng ito, iyon ang isang recursive function ay.
Kung kumuha ka ng 51, makakakuha ka ng napaka, napaka-kumportable sa Rekursiyon.
Ito ay talagang cool.
Ito ginawa kahulugan sa tulad ng 03:00 isang gabi out.
At ako ay tulad ng, kung bakit na Hindi ko kailanman gamitin ito?
>> Kaya para sa pag-uuri-merge, talaga kung ano ang pagpunta sa gawin ay ito
pagpunta sa masira ito down at masira ito pababa hanggang sa ito lamang ang nag-iisang elemento.
Ang nag-iisang elemento ay madaling ayusin.
Nakita namin na.
Kung mayroon kang isang elemento, ito ay na itinuturing na pinagsunod-sunod.
Kaya sa isang input ng n elemento, kung n ay mas mababa sa 2,
bumalik lamang dahil paraan na ito ay alinman sa 0 o 1 bilang nasaksihan namin.
Yaong ay itinuturing na pinagsunod-sunod ng mga elemento.
>> Kung hindi man masira ito sa kalahati.
-Uri-uriin ang unang kalahati, uri-uriin ang pangalawang kalahati, at pagkatapos ay pagsamahin ang mga ito nang magkakasama.
Bakit ay tinatawag na ito-uri-uriin merge.
Kaya mayroon kaming dito namin uri-uriin ang mga ito.
Kaya panatilihin namin ang pagkakaroon ng mga ito hanggang sa laki ng array ay 1.
Kaya kapag 1, bumalik lang kami dahil ito ay isang Pinagbukud-bukod array,
at ito ay isang Pinagbukud-bukod array, at iyon ang Pinagbukud-bukod ng array, lahat kami ay pinagsunod-sunod.
Kaya pagkatapos ay kung ano ang ginagawa namin ay namin simulan pinagsasama ang mga iyon nang magkakasama.
>> Kaya ang paraan na makakaya mo isipin ang tungkol sa pagsasama ay
alisin mo lamang ang mas maliit bilang ng bawat isa sa mga sub array
at ikabit lamang ito sa lumitaw array.
Kaya't kung tiningnan mo dito, kapag mayroon kami mga hanay ng mayroon kaming 4, 6, at 1.
Kapag gusto naming pagsamahin ang mga ito, tinitingnan namin ang mga unang dalawang
at sabihin namin, OK, 1 ay mas maliit, ito ang papunta sa front.
4 at 6, walang upang ihambing ang ito sa, i-tag lang ito sa sa dulo.
>> Kapag pagsamahin namin ang dalawang, namin lamang gawin ang mga mas maliit na ang isa sa mga dalawang,
kaya 1.
At ngayon ginagawa namin ang mas maliit sa dalawang, kaya 2.
Mas maliit sa dalawang, 3.
Mas maliit sa dalawang, 4, 5, 6.
Kaya ka lamang ng paghila off ang mga ito.
At dahil na sila na pinagsunod-sunod sa nakaraan,
Mayroon ka lamang ng isa paghahambing sa bawat oras doon.
Kaya nang higit pa code dito, representasyon lamang.
Kaya simulan mo sa gitna at ka-uri-uriin kaliwa at kanan
at pagkatapos ay pagsamahin mo lamang ang mga naka.
>> At wala kaming code para magsamang bumaybay dito mismo.
Ngunit, muli, kung pumunta ka sa pag-aaral 50, magkakaroon ito maging doon.
Kung hindi man ay makipag-usap sa akin kung ikaw ay lito pa rin.
Kaya cool na bagay dito ay ang pinakamahusay na sitwasyon, pinakamasamang sitwasyon, at inaasahan runtime
ang lahat ng log-in n, na ay malayo mas mahusay kaysa sa hindi namin
nakita para sa natitirang bahagi ng aming mga klase.
Nasaksihan namin n nakalapat at kung ano ang namin ang aktwal na
makarating dito ay n log n, na mahusay.
>> Tumingin sa kung magkano ang mas mahusay na.
Ang nasabing mga gandang curve.
Kaya lubos na mas mahusay.
Kung sakaling maaari, gamitin ang magsamang bumaybay-uri-uriin.
Ito ay i-save sa iyo ng oras.
Pagkatapos muli, tulad ng sinabi namin, kung ikaw ay pababa sa mas mababang rehiyon,
hindi ito gawin iyon karami ng isang pagkakaiba.
Makakakuha ka ng hanggang sa libu-libo at libu-libong mga input,
gusto mo talagang isang mas mahusay na algorithm.
At, muli, ang aming kaibig-ibig talahanayan ng lahat ng uri na natutunan sa iyo guys ngayon.
>> Kaya alam ko naging isang siksikan na araw.
Ito ay hindi kinakailangan ng pagpunta upang tulungan ka sa iyong pset.
Pero gusto ko lang gumawa ng disclaimer seksyong iyon ay hindi lamang tungkol sa psets.
Ang lahat ng mga materyales na ito ay patas laro para sa iyong midterms.
At din kung gagawin mo magpatuloy sa may CS, ang mga ito ay talagang mahalaga batayan
na kakailanganin mo upang malaman.
Kaya ilang mga araw ay magiging isang kaunti pa pset tulong,
ngunit ang ilang linggo ay magiging higit pa aktwal na nilalaman
na maaaring hindi mukhang super kapaki-pakinabang sa iyo sa ngayon,
ngunit ipinapangako ko kung patuloy kang sa ay napaka, napaka-kapaki-pakinabang.
>> Kaya na ito para sa na seksyon.
Pababa sa wire.
Ginawa ko ito sa loob ng isang minuto.
Ngunit may kang pumunta.
At ako ay may donut o kendi.
Ay sinuman allergy upang anumang bagay, sa pamamagitan ng ang paraan?
Mga itlog at gatas.
Kaya donut ang hindi?
OK.
Lahat ng karapatan.
Chocolate walang?
Starburst.
Starbursts ang mga magandang.
OK.
Kami ay pagpunta sa may Starburst sa susunod na linggo pagkatapos.
Iyon ay kung ano ang makikita na nakukuha ko.
Ikaw guys magkaroon ng isang mahusay na linggo.
Basahin ang iyong mga spec.
>> Ipaalam sa akin kung mayroon kang anumang mga katanungan.
Pset dalawang mga marka ay dapat na out sa iyo sa pamamagitan ng Huwebes.
Kung mayroon kang anumang mga katanungan tungkol sa kung paano ko namarkahan ang isang bagay
o kung bakit minamarkahan ko ng isang bagay sa paraan ko nag, mangyaring mag-email sa akin, ay makipag-usap sa akin.
Ako ay isang maliit na mabaliw na ito linggo, ngunit nangangako ako
Ako ay tumugon pa rin sa loob ng 24 na oras.
Kaya magkaroon ng isang mahusay na linggo, sa lahat.
Good luck sa iyong pset.