[Mūzikas atskaņošanas] DAVID J. Malan: Nu labi. Tik laipni atpakaļ. Tas ir CS50, un ir beigām, trīs nedēļas. Tātad atgādināt vairāku pēdējo nedēļu laikā, mēs esam izdevumu diezgan daudz laiks C, uz plānošanu, par sintaksi. Un tas ir pavisam normāli, ja jūs joprojām cīnās ar problēmu Set 2, lai būtu banging galvu pret sienu. Tas ir mistisks vērstu kļūdu ziņojumi un bugs, ka jūs nevar gluži tramdīt leju. Jo, drošs, ka tikai Dažu nedēļu laikā jūs varēsiet atskatīties uz lietas, piemēram, Cēzara, un [? V-genair,?] varbūt pat kreka, un saprast, cik tālu Jūs esat nonācis īsā laika periodā. Tātad, ja tas ir kāds mierinājums, karājas tur tagad. Šodien, lai gan, mēs sākam pāreju līdz lietas augstākā līmenī. Un mēs sākam pieņemt par pašsaprotamu, ka jūs guys zināt, kā programma, vai vismaz iesākums ka komforta līmeni. Un mēs sākam apsvērt, kā mēs varam iet par projektēšana programmu vairāk efektīvi. Kā mēs varam iet par optimizēt efektivitāti mūsu algoritmiem, un parasti risināšanā vairāk interesanti problēmas. Un sāk pieņemt par pašsaprotamu, ka, ja mēs vēlējāmies, mēs varētu kodēt nekādus no piemēriem ir prātā. Tātad šodien, mums nav pieskarties tastatūru jebkura veida kodu. Tas būs daudz augstākā līmenī, un galu galā, par problēmu risināšanas. Tātad, lai saņemtu uz šo jautājumu, ļaujiet man piedāvāt ka šādi septiņi taisnstūri veido septiņas durvis, aiz kas ir visai ķekars numuri, starp kuriem ir skaitlis 50. Ļaujiet man projekts šo par šo Ekrāns arī šeit. Un ierosina, ka mums ir nepieciešams brīvprātīgo palīdzēt atrast man numuru priekšā internets šeit, lai aplūkotu. Nāciet uz augšu, rozā. Labi. Kāds ir Jūsu vārds? Jennifer: [dzirdams] DAVID J. Malan: Atvaino? Jennifer: Jennifer. DAVID J. Malan: Jennifer. Visas tiesības, Jennifer. Priecājos ar jums iepazīties. Nāciet uz augšu. Tātad, tie šeit ir septiņi durvis, un kādi Es gribētu, lai jūs darīt mums šeit, priekšā visiem saviem klasesbiedriem, ir mūs atrast numuru, 50. Lai atrastu numuru, jūs varat palūrēt aiz kāda no šīm durvīm, vienkārši pieskaroties uz vienas no durvīm, un atklās savu numuru. Un pieņemsim redzēt, cik ātri jūs var atrast mums numuru, 50. 15. 16. 50. Labi darīts. Labi. Kārta aplausi par Jennifer. [Aplausi] Labi. Tātad, kādi bija jūsu stratēģija atrast numuru, 50? Jennifer: Um, es domāju, varbūt, ja - [Dzirdams] DAVID J. Malan: Ak. Piešķiriet vienu sekundi. Tātad bija jūsu stratēģija atrast numuru, 50? Jennifer: Tāpēc es tikai sākas sāk redzēt to, ko pirmais numurs bija, un tad es domāju, varbūt, ja viņi sakārtoti, es ņemšu tikai glabāt pieskaroties augstāk? DAVID J. Malan: OK. Un mēs, šķiet, esam atraduši kas ir gadījums. Lai gan, pieņemsim mizu atpakaļ slāņi tikai mazliet, un jūs vēlaties doties priekšu un atklāt citas durvis jūs varētu izvēlēties? Jennifer: Ak, mīļais. DAVID J. Malan: Ah. Jennifer: Tāpēc es tikko saņēmu laimīgs. DAVID J. Malan: Tātad jums laimīgs. Labi. Tātad nav slikti. Bet tas ir interesanti ieskatu, vai ne? Ja jūs pieņemts, un jūs saņemsiet, tiešām, mazliet laimīgs tur. Bet, ja tu pieņem, ka to skaits bija sakārtoti, jūs varat būt precīzāks par to, kā tas ietekmē jūsu uzvedība? Jennifer: Tātad, ja tie sakārtoti, es domāju, varbūt mazākā līdz lielākajam. DAVID J. Malan: OK. Jennifer: Vai, ja tas beidzās ar to, tiešām liels, tad vislielākā uz vismazāko. DAVID J. Malan: OK. Tātad vislielākā uz vismazāko, vai vismazākās līdz lielākais. Bet ļaujiet man piedāvāt, pieņemsim, ka jums bija gotten nelaimīgs, un pieņemsim, ka viņi nebija, patiesībā, šķiroti, cik no šīs durvis varētu jums bija palūrēt aiz ka sliktākajā gadījumā? Jennifer: Visi no tiem. DAVID J. Malan: Visi no tiem. Tā ļauj vispārināt, ka n. Tur notiek, ir 7, bet pieņemsim vairāk Parasti saka, tur ir n durvis ekrāns šeit. Tātad, sliktākajā gadījumā, jums būtu meklēt aiz 7 durvīm, vai n durvīm. Un tā tas tiešām ir, tas ir mazliet veiksmi šodien, bet tas tiešām lineārs algoritms par veidu, pat ja jūs bija sava veida izlaižot apkārt. Vai tas ir godīgi? Jennifer: Jā. DAVID J. Malan: Nu, ļaujiet man redzēt, ja jūsu stratēģija izmaiņas, ja es pārceļos mūs uz Mūsu Otrs piemērs šeit ar 7 dažādas durvis. Paši skaitļi, bet šī reizi, kad tie ir sakārtoti. Kāds ir jūsu stratēģija šeit būs, mēģinot nodot no sava prāta, kas pārējie skaitļi bija - Jennifer: OK. DAVID J. Malan: - agrāk? Jennifer: Sāksim ar pirmo. DAVID J. Malan: Nu labi. Sākt ar pirmo. 4. Tagad, ja jūs plānojat doties, un kāpēc? Jennifer: 4, ir ļoti mazs. Tātad, ja viņi veida varbūt mazākā uz lielāko, tas būtu būt divreiz, ka, un -. DAVID J. Malan: OK. Let 's redzēt, ko jūs domājat? Jennifer: Mēģiniet pēdējais. Nice. DAVID J. Malan: Ļoti labi darīts. Labi. [Aplausi] DAVID J. Malan: OK. Tātad jūs faktiski dara to briesmīgi, jo tu esi dara to ļoti labi. Kas atstāj mūs nespēj veikt konkrētus punktus. Tātad, pieņemsim mēģināt roll atpakaļ šeit. Jennifer: OK. DAVID J. Malan: Ļoti labi darīts, tomēr. Tātad jums sākās sākumā, redzējāt, ka tas bija 4, tad jūs pārvietots uz beigām. Bet pieņemsim, ka jums nav get laimīgs tur, un pieņemsim, 50 bija kaut kur citur. Kādas ir jūsu Trešais solis ir bijis? Jennifer: Iet atpakaļ uz sākumu. DAVID J. Malan: Iet atpakaļ līdz sākumā. Labi, lai jūs esat pieskāries šīs durvis, kas bija 8. Labi. Tātad, tas nav 50. Kur jūs esat izskatījās tālāk? Jennifer: Ja man nav zināt, tie sakārtoti. DAVID J. Malan: Pareizi. Nu, ja jūs zināt, tie sakārtoti - Jennifer: Ak, zinu, jā. DAVID J. Malan - bet jums nav zināt, kur 50 bija vēl? Jennifer: Just glabāt turpinās. DAVID J. Malan: Nu labi. Labi. Uzglabāt iet. Labi, ka es varu strādāt. Jennifer: OK. DAVID J. Malan: Tagad, ja jūs tikai dodas, lai saglabātu turpinās, kas ir jūsu algoritms pārgājuši atbalstīja into. Jennifer: lineāra -. DAVID J. Malan: Tā ir sava veida lineāra. Bet ļaujiet man piedāvāt, lai man likt uz vietas. Ļaujiet man atsvaidzināt lapā. pats numurs, pašu vienošanos, pašas durvis. Bet domāju, ka atpakaļ uz šo pirmo dienu klasē, kad mēs saplēsa tālruņa grāmatu puse, veida, un to, kas bija mūsu stratēģija tur? Jennifer: Sāciet vidū. DAVID J. Malan: OK. Tātad, sākt pa vidu. Tāpēc iesim uz priekšu un simulēt to. Sākt pa vidu ar atklājot, ka durvis. Tātad skaitlis 16. Tātad, kas būtu spēcīgs puisis ir izdarīts, kurš saplēsa telefona grāmatu pusē, nokļūt uz nākamo guess? Jennifer: Go šajā pusē. DAVID J. Malan: Un kāpēc uz labo pusi? Jennifer: Ja tie bija sava veida mazākā uz lielāko, tad 50 būtu šajā sakarā. DAVID J. Malan: Labi. Pilnīgi pamatoti. Tātad, piemēram, tālruņa grāmatu, jūs doties uz pa labi, nevis pa kreisi, bet šeit ir galvenais takeaway. Jūs tagad varat mest prom, vai noplēst, puse no šīs problēmas, atstājot jūs ne ar 7 durvīm, bet tiešām ar 3 tikai. Kas ir aptuveni puse no lielums problēmu. Labi. Tātad tagad, ko jūs būtu izdarīts pēc tam, kad iet labi? Jennifer: Tātad 16 joprojām ir diezgan mazs, salīdzinot ar 50, tāpēc varbūt es mēģināšu, piemēram, šo vienu. DAVID J. Malan: Nu labi. 42. Labi, tāpēc tagad to, kas ir jūsu instinkts stāsta jums? Jennifer: Es varu mest prom šo un tad tikai - DAVID J. Malan: OK. Labi, jūs varat mest prom kreiso pusi tur. Jennifer: - izvēlēties šo vienu. DAVID J. Malan: Un labi. Jennifer: Jā. DAVID J. Malan: Tātad, pat ja tas ir grūti redzēt, varbūt, ja tur ir tikai 7 durvis, domā par to, kas tagad, konsekvence algoritms, jūs vienkārši piemērot. Iepriekšējā gadījumā, jūs paveiksies, kas bija lieliski. Bet jūs izmantojat heiristisko, Es teiktu. Tu izmanto veida savu instinktu, un zinot to sakārtoti, ja tas ir diezgan mazs sākumā, protams, mēs esam got iet vairāk uz labo pusi. Bet zināmā mērā, jums laimīgs, jo varbūt tas bija skaitlis 100, un varbūt 50 bija pa vidu. Varbūt 50 bija pat vairāk nekā šeit. Bet ko jūs nedaudz savādāk šoreiz bija, jūs pats atkal un atkal. Un es teiktu, ka tas, ko jūs tikko tomēr, lai gan ietekmē tālruni grāmata, piemēram, ir kaut kas daudz vairāk algoritmiskās, un daudz mazāk īpašu cased. Daudz mazāk instinktīvs. Tātad, kas galu galā, kā būtu Jūs raksturotu efektivitātes Pirmais algoritms, kur jums gāja kreisās uz labo pusi, salīdzinot Otrais algoritms šeit? Jennifer: Tas viens ir, piemēram, varbūt uz pusi samazināt laiku, vai pat vairāk, jā. DAVID J. Malan: Labi, varbūt pat vairāk. Let 's push nedaudz grūtāk par to. Kas īsti, ja mēs turpināsim šo loģika, mēs noteikti uz pusi darba laiku, ar šo otro algoritmu metot prom pusi numurus, bet to, ko mēs izdarījām par nākamo atkārtojuma, kad Jennifer atklāja otrais numurs? Mēs pusi skaitu durvis atkal. Un tad ko mēs izdarījām pēc tam, ja tur bija vairāk durvis, lai spēlēt ar? Mēs vēlētos pusi samazināt tos, un atkal, un atkal, un atkal. Un tas bija tāpat kā jums, puiši visu stāv augšā pirmajā nedēļā klasē, puse no jums sēžot, puse no jums sēžot, pusi no jums sēžot, kamēr viens vientuļš dvēsele stāvēja. Un mēs teicām, ka darbības laiks ka, pakāpienu skaits, kas bija bija uz rīkojumu, ko? SPEAKER 1: [dzirdams] DAVID J. Malan: Tātad log bāze 2 no n, vai tikai vēl vienkāršāk, log n. Lai kaut logaritmiska. Un grafikā nav taisna līnija ka tikko ieguva arvien sliktāk un sliktāk, tas bija tas interesanti līkne, kas nav saņemt tik slikti laika gaitā. Tātad, pieņemsim turēt uz šo ideju. Let 's paldies Jennifer. Paldies tik daudz, lai nāk uz augšu. Un, viens sek. Nav galda lampas šodien, bet mēs Vai ir CS50 stresa bumbas. Jennifer: Yay. DAVID J. Malan: Nu labi, šeit. Paldies, uzņemoties stress šeit. Labi. Tātad, pieņemsim redzēt, ja mēs varam ne tagad formalizēt šo mazliet vairāk. Tātad vēlreiz, ko mēs tikko izdarījām, bija būtībā tas pats, kā mēs to darījām šajā pirmajā nedēļā. Bet nevis beigās tikai ar lineāru algoritms, ko mēs attēlota agrāk kā šīs taisnu līniju, saskaņā ar kuru, ja mēs ieliekam vēl vienu durvis ekrāns, tad Jennifer būtu nācās meklēt, iespējams, Aiz vēl vienu durvīm. Ja mēs uzdodam vēl divas durvis, viņa varētu būt meklēt aiz vēl divas durvis. Un tā, tur bija šī lineārā attiecības starp lielumu problēma, teiksim, x-ass, un laika daudzums, kas nepieciešams, lai atrisināt uz y. Bet bilde man bija atsaucoties uz agrāk bija šī zaļo līniju. Zaļš apzināti, jo tas vienkārši jutās labāk. Teorētiski, algoritms, kad mēs to paveicām ar telefona grāmatu, kad mēs to paveicām ar jums puiši skaitīšanas viens otru, un Otrajā gadījumā, kad Jennifer vienkārši to darīja šeit, tas bija sava veida fundamentāli labāk. Jo tas bija ne tikai divreiz ātrāk. Tas nebija pat četras reizes ātrāk. Tas bija pilnīgi atkarīgs no kāda izmērs no ieejas ir, kā uz cik daudz pasākumiem, ko tā galu galā bija. Un tā tas vienkārši ideja, ka mēs visi ņēma par pašsaprotamu ar tālruņu grāmatu, var līdzīgi piemērot lai kaut kas līdzīgs šim. Un tas varētu būt vairāk pagadās pazīstams kā, kā jūs varētu iedomāties, skaldi un valdi. Ne atšķirībā no to, ko mēs darījām, protams, ar tālruņu grāmatu. Bet pseudocode, atsaukšana, bija šī. Tāpēc mēs nevarēsim darīt atkal, bet atcerēties ka pirmo nedēļu, mums visiem piecēlās un tad puse no jums apsēdās, puse tu apsēdies, puse no jums apsēdās. Šis algoritms tika realizēts mazliet par krāpšanos veidā, ar to, ka, tā bija ne tikai viena no manis skaitīšana, būtiski, efektīvāk. Tādā gadījumā, man bija piesaistot sekundārā resurss. Kārtot, vairāku CPU, vairākas smadzenes, vairākas smart cilvēki istaba bija palīdzēt man iegūt no kaut lineārs kaut logaritmiska, no kaut kā sarkanas līdz kaut zaļu. Bet šajā gadījumā, Jennifer vien var būtiski uzlabo sniegums savu pirmo algoritmu, ko, atkal, tikai domāju nedaudz grūtāk. Un tagad, kad runa ir laiks, lai īstenotu šīs lietas, norādītas kāda rindiņas kodu, jūs varat rakstīt tādas ka jūs varat atkārtot tos atkal, un atkal, un atkal, sava veida kas looping veidā. Tāpēc, ka jūs neesat nāksies luksusa, piemēram, Jennifer darīja sākumā, lai vienkārši ir visai ķekars IF un teikt, hmm, ja šis pirmais skaitlis ir 4, ļaujiet man lēkt visu ceļu līdz beigām. Ooh, ja šis skaits ir pārāk liels, ļaujiet man pārvietoties patvaļīgi atpakaļ līdz otrā elementa. Jūs atradīsiet, ka tas būs daudz grūtāk noformēt to, ko mēs cilvēki pieņemt par pašsaprotamu, jo ļoti saprātīgs heiristikas, bet dators ir tikai gatavojas darīt to, kas jums pateiks to darīt. Tagad tas ir ļoti interesanti ietekme. Šajā grafikā ir sava veida domāts, lai sakārtotu ar apbērt vizuāli, bet paziņojums, kurā ir taisna līnija šajā grafikā? Kur ir lineāra diagramma ka mēs saucam n? Nu, tas ir sava veida virzienā no apakšas ar šo attēlu, vai ne? Tātad, visi mēs esam darījuši, ir, mēs esam sava veida attālināt līdz x-ass un y-ass, lai mēģinātu iegūt sajūtu par to, kas cita veida līknes izskatās. Un specifiku matemātisko izteiksmes šodien nav svarīgi tik daudz, bet paziņo, ka tur ir daudz algoritmi, kas ir daudz sliktāk, nekā kaut kas ir lineāra. Patiešām, kubā n izskatās diezgan slikti. 2 līdz n izskatās diezgan slikti. n kvadrātā izskatās diezgan slikti. Un mēs redzēsim, ko daži no tiem, varētu būt patiesībā šodien. Un log n nejūtas tik slikti, bet labāk nekā n ir log bāze 2 no n. Bet jūs zināt, tas būtu bijis vēl vairāk pārsteidzoša, ja Jennifer, vai ja mēs, ka pirmajā nedēļā, bija jānāk klajā ar kaut kas ir log log n. Tātad, citiem vārdiem sakot, tas viss virkne iespējamo risinājumu problēmas, bet pat šeit, paziņojums to, kas notiks. Kad es zoom out, kura no šīm līknēm gatavojas izrādīties absolūti sliktākais no uz ekrāna tiem tagad? Tātad n kubā izskatas slikti brīdī. Bet, ja mēs tālināt un redzēt vairāk x un y asi, kas dodas uz dominē galu galā? Tātad tas faktiski izrādās, ka 2 līdz n, un jūs varat skaitlis šo out, vienkārši tapām dažās arvien lielāku numuru, un jūs redzēsiet, ka 2 n, protams, kļūst lielāka daudz ātrāk. Ja mēs patiešām tālināt, ar 2, lai n algoritms absolūti sūkā. Es domāju tas ir gatavojas veikt pavisam nedaudz laika, lai datoru, lai kannu cauri. Bet jūs redzēsiet laika gaitā, jo īpaši ar nākotnes problēmu kopas, un pat galīgie projekti ir jūsu dati kas izpaužas liels, labi? Pat pirmajā versijas Facebook, cik draugu, un Reģistrēto lietotāju skaits got liels, Jūs varat kārtot par telefonu tas ir, un ieviest kaut ko ar lineāro meklēšanu, vai arī ļoti vienkāršs šķirošana algoritmu, kā mēs redzam šodien. Jums ir jāsāk domāt grūtāk un grūtāk par šīm problēmām. Un veida problēmām vietās, piemēram, Facebook un Google un Microsoft, un citi strādā pie tieši šiem kārtot lielo datu veida jautājumiem arvien vairāk šajās dienās. Labi. Tātad Dženiferas panākumiem, ka otrais algoritms, atklāti sakot, viņa bija pārsteidzoši arī pirmo reizi, bet, pieņemsim rakstīt to kā veiksmi, lai mēs var padarīt šo jautājumu. Otrajā gadījumā, viņa parādi algoritms, kas atkārtojas atkal un atkal, bet viņa ņēma par pašsaprotamu drošs pieņēmums, ka mēs atļāvām viņai, bet viņa izmanto daži dati otrā reize, kad viņai nebija pirmo reizi. Kas bija tas, ko? Šis saraksts tika sakārtots. Tātad, tiklīdz saraksts tika sakārtoti, mēs apgalvo, ka Jennifer varēja izdarīt fundamentāli labāk. 7 durvis, jā, nav tik interesanti, bet pieņemsim, ka to mēs esam 7 miljoni durvis. Log n ir noteikti gatavojas , lai veiktu daudz, daudz ātrāk ilgtermiņā. Bet viņa bija jābūt durvis sakārtoti viņai. Tagad, man bija atļaušos darām iepriekš uz datora ekrāna šeit, bet pieņemsim, ka Jennifer nācās darīt sev? Pieņemsim, ka durvis attiecīgie pārstāvēti datus datu bāzē, vai draugi reģistrējušies Facebook, vai visi mājas lapas internetā, kas dažādās tīmekļa vietnēs varētu būt vajadzīga indeksēt vai meklēt vairāk. Pieņemsim, ka jūs tikko bija izejas dati noteikt un tas tika atstāts, lai jūs, vai Jennifer to darīt šķirošanu? Tas drīzāk prasa, lai mēs atbildētu jautājums, labi, cik daudz laika būtu jāņem Jennifer, vai pat mani, kārtot šos numurus iepriekš, lai ka viņa varētu gūt labumu no tā? Labi? Jo Ietekme, protams, ir ja tas notiek man diezgan, bet, lai sakārtotu numuri, kas heck rūpējas, ka jums varat atrast vairākas, piemēram, 50 tik ātri, kā arī Dženiferas gadījumā, ja mēs vairāk nekā nomākti apjomu kopējā laika tas notika pēc šķirošanas lietas iepriekš? Tātad, pieņemsim redzēt, ja mēs nevaram krāsu attēlu šeit. Man ir visai ķekars vairāk uzsvērt bumbiņas, ja tas palīdz lauzt ledu šeit. Un, ja jūs neiebilstat, mēs nepieciešams septiņi brīvprātīgie - gada, OK. Wow. Tāpēc mums nav jātērē uz galda lampas, šķiet. Labi. Tā kā par tevi divi priekšā. Kā par jums divi puiši, kas aizmugurē. Tāpēc, ka ir četri. Kā par jums priekšā pieci, seši un septiņi. Labi tur. Jūsu drauga norādot tevi, lai jūs iegūtu balvu. Labi. Nāciet uz augšu. Un kāpēc nav mēs esam jums puiši nāk vairāk nekā šeit. Es esmu gatavojas sniegt jums katru numuru. Un iet uz priekšu, un sakārtot sevi vienāds ar to, kas ir attēlots uz ekrāna. [Interposing Voices] DAVID J. Malan: OOP, sorry. Bug. Labi. Nu, šeit mēs iet. Numuru pieci. Seši numurs. Viens, divi, trīs, četru, piecu, sešu, septiņu. Ak, tas ir neērts. SPEAKER 2: Es ņemšu tikai iegūt -. DAVID J. Malan: Labi darījumu. Labi. Paldies par dalību. [Aplausi] Labi. Labi. Tātad mums ir četri, divi, seši, viens, trīs, septiņi, pieci. Perfect tāpēc mums ir septiņi brīvprātīgie šeit, kas ir vienāds ar platumu, lai masīvs, ka mēs esam spēlē ar agrāk. Un es izvēlējos septiņus iemeslu dēļ ka būs tikai ērts mazliet. Un es esmu gatavojas ierosināt ka, pirmkārt, mēs šķirot šos septiņus brīvprātīgos. Ja vēlaties, pirmkārt, teikt hello, lai gan. Tā kā šī būs neērts vairākas minūtes. Ieviest sevi. GRACE: Sveiki, es esmu Grace. Es esmu otrā kursa students, kas Leverett namā. BRANSON: Hi. Es esmu Branson. Es esmu pirmkursnieks metināt. Gabe: Hi. Es esmu Gabe. Es esmu junioru Cabot. Neil: Es esmu Neil. Es esmu pirmkursnieks Matthews. Jason: Es esmu Jason. Es esmu pirmkursnieks Greenough. MIKE: Es esmu Mike. Es esmu pirmkursnieks Grays. JESS: Es esmu Jess. Es esmu otrā kursa students, kas Leverett. DAVID J. Malan: Excellent. Labi. Nu, paldies visiem mūsu brīvprātīgie šeit līdz šim. Un pie rokas uzdevums šobrīd notiek jābūt, lai sakārtotu šos puiši, bet pēc tam mēs esam nāksies domāt nedaudz grūti par to, cik efektīvi mēs patiesībā sakārtoti tos. Tātad, pieņemsim vispirms izmēģināt šo. Jūs guys var redzēt viens otra numuru vienkārši ievietojot ap stūri. Iet uz priekšu un veikt dažas sekundes, un kārtot paši no mazākais pa kreisi, lai lielākā labajā pusē. Iet. Labi. Labs. Tas bija tiešām darn ātri. Tagad kāds šeit, kas bija algoritms ka šie puiši piemērots? SPEAKER 1: vismaz uz lielāko. DAVID J. Malan: OK. Vismaz uz lielāko tiešām ir sava veida mērķis, bet es neesmu pārliecināts, ka ir tiešām algoritms. Vismaz uz lielāko nestāsta man soli pa solim, ko darīt. Yeah? SPEAKER 1: [dzirdams] DAVID J. Malan: OK. Tātad, ja jūs redzat persona mazāks nekā jūsu numurs, tad pāriet uz tiesības uz tiem. Tātad, kas ir tagad kļūst daudz izteiksmīgāku, vairāk kā algoritms, jo jūs var teikt, ja tā, tad tā. Tāpēc mums ir sava veida nosacīta konstrukcija. Un šie puiši, šķiet, darīt, ka daži reizes, jo daži no jums pārcēlās mazliet no attāluma. Tātad bija iespējams, sava veida looping notiek viņu prātos. Bet pieņemsim mēģināt formalizēt to. Ja jūs puiši varētu nomainīt atpakaļ ar šo vienošanos. Redzēsim, vai mēs nevaram noformēt šo bit, un pēc tam uzdot jautājumu, vienkārši cik efektīvi tas ir? Protams, tad, kad mēs to darām lēnāk, tas notiek, lai justos tik laba algoritms, bet pieņemsim redzēt, ja mēs varam nodot mūsu pirkstiem uz konkrētiem soļiem. Tātad jūs abi puiši ir četri un divi. Vai jūs pareizi vai nepareizi pasūtīt? Acīmredzami nepareizs. Tāpēc mēs nomainīju. Tagad es esmu gatavojas pārcelties malā šeit un teikt, 05:56. Vai jūs pareizi vai nepareizi? Gabe: Pareizi. DAVID J. Malan: Pareizi. Seši un viens? Nē. Swap. Tātad tas ir divas mijmaiņas. Seši un trīs? Nē. Swap. Seši un septiņi? Izskatās labi. Septiņi un pieci? JESS: [dzirdams] DAVID J. Malan: Labi, swap. Un sakārtoti. Labi. Tātad acīmredzot ne, labi? Tātad, tur bija vairāk notiek. Bet, protams, šie puiši, pat vienkārši instinktīvi. tur pārvietojas. Tās nav tikai pārtraukt, kad viņi labota viena problēma. Tātad. Patiešām, es esmu nāksies darīt to pašu. Es esmu nāksies kārtot no attīt atpakaļ līdz sākumā šīs problēmas, vai sākumā šī masīva cilvēki, sāksim aicinot viņus. Un tagad kāds būtu mans algoritms uz otro pass būt? SPEAKER 1: Same lieta. DAVID J. Malan: Same lieta. Un tas, es esmu sāk patīk, vai ne? Tiklīdz jūs varat atrast sev dara pats atkal un atkal, tas ir kļūst vairāk, piemēram, algoritmu, un mazāk cilvēka instinkts. Tāpēc tagad, šeit mēs aiziet vēlreiz. Divi un četri? Nē. Četri un viens? Ah, tur tiešām bija daži darba vēl jāpaveic. Par un trīs? Labs. Četras līdz sešas? Seši un pieci? Seši un septiņi? Labi, tagad, darīts. Labi, nē. Man ir jāiet atpakaļ. Tāpēc tagad, atkal, mēs darām to nedaudz vairāk apzināti. Un tagad, tur ir tikai viena smadzeņu izpildot šo algoritmu. Viens CPU, ja Jums gribas. Un, atklāti sakot, tas ir vienīgais resurss mēs ejam, lai būtu pieejami. Un, kad mēs iet atpakaļ uz klaviatūras un ir kaut kas līdzīgs C pie mūsu iznīcināšana, mēs esam tikai rakstot programmu ka var darīt viena lieta laikā. Tā kā šie puiši pirms brīža, mēs parādi to kolektīvās intelektuālo potenciālu kā jūs puiši darīja nedēļu nulles. Tā ļauj saglabāt to izdarīt. Divi un viens. Divi un trīs. Trīs un četras. Četri un pieci. Piecus un sešus. Seši un septiņi. Gatavs? Tāpēc es esmu, bet ļaujiet man spēlēt Velna advokāts. Vai man, veida datora, kurš tikko sniedza piespēli šo masīvu cilvēki, zina, ka es esmu darīts? SPEAKER 1: Nē. DAVID J. Malan: Tad kāpēc? Kas man jādara, lai secināt, izlēmīgi, ka es esmu darīts? Iespējams, vēl viens pass. Labi? Jo viss, ko es zinu no ka iepriekšējais caurlaide ir, ka man jālabo kļūda. Un tas nozīmē, varbūt tur ir vēl viena kļūda ka man ir nepieciešams labot. Tāpēc es varu tikai būt pārliecināts, ka līdz pārtīšana, un pēc tam pārbaudot, 1-2, divi un trīs, trīs un četri, četri un pieci, pieci un seši, seši un septiņi. Labi, tagad man nebija nekādu darbu. Es, protams, atceros, ka man nebija neviena strādāt ar kaut ko, piemēram, mainīgo, piemēram, int. Call to mijmaiņas līgumus, un, ja mijmaiņas ir 0, kad I iegūt šeit, un tas sākās ar 0, tad Es būtu vienkārši muļķīgi, lai saglabātu turpinās uz priekšu un atpakaļ, pārbaudot atkal, un atkal, un atkal, vai ne? Tāpēc, ka jums iestrēdzis dažos veida bezgalīga cilpa. Tātad, tiklīdz tur ir 0 mijmaiņas darījumi, mēs varam apgalvot, ka šis algoritms ir patiešām pilnīgs. Tagad, pieņemsim likt vārdu par to. Algoritms, ka es ierosinu mēs tikko īstenota, ir kaut kas ko sauc burbulis kārtot, kas pazīstams kā tāds nozīmē, ka skaitļi, kas ir lielāki veida burbulis savu ceļu uz augšu uz augšu, vai uz augšu līdz beigām masīva numuriem. Bet cik efektīva bija šis algoritms? Cik soļus gan es fiziski ir veikt, piemēram, lai sakārtotu šos septiņi cilvēki? Četriem līdz pieciem? Labi, pārāk daudz galu galā būs atbilde. Bet pat tad, konkrētu skaitu nav tik interesanti. Pieņemsim vispārināt to kā n. Tātad, ja man bija n cilvēkus šeit, un viņi bija sava veida, nejaušā secībā pēc sākumā, jo šajā sākotnējā secībā. Nu, cik soļus bija man uzņemties pirmā loka? Tas bija viens, divi, trīs, četru, piecu, seši, un viņi ir septiņi cilvēki, tāpēc kas ir septiņi, seši -, tā ka ir n mīnus viens soļi pirmo reizi. Tagad, cik soļus bija man lai tad, kad es jāpārtin? Nu, mēs patiešām varētu dubultot, ka, ja mēs patiešām vēlējāmies, bet tagad, es esmu tikai gatavojas teikt, labi, vēl viens n mīnus 1. Tātad n mīnus 1 ir gatavojas iegūt kaitinošas, lai sekotu, tāpēc pieņemsim tikai noapaļot uz augšu mazliet. Tātad 2n soļi. Tātad 14 soļi, sniegt vai pieņemt. Cik reizes es solis nākamreiz? Nu, tas ir 3n. tiešām. Un tagad, sliktākajā gadījumā, attiecībā Piemēram, cik reizes man ir gājusi uz priekšu un atpakaļ, uz priekšu un atpakaļ, izpildot šo algoritmu, pārnešana cilvēki uz katra brauciena, aptuveni? Tas ir patiešām n rūtiņām, vai ne? Jo sliktākajā gadījumā, jūs varat veida gada domā par to intuitīvi, kaut gan tas var aizņemt nedaudz mazliet laika, lai izlietne collas Sliktākajā gadījumā, kādi būtu šie septiņi cilvēki izskatījās, it vienošanās noteikumi par to skaitu? Pilnīgi atpakaļ, labi? Un tikai, lai modelētu, ka, kāda bija jūsu vārds atkal? MIKE: Mike. DAVID J. Malan: Mike? Labi, Mike, jūs varat vienkārši pievienoties man vairāk šeit tikai par vienu sekundi? Patiesībā, nē. Atvainojiet Mike, pieņemsim atpakaļ. Kāds ir Jūsu vārds atkal? Neil: Neil. DAVID J. Malan: Neil. Labi, Neil, jūs nākt ar man, ja jums nav prātā. Tāpēc es esmu gatavojas ierosināt, tikai vienkāršība, ka Neil tagad viņa vissliktākais iespējamais gadījums. Bet atceros, kā es īstenoti mans algoritms. Es esmu salīdzinot, salīdzinot, salīdzinot, Salīdzinot, salīdzinot, oh. Tagad šie puiši ir out kārtības, tāpēc es noteikt. Tātad jūs guys swap. Bet uzskatu, tagad, cik daudz tālāk nav Neil jāiet? Tas ir aptuveni n. Jūs zināt, tas nav reāli n. Tas ir tāpat, n mīnus 1, bet es saņemu kaitina sekotu maz numuru, tāpēc pieņemsim tikai sauc to n. Tātad, ja Neil kustas viens solis maksimāli katras laiku, un, lai pārvietotu Neil vienu soli, Man ir, lai padarītu šo patiesi nogurdinošs caurlaide uz priekšu un atpakaļ, tas ir aptuveni darot, n posmi, no n reizes kopā, tāpēc, ka tas notiek, lai mani ka daudzi soļi, lai saņemtu Neil visiem veids, kur viņš pieder. Nemaz nerunājot visi pārējie, ja jūs guys visi bija nepareizi lika, kā arī. Tāpēc sauksim burbulis veida n brusas. Darbības laiks šo algoritmu, izpilde šī algoritma, efektivitāte šo algoritmu, mēs vienkārši aprakstīt vairāk , kā parasti n rūtiņām. Kas ir jauki, jo es varētu darīt pats piemērs ar astoņiem cilvēkiem, deviņas cilvēki, miljons cilvēku, un ka Atbilde nav gatavojas mainīt. Tātad, ja jūs guys nebūtu prātā, pieņemsim reset jums, kur jums sākusies. Un pamēģināsim divas citas pieejas un redzēt, ja mēs nevaram darīt fundamentāli labāk nekā šis. Tātad šajā laikā, es esmu gatavojas ierosināt veida dažādu algoritmu. Tas bija ļoti gudrs no mums pēdējo reizi, un jūs puiši bija tiesības uz tiesības instinkti tikko veida pārnešana pāru. Bet, ja es tiešām gribēju, lai pieeja šo vienkārši, un mans mērķis ir, lai pārvietotos visas maz numuriem šādā veidā, un push visi lielie numuriem, veidā, kāpēc ne es tikai darīt, ka visvairāk naivs veidā iespējams, un redzēt, ja es var darīt labāk, nekā to, kas bija diezgan sarežģītu algoritmu? Tātad, pieņemsim redzēt. Četri ir diezgan maz, tāpēc es esmu gatavojas atstāt jūs tur brīdi. Ooh, numur divi ir pat labāk. Tātad, jūs varat vienkārši soli uz priekšu uz brīdi? Tas pašlaik ir mans mazākais numurētas kandidāts, un es esmu gatavojas atcerēties ka ar, piemēram, mainīgo. Bet es esmu gatavojas, lai saglabātu pārbaudot. Vai ir kāds, kuru skaits ir mazāks? Seši, nē. Ak, tur ir Neil vēlreiz. Tāpēc es esmu gatavojas push jums atpakaļ veida konceptuāli. Neil nāks klajā. Un tagad, mainīgo, ka es esmu, izmantojot to sekot līdzi, kas ir mazākais numurs tiek atjaunināts, lai apturētu Neil atrašanās vietu. Nu, paskatīsimies. Trīs, septiņi, pieci. Labi, es zinu, Neil bija vismazākā. Kas ir vienkāršākais lieta man tagad darīt? Es netaisos tērēt savu laiku, tikai burbuļošana Neil vienas vietas pa kreisi. Kāpēc es tikai izvirzīti Neil kur viņš pieder, kas ir, protams, kur? Visu ceļu sākumā. Tātad Neil, nāc ar mani. Un kāda bija jūsu vārds atkal? GRACE: Grace. DAVID J. Malan: Grace. Labi. Tātad Grace, diemžēl, tu esi veida ceļā. Tātad, kā mēs atrisināt šo problēmu? Labi? Ja tas ir masīvs, tur ir tikai septiņas vietas. Atgādināt, ka, ar Rob, mēs runājām deklarē vecumu, un mums bija tikai ierobežots skaits vecumu? Pati ideja šeit. Mums ir tikai ierobežots skaits ints. Grace ir sava veida mūsu veidā, tad kā mēs varam noteikt? Vienkāršākais veids ir, piemēram, Žēlastība, sorry. Jūs esat nāksies iet pa tur, lai mēs varētu padarīt telpu. Tagad, ja jūs domājat par to, varbūt mēs tikko veikts problēma sliktāka. Un varbūt mēs darījām, jo ​​kas notiks, ja Grace bija īstajā vietā? Bet mēs zinām, viņa nav, jo citādi, viņai būtu bijis stāvot uz priekšu, nevis Neil šajā laikā, vai ne? Mēs jau paņemts viņas numuru out. Labi. Tāpēc tagad, Neil ir pareizajā vietā, un Es varu darīt nelielu optimizāciju. Attiecībā uz nākamo minūti, es esmu gatavojas ignorēt Neil visi kopā, tā, lai atkritumu savu laiku, vai nejauši swap viņu nepareizā vietā. Tāpēc tagad, kā es varu atrast nākamo elements, kas ir mazākais? Divi. Tas ir diezgan labs numurs, ja Jūs vēlaties, lai soli uz priekšu un Es atceros tevi. Seši, nav labi. Četri, trīs, septiņi, pieci, nav labi. Tātad, ļaujiet man pāriet jums Jūsu īstā vieta. Un mēs vienkārši palaimējies šoreiz. Tagad es esmu gatavojas ignorēt šos divi puiši, bet tagad vēl viena iet caur šo. Seši, ka diezgan neliels skaits. Nāc uz priekšu. Ak, piedodiet. Grace numurs ir labāk, tā solis uz priekšu. Četri. Atvainojiet, Grace. Iet atpakaļ. Numurs trīs ir labāk. Septiņi. Pieci. Un tagad kāds ir tavs vārds atkal? Jason: Jason. DAVID J. Malan: Jason. Tātad Jason tagad mazākais elements, es esmu izvēlēts. Gadījumos, kad viņš gatavojas doties? Tātad, kur seši ir. Un jūsu vārds atkal? Gabe: Gabe. DAVID J. Malan: Gabe. Gabe ir ceļā. Kas ir vieglākais lieta darīt? Swap šie divi puiši un turpināt. Tātad tagad pieņemsim redzēt. Kurš ir mazākais? Četri. Ļaujiet man tikai veida pievilt. Pieci būs vismazākā. Es atrast nākamo, ja jūs vēlaties, lai soli priekšu, kas man ir jādara ar šie puiši, ar Gabe? Swap vēlreiz. Tāpēc tagad, vēl nedaudz bojātas. Es konstatēts Gabe būt mazākais, tā Es pop viņu ārā, pārvietot jūs puiši vairāk. Un darīts. Tātad atbilde ir tas pats. Gala rezultāts ir tāds pats. Kurš no šiem diviem algoritmu ir labāks? Otrs, es dzirdēju. Kāpēc? SPEAKER 3: Tas ir n soļi [nedzirdama]. DAVID J. Malan: Tas ir n soļi pie visvairāk. Interesanti. Tātad, tas ir gan? Tātad, kā es varu atrast mazākais elements? Cik soļus did I ir jāņem atrast mazāko elementu? Man bija skatīties visu ceļu gada beigās, vai ne? Jo šajā sliktākajā gadījumā, kas ja Neil bija vairāk nekā šeit? Tik vienkārši atrast mazāko elementu ņem mani n soļi, vai n mīnus 1. Bet, OK. Tātad noteikt Neil. Atcerieties, ka, minūti, vai arī tā atpakaļ. Bet kā es varu atrast nākamo mazākais elements? Tas ir n mīnus 1, vai n mīnus 2 tiešām, no to darbību skaitu. Tātad OK. Tāpēc man nebija n mīnus 2. Labi. Tāpēc, ka jūtas mazliet labāk. Labi. Cik soļus nākamreiz lai atrastu numuru trīs? Tā n mīnus 4. Tātad tas samazinās, viens mazāk soli uz katra atkārtojuma. Tātad tas justies labāk, vai ne? Ja pēdējā laikā, tas ir aptuveni n reizes, n, šoreiz tas ir n mīnus 1, plus n mīnus 2, plus n mīnus 3, plus n mīnus 4, dot, dot, dot. Bet, ja jūs atceraties no jūsu vidusskolā mācību grāmatas, maz apkrāptu loksnes pie muguras, kas ir formulas, ja Saskaitot šīs sērijas numuru, kāds ir kopējais skaits soļiem būs, ka es šeit? Šis ir viens no tiem, piemēram, n mīnus 1 reizes n, dalot ar 2. Tātad, ļaujiet man redzēt, ja es varētu pull šo up tikai brīdi. Un atkal, es esmu veida noapaļošanas dažu numurus tikai, lai saglabātu mūsu dzīvi vienkāršu, bet, cik es atceros, tas ir kaut kas līdzīgs, ja Man n mīnus 1 lietas, tad n mīnus 2, tad n mīnus 3, tas ir aptuveni kaut kas līdzīgs šim vairāk nekā 2, un, ja es reizināt šo out, tas ir faktiski n kvadrātu. Tas nav slikta pārāk labi. n mīnus n vairāk nekā 2. Bet šeit ir lieta. Datorzinātnēs, kad problēmas sāk iegūt interesantu, ir tad, kad n izpaužas patiešām liels. Un, ja n kļūst patiešām liels, kas no šīs vērtības gatavojas dominēt visu par citiem? Tas ir sava veida n brusas, vai ne? Jā, dalot ar 2, ir diezgan laba. Bet, ja jūs runājat par miljardu gabalu datu vai triljoniem gabalu datiem, OK, tāpēc tu esi divreiz ātrāk. Bet kas tiešām rūpējas, ja šo lielo skaitu, ja šis faktors ir tas, kas izpaužas lielāka un lielāka. Un, protams, tas padara vairāk atšķirība par šo puisis. Tātad, pat ja jūs guys ir taisnība, otrkārt algoritms, mēs to saucam izvēle kārtot, ir reālajā pasaulē, mazliet ātrāk iespējams, jo es esmu ņemot mazāk un mazāk soļus katru reizi. Tas nav īsti būtiski ātrāk. Jo, ja mēs faktiski spēlēt šo out lielas vērtības no N, beigās diena, lieliem pietiekami n, tas joprojām ir gatavojas justies diezgan lēns. Nu, ļaujiet man izmantot vienu pēdējo reizi iet tajā. Tas ir tas, ko es sauktu atlase kārtošanas. Vai jūs guys reset sevi pēdējo reizi? Un šajā pēdējā gadījumā, es esmu gatavojas ierosināt kaut ko sauc ievietošanas veida. Ievietošanas šķirot ir konceptuāli nedaudz savādāka. Nevis iet uz priekšu un atpakaļ, un izvēloties mazāko elementu, es esmu tikai gatavojas, lai risinātu ar katru no šiem puiši kā es saskaras viņiem, un ievietojiet tos savā pareizajā vietā. Tāpēc es esmu tikai gatavojas sākt ar Grace, un es redzu, ka viņa ir numur četri. Kur numur četri pieder? Man nav sākusies šķirošana neko, tāpēc Grace izpaužas palikt turpat. Un tagad es esmu gatavojas pieprasīt, ja jūs varētu spert soli, lai jūsu tiesības, tas mans sakārtoti sarakstā, tas ir mans nešķiroti atlikušo sarakstu. Tāpēc tagad es esmu gatavojas sākt nākamo, un kāds ir tavs vārds atkal? BRANSON: Branson. DAVID J. Malan: Branson. Tātad Branson ir numur divi. Tāpēc es esmu gatavojas pieņemt jums kas uz brīdi. Un tagad, kad jūs piederat Šajā masīva? Tātad, pa labi no Grace. Tātad vēlreiz, mēs esam sava veida padarīt Grace darīt daudz darba šeit. Kur mēs nodot jums? Tātad, mēs ejam, lai slīdētu jums pa kreisi, un ievietojiet Branson tur. Bet tagad man apgalvot, ka jūs guys ir darīts. Bet paziņojums, es neesmu, izmantojot papildu telpas. Tas joprojām ir 2 elementi Šeit, 5 vairāk nekā šeit. Kopējais masīva izmērs ir 7, tāpēc es esmu nekrāpj, labi? Tāpēc tagad mums ir, ar Gabe šeit, numuru seši, ja jūs piederat? Tev laimīgs atkal. Tātad jums palikt turpat. Just veikt nelielu soli, lai labi tikai, lai būtu skaidrs, ka jūs esat sakārtoti. Un tagad mums ir Neil atkal, skaits viens, kur jūs iet? Un tagad ir, ja mēs sāksim redzēt, ka tas algoritms, lai gan par pirmo skatienu, jūtas diezgan gudri, skatīties kas ir aptuveni notikt. Ja jūs varētu soli uz priekšu. Kur mēs vēlamies, lai Neil? Tātad acīmredzot šeit, tad kā Vai mēs Neil tur? Darīsim to soli pa solim. Gabe, kur jums jāiet? Yep, tā veic vienu lielu soli, vai divu pusi-soļi, lai padarītu viens solis tur. Grace, kur jums iet? Labs. Tātad vēl viens solis. Un, visbeidzot, Branson? Vēl viens solis. Un tagad mēs varam nodot Neil vietā. Tāpēc tagad, turpināt šo loģiku. Pat ja mēs neesam novirzot Neil vairāk un vairāk, un vairāk, lai viņu kur viņš dodas, sliktākajā gadījumā, nākamais skaitlis mēs varētu saskarties varētu ir skaitlis, teiksim, tur bija vairāki nulle, tad mēs ejam, lai novirzīt visus šie puiši. Pieņemsim, ka tur ir vairāki, negatīvs viens, tad mums ir novirzīt visiem šiem puišiem. Tāpēc mēs esam tiešām tikai veida flipping problēma apkārt, piemēram, ka mēs esam pārceļot rēķina no atlases process tāpēc ievietošanas procesā, piemēram, ka jūs puiši tikko bija pārvietot aptuveni n mīnus kaut ko virkne pasākumu. Un, ka vairāki pasākumi ir tikai gatavojas palielināties, jo es izvēlētos citus numurus, ja man ir, lai saglabātu shoving jums guys atpakaļ, un atpakaļ, un atpakaļ. Tik skumji lieta tagad ir visi šie algoritmi ir n rūtiņām. Iesim uz priekšu, un, pateicoties šiem puiši, un vizualizēt šos mazliet savādāk. Ļoti labi darīts. [Aplausi] Labi. Tur jums iet. Paldies par - BRANSON: [dzirdams] saglabāt numurus. DAVID J. Malan: Nē, jūs varat saglabāt numurus, kā arī. Labi. Labi darīts. Labi. Tātad, pieņemsim redzēt, ja mēs nevaram tagad apkopot ātrāk, un vairāk vizuāli, tieši to, kas tikko notika Šeit šādi. Es iešu uz priekšu un uzvilkt Firefox. Mēs saistīt šo demonstrāciju par kursu tīmekļa vietnē. Java ir mazliet kaitinošas, lai saņemtu darbu dažās pārlūkprogrammās šajās dienās. Tātad, ja jūs spēlēt ar šo mājās, saproti, jums var būt nepieciešams izmantot Firefox lai saņemtu to strādāt. Un ko es esmu gatavojas darīt ar to demonstrācija ir šādi. Apakšā, man ir visai ķekars izvēlnes iespējas, tostarp sākuma un stop pogu. Tāpat kā malā, šķiet, bug šajās programmās, kuru jūs nevarat patiešām redzēt sākuma vai beigu pogu, ja jūs turiet Command vai Alt plus un zoom in, kas savādi rāda vairāk pogu. Tik vienkārši FYI, ja jūs spēlēt ar šo mājās. Tagad es esmu gatavojas noklikšķiniet uz Sākt, kas tikko Mirklī, kad norādot kavēšanās, piemēram, 200 milisekundes šeit, vienkārši lai mēs varētu redzēt, kas notiek. Tāpēc es apgalvo, ka tas ir vizualizācija Pirmā algoritma šie puiši darīja, burbulis kārtot, kuru mēs nomainīju cilvēkus pa pāriem. Galvenais ieskatu šajā vizualizācijas ir tas, ka augstums stieņiem apzīmē lielumu skaitu. Tātad garāki josla, lielāks skaits. Īsāks bārs, mazāku skaitu. Un, ja pamanāt, mēs ejam cauri Pirmo atkārtojumu šo algoritmu, pārnešana lielos un mazos numurus, lai neliels skaits ir pirmajā vietā, un liels skaitlis iet uz labo pusi. Un, tiklīdz mēs saņemam beigām masīva Daudzu vairāk skaits nekā septiņiem, mēs esam gatavojas doties atpakaļ uz sākumu. Un paredzēt šo. Par tālu pa kreisi, ka maz puisis notiek apmainīt uz pusi, un šis process atkārtojas. Tagad šis vizualizācija ātri kļūst garlaicīgi, tāpēc ļaujiet man iet uz priekšu un apstāties tas, izmainīt aiztures kaut kas daudz ātrāk, tikai, lai iegūtu tagad justies par tas algoritms. Tātad, pat ja es esmu jāpaātrina to uz augšu, tas ir kā uzlabot manu procesoru, pērkot jaunu datoru. Man nav būtiski mainīja manu algoritms, bet jūs tiešām var redzēt vairāk skaidrāk nekā ar cilvēkiem, ka liela skaits ir burbuļo uz augšu, un mazie skaitļi ir burbuļošana uz leju, lai apakšā. Un tagad šī lieta šeit sakārtoti. Un kā malā, ar kvadrātu, tur ir tikai daži grāmatvedības tur palīdzēs jums saskaitīt, cik daudz salīdzinājumus, vai cik atvasinātie faktiski veikts. Nu, pieņemsim, mēģiniet vienu no citi mēs redzējām. Ļaujiet man noklikšķiniet uz burbulis kārtot šeit, un ļaujiet man izvēlēties, un visa šī mājas lapa ir nedaudz buggy. Let 's pieņemt risku un palaist to no jauna. Tur mēs ejam. Tātad, pieņemsim do atlases veida. Es nezinu, kāpēc izvēlne Šķiet tur. Let 's tālummaiņu, lai noteiktu, ka bug, mainīt līdz 50. Ah, pieņemsim faktiski darīt ka daudz ātrāk. Piecas milisekundes, vai arī tā, un sākt. Tātad šī ir izvēle veida. Tātad vēlreiz, domāju par to, ko mēs darīja ar cilvēkiem šeit. Mēs gājām cauri masīva un izvēlēto mazākais elements atkal, un atkal, un atkal. Tagad es apgalvo, ka vēl bija diezgan slikti. Tas vēl bija n rūtiņām, sniegt vai pieņemt, bet tas bija, reālajā pasaulē, nedaudz ātrāk, jo man tiešām bija, ņemot Nedaudz mazāk soļus katru reizi. Bet mēs esam tikai runājam, ko? Varbūt 40 vai tik bāri šeit? Mēs nerunājam 40 miljonus. Tātad, tas nav pilnīgi skaidrs, man, ka tiešām bija nozīmīgs ieguvums. Ļaujiet man tagad iet atpakaļ un mainīt, lai mūsu trešais algoritmu, kas tika atlasīt ievietošanas kārtošanas. Un tagad tas ir patiešām buggy, jo izvēlne tiešām nevajadzētu būt tur lejā. Tāpēc tagad mēs ritināt atpakaļ uz augšu šeit un sākt šo algoritmu. Bļāviens, sākt un pārtraukt. Tātad šī viena veida ir diezgan modelis uz to, kur mēs esam atkal Ievietojot cilvēkus, vai arī Šajā gadījumā, bāri vērā to piemērotu vietu. Un tas jau ir izdarīts pirms Es pagriezos. Bet tas viens, arī teorētiski, ir vēl n rūtiņām. Tātad, pieņemsim redzēt, ja mēs nevaram apkopot tie ir šādi. Es iešu uz priekšu un tikai, lai dotu mums sava veida kopīgu ceļu, kā runāt par šīm lietām, ļaujiet man iepazīstināt tikai mazliet notācijas šeit. Jūs gatavojaties, lai redzētu kaut ko sauc liels O, jo tas ir burtiski liels O. Un tas ir tā, ka dators zinātnieks vai matemātiķis pat izmanto lai aprakstītu darbības laiku par kādu algoritmu. Cik soļus tas tiešām nepieciešams? Tagad es esmu gatavojas apgrūtināt sevi ar mans rokraksts šeit tikai brīdi. Bet ļaujiet man iet uz priekšu un teikt, ka tas būs liels O nekā šeit. Un ļaujiet man iepazīstināt vienam otru simbols, kapitāla omega. Omega būs pretējs, būtībā, lielo O. tā lielā O nozīmē, sliktākajā gadījumā, cik daudz laika varētu kādu algoritms veikt, noteikumi n, omega gatavojas ir, cik daudz laika tas varētu veikt labākajā gadījumā. Un mēs redzēsim, ko mēs saprotam ar labākajā gadījumā tikai brīdi. Tāpēc sāksim kaut ko vienkāršu. Ļaujiet man sākt ar lineāru meklēšanu. Tāpēc ne šķirošana. Mēs to saucam par lineāru meklēšanu. Un tagad, padara nedaudz tabulu no šīs. Un tagad, ja lineāro meklēšanu, sliktākajā gadījumā, cik soļus ir tas notiek, lai mani atrast skaits patvaļīgas izvēles? Un tur ir n kopējais durvis vai n kopējais skaits. Sliktākajā gadījumā. Cik soļus man nāksies veikt, lai atrastu skaitli 50 masīvā no n durvīm? Un kāpēc? Tāpēc, ka tas varētu būt visu kā vairāk uz beigām. Tik daudz, piemēram, Jennifer radušās, numuru 50 bija visu ceļu pāri, tāpēc sliktākajā gadījumā lineāra meklēšana ir liels O n, mēs teikt. Kas par labākajā gadījumā, ja jums patiesi laimīgs? Tas ir tikai gatavojas veikt vienu soli, vai konstante skaits no soļiem. Tāpēc mēs aprakstīt, ka 1. Tātad tas ir diezgan laba. Tagad, kas notiks, ja mēs kaut ko patīk bināro meklēšanu? Tātad bināro meklēšanu, jo sliktākajā gadījumu, ņēma cik daudz laika? [Interposing Voices] DAVID J. Malan: Tik tiešām, es dzirdēja to pāris vietās. Tātad, tas ir faktiski log n, sniegt vai pieņemt, jo, kā mēs sadalīt sarakstu pusi atkal, un atkal, un atkal, mēs esam spējīgi atrast, galu galā, vērtību, ja tas ir tur, bet tur ir nozvejas. Kas ir pieņēmums, ka mums ir par pašsaprotamu bināro meklēšanu? Tā ir jābūt sakārtoti. Tas nav sakārtots, jūs varat sadalīt lieta uz pusi atkal un atkal, un jūs var iet pa kreisi, un jūs varat iet labi, un jūs varat iet pa kreisi un pa labi, bet jūs esat nav dodas, lai atrastu elementu, ja saraksts nav sakārtots, jo jūs varat palaist garām to. Tāpēc, ka jūsu heiristisko, lai dotos pa kreisi vai pa labi, būs kļūdaina, ja tas ir tiešām nav sakārtoti. Tātad tur ir sava veida slēptās izmaksas lai, izmantojot kaut kas līdzīgs šim. Tagad, iesim uz mūsu šķirošanu algoritmi nav meklē - ak, tiešām iesim šajā tukšu. Bināro meklēšanu labākajā gadījumā? Tas ir arī 1, ja tas vienkārši notiek, ir in pašā vidū masīva, vai vidū tālruņu grāmatu. Tagad pieņemsim do burbulis veida. Tātad vēlreiz, tagad mēs esam ienāk sakārto, nevis meklē. Sliktākajā gadījumā, cik soļus vai mēs prasība burbulis kārtot gatavojas veikt? n rūtiņām. Tāpēc es esmu gatavojas izdarīt to. Ooh, mans rokraksts izskatās vēl sliktāk kad tas ir prognozēts, ka liels. Labi. Tātad, kas ir n rūtiņām. Un labākajā gadījumā uz burbuļa veida, cik soļus tā gatavojas veikt? 1, es dzirdēju. SPEAKER 1: n. DAVID J. Malan: n, es dzirdēju. SPEAKER 1: 2. DAVID J. Malan: 2, es dzirdēju. Vai es dzirdu 3? Labi. Tāpēc es esmu dzirdējis 1, n, 2, bet pieņemsim izvēlēties Apart vismaz pirmais no tiem ieteikumi, 1. Tas nav slikti instinkts, jo tas veida seko rakstu šeit. Bet, ja tas aizņem tikai 1 solis, kā in pasaule es varētu apgalvot, ka saraksts ir sakārtots, jo, ja es esmu tikai atļauts veikt 1 soli, cik elementi es varētu faktiski pārbaudīt, lai pārliecinātos? Nu, tikai 1, kas nozīmē, ka ir n mīnus 1 elementi, kas varētu būt no kārtība, un es esmu tikai gatavojas uz ticību pēc Aplūkojot 1 elements, kas lieta ir sakārtots. Līdz 1 Tas nav pareizi šeit. Tātad minimāli, cik man apskatīt? [Interposing Voices] DAVID J. Malan: n mīnus 1, vai tiešām, n, jo man ir nepieciešams, lai apskatīt katru elements, lai pārliecinātos, ka tas nav bojātas. Bet atkal, mēs sava veida vilnis mūsu rokas pie mazākā skaitā un pieņemu, ka n kļūst liels, viņi neinteresanti anyway. Tātad, tas ir burbulis šķirot. Un tagad, pieņemsim do pēdējiem diviem. Atlase kārtot, un tad mēs do ievietošanas veida. Un tad mums būs trieciens jūsu prāts ar kaut ko daudz labāk nekā visi no tiem. Labi. Kas ir sliktākajā gadījumā darbojas laiks atlases veida? SPEAKER 4: n rūtiņām. DAVID J. Malan: n kvadrātveida, es esmu dzirde. Bet kāpēc n rūtiņām, intuitīvi? SPEAKER 4: Jo mēs vienkārši to darīja. DAVID J. Malan: Tāpēc, ka mēs vienkārši to darīja. Labi. Laba atbilde. Bet intuitīvi, kāpēc ir izvēle kārtot n kvadrātā? Ko mums jādara atkal un atkal? Mums bija, lai saglabātu skenēšana, izmantojot, ir Jūs mazākais, jūs mazākais, jūs mazākais. Un piešķirts, mēs varējām veikt n soļi, tad n mīnus 1, tad n mīnus 2. Bet, ja jūs veida pievienot tos visus uz augšu, vai ņemt to uz ticību, ka es esmu pievienojusi viņiem jau iepriekš, mēs iegūstam aptuveni n kvadrātā mīnus dažiem mazākiem skaitļiem. Tāpēc es esmu gatavojas nosaukt šo n rūtiņām. Bet ar atlases veida, kas vislabāk gadījumā, cik soļus ir tas, gatavojas pieņemt mani? SPEAKER 5: [dzirdams] DAVID J. Malan: Tas diemžēl vēl n kvadrātā, vai ne? Jo, ja es esmu izvēloties mazāko elements, un mums bija septiņi cilvēki šeit, Es tikai zinu, kad es nokļūt ļoti end, ka es esmu atradis mazākais numuru, kur viņš vai viņa var būt. Bet kā es varu atrast nākamo Vismazāk? Man ir jādara citas caurlaide. Tātad labākajā gadījumā, kāds ir ieguldījums atlases veida? Tas ir jau sava saraksta, numur viens, numurs divi, trīs numurs, numurs četri. Bet es esmu datoru. Es varu tikai apskatīt vienu lieta laikā. Es nevaru sava veida spert soli atpakaļ, piemēram, cilvēku un saka: ooh, tas izskatās pareizi. Es varu tikai spriest pareizību, kas atlase kārtot, izvēloties Vismazāk. Bet, pat ja es uzskatu, numur viens, pirmkārt, ja es nezinu neko citu par pārējie skaitļi, kas man nav, viss, ko es zina, ka es esmu bijis nodots masīvs vai kopums, durvis, aiz kuriem ir numurus, vienīgais veids, kā es zinu, ka viens bija mazākais? Ja man visu ceļu šeit un saprast, damn, viens bija patiešām mazākais. Bet kā es varu, tad nosaka, ka divi ir nākamais mazākais? Darot to pašu neefektivitāti atkal un atkal. Tātad beidzot, ar ievietošanas veida, kā, sliktākajā gadījumā, tomēr mēs sakām tā veic? Tas arī ir n rūtiņām. Un kā ar to labākajā gadījumā? Mēs ņemšu atvaļinājumu, ka cliffhanger. Mēs aizpildīt šo tukšo nākamreiz, bet vispirms ļaujiet man ieteikt, ka mēs būtiski darīt labāk nekā visi šie, labi? Tāpēc domāju, ka sev ko ievietošanas kārtot būs. Labi, ka nebija ļoti dramatiska, tāpēc, ka es esmu tikai viens kas redzēja izmaiņas. Wow. Labi. Tātad, šeit mums ir nedaudz atšķirīgs demonstrācija. Ja es tuvinātu šeit, jūs redzēsiet, ka kreisi mums ir burbulis veida, kas vidū mums ir atlases veida, un cik labi, mums ir kaut kas, mēs nav paskatījās vēl aicināja apvienot kārtot. Bet uzskatu, ko mēs esam bijuši te dari līdz šim šodien. Kad Jennifer pirmo reizi nāca uz skatuves, mēs gājām cauri masīva numuru atkal, un atkal, ar lineāro meklēšanu, un mēs saņēmām lineāru darba laiku, big O no n, tā sakot. Kad mēs tagad uzskata, ka pirmajā nedēļā klasē, kad mums bija skaldi un valdi, un mums bija telefona grāmatu plīsumi, un Jennifer, un mēs kopīgi parādi, ka atslēgu ieskatu, kas bija atkārtot sevi atkal un atkal kaut kā throwing prom, throwing prom, throwing prom, no problēmas puse, vai parasti, dalot problēma pusi, un pēc tam apstrādājot mazāku gabalu problēma, jo konceptuāli ekvivalents uz otru, mēs kaut kā bija fundamentāli labāk. Bet ar burbuļu veida, ar atlases kārtot, ar ievietošanas veida, mēs esam var nav tādas atziņas, ka Dženifera darīja. Mēs diezgan daudz tikai gāja atpakaļ un tālāk viss ķekars reizes, un mēs tweaked lietas mazliet, pārnešana šādā secībā, varbūt Ievietojot vai izvēloties. Bet beigās, dienā, es did daudz no neērtā kājām un atpakaļ. Mums nav īsti sviras kaut ko smart piemēram, Jennifer darīja, piemēram, dalot un iekarošana. Tātad apvienot kārtot, gluži pretēji, kuru mēs nebūs redzēt tikai nākamajā nedēļā, tas notiek lai piesaistītu ka galvenais ideja dalot ievadi, un pēc tam uz pusi, un pēc tam pusi, un pēc tam pusi. Un uz katra atkārtojuma šīs cilpas, šķirošana kreiso pusi, un labais puse, tad kreiso pusi no kreisās puses, un labajā pusē no kreisās puses, tad kreiso pusi no labās puses, un tiesības puse no labajā pusē. Un atkārtojot atkal un atkal. Tātad, jūs redzēsiet to vizuāli, bet tas ir tas, kas mūs sagaida nākamajā nedēļā. Un vispār, kad mēs domājam, nedaudz mazliet grūtāk par šādu problēmu. Mums ir n rūtiņām pa kreisi, n kvadrātā vidū, un n log n labajā pusē. Tātad tur ir jūsu reālā cliffhanger. Mēs tiksimies pirmdien. [Aplausi]