SPEAKER: Nu labi, tas ir CS50. Tas ir beigu trīs nedēļas, un, ja jums nav izmantojuši jau, zinu, ka būs pusdienas šo piektdien, kā ierasts, kur Jūs varat baudīt laba saruna un ēdiens Uguns un ledus ar dažiem no CS50 s personāls un klasesbiedru. Dodies uz šo URL šeit. 

Tagad jūs varat atgādināt, vai arī jūs drīz var iepazīties ar, šīs lietas šeit, kas tiek dots beigās semestra daudziem klasēm. Tā sauktais eksāmenu zilas grāmatas, kurās jums rakstīt jūsu atbildes uz eksāmeniem. Tagad man ir šeit 26 tādas zilā grāmatas, par katru no tām ir rakstīts nosaukumu, A caur Z. Un patiesi vārdi ir tik vienkārši, līdz Z. Un viens no mērķi pie rokas šodien būs arī turpmāk, ko mēs sākām pirmdien, kas nav tik daudz meklē kodu, bet tiešām meklē idejas un problēmu risināšanu. Viens no mērķiem, un solījumi šajā kursā ir mācīt jūs domāt vairāk uzmanīgi, vairāk metodiski, un risināt problēmas efektīvāk. Un tiešām, mēs varam darīt, ka patiešām , pat nepieskaroties līnijas kodu. Tāpēc man ir pāris ziloņi šeit šodien, oranžā un zilā krāsā, ja mēs varētu saņemt viens brīvprātīgais, varbūt no tālāk atpakaļ nekā parasti. Kā par turpat, nāk uz leju. Kura mērķis būs līdz palīdzēt plus administrēt šo eksāmenu šeit. Kāds ir tavs vārds? 

AUDITORIJA: Mary Beth. SPEAKER: Mary Beth, nākt uz augšu. Ļaujiet man iegūt mikrofonu šeit jums. Prieks iepazīties. 

AUDITORIJA: Prieks iepazīties. SPEAKER: Nu labi, tāpēc man ir Šeit zila grāmatas līdz Z, un es esmu gatavojas izlikties, ka Man ir viens no skolēniem, un viņi nāk nedaudz nejauši beigās trīs stundu Exam bloku, lai viņi beidzot dažās daļēji izlases kārtība, kā šis. Tagad jūsu uzdevums tikai brīdi notiek to be-- tas ir faktiski, kā viņi saņem griezt beigās klasē, visticamāk. Jūsu darbs tagad būs diezgan vienkārši, lai kārtotu šos zilos grāmatas mums no A līdz Z. 

AUDITORIJA: Ak, tas ir gatavojas veikt uz visiem laikiem. 

SPEAKER: Un mēs skatīties kā jūs to izdarītu, nav spiediena. AUDITORIJA: Nē, nav spiediena vai neko. 

SPEAKER: Un jautri, pieņemsim safasēti taimeri. 

AUDITORIJA: Tik daudz jautrības, tik jautri. 

SPEAKER: Es varu turēt mic jums. Labi, mēs esam tikai dubultojies mūsu ātrumu. Tātad to laiku, ļaujiet man uzdot to, kas ir būs jautājums Mary Beth ir to, kas ir viņa dara, cik ir viņa iet par risināšanas šo? Un patiesībā, iespējams, jums nav kādreiz domājuši par kaut ko tik vienkārši, kā tad, kad jūs izvēlaties līdz 26 grāmatas, piemēram, tas, kam ir dabisks pasūtot uz tiem. Kas ir process ka jūs faktiski izmantot? Vai tas ir diezgan nejauši tikko picking pirmo redzat un ievietojot to savā vietā? Vai jums vispirms pārvietoties rokas apkārt meklē, tad meklē B? Vai jūs to apskatīt No tiem blakus pāris un tikai teikt, pagaidiet minūti, šis nav pareizi, un tad ielieciet pasūtījumu? Mēs jau redzējām pirmdien ka tur ir vairāki veidi kurā mēs varam izdarīt, un tiešām, kā mēs pie beigām šeit Es varētu ņemt vērā varbūt par ko Mary Beth dara. Mums ir daži pāļi šķiet, lielāks par vienu, trīs mazākie. 

AUDITORIJA: Es esmu pasūtot tos kad es atrast divus burtus , ka es zinu, ir kopā secībā, Es viņus kopā tā, ka man nav jāuztraucas par saglabājot līdzi veselu rindu grāmatas. Tas ir tikai, ak, ir pirmais, Man šī kaudze šeit. SPEAKER: Tātad, gandrīz kā puzzle gabalus, ka ir pareizo formu sakrīt ar otru. AUDITORIJA: Diezgan daudz, jā. SPEAKER: OK, lielisks. Un tagad katru no šiem pāļi, ir iespējams, sakārtoti? 

AUDITORIJA: Jā. 

SPEAKER: Labi, izmantojot Z. All labi, apsveicu, jūs to darīja. Jums ir jūsu izvēle. Blue? Nu labi, paldies par to. Tātad Mary Beth nebija ierosināt ko viņas pieeja bija, bet to, kas ir cita pieeja, kā jums varētu iet par šķirošanas šīs lietas? Ko jūs esat darījuši? Ieraksts pārspēt būtu bijis vienu minūti un 50 vai tik sekundes, plus tie, es aizmirsu skaitīt. Ko jūs esat darījuši? Yeah? AUDITORIJA: Veikt kaudze. Sākt no sākuma. Pārbaudiet savus dokumentus. Un, ja top viens ir augstāks nekā, varbūt, tie ir, apakšā viens ir augstāka, tad pāriet tos. 

SPEAKER: Labi, tāpēc sākot augšā un apakšā, un tad strādā savu ceļu ievešana, piemēram, ka, pārnešana viņiem? Labi, tāpēc mazliet līdzīgs garā uz burbulis kārtot, bet izvēloties galējībām nav blakus pāri. Bet īss ir tas, ka tur ir protams ķekars dažādos veidos mēs varētu darīt, un godīgi sakot, es domāju, ka jūs veida pieņēma pāris pieejas, labi? Jūs, kas veida četri Šķirotu pāļi, un Tad faktiski apvienojās kopā. Un tas ir, daresay, cits tehniku ​​vispār. Jums nav pret to, kā vienu lielu kaudzi, Jums sadalīja problēmu četrās kvadrociklu, ja jūs, un tad kaut apvienoti tos beigās. 

Tātad, pieņemsim apsvērt, galu galā, kā gan citādi mēs varētu darīt. Mēs oficiāli jēdzienu burbuļiem kārtošanas pēdējo reizi, un burbulis kārtot atsaukšana bija algoritms, kas mēs vizualizēta ar astoņiem jūsu klasesbiedriem up šeit, šķietami nejauši sakārtoti sākumā. Un mēs pēc tam nolēma pairwise, ja divi elementi ir no rīkojuma, vienkārši mijmaiņas tiem. Tātad četri un divi acīmredzot nedarbojas, tāpēc šie divi klasesbiedru pārgāja pozīcijas. Un tad mēs atkārto ar četriem un sešiem, Pēc tam sešas un astoņas, par katru atkārtojuma, pārvietojas pa labi. 

