SPEAKER: Dobre, to je CS50. To je koniec troch týždňov, a ak ste využili už vedieť, že tam bude obed tento piatok ako obvykle, kde môžete teraz dobrý rozhovor a jedlo na ohňa a ľadu s niektorými CS50 je Zamestnanci a spolužiaci. Vydajte sa na tejto adrese tu. 

Teraz si môžete pripomenúť, alebo môže čoskoro byť oboznámený s, tieto veci, ktorá sem sú uvedené na konci semestra pre mnoho tried. Takzvaná skúška modrej knihy, v ktorej môžete písať svoje odpovede na skúšky. Teraz mám tú 26 ako modrej knihy, na každý z nich je napísané meno, až Z. A naozaj mená sú tak jednoduché, vďaka Z. A jeden z ciele na dosah ruky dnes bude pokračovať v čo sme začali v pondelok, čo nie je tak pri pohľade na kód, ale v skutočnosti pri pohľade na nápady a riešenia problémov. Jedným z cieľov a sľuby tohto kurzu je, aby vás naučí myslieť viac opatrne, viac metodicky, a efektívnejšie riešiť problémy. A skutočne, môžeme to urobiť naozaj bez toho aby ste sa dotkli jediného riadku kódu. Takže mám pár slonov tu dnes, oranžovej a modrej, ak by sme sa mohli dostať jedného dobrovoľníka, možno z väčšej späť, než je obvyklé. Ako sa asi tu, poď dole. Ktorého cieľom bude, aby pomôcť a navyše spravovať túto skúšku tu. Ako sa voláte? 

Divákov: Mary Beth. SPEAKER: Mary Beth, poď hore. Dovoľte mi, aby som sa mikrofón tu pre vás. Teší ma. 

Divákov: Teší ma. SPEAKER: Dobre, takže mám tu modrej knihy A až Z, a budem predstierať, že Mám jeden zo študentov, a oni prichádzajú trochu náhodne na konci tri hodiny skúška bloku, tak oni skončia v niektorej semi-náhodné poradie takhle. Teraz svoju prácu za chvíľu bude na bylo-- to je vlastne, ako sa dostať obrátil na konci roka triedy, s najväčšou pravdepodobnosťou. Vašou úlohou teraz bude úplne Jednoducho povedané, triediť tieto modrej knihy pre nás od A po Z. 

DIVÁKOV: Oh, to je bude trvať večne. 

SPEAKER: A budeme sledovať ako to urobíte, žiadny tlak. DIVÁKOV: Nie, žiadny tlak alebo tak niečo. 

SPEAKER: A pre zábavu, poďme dať časovač. 

Divákov: Toľko zábavy, toľko zábavy. 

SPEAKER: Môžem držať mikrofón pre vás. Dobre, práve sme zdvojnásobili našu rýchlosť. Takže do tej doby, dovoľte mi, aby som predstavovať, čo je bude otázka pre Mary Beth je to, čo robí, ako je že ide o riešenie tohto? A v skutočnosti, možno nebudete mať niekedy premýšľali o niečom tak jednoduché, ako keď si vyberiete až 26 kníh, ako je tento, ktoré majú prírodný objednanie k nim. Aký je proces že ste skutočne používať? Je to celkom náhodne len vyberanie prvý uvidíte a uvedenie na svojom mieste? Myslíte si najprv presunúť svoje ruky okolo Hľadáme potom hľadal B? Myslíte si, pozrite sa na pár z nich vedľa seba a len povedal, počkaj, to nie je v poriadku, a potom vymeniť poradie? Už sme videli v pondelok že existuje viacero spôsobov, ako v ktorom môžeme urobiť, a naozaj, ako sme u konca tu, Chcel by som vziať na vedomie možná z čoho Mary Beth robí. Máme niekoľko kôpok zdá sa, Väčšia z nich, tri menšie. 

Divákov: Ja je objednanie keď som si dva listy že viem, že sú spolu v poradí, Dal som ich dohromady tak, že sa mi nepáči musieť starať o udržanie track z celej rady kníh. Je to len, ach, je prvý, Mám tento stoh tu. SPEAKER: Takže, skoro ako puzzle kúsky, ktoré mať správny tvar na zhodovať s navzájom. DIVÁKOV: Docela veľa, jo. SPEAKER: OK, výborná. A teraz každá z nich zhromaždenia je pravdepodobne radené? 

Hľadisko: Áno. 

SPEAKER: Dobre, vďaka Z. Všetko Dobre, gratulujem, ste to urobil. Máte možnosť voľby. Modrá? Dobre, ďakujem vám za to. Takže Mary Beth sa navrhnúť čo jej prístup bol, ale to, čo je iný prístup, ako na Vás môže ísť o triedení týchto vecí? Čo by ste urobili? Záznam poraziť by bolo jednu minútu a 50 sekúnd, alebo tak, plus tie, ktoré som zabudol počítať. Čo by ste urobili? Jo? Divákov: Vezmite stoh papierov. Od začiatku. Skontrolujte, či vaše dokumenty. A v prípade, že horný z nich je vyššia ako, možno, že sú spodný z nich je vyššia, potom nimi prepínať. 

SPEAKER: OK, tak začína V hornej a spodnej časti, a pracovnú cestu dovnútra ako to, že ich vymení? OK, tak málo podobný duchom bublinkové druhu, ale voľba extrémy nie sú priľahlé pary. Ale krátke na to, že je tu určite veľa rôznych spôsobov, by sme to mohli urobiť, a Úprimne povedané, myslím, že tak nejako prijal pár prístupy, nie? Urobil si niečo ako štyri triedených pilotov a potom efektívne spojil dohromady. A to je, trúfam povedať, ďalšie technika dohromady. Vy ste to brať to ako jedna veľká hromada, môžete rozdeliť problém do štyroch štvorkolky, ak chcete, a potom sa nejakým spôsobom spojil ich do konca. 

Takže poďme zvážiť, nakoniec, Ako inak by sme mohli urobiť. Formalizované sme pojem bublinkové triedenie minule, a bubble sort odvolanie bolo Algoritmus, ktorý sme vizualizované s ôsmimi svojimi spolužiakmi sa tu, zdanlivo náhodne radené na prvom mieste. A potom sme sa rozhodli po dvoch, ak dva prvky sú mimo prevádzky, jednoducho ich vymeniť. Takže štyri a dve zrejme mimo prevádzku, Takže tí dvaja spolužiaci prepnúť pozície. A potom sme sa opakuje so štyrmi a šiestimi, potom šesť a osem, na každej iterácii, pohybujúce sa doprava. 

