David MALAN: Lahat ng karapatan. Kami ay bumalik. Kaya sa segment na ito sa programming kung ano Akala ko gusto naming gawin ay isang halo ng mga bagay. One, gawin ang isang maliit na bit ng isang bagay na kamay-on, albeit paggamit ng isang mas mapaglaro programming environment-- isa na ay demonstrative ng eksakto ang uri ng mga ideya kami ay pakikipag-usap tungkol sa, ngunit ng kaunti pa pormal. Two, tingnan ang ilan sa ang mga teknikal na paraan na ang isang programmer ay tunay na malutas problema tulad ng mga naghahanap problema na kami ay tumingin sa bago at din ng isang mas panimula kagiliw-giliw na problema ng pag-uuri. 

Lang namin ipinapalagay mula sa makakuha ng pumunta na na phone book ay pinagsunod-sunod, ngunit na nag-iisa ay talagang uri ng isang mahirap problema sa maraming iba't ibang paraan upang malutas ito. Kaya gagamitin namin ang mga ito bilang isang klase ng mga problema kinatawan ng mga bagay na maaaring lutasin sa pangkalahatan. At pagkatapos ay gagamitin namin makipag-usap tungkol sa ilang mga detalye kung ano ang ay tinatawag na data structures-- may interes paraan tulad listahan ng link at hash talahanayan at mga puno na isang programmer gagawin talaga gamitin at sa pangkalahatan gamitin sa isang whiteboard upang ipinta isang larawan ng kung ano ang kanyang Envisions para sa pagpapatupad ilang piraso ng software. 

Kaya sabihin gawin ang hands-on bahaging muna. Kaya lang makuha ang iyong mga kamay marumi na may isang kapaligiran tinatawag scratch.mit.edu. Ito ay isang kasangkapan na ginagamit namin sa aming undergraduate class. Kahit na ito ay naka-disenyo para sa edad 12 at pataas, ginagamit namin ito para sa up bahagi ng na lubos ng kaunti dahil ito ay isang nice, fun graphical na paraan ng pag-aaral isang maliit na bagay tungkol sa programming. Kaya magtungo sa URL na iyon, kung saan mo dapat makita ang isang page lubos na tulad nito, at sige at i-click Sumali Scratch sa kanang tuktok at pumili ng isang username at isang password at sa huli makakuha ng iyong sarili isang account-- scratch.mit.edu. Akala ko gusto ko bang gamitin ito bilang isang pagkakataon unang upang ipakita na ito. Ang isang tanong ay dumating up sa panahon ng pahinga tungkol sa kung ano ang tunay na code ganito ang hitsura. At kami ay pakikipag-usap pagkatapos patamaan tungkol sa C, in particular-- lalo na ng isang mas mababang antas sa isang mas lumang wika. At ako lamang ay isang mabilis Paghahanap sa Google upang mahanap C code para sa binary paghahanap, ang algorithm na kami magamit upang maghanap na phone book nang mas maaga. Ang partikular na halimbawa, ng mga kurso, ay hindi paghahanap ng isang phone book. Ito lamang naghahanap ng isang buong grupo ng mga numero sa memory ng computer. Ngunit kung nais mong lamang makakuha ng isang visual kahulugan ng kung ano ang isang aktwal na mga programa wika ganito ang hitsura, ang hitsura nito isang maliit na bagay tulad nito. Kaya ito ay tungkol sa 20-plus, 30 o kaya mga linya ng code, ngunit ang pag-uusap namin ay nagkakaroon ng higit sa pahinga ay tungkol sa kung paano ito aktwal na makakakuha morphed sa mga zero at mga at kung hindi lamang ang maaari mong ibalik sa dati na proseso at pumunta mula zero at mga i-back sa code. 

Sa kasamaang palad, ang proseso ay kaya transformative na ito ay isang pulutong mas madali kaysa sa sinabi tapos na. Nagpunta ako maaga at aktwal na naka na programa, Binary Search, sa mga zero at mga bago sa pamamagitan ng paraan ng isang programa na tinatawag na Compiler Ang na ako mangyari na magkaroon dito mismo sa aking Mac. At kung pagtingin mo ang mga screen dito, mismong tumututok sa mga middle anim na haligi lamang, makikita mo lamang zero at mga. At ang mga ay ang mga zero at mga bago na gumawa ng sulat eksakto na searching programa. 

At sa gayon ang bawat tipak ng limang bits, bawat byte ng mga zero at mga bago dito, kumakatawan ang ilang mga pagtuturo karaniwang sa loob ng isang computer. At sa katunayan, kung ka na marinig ang marketing slogan "Intel loob" - na, siyempre, ay nangangahulugan lamang mayroon kang isang Intel CPU o utak sa loob ng computer. At kung ano ang ibig sabihin nito upang maging isang CPU ay na ikaw ay may isang pagtuturo set, kaya na magsalita. 

Bawat CPU sa mundo, marami sa ang mga ito na ginawa ng Intel mga araw na ito, nauunawaan ng isang may hangganan bilang ng mga tagubilin. At ang mga tagubilin ay kaya mababa na antas habang nagdadagdag ito ng dalawang numero ng magkasama, multiply ang dalawang numero ng magkasama, galaw ng mga piraso ng data mula dito sa dito sa memory, kundi itong impormasyon mula dito sa dito sa memorya, at iba pa forth-- kaya napaka, napaka mababang antas, halos electronic detalye. Ngunit sa mga mathematical operations kaisa sa kung ano ang napag-usapan namin kanina, ang representasyon ng data bilang mga zero at mga, maaari kang bumuo ng up ang lahat ng bagay na ang isang computer ay maaaring gawin ngayon, kung ito ay tekstuwal, graphical, musical, o kung hindi man. 

Kaya ito ay mas madali upang makakuha nawala sa mga damo ng mabilis. At mayroong isang pulutong ng mga syntactical hamon kung saan kung gumawa ka ng ang pinakasimpleng, stupidest ng typos wala sa mga programa gagana kung ano pa man. At kaya sa halip ng paggamit ng isang wika tulad ng C na ito umaga, Akala ko ay ito ay mas masaya upang aktwal na gawin isang bagay na mas visual, na kung saan habang dinisenyo para sa mga bata ay talagang isang perpektong paghahayag ng isang aktwal na programming language-- lang ang mangyayari sa gamitin ang mga larawan sa halip ng teksto upang kumatawan sa mga ideya. 

Kaya sa sandaling ikaw ay sa katunayan ay may isang account sa scratch.mit.edu, i-click ang pindutan ng Gumawa sa pinakamataas na naiwan, sa mga site. At dapat mong makita ang isang kapaligiran tulad ng ang isa ako tungkol sa upang makita ang sa aking screen dito. At kami gastusin lamang ng isang maliit bit ng oras sa paglalaro dito. Sabihin makita kung hindi lahat kami ay maaaring malutas ang ilang problema nang magkasama sa mga sumusunod na paraan. 

Kaya kung ano ang makikita mo sa loob ng environment-- at talagang lang basta hayaan akin i-pause. Ay sinuman na hindi dito? Hindi dito? OK. Kaya hayaan mo akong ituro ng ilang mga katangian ng environment na ito. 

Kaya sa kaliwang tuktok ng screen, kami may stage ni Scratch, kaya na magsalita. Scratch ay hindi lamang ang pangalan ng programming language; ito ay din ang pangalan ng pusa na nakikita mo sa pamamagitan ng default doon sa orange. Siya ay nasa isang yugto, kaya marami tulad ng inilarawan ko ang pagong mas maaga bilang kabilang sa hugis-parihaba white board kapaligiran. Mundo na ito pusa ay nakakulong ganap sa na rectangle up tuktok doon. 

Samantala, sa kanan kamay gilid dito, ito ay lamang ng isang script area, blangkong slate kung ikaw ay. Ito ay kung saan kami ay pagpunta sa sumulat ang aming mga programa sa loob lamang ng ilang sandali. At ang malaking bloke na dapat namin gamitin upang isulat ito program-- ang puzzle piraso, kung ikaw will-- ay mga karapatan dito sa gitna, at sila ay ikinategorya sa pamamagitan ng pag-andar. Kaya, halimbawa, ako pagpunta sa sige at nagpapakita ng hindi bababa sa isa sa mga. Ako pagpunta sa sige at i-click ang Control kategoryang up tuktok. 

Kaya ito ang mga kategorya up tuktok. Pupunta ako sa i-click ang Control kategorya. Sa halip, ako pagpunta sa i-click ang Mga Kaganapan kategorya, ang pinakaunang isa up tuktok. At kung gusto mong upang sundin kasama kahit tulad ng ginagawa namin ito, ikaw ay lubos na maligayang pagdating sa. Pupunta ako sa i-click at i-drag ito unang isa, "kapag berdeng bandila click." At pagkatapos ay ako pagpunta sa drop ito lamang halos sa tuktok ng aking blangko slates. 

At kung ano ang maganda tungkol Scratch ay na ito palaisipan piraso, kapag interlocked sa iba pang mga puzzle piraso, ay pagpunta sa gawin literal kung ano ang mga piraso ng puzzle sabihin na gawin. Kaya, halimbawa, Scratch ay tama ngayon sa gitna ng kanyang mundo. Ako pagpunta sa sige at piliin ang ngayon, sabihin nating, ang kategorya Motion, kung nais mong upang gawin ang same-- kategoryang Motion. At ngayon mapansin mayroon akong isang buong grupo ng mga piraso ng puzzle dito na, muli, uri ng gawin kung ano ang sinasabi nila. At ako pagpunta sa sige at i-drag and drop ang ilipat bloke karapatan sa paglipas dito. 

At mapansin na sa lalong madaling makakuha ka malapit sa ibaba ng "green bandila nag-click "na pindutan, notice kung paano ang isang puting linya ay lilitaw, na parang ito ay halos magnetic, ito ay nagnanais na pumunta doon. Ipaalam lamang sa pumunta, at ito ay snap sama-sama at ang mga hugis ay tutugma. At ngayon maaari mong marahil halos hulaan kung saan kami ay pagpunta sa mga ito. 

Kung tumingin ka sa mga Scratch stage sa paglipas dito at tumingin sa itaas ng mga ito, makikita mo ang isang pulang ilaw, isang itigil-sign, at isang green flag. At ako pagpunta sa sige at panoorin ang aking screen-- para sa sandali lamang, kung maaari mong. Pupunta ako sa i-click ang berdeng bandila sa ngayon, at kaniyang kinilos kung ano ay lilitaw upang maging 10 mga hakbang o 10 pixels, 10 mga tuldok, sa screen. 

At kaya hindi na kapana-panabik, ngunit hayaan mo akong magpanukala walang kahit pagtuturo na ito, kailangan lang gamit ang sariling iyong sariling intuition-- let akong magpanukala na figure out ka kung paano gumawa Scratch lakad karapatan off ang yugto. Nakarating siya gumawa ng paraan para sa kanang bahagi ng screen, ang lahat ng mga paraan sa kanan. Hayaan akong bigyan ka ng ilang sandali o kaya upang bunuin iyon. Baka gusto mong kumuha ng isang pagtingin sa iba pang mga kategorya ng mga bloke. Lahat tama. Kaya lang sa paglalagom, kapag mayroon kaming ang berdeng bandila click dito at ilipat 10 hakbang ay ang lamang pagtuturo, sa bawat oras na ko i-click ang berdeng bandila, kung ano ang nangyayari? Well, na tumatakbo ang aking programa. Kaya kaya kong gawin ito siguro 10 beses mano-mano, ngunit ito nararamdaman ng kaunti bit hackish, kaya na magsalita, kung saan hindi ako talagang paglutas ng problema. Ako lang sinusubukan muli at muli at muli at muli hanggang ako uri ng aksidenteng makamit ang direktiba na ako magse-set out upang makamit mas maaga. 

Ngunit alam namin mula sa aming mga pseudocode mas maaga na may ito paniwala sa programming ng looping, ginagawa nang paulit-ulit ng isang bagay. At gayon din nakita ko na ang isang grupo ng mga ka Naabot para sa kung ano puzzle piraso? Ulitin hanggang. Kaya maaari naming gawin ang isang bagay tulad ulitin hanggang. At kung ano ang ginawa mo ulitin hanggang eksakto? 

OK. At hayaan mo akong pumunta sa isang bagay na medyo mas simple para sa mga lamang ng ilang sandali. Hayaan akong magpatuloy at gawin ito. Pansinin na, tulad ng maaari kang magkaroon ng natuklasan sa ilalim Control, diyan ay ito repeat block, kung saan ay hindi mukhang ito ay na malaki. Mayroong hindi magkano ang kuwarto sa pagitan ng mga dalawang dilaw na linya. Ngunit bilang ang ilan sa inyo ay maaaring magkaroon ng napansin, kung i-drag mo at drop, paunawa kung paano ito ay lumalaki upang punan ang hugis. 

At maaari ka ring Cram higit pa. Makikita ito lamang panatilihin ang lumalaking kung i-drag mo at mag-hover sa ibabaw nito. At hindi ko alam kung ano ang pinakamahusay na dito, kaya hayaan akin ng hindi bababa ulitin limang beses, para sa halimbawa, at pagkatapos ay bumalik sa entablado at i-click ang berdeng bandila. At ngayon mapansin ito ay hindi pa doon. 

Ngayon ilan sa inyo iminungkahi, bilang Victoria lamang ay, ulitin 10 beses. At na sa pangkalahatan ay kumuha sa kanya lahat ng paraan, ngunit gagawin hindi ba ng isang mas matatag na paraan kaysa arbitrarily figuring out kung gaano karaming mga gumagalaw upang gumawa? Ano ang maaaring maging isang mas mahusay na block kaysa ulitin 10 beses na ito? 

Oo, kaya kung bakit hindi gumawa ng isang bagay magpakailanman? At ngayon hayaan mo akong ilipat ito palaisipan piraso sa loob doon at kumuha alisan ng isang ito. Ngayon pansinin kahit na kung saan Scratch pagsisimula, siya ay napupunta sa gilid. At thankfully MIT, na gumagawa ng simula, lamang tinitiyak na siya ay hindi kailanman disappears ganap. Maaari mong palaging grab kanyang buntot. 

At lamang intuitively, bakit niya panatilihin ang paglipat? Anong nangyayari dito? Siya tila sa may tumigil, ngunit pagkatapos ay kung ako pick up at i-drag siya mapigil ang kinakapos upang pumunta sa banda roon. Bakit na? Truly, isang computer ay literal pagpunta sa gawin kung ano ang iyong sabihin sa ito upang gawin. Kaya kung sinabi mo ito nang mas maaga gawin ang sumusunod na bagay magpakailanman, ilipat 10 mga hakbang, ito ay pagpunta upang panatilihin ang pagpunta at pagpunta hanggang maabot ko ang pulang stop sign at itigil ang programa sa kabuuan. 

Kaya kahit na ikaw ay hindi gawin ito, kung paano kaya kong gumawa Scratch ilipat mas mabilis sa kabila ng screen? Higit pang mga hakbang, right? Kaya sa halip ng paggawa ng 10 sa isang pagkakataon, bakit hindi namin sige at baguhin ito to-- ano ang gusto mong propose-- 50? Kaya ngayon ako pagpunta sa i-click ang berdeng flag, at sa katunayan, siya ay napupunta talagang mabilis. 