Tāpēc, astoņi cilvēki, cik pairwise salīdzinājumi man darīt ejot no kreisās uz labo vienu šādu atkārtojuma? Cik salīdzinājumi? Septiņi, labi? Jo, ja tur ir astoņi cilvēki, bet jums ir pāri viņiem un jūs pastāvīgi pārvietojas viens hop pa labi, jūs neesat nāksies astoņi salīdzinājumus, jo jūs nevarat salīdzināt elements pret sevi, vai tas būtu vienkārši bezjēdzīgi, tāpēc jums ir septiņi. Vai biežāk, ja mums ir n cilvēki, mēs do n mīnus 1 salīdzinājumus ar burbulis veida. 

Tātad, pieņemsim apsvērt, tagad, cik labi vai slikts burbulis kārtot patiesībā bija, un mēģiniet dot sev vārdu krājumu ar kuras kritikas algoritmus, piemēram, tas, un drīz mūsu pašu. Tātad pirmā loka caur burbulis kārtot, pirmo reizi Es aizgāju no kreisās uz labo pusi pāri posms, paņēma mani n mīnus 1 salīdzinājumus. Un kas notiek, lai būtu mans mērvienība, labi? Es biju veida runā un pastaigām, nedaudz ātrs, nedaudz lēns, tāpēc skaitot manu numuru sekundes nav īpaši spēcīgi, bet, saskaitot operācijām, ka man pirmdien, Salīdzinot divus cilvēkus, kas jūtas kā jauku mērvienības. 

Tātad n mīnus 1 soļus pirmo reizi, bet tad to, kas notika pēc tam? Kas ir viens otrādi viena caurlaide caur citādi nešķirotiem sarakstā? Ko jūs varat man pastāstīt par elementu kurš bija visu ceļu tur? Yeah? Tas bija lielākais elements, vai ne? Numurs astoņi, kaut gan viņa sākās šeit, katru reizi, kad es salīdzinot viņu pret kaimiņš, viņa tur burbuļo uz labo pusē no saraksta. Un tiešām, tas ir, ja algoritms iegūst savu nosaukumu. 

Tagad ar šo loģiku, cik daudz salīdzinājumi vajag Es veicu uz otro reizi Es veicu šo piespēli no kreisās uz labo pusi? n mīnus 2, vai ne? Tas būtu vienkārši izšķērdēt manu laiku, ja I saglabāt salīdzinot astoņi pret kādu citur, jo mēs jau zinām viņa bija savā vietā. Tā ka ir mazliet optimizācija, tāpēc nākamais pass būs plus n mīnus divi soļi, kur n ir cilvēku skaits. Tagad jūs varat veida ekstrapolēt, pat Ja jūs neesat datorzinātnieks, kā tas beidzas. Beigās šo algoritmu, iespējams tev tikai viens salīdzinājums pa kreisi. Jums ir sava veida noteikt sākums saraksta gadījumā divām un viens ir no rīkojuma un būtu viens un divi, tāpēc šis dibeni veic plus 1 final salīdzinājums. 

Tagad dot, dot, dot veida viļņi, tas ir rokas pie dažas juicier detaļas, bet pieņemsim tikai iet uz priekšu un vienkāršot. Ja jūs atceraties no augstas skola, atklāti sakot, daudzi no jums bija matemātikas grāmatas, kas bija mazliet apkrāptu lapa uz priekšējā vāka, vai aizmugurējais vāciņš, kas parādīja, jums kādi sērijas summations piemēram Tas galu galā saskaita. Vispārīgā gadījumā, ja jums ir mainīgs, piemēram n, un patiesībā tas viens, ja jūs paskatījās jūsu vecās skolas matemātikas grāmata, jūs varētu redzēt, ka tas patiesībā piebilst, līdz šīs summas šeit n reizes n mīnus 1 viss dalīts ar 2. Tātad tagad ļaujiet man tikai noteikt, tā ir taisnība, tāpēc uz lēciens ticības, ka tas, ko šis rezumē līdz, un mēs varētu pierāda, ka daudz vispārējā gadījumā. Bet tagad pieņemsim paplašināt šo out. Tāpēc pieņemsim reizināt šo, tā ka ir n brusas, mīnus n, viss dalīts ar 2. Tas tiešām n rūtiņām, dalīts ar 2, mīnus n nekā 2, tā, ka viss ir jauki un interesanti. Bet kas notiek, ja mēs Tagad plug-in vērtību? Pieņemsim, ka man nebija astoņi cilvēki, bet saka miljons. Un miljonus tikai tāpēc, ka tas ir diezgan liels skaits, pieņemsim plug ka, un redzēt, kas notiek. Tātad, ja es plug miljons minētajā formulā Es esmu gatavojas saņemt miljonus rūtiņām, dalīts ar 2, mīnus miljoni, dalīts ar 2. Tagad to, kas ir, kas notiek, lai ir vienādi? Tātad 500 miljardi, mīnus 500,000. Un, ja es tiešām ka math out, ka līdzekļi ka šķirošana miljons cilvēki ar burbuļa kārtošanas var aizņemt man 499999500000 soļi vai salīdzinājumi beigās, mēs esam tikai ekstrapolējot. 

Ka jūtas diezgan lēns, bet atklāti sakot mērot vienu konkrētu ieguldījumu , piemēram, tas, nav viss, kas stāsta. Bet tiešām tas liecina, ka, tā kā n saņem lielāku un lielāku, šo algoritmu veida jūtas sliktāk un sliktāk, vai jūs tiešām sāk izjust sāpes, ka exponentiation, ka n rūtiņām, kas iznāk diezgan ātri. Un šī informācija nav zaudēja uz cilvēkiem, patiesībā Pirms dažiem gadiem zināma senators, kurš bija kampaņas, apsēdās uz interviju ar Google Eric Schmidt, CEO tajā laikā, un apstrīdēja ar jautājumu daudz, piemēram, mēs pētām šodien. Pieņemsim to apskatīt. 

[Video atskaņošana] 

-Senator, Tu esi šeit Google, un man patīk domāt par prezidentūras kā darba interviju. Tagad, tas ir grūti iegūt darbu kā prezidents, un jūs iet cauri drebuļi tagad. Tas ir arī grūti iegūt darbu pie Google. Mums ir jautājumi, un mēs uzdot mūsu kandidātiem jautājumus, un tas viens no Larry Schwimmer. What-- jūs puiši domājat, ka es esmu kidding, tas ir tepat. Kas ir visefektīvākais veids, kā šķirot miljons 32-bitu integers? 

-Well-- 

-Es Žēl, maybe-- 

-Nē, Nē, nē. Es domāju, ka burbulis šķirot būtu nepareizs ceļš. 

-Nāc, Kas viņam šo stāstīja? Es neredzēju datoru zinātne jūsu fona. 

-We've Ieguva mūsu spiegu tur. 

-OK, Pieņemsim uzdot atšķirīgs intervija jautājums. 

[END VIDEO PLAYBACK] 

SPEAKER: Tātad runājam konkrēti skaitļi, lai gan, nav būs viss, kas noderīgs. Tas nav dzīves mācība, ka burbulis kārtot, ņemot miljons ieejas, varētu veikt tik daudz kā 500 miljardi soļus. Jūs nevarat īsti vispārināt Arī faktiski no tā un darīt labus dizains lēmumus rakstot programmas. Tātad, pieņemsim koncentrēties gan uz to, kā mēs varētu vienkāršot šo rezultātu. 