Takže vzhľadom k tomu osem ľudí, koľko pairwise porovnanie som urobil pri chôdzi od zľava doprava v jednom takom iterácii? Koľko porovnanie? Sedem, že jo? Vzhľadom k tomu, či je osem ľudia, ale máte pár ne a ďalej jeden hop na pravej strane, nebudeš mať osem porovnanie, pretože nemôžete porovnať prvok proti sebe, alebo by len zbytočné, takže budete mať sedem. Alebo všeobecnejšie, ak máme n ľudí, sme do n mínus 1 porovnaniu bublinkové druhu. 

Takže uvažujme teraz, ako dobrý alebo zlý bubble sort vlastne bol, a skúste aby sami slovnú zásobu ktoré k posudku algoritmov, ako je tento, a čoskoro sa naše vlastné. Takže prvom prechode bublina druh, prvýkrát Išiel som zľava doprava cez etapa, vzal ma n mínus 1 porovnanie. A to bude môj merná jednotka, nie? Bol som trochu hovoriť a prechádzky, trochu rýchlo, trochu pomalý, takže počítanie moje číslo v sekundách nie je osobitne hovorí, ale spočítaním operácie, ktoré som robil v pondelok, porovnanie dvoch ľudí, že sa cíti ako pekný mernú jednotku. 

Tak n mínus 1 krok prvýkrát, ale potom, čo sa stalo potom? Čo je to jeden nahor na jeden priechod cez inak netriedeného zoznamu? Čo mi môžete povedať o prvok ktorý bol po celú cestu tam? Jo? To bol najväčší prvok, nie? Číslo osem, aj keď tu začala, zakaždým, keď som v porovnaní s ňou proti sused, stále vyviera na pravej strane strane zoznamu. A vskutku, to je miesto, kde algoritmus dostane jeho meno. 

Práve týmto logiky, koľko porovnanie Potrebujem, aby na druhýkrát Robím, že prihrávku zľava doprava? n mínus 2, nie? Bolo by to plytvanie mojím časom, keby som udržať nákupný osem proti niekomu, iného, ​​pretože už vieme, bola na správnom mieste. Takže je to trochu optimalizácia, takže ďalší priechod bude navyše n mínus dva kroky, kde n je počet osôb. Teraz môžete trochu extrapolovať, a to aj ak nie ste počítačový odborník, ako to skončí. Na konci tohto algoritmu, pravdepodobne máte len jeden porovnanie odišiel. Musíte sa trochu opraviť začiatku zoznamu v prípade, že dvaja a jedna sú mimo poradia a mala by byť jedna a dve, tak to doraz na plus 1 v konečnom znení porovnanie. 

Teraz je bodka, bodka, bodka druh vĺn je ruky na niektoré šťavnatejšie podrobnosti ale poďme jednoducho ísť dopredu a zjednodušiť. Ak si spomínate z vysoko Škola, úprimne povedané, veľa z vás mali matematické knihy, ktoré mali malý ťahák na prednej strane obálky alebo zadný kryt, ktorý vám ukázal, čo séria súčtov ako to nakoniec pridal až. Vo všeobecnom prípade, ak máte variabilné, ako n, a v skutočnosti to jeden, ak ste sa pozreli na vaše old school math knihy, by ste vidieť, že to v skutočnosti pridáva do tejto sumy tu n krát n mínus 1 všetko deleno 2. Takže teraz mi dovoľte stanovuje je to pravda, tak na skok viery, to je to, čo to vystihuje až, a my sme mohli dokázať, že vo všeobecnejšom prípade. Ale teraz poďme rozšíriť to. Takže poďme sa množia na to, aby ich n na druhú, mínus n, všetko deleno 2. To je naozaj n na druhú, deleno 2, mínus n na 2, tak to je všetko pekné a zaujímavé. Ale čo sa stane, keď Teraz plug-in v hodnote? Dajme tomu, že som nemal osem ľudia, ale hovoria milióna. A milióny len preto, že to je celkom veľké číslo, poďme zástrčka, že v roku, a uvidíme, čo sa stane. Takže keď som plug miliónov do tohto vzorca Idem si milión na druhú, deleno 2, mínus miliónov, deleno 2. A teraz, čo to ide, aby sa rovnala? Takže 500 miliárd, mínus 500.000. A keď som vlastne robiť že matematika, znamená to, že triedenie milión ľudia s bubliny druhu mi môže trvať 499999500000 kroky alebo porovnanie na konci, sme len extrapolácie. 

Že sa cíti celkom pomaly, ale úprimne povedané, meranie jednej konkrétnej vstup ako je toto, nie je všetko, že to povedal. Ale v skutočnosti to naznačuje, že pre n dostane väčšie a väčšie, tento algoritmus druh cíti horšie a horší, alebo naozaj začnete cítiť bolesť, ktorá umocňovanie, že n na druhú, ktorý sčíta docela rýchlo. A to detail nie je stratil na ľudí, v skutočnosti pred niekoľkými rokmi istý senátor, ktorý bol kampane, sadol si na pohovor s Google Eric Schmidt, CEO v tej dobe, a bol napádaný s otázkou rovnako ako sme skúmanie dnes. Poďme sa pozrieť. 

[PREHRÁVANIE] 

-Senator, Že si tu na Google, a páči sa mi myslieť na predsedníctvo ako pracovný pohovor. Teraz je ťažké sa dostať zamestnania ako prezident, a idete cez nástrahami teraz. Je to tiež ťažké získať prácu v spoločnosti Google. Máme otázky, a my opýtajte Naši kandidáti otázky, a toto je od Larry Schwimmer. Co-- vy myslíte, že som Robíš si srandu, že je to tu. Aký je najúčinnejší spôsob, ako zoradiť milión 32bitová celé čísla? 

-Well-- 

-Prepáčte, Maybe-- 

Nie, nie, nie. Myslím si, že bublina druh by bol zlý spôsob, ako ísť. 

No tak, kto mu to povedal? Nevidel som počítač veda v pozadí. 

-Musíme Naša zvedov tam. 

-OK, Poďme sa opýtať iný rozhovor otázka. 

[END Videoprehrávanie] 

SPEAKER: Tak hovorí o Konkrétne čísla však sa nebude všetko užitočné. Nejedná sa o životnú lekciu, že bublina triedenie, vzhľadom k tomu milión vstupov, môže trvať toľko ako 500 miliárd kroky. Nemôžete naozaj zovšeobecniť príliš účinne od a robiť správne rozhodnutia návrhu pri písaní programov. Takže poďme sa zamerať na to, ako by môžeme zjednodušiť tento výsledok. 

