GARSIAKALBIS: Gerai, tai yra CS50. Tai savaitės trijų pabaigoje, ir, jei turite ne pasinaudojo jau, žinau, kad ten bus pietūs šį penktadienį, kaip įprasta, kur jūs galite mėgautis geras pokalbis ir maisto tuo Priešgaisrinės apsaugos ir ledo su kai kuriais iš CS50 s darbuotojai ir klasiokais. Eikite į šį URL čia. 

Dabar tu gali prisiminti, ar jūs greitai gali būti susipažinę su, šie dalykai čia, kurios išduodamos pabaigoje iš daugelio klasių semestrą. Vadinamasis egzamino mėlynos knygos, kurioje rašote savo atsakymus į egzaminus. Dabar aš turiu čia 26 tokių mėlynos knygos, apie kiekvieną iš jų parašyta pavadinimą, nuo A iki Z. Ir iš tikrųjų pavadinimai yra taip paprasta, per Z. Ir vienas iš po ranka šiandien tikslai bus toliau, ką mes prasidėjo pirmadienį, kuris yra ne tiek daug žiūri kodą, bet tikrai ieško idėjų ir problemų sprendimo. Vienas iš tikslų, ir pažadai šį kursą yra išmokyti jus mąstyti atsargiai, daugiau metodiškai, ir efektyviau spręsti problemas. Ir iš tiesų, mes galime padaryti, kad tikrai net neliesdamas kodo eilutę. Taigi turiu dramblių pora čia šiandien, oranžinė ir mėlyna, jei mes galime gauti vieną savanorį, gal iš toliau atgal nei įprasta. Kaip apie teisę ten, nagi žemyn. Kurių tikslas bus į padėti plius administruoti šį egzaminą čia. Koks tavo vardas? 

PUBLIKA: Mary Beth. GARSIAKALBIS: Mary Beth, nagi iki. Leiskite gauti mikrofoną čia jums. Nice to meet you. 

PUBLIKA: Nice to meet you. GARSIAKALBIS: Gerai, kad turiu čia mėlyna knygos iki Z, ir aš ruošiuosi apsimesti, kad Aš turiu vieną iš mokinių, ir jie ateina šiek tiek atsitiktinai pasibaigus trijų valandų egzaminą bloko pabaigos, todėl jie baigiant kai pusiau atsitiktine tvarka, kaip šis. Dabar jūsų darbas tik akimirką vyksta į be-- iš tikrųjų tai yra, kaip jie gauti sužaidė pabaigoje klasė, greičiausiai. Jūsų darbas dabar bus gana tiesiog, rūšiuoti šiuos mėlynus knygas mus nuo A iki Z. 

PUBLIKA: O, tai yra ketina imtis amžinai. 

GARSIAKALBIS: Ir mes žiūrėti kaip jums tai padaryti, jokio spaudimo. PUBLIKA: Ne, jokio spaudimo arba nieko. 

GARSIAKALBIS: Ir smagu, tegul supakuoti laikmatį. 

PUBLIKA: Labai smagu, taip smagu. 

GARSIAKALBIS: galiu turėti mikrofoną už jus. Gerai, mes ką tik dvigubai mūsų greitį. Taigi tuo metu, leiskite man kelia tai, kas bus už Mary Beth klausimas yra tai, ką ji daro, kaip yra ji vyksta apie sprendžiant tai? Ir iš tiesų, jūs galite neturėti kada nors galvojote apie tai, kas taip paprasta, kaip kai jūs pasirenkate iki 26 knygų, pavyzdžiui, tai, kurie turi natūralių Užsakant į juos. Kas yra procesas kad jūs iš tikrųjų naudoti? Ar tai gana atsitiktinai tiesiog skinti pirmasis matote ir išleisti jį į savo vietą? Ar jūs pirmą kartą perkelti savo rankas aplink ieško tada ieško B? Ar jums pažvelgti išvaizdą pora juos šalia ir tiesiog pasakyti, palauk, tai nėra teisinga, ir tada apsikeitimo tvarką? Mes jau matė pirmadienį kad ten iš būdų , kurioje mes galime tai padaryti, ir Iš tiesų, kaip mes prie pabaigos čia Norėčiau atkreipti dėmesį, galbūt KĄ Mary Beth daro. Mes turime keletą poliai atrodo, didesnis vienas, trys smulkesni. 

PUBLIKA: aš užsisakyti juos kai aš susirasti du laiškus kad aš žinau, yra kartu seka, Aš juos kartu, kad aš ne jaudintis išlaikyti trasa visą eilę knygų. Tai tiesiog, oi, yra, pirma, Aš gavau šį krūvą čia. GARSIAKALBIS: Taigi, beveik kaip Puzzle gabalus, turėti tinkamą pavidalą sutapti su tarpusavyje. PUBLIKA: Gana daug, taip. GARSIAKALBIS: Gerai, puikus. Ir dabar kiekvienos iš jų poliai yra turbūt rūšiuojami? 

PUBLIKA: Taip. 

GARSIAKALBIS: Gerai, per Z. Viskas teisė, sveikinimai, jūs tai padarė. Jūs turite savo pasirinkimą. Mėlyna? Gerai, ačiū už tai. Taigi Marija Bet nebuvo pasiūlyti ką jos požiūris buvo bet kas yra dar vienas būdas, kaip jus gali eiti apie rūšiavimą šiuos dalykus? Ką tu padarei? Įrašas įveikti būtų buvę vieną minutę ir 50 sekundžių, arba tiek, plius tie Aš pamiršau skaičiuoti. Ką tu padarei? Taip? PUBLIKA: Paimkite kamino. Pradėti nuo pradžių. Patikrinkite savo dokumentus. Ir jei viršutinė vienas yra didesnis nei, galbūt, jie yra, Apatinė yra didesnis, tada įjunkite juos. 

GARSIAKALBIS: Gerai, kad pradedant viršuje ir apačioje, ir tada dirbti savo kelią į vidų, kaip kad, keičiant juos? Gerai, kad šiek tiek panašus dvasia burbulas rūšiuoti, bet renkantis kraštutinumų ne gretimos poros. Bet tai trumpas yra tai, kad ten tikrai įvairių būdų krūva galėtume tai padaryti, ir atvirai, manau, kad jums rūšies priėmė keletą metodų, tiesa? Jūs padarė tarsi keturių rūšiuotų krūvos, ir tada efektyviai sujungta kartu. Ir tai, Manyti, kita metodas apskritai. Jūs ne gydyti jį kaip vieną didelį krūva, Jūs padalintas problemą į keturias keturračiai, jei norite, ir tada kažkaip susijungė juos pabaigoje. 

Taigi aptarkime, galiausiai, kaip kitaip mes galime tai padaryti. Mes oficialiai nuomonei, burbuliukų rūšiavimo paskutinį kartą, ir burbulas tarsi priminti buvo algoritmas, kad mes ryškinamos su aštuonių Klasiokų čia, atrodytų, atsitiktinai rūšiuojami ne pirmas. Ir tada mes nusprendėme poromis, jei du elementai yra iš tam, tiesiog sukeisti juos. Taigi keturių ir dviejų, yra akivaizdžiai neveikia, Taigi tie du klasiokai susikeitė pozicijomis. Ir tada mes kartojamas keturis ir šešis, aštuonių tada šešių ir, kiekvienos iteracijos, juda į dešinę. 