At ito, siyempre, ay lamang isang paghahayag ng animation. Ano ang animation? Lamang Ito ay nagpapakita sa iyo ng tao isang ang maramihang mga imahe pa rin talaga, tunay, tunay mabilis. At kaya kung kami ay lamang na nagsasabi sa sa kanya upang ilipat sa karagdagang hakbang, lang namin sa pag-ang epekto ay upang pagbabago kung saan siya ay sa screen lahat ng mga mas mabilis na sa bawat yunit ng oras. 

Ngayon ang susunod na hamon na aking iminungkahi ay upang magkaroon ng kanya bounce off sa gilid. At walang pag-alam kung ano ang palaisipan piraso exist-- dahil ito ay pagmultahin kung hindi mo makakuha ng sa yugto ng challenge-- ano ang gusto mong gawin intuitively? Paano kami ay may kanya bounce pabalik- balik, sa pagitan ng kaliwa at kanang? 

Yeah. Kaya kailangan namin ng ilang mga uri ng kalagayan, at kami mukhang may conditionals, kaya na makipag-usap, sa ilalim ng kategorya Control. Alin sa mga bloke namin malamang na gusto? Yeah, siguro "kung, pagkatapos." Kaya mapapansin na kabilang sa mga kulay-dilaw na mga bloke ang mayroon kami dito, diyan ay ito "kung" o ito "kung, sino pa ang paririto" block na habilin daan sa amin upang gumawa ng isang desisyon na gawin ito o upang gawin iyon. At maaari mong kahit na nest ang mga ito upang gawin ang maramihang mga bagay na ito. O kung hindi mo na pa nawala dito, sige sa kategorya Sensing at- sabihin makita kung ito ay dito. 

Kaya kung ano ang bloke ay maaaring maging kapaki-pakinabang dito upang makita kung siya ay off ang yugto? Yeah, mapapansin na ang ilan sa mga bloke maaaring parametrized, kaya na magsalita. Sila ay maaaring uri ng customized na, hindi hindi katulad HTML kahapon na may mga katangian, kung saan ang mga katangian uri ng i-customize ang pag-uugali ng isang tag. Katulad nito dito, maaari ko grab ito hinahawakan block at pagbabago at tanungin ang tanong, ikaw ay pagpindot sa mouse pointer tulad ng mga cursor o ikaw ay pagpindot sa gilid? 

Kaya hayaan mo akong pumunta sa at gawin ito. Pupunta ako upang mag-zoom out para sa isang sandali. Hayaan akong sunggaban ito palaisipan piraso dito, ito piraso ng puzzle na ito, at ako pagpunta sa kaguluhan up ang mga ito para sa sandali lamang. Pupunta ako upang ilipat ito, baguhin ito sa paghawak edge, at ako pagpunta sa paggalaw gawin ito. Kaya narito ang ilang mga sangkap. Sa tingin ko Mayroon akong ang lahat ng gusto ko. 

Gusto isang tao na gusto upang ipanukala kung paano ko maaaring kumonekta mga siguro itaas hanggang sa ibaba upang malutas ang problema ng pagkakaroon ng Scratch ilipat karapatan sa kaliwa papunta sa kanan upang kaliwa papunta sa kanan papuntang kaliwa, ang bawat oras lamang nagba-bounce off ang mga pader? Ano ang gusto kong gawin? Aling block ang dapat kong kumonekta sa "Kapag berdeng bandila click unang"? 

OK, kaya sabihin magsimula sa ang "walang hanggan." Ano ang napupunta sa loob ng susunod? Ibang tao. OK, ilipat hakbang. Lahat tama. Tapos ano? Kaya pagkatapos ay ang kung. At mapansin, kahit na ito asta Napapagitnaan magkasama mahigpit, ito lamang lumago upang punan. Ito ay lamang tumalon sa kung saan gusto ko ito. 

At ano ang gagawin ko bang ilagay sa pagitan ng ang kung at ang pagkatapos? Marahil "kung hawakan gilid." At pansinin, muli, ito ay masyadong malaki para dito, ngunit ito ay lumago upang punan. At pagkatapos ay i-15 degrees? Ilang degrees? Oo, kaya 180 ay iikot akin ang lahat ng mga paraan sa paligid. Kaya sabihin makita kung ako got ang karapatan na ito. Hayaan akong mag-zoom out. 

Hayaan akong i-drag Scratch up. Kaya siya ay isang maliit na pangit ngayon, ngunit iyan ay pagmultahin. Paano ko i-reset sa kanya madali? Ako pagpunta sa impostor na bahagyang. Kaya ako pagdaragdag ng isa pang block, lamang na maging malinaw. Gusto ko sa kanya upang ituro 90 degrees sa kanan sa pamamagitan ng default, kaya lang ako pagpunta sa sabihin sa kanya upang gawin iyon ng programming. At dito namin pumunta. Mukhang naming gumawa niyaon. Ito ay isang maliit na kakaiba, dahil Naglalakad siya baligtad. Sabihin tumawag na ang isang bug. Iyan ay isang pagkakamali. Ang isang bug ay isang pagkakamali sa isang programa, ang isang logical error na ako, ang tao, ginawa. Bakit siya pagpunta baligtad? Ang ibig MIT magtaas o ginawa ko? 

Yeah, I mean, ito ay hindi MIT ni kasalanan. Binigyan naman nila ako ng isang piraso puzzle na nagsasabing i-ilang bilang ng mga degree. At sa Victoria mungkahi, Ako pag-on 180 degrees, na kung saan ay ang karapatan intuwisyon. Ngunit pag 180 degrees literal ay nangangahulugan ng pag-on 180 degrees, at iyan ay hindi talagang ano ang gusto ko, tila. Dahil hindi bababa sa siya ay nasa ito ng dalawang-dimensional na mundo, kaya pag-on ang tunay na nangyayari upang i-flip sa kanya baligtad. 

Ako marahil nais na gumamit ng kung ano ang block sa halip, batay sa kung ano ang nakikita mo dito? Paano natin ayusin ito? Yeah, kaya maaari kaming ituro sa tapat ng direksyon. At talagang kahit na hindi pagpunta sa maging sapat na, dahil aming makakaya lamang hard code sa pagturo kaliwa o kanan. 

Alam mo kung ano ang maaari naming gawin? Mukhang kami ay may isang convenience block dito. Kung ako mag-zoom in, tingnan ang isang bagay na gusto namin dito? Kaya mukhang MIT ay may isang abstraction built in dito. block na ito ay tila upang maging katumbas na kung saan ang iba pang mga bloke, plural? 

Ito isang bloke ay tila na maging katumbas sa ito buong trio ng mga bloke na mayroon kami dito. Kaya ito lumiliko out maaari kong gawing simple ang aking programa sa pamamagitan ng getting alisan ng lahat ng na at lamang ilagay ito sa dito. At ngayon siya ay pa rin ng kaunti maraming surot, at iyan ay pagmultahin para sa ngayon. Susubukan naming mag-iwan na maging. Ngunit ang aking mga programa ay kahit na mas simple, at ito, masyadong, ay magiging representative ng isang layunin sa programming-- ay upang may perpektong gumawa ng iyong code bilang simple, bilang compact hangga't maaari, habang pa rin bilang nababasa hangga't maaari. Hindi mo nais na gawin ito upang maikli at malinaw na ito ay mahirap na maunawaan. 

Ngunit mapansin ko na papalitan tatlong mga bloke sa isa, at iyan ay arguably isang magandang bagay. Ko na abstracted malayo ang paniwala ng pag-check kung ikaw ay sa gilid na may isa lamang block. Ngayon ay maaari naming masiyahan sa mga ito, sa katunayan. Na ito ay hindi magdagdag ng so much intelektwal halaga ngunit mapaglaro halaga. Ako pagpunta sa sige at grab ang tunog dito. Kaya hayaan mo akong sige, at ipaalam sa akin itigil ang programa para sa isang sandali. Pupunta ako upang i-record ang mga sumusunod, na nagpapahintulot ng access sa aking mikropono. 

Ayan na naman. Ouch. Tayo'y subukan ito muli. Ayan na naman. OK, naitala ko ang maling bagay. Ayan na naman. Ouch. Ouch. Lahat tama. Ngayon ay kailangan ko upang makakuha ng mapupuksa ng na. Lahat tama. 

Kaya ngayon mayroon akong isang record ng lamang "ouch." Kaya ngayon ako pagpunta sa pumunta maaga at tawagan ito "ouch." Pupunta ako sa bumalik sa aking mga script, at ngayon notice mayroong block na ito na tinatawag na play ng tunog "meow" o-play ng tunog "ouch." Pupunta ako upang i-drag ito, at kung saan ang dapat kong ilagay ito para sa nakakatawa epekto? Yeah, kaya ngayon ito ay uri ng maraming surot, dahil ngayon ito block-- paunawa kung paano ito "kung sa gilid, bounce "ay uri ng self-contained. Kaya kailangan ko upang ayusin ito. Hayaan akong magpatuloy at gawin ito. Hayaan akong kumuha alisan ng mga ito at bumalik sa aming orihinal na, mas sinadya functionality. Kaya "kung hawakan talim," Gusto kong upang i-on, tulad ng Victoria iminungkahi, 180 degrees. At ang gusto kong i-play ang tunog "ouch" doon? 

Yeah, mapapansin ito ay sa labas na dilaw na bloke. Kaya ito, masyadong, ay magiging isang bug, ngunit Napansin ko ito. Kaya ako pagpunta sa i-drag ito up dito, at notice ngayon ito ay sa loob ng "kung." Kaya ang "kung" ay ganitong uri ng tulad braso-like blot na lamang ang pagpunta sa gawin kung ano ang nasa loob ng mga ito. Kaya ngayon kung ako mag-zoom out sa ang panganib ng annoying-- 

COMPUTER: Ouch, ouch, ouch. 

David MALAN: At ito ay pumunta lamang sa magpakailanman. Ngayon lang upang mapabilis bagay dito, hayaan mo akong sige at buksan up, sabihin say-- hayaan mo akong pumunta sa ilang ng aking sariling mga bagay-bagay mula sa klase. At hayaan mo akong magbukas ng, sabihin nating, ang isa na ginawa ng isa sa aming mga Fellows ng pagtuturo isang pares ng mga taon na nakalipas. Kaya ang ilan sa inyo ay maaaring pagpapabalik ito laro mula sa nakalipas na panahon, at ito ay talagang kahanga-hangang. Kahit na tapos na namin ang pinakasimpleng ng mga programa sa ngayon, isipin natin kung ano ito talagang ganito ang hitsura. Hayaan akong pindutin ang play. 

Kaya sa larong ito, mayroon kaming isang palaka, at gamit ang mga arrow keys-- siya ay tumatagal ng mas malaking hakbang kaysa remember-- ko Mayroon akong kontrol sa palaka na ito. At ang layunin ay upang makakuha ng buong busy road na walang tumatakbo sa mga kotse. At sabihin see-- kung pumunta ako dito, ako kailangang maghintay para sa isang mag-log upang mag-scroll sa pamamagitan ng. Ito nararamdaman tulad ng isang bug. Ito ay uri ng isang bug. Lahat tama. Ako ay nasa ito dito, doon, at pagkatapos ay sa iyo na panatilihin pagpunta hanggang sa makuha mo ang lahat ng ang mga palaka sa liryo pads. Ngayon na ito ay maaaring tumingin lahat ng mga mas mahirap unawain, ngunit sabihin subukan upang basagin ito down itak at pasalita sa kanyang mga bloke component. Kaya doon ay marahil isang malaking suliranin piraso na hindi pa namin nakikita pa ngunit na pagtugon sa mga keystroke, sa mga bagay ko pindutin sa keyboard. 

Kaya doon ay marahil ilang mga uri ng block na nagsasabing, kung key ay katumbas up, pagkatapos ay gawin ang isang bagay na may Scratch-- siguro ilipat ito 10 hakbang sa ganitong paraan. Kung down key ay pinindot, ilipat 10 hakbang sa ganitong paraan, o kaliwa key, ilipat 10 hakbang sa ganitong paraan, 10 hakbang na. malinaw ko na nakabukas ang cat sa isang palaka. Kaya na lamang kung saan ang costume, pati Scratch tawag it-- namin lamang-import ng isang larawan ng palaka. 

Ngunit ano pa ang nangyayari? Ano ang iba pang mga linya ng code, ano ang iba pang mga piraso ng puzzle ginawa Blake, ating pagtuturo kapwa, gamitin sa programang ito, tila? Ano kaya ang paggawa ng lahat ng bagay move-- kung ano ang programming bumuo? 

Motion, sure-- kaya ang ilipat block, para sigurado. At kung ano ang na ilipat block loob ng, malamang? Yeah, ang ilang mga uri ng loop, marahil ng isang magpakailanman harangan, marahil ng isang umuulit block-- ulitin hanggang block. At na kung ano ang gawin ang mga logs at liryo pads at lahat ng iba pa ilipat pabalik-balik. Lamang Ito ay nangyayari endlessly. 

Bakit ang ilan sa mga kotse paglipat ng mas mabilis kaysa sa iba? Ano ang iba't ibang tungkol sa mga programang ito? Yeah, marahil ang ilan sa kanila ay pagkuha higit pang mga hakbang sa isang beses at ang ilan sa kanila mas kaunting mga hakbang sa iisang pagkakataon. At ang visual effect ay mabilis kumpara mabagal. 

Ano sa tingin mo ang nangyari? Kapag nakuha ko ang aking frog lahat ng mga paraan sa kabila ng kalye at ang ilog papunta sa liryo pad, isang bagay kapansin-pansin ang nangyari. Ano ang nangyari sa lalong madaling ginawa ko na? Ito tumigil. palaka na tumigil, at Nakakuha ako ng isang pangalawang palaka. Kaya kung ano ang bumuo ay dapat na ginagamit doon, kung ano tampok na ito? 

Oo, kaya mayroong ilang mga uri ng "Kung" kondisyon up doon, masyadong. At ito ay lumiliko out-- hindi namin nakita this-- ngunit mayroong iba pang mga bloke sa may na maaaring sabihin, kung ikaw ay paghawak isa pang bagay sa screen, kung ikaw ay pagpindot sa liryo pad, "pagkatapos." At pagkatapos ay na kapag kami ay gawin ang ikalawang palaka lilitaw. Kaya kahit na ang laro na ito ay tiyak na very napetsahan, kahit na sa unang tingin may kaya magkano ang pagpunta on-- at Blake ay hindi mamalo ito up sa dalawang minuto, ito marahil kinuha sa kanya ng ilang oras upang lumikha ng larong ito batay sa kanyang memory o mga video ng bersyon ni nakalipas na panahon ng mga ito. Subalit ang lahat ng mga maliit na bagay pagpunta sa screen sa paghihiwalay pasingawan sa mga napaka-simple constructs-- paggalaw o pahayag tulad namin tinalakay, loop at kondisyon, at na ang tungkol dito. Mayroong ilang mga iba pang may interes tampok. Ang ilan sa kanila ay pulos aesthetic o acoustic, tulad ng mga tunog ko lang nilalaro gamit. Ngunit para sa pinaka-bahagi, ikaw magkaroon sa wikang ito, simula, lahat ng mga pangunahing gusali ng mga bloke na kayo magkaroon sa C, Java, JavaScript, PHP, Ruby, Python, at anumang bilang ng iba pang mga wika. Ang anumang mga katanungan tungkol sa Scratch? Lahat tama. Kaya hindi namin ay sumisid sa mas malalim sa simula, bagaman ikaw ay malugod na ito katapusan ng linggo, lalo na kung mayroon kang mga bata o nieces at nephews at tulad, upang ipakilala ang mga ito sa scratch. Ito ay talagang isang kamangha-mangha mapaglaro kapaligiran na may, tulad ng mga may-akda nito sabihin, mataas na kisame. Kahit na namin na nagsimula sa napakababang-level sa mga detalye, maaari mong talagang gawin ganap ng isang bit sa ito, at ito ay marahil isang pagtatanghal ng eksakto na. 