Tak som sa zvýrazní žlto tu výsledkom n na druhú deleno 2, tak milión na druhú delené 2, a potom Som zvýrazní to, čo konečná odpoveď bola akonáhle sme sa odpočíta z n deleno 2. A tvrdenie, budem teraz robiť, je kto sakra zaujíma, či si odpočítať z trochu starý n na 2, keď prvý Súčasťou tohto vzorca je tak oveľa väčší? Je dominantou druhej Termín, n na druhú deleno 2 je tak oveľa väčší, jasne, ako n dostane veľký ako milión, to je naozaj veľký rozdiel v koniec dňa medzi 500000000000 a 499999500000? Nie tak celkom. A tak to, čo budeme robiť, čo počítačoví odborníci sa ignorovať tie nižšieho rádu podmienky a sa niečo také a naozaj len zjednodušiť na termín, ktorý to bude jedno. Väčšia naše súbory dát, tým väčšia Naša databáza získať, tým viac webových stránok musíme hľadať, viac priatelia máte na Facebooku. 

Ako n zväčšuje, sme naozaj bude sa starať o najväčší Výraz v každej takejto analýze naše algoritmy výkon. A ja som chcel povedať, že vieš, čo, bubble sort je na objednávku veľký O, na poradí n na druhú. Nie je to zrovna n na druhú, ako sme videli, ale kto naozaj zaujíma o tých menších podmienkach, a úprimne povedané, kto naozaj zaujíma, či budeme deliť dve? To je len konštantný faktor. A 500 miliárd, v porovnaní s 250 miliárd naozaj tak veľký problém? Som mohol len čakať jeden rok, nechať notebook doslova sa dvakrát tak rýchlo v hardvéri, a že tak nejako rozdiel proste zmizne prirodzene v priebehu času. 

To, čo zaujíma je výraz, časť výrazu, že sa to líši ako náš vstup dostane väčšie a väčšie. A skutočne, v reálnom svete, to je to, čo sa deje ďalej Je vstupy do našich problémov a algoritmy sú stále väčšie. Tak veľký O bude zápis, asymptotickej notácie, ktorý sme práve použiť ako počítačoví experti popísať výkon, alebo čas beží, algoritmu. Takže môžeme porovnávať algoritmy na rôznych počítačoch písomných rôznymi ľuďmi, s použitím niektoré zásadne podobné metriky ako je počet porovnaní ste robiť, alebo možno počet swapov robíte. 

Čo my nebudeme počet je množstvo času, , Ktorý prechádza na hodiny na stene typicky. Čo my nebudeme sa báť o tom, je, koľko pamäte používate dnes na najmenej, aj keď je to iný zdroj môžeme merať. Budeme sa snažiť založiť svoje analýzy na len základné operácie, tie, úprimne, že môžete vidieť najviac vizuálne. Takže niečo ako veľký O n štvorcový, tvrdím, že O n na druhú je horná hranica na takzvaný doba chodu bublín druhu. Inými slovami, ak máte chcel tvrdiť, že je tu Tento horný limit na tom, koľko kroky algoritmus môže trvať, že to bude vo veľkom O n v tomto prípade štvorcový, horná hranica. 

Čo keby som namiesto toho zmeniť príbeh sa nejedná o bubble sort, ale o to hornú hranicu. Spomeniete si na algoritme že sme sa pozrel na už ktorého horná hranica, maximálny meranie času alebo prevádzky, by sa povedať, že je ohraničená o n, lineárne funkcie, nie je kvadratická ten, ktorý je zakrivený? Čo je to algoritmus, ktorý vždy netrvá dlhšie než ako n krokov, alebo 2n krokov, alebo 3n kroky? Jo? 

Divákov: Hľadanie najväčšie číslo v zozname? 

SPEAKER: Perfektné, hľadanie najväčšie číslo v zozname. Ak som dal zoznam ľudia napríklad, Každý, kto ich drží číslo, aký je maximálny počet krokov, to by ma vziať, primerane inteligentný človek, nájsť najväčšie osoby v tomto zozname? n, že jo? Vzhľadom k tomu, v najhoršom prípade, kedy je možné, že najväčšia hodnota byť? Jasné, úplne na konci. Takže v najhoršom prípade horná hranica, možno som musieť ísť celú cestu tu a byť rád, oh, tu je číslo osem, alebo čo, že hodnota je. Teraz to bude len hlúpy keď som išiel ďalej, že jo? Hľadáte viac a viac prvkov v prípade, že posledný z nich je tam? Tak isto, n je horná hranica. Nepotrebujem, aby sa viac krokov, ako je. 

Čo keď namiesto toho navrhuje, aby sú algoritmy v tomto svete, majú prevádzkovú dobu, ktorá je ohraničené veľkým O log n log n? Tam, kde sme videli skôr? Jo? 

Divákov: V telefónnom zozname problém? SPEAKER: Ako telefónneho zoznamu problém. Čo bolo meradlom toho, ako veľa času a koľko ju strhne trvalo mi nájsť niekoho, ako je Mike Smith v telefónnom zozname? Vyhlasoval sme, že log n, a aj keď nepoznajú, alebo je to trochu zahmlený, čo logaritmus alebo exponent bol, Len nezabudnite, že log n všeobecne sa odkazuje na proces, v tomto prípade delenia niečo v polovici znova a znova, a znova, a znova, tak, že dostane stále malý, ako to urobiť. 

Takže log n označuje, iste, do telefónneho zoznamu napríklad binárne vyhľadávanie v teórii, keď sme mal virtuálne dvere na palube, alebo keď bol Sean niečo hľadal. Keby bol použitý binárne vyhľadávanie, binárny log n bude horná hranica na tom, koľko čas, ktorý trvá. Ale tie algoritmy, ktoré bežali v log n predpokladá, aké kľúčové detail? Že zoznam bol triedený, že jo? Algoritmus ak je zle Váš vstup netriedi, a napriek tomu, že používate niečo ako binárne vyhľadávanie pretože by ste mohli skočiť priamo cez prvku bez toho aby si uvedomil, že je to naozaj tam. 

A teraz, čo by to mohlo znamenať, veľký O jedného? To neznamená, že algoritmu trvá jeden a len jeden krok, to jednoducho znamená, že to trvá konštantný počet krokov. Možno je to jeden, možno je to 10, možno je to 1000, ale je to nezávislý Veľkosť problému. Bez ohľadu na to, aký veľký je n, časová konštanta algoritmus má vždy rovnaký počet krokov. Takže to, čo by mohlo byť algoritmus sme hovorili o, alebo len intuitívne, že k vám príde, že vždy beží v takzvanej konštantnom čase? Jo? 