Taigi suteiktas aštuonių žmonių, kiek Porinis palyginimai aš padariau vaikštant nuo iš kairės į dešinę per vieną tokį iteracijos? Kiek palyginimai? Septyni, tiesa? Nes jei ten aštuonis žmonės, bet jūs turite porą juos, ir jūs nuolat juda viena apynių į dešinę, jūs nesiruošia turėti aštuonis palyginimai, nes tu negali palyginti prieš save elementas, ar tai būtų tiesiog beprasmiška, todėl jūs turite septynias. Arba apskritai, jei mes turime n žmonių, mes padaryti n atėmus 1 palyginimus su burbulo rūšiuoti. 

Taigi aptarkime dabar kaip geras ar blogai burbulas tarsi iš tikrųjų buvo, ir bandykite suteikti sau žodyną su kuri kritikos algoritmų, pavyzdžiui, tai, ir netrukus mūsų. Taigi pirmąjį perdavimą per burbulas rūšiuoti, pirmą kartą Ėjau iš kairės į dešinę visoje etapas, paėmė mane n minuso 1 palyginimų. Ir tai bus mano matavimo vienetas, tiesa? Buvau rūšies kalbėti ir pasivaikščioti, šiek tiek greitai, kiek lėtas, taip skaičiuoti mano sekundžių skaičių nėra labai svarbi, bet skaičiuodamas skaičių operacijos, kad aš pirmadienį, Lyginant du žmones, kad jaučiasi kaip gražus matavimo vienetas. 

Taigi n atėmus 1 žingsnius pirmą kartą, bet tada tai, kas atsitiko po to? Kas vienas aukštyn kojom vieno perdavimo per kitaip nerūšiuotų sąrašą? Ką galite papasakoti apie elemento kas buvo viskas ten taip? Taip? Tai buvo didžiausias elementas, tiesa? Taškų aštuonių, nors ji pradėjo čia, kiekvieną kartą, kai aš palyginti ją su kaimynas, ji nuolat burbuliuoja iki dešinę pusėje sąrašo. Ir iš tiesų, tai kur algoritmas gauna savo pavadinimą. 

Dabar ta logika, kiek palyginimai reikia man padaryti antrą kartą Aš padaryti, kad perdavimą iš kairės į dešinę? n atėmus 2, tiesa? Tai tiesiog eikvoti savo laiką, jei I išlaikyti lyginant aštuonių prieš ką nors kitur, nes mes jau žinome, ji buvo reikiamoje vietoje. Štai iš tiek optimizavimas, todėl šalia perdavimas bus plius n atėmus du žingsniai, kur n yra žmonių skaičius. Dabar galite rūšies ekstrapoliuoti, net jei nesate kompiuterių mokslininkas, kaip tai baigiasi. Šio algoritmo pabaigoje, matyt jūs turite tik vieną palyginimas kairėje. Turite rūšies nustatyti pradžioje sąrašo atveju dviejų ir vienas yra iš tam ir turėtų būti vienas ir du, todėl tai iki dugno iš ne plius 1 galutinis palyginimas. 

Dabar dot, dot, dot rūšies bangų tai rankos, o kai kuriose sultingesnis informacijos bet tegul tiesiog eiti į priekį ir supaprastinti. Jei prisimenate iš aukštos mokykla, tiesą sakant, iš jūsų daug turėjo matematikos knygas, kurios turėjo mažai apgauti lapas ant priekinio dangčio ar galinį dangtelį, kad jums parodė, kas serijos summations kaip tai galiausiai pridėti iki. Bendroje atveju, jei turite kintamasis kaip n, o iš tikrųjų tai viena, jei jūs žiūrite į savo senosios mokyklos matematikos knyga, jūs pamatysite, kad tai iš tiesų išauga iki šios sumos čia n kartų n atėmus 1 visi padalinti iš 2. Taigi dabar leiskite man tiesiog nustatyti tai tiesa, kad dėl tikėjimo šuolis, kad tai, ką šis apibendrina iki, ir mes galime įrodyti, kad bendresniu atveju. Bet dabar tegul išplėsti this out. Taigi leiskite padauginti, ir todėl, kad tai n kvadratu, atėmus n visi padalinti iš 2. Tai tikrai n kvadratu, padalinti iš 2, atėmus n daugiau kaip 2 kad viskas gražu ir įdomu. Bet kas atsitinka, jei mes dabar plug-in vertė? Tarkime, aš neturėjo aštuoni žmonės, bet pasakyti mln. Ir tik todėl, kad milijonų tai gana didelis skaičius, tegul įjunkite, kad ir pamatyti, kas atsitiks. Taigi, jei aš prijunkite milijonų į tą formulę Aš ruošiuosi gauti milijonų kvadrato, padalinti iš 2, atėmus milijonų eurų, padalintas iš 2. Dabar kas, kad vyksta prilygti? Taigi 500 mlrd minus 500,000. Ir jei aš iš tikrųjų kad matematikos, ši priemonė kad rūšiavimas milijono žmonės su burbulas rūšiuoti gali imtis man 499.999.500.000 žingsniai ar palyginimai, galų gale, mes tiesiog ekstrapoliuoti. 

Tai jaučiasi gana lėtas, bet atvirai matavimo vieną konkretų indėlį kaip šis, yra ne visi, kad spėjimas. Bet iš tikrųjų jis rodo, kad n gauna didesnį ir didesnį, šį algoritmą rūšies jaučiasi blogiau ir Dar blogiau, ar jūs tikrai pradėti jausti, kad skausmas kėlimas laipsniu, kad n kvadratu, kuris išauga iki gana greitai. Ir tai detalė nėra neteko žmonių, iš tikrųjų Prieš keletą metų tikra senatorius, kuris buvo kampanijos, susėdo pokalbiui su "Google" Eric Schmidt direktorius tuo metu, ir ginčijo su klausimu daug, kaip mes ištirti šiandien. Paimkime išvaizdą. 

[VIDEO PLAYBACK] 

-Senator, Jūs čia "Google", ir man patinka galvoti apie pirmininkavimo kaip darbo interviu. Dabar, tai sunku gauti darbas, kaip prezidentas, ir jūs ketinate per sąstingis dabar. Taip pat sunku gauti darbą "Google". Mes turime klausimų, ir mes paklausti mūsų kandidatams klausimus, ir tai vienas iš Larry Schwimmer. What-- jūs manote aš juokauji, tai čia. Kas yra efektyviausias būdas rūšiuoti milijoną 32 bitų sveikųjų skaičių? 

-Well-- 

-Aš Atsiprašome, maybe-- 

Ne, ne, ne. Manau, kad burbulas rūšiuoti Būtų neteisinga būdas eiti. 

Nagi, kas jį šį pasakyta? Nemačiau kompiuterį mokslas savo fone. 

-Mes Gavo mūsų šnipai ten. 

Ok, tegul paklausti skiriasi interviu klausimą. 

[END VIDEO PLAYBACK] 

GARSIAKALBIS: Taigi kalbame apie konkretūs skaičiai, nors, nesiruošia būti visi, kad naudinga. Tai nėra gyvenimo pamoka, kad burbulas Rūšiuoti, atsižvelgiant milijono įėjimai, gali užtrukti net 500 mlrd veiksmus. Jūs tikrai negali apibendrinti per efektyviai nuo ir padaryti gerus dizaino sprendimus, rašant programas. Taigi susitelkime nors apie tai, kaip mes galime supaprastinti šį rezultatą. 

