[Mūzikas atskaņošanas] DAVID Malan: Nu labi. Visas tiesības, welcome atpakaļ. Tātad šī ir nedēļa 4, sākums pantu, jau ir. Un jums atgādināt, ka pagājušajā nedēļā, mēs liekam kodu malā, lai tikai mazliet un mēs sākām runāt nedaudz vairāk augsta līmeņa, par lietām, piemēram, meklēšanu un kārtošanu, kas gan nedaudz vienkāršas idejas, ir pārstāvis klases problēmas jūs varēsiet atrisināt īpaši kā jūs sākat domāt par galīgo projekti un interesanti risinājumi jums varētu būt reālās pasaules problēmas. Tagad burbulis veida bija viens no vienkāršākajiem šie algoritmi, un tas strādāja, ņemot šos nelielu skaitu sarakstā vai masīva veida burbulis savu ceļu uz augšu uz augšu, un lielos skaitļus pārvietot savu ceļu uz leju, lai beigās šajā sarakstā. Un atcerēties, ka mēs varētu iztēloties burbulis šķirot nedaudz kaut kas līdzīgs šim. Tātad, ļaujiet man iet uz priekšu un noklikšķiniet uz Sākt. Esmu iepriekš izvēlēta burbulis šķirot. Un, ja jūs atceraties, ka augstāks zila līnijas veido lielos skaitļus, mazs zilās līnijas veido nelielu skaitu, jo mēs iet caur šo atkal un atkal, un atkal, salīdzinot divas joslas blakus viens otru sarkanu, mēs ejam, lai mijmaiņas lielākais un mazākais, ja tās ir bojātas. Tātad tas iet un iet un iet gada, un jūs redzēsiet, ka lielāks elementi ir padarīt savu ceļu uz pa labi, un mazākās elementi ir padarot savu ceļu pa kreisi. Bet mēs sākām kvantitatīvi efektivitāte, kvalitāte šī algoritma. Un mēs teicām, ka sliktākajā gadījumā, šis algoritms bija aptuveni cik soļus? Tātad n kvadrātā. Un kāda bija n? Mērķauditorija: Elementu skaits. DAVID Malan: Tātad n bija elementu skaits. Un tā mēs darīsim to bieži. Katru reizi, kad mēs vēlamies runāt par lielumu par problēmu vai izmēru ievadi, vai laika daudzums, kas nepieciešams ražot produkciju, mēs vienkārši ģeneralizētas neatkarīgi ievade ir kā n. Tātad atpakaļ 0 nedēļas, numuru lapas tālruņu katalogā bija n. Studentu skaits telpā tika n. Tātad arī šeit, mēs esam pēc ka modelis. Tagad n kvadrātā nav īpaši ātri, tāpēc mēģinājām darīt labāk. Un tā mēs paskatījās pāris citi algoritmi, kuru vidū bija izvēle kārtošanas. Tātad izvēle kārtošanas bija nedaudz atšķiras. Tas bija gandrīz vienkāršāk, es uzdrošinos teikt, , saskaņā ar kuru es sākās sākumā mūsu brīvprātīgajiem sarakstu, un es tikko atkal un atkal un atkal gāja cauri sarakstā, noplūkšanas no mazākā laikā elements, un liekot viņam vai viņas pie saraksta sākumā. Bet tas arī, kad mēs sākām domāt ar matemātiku un lielāks attēlu, domāja par to, cik reizes Man bija iet uz priekšu un atpakaļ un atpakaļ un atpakaļ, mēs teicām, sliktākajā gadījumā, atlase kārtot, arī bija tas, ko? n rūtiņām. Tagad reālajā pasaulē, tas varētu patiesībā var būt nedaudz ātrāk. Jo atkal, man nav, lai saglabātu atteikšanās kad man bija sakārtoti Vismazākās elementi. Bet, ja mēs domājam par ļoti lielu n, un ja jūs veida jādara norādīts math kā I did uz kuģa, ar n kvadrātā mīnus kaut kas, viss pārējais turklāt n brusas, reizi n izpaužas patiešām liels, nav īsti jautājums tik daudz. Tā kā datorzinātnieku, mums sava veida pievērt acis uz mazāku faktori un tikai faktors koncentrēsies izteiksme, kas notiek, lai lielākā atšķirība. Nu, visbeidzot, mēs skatījāmies pēc ievietošanas veida. Un tas bija līdzīgs garā, bet nevis iet cauri iteratīvi un izvēlētos mazāko elementu vienam laiku, es tā vietā veica roku, ka es Tika izskatīts, un es nolēmu, visi labi, jūs piederat šeit. Tad es pārvietots uz nākamo elementu un nolēma, ka viņš vai viņa piederēja šeit. Un tad es pārcēlos vēl un vēl. Un es varētu to, pa ceļam, maiņu šie puiši, lai padarītu telpu par viņiem. Tā, ka bija sava veida garīgo maiņu atlases veida, ka mēs sauc ievietošanas veida. Tātad šie temati rodas reālajā pasaulē. Tikai pirms dažiem gadiem, kad dažas senators skrēja par prezidentu, Eric Schmidt, brīdī, kad vadītājs Google, faktiski bija iespēja intervēt viņu. Un mēs domājam, ka mēs gribētu dalīties ar šo YouTube klipu, lai jūs šeit, ja mēs varētu uzlocīt tilpums. [VIDEO PLAYBACK] -Tagad, senators, jūs esat šeit Google, un man patīk domāt par prezidentūras kā darba interviju. [Smiekli] -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 lūdzam Mūsu kandidāti jautājumi. Un tas viens ir no Larry Schwimmer. [Smiekli] -Jūs guys domāju, ka es esmu kidding? Tas ir labi šeit. Kāds ir visefektīvākais veids, kā šķirot miljons divu bitu integers? [Smiekli] -Nu, uh - -I'm žēl. Varbūt mums vajadzētu - -Nē, nē, nē, nē, nē. -Tas nav - Labi. -Es domāju, ka burbuļa kārtošanas būtu ir nepareizs veids, kā iet. [Smiekli] [Uzmundrinoša un aplausi] -Nāc, kurš viņam šo? Labi. [END VIDEO PLAYBACK] DAVID Malan: Tātad jums ir tā. Tāpēc mēs sākām aprēķināt šos darbojas reizes, tā sakot, ar kaut ko sauc asimptotiskās apzīmējums, kas ir tikai, atsaucoties uz mūsu veida pagrieziena neredzam šos mazākiem faktoriem un tikai meklē braukšanas laikā, sniegumu šiem algoritmiem, kā n izpaužas patiešām liels laika gaitā. Un tā mēs ieviesām liels O. And Big O pārstāv kaut kas mēs domājam no kā augstākā robeža. Un patiesībā, Barry, mēs varam samazināt nekā mic maz bitu? Mēs domājām, ka no tā ir augšējā robeža. Tik liela O no n kvadrātā nozīmē, ka sliktākajā gadījumā, kaut kas līdzīgs atlase kārtošanas varētu veikt n kvadrātā soļus. Vai kaut kas tamlīdzīgs ievietošanas veida būtu n kvadrātā soļi. Tagad kaut ko līdzīgu ievietošanai kārtošanas, kas bija sliktākais? Ņemot vērā masīvs, kas ir sliktākais iespējams scenārijs, ka jūs varētu atrast sev saskaras ar? Tas ir pilnīgi atpakaļ, vai ne? Jo, ja tas ir pilnīgi atpakaļ, jums ir jādara visai daudz darba. Jo, ja jūs esat pilnīgi atpakaļ, jūs gatavojas atrast Lielākā daļa šeit, lai gan tas pieder tur lejā. Tātad jūs gatavojas teikt, visas tiesības pēc šis laika brīdis, jūs piederat šeit, lai jūs atstāt to atsevišķi. Tad tu saproti, ak, damn, man ir pārvietot šo nedaudz mazāks elements, lai kreisi no jums. Tad man ir jādara, ka atkal un atkal un atkal. Un, ja man gāja uz priekšu un atpakaļ, jūs būtu sava veida justies sniegumu ka algoritms, jo pastāvīgi esmu es shuffling visi pārējie noteikti masīvs, lai atbrīvotu vietu tajā. Tātad tas ir sliktākajā gadījumā. Turpretī - un tas bija cliffhanger pēdējo reizi - mēs teicām, ka ievietošana veida bija par to, ko omega? Kas ir labākā lieta iebraukšanu laiks ievietošanas veida? Tātad, tas ir patiešām n. Tas bija tukša, ka mēs pa kreisi uz kuģa pēdējā reize. Un tas ir omega n jo kāpēc? Nu, ļoti labākajā gadījumā, kas ir ievietošanas kārtošanas būs jānodod? Nu, saraksts, kas ir pilnībā sakārtoti jau minimāla jāstrādā. Bet kas ir veikls par ievietošanas veida ir tas, ka tāpēc, ka tas sākas šeit un nolemj, ak, jūs esat numuru viens, jūs piederat šeit. Ak, kāda laime. Tu esi numur divi. Jūs arī piederat šeit. Numurs trīs, vēl labāk, jūs piederat šeit. Tiklīdz tā izpaužas uz beigām sarakstā, par ievietošanas kārtot s pseudocode ka mēs gājām cauri mutiski pēdējo reizi, tas ir darīts. Bet izvēle kārtot, gluži pretēji, tur dara ko? Tur iet cauri sarakstam atkal un atkal un atkal. Jo galvenais ieskats bija tikai kad jūs esat izskatījās visu veidu saraksta beigās var jums būt drošs ka elements izvēlējāties bija patiešām šobrīd mazākais elements. Tātad, šīs dažādās garīgās modeļi beigas līdz iegūstot dažas ļoti reālā pasaule atšķirības, lai mēs, kā arī šīs teorētiskās asimptotiskās atšķirības. Tik vienkārši, lai Atgādinājums, tad liela O no n kvadrātā, mēs esam redzējuši dažas tādas algoritmi līdz šim. Big O n? Kas ir algoritms, kas varētu teikt, ka liels O n? Sliktākajā gadījumā, tas aizņem lineāra skaits no soļiem. Labi, lineāra meklēšanu. Un sliktākajā gadījumā, ja ir elements, jūs meklējat, kad piemērojot lineāru meklēt? Labi, sliktākajā gadījumā, tas nav pat tur. Vai otrajā sliktākajā gadījumā, tas ir visu ceļu beigās, kas ir plus-vai-mīnus vienu soli atšķirība. Tātad, beigās, dienā, mēs varam teikt, tas ir lineāra. Big O n būtu lineāra meklēšanu, jo sliktākajā gadījumā, elements nav pat tur, vai tas ir visu ceļu beigās. Nu, liela O no žurnāla n. Mēs nerunājām ļoti detalizēti par , bet mēs esam redzējuši šo pirms. Kas darbojas ts logaritmiska laiks, sliktākajā gadījumā? Jā, tā bināro meklēšanu. Un bināro meklēšanu sliktākajā gadījumā varētu būt elements kaut kur vidū, vai kaut kur iekšpusē masīvs. Bet jūs tikai atrast to, kad jūs sadalīt sarakstu, uz pusēm, kas puse, uz pusēm, uz pusēm. Un tad voila, tas ir tur. Vai atkal, sliktākajā gadījumā, tas nav pat tur. Bet jūs nezināt, ka tas nav tur līdz jūs veida sasniegt, ka pagājušajā bottom-lielākā daļa elementu, uz pusi samazinot un pusi un pusi. Big O gada 1. Tātad, mēs varētu Big O 2, lielo O 3. Anytime jūs vēlaties tikai konstantu skaitli, mēs vienkārši šķirot, lai tikai vienkāršotu ka kā liels O no 1. Kaut gan, ja reāli, tas aizņem 2 vai pat 100 soļus, ja tas ir pastāvīga virkne pasākumu, mēs tikai pateikt lielu O gada 1. Kas ir algoritms, kas ir lielas O no 1? Mērķauditorija: Meklējot garumu ir mainīgs. DAVID Malan: Meklējot garums ir mainīgs? Mērķauditorija: Nē, garums ja tas jau ir sakārtoti. DAVID Malan: Labi. Labi, tāpēc atrast garumu kaut ja garums, kas kaut ko, piemēram, masīvs, tiek glabāti kādā mainīga. Tāpēc, ka jūs varat vienkārši lasīt mainīgo, vai izdrukāt mainīgo, vai tikai parasti piekļūt šo mainīgo. Un voila, kas prasa pastāvīgu laiku. Turpretī, domāju, ka atpakaļ, lai nesaskrāpētu. Domāt atpakaļ uz pirmajā nedēļā C, zvana tikai printf un drukāšana kaut ko uz ekrāna, ir apstrīdami pastāvīgu laiku, jo tā vienkārši notiek daži skaits CPU ciklu, lai parādītu šis teksts uz ekrāna. Vai gaidīt - tas? Kā gan citādi mēs varbūt modelēt izpilde printf? Vai kāds gribētu nepiekrist, ka varbūt tas nav īsti konstante laiks? Kādā ziņā varētu printf ir palicis laiks, kas faktiski drukāšanas virkni par ekrāns, ir kaut , kas nav konstante. Mērķauditorija: [nedzirdama]. DAVID Malan: Jā. Tātad tas ir atkarīgs no mūsu viedokļa. Ja mēs patiesībā domājam par ieguldījumu printf kā stīgu, un tāpēc mēs novērtējam izmēru, kas ieeja ar savu garumu - tāpēc sauksim ka garums n kā arī - varbūt, printf pati liela O no n tāpēc, ka tas notiek, lai jūs n soļi izdrukāt katru no tiem n rakstzīmes, visticamāk. Vismaz tādā mērā, ka mēs pieņemam ka varbūt tas ir, izmantojot uz cilpas zem motora pārsega. Bet mums būtu apskatīt, ka Kods, lai saprastu labāk. Un tiešām, kad jūs puiši sāk analizējot savus algoritmus, jūs burtiski darīt tieši to. Kārtot ābola savu kodu, un domāju, ka par - labi, man ir šī cilpa šeit vai man ir Nested cilpas šeit, kas gatavojas darīt n lietas n reizes, un jūs varat kārtot saprāta savu ceļu izmantojot kodu, pat ja tas ir pseudocode un nevis faktiskais kods. Tātad, ko par omega no n kvadrātā? , Kas bija algoritmu, kas ir vislabāk gadījumā, vēl bija n kvadrātā soļi? Yeah? Mērķauditorija: [nedzirdama]. DAVID Malan: Tātad izvēle kārtošanas. Jo šo problēmu tiešām ir samazināts ar to, ka no jauna, es nezinu Es esmu atradis pašreizējā mazākais līdz Esmu pārbaudījusi visus darn elementus. Tā omega no, teiksim, n, mēs tikko nāca klajā ar vienu. Ievietošanas kārtošanas. Ja saraksta notiek, ir sakārtoti jau ir, labākajā gadījumā mums vienkārši ir , lai iegūtu vienu iet caur to, kurā brīdī mēs esam pārliecināti. Un tad varētu teikt, ir lineāra, protams. Kas par omega-1? Kas, labākajā gadījumā, varētu veikt pastāvīga vairāki soļi? Tātad lineāra meklēt, ja jūs vienkārši saņemt laimīgs un elements, jūs meklējat ir labi pie saraksta sākumā, ja tas ir, ja jūs, sākot savu lineāra šķērsošana minētajā sarakstā. Un tā ir taisnība, vairākas lietas. Piemēram, pat binārā meklēšana ir omega gada 1. Jo ko tad, ja Jums ir patiešām lāpīt laimīgs un nokrāsa-DAB vidū Jūsu masīvs ir skaitlis jūs meklējat? Tātad jūs varat saņemt laimīgs tur, kā labi. Tas viens, visbeidzot, omega n log n. Tātad n log n, mēs neesam īsti runāt par vēl, bet - Mērķauditorija: Apvienot kārtot? DAVID Malan: Apvienot kārtošanas. Tas bija cliffhanger par pēdējo reizi, kur mēs ierosinājām, un mēs parādījām vizuāli, ka tur ir algoritmi. Un apvienot veida tikai viens šāds algoritmu, kas ir būtiski ātrāk kā daži no šiem citiem puišiem. Faktiski, apvienot īss ir ne tikai Labākajā gadījumā n log n, jo sliktākajā ja n log n. Un, ja jums ir šāda sakritība omega un lielo O ir viens un tas pats? Mēs faktiski var aprakstīt, ka to, kas ir sauc par teta, lai gan tas ir nedaudz mazāk izplatīta. Bet tas tikai nozīmē divas robežas, šajā gadījumā, ir tas pats. Tātad apvienot veida, ko tas tiešām vārīties uz leju, lai mums? Nu, atgādināt motivāciju. Ļaujiet man uzvilkt citu animāciju, ka mēs neesam apskatīt pēdējo reizi. Tas viens, pati ideja, bet tas ir nedaudz lielāks. Un es iešu uz priekšu un norādīt Pirmais - mēs esam ievietošanas secībā augšējā kreisajā pusē, tad izvēle kārtot, burbulis kārtot, pāris citu veidu - čaulas un ātri - ka mēs neesam runājuši par, un kaudzes un apvienot veida. Tātad vismaz mēģināt koncentrēties acis uz top trīs pa kreisi un pēc tam apvienot veida, kad es noklikšķiniet Šī zaļā bulta. Bet es let visi no tiem darbojas, tikai jums sajūtu daudzveidību algoritmi, kas pastāv pasaulē. Es esmu gatavojas let šo skrējienu tikai dažas sekundes. Un, ja jums koncentrēties jūsu acis - izvēlēties algoritms, jākoncentrējas uz to, lai tikai sekundes - jūs sāksiet redzēt raksts, kas tas ir ieviešanas. Apvienot kārtot, paziņojums, tiek darīts. Kaudze kārtot, ātri kārtot, apvalks - tāpēc šķiet, mēs iepazīstināja ar trīs sliktākajā algoritmi pagājušajā nedēļā. Bet tas ir labi, ka mēs esam šodien šeit, lai apskatīt sapludināšanas šķirot, kas ir viens no jo vieglāk tiem ir aplūkot, pat lai gan tas, iespējams, būs saliekt jūsu prātā tikai mazliet. Šeit mēs varam redzēt, cik daudz atlases veida sūkā. Bet par Flip pusē, tas ir ļoti viegli īstenot. Un varbūt par P Set 3, kas ir viens no algoritmi izvēlējāties, lai īstenotu standarta izdevums. Pilnīgi naudas sodu, pilnīgi pareizi. Bet atkal, jo n kļūst liels, ja jūs izvēlas īstenot ātrāku algoritmu patīk apvienot kārtot, izredzes ir lielākas, un lielāki ieguldījumi, jūsu kods ir tikai gatavojas palaist ātrāk. Jūsu mājas lapā ir dodas uz darbu labāk. Jūsu lietotāji būs laimīgāki. Un tāpēc ir šie efekti faktiski dodot mums daži dziļāk domāja. Tātad, pieņemsim apskatīt to, kas apvienojas veida ir patiešām visu par. Cool lieta ir tā, ka apvienot veida ir tikai to. Tas ir, atkal, ko mēs esam sauc pseudocode, pseudocode būtne Angļu-piemēram, sintakse. Un vienkāršība ir veida aizraujošu. Tā par ieejas n elementiem - tā, ka tikai nozīmē, šeit ir masīvs. Tas ir ieguvuši n lietas tajā. Tas ir viss, ko mēs esam sakot tur. Ja n ir mazāks par 2, atgriezties. Tātad tas ir tikai triviāla lieta. Ja n ir mazāks par 2, tad protams, tas ir 1 vai 0, un šajā gadījumā lieta jau ir sakārtoti vai neeksistējošu, tik vienkārši atgriezties. Tur neko darīt. Tātad, tas ir vienkāršs gadījums raut off. Else, mums ir trīs soļus. Kārtot kreiso pusi no elementiem, kārtot tiesības puse no elementiem, un pēc tam apvienot sakārtoti pusītes. Kas ir interesanti ir tas, ka Es esmu veida punting, vai ne? Tur ir sava veida apļveida definīcijas šo algoritmu. Kādā ziņā tas ir algoritms ir definīcija apļveida? Mērķauditorija: [nedzirdama]. DAVID Malan: Jā, mans šķirošana algoritms, divi tās soļiem ir "sava kaut ko. "Un tā, ka lūdzas jautājums, labi, ko es esmu gatavojas izmantot kārtot kreiso pusi un labajā pusē? Un skaistums šeit ir tas, ka, lai gan atkal, tas ir prātā-saliekuma daļu iespējams, jūs varat izmantot pašu algoritmu, lai sakārtotu kreiso pusi. Bet pagaidiet minūti. Kad esat teicis, lai sakārtotu kreisā puse, kas ir divi soļi būs nākamais? Mēs kārtot kreiso pusi kreiso pusi, un labais puse no kreisajā pusē. Sasodīts, kā es varu atrisināt šo divu pusītes, vai ceturtdaļas, tagad? Bet tas ir OK. Mums ir šķirošanas algoritmu šeit. Un, pat ja jūs varētu jāuztraucas Sākumā tas ir sava veida bezgalīgs cilpa, tas ir cikls, kas nekad nav beigsies - tas notiek, lai beidzas, kad, kas notiek? Pēc tam, kad n ir mazāks par 2. Kas galu galā notiks, jo, ja jūs saglabāt pusi un uz pusi samazināt uz pusi samazināt šos pusītes, protams, galu galā jūs gatavojas galu līdzi tikai 1 vai 0 elementiem. Un tajā brīdī, šis algoritms saka, ka jūs esat darīts. Tātad reālā burvju šajā algoritms, šķiet, ir ka pēdējais solis, apvienojot. Šī vienkāršā doma vienkārši apvienojot divas lietas, tas ir to, kas galu galā notiek lai ļautu mums, lai sakārtotu masīvu, teiksim, astoņus elementus. Tāpēc man ir astoņi vairāk stresa bumbas augšu šeit, astoņi gabali no papīra, viens un Google Stikls - kas man, lai saglabātu. [Smiekli] DAVID Malan: ja mēs varētu veikt astoņus brīvprātīgie, un pieņemsim redzēt, ja mēs varam spēlēt šo out, tā. Wow, OK. Datorzinātnes kļūst jautri. Labi. Tātad, kā par jums trīs, Lielākais roku tur. Četri uz muguras. Un kā mēs do you trīs šajā rindā? Un četri priekšā. Tātad jūs astoņi, nākt uz augšu. [Smiekli] DAVID Malan: Es esmu patiešām nav pārliecināts, kas tas ir. Vai tas ir stresa bumbas? Galda lampas? Materiāls? Internets? Labi. Lai nāk uz augšu. Kurš gribētu - glabāt nāk uz augšu. Let 's redzēt. Un tas liek jums vietā - tu esi vienā vietā. Uh-oh, pagaidiet minūti. 1, 2, 3, 4, 5, 6, 7 - oh, labi. Labi, mēs esam labi. Labi, tāpēc ikviens ir vieta, bet ne uz Google Glass. Ļaujiet man rindā šos up. Kāds ir Jūsu vārds? MICHELLE: Michelle. DAVID Malan: Michelle? Labi, jums izskatās geek, ja tas ir OK. Nu, man arī, es domāju, tikai brīdi. Visas tiesības, gaidīšanas režīmā. Mēs esam mēģinājuši nākt klajā ar lietošanas gadījumu Google Glass, un mēs domāju, ka būtu jautri, lai tikai darīt tas, kad cilvēki ir uz skatuves. Mēs ierakstīt pasaulē no viņu viedokļa. Labi. Nav iespējams, ko Google paredzēti. Labi, ja jums nav prātā, valkājot Šī nākamo neveikli minūtes, tas būtu brīnišķīgi. Labi, tāpēc mēs esam šeit masīvs elementi, un tas masīvs, kā vienu papīra gabalus ar šiem ļaudīm " rokas, pašlaik nešķirotu. MICHELLE: Ak, tas ir tik dīvaini. DAVID Malan: Tas ir diezgan daudz izlases. Un tikai brīdi, mēs ejam, lai mēģinātu īstenot apvienot kārtot kopā un redzēt, kur tas galvenais ieskats ir. Un triks šeit ar sapludināšanas veida ir kaut kas, ko mēs neesam pieņemts vēl. Mums tiešām ir nepieciešams zināms papildus vieta. Tātad, kas būs īpaši interesanti par šo ir tas, ka šie puiši gatavojas, lai pārvietotos nedaudz mazliet, jo es esmu gatavojas pieņemt, ka tur ir papildus masīvs vietas, teiksim, tieši aiz viņiem. Tātad, ja viņi aiz sava krēsla, tas ir sekundārais masīvs. Ja viņi sēž šeit, tas ir primārā masīvs. Bet tas ir resurss, kas mums ir nevar pārvirzīt līdz šim ar burbulis kārtot, ar atlases veida, ar ievietošanas veida. Atsaukt pagājušajā nedēļā, visi tikai veida iegrozījās vietā. Viņi neizmantoja nekādas papildu atmiņu. Mēs veicām telpu cilvēkiem, pārvietojas cilvēki apkārt. Tātad tas ir galvenais ieskatu, too. Tur tas ir kompromiss, ka kopumā datorzinātnes, resursu. Ja jūs vēlaties, lai paātrinātu kaut ko piemēram, laiku, jūs gatavojas ir jāmaksā cenu. Un viena no tām cenām, ir ļoti bieži telpa, atmiņas apjomu vai grūti diska vietas, ka jūs izmantojat. Vai arī, godīgi sakot, summa gada programmētājs laika. Cik daudz laika nepieciešams, jūs, cilvēku, lai faktiski īstenotu dažas vairāk sarežģīts algoritms. Bet šodien, kompromiss ir laiks un telpa. Tātad, ja jūs puiši varētu tikai turēt uz augšu savu numurus, lai mēs varam redzēt, ka tu esi patiešām saskaņojot 4, 2, 6, 1, 3, 7, 8. Excellent. Tāpēc es esmu gatavojas izmēģināt, lai orķestrēt lietas, ja jūs guys var tikai sekot manu svina šeit. Tāpēc es esmu gatavojas īstenot, pirmkārt, pirmais solis pseudocode, kas ir par ieejas n elementiem, ja n mazāk nekā 2, tad atgriezties. Protams, ka nav piemērojams, tāpēc mēs virzāmies tālāk. Tātad šķirot kreiso pusi elementiem. Tātad tas nozīmē, ka es esmu gatavojas koncentrēties manu uzmanību tikai brīdi par šo četri puiši šeit. Visas tiesības, ko man nākamo darīt? Mērķauditorija: Kārtot kreiso pusi. DAVID Malan: Tāpēc tagad man ir, lai sakārtotu kreiso pusi no šiem guys. Jo atkal, uzņemas uz sevi ar Mērķis ir sakārtot kreiso pusi. Kā jūs to darīt? Vienkārši sekojiet instrukcijām, pat ja mēs darām to vēlreiz. Tātad šķirot kreiso pusi. Tagad es esmu šķirošana šie divi puiši. Kas būs tālāk? Mērķauditorija: Kārtot kreiso pusi. DAVID Malan: kārtot kreiso pusi. Tāpēc tagad tie, šī vieta šeit, ir saraksts ar apjomu 1. Un kāds ir tavs vārds atkal? PRINCESS DAISY: Princess Daisy. DAVID Malan: Princess Daisy ir šeit. Un tā viņa jau ir sakārtots, jo saraksts ir 1 izmēru. Ko man blakus darīt? Labi, atpakaļ, jo šis saraksts ir izmērs 1, kas ir mazāks par 2. Tad kas ir nākamais solis? Un tagad jums ir sava veida backtrack jūsu prātā. Kārtot pareizo pusi, kas ir - kāds ir tavs vārds? LINDA: Linda. DAVID Malan: Linda. Un tā, ko mēs darām tagad, mums ir saraksts ar apjomu 1? Mērķauditorija: Atgriešanās. DAVID Malan: uzmanīgi. Mēs atgriezties pirmais, un tagad trešais solis - un, ja es veida attēlot to, aptverot divas vietas tagad, tagad es ir apvienot šos divus elementus. Tāpēc tagad, diemžēl, elementi ir bojātas. Bet tas ir, ja apvienošanās process sāk iegūt pārliecinoši. Tātad, ja jūs puiši varētu piecelties, lai tikai brīdis, es esmu gatavojas nepieciešams, lai jūs, jo brīdis, lai soli aiz sava krēsla. Un ja Linda, jo 2 ir mazāks par 4, kāpēc ne jūs nākt apkārt vispirms? Tur uzturēties. Tātad Linda, jūs nākt apkārt vispirms. Tagad, patiesībā, ja tas ir tikai masīvs mēs varētu virzīties viņai reālā laikā no šī krēsla, lai šajā vietā. Tātad, iedomāties, kas notika dažas konstante numurs 1 soļiem. Un tagad - bet mums ir nepieciešams, lai jums pirmā vieta šeit. Un tagad, ja jūs varētu nākt apkārt, , kā arī, mēs ejam, lai tā sastāv no divām atrašanās vietu. Un, pat ja tas uzskata, tāpat kā tas ir ņemot kādu laiku, kas ir jauki, tagad ir ka kreisā puse no kreisā puse tagad ir sakārtots. Tātad, kāds bija nākamais solis, ja mēs tagad attīt tālāk stāsts? Mērķauditorija: labajā pusē. DAVID Malan: kārtot labo pusi. Tātad jūs guys to darīt, kā labi. Tātad, ja jūs varētu piecelties tikai brīdi? Un kāds ir tavs vārds? JESS: Jess. DAVID Malan: Jess. Labi, tāpēc Jess tagad ir pa kreisi puse no labajā pusē. Un tāpēc viņa ir saraksts ar apjomu 1. Viņa acīmredzot sakārtoti. Un Jūsu vārds atkal? MICHELLE: Michelle. DAVID Malan: Michelle ir acīmredzami sarakstu apjomu 1. Viņa jau ir sakārtoti. Tāpēc tagad burvju notiek, apvienošanās process. Tātad, kas notiek, lai brauc, tas pirmais? Acīmredzot Michelle. Tātad, ja jūs varētu nākt apkārt atpakaļ. Telpa mums ir pieejams par viņas tagad tieši aiz šī krēsla šeit. Un tagad, ja jūs varētu nākt atpakaļ, kā arī, mums tagad ir, lai būtu skaidrs, divi pusītes, katrs no 2 izmēru - un tikai tēlojuma dēļ, ja varētu mazliet telpā - viens pa kreisi puse šeit, viens labajā pusē šeit. Attīt tālāk stāstā. Kas solis ir nākamais? Mērķauditorija: Apvienot. DAVID Malan: Tāpēc tagad mums ir apvienot. Tātad Labi, tāpēc tagad, par laimi, mēs tikko atbrīvojušies četri krēsli. Tāpēc mēs esam, ko izmanto divreiz tik daudz atmiņu, bet mēs varam dot flip-flopping starp divi masīvi. Tātad, cik daudz ir jānāk vispirms? Tātad Michelle, protams. Lai nāk apkārt un veikt jūsu vieta šeit. Un tad skaitlis 2 ir acīmredzami Nākamais, lai jūs nākt šeit. 4 numurs, numurs 6. Un atkal, lai gan tur ir Mazliet pastaigas iesaistīts, tiešām, tas varētu notikt uzreiz, pārceļot vienu - Labi, labi spēlēja. [Smiekli] DAVID Malan: Un tagad mēs esam diezgan labā formā. Kreiso pusi no visa ieeja tagad ir sakārtots. Labi, tāpēc šie puiši bija priekšrocība manā - kā to darīja galu galā visas meitenes uz pa kreisi un visi par tiesībām zēni? Labi, tāpēc puiši 'savukārt tagad. Tāpēc es ne staigāt jums caur šie pasākumi. Redzēsim, vai mēs varam atkārtoti pats pseudocode. Ja jūs vēlaties, lai iet uz priekšu un piecelties, un jūs guys, ļaujiet man sniegt jums mic. Skat, ja jūs nevar atkārtot to, ko mēs tikko izdarījām šeit otru galu no saraksta. Kas nepieciešams izteikties vispirms; balstoties uz algoritmu,? Tātad, paskaidrot, ko jūs darāt, pirms veicat jebkādas kāju kustības. SPEAKER 1: Nu labi, tāpēc, ka Es esmu kreisajā pusē kreiso pusi, es atgriezties. Labi? DAVID Malan: Labi. SPEAKER 1: Un tad - DAVID Malan: Kam mic iet uz nākamo? SPEAKER 1: Nākamais numurs. SPEAKER 2: Tāpēc es esmu labajā pusē no kreisajā pusē kreiso pusi, un es atgriezties. DAVID Malan: Labi. Jūs atgrieztos. Tātad, tagad, kas ir nākamais pēc jums abiem? SPEAKER 2: Mēs gribam redzēt, kas ir mazāks. DAVID Malan: Tieši tā. Mēs vēlamies apvienot. Kosmosa mēs spēsim izmantot, lai apvienot tevi, pat ja viņi protams sakārtoti jau mēs ejam ievērot tādu pašu algoritmu. Tātad, kas iet atpakaļ pirmo reizi? Tātad, 3, 7 un pēc tam. Un tagad mic iet lai šie puiši, OK? SPEAKER 3: Tāpēc es esmu labajā pusē no kreisā puse, un mans n ir mazāks nekā 1, tāpēc es esmu tikai gatavojas iet - DAVID Malan: Labi. SPEAKER 4: Es esmu labajā pusē no labajā pusē no labās puses, un es esmu arī viens cilvēks, tāpēc es esmu gatavojas atgriezties. Tāpēc tagad mums apvienoties. SPEAKER 3: Tātad mēs ejam atpakaļ. DAVID Malan: Tātad jūs doties uz muguras. Tātad 5 iet pirmais, tad 8. Un tagad audience, kas ir solis mums ir tagad attīt atpakaļ uz mūsu prātos? Mērķauditorija: Apvienot. DAVID Malan: apvienošana kreisajā pusē un pa labi puse no sākotnējā kreisajā pusē. Tātad tagad - un tikai, lai tas skaidri, padarīt mazliet vietas Starp jums divi puiši. Tāpēc tagad, ka ir divi saraksti, pa kreisi un pa labi. Tātad, kā mēs tagad apvienot jūs guys uz priekšējo sēdekļu rinda atkal? 3 iet pirmais. Tad 5, protams. Tad 7, un tagad 8. Labi, un tagad mēs esam? Mērķauditorija: Nav darīts. DAVID Malan: Nav darīts, jo protams, tur ir viens solis paliek. Bet atkal, iemesls, kāpēc es esmu, izmantojot šo žargons, piemēram, "savā prātā, attīt atpakaļ," tas ir tāpēc, ka tas ir patiešām kas notiek. Mēs ejam cauri visiem šiem soļiem, bet mēs esam sava veida pauzes brīdis, niršana dziļāk algoritms, pauzes uz brīdi, niršanas dziļāk algoritmu, un Tagad mums ir sava veida attīšanas mūsu prāts un atsaukt visus no šiem slāņiem ka mēs esam sava veida aizturēts. Tāpēc tagad mums ir divi saraksti 4 izmēru. Ja jūs puiši varētu piecelties pēdējo reizi un padarīt daudz vietas šeit būtu skaidrs, ka tas ir pa kreisi puse no oriģināla, labajā pusē no oriģināla. Kurš ir pirmais skaitlis, kas mums nepieciešams, lai vilktu uz muguras? Michelle, protams. Tātad mēs ieliekam Michelle šeit. Un kas ir numurs 2? Numurs 2 nāk atpakaļ, kā arī. Numurs 3? Excellent. Skaits 4, skaits 5, skaits 6, skaits 7, un numurs 8. Labi, tāpēc jutos kā daudz pakāpienu, protams. Bet tagad pieņemsim redzēt, ja mēs nevaram apstiprināt veida intuitīvi, ka šis algoritms būtiski, jo īpaši attiecībā n kļūst patiešām liels, kā mēs esam redzējuši ar animācijas, ir būtiski ātrāk. Tāpēc es saņemt šo algoritmu, kas sliktākajā lietu un pat labākajā gadījumā, ir liela O no n reizes log n. Tas nozīmē, ka tur ir dažas no šis aspekts algoritms, kas notiek n pasākumus, bet tur ir vēl viens aspekts, kaut kur ka atkārtojuma, ka looping, ka ņem log n pasākumus. Vai mēs varam nodot mūsu pirkstu uz to, kas tiem divi skaitļi ir domāta? Nu, ja - where'd mic iet? SPEAKER 1: Vai log n ir sadalīšana mūs divās daļās - dalot ar divi, būtībā. DAVID Malan: Tieši tā. Katru reizi, kad mēs redzam kādu algoritmu tādējādi tālu, tur ir bijis šis modelis dalot, dalot, dalot. Un tas parasti ir jāsamazina uz kaut ko, kas ir logaritmiska, log bāze 2. Bet tas tiešām varētu būt kaut kas, bet pieteikties bāze 2. Tagad to, ko par n? Es redzu, ka mēs veida sadalīta jums puiši - sadalīta tevi, sadalīta jums, sadalīta tevi, sadalīta jums. Kur gals nāk no? Tātad, tas ir apvienošanās. Tāpēc, ka domā par to. Kad jūs apvienot astoņi cilvēki kopā, , saskaņā ar kuru puse no tiem ir noteikts četru un otra puse ir vēl viens komplekts no četriem, kā jūs iet par darot apvienojas? Nu, jūs puiši to darīja diezgan intuitīvi. Bet, ja es tā vietā to darīja nedaudz vairāk metodiski, es varētu būt norādīja uz kreisās malas persona pirmo ar manu kreiso No otras puses, norādīja uz kreisās malas personas Šī puse ar savu labo roku, un tikai pēc tam gāja cauri sarakstu, norādot uz mazāko elementu katru reizi, pārvietojas manu pirkstu pāri un vairāk kā nepieciešams visā sarakstā. Bet kas ir galvenais par šo apvienošanu Process ir es esmu Salīdzinot šos pārus no elementiem. No labajā pusē un no kreisās pusi, es esmu nekad vienreiz atteikšanās. Tātad sapludināšanas pati, ņemot ne vairāk nekā N soļus. Un cik reizes bija man to darīt apvienojas? Nu, ne vairāk kā n, un mēs tikko redzēja, ka ar galīgo sapludināšanu. Un tā, ja jūs kaut ko darīt, kas ņem log n soļus n reizes, vai otrādi, tas notiek, lai dotu mums n reizes log n. Un kāpēc tas ir labāks? Nu, ja mēs jau zinām, ka žurnālu n ir labāk nekā n - labi? Mēs redzējām bināro meklēšanu, tālruņa grāmatu Piemēram, log n noteikti bija labāk nekā lineāra. Tātad, kas nozīmē, n reizes log n ir noteikti labāk nekā n reizes otru n, AKA n kvadrātā. Un tas, ko mēs galu galā jūtas. Tik liels kārta aplausi, ja mēs varētu, šiem puišiem. [Aplausi] DAVID Malan: Un jūsu atvadu dāvanas - Jūs varat saglabāt numurus, ja jūs vēlētos. Un jūsu šķiršanās dāvanu, kā parasti. Ak, un mēs nosūtīsim jums kadrus, Michelle. Paldies. Labi. Palīdzēt sevi stresa bumbu. Un ļaujiet man uzvilkt, pa to laiku, mūsu draugs Rob Bowden piedāvāt nedaudz atšķirīgs skatījums uz to, jo jūs varat domāt par šiem pasākumi notiek nedaudz citādā veidā. Faktiski, set-up par to, kas Rob ir par lai parādītu mums, tiek pieņemts, ka mēs esam jau izdarīts dalot up liels saraksts astoņās mazos sarakstos, katrs no 1 izmēru. Tātad, mēs esam mainās pseudocode mazliet tikai, lai kārtotu, kas nokļūt pie galvenā ideja par to, kā apvienot darbu. Bet darba laiks par to, ko viņš gatavojas darīt, ir vēl būs tāds pats. Un atkal, set-up, šeit ir tas, ka viņš ir sākās ar astoņiem sarakstiem apjomu 1. Tātad jūs esat neatbildētos daļa, kur viņš ir faktiski izdarīts log n, log n, log n izdalot no ieejas. [VIDEO PLAYBACK] -Tas ir tas par vienu soli. Par soli diviem, atkārtoti apvienot pārus sarakstos. DAVID Malan: Hm. Tikai audio nāk no mana datora. Mēģināsim to atkal. -Tikai patvaļīgi izvēlēties, kuras - tagad mums ir četri saraksti. Uzziniet pirms tam. DAVID Malan: Tur mēs ejam. -Apvienošana 108 un 15, mēs galu up ar sarakstu 15, 108. Apvienojas 50 un 4, mēs galu galā ar 4, 50. Apvienojas 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 katram četri saraksti ir sakārtoti. Tātad, mēs varam sākt apvienojas pāru sarakstu vēlreiz. Apvienojas 15 un 108 un 4 un 50, mēs vispirms veic 4, tad 15, tad 50, pēc tam 108. Apvienojas, 8, 42 un 16, 23, mēs vispirms veikt 8, tad 16, tad 23, pēc tam 42. Tāpēc tagad mums ir tikai divi saraksti izmēra 4, katrs no kuriem ir sakārtots. Tāpēc tagad mums apvienot šos divus sarakstus. Pirmkārt, mēs ņemam 4, tad mēs 8, tad mēs to 15, tad 16, tad 23, tad 42, tad 50, tad 108. [END VIDEO PLAYBACK] DAVID Malan: Atkal, paziņojums, viņš nekad pieskārās doto tasi vairāk nekā vienu reizi Pēc virzās ārpus tās. Tāpēc viņš nekad atkārtot. Tāpēc viņš vienmēr virzās uz sāniem, un tas, kur mēs saņēmām mūsu n. Kāpēc ne man uzvilkt vienu animāciju ka mēs redzējām agrāk, bet šoreiz koncentrējoties tikai sapludināšanas kārtošanas. Ļaujiet man iet uz priekšu un tuvinātu kas par šo šeit. Vispirms ļaujiet man izvēlēties izlases ievadi, pārspīlēt to, un jūs varat kārtot no redzēt ko mēs ņēmām par pašsaprotamu, agrāk, apvienot veida ir faktiski dara. Tātad ievēroju, ka jūs saņemtu šos pusītes vai šie ceturtdaļas vai tie astotdaļas problēma, ka visi pēkšņi sāk veikt labu formu. Un tad beidzot, jūs redzat pašām beigām, ka bam, viss ir apvienots kopā. Tātad šie ir tikai trīs dažādi uzņemas to pašu ideju. Bet galvenais ieskatu, tāpat kā plaisa un iekarot jau pirmajā klasē, bija tas, ka mēs nolēmām kaut kā sadalīt problēma par kaut ko lielu, stājās kaut veida identisks garā, bet mazākas un mazākas un mazākas un mazākas. Tagad cita jautri veids, kā sakārtot of domāt par šiem, pat ja tas nav gatavojas sniegt jums pašu intuitīvi izpratne, ir šādas animācija. Tātad šis ir video kāds salikt kopā kas saistīti dažādi skaņas ar dažādām darbībām, lai ievietošanas kārtot, lai sapludināšanas kārtot, un par pāris citiem. Tātad brīdī, es esmu gatavojas hit Atskaņot. Tas ir par minūti garš. Un, pat ja jūs varat redzēt modeļi notiek, šoreiz jūs varat arī dzirdēt, kā šie algoritmi veicot atšķirīgi un ar nedaudz atšķirīgus. Tas ir ievietošanas veida. [TONES SPēLES] DAVID Malan: Tas atkal mēģina ievietot katrs elements vērā, ja tā pieder. Tas ir burbulis veida. [TONES SPēLES] DAVID Malan: Un jūs varat kārtot ar jūtas cik salīdzinoši maz darba, ka tas dara uz katra soļa. Tas ir tas, ko garlaicības izklausās. [TONES SPēLES] DAVID Malan: Šī ir izvēle kārtot, kur mēs izvēlētos elementu, ko mēs gribam, ko iet cauri atkal un atkal, un atkal un nodot to sākumā. [TONES SPēLES] DAVID Malan: Tas ir apvienot veida, kas Jūs tiešām var sākt justies. [TONES SPēLES] [Smiekli] DAVID Malan: Kaut ko sauc rūķis kārtot, ko mēs neesam paskatījās. [TONES SPēLES] DAVID Malan: Tātad, ļaujiet man redzēt, tagad, apjucis kā jūs cerams, jau pēc mūzika, ja es varētu paslīdēt nedaudz mazliet math šeit. Tātad tur ir Ceturtais veids, ka mēs varam domāt par to, ko nozīmē šie funkcijas, ir ātrāk, nekā tie, ka mēs esam redzējuši iepriekš. Un, ja jūs nāk pie kursu no matemātikas fona, jūs zina, varbūt jau ka tu var iepļaukāt termiņu par šo tehniku ​​- proti rekursijas, funkcija ka kaut sauc sevi. Un atkal, atgādinām, ka sapludināšanas veida pseudocode bija rekursīvs tādā ziņā, ka viens no sapludināšanas kārtot s soļiem bija zvanīt veida - kas ir, pats par sevi. Bet par laimi, jo mēs tur zvana veida, vai apvienot kārtot, konkrēti, uz mazākas un mazākas un mazāku sarakstu, mēs galu galā dibenu, pateicoties to, ko mēs saucam bāzes scenārijs, iekodēts lieta, ka teica, ja saraksts ir neliels, mazāk nekā 2 šajā gadījumā, tikai atpakaļ nekavējoties. Ja mums nebūtu šo īpašo gadījumu algoritms nekad jākrītas, un jūs tiešām nokļūt bezgalīga cilpa patiesi uz visiem laikiem. Bet pieņemsim, ka mēs vēlējāmies tagad nodot daži par šo numuru, atkal, izmantojot n kā lielums ievadi. Un es gribēju jautāt jums, kas ir kopējais laiks iesaistīts darbojas sapludināšanas kārtot? Vai, plašākā nozīmē, kas ir izmaksas par to laiku? Nu tas ir diezgan viegli noteikt, ka. Ja n ir mazāks par 2, laiks iesaistīts šķirošanas n elementus, kur n ir 2, ir 0. Tāpēc, ka mēs vienkārši atgriezties. Nav darāmā. Tagad varbūt, varbūt tas ir viens solis vai divas soļi, lai noskaidrotu apjomu strādāt, bet tas ir pietiekami tuvu 0, ka Es esmu tikai gatavojas teikt darbs nav nepieciešams, ja saraksts ir tik mazs , kas neinteresantas. Bet šī lieta ir interesanta. Rekursīvas gadījums bija filiāle pseudocode kas teica cits, kārtot kreiso pusi, šķirot tiesības pusi, apvienot abas pusītes. Tagad, kāpēc šī izteiksme pārstāv ka izdevumi? Nu, T n tikai nozīmē, laiks, lai sakārtotu n elementiem. Un pēc tam uz labajā pusē vienādības zīme tur, no n T dala ar 2 atsaucas uz izmaksām, ko? Šķirošana kreiso pusi. Otru n T dalīts ar 2 ir iespējams, atsaucoties uz izmaksām šķirot labo pusi. Un pēc tam, kā arī n? Vai apvienojas. Jo, ja jums ir divi saraksti, kas ir viens no izmēru vairāk nekā 2 n un citu lieluma n vairāk nekā 2, jums ir būtībā pieskarties katram no šiem elementiem, tāpat kā Rob pieskārās katram bļodiņu, un tikai kā mēs norādīja uz katru no brīvprātīgie uz skatuves. Tātad n ir rēķina apvienošanu. Tagad diemžēl, šī formula ir arī pati rekursīvs. Tātad, ja uzdeva jautājumu, ja n ir, teiksim, 16, ja tur ir 16 cilvēki uz skatuves vai 16 kausi video, cik kopā soļi tas veic, lai sakārtotu tos ar sapludināšanas veida? Tas tiešām nav skaidra risinājuma, jo tagad jums ir sava veida rekursīvi atbildēt uz šo formulu. Bet tas ir OK, tāpēc ļaujiet man piedāvāt ka mēs šādi. Laiks iesaistīties, lai sakārtotu 16 cilvēkiem vai 16 kausi būs pārstāvētas parasti kā T gada 16. Bet tas ir vienāds, saskaņā ar mūsu Iepriekšējā formula, 2 reizes summu laiku, kas nepieciešams, lai kārtotu 8 glāzes plus 16. Un atkal, 16 plus ir laiks apvienoties, un divas reizes T no 8 ir laiks, lai sakārtotu kreiso pusi un labo pusi. Bet atkal, tas nav pietiekami. Mums ir ienirt dziļāk. Tas nozīmē, ka mums ir jāatbild Jautājums, kas ir T gada 8? Nu T gada 8 ir tikai 2 reizes T no 4 plus 8. Nu, kas ir T 4? T no 4 ir tikai 2 reizes T no 2 plus 4. Nu, kas ir T 2? T 2 ir tikai 2 reizes T 1 plus 2. Un atkal mēs esam veida, kā iegūt iestrēdzis šajā ciklā. Bet tas ir par hit, ka tā saukto vispārējo gadījumu. Jo kas ir T 1, vai mēs apgalvot? 0. Tātad beidzot, mēs varam strādāt atpakaļ. Ja T no 1 ir 0, es tagad var iet atpakaļ uz augšu viens rindā uz šo puisis šeit, un es varu iespraudiet 0 t 1. Tātad tas nozīmē, ka tā atbilst 2 reizes nulles, citādi pazīstams kā 0, 2 plus. Un tā, ka visa izteiksme ir 2. Tagad, ja es ņemtu T 2, kura atbilde ir 2, plug to viduslīnijas, T gada 4, kas dod man 2 reizes 2 plus 4, tā 8. Ja es pēc tam plug 8 līdz iepriekšējā līnija, kas dod man 2 reizes 8, 16. Un, ja mēs pēc tam turpināt, ka ar 24, pievienojot 16, mēs beidzot nokļūt vērtība no 64. Tagad, ka pati par sevi veida runā nekas līdz n apzīmējums, Big O, omega, ka mēs esam runājam par. Bet izrādās, ka 64 ir patiešām 16, izmērs no ieejas, log no 16 2 bāzi. Un, ja tas ir mazliet svešs, tikai domāju, ka atpakaļ, un tas būs nāk atpakaļ jums galu galā. Ja tas ir log bāze 2, tas ir tāpat kā 2 izvirzīts uz ko jums dod 16? Ak, tas ir 4, tāpēc tas ir 16 reizes 4. Un atkal, tas nav liels galā, ja tas ir sava veida miglaina atmiņas tagad. Bet tagad, ņem uz ticību ka 16 log 16 ir 64. Un tik tiešām, ar šo vienkāršo veselība pārbauda, ​​mēs esam apstiprināta - bet izrādījās formāli - ka darbības laiks sapludināšanas veida ir patiešām n log n. Tātad nav slikti. Tas noteikti ir labāk nekā algoritmi mēs esam redzējuši līdz šim, un tas ir tāpēc, ka mēs esam parādi, viens, tehniku, ko sauc rekursija. Bet vēl interesantāka nekā tas, ka jēdziens dalot un iekarošana. Atkal, patiesi nedēļa 0 sīkumi, ka pat tagad ir atkārtošanos vairāk pārliecinoša veidā. Tagad fun maz izmantot, ja jūs esat nekad nav izdarījusi - un jūs, iespējams, nebūtu, jo sava veida normāli cilvēki nedomā to darīt. Bet, ja es eju uz google.com un, ja Es gribu, lai uzzinātu kaut ko par rekursijas, Enter. [Smiekli] [Vairāk smiekli] DAVID Malan: Slikti joks lēnām izplatās. [Smiekli] DAVID Malan: Tikai gadījumā, tas ir tur. Man nav izskaidrot to nepareizi, un tur ir joks. Labi. Izskaidrot to, lai cilvēki blakus jums, ja tas nav gluži uzklikšķināt tikai yet. Bet rekursijas, plašākā nozīmē, attiecas procesam funkciju zvana pats, vai, plašākā nozīmē, dalot problēma, par kaut ko, kas var būt atrisināt savstarpēji nesaistīti, risinot identiskas pārstāvis problēmas. Nu, pieņemsim mainīt rīkiem tikai brīdi. Mēs vēlētos, lai izbeigtu par dažiem cliffhangers, tāpēc sāksim uzstādīt posms, vairākas minūtes, uz ļoti vienkāršu ideju - ka pārnešana diviem elementiem, vai ne? Visi šie algoritmiem, mēs esam bijuši runājot par pēdējo pāris lekcijas ietver dažus veida pārnešana. Šodien tā ir vizualizēta ar viņiem kļūst up no saviem krēsliem un staigā, bet kodu, mēs būtu tikai ņemt elements no viena masīva un plunkšķis to uz citu. Tātad, kā mēs iet par to izdarīt? Nu, ļaujiet man iet uz priekšu un rakstīt ātrs programma šeit. Es iešu uz priekšu un darīt Tas kā tālāk. Sauksim šo - Ko mēs gribam, lai izsauktu šo vienu? Patiesībā, nē. Ļaujiet man attīt. Es nevēlos to darīt cliffhanger vēl. Tas būs sabojāt fun. Darīsim to vietā. Pieņemsim, ka es gribu uzrakstīt nedaudz programma, un ka tagad aptver šis Ideja par rekursijas. I veida got priekšā sevi tur. Es esmu gatavojas veikt šādas darbības. Pirmkārt, ātrs ietver standarta io.h, kā arī ietvert cs50.h. Un tad es iešu uz priekšu un atzīt int galvenais spēkā neesošu parastajā veidā. Es sapratu, ka es esmu misnamed failu, tāpēc ļaujiet man vienkārši pievienojiet. c pagarinājumu šeit, lai ka mēs varam apkopot to pareizi. Sākt šo funkciju off. Un funkcija es gribu rakstīt, gluži vienkārši, ir viens, kas prasa par vairākiem lietotāju un pēc tam pievieno uz augšu visi skaitļi starp ka numuru un, teiksim, 0. Tātad vispirms es iešu uz priekšu un atzīt int n. Tad es kopēt kādu kodu, kas mēs esam, ko izmanto uz brīdi. Kamēr kaut kas ir patiess. Es atnākšu atpakaļ, ka brīdi. Ko es gribu darīt? Es gribu teikt printf pozitīvu skaitlis lūdzu. Un tad es esmu gatavojas saka n izpaužas saņemt int. Tātad vēlreiz, daži tekstveidnes kodu ka mēs esam, ko izmanto iepriekš. Un es esmu gatavojas darīt bet n ir mazāk nekā 1. Tātad, tas nodrošinās, ka lietotājs dod man vesels pozitīvs skaitlis. Un tagad es esmu gatavojas darīt šādi. Es gribu, lai saskaitītu visus numurus starp 1 un un n, 0 vai un n, līdzvērtīgi, lai iegūtu kopējo summu. Tik liels sigma simbolu ka jūs varētu atcerēties. Tāpēc es esmu gatavojas darīt to pēc pirmā zvana funkcija sauc sigma, iet to n, un tad es esmu gatavojas saka printf, atbilde ir tiesības tur. Tātad, īsi sakot, man un int no lietotāja. Es nodrošinātu, ka tā ir pozitīva. Es apliecinu, mainīgo sauc atbildi tipa int un uzglabāt tajā atgriešanās vērtība sigma, garāmejot n kā priekšnodokli. Un tad es izdrukāt šo atbildi. Diemžēl, lai gan sigma izklausās kā kaut kas varētu būt math.h failu, savu deklarāciju, tas faktiski nav. Tātad tas ir OK. Es varu īstenot šo sevi. Es esmu gatavojas īstenot sauc funkciju sigma, un tas notiek, lai parametrs - pieņemsim tikai sauc to m, tikai tāpēc tas ir atšķirīgs. Un tad šeit, es esmu gatavojas teikt, labi, ja m ir mazāk nekā 1 - tas ir ļoti neinteresanti programmu. Tāpēc es esmu gatavojas iet uz priekšu un nekavējoties atdod 0. Tas vienkārši nav jēgas, lai pievienotu up visu skaitļi no 1 līdz m, ja m pati ir 0 vai negatīvs. Un tad es iešu uz priekšu un darīt to ļoti iteratīvi. Es esmu gatavojas darīt šāda veida vecās skolas, un es iešu uz priekšu un teikt, ka es esmu gatavojas atzīt kāda summa ir 0. Tad es esmu nāksies lai cilpa int - un ļaujiet man darīt to, kas atbilst mūsu sadales kodu, tāpēc jums ir kopiju mājās. int i izpaužas 1 gada līdz i ir mazāks par vai vienāds ar m. i plus plus. Un tad iekšpusē tā, lai cilpa - mēs esam gandrīz tur - Summa izpaužas summu plus 1. Un tad es esmu gatavojas atgriezties summu. Tāpēc es darīju to ātri, diezgan protams. Bet atkal, galvenā funkcija ir diezgan vienkārši, pamatojoties uz kodu, kuru mēs esam rakstīts līdz šim. Izmanto dubulto cilpu, lai iegūtu pozitīvu int no lietotāja. Es tad iet, ka int uz jaunu funkciju sauc sigma, aicinot to, atkal, n. Un es glabāt atgriezto vērtību, atbilde No melnās kastes patlaban pazīstams kā sigma, jo mainīgo sauc par atbildi. Tad es to izdrukāt. Ja mēs tagad turpināt stāstu, cik ir sigma īstenots? Es ierosinu, lai īstenotu šādi. Pirmkārt, mazliet kļūdas kontrolpārbaudes lai pārliecinātos, ka lietotājs nav messing ar mani un garāmejot daži negatīvs vai 0 vērtības. Tad es deklarēt sauc mainīgo Apkopojot un noteikt to līdz 0. Un tagad man sāk pāriet no i vienāds 1 visu ceļu līdz pat un ieskaitot m, jo es gribu, lai iekļautu visus skaitu no viena līdz m, ieskaitot. Un iekšpusē šis cilpas, es tikai darīt Summa izpaužas kāds tas ir tagad, plus I vērtība. Plus vērtība no i. Kā malā, ja jūs esat nav redzējis šo pirms, tur ir dažas sintaktisko cukura uz šīs līnijas. Es varu pārrakstīt šo kā arī vienāds i, tikai, lai saglabātu sev dažus taustiņsitienus un izskatās mazliet vēsākas. Bet tas arī viss. Tas ir funkcionāli pats. Diemžēl, šis kods ir nav gatavojas sastādīt vēl. Ja es palaist darīt sigma 0, cik am Es gatavojas saņemt kliedza uz? Kas tas būs nepatīk? Mērķauditorija: [nedzirdama]. DAVID Malan: Jā, man nav deklarējis funkcija up top, labi? C ir sava veida stulba, ar to, ka tā tikai dara to, ko jums pateikt to, ko darīt, un jūs ir darīt to šādā secībā. Un tāpēc, ja es hit Enter šeit, es esmu gatavojas saņemt par sigma brīdinājums netieši deklarācija. Ak, nav problēmu. Es var iet uz augšu uz augšu, un es var saka, labi, pagaidiet minūti. Sigma ir funkcija, kas atgriež int un tā sagaida, int kā ievade, semikolu. Vai es varētu likt visu funkciju Iepriekš galvenais, bet kopumā, es gribētu iesaka pret to, jo tas ir jauki, vienmēr ir galvenais augšā tā Jūs varat nirt tiesības un zina, ko Programma dara, lasot galveno pirmās. Tātad, tagad ļaujiet man notīrītu ekrānu. Pārtaisīt sigma 0. Viss, šķiet, lai pārbaudītu out. Ļaujiet man palaist sigma 0. Pozitīva cita. Es došu to skaitu 3, lai saglabātu tā vienkārši. Tā, ka vajadzētu dot man 3 plus 2 plus 1, tā 6. Enter, un patiešām man 6. Es varu darīt kaut ko lielāku - 50, 12, 75. Tāpat kā pieskari, es esmu gatavojas darīt kaut ko smieklīgu, piemēram, ļoti liels numuru, Ak, kas faktiski izstrādāta - eh, es nedomāju, ka ir labi. Let 's redzēt. Let 's tiešām sajaukt ar to. Tas ir problēma. Kas notiek? Kods nav tik slikti. Tas joprojām ir lineāra. Whistling ir labs efekts, lai gan. Kas notiek? Nav pārliecināts, vai es dzirdēju to. Tātad izrādās, - un tas ir kā malā. Tas ir ne kodols, lai Ideja par rekursijas. Izrādās, jo es cenšos pārstāvēt tik liels skaits, lielākā daļa iespējams, tas tiek nepareizi ar C kā nav pozitīvu skaitli, bet negatīvs skaitlis. Mēs esam nav runājuši, bet tas Izrādās, tur ir negatīvie skaitļi pasaulē papildus uz pozitīviem skaitļiem. Un līdzekļus, ar kuriem jūs varat pārstāvēt negatīvu skaitli būtībā ir, jūs izmantojat vienu īpašu bit norādīt pozitīvi nekā negatīvi. Tas ir nedaudz sarežģītāka nekā, bet tas ir pamata ideja. Tātad, diemžēl, ja C ir mulsinoši vienu no tiem kā reāli nozīmē biti, ak, tas ir negatīvs skaitlis, mana cilpa Šeit, piemēram, ir faktiski nekad nav gatavojas pārtraukt. Tātad, ja es faktiski drukāšanas kaut atkal un atkal, mēs būtu redzēt visai daudz. Bet atkal, tas ir papildus punktu. Tas ir patiešām vienkārši veida zinātkāres, ka mēs nāksim atpakaļ beidzot. Bet tagad, tas ir pareizs īstenošanu, ja mēs pieņemam, ka lietotājs sniegs Ints kas iederas ints. Bet es apgalvo, ka šis kods, atklāti sakot, varētu izdarīt tik daudz vienkāršāk. Ja pie rokas mērķis ir veikt vairākus , piemēram, m un pievienot up visi no skaitļi starp to un 1 vai otrādi starp 1 un tas, es pretenziju ka es varētu aizņemties šo ideju, kas apvienojas kārtot bija, kas ir lietojis problēmu Šāda izmēra un dalot to uz kaut ko mazāku. Varbūt ne pusi, bet mazāks, bet reprezentatīva pats. Pati ideja, bet mazāka problēma. Tāpēc es esmu faktiski - ļaujiet man ietaupīt šo failu ar atšķirīgu versijas numuru. Mēs saucam šo versiju 1, nevis 0. Un es apgalvot, ka es faktiski var reimplement tas šāda veida prātā saliekuma veidā. Es esmu gatavojas atstāt daļu no tā vien. Es esmu gatavojas teikt, ja m ir mazāks par vai pat vienāds ar 0 - Es esmu tikai būs nedaudz vairāk anālais šoreiz ar manu kļūdu pārbaudi - Es iešu uz priekšu un atpakaļ 0. Šī ir patvaļīga. Es esmu vienkārši izlemt, ja lietotājs dod man negatīvu skaitli, es esmu atgriežoties 0, un tie būtu jālasa dokumentāciju ciešāk. Pārējais - paziņojums, ko es esmu gatavojas darīt. Vēl es esmu gatavojas atgriezties m plus - kas ir sigma no m? Nu, sigma no m plus m mīnus 1, plus m mīnus 2, plus m mīnus 3. Es nevēlos rakstīt visu šo out. Kāpēc ne es tikai punt? Rekursīvi zvanu sevi ar nedaudz mazāka problēma, semikols, un sauc to dienu? Labi? Tagad arī šeit, jūs varētu justies, vai jāuztraucas ka tas ir bezgalīga cilpa, kas es esmu pamudināt, kuru es esmu ieviešanas sigma, izsaucot Sigma. Bet tas ir pilnīgi OK, jo es domāju uz priekšu, pievieno kuras pozīcijas? Mērķauditorija: [nedzirdama]. DAVID Malan: 23.-26, kas ir mana ja nosacījums. Jo to, kas ir jauka par atņemšanu šeit, jo es glabāt pasniegtas sigma mazākas problēmas, mazākas problēmas, mazākas - tas nav uz pusi mazāks. Tas ir tikai bērns solis mazāks, bet tas ir OK. Jo galu galā, mēs darbu mūsu ceļu uz leju, uz 1 vai 0. Un, kad mēs hit 0, sigma nav saukšu sevi vairs. Tas notiek, lai uzreiz atgrieztos 0. Tātad efekts, ja jūs veida vēja šis up jūsu prātā, ir pievienot m plus m mīnus 1, plus m mīnus 2, plus m mīnus 3, kā arī dot, dot, dot, m mīnus m, beidzot sniedzot jums 0, un efekts ir galu galā pievienot visus šīs lietas kopā. Tāpēc mums nav, ar rekursijas, atrisināt problēmu, ka mēs nevarētu atrisināt agrāk. Patiešām, versija 0 par šo, un ik problēma līdz šim ir bijusi atrisināmas ar tikai izmantojot, cilpas vai kamēr cilpas vai līdzīgas konstrukcijas. Bet rekursijas, es daresay, dod mums atšķirīgs veids, kā domāt par problēmas, kuru, ja mēs varam veikt Problēma, sadalīt to no kaut kā diezgan liela kaut gan ierobežota mazāks, es apgalvot, ka mēs varam atrisināt varbūt nedaudz vairāk eleganti ziņā no dizaina, ar mazāk kodu, un varbūt pat novērst problēmas, kas varētu būt grūtāk, jo mēs galu galā skat, risinot tīri iteratīvi. Bet cliffhanger, ka es to darīju vēlaties atstāt mums bija šī. Ļaujiet man iet uz priekšu un atvērt up failu no - faktiski, ļaujiet man iet un izdarītu reālu ātri. Ļaujiet man iet uz priekšu un ierosināt punktu. Starp šodienas kods ir šo failu šeit. Tas viens šeit, noswap. Tātad šī ir stulba maz programmu, kas Es saputota up, kas apgalvo, ka darīt punktu. Jo galvenais, tā pirmo reizi paziņo int sauc x un piešķir tai vērtība no 1. Tad tas paziņo, int y un piešķir tam vērtību 2. Tad tas izdrukā kādi x un y ir. Tad tas saka, pārnešana, dot dot dot. Tad tas apgalvo, ka ir zvana funkciju sauc swap, iet uz x un y, ideja, kas ir kas, cerams, x un y nāks atpakaļ atšķirīgs, pretī. Tad tas apgalvo nomainīju! ar izsaukuma zīmi. Tad tas izdrukā x un y. Bet izrādās, ka tas ir ļoti vienkārši demonstrācija uz leju šeit ir faktiski buggy. Kaut arī es esmu atzīts pagaidu mainīga un īslaicīgi liekot uz tā, tad es esmu pārcelšanu citā amatā vērtība, b - kas jūtas pamatoti, jo es esmu saglabāts kopiju, kas temp. Tad es atjaunināt b uz vienlīdzīgu kāds bija temp. Šī veida čaulu spēli pārvietojas uz b un b vērā, izmantojot šo vidējā cilvēks sauc temp jūtas pilnīgi pamatota. Bet es apgalvo, ka tad, kad es palaist šo kods, kā es darīšu tagad - ļaujiet man iet uz priekšu un ielīmēt to šeit. Es aicinu šo noswap.c. Un, kā liecina nosaukums, tas nav būs pareizs programmu. Padarīt noswap / nē mijmaiņas.. x ir 1, y ir 2, pārnešana, samainās. x ir 1, y ir 2. Tas ir pilnīgi nepareizi, pat lai gan tas šķiet pilnīgi saprātīgi mani. Un tur ir iemesls, bet mēs neesam gatavojas atklāt iemeslu tikai yet. Tagad otro cliffhanger es gribēju atstāt jūs ar ir tas, paziņojums par veidu par kupona kodu. Mūsu inovācija vēlu dienu šogad ir izraisījusi ne-triviāls numuru jautājumu, kas bija nav mūsu mērķis. Nodoms šo kuponu kodiem, saskaņā ar kuru, ja jums ir daļa no problēmas noteikti agri, tādējādi iegūt papildus dienu, bija patiešām palīdzēt jums guys palīdzēt pats sāk agri, kārtot par ko incentivizing jums. Mums palīdz sadalīt slodzi starp darba laiks labāk tā, ka tas ir sava veida win-win. Diemžēl, es domāju, ka manas instrukcijas nav bijuši līdz šim, ļoti skaidrs, tāpēc Es devos atpakaļ šīs nedēļas nogalē, un atjaunināts spec lielāks, drosmīgāki tekstu izskaidrot lodes, piemēram, šo. Un tikai teikt to vēl publiski, ar noklusējuma, problēmu kopas ir saistīts ceturtdiena pusdienlaikā, par mācību programmu. Ja jūs sākat agri, apdares daļa problēma, kas līdz trešdienai pulksten 12:00 PM, daļu, kas attiecas uz kuponu kods, ideja ir, ka jūs varat paplašināt Jūsu termiņš P noteikts līdz piektdienai. Kas ir, mazliet off tiny daļu no P noteikts, salīdzinot ar to, kas parasti ir lielāka problēma, un jūs pērkat sev papildus dienu. Atkal, tas izpaužas jums domāt par problēma, kas, izpaužas jums darba laiks ātrāk. Bet kupona kods problēma joprojām nepieciešams, pat ja jums nav jāiesniedz to. Bet vēl pārliecinoši tas ir. (STAGE WHISPER) Un tiem ļaudīm, atstājot Jau ir gonna žēl to. Tā kā ir uz balkona ļaudīm. I atvainojos iepriekš ļaudīm, par balkons tādu iemeslu dēļ, kas būs skaidrs tikai brīdi. Tātad, mums ir paveicies, lai būtu viens no CS50 ir bijušie direktoru vietnieki mācību puiši pie kompānija sauc dropbox.com. Viņi ir ļoti dāsni ziedojuši kupona kods, šeit par šo daudz vietas, , kas ir izveidota no ierastie 2 gigabaitiem. Tātad, ko es domāju, ka mēs varētu darīt par to gala piezīmi, ir darīt mazliet giveaway, saskaņā ar kuru tikai brīdi, mēs atklās uzvarētājs un kurš ir kuponu kodu, tad varat doties uz viņu mājas lapā, ierakstiet to, un voila, iegūt kopumā daudz vairāk Dropbox vietas jūsu ierīces un jūsu personas lietas. Un pirmais, kurš vēlētos piedalīties Šajā zīmējumā? Labi, tagad, kas padara to vēl vairāk jautrības. Persona, kas saņem šo 25 gigabaitu kupona kods - kas ir tālu vairāk pārliecinoša par vēlu dienas tagad, varbūt - ir viens, kurš sēž uz augšu sēdekļa spilvenu, zem kuras ir ka kupona kodu. Jūs tagad var meklēt zem Jūsu sēdekļa spilvenu. [VIDEO PLAYBACK] -Viens, divi, trīs. [Kliedz] -Jūs saņemsiet auto! Jūs saņemsiet automašīnu! DAVID Malan: Redzēsim Jūs trešdien. -Jūs saņemsiet auto! Jūs saņemsiet automašīnu! Jūs saņemsiet automašīnu! Jūs saņemsiet automašīnu! Jūs saņemsiet automašīnu! DAVID Malan: Balkons ļaudīm, nāc lejup šeit uz priekšu, kur mums ir ekstras. -Ikviens izpaužas auto! Ikviens izpaužas automašīnu! [END VIDEO PLAYBACK] Teicējs: Nākamajā CS50 - SPEAKER 5: Ak mans Dievs Dievs Dievs Dievs Dievs Dievs Dievs Dievs Dievs Dievs - [UKELELE spēlē]