Divákov: Pridajte dve čísla. SPEAKER: Pridajte dve čísla, 2 plus 2 sa rovná 4, hotovo. Tak to by mohlo fungovať, čo iné? Ako sa o viac skutočnom svete, nie? 

Divákov: Hľadanie Prvá vec, ktorú v zozname. SPEAKER: Nájdenie prvý prvok v zozname, iste. Sme vlastne hovorili o poliach už ako sa dostať na prvý prvok v matici, bez ohľadu na to, ako dlho pole je v C kóde? Stačí použiť ako držiak bum, ste tam nula notácie, ty. A samozrejme poľa, ako stranou, Podpora niečo všeobecne známe, ako náhodný prístup, s priamym prístupom pamäť, pretože môžete doslova preskočiť na jednom mieste. Môžeme to urobiť ešte jednoduchšie môžeme pretočiť na týždeň nulovej keď sme nuly. Koľko času to trvať povedať, blok Scratch vykonať? Len konštantný čas, že jo? Povedz niečo, povedz niečo, nezáleží na tom, ako veľké škrabance svet, je to vždy bude trvať rovnakú dobu proste niečo povedať. 

Tak to je časová konštanta, ale čo druhá strana? Keby tomu tak bolo vyššie hranice, čo chceme popísať dolnej medze z našich algoritmov beží čas? Takmer v najlepšom prípade potenciálne, ak chcete, keď tieto podmienky by sa mohli vzťahovať k najlepším puzdrá, najhoršie prípady, priemer púzdra viac všeobecne, ale poďme sa sústrediť len Na spodnej hranice všeobecne. Čo je to algoritmus, ktorý má dolná hranica n krokov, alebo 2n krokov, alebo 3n kroky? Niektoré faktor n krokov, to je jeho dolná hranica. Jo? 

Divákov: Bubble sort? 

SPEAKER: Bubble sort sa budete minimálne n krokov, prečo? Prečo tomu tak je? Prečo by to začiatok prísť k vám intuitívne, aj keď to nie je len ešte? Jo? 

Divákov: [nepočuteľné]. SPEAKER: Presne tak. V najlepšom možnom scenári bublina triediť a mnoho algoritmov, ak odovzdám vám osem ľudí ktorý už je zoradený, že by bolo pochabé pre vás, algoritmus, ísť tam a späť viac ako raz, nie? Vzhľadom k tomu, akonáhle sa prejsť zoznam raz, mali by ste si uvedomiť, oh, som žiadny swapy, tento zoznam je triedený, exit. Ale, čo sa deje, aby vás n krokov. 

A naopak, čo je iný spôsob, ako o tom premýšľať? Bubble sort je omega, aby som tak povedal, n, pretože keď sa pozriete na menej ako n prvkov, čo sa je tu zásadný problém? Neviete, či je to triedenie, doprava. Sme ľudia, môže dôjsť pohľad na osem ľudí a byť rád, ach, je to triedenie, že si mi n krokov neberie, ale stalo sa. Tvoje oči, aj keď tak nejako zo majú veľký zorné pole, ste sa pozreli na ôsmich prvkov, ste sa pozreli na osem osôb, to je osem krokov efektívne. A len vtedy, ak som prejsť celý Zoznam mám uvedomiť, áno, triediť. Ak by som sa zastaví na mysli všetky Dobre, je to celkom radené tak ďaleko, aké sú šance, že to nie je triedené? To algoritmy nebude správne. Môže byť rýchlejší, ale nesprávne. 

Takže teraz máme spôsob, ako popisujúce dolná hranica, a čo konštantnom čase? Čo je to algoritmus, ktorý má nižší viazaná na jeho chode dobe jedného? 1 krok, dva kroky, 10 krokov, ale konštantná, nezávisle na n, Veľkosť vstupu? Jo, v chrbte. 

Divákov: printf? SPEAKER: Čo je to? Divákov: printf? SPEAKER: printf. OK, iste. Tak to trvá stanovenom počte krokov. A ja som mala teď-- teraz hovoríme o C kódu a nie Scratch, niečo ako povedzme, s printf, by sme mali začať, aby si opatrný. Vzhľadom k tomu, printf sa vziať vstup, je to reťazec, a reťazce to technicky mať dĺžku. Takže ak chceme teraz vybrať na vás, či vám to nebude vadiť, technicky by sme mohli tvrdiť, že printf to sa s premennou dĺžkou vstup, a iste by to mohlo trvať dlhšie Doba tlače reťazec tak dlho, ako tak dlho. 

A čo keď vezmeme do úvahy len triedenie a vyhľadávanie príkladov? Čo Mike Smith v telefóne kniha, alebo binárne vyhľadávanie všeobecne? V najlepšom prípade, čo sa môže stať? Otvoril som telefónny zoznam, a bum, tam je číslo Mike Smith. Nemôžem ho zavolať hneď. 

Urobil jeden krok, možno dva kroky, ale konštantný počet krokov keď som mal šťastie. A úprimne povedané, sme videli na Pondelok váš spolužiak dostať celkom šťastie dvakrát za sebou. A to je skutočne konštantná čas v dolná hranica na algoritme sa jedná o hľadanie číslo 50 za tie zatvorené dvere. 

Teraz, rovnako ako stranou, keď zistíte, že tak veľký O, horná hranica, a omega, dolná hranica, sú jeden v rovnakej, že je rovnaký vzorec v zátvorky, môžete tiež povedať, len pre chuť, , Že niečo, čo je v theta n alebo theta nejaké iné hodnoty. To jednoducho znamená, že keď veľká O a omega sú rovnaké. A čo výber druhu teraz? Využime túto novú slovnú zásobu. Vo výbere druhu, o čom sme robiť znova a znova a znova? Bol som tam a späť cez zoznam, hľadá pre koho? Najmenšie číslo. 

Tak koľko krokov, ako veľa porovnaní urobil ja musieť urobiť, aby sa zistiť, kto najmenší prvok v zozname je? n mínus 1, nie? Pretože keď som začať s jedným Som vzhľadom k tomu, a začnem ho porovnávanie, potom on alebo ona, ho alebo ona, on alebo ona, som možno spárovať iba prvky spolu n mínus 1 krát. Takže výber trochu podobne sa n mínus 1 krok prvýkrát. 