Taigi aš paryškinamas geltonai čia n rezultatas kvadratėliais padalintas iš 2, taip mln kvadrato padalinti iš 2, tada Aš pabrėžė, kas Galutinis atsakymas buvo kai mes atimama išjungta n padalinti iš 2. Ir teiginys aš ruošiuosi padaryti dabar yra, kas gi cares, jei jūs atimkite išjungtas tiek metų n virš 2, kai pirmą kartą dalis šios formulės yra daug didesnis? Ji dominuoja kitos terminas n kvadratėliais padalintas iš 2 Yra tiek daug daugiau, be abejo, kaip n gauna didelis kaip milijonas, tai ten tikrai didelis skirtumas ne dienos pabaigos nuo 500 mlrd ir 499.999.500.000? Ne tikrai. Ir taip, ką mes ketiname daryti, kaip kompiuterių specialistai yra ignoruoti tuos mažesnius užsakymo sąlygų ir imtis ko nors panašaus į tai ir tikrai tiesiog supaprastinti ją terminas, kuris ketina reikšmės. Didesnės mūsų duomenų rinkiniai gauti, didesnis mūsų duomenų bazės gauti, tuo daugiau tinklalapius mes turime ieškoti, daugiau draugai turite "Facebook". 

Kaip n gauna didesni, mes tikrai ketina rūpintis didžiausia terminas tokio analizės mūsų algoritmai efektyvumą. Ir aš ruošiuosi pasakyti, žinote, ką, burbulas tarsi yra ant didžiojo O tam, nuo n, kad kvadrato. Tai nėra tiksliai n kvadrato, kaip mes matėme, bet kas tikrai rūpi apie tuos mažesnius sąlygomis, ir tiesą sakant, kas iš tikrųjų cares, jei mes padalinti iš 2? Tai tiesiog pastovus veiksnys. Ir yra 500 milijardų, palyginti su 250 milijardų tikrai, kad didelis spręsti? Galėčiau tik laukti vienerius metus, tegul mano nešiojamas pažodžiui gauti du kartus taip greitai, aparatūros, ir kad skirtumas tarsi tiesiog nueina natūraliai per tam tikrą laiką. 

Kas mums rūpi tai išraiška, dalis išraiškos, kad ketina skirtis kaip mūsų indėlis tampa didesni ir didesni. Ir iš tiesų, realiame pasaulyje, tai, kas vyksta vis yra mūsų problemų įėjimai ir algoritmai vis didesni. Taigi didelis O bus notacija, asimptotinio notacija, kad mes tiesiog naudoti kaip kompiuterių mokslininkai apibūdinti veiklai arba važiavimo laikas, algoritmą. Taigi, kad mes galime palyginti algoritmus skirtinguose kompiuteriuose raštu skirtingi žmonės, naudojant kai iš esmės panašus metrika kaip palyginimų skaičius esate priėmimo, o gal apie sandorius skaičių jūs darote. 

Ką mes neketiname skaičius yra laiko suma kad eina į laikrodį ant sienos: paprastai. Ką mes neketiname jaudintis apie tai, kiek atminties Jūs naudojate šiandien mažiau, nors tai kitas šaltinis, mes galime išmatuoti. Mes ketiname bandyti grįsti savo analizę teisingomis pagrindines operacijas, tie, tiesą sakant, kad jūs galite pamatyti dauguma vizualiai. Taigi su kažką panašaus į didįjį O n kvadrato, aš teigti, kad O n kvadratu yra viršutinė riba nuo vadinamųjų važiavimo laikas burbuliukų rūšiuoti. Kitaip tariant, jei jūs norėjo teigti, kad ten ši viršutinė riba, kiek veiksmus algoritmas gali užtrukti, jis ketina būti didelis O n kvadrato šiuo atveju viršutinė riba. 

Ką daryti, jei aš vietoj keisti istorija būtų ne apie burbulo rūšiuoti, bet apie tai viršutinė riba. Ar manote, kad algoritmas kad mes pažvelgė jau kurio viršutinė riba, maksimalus išmatuoti laiko ar operacijų, būtų teigti, kad būti ribojama iš n, tiesinė funkcija, ne kvadratinis vienas, kad yra lenkta? Kas algoritmas, visada užtrunka ne daugiau nei kaip n žingsnių, arba 2n žingsniai, ar 3n žingsniai? Taip? 

PUBLIKA: Ieškoti Daugiausia sąraše? 

GARSIAKALBIS: Puikiai, rasti Didžiausias skaičius sąraše. Jei aš duotas sąrašą žmonės pavyzdžiui, kiekvienas laikiusį numerį, kas yra didžiausias skaičius žingsnių ji turėtų imtis man, pagrįstai protingas asmuo, rasti didžiausią asmenį į tą sąrašą? n, tiesa? Nes blogiausiu atveju, kur gali didžiausia vertė būtų? Teisė, visi pabaigoje būdas. Taigi, blogiausiu atveju viršutinė riba, galiu turi pereiti visą kelią čia ir bus kaip, Oh, štai numeris aštuonių, ar kokia ta vertė. Dabar ji tiesiog kvaila jei aš nuolat vyksta, tiesa? Ieškote daugiau ir daugiau elementų jei paskutinis iš jų yra ten? Taigi tikrai, n yra viršutinė riba. Man nereikia imtis daugiau veiksmų, nei nurodyta. 

Taigi ką daryti, jei vietoj aš pasiūliau, kad yra algoritmai šiame pasaulyje, kad turėti darbo laiką, kad yra riboja didelis O log n, prisijunkite n? Kur mes matėme tai anksčiau? Taip? 

PUBLIKA: telefonų knygoje problemos? GARSIAKALBIS: Kaip telefonų knygos problema. Kas buvo, kaip priemonė kiek laiko ar kiek ašaros IT paėmė mane rasti ką nors panašaus Mike Smith telefonų knygoje? Mes teigė, kad buvo log n, o net jei nepažįstamas ar jis tai tiek miglotas, ką pagrindu arba eksponentė buvo Tiesiog neužmirškite, kad log n paprastai reiškia procesą, šiuo atveju, dalijant kažkas per pusę vėl, ir vėl, ir vėl, ir vėl, taip, kad juo gauna vis maža, kaip jums tai padaryti. 

Taigi prisijunkite n reiškia, tikrai, į telefonų knygą, pavyzdžiui, dvejetainis paieškos teorija, kai mes turėjo virtualias duris ant lentos, arba kai Seanas buvo ieškoti kažko. Jei jis naudojamas dvejetainis paiešką, prisijunkite n būtų viršutinė riba, kiek laikas, kad mano. Bet tie algoritmai, kad vykdavo log n prielaida kas svarbiausią detalę? Tai sąrašas buvo rūšiuojamos, tiesa? Jūsų algoritmas yra negerai, jei jūsų indėlis nėra rūšiuojamos, ir dar jūs naudojate kažkas panašaus dvejetainėje paiešką nes jums gali šokinėti tiesiai virš elemento nesuvokdami, kad tai iš tikrųjų yra. 

Dabar kas gali tai reiškia, didelis O vieną? Tai nereiškia, kad savo algoritmą trunka vienas ir tik vienas žingsnis, tai tiesiog reiškia, kad ji trunka pastovus pakopų skaičius. Gal tai 1, o gal tai 10, gal tai 1000, bet tai nepriklauso nuo Problemos dydis. Nesvarbu, kaip didelis n, pastovus laikas algoritmas visada užima tiek pat žingsnių. Taigi, kas gali būti algoritmas mes kalbėjome apie ar tiesiog intuityviai, kad ateis pas jus, kad visada veikia vadinamąjį nuolat laiku? Taip? 