Tāpēc es esmu iezīmēts dzeltenā šeit rezultāts n kvadrātā dalīts ar 2, tāpēc miljons kvadrātā dalot ar 2, un pēc tam Es esmu uzsvērusi to, ko galīgā atbilde bija kad mēs jāatņem off n dalīts ar 2. Un apgalvojums es esmu gatavojas darīt tagad, kurš heck cares, ja tu atņem off mazliet vecs n vairāk nekā 2, kad pirmais daļa no šīs formulas ir tik daudz lielāks? Tā dominē otru termins, n kvadrātā dalīts ar 2 ir tik daudz lielāks, nepārprotami, jo n izpaužas liels, piemēram, miljons, ka ir tiešām liela atšķirība pie dienas beigās no 500 miljardu un 499.999.500.000? Nav īsti. Un tā, ko mēs gatavojamies darīt, kā datoru zinātnieki ir ignorēt šos zemākas kārtības noteikumus un veikt kaut kas līdzīgs šim, un patiešām tikai vienkāršot to termins, kas notiek, lai jautājums. Lielāki mūsu datu kopas nokļūt, lielāks Mūsu datu bāzes iegūt, jo vairāk interneta lapas mums ir jāmeklē, vairāk draugi jums ir uz Facebook. 

Kā n kļūst lielāka, mēs patiešām gatavojas rūpēties par lielāko jēdziens jebkurā šādā analīzē mūsu algoritmi sniegumu. Un es esmu gatavojas teikt, jūs zināt, ko, burbulis veida ir par lielo O rīkojumu, par n secībā brusas. Tas nav tieši n brusas, kā mēs esam redzējuši, bet kurš tiešām rūpējas par šiem mazākiem nosacījumiem, un godīgi sakot, kas tiešām cares, ja mēs sadalīt pa 2? Tas ir tikai nemainīgs faktors. Un ir 500 miljardi pret 250 miljardiem tiešām tik liels ir galā? Es varētu vienkārši gaidīt vienu gadu, let manu klēpjdators burtiski saņemt divreiz ātrāk aparatūru, un kas veida starpības vienkārši iet prom dabiski laika gaitā. 

Ko mēs rūpējamies par to ir izteiksme, daļa Izteiksmes, kas notiek variēt kā mūsu ieguldījums kļūst lielāka un lielāka. Un tiešām, reālajā pasaulē, tas, kas notiek arvien biežāk ir ieejas uz mūsu problēmām un algoritmi kļūst lielāki. Tik liels O būs atzīme, asimptotiskās apzīmējums, ka mēs vienkārši izmantot kā datoru zinātnieki, lai aprakstītu stāvokli, vai darbības laiks, algoritma. Tāpēc, ka mēs varam salīdzināt algoritmus uz dažādiem datoriem rakstveida dažādi cilvēki, izmantojot daži fundamentāli līdzīgs metrisko tāpat skaita salīdzinājumu tu esi pieņemšanā, vai varbūt skaitu mijmaiņas darījumu jūs gūstat. 

Ko mēs nebrauksim skaits ir laika daudzums kas iet uz pulksteni uz sienas tipisku. Ko mēs nebrauksim jāuztraucas par to ir, cik daudz atmiņas jūs izmantojat šodien at Vismaz, lai gan tas ir vēl viens resurss, mēs varētu izmērīt. Mēs ejam, lai mēģinātu pamatot savu analīzi par tikai no pamatdarbības, tie, atklāti sakot, ka jūs varat redzēt, lielākā daļa vizuāli. Tātad ar kaut ko līdzīgu lielo O n brusas, es apgalvot, ka O n kvadrātā ir augšējā robeža tā saukto darbības laiks burbulis veida. Citiem vārdiem sakot, ja jums gribēja apgalvot, ka tur ir šī augšējā robeža, cik daudz soļi algoritms varētu veikt, tas būs lielā O n brusas šajā gadījumā, augšējo robežu. 

Ko darīt, ja es tā vietā mainās stāsts ir ne par burbulis kārtot, bet par šo augšējo robežu. Vai jūs varat iedomāties algoritmu ka mēs esam paskatījās jau kuru augšējo robežu, maksimālais izmērīt laika vai darbībām, būtu teikt, ka ierobežo ar n, lineāra funkcija, nav kvadrāta viens, kas ir izliekta? Kas ir algoritms, kas vienmēr aizņem ne vairāk nekā, piemēram, n soļus, vai 2n pakāpieni, vai 3n soļi? Yeah? 

AUDITORIJA: Meklējot Visvairāk sarakstā? 

SPEAKER: Perfect, konstatējot Visvairāk sarakstā. Ja es esmu dota sarakstu cilvēki piemēram, katrs no kuriem ir saimniecības numuru, kas ir maksimālais skaits par pasākumiem, ko tā būtu jāņem mani, samērā gudrs cilvēks, lai atrastu lielāko personu šajā sarakstā? n, vai ne? Jo sliktākajā gadījumā, kad varētu lielākā vērtība būt? Labi, visu ceļu beigās. Tātad sliktākajā gadījumā augšējā robeža, es varētu ir iet visu ceļu šurp un būt, piemēram, oh, šeit ir vairāki astoņi, vai kāds, ka vērtība ir. Tagad tas būtu vienkārši stulbi ja es tur iet, vai ne? Meklē vairāk un vairāk elementiem ja pēdējais no tiem ir tur? Tātad, protams, n ir augšējo robežu. Man nav nepieciešams veikt vairāk soļi nekā. 

Tātad, ko tad, ja tā vietā, es ierosināju, ka ir algoritmi šajā pasaulē, kas ir darbības laiku, kas ir robežojas ar lielo O log n log n? Kur mēs esam redzējuši šo pirms? Yeah? 

AUDITORIJA: In tālruņa grāmatu problēmu? SPEAKER: Tāpat tālruņa grāmatu problēmu. Kāds bija pasākums, cik daudz laika vai cik asaras IT aizveda mani atrast kādu, piemēram, Mike Smith tālruņu katalogā? Mums apgalvoja, ka tas bija log n, un pat ja svešs, vai tas tā ir mazliet dūmakains, ko logaritms vai eksponents bija tikai atcerieties, ka log n parasti attiecas uz procesu, Šajā gadījumā, dalot kaut pusi atkal, un atkal, un atkal, un atkal, tā, ka tā kļūst arvien mazs, kā jūs darīt. 

Tātad log of n atsaucas, pārliecināts, uz tālruņa grāmatu, piemēram, uz bināro meklēšanu teoriju, kad mēs bija virtuālās durvis uz kuģa, vai tad, kad Sean bija meklē kaut ko. Ja viņš ir izmantojis bināro meklēšanu, log n būtu augšējo robežu, cik daudz laiks, kas notiek. Bet tie algoritmi, kas skrēja log n pieņemts kāda atslēgu detaļu? Šis saraksts ir sakārtots, labi? Tavs algoritms ir nepareizi, ja jūsu ieguldījums nav sakārtots, un tomēr jūs izmantojat kaut kā bināro meklēšanu tāpēc, ka jūs varētu lēkt tiesības pār elementu neapzinoties tā ir patiešām tur. 

Tagad, ko tas varētu nozīmēt, Big O vienu? Tas nenozīmē, ka jūsu algoritmu aizņem viens un tikai viens solis, tas tikai nozīmē, ka tas notiek konstante vairāki soļi. Varbūt tas ir 1, varbūt tā ir 10, varbūt tas ir 1000, bet tas ir neatkarīgs no problēmas apmēri. Nav svarīgi, cik liels n ir, pastāvīgs laiks algoritms vienmēr ir tāds pats vairākus pasākumus. Tātad, kādi varētu būt algoritms mēs esam runājuši par to, vai vienkārši intuitīvi, kas nāk pie jums, ka vienmēr darbojas tā sauktajā pastāvīgu laiku? Yeah? 