Koľko krokov to ma vziať nájsť druhý najmenší prvok? n mínus 2, pretože som bol hlúpy ak Stále sa pozerá na rovnakých ľudí znova, či som ho už vybrali alebo ju a dať ich na ich miesto. A tretí krok, n mínus 3, potom n mínus štyri. Videli sme tento model pred, a skutočne Výber triedenie podobne je horná hranica n na druhú, ak budeme robiť až ten zhrnutie. Aká je jeho dolná hranica, výber trochu? Minimálne, koľko výber času musí triedenie sa, ako sa nám to definované v pondelok? Navrhnúť dve možnosti. Možno je to n, ako predtým. Možno, že to je n na druhú, ako to Teraz je ako horná hranica. 

Divákov: n na druhú. SPEAKER: n na druhú. Prečo? 

Divákov: Pretože máte definovať [nepočuteľné]. 

SPEAKER: Presne tak. Aspoň ako som je definované výber druhu to bolo dosť naivné, pokračuj, nájsť najmenší prvok. Iďte zase, nájsť najmenší prvok. Iďte zase, nájsť najmenší prvok. Neexistuje žiadny druh optimalizácia v tam, že môže mi dovoľte ukončiť po len n alebo tak kroky. Takže naozaj, výber triedenie, omega n na druhú. 

Čo vloženie druhu, kde som vzal ktorý som dostal, a potom som ho zvalil alebo ju na správne miesto? Potom som pristúpil k druhej osobe, zvalil ho na správnom mieste. Potom ďalšia osoba, zvalil ho alebo ju na správnom mieste. Všimnite si, že je to veľmi lineárne, aby som tak povedal. Som priamka, ja som Nie je tam a späť, Nikdy som sa obzrel nie, ale čo sa deje, keď som sa ho vložiť alebo ju do začiatku zoznam ako sme to urobili v pondelok? Čo sa deje? Jo? Divákov: [nepočuteľné]. SPEAKER: Jo, to bol úlovok, nie? Možno pamätáte z svojimi spolužiakmi, ak sa robili akýkoľvek pohyb s ich nohy, to je operácia. Takže v prípade, že boli traja ľudia tu a nový človek patril tamto, na dlhú fázu, ako je táto, iste, že alebo mohla jednoducho ísť až do samého konca. Ale ak uvažujete o počítača a polia pamäti, títo ľudia idú musieť zamiešať cez aby sa priestor pre túto osobu. A tak, aby n mínus 1 shufflings, n mínus 2 shufflings, n mínus 3 shufflings je len trochu sa deje za mnou, nie predo mnou ako predtým, v istom zmysle. Teraz ako stranou a ako ste mohli vidieť on-line ak začnete vŕtať o druhy, je tam toľko rôznych ty tam, niektoré z nich lepší než ostatní. V skutočnosti, je jedným bogosort to je celkom zábavné vzhliadnuť. Bogosort má sadu čísla alebo hovoria, balíček kariet, náhodne zamieša je a skontroluje, či oni sú radené. A ak nie, urobí to znova. A ak nie, urobí to znova. Ak nie, robí to znova. Neuveriteľne hlúpy. 

A skutočne, keď si prečítate ako Wikipedia článku, jeho prezývka je hlúpy druh. To bude nakoniec fungovať, dúfajme, že vzhľadom na to dostatok času, ale to množstvo času, môže trvať nejakú dobu. Takže ak by som mohol, poďme rýchlosti vecí up od Mary Beth je napríklad skôr tým, že má ešte niekoľko ďalších prvkov, ale ďalšie dva procesory. Dvaja ľudia, ak máte Nevadilo by mi to spojenie. Ako sa o jeden sem, a poďme jít-- nikoho tam? Nikto tam? OK. Tie s čiernou košele, áno, poď dole. Tak jo, Ako sa voláte? 

DIVÁKOV: Peter. 

SPEAKER: Čo je to? 

DIVÁKOV: Peter. SPEAKER: Peter Dávid, rád ťa spoznávam. Dobre, máme Petra tu, ak máte chcú prísť na stôl sem. A Ako sa voláte? 

DIVÁKOV: Elena. SPEAKER: Elena. OK, rád ťa spoznávam. Elena stretnúť Petera. Peter, Elena. A budeme potrebovať Andrew sa aj tu, prosím. A vaša výzva sa deje aby triediť balíček kariet. A ak nepoznáte, paluba kariet by malo v konečnom dôsledku zoradiť trochu niečo ako Tu urobíme kluby, potom lopatky, potom srdce a diamanty, od esa ako jeden, celú cestu až ku kráľovi. 

Karty budem vám sa bude 52 v množstve. Chystáme sa podobne čas vás za chvíľu. Budeme hádzať Andrew na obrazovke tu tak sa pozerať, ako to urobíte. A aby to všetko je to viac vidieť, to sú karty Dostal som na Amazonu. Takže už sú náhodne radené, a budeme vám čas. A ideme na udržať skutočný tentoraz takže budeme snažiť tlačiť pretože inak to bude únavné rýchlo. Ak by ste mohli pokračovať triediť 52 prvky spolu cez niektoré prostriedky, hneď. 

A opäť, ako sme sa pozerať na to chlapci robiť čo, na konci bude produkovať jasné Výsledkom je, premýšľať o tom, naozaj ako si každý robí, ako môžete to popísať. Vzhľadom k tomu, opäť sa jedná o Všetky procesy, algoritmy ktoré berieme ako samozrejmosť ako človek. Ale pravdepodobne ste už dlho intuícia, dlho predtým, než vás, aj myšlienka o tom, výpočtová technika vám trieda mohla byť dôvodom pre intuíciu s pre riešenie problémov, ako je tento. Ale akonáhle spoznáte vzory a začať formalizovať kroky, s ktorými máte riešenie týchto problémov, zistíte, že môžete vyriešiť veľa zaujímavejšie a oveľa zložitejšie problémy rýchlo. Takže niekto z publika, čo je aspoň jeden prvok z algoritmu že používate tu? 

Divákov: [nepočuteľné] SPEAKER: Čo je to? DIVÁKOV: Podľa obleku. SPEAKER: Podľa obleku. Takže najprv sa klastrovanie všetky diamanty spoločne Zdá sa, že všetky srdce spolu sa zdá, a tak ďalej, a to bez ohľadu pre čísla na kartách. A teraz sa zdá, napríklad, k triedenie je podľa čísla. Veľmi dobre. 

Dobre, takže to, čo sa byť posledným krokom potom tu? Akonáhle budeme mať štyri triedených obleky, čo to musíme urobiť, aby sa štyri pilotmi , Aby sa dosiahlo jednej radené palubu, jednoducho? Preto musíme znova zlúčiť. 