PUBLIKA: Įlašinkite du numerius. GARSIAKALBIS: Pridėti du numerius, 2 plius 2 lygi 4, padaryta. Taigi, kad galėtų dirbti, kas dar? Kaip apie daugiau realiame pasaulyje, taip? 

PUBLIKA: Ieškoti Pirmas dalykas, sąraše. GARSIAKALBIS: Ieškoti pirmas elementas sąraše, tikrai. Mes iš tikrųjų buvo kalbama apie masyvų jau kaip jums ne Pirmasis elementas masyve, nesvarbu, kiek laiko masyvas C kodą? Jūs tiesiog naudoti kaip kronšteino nulis notacija, bam jūs ten. Ir iš tiesų matricos, kaip panaikinti, parama kažkas visuotinai žinomas kaip laisvą prieigą, laisvosios kreipties atminties, nes jūs galite tiesiog peršokti į vieną vietą. Mes galime tai padaryti dar paprasčiau mes galime atsukti iki nulio savaitę kai mes padarėme nulio. Kiek laiko užtruks pasakyti blokas Scratch vykdyti? Tiesiog pastovus laikas, tiesa? Pasakyk ką nors, tarkim, kažkas, nesvarbu Kaip didelis Įbrėžimai pasaulis, tai visada ketina imtis tą patį laiko tiesiog pasakyti kažką. 

Štai pastovus laikas, bet kas Pasitaiko? Jei tai buvo viršutinis ribos, ką daryti, jei norime apibūdinti mažesnes ribas mūsų algoritmų veikimo laikas? Beveik geriausias atvejis potencialiai jei norite, nors šie terminai gali būti taikomas geriausias dėklai, blogiausiu atveju, vidutinis atvejai daugiau Paprastai, bet tegul tik sutelkti mažesnes ribas apskritai. Kas algoritmas, kuris turi Apatinė riba n žingsnių, ar 2n žingsniai, ar 3n žingsniai? Kai n žingsnių veiksnys, tai jo apatinė. Taip? 

PUBLIKA: burbulas rūšiuoti? 

GARSIAKALBIS: burbulas tarsi užima Jūs minimaliai n žingsnių, kodėl? Kodėl taip yra? Kodėl reikėtų, kad pradžia ateiti pas tave intuityviai, net jei ji ne tik Dar neužsiregistravote? Taip? 

PUBLIKA: [nesigirdi]. GARSIAKALBIS: Būtent. Į geriausią scenarijų burbulas rūšiuoti ir algoritmų daug, jei aš ranka jums aštuonis žmones kurie jau rūšiuojamos, būtų kvaila už jus, algoritmas, eiti pirmyn ir atgal daugiau nei vieną kartą, tiesa? Kadangi, kaip greitai, kaip jūs vaikščioti per sąrašą iš karto, jūs turėtumėte suprasti, oh, aš padariau ne apsikeitimo sandoriai, šis sąrašas surūšiuotas, išėjimą. Bet, kad ketina imtis jums n žingsnių. 

Ir atvirkščiai, kas dar būdas galvoti apie tai? Burbulas tarsi yra omega, taip sakant, n, nes jei peržvelgsite mažiau nei n elementai, tai, kas yra esminis klausimas yra? Jūs nežinote, jei ji rūšiuojamos, į dešinę. Mes, žmonės gali pažvelgti į aštuonis žmonės ir bus kaip, oi, tai rūšiuojamos, kad neatsižvelgė man n žingsnių, tačiau tai padarė. Tavo akys, nors jums natūra iš turi didelį matymo lauką, jūs pažvelgė aštuonių elementų, jūs pažvelgė aštuonių žmonių, kad aštuonių žingsnių veiksmingai. Ir tik tada, kai aš vaikščioti per visą sąrašas daryti Suprantu taip, rūšiuojamos. Jei aš sustabdytas įpusėjus galvoju, visi Gerai, tai gana rūšiuojami šiol, kas yra šansai tai nėra surūšiuoti? Tai algoritmai nesiruošia būti teisinga. Gali būti greitesnis, bet neteisingas. 

Taigi dabar mes turime būdą aprašant mažesnę ribas, ir ką apie nuolat laiku? Kas algoritmas, kuris yra mažesnis privalo savo veikimo laiką vienos? 1 žingsnis 2 žingsniai, 10 žingsnių, tačiau pastovus, nepriklauso nuo n, iš įėjimo dydis? Taip, iš nugaros. 

PUBLIKA: Printf? GARSIAKALBIS: Kas tai? PUBLIKA: Printf? GARSIAKALBIS: Printf. Gerai, tikrai. Taigi užtrunka fiksuotą skaičių žingsnių. Ir turėčiau now-- dabar, mes kalbame apie C kodas ir ne nulio, kažkas kaip tarkim, su printf, turėtume pradėti gauti atsargūs. Kadangi printf nėra priimti įėjimo, tai eilutė, ir styginiams tai techniškai turi ilgį. Taigi, jei mes dabar nori pasiimti jums, jei jūs neprieštaraujate, techniškai galėtume teigti, kad printf nėra priimti kintamo ilgio įvestį, ir, žinoma, tai gali užtrukti daugiau laikas atspausdinti eilutę taip ilgai, nei šis ilgai. 

Taigi ką daryti, jei mes manome, tik rūšiavimo ir ieškoti pavyzdžių? Ką apie Mike Smith telefone knyga, ar dvejetainis paieškos apskritai? Geriausiu atveju, kas gali atsitikti? Atidaryti telefono knyga ir bam ten Mike Smith skaičius. Galiu skambinti jam iš karto. 

Paėmė vieną žingsnį, gal dviem etapais, bet pastovus pakopų skaičius jei aš laimingas. Ir tiesą sakant, matėme Pirmadienis jūsų klasiokas gauti gana pasisekė du kartus iš eilės. Ir tai iš tiesų buvo nuolatinis laikas per apatinių ribų dėl tos algoritmas ieškant skaičius 50 už tuos uždarytas durys. 

Dabar, kaip panaikinti, jei jums atrasti kad tiek didelis O viršutinė riba, ir omega, apačios, yra vienas pats, kad yra pati formulė skliausteliai, taip pat galite pasakyti, tiesiog, kad būtų išgalvotas, kad kažkas yra teta n ar teta iš kitu vertę. Tai tiesiog reiškia, kad kai didelis O ir omega yra tas pats. Dabar ką apie atrankos rūšiuoti? Leiskite naudoti šią naują žodyną. Be atrankos rūšiuoti, ką gi mes buvome daro vėl ir vėl, ir vėl? Aš buvau ketinate pirmyn ir atgal per sąrašas, ieško kam? Mažiausias skaičius. 

Taigi, kaip daug priemonių, kaip daug palyginimų aš turite padaryti, siekiant išsiaiškinti, kas mažiausias elementas sąraše buvo? n atėmus 1, tiesa? Nes jei aš tiesiog pradėkite su vienas aš tikiu, suteikta ir aš pradedu lyginant jį ar ją, tada jam ar jai, jam ar jai, jam ar jai, aš gali tik suporuoti elementai kartu n atėmus 1 kartus. Taigi pasirinkimas tarsi panašiai trunka n atėmus 1 žingsnius pirmą kartą. 