Ngunit sabihin ngayon lumipat sa ilang mga higit pa sopistikadong problema, kung ikaw ay, na kilala bilang "naghahanap" at "Pag-uuri," mas pangkalahatang paraan. Kami ay nagkaroon na ito phone book earlier-- narito ang isa pa lamang para discussion-- na kami ay able sa paghahanap nang mas mahusay dahil ng isang makabuluhang palagay. At lamang maging malinaw, kung ano palagay ay ko ang paggawa ng kapag naghahanap sa pamamagitan ng phone book? That Mike Smith ay sa phone book, kahit na ako magagawang upang mahawakan ang sitwasyon nang hindi siya doon kung ako lang tumigil prematurely. Ang libro ay alphabetical. At iyan ay isang napakamapagbigay palagay, dahil na nangangahulugan someone-- ako uri ng pag-cut isang sulok, tulad ng ako ay mas mabilis dahil ang isang tao sino pa ang paririto ay isang pulutong ng mga hirap sa trabaho para sa akin. 

Ngunit paano kung ang telepono libro ay unsorted? Siguro Verizon got tamad, lamang threw pangalan ng lahat at numero sa doon siguro sa pagkakasunud-sunod sa kung saan sila sign up para sa serbisyo ng telepono. At kung gaano karaming oras ang aabutin sa akin upang mahanap ang isang tao tulad ng Mike Smith? 1,000 page phone book-- kung gaano karaming mga pahina ang mayroon ako upang tumingin sa pamamagitan ng? 

Lahat sila. Ikaw uri ng out ka sana. Mong literal ay may upang tumingin sa bawat pahina kung ang telepono ng libro ay lamang random pinagsunod-sunod. Maaari kang makakuha ng masuwerteng at hanapin Mike sa pinakadulo unang pahina, dahil siya ay ang unang customer mag-order ng serbisyo ng telepono. Ngunit maaaring siya ay ang huling, masyadong. 

So random order ay hindi mabuti. Kaya ipagpalagay na mayroon kami upang ayusin ang phone book o sa pangkalahatan data uri na kami ay ibinigay. Paano natin ito magagawa? 

Well, hayaan mo akong subukan lamang isang simpleng halimbawa dito. Hayaan akong sige at palabunutan ng ilang mga numero sa board. Ipalagay na ang mga numero na mayroon kami ay, sabihin nating, apat, dalawa, isa, tatlo. At, Ben, uri-uriin ang mga numerong ito para sa amin. 

OK, mabuti. Paano ang ginawa mo iyon? Lahat tama. Kaya magsimula sa na ang pinakamaliit na halaga at ang pinakamataas na, at iyon ang tunay na magandang intuwisyon. At mapagtanto na kami ang mga tao ay talagang kaakit-akit magandang sa paglutas ng mga problema tulad nito, hindi bababa sa kapag ang data ay relatibong maliit. Sa sandaling simulan mo upang may daan-daang ng mga numero, libu-libong ng mga numero, milyon-milyong mga numero, Ben marahil hindi maaaring gawin ito lubos na mabilis, sa pag-aakala na mayroong gaps sa ang mga numero. Medyo madali upang mabilang sa isang milyong sa kabilang banda, lamang oras na gugulin. 

Kaya ang algorithm ito tunog tulad ng Ben ginagamit ngayon lang ay ang paghahanap para sa mga pinakamaliliit na numero. Kaya kahit na namin ang mga tao ay maaaring tumagal ng sa isang pulutong ng mga impormasyon visually, isang computer ay talagang isang maliit na mas limitado. Ang computer ay maaari lamang Tingnan natin ang isa byte sa isang panahon o marahil apat na bytes sa isang time-- mga araw na ito siguro 8 bytes sa isang time-- ngunit isang napaka-maliit na bilang ng bytes sa isang ibinigay na oras. 

Kaya ibinigay na namin talagang magkaroon ng apat na magkakahiwalay na mga halaga here-- at maaari mong isipin Ben bilang pagkakaroon blinders sa kung siya ay isang computer tulad na ay hindi siya makakakita ng kahit ano maliban sa isang numero sa isang time-- kaya kami sa pangkalahatan ay ipinapalagay, na kahalintulad lamang English, kami basahin mula sa kanan papuntang kaliwa. Kaya ang unang numero Ben marahil ay tumingin sa ay apat at pagkatapos ay masyadong mabilis natanto na ang isang medyo malaking number-- hayaan mo akong panatilihin ang naghahanap. 

Mayroong dalawang. Maghintay ng isang minuto. Dalawang ay mas maliit kaysa apat. Pupunta ako upang matandaan. Dalawang ay ngayon ang pinakamaliit. Ngayon one-- na mas mahusay. Iyan ay kahit na mas maliit. Ako pagpunta sa kalimutan ang tungkol sa dalawang at tandaan lamang ng isa ngayon. 

At hindi siya nakagawa ihinto ang pagtingin? Well, siya ay maaaring batay sa impormasyong ito, ngunit gusto niya mas mahusay na search ang natitirang bahagi ng listahan. Dahil kung ano ang kung zero ay sa listahan? Paano kung negatibo isa'y ayon sa listahan? Siya lamang ang nakakaalam na ang kanyang sagot ay tama kung siya ay exhaustively naka-check ang buong listahan. Kaya tinitingnan namin ang magpahinga ng ito. Three-- na noon ay isang aksaya ng oras. Got kapus-palad, ngunit ako ay pa rin tama na gawin ito. At kaya ngayon siya siguro pinili ang pinakamaliit na bilang at lamang ilagay ito sa simula ng listahan, tulad ng makikita kong gawin dito. Ngayon kung ano ang gagawin mo susunod, kahit na hindi mo naisip tungkol dito halos sa lawak na ito? Ulitin ang proseso, kaya ang ilang mga uri ng loop. May isang pamilyar na ideya. Kaya dito ay apat. Iyan ay kasalukuyang ang pinakamaliit. Iyan ay isang kandidato. Hindi na. Ngayon ko na nakita sa dalawa. Iyan ang susunod na pinakamaliit na elemento. Three-- iyan ay hindi mas maliit, kaya ngayon Ben ay maaaring aking bubunutin ang dalawa. 

At ngayon kami ulitin ang proseso, at siyempre tatlong makakakuha hugot susunod. Ulitin ang proseso. Apat makakakuha hugot. At ngayon kami ay out ng mga numero, kaya ang listahan ay dapat na pinagsunod-sunod. 

At sa katunayan, ito ay isang pormal na algorithm. Ang isang computer scientist gagawin tawag na ito "pagpili ng uri," ang ideya ng pagiging uri ng ilista iteratively-- muli at muli at muli ng pagpili ang pinakamaliit na bilang. At kung ano ang magaling tungkol dito ay ito lang ang kaya darn intuitive. Ito ay sobrang simple. At maaari mong ulitin ang parehong operasyon muli at muli. Ito ay simple. 

Sa kasong ito ito ay mabilis, ngunit kung gaano katagal ay ito tunay na tumagal? Sabihin gumawa ito tila at pakiramdam ng isang maliit na mas nakakapagod. Kaya isa, dalawa, tatlo, apat, lima anim, pito, walo, siyam, 10, 11, 12, 13, 14, 15, 16-- arbitrary numero. Nais ko lamang pa ito oras na lamang ang apat. Kaya kung ako got ang isang buong grupo ng mga numero now-- ito ay hindi kahit na mahalaga kung ano ang kanilang are-- sabihin isipin ang tungkol sa kung ano ang algorithm ay tunay na tulad ng. 

Ipalagay na may mga numero doon. Muli, hindi mahalaga kung ano ang mga ito, ngunit ang mga ito random. Ako ay nag-aaplay algorithm ni Ben. Kailangan ko upang piliin ang pinakamaliit na bilang. Ano ang gagawin ko? At ako pagpunta sa pisikal na gawin ito sa oras na ito na kumilos ito. Naghahanap, naghahanap, naghahanap, naghahanap, naghahanap. Tanging sa pamamagitan ng ang oras na nakukuha ko sa ang dulo ng listahan Maaari Napag-alaman kong ang pinakamaliit number ay dalawang oras na ito. One ay hindi sa listahan. Kaya ko bang ilagay down na dalawa. 

Ano ang gagawin ko susunod? Naghahanap, naghahanap, naghahanap, naghahanap. Ngayon ko natagpuan ang numero ng pitong, dahil mayroong gaps sa mga numbers-- ngunit lamang arbitrary. Lahat tama. Kaya ngayon maaari ko bang ilagay down na pitong. Naghahanap naghahanap, naghahanap. 

Ngayon ako sa pag-aakala, ng siyempre, na Ben ay hindi may dagdag na RAM, dagdag memory, dahil, siyempre, Naghahanap ako sa parehong numero. Tiyak na maaari aking naalaala ang lahat ng mga numero, at iyan ay ganap na totoo. Ngunit kung Ben Naaalala ng lahat ng mga numero siya ay nakita, siya ay hindi tunay na ginawa pangunahing pag-unlad dahil siya ay mayroon nang ang kakayahan upang maghanap sa pamamagitan ng mga numero sa board. Remembering ang lahat ng mga numero ay hindi makakatulong, dahil maaari siya pa rin bilang isang computer lamang tumingin sa, na aming sinabi, isang numero sa isang pagkakataon. Kaya walang uri ng cheat doon na maaari mong pagkilos. 

Kaya sa katotohanan, bilang ako patuloy na maghanap sa listahan, Literal na ako kung lamang panatilihin ang pagpunta pabalik-balik sa pamamagitan ng ito, plucking out ang susunod na maliit na numero. At bilang maaari mong uri ng magpakilala mula sa aking ulok mga paggalaw, ito lamang ay nagiging sobrang nakakapagod nang masyadong mabilis, at tila ako ay pagpunta sa likod at balik, pabalik-balik pa ng kaunti. Ngayon upang maging patas, hindi ko na kailangang pumunta lubos na bilang, well, sabihin see-- upang maging patas, Hindi ko na kailangang maglakad lubos ng maraming mga hakbang sa bawat oras. Dahil, siyempre, bilang ako piliin ang mga numero mula sa listahan, ang mga natitirang mga listahan ay nakakakuha ng mas maikli. 

At kaya sabihin isipin ang tungkol kung gaano karaming mga hakbang na ako talaga traipsing sa pamamagitan ng bawat oras. Sa pinakaunang sitwasyon kami ay nagkaroon ng 16 mga numero, at iba pa maximally-- sabihin lang gawin ito para sa isang discussion-- Mayroon akong upang tumingin sa pamamagitan ng 16 mga numero upang mahanap ang pinakamaliit. Ngunit sa sandaling ko na naagaw ang pinakamaliit na bilang, kung paano katagal ang natitirang listahan, siyempre? Just 15. Kaya kung gaano karaming mga numero ay Ben o ba akong magkaroon ng upang tumingin sa pamamagitan ng ikalawang oras sa paligid? 15, lamang upang pumunta at hanapin ang pinakamaliit. Ngunit ngayon, siyempre, ang listahan ay, masyadong, mas maliit kaysa sa ito ay bago. Kaya kung gaano karaming mga hakbang ginawa ko may sa gawin ang susunod na pagkakataon? 14 at pagkatapos ay 13 at pagkatapos ay 12, plus tuldok, tuldok, tuldok, hanggang ako kaliwa na may isa lamang. Kaya ngayon isang computer siyentipiko gagawin magtanong, well, kung ano ang ginagawa na ang lahat ng pantay-pantay? Ito ang tunay na katumbas ng ilang mga kongkreto number na kami ng dati tiyak gawin arithmetically, ngunit nais naming makipag-usap tungkol sa kahusayan ng mga algorithm ng kaunti pa formulaically, independiyenteng ng kung gaano katagal ang listahan ay. 

At sa gayon alam mo kung ano? Ito ay 16, ngunit tulad ng sinabi ko bago, sabihin lamang tawagan ang laki ng problema n, kung saan ang n ay ang ilang mga numero. Siguro ito ay 16, marahil ito ay tatlo, marahil ito ay isang milyon. Hindi ko alam. Wala akong pakialam. Ano ko talagang gusto ay isang formula na maaari kong gamitin upang ihambing ito algorithm laban sa iba pang mga algorithm na ang isang tao ay maaaring i-claim ay mas mahusay o mas masahol pa. 

Kaya ito ay lumiliko out, at ako lamang malaman na ito mula grade school, na ito talagang gumagana out sa parehong bagay bilang n higit n plus one sa higit sa dalawang. At ito ang mangyayari sa pantay, ng Siyempre, n squared plus n higit sa dalawang. Kaya kung nais ko ng isang formula para sa kung paano maraming mga hakbang ay kasangkot sa pagtingin sa lahat ng mga numero muli at muli at muli at muli, nais kong sabihin n ito ay squared plus n higit sa dalawang. Pero alam mo kung ano? Ito lamang ang hitsura makalat. Ko lang talagang gusto ng isang pangkalahatang kamalayan ng mga bagay. At maaari mong isipin ang mula high school na ay ang pagkaunawa ng pinakamataas matagalang order. Alin sa mga tuntuning ito, ang n squared, ang n, o ang kalahati, ay ang pinaka-epekto sa paglipas ng panahon? Ang mas malaki n ay makakakuha ng, na kung saan sa mga bagay na ang pinakagigiliwan mo? 

Sa ibang salita, kung ang plug ko in a million, n squared ay magiging pinaka-malamang ang dominating kadahilanan, dahil ang isang milyong beses mismo ay isang pulutong mas malaki kaysa plus isang karagdagang million. Kaya alam mo kung ano? Ito ay tulad ng isang darn malaki numero kung parisukat sa iyo ng isang numero. Ito ay hindi talagang mahalaga. Lamang kami ng pagpunta krus na out at kalimutan ang tungkol dito. At sa gayon ang isang computer siyentipiko nais sabihin na ang kahusayan ng algorithm na ito ay sa pagkakasunud-sunod ng n squared-- Ibig sabihin ko tunay na isang approximation. Ito ay uri ng halos n squared. Sa paglipas ng panahon, ang mas malaki at mas malaki n ay makakakuha ng, ito ay isang mahusay na kuru-kuro para sa kung ano ang kahusayan o kakulangan ng kahusayan ng algorithm na ito ay tunay. At nakukuha ko na, siyempre, mula sa aktwal na paggawa ng matematika. Ngunit ngayon lang ako waving aking mga kamay, dahil ko lang gusto ng isang pangkalahatang pakiramdam ng algorithm na ito. 