Takže tam je to zaujímavý nápad, ktorý opäť Trúfam si tvrdiť, je veľmi intuitívne, aj ak ste možno nikdy facku tento druh štítku na to. Táto základná predstava o rozdelení problém nie je v polovici tejto doby, ale aspoň do štyroch častí. Riešenie do značnej miery v podstate identické problémy izolovane od seba, a zlúčenie výsledkov. A vynikajúce, hotovo. Tak jo, malý a veľký okruh potlesk, keby sme mohli. 

[APPLAUSE] 

SPEAKER: Nemám poňatia, čo budete robiť s nimi, ale tu to máte. Ďakujem moc. Tak sa pozrime, dve minúty a osem sekúnd, ak by ste chceli vyzvať svojich priateľov. Čo sa potom bude by sa od tohto že môžeme využiť všeobecne? No, myslím, že späť do Toto pole čísel, a myslím, že teraz vrátiť k niektorým pseudokód písali sme v minulosti, a to pseudokód pre riešenie telefónneho zoznamu problém. Pričom v pseudokódu I vymenoval viac metodický spôsob popisovať, ako som to urobil veľmi intuitívne ľudský algoritmus delenia telefón knihy na polovicu, opakovať, opakovať, opakovať, kým nenájdem niekoho, ako Mike Smith, v prípade, že je naozaj v telefónnom zozname. 

Ale nejako som použiť to, čo budem hovoriť veľmi iteratívny prístup tu najmä oznámenia linka 8 a linka 11. To sú dôkazy o iteratívny prístup, prístup smyčkování, pretože to je presne to, správanie, ktoré vyvolávajú. Tieto riadky obaja, že ísť do riadok tri, a môžete trochu myslieť, že vo vašom mysli oko ako slučka. Je to hovorím, ísť späť ku kroku tri a opakovať znovu a znovu, a znovu. 

Ale čo keď budeme využívať kľúčovú myšlienku tu, že sme nemali v poslednej dobe, a zjednodušiť linky 8 a riadok 11 a ich susedia ako je len to, žlto. Nie je to v podstate skrátenie pseudokód moc, ale je to v podstate mení povahu môjho algoritmu. To, čo som teraz povedal v kroku 7, v kroku 10, je hľadať Mike v presne rovnakým spôsobom, ale len v ľavej polpenzia alebo pravú polovicu. 

Takže inými slovami, v prípade, Začnem od kroku jedna, zdvihnúť telefónny zoznam, otvorený stred z telefónneho zoznamu, pozrite sa na mená, ak Smith patrí medzi Názov je, zavolajte Mike, inak ak Smith predtým v knihe krok za sedem hľadať Mike v ľavej polovici knihy. Ale trochu pocit, ako to nechal ma visí, že jo? V žltej, je inštrukcie, ale ako to mám hľadanie Mike v ľavej polovica z telefónneho zoznamu? Kde mám algoritmus, s ktorým som Môžete hľadať niekoho, ako je Mike Smith? No, je to zíza nás tvárou v tvár. Môžem doslova použiť presne rovnaký program skutočne ísť až na vrchol Znovu a znovu beží rovnaké riadky kódu. 

Takže aj keď by to malo cítiť ako trochu cyklické definície kam odpovede niekto Otázka, ktorú tak nejako sa pýtať opäť rovnaká otázka, ako prečo, prečo, prečo? Skutočnosťou je, pretože sme pevne dané niekoľko špeciálnych liniek, krok 4, , Ktorý je v prípade, a krok 12, ktorý je v podstate ďalšia vetva, pretože máme tie provizórium opatrenia, Tento algoritmus sa ukončí, ak budeme nájsť Mike, alebo ak to neurobíme. Ale v kroku 7 a 10 teraz máme čo budeme hovoriť rekurzívny algoritmus. A rekurzia je naozaj silný nápad to je trochu myseľ ohýbanie na prvý, že teraz môžeme aplikovať takto. 

Merge sort bude posledný druh, ktorý sa pozrieme na, aspoň v triede formálne. A to je zásadne odlišná z tých posledných troch, a iste Posledné štyri ak zahrnieme bogosort. Tu je pseudokód pre zlučovacie druhu. Keď sa na vstupe n prvkov tak, vzhľadom k poľa veľkosti n, ak n je menšie ako 2, vrátiť. Tak prečo mám, že zdravý rozum skontrolovať ako prvý? Aký je dôsledok, ak odovzdám vás pole, ktorého dĺžka n je menšia ako 2? Je to už zoradený, samozrejme, že jo? Pretože zoznam má buď jeden prvok, ktorý je triviálne radené, pretože je to Jediné, čo tam. Alebo je to o veľkosti nula, čo znamená, nič vyriešiť, tak od prírody to je triedený. Je tu len nič zlého tam. Tak to je náš takzvaný referenčný prípad. 

To je podobné v duchu na to, čo sme urobili s Mikom. Ak sa Mike v telefónnom zozname, zavolajte mu. Ak tam nie je, vzdať. Je to takzvaný referenčný prípad, aby sa ubezpečil, Tento algoritmus na konci dňa sa zastaví v určitých okolností. 

Ale tu je ten skok viery teraz, inak, zoradiť ľavú polovicu prvkov, zoradiť právo polovica z prvkov, a potom zlúčiť zoradené polovice. A tu je miesto, kde sa cíti to, že sme Copping von. Požiadal som vás, aby ste triedenie n prvkov, a ja som riekol: OK, to je triedenie doľava a triedenie právo. Ale ja hovorím jedno Ďalšia vec, a to je kľúčové téma sa zdá, v intuíciu tak ďaleko, tam je to tretí krok zlučovanie. Ktoré, aj keď sa zdá byť tak hlúpy v duchu, ako práve zlúčiť veci spolu, sa zdá byť kľúčovým krokom smerom k opätovnú montáž dvoch problémov, ktoré boli rozdelené nakoniec v polovici. 

Takže zlúčiť druh, ideme na to, ak budete humor, aby som sa ešte jednu demonštráciu, len preto, že máme nejaké Čísla pracovať. Môžem u Vás vymeniť osem stres lopty pre osem ľudí? Dobre, a čo vy tri, vy štyria v tejto časti, päť, šesť, a poďme do 7, 8, poď hore. OK, jo OK. Mínus 8, ideme na to, plus 1. Výborne. Dobre poď hore, poďme Rýchlo vám čísel. Číslo dve, číslo tri, číslo štyri, číslo päť, šesť, sedem a osem. Urobil som osem správne tentoraz. 