Kiek žingsnių užtrunka mane rasti antrą mažiausią elementą? n atėmus 2, nes aš būdamas kvailas jei aš nuolat ieško pačių žmonių dar kartą, jei aš jau pasirinkote jį ar jos ir įdėti juos į jų vietą. Ir trečiasis etapas, n minus 3, 4, tada n atėmus. Mes matėme šį modelį anksčiau, ir iš tiesų pasirinkimas tarsi panašiai turi viršutinė riba n kvadratu, jei mes iki tos api. Koks jo apatinė atranka rikiuoti? Minimaliai, kiek laiko būtina atranka Rūšiuoti imtis, kaip mes apibrėžti jį pirmadienį? Pasiūlyti du variantai. Gal tai n, kaip ir anksčiau. Gal tai n kvadratu, nes ji dabar kaip viršutinė riba. 

PUBLIKA: n kvadratu. GARSIAKALBIS: n kvadratu. Kodėl? 

PUBLIKA: Kadangi jūs turite apibrėžti [nesigirdi]. 

GARSIAKALBIS: Būtent. Bent jau aš apibrėžti atrankos rūšiuoti jis buvo gana naivus, nesustoti, rasti mažiausias elementas. Eiti vėl, rasti mažiausią elementą. Eiti vėl, rasti mažiausią elementą. Nėra rūšiuoti optimizavimas ten, kad gali leiskite nutraukti po tik n arba tiek žingsnių. Taigi iš tiesų, pasirinkimas Rūšiuoti, omega n kvadratu. 

Ką apie įterpimo rūšiuoti, kur aš paėmė kas man buvo suteikta, ir tada aš plopped jį ar jos tinkamoje vietoje? Tada aš pradėjo antrąjį asmenį, plopped jį ar ją į tinkamą vietą. Tada kitas asmuo, plopped jam ar jai į tinkamą vietą. Atkreipkite dėmesį, kad tai yra labai linijinis, taip sakant. Aš tiesi linija, aš nesiruošia pirmyn ir atgal, Aš niekada Prisiminus tikrai, bet tai, kas vyksta, kai aš įdėti jį ar jai į pradžią sąrašas, kaip mes padarėme pirmadienį? Kas vyksta? Taip? PUBLIKA: [nesigirdi]. GARSIAKALBIS: Taip, kad buvo sugauti, tiesa? Galbūt jūs žinote, iš Jūsų klasiokais, jei jie buvo padaryti bet kokį judėjimą su jų kojos, kad buvo operacija. Taigi, jei ten buvo trys žmonės čia ir naujas žmogus priklausė būdas ten, ant ilgo etape, kaip tai, tikrai, jis arba ji gali tiesiog eiti iki galo. Bet jei mes galvojame apie kompiuteris ir atminties masyvas, šie žmonės vyksta turėti shuffle per padaryti kambarį tą asmenį. Ir taip, kad n atėmus 1 shufflings, n atėmus 2 shufflings, n minus 3 shufflings yra tik rūšies vyksta už mane, o ne priešais mane kaip ir anksčiau, tam tikra prasme. Dabar, kaip žemę, ir kaip galite matyti internete jei jums pradėti išnyra aplink apie rūšių, yra tiek daug skirtingų tie ten, kai kurie iš jų geriau nei kiti. Iš tiesų, bogosort yra vienas tai įdomus natūra ieškoti. Bogosort užima rinkinį numerius ar pasakyti kortų kaladę, atsitiktinai sumaišo juos, ir patikrina, ar jie rūšiuojami. Ir jei ne, ar jį dar kartą. Ir jei ne, ar jį dar kartą. Jei ne, ar jį dar kartą. Neįtikėtina kvaila. 

Ir iš tiesų, jei jūs skaitote kaip Vikipedijos straipsnio, jo slapyvardis yra kvaila rikiuoti. Tai galų gale dirbti, tikiuosi, suteikta pakankamai laiko, bet kiek laiko gali užtrukti šiek tiek laiko. Taigi, jei aš galėtų tegul greičio dalykų iki iš Mary Beth pavyzdžiu anksčiau, turėdami kelis elementus, bet dar dvi procesoriai. Du žmonės, jei jums ne tai prisijungti prie manęs. Kaip apie 1 per čia, ir tegul go-- niekas ten? Niekas ten? Gerai. Jūs su juoda marškinėliai, taip, nagi žemyn. Gerai, koks tavo vardas? 

PUBLIKA: Petras. 

GARSIAKALBIS: Kas tai? 

PUBLIKA: Petras. GARSIAKALBIS: Petras Dovydas malonu susitikti su jumis. Gerai, mes turime Petrui čia, jei jus nori ateiti ant stalo čia. Ir koks tavo vardas? 

PUBLIKA: Elena. GARSIAKALBIS: Elena. Gerai, nice to meet you. Elena susitikti Petrą. Petras, Elena. Ir mes turime Andrew čia taip pat, prašom. Ir jūsų užduotis vyksta būti rūšiuoti kortų kaladę. Ir jei nepažįstamas, denio korteles turėtų galiausiai būti rūšiuojami truputį kažką panašaus tai kur mes padarysime klubai, tada kad kastuvai, tada širdis ir deimantai, nuo tūzo kaip vienas, visą kelią iki karaliaus. 

Kortos Aš ruošiuosi duoti jums ketiname būti 52 kiekybe. Mes ketiname panašiai laikas jums, vos akimirką. Mes ketiname mesti Andrew Ekrane čia taip žiūrėti, kaip jums tai padaryti. Ir taip, kad visa tai yra dar akivaizdesnis, tai kortelės gavau "Amazon". Taigi jie jau atsitiktinai rūšiuojami, ir mes ketiname kartą jums. Ir mes ketiname keep it real šį kartą, todėl mes ketiname bandyti spausti jus nes kitaip tai bus sunkus greitai. Jei galėtumėte tęsti rūšiuoti 52 elementus, kartu per kai kurių priemonių, dabar. 

Ir vėl, kaip mes žiūrėti šiuos vaikinai ką daryti, galų gale ketina gaminti akivaizdus rezultatas, galvoti apie tikrai kaip jie kiekvienas daro tai, kaip jūs galėtumėte apibūdinti. Nes vėl, tai yra Visi procesai, algoritmai kad mes priimame kaip savaime, kaip žmogaus. Bet jūs tikriausiai seniai intuicija, ilgai prieš jums dar maniau apie vartojate informatikos klasė jums galėjo intuicija su kuri, siekiant išspręsti problemas, kaip šis. Bet kai jūs pripažinti modeliai ir pradėti formalizuoti veiksmus, su kuriomis jūs spręsti šias problemas, jūs pamatysite, kad jūs galite išspręsti daug įdomesnis ir daug sudėtingesnis problemos greitai. Taigi kažkas iš auditorijos, kas yra bent vienas iš elementų, algoritmas kad jie naudoja čia? 

PUBLIKA: [nesigirdi] GARSIAKALBIS: Kas tai? PUBLIKA: Pagal kostiumas. GARSIAKALBIS: Pagal kostiumas. Taigi, pirmiausia jie grupavimo visi deimantai kartu atrodo, visi širdys kartu atrodo, ir taip toliau, be pagarbos už dėl kortelių numerius. Ir dabar jie atrodo, pavyzdžiui, būti rūšiavimą skaičiaus. Labai gerai. 

