[Muzikos grojimo] David J. Malan: Tai CS50. Ir tai yra savaitės trys pradžia. Taigi mes turime daug įdomių dalykų, kuriuos reikia padengti šiandien. Daug galimybių už savanoriai ant scenos. Ir galiausiai, šiandien yra ne apie kodo ne visiems. Bet tai apie idėjas ir tai apie algoritmus, ir iš tikrųjų sugrįžus kai ko pasimokyta iš nulio savaitę kuriame Prisiminkite, mes pristatė šį Straszliwość. Ir skolinimasis įkvėpimas to, pradėti išspręsti vis sudėtingesnės problemos algoritmiškai. Bet pirmiausia, iš skelbimų pora. Taigi vienas, jei norėtumėte prisijungti CS50 personalas ir klasiokų pietų šį penktadienį, tiek čia ir Kembridžo ir New Haven, apsilankykite aikštyno svetainė, kurioje URL gali būti rasta. Paskaita šį trečiadienį bus ne čia Sanders. Tai bus tik internete, todėl melodija ne CS50 tinklalapyje, ar čia Kembridže ar Niu Heivenas, taip pat. Ir tada problema nustatyti du jau jūsų rankose. Jei neturite nėrė dar, leiskite man pasiūlyti stipriai suformuluotą pasiūlymą kad, ypač dabar, kaip problema nustato iš anksto, jūs tikrai norite pradėti jau dabar, jei ne taškytis ant savaitgalį arba prieš tiek kai jie pirmą kartą išeiti Penktadieniais, nes jūs kad jie nebūtinai ilgėja ar sunkiau už SE. Manau, kad jūs rasite, kad Apskritai, jie linkę imtis maždaug aplink tą patį laiką. Bet tai tikrai priklauso mokinyje, ir ji priklauso nuo mąstymo su kuria jūs požiūrį. Bet visada, jūs ketinate paleisti prieš tikrą sieną, ir jūs ketinate Hit kai klaida, ir jūs tiesiog nesiruošia galėtų gauti per jį tam tikru momentu. Ir tai labai vertingas, kad būtų galima žingsnį, grįžti kitą dieną, pereiti prie darbo valandų, post CS50 Aptarkite ar panašiai, faktiškai gauti atblokuota. Taigi keep that in mind. Nuo anksčiau, kaip įmanoma yra geriausia, ką jūs galite padaryti. Taigi čia, kur mes pradėjome klasė, daugiau kaip nulinės savaitę. Ir mes galime gauti savanoris Čia padėti man rasti mikrofonus? GERAI. Atsistojus jau. Nagi iki. Manau, kad tai, kaip ji vyksta į darbą. Koks tavo vardas? ALAN ESTRADA: Alanas Estrada. David J. Malan: Alanas Estrada. Nagi iki. Malonu susipažinti. ALAN ESTRADA: Nice to meet jums. David J. Malan: Ir tu buvai čia su mus nulinės savaitę, žinoma. ALAN ESTRADA: buvau. Aš buvau. David J. Malan: Taigi gal jūs einate į priekį ir rasti mums Mike Smith taip pat greitai, kaip jūs galite? Kaip greitai, kaip jūs galite. Drąsiai ašarojimas problemą per pusę, kaip jums reikia. ALAN ESTRADA: Hm. David J. Malan: Pažodžiui ašarojimas per pusę problemą. ALAN ESTRADA: O. Mm. Labai gerai. David J. Malan: Gerai. Geras. Ačiū. ALAN ESTRADA: Labai gera. GERAI. David J. Malan: Ir taip dabar Jūs sutrumpino jį žemyn pusei problemos dydžio. Dabar mes iki ketvirčio. Ar jūs atkreipti dėmesį į kurioje pusėje mes išlaikyti? [Atsakyti] ALAN ESTRADA: Taip, aš think-- David J. Malan: Kas skyriuje mes esame? ALAN ESTRADA: DUSLINTUVAI, todėl. David J. Malan: Gerai. Bet Mike Smith ketina būti po Garso slopintuvas. So-- [Atsakyti] Gerai. ALAN ESTRADA: Kur mes ieškome? David J. Malan: Mike Smith. ALAN ESTRADA: Mike Smith. David J. Malan: Dabar mes chirurginių. Dabar gydytojai. Now-- ALAN ESTRADA: Let's- eikime su realiais. Real. David J. Malan: Nekilnojamojo. GERAI. Jei reikia realių. Dabar, kuris būdas yra Mike Smith? ALAN ESTRADA: Šis būdas. David J. Malan: Kokiu būdu? ALAN ESTRADA: Palaukite. M is-- tiesa? Mes pradėjome with-- David J. Malan: Taip. Jie paliko. Tu teisus. ALAN ESTRADA: Taip. David J. Malan: Taigi Mike čia. ALAN ESTRADA: Kas? [Atsakyti] Blogas pavyzdys, vaikinai. Atsiprašau. David J. Malan: tai bus išmokyti jums šuolis iš savo kėdės. ALAN ESTRADA: O. Oh. Aš turiu jums. Aš turiu jums. Oh. Oh. Tai is-- Gerai, aš turiu jums. Smith čia? David J. Malan: Smith, ačiū. Taigi aš nuolat ieško iki Smith? ALAN ESTRADA: O, taip. Ne, ne, ne. O ne. Tai yra mano. David J. Malan: Oi, jūs turite Smith. GERAI. ALAN ESTRADA: Taip, aš gavo Smith čia. Atsiprašome, vaikinai. Maniau Michael-- mes ieško Michael. Atsiprašau. David J. Malan: Tai gerai. Gerai, dabar mes į Paccini ir Sūnų. ALAN ESTRADA: Paccini ir sūnūs. David J. Malan: Tik jūs ir aš yra apie tai. GERAI. Raskite mus Mike Smith. Smith. ALAN ESTRADA: Smith. David J. Malan: Smith. Mes R už šiukšlių. ALAN ESTRADA: Šiukšlės. Oh. Tai ketina užtrukti. [Atsakyti] David J. Malan: Avalynė. Mes į batus. ALAN ESTRADA: Dabar mes gonna-- David J. Malan: gražus. ALAN ESTRADA: Which-- [Atsakyti] O, tai puiku. [Atsakyti] David J. Malan: Tai gerai. ALAN ESTRADA: O, tai yra gerai. Aš nemanau, kad aš ruošiuosi turi PSAT bičiuliai po šio. David J. Malan: Geras. Sporto. ALAN ESTRADA: Sporto. Um, L, M, N, O, p David J. Malan: Gerai. Taigi leiskite ašara tai per pusę. Viskas gerai. Tai baigiasi blogai vistiek, nes Mike Smith nebus geltonieji puslapiai. ALAN ESTRADA: Aw. David J. Malan: Ne, tai gerai. Bet tegul apsimeta kaip jis šiame puslapyje. Taigi dabar jūs sutrumpino problemą žemyn kad viename puslapyje, ir mes nustatėme, Mike Smith. [Didelio džiaugsmo] Gerai, ačiū. GERAI. Tai buvo nepaprastas. Bet tai dar greičiau buvo nei tiesinės paieškos, kuriame mes pradėsime ne pradedant knygos, ir mes perkelti savo kelią iš kairės į dešinę, galiausiai ieško Mike Smith. Ir taip, jei telefonas knyga turėjo gal 1000 puslapių, gal jis ėmėsi mums 10 ar taip puslapis ašaros. Tačiau jums gali būti išnaudojamos palietė prielaidą, per visa tai, ir kuri yra pasakyti, kad telefonas užsisakyti iš anksto buvo kas? Auditorija: Rūšiuota. David J. Malan: Tai rūšiuojami. Teisė? Tai rūšiuojami pagal abėcėlę, taip kad visi iš šių pavadinimų ir numeriai yra rūšiuojami nuo A s į Z ir abėcėlę tarp jų. Tačiau šiandien, mes dabar paklausti klausimas, gerai, Kaip "Verizon arba telefonas Bendrovė gauti jį į tos valstybės? Nes tai vienas dalykas, siekiant pritraukti kad prielaida, ir todėl, išspręsti su problema algoritmas efektyviau. Bet mes niekada paklausė nulio savaitę, gerai, Kiek tai kainuos "Verizon" ar kažkas gauti, kad telefono knygą rūšiuotų tam? Teisė? Nesvarbu, jei žiūrint Mike Smith yra super greitas, jei ji nukelia į metų rūšiuoti puslapius pradžių. Teisė? Jūs galite taip pat tiesiog atsijoti per atsitiktinių imčių telefonų knygoje, jei jis bus super brangu rūšiuoti. Taigi, jei mes galime turėti dar vieną savanorį. Paimkime pažvelgti čia kaip mes might-- nagi up-- kaip mes galime eiti apie rūšiavimą jų. Ir jei Jordanija tikrųjų galėtų prisijungti prie mūsų čia ant scenos. Nagi už akimirką. Koks tavo vardas? CAROLINE: Caroline. David J. Malan: Caroline, nagi iki. Ir jums bus sujungtos man ir Jordanijos čia. Karolina, ačiū. Gerai. Taigi, ką mes turime čia Caroline 26 mėlyna knygos kad FAS naudoja administruoti tam tikri baigiamuosius egzaminus. Tai vis sunku rasti, bet ką mes padarėme iš anksto yra tai, kad mes įdėti kažkieno vardą ant kiekvieno iš jų priekyje, bet mes nuolat jį paprasta iki tada pradėti iš vardai ir pavardės. Taigi mes įdėti asmenį su pavadinimu L, D, J, B, visą kelią nuo A iki Z, bet jie atsitiktine tvarka. Ir taip, jei galėtumėte, kalbėti tavo kelią per problema, kaip jums tai padaryti, galite eiti į priekį ir rūšiuoti jų mums, nuo A iki Z. Auditorija: Gerai, kad L yra kaip, viduryje. C prasideda. B. J prieš L. B Q. David J. Malan: laikykite, kad pagalvojo vieną sekundę. Nes kitaip, tai yra tik Jums įdomu, ME, ir Jordanija. Čia mes eiti. Auditorija: [nesigirdi]. R. David J. Malan: Gerai. Ką tu darai? CAROLINE: M ateina po O. David J. Malan: Gerai. CAROLINE O. David J. Malan: "O, gerai. CAROLINE E. David J. Malan: E, F. Taip. CAROLINE: T, U, V David J. Malan: V, T, U, V, todėl atrodo, kad jūs esate making-- nesustoti. Jis atrodo kaip jūs darote didelis krūva per čia ir rūšis didelis krūva ten. Todėl pirmoji pusė abėcėlės, Antroji pusė abėcėlės. GERAI. Geras. Geras išskaidyti problemą į dvi dalis. M, N X. Taip. CAROLINE K. David J. Malan: Gerai. K. Taigi jūs rūšies pasirinkdami vienas jų po kito, išleisti jį kairę arba į dešinę, arba Z vyksta ant grindų. GERAI. CAROLINE: ZA vyksta ant grindų. David J. Malan: Gerai. Y vyksta ant grindų. Dabar mes galime įdėti X CAROLINE G. David J. Malan G vyksta į kairę. S vyksta teisinga. Visos teisės A vyksta visą kelią į kairę. CAROLINE: A, B, C, D David J. Malan: Dabar gerai. Mes turime A, B, C. W. vyksta ten. Visos teisės T. CAROLINE: H, I, J. David J. Malan: H, I, J. Geras. CAROLINE: Centre, aš gonna-- David J. Malan: Gerai. Taigi dabar mes ketiname rūšies iš sujungti šiuos įvairius poliais. Taigi per C, tada matau D ir E ir F, ir G, ir H, ir I. Nica. J K. Ir tada, tai krūva yra apverstą, bet viskas OK. Tikrai. Mes galime sumažinti kai kampuose. GERAI. Ir tada turime W, X, Y, Z. CAROLINE: Taip. David J. Malan: Puikiai. Taigi didelis ačiū Caroline rūšiavimo jų. [Didelio džiaugsmo] Ačiū. Labai ačiū. Taigi, dabar aptarkime akimirkai kaip Caroline vaikščiojo, darydamas, kad ir ką tiksliai mes galėjo to-- kaip mes galėjo išspręsti, kad problema, kai mes buvome tik suteikta visa krūva atsitiktinių įėjimai. Na, atrodo, kad ten buvo sistemos ten bitų? Teisė. Taigi ankstesnių laiškų abėcėlė, ji buvo išleisti į kairę, ir vėliau raidės abėcėlės, ji buvo išleisti į dešinę. Ir kuo greičiau ji rado kai artimieji raidės, ones kad eiti šalia viena kitos, ji būtų įdėti tuos tvarka. Ir todėl mes natūra turėjo tai mažas krūvos rūšiuotų žaliavų pasikartojimui. Ir taip, kad visai patinka tai, ką Daugelis iš mūsų žmonės būtų padaryti. Mes tarsi atsijoti per jį, ir mes norime rūšies turėti mechanizmą. Bet tai gali būti sunku rašyti jį žemyn SE formulę per. Jis manė, šiek tiek daugiau organinių kad ne. Taigi pažiūrėkime, jei mes galime dabar jungiasi Su mažiau sąnaudų problema. Vietoj 26, tegul kažką daryti kur kas mažiau su tik pasakyti, septyni, už Šios durys, taip sakant. Ar ten tik septyni numeriai? Ir jei tikslas dabar ranka yra rasti vertę, pažiūrėkime, kaip efektyviai mes galime eiti apie tai daryti. Ir tegul pamatyti, jei mes galime dabar pradėti taikyti kai kuriuos skaičius, arba kai formulės, su kuria apibūdinti mūsų telefonų knygoje efektyvumas algoritmas, mūsų egzaminas knyga algoritmas ir apskritai ieškant informacijos. Taigi už tai, leiskite man eiti į priekį ir ant jutiklinio ekrano nei čia taikstytis naršyklę, kuri turi tiksliai šie septyni durys. Ir jei mes galime gauti vieną kitą pasisiūlyti ateiti per čia Aš įdėti tuos pačius duris čia. Greita savanoris. Šis one-- demo vyksta kad greitesnis ir greitesnis dabar. Nagi žemyn. Koks tavo vardas? TREVOR: Trevoras. David J. Malan: Trevor? Gerai, Trevoras, nagi žemyn. Taigi Trevoras buvo čia pasisiūlė padaryti panašią problemą, bet vienas, kad siauresnės apimties, ir kad vyksta leisti mums pabandyti įforminti dabar už rūšiavimas šiuos numerius procesas. Taigi Trevoras, nice to meet jums. Taigi čia yra masyvas, taip kalbėti, septynių durų sąrašą. Eiti į priekį ir mus rasti skaičių 50. Ir tada, po to,, papasakoti, kaip jums rasti ją. Jei be-- visą teisę. Taip, tai yra vienas čia? Uh Oh. GERAI. Jūs paspaudėte, kad vienas. Geras. Ir gerai. Dabar jūs paspaudėte, kad vienas. Ir leiskite man duoti jums mikrofoną, taip, kad jūs turite jį vos akimirką. Eiti į priekį ir spustelėkite šalia durų, kad jūs ketinate. Taip gerai. TREVOR: Ar galiu nuimkite duris? David J. Malan: Ne, jūs negalite nuimkite. TREVOR: Gerai. Šitas. David J. Malan: Kur tu nori eiti? Kuris? TREVOR: Tai viena. David J. Malan: Ne TREVOR: Gerai. Šitas. David J. Malan: Taip. Tai buvo gera. Gerai. Taigi, kas buvo jūsų algoritmu arba tvarka tai daryti, Laisvas valdo? TREVOR: Aš ką tik išgyveno durys kol radau 50. David J. Malan: Gerai. Puikus algoritmas. Taigi, kad viskas gerai. Nes iš tiesų, jei aš atskleisti tai, kas Už šių dviejų kitų durų, kas mes surasime, kad čia yra mes turime tik atsitiktinis įvestį. Taigi, kad iš tikrųjų buvo taip gerai, kaip jūs galite gauti. Ir iš tiesų, jūs turite geriau nei išsamiai ieško visą masyvą, nes tai būtų buvę tikrai nelaimingas, jei jau nukentėjo numerį 50, per paskutinę duris. Bet kas, jei mes vietoj padovanojo tau prielaidą. Tarkime, aš tarsi visi Šios durys aplink, taip, kad jūs turite numeriai surūšiuoti šį kartą, bet šį kartą tai tikrai different-- šį kartą, tai tikrai rūšiuojami už jus. Ir dabar po ranka tikslas yra pataikyti skaičių 50. TREVOR: Gerai. David J. Malan: Kas Jūsų algoritmas bus? TREVOR: Na, jei tai rūšiuojamos, tai arba ketina į be-- jei didžiausias iki didžiausių mažėjančia tvarka, tai bus pirmasis, arba, jei tai priešinga, ji bus paskutinis. Taigi aš tiesiog bakstelėkite šį dureles ir tada tiesiog bakstelėkite paskutinį duris. David J. Malan: Puikiai. Gerai. Taigi mes nustatėme, kad skaičių 50. Taigi kuo greičiau jūs žinojo jie buvo rūšiuojamos, mes galėjome išnaudoti šią prielaidą. Taigi jie per daug, kaip telefonų knyga pavyzdys. Kaip tik jūs turite, net su maža problema, kaip tai, Jūsų įėjimai iš anksto rūšiuojamos, mes galime iš tikrųjų rasti vertę, be abejo, efektyviau. Ir aš ne pasakyti jums, jei ji buvo rūšiuojami mažų iki didelių, ar didelis, mažas, ir todėl buvo labai protinga pradėti viename gale arba kita kad iš tikrųjų surasti tą siektiną vertę. Taigi padėkoti Trevor taip pat. Ir aš propose-- gražiai padaryta. Mes turime mažai įrašą, iš tikrųjų, kad yra tarp mūsų mėgstamų momentus CS50, kuriuo kartais šie demo ne visai eiti pagal planą. Ir iš tiesų, dabar, aš išrautas klaidingą sąsaja su kuria naudoti jutiklinį ekraną. Taigi, tai buvo mano kaltė ten. Taigi tai padarys už kitų metų klipas taip kodėl aš Paspaudę ant mano paties ekrano. Bet tegul priimti greitai pažvelgti kas atsitiko pernai su Jay, kuris atėjo daug kaip Trevor čia savanoriškai, ir šį trumpą klipą, pamatysite kaip tai tas pats demo ne visai atskleisti pačias pamokas. [Vaizdo įrašų atkūrimas] -Visos Noriu jums padaryti dabar rasti man, ir mums, tikrai, skaičius 50 vienas žingsnis metu. -The Numeris 50? -The Numeris 50. Ir jūs galite atskleisti, kas po kiekvieno iš šių durų tiesiog palietus jį su pirštu. Velnias. [Atsakyti] [PABAIGA PLAYBACK] David J. Malan: Taigi, kad išėjo labai gerai. Tai buvo nerūšiuotos durys. Jay, žinoma, nustatė, kad jis pernelyg greitai. Trevoras padarė daug geresnį darbą kalbant apie tam Pojętny metu taip sakant, šiais metais trunka ilgiau jį rasti. Žinoma, tada mes davė Jay antras šansas, kurią mes rūšiuojami duris, kaip mes padarė Trevor, ir Trevoras padarė super gerai šį kartą. Bet Jay tai padarė pusę taip greitai. [Vaizdo įrašų atkūrimas] -The Tikslas dabar yra taip pat mus rasti skaičių 50, bet tai padaryti algoritmiškai ir papasakoti, kaip jūs ketinate apie tai. -GERAI. -O Jei jums rasti ją, jūs nuolat filmą. Jei nerandate, galite duoti jį atgal. -Man. -OH! - [Nesigirdi] Gerai. Taigi, aš ruošiuosi patikrinti galus pirmiausia reikia patikrinti, ar there's-- Oh. [Plojimai] [PABAIGA PLAYBACK] David J. Malan: Gerai. Taigi rūšiavimo duris aiškiai veda prie didesnio efektyvumo. Ir taip, du kartus taip greitai, yra tai, ką aš ten reiškė. Ir taip Jay pasisekė abu kartus. Ir jis taip pat pasisekė, kad paskutinis metus, aš užsisakiau keletą Blu-ray diskus kad iš tikrųjų duoti. Aš atsiprašau šiemet, mes neturėjo tas pats, Laisvas valdo. Bet vis tiek geriau buvo keletą metų atgal. Ir kai kurie iš jūsų gali žinoti kolega Sean, kuris, kai jis buvo CS50, buvo užginčytas su Tiksli Ta pati problema, nors ir SD, kaip jūs netrukus pamatysite, atgal per dieną. Ir jūs pamatysite, kad ne tik nebuvo jis užtrukti šiek tiek ilgiau nei Jay, šiek tiek ilgiau nei Trevor, tai buvo iš tikrųjų tai puiki galimybė užsiimti beveik kiekvienas Minia a la Kaina yra teisinga, skatinant jam rasti skaičių buvome ieško. Leiskite. priimti greitai pažvelgti. [Vaizdo įrašų atkūrimas] -GERAI. Taigi jūsų užduotis čia Sean, yra tokia. Aš paslėpta už tai durys skaičius septyni. Bet nuošalioje kai kuriose iš šių durų taip pat yra ir kitų neigiami skaičiai. Ir jūsų tikslas yra galvoti Šio viršų eilės numerių kaip tik masyvo, arba tiesiog seka popieriaus lapų, su numeriais už jų. Ir jūsų tikslas yra, tik naudojant viršaus masyvas čia rasite me skaičius septyni. Ir mes tada ketiname kritika kaip jums eiti apie tai daro. -Gerai. -Find Mums skaičius septyni, prašau. Ne. Penki, 19, 13. [Atsakyti] Tai ne triukas klausimas. Vienas. [Atsakyti] Šiuo metu, jūsų rezultatas nėra labai gerai, todėl jums gali taip pat nesustoti. Trys. [Atsakyti] Tęsk. Atvirai kalbant, aš negaliu padėti, bet įdomu ką jūs net galvoti apie, so-- [Atsakyti] Tik viršutinėje eilutėje, todėl jūs turite tris kairę. Taigi mane surasti septyni. [Atsakyti] 17. Septynios. [Plojimai] Gerai. [PABAIGA PLAYBACK] David J. Malan: kad galėtume žiūrėti šiuos visą dieną. Ir, žinoma, kai kurie iš šiemet demo galbūt dabar baigti Kitas metų vaizdo, taip pat. Taigi, dabar tegul iš tikrųjų sutelkti dėmesį į algoritmų čia, ir pamatyti, jei mes negalime dabar pradeda formalizuoti kaip mes galime eiti apie tai mūsų duomenis į šios valstybės, kad ji manimi rūšiuojamos, taip, kad galiausiai, mes galime iš tikrųjų ieškoti ją efektyviau. Ir nors mes ketiname naudoti gana mažas duomenų rinkinius, kaip aštuoni numeriai ir mes turime čia ant lentos, galiausiai tie patys idėjos galėtų taikyti 1000 įėjimai, milijonas įėjimai, 4 mlrd įėjimai, nes algoritmai yra bus iš esmės ta pati. Ir todėl tai yra mūsų paskutinis galimybė savanorių šiandien bet galbūt labiausiai dalyvauja viena, dėl kurių mes turime aštuonis savanorius sugalvoti ir vaikščioti su mumis per procesas rūšiavimas, ką netrukus būti šių muzikos stovi čia. Leiskite man pradėti vėl čia. Taigi vienas iš turquoise-- žalia tai? Ar jūs įsipareigojant? Du. Nagi žemyn. GERAI. Trys. Keturi. Tegul me-- Gerai, penki. Jūs esate nominuotas jūsų draugas. Šeši, septyni, aštuoni. Nagi iki. Gerai. Labai ačiū. Nagi iki. Nagi iki. Gerai. Taigi, ką mes turime here-- ir tai yra tarp daugiau nepatogios tie, nes tai reikalauja, kad jūs humoras man tik už šiek tiek laiko. Jūs turi būti numeris vienas. Koks tavo vardas? Ananas: Annanas. David J. Malan: Annanas. Davidas. Koks tavo vardas? JOSEPH: Juozapas. David J. Malan: Juozapas Jūs esate numeris du. SERENA: Serena, numeris trys. Stefanas numeris keturi. CYNTHIA: Cynthia. David J. Malan: Cynthia numeris penki. [Nesigirdi] David J. Malan: [nesigirdi]. Davidas numeris šeši. Matt: Matt. David J. Malan: Matt skaičius septyni. Ir? WAVERLY: Waverly. David J. Malan: Waverly numeris aštuoni. Gerai. Jei could-- šūksniais. Jei jums visiems, kaip jūsų Pirmasis uždavinys, yra Yra aštuonios muzikos stendai Čia susiduria auditoriją. Jei galite įdėti savo numerius šie muzikos stovi tokiu būdu, kad jie išsirikiuoja su tie patys numeriai ant lentos. Todėl įsitikinkite patys atrodyti, kad išleisti savo numerius šių muzikos stovi čia. Puikus iki šiol. Puikus. GERAI. Taigi dabar mes ketiname paklausti klausimas keletą skirtingų būdų. Kaip mes galime eiti apie rūšiavimas Šie žmonės čia? Kadangi mes turėjome keletą požiūrių anksčiau, pagal kurį mes buvome rūšies priėmimo du skirtingus kibirus. Ir tada mes paprastai buvo susegimas kartu. Kaip greitai, kaip mes matėme du numerius kad priklausė kartu, mes juos kartu. Dvi raidės, kurios priklauso kartu. Bet pažiūrėkime, jei mes negali įteisinti tai, kad mes galiausiai turi kai pseudo-kodas bus, su kuria jūs galite išspręsti šias problemas. Taigi dabar aš dairytis ne šie skaičiai čia. Ir aš matau visa krūva klaidų. Galų gale, aš noriu vieną ant kairysis ir aštuoni dešinėje. Ir taip aš žiūriu šių dviejų, keturių ir dviejų. Ir kas yra problema, žinoma? Taip. So. Du akivaizdžiai ateina prieš keturi, kad jūs žinote, ką? Leiskite pirmiausia imtis gobšus požiūrį, jei bus, panašiai kaip problema nustatyti one-- Jei prisimenate iš Standard Edition problema nustatyti vieną, kur aš tiesiog vietoje išspręsti problemą tai čia priešais mane ir pamatyti, kur ji veda mane. GERAI. Taigi du keturi, leiskite man eiti į priekį ir tiesiog sukeisti tau du. Jei galite fiziškai judėti patys ir jūsų popierius, Man atrodo, kad Dotarłeś sąrašą geriau valstybei. Dabar, jie geri. Aš ruošiuosi judėti į priekį, keturių ir šešių, gerai atrodo. Ne problema. Šeši aštuoni, Gerai. Aštuoni ir viena, ir kita problema. Nes tai, kas tiesa apie aštuonių ir vienas? Vienas ateina prieš aštuonių, ir taip ką mums daryti? Leiskite apsikeitimo šias dvi. Vienas aštuoni. Ir dabar, aš ruošiuosi nesustoti. Aš ruošiuosi nuolat ieško priekį. Ir pažiūrėkime, kas vyksta. Aštuoni ir trys, ir Žinoma, iš tvarka. Leiskite apsikeitimo. Aštuonių ir septynių, žinoma. Neveikia. Leiskite apsikeitimo. Aštuoni ir penki, žinoma, galime apsikeitimo. Gerai. Sąrašas surūšiuotas. Taip? Gerai, žinoma, nėra. Bet tai šiek tiek geriau, tiesa? Kadangi pranešimas, kas atsitiko. Kiekvieną kartą, kai mes atlikome apsikeitimo mažesniu Taškų rūšies percolated, kad taip, ir didesnis skaičius percolated šį kelią, ar mes pradėti sakydamas burbuliukais į kairę arba į burbuliukais į dešinę. Dabar, tai nėra pakankamai, nes geriausiu skaičius gali persikėlė vienoje vietoje į priekį, arba blogiausiu atveju, skaičius gali būti persikėlė vienoje vietoje toliau. Taigi jūs žinote, ką šis natūra išdirba gana gerai iki šiol. Leiskite man tiesiog pabandykite dar kartą. Dviejų ir keturių, jie Gerai. Keturi šeši, jie Gerai. Šeši ir vienas iš tvarka. Taigi leiskite apsikeitimo jūs abu. Ir dabar, pastebėsite, kad problema s pradeda gauti šiek tiek geriau dar kartą. Šešių ir trijų iš tvarka. Leiskite apsikeitimo jūs abu. Šeši septyni, jūs gerai. Septynios ir penki, žinoma, iš tvarka. Septyni aštuoni, kad. Ir dabar, aš gali tekti tai padaryti dar kelis kartus. Ir iš tiesų, manau sau gal kiek kartų maksimaliai gali turiu vaikščioti pirmyn ir atgal? Mes grįžti prie to. Taigi du keturios tebėra Gerai. Keturi ir vienas, nope. Taigi, tegul apsikeitimo. Ir vėl pastebėti vizualiai viena yra natūra burbuliuoja į kairę, kur ji turėtų būti. Keturių ir trijų apsikeitimo. Keturi šeši. Šeši penki apsikeitimo. Šeši septyni. Septyni aštuoni yra gera. Geras. Mes vis dar geriau. Taigi pažiūrėkime. Dabar, mes turime du ir vienas. Žinoma, apsikeitimo. Dviejų ir trijų, trijų ir keturių, keturi ir penki, šeši ir septyni, septyni aštuoni. Geras. Ir žinote ką? Nes aš padariau vieną pakeitimą ten, leiskite man padaryti vieną normalumas patikrinti. Leiskite man pereiti visą kelią atgal į pradžioje. GERAI. Vienas iš jų, two-- Yup, pamatyti? Kažkas buvo negerai. Trys, keturi, penki, šeši, septyni, aštuoni. Ir šioje paskutinio perdavimo, yra jums patogu su mano dabar tvirtindami, kad yra rūšiuojami? GERAI. Vizualiai tai visiškai teisinga. Bet funkciškai ką nebuvo taip tiesiog atsitikti toje paskutinio perdavimo, kuris leidžia jums patvirtinti, kad šis sąrašas yra iš tiesų rūšiuoti? Ką man daryti, ar ne padaryti šį paskutinį perdavimą? Auditorija: Nebuvo jokių pakeitimų. David J. Malan: Atsiprašome? Auditorija: Nėra pakeitimų. David J. Malan: Nebuvo jokių pakeitimų. Taigi būtų kvaila ir man padaryti tą patį algoritmą vėl jei aš nepadarė keičia pirmą kartą. Ir valstybė nepasikeitė. Žinoma, aš nesiruošia padaryti Bet kokie pakeitimai antrą kartą. Ir taip, tai saugu dabar pasakyti, sąrašas surūšiuotas. Ir iš tikrųjų, tai yra, dabar kažkas, kad mes paprastai kvietimas burbulas rūšiuoti, kuriuo Porinis, Jūs ištaisyti klaidas vėl, ir vėl, ir vėl, ir jūs nesustoti ir atgal, ir pirmyn ir atgal, kol jums atlikti tokius apsikeitimo Ne, kuri vieta galite būti tikri, taip, aš baigė tvirtinimo visus klaidų. Leiskite naujo ir bandykite kitą metodą. Jei jus vaikinai gali grįžti į pavedimas jums buvo metu senumo, kuris atrodė kaip šis. Dabar galime imtis požiūris šiek tiek daugiau kaip egzamino knygos kuriuo buvome nuolat parinkus abėcėlės raidė kad mes rūšies norėjau elgtis su kitais. Gal tai buvo didelė raidė, pavyzdžiui, A, arba mažo raide Z. Taigi kiekvienas atgal tokia tvarka. O dabar leiskite man tai padaryti. Pažiūrėkime, aš žinau, aš turiu aštuoni numeriai čia. Aš ruošiuosi eiti į priekį ir tiesiog sąmoningai pasirinkti mažiausias elementai. Teisė? Tai atrodo intuityviai pernelyg. Kodėl manau, mažiausias elementas, įdėti jį ten, kur jis priklauso, tada gauti kitą mažiausią elementą, įdėti tai jei ji priklauso, ir tik pakartoti. Kadangi intuityviai, kad turėtų per darbą. Taigi keturi, tai yra gana mažas skaičius. Aš ruošiuosi prisiminti, kur tai yra. Palauk minutėlę. Du yra mažesnis. Tegul dabar man prisiminti, kur dvi yra, ir pamiršti apie keturi. Mes spręsti vėliau. Šeši, aš nesu suinteresuotas. Aštuoni, aš nesu suinteresuotas. Vienas iš jų yra mano naujas nedidelis skaičius. Taigi, aš ruošiuosi prisiminti, kur vienas yra. Trys neįdomu. Septyni, neįdomu. Penki neįdomu. Taigi be nukristi etapas šiais metais, Aš ruošiuosi patraukti skaičių one-- ir kas buvo tavo vardas dar kartą? Ananas: Annanas. David J. Malan: Annanas. Ir jei jūs galėtumėte prisijungti su manimi iš sąrašo pradžia, tegul padėti jums, jei jūs priklausote. Unfortunately-- koks tavo vardas? STEFAN: Stefanas. David J. Malan: Stefan į kelią. Taigi prieš Stefan išsprendžia šią problema, ką turėtume daryti? Ką mes darome su Stefan? Auditorija: [nesigirdi]. David J. Malan: Gerai. Taigi, mes galime tai padaryti. Mes galime tarsi imtis Stefan ir jo keturi, ir tiesiog įdėti jį į kintamąjį ir palaikykite jai kai laikotarpis, tokiu būdu kambarį numeris vienas. Ir tai nėra blogai. Galėčiau pasiūlyti, kodėl gi ne mes tiesiog įdėti Stefan čia? Kodėl tai gali pažeisti vieną idėjų mes pradėjome kalbame apie paskutinį kartą, praėjusią savaitę? Taip? Auditorija: [nesigirdi]. David J. Malan: Nėra už jį indeksas. Jei manote, kad tai, iš tiesų, kaip masyvo, tai yra, kaip neigiamas, todėl nėra atminties tikrųjų čia, jei tai iš tiesų masyvas, kaip mes paskelbė praėjusią savaitę paskaita. Taigi, mes turime tai padaryti. Mes galime laikyti jį į kintamąjį. Arba jūs žinote, ką? Aš girdėjau, kad kažkas rodo ją. Ką dar būtų galima padaryti su Stefan? Kodėl ne mes tiesiog iškeldinti jį ir įdėti jį per kur numeris vienas buvo. Taigi, jei norite eiti ten. Ir iš tikrųjų, tai yra gana geras sprendimas. Dabar, viena vertus, aš rūšies Made problemą blogiau. Keturi dabar tolyn iš kur ji turėtų būti. Ji turėtų būti link šio pusę. Bet žinote ką? Tai galėjo būti nepasisekimas. Gal numeris aštuoni buvo čia. Ir taip, gal mes būtume Dotarłeś pasisekė, ir stumti aštuonių arčiau pabaigos. Taigi, dienos pabaigoje, Jis rūšies visų vidurkiai iš. Mums nereikia rūpintis keturi. Viskas, ką aš rūpi dabar yra Pasirinkę mažiausią elementą. Ir dabar, ką aš ruošiuosi padaryti, tai pamiršti apie numeris vienas nuolat, nes žinau, kad Sąrašas už manęs dabar rūšiuojami. Taigi, mano sąrašas buvo anksčiau dydis aštuoni. Dabar, tai dydžio septyni. Taigi, mano problema yra gauti mažesni, nors tiesiškai. Taigi dabar aš ruošiuosi pasirinkti Dabartinė mažiausia elementas, du. Šeši, aštuoni, keturi, trys, septyni, penki. Tai buvo mažiausias elementas. Taigi, ką aš ketinu daryti with-- kas buvo jūsų vardas vėl? JOSEPH: Juozapas. David J. Malan: Juozapas? Mes ketiname palikti Juozapą vietoje. Dabar aš ruošiuosi apsimesti kad šie vaikinai are-- gerai, Žinau, kad šie du jau rūšiuojamos. Tegul dabar orientavimą į likusi sąrašo. Šeši yra dabartinė mažiausių. Aštuoni yra didesni. Keturi dabar dabartinė mažiausių. Trys dabar dabartinė mažiausių. Ir todėl dabar aš ruošiuosi pasirinkti tris, kas is-- koks tavo vardas dar kartą? SERENA: Serena. David J. Malan: Serena, jei galėtumėte patraukti savo numerį ir apsikeitimo with-- KALSANG: Kalsang. David J. Malan: Kalsang. Nagi atgal, ir mes ketina sukeisti šių dviejų. Ir dabar, tegul įdėti šią autopilotas. Aš ruošiuosi eiti ir palikti jį jums vaikinai Norėdami pasirinkti kitą smulkiausius elementus. Dun Dun Dun Dun. Taškų keturi, ką daryti? Puikus. Dabar aš ruošiuosi padaryti kitą perdavimo. Dun Dun Dun Dun. Matau penkių yra šalia mažiausias. Dabar aš ruošiuosi fotografuoti kitą perdavimo. Dun Dun Dun Dun. Šeši yra mažiausias. Geras. Septynios yra mažiausias. Jokių pokyčių. Aštuoni yra mažiausias. Atlikta. Taigi, ką mes ką tik padaryta keletą kartų pasirenkant vieną elementą po kito yra įgyvendinti kažką, kad mes ketina įteisinti kaip atrankos rūšiuoti. Ir tai gal net paprasčiau paaiškinti, tuo, kad tiesiog viskas, ko jums noriu padaryti, tai tiesiog laikyti vyksta ir atgal per sąrašą atrankos, kitą mažiausias elementas, kol baigsite. Taigi tai dar paprasčiau, galbūt intuityviai, nei paskutinis. Pabandykime vieną paskutinį vienas. Jei jus vaikinai gali iš naujo save į šias pozicijas Vienas galutinis laikas, pažiūrėkime, jei mes negalime dabar įteisinti vieną kitą požiūrį. Tiesą sakant, būtų kažkas ten norėčiau pasiūlyti kaip kitaip mes galime eiti apie tai daro? Be supimas iš buzzwords ar rūšiuoti atsakymų, kurie jau žinomi, tiesiog intuityviai, ką galėtume padaryti? Auditorija: [nesigirdi]. David J. Malan: Taip. Taigi ten puikiai intuicija ten. Geri dalykai atrodo, kad taip atsitiktų šiol kompiuterių mokslo, kai mes padalinti ir užkariauti padalinus problemą jis per pusę, o kitą pusę ir pusę. Ir taip iš tiesų, mes gali pradėti tai daryti. Ir iš tiesų, kad tai bus, mes matyti, vienas iš mūsų geriausių sprendimų dar. Bet tegul grįžti į, kad iki ilgai. Tiesą sakant, mes ketiname daryti kad šiek tiek vėliau šią savaitę. Ką dar gali darome išspręsti tai? Taigi visi čia yra atrodytų, atsitiktinė tvarka. Zinai ka? Užuot eiti pirmyn ir atgal, pirmyn ir atgal, pirmyn ir atgal, kiekvieną kartą, tai jaučiasi Darau daug vaikščioti. Kodėl ne aš tiesiog prasideda iš sąrašo pradžia, ir tiesiog įdėti keturis, jei ji priklauso? Taigi leiskite man už tą akimirką, kad Mano sąrašas tik tai pirmasis elementas. Yra keturių rūšiuojami šiuo momentu, jei viskas, ką aš rūpi viskas čia? Tai tarsi banaliai tiesa, tiesa? Kaip sąrašą, kuriame vieną numerį ir šis skaičius keturių akivaizdžiai rūšiuojami. Taigi leiskite man tiesiog nurodoma, kad šis sąrašas surūšiuotas. Bet dabar turiu šį sąrašą pailsėti. Taigi, dabar, aš susiduria du. Kur du akivaizdžiai priklauso susijusių su keturių? Prieš keturias. Taigi, ką aš galiu padaryti čia? Koks jūsų vardas vėl? JOSEPH: Juozapas. David J. Malan: Juozapas jei galėtų atsitraukti tik už akimirką su savo numeriu. Ir dabar kas turėtų Stefanas padaryti čia? Leiskite pereiti Stefan čia. Ir dabar, tegul Juozapas atėjo čia. O dabar leiskite man teigti, kad Viskas čia yra rūšiuojami. Taigi, panašus rezultatas, bet iš esmės skiriasi požiūris. Aš net mačiau, kas ten. Aš tiesiog gertumėte elementai kaip jie įteikė man ir su jais susidoroti. Taigi dabar, matau skaičių šeši. Kur numeris šešių priklauso? Mes turime du, keturi, šeši. Tiksliai ten, kur ji yra dabar. Taigi palikime, kad vieni, ir dabar teigia, kad šio sąrašo dalis dabar rūšiuojami. Ir taip, tai jaučiasi iš esmės skiriasi tuo, kad aš tiesiog juda per sąrašą čia tiesiškai, ir aš niekada dvigubai atgal. Taip. Gerai. Taigi aštuoni, kur jūs priklausote? Štai čia. Tobula. Taigi dabar, vienas. Uh Oh. Tai jaučiasi tai bus brangus. Dabar, ankstesnį algoritmas, Aš tiesiog pavertė žmones. Taigi galiu įdėti jį visą kelią ne pradžioje, tačiau vėliau persikėlė Juozapą. Bet jei aš judėti Juozapą, dabar kas bus negerai? Dabar, aš tarsi undone-- aš imtasi vieną žingsnį į priekį ir tada vienas žingsnis atgal, nes dabar Juozapas būtų iš eilės. Taigi leiskite tai padaryti. Jei galėtų imtis numeris vienas ir žingsnis atgal tik akimirką. Kaip mes galime put-- ką buvo jūsų vardas vėl? Ananas: Annanas. David J. Malan: Ananas vietoje? Kas turi įvykti, atsižvelgiant į dviejų, keturių, šešių, o aštuonių? Jie visi turime pereiti. Taigi, jei aštuoni norėtų pereiti pirma, tada šešių, tada keturių, tada du. Ir tada Annanas, jei norite patinka ateiti čia gera. Bet čia mes ką tik rūšies sumokėjo kainą skirtingu taško algoritmą. Kadangi paskutinį kartą su atrankos Rūšiuoti, ir net burbulas rūšiuoti, Aš einu atgal ir pirmyn, pirmyn ir atgal, kuri yra tikrai sudėjus laiko atžvilgiu, ir tiesiog palaipsniui. Įterpimas rūšiuoti, iš pradžių žvilgsnis, atrodo, kad jis yra Super protingesni, nes aš tiesiog priėmimo lėtai ir laipsnišką pažangą, bet aš nesiruošia tai pirmyn ir atgal. Bet jei kas nors iš tiesų yra iš eilės, pranešimu visus darbus aš tiesiog turėjo tai padaryti. Aš turėjo judėti pusė sąrašo tiesiog padaryti kambarį numeris vienas. Taigi, tai ta pati suma Darbo šiol ją jaučiasi, tik skirtingo tipo darbo. Leiskite tęsti. Taigi, dabar mes žinome, kad kiekvienas tarp vieno ir aštuonių rūšiuojami. Čia turiu numeris trys. Jei jums patinka pasiimti numeris trys, žingsnis atgal vieną. Ir ką jūs vaikinai reikia daryti? Yep. Štai dar vienas, du, trys žingsniai. Trys laiko vienetais, kurie tiesiog kainuoti me, todėl, kad trys dabar gali tilptų. Galiausiai, septyni. Vykime į priekį ir turi Jums žengti žingsnį atgal. Tai tik ketina kainavo mums vienas vienetas metu, bet viskas OK. Ir dabar, penkių ketina būti šiek tiek daugiau brangi. Jei norite atsitraukti. Turime judėti aštuoni, septyni, o šeši. Ir tada visi dabar rūšiuojami. Taigi didelis ranka mūsų savanoriai čia. Labai ačiū. [Plojimai] Ačiū jums visiems. Ačiū jums visiems. Taigi pažiūrėkime, dabar tik kaip brangu visa tai buvo. Apsvarstykite, ko gero, Paprasčiausias iš jų, burbulas rūšiuoti. Ir aš sakau, paprasčiausias, tik dėl to, galite ją išspręsti godžiai tiesiog nustatyti Porinis problema čia. Pritvirtinkite Porinis problemą čia vėl ir vėl ir vėl, kartojant, nes daugelis kartų, kiek iš tikrųjų reikia. Taigi, tai Pasirodo, kad su burbulas rūšiuoti, gerai, kiek žingsnių turiu imtis pirmasis perdavimas šio algoritmo? Galėčiau take-- tegul see-- vieną, dviejų, trijų, keturių, penkių, šešių, septynių. Ir ten aštuonis elementus čia. Taigi, tai, kaip n atėmus 1 žingsnių gauti iš sąrašo pradžioje į sąrašo pabaigoje. Bet su atrankos rūšiuoti, priminti, kad aš vėl ir vėl pasirinkdami elementus ir vėl, kad mažiausias, Aš pradėti jį į vietą, bet tada aš nesu ieško už manęs dar kartą. Taigi, aš manau, kad tai šiek tiek daugiau aišku tada, kad pirmą kartą, galiu turi imtis visų n minuso veiksmus nuo 1 rasti mažiausią elementą. Tada aš įdėti juos į vietą, ir aš iškeldinti kas čia buvo anksčiau. Bet tada aš neturiu nuolat ieško šio elemento, nes aš žinau, tai jau mažiausias. Taigi, dabar, aš galiu pažvelgti tik septyni elementai, tada šeši elementai, tada penki elementai, tada keturi elementai. Ir taip matematiškai, jei n yra iš elementų ar numerių kad mes pradėjome, galite įsivaizduoti, , kad tai yra tas pats, kaip n minus 1, plius n ± 2 žingsniai, plius n atėmus 3 žingsniai, plius n minus 4 žingsniai, visi kelią žemyn tik vienas žingsnis. Ir aš tikiu, mano paskutinis žmogus. Ir jei jūs prisimenate, kad daug nuo statistika knygas ar matematikos knygas turi tas formules ant Kieti atgal arba priešais juos, paaiškėja, kad šios serijos gali būti išreikštas daugiau tiesiog N kartų n atėmus 1 per 2. Ir tai gerai, jei tai ne ne savo proto priešakyje. Bet tai tiesa. Tai tiesiog paprastesnis būdas jį raštu. Ir tada, jei jūs manote Atgal į pradinėje mokykloje, kai jūs tiesiog pradėkite dauginant dalykų, ši žinoma, tiesiog n kvadrato atėmus n padalytą iš 2. Viskas, ką aš padariau yra išplėsti pasakymai ten. Ir todėl galime perrašyti šio šiek tiek kitaip. Štai N kvadratėliais padalintas 2 minus n / 2. Taigi dar kartą, aš tiesiog rūšies taikymo kai aritmetinis ten taisykles. Tačiau pastebėti, kad dabar didžiausias terminas Šioje išraiška, taip sakant, yra tai, kad n kvadrato. Ir taip, tai n kvadratu padalytą iš 2, atėmus n / 2. Tačiau paprastai, jei n yra bus didelis vertė, Aš ruošiuosi teigia, kad n kvadratu bus dominuojantis veiksnys. Tai tiesiog bus didesnis indėlis į žingsnius nei N / 2 numeriu. Taigi, ką aš turiu galvoje tai? Pabandykime paprastą pavyzdį, net nors matematikos gauna šiek tiek didelis. Taigi tarkime, mes turėjome 1 milijonas žmonių scenoje, arba 1 mln dalykų kad mes norime rūšiuoti. Leiskite prijungti mln į lygiai tą formulę pamatyti, kiek žingsnių užtrunka viso rūšiuoti milijoną elementus naudojant tarkim, pasirinkimas rūšiuoti. Taigi, mes norime turėti tą pačią formulę kaip ir anksčiau. Aš prijunkite milijono, kad gaunu milijono kvadratėliais padalintas iš 2, minus mln padalytą iš 2. Jei aš padaryti, kad matematikos anksto čia mes turime 500 mlrd atėmus 500000, kuris suteikia mums 499999500000, kuris yra pretty darn didelis. Iš tiesų, jei jūs palyginkite dabar 499000000000 999 milijonų eurų, 500.000 prieš mūsų pradinės vertės, 500 milijardų, tai taip velniškai arti. Teisė? N kvadratėliais padalintas 2 suteikia us-- ar veikiau, N kvadratėliais padalintas iš 2 davė mums 500 mlrd. Štai pretty darn Uždaryti į 499,999,500,000, kuri yra pasakyti atimant nuo 500,000, arba apskritai, atimant išjungtas n kvadratu, tikrai ne big deal. Pagal "n kvadratu daro šias numeriai auga tikrai greitai. Dabar, tai yra svarbus tik tiek, kaip mes, kompiuterių specialistų, paprastai nesiruošia taip rūpinatės apie šių formulių niuansų ir būtent tai, ką Tikslios atsakymai. Mes rūpinamės tik, kad jūs žinote, ką? Tuo dienos pabaigos, ši formulė yra ant tam, n kvadrato. Taip, mes padalinus iš 2 ten. Taip, mes atimant išjungta n ± 2. Bet dienos pabaigoje, terminas kad tikrai skauda su mumis ir mums kainuoja žingsnių daug yra tai, kad kvadrato sąvoka. Ir taip, ko kompiuterių mokslininkas ketina paprastai padaryti yra ignoruoti visus tuos mažesni pavedimo sąlygas, ir tik pažvelgti į vieną, kad prisideda į sąnaudas labiausiai. Ir tai yra gražus, nes mes galime dabar kalbėti daug daugiau bendrumo apie algoritmų, ir gali juos palyginti. Ir tai, kad aš Naudojant šią O yra sąmoningas. Kai aš sakau, pagal užsakymą apie, aš specialiai nuoroda į kažką vadinamas didelis O. didelis O yra notacija, kad kompiuteris mokslininkas naudoja apibūdinti viršutinė riba kažką. Taigi, jei jūs sakote, kad algoritmas yra didelis O n kvadratu, kaip aš pasiūliau tik akimirka prieš tai reiškia, kad kad, kalbant apie jos veikia laikas arba jo efektyvumas, jis įgauna tam n kvadrato žingsnius. Gal daugiau, gal mažiau. Bet tai ant n Kad kvadrato. Ir tai viršutinė riba. Jis nesiruošia būti labiau skausminga, nei nurodyta. Jis nesiruošia būti n kubeliais, arba 2 į N, ar kažkas daug daugiau. Tai viršutinė riba ant kokio kad kaina yra. Taigi atsižvelgiant į tai, tegul mano tik keletą pavyzdžių. Ir tai tik baigtinis sąrašas labai dažni bėgimo kartų algoritmai, kurie reiškia būti iliustruoja kai kurių dalykų mes matyti jau. Taigi, pavyzdžiui, tokiais atvejais, kai pasirinkimas rūšiuoti, ką aš teigdamas čia yra, kad atrankos Rūšiuoti bėga laikas yra ant n siekiant kvadrato. Blogiausiu atveju, aš ruošiuosi visa krūva atsitiktinių skaičių čia. Ir kaip mes matėme matematiškai, jei aš nuolat vaikščioti per sąrašą, per sąrašas, pasirinkdami kitą mažiausias elementas vėl ir vėl, jei aš iš tikrųjų užsirašyti visus veiksmus, Aš atsižvelgiant, kaip aš formulaically pasiūlė anksčiau, tai nuo n kvadratu tam žingsnių, kad aš vartojate. Ir paaiškėja, kad burbulas rūšiuoti bei įterpimo Rūšiuoti yra lygiai taip pat lėtai, blogiausiu atveju. Apsvarstykite, pavyzdžiui, įterpiant rūšiuoti, labai paskutinis algoritmas mes nagrinėjami, kuri turėjo mums pažvelgti į elementą, ir įdėkite jį ten, kur jis priklauso. Ir tada mes pažvelgė į kito elemento, ir įterpiamas jį ten, kur jis priklauso. Taigi mano geriausią įmanomą scenarijų. Tarkime, aš turėjau savanoriai išsirikiuoti pažodžiui, kaip šis, vienas per aštuonių, jau rūšiuojamos. Kiek žingsnių yra įterpimo Rūšiuoti ketina imtis rūšiuoti aštuoni žmonės, jei jie atvyksta į sceną ieško patinka tai? Aštuoni žmonės jau rūšiuojamos. Ir aš naudoju įterpimo rūšiuoti. Tai paskutinis iš algoritmai. Na, tegul Kartoti labai greitai. Taigi, jei aš pradedu čia matau vieną. Kur vienas priklauso? Jis priklauso čia. Matau du. Kur du priklauso? Štai čia. Matau tris. Kur trys priklauso? Štai čia. "Aš matau keturis. Štai čia. Penki, šeši, septyni, aštuoni. Nėra jokios priežasties, kad pasikartosiu. Ir taip, kiek žingsnių yra tai, kad, kalbant apie n? Tai ant n tvarka žingsniai, tiesa? n atėmus 1. Bet aš paėmė linijinis skaičių žingsnių, ir dabar aš padaryti. Taigi, kad geriausiu atveju, nors. Ką apie blogiausiu atveju? Kas aštuoni buvo ten, o septyni buvo ten, ir vienas ir du buvo per čia, todėl kad šis sąrašas buvo tikrai pasikeitė? Na, kas atsitinka iš tikrųjų jei tai yra numeris? Ir mes padarysime tik keletą pavyzdžių. Ką daryti, jei, žinoma, numeris aštuoni yra čia ir number-- šūksniais. Taigi ką daryti, jei iš tiesų, skaičius aštuonių yra visą kelią per čia ir aš naudoju įterpimo rūšiuoti? GERAI. Aš teigia šiuo metu jis yra vietoje. Bet dabar, seven-- kur nėra septynių eiti? Žinoma, jis eina čia. Taigi turiu judėti aštuoni per vieną vietą. Dabar šešių, kur ji eiti? Na, viskas gerai. Dabar, aš turiu judėti aštuoni per vieta, o septyni per vietą, ir tada aš pop žemyn šeši. Taigi, pirmą kartą, ji išlaidų man vienas žingsnis siekiant nustatyti dalykus, tada jis man kainavo du žingsnius nustatyti dalykus. Kiek žingsnių tai ketina imtis nustatyti dalykų, kuriuos reikia sudėti penkias reikiamoje vietoje? Trys. Kadangi dabar turiu judėti vienas, du, trys. Kiek žingsnių ji ketina imtis įdėti keturi reikiamoje vietoje? 4 plius 5, plius 6, plius 7. Ir todėl matematiškai identiška ką mes aprašyta atrankos rūšiuoti. Mes turime šią seriją tai tik didėja. 1 plius 2 plius 3 plius 4, arba atvirkščiai, 7 plius 6 plius 5 plius 4 išauga iki šiandienos tikslais ant n Kad kvadrato. Taigi leiskite man nurodoma, kad per burbulas rūšiuoti taip pat n kvadratu. Kadangi su burbulas rūšiuoti, kiekvieno kartą aš einu per sąrašą, Aš atsižvelgiant maždaug kiek žingsnių? Kiekvieną kartą, kai aš tiesiog vaikščioti iš ten į ten? Maždaug n žingsnių. Bet kiek kartų galėčiau reikia eiti per sąrašą? Na, maždaug n laiko. Gal n atėmus 1, tačiau maždaug n kartų. Na, kodėl taip yra? Na, su burbulas rūšiuoti, jei mes pradėti su burbulas rūšiuoti, su blogiausiu įmanoma sąrašą situacija, kuri vėl yra visiškai atgal, kas nutiks? Aš einu per sąrašą, ir numeris vienas priklauso visą kelią ten. Bet su burbulas rūšiuoti, kiek daro vieną perkelti ant mano pirmojo prasiskverbimo per sąrašą? Kiek taškų jis prieina arčiau teisingoje vietoje? Tik vienas. Taigi, jei jūs rūšies priežastis per tai, kiekvieną kartą, per šį algoritmą, Dovydo atsižvelgiant maždaug n žingsnių. Bet kiek eina Sąraše yra ją ketina imtis vienas burbulas į kairę, kur jis priklauso? Kamuolys atšoko judėti kaip, n erdves šiuo būdu. Taigi tiesiog padaryti rūšiavimą sąrašo, Turiu vaikščioti pirmyn ir atgal n kartų. Ir kiekvieną kartą, aš žiūri n elementų. Taigi, tai n dalykų n kartų iš n Kad kvadrato. Dabar mes pamatysime kai iš šortai yra įdėta į CS50 naujos problemos nustatyti, kitą metodą ne tai, Bet dabar, tegul tiesiog apsvarstyti kai kurių kitų bėgimo kartų, ypač jei rūšiavimo tie imtis šiek tiek laiko, kad kriaukle. Kas yra algoritmas mes matėme jau kad įgauna n žingsnių tam,? Kas turėtų imtis linijinis skaičių žingsnių, kad mes matėme iki šiol? Kas tai? Telefonas katalogas paiešką. Pirmasis algoritmas. Teisė? Kur mes tiesiškai ieškoti Mike Smith? Išties. Nuo nulio savaitę, kai aš pradėjau sukant vieną lapą vienu metu, ir aš net sakė, kad jis buvo natūra linijinio jausmas algoritmas, ir mes turėjome tą nuotrauką ant lenta su tiesiu raudona linija ir tiesiai geltona linija, tai buvo iš tiesų algoritmai, kurie yra didelis O n. Kadangi rasti Mike Smith telefoną knyga n puslapių, blogiausiu atveju, gali pasiimti mane n veiksmus. Ką apie vartojate lankomumą? Vienas du trys Keturi Penki Šeši. Koks veikimo laikas apie tai algoritmas, atsižvelgiant lankomumą? Didelės O n, nes teoriškai aš turi atkreipti visus į kambarį. Dabar, kaip panaikinti, ką apie kita optimizavimas nuo nulinio savaitę? Dviejų, keturių, šešių, aštuonių, 10, 12. Kompiuterių mokslininkas būtų suvokti, palauk, tai remiantis tam N, padalytą iš dviejų etapų. Teisė? Nes aš darau du žmones vienu metu. Tačiau mes ketiname ignoruoti Šios žemesnės pavedimo sąlygas, ir mes tik ketina išmesti padalinti iš 2, ir tiesiog pasakyti, didelis O n už šio algoritmo taip pat. Ką manai apie šį? Mes praleisti kai kurie iš jų, bet ką buvo algoritmas, kuris buvo žurnalo n? Tam prireikė maždaug log n veiksmus? Skaldyk ir valdyk. Būtent. Patinka telefonų knygos pavyzdžiui, nulis savaitę ir anksčiau šiandien, kur mes suskirstyti problemą vėl ir vėl ir vėl. Mes išsitraukė jį ant lentos į savaitę nulis kaip lenkta žalia linija, ir sakėme, kad diena buvo logaritminis algoritmas. Ir iš tiesų, numerių veiksmus, kurių ji mano, kad atlikti skaldyk ir valdyk, arba dvejetainis paiešką kaip mes pradėsime vadindami jį, kaip į telefonų knygą, yra ant log ir priemones, tvarka. Ir tai yra keistai vienas bitas. Kas užima vieną žingsnį, arba, konkrečiau pastovus pakopų skaičius? Gal tai dvi, o gal tai trys, bet kompiuteris mokslininkas tiesiog supaprastina jį kaip didelis O 1, kai nuolatinis pakopų skaičius. Kas ką galite padaryti, kad mano pastovų skaičių žingsnių? Koks veikimo laikas plojimai? Pastovus laikas. Teisė? Kaip, kas yra veikimo laikas daro viską, kad turėjo tik vieną operacija, kaip spausdinti F Hello World. Tai gali būti laikomas pastovus laikas, nebent mažiau kampe atveju su spausdinimo F, kas gali veikimo laiką Spausdinimo F tikrųjų? Ir kodėl? Tai, kas yra n matavimo tuo atveju? Auditorija: [nesigirdi]. David J. Malan: Būtent. Simbolių skaičių mes norime spausdinti. Taigi tai labai konteksto. Šiandien mes jau dėmesio daug apie raidės ir skaičiai čia ant lentos. Tačiau ji taip pat gali būti simbolių faktinė eilutę. Taigi paaiškėja, yra dar vienas priemonė, kuri pradės rūpintis, ir tai yra priešinga stambaus O, taip sakant. Štai Omega notacija. Kadangi didelis O tai kas, The viršutinė riba nuo jūsų važiavimo laikas? Maksimaliai, kiek laiko gali kas nors imtis? Omega-- Atsiprašome Tai apsaugo ateina up-- yra, kad priešais, kuriuo tai apatinė riba laiką kažkas gali imtis. So. Pavyzdžiui, kas yra algoritmas kad mano visada n kvadratu veiksmus? Na, vienas iš algoritmų mes matėme šiandien, iš tikrųjų, gali būti, kad taip pat. Atrankos rūšiuoti. Atrankos Rūšiuoti gana kvaila. Net jei algorithm-- Atsiprašome, net jei masyvas jau rūšiuojamos, pasirinkimas Rūšiuoti ketina nuolat vaikščioti per sąrašą įsitikinkite, kad jis yra mažiausias elementas vėl ir vėl ir vėl. Ir net jei žmogaus veiklos rezultatas publika žino, kad, palauk, Jūs jau praėjo mažiausias elementas, kompiuteris nežino, kad tol, kol ji atrodo visą kelią per sąrašą. Panašiai, apatinė, kad Taip pat gali būti atsižvelgiama į gali būti linijinė laiko. Kiek laiko užtrunka Rūšiuoti n elementų geriausias atveju naudojant kažką panašaus burbulas rūšiuoti? Tarkime, kad jūsų sąrašas yra jau išspręstos. Mes pasakė burbulas rūšiuoti įgauna iš n Kad kvadrato veiksmus. Bet kas, jei jis jau rūšiuojami? Ką daryti, jei jūs suprasite, kai vienas pro masyvo kad jūs atlikote jokių apsikeitimo? Ar jums reikia išlaikyti priimant daugiau eina? Ne. Taigi apatinės burbulas rūšiuoti gali būti laikomas linijinė. Omega-n. Ir mes galime pažvelgti į kiti šių, taip pat. Taigi leiskite priimti greitai pažvelgti ne tik vizualizacijos čia pamatyti, kaip jie atskirti save. Aš ruošiuosi eiti čia į tai puslapis tai galima rasti C50 tinklalapyje, tačiau ji bus skausmas gauti darbo, nes jis naudoja technologiją, vadinamą Java programėles, kuris yra daugiausia nepalaikomas šių dienų, bent Chrome ir tam tikrų kitų. Ir leiskite man eiti į priekį ir pagreitinti šį aukštyn ir paaiškinti, kas vyksta. Tai yra burbuliukų demonstravimo Rūšiuoti pirmasis algoritmas mes pažvelgė. Ir tai, kad vizualizacija kiekvienas Šių barų reiškia skaičių. Kuo didesnis baras, Kuo didesnis skaičius. Kuo mažesnis baras, mažesnis skaičius. Ir tai, ką jūs galite pamatyti vizualiai, net nors tai vyksta super greitai, yra tai, kad raudona juosta yra panašus į mane, vaikščioti pirmyn ir atgal nustatymo problemas. Jūs galite pamatyti, kad didesni elementai iš tiesų burbuliuoja iki dešinę, ir mažesni elementai yra burbuliuoja iki kairę. Ir žemyn čia, jei mes realiai atrodo geriau, mes iš tikrųjų galime suskaičiuoti skaičius palyginimais ir apsikeitimo kad buvo daroma. Bet vietoj to, pažiūrėkime antroje algoritmu mes pažvelgė anksčiau su mūsų savanoriai, atranka rūšiuoti. Vizualiai jis turi labai skiriasi poveikis. Bet tai vėlgi labai intuityvus, į kad mes nuolat pasirinkdami kitą mažiausias elementas, ir mes turime šiek tiek pasisekė. Tai pajuto esmės greičiau. Bet jei mes bėgo tai vėl ir vėl ir vėl su daug įėjimų, mes norėtume pamatyti, kad tai iš tiesų dar didelis O n kvadratu. Darom paskutinį vieną čia įterpimo rūšiuoti, kuri buvo trečioji algoritmas mes pažvelgė ir atšaukimo kad tai vienas susijęs su elementai, kaip ji susiduria juos, bet tada jis gal pamainomis viskas per padaryti kambarį, įterpiant elementus, jei jie priklauso. Ir tai taip pat baigiasi suteikiant Galutinis rezultatas. Dabar visi tie trys jaučiausi gana greitai. Ir iš tiesų, išbėgau juos ne gana gera klipas. Bet iš esmės, jie visi gana siaubinga, būti sąžiningiems. Visi šie algoritmo šiol kad paleisti į didįjį O n kvadratu imtis gana šiek tiek laiko paleisti į pabaigoje. Ir iš tiesų, mes galime pamatyti, ir manote, kad tai galiausiai jei aš atsigriebti šį trečiąjį ir galutinis demo. Tai yra dar vienas vizualizacija, kad vyksta rodyti burbulas rūšiuoti kairėje, pasirinkimas Rūšiuoti centru, ir kažkas, kaip vienas iš mūsų ranka kelia anksčiau siūlė, sujungti rūšiuoti dešinėje. Skaldyk ir valdyk strategija dešinėje. Ir tai, tiesą sakant, tai, ką mes ketiname ieškoti trečiadienį. Bet tegul laiko juos lygiagrečiai. Tai beveik tas pats numeris elementai, visų veikia tuo pačiu metu. Burbulas rūšiuoti vs atrankos Rūšiuoti vs merge rūšiuoti. Dabar jie visi veikia teoriškai, tuo pačiu metu. CPU veikia pačiu greičiu, bet jūs gali jaustis kaip nuobodu tai labai greitai taps, ir tiesiog, kaip greitai, kai mes švirkšti savaitę tiek Zero algoritmai gali mes pagreitinti. O dabar tegul palyginti tai vienoje paskutinio forma. Aš ruošiuosi eiti į priekį į CS50 tinklalapyje, kur mes turime šį galutinį adreso šiandien kai kažkas į internetą Maloniai sudėti vaizdo įrašą, kuris fiksuoja Kokios rūšiavimą algoritmai skamba. Tai įterpimo rūšiuoti. [Pypsėjimas] Drauge jūs kreipiatės dažnį remiantis brūkšniniu juostoje aukščio. Tai burbulas rūšiuoti. [Deformuotas pypsėjimas] Coming Up Next is-- ateina Kitas is-- pasirinkimas rūšiuoti, kur vėl, mes pasirinkdami Kitas mažiausias elementas, ir mes galime pamatyti, kad auga iš kairės į dešinę. Sujungti rūšiuoti, todėl mūsų nugalėtojas kas šiandien. Atkreipkite dėmesį, kaip jis padalinus dalykus į [nesigirdi] pusė ir ketvirčiai. Gnome Rūšiuoti, kurį mes turime ne kalbėjo apie, ir sukuria vizualiai ir audally iš šiek tiek skirtingos formos ir sveiki. Ėjimas pirmyn ir atgal, Valymo dalykų. Taip pat patikrinkite heapsort dėl šios vaikino svetainėje. Ir tai viskas. Pamatysime, jums kitą kartą. [WHOOSHING ir muzika]