AUDITORIJA: Pievienot divus numurus. SPEAKER: Pievienot divus numurus, 2 plus 2 ir vienāds ar 4, darīts. Lai varētu strādāt, ko vēl? Kā par vairāk reālajā pasaulē, jā? 

AUDITORIJA: Meklējot pirmā lieta sarakstā. SPEAKER: Meklējot pirmais elements sarakstā, pārliecināts. Mēs esam patiešām ir runāt par masīviem jau kā jūs saņemsiet pie pirmais elements masīvā, vienalga, cik ilgi masīvs ir C kodu? Jūs vienkārši izmantot kā kronšteinu nulle apzīmējums, bam, tu esi tur. Un patiešām bloki, kā malā, atbalsts kaut vispārzināma kā brīvpiekļuves, brīvpieejas atmiņa, jo jūs varat burtiski pāriet uz jebkuru vienā vietā. Mēs varam izdarīt vēl vienkāršāk mēs varam attīt uz nedēļu nulles kad mēs darījām Scratch. Cik daudz laika tas veic, lai saka bloks Scratch izpildīt? Tikai nemainīgs laiks, vai ne? Pateikt kaut ko, teiksim kaut ko, tas nav svarīgi cik liels Skrāpējumi pasaule ir, tas vienmēr ir gatavojas pieņemt tādu pašu laiku vienkārši pateikt kaut ko. 

Tā ka ir nemainīgs laiks, bet to, kas ir otra puse? Ja tas bija augšējais robežas, kas notiks, ja mēs gribam aprakstīt zemākas robežas mūsu algoritmu darbības laiks? Gandrīz labākajā gadījumā potenciāli, ja jūs, gan šie noteikumi varētu attiekties uz labāko lietas, sliktākajā lietas, vidējās gadījumi vairāk vispār, bet pieņemsim tikai koncentrēties uz apakšējā robeža kopumā. Kas ir algoritms, kas ir zemākā robeža n soļiem, vai 2n pakāpieni, vai 3n soļi? Daži no n soļiem faktors, tas tā apakšējo robežu. Yeah? 

AUDITORIJA: Bubble kārtošanas? 

SPEAKER: Bubble kārtošanas notiek Jūs minimāli n soļi, kāpēc? Kāpēc tā? Kāpēc, ka sākums nākt pie jums intuitīvi, pat ja tas ne tikai vēl? Yeah? 

AUDITORIJA: [nedzirdama]. SPEAKER: Tieši tā. Vislabākajā iespējamajā scenārijā burbulis kārtot, un daudz algoritmu, ja es roku jums astoņi cilvēki kuri jau ir sakārtoti, tas būtu muļķīgi jums, algoritms, iet uz priekšu un atpakaļ vairāk nekā vienu reizi, vai ne? Jo, tiklīdz jūs iet cauri sarakstam vienu reizi, Jums vajadzētu saprast, ak, es nē mijmaiņas līgumi, šis saraksts ir sakārtots, izeju. Bet kas notiek, lai tevi n soļus. 

Un otrādi, kas ir vēl viens veids, kā domāt par to? Bubble kārtošanas ir omega, tā sakot, no n, jo, ja paskatās mazāk nekā n elementi, ko ir būtisks jautājums tur? Jūs nezināt, ja tas ir sakārtots, labi. Mēs cilvēki varētu skatienu pulksten astoņos cilvēki un būt, piemēram, ak, tas ir sakārtoti, ka neņēma mani n soļus, bet tas notika. Tavas acis, lai gan jums veida gada ir liels redzeslauku, Jūs paskatījās astoņiem elementiem, Jūs paskatījās astoņiem cilvēkiem, tas ir astoņi soļi efektīvi. Un tikai tad, ja es staigāju visa saraksts darīt es saprotu, jā, sakārtoti. Ja man apstāties pusceļā domāt, viss labi, tas ir diezgan sakārtoti līdz šim, kādas ir izredzes, tas nav šķirotas? Ka algoritmi nebūs pareizs. Varētu būt ātrāks, bet nepareizi. 

Tāpēc tagad mums ir veids, kā Aprakstot zemākas robežas, un ko par pastāvīgu laiku? Kas ir algoritms, kas ir zemāka saista tās darba laika viena? 1 solis, 2 soļi, 10 soļi, bet nemainīgs, neatkarīgi no N, lielums ievadi? Jā, aizmugurē. 

AUDITORIJA: Printf? SPEAKER: Kas tas tāds? AUDITORIJA: Printf? SPEAKER: Printf. Labi, protams. Tātad tas aizņem fiksētu vairākus pasākumus. Un es būtu now-- tagad, ka mēs runājam par C kodu un nevis Scratch, kaut piemēram, teiksim, ar printf, mums vajadzētu sākt saņemt uzmanīgiem. Jo printf nav jāveic ievadi, tas ir string, un auklas tie tehniski ir garums. Tātad, ja mēs tagad gribam uzņemt par jums, ja jums nav prātā, tehniski mēs varētu apgalvot, ka printf tas ņem mainīga garuma ievadi, un, protams, tas var aizņemt vairāk laiks drukāt virkni šo ilgi, par šo ilgi. 

Tātad, ko tad mēs uzskatām tikai šķirošanas un meklēšanas piemērus? Kas par Mike Smith tālrunī grāmatu, vai binārā meklēšana plašāk? Labākajā gadījumā, kas varētu notikt? Es atvērt telefona grāmatu un, bam, tur ir Maika Smita numurs. Es varu zvanīt viņam uzreiz. 

Spēra vienu soli, varbūt divos posmos, bet pastāvīga vairākus pasākumus ja es saņēmu laimīgs. Un godīgi sakot, mēs redzējām Pirmdiena Jūsu klasesbiedrs iegūt diezgan laimīgs divas reizes pēc kārtas. Un tas patiešām bija nemainīgs laiks zemāku robežas par algoritma jautājumu, lai atrastu numurs 50 aiz tiem slēgts durvis. 

Tagad, kā malā, ja jūs atklāsiet ka gan liels O, augšējo robežu, un omega, zemākā robeža, ir viena un tā pati, kas ir tāda pati formula iekavas, varat arī teikt, tikai, lai būtu iedomātā, ka kaut kas ir teta n vai teta kādas citas vērtības. Tas tikai nozīmē, kad liels O un omega ir vienādi. Tagad, ko par atlases veida? Pieņemsim izmantot šo jauno vārdu krājumu. Šajā atlases veida, kādi bija mēs dara atkal, un atkal, un atkal? Man bija iet uz priekšu un atpakaļ, izmantojot sarakstu, meklē kam? Mazākais numurs. 

Tik, cik daudzi soļi, kā daudzi salīdzinājumi did I ir jāveic, lai noskaidrotu, kurš mazākais elements sarakstā bija? n mīnus 1, vai ne? Jo, ja es vienkārši sākt ar vienu es esmu dota, un es sāku salīdzināt viņu, tad viņam vai viņai, viņam vai viņas, viņam vai viņai, es var tikai pārī elementus kopā n mīnus 1 reizes. Tātad izvēle veida līdzīgi notiek n mīnus 1 soļus pirmo reizi. 