Gerai, kad tai, kas vyksta būti galutinis žingsnis tada čia? Kai mes turime keturis surūšiuotas kostiumai, ką mes turime daryti, kad keturių polių siekiant vieno rūšiuoti denio, tiesiog? Taigi, mes turime sujungti juos vėl. 

Taigi, čia yra įdomi mintis, kad vėl Manyti, yra labai intuityvus, net jei gali niekada antausį kad etiketės ant jo natūra. Ši pagrindinė sąvoka dalijant problema ne pusę šio laiko, bet bent į keturis gabalus. Spręsti gana daug iš esmės identiškos problemos atskirai vienas nuo kito, ir tada sujungti rezultatus. Ir puikus, padaryta. Gerai, didelis apvalus plojimų, jei galėtume. 

[Plojimai] 

GARSIAKALBIS: aš neįsivaizduoju, ką jūs daryti su tai, bet čia jums eiti. Labai ačiū. Taigi pažiūrėkime, dvi minutes ir aštuonios sekundės, jei norite mesti iššūkį savo draugams. Kas tada vyksta į būti atimti iš to kad mes galime pritraukti daugiau apskritai? Na, manau, kad atgal į šis skaičius masyvas, ir manau, kad dabar sugrįžote pas kai Pseudocode mes parašiau anksčiau, ir tai buvo dėl Pseudocode sprendžiant telefonų knygos problema. , Pagal kurį Pseudocode I išvardijo daugiau metodinę būdas aprašyti, kaip aš labai intuityvus žmogaus algoritmas dalijant telefoną knyga per pusę, kartoju, kartoju, kartoju, kol aš rasti ką nors, kaip Mike Smith, jei jis iš tikrųjų yra telefonų knygoje. 

Bet aš rūšies naudojami, ką aš kviesiu labai pasikartojantis požiūris čia ypač įspėjimo linija 8 ir linija 11. Tai yra įrodymas, pasikartojantis požiūris, apsisukimo požiūris, nes tai yra būtent tai, elgesys jie sukelia. Tos linijos abu sako eiti į rūšies linija trijų, ir jūs galite iš manau, kad jūsų proto akis kaip kilpa. Tai sakau, kad grįžti iki žingsnio trijų ir pakartoti, vėl, ir vėl, ir vėl. 

Bet ką daryti, jei mes sverto pagrindinį idėją čia, kad mes ne paskutinį kartą, ir supaprastinti linija 8 ir 11 eilutė ir jų kaimynai kaip tik tai, geltonai. Tai nėra iš esmės sutrumpinti Pseudocode labai daug, bet tai iš esmės keičia mano algoritmas pobūdis. Ką aš dabar sako, 7 žingsnis 10 žingsnis, yra ieškoti Mike į tą patį kelią, bet tik į kairę pusę arba į dešinę pusę. 

Taigi, kitaip tariant, jei Pradėsiu nuo vieno žingsnio pasiimti telefono knyga, atvira viduryje iš telefonų knygos, pažvelgti pavadinimų, jei Smithas yra tarp NAME, skambinkite Mike, kita jei Smith anksčiau knygos, Žingsnis Septyni ieškoti Mike kairėje pusėje knygoje. Tačiau, kad šios rūšies jaučiasi jis palieka mane kabo, tiesa? Geltonai, yra instrukcija, bet kaip man ieškoti Mike į kairę pusė telefonų knygoje? Kai turiu algoritmas, su kuria aš galite ieškoti kažkas panašaus Mike Smith? Na, tai žiūri mums į veidą. Galiu tiesiog naudoti patį programa efektyviai einame į viršų vėl ir vėl veikia tie patys eilučių kodo. 

Taigi, nors tai turėtų jaustis kaip ciklinio apibrėžimą šiek tiek kur jūs atsakyti į kažkieno klausimas, tiesiog tarsi klausia tą patį klausimą vėl, kaip, kodėl, kodėl, kodėl? Realybė yra tai, nes mes sunkiai koduojami Specialiųjų linijų pora, 4 žingsnis, kuris yra, jei ir 12 žingsnis, yra efektyviai kitą filialas, nes mes turime tuos laikina priemones, Šis algoritmas bus nutraukti, jei mes rasite Mike, ar jei mes ne. Tačiau 7 ir 10 etapas dabar, mes turime ką mes vadiname rekursinį algoritmą. Ir rekursija yra iš tiesų galinga idėja kad šiek tiek proto lenkimo per pirmąjį, kad dabar mes galime taikyti taip. 

Sujungti Rūšiuoti bus paskutinis rūšiuoti, kad mes pažvelgti, bent jau klasę formaliai. Ir tai iš esmės skiriasi nuo Šių trijų, ir tikrai keturi paskutinieji, jei mes įtraukti bogosort. Štai už merge rūšiuoti Pseudocode. Kai ant įvesties n elementų, todėl atsižvelgiant į iš dydžio n matrica, jei n yra mažesnis nei 2, grįžti. Taigi, kodėl aš turiu, kad normalumas patikrinti pirmiausia? Kas iškyla, jei aš ranka jums masyvas, kurio ilgis n yra mažesnis nei 2? Tai jau rūšiuojamos, be abejo, tiesa? Kadangi sąrašas arba turi vienas elementas, kuris yra banaliai rūšiuojami, nes tai Vienintelis dalykas ten. Arba, tai dydžio nulinio o tai reiškia, nieko rūšiuoti, todėl pagal savo pobūdį ji yra rūšiuojama. Yra tik nieko blogo ten. Taigi, kad mūsų vadinamosios bazinį scenarijų. 

Tai yra panašus į dvasią tai, ką mes padarėme su Mike. Jei Mike telefonų knygoje, skambinti jam. Jei jis nėra, pasiduoti. Tai vadinamasis bazinį scenarijų, įsitikinkite, kad Šis algoritmas ne dienos pabaigoje sustos tam tikromis aplinkybėmis. 

Bet čia tikėjimo šuolis dabar kitur, rūšiuoti kairėje pusėje, elementų, tada rūšiuoti teisę pusė iš elementų, ir tada sujungti rūšiuoti puses. Ir čia, kur jis jaučiasi kaip mes copping iš. Aš paklausiau, rūšiuoti n elementų, ir aš sakydamas, gerai, tai jį rūšiavimas kairę ir rūšiavimas teisę. Bet aš sakau, vieną kitas dalykas, ir tai yra pagrindinė tema atrodo į intuicija iki šiol, ten šis trečiasis žingsnis sujungiant. Kuris nors jį atrodo, kad kvailas dvasia, kaip tik sujungti dalykų kartu, atrodo, būti svarbus žingsnis link sumontavimu dvi problemas, kad buvo suskirstyti galiausiai per pusę. 

Taigi sujungti rūšiuoti, tegul tai padaryti, jei jūs humoras man, dar vienu demonstravimo, tik todėl, kad mes turime kai Skaičiai dirbti. Ar galiu pasikeisti aštuonis stresą kamuoliukai aštuonių žmonių? Gerai, kaip apie jus trijų, jūs keturių Šiame skyriuje, penki, šeši, ir tegul do, 7, 8, nagi iki. Gerai, taip gerai. Minus 8, ten mes einame, plius 1. Puikus. Visos teisės ateiti iki, tegul greitai jums numerius. Taškų du, skaičius "trys", ketvirtą, skaičius penkis, šešis, septynis, o aštuoni. Aš aštuonis teisingai šį kartą. 