OK, tak do toho, ak by ste mohol, a zoraďte v pôvodnom poradí že sme mali včera, ktorá sa zaoberala takto, ak vám to nebude vadiť. A ideme na to pred stolom. Dobre, takže zlúčiť druh. To je miesto, kde to bude dostať celkom zaujímavé, pretože to vyzerá, že dávať sám seba oveľa menej informácií dnes. 

Takže zlúčiť druh v prvom rade na vstupe n prvkov, a je samozrejme nie menej ako dva, je to osem, takže mám trochu viac práce. Takže teraz psychicky sme sa ako trieda sú teraz v inom sektore, čo znamená, že tri kroky. Po prvé, musím vyriešiť ľavá polovica prvkov. Tak ako mám ísť asi robí? No, ja idem na druh mentálne rozdeliť zoznam tu nemáte k fyzicky pohybovať, a ja som Zameriam sa iba na ľavá polovica prvkov tu. Tak ako mám ísť o triedení zoznam sa veľkosti štyri? Čo je môj algoritmus? Najprv som skontrolujte n menšia než dva, nie, tak som sa pristúpiť k bloku iného znovu. Zoradiť ľavej polovici prvkov. 

Takže znova, mentálne, a to je tam, kde Máte pribúdať veľa duševné histórie, ak chcete. Teraz triedenie ľavej polovica z ľavej polovice. Dobre, takže teraz volám rovnaký korešpondencie algoritmus triedenia, n je menšia než dva? Nie, je to dva, takže musím vyriešiť ľavá polovica, a pravú polovicu. Tak ideme na to, triedenie ľavej polovice. Prečo nie len jeden krok vpred. Ako sa voláte? 

DIVÁKOV: Darren. 

SPEAKER: Dan. Dan urobil krok vpred. 

DIVÁKOV: Darren. SPEAKER: Darren, hotovo. Hovorila ste, že Darrena alebo Dan? 

DIVÁKOV: Darren. 

SPEAKER: Darren. OK, Darren pristúpil dopredu a on je teraz radené. A to je takmer stupídne tvrdenie, že jo? Nemám naozaj Zdá sa, že dosiahnutie niečo, ale poďme pokračovať. Teraz mi dovoľte zoradiť právo polovica z týchto prvkov. Ako sa voláte? 

DIVÁKOV: Luke. 

SPEAKER: Luke. Poď, krok vpred. Hotovo, som radené Luku. Ľavá polovica je teraz triedené a pravá polovica je teraz triedené, ale zase tam je kľúčovým krokom tu. Čo u potrebné urobiť? Zlúčiť zoradené polovice. Teraz budeme jednoducho musieť všetci sem a tam tak, pretože som tak trochu potrebovať nejaký odkladací priestor. Je to skoro, ako sú tieto chlapci sú na stole, a ja potrebujem nejaký priestor je pohybovať ďalej. Takže budem zlúčiť vy od pohľadu v ľavej polovici a pravej polovici. A kto zrejme je na prvom mieste, vľavo alebo vpravo polovica polovice? Takže pravá polovica, takže poďme Luka nad tu pôvodnej polohy Darren. A teraz zlúčiť ich ľavú polovicu v, Darren sa bude pohybovať práve tam. 

Tak sa cíti ako takmer bublina druh účinku, ale moja základná algoritmus, veľmi odlišné tentoraz. Ale teraz je miesto, kde sa veci trochu nepríjemné, pretože ste musieť pretočiť mentálne kde som odísť preč. Práve som sa spojil zotriedené polovice, čo znamená, že som tam, kde vo svojom algoritmu? Musím vyriešiť pravú polovicu, nie? 

Ak máte vzad, a to doslova na videu, budete vidieť, že sme sa dostali do tejto bod Luke a Darren triedením doľava polovica z ľavej polovice. Potom sme sa spojil tie triedené polovice, ktoré znamená, že ďalším krokom je triedenie Pravá polovica ľavej polovici. Dobre, tak poďme to rýchlejšie. Tak jo, šesť, budem tvrdiť, ste teraz triedené, poď dopredu. Ako sa voláte? 

DIVÁKOV: Adriano. 

SPEAKER: Adriano. Adriano je teraz radené. A Ako sa voláte? 

DIVÁKOV: Alex. 

SPEAKER: Alex je teraz radené. Ľavá polovica, pravá polovica, čo je posledný krok? Zlúčiť. Celkom triviálne, takže som k fúzii v šiestich, krok späť, osem, urobiť krok späť. A teraz si toho všimnúť je užitočné stánok s jedlom, čo je teraz platí o ľavej polovici zoznam, a to bez ohľadu na to, ako sme začali? To je triedený. 

Teraz to nie je zoradený veľký schéme vecí, ale to je radený samostatne z druhej polovice. A teraz, čo krok to som na tom, či som sa udržať prevíjanie, ako príbeh začal? Teraz musím vyriešiť pravú polovicu. Takže teraz sme cestu späť na začiatok príbehu, a poďme na to rýchlejšie. Takže budem triediť pravá polovica celého zoznamu. Aký je ďalší krok? Zoradiť ľavú polovicu pravej polovici. Zoradiť ľavej polovici ľavá polovica v pravej polovici. A Ako sa voláte? 

DIVÁKOV: Omar. 

SPEAKER: Omar, krok vpred, hotovo. Ľavá polovica je triedený. A Ako sa voláte? 

DIVÁKOV: Chris. 

SPEAKER: Chris, krok vpred, ste teraz radené. Čo je kľúčovým krokom teraz? Zlúčiť. Takže človek sa chystá zlúčiť svoje miesto tu, ak by ste mohli urobiť krok späť, a tri sa chystá krok späť, zlúčiť. Takže ľavá polovica Pravá polovica je teraz radené. Úprimne povedané, tento algoritmus pocit, ako by sme Strácate spôsobom viac času ako predtým, ale keď sme to urobili v reálnom čase, budeme vidieť, čo takeaways bude. A teraz som tu, že jo polovica pravej polovici, nechaj ma ísť napred a zoradiť ľavú polovicu. Krok vpred, Ako sa voláte? DIVÁKOV: Ramsey. SPEAKER: Ramsey je teraz radené. Ako sa voláte? 

DIVÁKOV: Marina. 

