>> [Nagpe-play ng musika]
David MALAN: Lahat ng karapatan.
Ang lahat ng mga karapatan, maligayang pagdating pabalik.
Kaya ito ay Linggo 4, sa simula niyaon, na.
At makikita mo na isipin ang nakaraang linggo, inilalagay namin ang Code para sa isang tabi lamang ng kaunting
at nagsimula kaming nagsasalita ng kaunti pa mataas na antas, tungkol sa mga bagay tulad ng
paghahanap at pag-uuri, na bagaman medyo simpleng ideya, ay
kinatawan ng isang klase ng mga problema magsisimula kang upang malutas lalo
bilang ka magsimula-iisip tungkol sa huling proyekto at kagiliw-giliw na mga solusyon sa iyo
baka magkaroon sa real-world problema.
Ngayon bubble-uri ay isa sa mga pinakamadaling tulad ng mga algorithm, at ito
nagtrabaho sa pamamagitan ng pagkakaroon ng mga maliliit na mga numero sa isang listahan o sa isang array uri ng
bubble kanilang mga paraan up sa tuktok, at ang malaki mga numero ng ilipat ang kanilang mga paraan pababa sa
sa dulo ng listahan na iyon.
>> At isipin ang na kami maaaring maisalarawan bubble sort ng kaunti
isang bagay na katulad nito.
Kaya ipaalam sa akin sige at i-click ang Simulan.
Ko na preselected bubble sort.
At kung isipin ang mo na ang taller asul mga linya ay kumakatawan sa malaking numero, maliit
asul na linya ay kumakatawan maliit na mga numero, bilang pumunta namin sa pamamagitan ng ito muli at muli at
muli, paghahambing ng dalawang bar sa tabi ng bawat iba sa pula, kami ay pagpunta sa swap ang
pinakamalaki at ang pinakamaliit na kung ang mga ito ay out ng order.
>> Kaya ito ay pumunta sa at pumunta sa at pumunta on, at makikita mo na ang mas malaking
mga elemento ay paggawa ng kanilang mga paraan upang ang kanan, at ang mga mas maliit na mga elemento ay
paggawa ng kanilang mga paraan sa kaliwa.
Ngunit sinimulan namin upang tumyak ng dami ang kahusayan, ang
kalidad ng mga ito algorithm.
At sinabi namin na sa pinakamalala kaso, algorithm na ito kinuha
halos kung gaano karaming mga hakbang na ito?
>> Kaya n squared.
At kung ano ang n?
>> Madla: Bilang ng mga elemento.
>> David MALAN: Kaya n ay ang numero ng mga elemento.
At kaya namin gawin ito madalas.
Anumang oras na gusto naming makipag-usap tungkol sa laki sa isang problema o ang laki ng isang
input, o ang dami ng oras na aabutin upang makabuo ng output, bibigyan namin lamang
heneralisado anumang input ay ang bilang n.
Kaya bumalik sa Linggo 0, bilang ng mga pahina sa aklat ng telepono ay n.
Ang bilang ng mga mag-aaral sa kuwarto ay n.
Kaya dito, masyadong, namin sinusubaybayan na pattern.
>> Ngayon n squared ay hindi partikular na mabilis, kaya sinubukan naming gawin mas mahusay.
At kaya kami ay tumingin sa isang pares ng mga iba pang mga algorithm, bukod sa kung saan
mga seleksyon-uri.
Kaya seleksyon-uri noon ay medyo naiiba.
Ito ay halos mas simple, maglakas-loob ko sabihin, kung saan ako nagsimula sa simula ng
listahan ng aming mga boluntaryo at ko lang muli at muli at muli nagpunta sa pamamagitan ng
ang listahan, plucking out sa pinakamaliliit elemento sa isang pagkakataon at paglalagay sa kanya o
kanya sa simula ng listahan.
>> Ngunit ito, masyadong, sa sandaling nagsimula kaming mag-isip sa pamamagitan ng matematika at mas malalaking
larawan, naisip tungkol sa kung gaano karaming beses Ako ay pagpunta sa likod at sa una at likod
at balik, sinabi namin sa pinakamasama kaso, pagpili ng uri, masyadong, ay kung ano?
n nakalapat.
Ngayon, sa tunay na mundo, maaari itong talagang maging marginally mas mabilis.
Dahil muli, hindi ko na kailangang panatilihing backtracking isang beses ko ay pinagsunod-sunod ang
pinakamaliliit na elemento.
Ngunit kung sa tingin namin tungkol sa napakalaking n, at kung iyong pag-uuri ng gawin ang matematika bilang
Ginawa ko sa board, na may n squared minus isang bagay, lahat ng iba pa
maliban sa n squared, sa sandaling n ay makakakuha ng talagang malaki, ay hindi
talagang mahalaga bilang magkano.
Kaya bilang mga siyentipiko computer, namin-uri-uriin ng pumikit ang mga mata sa mas maliit
salik at focus lamang sa mga salik sa isang expression na pagpunta sa gumawa
ang pinakamalaking pagkakaiba.
>> Well, bilang wakas, kami ay tumingin pagpapasok sa pag-uuri.
At ito ay katulad sa espiritu, ngunit sa halip na pumunta sa pamamagitan ng iteratively at
piliin ang pinakamaliit na ang isang elemento sa isang oras, ako sa halip kinuha ang kamay na ako
ay Aaksyunan, at ako nagpasya, lahat karapatan, pag-aari mo dito.
Pagkatapos ko inilipat sa susunod na elemento at nagpasya na siya o
aari niya dito.
At pagkatapos ay ako inilipat sa at sa.
At maaari kong, kasama ang paraan, shift ang mga guys upang
gumawa ng room para sa mga ito.
Kaya na noon ay isang uri ng mga sakit sa baligtad ng pagpili ng pag-uuri na namin
tinatawag na pagpapasok sort.
>> Kaya ang mga paksa na mangyari sa tunay na mundo.
Ilang taon na ang nakalipas, kapag ang isang tiyak na senador ay tumatakbo para sa presidente,
Eric Schmidt, sa panahon na ang CEO ng Google, talagang nagkaroon ng pagkakataon
sa pakikipanayam sa kanya.
At naisip naming ibahagi ito sa YouTube sipit para sa iyo dito, kung maaari naming i-up
ang lakas ng tunog.
>> [Video playback]
>> -Ngayon, Senator, nandito ka sa Google, at gusto kong isipin na ang pagkapangulo
bilang isang trabaho interbiyu.
>> [Tawa]
>> -Ngayon ay mahirap na makuha isang trabaho bilang presidente.
At ka ng pagpunta sa pamamagitan ng ang mga kahirapan ngayon.
Ito ay din mahirap upang makakuha ng trabaho sa Google.
Mayroon kaming mga tanong at hinihiling namin ang aming mga kandidato tanong.
At ang isang ito ay mula sa Larry Schwimmer.
>> [Tawa]
-Mo guys sa tingin ko kidding?
Ito ay karapatan dito.
Ano ang pinaka-mahusay na paraan upang -uri-uriin ng isang milyon dalawang-bit integer?
>> [Tawa]
>> -Well, uh -
>> -I'm paumanhin.
Siguro dapat namin -
>> -Hindi, hindi, hindi, hindi, hindi.
>> -Iyan ay hindi isang -
OK.
>> -Sa tingin ko ang bubble sort ng ginagawa maging sa maling paraan upang pumunta.
>> [Tawa]
>> [Pagpalakpak AT palakpakan]
>> -Halika sa, na sinabi sa kanya ito?
OK.
>> [END-playback ng video]
>> David MALAN: So doon mayroon kang ito.
Kaya sinimulan namin upang tumyak ng dami ang mga tumatakbo beses, sa gayon na magsalita, may isang bagay
tinatawag asymptotic notation, na kung saan ay nagre-refer lamang sa aming mga uri ng pag-on
isang bulag mata sa mga mas maliit na mga kadahilanan at lamang ng pagtingin sa mga tumatakbo ang oras,
ang pagganap ng mga algorithm, bilang n nakakakuha talagang malaki sa paglipas ng panahon.
At kaya ipinakilala namin malaki O. At malaki O kinakatawan ng isang bagay na naisip namin na
ng bilang isang pang-itaas bound.
At talagang, Barry, maaari naming babaan kaysa sa mic Medyo?
>> Naisip namin na ito ay isang upper bound.
Kaya malaki O ng n squared ay nangangahulugan na sa ang pinakamasamang sitwasyon, isang bagay tulad ng
pagpili sort gusto tumagal n squared hakbang.
O isang bagay tulad ng pagpasok ng pag-uuri gagawin n squared hakbang.
Ngayon para sa isang bagay tulad ng pagpapasok uri, ano ay ang pinakamasama kaso?
Given isang array, ano ang pinakamasama posibleng sitwasyon na maaari mong makita
iyong sarili nahaharap na may?
>> Ito ay ganap na paurong, tama?
Dahil kung ito ay ganap na paurong, mayroon ka na gawin ang isang buong maraming trabaho.
Dahil kung ikaw ay ganap na paurong, ka pagpunta upang mahanap ang
pinakamalaking elemento dito, kahit na ito ay kabilang pababa doon.
Kaya ka pagpunta sa sabihin, ang lahat ng karapatan, sa sandaling ito sa oras, nabibilang ka dito,
kaya mong iwanan ito nang nag-iisa.
>> Pagkatapos ay natanto, oh, sumpain, mayroon akong upang ilipat ito bahagyang mas maliit na elemento upang
sa kaliwa ng iyo.
Pagkatapos ay kailangan kong gawin na muli at muli at muli.
At kung ako lumakad na pabalik-balik, mo Gusto-uri-uriin ng pakiramdam ang pagganap ng
algorithm na, dahil patuloy Ako shuffling ang iba pababa sa
array upang gumawa ng room para sa mga ito.
Kaya iyon ang pinakamasama kaso.
>> Sa pamamagitan ng kaibahan -
at ito ay isang cliffhanger huling beses na -
sinabi namin na ang pagpapasok ng pag-uuri ng wakas ng ano?
Ano ang pinakamahusay na-case na tumatakbo oras ng pagpasok ng pag-uuri?
Kaya talaga ito n.
Iyon ay ang blangko na iniwanan namin sa board huling oras.
>> At ito ay katapusan ng n dahil bakit?
Well, sa pinakamahusay na kaso, kung ano ang pagpapasok ng pag-uuri ng pagpunta sa ma-ipinasa?
Well, isang listahan na ganap na pinagsunod-sunod pa, minimal na trabaho upang gawin.
Ngunit kung ano ang tungkol sa malinis at maayos ang pagpapasok ng pag-uuri ay na dahil ito magsimula dito at
Nagpasya, oh, ikaw ang numero isa, nabibilang ka dito.
Oh, kung ano ang isang magandang kapalaran.
>> Kayo ang dalawang numero.
Bahagi ka rin dito.
Numero ng tatlong, kahit na mas mahusay, nabibilang ka dito.
Sa sandali na ito ay nakakakuha sa dulo ng pseudocode listahan, sa bawat insertion sort ni
na namin lumakad sa pamamagitan ng pasalita huling oras, tapos na ito.
Ngunit seleksyon uri, sa pamamagitan ng kaibahan, iningatan ginagawa kung ano?
>> Iningatan ng pagdaan sa listahan muli at muli at muli.
Dahil ang mga key pananaw nagkaroon lamang sa oras na iyong ay tumingin sa lahat ng mga paraan upang ang
dulo ng listahan maaari kang maging tiyak na ang mga elemento na iyong pinili ay
sa katunayan ang kasalukuyang pinakamaliit na elemento.
Kaya ang mga iba't ibang mga sakit sa mga modelo ng pagtatapos up mapagpakumbaba ilang mga napaka-real-world
mga pagkakaiba para sa amin, pati na rin ang mga manilay-nilay asymptotic pagkakaiba.
>> Kaya lang sa paglalagom, pagkatapos, malaki O ng n squared, nakakita kami ng ilang tulad
algorithm kaya sa ngayon.
Big O ng n?
Ano ang isang algorithm na maaari ay sinabi na maging malaki O ng n?
Sa pinakamasama kaso, ito ay tumatagal ng isang linear na bilang ng mga hakbang na ito.
>> OK, linear paghahanap.
At sa pinakamasama kaso, kung saan ay ang element na hinahanap mo kapag
paglalapat ng linear paghahanap?
>> OK, sa pinakamasama kaso, ito ay hindi kahit doon.
O kaya sa pangalawang pinakamasama kaso, ito ay ang lahat ng mga paraan sa dulo, na kung saan ay
plus-o-minus isang hakbang pagkakaiba.
Kaya sa katapusan ng araw, maaari naming sabihin ito ay linear.
Big O ng n magiging linear paghahanap, dahil sa ang pinakamasama kaso, ang
elemento ay hindi kahit doon o ito ang lahat ng mga paraan sa dulo.
>> Well, malaki O ng log ng n.
Hindi namin makipag-usap sa mahusay na detalye tungkol sa ito, ngunit nasaksihan namin ito bago.
Ano ang tumatakbo sa tinaguriang logarithmic oras, sa pinakamasama kaso?
>> Oo, kaya binary paghahanap.
At binary paghahanap sa pinakamasama kaso Maaaring magkaroon ang elemento sa isang lugar sa
sa gitna, o sa isang lugar sa loob ng array.
Ngunit mo lamang makita ito sa sandaling hatiin ang listahan sa kalahati, sa
kalahati, sa kalahati, sa kalahati.
At pagkatapos ay voila, ito ay doon.
O muli, pinakamasama kaso, ito ay hindi kahit doon.
Ngunit hindi mo alam na ito ay hindi doon hanggang sa ikaw ay isang uri ng maabot na ang huling
ibabang pinaka elemento sa pamamagitan ng paghati at paghati at paghati.
>> Big O ng 1.
Kaya maaari naming malaki ng O 2, malaki O ng 3.
Anumang oras na gusto mo lamang ng isang hindi nagbabagong numero, namin lamang-uri-uriin ng lang gawing simple
na malaki ang bilang ng mga O 1.
Kahit na kung realistically, ito ay tumatagal ng 2 o kahit na 100 mga hakbang, kung ito ay isang
pare-pareho ang bilang ng mga hakbang, kami lang sabihin malaki O ng 1.
Ano ang isang algorithm na sa malaki O ng 1?
>> Madla: Paghahanap ng ang haba ng isang variable.
>> David MALAN: Hinahanap ang haba ng isang variable?
>> Madla: Hindi, ang haba kung ito ay pinagsunod-sunod.
>> David MALAN: Mahusay.
OK, kaya sa paghahanap ng haba ng isang bagay kung ang haba ng na may isang bagay, tulad ng
isang array, ay naka-imbak sa ilang mga variable.
Dahil maaari mo lamang basahin ang mga variable, o i-print ang variable, o
lamang sa pangkalahatan access na variable.
At voila, na tumatagal ng pare-pareho ang panahon.
>> Sa pamamagitan ng kaibahan, sa tingin bumalik sa simula.
Isipin pabalik sa unang linggo ng C, pagtawag lamang printf at pag-print
isang bagay sa screen ay arguably pare-pareho ang panahon, dahil ito lamang tumatagal
ilang bilang ng mga siklo ng CPU upang ipakita ang na teksto sa screen.
O kaya maghintay - ang ibig ito?
Paano pa ang maaari naming gawing modelo ang pagganap ng printf?
Gusto isang tao na gusto upang hindi sumang-ayon, na marahil ito ay hindi talaga pare-pareho ang oras?
Sa anong kahulugan ay maaaring printf Tumatakbo oras, talagang pag-print ng isang string sa
ang screen, maging isang bagay bukod sa pare-pareho.
>> Madla: [hindi marinig].
>> David MALAN: Oo.
Kaya ito ay depende sa aming pananaw.
Kung namin ang aktwal na sa tingin ng mga input upang printf bilang pagiging string, at
samakatuwid namin sinusukat ang laki ng mga na input sa pamamagitan ng haba nito - kaya natin tawagan
na haba n pati na rin -
arguably, printf mismo ay malaki O ng n dahil ito ay pagpunta sa magdadala sa iyo n hakbang
upang i-print out sa bawat isa sa mga n character, pinaka-malamang.
Hindi bababa sa lawak na ipinapalagay namin na siguro gumagamit ito ng para sa loop
sa ilalim ng hood.
>> Pero gusto naming magkaroon upang tumingin sa na code upang maunawaan itong mas mahusay.
At sa katunayan, sa sandaling simulan guys pag-aaral ng iyong sariling mga algorithm, makikita mo
Literal na gawin lamang na.
Pagsunud-sunurin ng eyeball ang iyong code at sa tingin tungkol - lahat ng mga karapatan, mayroon akong ito loop
dito o ba akong magkaroon ng isang nested loop dito, na pagpunta sa gawin ang mga bagay n n beses,
at maaari mong uri-uriin ang dahilan ng iyong paraan sa pamamagitan ng code, kahit na ito ay
pseudocode at hindi aktwal na code.
>> Kaya kung ano ang tungkol sa katapusan ng n squared?
Ano ang isang algorithm na sa ang pinakamahusay na kaso, kinuha pa rin n squared hakbang?
Oo?
>> Madla: [hindi marinig].
>> David MALAN: Kaya seleksyon-uri.
Dahil sa problema na talagang binawasan upang ang katotohanan na muli, hindi ko alam
Nahanap ko ang kasalukuyang pinakamaliit hanggang Ko na naka-check ang lahat ng mga elemento darn.
Kaya wakas ng, sabihin nating, n, namin lamang ay dumating up sa isa.
Insertion sort.
Kung listahan ang mangyayari na pinagsunod-sunod pa, sa ang pinakamahusay na kaso namin na lang ay
upang gumawa ng isang pass sa pamamagitan nito, at sa puntong sigurado kami.
At pagkatapos na ma-sinabi upang maging linear, para sigurado.
>> Paano ang tungkol sa wakas ng 1?
Ano, sa ang pinakamahusay na kaso, maaaring tumagal isang pare-pareho ang bilang ng mga hakbang na ito?
Kaya linear paghahanap, kung mo lamang makakuha ng masuwerteng at ang sangkap na hinahanap mo
ang tama sa simula ng listahan, kung na kung saan ka pagsisimula ng iyong
linear traversal ng listahang iyon.
>> At ito ay totoo ng isang bilang ng mga bagay.
Halimbawa, kahit na binary paghahanap ay wakas na 1.
Dahil kung ano ang kung makakuha ka talaga darn mapalad at may bakas-magdutdot sa gitna ng
ang iyong array ay ang bilang ang iyong hinahanap para sa?
Kaya maaari kang makakuha ng masuwerteng doon, pati na rin.
>> Ito ang isa, bilang wakas, wakas ng n log n.
Kaya n log n, ginawa namin hindi talaga makipag-usap tungkol sa pa, ngunit -
>> Madla: Pagsamahin-uri?
>> David MALAN: Pagsamahin ang pag-uuri.
Iyon ay ang cliffhanger ng huling oras, kung saan kami ipinanukala, at kami ay nagpakita ng
biswal, na may mga algorithm.
At pagsamahin ang uri ng isa lang gaya algorithm na ay mas mabilis sa panimula
kaysa sa ilang ng iba pang mga guys.
Sa katunayan, pagsamahin maikling ay hindi lamang sa pinakamahusay na kaso n log n, sa pinakamalala
kaso n log n.
At kapag mayroon kang ito ng pagkakaisa wakas at malaki O pagiging ang parehong bagay?
Maaari naming ilarawan ang aktwal na bilang kung ano ang tinatawag theta, bagaman ito ay isang
maliit na mas mababa karaniwang.
Ngunit iyon lamang ay nangangahulugan na ang dalawang hanggahan, sa kasong ito, ay pareho.
>> Kaya pagsamahin ang uri, kung ano ang ibig ito talaga pasingawan sa para sa amin?
Well, isipin ang mga pagganyak.
Hayaan akong makuha ang isa pang animation na hindi kami tumingin sa huling beses.
Ang isa, parehong ideya, ngunit ito ay isang maliit na mas malaki.
At ako pagpunta sa sige at ituro una - kami ay may pagpapasok-uri sa
sa tuktok na kaliwang, pagkatapos ay pagpili ng uri, bubble sort, isang pares ng mga iba pang mga uri -
shell at mabilis - na hindi namin na-uusapang tungkol sa, at kimpal at pagsamahin ang pag-uuri.
>> Kaya hindi bababa sa subukan upang ituon ang iyong mga mata sa ang tatlong nangungunang sa kaliwa at pagkatapos ay
merge sort kapag i-click ko ang berdeng arrow.
Ngunit Ipapaalam ko sa lahat ng mga ito tatakbo, para lamang bigyan ka ng isang pakiramdam ng pagkakaroon ng mga pagkakaiba-iba ng
algorithm na umiiral sa mundo.
Pupunta ako upang ipaalam ito run para lamang ng ilang segundo.
At kung mong ituon ang iyong mga mata - pumili ng isang algorithm, tumuon sa mga ito para lamang sa isang
segundo - magkakaroon ka magsimula upang makita ang pattern na ito pagpapatupad.
>> Pagsamahin ang mga pag-uuri, notice, tapos na.
Kimpal sort, quick sort, shell -
kaya mukhang ipinakilala namin ang tatlong pinakamasama algorithm noong nakaraang linggo.
Ngunit iyon lamang ang mahusay na kami dito ngayon sa tumingin sa pagsasama-uri, na kung saan ay isa sa mga
mas madali ang mga bago ay ang pagtingin sa, kahit na bagaman marahil ito ay yumuko iyong isip
lamang ng isang maliit na bit.
Dito maaari naming makita lamang kung magkano pagpili sort sucks.
>> Ngunit sa gilid tingnan ito, talaga madaling ipatupad.
At marahil para sa P Set 3, na isa sa mga algorithm na pinili mo upang ipatupad
para sa standard edition.
Ganap na ganap fine, perpektong tama.
>> Ngunit muli, bilang n nakukuha ng malaki, kung ikaw pumili upang ipatupad ng mas mabilis na algorithm
i-merge sort, bentahe sa mga mas malaki at mas malaki input, ang iyong code lamang ang
pagpunta upang tumakbo nang mas mabilis.
Ang iyong website ay pagpunta upang gumana nang mas mahusay.
Ang iyong mga gumagamit ay pumunta sa upang maging mas masaya.
At kaya mayroong mga effect ng aktwal na nagbibigay sa
sa amin ng ilang mas malalim na inisip.
>> Kaya sabihin tumingin sa kung ano sumanib -uri ay talagang lahat tungkol sa.
Ang mga cool na bagay ay na-merge sort lamang ito.
Ito ay, muli, kung ano ang namin ang tinatawag na pseudocode, pseudocode pagkatao
Ingles-tulad ng syntax.
At ang pagiging simple ay uri ng mga kamangha-manghang.
>> Kaya sa pag-input ng mga elemento n - sa gayon ay Nangangahulugan lamang, narito ang isang array.
Ito ay nakuha ko n bagay sa loob nito.
Iyon lang namin sinasabi na doon.
>> Kung n Mababa sa 2, bumalik.
Kaya ito lamang ang walang kuwenta kaso.
Kung n Mababa sa 2, pagkatapos ay malinaw naman ito 1 o 0, kung saan ang mga bagay
ay pinagsunod-sunod o nonexistent, kaya lang bumalik.
Wala na gawin.
Kaya na ang isang simpleng kaso sa pumitas off.
>> Iba Pa, mayroon kaming tatlong hakbang.
Pagbukud-bukurin sa kaliwang kalahati ng mga elemento, pag-uuri ang karapatan kalahati ng mga elemento,
at pagkatapos ay pagsamahin ang pinagsunod-sunod halves.
Ano ang mga kagiliw-giliw dito ay na Ako uri ng punting, tama?
Mayroong uri ng isang pabilog na kahulugan upang ito algorithm.
Sa anong kahulugan ay ang algorithm ni Kahulugan ng pabilog?
>> Madla: [hindi marinig].
>> David MALAN: Oo, ang aking mga pag-uuri algorithm, dalawa sa kanyang mga hakbang ay ang "pag-uuri
isang bagay. "At kaya na begs ang pinag-uusapan, well, kung ano ako pagpunta sa gamitin
upang pagbukud-bukurin ang kaliwang kalahati at ang kanang kalahati?
At ang kagandahan dito ay na kahit na muli, ito ang isip-baluktot
bahagi potensyal na, maaari mong gamitin ang parehong algorithm upang pagbukud-bukurin ang kaliwang kalahati.
>> Ngunit maghintay ng isang minuto.
Kapag naka-Sinabi upang ayusin ang kaliwa kalahati, kung ano ay ang dalawang
hakbang ng pagpunta sa maging susunod?
Kami uri-uriin ang kaliwang kalahati ng kaliwa kalahati at ang karapatan
kalahati ng kaliwang kalahati.
Sumpain, paano ko uri-uriin ang mga dalawang halves, o quarters, ngayon?
>> Ngunit iyon lamang ang OK.
Mayroon kaming isang pag-uuri algorithm dito.
At kahit na maaari kang mag-alala sa unang ito ay uri ng isang walang-katapusang
loop, ito ay isang cycle na hindi kailanman pagpunta sa tapusin - ito ay pagpunta sa
tapusin beses kung ano ang mangyayari?
Sa sandaling n ay mas mababa kaysa 2.
Aling kalaunan ay pagpunta sa mangyari, dahil kung patuloy mong paghati at
paghati sa paghati mga halves, tiyak malaon ka ng pagpunta sa magtapos
up na may lamang 1 o 0 na mga elemento.
Sa aling mga punto, ito algorithm sabi tapos ka na.
>> Kaya ang tunay na magic sa ito algorithm ay anyong sa
na huling hakbang, pinagsasama.
Iyon simpleng ideya lamang pinagsasama ang dalawang mga bagay, na kung ano ang pagpunta sa huli
upang payagan sa amin upang ayusin ang isang array ng, sabihin nating, walong elemento.
Kaya Mayroon akong walong higit pang mga bola ng stress up dito, walong piraso ng papel, at isa
Google Salamin -
na nakukuha ko upang panatilihing.
>> [Tawa]
>> David MALAN: Kung kami maaaring tumagal ng walong boluntaryo, at sabihin makita kung ang aming makakaya
maglaro ito out, nang sa gayon.
Wow, OK.
Computer science ay nakakakuha ng masaya.
Ayos lang.
Kaya kung paano tungkol sa iyo tatlo, pinakamalaking kamay up doon.
Apat sa likod.
At kung paano tungkol sa gagawin namin sa iyo tatlong sa hilerang ito?
At apat na nasa harap.
Kaya mo walo, dumating sa up.
>> [Tawa]
>> David MALAN: Ako talaga Hindi sigurado kung ano ito ay.
Ito ba ay ang bola ng stress?
Ang desk lamp?
Ang materyal?
Ang internet?
>> OK.
Kaya dumating sa up.
Sino ang nais -
panatilihing darating up.
Tayo'y makita.
At ito Binibigyan ka ng lokasyon -
ikaw ay nasa isang lokasyon.
Uh-oh, maghintay ng isang minuto.
1, 2, 3, 4, 5, 6, 7 - oh, mabuti.
Ang lahat ng mga karapatan, kami ay mabuti.
Ang lahat ng mga karapatan, kaya lahat ng tao ay may isang upuan, ngunit hindi sa Google Glass.
Hayaan akong i-queue ang mga up.
Ano ang inyong pangalan?
>> Michelle: Michelle.
>> David MALAN: Michelle?
Ang lahat ng mga karapatan, nakarating ka na sa hitsura ang geek, kung iyon ang OK.
Well, gawin ko masyadong, ipagpalagay ko, para lamang ng ilang sandali.
Ang lahat ng mga karapatan, standby.
Kami ay sinusubukan upang makabuo ng isang gamitin ang kaso para sa Google Glass, at kami
naisip magiging masaya na lang gawin ito kapag ang mga tao onstage.
Itatala namin ang mundo mula sa kanilang mga pananaw.
Ayos lang.
Hindi marahil kung ano ang inilaan ng Google.
Ang lahat ng mga karapatan, kung hindi tututol kayo suot ito para sa susunod na nakahihiya minuto,
na magiging kahanga-hanga.
>> Ang lahat ng mga karapatan, kaya't mayroon kaming dito ng isang hanay ng mga mga sangkap, at na array, bilang bawat ang
piraso ng papel sa mga tao ' mga kamay, ay kasalukuyang unsorted.
>> Michelle: Oh, syanga kakaiba.
>> David MALAN: Ito ay medyo magkano ang random.
At sa loob lamang ng isang sandali, kami ay pagpunta sa subukan ipatupad ang pagsamahin-uri-sama
at makita kung saan na key pananaw ay.
At ang kahanga-hangang gawa dito na may sumanib-uri ay isang bagay na hindi pa namin ipinapalagay pa.
Kami talagang kailangan ang ilang mga dagdag na espasyo.
Kaya kung ano ang nangyayari upang maging partikular na kagiliw-giliw na tungkol sa ito ay na ang mga
guys ay pagpunta sa ilipat sa paligid ng kaunti bit, dahil ako pagpunta sa ipagpalagay na ang
mayroong isang dagdag na hanay ng mga espasyo, sabihin, karapatan sa likod ng mga ito.
>> Kaya kung ang mga ito ay sa likod ng kanilang mga upuan, iyon ang pangalawang array.
Kung sila ay nakaupo dito, na ang pangunahing array.
Ngunit ito ay isang mapagkukunan na mayroon kami Hindi magagamit sa ngayon kaya may bubble
uri, na may pagpili-uri, may pagpapasok ng pag-uuri.
Isipin ang nakaraang linggo, lahat ng tao lamang uri ng shuffled sa lugar.
Hindi nila gamitin ang anumang karagdagang memorya.
Ginawa namin room para sa mga tao sa pamamagitan ng paglipat ng mga tao sa paligid.
>> Kaya ito ay isang mahalagang pananaw, masyadong.
Mayroong ito kalakalan-off, sa pangkalahatan sa computer science, ng mga mapagkukunan.
Kung nais mong pabilisin ang isang bagay tulad ng oras, ikaw ay pagpunta sa
kailangang magbayad ng isang presyo.
At ang isa sa mga presyo ay napakadalas espasyo, ang halaga ng memorya o hard
puwang sa disk na ginagamit mo.
O kaya naman, lantaran, ang halaga programmer ng oras.
Gaano karaming oras na aabutin mo, ang tao, upang aktwal na ipatupad ang ilang higit pang mga
kumplikadong mga algorithm.
Ngunit para sa ngayon, ang kalakalan-off ay oras at espasyo.
>> Kaya't kung ikaw guys ay maaaring hawakan lamang up ang iyong mga numero upang maaari naming makita na ikaw ay
sa katunayan na tumutugma sa 4, 2, 6, 1, 3, 7, 8.
Magaling.
Kaya ako ng pagpunta sa subukan upang mamigay bagay, kung maaari guys lamang
sundin ang aking mga nangunguna dito.
>> Kaya ako ng pagpunta sa ipatupad, una, ang unang hakbang ng pseudocode, na siyang
sa input ng n elemento, kung n ay Mababa sa 2, pagkatapos ay bumalik.
Malinaw, na ang hindi Ilapat, kaya kami umusad.
Kaya-uri-uriin ang kaliwang kalahati ng mga elemento.
Kaya ito ay nangangahulugan na pupuntahan ko ang aking pokus pansin para sa sandali lamang sa mga
apat na guys dito.
Ang lahat ng mga karapatan, ano ang gagawin ko susunod na gagawin?
>> Madla: Pagbukud-bukurin sa kaliwa kalahati.
>> David MALAN: Kaya ngayon mayroon akong upang pagsunud-sunurin sa kaliwang kalahati ng mga guys.
Dahil muli, ipagpalagay na ang iyong sarili layunin ay upang ayusin ang kaliwang kalahati.
Paano mo gawin iyon?
Sundin lamang ang mga tagubilin, kahit kahit na ginagawa namin itong muli.
Kaya-uri-uriin ang kaliwang kalahati.
Ngayon ako ng pagbubukod-bukod ng mga dalawang guys.
Ano ay susunod?
>> Madla: Pagbukud-bukurin sa kaliwa kalahati.
>> David MALAN: Pagbukud-bukurin sa kaliwa kalahati.
Kaya ngayon ang mga ito, ito upuan dito, ay isang listahan ng sukat 1.
At kung ano ang iyong pangalan muli?
>> Uri ng bulaklak Princess: Princess Daisy.
>> David MALAN: Princess Daisy ay dito.
At kaya na siya ay pinagsunod-sunod, dahil listahan ay ang laki ng 1.
Ano ang gagawin ko susunod na gagawin?
OK, bumalik, dahil listahan na ng 1 laki, na kung saan ay mas mababa kaysa 2.
Pagkatapos ay kung ano ang susunod na hakbang?
At ngayon ikaw ay may sa uri ng pag-urong sa iyong isip.
>> Pagbukud-bukurin ang karapatan kalahati, na kung saan ay -
ano ang pangalan mo?
>> Linda: Linda.
>> David MALAN: Linda.
At kaya kung ano ang gagawin namin ngayon na kami ay may isang listahan ng mga laki 1?
>> Madla: Return.
>> David MALAN: ingat.
Ibalik namin ang una, at ngayon ang ikatlong hakbang - at kung ako uri ng ilarawan ito sa pamamagitan ng
embracing ang dalawang upuan ngayon, ngayon ako mayroon upang pagsamahin ang dalawang mga elemento.
Kaya ngayon sa kasamaang-palad, ang mga elemento ay sira.
Ngunit iyon kung saan ang proseso ng pagbubuklod nagsisimula upang makakuha ng nakahihimok.
>> Kaya't kung ikaw guys maaaring tumayo para lang isang saglit, pupuntahan ko kailangan mo, sa isang
sandali, sa hakbang sa likod ng iyong upuan.
At kung Linda, dahil 2 ay mas maliit sa 4, bakit hindi gawin
dumating ka sa paligid muna?
Manatili doon.
Kaya Linda, dumating ka sa paligid muna.
>> Ngayon sa katotohanan kung ito lamang ay isang array kami maaaring lamang ilipat ang kanyang sa real time
mula sa upuan sa lugar na ito.
Kaya isipin na tumagal ng ilang mga pare-pareho bilang ng mga hakbang 1.
At ngayon -
ngunit kailangan naming ilagay mo sa ang unang lokasyon dito.
>> At ngayon kung maaari mong dumating sa paligid, pati na rin, kami ay pagpunta sa
maging sa dalawang lokasyon.
At kahit na ito nararamdaman tulad ng ito ay tumatagal ang, ano ang maganda ngayon ay
na sa kaliwang kalahati ng kaliwa kalahati na ngayon ang pinagsunod-sunod.
Kaya kung ano ang susunod na hakbang, kung namin ngayon rewind pa sa kuwentong ito?
>> Madla: Mag-right kalahati.
>> David MALAN: Pagsunud-sunurin ang karapatan kalahati.
Kaya mo guys na kailangang gawin ito, pati na rin.
Kaya kung maaari mong tumayo para sandali lamang?
At kung ano ang iyong pangalan?
>> Jess: Jess.
>> David MALAN: Jess.
OK, kaya Jess na ngayon ang sa kaliwa kalahati ng kanang kalahati.
At kaya niya ang isang listahan ng sukat 1.
Malinaw naman ang kanyang pinagsunod-sunod.
At ang iyong pangalan muli?
>> Michelle: Michelle.
>> David MALAN: Michelle ay malinaw naman isang listahan ng mga sukat 1.
Na siya pinagsunod-sunod.
Kaya ngayon magic ang mangyayari, ang proseso ng pagbubuklod.
Kaya kung sino ang pagpunta sa dumating una?
Malinaw Michelle.
Kaya kung maaari mong dumating sa paligid ng likod.
Ang espasyo mayroon kaming magagamit para sa kanya ngayon ang tama ito sa likod ng upuan dito.
At ngayon, kung maaari kang bumalik pati na rin, kami ay mayroon na ngayong, upang maging malinaw, dalawang
halves, bawat isa sa laki ng 2 -
at para lamang sa kapakanan ng paglalarawan, kung maaaring gumawa ng isang maliit na bit ng isang puwang -
isa pakaliwa kalahati dito, isa kanang kalahati dito.
>> Rewind pa sa kuwento.
Ano hakbang ay ang susunod?
>> Madla: Pagsamahin.
>> David MALAN: Kaya ngayon kami ay may upang sumanib.
Kaya OK, kaya ngayon, thankfully, namin lamang nabakante apat na upuan.
Kaya namin ang ginamit nang dalawang beses bilang magkano ang memorya, ngunit maaari naming bigyan tingnan-flopping sa pagitan ng
ang dalawang array.
Kaya kung aling mga numero ay na dumating una?
Kaya Michelle, nang walang alinlangan.
Kaya dumating sa paligid at tumagal ang iyong upuan dito.
At pagkatapos ay number 2 ay malinaw naman susunod, kaya napunta ka dito.
Number 4, 6 na numero.
At muli, kahit na mayroong isang kaunting paglalakad kasangkot,
talaga, ang mga ito ay maaaring mangyari kaagad, sa pamamagitan ng paggalaw ng isa -
OK, nag-play na rin.
>> [Tawa]
>> David MALAN: At ngayon kami ay sa medyo magandang hugis.
Ang kaliwa kalahati ng buong input na ngayon ang pinagsunod-sunod.
Ang lahat ng mga karapatan, sa gayon ang mga guys ay nagkaroon ng kalamangan sa aking -
paano ginawa ito tapusin ang lahat ng mga batang babae sa pakaliwa at ang lahat ng mga lalaki sa kanan?
>> OK, kaya guys 'i-on ngayon.
Kaya hindi ko ituturo sa iyo mga hakbang na ito.
Susubukan naming makita kung maaari naming muling mag-apply ang parehong pseudocode.
Kung nais mong sige at tumayo, at ka guys, hayaan mo akong bigyan ka ng mic.
Tingnan kung hindi ka maaaring magtiklop kung ano lang namin ginawa dito sa
kabilang dulo ng listahan.
Sino ang kailangang makipag-usap muna, batay sa mga algorithm?
Kaya ipaliwanag kung ano ang iyong ginagawa bago gumawa ka ng anumang mga paa paggalaw.
>> Tagapagsalita 1: Ang lahat ng mga karapatan, kaya mula noong Ako ang kaliwang kalahati ng
kaliwa kalahati, bumalik ako.
I-right?
>> David MALAN: Mahusay.
>> Tagapagsalita 1: At pagkatapos -
>> David MALAN: Sino ang ipinapakita mic ang pumunta sa susunod?
>> Tagapagsalita 1: Susunod na numero.
>> Tagapagsalita 2: Kaya ako ang kanang kalahati ng kaliwang kalahati ng
kaliwa kalahati, at ibalik ko.
>> David MALAN: Mahusay.
Bumalik ka.
Kaya ngayon kung ano ang susunod na up para sa iyo dalawang?
>> Tagapagsalita 2: Gusto naming makita kung sino ang mas maliit.
>> David MALAN: Mismong.
Gusto naming pagsamahin.
Ang espasyo kami ng pagpunta sa gamitin upang sumanib sa iyo, kahit na ang mga ito
malinaw naman na pinagsunod-sunod, kami ay pagpunta na sundin ang parehong algorithm.
Kaya kung sino ang pupunta sa likod muna?
Kaya 3, at pagkatapos ay i-7.
At ngayon ang mic napupunta sa mga guys, OK?
>> Tagapagsalita 3: Kaya ako ang kanang kalahati ng kaliwa kalahati, at ang aking n Mababa sa
1, kaya lang ako pagpunta sa pumasa -
>> David MALAN: Mahusay.
>> Tagapagsalita 4: Ako ang kanang kalahati ng kanang kalahati ng kanang kalahati, at ako
din ang isang tao, kaya ako pagpunta sa bumalik.
Kaya ngayon namin pagsamahin.
>> Tagapagsalita 3: Kaya naming bumalik.
>> David MALAN: Kaya kang pumunta sa likod.
Kaya 5 napupunta muna, pagkatapos ay i-8.
At ngayon madla, kung saan ay ang hakbang na mayroon kami sa ngayon rewind
upang i-back sa ating mga isip?
>> Madla: Pagsamahin.
>> David MALAN: Ang pagsasama sa kaliwa kalahati at kanang kalahati ng orihinal na kaliwa kalahati.
Kaya ngayon -
at lamang upang gumawa ng malinaw na ito, gumawa ng kaunting espasyo
sa pagitan mo dalawang guys.
Kaya ngayon na ang dalawang mga listahan, kaliwa at kanan.
Kaya paano namin ngayon pagsamahin mo guys sa sa harap hilera ng upuan muli?
>> 3 napupunta unang.
Pagkatapos 5, nang walang alinlangan.
Pagkatapos ay 7, at ngayon ay 8.
OK, at ngayon kami ay?
>> Madla: Di tapos na.
>> David MALAN: Hindi tapos na, dahil malinaw naman, mayroong isang hakbang natitira.
Ngunit muli, ang dahilan gumagamit ako ng ito magulong pag-uusap tulad ng "rewind sa iyong isip,"
ito ay dahil na talaga kung ano ang nangyayari.
Kami ay pagpunta sa pamamagitan ng lahat ng mga hakbang na ito, ngunit kami ay isang uri ng pag-pause para sa isang
sandali, diving mas malalim sa algorithm, pag-pause para sa isang sandali,
diving mas malalim sa mga algorithm, at ngayon kami ay may upang ayusin ng rewind sa aming
isip at i-undo lahat ng mga layer na namin ang uri ng ilagay sa hold.
>> Kaya ngayon kami ay may dalawang mga listahan ng mga sukat 4.
Kung ka guys ay maaaring tumayo ang huling oras at gumawa ng kaunting espasyo dito upang
gumawa ng malinaw na ito ay ang kaliwa kalahati ng orihinal na, ang
kanang kalahati ng orihinal.
Sino ang unang numero na aming kailangan upang hilahin sa likod?
Michelle, siyempre.
>> Kaya naming ilagay Michelle dito.
At sino ang may number 2?
Numero ng 2 pagdating sa likod pati na rin.
Number 3?
Magaling.
Number 4, numero 5, 6 na numero, number 7, at 8 numero.
>> OK, sa gayon ito nadama tulad ng maraming ng mga hakbang, para sigurado.
Ngunit ngayon sabihin makita kung hindi namin makumpirma uri ng intuitively na ito
algorithm sa panimula, lalo na bilang n ay nakakakuha talagang malaki, pati na nasaksihan namin
may animation, ay sa panimula mas mabilis.
Kaya inaangkin ko ito algorithm, sa pinakamalala kaso at kahit na sa ang pinakamahusay na kaso,
ay malaki O ng beses n log n.
Iyon ay, mayroong ilang mga aspeto ng ito algorithm na tumatagal ng mga hakbang n, ngunit
mayroong isa pang aspeto sa isang lugar sa na-ulit, na looping, na
tumatagal log hakbang n.
Maaari naming ilagay ang aming mga daliri sa kung ano ang mga dalawang numero ay nagre-refer sa?
Well, kung saan -
where'd mic ang pumunta?
>> Tagapagsalita 1: Gusto ang mag-log n maging pagsira sa amin up sa dalawa -
paghahati sa pamamagitan ng dalawang, mahalagang.
>> David MALAN: Mismong.
Anumang oras na nakikita namin sa anumang mga algorithm kaya sa ngayon, mayroong nangyaring ang pattern na ito ng
divide, divide, divide.
At karaniwang ito ay nabawasan sa isang bagay na
logarithmic, log base 2.
Ngunit maaari itong talagang maging anumang bagay, ngunit mag-log base 2.
>> Ngayon kung ano ang tungkol sa n?
Maaari ko bang makita na namin ang uri ng hinati mo guys - hinati sa iyo, na hinati sa iyo,
hinati mo, hinati sa iyo.
Saan kinukuha ng pagtatapos ang nanggaling?
>> Kaya ito ang pinagsasama.
Dahil sa tingin tungkol dito.
Kapag pagsamahin mo ang walong taong magkasama, kung saan ang kalahati sa kanila ay isang hanay ng mga apat
at ang iba pang kalahati ay isa pang set ng apat, paano mo pumunta
tungkol sa paggawa ng pagbubuklod?
Well, ka guys ginawa ito medyo intuitively.
>> Ngunit kung ako sa halip ginawa ito ng kaunti pa methodically, maaari ko pa sa may tulis
pinakakaliwa ang unang tao sa aking kaliwa banda, itinuturo sa pinakakaliwa tao
ng na kalahati sa aking kanang kamay, at lamang pagkaraan lumakad sa pamamagitan ng
listahan, na nagtuturo sa mga pinakamaliliit na elemento bawat oras, gumagalaw ang aking daliri sa ibabaw at
sa ibabaw tulad ng kinakailangan sa buong listahan.
Ngunit kung ano ang tungkol sa key na ito pinagsasama proseso ay ako paghahambing ng mga pares
ng mga elemento.
Mula sa kanang kalahati at mula sa kaliwa kalahati, hindi ako isang beses backtracking.
>> Kaya ang sumanib mismo ay pagkuha hindi hihigit sa n hakbang.
At kung gaano karaming beses ginawang Mayroon akong gawin na pinagsasama?
Well, hindi hihigit sa n, at hindi na namin lamang Nakita na may mga panghuling sumanib.
At kaya kung gagawin mo ang isang bagay na tumatagal mag-log n hakbang n beses, o kabaligtaran,
ito ay pagpunta sa bigyan kami ng n beses log n.
>> At kung bakit ito ay mas mahusay?
Well, kung kami na malaman na ang log n ay mas mahusay kaysa sa n - tama?
Nakakita kami sa binary paghahanap, ang phone book Halimbawa, log n noon ay siguradong
mas mahusay kaysa sa linear.
Kaya na nangangahulugan n beses log n ay Talagang mas mahusay kaysa sa n isa pang beses
n, aka n squared.
At ang ginagawa namin sa huli pakiramdam.
>> Kaya malaki ang pag-ikot ng papuri, kung maaari naming, para sa mga guys.
>> [Palakpakan]
>> David MALAN: At ang iyong Paghahati ng mga regalo - maaari mong panatilihin ang mga numero,
kung gusto mo.
At iyong Paghahati ng regalo, gaya ng dati.
Oh, at magpapadala kami sa iyo ang footage, Michelle.
Salamat sa inyo.
Ayos lang.
Tulungan ang iyong sarili sa isang bola stress.
>> At hayaan mo akong hilahin pataas, sa pansamantala, ang aming mga kaibigan Rob Bowden upang mag-alok
medyo iba sa pananaw na ito, dahil maaari mong isipin ang tungkol sa mga
hakbang na nangyayari sa isang medyo iba't ibang paraan.
Sa katunayan, ang set-up para sa kung ano ang Rob ay tungkol sa upang ipakita sa amin Ipinagpapalagay na na namin
nagagawa sa naghahating up ng malaking listahan sa walong maliit na mga listahan,
bawat isa sa laki 1.
>> Kaya naming binabago ang isang pseudocode Medyo lamang upang pagbukud-bukurin makakuha ng sa
pangunahing ideya kung paano ang pinagsasama ang mga gawa.
Ngunit ang oras ng paggana ng kung ano siya ay tungkol sa upang gawin ay pa rin
pagpunta sa maging ang parehong.
At muli, ang set-up dito ay na siya ay nagsimula na may walong mga listahan ng mga sukat 1.
Kaya mo nasagot ang bahagi kung saan siya talagang tapos na ang log n, log n, log n
paghahati ng input.
>> [Video playback]
>> -Iyon lang para sa hakbang ng isa.
Para sa dalawang hakbang, paulit-ulit pagsamahin ang mga pares ng mga listahan.
>> David MALAN: Hm.
Tanging ang audio ay darating out sa aking computer.
Tayo'y subukan ito muli.
>> -Nagkataon lang piliin kung aling mga - ngayon kami ay may apat na mga listahan.
Matuto nang bago.
>> David MALAN: Mayroon kaming pumunta.
>> Ang pagsasama-108 at 15, tapusin namin up sa listahan ng 15, 108.
Ang pagsasama sa 50 at 4, namin end up sa 4, 50.
Ang pagsasama sa 8 at 42, kami end up sa 8, 42.
At pagbubuklod 23 at 16, kami end up na may 16, 23.
>> Ngayon ang lahat ng aming mga listahan ay ang laki ng 2.
Pansinin na ang bawat isa sa apat na listahan ay pinagsunod-sunod.
Kaya maaari naming simulan pinagsasama mga pares ng mga listahan muli.
Ang pagsasama sa 15 at 108 at 4 at 50, kami unang kumuha ng 4, pagkatapos ang 15, pagkatapos ay
ang 50, pagkatapos ay ang 108.
Ang pagsasama sa 8, 42 at 16, 23, una naming tumagal ang 8, pagkatapos ang 16, pagkatapos ay ang 23,
pagkatapos ng 42.
>> Kaya ngayon kami ay may lamang ng dalawang mga listahan ng mga laki 4, ang bawat isa ay pinagsunod-sunod.
Kaya ngayon pagsamahin namin ang dalawang mga listahan.
Una, tumagal kami ng 4, pagkatapos ay i-alang namin ang mga 8, pagkatapos ay i-alang namin ang 15, pagkatapos ay 16, pagkatapos
23, pagkatapos ay 42, pagkatapos ay 50, pagkatapos ay 108.
>> [END-playback ng video]
>> David MALAN: Muli, paunawa, siya ay hindi kailanman hinawakan isang ibinigay na tasa ng higit sa isang oras
pagkatapos ng pagsulong lampas ito.
Kaya hindi na niya paulit-ulit.
Kaya palagi niya gumagalaw sa gilid, at na kung saan namin nakuha ang aming n.
>> Bakit hindi hayaan mo akong makuha ang isa animation na nakita natin mas maaga, ngunit oras na ito
tumututok lamang sa pagsasama-uri.
Hayaan akong sige at mag-zoom in sa mga ito dito.
Unang hayaan mo akong pumili ng isang random na input, palakihin ito, at maaari mong i-sort ng makita
ano kinuha namin para sa ipinagkaloob, mas maaga, pagsamahin ang pag-uuri ay aktwal na paggawa.
>> Kaya mapapansin na kumuha ka ng mga halves o mga quarters o mga eighths ng
problema na ang lahat ng isang biglaang simulan na kumuha ng mahusay na hugis.
At pagkatapos ay sa wakas, makikita mo sa pinakadulo na panunuba,
ang lahat ng bagay ay pinagsama-sama.
>> Kaya ang mga ito ay lamang ng tatlong iba't ibang tumatagal sa parehong mga ideya.
Ngunit ang key na pananaw, tulad ng hatiin at lupigin sa pinakadulo first class,
na noon ay napagpasyahan naming sa paanuman hatiin ang mga problema sa isang bagay na malaki, sa
isang bagay na uri ng katulad sa espiritu, ngunit mas maliit at mas maliit at mas maliit
at mas maliit.
>> Ngayon ay isa pang masaya na paraan upang ayusin ng tingin tungkol sa mga ito, kahit na ito ay hindi
pagpunta sa magbibigay sa iyo ng parehong madaling maunawaan pang-unawa, ay
ang mga sumusunod na animation.
Kaya ito ay isang video ng isang tao ilagay magkasama na nauugnay ibang
tunog na may iba't-ibang mga pagpapatakbo para sa pagpapasok ng uri, para sa pagsasama-uri-uriin, at
para sa isang pares ng mga iba.
Kaya sa isang sandali, pupuntahan ko pindutin ang Play.
Ito ay tungkol sa isang minuto ang haba.
At kahit na maaari mo pa ring makita ang pattern ng nangyayari, oras na ito maaari mong
din marinig kung paano ang mga algorithm ay gumaganap naiiba at may
medyo iba pattern.
>> Ito ay pagpapasok-uri.
>> [Tone pag-play]
>> David MALAN: Ito muli ay sinusubukan upang magpasok ng bawat elemento
sa kung saan ito ay kabilang.
Ito ang bubble sort.
>> [Tone pag-play]
>> David MALAN: At maaari mong uri-uriin ng pakiramdam paano relatibong maliit na gumana ito ginagawa
sa bawat hakbang.
Ito ay kung ano tediousness Mukhang.
>> [Tone pag-play]
>> David MALAN: Ito ang seleksyon-uri, kung saan namin piliin ang sangkap na nais naming sa pamamagitan ng
sa pamamagitan ng pagpunta muli at muli at muli at paglalagay ito sa simula.
>> [Tone pag-play]
>> David MALAN: Ito ay sumanib-uri, na Maaari mo ba talagang simulan sa pakiramdam.
>> [Tone pag-play]
>> [Tawa]
>> David MALAN: Isang bagay na tinatawag na lamang-lupa -uri-uriin, na hindi pa namin ay tumingin sa.
>> [Tone pag-play]
>> David MALAN: Kaya hayaan mo akong makita, ngayon, ginulo bilang ka sana ay sa pamamagitan ng mga
musika, kung maaari kong slip ng kaunti bit ng math in dito.
Kaya mayroong 1/4 na paraan na aming makakaya isipin ang tungkol sa kung ano ang ibig sabihin nito ang mga
mga function na maging mas mabilis kaysa sa mga bago na nasaksihan namin dati.
At kung ikaw ay darating sa kurso mula sa isang matematika background, mo
talaga alam na marahil na ikaw Maaari sampal isang termino sa diskarteng ito -
lalo recursion, isang function sa paanuman na tawag mismo.
>> At muli, isipin ang sumanib na pag-uuri pseudocode ay recursive sa kamalayan
na ang isa sa mga hakbang sa pagsasama-uri ng ay tumawag sa uri-uriin -
iyon ay, mismo.
Pero thankfully, sapagkat hindi namin itinatago pagtawag-uri, o pagsamahin ang pag-uuri,
partikular, sa isang mas maliit at mas maliit at mas maliit na listahan, namin kalaunan
bottomed out salamat sa kung ano ang makikita namin tumawag isang base ng kaso, ang hard-code na kaso
Sinabi kung ang listahan ay maliit, mas mababa sa 2 sa kasong iyon, bumalik lang agad.
Kung hindi namin ginawa na may mga espesyal na kaso, ang algorithm ng ginagawa hindi kailanman ilalim out,
at gusto mo talagang makapunta sa isang walang katapusang loop tunay magpakailanman.
>> Ngunit ipagpalagay na gusto naming ilagay ngayon ilang mga numero sa mga ito, muli, gamit n
bilang ang laki ng input.
At Nais kong hilingin sa iyo, kung ano ang ang kabuuang oras na kasangkot sa
tumatakbo pagsasama-uri?
O kaya naman mas pangkalahatang paraan, kung ano ang ang gastos ng mga ito sa oras?
>> Well ito ay medyo madali upang masukat na.
Kung n Mababa sa 2, ang oras na kasangkot sa pagbubukod-bukod ng mga elemento n,
n kung saan ay 2, ay 0.
Dahil kami lang bumalik.
Walang trabaho upang gawin.
Ngayon arguably, marahil ito ay isang hakbang o dalawang hakbang na ito upang malaman ang halaga ng
gumana, ngunit ito ay malapit na sapat upang 0 na Lamang ako ng pagpunta sa sabihin walang trabaho ay
kinakailangan kapag ang listahan ay kaya maliit na na hindi kawili-wili.
>> Ngunit kasong ito ay kawili-wili.
Ang recursive kaso ay ang sangay ng ang pseudocode na sinabi ng ibang tao, pag-uuri
sa kaliwang kalahati, uri-uriin ang karapatan kalahati, pagsamahin ang dalawang halves.
Ngayon kung bakit gumagana ang expression na ito kumakatawan na gastos?
Well, T ng n lamang ay nangangahulugan na ang oras upang ayusin n elemento.
At pagkatapos ay sa kanang bahagi ng equals sign doon, ang T ng n hinati
sa pamamagitan ng 2 ay nagre-refer na upang ang gastos ng kung ano?
Pag-aayos sa kaliwa kalahati.
Ang iba pang mga T ng n hinati sa 2 ay siguro nagre-refer sa mga gastos sa
-uri-uriin ang karapatan kalahati.
>> At pagkatapos ay ang plus n?
Ay ang pinagsasama.
Dahil kung mayroon kang dalawang mga listahan, isa sa laki n sa 2 at isa pa sa laki n
sa 2, mayroon ka upang lubos na hawakan bawat isa sa mga elemento, tulad ng Rob
hinawakan bawat isa sa mga tasa, at lamang bilang namin itinuturo sa bawat isa sa mga
boluntaryo sa entablado.
Kaya n ay ang gastos ng pagbubuklod.
>> Ngayon, sa kasamaang-palad, ito formula din ang kanyang sarili recursive.
Kaya kung tinanong ang tanong, kung n ay, sabihin nating, 16, kung mayroong 16 mga tao sa entablado
o 16 tasa sa video, kung gaano karaming mga kabuuang hakbang na aabutin upang pagbukud-bukurin ang mga ito
may sumanib-uri?
Ito ay talagang hindi isang halata na sagot, dahil ngayon ikaw ay may upang ayusin ng
recursively sagutin ang formula.
>> Ngunit iyon lamang ang OK, dahil ipaalam sa akin imungkahi na gawin namin ang mga sumusunod.
Ang oras na kasangkot upang pagbukud-bukurin 16 mga tao o 16 tasa ay pagpunta sa ay kakatawanin
sa pangkalahatan bilang ng T 16.
Ngunit na katumbas, ayon sa aming nakaraang formula, 2 beses ang halaga
ng oras na aabutin upang pagsunud-sunurin 8 tasa plus 16.
At muli, plus 16 ang oras upang pagsamahin, at ang dalawang beses T ng 8 ay ang
oras upang ayusin kaliwa kalahati at kanang kalahati.
>> Ngunit muli, ito ay hindi sapat.
Mayroon kaming upang sumisid sa mas malalim.
Nangangahulugan ito na mayroon kami upang sagutin ang tanong, ano ang T ng 8?
Well T ng 8 ay 2 T beses na 4 na plus 8.
Well, kung ano ang T ng 4?
T ng 4 ay 2 beses T ng 2 plus 4.
Well, kung ano ang T ng 2?
T ng 2 ay 2 beses T ng 1 plus 2.
>> At muli, hindi namin uri ng pagkuha ng natigil sa pag-ikot na ito.
Ngunit ito ay tungkol sa hit na tinatawag nang gayon base kaso.
Dahil kung ano ang T na 1, kami nag-claim?
0.
Kaya ngayon sa wakas, maaari naming magtrabaho paurong.
>> Kung T ng 1 ay 0, maaari ko na ngayong bumalik up isa linya upang ito tao dito, at maaari ko
plug sa 0 para sa T na 1.
Kaya ito ay nangangahulugan na ito ay katumbas ng 2 beses zero, kung hindi man kilala bilang 0, plus 2.
At upang ang buong expression ay 2.
>> Ngayon kung kumuha ako ng T ng 2, na ang sagot ay 2, plug ito sa gitnang linya, T
ng 4, na nagbibigay sa akin ng 2 beses 2 plus 4, kaya 8.
Kung ako pagkatapos ay i-plug in 8 sa nakaraang linya, na nagbibigay sa akin ng 2 beses 8, 16.
At kung namin pagkatapos ay patuloy na may mga 24, pagdaragdag sa 16, namin sa wakas makakuha ng isang
halaga ng 64.
>> Ngayon na in at ng mismong uri ng nagsasalita walang kinalaman ang notation n, ang
malaki Oh, ang wakas na na namin na-pakikipag-usap tungkol sa.
Ngunit ito lumiliko out na 64 ay talagang 16, ang laki ng input,
mag-log base 2 ng 16.
At kung ito ay isang maliit na pamilyar, lamang Sa tingin pabalik, at makikita ito ay bumalik
sa iyo sa kalaunan.
Kung ito ay base log 2, ito ay tulad ng 2 itataas sa kung ano ang nagbibigay sa iyo ng 16?
Oh, na 4, kaya 16 beses 4.
>> At muli, ito ay hindi isang malaking pakikitungo kung ito ay isang uri ng isang malabo memory ngayon.
Ngunit para sa ngayon, kumuha sa pananampalataya 16 na log 16 ay 64.
At gayon nga, na may ganitong simpleng kaliwanagan ng isip check, kami Nakumpirma -
ngunit hindi pormal na di-napatutunayang -
na ang oras ng pagsasama -uri ay sa katunayan n log n.
>> Kaya hindi masama.
Ito ay tiyak na mas mahusay kaysa sa algorithm nasaksihan namin kaya sa ngayon, at
ito ay dahil kami na magagamit, isa, isang diskarte na tinatawag na recursion.
Ngunit mas kawili-wiling kaysa sa na, na kuru-kuro ng paghahati at mapanakop.
Muli, ang tunay na linggo 0 bagay-bagay na kahit na ngayon ay umuulit sa isang
mas nakakahimok paraan.
>> Ngayon ay isang masaya maliit na ehersisyo, kung ikaw ay hindi kailanman tapos na ito - at malamang na
hindi mayroon, dahil uri ng normal mga tao ay hindi isip upang gawin ito.
Ngunit kung pumunta ako sa google.com at kung Gusto kong matuto ng isang bagay tungkol sa
recursion, ang Enter.
>> [Tawa]
[MORE tawa]
David MALAN: Hindi magandang biro mabagal ang pagkalat.
[Tawa]
David MALAN: lamang sa kaso, ito ay doon.
Hindi ko oras ng paggawa ito mali, at mayroong biro ang.
Ayos lang.
Ipaliwanag ito sa mga tao na susunod sa iyo kung ang hindi ito ay lubos na nag-click pa lang.
Ngunit recursion, higit pa sa pangkalahatan, ay tumutukoy upang ang proseso ng isang function sa pagtawag
mismo, o sa mas pangkalahatang paraan, paghahati ng problema sa isang bagay na maaaring maging
Nalutas unti-unti sa pamamagitan ng paglutas ng magkaparehong kinatawan problema.
>> Well, sabihin pagbabagong gears para lamang ng ilang sandali.
Nais namin na magtatapos sa ilang cliffhangers, kaya natin simulan upang i-set
ang entablado, para sa ilang mga minuto, sa isang napaka-simpleng ideya -
na pagpapalit ng dalawang mga elemento, tama?
Ang lahat ng mga algorithm kami nakapunta pakikipag-usap tungkol sa mga nakalipas na ilang
aralin kasangkot sa ilang uri ng pagpapalit.
Ngayon ay makita ang mga ito sa pamamagitan ng pagkuha ng up out ng kanilang mga upuan at
paglalakad sa paligid, ngunit sa code, gagawin namin lamang tumagal ng isang elemento mula sa isang array
at masamang balak ito sa isa pa.
>> Kaya paano namin pumunta tungkol sa paggawa na ito?
Well, ipaalam sa akin sige at isulat isang mabilis na programa dito.
Pupunta ako sa sige at gawin ito bilang sumusunod.
Sabihin tumawag ito -
ano ang gusto namin na tawagan ang isang ito?
>> Talaga, hindi.
Hayaan akong rewind.
Hindi ko nais upang gawin iyon cliffhanger pa.
Ito ay palayawin ang saya.
Natin gawin ito sa halip.
>> Ipagpalagay na gusto kong magsulat ng kaunti at programa na ngayon embraces ito
ideya ng recursion.
Ako uri ng nakuha nang mas maaga sa aking sarili doon.
Pupunta ako sa gawin ang mga sumusunod.
>> Una, ang isang mabilis na isama ng standard io.h, pati na rin ang kinabibilangan ng cs50.h.
At pagkatapos ay ako pagpunta sa sige at ipinapahayag int pangunahing walang bisa
sa karaniwang paraan.
Ako natanto ko na misnamed ang file, sa gayon hayaan mo akong magdagdag lang ng isang. extension c dito kaya
na maaari naming ipunin ito nang maayos.
Simulan ang pag-andar na ito off.
>> At ang function na gusto kong isulat, medyo lamang, ay isa na itinatanong ang
gumagamit para sa isang numero at pagkatapos ay nagdadagdag up ang lahat ng mga numero sa pagitan na
numero at, sabihin nating, 0.
Kaya unang pupuntahan ko sige at ipinapahayag int n.
Pagkatapos ay kokopyahin ang ilang mga code na kami na ginagamit para sa isang habang.
Habang ang isang bagay ay totoo.
Kukunin ko ay bumalik sa na sa ilang sandali.
>> Ano ang gusto kong gawin?
Gusto kong sabihin printf positibong mangyaring integer.
At pagkatapos ay pupuntahan ko sabihin n nakakakuha makakuha ng int.
Kaya muli, ang ilang mga boilerplate code na aming ginamit bago.
At ako pagpunta sa gawin ito habang n Mababa sa 1.
Kaya ito ay tinitiyak na ang mga gumagamit ay nagbibigay sa akin ng isang positibong integer.
>> At ngayon ako pagpunta sa gawin ang mga sumusunod.
Gusto kong magdagdag ng hanggang ang lahat ng mga numero sa pagitan ng 1 at at n, o 0 at n,
equivalently, upang makuha ang kabuuang sum.
Kaya ang malaking simbolo palatandaan na maaari mong isipin ang.
Kaya ako ng pagpunta sa gawin ito sa pamamagitan ng pagtawag sa unang isang function na tinatawag na palatandaan,
pagpasa ito sa n, at pagkatapos ay pupuntahan ko sabihin printf, ang sagot ay kanan doon.
>> Kaya sa maikling, kumuha ako at int mula sa user.
Ko matitiyak na ito ay positibo.
Ipinahahayag ko sa isang variable na tinatawag na sagot ng Uri ng int at iimbak sa ito ang balik
halaga ng mga palatandaan, pagpasa sa n bilang input.
At pagkatapos kong i-print out na sagot.
>> Sa kasamaang palad, kahit na palatandaan tunog tulad ng isang bagay na maaaring maging sa
ang math.h file, deklarasyon nito, ito ay talagang hindi.
Kaya iyon ang OK.
Maaari ko bang ipatupad ang sarili ko.
Pupunta ako sa ipatupad ang isang function na tinatawag na palatandaan, at ito ay pagpunta sa kumuha ng isang
parameter -
sabihin lang tumawag ito m, lamang kaya iba ito.
At pagkatapos ay i-up dito, pupuntahan ko sabihin, well, kung m ay mas mababa sa 1 - ito ay isang
napaka hindi kawili-wili programa.
Kaya pupuntahan ko sige at agad na bumalik 0.
Ito lamang ay hindi magkaroon ng kahulugan upang magdagdag ng hanggang ang lahat ng ang mga numero sa pagitan ng 1 at m kung m
mismo ay 0 o negatibo.
>> At pagkatapos ay ako pagpunta sa sige at gawin ito napaka iteratively.
Pupuntahan ko na gawin ang ganitong uri ng lumang-paaralan, at pupuntahan ko sige
at sabihin na pupuntahan ko magpahayag ng isang kabuuan sa 0.
Pagkatapos ay pupuntahan ko mayroon isang para sa loop ng int -
at ipaalam sa akin gawin ito upang tumugma sa aming pamamahagi code, kaya mayroon kang isang kopya
sa bahay. int i makakakuha ng 1 sa hanggang sa i mas mababa sa o katumbas ng m.
i plus plus.
At pagkatapos ay sa loob ng mga ito para sa loop -
Ikinalulungkot namin halos doon -
sum ay nakakakuha ng sum plus 1.
At pagkatapos ay ako pagpunta sa bumalik ang kabuuan.
>> Kaya ko ginawa ito nang mabilis, medyo tinatanggap na.
Ngunit muli, ang pangunahing function na ay medyo tuwiran, batay sa code na namin
nakasulat kaya malayo.
Gumagamit ang dual loop upang makakuha ng positibong int mula sa user.
Pagkatapos kong pumasa na int sa isang bagong pag-andar tinatawag na palatandaan, pagtawag ito, muli, n.
At mag-store ko ang return value, ang kasagutan mula sa itim na kahon sa kasalukuyan
Kilala bilang palatandaan, sa isang variable tinatawag na sagot.
Pagkatapos ko i-print ito.
>> Kung namin ngayon magpatuloy sa kuwento, paano palatandaan ay ipinatupad?
Ipanukala ko upang ipatupad tulad ng sumusunod.
Una, ng kaunting error-checking upang tiyakin na ang gumagamit ay hindi
panggugulo sa akin at sa pagpasa sa ilang mga negatibong o 0 halaga.
Pagkatapos kong idedeklara sa isang variable na tinatawag na sabihin sa ilang at itakda ito sa 0.
>> At ngayon ako magsisimulang upang ilipat mula sa i katumbas 1 ang lahat ng mga paraan ng hanggang sa at kabilang ang m,
dahil gusto ko upang isama ang lahat ng mga numero mula sa isa sa pamamagitan ng m, inclusive.
At sa loob ng mga ito para sa loop, ko lang gawin sum ay nakakakuha ng anumang ito ay ngayon, pati ang
halaga ng i.
Plus ang halaga ng i.
>> Bilang isang tabi, kung hindi mo nakita ito bago, mayroong ilang mga sintaktik asukal
para sa linyang ito.
Maaari ko bang isulat na muli ito bilang katumbas ng plus i, lamang i-save ang sarili ko ng ilang mga keystroke
at upang tumingin ng kaunti mas cool.
Ngunit iyon lamang ang lahat.
Ito ay halos pareho sa pagtakbo bagay.
>> Sa kasamaang palad, ang code na ito sa hindi pagpunta sa sumulat ng libro pa.
Kung nagpapatakbo ako gumawa palatandaan 0, paano am Ako pagpunta upang yelled sa?
Ano kaya ito ng pagpunta sa hindi gusto?
>> Madla: [hindi marinig].
>> David MALAN: Oo, hindi ko idedeklara ang pagpapaandar up tuktok, tama?
C ay uri ng bobo, sa na ito lamang kung ano ang ibig sabihin mo ito gawin, at ikaw
kailangang gawin ito sa na order.
At kaya kung ako pindutin ang Enter dito, pupuntahan ko makakuha ng isang babala tungkol sa palatandaan implicit
deklarasyon.
>> Oh, hindi problema.
Maaari ba akong mag-up sa tuktok, at maaari ko sabihin, ang lahat ng karapatan, maghintay ng isang minuto.
Sigma ay isang function na nagbabalik isang int at ito Inaasahan ng isang
int bilang input, tuldok-kuwit.
O maaari ko bang ilagay ang buong pag-andar sa itaas pangunahing, ngunit sa pangkalahatan, Gusto ko
Inirerekumenda laban na, dahil ito ay Nice upang laging may pangunahing sa tuktok kaya
maaari kang sumisid karapatan sa at alam kung ano ang isang programa ay ginagawa sa pamamagitan ng pagbabasa pangunahing muna.
>> Kaya ngayon hayaan mo akong i-clear ang screen.
Muling paggawa palatandaan 0.
Ang lahat ay tila mag-check out.
Hayaan akong magpatakbo palatandaan 0.
Positibong ilibing.
Kukunin ko bigyan ito ang bilang 3 upang panatilihin itong simple.
Kaya na dapat magbigay sa akin 3 plus 2 plus 1, kaya 6.
Ipasok, at sa katunayan nakukuha ko 6.
>> Ang maaari kong gawin ng isang bagay na mas malaki -
50, 12, 75.
Tulad ng isang tanghente, pupuntahan ko gawin isang bagay na katawa-tawa tulad ng isang talagang malaking
numero, Oh, na aktwal na nagtrabaho out -
eh, Hindi sa tingin ko na tama.
Tayo'y makita.
Natin talaga Nagkamali gamit ito.
>> Iyan ay isang problema.
Ano kaya ang nangyari?
Ang code ay hindi na masama.
Ito ay pa rin linear.
Sumisipol ay isang mahusay na epekto, bagaman.
Ano kaya ang nangyari?
>> Hindi sigurado kung Narinig ko ito.
Kaya ito lumiliko out - at ito ay bilang isang bukod.
Ito ay hindi core sa ideya ng recursion.
Ito ay lumiliko out, dahil sinusubukan ko upang Kinakatawan tulad ng isang malaking bilang, karamihan
malamang ito ay misinterpreted sa pamamagitan ng C bilang isang hindi positibong numero,
ngunit negatibong numero.
>> Hindi pa kami uusapang tungkol sa ito, ngunit ito lumiliko out may mga negatibong numero
sa mundo bilang karagdagan sa positibong numero.
At ang paraan kung saan maaari kang kumakatawan sa isang negatibong numero
talaga ay, gamitin mo ang isa espesyal na sandali upang ipahiwatig
positibo sa paglipas ng mga negatibong.
Ito ay isang maliit na mas kumplikado kaysa sa na, ngunit iyon ang pangunahing ideya.
>> Kaya sa kasamaang-palad, kung C ay nakakalito isa ng mga piraso ng kung aktwal ibig sabihin,
oh, ito ay isang negatibong numero, ang aking loop dito, halimbawa, ay talagang hindi kailanman
pagpunta sa wakasan.
Kaya kung talagang ako ay pag-print ng isang bagay muli at muli, kami ay
makita ang isang buong lot.
Ngunit muli, ito ay bukod sa punto.
Ito ay talagang lamang ng isang uri ng intelektwal na pag-usisa na kami ay dumating
i-back sa kalaunan.
Ngunit para sa ngayon, ito ay isang tamang pagpapatupad kung ipinapalagay namin na ang
user ay magbibigay ng ints na akma sa loob ng ints.
>> Pero inaangkin ko na ang code na ito, lantaran, ma-nagagawa mas simple.
Kung ang layunin sa kamay ay upang kumuha ng isang numero tulad m at magdagdag ng hanggang ang lahat ng mga
mga numero sa pagitan ng ito at ang 1, o pasalungat sa pagitan ng 1 at ito, inaangkin ko
na maaari ko bang hiramin ang ideya na pagsamahin sort nagkaroon, kung saan ito ay tumatagal ng problema
na ganito ang laki at paghahati nito sa isang bagay na mas maliit.
Siguro hindi kalahati, ngunit mas maliit, ngunit representatively ang parehong.
Parehong mga ideya, ngunit isang mas maliit na problema.
>> Kaya talaga ako - hayaan mo akong i-save ang file na ito gamit ang ibang numero ng bersyon.
Susubukan naming tawagan ang bersyon na ito 1 sa halip na 0.
At inaangkin ko na makakaya ko talaga reimplement ito sa ganitong uri ng
isip-baluktot na paraan.
>> Pupunta ako sa umalis bahagi nito nag-iisa.
Pupunta ako sa sinasabi kung m ay mas mababa mababa sa o kahit na katumbas ng 0 -
Lamang ako ng pagpunta sa maging isang maliit na mas anal oras na ito
kasama ang aking mga error checking -
Pupunta ako sa sige at bumalik 0.
Ito ay di-makatwirang.
Lamang ako ay simpleng pagpapasya kung ang user Binibigyan ako ng isang negatibong numero, ako
bumabalik na 0, at dapat nilang Nabasa ang dokumentasyon ng malapitan.
>> Iba Pa -
mapansin kung ano ako ng pagpunta sa gawin.
Iba Pa ako pagpunta sa bumalik m plus -
ano ang palatandaan ng m?
Well, palatandaan ng m plus m minus 1, plus m minus 2, plus m minus 3.
Hindi ko nais upang isulat ang lahat ng na out.
Bakit hindi ko lang magtikin?
Recursively tumawag sa aking sarili na may isang bahagyang mas maliit problema, tuldok-kuwit,
at tumawag ito ng isang araw?
>> I-right?
Ngayon dito, masyadong, maaari mong huwag mag-o-alala na ito ay isang walang-katapusang loop na ako
pampalaglag, kung saan ako ay pagpapatupad palatandaan sa pamamagitan ng pagtawag ng palatandaan.
Ngunit iyon lamang ang perpektong OK, dahil ako Naisip maaga isang idinagdag na mga linya?
>> Madla: [hindi marinig].
>> David MALAN: 23-26, na ay ang aking kung kondisyon.
Dahil kung ano ang maganda tungkol sa palabawasan dito, dahil panatilihing ako
handing palatandaan mas maliit na problema, mas maliit problema, mas maliit - hindi ito
kalahati ng laki.
Ito ay lamang ng isang sanggol hakbang na mas maliit, ngunit iyon ang OK.
Dahil sa huli, makikipagtulungan kami ang aming paraan down sa 1 o 0.
At sa sandaling pindutin namin 0, palatandaan ay hindi pagpunta sa tawagan mismo nakikita.
Ito ay pagpunta sa agad na bumalik 0.
>> Kaya ang epekto, kung uri ng hangin na ito up sa iyong isip, ay ang magdagdag ng m plus
m minus 1, plus m minus 2, plus minus m 3, plus tuldok, tuldok, tuldok, m minus
m, sa huli pagbibigay sa iyo ng 0, at ang epekto sa huli ay upang idagdag ang lahat ng
mga bagay na ito nang magkakasama.
Kaya kami ay may hindi, may recursion, malutas ang problema na namin
Hindi ma-solve bago.
Sa katunayan, 0 bersyon ng ito, at ang bawat problema sa petsa, ay naging nalulusaw
sa pamamagitan lamang ng paggamit para sa mga loop o habang mga loop o katulad na mga constructs.
>> Ngunit recursion, sa palagay ko, ay nagbibigay sa amin ang ibang paraan ng pag-iisip tungkol sa
problema, kung saan kung maaari naming maglaan ng problema, hatiin ito mula sa isang bagay
medyo malaki sa isang bagay na medyo mas maliit, inaangkin ko na maaari naming malutas ito
marahil ng kaunti pa elegante sa tuntunin ng mga disenyo, na may mas kaunting code,
at marahil kahit na malutas ang mga problema na gagawin maging mahirap, pati na bibigyan namin ng kalaunan
makita, solve pulos iteratively.
>> Ngunit ang cliffhanger na aking ginawa nais na mag-iwan sa amin noon ay sa ito.
Hayaan akong sige at buksan up ng isang file mula sa -
talaga, hayaan mo akong pumunta at gawin ito real mabilis.
Hayaan akong sige at ipanukala ang mga sumusunod na.
Kabilang sa mga code na ngayong araw ay ang file na ito dito.
Ito ang isa dito, noswap.
>> Kaya ito ay isang maliit na nakababagod programa na Ako whipped up na claim na gawin
ang mga sumusunod na.
Sa pangunahing, ito muna declares isang int tinatawag na x at nagtatalaga ito
ang halaga ng 1.
Pagkatapos ito declares isang int y at Nagtatalaga ito ang halaga 2.
Pagkatapos ito prints out kung ano ang x at y ay.
Pagkatapos ay sinasabi nito, pagpapalit, tuldok tuldok tuldok.
>> Pagkatapos ito ang sinasabing ay pagtawag ng isang function tinatawag makipagpalitan ng, pagpasa sa x at
y, ang ideya ng kung saan ay na sana x at y ay bumalik
naiiba, ang kabaligtaran.
Pagkatapos ay i-claim ito swapped!
may isang tandang padamdam.
Pagkatapos ito prints out x at y.
>> Ngunit ito lumiliko out na ito napaka simpleng demonstration pababa
dito ay ang tunay maraming surot.
Kahit na ako deklarasyon ng pansamantalang variable at pansamantalang paglalagay ng sa
ito, pagkatapos ay ako reassigning ng ang halaga ng b -
na palagay ng makatwirang, dahil nag ko nai-save ang isang kopya ng isang sa Temp.
Pagkatapos ay i-update ko b-pantay na ano ay nasa Temp.
Ang ganitong uri ng shell laro ng paglipat ng isang sa b at b papunta sa isang sa pamamagitan ng paggamit na ito
gitna-tao na tinatawag na palagay ng Temp ganap na ganap makatwirang.
>> Pero inaangkin ko na kapag nagpatakbo ako ito code, dahil kakailanganin kong gawin ngayon -
ipaalam sa akin sige lang at i-paste ito sa dito.
Tatawag ako ito noswap.c.
At bilang ang pangalan nagmumungkahi, ito ay hindi pagpunta sa maging isang tamang programa.
Gawing noswap. / Hindi makipagpalitan.
x ay 1, y ay 2, pagpapalit, swapped.
x ay 1, y ay 2.
Ito ay sa panimula mali, kahit na bagaman ito ay tila ganap na ganap
makatwirang sa akin.
At doon ay isang dahilan, ngunit kami ay hindi pagpunta sa ibunyag ang dahilan lamang pa.
>> Para sa ngayon ang pangalawang cliffhanger Nais kong umalis ka ay may ito, isang
anunsyo ng ibang mga klase sa mga code ng kupon.
Ang aming mga makabagong ideya na may late na araw sa taong ito ay provoked isang non-walang halaga bilang
ng mga katanungan, na noon ay hindi aming intensyon.
Ang intensyon ng mga code ng kupon, kung saan gawin kung bahagi ka ng problema
itakda maaga, at dahil doon nakakakuha ng isang extrang araw, ay talagang upang matulungan kang makatulong na guys
simulan ang iyong sarili nang maaga, pag-uuri sa pamamagitan ng incentivizing mo.
Tumutulong sa amin ipamahagi sa buong load opisina ng mas mahusay na oras upang ang
ito ay isang uri ng manalo-manalo.
>> Sa kasamaang palad, sa tingin ko ang aking tagubilin hindi naging, sa petsa, napakalinaw, kaya
Nagpunta ako pabalik na ito katapusan ng linggo at na-update ang spec sa mas malaki, mas agresibong mga teksto sa
ipaliwanag bullet tulad ng mga ito.
At para lamang ito sinasabi pa sa publiko, sa pamamagitan ng default, ang problema sets ay dahil Huwebes
sa tanghali, sa bawat ang syllabus.
Kung nagsimula ka nang maaga, pagtatapos bahagi ng ang problema itinakda ng Miyerkules sa 12:00
PM, ang mga bahagi na nauugnay sa isang kupon code, ang ideya ay na maaari mong pahabain
iyong deadline para sa P itakda hanggang Biyernes.
Iyon ay, ang bit-off ang isang napakaliit na bahagi ng P set na may kaugnayan sa kung ano ang karaniwang ay ang
mas malaking problema, at bumili ka iyong sarili ng dagdag na araw.
Muli, ito ay nakakakuha ka ng pag-iisip tungkol sa ang problema set, nakakakuha ka sa
opisina oras mas maaga.
Ngunit ang kupon code problema pa rin ang kailangan, kahit na hindi mo isumite ito.
>> Ngunit higit pa compellingly ay ito.
(Stage bulong) At ang mga tao umaalis maagang gonna ay ikinalulungkot ito.
Habang ang mga tao sa balkonahe.
Humihingi ako ng paumanhin sa maaga upang ang mga tao sa ang balkonahe para sa mga kadahilanang iyon ay magiging
i-clear sa loob lamang ng ilang sandali.
>> Kaya tayo ay masuwerte upang magkaroon ng isa sa Dating ulo CS50 ng pagtuturo sa Fellows
isang kumpanya na tinatawag na dropbox.com.
Sila ay napaka maraming donasyon ng coupon code dito para sa mas espasyo,
na kung saan ay up mula sa karaniwan 2 gigabytes.
Kaya kung ano naisip ko na gusto naming gawin sa mga ito panghuling tala ay gawin ang isang bit ng isang giveaway,
kung saan sa loob lamang ng ilang sandali, ay namin ibinubunyag sa panalo at kung sino ang may isang kupon
code na maaari mong pagkatapos ay pumunta sa kanilang website, i-type ito sa, at voila, kumuha ng isang
buong maraming higit pa Dropbox espasyo para sa iyong appliance at para sa iyong personal na mga file.
>> At una sa lahat, na nais na lumahok sa ang guhit na ito?
OK, ngayon na ginagawang mas masaya.
Ang taong ito na natatanggap ng 25-gigabyte coupon code - na kung saan ay malayo
mas mabisa kaysa sa huli araw ngayon, siguro -
ay ang isa kung sino ang nakaupo sa tuktok ng isang upuan unan sa ilalim kung saan mayroong
na coupon code.
Maaari mo na ngayong tumingin sa ilalim ang iyong upuan unan.
>> [Video playback]
>> -Ang isa, dalawa, tatlo.
>> [Magaralgal]
>> -Mong makakuha ng isang kotse!
Makakakuha ka ng isang kotse!
>> David MALAN: Makikita natin mo sa Miyerkules.
>> -Mong makakuha ng isang kotse!
Makakakuha ka ng isang kotse!
>> David MALAN: Balkonahe kakailanganin ng mga tao, dumating down na dito sa harap,
kung saan mayroon kaming mga extra.
>> -Lahat ng tao ay nakakakuha ng kotse!
Lahat ng tao ay nakakakuha ng kotse!
>> [END-playback ng video]
>> Tagapagsalaysay: Sa susunod na CS50 -
>> Tagapagsalita 5: Oh aking sus sus sus sus sus sus sus sus sus sus -
>> [UKELELE pag-play]