Gerai, kad eiti į priekį, jei galėtų, ir tegul rūšiuoti originalioje kad , kad mes turėjome vakar kuris atrodė kaip tai, jei ne tai. Ir tegul tai padaryti priešais esančioje lentelėje. Gerai, kad sujungti rūšiuoti. Tai kur ji vyksta gauti natūra įdomu, nes man atrodo, kad reikia duoti save tiek mažiau informacijos šiandien. 

Taigi sujungti tarsi visų pirma indėliu į n elementų, ir, žinoma, ne mažiau kaip du, tai aštuonių, todėl turiu šiek tiek daugiau nuveikti. Taigi, dabar mintyse mes, kaip klasės yra dabar kitas filialas o tai reiškia, tris žingsnius. Pirma, aš turiu rūšiuoti kairė pusė elementų. Taigi, kaip aš galiu eiti apie tai daro? Na, aš ruošiuosi rūšies protiškai padalinti sąrašą čia Jūs neturite fiziškai judėti, ir aš ketina sutelkti dėmesį tik į kairė pusė čia elementų. Taigi, kaip aš galiu eiti apie rūšiavimą Sąraše dydžio keturių? Koks mano algoritmas? Pirmiausia aš patikrinti yra n mažiau kaip du, ne, todėl aš pereiti prie kito bloko dar kartą. Rūšiuoti paliko pusę elementų. 

Taigi dabar vėl, psichiškai, ir tai yra, kai jūs turite sukaupti daug daug psichikos istorija, jei bus. Dabar aš rūšiavimas į kairę pusė kairėje pusėje. Gerai, kad dabar aš vadinu mano paties suliejimą rūšiavimo algoritmą, yra n mažiau nei du? Ne, tai yra du, todėl aš turiu rūšiuoti kairė pusė, o į dešinę pusę. Taigi čia mes einame, rūšiuoti yra kairėje pusėje. Kodėl ne jūs tiesiog išgerkite vieną žingsnį į priekį. Koks tavo vardas? 

PUBLIKA: Darren. 

GARSIAKALBIS: Dan. Danas žengė į priekį. 

PUBLIKA: Darren. GARSIAKALBIS: Darren, padaryta. Ar galite pasakyti Darren arba Dan? 

PUBLIKA: Darren. 

GARSIAKALBIS: Darren. Gerai, Darren sustiprino į priekį ir jis yra dabar rūšiuojami. Ir tai yra beveik kvailas teiginys, tiesa? Nemanau, tikrai atrodo, kad būti pasiekti nieko, bet tegul tęsti. Dabar leiskite man rūšiuoti teisę pusė iš elementų. Koks tavo vardas? 

PUBLIKA: Lukas. 

GARSIAKALBIS: Lukas. Nagi, žingsnį į priekį. Priimta, aš rūšiuojami Luko. Kairė pusė dabar rūšiuojami ir Dešinė pusė dabar rūšiuojamos, bet vėlgi, ten svarbiausias žingsnis čia. Ką aš šalia reikia daryti? Sulieti rūšiuoti puses. Dabar mes ketiname tiesiog kiekvienas pirmyn ir atgal, tokiu būdu, nes aš tipo reikia kai įbrėžimams vietos. Tai beveik kaip jie vaikinai yra ant stalo, ir man reikia šiek tiek kambarį perkelti juos aplink. Taigi, aš ruošiuosi sujungti vaikinai, žiūrėdamas kairėje pusėje ir dešinėje pusėje. Ir kas akivaizdžiai ateina pirma, į kairę arba į dešinę pusę pusę? Taigi teisė pusę, todėl galime pereiti per Luko Čia Darren pradinę padėtį. Ir dabar sujungti savo kairiąją pusę, Darren ketina perkelti tiesiai ten. 

Taigi jaučiasi beveik burbulas tarsi poveikis, bet mano pagrindinis algoritmas, labai skiriasi šiuo metu. Bet dabar kur viskas susitvarko šiek tiek erzina, nes jums reikia atsukti protiškai kur aš palikti išjungtas. Aš tiesiog sujungė surūšiuotas puses, kuris reiškia, kad aš kur mano algoritmas? Turiu rūšiuoti tinkamą pusę, tiesa? 

Jei atsukti, tiesiog ant vaizdo, jums matyti, kad mes turime tai taškas ir Luko Darren rūšiuoti kairę pusė kairėje pusėje. Tada mes susijungė tie rūšiuotas puselės, kurios tai sekantis žingsnis yra tarsi Teisė pusė kairėje pusėje. Gerai, tad tai greičiau padaryti. Visos teisės, šešių aš ruošiuosi teigia jūs dabar rūšiuojami, nagi pirmyn. Koks tavo vardas? 

PUBLIKA: Adriano. 

GARSIAKALBIS: Adriano. Adriano dabar rūšiuojami. Ir koks tavo vardas? 

PUBLIKA: Alex. 

GARSIAKALBIS: Alex dabar rūšiuojami. Kairysis pusę, į dešinę pusę, kas paskutinis žingsnis? Sujungti. Gana trivialus, todėl aš ketina sujungti į šešias, žengti žingsnį atgal, aštuonių, žengti žingsnį atgal. Ir dabar pastebėti tai naudinga Takeaway, ką dabar tiesa apie kairėje pusėje sąrašas, nepriklausomai nuo to, kaip mes pradėjome? Jis rūšiuojami. 

Dabar tai nėra rūšiuojamos didelis schema dalykų, tačiau ji yra rūšiuojami nepriklausomai kitos pusės. Dabar, kas žingsnis esu I jei aš nuolat pervyniojimas, kaip istorija prasidėjo? Dabar aš turiu rūšiuoti tinkamą pusę. Taigi dabar mes grįžta į Istorijos pradžia, ir tegul tai greičiau padaryti. Taigi, aš ruošiuosi rūšiuoti Teisė pusė viso sąrašo. Kas kitas žingsnis? Rūšiuoti kairėje pusėje, dešinėje pusėje. Rūšiuoti kairįjį pusę kairė pusė dešinėje pusėje. Ir koks tavo vardas? 

PUBLIKA: Omaras. 

GARSIAKALBIS: Omaras, žingsnis į priekį, daroma. Kairė pusė yra rūšiuojami. Ir koks tavo vardas? 

PUBLIKA: Chris. 

GARSIAKALBIS: Chris žengti žingsnį į priekį, jūs dabar rūšiuojami. Kas svarbus žingsnis dabar? Sujungti. Taigi vienas ketina sujungti į vietą čia, jei galėtumėte žengti žingsnį atgal, ir trijų ketina žengti žingsnį atgal, sujungti. Taigi kairę pusę Teisė pusė, dabar rūšiuojami. Atvirai kalbant, tai algoritmas jaučiasi mes eikvoti būdas daugiau laiko nei anksčiau, bet jei mes padarėme tai realiu laiku, mes pamatyti, kas takeaways bus. Dabar aš esu čia, teisė pusė dešinėje pusėje, leiskite man eiti į priekį ir rūšiuoti kairįjį pusę. Žingsnis į priekį, koks tavo vardas? PUBLIKA: Ramsey. GARSIAKALBIS: Ramsey dabar rūšiuojami. Koks tavo vardas? 

PUBLIKA: Marina. 