Cik soļus tas veic mani atrast otro mazāko elementu? n mīnus 2, jo es esmu mēms ja es turpinu meklē paši cilvēki atkal, ja es esmu jau izvēlējies viņam vai viņas un nodot tos savā vietā. Un trešais solis, n mīnus 3, tad n mīnus 4. Mēs esam redzējuši šo modeli pirms, un patiešām atlase veida līdzīgi ir augšējo robežu no n kvadrātā, ja mēs uz augšu, ka summēšanas. Kas ir tās apakšējo robežu, atlase kārtošanas? Minimāli, cik daudz laika must atlase kārtot veikt, kā mēs to definēja pirmdien? Ierosinās divas iespējas. Varbūt tas ir n, kā iepriekš. Varbūt tas ir n brusas, kā tas ir tagad, jo augšējo robežu. 

AUDITORIJA: n brusas. SPEAKER: n brusas. Kāpēc? 

AUDITORIJA: Jo jums ir definēt [nedzirdama]. 

SPEAKER: Tieši tā. Vismaz kā es noteikti atlases veida tas bija diezgan naivi, turpiniet, atrast mazāko elementu. Iet atkal, atrast mazāko elementu. Iet atkal, atrast mazāko elementu. Nav veida optimizācija tur, ka varētu man pārtraukt pēc tikai n vai tik soļi. Tik tiešām, atlase kārtot, omega n brusas. 

Kas par ievietošanas veida, kur es ņēma kas man tika dots, un tad es viņam plopped vai viņai īstajā vietā? Tad es turpināja otrajā personā, plopped viņam vai viņai īstajā vietā. Tad nākamais cilvēks, plopped viņam vai viņai īstajā vietā. Ievērojiet, ka tas ir ļoti lineāra, lai runāt. Es esmu taisne, es esmu nebrauksim uz priekšu un atpakaļ, Es nekad neesmu atskatoties īsti, bet kas notiek, kad es ievietot viņu vai viņas uz sākumu sarakstu, kā mēs to darījām pirmdien? Kas notiek? Yeah? AUDITORIJA: [nedzirdama]. SPEAKER: Jā, ka bija nozvejas, vai ne? Jūs varētu atsaukt no savu klasesbiedru, ja tie Tika jebkādu kustību ar kājām, kas bija operācija. Tātad, ja tur bija trīs cilvēki šeit un jauna persona piederēja ceļu tur, uz ilgu skatuves kā šis, protams, viņš vai viņa varētu vienkārši doties uz pašām beigām. Bet, ja mēs, domājot par dators un masīvs atmiņas, šie cilvēki dodas lai būtu, lai sajauktu vairāk lai atbrīvotu vietu šai personai. Un tā, ka n mīnus 1 shufflings, n mīnus 2 shufflings, n mīnus 3 shufflings ir tikai sava veida notiek aiz manis, nevis man priekšā kā iepriekš, savā ziņā. Tagad, kā malā, un kā Jums varētu būt reizi manīts Ja jūs sākat papētījis par veidu, tur ir tik daudz dažādas tie tur, daži no tiem labāk nekā citi. Patiešām, bogosort ir viens tas ir sava veida jautrības uzmeklēt. Bogosort aizņem kopumu numuri vai teikt kārtis, nejauši sajauks viņiem, un pārbaudes, ja viņi sakārtoti. Un, ja nav, to dara atkārtoti. Un, ja nav, to dara atkārtoti. Ja tā nav, to dara atkārtoti. Neticami stulba. 

Un tiešām, ja jūs lasīt piemēram, Wikipedia rakstu, tā segvārds ir stulba kārtošanas. Tas būs iespējams strādāt, cerams, dots pietiekami daudz laika, bet, ka daudz laika varētu veikt diezgan kādu laiku. Tātad, ja es varētu, pieņemsim ātruma lietām up no Mary Beth piemēru agrāk, , ņemot vēl dažus elementus, bet vēl divi procesori. Divi cilvēki, ja jums neiebilstu savieno mani. Kā par 1 vairāk nekā šeit, un pieņemsim go-- nevienu pār tur? Neviens tur? OK. Tu ar melnu krekls, jā, nāk uz leju. Nu labi, kāds ir tavs vārds? 

AUDITORIJA: Peter. 

SPEAKER: Kas tas tāds? 

AUDITORIJA: Peter. SPEAKER: Pēteris, Dāvids, nice to meet you. Nu labi, mums ir Pēteris šeit, ja jums vēlaties nākt uz galda nekā šeit. Un kāds ir tavs vārds? 

AUDITORIJA: Elena. SPEAKER: Elena. OK, nice to meet you. Elena tiekas Pēteris. Pēteris, Elena. Un mums būs nepieciešams Andrew šeit, kā arī, lūdzu. Un jūsu uzdevums ir iet jābūt, lai kārtotu kārtis. Un, ja svešs, klāja Karšu vajadzētu galu galā sakārtoti nedaudz kaut kas līdzīgs tas, kur mēs darīsim klubiem, tad tad lāpstas, tad sirdis un dimanti, no dūzi kā viens, visu ceļu līdz pat karalim. 

Kārtis Es esmu gatavojas sniegt jums ir būs 52 daudzuma. Mēs ejam, lai līdzīgi laiks jums, tikai brīdi. Mēs ejam, lai mest Andrew uz ekrāna šeit lai skatīties, kā jūs to izdarītu. Un tā, ka tas viss ir viss vairāk redzams, šie ir kārtis es saņēmu par Amazon. Tātad tie jau nejauši sakārtoti, un mēs braucam pa laikam jums. Un mēs ejam saglabāt to reālu šoreiz, tāpēc mēs esam gatavojas izmēģināt, lai piespiestu tevi , jo pretējā gadījumā tas kļūs garlaicīgs ātri. Ja jūs varētu turpināt kārtot 52 elementus kopā caur kādu līdzekļiem, tagad. 

Un atkal, kā mēs skatīties šos guys darīt ko, kas beigās gatavojas ražot acīmredzama Rezultāts, domāju par patiešām cik viņi katrs dara to, kā jūs varētu aprakstīt to. Jo atkal, tie ir visi procesi, algoritmi ka mēs uztveram par pašsaprotamu, jo cilvēkam. Bet jūs esat droši vien sen bija intuīcija, ilgi pirms jums pat domāja par ņemot datorzinātnes jums klase varētu būt bijusi intuīcija ar kas, lai atrisinātu problēmas, kā šis. Bet tad, kad jūs apzināties modeļus un sākt formalizēt pasākumus, ar kuriem jūs atrisināt šīs problēmas, Jūs atradīsiet, ka jūs varat atrisināt daudz vairāk interesantu un daudz sarežģītāka problēmas ātri. Lai kāds no skatītājiem, kas ir vismaz viens elements algoritmu ka viņi, izmantojot šeit? 

Mērķauditorija: [dzirdams] SPEAKER: Kas tas tāds? AUDITORIJA: Pēc uzvalks. SPEAKER: Pēc uzvalks. Tātad vispirms tie, sagrupējot visas dimantu kopā šķiet, visi sirdis kopā, šķiet, un tā tālāk, neievērojot par cipariem uz kartes. Un tagad tie parādās, piemēram, kas šķirojot tos pēc skaita. Ļoti labs. 

