>> [MUSIC nagpe-play]
>> David J. MALAN: Ito ang CS50.
At ito ay ang simula ng linggo tatlo.
Kaya namin nakuha ng isang pulutong ng mga kapana-panabik na mga bagay-bagay upang masakop ang araw na ito.
Ang isang pulutong ng mga pagkakataon para sa boluntaryo up sa entablado.
At sa huli, ngayon ay hindi tungkol sa code sa lahat.
Ngunit ito ay tungkol sa mga ideya, at ito ay tungkol sa mga algorithm,
at ang tunay na nagdadala sa likod ng ilan sa ang mga araling natutunan mula sa linggo zero,
kung saan ang pagpapabalik, namin ipinakilala ang isang napakapangit na bagay.
At paghiram ng inspirasyon mula sa na, upang simulan
upang malutas kailanman mas sopistikadong problema algorithmically.
Ngunit una, isang pares ng mga anunsyo.
Kaya isa, kung nais mong sumali Kawani at mga kaklase CS50 sa tanghalian
ito Biyernes, parehong dito at sa Cambridge, at sa New Haven,
mangyaring bisitahin ang kurso na iyon website, kung saan ay matatagpuan sa isang URL.
Magbigay ng panayam na ito Miyerkules Hindi na dito sa Sanders.
Ito lamang ay online, upang tune in sa website CS50,
kung dito sa Cambridge o New Haven rin.
>> At pagkatapos ay itakda ang problema ng dalawang Nasa iyong mga kamay.
Kung hindi mo pa dived sa pa, payagan ako na nag-aalok ng malakas na worded suggestion
na, lalo na ngayon, tulad ng Nagtatakda ang problema advance,
na tunay na nais na magsimula ngayon, kung hindi magkawkaw ng kaunti sa katapusan ng linggo o bago
kapag pumunta sila out muna sa Biyernes, dahil bibigyan ka
makita na ang mga ito ay hindi kinakailangan nakakakuha ng mas matagal o mas mahirap na per
se.
Tingin ko makikita ninyo na, sa pangkalahatan, sila ay madalas na tumagal ng humigit-kumulang
sa paligid ng parehong halaga ng oras.
Ngunit ito ay tiyak depende sa mag-aaral, at ito
depende sa mindset na kung saan ang diskarte mo ito.
Ngunit walang paltos, ikaw ay pagpunta na tumakbo up laban sa ilang mga pader,
at ikaw ay pagpunta sa hit ilang bug, at ikaw lamang
hindi pagpunta sa ma- makakuha ng higit ito sa ilang mga punto.
At ito ay hugely mahalaga para ma sa hakbang ang layo, bumalik sa susunod na araw,
pumunta sa mga oras ng opisina, post sa CS50 Talakayin o ang gusto, sa aktwal na makakuha unblock.
Kaya panatilihin na sa isip.
Simula sa pinakamaagang panahon ay ang pinakamahusay na bagay na maaari mong gawin.
Kaya dito ay kung saan namin sinimulan klase, higit sa week zero.
At maaari naming makakuha ng isang volunteer dito upang makatulong sa akin mahanap ang mics?
SIGE.
Nakatayo up na.
Lumapit sa up.
Hulaan na kung paano ito ay pagpunta sa trabaho.
Ano ang pangalan mo?
ALAN ESTRADA: Alan Estrada.
David J. MALAN: Alan Estrada.
Lumapit sa up.
Masaya akong makilala kayo.
ALAN ESTRADA: Masaya akong makilala kayo.
David J. MALAN: At ikaw ay dito sa amin sa linggo zero, siyempre.
ALAN ESTRADA: ako ay.
Ako ay.
>> David J. MALAN: Kaya ikaw ay maaaring pumunta magpatuloy at hanapin para sa amin Mike Smith,
nang mas mabilis hangga't maaari mo?
Nang mas mabilis hangga't maaari mong.
Literal mapunit ang problema sa kalahati ng iyong kailangan sa.
>> ALAN ESTRADA: Um.
David J. MALAN: Literal mapunit ang problema sa kalahati.
>> ALAN ESTRADA: Oh.
Mm.
Napakabuti.
>> David J. MALAN: OK.
Good.
Salamat.
ALAN ESTRADA: Napakaganda.
SIGE.
>> David J. MALAN: At kaya ngayon, na iyong whittled ito pababa
sa kalahati ang laki ng problema.
Ngayon, hindi namin down sa isang quarter.
Ikaw ba ay nagbabayad ng pansin sa kung aling bahagi Pinananatili namin?
>> [Tumatawa]
>> ALAN ESTRADA: Oo, think-- ko
>> David J. MALAN: Ano section kami ay nasa?
ALAN ESTRADA: Mufflers, kaya.
>> David J. MALAN: OK.
Ngunit Mike Smith ay pagpunta upang maging pagkatapos Mufflers.
So--
>> [Tumatawa]
>> Lahat tama.
ALAN ESTRADA: Saan tayo naghahanap?
David J. MALAN: Mike Smith.
ALAN ESTRADA: Mike Smith.
David J. MALAN: Ngayon, hindi namin sa surgical.
Ngayon, ang mga manggagamot.
Now--
>> ALAN ESTRADA: pumunta sa real Let's- ipaalam.
Real.
>> David J. MALAN: Real.
SIGE.
Kung kailangan mo ng Real.
Ngayon, kung aling paraan ay Mike Smith?
>> ALAN ESTRADA: Sa ganitong paraan.
>> David J. MALAN: Aling paraan?
ALAN ESTRADA: Maghintay.
M is-- right?
Sinimulan na naming with--
>> David J. MALAN: Oo.
Sila ay iniwan.
Ang iyong karapatan.
>> ALAN ESTRADA: Oo.
>> David J. MALAN: Kaya ni Mike sa dito.
ALAN ESTRADA: Ano?
>> [Tumatawa]
>> Masamang halimbawa, guys.
Sorry.
David J. MALAN: Ito ay magturo mong tumalon sa labas ng iyong upuan.
>> ALAN ESTRADA: Oh.
Oh.
Nakatanggap ako sa iyo.
Oh.
Ito is-- OK, ang nakuha ko sa iyo.
Smith karapatan dito?
>> David J. MALAN: Smith, salamat sa iyo.
Kaya kailangan ko panatilihin ang hinahanap up Smith?
>> ALAN ESTRADA: Oh, oo.
Hindi, hindi, hindi.
Oh hindi.
Ito ay akin.
>> David J. MALAN: Oh, nakuha mo Smith.
SIGE.
>> ALAN ESTRADA: Oo, ako Nakakuha Smith karapatan dito.
Paumanhin, guys.
Akala ko Michael-- namin hinahanap Michael.
Sorry.
>> David J. MALAN: Ito ay OK.
Lahat ng karapatan, ngayon kami ay sa Paccini at anak.
>> ALAN ESTRADA: Paccini at mga anak.
David J. MALAN: Tanging at ako ay sa sa mga ito.
SIGE.
Hanapin sa amin Mike Smith.
Smith.
>> ALAN ESTRADA: Smith.
>> David J. MALAN: Smith.
Humihingi kami sa R ​​para sa basura.
ALAN ESTRADA: basura.
Oh.
Ito ay pagpunta sa tumagal ng isang habang.
>> [Tumatawa]
David J. MALAN: Shoes.
Humihingi kami sa shoes.
>> ALAN ESTRADA: Ngayon kami ay gonna--
>> David J. MALAN: Nice.
ALAN ESTRADA: Which--
[Tumatawa]
Oh, ito ay mahusay.
[Tumatawa]
>> David J. MALAN: Ito ay OK.
>> ALAN ESTRADA: Oh, ito ay mabuti.
Hindi sa tingin ko ako pagpunta sa Mayroon PSAT buddies matapos na ito.
David J. MALAN: Magandang.
Sporting.
ALAN ESTRADA: Kagamitan.
Um, L, M, N, O, P.
David J. MALAN: OK.
Kaya natin mapunit na ito sa kalahati ipaalam.
Ito ay OK.
Ito ay nagtatapos ng hindi maganda pa rin, dahil Mike Smith ay hindi sa mga kulay-dilaw na mga pahina.
>> ALAN ESTRADA: Aw.
>> David J. MALAN: Hindi, ito ay OK.
Ngunit sabihin magpanggap tulad ng ipaalam siya ay sa pahinang ito.
Kaya ngayon, mo na whittled ang problema down sa isang pahina, at natagpuan namin ang Mike Smith.
>> [Pagpalakpak]
Sige salamat.
SIGE.
Iyon ay kahanga-hanga.
Ngunit ito ay pa rin mas mabilis kaysa sa linear paghahanap,
kung saan namin magsimula sa simula ng libro,
at lumipat kami sa aming mga paraan mula kaliwa hanggang kanan, kalaunan ay naghahanap para sa Mike Smith.
At kaya, kung ang telepono ng libro Nagkaroon siguro 1,000 mga pahina,
marahil ito ay kinuha sa amin ng 10 o kaya mga luha page.
>> Ngunit kayo ay maaaring may leveraged hinawakan ng isang palagay
sa panahon ng lahat ng iyon, na ang ibig sabihin na ang telepono ng libro nang maaga ay kung ano?
Madla: Pinagbukud-bukod.
David J. MALAN: Ito ay pinagsunod-sunod.
Right?
Ito ay inayos ayon sa alpabeto, kaya na ang lahat ng mga pangalan at mga numero
ay pinagsunod-sunod mula sa A sa Z, at ayon sa alpabeto sa pagitan.
Ngunit ngayon, kami ay magtatanong ngayon ang tanong, well,
paano ginawa Verizon o ang telepono kumpanya makakuha ng ito sa na estado?
>> Dahil ito ay isang bagay na pagkilos na palagay, at sa gayon,
malutas ang isang problema sa isang algorithm nang mas mahusay.
Ngunit hindi talaga namin tinanong sa linggo zero, well,
kung magkano ay ito gastos Verizon o ng ibang tao
upang makakuha ng na libro ng telepono sa inayos order?
>> Right?
Hindi mahalaga kung naghahanap up Mike Smith
ay sobrang mabilis, kung ito ay magdadala sa iyo ng isang taon upang pagbukud-bukurin sa una ang mga pahina.
Right?
Maaaring gusto mo rin salain lamang sa pamamagitan ng isang randomized phone book,
kung ito ay magiging sobrang mahal upang ayusin ito.
Kaya kung kami ay maaaring magkaroon ng isa pang volunteer.
Magpahinga ng isang tumingin hanggang dito sa kung paano namin might-- puntahan up-- paano
maaari naming pumunta tungkol sa pag-uuri ng mga ito.
>> At kung Jordan maaaring aktwal sumali sa amin dito sa entablado.
Lumapit sa up para sa isang sandali lamang.
Ano ang pangalan mo?
CAROLINE: Caroline.
David J. MALAN: Caroline, dumating sa up.
At kayo ay sumali sa pamamagitan ng sa akin at sa Jordan dito.
Caroline, salamat.
Lahat tama.
Kaya kung ano ang mayroon kami dito para sa Caroline ay 26 blue libro
na FAS gumagamit upang tumulong tiyak na huling pagsusulit.
Ang mga ito ay pagkuha ng mahirap upang mahanap, ngunit ano ang ginawa namin in advance
ay na ilalagay namin ang pangalan ng isang tao sa harap ng bawat isa sa mga ito,
ngunit ko itinatago namin ito sa pamamagitan ng simpleng pagkatapos paglalagay sa labas ng buong pangalan.
Kaya gusto naming ilagay ang tao na may pangalan L, D, J, B, ang lahat ng paraan A sa pamamagitan ng Z,
ngunit ang mga ito sa random order.
At kaya kung gusto mo, pakikipag-usap sa iyong paraan sa pamamagitan ng mga problema tulad ng sa iyo
gawin ito, maaari mong sige, at ayusin ang mga ito para sa amin, mula A hanggang Z.
>> Madla: OK, kaya L ay gusto mo, sa gitna.
C ay simula.
B. J bago L. B, Q.
>> David J. MALAN: Pindutin ng matagal na Naisip para sa isang segundo.
Dahil kung hindi man, ito ay lamang kawili-wili sa iyo, sa akin, at Jordan.
Mayroon kaming pumunta.
Madla: [hindi marinig].
R.
David J. MALAN: OK.
Ano ang iyong ginagawa?
>> CAROLINE: M dumating pagkatapos ng O.
>> David J. MALAN: OK.
>> CAROLINE: O.
David J. MALAN: Oh, Good.
>> CAROLINE: E.
>> David J. MALAN: E, F. Oo.
>> CAROLINE: T, U, V.
>> David J. MALAN: V, T, U, V. Kaya ito Mukhang ikaw making-- panatilihin ang pagpunta.
Mukhang ikaw ay gumagawa ng isang malaking tumpok sa paglipas dito,
at uri ng isang malaking pile doon.
Kaya ang unang kalahati ng alpabeto, ikalawang kalahati ng alpabeto.
SIGE.
Good.
Uri ng malakas ang problema sa dalawa.
M, N, X. Oo.
CAROLINE: K.
David J. MALAN: OK.
K. So uri ng pumipili ka mga ito ng isa-isa,
paglagay ito sa alinman sa kaliwa o kanan, o Z ng pagpunta sa sahig.
SIGE.
>> CAROLINE: Z ang nangyayari sa sahig.
>> David J. MALAN: OK.
Y ay pagpunta sa sahig.
Ngayon ay maaari naming ilagay ang X.
>> CAROLINE: G.
David J. MALAN: G pagpunta sa kaliwa.
S ay pagpunta kanan.
Lahat ng mga karapatan, A ay nangyayari sa lahat ng mga paraan sa kaliwa.
>> CAROLINE: A, B, C, D.
>> David J. MALAN: Ngayon, mabuti.
Mayroon kami ng A, B, C. W pagpunta doon.
Lahat ng mga karapatan, T.
>> CAROLINE: H, I, J.
David J. MALAN: H, I, J. Good.
CAROLINE: Sa gitna, ako gonna--
David J. MALAN: OK.
Kaya ngayon, kami ay pagpunta sa uri ng pagsamahin ang mga iba't-ibang mga piles.
Kaya A sa pamamagitan ng C, pagkatapos ko makita D, at E, at F, at G, at H, at I. Nice.
J, K. At pagkatapos, ito tumpok ay baligtad, ngunit iyan ay OK.
Oo naman.
Maaari naming i-cut ilang mga sulok.
SIGE.
At pagkatapos ay kailangan naming W, X, Y, Z.
>> CAROLINE: Oo.
>> David J. MALAN: Magaling.
Kaya isang malaking salamat sa Caroline para sa pagbubukod-bukod ng mga ito.
>> [Pagpalakpak]
>> Salamat.
Maraming salamat.
Kaya ngayon isaalang-alang para sa isang sandali Kung paanong ang Caroline tungkol sa paggawa na,
at kung ano ang eksaktong namin Nagawa to-- kung paano namin
nagawang lutasin na kapag problema kami ay lamang
bibigyan ng isang buong grupo ng mga random na input.
>> Well, mukhang walang ay isang piraso ng isang sistema doon?
Right.
Kaya ang mga naunang mga titik sa alpabeto, siya
ay paglagay sa kaliwa, at ang mamaya mga titik sa alpabeto,
siya ay paglagay sa kanan.
At sa lalong madaling siya natagpuan ilang proximal mga titik, mga
na pumunta sa tabi mismo ng isa't isa, siya ay ilagay ang mga order.
At kaya namin uri ng nagkaroon ng mga maliliit tambak na pinagsunod-sunod na mga input sa nangyari.
>> At kaya na lubos na tulad ng kung ano ang karamihan ng mga tao sa amin ay gawin.
Gusto namin ang uri ng suriing mabuti sa pamamagitan ng ito, at gusto naming uri ng magkaroon ng isang mekanismo.
Ngunit maaaring maging mahirap na isulat down na ito sa isang formula per se.
Ito nadama ng kaunti pa sa organic kaysa.
Kaya sabihin makita kung maaari naming ngayon bound ang mga problema sa mas kaunting input.
>> Sa halip na 26, sabihin gawin ang isang bagay malayo mas kaunting
may sabihin lang, pitong, sa likod mga pinto, kaya na magsalita.
Mayroon lamang pitong mga numero?
At kung ang layunin na ngayon sa kamay ay upang mahanap ang isang halaga,
sabihin makita kung paano mahusay maaari naming pumunta tungkol sa paggawa nito.
At makita kung maaari naming ngayon hayaan magsimula na mag-aplay ng ilang mga numero,
o ang ilang mga formula na kung saan upang ilarawan ang kahusayan ng aming phone book
algorithm, ang aming algorithm aklat pagsusulit, at higit pa sa pangkalahatan, sa paghahanap ng impormasyon.
>> Kaya para sa mga ito, hayaan mo akong magpatuloy, at ang touch screen sa paglipas dito,
maglagay ng isang web browser na may eksakto ang mga pitong pintuan.
At kung kami ay maaaring makakuha ng isa sa iba pang mga magboluntaryo upang dumating sa paglipas dito,
Naglagay ako ng mga parehong mga pinto sa paglipas dito.
Quick volunteer.
>> Ito one-- demo ay pagpunta sa isang mas mabilis at mas mabilis na ngayon.
Halika sa down.
Ano ang pangalan mo?
TREVOR: Trevor.
>> David J. MALAN: Trevor?
Sige, Trevor, dumating sa pababa.
Kaya Trevor ay nagboluntaryo para gawin ng isang katulad na problema, ngunit isang bagay na
makitid sa saklaw, at na ang nangyayari sa daan sa amin upang subukan upang gawing pormal ngayon
ang proseso para sa pag-uuri ng mga numero.
>> Kaya Trevor, Natutuwa akong makilala kayo.
Kaya dito ay isang array, para sa magsalita, isang listahan ng mga pitong pintuan.
Sige at hanapin sa amin ang numero 50.
At pagkatapos ay pagkatapos ng katotohanan, sabihin sa amin kung paano mo natagpuan ito.
Dapat be-- lahat ng karapatan.
Oo, ito ay ang isa dito?
Naku.
SIGE.
Nag-click ka na ang isa.
Good.
>> At mabuti.
Ngayon mo na-click ang isa.
At ipaalam sa akin magbibigay sa iyo ng mikropono, upang ikaw ay may mga ito sa ilang sandali lamang.
Sige at i-click ang sa tabi ng pinto na iyong balak.
Oo, magaling.
TREVOR: Maaari ko bang unclick isang pinto?
David J. MALAN: Hindi, hindi mo maaaring unclick.
TREVOR: OK.
Itong isa.
David J. MALAN: Saan mo gustong pumunta?
Alin?
>> TREVOR: Ang isang iyon.
>> David J. MALAN: No.
>> TREVOR: OK.
Itong isa.
>> David J. MALAN: Oo.
Iyon ay mabuti.
Lahat tama.
Kaya kung ano ang iyong algorithm o pamamaraan para sa paggawa nito, Trevor?
>> TREVOR: ko lang nagpunta sa pamamagitan ng pinto hanggang sa nakita ko ang isang 50.
David J. MALAN: OK.
Magaling algorithm.
Kaya na multa.
Dahil sa katunayan, kung ibunyag ko kung ano ang sa likod ng mga ito ng dalawang iba pang mga pinto, kung ano
kami makahanap dito ay na lamang kami ay may random input.
Kaya na ay tulad ng aktwal na mabuti bilang maaari mong makuha.
At sa katunayan, nakakuha ka ng mas mahusay kaysa exhaustively sinusuri ang buong array,
dahil ito ay talagang buwisit na kung ikaw ay pindutin ang numero ng
50 sa huling pinto.
Ngunit paano kung namin sa halip ay nagbigay sa iyo ng isang palagay.
Ipagpalagay ko maisasa-ayos ang lahat ng ang mga pinto sa paligid,
upang ikaw ay may mga numero inayos oras na ito,
ngunit oras na ito ito ay aktwal na isang different-- oras na ito,
tunay na ito ay pinagsunod-sunod para sa iyo.
At ngayon, ang layunin sa kamay ay na matumbok ang bilang 50.
>> TREVOR: OK.
>> David J. MALAN: Ano ang iyong algorithm magiging?
>> TREVOR: Well, kung ito ay inayos, ito ay alinman sa pagpunta
upang be-- kung pinakamalaking sa pinakamalaking, pababang, makikita ito ay ang unang isa,
o kung ito ay ang kabaligtaran, ito ay ang huling isa.
Kaya makikita lamang i-tap ko ang pinto, at pagkatapos ay i-tap lamang ang huling pinto.
David J. MALAN: Magaling.
Lahat tama.
Kaya nakita namin ang bilang 50.
Kaya sa lalong madaling alam mo sila ay inayos, namin
nagawang pagkilos na ito palagay.
Kaya ang mga ito ng masyadong maraming tulad mga halimbawa phone book.
Sa sandaling mayroon ka, kahit na may isang maliit na problema na tulad nito,
pre-nakaayos ang iyong mga input, maaari naming talagang mahanap ang halaga arguably
mas mahusay.
>> At hindi ko sabihin sa iyo kung ito ay inayos sa maliit sa malaki, o malaki sa maliit,
at sa gayon ito ay napaka-makatwirang upang magsimula sa isang dulo o sa iba pang
upang aktwal na makita na ang target na halaga.
Kaya salamat pati na Trevor.
At makikita ko propose-- mabuti tapos na.
Kami ay may isang maliit na clip, talaga, na ay kabilang sa aming mga paboritong sandali sa CS50,
kung saan minsan ang mga demo hindi lubos na pumunta ayon sa plano.
At sa katunayan sa ngayon, ako nakuha up sa mga maling interface
na kung saan upang gamitin ang touch screen.
Kaya na ay ang aking mga kasalanan doon.
>> Kaya ito ay gumawa para sa clip ng susunod na taon bilang
sa kung bakit ako ay pag-click sa aking sariling mga screen.
Ngunit tumagal ng isang mabilis na pagtingin hayaan sa kung ano ang nangyari noong nakaraang taon
Jay, na dumating up, marami tulad Trevor dito, nagboluntaryo,
at sa maikling clip, makikita mo ang paano ginawa hindi lubos na ito parehong demo
ibunyag ang parehong mga aralin natutunan.
[Playback ng video]
-Ang Lahat ng gusto ko sa iyo na gawin ngayon ay upang mahanap para sa akin, at para sa amin,
talaga, ang bilang ng 50 isang hakbang sa isang pagkakataon.
>> -Ang Bilang 50?
>> -Ang Bilang 50.
At maaari mong ipakita kung ano ang sa likod ng bawat isa sa mga pinto
sa pamamagitan lamang ng pagpindot ito gamit ang isang daliri.
Mapapahamak ang mga ito.
>> [Tumatawa]
>> [END playback]
David J. MALAN: Kaya na nagpunta napakahusay.
Yaong ang mga unsorted pintuan.
At Jay, siyempre, masyadong mabilis na natagpuan ang lahat ng ito.
Trevor ay isang mas mas mahusay na trabaho sa mga tuntunin ng isang madaling ituro sandali,
wika nga, sa taong ito sa mas matagal upang hanapin ito.
Siyempre, pagkatapos ay nagbigay kami Jay ng pangalawang pagkakataon,
kung saan inayos namin ang mga pinto, tulad ng ginawa namin para sa Trevor,
at Trevor ay super rin oras na ito.
Ngunit ito Jay half nang mabilis.
[Playback ng video]
-Ang Layunin ay ngayon upang din hanapin sa amin sa bilang 50,
ngunit gawin ito algorithmically, at sabihin sa amin kung paano ka ng pagpunta sa.
>> -SIGE.
>> -At Kung iyong makita ito, ingatan mo ang pelikula.
Kung hindi mo mahanap ito, binibigyan mo ang mga ito pabalik.
>> -Man.
>> -Oh!
>> - [Hindi marinig] OK.
Kaya ako pagpunta upang suriin ang mga dulo unang upang matukoy kung there's-- Oh.
>> [Palakpakan]
>> [END playback]
David J. MALAN: OK.
Kaya sa pag-uuri ng malinaw na pinto hahantong sa higit na kahusayan.
At ito, dalawang beses nang mas mabilis ay kung ano ang ibig sabihin ko doon.
At kaya Jay got mapalad parehong oras.
At siya ay nakuha din sa mapalad na ang huling taon, iniutos ko ang ilang mga Blu-ray discs
upang aktwal na bigyan out.
Sorry sa taong ito, kami ay ay hindi magkakaroon ng parehong, Trevor.
Ngunit ay mas mahusay pa rin ng ilang taon likod.
At maaaring kilala ang ilan sa iyo na ito kapwa, Sean, na kapag siya ay sa CS50,
ay hinamon na may eksaktong parehong problema, kahit na sa SD,
tulad ng makikita mo agad makita, pabalik sa araw.
At makikita mo na hindi lamang ay siya ay kumuha ng isang maliit na mas mahaba kaysa sa Jay,
isang maliit na mas mahaba kaysa sa Trevor, ito ay tunay na ito kahanga-hangang pagkakataon
upang hikayatin ang halos lahat ng tao sa karamihan ng tao a la Presyo ay Kanan, na naghihikayat sa
sa kanya upang mahanap ang numero ng aming hinahanap.
Sabihin. kumuha ng isang mabilis na pagtingin.
>> [Playback ng video]
>> -SIGE.
Kaya ang iyong mga gawain dito, Sean, ay ang sumusunod.
Ako ay may nakatago sa likod ng mga pinto sa bilang pitong.
Ngunit nakatago ang layo sa ilan sa mga pinto pati na rin ang mga iba pang mga negatibong numero.
At ang iyong layunin ay upang mag-isip ng tuktok na hilera ito ng mga numero
bilang lamang ng isang array, o lamang pagkakasunod-sunod ng mga piraso ng papel
na may mga numero sa likod ng mga ito.
At ang iyong layunin ay, lamang gamit ang top array dito, hanapin sa akin ang numero ng pitong.
At kami ay pagkatapos ay pagpunta sa pumupuna kung paano mo pumunta tungkol sa paggawa nito.
-Lahat tama.
-Find Sa amin ang numero ng pitong, please.
Hindi.
Five, 19, 13.
>> [Tumatawa]
>> Ito ay hindi isang nanlilinlang tanong.
One.
>> [Tumatawa]
Sa puntong ito, ang iyong iskor ay hindi masyadong mabuti, sa gayon ay maaari mo rin panatilihin ang pagpunta.
Three.
>> [Tumatawa]
>> Ipagpatuloy mo.
Lantaran, hindi ko maaaring makatulong ngunit magtaka kung ano ang kahit na ang iyong iniisip tungkol sa, so--
>> [Tumatawa]
Hanay sa itaas na lamang, para Mayroon tatlong kaliwa.
Kaya mahanap ako ng pitong.
>> [Tumatawa]
17.
Pitong.
>> [Palakpakan]
>> Lahat tama.
>> [END playback]
>> David J. MALAN: Kaya maaari namin panoorin ang mga buong araw.
At siyempre, ang ilan sa demo na ito taon marahil
ay ngayon ay napupunta sa susunod na video taon pati na rin.
Kaya ngayon sabihin aktwal focus sa mga algorithm
dito, at makita kung ito ay hindi natin ngayon simulan upang gawing pormal
kung paano namin pumunta tungkol sa pagkuha ng aming data sa estadong ito na ito ay pinagsunod-sunod,
para sa kalaunan, maaari naming aktwal maghanap ng mas mahusay.
At kahit na kami ay pagpunta gamitin medyo maliit na set ng data,
tulad ng mga walong numero namin Mayroon dito sa board,
sa huli ay maaaring gamitin ang mga parehong mga ideya sa 1,000 na input, isang milyong input,
4 na bilyon na input, dahil ang algorithm ay magiging panimula ang parehong.
>> At kaya ito ay ang aming huling pagkakataon para sa mga boluntaryo na ngayon,
ngunit marahil ang isa sa pinaka-kasangkot, para sa kung saan kailangan namin ng walong volunteers
na dumating up at paglalakad sa amin sa pamamagitan ng mga proseso ng pag-uuri sa kung ano ang sa lalong madaling panahon
maging sa mga music nakatayo dito.
Hayaan akong magsimula bumalik dito.
>> Kaya isa sa turquoise-- green ito?
Ikaw ba gumawa?
Dalawang.
Halika sa down.
SIGE.
Three.
Four.
Hayaan me-- OK, lima.
Na kayo ay hinirang ng iyong kaibigan.
Anim, pito, walo.
Lumapit sa up.
Lahat tama.
Salamat sa iyo kaya magkano.
Lumapit sa up.
>> Lahat tama.
Kaya kung ano ang mayroon kami here-- at ito ay kabilang sa mga mas mahirap na mga,
dahil ito ay kailangan na ikaw katatawanan sa akin lamang ng isang maliit na piraso ng oras.
Ikaw ay magiging bilang isa.
Ano ang pangalan mo?
>> ANNAN: Annan.
>> David J. MALAN: Annan.
David.
Ano ang pangalan mo?
>> JOSEPH: Joseph.
>> David J. MALAN: Joseph, mga numero ng dalawang mo.
>> SERENA: Serena, numero ng tatlong.
Stefan, bilang apat.
CYNTHIA: Cynthia.
David J. MALAN: Cynthia, numero ng limang.
[Hindi marinig]
David J. MALAN: [hindi marinig].
David, numero ng anim.
MATT: Mat.
David J. MALAN: Matt numero ng pitong.
At?
>> WAVERLY: Waverly.
>> David J. MALAN: Waverly, numero ng walong.
Lahat tama.
Kung could-- ka Oops.
Kung sa iyo ang lahat, tulad ng iyong unang hamon, may
mga walong kinatatayuan musika nakaharap dito ang madla.
Kung maaari mong ilagay ang iyong numero sa mga music nakatayo sa paraan
na line up nila sa mga parehong numero sa board.
Kaya gumawa ng sarili hitsura na sa pamamagitan ng paglalagay ng iyong mga numero sa mga music
nakatayo dito.
Magaling sa ngayon.
>> Magaling.
SIGE.
Kaya ngayon, kami ay pagpunta sa hilingin sa mga tanong sa loob ng ilang iba't-ibang paraan.
Paano namin pumunta tungkol sa pag-uuri dito ang mga tao up?
Dahil nagkaroon kami ng ilang mga pamamaraang mas maaga, kung saan tayo ay
uri ng paggawa ng dalawang magkaibang mga bucket.
At pagkatapos kami ay sa pangkalahatan piecing bagay nang magkakasama.
Nang makita kami ng dalawang mga numero na pag-aari sama-sama,
inilalagay namin ang mga ito nang magkakasama.
Dalawang titik na pag-aari sama-sama.
>> Ngunit sabihin makita kung kami hindi maaaring gawing pormal ito,
kaya na namin sa huli ay may ilang tunay code ay sa iyo,
na kung saan maaari mong malutas ang mga problemang ito.
Kaya ngayon, Naghahanap ako ng out sa mga numerong ito dito.
At nakikita ko ang maramihang mga pagkakamali.
Sa huli, gusto ko ang isa sa mga kaliwa at walong sa kanan.
>> At kaya Naghahanap ako sa mga dalawang, apat at dalawa.
At ano ang problema, malinaw naman?
Oo.
So.
Dalawang malinaw na hinango bago apat, sa gayon alam mo kung ano?
Hayaan akong unang kumuha ng isang sakim na diskarte, kung ikaw ay, magkano ang gusto problema
itakda one-- kung isipin mo mula sa Standard Edition ng Problema Itakda One,
kung saan ko lang sa local na malutas ang problema na dito mismo sa harap ng akin
at makita kung saan ito ay humahantong sa akin.
>> SIGE.
Kaya dalawa at apat, hayaan mo akong magpatuloy at lang magpalit ka dalawa.
Kung maaari mong pisikal na ilipat inyong sarili at ang iyong papel,
Mukhang ako na may tapat na paraan ng ilista sa isang mas mahusay na estado.
>> Ngayon, ang mga ito ay mabuti.
Pupunta ako upang ilipat sa, apat at anim, mukhang maganda.
Hindi problema.
Anim walo, OK.
Eight at isa, isa pang problema.
Dahil kung ano ang totoo tungkol sa walong at isa?
One dumating bago walo, at kaya kung ano ang dapat naming gawin?
Magpalitan ng mga dalawang.
One walo.
At ngayon, ako pagpunta sa panatilihin ang pagpunta.
Pupunta ako sa panatilihin ang hinahanap nang mas maaga.
At makita kung ano ang mangyayari.
Eight at tatlong, ng Siyempre, sa labas ng order.
Ni swap Hayaan.
Eight at pitong, siyempre.
Mula sa order.
Ni swap Hayaan.
Eight at limang, siyempre, sabihin swap.
Lahat tama.
Listahan ay pinagsunod-sunod.
yes?
>> OK, malinaw naman hindi.
Ngunit ito ay isang maliit na mas mahusay, tama?
Dahil kung ano ang notice nangyari.
Sa bawat oras na namin ginanap sa isang swap, isang mas maliit number percolated uri ng na paraan,
at ang isang mas malaking bilang percolated ganitong paraan, o bibigyan namin ng
simulan sinasabi bubbled sa pakaliwa o bubbled sa kanan.
>> Ngayon, ito ay hindi sapat, dahil sa pinakamahusay na isang numero ng kapangyarihan
Inilipat sa isang lugar pasulong, o sa pinakamalala,
ay maaaring magkaroon ng isang bilang inilipat sa isang spot sa karagdagang.
Kaya alam mo kung ano ang, uri na ito ng medyo maayos na nagtrabaho sa ngayon.
Hayaan lamang na subukan uli ako dito.
Dalawang at apat na, ang mga ito ay OK.
Apat at anim na, ang mga ito ay OK.
Anim at isa, sa labas ng order.
So magpalit ni kang dalawang ipaalam.
At ngayon, mapapansin ang problema ni simula upang makakuha ng isang maliit na mas mahusay na muli.
Anim at tatlong, sa labas ng order.
Swap ni mo dalawang.
Anim at pitong, ikaw ay mabuti.
Pitong at limang, siyempre, sa labas ng order.
Seven at walong, sa order.
At ngayon, maaaring kailangan ko upang gawin ito ng ilang higit pang mga beses.
At sa katunayan, sa tingin para sa inyong sarili marahil kung gaano karaming beses maximally
baka ako kailangang maglakad papunta at pabalik?
>> Susubukan naming bumalik sa mga iyon.
Kaya dalawa at apat na mga OK pa rin.
Apat at isa, nope.
Kaya, swap ipaalam.
At muli, napansin biswal isa ay uri ng bulubok
sa kaliwa, kung saan ito ay dapat.
Apat at tatlong swap.
Apat anim.
Anim at limang swap.
Anim at pitong.
Seven at walong ay mabuti.
>> Good.
Kahit na mas mahusay Kami ay nakakakuha.
Kaya sabihin makita.
Ngayon, kami ay may dalawa at isa.
Siyempre, magpalit.
Dalawang at tatlong, tatlo at apat, apat at lima, anim at pito, pitong walo.
Good.
At alam mo kung ano?
Dahil ginawa ko ng isang pagbabago doon, hayaan mo akong gawin ang isa katinuan check.
Hayaan akong pumunta sa lahat ng paraan bumalik sa simula.
SIGE.
One, two-- yup, tingnan?
Isang bagay ay mali.
Tatlo, apat, lima, anim, pitong, walong.
At sa mga huling pass, ay ikaw ay komportable sa aking ngayon
pagtubos ng ito ay pinagsunod-sunod?
SIGE.
Biswal na, na ang ganap na totoo.
Ngunit sa pagtakbo, kung ano nag ring mangyari lamang
sa huling na pass na nagpapahintulot sa iyo upang kumpirmahin na ang listahan na ito ay sa katunayan
Inayos?
>> Ano ang gagawin ko o hindi gawin ito huling pass?
Madla: Walang pagbabago.
David J. MALAN: Paumanhin?
Madla: Walang pagbabago.
David J. MALAN: Walang pagbabago.
Kaya magiging bobo ko na muli gawin na parehong algorithm
kung ako ay hindi gumawa ng anumang mga pagbabago sa unang pagkakataon.
At ang estado ay hindi nagbago.
Tiyak, hindi ako pagpunta sa gumawa anumang mga pagbabago sa ikalawang pagkakataon.
At ito, ito ay ligtas na ngayon sabihin, listahan ay nakaayos.
>> At sa katunayan, ito ay ngayon isang bagay na ipapakita namin sa pangkalahatan
call bubble sort, kung saan pairwise, itama mo pagkakamali muli,
at muli, at muli, at ikaw ay panatilihin ang pagpunta papunta at pabalik,
at pabalik-balik, hanggang sa ikaw ay gumawa ng walang tulad swaps, at sa puntong
maaari kang maging kumpyansa, oo, ako tapos sa pag-aayos ng lahat ng mga pagkakamali.
Ni-reset at subukan ang ibang diskarte.
Kung ikaw guys maaaring bumalik sa ang order na kayo ay isang sandali ang nakalipas,
na mukhang ito.
Ngayon, sabihin kumuha ng isang diskarte ng kaunti pa tulad ng mga libro pagsusulit,
kung saan kami ay patuloy na pagpili sa titik ng alpabetong
na uri ng namin pinaghahanap upang harapin ang susunod.
Siguro, ito ay isang mataas na sulat, tulad ng A, o isang mababang sulat Z.
>> Kaya lahat ay bumalik sa ayos na ito.
At ngayon hayaan mo akong gawin ito.
Tingnan natin kung alam ko ako Hayaan walong numero dito.
Pupunta ako sa sige at sadyang piliin lamang
ang pinakamaliit na elemento.
Right?
Ito ay tila masyadong intuitive.
Bakit hindi ko mahanap ang pinakamaliit element, ilagay ito kung saan ito ay kabilang,
pagkatapos makuha ang susunod na pinakamaliit na elemento, ilagay ito kung saan ito ay kabilang, at ulitin lamang.
>> Dahil intuitively, na dapat gumana masyadong.
Kaya apat, na ang isang medyo maliit na bilang.
Pupunta ako sa tandaan kung saan ito ay.
Sandali lang.
Dalawang ay mas maliit.
Hayaan alalahanin mo ako ngayon kung saan ang dalawang ay, at kalimutan ang tungkol sa apat.
Susubukan naming haharapin ang mga iyon sa ibang pagkakataon.
Anim na, hindi ako interesado.
Eight, hindi ako interesado.
Isa ang aking bagong maliit na bilang.
Kaya ako pagpunta sa tandaan kung saan ang isa ay.
Three, hindi interesado.
Seven, hindi interesado.
Limang, hindi interesado.
>> Kaya walang lagas ang yugto sa taong ito,
Pupunta ako sa grab number one-- at kung ano ang muli ay ang pangalan mo?
>> ANNAN: Annan.
>> David J. MALAN: Annan.
At kung kayo ay sumali sa akin sa sa simula ng listahan,
Maglagay mo kung saan ka nabibilang ipaalam.
Unfortunately-- ano ang pangalan mo?
>> STEFAN: Stefan.
>> David J. MALAN: Stefan ay sa paraan.
Kaya bago Stefan malulutas nito ang Ang problema, ano ang dapat naming gawin?
Ano ang gagawin namin sa Stefan?
>> Madla: [hindi marinig].
David J. MALAN: OK.
Kaya maaari naming gawin iyon.
Kami ay maaaring uri ng tumagal Stefan at ang kanyang apat, at lamang ilagay ito sa isang variable
at kumapit sa mga ito para sa ilang mga halaga ng oras,
sa gayon ang paggawa ng room para sa isang numero.
At iyan ay hindi masama.
Maaaring Mungkahi ko, bakit hindi ilagay lang namin Stefan dito?
Bakit maaaring lumalabag sa isang ito ng mga ideya namin na nagsimula
pakikipag-usap tungkol sa huling panahon, noong nakaraang linggo?
Oo?
>> Madla: [hindi marinig].
>> David J. MALAN: Walang index para sa mga ito.
Kung sa tingin mo ng mga ito, sa katunayan, bilang isang array, ito ay tulad ng negatibong isa,
kaya walang memory talaga dito kung ito nga ay isang array,
tulad ng ipinahayag namin noong nakaraang linggo sa panayam.
Kaya hindi namin dapat gawin ito.
Maaari naming iimbak ito sa isang variable.
>> O alam mo kung ano?
Narinig ko ang ibang tao iminumungkahi ito.
Ano pa ang maaari naming gawin sa Stefan?
Bakit hindi paalisin namin siya lamang at inilagay siya sa kung saan bilang isa ay.
Kaya kung nais mong pumunta doon.
At sa katunayan, ito ay isang pretty magandang solusyon.
Ngayon sa isang banda, na ako ng uri ng ginawa ang problema mas masahol pa.
Apat na ngayon ang mas malayo mula sa kung saan ito ay dapat.
Ito ay dapat na ito papunta sa kalahati.
>> Pero alam mo kung ano?
Na maaaring naging masamang kapalaran.
Siguro bilang walong ay dito.
At ito, marahil gusto namin nakuha masuwerteng,
at itinulak walong mas malapit sa dulo.
Kaya sa katapusan ng araw, ito uri ng lahat out katamtaman.
Hindi natin kailangan sa pag-aalaga tungkol sa apat.
Lahat ng pag-aalaga ko tungkol sa ngayon ay pagpili ng pinakamaliit na elemento.
>> At ngayon, kung ano ako ng pagpunta sa gawin ay kalimutan ang tungkol sa numero ng isa
permanente, dahil alam ko ang list sa likod ako ay inayos ngayon.
Kaya ang aking list dati ay size walo.
Ngayon, ito ay ang laki ng pito.
Kaya ang aking mga problema ay nakakakuha ng mas maliit, kahit na linear.
Kaya ngayon, ako pagpunta upang piliin ang kasalukuyang pinakamaliit na elemento, dalawa.
Anim, walo, apat, tatlo, pitong, lima.
Iyon ay ang pinakamaliit na elemento.
Kaya kung ano ang ako pagpunta sa gawin with-- kung ano ang muli ay ang pangalan mo?
>> JOSEPH: Joseph.
>> David J. MALAN: Joseph?
Kami ay pagpunta sa umalis Joseph sa lugar.
Ngayon, ako pagpunta upang magpanggap na ang mga guys are-- rin,
Alam ko na ang mga ito ng dalawang ay pinagsunod-sunod.
Hayaan focus ngayon sa naiwan ng listahan.
Anim ay ang kasalukuyang pinakamaliit.
Eight ay mas malaki.
Apat na ngayon ang kasalukuyang pinakamaliit.
Tatlong ngayon ay ang kasalukuyang pinakamaliit.
At kaya ngayon, ako pagpunta upang piliin tatlo, na is-- ano ang muli ang iyong pangalan?
SERENA: Serena.
David J. MALAN: Serena, kung magagawa mong grab ang iyong numero at swap with--
Kalsang: Kalsang.
David J. MALAN: Kalsang.
Lumapit sa likod, at hindi namin pagpunta sa magpalitan ng mga dalawang.
At ngayon, ni ilagay ito sa autopilot ipaalam.
Pupunta ako sa pumunta at mag-iwan ito sa iyo guys upang piliin ang susunod na maliit na mga elemento.
Dun, dun, dun, dun.
Numero ng apat, kung ano ang dapat mong gawin?
Magaling.
Ngayon, ako pagpunta sa gumawa ng isa pang pass.
Dun, dun, dun, dun.
Nakakakita ako ng limang ay ang susunod na pinakamaliit.
Ngayon, ako pagpunta kumuha ng isa pang pass.
Dun, dun, dun, dun.
Anim ay ang pinakamaliit.
Good.
Pitong ay ang pinakamaliit.
Walang pagbabago.
Eight ay ang pinakamaliit.
Tapos na.
>> Kaya kung ano lang namin nagawa sa pamamagitan iteratively pagpili ng isa element matapos ang iba pang
ay ipatupad ang isang bagay na hindi namin pagpunta upang gawing pormal bilang uri selection.
At ito ay marahil kahit na mas simple upang ipaliwanag,
in na literal lahat mo nais na gawin ay panatilihin lamang
balik-balik sa listahan pagpili, ang susunod na pinakamaliit na elemento,
hanggang sa ikaw ay tapos na.
>> Kaya ito ay kahit na mas simple, marahil intuitively, kaysa sa nakaraang.
Subukan natin ang huling ng isa.
Kung ikaw guys ay maaaring i-reset ang inyong sarili sa mga sumusunod na mga posisyon
ng isang pangwakas na oras, tingnan natin kung hindi namin maaari ngayon gawing pormal ang isa sa iba pang mga diskarte.
Sa katunayan, ay isang tao out there nais imungkahi
kung paano pa namin maaaring pumunta tungkol sa paggawa nito?
Walang paghuhugas ang buzzwords o pag-uuri ng mga sagot na nai-kilala,
intuitively lang, kung ano ang maaari naming gawin?
>> Madla: [hindi marinig].
David J. MALAN: Oo.
Kaya may ilang mga mahusay na Swersey doon.
Magandang mga bagay na tila sa mangyayari kaya sa ngayon sa computer science kapag hinati namin
at mapaglabanan ang problema ng paghahati ito sa kalahati at kalahati at kalahati.
At kaya nga, kami ay maaaring simulan upang gawin iyon.
At sa katunayan, iyon ay magiging, ipapakita namin makita, isa sa aming pinakamahusay na solusyon pa.
Ngunit sabihin ay bumalik sa na bago mahaba ipaalam.
Sa katunayan, kami ay pagpunta sa gawin na ang isang maliit na mamaya sa linggong ito.
Ano pa ang maaari naming gawin upang malutas ito?
Kaya lahat ng tao dito ay sa tila random na order.
Alam mo ba?
Sa halip na bumalik-balik, papunta at pabalik, papunta at pabalik
sa bawat oras, ito nararamdaman tulad ng Ako paggawa ng isang pulutong ng mga naglalakad.
Bakit hindi simulan lang ako sa sa simula ng listahan,
at ilagay lamang sa apat na kung saan ito aari?
Kaya hayaan mo akong ipalagay para sa sandaling iyon aking listahan ay lamang ang unang elemento.
Ay apat na pinagsunod-sunod sa panahon na ito sa oras, kung ang lahat ng pag-aalaga ko tungkol dito sa lahat ng bagay?
Ito ay uri ng trivially totoo, di ba?
Tulad ng mga listahan na naglalaman ng isang numero, at na apat na numero ay malinaw naman inayos.
>> Kaya ipaalam magtadhana sa akin lamang na listahan na ito ay pinagsunod-sunod.
Ngunit ngayon ay mayroon akong mga natitira sa listahang ito.
Kaya ngayon, nakatagpo ako ng dalawang.
Saan ang dalawang malinaw naman nabibilang na may paggalang sa apat?
Bago apat.
Kaya kung ano ang maaari kong gawin dito?
Ano ulit ang pangalan mo?
>> JOSEPH: Joseph.
>> David J. MALAN: Joseph, kung maaari mong hakbang likod
para sa sandali lamang ito sa iyong numero.
At ngayon kung ano ang dapat gawin dito Stefan?
Shift ni Stefan sa paglipas dito.
At ngayon, hayaan Joseph pumasok ka dito.
At ngayon, hayaan mo akong i-claim na lahat ng bagay dito ay pinagsunod-sunod.
Kaya, katulad na resulta, ngunit isang panimula iba't ibang mga diskarte.
Hindi ko pa kahit na tumingin kung ano ang down doon.
Katatapos ko lamang panatilihin ang pagkuha ng mga elemento bilang mga ito ay ipinasa sa akin,
at makikitungo sa kanila.
>> Kaya ngayon, nakikita ko ang numero ng anim.
Saan ang numero ng anim na nabibilang?
Mayroon kaming dalawang, apat, anim.
Eksakto kung saan siya ay sa ngayon.
Kaya ng iwan na mag-isa ipaalam, at ngayon paghahabol na ito sa bahagi ng listahan
ay inayos ngayon.
At ito, ang nararamdaman panimula naiiba sa na lang ako
paglipat sa pamamagitan ng listahan dito linearly, at ako ay hindi kailanman pagdodoble likod.
Oo.
Lahat tama.
Kaya walong, saan ka nabibilang?
Dito.
Perpekto.
Kaya ngayon, isa.
Naku.
Ito nararamdaman tulad ng ito ay magiging mahal.
Ngayon, sa mga nakaraang algorithm, Lamang swapped ko ang mga tao.
Kaya maaari ko bang ilagay sa kanya lahat ng mga paraan sa sa simula, ngunit pagkatapos ay inilipat Joseph.
Ngunit kung ilipat ko Joseph, ngayon kung ano ang nangyayari na mali?
>> Ngayon, hindi ko na uri ng undone-- na ko kinuha ng isang hakbang pasulong at pagkatapos ay
isang hakbang sa likod, dahil ngayon Joseph ay sa labas ng order.
Kaya sabihin gawin ito.
Kung maaari kang kumuha bilang isa at hakbang pabalik para sa sandali lamang.
Paano natin put-- ano ay muli ang iyong pangalan?
>> ANNAN: Annan.
>> David J. MALAN: Annan sa lugar?
Ano ang kailangang mangyari na may paggalang sa dalawa, apat, anim, walo?
Lahat sila ay kailangan sa paglilipat.
Kaya kung walong nais na maglipat una, pagkatapos ng anim na, pagkatapos ng apat na, pagkatapos ng dalawang.
At pagkatapos Annan, kung gusto mo sa nais na pumasok ka dito, mabuti.
Ngunit dito, na namin lamang uri ng mga bayad na isang presyo
sa isang iba't ibang mga punto sa algorithm.
Sapagkat huling oras na may seleksyon uri, at kahit na bubble uri,
Ako naglalakad papunta at balik, balik,
na kung saan ay tiyak na pagdagdag up oras-matalino, at literal stepwise.
>> Sort Insertion, sa unang sulyap, kamukha ito
sobrang mas matalinong, sa na lang ako paggawa ng mabagal, incremental-unlad,
ngunit hindi ako pagpunta ito papunta at pabalik.
Ngunit kung ang isang tao ay sa katunayan sa labas ng order, ang paunawa
lahat ng mga trabaho ko lang ay nagkaroon na gawin.
Nagkaroon na ako upang ilipat sa kalahati ng mga listahan lamang na gumawa ng room para sa mga numero ng isa.
Kaya ito ay ang parehong halaga ng trabaho kaya malayo ito
nararamdaman, lamang ng isang iba't ibang mga uri ng trabaho.
>> Ituloy natin.
Kaya ngayon ay alam namin na ang lahat sa pagitan ng isa at walong ay nakaayos.
Dito, ako ay may tatlong numero.
Kung gusto mong i-pick up numero ng tatlong, hakbang likod ng isa.
At ano ang gagawin mo guys kailangan na gawin?
Yep.
Kaya na ang isa pang isa, dalawa, tatlong hakbang.
Tatlong mga yunit ng oras na gastos lamang sa akin, sa gayon ay tatlong ay maaari na ngayong magkasya.
Sa wakas, pitong.
>> Sabihin sige at mayroon ikaw ay kumuha ng isang hakbang pabalik.
Ito ay lamang ang pagpunta sa gastos sa amin isang yunit ng oras, ngunit iyan ay OK.
At ngayon, limang pupuntahan maging isang maliit na mas mahal.
Kung gusto mo sa hakbang pabalik.
Kailangan namin upang ilipat walo, at pitong, anim.
At pagkatapos ang lahat ay inayos ngayon.
Isang malaking kamay sa aming mga boluntaryo dito Kaya.
Salamat sa iyo kaya magkano.
>> [Palakpakan]
>> Salamat sa lahat.
Salamat sa lahat.
Kaya tingnan natin ngayon kung paano lamang magastos lahat ng iyon ay.
Isaalang-alang natin marahil ang Ipaalam pinakasimpleng ng mga, uri bubble.
At sinasabi ko pinakasimpleng, dahil lamang maaari mong malutas ito nang buong kasakiman sa pamamagitan lamang
ayusin ang mga pairwise problema dito.
Ayusin ang pairwise problema dito, muli at muli
at muli, paulit-ulit na bilang ng maraming beses ng iyong aktwal na kailangan sa.
>> Kaya ito ay lumiliko out na may isang bubble sort, well,
kung gaano karaming mga hakbang na kailangan kong gawin sa mga ang unang pass ng algorithm na iyon?
Baka ako take-- ni see-- isa ipaalam, dalawa, tatlo, apat, lima, anim, pitong.
At mayroong walong elemento dito.
Kaya ito ay tulad n minus 1 na hakbang upang makuha mula sa simula ng listahan
sa dulo ng listahan.
>> Ngunit sa pagpili ng uri, pagpapabalik na ako piliing muli at muli ang mga elemento
at muli na pinakamaliit, Ako ng paglalagay ito sa lugar,
ngunit pagkatapos ay hindi ako naghahanap likod ako muli.
Kaya tingin ko ito ay isang maliit na mas malinaw pagkatapos na sa unang pagkakataon, maaari ko
kailangang gawin ang lahat n minus 1 na hakbang upang mahanap ang pinakamaliit na elemento.
Pagkatapos ko bang ilagay ang mga ito sa lugar, at ako paalisin ang sinumang ay dito dati.
>> Ngunit pagkatapos ay hindi ko na kailangang panatilihin ang pagtingin sa elementong ito,
dahil alam ko ito ay na ang pinakamaliit.
Kaya ngayon, maaari kong tumingin sa loob lamang ng pitong sangkap, at pagkatapos ng anim na mga sangkap,
pagkatapos ng limang mga sangkap, at pagkatapos ng apat na mga sangkap.
At kaya mathematically, kung n ay ang bilang ng mga elemento o numero
na namin na nagsimula sa, maaari mong isipin na ito ay ang parehong bilang n minus 1,
plus n minus 2 na hakbang, plus n minus 3 hakbang na ito,
plus n minus 4 na hakbang, ang lahat ng mga paraan pababa sa isang hakbang lamang.
At ako sa aking huling tao.
>> At kung isipin mo na ang isang pulutong ng stats ng mga libro o matematika libro
magkaroon ng mga formula sa Hardcover likod o sa harap ng mga ito,
ito ay lumiliko out na ang seryeng ito maaaring ipinahayag mas lamang
bilang n beses n minus 1 sa higit sa 2.
At ito ay multa kung hindi iyon sa harapan ng iyong isip.
Ngunit ito ay sa katunayan totoo.
Iyan na lamang ng isang mas simpleng paraan ng pagsusulat ng mga ito.
At pagkatapos ay kung sa tingin mo bumalik sa mababang paaralan,
kapag nagsimula ka lamang ng pagpaparami out, ang mga bagay na ito ng mga kurso,
ay lang n nakalapat minus n hinati sa 2.
Lahat ng aking nagawa ay palawakin ang expression doon.
At ni sa pagsulat na muli ito upang ipaalam sa isang maliit na naiiba.
Iyan ay n squared hinati sa 2 minus n / 2.
>> Kaya muli, ako lamang ang uri ng pag-aaplay patakaran ng ilang arithmetic doon.
Ngunit ngayon mapansin na ang mga pinakamalaking kataga sa ganitong expression, kaya na magsalita,
ay na n nakalapat.
Kaya oo, ito ay n squared hinati sa 2, minus n / 2.
>> Ngunit sa pangkalahatan, kung ang n ay magiging isang malaking halaga,
Pupunta ako sa claim na n nakalapat ay magiging ang nangingibabaw na kadahilanan.
Lamang Ito ay pagpunta sa maging isang mas malaking contributor
sa bilang ng mga hakbang sa n / 2.
Kaya kung ano ang ibig sabihin ako sa pamamagitan ng ito?
Subukan ang isang simpleng halimbawa, kahit na kahit na ang matematika ay makakakuha ng isang maliit na malaki.
>> Kaya ipagpalagay namin ay 1 milyong mga tao sa entablado, o 1 milyong mga bagay
na gusto naming ayusin.
Ni plug isang milyong Ipaalam sa eksaktong na formula
upang makita kung gaano karaming mga hakbang na aabutin pagiging upang maipagsama-sama sa isang milyong mga elemento gamit sabihin,
sort pagpili.
>> Kaya gusto naming magkaroon ng parehong formula tulad ng dati.
Gusto ko plug ng isang milyon, kaya na nakukuha ko isang milyong squared hinati sa 2,
minus isang milyon na hinati sa 2.
Kung gagawin ko na math in advance dito, mayroon kaming 500 bilyon
minus 500,000, kung saan ay nagbibigay sa amin 499,999,500,000,
kung saan ay medyo darn malaki.
>> Sa katunayan, kung ihahambing mo ngayon 499,000,000,000, 999 milyon,
500,000 laban sa aming mga orihinal na halaga, 500 bilyong, ito ay kaya sumpain malapit.
Right? n squared hinati sa 2 ay nagbibigay sa us-- o sa halip, n squared hinati sa 2
nagbigay sa amin ng 500 bilyon.
Iyan ay medyo malapit darn sa 499,999,500,000,
na ang ibig sabihin ng pagbabawas off 500,000, o sa mas pangkalahatang, pagbabawas off
n nakalapat, hindi talagang isang malaking pakikitungo.
N Ang nakalapat ang gumagawa ng mga numero lumago talagang mabilis.
>> Ngayon, ito ay mahalaga lamang insofar bilang kami, bilang mga siyentipiko computer,
ay karaniwang hindi pagpunta sa pag-aalaga kaya magkano tungkol sa mga nuances ng mga formula
at kung ano mismo ang tumpak na mga sagot ay.
Kami ay pag-aalaga na lang na, alam mo kung ano?
Sa katapusan ng araw, ang formula na ito ay sa order ng n nakalapat.
>> Oo, kami ay naghahati sa pamamagitan ng 2 sa doon.
Oo, kami ay pagbabawas off n minus 2.
Ngunit sa pagtatapos ng araw, ang mga kataga na talagang masakit sa amin at bayad sa amin
isang pulutong ng mga hakbang ay na square term.
At kaya kung ano ang isang computer scientist ay pagpunta sa pangkalahatan ay gawin
ay huwag pansinin ang lahat ng mga mas maliit na mga tuntunin order,
at tumingin lang sa isa na nag-aambag sa mga pinaka sa mga gastos.
>> At ito ay nice, dahil maaari naming ngayong makipag-usap sa mas higit na panlahat
tungkol sa mga algorithm, at maaaring ihambing ang mga ito.
At ang katotohanan na ako gamit na ito O ay sinadya.
Kapag sinasabi ko sa pagkakasunud-sunod ng, partikular na ako
nagre-refer sa isang bagay tinatawag na malaking O. At malaking O
ay isang palatandaan na ang isang computer ay gumagamit ng mga siyentipiko upang ilarawan
isang itaas na nakatali sa isang bagay.
>> Kaya kung sinasabi mo na ang isang algorithm ay nasa malaking O ng n squared,
bilang ipinanukalang ko lamang ng isang ilang sandali ang nakalipas, ang ibig sabihin nito
na sa mga tuntunin ng kanyang pagtakbo oras o ang kanyang kahusayan,
ito ay tumatagal sa pagkakasunud-sunod ng n nakalapat na mga hakbang.
Siguro higit pa, siguro ay mas mababa.
Ngunit ito ay sa order ng n nakalapat.
At iyan ang itaas na nakatali.
Hindi na ito ay magiging mas masakit kaysa sa na.
Hindi ito ay magiging n nakakubo, o 2 sa n, o isang bagay na mas malaki.
Ito ay isang itaas na nakatali sa kahit na ano na gastos ay.
Kaya ibinigay na, sabihin isaalang-alang ang ilan sa mga halimbawa.
At ito ay lamang ng isang may hangganan listahan ng napaka-pangkaraniwan ulit na tumatakbo
para sa mga algorithm na ay sinadya upang maging nakapagpapakita ng ilang mga bagay na namin
nakita na.
>> Kaya halimbawa, sa kaso ng pagpili ng uri, kung ano ako ng pagtubos dito
ay tumatakbo na ang uri ng pagpipilian oras ay sa order ng n nakalapat.
Sa pinakamasama kaso, ako pagpunta sa may isang buong grupo ng mga random na numero dito.
At tulad ng nakita natin mathematically, kung ako panatilihin ang paglalakad
sa pamamagitan ng listahan, sa pamamagitan ng list, ang pagpili sa susunod na pinakamaliit
muli at muli element, kung ako talagang isulat ang lahat ng mga hakbang
Ako pagkuha bilang ipinanukalang ko formulaically bago, ito ay sa order ng n squared
hakbang na aking iniinom.
>> At ito ay lumiliko out na ang bubble uri-uriin at insertion sort
ay tulad ng mabagal na sa pinakamasama kaso.
Isaalang-alang, halimbawa, uri insertion, sa huling algorithm namin dealt sa,
na kung saan ay nagkaroon sa amin tingnan ang element, at pagkatapos ay ipasok ito kung saan ito kabilang.
At pagkatapos ay itinuturing namin ang susunod na sangkap, at ipinasok na ito kung saan ito kabilang.
>> Kaya isaalang-alang ang pinakamahusay na posibleng sitwasyon.
Ipagpalagay aking volunteers ko ay pumila literal na tulad nito, ang isa sa pamamagitan ng walong,
pinagsunod-sunod.
Gaano karaming mga hakbang ay uri insertion pagpunta sa gawin upang ayusin walong tao,
kung dumating sila sa entablado naghahanap tulad nito?
>> Eight mga tao na pinagsunod-sunod.
At gagamitin ko uuri.
Na huling ng algorithm.
Well, reenact ni tunay na mabilis ipaalam.
Kaya kung simulan ko dito, nakikita ko ang isa.
Saan ang isa ay pag-aari?
Ito ay nabibilang dito mismo.
Nakakakita ako ng dalawa.
Saan ang dalawang nabibilang?
Dito.
Nakakakita ako ng tatlo.
Saan ang tatlong nabibilang?
Dito.
>> Nakakakita ako ng apat.
Dito.
Five, anim, pitong, walong.
Walang dahilan upang ulitin ang aking sarili.
At kaya, kung gaano karaming mga hakbang ay na sa mga tuntunin ng n?
Ito ay sa order ng n hakbang na ito, i-right? n minus 1.
Ngunit kinuha ko ang isang guhit number ng mga hakbang, at ngayon ako tapos na.
Kaya iyon ang pinakamahusay na kaso, bagaman.
Ano ang tungkol sa pinakamasama kaso?
Ano walong ay banda roon, at pitong ay down doon,
at isa at dalawa ay sa paglipas dito, para na ang listahan ay tunay na baligtad?
>> Well, kung ano ang mangyayari sa katunayan kung ito ang number?
At kami na ang lamang ng isang pares ng mga halimbawa.
Paano kung, sa katunayan, ang bilang ng walong ay dito, at ang mga number-- Oops.
Kaya kung ano kung, sa katunayan, ang bilang walong ay ang lahat ng paraan sa paglipas dito,
at gumagamit ako ng uri pagpapasok?
>> SIGE.
Inaangkin ko sa sandaling ito ay sa lugar.
Ngunit ngayon, seven-- kung saan ay pitong pumunta?
Siyempre, ito ay pumunta sa paglipas dito.
Kaya ko bang ilipat ang walong higit sa isang lugar.
Ngayon, anim, kung saan ito pumunta?
Well, ang lahat ng karapatan.
Ngayon, mayroon akong upang ilipat walong higit sa isang lugar, at pitong higit sa isang lugar,
at pagkatapos ay gumawa ng mapa ko pababa anim.
>> Kaya sa unang pagkakataon, cost ito sa akin sa isang hakbang upang ayusin ang mga bagay-bagay,
pagkatapos ay ang halaga sa akin ang dalawang mga hakbang upang ayusin ang mga bagay.
Ilang hakbang ito pagpunta sa gawin upang ayusin
bagay ilagay ang lima ay nasa tamang lugar?
Three.
Dahil ngayon ko bang ilipat ang isa, dalawa, tatlo.
Ilang hakbang ito sa pagpunta sa tumagal upang ilagay ang apat na nasa tamang lugar?
4 plus 5, plus 6, plus 7.
>> At kaya ito ay mathematically magkapareho sa kung ano ang namin na inilarawan para sa pagpili-uuri.
Mayroon kaming mga seryeng ito na lang ang pagtaas.
1 plus 2 plus 3 plus 4, o pasalungat, 7 plus 6
plus 5 plus 4 nagdadagdag up para ngayong araw mga layunin na sa order ng n nakalapat.
>> Kaya hayaan mo akong magtadhana masyadong na bubble sort ay din sa n nakalapat.
Dahil sa uri bubble, ang bawat isa oras na pumunta ko sa pamamagitan ng mga listahan,
Ako paglalaan ng humigit-kumulang kung gaano karaming mga hakbang na ito?
Sa bawat oras na ako ay literal lakad mula doon sa doon?
Sa pahapyaw n hakbang.
Ngunit kung gaano karaming beses maaaring ako kailangan upang pumunta sa pamamagitan ng listahan?
>> Well, halos n oras.
Siguro n minus 1, ngunit humigit-kumulang n ulit.
Well, kung bakit ay na?
Well, na may bubble sort, kung namin magsimula sa bubble uri,
may listahan sa pinakamasama posibleng sitwasyon, na muli ay ganap na
paurong, kung ano ang nangyayari sa mangyayari?
Pumunta ako sa pamamagitan ng listahan, at numero nabibilang sa isa ang lahat ng paraan sa banda roon.
>> Ngunit sa bubble sort, gaano kalayo ang ginagawa ng isa ilipat sa aking unang pass sa pamamagitan ng listahan?
Gaano karaming mga spot ay siya makakuha ng mas malapit sa tamang lugar?
Isa lamang.
Kaya't kung ikaw uri ng dahilan sa pamamagitan na ito, sa bawat oras sa pamamagitan ng algorithm na ito,
Pagkuha ng humigit-kumulang n hakbang na si David.
Ngunit kung gaano karaming mga pumasa sa pamamagitan ng listahan ay ito
pagpunta sa gawin para sa isa sa bubble sa kaliwa kung saan-aari?
>> Siya ay nakuha upang ilipat tulad, n puwang sa ganitong paraan.
Kaya upang gawin lamang ang pagbubukod-bukod ng mga listahan, Kailangan kong maglakad papunta at pabalik n ulit.
At sa bawat oras, ako naghahanap sa n elemento.
Kaya gawin n bagay n beses sa ang order ng n nakalapat.
>> Ngayon, kami ay makita sa ilang ng shorts na
naka-embed sa susunod na problema CS50 set, isa pang diskarte sa mga ito,
ngunit sa ngayon, hayaan ang isaalang-alang lamang ilang iba pang mga oras ng pagpapatakbo,
lalo na kung ang pag-uuri na mga tumagal isang maliit na piraso ng oras sa lababo.
Ano ang isang algorithm na nakita namin na na tumatagal sa order ng n hakbang?
>> Ano ang dapat gawin ng isang guhit number ng mga hakbang na namin nakita kaya ngayon?
Ano yan?
Ang paghahanap na direktoryo ng telepono.
Ang unang algorithm.
Right?
Saan hindi namin linearly naghahanap para sa Mike Smith?
Sa katunayan.
Mula week zero, kapag sinimulan ko paggawa sa isang pahina sa isang oras,
at kahit na sinabi ko na ito ay uri ng isang pakiramdam linear algorithm,
at nagkaroon kami na larawan sa board na may tuwid pulang linya
at ang mga straight dilaw line, ang mga iyon ay sa katunayan
algorithm na sa malaking O ng n.
>> Dahil upang mahanap Mike Smith sa isang telepono aklat ng n pahina, sa pinakamasama kaso,
maaring tumagal ako n hakbang.
Paano ang tungkol sa pagkuha ng pagdalo?
Isa dalawa tatlo apat lima anim.
Ano ang oras ng paggana ng mga ito algorithm para sa pagkuha ng pagdalo?
Big O ng n, dahil sa theory ko kung ituro sa lahat ng tao sa kuwarto.
>> Ngayon bilang isang bukod, ano ang tungkol sa iba pang mga optimization mula sa linggo zero?
Dalawa, apat, anim, walo, 10, 12.
Ang isang computer scientist gagawin mapagtanto, maghintay ng isang minuto,
na sa order ng n hinati sa dalawang hakbang.
Right?
Dahil ako ng paggawa ng dalawang tao sa isang pagkakataon.
Ngunit kami ay pagpunta upang huwag pansinin mga mas mababang mga tuntunin order,
at kami ay lamang ng pagpunta sa itapon ang hatiin sa pamamagitan ng 2,
at sabihin lamang, malaking O ng n para na algorithm rin.
>> Ano ang tungkol sa isang ito?
Makikita laktawan kaming mahigit sa ilan sa mga ito, ngunit kung ano ay isang algorithm na iyon ay mag-log ng n?
Na kinuha halos log n hakbang?
Ang hatiin at lupigin.
Mismong.
Tulad ng sa halimbawa sa aklat ng telepono sa week zero at mas maaga sa araw,
kung saan hinati namin ang problema at muli at muli.
Drew namin ito sa board sa week zero bilang hubog berdeng linya,
at sinabi namin sa araw na iyon, ito ay isang logarithmic algorithm.
>> At sa katunayan, ang bilang ng mga hakbang na ito ang kinakailangan upang maisagawa ang hatiin at lupigin,
o binary paghahanap bilang magsisimula kami pagtawag na ito, tulad ng sa aklat ng telepono,
ay sa pagkakasunud-sunod ng mga mag-log at mga hakbang.
At ito ay isang piraso ng isang isa kakaiba.
>> Ano ang tumatagal ng isang hakbang, o mas partikular na
ang tapat na bilang ng mga hakbang na ito?
Siguro ay dalawang, marahil ito ay tatlo, ngunit isang computer scientist na lang
Pinadadali ito bilang malaking O ng 1, ilang mga tapat na bilang ng mga hakbang.
Ano ang isang bagay na maaari mong gawin na tumatagal ng isang pare-pareho ang bilang ng mga hakbang na ito?
>> Ano ang oras ng paggana ng pumapalakpak?
Pare-pareho ang panahon.
Right?
Tulad ng, kung ano ang ang oras ng paggana ng paggawa ng anumang bagay na tumatagal lamang ng isa
operasyon, tulad ng i-print F Hello World.
Iyon ay maaaring maging sinabi na pare-pareho ang oras, maliban na lamang kung mas mababa sulok kaso may print F,
kung ano ang maaaring ang oras na tumatakbo ng print F tunay na maging?
At bakit?
Anong n pagsukat sa kasong iyon?
>> Madla: [hindi marinig].
David J. MALAN: Eksakto.
Ang bilang ng mga character gusto naming i-print.
Kaya napaka context-sensitive.
Ngayon, kami ay nagbibigay-diin sa isang pulutong sa mga titik at numero dito sa board.
Ngunit maaari din itong maging character sa isang aktwal na string.
Kaya ito ay lumiliko out may isa pang Ang panukalang-batas na ay magsisimula sa pag-aalaga tungkol sa,
at iyon ang kabaligtaran ng malaking O, kaya na magsalita.
>> Iyon ang wakas notation.
Sapagkat malaking O ay nangangahulugan kung ano ang, ang itaas na nakatali sa iyong tumatakbo oras?
Maximally, kung gaano karaming oras Maaaring ang isang bagay tumagal?
Omega-- paumanhin mapigil ito darating up-- ay ang kabaligtaran ng iyon,
kung saan ito ay isang mas mababang nakatali sa halaga ng oras ng isang bagay na maaaring gawin.
>> So. halimbawa, kung ano ang isang algorithm na tumatagal laging n nakalapat hakbang?
Well, isa sa mga algorithm na namin nakita ngayon, sa katunayan, ay maaaring maging pati na rin na iyon.
Selection sort.
Pinili uri ay medyo tanga.
Kahit na kung ang algorithm-- paumanhin, kahit na kung ang array na pinagsunod-sunod,
pagpili-uuri ay pagpunta sa panatilihin ang paglalakad sa pamamagitan ng listahan
upang tiyakin na ito ay ang pinakamaliit na element at muli at muli.
At kahit na iyong mga kawani na tao sa alam ng madla na, maghintay ng isang minuto,
ikaw ay nakapasa sa pinakamaliit na elemento, ang computer
ay hindi alam na hanggang sa ito hitsura lahat ng mga paraan sa pamamagitan ng mga listahan.
Katulad nito, ang isang mas mababang nakatali na Maaari din ay dadalhin sa account
ito ay maaaring maging sa haba ng panahon.
>> Gaano karaming oras ang hihintayin upang uri n elemento sa pinakamahusay na
kaso gamit ang isang bagay tulad ng bubble uri?
Ipagpalagay na ang iyong listahan ay pinagsunod-sunod.
Sabi namin tumatagal sa bubble sort ang order ng n nakalapat na mga hakbang.
Ngunit ano kung na-pinagsunod-sunod?
Paano kung nauunawaan mo pagkatapos ng isa pumasa sa pamamagitan ng array
na iyong ginawa walang swaps?
Kailangan mo bang panatilihin ang paggawa ng mas maraming passes?
>> Hindi.
Kaya ang isang mas mababang nakatali sa bubble sort Maaaring maging sinabi na linear.
Omega ng n.
At maaari naming tumingin sa iba sa mga ito pati na rin.
Kaya sabihin kumuha ng isang mabilis na pagtingin sa loob lamang ng visualization dito
upang makita kung paano ang mga ito na makilala ang kanilang mga sarili.
Pupunta ako sa bumaba dito sa ito pahina na magagamit sa website C50 ni,
ngunit ito ay isang sakit upang makakuha ng trabaho, dahil ito ay gumagamit ng isang teknolohiya na tinatawag na
Applets Java, kung saan ay isang higit sa lahat hindi suportadong mga araw,
hindi bababa sa pamamagitan ng Chrome at ilang iba.
>> At hayaan mo akong magpatuloy at bilis na ito up at ipaliwanag kung ano ang nangyayari sa.
Ito ay isang pagpapakita ng bubble uri, ang unang algorithm itinuturing namin.
At ito ay isang paggunita sa na ang bawat sa mga bar ay kumakatawan sa isang numero.
Mas malaking bar, ang mas malaki ang bilang.
Ang mas maliit na bar, ang mas maliit na ang numero.
At kung ano ang maaari mong makita ang biswal, kahit kahit na ito ay pagpunta napakabilis,
ay na ang mga pulang bar ay tulad ng sa akin, paglalakad papunta at pabalik sa pag-aayos ng mga problema.
Maaari mong makita na ang mga mas malaking mga elemento sa katunayan ay bumabalong sa kanan,
at ang mas maliit na mga elemento ay bumabalong sa kaliwa.
And pababa dito, kung kami talagang pagmasdan,
maaari naming aktwal na bilangin ang bilang ng mga paghahambing at swaps
na na na ginawa.
>> Ngunit sa halip, tingnan natin hayaan sa ikalawang algorithm
kami ay tumingin sa mas maaga sa aming boluntaryo, pagpili-uuri.
Biswal, ito ay may ibang-iba ng epekto.
Ngunit ito ay, muli, napaka-intuitive, sa na panatilihin namin ang pagpili sa susunod na pinakamaliit
sangkap, at nakuha namin ang isang maliit na mapalad.
Na nadama panimula mas mabilis.
Ngunit kung namin tumakbo muli at muli ito at muli may maraming ng input,
Gusto naming makita na ito ay sa katunayan pa rin sa malaking O ng n squared.
>> Gawin ang isa huling isa Ipaalam dito, uuri,
na kung saan ay ang ikatlong algorithm kami ay tumingin sa, at pagpapabalik
na ang isang ito ang trato sa mga mga elemento tulad ng ito ay nakatagpo ng mga ito,
ngunit pagkatapos ay ito marahil nagbabago mga bagay na higit na gumawa ng room,
pagpasok elemento kung saan nabibilang sila.
>> At ito masyadong nagtatapos up pagbibigay ng huling resulta. Ngayon ang lahat ng tatlong mga
nadama medyo mabilis.
At sa katunayan, ako ang bumangga sa kanila sa isang medyo magandang clip.
Ngunit sa panimula, ang mga ito ang lahat ng medyo kakila-kilabot, na maging matapat.
Lahat ng mga algorithm kaya sa ngayon na tumakbo sa malaking O ng n squared
kumuha pa ng kaunting ng panahon upang tumakbo sa dulo.
>> At sa katunayan, maaari naming makita at pakiramdam na ito bilang wakas
kung pull up ko ito ikatlong at huling demo.
Ito ay isa pang visualization na pupuntahan
upang ipakita ang bubble sort sa kaliwa, sort pagpipilian sa gitna,
at isang bagay, tulad ng isa sa aming mga kamay iaangat mas maaga iminungkahi,
sumanib uri sa kanan.
A hatiin at lupigin diskarte sa kanan.
At na, sa katunayan, kung ano ang hindi namin pagpunta sa tumingin sa sa Miyerkules.
Ngunit oras na ito na tumakbo sa parallel ipaalam.
Ito ay humigit-kumulang ang parehong bilang ng mga mga elemento, ang lahat ng tumatakbo sa parehong oras.
Bubble uri vs seleksyon sort vs pagsasama-uuri.
>> Ngayon, ang lahat ng mga ito ay tumatakbo sa teorya at sa parehong oras.
Ang CPU ay tumatakbo sa sa parehong bilis, ngunit ikaw
Maaari pakiramdam kung paano panganganak na ito ay masyadong mabilis ang pagpunta sa maging,
at lamang kung gaano kabilis kapag mag-iniksyon kami ng kaunting week
algorithms zero ni maaari pabilisin namin ang mga bagay up.
>> At ni ihambing ngayon hayaan ang mga ito sa isa sa huling form.
Pupunta ako sa sige sa website CS50, kung saan
taglay namin ang pangwakas na link para sa araw na ito, kung saan ang isang tao sa internet
mabait magkasama sa isang video na kinukuha kung ano ang iba't ibang mga pag-uuri
algorithms tunog tulad ng.
Ito ay uri insertion.
>> [Beep]
>> Kung saan ka nag-aaplay ng isang dalas batay sa taas ng bar bar.
Ito ang bubble sort.
>> [Bingkong beep]
>> Pagdating up sa susunod is-- darating up susunod is-- pagpili ng uri,
kung saan muli, kami ay pagpili sa susunod na pinakamaliit na sangkap,
at maaari naming makita ang mga ito lumalaki mula kaliwa papuntang kanan.
>> Pagsamahin ang mga uri, ang aming winner kaya ngayon ngayon.
Pansinin kung paano ito ay naghahati bagay sa [hindi marinig] kalahati at tirahan.
Gnome uri, na kung saan mayroon kaming hindi usapan tungkol sa, at lumilikha ng biswal
at audally isang piraso ng isang iba't-ibang hugis at tunog.
Pagpunta papunta at pabalik, paglilinis ng mga bagay up.
Suriin din ang heapsort sa website na ito tao.
>> At na ito.
Kami ay makita mo ang susunod na oras.
>> [Whooshing AND MUSIC]