[Powered by Google Translate] [3 nedēļas, Turpinājums] 

[David J. Malan - Hārvarda] 

[Tas ir CS50. - CS50.TV] 

Labi. Laipni lūdzam atpakaļ. Tas ir CS50 un tas ir beigu 3 nedēļas. 

Tātad tiem svešs, pagājušā gada Hārvardas uzsāka ko sauc Inovāciju Lab, vai i-lab, kas ir brīnišķīga ēka pāri upei uz HBS pilsētiņas kas ir atvērta koledžu studentiem, ĢAA studentiem, studenti no visas pilsētiņas, ieskaitot fakultāte, un tā ir vieta, kur sanākt kopā, lai strādātu pie inovatīviem lietām, īpaši uzņēmējdarbības lietas ja un 0 vai vairāk draugu domā par kaut ko dara uzņēmējdarbības nu šajā klasē, pēc šīs klases, vai ārpus tās. 

Tātad viena no lietām, ko viņi dara pāri J termiņā ir šie braucieni, no kuriem viens ir New York, viens no kuriem ir Silicon Valley. Telpa ir ļoti ierobežota, bet tas ir iespēja berzēt pleciem ar MBA un pēcdiploma studentiem pāri Campus un faktiski tērēt laiku šajās attiecīgajās jomās čatā augšu jaunizveidotiem, čatā augšu uzņēmējus un tamlīdzīgi. Tātad, ja interese, pārbaudiet šo URL šeit. Tas ir pieejams arī uz slaidiem tiešsaistē. 

Vai mēs pieklusināt māju audio tikai mazliet? Ja jūs vēlētos, lai pievienoties mums pusdienās šo piektdien, 13:15 jo Fire & Ice, lūdzu galvu tur. Atvainojos, ja veidlapa ir jau aizpildīta ar laiku jums tur. Taču mēs turpināsim šo tradīciju vēlāk. 

Šodien mēs turpinām augstāka līmeņa diskusiju par dažādām problēmām, ka mēs varam atrisināt, koncentrējoties daudz mazāk, šodien vismaz uz kodu un vēl daudz vairāk par idejām. Tāpēc domāju, ka atpakaļ līdz 0 nedēļā, kad mēs saplēsa tālruņa grāmatu pusē, gada kura mērķis bija kaut ko darīt, protams, mazliet dramatisks bet nosūtīt punktu, ka meklēšana nav jābūt, obligāti, kā skaidrs pēc pirmā acu uzmetiena, kā jūs varētu domāt. Un problēmu risināšana vispār varētu nebūt vienmēr būs labākā - Pašsaprotama risinājums varētu nebūt labākais. Tāpēc mums bija šī tālruņa grāmatu un, godīgi sakot, mums visiem šajā telpā bija instinktiem, visticamāk, lai sāktu vidū, meklējot Mike Smith un tad iet pa kreisi vai pa labi pamatojoties uz neatkarīgi alfabēta burts mums gadījās nonākt. 

Bet ka vienkārša ideja, ka mēs cilvēkiem ir pašsaprotama tik ilgi tiešām vajadzētu sākt nākt uz priekšgalā jūsu prātā jo, kā problēmas iegūt daudz sarežģītāka nekā tālruņa grāmatu, šie paši vienkārši, izcili atklāsmes ir tas, ko gatavojas ļauj mums atrisināt daudz sarežģītāka un interesantāka problēmas, Starp tām dažas no lietām, ko mēs uzskatām par pašsaprotamu jau šajās dienās. Miljardiem tīmekļa lapas, kas tur, un vēl Google un Bing un tamlīdzīgi ir iespēja atrast lietas mums tāpat. Tas nav noticis, izmantojot lineāro meklēšanu, meklējot visos iespējamos interneta lapas. Facebook ir spējīgs pateikt, kas visiem saviem draugiem ir vai draugu draugi, un ka pārāk var izdarīt šķietami vienā mirklī šajās dienās pat ja tie ir miljoniem lietotāju. 

Un tā kā mēs patiesībā risināt problēmas šajā mērogā galu galā samazinās uz idejām mēs paskatījās pieejama 0 nedēļā un mazliet vairāk šodien. Mēs ne atkārtoti izpildīt šo algoritmu, bet atgādināt mēs arī darījām nedēļā 0 šī uzdevuma kur mums bija visi piecelties, uzņemties numuru 1, un tad mums bija ikvienam sevi skaitīšanas ko pārī off, pievienojot savu telefona numurus, tad puse no bandas apsēdās uz katra atkārtojuma. Tātad, mēs devāmies no 500 skolēniem uz 250-125 un tā tālāk. Bet kā mēs pirmdien paziņoja, spēcīgs ideja tur bija tas, ka, ja mēs dubultojies lielumu šo problēmu un visi no Tieslietu vai EK 10 bērni nāca atpakaļ istabā un pievienojies mums, labi, mēs varētu droši rēķināties, ka viss kopējais grupu tikai ar vēl 1 liels atkārtojuma no cilpas, jo viņi tikai varbūt divtik vai EK 10 lietu nedaudz vairāk nekā divas reizes izmēru. Un tā mēs būtu tērēt mazliet vairāk laika, bet mēs nebūtu jātērē 400 vai 700 vairāk soļus. 

Tikai, lai krāsu šo attēlu tādā veidā, kas ir nedaudz mazāk abstrakta, pieņemsim, nav visi piecelties. Bet, ja tie no jums, kas izvēlējās sēdēt orķestra šodien nebūtu prāta stāvus, pieņemsim redzēt, ja mēs varam izdomāt starp jums, kas ir augstākā persona ir darot to pašu veida salīdzinošo algoritmu. Tātad, ja jūs sēžat orķestrī, manu atvainošanos, bet soli 1, piecelties; soli 2, pāris off ar Ikviens tuvumā tu, skaitlis, kurš ir garāks, un apsēsties, ja Jums ir īsāks. Tad atkārtot. [Studenti murmuring] 

Labi. Labi. Viens ir palicis stāvot. Kāds ir Jūsu vārds? >> Andrew. 

Andrew, jums ir garākais cilvēks orķestris sadaļā šodien. 

Apsveicu. [Aplausi un uzmundrinoša] Labi. Ir vieta. Tāpēc mēs atradām Andrejam. Bet cik ilgi tas tā ir veikusi mani, piemēram, lai atrastu Andrejam Šajā orķestrim sadaļā 50 + vai lai cilvēki? Es varētu būt veikusi diezgan vienkāršu pieeju un sākt šeit. Un man ir 2 cilvēki piecelties un es tikko salīdzināt tos, un tad es saku, lai kurš ir nedaudz īsāks, "Labi, tu apsēdies," un es esmu gatavojas atcerēties, kas garāki persona. Tad es atkārtoju, atkārtoju, atkārtoju, un es pakārt uz garākais personai līdz es atrast kādu nedaudz garāks nekā tiem, kurā brīdī nedaudz īsāks personai ir tad sēdēt. Bet šajā algoritma šajā orķestrī sadaļā, ja tur ir n no jums, cik soļus ir tas, ka algoritms gatavojas veikt? >> [Students] N. 

Tas notiek, lai n, pa labi, jo sliktākajā gadījumā, tā teikt, garākais cilvēks ir ļoti pēdējā persona, kas man vienkārši izlases neveiksmēm. Tātad sliktākajā gadījumā, darbības laiks šīs algoritms ir lineāra, tas ir n, kur n ir kopējais cilvēku skaits telpā, lielumu problēmu. Ko par šo algoritmu? Fakts, ka jūs visi piecēlās un tad atkal puse no jums apsēdās, puse no jums apsēdās, puse no jums apsēdās. Cik soļus, kas jāveic, ja tur ir n no jums šeit? [Students] N log n. >> Tas būtu sliktāk. Log n. 

Tātad log n, pat ja jums nav gluži atcerēties, ko logaritms ir, tagad, tikai saprotu, ka tas attiecas kaut uz šo pusi un pusi un pusi. Tai nav jābūt koeficientu 2. Tas varētu būt faktors gada 3. Bet tas ir tas atkārtošanās paša veida faktoru šāda ka problēmas lielums sākas šeit bet tad uzreiz iet šeit, tad šeit, tad šeit, tad šeit. Jūs neesat lietojat nelielu kodumi no problēmas, jūs tiešām kapāšanas prom pie tā ar lielu samazinājās sagrābt katru reizi. Tāpēc mums bija 50 cilvēki, tad 25, tad 12 ½ vai 13 cilvēki stāv, tad 6 ½ un tā tālāk, līdz beidzot tikai Endrjū palika stāvot. Tāpēc mēs esam gatavojas aicināt ka žurnālu n, un jūs varat iztēloties šo šādi. Atceros šo bildi šeit, kur lineāra algoritms ir kā sarkanās līnijas tur, dzeltenā līnija bija skaitīšanas par 2s algoritmu, ka mēs izmantojām, lai uzskaitītu studentiem pagātnē, bet šodien Svētais Grāls gatavojas saglabāt šo zaļo līniju kur, ja mēs dubultojies to cilvēku skaits, kas orķestra sadaļā vai vienkārši teica, ellē, pieņemsim ir ikvienam visā telpā piecelties, nav tik liels darījumu jo mēs rupji dubultot, cik daudz cilvēku ir uz leju šeit, 1 vairāk atkārtojumu, nevis problēma. 

Mēs esam noskaidrojuši, Andrejs vai kurš notiek, ir garāks nekā Andrew ar mezzanine vai uz balkona. Tāpēc šo vienkāršo domu, ka mums bija tik daudz par pašsaprotamu telefona grāmatā, apzināties, ka ir tik daudz dažādās vietās, kā mēs varam piemērot. Tikai, lai iepļaukāt daži žargons - patiesībā, nevis žargona pirmkārt, ļaujiet man iet uz šo attēlu šeit. Tieši tagad mēs runājām par un n / 2 un tad log n, bet mēs noteikti var nākt klajā ar, kā mēs gaitā semestra, cita veida matemātisku formulu, lai aprakstītu šo vispārējo jēdzienu darba laika. Tie ir ārpus kontekstā tagad, jo mēs redzēsim pirms ilgi algoritmus, ka tie faktiski pārstāv. 

Bet pamanīt šeit lineāro līniju N, taisni, tiešām ir ļoti zems norādot tiesības tagad. Tas ir sava veida ilūziju, ka mēs vienkārši mainīt to, ko x ass pārstāv un y asi, un mēs varam darīt taisnu līniju punktu jebkurā virzienā mēs vēlamies. Bet tāpēc, ka tas ir tik šķietami dzīvoklis tagad ir tāpēc, ka mums vajadzēja, lai padarītu telpu par šo grafikā par daudz lēnāk darbojas reizes. Tagad zinu, ka ir dažas diezgan slikti algoritmus dzīvē, no kuriem daži nav veikt n pasākumus vai, vēl labāk, log n pasākumus, bet vairāk. Tātad virs līnijas n šeit apakšā paziņojuma tur n reizes žurnālu n, un mēs redzēsim, ko tas nozīmē pirms ilgi. Virs ka ir n rūtiņām, un mēs neesam redzējuši nevienu n kvadrātā algoritmus vēl, bet mēs esam par to. Un tas izskatās tiešām slikti. Tur ir 2 līdz n, kaut eksponenciāls, kas jūtas vēl sliktāk. Un vēl, savādi, tad tur ir n kubā, kas, ja jūs esat veida domāšana uz priekšu, ja jūs veida math, 2 līdz n faktiski kļūst daudz taisnāki, daudz augstāk nekā n kubā, ja paskatās asīm pietiekami tālu. Tāpēc pamanīt tagad šie virzieni ir patvaļīgi 2-10 uz x ass. 