Labi, lai to, kas notiek, lai būs pēdējais solis, tad šeit? Tiklīdz mums ir četri sakārtotās kostīmi, ko vai mums vajag darīt, lai četriem pāļu lai sasniegtu vienu sakārtoti klāja, gluži vienkārši? Tāpēc mums ir nepieciešams apvienot tos vēlreiz. 

Tātad tur ir interesanta ideja, ka atkal, daresay, ir ļoti intuitīva, pat ja jūs varētu nekad cirta šāda veida etiķetes par to. Šis būtisks jēdziens dalot problēma ne pusi šajā laikā, bet vismaz četrās daļās. Risināšana diezgan daudz fundamentāli identiskas problēmas ir izolēti viens no otra, un pēc tam apvienojot rezultātus. Un, lielisks, darīts. Labi, liels apaļš aplausu, ja mēs varētu. 

[Aplausi] 

SPEAKER: Man nav ne jausmas, ko jūs darīt ar tiem, bet šeit jums iet. Thank you so much. Tātad, pieņemsim redzēt, divas minūtes un astoņas sekundes, Ja vēlaties, lai apstrīdētu draugus. Kas tad ir gatavojas ir prom no šīs ka mēs varam piesaistīt vairāk vispār? Nu, domāju, ka atpakaļ uz šis masīvs numuru, un domāju, ka atpakaļ tagad dažus pseudocode mēs esam rakstīts pagātnē, un tas bija pseudocode par risināšanā tālruņu grāmatas problēmu. Kuru in pseudocode I uzskaitītas vairāk metodisku ceļu aprakstīt, kā es darīju ļoti intuitīvs cilvēka algoritms dalot tālruni grāmata uz pusēm, atkārtot, atkārtot, atkārtot, līdz es atrast kāds, piemēram, Mike Smith, ja viņš ir patiešām tālruņu grāmatā. 

Bet es veida izmanto to, ko es saukšu ļoti iteratīvs pieeja šeit, jo īpaši paziņojumā līnija 8 un pozīcija 11. Tie ir pierādījums iteratīvs pieeja, looping pieeja, tāpēc, ka tas ir tieši uzvedība tie liek. Šie līnijas abas saku iet uz veida līniju trīs, un jūs varat no domāju, ka jūsu prāta acs kā cilpa. Tā stāsta jums iet atpakaļ uz augšu soli trīs un atkārtot atkal un atkal, un atkal. 

Bet ja mēs sviras galvenā ideja šeit, ka mēs neesam pēdējā reize, un vienkāršot līniju 8 un pozīcija 11 un viņu kaimiņi , jo tikai tas, dzeltenā krāsā. Tas nav būtiski saīsinot pseudocode ļoti daudz, bet tas ir būtiski mainās raksturs manas algoritmu. Kas es esmu tagad saka 7 soli, 10 solis ir meklēt Mike tieši tādā pašā veidā, bet tikai pa kreisi puse vai labi pusi. 

Tātad, citiem vārdiem sakot, ja Es sāku no viena soļa, uzņemt tālruņa grāmatu, atvērta vidu no tālruņu grāmatas, apskatīt vārdiem, ja Smith ir viena vārds ir, zvaniet Mike, cits ja Smits ir agrāk grāmatā, septiņi soli meklēt Mike kreisajā pusē grāmatas. Bet šāda veida jūtas kā tas ir atstājot mani karājas, labi? Dzeltenā krāsā, ir instrukcija, bet kā es varu meklēt Mike kreisi puse no tālruņa grāmatu? Kur man ir algoritms, ar kuru es var meklēt kādu, piemēram, Mike Smith? Nu, tas skatās mums sejā. Es varu burtiski izmantot tieši tādu pašu programma faktiski iet uz augšu uz augšu atkal un atkal darbojas tās pašas līnijas kodu. 

Tātad, pat ja tas būtu justies kā mazliet cikliskas definīcijas kur jūs atbildētu kāds ir jautājums, ko tikai veida jautā pats jautājums atkal, piemēram, kāpēc, kāpēc, kāpēc? Realitāte ir tāda, ka mēs esam smagi kodēta pāris īpašas līnijas, 4 soli, kas ir, ja, un 12 soli, kas ir efektīvi cits filiāle, jo mums ir šie spunde pasākumus, tas algoritms beigsies, ja mēs atrast Mike, vai arī, ja mums nav. Bet 7 un soli 10 tagad, mums ir tas, ko mēs saucam rekursīvo algoritmu. Un rekursijas ir patiešām spēcīgs ideja ka ir maz prāta saliekuma sākumā, , ka mēs tagad varam piemēro šādi. 

Apvienot kārtot būs pēdējais kārtošanas, ka mēs skatāmies, vismaz klasē formāli. Un tas ir būtiski atšķiras no tiem pēdējiem trīs, un, protams, pēdējo četru ja mēs iekļaujam bogosort. Lūk pseudocode par sapludināšanas kārtošanas. Kad par ieejas n elementiem, tā, ņemot vērā masīva izmērs N, ja n ir mazāks par 2, atgriezties. Tātad, kāpēc man ir, ka vesels saprāts pārbaudīt vispirms? Kāda ir saistība, ja es roku tevi masīvs, kura garums n ir mazāks par 2? Tas jau ir sakārtoti, protams, labi? Jo saraksts nu ir viens elements, kas ir trivially sakārtoti, jo tas ir Vienīgais, kas tur. Vai tas ir no lieluma nulles, kas nozīmē, nekas, lai kārtotu, tāpēc pēc būtības tas ir sakārtots. Tur ir tikai nekas nepareizs tur. Tātad tas ir mūsu tā saucamā bāzes gadījums. 

Tas ir līdzīgs garā to, ko mēs darījām ar Mike. Ja Mike s tālruņu grāmatā, zvanu viņam. Ja viņš tur nav, atmest. Tas ir tā sauktais bāzes scenārijs, lai pārliecinātos, ka Šis algoritms beigās dienā apstāsies noteiktos apstākļos. 

Bet šeit ir lēciens ticības tagad, cits, kārtot kreiso pusi elementiem, tad šķirot tiesības puse no elementiem, un pēc tam apvienot sakārtoti pusītes. Un šeit ir, ja tā uzskata, kā mēs esam copping out. Esmu lūdza, lai sakārtotu n elementi, un es esmu sacīdams, OK, es to ar šķirošanu kreisi un šķirošanas tiesības. Bet es saku vienu Otra lieta, un šī ir galvenais temats šķiet uz intuīciju līdz šim, tur ir šis trešais solis apvienošanu. Kas, kaut arī tā šķiet tik mēms garā, tāpat vienkārši apvienot lietas kopā, šķiet, būt svarīgs solis pārbūves divas problēmas, kas tika sadalītas galu galā uz pusēm. 

Tātad apvienot kārtot, pieņemsim darīt, ja jūs humors mani, ar vēl vienu demonstrāciju, tikai tāpēc, ka mums ir daži numuri strādāt. Es varu apmainīties astoņi stresu bumbas astoņu cilvēku? Nu labi, kā par jums trīs, jūs četri šajā sadaļā, pieci, seši, un pieņemsim do 7, 8, nākt uz augšu. OK, jā OK. Mīnus 8, tur mēs ejam, plus 1. Excellent. Visas tiesības nākt uz augšu, pieņemsim ātri sniegt jums numurus. Numurs divi, numurs trīs, numurs četri, numuru pieci, seši, septiņi un astoņi. I did astoņi pareizi šo laiku. 