Kaya gamit ang parehong logic, samantala, sabihin isaalang-alang ang isa pang algorithm kami ay tumingin at-- linear paghahanap. Kapag ako ay naghahanap para sa book-- phone hindi paghihiwalay ito, paghahanap sa pamamagitan ng book-- phone namin iningatan nagsasabi na ito ay 1,000 mga hakbang, o 500 hakbang. Ngunit sabihin ng tuntuning panlahat na. Kung may n mga pahina sa phone book, kung ano ang ang oras o ang kahusayan ng linear paghahanap? Ito ay sa order ng kung gaano karaming mga hakbang na ito upang makahanap ng Mike Smith gamit linear paghahanap, ang unang algorithm, o kahit na ang ikalawang? 

Sa pinakamasama kaso, Mike ay sa dulo ng aklat. Kaya kung ang phone book ay may 1,000 mga pahina, sinabi namin huling oras, sa pinakamasama kaso, maaaring tumagal ng humigit-kumulang kung gaano maraming mga pahina upang mahanap Mike? Like 1,000. Ito ay isang itaas na nakatali. Ito ay isang pinakamasama posibleng sitwasyon. Ngunit muli, kami ay gumagalaw ang layo mula sa mga numero tulad ng 1,000 ngayon. Ito ay lamang ng n. 

Kaya kung ano ang lohikal na konklusyon? Paghahanap ng Mike sa isang telepono libro na may mga pahina n Maaaring tumagal, sa pinakadulo pinakamasama kaso, kung gaano karaming mga hakbang na ito sa pagkakasunud-sunod ng n? At sa katunayan ng isang computer siyentipiko nais sabihin na ang pagtakbo ng oras, o ang pagganap o ang kahusayan o kawalan ng kaalaman, ng isang algorithm tulad isang linear paghahanap ay sa order ng n. At maaari naming ilapat ang parehong lohika ng tawiran ng isang bagay out bilang ko lang ginawa sa ikalawang algorithm nagkaroon kami sa phone book, na ating pinuntahan dalawang pahina sa isang pagkakataon. 

Kaya 1,000 ang pahinang phone book baka ariin mo kaming 500 pahina liko, plus one kung double namin pabalik ng kaunti. Kaya kung ang isang phone book ay may mga pahina n, ngunit kami ay gumagawa ng dalawang pahina sa isang pagkakataon, na halos kung ano? N higit sa dalawang, kaya na tulad n higit sa dalawang. Ngunit ginawa ko ang pag-angkin ng isang ilang sandali ang nakalipas na n sa ibabaw two-- iyon ang uri ng ang parehong bilang lamang n. Ito ay lamang ng isang pare-pareho na kadahilanan, computer siyentipiko nais sabihin. Sabihin lamang ang focus sa ang mga variable, really-- ang pinakamalaking variable sa equation. 

Kaya linear paghahanap, kung tapos na ang isa pahina sa isang oras o dalawang pahina sa isang pagkakataon, ay isang uri ng panimula ang parehong. Ito ay pa rin sa order ng n. Ngunit inaangkin ko ang aking larawan mas maaga na ang ikatlong algorithm ay hindi linear. Ito ay hindi isang tuwid na linya. At ito'y yaong hindi tuwid na linya, at ang algebraic formula nagkaroon kung ano? Log ng n-- kaya log base dalawa sa n. At hindi namin kailangang pumunta sa masyadong maraming detalye sa logarithms araw na ito, ngunit karamihan computer siyentipiko gagawin hindi kahit na sabihin sa iyo kung ano ang base ay. Dahil ito ay ang lahat lamang pare-pareho ang mga kadahilanan, kaya na magsalita, lamang bahagyang numeric pagkakaiba. At kaya ito ay magiging isang napaka-pangkaraniwan paraan para lalo pormal na computer siyentipiko sa isang lupon o programmers sa isang white board aktwal na arguing na algorithm sila ay gumamit ng o kung ano ang kahusayan ng kanilang algorithm ay. 

At ito ay hindi kinakailangan ng isang bagay talakayin sa iyo sa anumang mahusay na detalye, ngunit isang mahusay na programmer ay isang tao na may isang solid, pormal na background. Siya ay able sa makipag-usap sa sa iyo sa ganitong uri ng paraan at tunay na gumawa ng husay argumento bilang kung bakit isa algorithm o isang piraso ng software ay higit na mataas sa ilang mga paraan sa isa pa. Dahil maaari mong tiyak na lamang patakbuhin ang program na isang tao at bilangin ang bilang ng mga segundo ang kinakailangan upang ayusin ang ilang mga numero, at maaari mong magpatakbo ng ilang program iba pang mga tao at bilangin ang bilang ng mga segundo na aabutin. Ngunit ito ay isang mas pangkalahatang paraan na maaari mong gamitin upang pag-aralan mga algorithm, kung ikaw ay, lamang sa papel o lamang sa salita. Nang walang kahit na tumatakbo ito, nang walang kahit na sinusubukan sample inputs, maaari mo lamang dahilan sa pamamagitan nito. At kaya sa pagtanggap ng empleyado ng isang developer o kung pagkakaroon sa kanya uri ng magpakilala sa iyo kung bakit ang kanilang algorithm, ang kanilang mga lihim sauce para sa paghahanap ng bilyun-bilyong ng mga web page para sa iyong kumpanya ay mas mahusay, ang mga ito ang mga uri ng argumento nila dapat na sa isip ay maaaring gumawa. O hindi bababa sa mga ito ay ang uri ng mga bagay na sumampa ka sa discussion, sa hindi bababa sa isang napaka-pormal na talakayan. Lahat tama. Kaya Ben iminungkahi ng isang bagay tinatawag selection sort. Ngunit ako pagpunta sa imungkahi na mayroong iba pang mga paraan ng paggawa nito, masyadong. Ano Hindi ko talaga gusto tungkol sa Ben algorithm ay na patuloy siyang lumakad, o pagkakaroon akin maglakad, pabalik-balik at pabalik-balik at pabalik-balik. Paano kung sa halip ako ay upang gawin isang bagay tulad ng mga numerong ito dito at ako ay sa makatarungan makitungo sa bawat number naman bilang ako binigyan nito? 

Sa ibang salita, narito ang aking listahan ng mga numero. Apat, isa, tatlo, dalawa. At ako pagpunta sa gawin ang mga sumusunod. Ako pagpunta sa ipasok ang mga numero kung saan sila nabibilang sa halip kaysa pagpili sa mga ito nang paisa-isa. Sa ibang salita, narito ang bilang apat. 

Ito ang aking orihinal na listahan. At ako pagpunta upang mapanatili ang mahalagang isang bagong listahan dito. Kaya ito ay ang lumang listahan. Ito ang bagong listahan. nakikita ko ang mga numero ng apat muna. Ang aking bagong listahan ay una walang laman, kaya ito ay trivially kaso na apat na ngayon ay sari-sari listahan. Tingin lang ako sa pagkuha ng bilang ako ibinigay, at ako ng paglagay ito sa aking bagong listahan. 

Ay pinagsunod-sunod ang bagong listahan? Yeah. Ito ay bobo dahil mayroong isa lamang elemento, ngunit ito ay ganap na pinagsunod-sunod. May walang wala sa lugar. Ito ay mas kawili-wiling, ang algorithm, kapag lumipat ako sa susunod na hakbang. 

Ngayon Mayroon akong isa. Kaya isa, siyempre, ay kabilang sa simula o dulo ng ito ng mga bagong listahan? Ang simula. Kaya kailangan kong gawin ang ilang mga trabaho ngayon. Gumagamit ako pagkuha ng ilang mga kalayaan sa aking marker sa pamamagitan lamang ng pagguhit bagay kung saan gusto ko ang mga ito, ngunit iyan ay hindi talagang tumpak sa isang computer. Ang isang computer, bilang alam namin, ay may RAM, o Random Access Memory, at iyon ang isa byte at isa pang byte at isa pang byte. At kung mayroon kang isang gigabyte ng RAM, mayroon kang isang bilyong bytes, ngunit ang mga ito pisikal sa isang lokasyon. Hindi lamang ka maaaring ilipat bagay sa paligid sa pamamagitan ng pagguhit ito sa board Kahit saan mo gusto. Kaya kung ang aking bagong listahan ay apat na mga lokasyon sa memorya, sa kasamaang-palad ang apat ay na sa maling lugar. 

Kaya upang ipasok ang numero ng isa hindi lang ako makapag gumuhit ito dito. Ito memory location ay hindi umiiral. Iyon ay magiging pagdaraya, at ako ay cheating pictorially para sa isang ilang minuto dito. Kaya talaga, kung gusto ko upang ilagay ang isa dito, Mayroon akong upang pansamantalang kopyahin ang apat at pagkatapos ay ilagay ang isa doon. 

Iyon ay pinong, na tama, na technically maaari, ngunit mapagtanto na dagdag na trabaho. Hindi ko na lang ilagay ang numero sa lugar. Ako unang nagkaroon upang ilipat ang isang numero, pagkatapos ay ilagay ito sa lugar, kaya ako uri ng lambal ang aking halaga ng trabaho. Kaya panatilihin na sa isip. 

Ngunit ngayon ako tapos may sangkap na ito. Ngayon, gusto kong i-grab ang numero ng tatlong. Saan, siyempre, ay ito nabibilang? Sa gitna. Hindi ko ma-impostor anymore at lamang ilagay ito doon, dahil, muli, ito memory ay sa pisikal na mga lokasyon. Kaya ko bang kopyahin ang apat at kaniyang inilagay ang tatlong sa paglipas dito. Hindi isang malaking pakikitungo. Ito ay lamang ng isa dagdag na hakbang again-- nararamdaman napaka murang. 

Ngunit ngayon ilipat ko sa sa dalawang. Ang dalawang, siyempre, ay kabilang dito. Ngayon simulan mo upang makita kung paano ang trabaho ay maaaring pile up. Ngayon kung ano ang kailangan kong gawin? Yeah, kailangan kong ilipat ang apat, Ako pagkatapos ay kung kopyahin ang tatlo, at ngayon ko ipasok ang dalawa. At ang catch na may ganitong algorithm, nang kawili-wili sapat, ay na ipagpalagay na mayroon kami ng isang mas matinding kaso kung saan ito ay sabihin natin walo, pito, anim, lima, apat, tatlo, dalawa, isa. Ito ay, sa maraming mga konteksto, ang pinakamasama kaso sitwasyon, dahil ang darn bagay ay literal paurong. 

Hindi ito tunay makakaapekto algorithm ni Ben, dahil sa pagpili ni Ben uri siya ay pagpunta sa panatilihin pagpaparoo't parito sa listahan. At dahil palaging siya ay naghahanap sa pamamagitan ng buong natitirang listahan, hindi bale kung saan ang mga elemento ay. Ngunit sa kasong ito sa aking pagpasok approach-- sabihin subukan ito. 

Kaya isa, dalawa, tatlo, apat, lima, anim, pito, walo. Isa dalawa tatlo apat, lima, anim, pito, walo. Pupunta ako upang gawin ang mga walong, at saan ko bang ilagay ito? Well, sa simula ng aking listahan, dahil ang bagong listahan ay pinagsunod-sunod. At i-cross ko ito out. 

Saan ko maaaring ilagay ang pitong? Darn ito. Ito mga pangangailangan upang pumunta doon, kaya kailangan kong gawin ang ilang mga pagkopya. At ngayon ang pitong napupunta dito. Ngayon ilipat ko sa sa anim. Ngayon ay mas mas maraming trabaho. 

Eight ay may upang pumunta dito. Seven ay may upang pumunta dito. Ngayon ang anim ay maaaring pumunta dito. Ngayon ko grab ang lima. Ngayon ang walong ay may upang pumunta dito, pitong ay may upang pumunta dito, anim ay may upang pumunta dito, at ngayon ang limang at ulitin. At ako ay medyo magkano gumagalaw ito patuloy. 

Kaya sa katapusan, ito algorithm-- bibigyan namin tumawag ito insertion sort-- talagang ay may isang pulutong ng mga trabaho, masyadong. Ito ay lamang ng iba't ibang uri ng trabaho kaysa sa Ben. ni Ben trabaho ay nagkaroon sa akin ng pagpunta pabalik-balik lahat ng oras, pagpili sa susunod na pinakamaliit element muli at muli. Kaya ito ay na ito napaka-visual uri ng trabaho. 

Ang iba pang mga algorithm, na kung saan ay pa rin correct-- ito makakuha ng trabaho done-- nagbabago lamang ang halaga ng trabaho. Mukhang sa una ikaw ay pag-save, dahil ikaw lamang pagharap sa bawat elemento up harap nang walang paglalakad ang lahat ang paraan sa pamamagitan ng listahan tulad ng Ben ay. Ngunit ang problema ay, lalo na sa mga crazy mga kaso kung saan ito ay ang lahat paurong, ikaw ay lamang uri ng postponing ang mahirap na trabaho hanggang sa ikaw ay upang ayusin ang iyong mga pagkakamali. 

At kaya kung maaari mong isipin na ito walong pu't pitong pu't anim at limang at sa ibang pagkakataon sa apat na at tatlong at dalawang paglipat ng kanilang mga paraan sa pamamagitan ng listahan, lamang namin ay nagbago ang uri ng trabaho ang aming ginagawa. Sa halip ng paggawa nito sa simula ng aking pag-ulit, Lang ako sa paggawa nito sa dulo ng bawat pag-ulit. Kaya ito lumiliko out na algorithm na ito, masyadong, sa pangkalahatan ay tinatawag na pagpapasok ng uri, ay din sa pagkakasunud-sunod ng n squared. Ito ay talagang hindi mas mabuti, Walang mas mahusay na sa lahat. 

Gayunman, may isang ikatlong diskarte Gusto ko hinihikayat sa amin upang isaalang-alang, na kung saan ay na ito. Kaya ipagpalagay aking listahan, para sa simple muli, ay apat, isa, tatlo, two-- lamang ng apat na numero. Ben ay nagkaroon ng magandang intuwisyon, mabuting tao intuwisyon bago, kung saan tayo naayos na ang buong ilista eventually-- insertion sort. coaxed ako sa amin kasama. Ngunit sabihin isaalang-alang ang pinakasimpleng paraan upang ayusin ang listahang ito. 

Ang listahang ito ay hindi pinagsunod-sunod. Bakit? Sa Ingles, ipaliwanag kung bakit ito ay hindi tunay na pinagsunod-sunod. Ano ang ibig ito nangangahulugan na hindi na pinagsunod-sunod? 

MAG-AARAL: Hindi ito sequential. 

David MALAN: Hindi sequential. Bigyan mo ako ng isang halimbawa. 

MAG-AARAL: Ilagay ang mga ito sa pagkakasunud-sunod. 

David MALAN: OK. Bigyan mo ako ng isang mas tiyak na halimbawa. 