Un ko tas nozīmē? Tas nozīmē, 2 cilvēki līdz 10 cilvēkiem istabā. Tas ir viss x nozīmē: lielums problēmu, neatkarīgi no konteksta ir. Un vertikālās ass tieši tagad ir sekunžu skaits vai pakāpienu skaits - Dažas vienības laika. Bet paziņo, ka tā ir 0-60 un 0 līdz 10. Bet, ja mēs veida zoom out, kā jūs varētu Excel vai kādu kartēšanas programmatūru, un mēs ejam līdz 200,000, pamanīt, ka kaut kas līdzīgs 2 līdz n gatavojas pilnībā pārņemt kārtējās laikus n brusas, n kubā, n log n - viss, ko mēs esam runājuši par līdz šim. Un vēl nozveja ir tad, kad jūs sākat runāt par lietām, piemēram, Facebook kur jums ir daudzi, daudzi, daudzi cilvēki visi savstarpēji saistīti, Jums ir n cilvēki, no kuriem katrs var būt tik daudz kā n draugiem ja visi ir sava veida draugs-draugs pasaulē, labi, ka ir n reizes n jau tā, ka ir n kvadrātā iespējamos draudzību, vismaz 1 virzienā, n kvadrātā iespējamo draudzību. Lai jau liecina, ka meklēšana Facebook sociālo grafiku, tā teikt, var sākt izteikt šajos formulas veidu. 

Mēs būsim atpakaļ un padarīt šo daudz betona, bet tagad, mērķis nākamajiem daudziem nedēļas būs pārliecinieties, nevis iet par īstenojot algoritmiem vai kods ka galu galā, ņemot tik daudz laika kā kaut kas līdzīgs šim. Bet aizraujošu lieta par datorzinātņu, ja jūs turpināt šajā jomā ņemot klasēm, piemēram, CS121, CS124, kas abi ir teorija kursi, ir, ka faktiski ir dažas problēmas, kas pastāv šajā pasaulē ka būtiski, cik mēs zinām, nevar atrisināt ātrāk nekā šo grafiku sliktākajiem patiesībā liecina. Tāpēc tur atklātu problēmas šajā pasaulē, lai darīt daudz labāk nekā cilvēki ir līdz šim partiju. 

Tāpēc sāksim tad ar šo piemēru. Mēs redzējām Šons cīnīties ar šo par kameru, viss ir pārāk neveikli video. Bet realitāte bija, kad Šons uzdevums bija atrast uz kuģa, piemēram, tas par 7, atceros, ka es teicu, ka, "Tur ir kaut kur aiz šiem papīra gabalu vai balto durvīm "Skaits 7 Sean. Atrast to par mums." Un tas bija lieliski neērti skatīties jo viņš bija tiešām cīnās ar šo problēmu. Bet realitāte bija Sean darīja, kā arī ikviens telpā varēja izdarīt. Viņš paņēma mazliet ilgāk nekā tipisks persona varētu būt, bet viņš secinājis, ka tur bija daži triks ar šo problēmu, viņš secinājis, ka viņš bija pazudis kaut. Un tā nav palīdzība, ka simtiem acis bija nes uz leju uz viņu. 

Bet realitāte bija ja ieeja uz problēmu, ir ķekars izlases numurus un jūs to lūdza, lai atrastu 1 tāds numurs, vislabāk varat darīt, ir lineāra meklēt. Sākas kreisi, pāriet uz labo, vai sākt labajā, pārvietot pa kreisi. Atpakaļejošu datumu, mēs varētu domāt, "Sean, kāpēc nav jūs vienkārši sākt no otra gala?" Nu, 7 varētu būt tikpat viegli ir šeit nejauši, bet es apzināti likt to tur, jo es sapratu, viņš nav gatavojas sākt beigās. Tāpēc es veida manipulē situāciju, bet pēc nejaušības 7 varētu būt jebkur. Tātad sākot no labajā pusē varētu būt labāk tad, bet ko tad, ja nākamajā gadā es pārvietot 7 citur? Tas nav principiāli jauna problēmas risinājums - sākot no 1 gada beigās vai citu - ja jūs esat dota nav citas pieņēmumus. Tāpēc Šons sāka meklē caur skaitļiem un viņš teica, "5 Tas nav šeit.". Tad viņš aizgāja šeit un redzēju 19, tad viņš apstājās aptuveni 20 sekundes, tad viņš atvēra šo par 13, un tad kļuva skaidrs, ka tur nav, šķiet, ir modelis šeit. Tas bija nevis 1, 2, 3, 4 vai tamlīdzīgi. Tur bija nepilnības skaitļiem, kas nepalīdzēja. Un arī, ka es izmantoti šos lētu papīra gabaliem, lai segtu līdz skaitļus faktiski apzināta, jo, ja es noņemt visus šos papīra gabaliem, Vairumam no mums, Šons iekļauts, iespējams, būtu paskatījās veida makroskopiski pie tāfeles un teica: "Ak, 7 ir acīmredzami labi tur." Mēs to uzreiz. 

Un kas varētu būt veids, kā darbojas cilvēka smadzenes, lai zināmā mērā, bet patiesībā, viņa acis vai prāta, iespējams, bija apdedžu ciparus no labās uz kreiso, kreisās uz labo, vidēju uz out - kaut kas notiek fizioloģiski tāda, ka tā jutos kā tas bija noticis uzreiz, bet izredzes ir vēl iekšēji tur bija daži no metodoloģijas veida, lai atrastu 7. Un tiešām, tagad, ka mēs runājam par masīvu un datu struktūras un atmiņas iekšpusē datoru, vienīgais, ko mēs, cilvēki var darīt ir apskatīt atsevišķu atmiņas vietās 1 laikā. 

Tāpēc katru citu vietu varētu arī tikt uz augšu ar kādu papīra jo mēs nevaram redzēt to anyway. Mēs varam darīt tikai 1 lieta laikā. Tātad šajā gadījumā, jo Šona gadījumā mēs devāmies šeit un tad mēs devāmies šeit un tad mēs devāmies šeit, šeit, šeit, šeit, ieguva gudrs beigām un tikai veida izlaidis šo vienu patvaļīgi un konstatēja 7 Ir. Tas viens bija ne sevišķi īpašs. Tas arī bija bojātas. Bet viņš beidzot ir atrasts 7. Bet tagad takeaway patiešām ir, ka labākais jūs varat darīt, ja sniegta nekāda informācija izņemot nejauši Šķirotu numuriem ir jāsāk no kreisās vai sākt no labās puses. Vai heck, jūs varat nejauši atvērt durvis, bet pat tad ko tas nozīmē būt nejauši? Nu, mēs ir kaut formalizēt to, ko nozīmē sākt šeit, tad iet šeit, tad iet šeit. Šons bija liels, un tas bija tikai jautri skatīties. Ko darīt, ja tā vietā mēs mainīt šo problēmu mazliet un audzināt šī gada Šonu, ja jūs? Vai kāds būtu ērti nāk uz skatuves un risināšanas nedaudz cita problēma un parādās uz kameru? 

Iesim tālāk orķestra jo jums puiši ir diezgan, jo jau šodien. Kā par rozā, jo cepure? Nāciet uz leju. Kāds ir Jūsu vārds? >> Alex. >> Alex. Labi. Tāpēc Alex būs šī gada Šons un parādīsies tuvāko gadu laikā vērts CS50 lekcijas. Alex, nice to meet you. >> Prieks iepazīties pārāk. Pie rokas jums izaicinājums ir tas, ka jums ir tas mazliet vieglāk jo es esmu stāsta jums paši numuri ir šeit, bet tagad sakārtots. Tāpēc tagad jūsu mērķis ir atrast numuru 7. Un tiešām, mums patiešām vajadzētu darīt to - jūs esat nokļuvis veida krāpšanos, kā dators nav, pēc tā, ko skaitļi bija pirms brīža. Ar krītu tas patiesībā nav dodas, lai palīdzētu visiem, ka daudz, bet pieņemsim izlikties, ka jūs nezināt, ko sākotnējā masīvs ir. Visi jūs zināt tagad ir tas, ka jums ir masīva sakārtoti numuru kas varētu būt atšķirības starp tām, un jūsu mērķis ir atrast numuru 7. Kā Jūs, saprātīgs cilvēks, iet par atrast numuru 7? 

Aiziet no zemas līdz augstam? >> Labi. Aiziet zemā uz augsto. Un nav asaru tos off. Pieņemsim tikai pacelt tos, lai mēs varētu tos izmantot. Labi, tā 1. Pagaidiet. Pirms jūs glabāt notiek, ka bija 1, pilnīgi nepareizi. Tātad, kas notiek ar jūsu prātā nākamais? Kāds ir jūsu nākamais solis? Nākamais. >> Labi. Nākamo. Labi. 3, tāpēc nepareizs. Kāds ir jūsu nākamais solis? Turēt uz iet. >> Visas tiesības. Turēt uz iet. 5. Tā turēt uz iet, un ļaujiet man nodot jums šo nākamajām paaudzēm. 7. >> Lieliska. Ļoti labi. Atrada numuru 7. [Aplausi] Tā, ka bija labs, bet Šons pārāk atrada numuru 7. Un es apgalvo, ka jums nav īsti izmantot šo papildu informācijas vienību, kas ir tas, ka šie skaitļi ir sakārtoti. Tātad mēs varam darīt labāk? Kādi ieteikumi šeit? Jā, jo atpakaļ. [Students] binārā meklēšana. >> Man nav ne jausmas, ko binārā meklēšana ir. 

[Students] Sākt vidū. >> Sākt vidū. Labi. Tātad, pieņemsim redzēt, ja mēs varam tur nokļūt. Tātad, ja tā vietā jūs esat teicis sākas no vidus, iet uz priekšu un atvērt vidū durvis. Ir 8 no tiem, lai jūs nāksies patvaļīgi izvēlēties vienu nedaudz pa kreisi vai pa labi. Labi. 7! [Aplausi] Ļoti jauka. Labi, bet kur bija mums iet ar šo? Pieņemsim tikai, lai izjauktu kaklasaites jums bija sākusies šeit jo tas vienlīdz varētu būt noticis, kā arī. Mēs tikko notika zināt, ka 7 bija tur. Tātad šis ir 13. Tātad, ja viņi šķiro un mēs tikko sāka vidū, kāds būtu optimālais nākamais solis ir? Iet pa kreisi. Un tāpēc šeit nāk tālruņu grāmatas piemērs vēlreiz. Ja 13 ir šeit un mēs zinām saraksts tiek sakārtots, tad visi no šiem papīra gabalu ir neinteresanti mums tagad jo mēs jau zinām, ka 7 ir jābūt pa kreisi ja šie skaitļi ir sakārtoti un mēs konstatējām 13. 

Tātad, kādi ir jūsu nākamais solis šeit? >> Iet pa kreisi. >> Labi, labi. Lai iet pa kreisi, un - pagaidiet, hey, hey, hey. Tas ir blēdība. Tātad jums atrast 7, bet to, kas bija algoritmu mēs tikai piemērots? Sākt vidū. >> Labi. Tātad, kāda ir loģisks turpinājums šo pašu ideju? Ak, lai tikai tie. >> Tieši tā. >> Tāpēc es sāktu šeit. >> Labi. Tāpēc tagad mēs devāmies nedaudz pa kreisi atkal. Tas ir 3. Bet interesanti takeaway tagad ir, ko viena jums nav jārūpējas par? Šie 2. >> Šie 2. Tāpēc tagad tas var iet prom, tas var iet prom. Tagad problēma, ka bija 8, tad bija izmērs 4 tagad ir izmērs 2. Mēs esam kļūst diezgan tuvu. Atkal iet uz vidu šiem 2 elementiem. 