Labi, tā iet uz priekšu, ja jūs varētu, un pieņemsim sakārtotu sākotnējā kārtībā ka mums bija vakar, kas izskatījās , piemēram, tas, ja jūs neiebilstat. Un pieņemsim to darīt pie galda. Labi, tāpēc apvienot kārtošanas. Tas ir, ja tas notiek nokļūt veida interesants, jo man šķiet, kas sevi tik daudz mazāk informācijas šodien. 

Tātad apvienot kārtot vispirms par ieejas n elementiem, un, protams, nav mazāks par diviem, tas ir astoņi, tāpēc man ir dažas vairāk jāstrādā. Tāpēc tagad garīgi mēs kā klasē šobrīd ir cits filiālē, kas nozīmē trīs soļus. Pirmkārt, man ir, lai kārtotu kreiso pusi no elementiem. Tātad, kā es varu iet par to izdarīt? Nu, es esmu gatavojas veida garīgi sadalīt sarakstu šeit, jums nav fiziski kustēties, un es esmu gatavojas koncentrēties tikai uz kreisā puse no elementiem šeit. Tātad, kā es varu iet par šķirošanu Piedāvājuma saraksts izmēra četriem? Kas ir mans algoritms? Vispirms es pārbaudītu, ir n mazāks nekā divi, nē, tāpēc es pārietu uz citu bloku vēlreiz. Kārtot atstājis pusi no elementu. 

Tāpēc tagad atkal, garīgi, un tas ir, ja Jums ir uzkrāt daudz garīgo vēsturi, ja Jums gribas. Tagad es esmu šķirošanu kreiso puse no kreisās puses. Labi, tāpēc tagad es aicinu manu pašu sapludināšanu šķirošana algoritms, ir n mazāk nekā divas? Nē, tas ir divi, tāpēc man ir, lai sakārtotu kreiso pusi, un labajā pusē. Tātad šeit mēs ejam, sakārtot pa kreisi pusi. Kāpēc ne jūs vienkārši veikt vienu soli uz priekšu. Kāds ir tavs vārds? 

AUDITORIJA: Darren. 

SPEAKER: Dan. Dan ir pastiprināts priekšu. 

AUDITORIJA: Darren. SPEAKER: Darren, darīts. Tu teici Darren vai Dan? 

AUDITORIJA: Darren. 

SPEAKER: Darren. OK, Darren ir pastiprināts priekšu, un viņš tagad sakārtots. Un tas ir gandrīz muļķīgs apgalvojums, vai ne? Man nav īsti, šķiet, ir sasniegt kaut kas, bet pieņemsim turpināt. Tagad ļaujiet man sakārtot tiesības puse no elementiem. Kāds ir tavs vārds? 

AUDITORIJA: Luke. 

SPEAKER: Luke. Come on, soli uz priekšu. Darīts, man ir sakārtoti Luke. Kreisā puse tagad ir sakārtoti un tiesības puse tagad ir sakārtoti, bet atkal, tur ir svarīgs solis šeit. Kas man blakus vajag darīt? Apvienot sakārtoti pusītes. Tagad mēs ejam, lai vienkārši ir katrs uz priekšu un atpakaļ šādā veidā, jo man veida vajag daži scratch telpa. Tas ir gandrīz kā šos puiši ir uz galda, un man vajag dažas telpas , lai tos tālāk. Tāpēc es esmu gatavojas apvienoties jūs puiši, apskatot kreisajā pusē un labajā pusē. Un kurš acīmredzot ir pirmajā vietā, kreisi puse jeb labi pusi? Tik labi pusi, tāpēc pāriesim Luke vairāk šeit, lai Darren sākotnējā stāvoklī. Un tagad apvienot savu kreiso pusi, kas, Darren gatavojas pārcelties turpat. 

Tāpēc jūtas kā gandrīz burbulis veida efekts, bet mans galvenais algoritms, ļoti atšķirīgs šoreiz. Bet tagad ir, ja lietas iegūt mazliet kaitinošas, jo jums jāgriež atpakaļ garīgi kurienes es mitēties. Esmu tikko apvienoja sakārtotos pusītes, kas nozīmē, ka es esmu, kur manā algoritmu? Man ir, lai sakārtotu labo pusi, vai ne? 

Ja jūs attīt, burtiski uz video, jūs redz, ka mēs saņēmām šo punkts Lūkas un Darren šķirošanas kreiso puse no kreisās puses. Tad mēs apvienojām tiem šķirotas pusītes, kas nozīmē, nākamais solis ir sava labo pusi kreisajā pusē. Labi, tāpēc pieņemsim izdarīt ātrāk. Nu labi, seši, es esmu gatavojas pieprasīt jūs tagad sakārtoti, nāc uz priekšu. Kāds ir tavs vārds? 

AUDITORIJA: Adriano. 

SPEAKER: Adriano. Tagad Adriano ir sakārtots. Un kāds ir tavs vārds? 

AUDITORIJA: Alex. 

SPEAKER: tagad Alex ir sakārtots. Kreisās puse, labi pusi, kas ir pēdējais solis? Apvienoties. Diezgan niecīgs, tāpēc es esmu gatavojas apvienot sešās, spert soli atpakaļ, astoņi, veikt soli atpakaļ. Un tagad paziņojums tas ir noderīgs takeaway, ko tagad ir taisnība par kreisajā pusē saraksts, neatkarīgi no tā, kā mēs sākām? Tas ir sakārtots. 

Tagad tas nav sakārtoti liels shēma lietām, bet tas ir sakārtots patstāvīgi no otras puses. Tagad to solis es esmu par, ja es turpinu pārtīšana kā stāsts sākās? Tagad man ir, lai sakārtotu pareizo pusi. Tāpēc tagad mēs esam ceļu atpakaļ sākums stāsts, un pieņemsim darīt ātrāk. Tāpēc es esmu gatavojas, lai sakārtotu labo pusi no visu sarakstu. Kāds ir nākamais solis? Kārtot kreiso pusi labajā pusē. Kārtot kreiso pusi kreisā puse no labajā pusē. Un kāds ir tavs vārds? 

AUDITORIJA: Omar. 

SPEAKER: Omar, soli uz priekšu, darīts. Kreisā puse ir sakārtots. Un kāds ir tavs vārds? 

AUDITORIJA: Chris. 

SPEAKER: Chris, veikt soli uz priekšu, jūs tagad sakārtoti. Kas ir galvenais solis tagad? Apvienoties. Tik viens gatavojas apvienot savā vietā Šeit, ja jūs varētu veikt soli atpakaļ, un trīs gatavojas spert soli atpakaļ, apvienot. Tātad kreisā puse labajā pusē, tagad ir sakārtots. Atklāti sakot, šis algoritms jūtas kā mēs ir izšķērdēt veids vairāk laika nekā agrāk, bet, ja mēs to darījām reālā laikā, mēs ņemšu redzētu takeaways būs. Tagad šeit es esmu, vai ne puse labajā pusē, ļaujiet man iet uz priekšu un kārtot kreiso pusi. Solis uz priekšu, kāds ir tavs vārds? AUDITORIJA: Ramsey. SPEAKER: tagad Ramsey ir sakārtots. Kāds ir tavs vārds? 

AUDITORIJA: Marina. 

