[MUSIC nagpe-play] PROFESSOR: Lahat ng karapatan. Ito ay CS50 at ito ay ang katapusan ng linggo tatlong. Kaya narito kami ngayon, hindi sa Sanders Theater, sa halip sa Weidner Library. Inside ng kung saan ay isang studio kilala bilang Hauser Studio, o dapat naming sabihin Studio H, o dapat say-- namin kung Tatangkilikin mo na joke, ito ay mula sa aktwal na kaklase, Mark, online, na iminungkahi ng mas maraming sa pamamagitan ng Twitter. Ngayon kung ano ang cool na tungkol pagiging dito sa isang studio ay na ako napapalibutan ng mga berdeng pader, ng isang kulay berdeng screen o Chromakey, wika nga, na nangangahulugan na ang CS50 production team, walang anumang kaalaman sa akin sa ngayon, maaaring maging paglagay sa akin karamihan sa kahit saan sa mundo, para sa mas mahusay o para sa mas masahol pa. Ngayon kung ano ang kasinungalingan maaga, itakda ang problema dalawang ito ay nasa iyong mga kamay para sa linggong ito, pero sa pamamagitan ng hanay ng problema tatlong ito darating na linggo, ikaw ay hinamon sa ang tinatawag na laro ng 15, ang lumang partido pabor na maaari mong isipin ang pagtanggap bilang isang bata na may isang buong grupo ng mga numero na maaaring i-slide pataas, pababa, pakaliwa at pakanan, at mayroong isang puwang sa loob ng mga puzzle, sa kung saan ka maaaring aktwal na i-slide ang mga piraso ng puzzle. Sa huli mong matanggap ito palaisipan sa ilang mga semi random order, at ang layunin ay upang ayusin ito, itaas hanggang sa ibaba, kaliwa hanggang kanan, mula sa isang lahat ng mga paraan up sa pamamagitan ng 15. Sa kasamaang palad, ang pagpapatupad magkakaroon ka sa kamay ay magiging software based, hindi pisikal. Ikaw ang tunay na ay pagpunta sa may upang isulat code na kung saan ang mag-aaral o manwal ng lata i-play ang laro ng 15. At sa katunayan, sa hacker edisyon ng laro ng 15, makikita mo ang isang hamon upang ipatupad, hindi lamang ang paglalaro ng old school laro, ngunit sa halip ang tuos ng mga ito, ang pagpapatupad ng mode diyos, wika nga, na aktwal na malulutas nito ang puzzle para sa mga tao, sa pamamagitan ng pagbibigay sa kanila ng hint, matapos hint, pagkatapos ng hint. Kaya higit pa sa na sa susunod na linggo. Ngunit iyon lamang ang mangyayari sa hinaharap. Para sa ngayon pagpapabalik na mas maaga sa linggong ito kami ay nagkaroon na ito cliffhanger, kung ikaw ay, kung saan ang mga pinakamahusay na aming ginagawa sa pag-uuri matalino ay isang itaas na nakatali sa malaking o ng n nakalapat. Sa ibang salita, bubble uri, pagpili ng uri, uri pagpapasok, lahat ng mga ito, habang ang iba't-ibang sa kanilang pagpapatupad, devolved sa isang n nakalapat tumatakbo oras sa pinakadulo pinakamasama kaso. At kami ay karaniwang ipinapalagay na tunay pinakamasama kaso para sa pag-uuri ay isa na ang iyong input ay ganap na paurong. At sa katunayan, ito kinuha lubos ng ilang mga hakbang upang ipatupad ang bawat isa sa mga algorithm. Ngayon sa dulo ng klase pagpapabalik, namin kumpara bubble sort laban uri laban sa isa sa iba pang mga pagpipilian na tinatawag naming pagsasama-uuri sa oras, at imungkahi ko na ito ay ang pagkuha bentahe ng isang aralin mula sa linggo zero, hatiin at lupigin. At sa anumang paraan sa pagkamit ng ilang mga uri ng logarithmic tumatakbo ang oras sa huli, sa halip ng isang bagay na pulos parisukat. At ito ay hindi lubos logarithmic, ito ay isang piraso ng higit sa na. Subalit kung ang pagpapabalik sa iyo mula sa klase, ito ay marami, marami mas mabilis. Tingnan natin ang isang pagtingin sa kung saan namin kaliwa off. Sort Bubble laban seleksyon uri laban sa pagsasama-uuri. Ngayon lahat sila ay tumatakbo, sa teorya, at sa parehong oras. CPU ay tumatakbo sa parehong bilis. Ngunit maaari mong pakiramdam kung paano boring ito ay masyadong mabilis ang pagpunta sa maging, at lamang kung paano mabilis, kapag mag-iniksyon namin isang piraso ng algorithm linggo zero, ang maaari naming mapabilis ang mga bagay up. Kaya mukhang kamangha-manghang mark sort. Paano natin pagkilos ito, upang upang maipagsama-sama mga numero na mas mabilis. Sabihin sa tingin pabalik Well hayaan sa isang sangkap na namin nagkaroon pabalik sa linggo zero, na ng na naghahanap para sa isang tao sa isang libro ng telepono, at isipin na ang pseudocode na aming iminungkahi, sa pamamagitan ng kung saan maaari naming mahanap ang isang tao tulad ng Mike Smith, tumingin ng isang maliit na isang bagay na katulad nito. Ngayon tingnan sa partikular sa line 7 at 8, at 10 at 11, na magbuod na loop, kung saan kami ay nag-iingat balik sa 3 linya muli, at muli, at muli. Ngunit ito ay lumiliko out na maaari naming tingnan algorithm na ito, dito sa pseudocode, isang maliit na mas holistically. Sa katunayan, kung ano Naghahanap ako at dito sa screen, ay isang algorithm para sa paghahanap para Mike Smith sa gitna ng ilang hanay ng mga pahina. At sa katunayan, maaari naming gawing simple ito algorithm sa mga linya 7 at 8, at 10 at 11 upang sabihin lamang na ito, na kung saan ko na ipinakita dito sa kulay dilaw. Sa ibang salita, kung Mike Smith ay mas maaga sa aklat, hindi namin kailangan upang tukuyin ang hakbang sa pamamagitan ng hakbang na ngayon kung paano pumunta mahanap sa kanya. Wala kaming upang tukuyin upang bumalik sa line 3, bakit hindi namin sa halip na lamang, sabihin, mas pangkalahatang paraan, maghanap para sa Mike sa kaliwang kalahati ng libro. Sa kabaligtaran, kung Mike ay talagang ibang pagkakataon sa mga libro, bakit hindi na quote lang namin magpanipi search para sa Mike sa kanang kalahati ng libro. Sa ibang salita, bakit hindi namin lamang uri ng tumikin sa ating sarili na sinasabi, maghanap para sa Mike sa ganitong subset ng libro, at iwanan ito sa aming mga umiiral na algorithm upang sabihin sa amin paano mag-search para sa Mike sa na kaliwang kalahati ng libro. Sa ibang salita, ang aming algorithm ay gumagana kung ito ay isang libro ng kapal ng telepono, ng mga ito kapal, o anumang kapal ano pa man. Kaya maaari naming recursively tukuyin ang algorithm na ito. Sa ibang salita, sa screen dito, ay isang algorithm para sa paghahanap para sa Mike Smith sa pagitan ng mga pahina ng isang libro ng telepono. Kaya sa linya 7 at 10, sabihin lang sabihin eksakto na. At gagamitin ko ang terminong ito sa isang sandali nakaraan, at sa katunayan, recursion ay ang buzzword para sa ngayon, at ito ay ang proseso na ito ng paggawa ng isang bagay cyclical pamamagitan paanuman gamit ang code na mayroon ka, at pagtawag ito muli, at muli, at muli. Ngayon ito ay magiging mahalaga na namin sa paanuman ibaba out, at huwag gawin na walang katapusan ang haba. Kung hindi man namin ang pagpunta sa Mayroon talagang isang walang-katapusang loop. Ngunit sabihin makita kung maaari naming humiram ng mga ideya na ito ng isang recursion, paggawa ng isang bagay muli at muli at muli, upang malutas ang pag-uuri ng problema sa pamamagitan ng merge uri, lahat ng mga mas mahusay. Kaya bigyan ko bang pagsamahin mo sort. Tignan natin. Kaya dito ay pseudocode, na may kung saan maaari naming ipatupad ang pag-uuri, gamit ang algorithm na ito na tinatawag na pagsasama-uuri. At ito ay lubos na lamang ito. On input ng n elemento, sa ibang salita, kung ikaw ay ibinigay n elemento at mga numero at mga titik o kahit na ano ang input ay, kung ikaw ay bibigyan n elemento, kung n ay mas mababa sa 2, bumalik lang. Right? Dahil kung ang n ay mas mababa sa 2, na ay nangangahulugan na ang aking listahan ng mga elemento ay alinman sa sukat na 0 o 1, at sa pareho ng mga walang kuwenta mga kaso, ang listahan na pinagsunod-sunod. Kung walang listahan, ito ay pinagsunod-sunod. At kung may isang listahan ng haba 1, malinaw naman ito ay pinagsunod-sunod. Kaya lamang ang mga pangangailangan ng mga algorithm upang talagang gawin ang isang bagay na interesante, kung kami ay may dalawa o higit pang elemento ibinigay sa atin. Kaya tingnan natin ang magic pagkatapos ay hayaan. Iba Pa ayusin ang kaliwang kalahati ng mga sangkap, pagkatapos ay ayusin ang kanang kalahati ng mga sangkap, pagkatapos ay pagsamahin ang pinagsunod-sunod halves. At kung ano ang uri ng isip baluktot dito, ay na hindi ko talaga mukhang may nagsabi sa iyo kahit ano pa lang, di ba? Lahat ng sinabi ko na ay, na ibinigay ng isang listahan ng mga n elemento, uri-uriin ang kaliwang kalahati, pagkatapos ay ang kanang kalahati, at pagkatapos ay pagsamahin ang pinagsunod-sunod halves, ngunit kung saan ay ang aktwal na lihim sauce? Saan ang algorithm? Well ito ay lumiliko out na ang mga dalawang linya una, uri kaliwa kalahati ng mga sangkap, at uri kanang kalahati ng mga sangkap, mga recursive tawag, kaya na magsalita. Pagkatapos ng lahat, hindi na ito punto sa panahon, ang mayroon ako isang algorithm na kung saan na ayusin ang maramihang mga elemento? Oo. Ito ay karapatan dito. Ito ay karapatan dito sa screen, at kaya ang maaari kong gamitin ang parehong hanay ng mga hakbang upang ayusin ang kaliwang kalahati, bilang ko ang kanang kalahati. At sa katunayan, muli, at muli. Kaya sa anumang paraan o iba pang, at bibigyan namin ng lalong madaling panahon makita ang mga ito, ang magic ng pagsasama-uuri ay naka-embed sa mga na napaka-final line, pinagsasama ang pinagsunod-sunod na halves. At na tila medyo madaling maunawaan. Kumuha ka ng dalawang kalahati, at ikaw, kahit papaano, pagsamahin ang mga ito nang sama-sama, at kami na makita na ito concretely sa isang sandali. Ngunit ito ay isang kumpletong algorithm. At ni makita ang eksaktong dahilan kung bakit ipaalam. Well ipagpalagay na kami ay ibinigay ng mga parehong walong elemento dito sa screen, isa sa pamamagitan ng walong, ngunit ang mga ito sa mukha random order. At ang mga layunin sa kamay ay upang ayusin ang mga elementong ito. Well paano ko pumunta tungkol sa ginagawa ito gamit, muli, sumanib-uuri, tulad ng bawat ang pseudocode? At muli, itanim ito sa ang iyong isip, para sa sandali lamang. Ang unang kaso ay medyo walang halaga, kung ito ay mas mababa sa 2, bumalik lang, walang trabaho upang gawin. Kaya talagang may tatlo lamang mga hakbang sa tunay na panatilihin sa isip. Muli, at muli, ako pagpunta sa nais na magkaroon upang ayusin ang kaliwang kalahati, pagbukud-bukurin ang kanang kalahati, at pagkatapos ay sa sandaling ang kanilang dalawang kalahati ay pinagsunod-sunod, Gusto ko na pagsamahin ang mga ito nang sama-sama sa isa pinagsunod-sunod na listahan. Kaya panatilihin na sa isip. Kaya dito ay ang orihinal na listahan. Ni ituturing ito bilang isang Ipaalam array, tulad namin na nagsimula sa sa dalawang linggo, kung saan ay isang magkadikit bloke ng memorya. Sa kasong ito, na naglalaman ng walong numero, bumalik sa likod sa likod. At ngayon mag-aplay pagsasama-uuri ipaalam. Kaya unang ko nais upang maipagsama-sama sa kaliwang kalahati ng listahan na ito, at sabihin, samakatuwid, focus sa 4, 8, 6, at 2. Ngayon paano ko pumunta tungkol sa pag-uuri ng isang listahan ng mga laki 4? Well kailangan kong ngayon isaalang-alang paghihiwalay sa kaliwa ng kaliwang kalahati. Muli, ni rewind para sa sandali lamang ipaalam. Kung ang pseudocode ay ito, at ako ng ibinigay walong elemento, 8 ay malinaw naman higit na kaysa sa o katumbas ng 2. Kaya sa ay hindi akma sa unang kaso. Kaya upang maipagsama-sama walong elemento, ako unang pagbukud-bukurin ang kaliwang kalahati ng mga sangkap, pagkatapos ko ayusin ang mga karapatan sa kalahati, pagkatapos ay pagsamahin ko ang dalawang inayos halves, ang bawat isa ng mga laki 4. SIGE. Ngunit kung lamang na iyong sinabi sa akin, ayusin ang kaliwang kalahati, na ngayon ng mga laki 4, paano ko ayusin ang kaliwa kalahati? Well kung ako ay may isang input ng apat na mga sangkap, Ako unang-uri-uriin ang kaliwang dalawa, pagkatapos ay ang karapatan ng dalawa, at pagkatapos ko bang pagsamahin ang mga ito nang magkakasama. Kaya muli, ito ay nagiging isang bit ng isang isip baluktot laro dito, dahil sa iyo, uri ng, kung tandaan kung nasaan ka sa mga kuwento, ngunit sa pagtatapos ng araw, bibigyan ng anumang numero ng mga elemento, unang nais na ayusin ang kaliwang kalahati, at pagkatapos ay ang kanang kalahati, pagkatapos ay pagsamahin ang mga ito nang magkakasama. Magsimula na gawin eksakto na Hayaan. Narito ang input ng walong elemento. Ngayon kami ay naghahanap sa kaliwang kalahati dito. Paano ko ayusin apat na mga sangkap? Well una kong ayusin ang kaliwa kalahati. Ngayon paano ko ayusin ang kaliwa kalahati? Well ko na binigyan ng dalawang elemento. Kaya ayusin ni ang dalawang mga elemento ipaalam. 2 ay mas malaki kaysa sa o katumbas ng 2, siyempre. Kaya na unang kaso ay hindi akma. Kaya ako ngayon ay upang ayusin ang kaliwang kalahati ng mga ito ng dalawang mga sangkap. Ang kaliwang kalahati, siyempre, ay 4 lamang. Kaya paano ko ayusin ang isang listahan ng isang elemento? Well ngayon, ang mga espesyal na base kaso up itaas, kaya na magsalita, nalalapat. 1 ay mas mababa sa 2, at ang aking list ay sa katunayan ng sukat 1. Kaya bumalik ako lang. Hindi ako gumawa ng kahit ano. At sa katunayan, tumingin sa kung ano na ko tapos, 4 na pinagsunod-sunod. Tulad na ako bahagyang matagumpay dito. Ngayon na tila uri ng tangang sa paghahabol, ngunit ito ay totoo. 4 ay isang listahan ng mga sukat 1. Na ito ay pinagsunod-sunod. Iyan ang kaliwang kalahati. Ngayon ko uri-uriin ang kanang kalahati. Aking input ay isang elemento, 8 katulad, pinagsunod-sunod. Stupid, masyadong, ngunit muli, pangunahing alituntuning ay pagpunta sa nagpapahintulot sa amin upang ngayon magtayo sa tuktok ng ito ay matagumpay na. 4 inayos, 8 ay inayos, ngayon kung ano na ang huling hakbang? Kaya ang ikatlong at huling hakbang, ang anumang oras na naka-uuri-uri ng isang listahan, pagpapabalik, ay upang sumanib sa dalawang halves, sa kaliwa at kanan. Kaya sabihin gawin eksakto na. Aking kaliwang kalahati ay, of course, 4. Aking kanang kalahati ay 8. Kaya sabihin gawin ito. Unang pupuntahan ko upang maglaan ang ilang mga karagdagang memory, na kukunin ko na kumakatawan dito, bilang lamang ng isang pangalawang array, na sapat na malaki upang magkasya ito. Ngunit maaari mong isipin ang pagpapalawak na rectangle ang buong haba, kung kailangan namin ng higit pang mga bago. Paano ako kumuha ng 4 at 8, at sumanib dalawang mga listahan ng mga ng laki 1 magkasama? Dito, masyadong, pretty simple. Unang 4 na dumating, at pagkatapos ay dumating 8. Dahil kung gusto kong ayusin ang kaliwang kalahati, at pagkatapos ay ang kanang kalahati, at pagkatapos ay pagsamahin ang dalawang halves sama-sama, sa inayos order, Unang 4 na dumating, at pagkatapos ay dumating 8. Kaya tila namin ay ang paggawa ng progreso, kahit na kahit na hindi ko nagawa ang anumang aktwal na trabaho. Ngunit tandaan na kung saan tayo sa kuwento. Orihinal naming kinuha walong elemento. Inayos namin ang kaliwang kalahati, na kung saan ay 4. Pagkatapos inayos namin ang kaliwang kalahati ng kaliwang kalahati, na kung saan ay 2. At ayan na naman. Kami ay tapos ka na sa hakbang na iyon. Kaya kung Inayos na namin ang mga kaliwa kalahati ng 2, na namin ngayon kung ayusin ang mga karapatan sa kalahati ng 2. Kaya ang kanang kalahati ng 2 ay mga ito ng dalawang mga halaga dito, 6 at 2. Kaya sabihin na ngayong kumuha ng isang input ng laki 2, at uri-uriin ang kaliwang kalahati, at pagkatapos ay ang kanang kalahati, at pagkatapos ay pagsamahin ang mga ito nang magkakasama. Well paano ko ayusin ang isang listahan ng laki 1, na naglalaman lamang ang bilang 6? Ginagamit ko na tapos na. Na listahan ng mga sukat na 1 ay pinagsunod-sunod. Paano ko ayusin ng isa pang listahan ng mga size 1, ang tinatawag na kanang kalahati. Well ito, masyadong, na pinagsunod-sunod. Ang bilang 2 ay nag-iisa. Kaya ngayon ay mayroon akong dalawang halves, kaliwa at karapatan, kailangan ko na pagsamahin ang mga ito nang magkakasama. Hayaan akong bigyan ang aking sarili ng ilang dagdag na espasyo. At maglagay ng 2 sa doon, pagkatapos ay 6 sa doon, sa gayon pag-uuri listahan na iyon, kaliwa at kanan, at pinagsasama ang mga ito nang sama-sama, sa huli. Kaya ako sa bahagyang mas mahusay na hugis. Hindi ko na tapos na, dahil malinaw na 4, 8, 2, 6 ay hindi ang panghuling pag-order na gusto ko. Ngunit ako ngayon ay dalawang mga listahan ng laki 2, na may pareho, ayon sa pagkakabanggit, ay inayos. Kaya ngayon kung rewind mo sa iyong isip ni eye, saan na-iwan sa amin? Nagsimula ako sa walong elemento, pagkatapos ay ako whittled ito pababa sa kaliwang kalahati ng 4, pagkatapos ay sa kaliwang kalahati ng 2, at pagkatapos ay ang kanang kalahati ng 2, Natapos ko, samakatuwid, pag-uuri sa kaliwa kalahati ng 2, at ang kanang kalahati ng 2, kaya kung ano ang ikatlong at huling hakbang dito? Kailangan ko bang sumanib magkasama dalawang mga listahan ng laki 2. Kaya sabihin sige. At sa screen dito, bigyan sa akin ang ilang mga karagdagang memory, bagaman technically, mapapansin na ko Naging isang buong bungkos ng mga blangko ang puwang up top doon. Kung gusto kong maging lalo mabisa space matalino, Hindi ko na lang simulan ang paglipat ng mga elemento balik, itaas at ibaba. Ngunit lamang para sa visual na kaliwanagan, Pupunta ako upang ilagay ito sa ibaba, upang panatilihing maganda at malinis na mga bagay. Kaya Mayroon akong dalawang mga listahan ng laki 2. Ang unang listahan ay may 4 at 8. Ang pangalawang listahan ay may 2 at 6. Ni sumanib mga Ipaalam magkasama sa inayos order. 2, siyempre, ang nauna, pagkatapos ay 4, pagkatapos 6, pagkatapos ay 8. At ngayon kami ay tila na maging sa pagkuha sa tabi-tabi na interesante. Ngayon ay na pinagsunod-sunod sa ko kalahati ng list, at coincidentally, ito ay lahat ng kahit na mga numero, ngunit na ay, sa katunayan, isang pagkakataon lamang. At ako ngayon ay may inayos ang kaliwang kalahati, kaya na ito ay 2, 4, 6, at 8. Walang ay sa labas ng order. Na pakiramdam ng tulad ng pag-unlad. Ngayon ito nararamdaman tulad na ko pakikipag-usap magpakailanman ngayon, kaya kung ano ay nananatiling upang makita kung ito algorithm ay, sa katunayan, mas mahusay. Ngunit kami ay pagpunta sa pamamagitan ng ito super methodically. Ang isang computer, siyempre, Gusto ko ito tulad na. Kaya kung saan ang mga namin? Nagsimula kami sa walong elemento. Inayos ko ang kaliwang kalahati ng 4. Mukhang kong gawin sa mga iyon. Kaya ngayon ang susunod na hakbang ay pagbukud-bukurin ang kanang kalahati ng 4. At bahagi ito maaari naming pumunta sa pamamagitan ng isang maliit na mas mabilis, kahit na ikaw ay malugod na rewind o i-pause, makatarungan tingin sa pamamagitan ng mga ito sa sarili mong bilis, ngunit kung ano na namin ngayon ay isang pagkakataon upang gawin ang eksaktong parehong algorithm sa apat magkakaibang numero. Kaya sabihin sige, at tumutok sa ang kanang kalahati, na kung saan kami ay dito. Ang kaliwang kalahati ng na kanang kalahati, at ngayon ang kaliwang kalahati ng kaliwang kalahati ng na kanang kalahati, at kung paano ko ayusin ang isang listahan ng laki 1 na naglalaman lamang ang bilang 1? Tapos na. Paano ko gawin ang parehong para sa isang listahan ng laki 1 na naglalaman lamang ng 7? Tapos na. Hakbang tatlong para sa mga ito sa kalahati pagkatapos ay upang sumanib ang dalawang mga elemento sa isang bagong listahan ng mga laki 2, 1 at 7. Huwag mukhang may tapos na ang lahat ganoong karaming mga kawili-wiling trabaho. Tingnan natin kung ano ang susunod na mangyayari Hayaan. Ko lang inayos ang kaliwang kalahati ng karapatan sa kalahati ng aking orihinal na input. Ngayon ayusin ni kanan ipaalam kalahati, na naglalaman ng 5 at 3. Muli tumingin sa kaliwa Ipaalam kalahati, ayun, kanang kalahati, ayun, at sumanib sa mga dalawang magkasama, sa ilang dagdag na espasyo, 3 ang mauna, at pagkatapos ay dumating 5. At kaya ngayon, may inayos namin ang mga kaliwang kalahati ng kanang kalahati ng orihinal na problema, at ang kanang kalahati ng kanang kalahati ng orihinal na problema. Ano ang ikatlong at huling hakbang? Well upang sumanib sa mga dalawang halves magkasama. Kaya hayaan mo akong makakuha ng aking sarili sa ilang dagdag na espasyo, ngunit, muli, ako maaaring gamit na ekstrang espasyo up top. Ngunit kami ay pagpunta sa panatilihin itong simple biswal. Hayaan akong sumanib sa ngayon 1, at pagkatapos ay 3, at pagkatapos ay 5, at pagkatapos ay 7. Sa gayong paraan Aalis ako ngayon sa mga kanang kalahati ng orihinal na problema na ganap na pinagsunod-sunod. Ano Kaya nananatiling? Pakiramdam ko ay tulad panatilihin ko sinasabi ang parehong bagay muli, at muli, ngunit iyan ay mapanimdim ng katunayan na aming ginagamit recursion. Ang proseso ng paggamit ng isang algorithm muli, at muli, sa mas maliit na subset ng ang orihinal na problema. Kaya ako ngayon ay may inayos ng isang kaliwa kalahati ng mga orihinal na problema. May karapatan akong inayos half ng orihinal na problema. Ano ang ikatlong at huling hakbang? Oh, ito ay pinagsasama. Kaya sabihin gawin iyon. Sabihin maglaan ng ilang karagdagang memory, ngunit ang aking mga diyos, kami ay ito ay maaaring ilagay kahit saan sa ngayon. Mayroon kaming magagamit kaya magkano ang puwang sa amin, ngunit kami ay panatilihin itong simple. Sa halip ng pagpunta sa likod at balik sa aming orihinal na memorya, sabihin lamang gawin ito biswal down dito sa ibaba, upang tapusin up pagsanib ng kaliwang kalahati at ang kanang kalahati. Kaya sa pamamagitan ng pinagsasama, ano ang kailangan kong gawin? Gusto kong kumuha ng mga elemento sa order. Kaya ang pagtingin sa kaliwang kalahati, Nakikita ko ang unang numero ay 2. Tumingin ako sa kanang kalahati, Nakikita ko ang unang numero ay 1, kaya malinaw naman kung saan number ang gusto kong bunutin, at inuuna sa aking huling listahan? Siyempre, 1. Ngayon, gusto kong hilingin na parehong katanungan. Sa kaliwang kalahati, na ako Nakakuha pa rin ang number 2. Sa kanang kalahati, Mayroon akong ang number 3. Aling isa ang gusto kong piliin? Siyempre, number 2 At ngayon ay mapapansin sa mga kandidato 4 sa kaliwa, 3 sa kanan. Sabihin, siyempre, piliin ang 3. Ngayon ang mga kandidato ay 4 sa sa kaliwa, 5 sa kanan. Kami, siyempre, piliin ang 4. 6 sa kaliwa, 5 sa kanan. Kami, siyempre, piliin ang 5. 6 sa kaliwa, 7 sa kanan. Pumili kami ng 6, at pagkatapos namin piliin ang 7, at pagkatapos ay piliin namin 8. Voila. Kaya ang isang malaking bilang ng mga salita sa ibang pagkakataon, kami ay may inayos ang listahang ito ng walong elemento sa isang listahan ng isa sa pamamagitan ng walong, na pagtaas sa bawat hakbang, ngunit kung magkano ang oras na ginawa aabutin upang gawin iyon sa amin. Well hindi ko na sadyang out pictorially inilatag bagay dito, upang maaari naming uri ng makita o pinasasalamatan ang division sa mapanakop na ang na-aksidente. Sa katunayan, kung ikaw ay tumingin muli sa wake, Iniwan ko na ang lahat ng mga tuldok na mga linya sa may hawak ng lugar, maaari mong, uri ng, makita, sa reverse order, kung ang uri ng kang maghanap pabalik sa kasaysayan ngayon, ang aking orihinal na listahan ay, of course, ng size 8. At pagkatapos ay dati, ako ay pagharap sa dalawang mga listahan ng laki 4, at pagkatapos ng apat na mga listahan ng mga laki 2, at pagkatapos ay walong listahan ng mga laki 1. Kaya kung ano ang gumagawa nito, uri ng, ipaalala sa iyo ng? Well, sa katunayan, ang alinman sa mga ang algorithm na namin tumingin sa gayon ay malayo kung saan kami hatiin, at hatiin, at hatiin, panatilihin ang pagkakaroon muli ng mga bagay, at muli, ang mga resulta na ito sa pangkalahatang ideya. At kaya mayroong isang bagay logarithmic nangyayari dito. At ito ay hindi lubos log ng n, ngunit mayroong isang logarithmic component sa kung ano lang ginawa namin. Ngayon isaalang-alang ang kung paano na aktwal na ay. Kaya mag-log ng n, ay muli isang mahusay na tumatakbo oras, kapag ginawa namin ang isang bagay tulad binary paghahanap, bilang tawag namin ito ngayon, ang hatiin at lupigin diskarte sa pamamagitan ng kung saan namin natagpuan Mike Smith. Ngayon technically. Iyan ay log base 2 ng n, kahit kahit na sa karamihan ng mga klase sa matematika, 10 ay karaniwang ang base na akala mo. Ngunit siyentipiko computer halos palaging mag-isip at makipag-usap sa mga tuntunin ng base 2, kaya kami ay karaniwang lamang sabihin log ng n, sa halip na mag-log base 2 ng n, ngunit ang mga ito ay eksaktong isang at ang parehong sa mundo ng mga computer agham, at bilang isang tabi, mayroong isang constant factor pagkakaiba sa pagitan ng dalawang, kaya pagtalunan pa rin, para sa mas pormal na dahilan. Ngunit sa ngayon, mga bagay na mahalaga namin tungkol sa ay halimbawa na ito. Kaya hindi ni patunayan sa pamamagitan ng halimbawa ipaalam, ngunit sa bababa gamitin ang isang halimbawa ng mga numero sa kamay bilang isang katinuan check, kung ikaw ay. Kaya dati ang formula ay log base 2 ng n, ngunit kung ano ang n sa kasong ito. Nagkaroon na ako n orihinal na mga numero, o 8 ng orihinal na numero mismo. Ngayon ito ay naging isang maliit na habang, ngunit ako ay medyo siguraduhin na mag-log base 2 ng halaga 8 ay 3, at sa katunayan, kung ano ang magaling tungkol sa na ay na ang 3 ay eksakto ang bilang ng mga beses na maaari mong hatiin ang isang listahan ng muli, at muli haba 8, at muli, hanggang sa ikaw ay kaliwa may mga listahan ng mga sukat lamang 1. Right? 8 papunta sa 4, papunta sa 2, papunta sa 1, at na ang mapanimdim ng eksakto na picture namin ay may lamang ng isang sandali ang nakalipas. Kaya ng kaunti katinuan check na sa kung saan logarithm ay aktwal na kasangkot. Kaya ngayon, ano pa ang kasangkot dito? n. Kaya mapapansin na ang bawat time split ko sa listahan, kahit na baligtad ang pagkakasunudsunod sa kasaysayan dito, hindi pa rin ako ay ginagawa n bagay. Na pinagsasama ang hakbang na kinakailangan na Hinawakan ko ang bawat isa sa mga numero, upang slide ito sa kanyang naaangkop na lokasyon. Kaya kahit na ang taas ng mga ito diagram ay ng laki log n ng n o 3, partikular, sa ibang salita, Ginawa ko tatlong sangay dito. Magkano work ang gagawin ko horizontally kasama ang chart na ito sa bawat panahon? Well, ginawa ko n hakbang ng magtrabaho, dahil kung hindi ko na Nakakuha ng apat na elemento at apat na mga sangkap, at kailangan ko upang pagsamahin ang mga ito nang magkakasama. Kailangan ko bang pumunta sa pamamagitan ng mga apat na at ang mga ito sa apat, sa huli upang pagsamahin ang mga ito bumalik sa walong elemento. Kung pasalungat Mayroon akong walong mga daliri higit sa rito, na hindi ako, at walong fingers-- sorry-- Kung Na ko Nakakuha apat na daliri sa paglipas dito, kung saan gagawin ko, apat na mga daliri higit sa rito, na ang gagawin ko, pagkatapos na ang parehong Halimbawa tulad ng dati, kung gagawin ko may walong daliri bagaman sa total, kung saan maaari kong, uri ng, gawin. Maaari ko nang eksakto gawin dito, pagkatapos ay maaari ko tiyak pagsamahin ang lahat ng mga listahang ito ng laki 1 magkasama. Ngunit tiyak ko upang tumingin sa bawat elemento ng minsan. Kaya ang taas ng prosesong ito ay log n, ang lapad ng prosesong ito, kaya na magsalita, ay n, kaya kung ano tila namin na magkaroon, sa huli, ay isang oras na tumatakbo ng laki n beses log n. Sa ibang salita, hinati namin listahan, mag-log n beses, ngunit sa bawat oras na ginawa namin na, kami ay sa pindutin ang bawat isa sa mga elemento upang pagsamahin ang mga ito lahat ng sama-sama, na kung saan ay n hakbang, kaya kami n beses log n, o bilang isang computer scientist nais sabihin, asymptotically, na ay magiging ang malaking salita upang ilarawan ang itaas nakasalalay sa isang tumatakbo ang oras, kami ay tumatakbo sa isang malaking o ng mag-log n oras, kaya na magsalita. Ngayon na ito ay makabuluhan, dahil isipin kung ano ang tumatakbo beses ay may mga uri ng bubble, at pagpili uri, at uri pagpapasok, at kahit na ang ilang mga iba na umiiral, n nakalapat ay kung saan kami ay sa. At maaari mong, uri ng, makita ang mga ito dito. Kung n nakalapat ay malinaw naman n ulit n, ngunit dito kami n beses log n, at kami na malaman mula sa linggo zero, na mag-log n, ang logarithmic, ay mas mahusay kaysa sa isang bagay linear. Pagkatapos ng lahat, isipin ang mga larawan na ang red at ang dilaw at ang berdeng linya na namin Drew, ang green logarithmic line ay lubhang mas mababa. At dahil dito, mas mas mahusay at mas mabilis na kaysa sa mga straight dilaw at pulang linya, n beses log n ay, sa katunayan, mas mahusay na kaysa n beses n, o n nakalapat. Kaya tila namin na magkaroon kinilala ng isang algorithm merge uri na tumatakbo sa marami mas mabilis na oras, at sa katunayan, na ang dahilan kung bakit, mas maaga sa linggong ito, kapag Nakita namin na ang paligsahan sa pagitan ng bubble uri, pagpili ng uri, at sumanib uri-uriin, sumanib uri tunay, tunay na nanalo. At sa katunayan, hindi namin kahit na maghintay para sa uri ng bubble at pagpili-uuri tapusin. Ngayon sabihin tumagal ng isa sa iba pang pass at ito, mula sa isang bahagyang mas pormal na pananaw, lamang sa kaso, mas mahusay na ito resonates kaysa sa mas mataas na antas ng talakayan. Kaya dito muli ang algorithm. Tanungin natin ang ating sarili Hayaan, kung ano ang mga oras na tumatakbo ay sa ito algorithm iba't-ibang mga hakbang na ito? Hatiin natin ito sa unang Ipaalam kaso at ang pangalawang kaso. Ang KUNG at ang Iba Pa Sa KUNG kaso, KUNG n ay mas mababa sa 2, bumalik lang. Nararamdaman tulad ng pare-pareho ang panahon. Ito ay, uri ng, tulad ng dalawang hakbang, KUNG n ay mas mababa sa 2, pagkatapos ay bumalik. Ngunit tulad ng sinabi namin sa Monday, pare-pareho ang oras, o malaki o ng 1, maaaring dalawang hakbang, tatlong hakbang na ito, kahit na sa 1,000 na mga hakbang. Ano ang mga bagay na ito ay ang tapat na bilang ng mga hakbang. Kaya ang dilaw na naka-highlight pseudocode dito ay tumatakbo sa, kami ay tumawag ito, pare-pareho ang panahon. Kaya mas pormal na, at kami ay pagpunta to-- ito ay ang lawak na kung saan namin gawing pormal ang karapatan na ito now-- T ng n, ang oras ng paggana ng isang problema na tumatagal n somethings bilang input, ay katumbas ng malaking o ng isa, KUNG n ay mas mababa sa 2. Kaya ito ay may kondisyon sa na. Kaya upang maging malinaw, KUNG n ay mas mababa sa 2, mayroon kaming isang maikling listahan, pagkatapos ay ang oras, T ng n, kung saan ang n ay 1 o 0, sa ito tunay tiyak na kaso, ito lamang ay magiging tapat na oras. Ito ay pagpunta sa tumagal ng isa hakbang, dalawang hakbang, kahit ano. Ito ay isang takdang bilang ng mga hakbang. Kaya ang juicy part dapat maging tiyak na sa sa iba pang mga kaso sa pseudocode. Ang Iba Pa kaso. Pagbukud-bukurin kaliwang kalahati ng mga elemento, uri ng karapatan kalahati ng mga elemento, sumanib inayos halves. Gaano katagal ang bawat isa sa mga hakbang na ginagawa? Well, kung ang tumatakbo oras upang ayusin n elemento ay, sabihin na tawag ito very generically, T ng n, pagkatapos ay pag-uuri sa kaliwa kalahati ng mga elemento ay, uri ng, tulad ng sinasabi, T ng n hinati sa 2, at parehas na pag-uuri ang kanang kalahati ng mga elemento ay, uri ng, tulad ng sinasabi, T ng n hinati sa 2, at pagkatapos ay pinagsasama ang pinagsunod-sunod halves. Well kung nakuha ko ang ilang mga bilang ng mga elemento dito, tulad ng apat, at ang ilang numero ng ng mga elemento dito, tulad ng apat, at ako ay may upang sumanib sa bawat isa sa mga apat na in, at bawat isa sa mga apat na sa, isang pagkatapos ng isa, upang ang sa huli mayroon akong walong elemento. Ito nararamdaman tulad na malaki o ng n hakbang? Kung Mayroon akong n daliri at ang bawat isa sa ang mga ito ay dapat na ipinagsama sa lugar, na tulad ng isa pang n hakbang. Kaya nga formulaically, maaari naming ipahayag ito, kahit na isang maliit scarily sa una sulyap, ngunit ito ay isang bagay na na kinukuha eksakto na lohika. Ang oras ng pagpapatakbo, T ng n, KUNG n ay mas malaki kaysa sa o katumbas ng 2. Sa kasong ito, ang Iba Pa kaso, ay T ng n hinati sa 2, plus T ng n hinati sa 2, plus malaki o ng n, ang ilang mga linear bilang ng mga hakbang, siguro eksakto n, siguro 2 beses n, ngunit ito ay halos, pagkakasunud-sunod ng n. Kaya na rin, ay kung paano namin Maaari ipahayag ito formulaically. Ngayon hindi mo nais na malaman na ito maliban kung na iyong narekord ito sa iyong isip, o hanapin ito sa likod ng isang aklat-aralin, na ay maaaring magkaroon ng isang maliit na cheat sheet sa dulo, ngunit ito ay, sa katunayan, pagpunta sa bigyan kami ng isang malaking o ng n log n, dahil iyon ang pag-ulit nakakakita ka dito sa screen, kung talagang ginawa ito, may isang walang-katapusang bilang ng mga halimbawa, o ginawa mo ito formulaically, gusto mo makita na ito, dahil ito formula mismo ay recursive, na may t ng n higit sa isang bagay sa kanan, at t of n higit sa sa kaliwa, ito ay maaaring aktwal na ipinahayag, sa huli, bilang malaking pumunta ng n log n. Kung hindi kumbinsido, na ang multa para sa ngayon, lamang kumuha sa pananampalataya, na na, sa katunayan, ano ang mga leads na pag-ulit sa, ngunit ito ay lamang ng isang bit higit pa sa isang matematiko sa naghahanap sa pagtakbo ng oras ng pagsasama-uuri batay sa pseudocode kanyang nag-iisa. Ngayon sabihin tumagal ng isang piraso ng isang hinay mula sa lahat ng mga iyon, at kumuha ng isang pagtingin sa isang tiyak na dating senador, na maaaring tumingin ng isang maliit na pamilyar, na nakaupo sa Eric Google Schmidt, ilang oras ang nakalipas, para sa isang interbyu sa entablado, sa harap ng isang buong grupo ng mga tao, pakikipag-usap sa huli tungkol sa isang paksa, na pamilyar pretty ngayon. Tignan natin. ERIC Schmidt: Ngayon Senator, nandito ka sa Google, at gusto kong isipin ng panguluhan bilang isang pakikipanayam sa trabaho. Ngayon ito ay mahirap upang makakuha ng trabaho bilang presidente. Pangulo Obama: Karapatan. ERIC Schmidt: At ikaw ay pagpunta sa gawin [hindi marinig] ngayon. Ito ay mahirap din upang makakuha ng trabaho sa Google. Pangulo Obama: Karapatan. ERIC Schmidt: Mayroon kaming mga katanungan, at hinihiling namin sa aming mga katanungan sa mga kandidato, at ang isang ito ay mula sa Larry Schwimmer. Pangulo Obama: OK. ERIC Schmidt: Ano? Ikaw guys sa tingin ko na ata? Ito ay karapatan dito. Ano ang pinaka-mahusay na paraan upang pagbukud-bukurin isang milyong 32 bit integer? Pangulo Obama: Well-- ERIC Schmidt: Minsan, siguro Sorry, maybe-- Pangulo Obama: Hindi, hindi, hindi, hindi, hindi, think-- ko ERIC Schmidt: Iyan ay hindi it-- Pangulo Obama: ko Sa tingin, tingin ko ang bubble uri ay ang maling paraan upang pumunta. ERIC Schmidt: Sige na. Sino ang nagsabi sa kanya ito? SIGE. Hindi ko ang computer science on-- Pangulo Obama: Hindi namin nakuha ang aming mga espiya sa doon. PROFESSOR: Lahat ng karapatan. Ni iwan sa likod tayo ngayon sa Ipaalam panteorya mundo ng mga algorithm sa asymptotic analysis niyaon, at bumalik sa ilang mga paksa mula sa linggo zero at isa, at start upang alisin ang ilang mga gulong ng pagsasanay, kung gagawin mo. Kaya na talagang nauunawaan mo sa huli mula sa lupa up, kung ano ang nangyayari sa ilalim ng hood, kapag ikaw sumulat, sumulat ng libro, at maglalapat ng mga programa. Pagpapabalik sa partikular, na ito ay ang unang programa C namin tumingin, isang canonical, simple program ng masama, medyo pagsasalita, kung saan, ang mga kopya, Hello World. At pagpapabalik na ang sinabi ko, ang proseso na source code Dumadaan ay eksakto na ito. Dalhin mo ang iyong source code, ipasa ito sa pamamagitan ng isang tagatala, tulad Clang, at lumapit object code, na Maaaring ganito ang hitsura, zero at mga na CPU ng computer, central processing unit o utak, huli nauunawaan. Lumalabas na iyon ang isang bit ng isang oversimplification, na kami ngayon sa isang posisyon upang mang-ulol hiwalayin upang maunawaan kung ano talaga ang naging nangyayari sa ilalim ng hood sa bawat oras na patakbuhin mo Clang, o mas pangkalahatang paraan, sa bawat oras na gumawa ng isang program, paggamit ng Magsagawa at CF 50 IDE. Sa partikular, ang mga bagay-bagay tulad ng ito ay unang nabuo, noong una itala ang iyong programa. Sa ibang salita, kapag kayo kunin ang iyong source code at ilista ang mga ito, kung ano ang unang pagiging outputted sa pamamagitan Clang ay isang bagay na kilala bilang assembly code. At sa katunayan, mukhang eksakto tulad nito. Nagpatakbo ako ng isang utos sa command line mas maaga. Hello.c Clang dash capital s, at ito ay lumikha ng isang file para sa akin na tinatawag na hello.s, sa loob ng kung saan ay eksakto mga nilalaman, at ng kaunti pa sa itaas at ng kaunti pa sa ibaba, ngunit ko na ilagay ang juiciest impormasyon dito sa screen. At kung titingnan mo nang maigi, makikita mo ang hindi bababa sa ilang mga pamilyar na mga keyword. Mayroon kaming main sa itaas. May printf down na kami sa gitna. At mayroon din kaming hello world backslash n sa quotes down sa ibaba. At lahat ng iba pa sa dito ay napakababa tagubilin level na naiintindihan ng CPU ng computer. Mga tagubilin CPU na ilipat memory sa paligid, na load string mula sa memorya, at sa huli, i-print mga bagay-bagay sa screen. Ngayon kung ano ang mangyayari kahit na matapos ito assembly code ay nabuo? Sa huli, ang gagawin mo, sa katunayan, pa rin bumuo ng object code. Ngunit ang mga hakbang na mayroon talagang ay nangyayari sa ilalim ng hood tumingin ng kaunti pa tulad nito. Source code nagiging assembly code, na pagkatapos ay nagiging object code, at ang pinaiiral salita dito ang mga iyon, kapag itala ang iyong source code, out pagdating assembly code, at pagkatapos ay kapag ipon mo ang iyong code sa pagpupulong, out pagdating object code. Ngayon Clang ay sobrang sopistikadong, tulad ng isang pulutong ng mga compiler, at ito ay ang lahat ng mga hakbang na ito sama-sama, at ito ay hindi kinakailangang output anumang intermediate file na maaari mong kahit na makita. Compiles Ito lamang ang mga bagay-bagay, kung saan ay ang pangkalahatang kataga na Inilalarawan ang buong proseso. Ngunit kung gusto mo talagang upang maging partikular, mayroong isang pulutong ng higit sa pagpunta doon pati na rin. Ngunit sabihin ring isaalang-alang na ngayon na kahit na sobrang simple na programa, hello.c, tinatawag na isang function. Ito ay tinatawag na printf. Ngunit hindi ko isulat printf, sa katunayan, na nanggagaling sa c, kaya na magsalita. Ito ay isang function na recall na ipinahayag sa standard io.h, na ay isang header ng file, na ay isang paksa kami talaga sumisid sa mas malalim na bago ang haba. Ngunit ang isang header na file ay karaniwang sinamahan sa pamamagitan ng isang code na file, source code file, kaya marami tulad ng may umiiral na standard io.h. Minsan ang nakakaraan, ang isang tao, o someones, nagsulat din isang file na tinatawag na standard io.c, sa na kung saan ang aktwal na kahulugan, o mga pagpapatupad ng printf, at mga kumpol ng iba pang mga pag-andar, ay tunay na nakasulat. Kaya ibinigay na, kung isasaalang-alang namin ang pagkakaroon dito sa kaliwa, hello.c, na kapag pinagsama-sama, ay nagbibigay sa amin hello.s, kahit na Clang ay hindi abala sa pag-save sa isang lugar maaari naming makita ang mga ito, at na pagpupulong code makakakuha tipunin sa hello.o, na ay, sa katunayan, ang default na pangalan ibinigay kapag mong ilista ang pinagmulan code sa object code, ngunit hindi lubos na handa upang maisagawa ito pa, dahil ang isa pang hakbang may mangyari, at may ay nangyayari para sa nakalipas na ilang linggo, marahil walang anumang kaalaman sa iyo. Partikular sa tabi-tabi sa CS50 IDE, at ito, masyadong, ay isang piraso ng isang oversimplification para sa isang sandali, may, o ay sa isang oras, isang file na tinatawag na standard io.c, na ang isang tao naipon sa standard io.s o ang katumbas, na ang isang tao pagkatapos ay binuo sa standard io.o, o ito ay lumiliko out sa isang bahagyang naiiba file format na maaaring magkaroon ng iba't ibang maghain extension kabuuan, ngunit sa teorya at conceptually, eksakto ang mga hakbang ay mangyari sa ilang mga form. Alin sa mga sinasabi, na ngayon ako kapag ako ay pagsulat ng isang programa, hello.c, na nagsasabing lamang, hello mundo, at gumagamit ako ng code ng ibang tao tulad ng printf, na kung saan ay isang beses sa isang panahon, sa isang file na tinatawag na standard io.c, pagkatapos ay sa paanuman Mayroon akong gumawa ng aking object code, ang aking mga zero at mga, at object ng taong iyon code, o zero at mga, at sa anumang paraan link ang mga ito nang magkakasama sa ng isang pangwakas na file, na tinatawag na hello, na may lahat ng mga zero at iyan mula sa aking pangunahing pag-andar, at ang lahat ng mga zero at iyan para sa printf. At sa katunayan, na ang huling proseso ay tinatawag na, na nagli-link ang iyong mga object code. Ang output ng na ay isang executable file. Kaya sa pagkamakatarungan, sa pagtatapos ng araw, wala ay nagbago dahil sa isang linggo, kapag kami unang nagsimula pag-ipon ng mga programa. Sa katunayan, ang lahat ng mga ito ay nangyayari sa ilalim ng hood, ngunit ngayon ay hindi namin sa isang posisyon kung saan maaari naming aktwal manunudyo bukod ang mga iba't-ibang mga hakbang na ito. At sa katunayan, sa pagtatapos ng araw, hindi pa rin namin sa kaliwa na may mga zero at mga, na ay talagang isang mahusay na segue ngayon sa ibang kakayahan ng C, na Hindi namin nagkaroon sa pagkilos malamang sa petsa, na kilala bilang bitwise operator. Sa ibang salita, kaya sa ngayon, anumang oras na namin Aaksyunan data sa C o mga variable sa C, nagkaroon kami ng mga bagay tulad ng karakter at sa kamay at ins at longs at doble at ang gusto, ngunit lahat ng mga ito ay hindi bababa sa walong bits. Na hindi pa nagawa naming upang manipulahin indibidwal na mga piraso, kahit na ang isang indibidwal na bit, namin alam, maaari kumakatawan sa isang 0 at 1. Ngayon ito ay lumiliko out na sa C, mo ay maaaring makakuha ng access sa mga indibidwal na mga piraso, kung alam mo ang syntax, na kung saan upang makakuha sa kanila. Kaya sabihin tumagal ng isang pagtingin sa bitwise operator. Kaya nakalarawan dito ang ilang mga simbolo na na, uri ng, uri ng, nakita natin dati. Nakakakita ako ng isang ampersand, isang vertical bar, at ilang mga iba pati na rin, at isipin na ampersand ampersand ay isang bagay na nakita natin dati. Ang lohikal AND operator, kung saan mayroon kang dalawa sa kanila nang magkasama, o ang mga lohikal na OR operator, kung saan mo may dalawang vertical bar. Bitwise operator, kung saan ipapakita namin makita gumana sa bits isa-isa, gamitin lamang ang isang solong ampersand, isang single vertical bar, ang simbolo caret ang susunod na dumating, ang maliit na tilde, at pagkatapos ay iniwan bracket kaliwa bracket, o right bracket right bracket. Ang bawat isa sa mga ito ay may iba't-ibang kahulugan. Sa katunayan, sabihin kumuha ng isang hitsura. Sabihin pumunta lumang paaralan ngayon, at gamitin ang isang touch screen mula sa nakalipas na panahon, kilala bilang isang white board. At ito white board ay pagpunta sa-daan sa amin upang ipahayag ang ilang mga medyo simple simbolo, o sa halip ng ilang mga medyo simple formula, na pagkatapos ay maaari naming sa huli pagkilos, upang upang ma-access indibidwal bits loob ng isang programa C. Sa ibang salita, sabihin gawin ito ipaalam. Sabihin unang talk para sa isang sandali tungkol ampersand, kung saan ay ang bitwise AT operator. Sa ibang salita, ito ay isang operator na nagbibigay-daan sa akin upang magkaroon ng isang variable para sa kaliwang kamay kadalasan, at isang variable right-kamay, o isang indibidwal na halaga, na kung kami AT sama ang mga ito, ay nagbibigay sa akin ng isang huling resulta. Kaya kung ano ang ibig sabihin ko? Kung sa isang programa, ikaw ay may isang variable na ang mga tindahan ng isa sa mga halagang ito, o hayaan panatilihin ito simple, at lamang isulat ang mga zero at mga isa-isa, narito kung paano gumagana ang mga ampersand operator. 0 ampersand 0 ay pagpunta sa pantay 0. Ngayon kung bakit ay na? Ito ay halos kapareho sa Boolean expression, na napag-usapan namin kaya sa ngayon. Kung sa tingin mo na matapos ang lahat, ang 0 ay false, 0 ay hindi totoo, hindi totoo at hindi totoo ay, bilang namin tinalakay lohikal, false din. Kaya makuha namin 0 dito rin. Kung ikaw ay kumuha 0 ampersand 1, mahusay na, masyadong, ay magiging 0, sapagkat sa dahilang ito kaliwang expression upang maging totoo o 1, ito ay kailangan upang maging totoo at tunay. Ngunit dito kami ay may mga maling at totoo, o 0 at 1. Muli Ngayon, kung kami ay may 1 ampersand 0, na, masyadong, ay magiging 0, at kung kami ay may 1 ampersand 1, sa wakas ang mayroon kami ng isang 1 bit. Kaya sa ibang salita, hindi namin ginagawa anumang bagay na interesante sa mga operator na ito pa lamang, ito ampersand operator. Ito ay ang bitwise AT operator. Ngunit ang mga ito ay ang mga sangkap sa pamamagitan ng kung saan maaari naming gawin kagiliw-giliw na mga bagay-bagay, tulad ng makikita sa lalong madaling panahon kami ay makita. Ngayon tingnan natin ang lang ang nag-iisang ipaalam vertical bar sa paglipas dito sa kanan. Kung mayroon akong isang 0 bit at ako O ito sa, ang bitwise OR operator, isa pang 0 bit, na ang pagpunta sa bigyan ako 0. Kung ako tumagal ng 0 bit at OR ito sa isang 1 bit, at pagkatapos ay ako pagpunta upang makakuha ng 1. At sa katunayan, para lamang sa kaliwanagan, hayaan mo akong bumalik, At ang aking mga vertical bar ay hindi mali para sa 1 ni. Hayaan akong muling isulat ang lahat ng aking 1 ng kaunti pa malinaw, kaya na namin sa susunod na makita, kung ako may isang 1 OR 0, na ang pagpunta sa maging isang 1, at kung mayroon isang 1 O 1 na ako, masyadong, ay magiging isang 1. Kaya maaari mong makita lohikal na ang OR operator behaves napaka naiiba. Nagbibigay sa akin ito 0 OR 0 ay nagbibigay sa akin 0, ngunit nagbibigay sa bawat iba pang mga kumbinasyon sa akin 1. Kaya hangga't mayroon akong isang 1 sa formula, ang mga resulta ay magiging 1. Sa pamamagitan ng kaibahan sa AND operator, ang ampersand, lamang kung mayroon akong dalawang 1 ni sa equation, ko talagang makakuha ng isang 1 out. Ngayon ay mayroong ilang mga iba pang operator pati na rin. Isa sa mga ito ay isang maliit na mas kasangkot. Kaya hayaan mo akong magpatuloy at burahin ito upang magbakante ng ilang espasyo. At tumagal ng isang pagtingin sa ipaalam caret simbolo, para sa sandali lamang. Ito ay karaniwang isang karakter na maaari mong i-type sa iyong hawak na keyboard Shift at pagkatapos ay isa sa mga numero na nasa ibabaw ng iyong US keyboard. Kaya ito ay ang eksklusibong OR operator, eksklusibong OR. Kaya lang namin nakita ang OR operator. Ito ang eksklusibong OR operator. Ano ang aktwal na mga pagkakaiba? Tingnan lang natin ang mga formula Well ipaalam, at gamitin ito bilang sangkap sa huli. 0 XOR 0. Pupunta ako sa sabihin ay palaging 0. Iyon ang kahulugan ng XOR. 0 XOR 1 ay magiging 1. 1 XOR 0 ay magiging 1, at 1 XOR 1 ay magiging? Maling? O di ba? Hindi ko alam. 0. Ngayon kung ano ang nangyayari dito? Well isipin ang tungkol sa pangalan ng operator. Exclusive OR, sa gayon ay ang mga pangalan, uri ng, nagmumungkahi, ang sagot ay lamang ang pagpunta sa maging isang 1 kung ang input ay eksklusibo, eksklusibo naiiba. Kaya dito ang input ay ang parehong, kaya ang output ay 0. Narito ang mga input ay ang mga parehong, kaya ang output ay 0. Narito ang mga output ay naiiba, ang mga ito ay eksklusibo, at sa gayon ang output ay 1. Kaya ito ay lubos na katulad sa AT, ito ay halos katulad na, o sa halip ito ay lubos na katulad sa OR, ngunit lamang sa isang eksklusibong paraan. Isa na ito ay hindi na isang 1, dahil kami ay may dalawang 1 ni, at hindi eksklusibo, isa lamang sa kanila. Lahat tama. Paano naman ang iba? Well ang tilde naman ay talagang maganda at simpleng, thankfully. At ito ay isang unary operator, na nangangahulugan ito ay inilapat lamang sa isang input, isa operand, kaya na magsalita. Hindi sa isang kaliwa at isang kanan. Sa ibang salita, kung ikaw ay kumuha ng tilde 0, ang sagot ay ang kabaligtaran. At kung ikaw ay kumuha ng tilde ng 1, ang Ang sagot doon ay ang kabaligtaran. Kaya ang tilde operator ay isang paraan ng negating ng kaunti, o flipping ng kaunti mula sa 0 hanggang 1, o 1 sa 0. At na nag-iiwan sa amin sa wakas may final operator lamang ng dalawa, ang tinatawag na kaliwang shift, at ang tinatawag na karapatan shift operator. Tingnan natin ang isang pagtingin sa kung paano ang mga trabaho. Ang kaliwa shift operator, nakasulat may dalawang bracket anggulo mo na, nagpapatakbo ang mga sumusunod. Kung ang aking input, o ang aking operand, sa kaliwa shift operator ay lubos na lamang ng isang 1. At pagkatapos ay sasabihin ko sa mga computer upang kaliwa shift na 1, sabihin na pitong lugar, ang resulta ay parang ako kumuha na 1, at ilipat ito pitong mga lugar sa paglipas ng sa kaliwa, at sa pamamagitan ng default, kami ay pagpunta sa ipalagay na ang puwang sa kanan ay magiging may palaman sa zero. Sa ibang salita, 1 kaliwa shift 7 ay pagpunta upang bigyan ako na ang 1, sinusundan ng 1, 2, 3, 4, 5, 6, 7 mga zero. Kaya sa isang paraan, ito ay nagpapahintulot sa inyo na kumuha ng isang maliit na bilang tulad ng 1, at malinaw na gawin itong mas magkano, magkano ang mas malaki sa ganitong paraan, ngunit ang tunay na kami ay pagpunta upang makita mas matalino approach para dito sa halip, pati na rin, Lahat tama. Iyan na ang lahat para sa tatlong linggo. Kami ay makita mo ang susunod na oras. Ito ay CS50. [MUSIC nagpe-play] Tagapagsalita 1: Siya ay sa snack bar ng pagkain ng isang mainit na gawing kalokohan sorbetes. Siya ay ang lahat ng ito sa kanyang mukha. Siya ay may suot na tsokolate tulad ng isang balbas Tagapagsalita 2: Ano ang ginagawa mo? Tagapagsalita 3: Hmmm? Ano? Tagapagsalita 2: Ang ibig mo double lumangoy lamang? Ikaw double dipped ang chip. Tagapagsalita 3: Mawalang galang na. Tagapagsalita 2: nabasa mo ang chip, ikaw ay kinuha ng isang kagat, at ikaw nabasa muli. Tagapagsalita 3: Tagapagsalita 2: Kaya na tulad ng paglalagay ng ang iyong buong bibig karapatan sa lumangoy. Susunod na panahon na kayo ay kumuha ng isang maliit na tilad, isawsaw lamang ito nang isang beses, at tapusin ito. Tagapagsalita 3: Alam mo kung ano, Dan? Isawsaw mo ang paraan na gusto mo upang lumangoy. Kukunin ko lumangoy ang paraan na gusto ko na isawsaw.