Labi. Tātad, tas ir sava veida žēl, ka tagad mēs esam vienmēr iet pa kreisi, jo mēs esam noapaļojot uz leju. Bet tas ir labi, jo tagad mēs mest šo prom un viss pārējais, atstājot mūs ar 7 tikai. Dosim kārta aplausi. Esam atraduši 7 vēlreiz. [Aplausi] Labi. Pārliecināts. Pakārt par tikai 1 vēl sekundi. Kaut gan, ka nākamais process veida bija nedaudz ilgāk, nekā mēs uzskatījām, tas būtu, godīgi sakot, jūsu pirmās instinkti bija labākais, vai ne? Esam atraduši 7 uzreiz. Bet mēs esam atraduši 7 ātrāk, vienalga ko, šajā piemērā versus šo vienu jo, ja šie numuri ir viss sakārtots, līdzīgi kā ar tālruni grāmatas lappusēm, Jūs varat patiešām cirst pusi problēmas atkal un atkal un atkal. Un tas nav tik viegli redzēt to ar tikai 8 numuriem pretstatā 1000 lappuses telefona grāmatu, kur jūs patiešām redzēt to vizuāli, bet šajā gadījumā šeit, kad Šons bija meklējot 7, cik soļus Sliktākajā gadījumā tas tā ir veikusi viņam? >> [Students] 7. 7 sliktākajā gadījumā. Nu, sliktākajā gadījumā nav 7 Ja tur ir 8 durvis šeit. Tas būtu jāņem viņam 8 soļi. 

Tātad, ja tur n durvis, tas varētu būt veikusi Šonu pirms pāris gadiem n soļus. Tagad, jūsu gadījumā, Alekss, ņemot vērā, ka šie skaitļi ir sakārtoti - un mēs varam veida nesecinot šo no kurienes mēs esam bijuši līdz šim šajā stāstā - kāda ir darbības laiks Alex vairāk viedo algoritmu gada sākot no vidus, un pēc tam atkārtojot? [Students] 3. >> Tātad tas būs 3, rupji, ja jums iet 8-4 2 līdz 1. Tātad 3 soļi vai, plašākā nozīmē, ka ir log n vēlreiz. Jebkurā laikā jūs uz pusi un pusi un pusi un pusi, tas izpaužas šo ideju žurnāla n. Un lai būtu ņemti jums tikai 3 soļus, un tas notika kad mēs atvērām durvis uz pusi un pusi, tā kā tas būtu jāņem Šons par 7 vai 8 soļus. Tāpēc paldies, ka esat kopā ar mums šajā gadā. >> Paldies. Nice tikšanos ar Jums. Paldies Alex. >> Tāpat. [Aplausi] 

Kas tad reālais saistība ar šo? Tagad iedomājieties, ka tas nav 8 durvis, kuras, godīgi sakot, mums visiem varētu atrast kaut ko aiz 8 durvis diezgan ātri, vienkārši plīsumi papīra gabaliņus un iet ar mūsu instinktiem. Bet ko tad, ja tas ir viens miljons durvis? Ko darīt, ja tas ir 4000000000 durvis? Attiecībā ir 4 miljardi durvju, jūs tiešām gatavojas vēlaties doties ar Alex algoritmu, binārā meklēšana, kā mēs sāksim aicinot to vai skaldi un valdi, plašāk, kur jums saglabāt pusi un pusi problēmu, jo, ja jums ir 4000000000 durvis, cik reizes jūs varat cirst 4 miljardus pusi? [Students] 32. >> Tas ir tiešām 32. Jūs varat strādāt šo out uz papīra vai savā galvā. Jūs dodieties 4000000000-2000000000 to 1 miljardu pusmiljardu, līdz 250 miljoniem, dot, dot, dot. Un, ja jūs, kas to math, jūs gatavojas tiešām saņem 32, un faktiski attiecas uz datorzinātņu jo mēs parasti rēķināties ar pilnvaru 2. 2-32 no notiek, ir 4 miljardi. Tātad tur ir sakars ar šiem pilnvaras 2 datorzinātņu veidu daudz. 

Bet ko 8 miljardu? Cik soļus ir tas, ka gatavojas veikt, ja ir 8000000000 durvis? [Students] 33. >> Tātad 33. Ko darīt, ja tur 16000000000 durvis? Cik soļus ir tas, ka gatavojas veikt? [Students] 34. >> 34. Mēs varētu veida turpina šo reklāmu nauseam. Bet tas ir spēcīgs lieta. Jūs varat ieviest miljardiem vairāk resursu, lai savu problēmu, bet, nav liels galā, Jūs tikai 1 papildu kodums no tā un tādējādi dod mums kaut kas līdzīgs bināro meklēšanu vai skaldi un valdi, kopumā. Bet es esmu veida krāpšanos šeit, vai ne? Attiecībā uz Alex algoritmu, viņa bija priekšrocības pār Šonu. Viņa zināja, ka šie skaitļi ir sakārtoti, bet Alekss nebija šķirot tos sev. Es jau iepriekš nāca klajā ar tāfeles un veidu pārliecināts ka es vērsa tos visus, kas sakārtoti secībā, tad es uz tiem ar papīru. Bet cik daudz darba bija, ka mani aizvest? Ja mēs būtu sākās ar šiem dažiem šķietami nejaušā secībā numuriem - Šajā gadījumā šie vienkāršāki numurus, 1 līdz 8 šeit - Kā mēs iet par šķirošanas šīs vērtības? Ja tu būtu cilvēks dots šis uzdevums, kāda veida intuitīvu pieeju jūs ņemtu lai šķirošanas visu ķekars numuriem? Šīs lietas tika izklāstīts, kā puzzle gabaliem. Yeah. 

[Students] es būtu katru numuru un salīdzināt to ar katru vienu un tur notiek pa kreisi. >> Labi, labi. Tātad, ņem katru numuru, salīdziniet to ar vienu blakus tam, un tad tikai glabāt pārvietojas pa saraksta, kāda veida rejiggering lietas kā jums iet. Tātad šeit mums ir izredzes uz varbūt vēl dažus ļaudīm iesaistīties. Vai mums ir vēl 8 brīvprātīgos, kuri labprāt vēlētos nākt klajā? Nedaudz mazāks spiediens, jo jūs esat ne tikai viens. 1, 2, 3, 4, 5, 6, 7, 8. Nāciet uz leju. Jūs guys būs numuriem no 1 līdz 8. Redzēsim, vai mēs nevaram darīt šķirošanu Alex daudz pašā veidā es to darīja iepriekš. 1, 2, 3, 4. Iet uz priekšu un, ja tu būtu, rindā uz skatuves starp mūzikas stāvēt un man šeit tādā pašā kārtībā kā slaidu uz ekrāna. Uh-oh. Mēs sadarbosimies tevi uz nākamo piemēru. Ak, pagaidiet, pagaidiet. Šeit mēs iet. Pagaidiet. Nākamais piemērs ir tagad. Šeit jums iet. Numuru 8. Nāciet uz augšu. Labi. Kārtot paši saskaņā ar šo. Slaidu tikai mazliet uz pusi mūzikas stāvēt šeit. Tāpēc mums ir 4, 2, 6 - nokļūt tur, nekā šeit, tieši tur - 3. Yeah. Labi. Jums iet vairāk nekā šeit. Nē, tu paliec tur. Jā, tieši tur. Nē, es kļūdos. Labi tur. Labi, ļoti labi. Labi. Tāpēc tagad pieņemsim šķirot tos arvien kārtībā. 

Kā es varu iet par to izdarīt? Algoritms, kas tika ierosināta pirms brīža bija kāpēc nav mēs vienkārši salīdzināt ļaudīm, kas ir sava veida blakus viens otram un tad noteikt visas kļūdas, pārvietojas no kreisās uz labo pusi. Tātad šeit mums ir 4 un 2, protams bojātas. Pieņemsim mijmaiņas jums. Labi. Tāpēc tagad es esmu gatavojas pārvietot uz leju līniju. 4 un 6, nope. [Smiekli] 6 un 8, diezgan labi. 8 un 1, ļaujiet man swap jums puiši. Labi. Tātad 8 un 3 mijmaiņas jūs puiši. 8 un 7, ļaujiet man swap jums puiši. 5 un 8, lielisks. Es jums sakārtoti sarakstu. Labi. Tātad ne gluži. Bet tas ir labāk, jo lielāki skaitļi - gadījums paziņojuma 8 - ir sava veida kūsāja no kreisās pāri uz labo pusi. Tāpēc es saņēmu 1 no tiem labi, bet tā uzskata, piemēram, tas nav gluži atrisināt problēmu. 

Tātad, ko jūs ierosināt mums darīt tālāk? >> [Students] Uzglabāt darot to. >> Mēs saglabāt to dara. Un realizēt, atkal, mēs noteikt lietas izveidota, tikai ar visiem cilvēkiem kārtot inteliģenti organizēt sevi, pamatojoties uz šo attēlu, bet tagad mums ir jābūt daudz metodisko. Mums jābūt algoritmiskas par to, it kā mēs rakstiski kodu - šajā gadījumā vārdiskais pseudocode. Tāpēc ļaujiet man tikai mēģināt to vēlreiz. , Kas strādāja diezgan labi. Tas nav to atrisināt. Bet, kad tas šaubos, vienkārši izmēģināt un mēģiniet vēlreiz. SO 2 un 4, nepalīdzēja vairs. 4 un 6. Ah! 6 un 1, nedaudz labāk tagad. 6 un 3, labi. 6 un 7, 7 un 5, 7 un 8, labi. Un jūs zināt, es varu droši ignorēt 8 Tagad, jo viņš ir pie saraksta beigās. Varbūt mums nav jāuztraucas par kāds dodas viņam garām. Bet pieņemsim redzēt, ja tas ir drošs pieņēmums. Tagad saraksts ir - nopelt - nav sakārtots. Mēģināsim to atkal. SO 2 un 4, 4 un 1, 4 un 3. 4 un 6, labi. 6 un 5, labi. 6, 7, 8 un, labi. Bet paziņojums, es varu tikai apstāties šeit tagad apstāties šeit tagad? [Students] Jā. >> Yeah? Ko darīt, ja viens no jums būtu bijis numurs 9 līdz galam tur? Tas būtu sakārtoti. >> Labi. Tas būtu sakārtoti pirmo reizi apkārt. Labi. Tāpēc iesim atpakaļ. Mēs esam gandrīz tur. 1 un 2, 2 un 3, 3 un 4, 4 un 5, 5 un 6, 6 un 7, 7 un 8. 