MAG-AARAL: Pataas order. David MALAN: Hindi pataas order. Maging mas tumpak. Hindi ko alam kung ano ang ibig sabihin sa pamamagitan ng pataas. Ano ang mali? 

MAG-AARAL: Ang pinakamaliit na ng mga numero ay hindi sa unang space. 

David MALAN: Pinakamaliit number ni hindi sa unang space. Maging mas tiyak. Ako simula upang magtuloy. Kami ay pagbibilang, ngunit kung ano ang out of order dito? 

MAG-AARAL: Numerical sequence. David MALAN: Numerical sequence. Ang bawat tao'y uri ng pag-iingat ito here-- napakataas na antas. Just literal sabihin sa akin kung ano ang mali tulad ng isang limang-taong gulang na maaaring. 

MAG-AARAL: Plus isa. 

David MALAN: Ano iyon? 

MAG-AARAL: Plus isa. 

David MALAN: Ano ang ibig mo bang sabihin plus one? Bigyan mo ako ng isang iba't ibang mga limang-taon gulang na. Ano ang mali, mom? Ano ang mali, ama? Ano ang ibig sabihin na ito ay hindi pinagsunod-sunod? 

MAG-AARAL: Hindi ito ang tamang lugar. 

David MALAN: Ano ang wala sa tamang lugar? 

MAG-AARAL: Four. David MALAN: OK, mabuti. Kaya apat na ay hindi kung saan ito ay dapat. Sa partikular, ay tama ito? Apat at isa, ang unang dalawang numero nakikita ko. Ito ba ay tama? Hindi, ang mga ito ay sa labas ng order, right? Sa katunayan, sa tingin ngayon tungkol sa isang computer, masyadong. Maaari lamang ito tumingin sa marahil isa, siguro dalawang bagay nang sabay once-- at talagang lamang ng isang bagay sa isang panahon, ngunit ito ay maaaring sa hindi bababa sa tumingin sa isang bagay at pagkatapos ay ang susunod na bagay karapatan sa tabi nito. 

Kaya ang mga ito sa pagkakasunud-sunod? Syempre hindi. Kaya alam mo kung ano? Bakit hindi namin kumuha ng sanggol hakbang sa pag-aayos ng problemang ito sa halip ng paggawa ng mga fancy algorithm tulad ng Ben, kung saan siya ay uri ng pag-aayos ng ito sa pamamagitan ng looping sa pamamagitan ng listahan sa halip ng paggawa ng kung ano ang aking ginawa, kung saan Ko lang ang uri ng taning na ito bilang namin pumunta? Sabihin lang literal masira ang paniwala ng order-- numerical order, tumawag ito anumang want-- mo sa mga pairwise paghahambing. 

Apat na pu't isa. Ito ba ang tamang pagkakasunod-sunod? Kaya sabihin ayusin na. Isa at apat na, at pagkatapos ay kami na lang kopyahin na. O sige, good. At aking iniayos sa isa at apat. Tatlong at dalawa? Hindi. Hayaan ang aking mga salita tumugma sa aking mga daliri. Apat at tatlo? 

Hindi ito sa pagkakasunod-sunod, kaya ako pagpunta na gawin ang isa, tatlo, apat, dalawa. OK, mabuti. Ngayon apat at dalawa? Kailangan namin upang ayusin ito, masyadong. Kaya isa, tatlo, dalawa, apat. Kaya ay ito inayos? Hindi, ngunit ito ay mas malapit sa pinagsunod-sunod? 

Ito ay, dahil naayos na namin ito pagkakamali, naayos na namin ang pagkakamaling ito, at naayos na namin ang pagkakamaling ito. Kaya naayos na namin ng tatlong mga pagkakamali arguably. Still ay hindi talagang tumingin pinagsunod-sunod, ngunit ito ay talaga mas malapit sa pinagsunod-sunod na dahil naayos na namin ang ilan sa mga pagkakamali. 

Ngayon kung ano ang gagawin ko susunod? Ako uri ng naabot ang dulo ng listahan. Ako tila sa may taning na lahat ng mga pagkakamali, ngunit walang. Dahil sa kasong ito, ang ilang mga numero maaaring bubbled up mas malapit sa iba pang mga numero na ay pa rin sa labas ng order. Kaya sabihin gawin ito muli, at kukunin ko na lamang gawin ito sa lugar ngayon. One at tatlo? Ayos lang. Tatlong at dalawa? Of course hindi, kaya sabihin baguhin iyon. Sa gayo'y dalawa, tatlo. Tatlo at apat na? At ngayon sabihin lamang lalo na pilosopo dito. Ito ba ay pinagsunod-sunod? You tao malaman ito ay pinagsunod-sunod. 

ang dapat kong subukan muli. Kaya Olivia ay pagpapanukala sinusubukan kong muli. Bakit? Dahil ang isang computer ay hindi magkaroon ang mga luho ng aming mga mata ng tao na lamang glancing back-- OK, ako tapos na. Paano gumagana ang computer matukoy na ang listahan ay pinagsunod-sunod ngayon? Nang wala sa loob. 

ang dapat kong pumunta sa pamamagitan ng minsan pa, at lamang kung ako huwag gumawa / makahanap ng anumang mga pagkakamali maaari kong pagkatapos ay tapusin na rin ang computer, yep, kami ay handa na upang patakbuhin. Kaya isa at dalawa, dalawa at tatlo, tatlong pu't apat. Ngayon ay maaari kong definitively sabihin na ito ay pinagsunod-sunod, dahil sa pinagaling kong walang mga pagbabago. Ngayon ay ito ay isang bug at lamang sira ang bait kung ako, ang computer, nagtanong muli ang mga parehong mga katanungan umaasang iba't ibang mga sagot. Hindi ba dapat mangyari. 

At kaya ngayon ang listahan ay pinagsunod-sunod. Sa kasamaang palad, tumatakbo ang oras ng algorithm na ito ay din n squared. Bakit? Dahil ikaw ay may n numero, at sa pinakamasama kaso mayroon kang upang ilipat n numero n beses dahil mayroon kang upang panatilihin ang pagpunta bumalik upang suriin at potensyal na ayusin mga numerong ito. At maaari naming gawin ang isang mas pormal na pag-aaral, masyadong. 

Kaya ito ay na makapagsalita nagsagawa kami tatlong iba't ibang approach na ito, isa ng mga ito kaagad intuitive off ang bat mula sa Ben sa aking mga iminungkahing insertion uri sa isang ito kung saan mo uri ng malimutan ang kagubatan para sa mga puno sa una. Ngunit pagkatapos ay kung magdadala sa iyo ng isang hakbang pabalik, voila, naayos na namin ang pag-uuri paniwala. Kaya ito ay, maglakas-loob sabihin, isang mas mababang antas marahil kaysa sa ilang ng iba pang mga algorithm, ngunit sabihin makita kung hindi namin maaaring maisalarawan ito sa pamamagitan ng paraan ng mga ito. 

Kaya ito ay ang ilang mga nice software na ang isang tao sinulat gamit ang mga makukulay bar na pagpunta sa gawin ang mga sumusunod na para sa amin. Bawat isa sa mga bar ay kumakatawan sa isang numero. Taller bar, ang mas malaki ang numero, mas maliit na ang bar, ang mas maliit na ang numero. Kaya sa isip na gusto namin sa isang masarap na pyramid kung saan ito ay nagsisimula maliit at ay makakakuha ng malaking, at na ay nangangahulugan na mga bar ay pinagsunod-sunod. Kaya ako pagpunta sa sige at piliin, halimbawa, algorithm ni Ben first-- selection sort. 

At pansinin kung ano ang ginagawa nito. Ang paraan na kanilang pinili upang maisalarawan ang algorithm na ito ay na, tulad ng ako ay naglalakad sa pamamagitan ng aking listahan, program na ito ay maaaring sa pamamagitan ng kanyang listahan ng mga numero, highlight sa pink bawat number na ito ay naghahanap sa. At kung ano ang tungkol sa mangyayari ngayon? 

Ang pinakamaliit na bilang na Ko o Ben natagpuan biglang makakakuha ng inilipat sa simula ng listahan. At mapansin ang kanilang ginawa paalisin ang bilang na ay doon, at na ay ganap na ganap pagmultahin. Hindi ko makuha sa na antas ng detalye. Ngunit kailangan namin upang ilagay na numero sa isang lugar, kaya kami lamang inilipat ito sa bukas na lugar na ay nilikha. Kaya ako ng pagpunta sa bilis na ito up, dahil kung hindi man ito nagiging napaka-nakakapagod mabilis. Animation speed-- doon pumunta kami. Kaya parehong ngayon prinsipyo Ako ay nag-aaplay, ngunit ikaw maaaring magsimula sa pakiramdam ang algorithm, kung ikaw ay, o makita ito ng kaunti pa malinaw. At ito algorithm ay ang epekto ng pagpili sa susunod na pinakamaliit na elemento, kaya ikaw ay pagpunta sa simulan upang makita ito ramp up sa kaliwa. At sa bawat pag-ulit, bilang ako iminungkahi, ito ay isang maliit na mas mababa trabaho. Hindi nito ay may upang pumunta lahat ng mga paraan pabalik sa kaliwang dulo ng listahan, dahil ito ay mayroon alam ang mga ito ay pinagsunod-sunod. Kaya ito uri ng pakiramdam ng tulad ng ito ay accelerating, kahit na ang bawat hakbang ay pagkuha ng parehong halaga ng oras. Mayroon lamang mas kaunting mga hakbang natitira. At ngayon maaari mong uri ng pakiramdam ang algorithm paglilinis up ang dulo ng ito, at sa katunayan ngayon ito ay pinagsunod-sunod. 

Kaya insertion sort ay ang lahat ng tapos na. Kailangan ko upang muling i-sunod ang array. At mapansin Maaari ko lang panatilihin randomizing ito, at kami makakuha ng isang approximation ng ang parehong diskarte, insertion sort. Hayaan akong mabagal ito pababa sa dito. Magsimula tayo na sa paglipas Hayaan. Itigil. 

ni laktawan apat Hayaan. Mayroon kaming pumunta. Sunod sila array. At dito namin go-- insertion sort. Play. Pansinin na ito ay pagharap sa bawat element ito encounters kaagad, ngunit kung ito ay kabilang sa maling notice lugar lahat ng mga trabaho na may mangyari. Mayroon kaming upang panatilihin ang paglilipat pa at higit pang mga elemento upang gumawa ng room for the one gusto naming ilagay sa lugar. 

Kaya kami ay nagbibigay-diin sa kaliwang dulo ng listahan lamang. Paunawa kami ay hindi kahit na tumingin at-- namin hindi naka-highlight sa pink kahit ano sa kanan. Lang namin ay pagharap sa ang mga problema bilang namin pumunta, ngunit kami ay ang paglikha ng isang pulutong ng mga trabaho para sa ating sarili pa rin. At kaya kung pabilisin namin ito up ngayon upang pumunta sa pagkumpleto, ito ay may isang iba't ibang mga pakiramdam na ito sa katunayan. Lamang Ito ay nagbibigay-diin sa kaliwang dulo ngunit paggawa ng isang kaunti pa sa trabaho bilang needed-- uri ng smoothing bagay higit sa, pag-aayos ng mga bagay, ngunit pagharap huli sa bawat elemento nang paisa-isa hanggang sa makuha namin sa the-- well, kami ang lahat ng malaman kung paano ito ay pagpunta sa dulo, kaya ito ay isang maliit na underwhelming marahil. 

Ngunit ang listahan sa end-- spoiler-- ay pagpunta sa ay pinagsunod-sunod. Kaya tingnan natin ang isa sa huling isa. Hindi lamang namin ay maaaring laktawan ngayon. Malapit na tayo. Dalawang upang pumunta, ang isa ay upang pumunta. At voila. Magaling. 

Kaya ngayon sabihin gawin ang isa huling isa, muling randomizing may bubble sort. At mapansin dito, lalo na kung mabagal ko ito down, ito ay panatilihin ang swooping sa pamamagitan ng. Ngunit mapansin ito lamang ang gumagawa ng pairwise comparisons-- uri ng lokal na mga solusyon. Ngunit sa lalong madaling makuha namin sa ang dulo ng listahan sa pink, kung ano ang pagpunta sa may sa mangyari muli? Yeah, ito ay pagpunta sa may sa magsimulang muli, dahil ito lamang fixed pairwise pagkakamali. At na maaaring nagsiwalat pa iba. At kaya kung pabilisin mo ito up, makikita mo makita na, mas maraming bilang ng pangalan ng nagpapahiwatig, ang mga mas maliit elements-- o sa halip, ang mas malaki elements-- ay simula sa bubble up sa itaas, kung ikaw ay. At ang mga mas maliit na mga elemento ay simula na bubble pababa sa kaliwa. At sa katunayan, na ang uri ng ang visual effect pati na rin. At kaya ito ay end up pagtatapos sa isang katulad na paraan, masyadong. 

Wala kaming na matatahanan sa partikular na isa. Hayaan akong buksan ito ngayon, masyadong. May ilang iba pang mga pag-uuri algorithm sa mundo, ang ilan sa kung saan ay nakunan dito. At lalo na para sa mga aaral na hindi kinakailangang visual o matematika, tulad ng ginawa namin bago, maaari naming ring gawin ito audially kung iuugnay namin ang isang tunog na may ito. At katuwaan lang, narito ang isang ilang iba't-ibang mga algorithm, at isa sa kanila sa partikular ikaw pagpunta sa paunawa ay tinatawag na "pagsasama-uuri." 

Ito ay talagang isang panimula mas mahusay na algorithm, tulad na sumanib-uuri, ang isa sa sana ang mga na ikaw ay tungkol sa upang makita, ay hindi pagkakasunud-sunod ng n squared. Ito ay sa pagkakasunud-sunod ng n beses log ng n, kung saan ay talagang mas maliit at sa gayon ay mas mabilis kaysa sa mga iba pang mga tatlong. At mayroong isang pares ng iba pang silly mga na kami makita. 

Kaya dito namin pumunta sa ilang mga tunog. Ito ang pagpapasok ng uri, kaya muli lamang ito ay pagharap sa ang mga elemento bilang dumating sila. Ito ang bubble sort, kaya ito ay alang ang mga ito pares sa isang pagkakataon. At muli, ang pinakamalaking elemento ay bulubok up sa tuktok. 

Next up pagpili-uuri. Ito ang ni Ben algorithm, kung saan muli siya ay pagpili iteratively sa susunod na pinakamaliit na elemento. At muli, ngayon maaari mong talagang marinig na ito ay bilis ng takbo ninyo up ngunit lamang sa gana bilang ito ay paggawa ng mas mababa at mas kaunti trabaho sa bawat pag-ulit. Ito ang mas mabilis na isa, pagsamahin uri, na kung saan ay pag-uuri ng mga kumpol ng mga numero sama-sama at pagkatapos ay pagsasama-sama ng mga ito. Kaya look-- kaliwa kalahati ay naka-pinagsunod-sunod. 