SPEAKER: Marina je teraz radené ako dobre, ak budete mať o jeden krok vpred. Kľúčovým krokom je tu teraz zlúčiť, som bude trhať zo svojich dvoch zoznamov, vľavo a vpravo. Päť bude na prvom mieste, a sedem sa chystá prísť ďalšie. A opäť, je to zámerné. Skutočnosť, že užívate kroky vpred a vzad má predstavovať, že nemôžeme do tohto algoritmu na mieste, ako ľahko ako bublinkové triedenie a výberu druhu, a vloženie triedenie, kde sa práve stále vymieňať ľudí. Doslova som potrebovať akúsi poškriabaniu papiera, v ktorom aby týchto ľudí keď som to zlúčenie, a potom som ich dať späť na miesto. A to je kľúč, pretože ja som s použitím nové zdroje, priestor, a to nielen čas. 

OK, to je úžasné. Ľavá polovica je triedený, pravá polovica je triedené, teraz ten kľúč zlúčenie krok. Ako to mám zlúčiť to? Takže ak budete nasledovať moje ľavá ruka a pravá ruka, Chystám sa ukázať svoju ľavú ruku na ľavej polovici, moja pravá ruka v pravej polovici, a teraz musím rozhodnúť, krok za krokom, ktorého sa zlúčia. Kto samozrejme na prvom mieste? Číslo jedna. Tak poď sem, tu je náš poznámkový blok. Takže teraz číslo jedna a oznámenia čo budem robiť s mojou pravou rukou, Chystám sa hýbať pravou rukou jedného krokom sa k bodu číslo tri, a teraz mám urobiť Rovnaké rozhodnutie. A vlastne stojí priamo v predné Lukáša tu, ak by ste mohli, pretože to je náš poznámkový blok. Tak kto je ďalší? Máme Luke s číslom dve alebo Chris s číslom tri. Je zrejmé, Luke, číslo dva, takže sa sem. 

Ale moja ľavá ruka teraz sa chystá byť zvýšený poukázať na Darrena, a tu je kľúč odniesť s zlúčenie, budem v tom pokračovať, Je zrejmé, že ak máte trochu o sledovať logiku. Ale moje ruky nikdy ísť späť, čo znamená, že som len niekedy sťahujú do odišiel s mojím proces zlúčenia, a že to bude kľúčom k naša analýza za chvíľu. 

Takže teraz poďme dokončiť rýchlo hore. Takže tri príde nabudúce, potom štyri príde nabudúce, a teraz päť príde nabudúce, potom šesť, a sedem a nakoniec osem. Cítim sa ako najpomalší algoritmus ešte, ale nie v prípade, vlastne nechajte ho bežať na rovnakom druhu o taktovaciu frekvenciu, takže sa hovoriť, s rovnakým tikajúce hodiny ako predtým. Prečo? No, poďme sa sa pozrieť na konečný výsledok. 

Vráťme sa tu, dovoľte mi, aby som vytiahnuť demonštrácii vizuálne z toho, čo sme práve urobili. Zväčšenie tu, na tomto strana tu, hovorí Firefox že chceme do fronty v tomto poli, poďme hovoria bublina druh, s ktorým teraz sme dobre oboznámení, Výber triedenie, čo je ďalší pomerne priamočiara, a teraz dnešné merge sort, ktorý bude naša vrcholná koniec. Dôvod, prečo to trvalo tak dlho tu s ľuďmi a ja slovne ich, samozrejme, ja som vysvetľovať každý krok. Ale ak ste jednoducho spustite tento, moc ako sme to urobili bubble sort a výber triediť nielen vizuálne, hodinky ako oveľa efektívnejšie to presadzovaním delenie a dobývanie môže byť pri aplikácii do dátového súboru, ktorý je Ani veľkosť osem, ale ešte oveľa, oveľa väčšie. Dám vám zlúčiť druh, vedľa strana s týmito ďalšími algoritmami. To dostane bolestivé rýchlo, a koniec nie je nijak zvlášť vrcholná, jednoducho skončiť radené. Ale kľúč odniesť je, že Pozri sa, ako ďaleko rýchlejšie zlúčiť druh bol, ak si myslíte, že som len tak si s vami. Ak sa nám tento jeden posledný čas, poďme znovu to, vráťme a vyberte bubliny druhu, a len tak pre srandu, Zvoľme vloženie triedenie, len pre istotu. A tentoraz opäť, poďme vyberte zlučovacie druh a poďme vlastne spustiť tieto bok po boku. 

A to nie je, v skutočnosti, náhoda. Čo som skutočne urobil je, že som rozdeliť svoj vstup na polovicu, opäť a znovu a znovu. A je to len toľkokrát môžete rozdeliť váš vstup do polovice, ľavá a vpravo. Aký je vzorec, ktorý držíme vidieť , Ktorý opisuje rozdelenie na dve polovice znova a znova, a znova, a znova? 

Divákov: log n. 

SPEAKER: log n. Ale potom je tu ešte jedna ďalší kľúčový krok, Tento algoritmus nie je nahlásená n krokov. Ak by bolo len prihlásiť n krokov, by sme byť v rovnakom probléme ako predtým, kde nemôže byť že všetko je triediť. Musíte sa minimálne pozrieť na n prvkov byť istí, že n prvky sú triedené, inak je to skok viery. 

Takže je to minimálne log n kroky, ale čo tejto kľúčovej zlúčenie kroku kde som sa spojil moje ľavá polovica a doprava polovice a prešiel cez javisko? Koľko krokov je zlúčiť? Je to n, ale neurobil som to len zlúčiť konečný čas. Na každej z týchto vnorených volaní, na každom z týchto vnorených zlučovanie, napriek tomu som radené. Aj zlúčil tieto dva chlapíkov, potom sa tieto dve chlapci, potom títo dvaja, a tak ďalej. 

Tak som sa zlúčenie znova a znova. Koľkokrát? Takže zakaždým, keď som sa rozdelil zoznam na polovicu, som zlúčenie. Rozdeľte zoznam na dve polovice, do zlúčenia. Takže v prípade, delenie zoznam môže byť vykonané log n krát, a zlúčenie nakoniec sa n kroky, čo by mohlo byť teraz horný viazaná na chod Doba nášho algoritmu? n log n. 

A vskutku, to je to, čo sme tu dosiahli. Takže myslíte, že ste vidieť vizuálne, keď tieto tri veci bežia bok po boku je n na druhú proti n na druhú proti n log n. Ktoré zásadným uvidíme, nielen dnes, ale v budúcnosti, je oveľa, oveľa rýchlejšie. Potlesk pre týchto ľudí, Ja sa za to odmení Antistresové loptičky. Poďme odložiť dnes, a Vás budeme vidieť v pondelok.