Es esmu darīts tagad, bet, atkal, es esmu dators, kas var darīt tikai to, ko es esmu teicis darīt, un mans vienīgais atmiņas tagad ir tā, ka es tiešām tikko bija daudz darba. Kaut mainījies šeit. Tāpēc man nav tehniski apstiprināts vizuāli vai algoritmiski, ka šis saraksts ir tiešām sakārtots. Tik vienkārši labs pasākums, tikai lai būtu anālais par šo, pieņemsim do šo 1 vairāk laika. Tātad 1 un 2, 2 un 3, 3 un 4. Un jūs zināt, ko? Tikai labs pasākums, es esmu gatavojas, lai sekotu uz manu roku šo laiku cik mijmaiņas man darīt tikai tāpēc, ka es zinu, cik daudz darba es esmu patiešām izdarīt. 3 un 4, 4 un 5, 5 un 6, 6 un 7, 7 un 8. Nav mijmaiņas. Tāpēc tagad es būtu likumīgi idiots to darīt atkal jo, ja es tomēr nav darba caur šo iet uz cilvēkiem, tad skaidri tas notiks atkal, ja neviena no tām ir sava veida nejauši adversarially pārvietojas sevi apkārt. Tāpēc tagad es varētu apstāties. Tagad uzdot jautājumu, cik daudz darba bija tas patiesībā ņem mani? Cik soļus bija kas ņem? >> N kvadrātā. Jā, tā N kvadrātā. Ja jūs saņemsiet n rūtiņām no? Jums ir pārbaudīt katru skaits - Tur ir n numuri, un jums ir pārbaudīt katru numuru ar citām n numuriem. Labi. >> Tātad tas ir n rūtiņām. >> Labi. 

Tāpēc uzskata, ka tas varētu ļoti labi būt n rūtiņām, vai ne? Tur n no šiem puišiem, 8 īpaši šajā gadījumā, bet katru reizi, kad es devos caur šo sarakstu es biju salīdzinot pirmo personu pret otro, otrais pret trešo atkal un atkal un atkal, un, kad es saņēmu uz beigām, ko es daru? Es redid to. Tātad, ja mēs vispārināt šo paskaidrojumu, mēs esam n cilvēki un es esmu padarot, protams, 8 soļi, n pakāpieni, katru reizi, kad es iet caur šo algoritmu. Bet cik daudz reizes, sliktākajā gadījumā man ir jāiet caur šo sarakstu ar cilvēkiem? [Students] N reizes. >> Iespējams n, tiesības, jo sliktākajā gadījumā, kāda ir iespējams, sliktākais gadījums izkārtojums no šiem puišiem no get-go? Ja viņi pilnīgi pretēja kārtībā jo tikai pieņemsim garīgi, let's - Kāds ir Jūsu vārds? >> Bowen. Bowen. Labi. Tātad Bowen, nāk vairāk nekā šeit tikai brīdi. 

Pieņemsim, ka Bovens bija šeit sākumā algoritmu, un mēs nezinām, ko ikviens cits ir, bet Bowen šeit, saskaņā ar šo algoritmu - un, ja jūs vēlaties, lai vienkārši pastaigāties ar mani - gatavojas burbulis up, kā viņš to darīja pirmo reizi apkārt, visu ceļu līdz beigām. Bet pieņemsim, ka persona blakus Bowen bija numur 7. Man ir jāiet atpakaļ un saņemt numuru 7, kas nozīmē, ka man ir iet visu ceļu atpakaļ šeit. Tagad man ir jābūt, ka pati pastaiga ar personu, kas ir numurs 7. Bet ko tad, ja tam skaits 6 bija viņam blakus, kā arī? Tad man ir jāiet atpakaļ un saņemt 6. Tātad vēlreiz, par katru atkārtojuma šīs cilpas es runāju ar katru no n cilvēkiem, un es varētu darīt n no šīm pastaigām, lai pārliecinātos, es esmu nostiepes visi no lielākajiem elementiem atpakaļ un atpakaļ un atpakaļ līdz pašām beigām saraksta. Tātad n lietas n reizes ir tikai n reizes vai N kvadrātā. 

Tātad šeit jau mums ir algoritms, kas vairs n, kas vairs log n, tas patiesībā sliktāk, nekā kaut ko mēs esam darīts iepriekš. Tāpēc Alekss veida palaimējies, jo es darīju visu darbu acīmredzot līdz priekšējā viņai, visu dārgu darbu, lai viņa varētu baudīt šajā binārā meklēšanas algoritmu, kas ir žurnāls n. Bet tas ir saskaņā ar pirmdien tēmu. Mēs likām mazliet vairāk vietas, mēs izmantojām vairāk bitu, lai paātrinātu mūsu darba laika. Tik daudz kā tur tas kompromiss starp laiku un telpu, tur varētu būt arī vienkārši kompromisi starp laiks līdz priekšējo veida iegūt lietas gatavs doties un faktiski izpildot algoritmu, piemēram, meklēšanu. Pamēģināsim kādu citu. Ja jūs puiši nebūtu prāta tikai ātri pārkārtojot sevi, lai atbilstu, ka atkal pamēģināsim kaut nedaudz atšķirīgs, ja tas nav gluži tik vienkārši kā tikai noteikt visus pairwise kļūdas, kas ir super intuitīvi. Pieņemsim vietā būs nedaudz vairāk apzinātu un darīt. Šis viena arī es ieteiktu, ir iespējams diezgan saprātīgi. 

Pieņemsim izvēlētos mazāko personu no saraksta atkal un atkal. Tāpēc šeit mēs iet. 4, jums ir mazākais cilvēks es esmu līdz redzējis līdz šim, tāpēc es esmu gatavojas garīgi atcerēties, ka, tikai norādot uz tevi tagad. 2. Ooh! Aizmirstiet par 4 numuru. Es tikko atklāju jaunu mazākais elements šajā sarakstā. Es esmu gatavojas veida jāatceras, ka. 6, 8. Ooh! 1. Uz redzēšanos. Tāpēc tagad es esmu gatavojas atcerēties numuru 1. Mēs zinām, ka 1 ir mazākais, bet es esmu datoru. Ko darīt, ja tur ir 0? Ko darīt, ja tur ir -1? Man ir, lai saglabātu turpinās. Tātad 3, 7, 5, nope. Labi. Tātad skaitlis 1 bija mazākais. Ļaujiet man izvēlēties jūs no saraksta - we'll iet šādā veidā - un nodot jums patvaļīgi sākumā sarakstā. Tagad, pagaidiet minūti. Es veida apkrāpti. Ja šie puiši pārstāv nevis no 8 cilvēkiem sarakstu, bet masīvs, 8 gabalos pieguļošajā atmiņas - jūs prātā pastiprināšanu atpakaļ tikai brīdi? Tur tiešām nav par jums telpu šeit. Tātad, kā mēs atbrīvotu vietu - kāda ir jūsu vārds? >> Sammy. >> Sammy. Kā mēs atbrīvotu vietu Sammy? 

Mēs pārvietot n kas ir pirms manis. >> Labi. Lai mēs varētu virzīties uz n cilvēkiem, kas ir pirms viņa, Tātad, ja jūs puiši vēlas veikt 1 apzinātu, dramatisku soli pa kreisi. Viņi visi bija, ka unisonā, bet pēdējā laikā man rakstīja daži kodu, Jūs nevarat kārtot no pārvietot daudzas lietas visu uzreiz. Mēs varētu darīt to cilpu, pārvietojas ikvienam vienu reizi laikā. Tātad, ja jūs puiši nebūtu prāta pastiprināšanu atpakaļ uz labo pusi, un Sammy, ja jūs varētu soli atpakaļ, jo tur ir vēl nav par jums telpa, Tagad pieņemsim darīt. Kur bija Sammy pirms brīža? Labi tur. Tāpēc tur plaisa tur. Lai jūs varētu pārvietoties Sammy s vietas. Tagad nākamais cilvēks, un tagad nākamais cilvēks, tagad nākamais cilvēks. Tagad mums ir telpa Sammy. Tagad, kāds no skatītājiem - kas bija labs, tas bija pareizs, jutos nedaudz laikietilpīgs - kas ātrāks? Yeah. [Students] Jaunais masīvs? >> Kas tas ir? >> [Students] Jaunais masīvs? >> Labi, labi. 

Tātad saskaņā ar šo tēmu tikai kompromisus, kāpēc ne es tikai veikt jaunu masīvu  un tad Sammy tiks peldēšanas telpā priekšā šiem cilvēkiem, piemēram, un mēs varam tikai sākt aizpildot jaunu masīvu vispār. Tas arī būtu jāstrādā. Bet es neesmu ieinteresēts tērēt vairāk vietas šodien. Kas cita pieeja? [Students] Apmainīt. >> Labi. Mēs varētu tikai swap šos 2 puiši. Kāds ir Jūsu vārds? Mario. >> Mario. Tātad Mario, jums bija pašreiz šeit. Sammy, jūs varat dublēt tikai brīdi? Mario bija šeit. Mums nav vietas tevi, tādēļ, ja jūs nebūtu prātā dodas uz vietu, kur Sammy ir, mēs likts Sammy šeit, un tagad es gribētu apgalvot, ka Sammy s pārnešana darbība bija daudz ātrāk. Mēs darījām 1 darbību swap šie puiši, vai varbūt 2 swap šos guys, bet mēs nedarīja 1, 2, 3, 4, lai jūtas labāk. Tagad, pagaidiet minūti. Es veida izgatavoti problēma sliktāk, jo skaits 4 bija sava veida tuvu sākumam. Tagad skaitlis 4 ir nedaudz tuvāk šim nolūkam, bet man nav īsti zināt, vai rūp to. Tātad tas ir tikai nelaime, ka skaitlis 4 ir nedaudz tālāk no tās galamērķis vietas. Tāpēc pieņemsim tagad atkārtot šo algoritmu. 

Lai Atgādinājums, kamēr tas stāsts bija viss, kas mums bija bija staigāt pa sarakstu meklē mazāko numurētā personu. Tāpēc tagad pieņemsim to darīt vēlreiz. Mums nav jāuztraucas par Sammy vairs. Mēs varam tikai iet šeit. Ooh! Numurs 2. Tas ir diezgan mazs skaits. 6, 8, 4, 3, 7, 5. Labi, labi. Un par laimi, sagadīšanās, man nav, lai pārvietotos - >> Willie. Willie jo viņš ir savā īstajā vietā tagad. Darīsim to atkal un ignorēt šos 2 puiši. 6. Tas ir diezgan mazs skaits. Ooh! 8 ir noteikti lielāks. 4. Pieņemsim koncentrēties uz 4. Ooh! 3 ir pat labāk. 7 un 5. Tātad, ko mēs darām tagad ar - >> Rodžers. >> Rodžers? Pieņemsim mijmaiņas viņam ar 6 numuru. Tātad, ja 6 un 3 vēlētos swap, mēs esam tagad veida gotten laimīgs 6, ka ir tuvāk, kur viņa būtu, bet tas ir tikai sagadīšanās šeit. Tāpēc pieņemsim tagad iet šeit. 8 ir diezgan mazs skaits. Ooh! 4 ir mazāks. 6, 7, 5. Ko mēs tagad darām? >> Apmainīt. >> Tieši tā. Tāpēc tagad pieņemsim darīt šāda veida ātrāk. 8, 6, 7, 5. Kur paliek 5 aiziet? Labi. Labi. 6, 7, 8. 6 izpaužas palikt tur, kur viņa ir. Kāds ir Jūsu vārds? >> Rosalie. Rosalie izpaužas palikt tur, kur viņa ir. 7 izpaužas - Paskatīsimies. 7, 8. Labi. Tātad 7 izpaužas palikt tur, kur viņa ir. Kāds ir Jūsu vārds? >> Amna. >> Amna. 