GARSIAKALBIS: Marina dabar surūšiuoti kaip gerai, jei vartojate vieną žingsnį į priekį. Pagrindinis žingsnis čia yra dabar sujungti, aš ketina skinti iš mano dviejų sąrašų, į kairę ir į dešinę. Penki ketina ateiti pirma, septyni ketina ateiti kitą. Ir vėl, tai yra tyčinis. Faktas, kad jie, atsižvelgiant žingsnius į priekį ir atgal reiškia atstovauti, kad mes negalime padaryti šį algoritmą vietoje taip pat lengvai kaip burbulas rūšiuoti ir atrankos rūšiuoti, ir įterpimo rūšiuoti, jei mes tiesiog nuolat Swapping žmonių. Aš tiesiog reikia rūšiuoti iš nulio popieriaus, kuris įdėti šie žmonės o aš susijungimas, ir tada aš galiu įdėti juos į vietą. Ir tai raktas, nes aš naudoju nauji ištekliai, erdvė, ne tik laiko. 

Gerai, tai yra nuostabu. Kairėje pusėje, rūšiuojamos, tiesa pusė rūšiuojami, kad dabar svarbiausias sujungimo žingsnis. Kaip aš sujungti tai? Taigi, jei jums sekti mano į kairę ranką ir dešinę ranką, Aš ruošiuosi atkreipti mano kairę ranką kairėje pusėje, mano dešinė dešinėje pusėje, ir dabar turiu nuspręsti, žingsnis po žingsnio, kurį galima sujungti į. Kas akivaizdžiai ateina pirmiausia? Taškų vienas. Taigi ateiti per čia čia mūsų Užrašinė. Taigi dabar numeris vienas ir pranešti ką aš daryti su mano dešinėje, Aš ruošiuosi perkelti savo vieną dešinėje perlipti atkreipti skaičių tris, ir dabar aš turiu padaryti Analogišką sprendimą. Ir iš tikrųjų stovėti teisę frontas Luko čia, jei galėtų, nes tai yra mūsų Užrašinė. Taigi, kas toliau? Mes turime Lk numeriu dviejų ar Chrisas numeriu trys. Akivaizdu Lukas, skaičius du, kad jūs čia. 

Bet mano kairė ranka dabar ketina būti padidinta atkreipti dėmesį į Darren, ir čia svarbiausia atimti su sujungti, aš nuolat daro tai, Žinoma, jei jums natūra iš sekti logika. Bet mano rankos niekada ketina eiti atgal, o tai reiškia, aš tik kada nors pereinant prie liko su mano sujungimo procesą, ir kad tai bus raktas į Mūsų analizė vos akimirką. 

Taigi dabar galime baigti šį sparčiai. Taigi trijų ateina šalia, tada keturių ateina šalia, ir dabar penkios ateina šalia, tada šešių, septyni, ir galiausiai aštuoni. Jaučia lėčiausiai algoritmas dar, bet ne, jei mes iš tikrųjų paleisti jį tos pačios rūšies laikrodis greičiu, taip kalbėti, su tos pačios tiksi laikrodis, kaip ir anksčiau. Kodėl? Na, Paimkime pažvelgti į galutinį rezultatą. 

Grįžkime per čia, leiskite man atsigriebti demonstraciją vizualiai kas mes ką tik padarė. Didinimas čia apie tai puslapis čia, pasakoja Firefox kad mes norime eilėje iki šiame langelyje, tegul pasakyti burbulas rūšiuoti, su kuria mes dabar gerai pažįstamas, pasirinkimas tarsi, kuris yra dar vienas gana paprastas vienas, ir dabar šiandien sujungti rūšiuoti, kuris bus mūsų kulminacinis pabaiga. Priežastis jis paėmė tiek daug ilgiau čia su žmonėmis ir man žodžiu yra žinoma, aš paaiškinti kiekvieną žingsnį. Bet jei jūs tiesiog atlikti tai, kas kaip mes padarėme burbulas rūšiuoti ir atranka Rūšiuoti ne tik vizualiai, laikrodis kiek daug efektyviau šis sverto pasidalijimas ir užkariauja gali būti, kai taikoma duomenų rinkinio ŠTAI net dydis aštuonių, tačiau net daug, daug didesni. Aš duodu jums sujungti rūšiuoti, šalia pusė šių kitų algoritmų. Tai ketiname gauti skausmingas greitai ir pabaiga nėra labai kulminacinis, jie tiesiog baigti rūšiuojami. Bet svarbiausia atimti tai, kad Pažiūrėkite, kaip daug greičiau sujungti tarsi buvo, jei jūs manote, kad aš tiesiog rūšies Messing su jumis. Jei mes darome šį vieną galutinį laiką, Leiskite Perkrauti šį, grįžkime ir pasirinkite burbulas rūšiuoti, ir tik smūgių, tegul pasirinkti įterpimo Rūšiuoti, tiesiog gera priemonė. Ir šį kartą vėl tegul pasirinkti merge rūšiuoti ir tegul iš tikrųjų paleisti šias šalia. 

Ir tai ne, iš tikrųjų, atsitiktinumas. Ką aš veiksmingai atlikti yra aš suskirstyti savo indėlį per pusę, vėlgi, ir vėl, ir vėl. Ir ten tik tiek daug kartų jūs galite padalinti savo indėlį į dvi dalis, į kairę ir į dešinę. Kas formulė, kad mes nuolat matome , kuris apibūdina padalijimą pusę vėl, ir vėl, ir vėl, ir vėl? 

PUBLIKA: Prisijungti n. 

GARSIAKALBIS: Prisijungti n. Bet ten yra vienas kitas svarbus žingsnis, Šis algoritmas yra ne prisijungti n žingsnių. Jei jis buvo prisijungti tik n žingsnių, mes būtume tą pačią problemą kaip ir anksčiau, kur mes negali būti Ar tikrai viskas rūšiuojami. Jūs turite minimaliai pažvelgti n elementų būti tikri, kad n elementai rūšiuojami, kitaip tai tikėjimo šuolis. 

Taigi, tai minimaliai žurnalas n priemonių, tačiau ką apie šio svarbaus sujungimo žingsnio kur aš susijungė mano kairė pusė ir teisė pusę ir ėjo per sceną? Kiek žingsnių yra tai, kad sujungti? Tai n, bet aš ne tik sujungti galutinį laiką. Dėl kiekvieno iš šių įdėtos į skambučius, ant kiekvieno tų įdėtos susilieja, aš vis dar rūšiuojami. Aš susijungė šiuos du vaikinai, tada šie du vaikinai, tada šie du vaikinai ir pan. 

Taigi aš sujungti vėl ir vėl. Kiek kartų? Taigi kiekvieną kartą, kai aš padalintas sąrašas per pusę, aš padariau suliejimą. Padalinkite sąrašą per pusę, padaryti suliejimą. Taigi, jei padalijus sąrašą galima padaryti log n kartų, ir sujungti galiausiai trunka n žingsnių, kas gali būti dabar viršutinė jungiasi į važiavimo laikas mūsų algoritmas? n log n. 

Ir iš tiesų, tai, ką mes pasiekėme čia. Taigi manote, kad pamatyti vizualiai šie trys dalykai paleisti greta yra n kvadratu nuo n kvadrato prieš n log n. Kuris iš esmės matysime, ne tik šiandien, bet ir ateityje, yra daug, daug greičiau. Plojimų šių vaikinai, Aš apdovanos juos streso kamuolius. Leiskite atidėti čia šiandien, ir matysime jus pirmadienį.