Ngayon ito ay pag-uuri ang kanang kalahati, at ngayon ito ay pagpunta sa pagsamahin ang mga ito sa isa. Ito ay isang bagay na tinatawag na "Gnome uri." At maaari mong uri ng makita na ito ay pagpunta papunta at pabalik, pag-aayos ng trabaho ng isang maliit na bit dito at may bago ito naaayos sa mga bagong trabaho. At na ito. May isa pang uri, na kung saan ay talagang lamang para sa akademikong layunin, tinatawag na "bobo uri," na tumatagal ang iyong data, uri ito random, at pagkatapos ay sumusuri kung ito ay pinagsunod-sunod. At kung ito ay hindi, ito muling uri ito random, sumusuri kung ito ay pinagsunod-sunod, at kung hindi inuulit. At sa teorya, probabilistically ito ay makumpleto, ngunit pagkatapos ng lubos ng kaunti ng oras. Ito ay hindi ang pinaka- mahusay ng mga algorithm. Kaya ang anumang mga katanungan sa mga partikular na algorithm o anumang bagay may kaugnayan doon, masyadong? 

Well, sabihin ngayon manunudyo bukod kung ano ang lahat mga linyang ito ay na ako ng pagguhit at kung ano ako sa pag-aakala ang computer maaaring gawin sa ilalim ng hood. Gusto ko magtaltalan na ang lahat ng mga numerong ito Panatilihin ko drawing-- kailangan nila upang makakuha naka-imbak sa isang lugar sa memorya. Susubukan naming kumuha alisan ng ang tao na ito ngayon, masyadong. 

Kaya ang isang piraso ng memorya sa isang computer-- kaya RAM DIMM ay kung ano ang aming hinanap kahapon, dual inline memory module-- ganito ang hitsura. At bawat isa sa mga maliit na itim na chips ilang bilang ng mga bytes, karaniwang. At pagkatapos ay ang gold pins ay gaya ng mga wires na ikonekta ito sa computer, at ang berde silikon board ay lamang kung ano ang mapigil ang lahat ng bagay sa lahat ng sama-sama. Kaya kung ano ang na ito ay talagang ibig sabihin nito? Kung ako uri ng gumuhit ito parehong larawan, sabihin ipagpalagay para sa simple na ito DIMM, dual inline memory module, ay isa gigabyte ng RAM, isang gigabyte ng memory, na kung saan ay kung gaano karaming bytes kabuuang? One gigabyte ay kung gaano karaming bytes? Higit pa diyan. 1,124 ay kilo, 1,000. Mega ay million. Giga ay isang bilyon. 

Ako ba ay namamalagi? Puwede ba kaming kahit na basahin ang label? Ito ay talagang 128 gigabytes, kaya higit pa. Ngunit kami ay magpanggap na ito ay isa lamang gigabyte. Kaya na nangangahulugan na mayroong isang bilyong bytes ng memorya na magagamit sa akin o 8 bilyong bits, ngunit kami ay pagpunta upang makipag-usap sa mga tuntunin ng mga byte ngayon, sumulong. 

Kaya kung ano ang ibig sabihin nito ay na ito ay isa byte, ito ay isa pang byte, ito ay isa pang byte, at kung kami ay talagang nais upang maging tiyak gusto naming magkaroon upang gumuhit ng isang billion maliit na mga parisukat. Ngunit ano ang ibig sabihin nito? Well, ipaalam sa akin lamang mag-zoom in sa this picture. Kung Mayroon akong isang bagay na mukhang tulad nito ngayon, na apat na bytes. 

At kaya ako ay maaaring ilagay ang apat na numero dito. Isa dalawa tatlo apat. O maaari ko bang ilagay ang apat na mga titik o simbolo. "Hey!" maaaring pumunta doon, dahil ang bawat isa ng mga titik, namin tinalakay nang mas maaga, ay maaaring kinakatawan na may walong bits o ASCII o isang byte. Kaya sa ibang salita, maaari mong ilagay 8 bilyon bagay sa loob ng isang ito stick ng memorya. Ngayon kung ano ang ibig sabihin na ilagay ang mga bagay sa likod upang i-back upang i-back sa memory tulad nito? Ito ay kung ano ang isang programista ay tumawag ng isang "array." Sa isang computer program, tingin ninyo ay hindi tungkol sa mga pinagbabatayan ng hardware, per se. Ikaw lamang ang tingin ng iyong sarili bilang pagkakaroon ng access sa isang kabuuang billion bytes, at maaari mong kahit anong gusto mo dito. Ngunit para sa kaginhawahan ito ay karaniwang kapaki-pakinabang upang mapanatili ang iyong memory karapatan tabi ng bawat isa na katulad nito. Kaya kung ako mag-zoom in sa this-- dahil tiyak na kami ay hindi pagpunta upang gumuhit ng isang billion maliit squares-- sabihin ipagpalagay na ang board na ito ay kumakatawan sa na stick ng memorya na ngayon. At kukunin ko na lang gumuhit ng marami ayon sa aking marker nagtatapos up pagbibigay sa akin dito. Kaya ngayon kami ay may isang stick ng memory sa board na nakuha ng isa, dalawa, tatlo, apat, lima, anim, isa, dalawa, tatlo, apat, lima, anim, seven-- kaya 42 bytes ng memory sa kabuuang screen. Salamat. Oo, ginawa ang aking mga arithmetic karapatan. Kaya 42 bytes ng memory dito. Kaya kung ano ang na ito tunay na ibig sabihin? Well, isang computer programmer Gusto talagang pangkalahatan tingin ng mga ito bilang memory addressable. Sa ibang salita, ang bawat isa sa mga ito lokasyon sa memorya, sa hardware, ay may isang natatanging address. 

Ito ay hindi bilang kumplikadong bilang One Brattle Square, Cambridge, Mass., 02138. Sa halip, ito ay lamang ng isang numero. Ito ang byte numerong zero, ito ay isa, ito ay dalawang, ito ay tatlo, at ito ay 41. Maghintay ng isang minuto. Akala ko ang sinabi ko 42 sa isang sandali ang nakalipas. Sinimulan ko ang pagbibilang sa zero, kaya na talagang tama. Ngayon hindi namin ay may upang aktwal na gumuhit ito bilang isang grid, at kung gumuhit ka ito bilang isang grid Sa tingin ko bagay na talagang makakuha ng isang bit nakaliligaw. Ano ang isang programmer ay, sa kanyang sariling pag-iisip, sa pangkalahatan sa tingin ng mga ito memorya bilang ay tulad ng isang tape, gaya ng putol ng masking tape na lamang napupunta sa at sa magpakailanman o hanggang sa naubusan ka ng memorya. Kaya ang isang mas karaniwang paraan upang gumuhit at sa tingin lamang tungkol memory ay magiging na ito ay byte zero, isa, dalawa, tatlo, at pagkatapos ay tuldok, tuldok, tuldok. At mayroon kang 42 tulad bytes total, kahit bagaman pisikal ito maaaring aktwal na maging isang bagay na mas tulad nito. 

Kaya't kung ikaw ngayon sa tingin ng iyong memory ng mga ito, tulad ng isang tape, ito ay kung ano ang isang programista muli ay tumawag ng isang array ng memory. At kapag gusto mong aktwal na tindahan isang bagay sa memorya ng isang computer, ikaw ay karaniwang gawin ang mga bagay store i-back-to-back upang i-back-to-back. Kaya kami ay pakikipag-usap tungkol sa mga numero. At kapag gusto ko upang malutas ang problema tulad ng apat, isa, tatlo, dalawa, kahit na lamang ako ay pagguhit lamang ang mga numero apat, isa, tatlo, dalawang sa board, ang computer gagawin talagang may ganitong setup sa memorya. 

At kung ano ang magiging sa tabi ng dalawa sa memory ng computer? Well, walang kasagutan sa na. Hindi namin talaga alam. At habang ang mga computer ay hindi ito kailangan, ito ay hindi kailangang pag-aalaga kung ano ang susunod sa mga numero ng ginagawa nito pag-aalaga tungkol. At kapag sinabi ko mas maaga na ang isang computer ay maaari lamang tumingin sa isa address sa isang pagkakataon, ito ay uri ng kung bakit. 

Hindi hindi katulad ng isang record player at isang pagbabasa ulo lamang pagiging able sa tumingin sa isang tiyak na uka sa isang pisikal na record old-school sa isang panahon, katulad Maaari isang computer thanks sa kanyang CPU at ang kanyang Intel pagtuturo set, kabilang na ang pagtuturo ay basahin mula sa memorya o i-save sa memory-- isang computer ay maaaring lamang tumingin sa isang lokasyon sa isang time-- minsan ng isang kumbinasyon ng mga ito, ngunit talagang lamang sa isang lokasyon sa isang pagkakataon. Kaya kapag kami ay ginagawa mga iba't-ibang mga algorithm, Hindi ko na lamang ang pagsusulat sa isang vacuum-- apat, isa, tatlo, dalawa. Yaong mga numero talagang nabibilang sa tabi-tabi pisikal sa memorya. Kaya may mga maliliit na maliit transistors o ilang mga uri ng electronics sa ilalim ng hood sa pag-iimbak ng mga halagang ito. 

At sa kabuuan, kung gaano karaming mga bits ay kasangkot sa ngayon, lamang na maging malinaw? Kaya ito ay apat na bytes, o ngayon ito ay 32 bits total. Kaya may mga tunay na 32 mga zero at mga aakda ang apat na bagay. Mayroong kahit higit pa sa paglipas dito, ngunit muli hindi namin pakialam tungkol sa na. 

Kaya ngayon sabihin humingi ng isa pang tanong gamit memory, dahil na sa dulo ng araw ay sa pag-iiba. Walang bagay na kung ano ang maaari naming gawin sa mga ang computer, sa dulo ng araw ang hardware ay pa rin ang parehong sa ilalim ng hood. Paano Gusto ko mag-imbak ng isang salita sa dito? Well, isang salita sa isang computer tulad ng "Hey!" ay naka-imbak tulad nito lamang. At kung ikaw ay wanted sa isang mas mahabang salita, maaari mo lamang patungan na iyon at sabihin ng isang bagay tulad ng "hello" at mag-imbak na dito. 

At kaya dito, masyadong, ito contiguousness ay talagang isang bentahe, dahil ang isang computer ay maaaring lamang basahin mula sa kanan papuntang kaliwa. Ngunit narito ang isang tanong. Sa konteksto ng salitang ito, h-e-l-l-o, exclamation point, kung paano maaaring ang computer alam kung saan ang salita ay nagsisimula at kung saan ang salita ay nagtatapos? Sa konteksto ng mga numero, kung paano gumagana ang computer alam kung gaano katagal ang pagkakasunod-sunod ng numero ay o kung saan ito ay nagsisimula? Well, ito ay lumiliko out-- at hindi namin ay pumunta masyadong maraming sa antas na ito ng detail-- computer ilipat bagay sa paligid sa memorya literal sa pamamagitan ng paraan ng mga address na ito. Kaya sa isang computer, kung ikaw ay pagsusulat ng code upang mag-imbak ng mga bagay tulad ng mga salita, kung ano ang ikaw ay talagang ginagawa ay nagta-type expression na matandaan kung saan sa memory ng computer ang mga salitang ito ay. Kaya hayaan mo akong gawin ang isang napaka, napaka-simpleng halimbawa. 

Ako pagpunta sa sige at buksan up ng isang simpleng programa ng teksto, at ako pagpunta upang lumikha ng isang file na tinatawag hello.c. Karamihan ng impormasyon na ito namin hindi pumunta sa sa mahusay na detalye, ngunit ako pagpunta sa magsulat ng isang program sa parehong wika, C. Ito ay malayo mas intimidating, Gusto ko magtaltalan, kaysa sa simula, ngunit ito ay halos kapareho sa espiritu. Sa katunayan, mga kulot braces-- Maaari mong uri ng isip ng kung ano lang ginawa ko ng mga ito. 

Natin gawin ito, ang tunay na Hayaan. Kapag berdeng bandila click, gawin ang sumusunod. gusto kong i-print out "hello." Kaya ito ay pseudocode ngayon. Ako uri ng blurring ng mga linya. Sa C, wikang ito ako pinag tungkol sa, ang linyang ito print kumusta talagang nagiging "printf" na may ilang mga panaklong at isang semi-colon. 

Ngunit ito ay ang eksaktong parehong ideya. At ito tunay user-friendly "Kapag berdeng bandila click" ay nagiging ang mas arcane "int pangunahing walang bisa." At ito tunay ay walang mapping, kaya lang ako pagpunta sa huwag pansinin na. Ngunit ang kulot tirante ay gaya ng mga hubog piraso puzzle tulad nito. 

Kaya maaari mong uri ng hulaan. Kahit na hindi mo na program bago, kung ano ang ibig sa programang ito marahil gawin? Marahil Kopya kumusta na may isang exclamation point. 

Kaya sabihin subukan na. Ako pagpunta sa i-save ito. At ito ay, muli, isang napaka old kapaligiran ng paaralan. Hindi ko ma-i-click ang, hindi ko maaaring i-drag. Mayroon akong mag-type utos. Kaya gusto kong patakbuhin ang aking programa, kaya maaari kong gawin ito, tulad ng hello.c. Iyan ang file ako ran. Ngunit maghintay, ako nawawala ng isang hakbang. Ano ang sinabi namin ay isang kinakailangang hakbang para sa isang wika tulad ng C? Lamang ko na nakasulat na pinagmulan code, ngunit kung ano ang kailangan ko? Yeah, kailangan ko ng isang tagatala. Kaya sa aking Mac dito, mayroon akong isang programa na tinatawag GCC, GNU C compiler, na nagpapahintulot sa akin na gawin this-- tira aking source code sa, kami ay tumawag ito, machine code. 

At maaari ko bang makita na, muli, tulad ng sumusunod, ang mga ito ang mga zero at mga ko lang nilikha mula sa aking source code, ang lahat ng mga zero at mga. At kung gusto kong patakbuhin aking program-- ito ang mangyayari na tinatawag a.out para makasaysayang reasons-- "hello." Maaari ko bang patakbuhin itong muli. Kumusta kumusta kumusta. At ito ay anyong nagtatrabaho. 

Ngunit na nangangahulugan sa isang lugar sa aking memory ng computer ay ang mga salita h-e-l-l-o, exclamation point. At ito ay lumiliko out, lamang bilang isang bukod, kung ano ang isang computer na gagawin ay karaniwang gawin upang ito nakakaalam kung saan bagay simulan at end-- ito ay pagpunta sa maglagay ng isang espesyal na simbolo dito. At ang convention ay upang ilagay ang numerong zero sa dulo ng isang salita sa gayon ay alam mo kung saan ito aktwal na nagtatapos, sa gayon ay ikaw hindi panatilihin sa pag-print ang higit pa at higit pa karakter kaysa sa iyong aktwal balak. 