Tāpēc Amna izpaužas palikt tur, kur viņa ir, un skaits 8 ir jau kur viņš tagad būtu. Labi, labi. Jūtas kā mēs esam tikai radīt darbu sev šeit, lai gan. Kas galu galā darbojas laiks šo algoritmu? Ja mēs domājam par šīm ne vien 8 bet kā n cilvēkiem? >> Tas ir n. Tas ir n soļus, bet mēs esam pārbaudot katru reizi. Labi. N bet jūs pārbaudot katru reizi? Labi, bet, ja tas ir n pasākumus, nebūtu man ir bijusi iespēja kārtot tevi tikai gatavojas 1, 2, 3, 4? Oh! Labi, ka ir liela atšķirība. Tātad n rūtiņām kāpēc? Kas īsti notiek? Ir n cilvēki šajā sarakstā, bet, lai atrastu mazāko personu sarakstā sliktākajā gadījumā, cik soļus man jābrauc? >> N. 

N, tiesības, jo sliktākajā gadījumā, Nr1 ir visu ceļu tur, tāpēc man ir iet saņemt viņam vai viņai. Un tad, kad es beidzot saproti 1 bija mazākais, tad tas ir diezgan ātri, lai mijmaiņas tiem. Bet tagad man ir jāsāk no sākuma un meklēt kas? Nākamais mazākais cilvēks, kas ir 2. Ja sliktākajā gadījumā ir 2? Ak, mans Dievs. Tas visu ceļu pāri šeit beigās. Tāpēc tagad es esmu tikai izdarīt vēl n soļus, vēl n soļiem. Un, ja mēs esam ieguvuši n cilvēkus un sliktākajā gadījumā mazākais cilvēks ir n soļu attālumā, tas atkal n reizes n, un tāpēc mēs atkal esam n rūtiņām. Tas nav slikta tik labi. Un patiesībā, pat labākajā gadījumā - domāju, ka viņi sāktu sakārtoti - cik soļus tas veic, lai man, izmantojot šo algoritmu, lai sakārtotu šos n cilvēkus? N brusas. >> Es dzirdēju n rūtiņām. Kāpēc n rūtiņām? Jo jums vēl ir jāpārbauda katru reizi. >> Jā. Un jums ir mijmaiņas tiem. >> Pat ja mēs cilvēki esam sava veida viszinošs tādā ziņā vizuāli ka mēs varam tikai veida redzēt, ka tas ir sakārtots, dators nav tik gudrs. Tas notiek, lai apskatīt šeit un šeit un šeit, bet, ja kas tas ir meklējat ir mazākais elements, jūs tikai zināt, ka jums atrast mazāko elementu ar kāda jēga? Kad esat beigās. Bet tajā brīdī, kad esat tikai atrast šobrīd mazākais elements. Jums nav obligāti zināt kaut ko citu par stāvokli pasaulē. Tātad jums ir jāiet atkal un atkal un atkal. 

Tāpēc šoreiz es tiešām izskatās muļķīgi, jo es esmu pārbaudes, labi, 2, tu esi mazākais, bet es nezinu, kas kopā vēl. 3, 4, 5, 6, 7, 8. Labi, labi. 2 bija patiešām mazākais. Tagad pieņemsim atrast nākamais mazākais. Labi. 3, tu esi šobrīd mazākais. Pieņemsim redzēt. 4, 5, 6, 7, 8. Labi, palaimējies vēlreiz. 3 bija patiešām pareizajā vietā. Bet es esmu gatavojas glabāt to izdarīt atkal un atkal un atkal. Kā mēs to varam izdarīt kādreiz tik nedaudz labāk? Tā vietā cilvēki burbulis augšu pairwise no mazākā uz lielāko un nevis iet uz priekšu un atpakaļ pa sarakstu izvēloties tad mazākais personu, kāpēc nav mēs nevis ievietot šos cilvēkus jaunā saraksta soli pa solim? Mēģināsim šo. Tagad ļaujiet man zvanīt šī lieta ievietošanas veida. Tāpēc šeit mēs esam šeit. Numurs 1. Man vienalga par kāds cits šajā sarakstā. Mans mērķis tagad ir likt numuru 1 sākumā sakārtoti sarakstu. Un es esmu gatavojas ierosināt, jo man ir tikai 8 gabalos atmiņas, patvaļīgi šobrīd es esmu siena starp manu domājams nešķirotu sarakstā, un ikviens, kurš ir aiz manis es esmu gatavojas pieprasīt tiek sakārtoti. Tāpēc tagad mums ir numurs 1. Es gribu, lai ievietotu viņu manā sakārtoti sarakstā, tāpēc es esmu tikai gatavojas pārvietot manu sienas nekā šeit, un tagad es apgalvo šis saraksts tiek sakārtots, šis saraksts tiek nešķirotu - vismaz tik cik es zinu. Es nevaru redzēt visus skaitļus uzreiz. 

Tagad es notikt saskarties numuru 2. Ko man darīt ar viņu? Es ievietot tevi tagad uz sakārtotās sarakstā. Bet paziņojums, cik viegli tas bija. Man vienkārši ir meklēt. Numurs 1 ir tur. Ak, protams 2 iet uz pusi 1 numuru. Tagad ko man darīt ar 3? Es ievietot tevi sakārtotās sarakstā. Bet tas bija super viegli. Tas ir super viegli, tas ir super viegli, tas ir super viegli, super viegli, super vienkārši. Un tagad viss ir sakārtots aiz manis, un cik soļus bija kas ņem? [Studenti] N. >> Tātad tas ir tikai n. Mēs saņēmām laimīgs. Tas bija tikai n kāpēc? >> [Students] Jo saraksts tika sakārtots. Saraksts ir jau sakārtots. Tātad mēs saņēmām laimīgs. Bet mēs paredzēti algoritmu šoreiz ka siksnām šāda veida veiksmi, ka labākā scenārija, ko cienām nevajadzīgu laiku. Tāpēc mums tagad ir tas, ko mēs saucam burbulis veidu kur cilvēki veida burbulis up pairwise. Mums tagad ir izvēles veida kur mēs raut ārā mazāko persona atkal un atkal. Un tagad mums ir ievietošanas veida, kur mēs veida aktīvi likt cilvēkiem, kur tie pieder jo arvien šķiroto sarakstā. Ja mēs varētu, kārtu aplausi šie puiši šeit. [Aplausi] Paņemsim mūsu 5 minūšu pārtraukumu šeit. Un, kad mēs atgriezīsimies, mēs trieciens visu šo algoritmu no ūdens ar kaut ko labāku. Labi. Pateicoties ļoti daudz. Jūs varat saglabāt tos kā suvenīrus. Labi. Mēs esam atpakaļ. 

Un Atgādinājums reālā ātri, mums bija šīs 3 dažādas pieejas šķirošanu, viss punkts, kas bija nokļūt līdz vietai, kur kāds, piemēram, Alex varētu meklēt sarakstu numurus ātrāk nekā kāds, piemēram, Šons varētu. Un, pat ja mums ir tik vienkāršus piemērus ar 8 numuriem, Jūs varētu ekstrapolēt viegli līdz 8 web lapas, 8 miljardiem tīmekļa lappuses vai 800,000,000 draugiem par Facebook. Tāpēc šie algoritmi noteikti var mērogu uz tām vērtībām veidu, un idejas ir galu galā pats. Tātad burbulis šķirot bija pirmā, kur mēs veida kūsāja lielāko personu visu ceļu pa labi, ko pārnešana cilvēkus pairwise. Tad mums bija ko mēs saucam atlases veida kur es nedaudz vairāk apzināti tur meklē pa sarakstu, izvēloties mazāko skaitu atkal un atkal un atkal, loģisks rezultāts, kas ir tas, ka saraksts ir beidzot sakārtoti. Tad trešais, es ievietota cilvēkus savā piemērotā vietā, un mums bija ļoti izdomāts piemēru, ka sarakstā jau bija sakārtots, bet tas bija, lai nosūtītu ziņu, ka ienesto kārtot s gadījumā, Jūs varat saņemt laimīgs. Ja skaitļi ir jau sakārtoti, tas ir tikai gatavojas pieņemt jums n pasākumus, lai iegūtu tik daudz, tā atlases veida tu esi mazliet vairāk tuneļa redze un jums nav kādreiz saprast, ka saraksts ir jau sakārtots. Tātad, pieņemsim redzēt burbuli veida darbībā šeit. Šajā piemērā, mēs esam par to, lai redzētu vertikālas joslas , kuru augstums skaitļu, lai mēs varētu sakārtot no iztēloties šķirošanas notikt. Jo mazāks ir josla, jo mazāks skaits, jo lielāka ir josla, jo lielāks skaits. 

Un mēs spēlēt šajā noklusējuma ātrumu. Tas notiek, lai pārvietotu nedaudz ātri, lai tagad, bet sarkanā ir tas, ko rāda 2 bāri ko salīdzina blakus. Un, ja jums skatīties cieši, kas notiek, ir tas, ka, ja bars ir bojātas, mazākais viens izpaužas pārvietot pa kreisi, lielāku vienu pa labi, un tad jūs saglabāt padziļinot. Tātad, ja mēs atkal un atkal, ievērosiet, ka vismazākais stieņi gatavojas glabāt inching savu ceļu pa kreisi un lielākie bāri gatavojas glabāt inching savu ceļu pa labi. Un tiešām, mēs sākam redzēt modeli visu ceļu uz labajā pusē tāpat kā mēs redzējām 8 un tad līdz 7 beidzot burbuļošana līdz tālākajā galā mūsu cilvēku sarakstā. Tātad tas būs ļoti ātri iegūt mazliet garlaicīgs, tāpēc ļaujiet man apstāties tas uz brīdi. Ļaujiet man mainīt ātrumu, kas ir daudz ātrāk. Es neesmu mainot algoritmu, es esmu tikai padarot animācijas notikt ātrāk. Vēl burbulis kārtot, pats algoritms, bet tagad jūs varat redzēt daudz ātrāk nekā mūsu verbālās demonstrāciju ka lielākie elementi ir patiešām burbuļo uz augšu. 

Kā malā, šie maz kvadrātu apakšējā kreisajā un apakšējā labajā ir tikai maz atgādinājumus par to, cik daudz salīdzinājumi jūs darāt. Bet tagad, mēs varam koncentrēties uz piramīdas, kas ir ņemot formu, un tur tas notiek. Mazākais elements ir pa kreisi, lielākā par tiesībām, un viss pārējais pa vidu. Tagad tā vietā to apskatīt atlases veida. Es iešu uz priekšu un hit Stop. Mēs ejam, lai saņemtu jaunu izlases kopumu bāriem. Atlases kārtot, atsaukšana, iet cauri sarakstam atkal un atkal un atkal, noplūkšanas veic mazāko elementu. Tātad, šeit ir izvēle veida. Izskatās, tur ir mazāk darba notiek tagad, jo mēs esam ne salīdzinot pairwise bet mēs esam tikai veida ķiršu picking vismazākās elementus no labās uz kreiso pusi. Tas bija ļoti maz laika, tāpēc tur ir auglīgs jau. Tikai tāpēc, ka algoritms ir teikt, lai ņemtu n kvadrātā laiku, tāpat burbulis kārtot un tāpat atlases veida, tie ir patiešām vissliktākie gaitas reizes. Piemēram, ja, teiksim, atlases kārtot, Es tiešām esmu izvēloties mazāko personu un liekot viņam šeit, tad es esmu dara to vēlreiz, tad es esmu dara to vēlreiz, bet tur bija neliela optimizācija es varētu darīt. 