SPEAKER: tagad Marina ir sakārtots kā labi, ja jūs veikt vienu soli uz priekšu. Būtisks šeit tagad apvienot, es esmu gatavojas raut no maniem diviem sarakstiem, pa kreisi un pa labi. Five gatavojas nākt pirmkārt, un septiņi gatavojas nākt nākamais. Un atkal, tas ir apzināta. Fakts, ka viņi lieto soļi uz priekšu un atpakaļ ir domāts, lai pārstāvētu, ka mēs nevaram darīt šo algoritmu vietā tik viegli kā burbulis veida, un atlases veida, un ievietošanas kārtošanas, kur mēs vienkārši tur pārnešana cilvēkus. Es burtiski vajag veida no skrāpējumiem papīra, kurā likt šiem ļaudīm kamēr es to apvienošanu, un tad es varu nodot tos atpakaļ vietā. Un tas ir galvenais, jo es esmu, izmantojot jaunu resursu, telpu, ne tikai laiks. 

OK, tas ir pārsteidzošs. Atstājis pusi ir sakārtots, labi puse sakārtots, tagad, ka galvenais apvienojas solis. Kā es gatavojas apvienot šo? Tātad, ja jums sekot manu kreisā un labā roka, Es esmu gatavojas atzīmēt manu kreiso roku kreisajā pusē, mana labā roka īstajā pusē, un tagad man ir izlemt soli pa solim, kam apvienoties in. Kurš acīmredzot nāk vispirms? Numur viens. Tā nāk vairāk nekā šeit, šeit ir mūsu scratch pad. Tātad tagad numur viens, un paziņojums Ko es darīšu ar savu labo roku, Es esmu gatavojas pārvietot savu labo roku vienu soli pa norādīt numuru trīs, un tagad man ir, lai pats lēmums. Un faktiski stāvēt tiesības priekšpuse Lūkas šeit, ja jūs varētu, tāpēc, ka tas ir mūsu scratch pad. Tātad, kas būs tālāk? Mums ir Lūkas ar divām skaits vai Chris ar numuru trīs. Acīmredzot Luke, numurs divi, lai jūs nākt šeit. 

Bet mana kreisā roka tagad gatavojas palielina norādīt uz Darren, un šeit ir atslēga atņemt ar apvienošana, es esmu gatavojas, lai saglabātu darot to, protams, ja jūs veida no sekot loģikai. Bet manas rokas nekad gatavojas doties atpakaļ, kas nozīmē, ka es esmu tikai kādreiz pārvietojas uz kreisi ar manu apvienošanu procesu, un kas notiek, lai būtu galvenais Mūsu analīze tikai brīdi. 

Tāpēc tagad pieņemsim pabeigt šo augšu strauji. Tātad trīs nāk nākamais, Pēc tam četras nāk nākamais, un tagad pieci nāk nākamais, tad seši, un septiņi, un tad beidzot astoņi. Jūtas kā vislēnākā algoritmu vēl, bet ne tad, ja mēs faktiski darbojas vienā un tajā pašā veida par pulksteni ātrumu, tāpēc, lai runā, ar pašu atzīmējot pulksteni kā iepriekš. Kāpēc? Nu, Paņemsim apskatīt gala rezultātu. 

Atgriezīsimies nekā šeit, ļaujiet man uzvilkt demonstrāciju vizuāli par to, ko mēs tikko izdarījām. Attālināt šeit, par šo lapā šeit, stāstot Firefox ka mēs vēlamies rindā up šajā ailē, pieņemsim saka burbulis veida, ar kuru Tagad mēs esam labi pazīstami, atlases veida, kas ir vēl viens diezgan vienkārši viens, un tagad šodienas sapludināšanas kārtošanas, kas būs mūsu klimatiskajiem beidzas. Iemesls tas bija tik daudz ilgāk šeit ar cilvēkiem, un man mutiski ir, protams, es esmu izskaidrojot katru soli. Bet, ja jūs vienkārši izpildīt šo, daudz tāpat kā mēs to darījām burbulis kārtot un atlase kārtot ne tikai vizuāli, pulkstenis cik daudz efektīvāk šis piesaistīšana nodaļa un iekarošana var, ja piemēro datu kopu, kas ir nav pat izmēra astoņi, bet pat daudz, daudz lielāks. Es dodu jums apvienot kārtot, otram pusē ar šiem citiem algoritmiem. Tas ir gatavojas saņemt sāpīga ātri, un beidzas nav īpaši klimatiskajiem, viņi vienkārši beigties sakārtoti. Bet galvenais atņemt ir tas, ka izskatās, cik daudz ātrāk apvienot kārtošanas bija, ja jūs domājat, ka es esmu tikko veida messing ar jums. Ja mēs to darām vienu pēdējo reizi, pieņemsim pārlādēt to, iesim atpakaļ un izvēlēties burbulis veida, un tikai sākas, pieņemsim izvēlēties ievietošanas kārtot, vienkārši labs pasākums. Un šoreiz atkal, pieņemsim izvēlēties sapludināšanas veida un pieņemsim faktiski vada šos blakus. 

Un tas nav, patiesībā, parazīts. Ko es esmu efektīvi panākt ir Esmu sadalīta manu ievadi uz pusēm, atkal, un atkal, un atkal. Un tur ir tikai tik daudz reizes jūs varat sadalīt savu ieguldījumu daļās, pa kreisi un pa labi. Kas ir formula, ka mēs turpinām redzam kas apraksta sadalījumu pusē atkal, un atkal, un atkal, un atkal? 

AUDITORIJA: Pieteikties n. 

SPEAKER: Pieteikties n. Bet tad tur ir viena cita galvenais solis, šis algoritms nav log n soļi. Ja tas būtu tikai log n soļi, mēs būtu tādā pašā problēmu kā agrāk, kad mēs nevaram būt ka viss ir sakārtots. Jums ir minimāli apskatīt n elementiem lai pārliecinātos n elementi ir sakārtoti, citādi tas ir lēciens ticības. 

Tātad, tas ir minimāli log n soļi, taču ko par šo svarīgo soli apvienošanu kur es apvienojās manu kreiso pusi un pa labi pusi un gāja pāri skatuves? Cik soļi ir tas, ka apvienot? Tas ir n, bet man nebija ne tikai apvienot galīgo laiku. Par katru no šiem ligzdotu zvaniem, par katru Šo ligzdotu asimilē, es joprojām sakārtoti. Es apvienoti šie divi puiši, tad šie divi puiši, tad šie divi puiši, un tā tālāk. 

Tāpēc es tomēr apvienojas atkal, un atkal. Cik reizes? Tāpēc katru reizi, kad es sadalīts saraksts pusē, I did sapludināšanu. Sadaliet sarakstu pusē, do sapludināšanu. Tātad, ja dalot sarakstu var izdarīt log n reizes, un apvienošanās galu galā notiek n soļi, kādi varētu būt tagad augšējais robeža ritošās laiks mūsu algoritmu? n log n. 

Un, protams, ka ir kas mēs esam sasnieguši šeit. Tā justies, ka jūs redzēt vizuāli, kad šie trīs lietas darbojas līdzās ir n kvadrātā pret n brusas pret n log n. Kas pašos mēs redzēsim, ne tikai šodien, bet arī nākotnē, ir daudz, daudz ātrāk. Aplausu kārta šiem puišiem, Es apbalvot tos ar stresa bumbiņām. Pieņemsim šodien atlikt šeit, un mēs redzēt jūs pirmdien.