Ngunit ang takeaway dito, kahit na kahit na ito ay medyo arcane, ay na ito ay sa huli medyo simple. Ikaw ay bibigyan ng isang uri ng isang tape, isang blangkong space kung saan maaari mong isulat ang mga titik. Kailangan lang may sa magkaroon ng isang espesyal na simbolo, tulad ng arbitrarily ang bilang zero, upang ilagay sa dulo ng ang iyong mga salita nang sa gayon ay alam sa computer, oh, dapat ko bang itigil printing matapos nakikita ko ang exclamation point. Dahil ang susunod na bagay doon ay isang ASCII na halaga ng zero, o ang null karakter bilang ang isang tao ay tumawag ito. Ngunit mayroong uri ng isang problema dito, at sabihin bumalik sa mga numero para sa isang sandali. Ipagpalagay na ko, sa katunayan, magkaroon ng isang array ng mga numero, at ipagpalagay na ang program Sumulat ako ay tulad ng isang grado ng libro para sa isang guro at isang guro sa silid. At ang program na ito ay nagbibigay-daan sa kanya i-type sa mga marka ng kanilang mga estudyante sa mga pagsusulit. At ipagpalagay na ang estudyante ay makakakuha ng 100 sa kanilang unang pagsusulit, marahil tulad ng isang 80 sa susunod na isa, at pagkatapos ng isang 75, pagkatapos ng isang 90 sa ikaapat na pagsusulit. 

Kaya sa puntong ito sa kuwento, array ay ng laki apat. Mayroon talagang mas memorya sa computer, ngunit ang array, kaya na magsalita, ay ng laki apat. Ipagpalagay na ngayon na ang mga guro ay nais upang magtalaga ng isang ikalimang pagsusulit sa klase. Well, isa sa mga bagay na siya o siya ay pagpunta sa may sa gawin ngayon ay mag-imbak ng isang karagdagang halaga dito. Ngunit kung ang array ang guro ay nilikha sa programang ito ay ang laki para sa, ang isa sa mga problema sa isang array ay na hindi lamang ang maaari mong panatilihin ang pagdaragdag sa memory. Dahil kung ano ang kung ang isa pang bahagi ng programa ay ang salitang "hey" right there? 

Sa ibang salita, ang aking memorya ay maaaring maging ginagamit para sa anumang bagay sa isang programa. At kung in advance ko nai-type sa, hey, Gusto kong input apat na mga marka ng pagsusulit, upang sila'y magsiyaon dito at dito. At kung ikaw ay biglang magbago ang isip mamaya at sabihin na gusto kong ikalimang pagsusulit puntos, hindi mo magagawa lamang ilagay ito kung saan man gusto mo, dahil kung ano kung ito memory ay ginagamit para sa isang bagay else-- ilang iba pang mga program o ilang iba pang mga tampok ng programa na kayo ay tumatakbo? Kaya ikaw ay may mag-isip nang maaga kung paano mo gustong upang i-imbak ang iyong data, dahil ngayon mo na lagyan ng kulay iyong sarili sa isang digital na sulok. 

Kaya isang guro maaaring sa halip sabihin kapag pagsulat ng isang programa upang mag-imbak ang kanyang marka, alam mo kung ano? I am pagpunta upang humiling, kapag sumusulat ang aking mga programa, na gusto kong zero, isa, dalawa, tatlo, apat, lima, anim, walo marka total. Kaya isa, dalawa, tatlo, apat, lima, anim, pito, walo. Guro ay maaaring lamang over-allocate memory kapag sumusulat kanyang programa at sabihin mo, alam mo kung ano? hindi ako pagpunta sa magtalaga ng karagdagang sa walong mga pagsusulit sa isang semester. Iyan na lamang mabaliw. Hindi ko makikita maglaan iyon. Kaya na sa ganitong paraan siya ay may ang flexibility sa mga marka store student, tulad ng 75, 90, at marahil isang dagdag na kung saan ang mag-aaral Nakakuha dagdag na credit, 105. 

Ngunit kung ang mga guro ay hindi kailanman ay gumagamit ng mga ito ng tatlong mga puwang, mayroong isang madaling gamitin na takeaway dito. Siya o siya lamang ay pag-aaksaya space. Kaya sa ibang salita, mayroong ito karaniwang tradeoff sa programming kung saan maaari kang mag-allocate eksakto tulad ng maraming memorya hangga't gusto mo, tuwad ng kung saan ay na ikaw ay sobrang efficient-- hindi ka pagiging mapag-aksaya sa all-- ngunit ang downside sa mga ito ay kung ano ang kung nagbago ang iyong isip kapag gamit ang programa na nais mong iimbak mas maraming data kaysa sa iyo orihinal na inilaan. 

Kaya siguro ang solusyon ay, at pagkatapos, isulat ang iyong mga programa sa paraan na ginagamit nila mas memorya kaysa sila ay talagang kailangan. Sa ganitong paraan hindi ka pagpunta upang tumakbo sa problemang iyon, ngunit ikaw ay pagiging mapag-aksaya. At ang mas memorya ng iyong programa ay gumagamit, bilang namin tinalakay kahapon, mas mababa memory na magagamit para sa iba pang mga programa, ang mas maaga ang iyong computer ay maaaring mabagal down na dahil sa virtual memory. At kaya ang ideal na solusyon ay maaaring kung ano? 

Under-allocating tila masama. Over-allocating tila masama. Kaya kung ano ang maaaring maging isang mas mahusay na solusyon? Reallocating. Maging mas dynamic. Huwag pilitin ang iyong sarili upang pumili ng isang priori, sa simula, kung ano ang gusto mo. At tiyak na hindi over-maglaan, baka mo na mapag-aksaya. 

At kaya upang makamit ang layuning iyon, kami kailangang magtapon ang data na ito istraktura, kaya na magsalita, ang layo. At kaya kung ano ang isang programmer ay karaniwang gamitin ay isang bagay na tinatawag hindi isang array ngunit isang naka-link na listahan. Sa ibang salita, siya ay magsimulang mag-isip ng kanilang mga memory bilang uri ng isang hugis na sila maaari gumuhit sa mga sumusunod na paraan. Kung gusto kong mag-imbak ng isang numero sa isang program-- kaya Setyembre, Ibinigay ko ang aking mga mag-aaral ng isang pagsusulit; gusto ko upang mag-imbak unang pagsusulit ang mga mag-aaral ', at sila got ang isang 100 sa it-- ko ay pagpunta sa hilingin ang aking computer, sa pamamagitan ng paraan ng programa na hindi ko na nakasulat, para sa isa tipak ng memory. At ako pagpunta sa tindahan ng number 100 sa loob nito, at iyon ito. 

Pagkatapos ng ilang linggo mamaya kapag nakukuha ko ang aking pangalawang pagsusulit, at ito ay oras na mag-type sa na 90%, I am pagpunta upang hilingin sa computer, hey, computer, Maaari ba akong magkaroon ng isa pang tipak ng memory? Ito ay pagpunta sa bigyan ako ito Walang laman tipak ng memory. Pupunta ako upang ilagay sa bilang 90, ngunit sa aking mga programa sa anumang paraan o other-- at hindi namin ay mag-alala tungkol sa ang syntax para this-- kailangan ko upang kahit papaano ay kadena ng mga bagay na sama-sama. At kukunin ko na kadena ang mga ito kasama ang kung ano ang hitsura tulad ng isang arrow dito. 

Ang ikatlong pagsusulit na nanggagaling up, Ako pagpunta sa sabihin, hey, computer, bigyan ako ng isa pang tipak ng memory. At ako pagpunta upang ilagay down na ano man ito ay, tulad ng 75, at kailangan kong chain na ito magkasama ngayon sa anumang paraan. Fourth pagsusulit ay dumating kasama, at marahil iyon patungo sa katapusan ng semestre. At sa pamamagitan ng puntong iyon ang aking mga programa ay maaaring maging gamit memory lahat ng dako ng lugar, sa buong pisikal. At kaya lamang sa mga kicks, ako pagpunta sa gumuhit ito hanggang quiz-- nakalimutan ko kung ano ito ay; ako tingin siguro isang 80 o something-- paraan sa paglipas dito. 

Ngunit iyon lamang ang fine, dahil pictorially Pupunta ako upang gumuhit ang linyang ito. Sa ibang salita, sa katotohanan, sa hardware ng iyong computer, ang unang puntos baka end up dito dahil ito ay karapatan sa simula ng semestre. Ang susunod na isa ay maaaring end up dito dahil ang isang bit ng oras ang lumipas at ang programa mapigil ang pagtakbo. Ang susunod na iskor, na kung saan ay isang 75, ay maaaring maging sa paglipas dito. At ang huling puntos ay maaaring maging isang 80, na kung saan ay higit sa dito. 

Kaya sa katotohanan, pisikal, ito ay maaaring maging ano ang memorya ng iyong computer kamukha. Ngunit ito ay hindi isang kapaki-pakinabang mental paradaym para sa isang computer programmer. Bakit dapat mong pag-aalaga kung saan ang ano ba ang iyong data ay nagtatapos up? Gusto mo lamang upang mag-imbak ng data. 

Ito ay uri ng tulad ng ating talakayan mas maaga ng pagguhit ang kubo. Bakit mo pag-aalaga kung ano ang ang mga anggulo ay ng kubo at kung paano mo ay may upang i-sa gumuhit ito? Gusto mo lamang ng isang kubo. Katulad nito dito, ikaw lamang ang nais na grado book. Gusto mo lang mag-isip ng ito bilang isang listahan ng mga numero. Sino ang nagmamalasakit kung paano ito ay ipinatupad sa hardware? 

Kaya ang abstraction ngayon ay ang larawang ito dito. Ito ay isang listahan ng mga link, pati na isang programmer ay tumawag ito, insofar bilang ikaw ay may isang list, nang walang alinlangan ng mga numero. Ngunit ito ay naka-link pictorially sa pamamagitan ng paraan ng mga arrow, at lahat ng mga arrow are-- ilalim ng hood, kung gusto mong malaman, pagpapabalik na ang aming pisikal na hardware ay may addresses zero, isa, dalawa, tatlo, apat. Ang lahat ng mga pana ay ay tulad ng isang mapa o mga direksyon, kung saan kung 90 is-- ngayon Nakatanggap ako upang mabilang. 

Zero, isa, dalawa, tatlo, apat, lima, anim, pito. Mukhang ang 90 ay memory address bilang na pito. Ang lahat ng mga pana ay ay tulad ng isang maliit scrap ng papel na nagbibigay sa mga direksyon sa program na nagsasabing sundin ang mapa upang makakuha ng sa lokasyon pitong. At doon ay makikita mo ang pangalawang pagsusulit na marka ng mag-aaral. Samantala, ang 75-- kung patuloy ko ito, ito ay pito, walo, siyam, 10, 11, 12, 13, 14, 15. 

Ang iba pang mga arrow lamang kumakatawan isang mapa upang memory location 15. Ngunit muli, ang programmer sa pangkalahatan ay hindi pag-aalaga tungkol sa mga ito antas ng detalye. At sa karamihan ng bawat programming wika ngayon, ang programmer Hindi maa-kahit na alam kung saan sa memory ang mga numerong ito ay tunay. Lahat siya ay may sa pag-aalaga tungkol sa ay na sila ay sa paanuman naka-link nang sama-sama sa isang istraktura ng data tulad nito. 

Ngunit ito ay lumiliko out hindi upang makakuha ng masyadong teknikal. Ngunit lamang dahil maaari naming marahil kayang magkaroon talakayang ito dito, Ipagpalagay na namin muling bisitahin ang isyu na ito dito ng isang array. Tayo'y makita kung kami ikinalulungkot pagpunta dito. Ito ay 100, 90, 75, at 80. 

Hayaan akong dagli gumawa ito claim. Ito ay isang array, at muli, ang salient katangian ng isang array ay na ang lahat ng iyong data ay bumalik sa back to back in memory-- literal isang byte o marahil apat na bytes, ilang takdang bilang ng mga bytes ang layo. Sa isang naka-link na listahan, na kung saan maaari naming gumuhit tulad nito, sa ilalim ng hood na nakakaalam kung saan bagay-bagay na ay? Ito ay hindi kahit na kailangan upang dumaloy tulad nito. Ang ilan sa mga data ay maaaring pabalik sa kaliwa hanggang doon. Ni hindi mo na malaman. 

At kaya sa isang array, mayroon kang isang tampok na kilala bilang random access. At kung ano ang random access ibig sabihin nito ay na ang computer ay maaaring tumalon agad sa anumang lokasyon sa isang array. Bakit? Dahil ang computer alam na ang unang lokasyon ay zero, isa, dalawa, tatlo. 

At kaya kung gusto mong pumunta mula sa ito ng elemento sa susunod na elemento, mong literal, sa isip computer, idagdag lamang ang isa. Kung nais mong pumunta sa ikatlong elemento, idagdag lamang one-- susunod na elemento, lamang magdagdag ng isa. Gayunpaman, sa ang bersyon na ito ng kuwento, ipagpalagay ang computer ay kasalukuyang naghahanap sa o pakikitungo sa mga number 100. Paano mo makakuha ng sa susunod grado sa grade libro? 

Mayroon kang gumawa ng pitong hakbang, na kung saan ay arbitrary. Upang makakuha ng sa susunod na isa, kailangan mong kumuha ng isa pang walong baytang upang makapunta sa 15. Sa ibang salita, ito ay hindi isang pare-pareho ang agwat sa pagitan ng mga numero, at kaya ito lamang tumatagal ng computer na mas maraming oras ay ang point. Ang computer na may sa paghahanap sa pamamagitan ng memory upang upang mahanap kung ano ang iyong hinahanap. 

Kaya kung saan ang isang array ay may gawi na maging isang mabilis ang data structure-- dahil ikaw maaaring literal lamang gawin simpleng aritmetika at makakuha ng kung saan mo nais sa pamamagitan ng pagdaragdag ng isa, para instance-- isang naka-link na listahan, mong isakripisyo ang tampok na iyon. Hindi ka maaaring pumunta lamang mula sa unang sa ikalawang sa mga ikatlong sa ika-apat. Kailangan mong sundin ang mapa. Mayroon kang gumawa ng higit pang mga hakbang upang makakuha ng mga halaga, na kung saan ay tila sa maaari ng pagdagdag ng isang gastos. Kaya kami ay nagbabayad ng isang presyo, ngunit kung ano ang ang tampok na Dan ay naghahanap dito? Ano ang isang listahan ng mga link tila daan sa amin upang gawin, na kung saan ay ang pinagmulan ng ito partikular na kuwento? 

Mismong. Ang isang dynamic na laki dito. Maaari naming idagdag sa listahang ito. Maaari naming kahit na pag-urong ang listahan, kaya na lamang ang aming ginagamit ng mas maraming memory bilang namin talagang gusto at kaya kami ay hindi kailanman over-allocating. 

Ngayon lang na talagang lisa-picky, mayroong isang nakatagong gastos. Kaya hindi lamang mo dapat hayaan mo akong kumbinsihin mo na ito ay isang nakahihimok tradeoff. May isa pang nakatagong gastos dito. Ang benepisyo, upang maging malinaw, ay na makuha namin dynamism. Kung gusto kong isa pang elemento, maaari ko na lang gumuhit ito at maglagay ng numero sa doon. At pagkatapos ay maaari kong i-link ito na may larawan dito, samantalang sa paglipas dito, muli, kung na hindi ko na ipininta ang aking sarili sa isang sulok, kung may ibang tao ay gumagamit na ang memory dito, ako sa labas ng kapalaran. ipininta ko na ang aking sarili sa sulok. 