Tiklīdz es pārcēlos numuru 1 šeit - Sammy šajā gadījumā - Ko es jādara ar viņu pēc tam? >> [Students] viņu atstāt. Atstāt viņu, vai ne? Nekas. Man nav nepieciešams, lai kādreiz runāt ar Sammy vēlreiz, jo, ja man bija izvēlēts mazākais elements un nodot viņu šeit, kāpēc tērēt laiku iet uz beigām visu manu sarakstu? Par nākamo atkārtojuma ļaujiet man faktiski pārvietoties tikai ar 2 numuru, tikai 3 numuru. Tātad patiesībā, man nebija darīt n lietas n reizes. Man bija darīt n lietas, tad n - 1 lietām, tad n - 2 lietas, tad n - 3 lietas, tad n - 4, dot, dot, dot. Mums ir mazliet ģeometriskā progresijā, kas nozīmē tikai to, jūs summējot pakāpeniski mazāku skaitu. Ne n + n + n + n bet n + 7 + 6 + 5 + 4 + 3 + 2 + 1. Un ko tas vispār darbojas, lai būtu - Es esmu gatavojas izjaukt manu kuģa šeit tikai brīdi - kas notiek uz darbu, lai būtu kaut kas līdzīgs n (n - 1) / 2 ja mēs tikai veida paskatās atpakaļ uz matemātikas grāmatas, kur jums ir visas apkrāptu loksnes formulas. Ja jūs vienkārši pievienojot kaut n n - 1 + n - 2, tā darbojas, lai būtu kaut kas līdzīgs šim. Un, ja mēs tikai veida reizināt šo out, kas ir n rūtiņām mīnus N / 2. Es tur saka n rūtiņām, lai gan, un tas ir tāpēc, ka man bija veida ņemot garīgo īsceļu jo patiesībā, n kvadrātā mīnus n dalīts ar 2 ir patiešām taisnība skaits soļiem ka līdzīgi atlases veida algoritms būtu nepieciešams, ja mēs patiešām saskaitījām visus šos salīdzinājumus un visu maz aizņemts darbā mēs darām. Bet godīgi sakot, kad n izpaužas būt, piemēram, miljonu vai miljardu, kurš heck rūpējas ja jūs darāt miljardu brusas mīnus miljardu dalīts ar 2? Miljardus kvadrātā ir milzīgs skaits. Jūs varat veikt vēl miljardi off no tā ar - n. Tas nav tik liels galā. Tāpēc jo lielāks skaitļi saņemt, mazāk svarīgas šīs zemākas sakārtotu termini ir. Who cares, ja jūs sadalīt pa 2, ja jūs runājat par quadrillions skaita pakāpieni? 

Tātad kopumā, datorzinātnieku mēdz mest prom visu, bet lielāko termiņu, un mēs tikko veida vienkāršotu pasauli un teikt, ka algoritms paņēma aptuveni n rūtiņām soļus. Tas ir darbības laiks algoritma. Tātad mēs būsim atpakaļ uz šo tikai brīdi ar dažiem konkrētiem piemēriem, bet tagad, ka ir sava veida intuitīvo motivācijas aiz tikai vienkāršotu mūsu pasauli un runājot par svarīgākajiem nosacījumiem, nevis iegūt visus šos iedomātā formulām. Tā, ka bija atlase šķirot, un mēs saņēmām mazliet laimīgs tur. Apskatīsim ievietošanas šķirot. Ļaujiet man iet uz priekšu un sākt šo vienu, kā labi. Tagad paziņojums modelis, ka notiek ir nedaudz atšķirīgs, un mēs sākām ar izlases numurus, bet, ja mēs tiešām saskaitīt pasākumu skaitu sliktākajā gadījumā, ja sarakstā sākās pilnīgi pareizā secībā, mēs tikai veikt n pasākumus, lai realizētu tik daudz. 

Bet ja sarakstā ir faktiski atpakaļ - piemēram, šajā gadījumā šeit - tad ievērosiet mēs faktiski ir jādara daudz vairāk darbu šajā lietā. Un tas būtu sava veida justies jums patīk šī ir veida strādā smagāk lai saņemtu šos mazākus elementus pa kreisi, un tas ir tāpēc, ka mēs saņēmām nelaimīgs. Saraksts tika sakārtoti nejauši atpakaļgaitā. Savukārt, ar ienesto kārtot, ja mēs atdarinātu to, ko mēs izdarījām ar mūsu cilvēkiem šeit , sākot ar šķiroto ikvienam un tad sākt, tas ir diezgan labs algoritms, vai ne? Tas jau, patiesībā, sakārtoti. Tāpēc pieņemsim mēģināt apkopot tieši cik daudz laika šīs lietas ir ņemot mums ieviešot tikai par žargonu bitu vai nošu, kas ir faktiski daudz vienkāršāk nekā fanciness veida liecina. Šī lieta šeit, šo lielo O uz ekrāna, ir tas, ko dators zinātnieks parasti izmanto aprakstīt sliktāko darbības laiku algoritms. 

Atkal, sliktākajā gadījumā, tas ir pilnīgi atkarīga no konteksta. Ko mēs saprotam ar sliktākajā gadījumā pilnīgi mainās atkarībā no problēmas, mēs runājam. Bet attiecībā uz šķirošanu, kas ir sliktākais iespējamais scenārijs? Viss ir atpakaļ, jo tā vienkārši jūtas kā tas nozīmē, ka daudz darba, lai mums. Es esmu jotted leju dažas no algoritmiem, ka mēs esam redzējuši līdz šim: lineārā meklēšana, binārā meklēšana tāpat ar telefonu grāmatā, vai papīra gabaliņi, tad burbulis kārtot, atlase kārtot un ievietošanas kārtot kā mēs redzējām ar mūsu cilvēkiem, un tad vēl 1, kas ir beidzot būs sauc apvienot šķirot. Tātad lineārā meklēšanai sliktākajā gadījumā, cik soļus tas veic, lai atrastu numuru 7 ja ir n durvis piemēram Sean saskārusies? >> [Students] N. N. Tāpēc mēs esam gatavojas rakstīt Big O n. Es esmu tikai gatavojas aizpildīt dažas sagataves. Tas ir tikai režģis sagataves. Bet labākajā gadījumā ar lineāro meklēšanā, 7 varētu būt pašā sākumā saraksta, un Sean varētu būt sākuši meklē sākumā sarakstā. Tātad, ja jūs izmantojat lineāro meklēšanu un tikai pārbaudīt kreisās uz labo vai varbūt no labās uz kreiso - viņi ekvivalents - labākajā gadījumā cik soļus varētu lineāra meklēšanu, piemēram Šona algoritmu, ņem? Tikai 1 solis. 

Tāpēc es esmu gatavojas teikt, ka ir omega apzīmējumu. Tas ir tikai kapitāla omega. Omega ir tikai seksīgs veids, kā pateikt labākajā gadījumā darba laika. Tātad labākajā gadījumā darbības laiks ir viens solis vai pastāvīga soļu skaitu - 1 Šajā gadījumā - bet sliktākajā gadījumā, Big O, tas tiešām ir n soļi. Un šo vienu šeit, Theta, mēs faktiski nav skatīsies tieši tagad. Tas nav attiecināms uz šo konkrēto piemēru. Bet tagad pamēģināsim bināro meklēšanu. Sliktākajā gadījumā ar bināro meklēšanu, cik soļus ir tas gatavojas veikt, lai atrastu numuru 7 vai kāds mēs meklējam? >> [Students] log n. Joprojām gatavojas veikt log n jo tāpat kā Alekss ieguva nelaimīgs kad mēs tiešām strādāja ar problēmu metodiski un viņa nav atrast numuru 7 līdz pēdējam durvīm viņa paskatījās, kaut gan, taisnīgumu, viņa dabūja mest prom dažas durvis pa ceļu, bināro meklēšanas sliktākajā gadījumā ir darbības laiku log n. Un atkal, kas runā uz šo dalot un iekarošana. Bet ko par labākajā gadījumā? Un Alex patiešām pieredzējis, ka labākajā gadījumā taisnība, kad viņa ieradās uz skatuves. Cik soļus bija kas ieņems binārā meklēt? >> [Students] 1. 1, tikai tāpēc, ka viņa ieguva laimīgs. Bet tas ir labi, jo omega attiecas uz labāko scenāriju, labākajā gadījumā ieejas, pat ja tas ir tikai izlases mēms luck. 

Tagad, tas arī mēs esam gatavojas tikko veida atstāt tukšu tagad. Kā par tagad burbulis šķirot? Sliktākajā gadījumā ar burbulis šķirot, visi ir apgrieztā secībā, tāpēc mums ir jādara daudz burbuļošana. Bet cik soļus ir tas, ka gatavojas veikt sliktākajā gadījumā? >> [Students] N kvadrātā. Tas bija n kvadrātā, jo, ja jūs domājat par to, Ja saraksts ir pilnīgi atpakaļ - 8 ir vairāk nekā šeit, 1 ir vairāk nekā šeit - kā lieta sāk burbuļot, skaits 8 gatavojas pārcelties šādā veidā, šādā veidā, Tādā veidā, šādā veidā, bet kur ir par 7 sliktākajā gadījumā? Te viņa vēl joprojām ir tur. Tāpēc mums tas ir jādara atkal un atkal. Un tur mēs n soļi, tad n - 1 pakāpieni, tad n - 2 pakāpieni. Un, ja jūs ņemt manu vārdu par to - ka, ja jūs veida reizināt to ārā, tas rupji n brusas, kas beigās ar dažiem citiem noteikumiem, kas mēs vienkārši ignorēt tagad - tad sliktākajā gadījumā burbulis šķirot ir n rūtiņām, sniegt vai pieņemt. Bet ko par labākajā gadījumā ar burbulis šķirot? Kas ir labākais scenārijs? Visi numuri ir sakārtoti jau. Un kāda bija heiristiskā es, triks es, lai saprastu, ka man bija darīts nekādu darbu un tādējādi varētu apturēt agri? [Students] Pārbaudīt to vienu reizi. >> Pārbaudiet to vienu reizi. Bet ko bija daru pa ceļu? Man bija sekot tam, cik daudz mijmaiņa es. Un es sapratu, ja man nav ieskaitīts nevienu mijmaiņa par manu pirkstiem, tad es esmu darījusi nav darba. Es noteikti nevajadzētu mēģināt darīt nekādu darbu atkal, lai es varētu vienkārši apstāties. 

Tātad labākajā gadījumā uz burbuļa veida kad saraksts jau ir sakārtots, Ko jūs teiktu, ka omega notācija ir, labākajā gadījumā darba laika? Tas ir tikai n. Mums ir darīt kādu darbu, bet mums jādara tikai 1 pastaiga vērts darbu. Un arī šeit es esmu gatavojas atstāt šo daļu tukšu. Un tagad izvēle kārtot. Atlases kārtot bija mani noplūkšanas mazāko persona atkal un atkal. Un ko mēs sakām darbības laiks, kas bija? Tas bija n rūtiņām sliktākajā gadījumā. Un diemžēl, labākajā gadījumā tas ir arī n kvadrātā jo man nav tāda veida visuzinošajam Ņemot vērā visā pasaulē; Es tikai zinu, pēc pilna atkārtojuma ka es esmu patiešām konstatēja mazāko personu. Tātad izvēle veida veida sucks ziņā, bet otrādi ir tas veida intuitīvi. Tas ir diezgan viegli kodu augšu, jo viss, kas jums jādara, ir uzrakstīt pāris ligzdotu uz cilpas, parasti, kas iet cauri meklē mazāko elementu un tad liek mazāko elementu, ja tā pieder pie saraksta beigās. Tātad arī šeit būs kompromiss. Laika daudzums, kas nepieciešams, lai jūs domāt un faktiski attīstīt kaut ko rakstot kodu varētu ļoti labi aizņemt vairāk laika, ja jūs vēlaties labāku algoritmu un ātrāku veiktspēju. 

Bet, ja jūs patiešām tikai veida kodu kaut up ātri un netīrās un tikai veida veikt stupidest iespējamo ideju jūs varat iedomāties, kas varētu veikt jums dažas minūtes, lai kodu, bet ar lielu datu kopu Jūsu algoritms varētu aizņemt laiku, lai palaistu. Un pat es absolvents skolā būtu reizēm šiem kompromisiem. Tas būtu 03:00, es centos analizēt kādu ļoti lielu datu kopu saistīti ar drošības pētniecības es daru, un tas bija vai nu pavadīt 5 minūtes tweaking savu programmu, lai analizētu datus un iet gulēt vai pavadīt 8 stundas iegūt to tikai tiesības, lai tā darbojas uzreiz, nevis iet gulēt. Un tāpēc arī tur tas ir sava veida apzināts lēmums. Mazāk izstrādes laiku, vairāk miega. Atskatoties pagātnē, es, iespējams, nedrīkst veicināt ka ja mērķis šeit ir, lai optimizētu kvalitāti no koda, bet ka pārāk reālajā pasaulē ir ļoti saprātīgs kompromiss. Mazāk laika, mazāk sniegums vai otrādi. Tātad šeit mēs beidzot ir iespēja runāt par theta. Theta notācija ir kaut datorzinātnieku var audzināt sarunā kad liels O un omega notikt ir tas pats. Jums teikt Theta patiešām nosūtītu ziņu, ka šis ir sava veida saspringts saistoši. Nav svarīgi, vai scenārijs ir labi vai slikti, tas ir n rūtiņām. Tātad, tas vienkārši nav nozīmes šiem stāstiem šeit. Ievietošanas kārtošanas ir pēdējais mēs paskatījās, kur man bija tikai ievietojot ikvienu uz pareizā vietā. Labākajā gadījumā, kāda bija darba laiks ievietošanas veida, kā mēs redzējām to šeit? [Students] labākajā gadījumā? >> Labākā gadījumā. 

Tas tika n jo labākajā gadījumā ikvienam sakārtoti, un Sammy un neviens cits īsti bija pārvietoties vispār. Viņi bija jau savā īstajā vietā. Tātad ievietošanas šķirot labākajā gadījumā ir, šajā gadījumā, n. Bet sliktākajā gadījumā tas ir sava veida n rūtiņām. Kāpēc? Ja mans saraksts cilvēkam ir apgrieztā kārtībā, Es vispirms sākt ar numuru 8, un es ievietot viņam vai viņai uz pareizā stāvoklī, kas ir šeit. Es veida pāreja uz pusi. Šie puiši ir nešķirotu, ka viņš vai viņa ir sakārtots. Bet tagad es notikt, lai atrastu, kurš nākamais? >> [Students] 7. 7 sliktākajā gadījumā, jo tas ir apgrieztā secībā. 

Tātad šeit ir 7. Kur tas 7 pieder? Noteikti aiz manis. Bet tagad 7 patiesībā pieder nevis uzreiz aiz manis, bet aiz numuru 8, tāpēc man ir jāsaka: "Piedodiet, numuru 8, jūs varat lūdzu pārvietot šo ceļu ", Lai padarītu telpu 7?" Tagad man rodas 6. "Ak, atvainojiet mani, skaits 8 un numuru 7, jūs varat pārvietot, lai padarītu telpu 6?" Tātad citiem vārdiem sakot, ar ievietošanas šķirot, lai gan es neesmu dara daudz kustību, aiz manis cilvēki dara daudz vairāk darba, un tas ir nokļuvis uz izmaksu kāds laiks. Tas notiek uz izmaksu datora laiku. Tātad gadījumā, ja ievietošanas veida mēs joprojām cieš. Ja jūs sākat saskaitot kopējo skaitu soļus, mēs galu galā hitting rupji N brusas jo šie puiši ir nepieciešams, lai padarītu telpu cilvēka jāievieto atpakaļ šajā sarakstā. Un tāpēc šajā gadījumā Theta ir vienkārši nav piemērojams ar konkrētu stāstu pie rokas. Tas ir viss jauki un labi. Mums ir šie 3 dažādas iespējas runāt par braukšanas laiku. Bet ko tas patiesībā nozīmē reālā izteiksmē, ja mēs faktiski cenšamies koda līdz algoritmu? 

Ļaujiet man ieteikt, ka tur pat labāk algoritms, kas tur ka pati ir daži kompromisi. Mēs ejam, lai izsauktu to apvienot veida, un tas ir sava veida šo burvju algoritma kas vienkārši darbojas ātrāk kaut kā, un tas ir tik viegli izteikt, vismaz pseudocode. Šīs algoritma sapludināšanas veida ieviešana būs šādi. Kad jūs esat dota n elementiem - N ciparus n cilvēki, neatkarīgi - Vispirms tur ir veselība pārbaudītu. Ja n ir mazāks par 2, apvienot šķirot vienkārši apstājas. Tas atgriežas, lai runāt. Kāpēc jūs pārtraukt, ja n ir mazāks nekā 2? >> [Dzirdams studentu reaģēšanas] Tiesības. Un atkal, n nav numurs sarakstā, n ir lielums sarakstā. Ja n ir mazāks par 2, tas nozīmē, ka jūsu saraksts ir vai nu 1, kur jūs acīmredzot sakārtoti, ja tas ir 1 numurs, vai 0, un šajā gadījumā nekas, lai sakārtotu, tāpēc mums ir nepieciešams šāda veida gadījumu. Ja saraksts ir tik īss, ka tur ir tikai nekas jādara, burtiski neko nedara. Atgriezties. Pretējā kārtot kreiso pusi no elementiem, tad šķirot labo pusi elementiem, pēc tam apvienot 2 sakārtoti pusītes. 

Šāda veida šķiet maz blēdis kuru es esmu jautā, kā kārtot elementus un tu man saki, "kārtot kreiso pusi, šķirot labo pusi." Es, piemēram, "viss kārtībā Kā jūs kārtot kreiso pusi?". "Kārtošana kreiso pusi kreisajā pusē, šķirot labo pusi kreisajā pusē, un tad jādara." Tu esi veida cikliski definēt, ko tas nozīmē, lai kārtotu, bet izrādās, ka patiesībā izcili šajā lietā. Tas nav patiesi šo apburto loku, kas nekad nebeidzas jo tas beidzas, kad? >> [Students] Kad jūs sasniedzat 1 lieta. Kad jūs sasniedzat 1 lieta. Tātad, pat ja jūs varētu sākt ar 8 cilvēkiem, un es saku, "kārtot kreiso pusi šiem cilvēkiem, šie 4 cilvēki, "tad es saku:" Kā jūs kārtot kreiso pusi? " "Nu, šķirot 2 cilvēki šeit." Un tad jūs, piemēram, "Labi, labi." "Kā jūs kārtot kreiso pusi no tiem cilvēkiem?" "Vienkārši sakārtot šo 1 personai šeit." Kas izcili atklāsme tagad? Man ir, lai sakārtotu 1 personu. Darīts. Man nav darīt jebkuru darbu. Bet tagad man ir, lai sakārtotu šo personu, bet viņi viens cilvēks, neko darīt. 

Tātad burvju acīmredzot ir šajā Trešais solis: apvienot sakārtoti pusītes. Tāpēc apvienot kārtot ņem šo izcili ieskatu, ka, ja jūs pauze liela problēma leju uz 2 mazākos, identiski lieluma problēmas un tad tikai veida līmi mazākiem risinājumi kopā beigās, Es ierosinu, ka mēs varam darīt daudz, daudz labāk [pieskaroties skaņu] nekā jebkura atlases veida vai ievietošanas šķirot. Es esmu faktiski ignorējot ka pusstundu, bet es tiešām nezinu, kas notiek ārpus šodien. [Whirring skaņa] [smiekli] Tātad, pieņemsim redzēt, ja mēs varam redzēt to ar nelielu palīdzību no mūsu drauga Rob Bowden. Ir 2 lieli soļi procesā sapludināšanas kārtošanas. Pirmkārt, nepārtraukti sadalīt sarakstu tases uz pusēm līdz mums ir ķekars sarakstos tikai ar 1 glāzi tiem. Neuztraucieties, ja sarakstā ir nepāra skaits un jūs nevarat veikt pilnīgi tīru griezumu starp tiem. Tikai patvaļīgi izvēlēties, kuras sarakstā iekļaut papildu tasi iekšā Tāpēc pieņemsim sadalīt šos sarakstus. Tagad mums ir 2 saraksti. Tagad mums ir 4 sarakstus. Tagad mums ir 8 saraksti ar vienu tasi katrā sarakstā. Tā ka tas uz 1 soli. Par soli 2 Mēs vairākkārt apvienot pārus saraksti, izmantojot sapludināšanas algoritmu mēs uzzinājām pirms tam. Apvienojot 108 un 15 mēs galu galā ar sarakstu 15, 108. Apvienojot 50 un 4 Mēs galu galā ar 4, 50. Apvienojot 8 un 42 mēs galu galā ar 8, 42. Un apvienojot 23 un 16 Mēs galu galā ar 16, 23. Tagad visi mūsu saraksti ir 2 izmēru. Ievērojiet, ka katrā no 4 sarakstiem ir sakārtoti, lai mēs varētu sākt apvienojot pārus sarakstos atkal. Apvienojot 15 un 108 un 4 un 50 mēs vispirms veic 4, tad 15, tad 50, tad 108. Apvienojas 8, 42 un 16, 23, mēs vispirms veic 8, tad 16, tad 23, tad 42. Tāpēc tagad mums ir tikai 2 saraksti 4 izmēra, no kuriem katrs ir sakārtots. Tāpēc tagad mēs apvienot šos 2 sarakstus. Vispirms mēs ņemtu 4, tad mēs ņemtu 8, tad mēs ņemtu 15 un 16 un 23 un 42 un 50 un 108. Un mēs esam darīts. Mums tagad ir sakārtoti sarakstu. 

Rob bija veida gūst priekšrocības, ko mēs to vēl nav izdarījušas. Tika ierosināts, bet mēs faktiski nav darīt to. Viņš dara kaut ko fiziski ar kausiem, kas liecina, Viņš bija izdevumu dažas resurss bez laika. >> [Students] Kosmosa. >> Tas bija telpa. Tas, ka viņš bija šāda veida bi līmeņa galda, kur viņš bija telpa līdz šeit un kosmosa noteikti šeit bija faktiski nozīmē to, ka viņš, izmantojot divreiz tik daudz vietas kā jebkurš no mūsu algoritmu, kas līdz šim - ievietošana kārtot, burbulis šķirot, vai atlase kārtot - bet viņš bija piesaistot šo papildu iespējas veida pārvietotu lietas uz priekšu un atpakaļ vienlaikus saglabājot lietas kārtībā. Un pat ja tā uzskata, tāpat kā mēs saņēmām uz sakārtoti sarakstu, ka jutos kā tas bija, bet. Patiesībā tas, ko Robs bija darīt bija tieši šis algoritms. Viņš pirmo reizi paņēma problēmu izmērs N, sadalīts to par kreiso pusi un labo pusi. Tas ir, kad viņš pārcēlās kausus. Tad viņš atkārtoja šo procesu. Viņš sadalīta 4 savos 2 komplekti 2 nekā šeit un vairāk nekā šeit. Tad viņš atkārtoja šo procesu un sadala 2 komplekti 1 katram no šiem dažādu tases 2. Un tas ir, ja izcili iespēja rodas. Tajā brīdī stāstā, Robs bija 8 sarakstus apjomu 1, kuras visas sakārtoti jau. 