Ngunit kung ano ang mga nakatagong gastos sa larawang ito? Ito ay hindi lamang ang dami ng oras na ito ay tumatagal upang pumunta mula dito sa dito, na kung saan ay pitong mga hakbang, at pagkatapos ay walong baytang, na kung saan ay higit pa sa isa. Ano ang isa pang nakatagong gastos? Hindi lamang oras. Ang karagdagang impormasyon ay kinakailangan upang makamit ang larawang ito. 

Oo, na mapa, ang mga maliit na mga scrap ng papel, pati na panatilihin ko naglalarawan sa mga ito bilang. Ang mga arrows-- mga ito ay hindi libre. A computer-- alam mo kung ano ang isang computer ay may. Ito ay may zero at mga. Kung nais mong kumakatawan sa isang arrow o isang mapa o isang numero, kailangan mo ng ilang memory. Kaya't ang isang presyo na iyong bayaran para sa isang naka-link na listahan, isang pangkaraniwang computer science mapagkukunan, ay din space. 

At sa katunayan kaya, kaya karaniwang, kabilang sa mga tradeoffs sa pagdisenyo ng software engineering systems kapanahunan at space-- ay dalawang sa iyong mga sangkap, dalawang ng iyong pinaka-mahal na mga sangkap. Na ito ay gastos sa akin mas maraming oras dahil kailangan kong sundin ang mapa, kundi pati na rin ito ay costing sa akin ng dagdag na espasyo dahil mayroon akong upang panatilihin ang mapa na ito sa paligid. Kaya ang pag-asa, bilang na namin uri ng tinalakay sa paglipas ng kahapon at ngayon, ay na ang mga benepisyo ay lumamang ang gastos. 

Ngunit walang malinaw na solusyon dito. Siguro ito ay better-- a la mabilis at marumi, bilang Kareem ipinanukalang earlier-- upang ihagis memory sa problema. Lamang bumili ng mas maraming memory, sa tingin mas mababa mahirap tungkol sa paglutas ng mga problema, at malutas ito sa isang mas madaling paraan. At sa katunayan mas maaga, kapag usapan natin ang tungkol tradeoffs, ito ay hindi na espasyo sa ang computer at oras. Ito ay nag-develop oras, na ay isa pang mapagkukunan. 

Kaya muli, ito ay ito balancing act sinusubukan upang magpasya kung alin sa mga bagay na iyon ikaw ay handa na gastusin? Alin ang hindi bababa sa mahal? Kung saan ay magbubunga ng mas mahusay na mga resulta? Yeah? 

Sa katunayan. Sa kasong ito, kung ikaw ay na kumakatawan sa mga numero sa maps-- ito ay tinatawag na sa maraming wika "Payo" o "address" - ito ay double ang space. Iyon ay hindi kailangang maging kasing masamang bilang double kung ngayon lang kami sa pag-iimbak ng mga numero. Ipagpalagay na kami ay pag-iimbak pasyente talaan sa isang hospital-- kaya pangalan ni Pierson, numero ng telepono, numero ng social security, doktor kasaysayan. Ang kahon na ito ay maaaring maging magkano, magkano ang mas malaki, at sa sitwasyong isang maliit na maliit maliit na pointer, ang address ng sa susunod element-- ito ay hindi isang malaking pakikitungo. Ito ay tulad ng isang palawit gastos na ito ay hindi mahalaga. Ngunit sa kasong ito, yeah, ito ay isang pagdodoble. Magandang tanong. 

Natin makipag-usap tungkol sa oras ng isang Hayaan kaunti pa concretely. Ano ang pagtakbo ng oras ng paghahanap listahang ito? Ipagpalagay Nais kong maghanap sa pamamagitan ng lahat ng mga marka ng mga estudyante, at mayroong n marka sa ganitong istraktura ng data. Dito, masyadong, maaari naming humiram ang bokabularyo ng mas maaga. Ito ay isang linear istraktura ng data. 

Big O ng n ay kung ano ang kinakailangan upang makakuha ng sa dulo ng ito istraktura ng data, whereas-- at hindi pa namin nakikita ito before-- isang array ay nagbibigay sa iyo ano ang tinatawag na pare-pareho ang oras, na nangangahulugan isang hakbang o dalawang hakbang o 10 steps-- ay hindi mahalaga. Ito ay isang nakapirming numero. Ito ay may kinalaman sa ang laki ng array. At ang dahilan para sa na, muli, ay random access. Ang computer na maaari lamang kaagad tumalon sa isa pang lokasyon, dahil ang mga ito ang lahat ng mga parehong distansya mula sa lahat ng bagay sino pa ang paririto. Walang pag-iisip na kasangkot. Lahat tama. Kaya kung maaari ko, hayaan mo akong subukan na pintura ng dalawang huling larawan. Isang napaka-karaniwang isa na kilala bilang isang hash table. Kaya upang ganyakin ang talakayang ito, hayaan mo akong mag-isip tungkol sa kung paano gawin ito. 

Kaya kung paano tungkol dito? Ipagpalagay na ang problema gusto naming malutas ngayon ay pagpapatupad sa isang dictionary-- kaya ng isang buong grupo ng mga salitang Ingles o ano pa man. At ang layunin ay upang ma-sagot tanong ng form na ito ay isang salita? Kaya nais mong ipatupad isang spell checker, lamang tulad ng isang pisikal na diksyunaryo na maaari mong tingnan ang mga bagay sa. Ipagpalagay ako ay upang gawin ito sa isang array. kaya kong gawin ito. 

At ipagpalagay na ang mga salita ay apple at saging at milong bilog. At hindi ako makapag-isip ng mga prutas na nagsisimula sa d, kaya kami lamang pagpunta sa may tatlong prutas. Kaya ito ay isang array, at kami ay pagtatago ng lahat ng mga salitang ito sa ganitong diksyunaryo bilang isang array. Ang tanong, at pagkatapos, ay kung paano pa maaari mong itabi ang impormasyon na ito? 

Well, ako uri ng cheating dito, dahil bawat isa sa mga titik sa salita ay talagang isang indibidwal byte. Kaya kung ako talagang nais na maging lisa-picky, ko dapat talagang ay naghahati ito up sa marami mas maliit na chunks ng memorya, at maaari naming gawin eksakto na. Ngunit kami ay pagpunta sa tumakbo sa ang parehong problema tulad ng dati. Paano kung, bilang Merriam Webster o Oxford ang bawat year-- sila magdagdag ng mga salita sa dictionary-- hindi kami kinakailangang gusto upang ipinta ang ating sarili sa isang sulok na may isang array? 

Kaya sa halip, marahil ng isang mas matalinong diskarte ay upang ilagay apple sa sarili nitong node o kahon, tulad ng gagawin namin sabihin, saging, at pagkatapos dito mayroon kaming milong bilog. At kami string ng mga bagay na sama-sama. Kaya ito ay ang array, at ito ay naka-link na listahan. Kung hindi mo pa masyadong maaaring makita, ito lamang nagsasabing "array," at ito says "listahan." 

Kaya kami ay may parehong eksaktong mga isyu tulad ng dati, kung saan mayroon kami ngayon dynamism sa aming naka-link na listahan. Ngunit kami ay may isang medyo mabagal na diksiyunaryo. Ipagpalagay na nais ko upang tumingin up ng isang salita. Maaaring dalhin ako malaking O ng n hakbang, dahil ang salita baka maging lahat ng mga paraan sa dulo ng sa listahan, tulad ng milong bilog. At ito ay lumiliko out na sa programming, pag-uuri ng mga banal na Kopita ng data istruktura, ay isang bagay na nagbibigay sa iyo ng pare-pareho oras tulad ng isang array ngunit na pa rin ay nagbibigay sa iyo dynamism. 

Upang maaari naming magkaroon ng pinakamahusay na ng parehong mundo? At sa katunayan, mayroong isang bagay na tinatawag na ang hash table na nagpapahintulot sa iyo na gawin eksakto na, albeit humigit-kumulang. A hash talahanayan ay isang may interes istraktura ng data na namin makapag-isip ng bilang ang kumbinasyon ng isang array at pupuntahan ko upang gumuhit ito tulad this-- at mga listahan ng link na kukunin ko gumuhit tulad na ito sa paglipas dito. 

At ang paraan ng bagay na ito mga gawa ay tulad ng sumusunod. Kung ito now-- hash table-- ang aking ikatlong istraktura ng data, at gusto kong mag-imbak mga salita sa ito, ako hindi nais na lamang-imbak ang lahat ng mga salita pabalik upang i-back upang i-back upang i-back. Gusto kong masulit ang ilang piraso ng impormasyon tungkol sa mga salita na hahayaan ako kumuha ito kung saan ito ay mas mabilis. 

Kaya ibinigay ang mga salita apple at saging at milong bilog, Kusa ko pinili ang mga salitang iyon. Bakit? Ano ang uri ng panimula iba't ibang tungkol sa tatlo? Ano ang halata? Simulan nila na may iba't ibang mga titik. 

Kaya alam mo kung ano? Sa halip na ilagay ang lahat ng aking mga salita sa ang parehong bucket, kaya na magsalita, tulad sa isang malaking listahan, bakit hindi Ko ng hindi bababa subukan ang isang optimization at gumawa ng aking listahan 1/26 bilang mahaba. A nakapanghihimok optimization maaaring bakit hindi I-- kapag nagpapasok ng isang salita sa ito istraktura ng data, sa memorya ng computer, kung bakit hindi ko ilagay ang lahat ng 'a' mga salita dito, lahat ng 'b' mga salita dito, at ang lahat ng 'c' salita dito? Kaya ito ay nagtatapos up ng paglagay ng isang mansanas dito, saging dito, milong bilog dito, at iba pa. 

At kung ako ay may isang karagdagang salita like-- kung ano ang iba? Mansanas, saging, peras. Kahit sino sa tingin ng isang prutas na nagsisimula sa a, b, oc? Blueberry-- perpekto. Iyon ay pagpunta sa end up dito. At kaya tila namin na magkaroon ng isang marginally mas mahusay na solusyon, dahil ngayon kung gusto kong upang maghanap para sa apple, ako first-- ginagawa ko'y hindi lamang dive sa aking data istraktura. Hindi ko sumisid sa memorya ng aking computer. Ako unang tumingin sa ang unang titik. 

At ito ay kung ano ang isang computer siyentipiko nais sabihin. hash ka sa iyong data istraktura. Dalhin mo ang iyong input, na sa kasong ito ay isang salita tulad ng mansanas. pag-aralan mo ito, ang pagtingin sa ang unang titik sa kasong ito, at dahil doon hashing ito. Hashing ay isang pangkalahatang kataga kung saan magdadala sa iyo ng isang bagay bilang input at makagawa ka ng ilang mga output. At ang output sa na kaso ay ang lokasyon na nais mong hanapin, ang unang lokasyon, pangalawang lokasyon, third. Kaya ang input ay mansanas, ang output ay unang. input ay banana, ang output ay dapat na segundo. input ay milong bilog, ang output ay dapat na third. input ay blueberry, ang output ay dapat muli maging second. At iyon ang kung ano ang tumutulong magdadala sa iyo shortcut sa pamamagitan ng iyong memory upang makakuha ng sa mga salita o data ng mas epektibo. 

Ngayon na ito cuts down ating panahon potensyal pamamagitan ng mas maraming gaya ng mula sa 26, dahil kung akala mo na ikaw magkaroon ng maraming "a" salitang gaya ng "z" salitang gaya ng "q" mga salita, na ay hindi tunay realistic-- ikaw ay pagpunta sa magkaroon ng hilig sa kabuuan tiyak na mga titik ng alphabet-- ngunit ito ay magiging isang incremental diskarte na ay magbibigay-daan sa mo upang makakuha ng mga salita mas mabilis. At sa katotohanan, isang sopistikadong programa, ang Googles ng mundo, ang Facebooks ng world-- ang mga ito ay gumamit ng isang hash table para sa isang pulutong ng mga iba't ibang mga layunin. Ngunit hindi sila ay kaya walang muwang bilang upang lamang tumingin sa ang unang titik sa mansanas o saging o peras o milong bilog, dahil tulad ng makikita mo ang mga mga listahan ay maaari pa ring makakuha ng mahaba. 

At kaya ito ay maaaring pa rin uri ng linear-- kaya uri ng mabagal, tulad ng sa malaking O ng n na namin tinalakay nang mas maaga. Kaya kung ano ay isang tunay na magandang hash table do-- magkakaroon ito ng isang magkano ang mas malaking array. At ito ay gamitin ng isang mas sopistikadong hashing function, upang ito ay hindi lang basta tingnan ang "a." Siguro ito ay tumitingin sa "a-p-p-l-e" at kahit papaano nagpalit ang limang titik sa ang lokasyon kung saan apple ay dapat na naka-imbak. Kami ay lamang naively gamit ang titik 'a' mag-isa, dahil sa ito ay maganda at simple. 

Ngunit ang isang hash table, sa Sa katapusan, maaari mong isipin ng bilang isang kumbinasyon ng isang array, ang bawat isa ay may isang listahan ng mga link na may perpektong dapat na bilang maikling hangga't maaari. At ito ay hindi isang malinaw na solusyon. Sa katunayan, marami ng fine tuning na napupunta sa ilalim ng hood kapag pagpapatupad ng mga uri ng mga sopistikadong istruktura ng data ay kung ano ay ang tamang haba ng array? Ano ang tamang hash? Paano mag-imbak ka ng mga bagay sa memory? 

Ngunit mapagtanto kung gaano kabilis ang ganitong uri ng talakayan tumataas, alinman sa ngayon na ito ay uri ng higit sa isa ng ulo sa puntong ito, na kung saan ay ayos. Ngunit kami nagsimula, isipin ang, na may tunay na isang bagay na mababa ang antas at electronic. At kaya ito ay muling sinabi ay ito tema ng abstraction, kung saan sa sandaling simulan mo na kumuha para sa ipinagkaloob, OK, Mayroon akong it-- mayroong pisikal na memory, OK, nakuha ko, sa bawat pisikal na lokasyon ay may isang address, OK, nakuha ko ito, maaari ba akong kumakatawan mga address bilang arrows-- maaari mong masyadong mabilis simulan upang magkaroon mas sopistikadong pag-uusap na sa dulo mukhang na nagpapahintulot sa amin upang malutas ang problema tulad ng paghahanap at pag-uuri ng mas epektibo. At magpahinga sigurado, too-- dahil sa tingin ko ito ay ang pinakamalalim na kami ay wala na sa ilang sa mga CS paksa proper-- na namin tapos na sa isang araw at isang kalahati sa ito ituro kung ano ang iyong karaniwang gawin sa paglipas ng kurso ng walong linggo sa isang semestre. 

Ang anumang mga katanungan sa mga ito? Hindi? Lahat tama. Well, bakit hindi namin i-pause doon, simulan tanghalian ng ilang minuto maaga, ipagpatuloy sa loob lamang tungkol sa isang oras? At kukunin ko na magtagal para ng kaunti sa mga tanong. Pagkatapos ay ako pagpunta sa may sa pumunta tumagal ng ilang mga tawag kung iyon lamang ang OK. Kukunin ko i-on ang ilang musika sa habang panahon, ngunit lunch dapat na sa paligid ng sulok.