Tātad tad ko viņš turpinātu to darīt? Pairwise viņš bija šīs sakārtoti sarakstu un šo sakārtoti sarakstu un apvienoja tos. Tad viņš paņēma šo vienu un apvienoja tos, tad šo vienu un apvienoja tos, tad tas viens un apvienoja tos. Un tad ko viņš dara tālāk? Pēc tam viņš atkal apvienojās lielākos sarakstus un pēc tam atkal apvienojās lielākos sarakstus. Un, ja jūs domājat par šo vienkārši intuitīvi tagad, Ko viņš īsti dara? Viņš bija dalot šo problēmu uz pusi, uz pusēm, uz pusēm, uz pusi Lai saņemtu šo super mazos sarakstus. Tad viņš bija veida apvienojot dubultā, dubultā, dubultā, dubultā. Tāpēc viņš dara divreiz tik daudz strādāt, kā mēs esam redzējuši līdz šim ar jebko, kas ietver skaldi un valdi, bet nav liels darījumu. Divreiz tik daudz darba, nav tik liels darījumu. Tas ir tikai nemainīgs faktors. Un līdzīgi mūsu aritmētisko izteiksmi pirms, es esmu tikai gatavojas izsvītrot konstante faktori tāpat kā 2 reizes. Who cares? Ja tas ir 2 miljardiem reizes 2, tas joprojām daudz pasākumus. Tātad šī apvienošana solis šķiet galvenais ieskats. Apskatīsim šo tikai skaitliski pirms - Ak, tas nav jāturpina vēl. Apskatīsim šo skaitliski tikai reāli redzēt, kā tas spēlē out. Tas ir galvenokārt tikai nedaudz nabaga vīra animācijas. Pieņemsim ierosināt šo. Darbības laiks sapludināšanas veida - mums vienkārši vajag veidu, kā runāt par to. Tas nav matemātika, tas ir tikai sava veida īsu veidā izteikt sevi. Tātad T attēlo laiku un n ir ko? >> [Students] lielums no - 

[Malan] problēmas apjomu, cilvēku skaits. Tāpēc es esmu apgalvojot, ka darba laiks, lai sakārtotu n cilvēkus būs 0 daudz laika ja n ir mazāks par 2, jo, ja jums ir 1 tasi vai nav krūzes, jums nekas nav jākārto. Bet vispār, es esmu gatavojas ierosināt darba laiks, lai sakārtotu n elementiem būs laiks, kas nepieciešams, lai sakārtotu kreiso pusi plus labo pusi plus - kas tas ir papildu + N? >> [Students] sapludināšana kārtošanas. [Malan] Tas patiesībā apvienojas, jo, ja jums ir n / 2 elementi šeit un jums ir n / 2 elementus šeit, cik daudz laika tas veic, lai tos apvienot? Tāpat kā Rob, jums ir apzagt šo vienu vairāk nekā šeit, varbūt iekšas nekā šeit, apzagt nekā šeit, raut nekā šeit, raut nekā šeit. Jums ir pieskarties viens no kausiem reizi. Un, ja tur ir 4 glāzes plus 4 tases, kas ir 8 glāzes vai vispārīgāk, 8 n tases. Tāpēc apvienojas solis mēs varam izteikt kā n, un kas burtiski ietver vairākas reizes Rob fiziski aizskāris viens no tiem putuplasta tases. Tāpēc pieņemsim tagad darīt patvaļīgu piemēru. Ja tur ir 16 kausi, kas ir darbības laiks šķirošanai, izmantojot Rob algoritms, 16 tases? Tas ir 2 reizes laika daudzums, kas nepieciešams, lai kārtotu 8 glāzes jo mums ir 8 glāzes šeit, 8 glāzes šeit. Es nezinu, cik ilgi tas notiek, tāpēc mēs vispārinot to kā T uz šo brīdi. Kurš zina, kas tas ir? Bet tagad es varu veida rekursīvi vai atkārtoti uzdot to pašu jautājumu. Cik daudz laika tas veic, lai sakārtotu 8 glāzes? 8 glāzes es esmu gatavojas teikt aizņem laiku, kas nepieciešams, lai kārtotu 4 tases plus 4 glāzes, tam apvienojot tos kopā. Fine. Mēs esam nokļūst ciklā jau. Cik ilgs laiks nepieciešams, lai kārtotu 4 tases? Laiks, kas nepieciešams, lai sakārtotu 4 tases ir 2 glāzes plus 2 tases šķirošanas plus apvienošanās procesu. Fine. Cik ilgs laiks nepieciešams, lai sakārtotu 2 tases? 2 glāzes ir laika daudzums, kas nepieciešams, lai kārtotu 1 tase plus laiks, kas nepieciešams, lai sakārtotu vēl vienu tasi plus laika daudzums, kas nepieciešams apvienoties, kas ir tikai 2. 

Fine. Pēdējais jautājums. Cik ilgs laiks nepieciešams, lai kārtotu 1 tasi? Šeit ir bāzes scenārijs, ka mēs prognozēts mēs gribētu hit agrāk. Fakts, ka tā neuzņemas nekādu darbu nekāda lai sakārtotu mazāko no problēmām nozīmē, ka tagad, kārtot pamatskolas stilu, mēs varam tikai iet sākt tapām šos skaitļus atpakaļ iekšā Mēs tagad zinām, kas T 1 ir, lai es varētu plug 0 par T 1. Tas dod man atbildi uz T 2, kas es pēc tam var plug augstāk. Tas dod man T no 4, ko es var spraudni augstāk. Tas dod man T no 8, ko es var spraudni augstāk. Un, ja es tiešām, ka math, pieslēdzot šīm atbildēm, Es pēc tam saņemt T gada 16 ir 64. Un ko 64 pārstāv? Ja T ir 16, jā, tas ir 16 reizes 4. Tāpēc es apgalvo, ka šobrīd darbojas laiks šo lietu sauc apvienot šķirot - un tas būs Fanciest no tiem mēs esam redzējuši līdz šim - gatavojas saukt n log n jo cik reizes var apzagt sadalīt veselu ķekars tases uz pusēm? Log n. Tas ir tāpat kā telefona grāmatu, piemēram, tas ir tāds pats kā sevis skaitīšanas piemērs. 

Cik reizes jūs varat sadalīt kaut pusi? Tomēr, tur ir tas apvienojas solis. Jums varētu būt sadalīt kausus uz pusi atkal un atkal un atkal, bet katru reizi, kad jūs nāksies apvienot. Un mēs teicām agrāk, ka apvienošanās n tases aizņem n pasākumus jo jums ir raut ārā kausu, raut ārā kausu, un jums ir pieskarties katru kauss vienreiz, tāpat kā Rob izdarīja. Tātad, ja mēs darām kaut žurnālu n reizes, un mēs darām n lietas, par katru no šiem atkārtojumiem, Katrs no šiem halvings, mums ir n reizes log n. Tātad, ja mēs plug 16 Šajā piemērā, 16 reizes log 16 - nav jāuztraucas par to, kāpēc tas ir gadījums, lai tagad, jo man nav sagatavots bāzi - bet žurnāls 16 2 bāzes ir 4, 16 4 reizes ir 64. Bet tieši pretēji, ja mēs būtu izmantoti burbuļu šķirot vai selekcijas kārtošanas vai ievietošanas šķirot ar 16 numuriem, kāda būtu darbības laiks ir bijis, ja n ir 16? Tas būtu 16 brusas, kas ir 256, kas pat tad, ja jums nav gluži sekoja visu math, 256 ir lielāks nekā 64. Tas ir patiešām maģisks takeaway šeit. Un saprast, ka darbs caur šo mazākās piemērus, kā jūs uz PSET padara to visu daudz vairāk intuitīvi. Bet ko tas īsti nozīmē ziņā noskaņu Šis algoritms ir šāds: Ja mēs faktiski apskatīt sapludināšanas kārtot šeit - ļaujiet man vilkt to uz augšu šajā logā šeit - Tas ir nedaudz atšķirīgs piemērs, kurā mēs visi esam 3 no šiem algoritmiem - burbulis, atlase, un apvienot - tikai blakus. 

Viņi visi esam sākuši ar izlases bāri, un tas ir labi. Neviens nav būtiska priekšrocība pār otru. Es esmu gatavojas uz brīdi uz katra no šīm animācijas - Start, Start, Start - tik ātri, kā es varu tā, ka, rupji, viņi visi sāk tajā pašā laikā, un pieņemsim uzskata, ka burbulis kārtot s sliktāk lieta darbības laiks ir tas, ko? >> [Students] N kvadrātā. N brusas. Atlases kārtot s sliktākajā gadījumā darba laika ir? N brusas. Un sapludināšanas kārtošanas ir acīmredzami - pat ja Jums nav gluži ievērot visus math tagad, tas būs kļuvis daudz vairāk intuitīvi laika gaitā - ir, mums apgalvo, n reizes log n. Un tāpēc žurnālu n ir stingri mazāks nekā n reizi mums ir lielas numurus, n reizes žurnāls n ir mazāks nekā n reizes n vai n rūtiņām. Tātad, ko tas jūtas, lai faktiski būtu labāks algoritms ziņā darba laika, n reizes log n atšķirībā n kvadrātā? Šeit mēs iet. Klikšķis, klikšķis, klikšķis. 

Tas, ko tas nozīmē, lai izmantotu kaut ko līdzīgu sapludināšanas kārtošanas. Mums ir brīdis. Paskatīsimies, kas notiek šeit. [Chuckles] Kuru nauda ir burbulis šķirot? Tas drīzāk ir atkarīgs no ieejas dažreiz. Pieņemsim redzēt. Come on. Tā uzskata, piemēram, viņš tuvojas. >> [Students] Go, burbulis šķirot! [Studenti murmuring] [Malan] Jā, jā. [Studenti murmuring] Iet, iet, iet! [Visi gavilēja] [aplausi] Tāpēc tagad ar 1 pēdējo, galīgajā demo, ja tas nedaudz grūts, lai wrap savas domas ap math vai sava veida vizualizācijas tur, jūs faktiski var dzirdēt ātrumiem dažādu algoritmu atšķirīgi. Tas ir animācija kāds, kas tiešām saista izklausās ar pārnešana procesu un bāriem augstums. Kā mēs redzēsim šeit, tur ir vēl dažas šķirošanas algoritmus, kas tur, ka ļaudīm ir doma. Šis pirmais būs ievietošanas šķirot, un tas lidot caur un jums skaņas izjūtu, kā šie dažādu algoritmu darbu. Šeit ir ievietošanas šķirot. [Elektroniskās skaņas] [Malan] burbulis šķirot. [Ātrāk elektroniskās skaņas] [Malan] Atlase kārtošanas. [Ātrāk elektroniskās skaņas] [Malan] sapludināšana kārtošanas. [Elektroniskās skaņas] [Skaņas palēnina] [smiekli] [Malan] Rūķis kārtošanas. [Elektroniskās skaņas] 

Tas ir CS50. Mēs redzēt jūs nākamajā nedēļā. [Aplausi un uzmundrinoša] 

[CS50.TV]