[Powered by Google Translate] [Săptămâna 3, Continuare]
>> [David J. Malan - Universitatea Harvard]
>> [Acest lucru este CS50. - CS50.TV]
>> Bine. Bine ai venit înapoi. Acest lucru este CS50 și acesta este sfârșitul săptămânii 3.
>> Deci, pentru cei nefamiliarizați ani, trecut la Harvard a lansat ceea ce se numește Lab Inovare,
sau i-Lab, care este o clădire minunată peste râu în campus CBGC lui
care este deschis pentru studenții de colegiu, studenți SZG, studenți din toată campus peste,
inclusiv facultate, și este un loc să vină împreună pentru a lucra asupra lucrurilor inovatoare,
lucruri deosebit de antreprenoriale
Dacă ați răspuns și 0 sau mai mulți prieteni de gândire de a face ceva antreprenoriale
fie în timpul această clasă, după această clasă, sau dincolo.
>> Deci, unul din lucrurile pe care le fac pe termen lung este J aceste excursii,
dintre care unul este la New York, dintre care unul este de la Silicon Valley.
Spatiul este foarte limitat, dar este o oportunitate de a freca umerii cu MBA
si tinerilor absolventi de facultati din campus și, de fapt petrece timpul în domeniile respective
chat up startup-uri, chat up antreprenorii și place.
Deci, daca te intereseaza, a verifica afară această adresă URL aici.
Acesta este, de asemenea, disponibile pe slide-uri on-line.
>> Am putea tonul jos audio casa doar un pic?
Dacă doriți să vă alăturați nouă pentru masa de prânz de vineri, ora 01:15, în Fire & Ice, vă rugăm să cap acolo.
Ne cerem scuze dacă formularul este deja umplut de dată când ajunge acolo.
Dar vom continua această tradiție mai departe.
>> Astăzi vom continua discuția nivel mai ridicat al diferitelor probleme pe care le putem rezolva,
concentrându-se mult mai puțin, astăzi, cel puțin, pe cod și mult mai mult pe idei.
Deci, cred că înapoi la săptămâna 0 atunci când am rupt-o carte de telefon în jumătate,
al cărei obiectiv a fost de a face ceva, desigur, un pic dramatic
dar pentru a trimite punctul în care căutarea nu trebuie să fie, în mod necesar,
la fel de evident la prima vedere ca ai putea crede.
Și rezolvarea de probleme, în general, nu s-ar putea să fie în mod necesar întotdeauna cel mai bun -
Soluția cea mai evidentă ar putea să nu fie neapărat cel mai bun.
Așa că am avut această carte de telefon și, sincer, noi toți din această cameră au avut instincte,
cel mai probabil, pentru a începe în mijloc atunci când caută pentru Mike Smith și apoi du-te la stânga sau la dreapta
bazată pe orice literă a alfabetului am sa întâmplat să se încheie pe.
>> Dar ideea simplă pe care noi, oamenii, s-au luat de atât de mult timp
într-adevăr ar trebui să înceapă să vină în fruntea mintea ta
pentru că așa cum problemelor obține mult mai complexă decât o carte de telefon,
aceste aceleași perspective strălucite simple, sunt ceea ce sunt de gând să ne permită
pentru a rezolva problemele mult mai complicate și mai interesant,
printre care unele din lucrurile pe care le ia pentru a acordat deja aceste zile.
Miliarde de pagini web acolo, și totuși Google și Bing și cum ar fi
sunt capabili de a găsi lucruri pentru noi așa.
Asta nu se întâmplă prin utilizarea o căutare liniară, căutarea prin toate paginile web posibile.
Facebook este în măsură să-ți spun cine toți prietenii tăi sunt sau prieteni ai prietenilor,
și că prea se poate face aparent într-o clipă aceste zile
chiar dacă acestea au milioane de utilizatori.
>> Și așa cum ne-am rezolvat problemele de fapt, pe care în cele din urmă va reduce la scară
la ideile ne-am uitat la în săptămâna 0 și un pic mai mult astăzi.
Noi nu va re-executa acest algoritm, ci amintesc, de asemenea, am făcut-o în săptămâna 0 acest exercițiu
în cazul în care am toată lumea se ridice, să ia de la numărul 1,
și apoi am avut toată lumea auto-count de asociere off, adăugând numerele voastre impreuna,
apoi jumătate din banda se așeză pe fiecare iterație.
Așa că am trecut de la 500 de elevi la 250 la 125 și așa mai departe.
Dar, așa cum am spus, luni, ideea puternic acolo
a fost că, dacă ne-am dublat dimensiunea acestei probleme
și toți copiii de la Justiție sau CE 10 a intrat înapoi în cameră și ni sa alăturat,
ei bine, am putea număra, probabil, că tot grupul agregat
cu doar 1 repetare mare mai mult de bucla, deoarece acestea nu ar face decât poate dubla dimensiunea
sau în cazul în care CE 10 este un pic mai mult decat dublu marimea.
Și așa ne-ar trebui să-și petreacă un pic mai mult timp,
dar nu ar trebui să-și petreacă 400 sau 700 mai mulți pași.
>> Doar pentru a picta această imagine într-un mod care este un pic mai puțin abstractă, să nu se ridice toată lumea s-au.
Dar, dacă cei dintre voi care au ales să stea în orchestra de astăzi nu s-ar deranja în picioare,
hai sa vedem daca ne putem da seama cine dintre voi este cea mai inalta persoana
de a face același tip de algoritm comparative.
Deci, dacă sunteți ședinței în orchestră, îmi cer scuze, dar pasul 1, se ridice în picioare;
pasul 2, pereche off cu oricine din apropiere,
seama cine este mai inalt, si stai jos, dacă sunt mai scurte.
Apoi repeta.
[Elevi murmurând]
>> Bine.
Bine. Unul este lăsat în picioare. Care e numele tău? Andrew >>.
>> Andrew, esti cea mai inalta persoana din secțiunea orchestra de astăzi.
>> Felicitări. [Aplauze și aplauze] Ok. Au un loc. Așa că am găsit Andrew.
Dar cât timp ar fi luat eu, de exemplu, pentru a găsi Andrew
în această secțiune orchestră de 50 + sau cam asa ceva de oameni?
Aș fi putut să iau o abordare destul de simplă și începe aici.
Și am 2 persoane se ridice și eu doar le compara,
și apoi spun oricui este puțin mai scurt, "Bine, stai jos,"
și am de gând să-mi amintesc cine a fost persoana mai inalt.
Apoi Repet, repet, repet, și am atârnă pe cea mai inalta persoana
până când am găsit pe cineva puțin mai înalt decât ei, moment în care
persoana un pic mai scurt trebuie să stai apoi în jos.
Dar în faptul că algoritmul în această secțiune orchestră, în cazul în care există n de tine,
câți pași este ca algoritmul de gând să ia? >> [Elev] N.
>> Se va lua N, dreapta, pentru că în cel mai rău caz, ca să spunem așa,
cea mai inalta persoana este persoana foarte ultima pe care am ajunge la doar ghinion aleatoare.
Deci, în cel mai rău caz, timpul de rulare a algoritmului este liniar, e N,
unde n este numărul total de persoane în spațiu, dimensiunea problemei.
Ce zici de acest algoritm?
Faptul că toți s-au ridicat și apoi din nou, jumatate din voi se așeză,
jumătate dintre voi se așeză, jumătate dintre voi se așeză.
Câte măsuri ar fi luat ca daca nu e de tine aici n?
[Elev] n log n. >> Asta ar fi mai rău. Log n.
>> Deci log n, chiar daca nu-mi amintesc destul de ceea ce un logaritm este,
de acum, doar aprecia faptul că se referă cumva la acest înjumătățirea și înjumătățirea și înjumătățirea.
Aceasta nu trebuie să fie un factor de 2. Ar putea fi un factor de 3.
Dar e această repetiție de același tip de factor, astfel încât dimensiunea problemei începe aici
dar apoi imediat se duce aici, apoi aici, apoi aici, apoi aici.
Nu te lua inghitituri mici din problema, sunteți cu adevărat tocare departe la ea
cu o mare lovitura de fiecare dată.
Deci, am avut 50 de oameni, apoi 25, apoi 12 ½ sau 13 de oameni în picioare,
apoi 6 ½ și așa mai departe până când în cele din urmă în picioare doar Andrew a fost lăsat.
Deci, vom numi că log n, și puteți vizualiza această după cum urmează.
Amintesc de această imagine aici, unde un algoritm liniar este ca linia roșie acolo,
linia galbenă a fost de numărare prin algoritmul 2s pe care am folosit pentru studenții de numărare
în trecut, dar astăzi Sfântul Graal este de gând să rămână această linie verde
în cazul în care, dacă ne-am dublat numărul de persoane din secțiunea orchestra sau doar a spus,
dracu ', hai să toată lumea din intreaga camera se ridice în picioare, nu, o astfel de afacere de mare
pentru ca am dubla aproximativ cât de mulți oameni sunt aici,
1 iterație mai mult, nu o problemă.
>> Am gasit Andrew sau oricine se întâmplă să fie mai inalt decat Andrew
în mezanin sau în balcon.
Deci, această idee simplă pe care am luat atât de mult pentru a acordat într-o carte de telefon,
dau seama că există atât de multe locuri diferite în care o putem aplica.
Doar pentru a palmă unele jargon - de fapt, mai degrabă decât jargonul în primul rând,
lasă-mă să merg la această imagine aici.
Chiar acum am vorbit despre n și n / 2 și apoi jurnal de n,
dar putem veni cu siguranță, cu, așa cum vom de-a lungul semestrului,
alt fel de formule matematice pentru a descrie această noțiune generală timpului de funcționare.
Acestea sunt scoase din context, pentru acum, pentru că vom vedea în scurt timp
algoritmi că acestea reprezintă, de fapt.
>> Dar observați aici linia N liniar, linia dreaptă, este de fapt foarte scăzută îndreptat acum.
Asta e un fel de iluzie optică, în care ne schimba doar ceea ce reprezintă axa x
și axa y, și putem face un punct de linie dreaptă în orice direcție dorim.
Dar motivul pentru care este atât de aparent plat acum
este pentru că avem nevoie pentru a face loc pe acest grafic pentru ori mult mai lent de funcționare.
Pentru moment, știu că există unele algoritmi destul de rău în viață,
dintre care unele nu iau măsuri N sau, mai bine încă, dar n log pași mai multe.
Deci, deasupra liniei n aici, la partea de jos preaviz nu e log n ori de n,
și vom vedea ce înseamnă înainte de mult timp.
De mai sus, care este n pătrat, și nu am văzut nici un algoritmi n patrate încă, dar suntem pe cale să.
Și care arată foarte rău.
Nu e 2 la N, ceva exponențială, care se simte chiar mai rău.
Și totuși, curios, atunci nu e n cubulete, care, dacă ești un fel de a gândi înainte,
daca faci un fel de matematica, 2 la N de fapt, devine mult mai drept,
mult mai mare decât până n tocata daca te uiti la axele suficient de departe afară.
Deci, observați acum aceste axe sunt arbitrar 2 la 10 pe axa x.
>> Și ce înseamnă asta?
Asta inseamna 2 persoane la 10 de persoane într-o cameră.
Asta e tot ce înseamnă x: dimensiunea problemei, indiferent de context este.
Și o axă verticală acum este numărul de secunde sau numărul de pași -
unele unitate de timp.
Dar observați că este 0 - 60 și 0 la 10.
Dar, dacă ne fel de zoom, astfel cum s-ar putea în Excel sau unele software-ul grafice,
și vom merge până la 200.000, observați că ceva de genul 2 la n
este de gând să copleșească complet ori de funcționare a pătrat n,
n tocata, n log n - tot ceea ce am vorbit până acum despre.
Și totuși, de captură este atunci când începi să vorbești despre lucruri cum ar fi Facebook
în cazul în care aveți mai multe, mulți, mulți oameni toate interconectate,
n-ați persoane, fiecare dintre care ar putea avea cât mai multe ca prieteni n
în cazul în care toată lumea este un fel de amic-amic în lume,
bine, asta e de n ori n deja, așa că e n patrate prietenii posibile,
cel puțin în direcția 1, n prietenii pătrat posibile.
Așa că deja sugerează că căutarea Graficul socială Facebook, ca să spunem așa,
poate începe să fie exprimată în aceste tipuri de formule.
>> Ne vom întoarce și să facă atât de mult mai concret,
dar pentru moment, obiectivul pentru următoarele săptămâni mai multe
va fi sigur de a nu merge despre algoritmi de punere în aplicare sau cod
care sfârșesc prin a lua timp la fel de mult ca pe ceva de genul asta.
Dar lucrul fascinant despre știință de calculator, dacă veți continua in acest domeniu
luând în clase ca CS121, CS124, ambele din care sunt cursuri teorie,
este că există, de fapt unele probleme care există în această lume
că fundamental, în măsura în care știm, nu pot fi rezolvate mai repede
decât cel mai rău dintre aceste grafice de fapt sugereaza.
Deci, există o mulțime de probleme deschise în această lume pentru a face mult mai bine decât oamenii au până în prezent.
>> Așa că hai să începem apoi cu acest exemplu.
Am văzut lupta Sean cu acest aparat foto pe, mult prea neîndemânatic pe video.
Dar realitatea a fost atunci când Sean a fost însărcinat cu găsirea de la o placa ca aceasta numărul 7,
amintesc că am spus că, "Nu este undeva în spatele acestor bucăți de hârtie sau de usi albe
"Sean numărul 7,. Pare pentru noi."
Și a fost minunat ciudat pentru a viziona
pentru că el a fost într-adevăr se luptă cu această problemă.
Dar realitatea a fost Sean a făcut la fel ca oricine în camera ar fi putut face.
El a luat un pic mai mult decât o persoană tipic ar putea avea,
dar el a presupus că au existat unele truc la această problemă,
el a presupus că el lipsea ceva.
Și nu a ajutat faptul că sute de ochi au fost poartă în jos pe el.
>> Dar realitatea a fost în cazul de intrare la problemă este o grămadă de numere aleatoare
și ești rugat să găsească o astfel de număr,
cel mai bun il poti face este căutare liniară.
Start la stânga, trece la dreapta, sau de a începe de la dreapta, trece la stânga.
Retroactiv, am putea fi de gândire, "Sean, de ce nu ai inceput doar de la celălalt capăt?"
Ei bine, 7 ar fi putut la fel de usor a fost aici la întâmplare,
dar am pus-o acolo în mod deliberat pentru că m-am gândit că nu o să înceapă la sfârșitul anului.
Asa ca am un fel de manipulat situația, ci de întâmplare 7 ar putea fi oriunde.
Deci, pornind de la capătul din dreapta ar fi fost mai bine, atunci,
dar ce se întâmplă dacă anul următor am muta în altă parte 7?
Asta nu este o solutie fundamental nouă a problemei -
începând de la 1 capăt sau altul - cand ai de dat nici o alte ipoteze.
Deci, Sean a început să caute prin numerele și el a spus, "5 Asta nu e aici.".
Apoi, el a fost aici și a văzut 19, apoi a făcut o pauză de aproximativ 20 de secunde,
apoi a deschis asta pentru 13, iar apoi a devenit evident
faptul că nu pare a fi un model aici.
Acesta nu a fost de 1, 2, 3, 4 sau similar. Au fost de lacune în privința numere, care nu ajută.
Și de asemenea, faptul că am folosit aceste piese ieftine de hârtie pentru a acoperi numerele
este de fapt deliberată, pentru că dacă am eliminat toate aceste bucăți de hârtie,
cele mai multe dintre noi, Sean inclus, probabil, s-ar fi aruncat o privire fel de macroscopic
la tablă și a spus, "Oh, 7 este, evident, acolo." Am făcut-o instantaneu.
>> Și care ar putea fi modul în care creierul uman funcționează într-o anumită măsură,
dar, în realitate, cu ochii sau mintea a fost, probabil, skimming numerele de la dreapta la stânga,
la stânga la dreapta, de mijloc afară - ceva se întâmplă punct de vedere fiziologic
astfel încât m-am simtit ca aceasta se intampla instantaneu,
dar sansele sunt chiar pe plan intern a existat un fel de metodologii pentru a găsi 7.
Și într-adevăr, acum că vorbim despre tablouri si structuri de date
și în interiorul memoria unui calculator, singurul lucru pe care noi, oamenii, putem face
se uita la locațiile de memorie individuale 1 la un moment dat.
>> Deci, la fiecare altă locație ar putea la fel de bine să fie acoperite cu unele bucată de hârtie
deoarece nu putem vedea oricum. Putem face doar 1 lucru la un moment dat.
Deci, în acest caz, în cazul lui Sean, ne-am dus aici, și apoi ne-am dus aici
și apoi ne-am dus aici, aici, aici, aici, am inteligent până la sfârșitul anului
și doar un fel de omit aceasta arbitrar si a gasit acolo 7.
Acest lucru nu a fost deosebit de specială. Acesta a fost prea în ordine.
Dar el a găsit în cele din urmă 7.
Dar acum livrata acasa este într-adevăr cel mai bun pe care le puteți face atunci când se administrează nici o informație
altele decât numere aleatoriu sortate este de a porni de la stânga sau de dreapta începe de la.
Sau naiba, aveți posibilitatea să deschideți la întâmplare ușile, dar chiar si atunci ce înseamnă să fi aleatoare?
Ei bine, vom avea de a formaliza într-un fel ceea ce înseamnă pentru a începe aici,
apoi du-te aici, du-te atunci aici. Sean a făcut mare, și a fost doar distractiv sa ma uit.
Ce se întâmplă dacă în schimb vom schimba problema un pic și să aducă pe Sean din acest an, daca vrei?
Ar fi cineva confortabil vine pe scenă și rezolvarea unei probleme ușor diferită
și care figurează pe aparat de fotografiat?
>> Să mergem dincolo de orchestră, deoarece voi au fost destul de implicat astăzi deja.
Ce zici de la roz, în pălărie? Vino pe jos. Care este numele tau? Alex >>. Alex >>. Bine.
Deci, Alex va fi Sean acest an și va apărea în următorii câțiva ani
în valoare de CS50 prelegeri.
Alex, mă bucur să te cunosc. >> Bucur să te cunosc prea.
Provocarea la îndemână pentru tine este că aveți un pic mai ușor
în care vă spun aceleași numere, sunt aici, dar sunt sortate acum.
Deci, acum obiectivul dvs. este de a găsi numărul 7.
Și, de fapt, ar trebui să facem cu adevărat acest lucru - Ești un fel de înșelăciune, ca un computer, nu ar fi,
uitandu-se la ceea ce numere erau acum un moment.
Cu creta acest fapt nu este de gând să ajute tot atât de mult,
dar hai să te prefaci că nu știi ce matrice originală este.
Tot ce știu acum este că aveți o serie de numere sunt sortate
care ar putea avea spații între ele, și de obiectivul dvs. este de a găsi numărul 7.
Cum ați, un om rezonabil ființă, du-te despre găsirea numărul 7?
>> Du-te la mic la mare? Bine >>. Du-te la mic la mare.
Și să nu-i smulgă. Să ridica doar le ca să le putem refolosi.
Ok, deci 1. Așteaptă. Înainte de a continua, care a fost de 1, în mod clar greșit.
Deci, ce se întâmplă prin minte următoarea ta? Care e următoarea ta mișcare?
Următoarea. Bine >>. Următoarea. Bine. 3, astfel incorectă. Care e următoarea ta mișcare?
Continuă să mergi. >> Regulă. Continuă să mergi. 5.
Așa că ține în desfășurare, și să-mi dai asta pentru posteritate.
7. Excelent >>. Foarte bine. S-au găsit numărul 7. [Aplauze]
Așa că a fost bun, dar Sean găsit prea numărul 7.
Și eu susțin că nu au exploatat într-adevăr această bucată suplimentară de informații,
care este faptul că aceste numere sunt sortate.
Deci, putem face mai bine? Orice sugestii aici? Da, în spate.
[Elev] binar de căutare. >> Nu am nici o idee despre ceea ce caută binar este.
>> [Elev] Start în mijloc. >> Start în mijloc. Bine. Deci, hai sa vedem daca putem ajunge acolo.
Deci, dacă în loc să ți-am spus de la început de mijloc, mergeți mai departe și să deschidă ușa din mijloc.
Există 8 dintre ei, deci ai de gând să aibă de a alege arbitrar una
ușor la stânga sau la dreapta. Bine. 7! [Aplauze] Foarte frumos.
Bine, dar în cazul în care s-au mergem cu asta?
Să presupunem doar pentru a sparge cravată ați început aici
pentru că la fel ar fi putut întâmpla la fel de bine.
Trebuie doar sa întâmplat să știu că 7 a fost acolo. Deci, aceasta este de 13.
Deci, dacă acestea sunt sortate și ne-am început în mijloc,
ce s-ar mișcare optimă următoare au fost?
Du-te la stânga. Și astfel vine aici, de exemplu cartea de telefon din nou.
Dacă 13 este aici și știm Lista este sortata,
atunci toate aceste bucati de hartie sunt neinteresante pentru noi acum
pentru că știm deja că 7 trebuie să fie la stânga
în cazul în care aceste numere sunt sortate și am găsit 13.
>> Deci, ce e următoarea ta mișcare aici? >> Du-te la stânga. Bine >>, bine.
Deci, du-te la stânga, și - așteaptă, hei, hei, hei. Asta e inselat.
Deci ai gasit 7, dar ceea ce a fost algoritmul care tocmai am aplicat?
Start în mijloc. Bine >>. Deci, ce e extensie logică a acestui aceeași idee?
Oh, doar pentru acestea. Exact >>. Așa că am început >> aici. Bine >>.
Deci, acum ne-am dus ușor la stânga din nou. E 3.
Dar acum este livrata acasa interesant care o faci tu nu trebuie să pasă?
Aceste 2. Aceste >> 2. Deci, acum aceasta se poate merge departe, aceasta se poate merge departe.
Acum, problema care a fost de 8, apoi a fost de 4 marimea acum este dimensiunea 2.
Primim destul de aproape. Din nou, du-te la mijlocul acestor 2 elemente.
>> Bine. Deci e un fel de nefericit ca acum suntem mereu merge plecat pentru că suntem rotunjirea în jos.
Dar asta e bine pentru că acum ne arunca această distanță și orice altceva, lăsându-ne cu doar 7.
Să-i dăm o rundă de aplauze. Am gasit 7 din nou. [Aplauze] Ok. Sigur.
Așteaptă pentru doar 1 secundă.
Chiar dacă acest tip de proces următoarea luat un pic mai mult decât ne-am simtit ca ar fi,
sincer, instinctele tale prima au fost cele mai bune, nu? Am gasit 7 instantaneu.
Dar ne-ar fi gasit 7 mai rapid, indiferent de ceea ce, în acest exemplu față de aceasta
pentru că, dacă numerele sunt toate sortate, la fel ca paginile dintr-o carte de telefon,
aveți posibilitatea să taie într-adevăr, jumătate din problemă din nou și din nou și din nou.
Și nu e chiar atât de ușor pentru a vedea acest lucru cu doar 8 numere
spre deosebire de o carte de telefon de 1000 de pagini în cazul în care veți vedea cu adevărat vizual,
dar, în acest caz, aici, când Sean a fost căutați pentru 7,
câți pași în cel mai rău caz ar fi luat el? >> [Elev] 7.
7 în cel mai rău caz. Ei bine, în cel mai rău caz, nu 7, dacă există 8 usi aici.
Aceasta l-ar fi luat 8 pași.
>> Deci, dacă nu e usi n, s-ar fi luat Sean câțiva ani în urmă pași n.
Acum, în cazul tău, Alex, având în vedere că aceste numere sunt sortate -
și putem deduce un fel de acest lucru de la care am fost până acum în această poveste -
ceea ce este timpul de execuție al algoritmului mai inteligent lui Alex
de a începe de la mijloc si apoi repeta?
[Elev] 3. >> Deci va fi de 3, aproximativ, dacă te duci 8 la 4 la 2 la 1.
Deci, 3 trepte sau, mai general, care este log n din nou.
De fiecare dată când te reducerea la jumătate și înjumătățirea și înjumătățirea și înjumătățirea,
ca o expresie a acestei idei de log n.
Si pentru ca s-ar fi luat doar 3 pasi, și într-adevăr a făcut-o
odată ce am deschis ușile și reducerea la jumătate reducerea la jumătate,
întrucât acest lucru ar fi luat unele Sean 7 sau 8 trepte.
Deci, vă mulțumesc pentru a fi alături de noi în acest an. >> Multumesc. Mă bucur să te cunosc.
Mulțumesc lui Alex. De asemenea >>. [Aplauze]
>> Care este atunci implicarea reală a acestei?
Acum, imaginați că nu e 8 usi, care, sincer, toți dintre noi ar putea găsi ceva
în spatele ușilor 8 destul de repede doar prin ruperea bucățile de hârtie și merge cu instinctele noastre.
Dar dacă e un milion de uși? Ce dacă e 4 miliarde usi?
În cazul de 4 miliarde de usi, sunteți cu adevărat de gând să vreau să merg cu algoritmul lui Alex,
binar de căutare după cum vom începe numindu-l sau dezbina si cucereste, mai general,
în cazul în care vă păstrați înjumătățirea și înjumătățirea problema,
pentru că, dacă aveți 4 miliarde usi, de câte ori poți taie 4 miliarde jumătate?
[Elev] 32. Este de fapt >> 32. Puteți lucra asta pe o bucată de hârtie sau în capul tău.
Tu du-te 4000000000 - 2 miliarde to 1 miliard la o jumătate de miliard, la 250 milioane de euro, dot, dot, dot.
Și dacă faci afară matematica, ai de gând să obțineți într-adevăr 32,
și că, de fapt, se referă la informatică, deoarece ne bazăm, de obicei, în competențele de 2.
2 la 32 se întâmplă să fie de 4 miliarde de euro.
Deci, există o mulțime de relevanță pentru aceste tipuri de competențe de 2 în informatică.
>> Dar ce aproximativ 8 miliarde? Câți pași se că va lua în cazul în care există 8 miliarde usi?
[Elev] 33. Deci, 33 >>. Ce se întâmplă dacă nu există 16 miliarde usi? Câți pași se că va dura?
[Elev] 34. >> 34. Am putea continua acest tip de ad nauseam. Dar asta e un lucru puternic.
Puteți introduce miliarde de mai multe intrari la problema ta, dar, nu e mare lucru,
luați doar 1 muscatura suplimentare din ea și, astfel, ne dă ceva de genul cautare binara
sau dezbina si cucereste, mai general.
Dar eu sunt un fel de inselat aici, nu?
În cazul algoritmului lui Alex, ea a avut un avantaj de peste Sean.
Ea știa că aceste numere au fost sortate, dar Alex nu a trebuit să le sorta ea.
Am venit în avans de până la tablă și tipul de făcut-vă că
că am atras-le pe toate în ordine sortate, apoi le-am acoperit cu hârtie.
Dar cât de mult munca sa, care mă ia?
Dacă am fi pornit la drum cu aceste numere într-o ordine aparent aleatorie -
în acest caz, aceste numere simple, 1 până la 8 aici -
cum putem merge despre sortarea aceste valori?
Dacă ai fi fost un om dat această sarcină, ce fel de abordare intuitivă ar fi luați
pentru sortarea o grămadă de numere?
Aceste lucruri au fost stabilite ca piese de puzzle. Da.
>> [Elev] mi-ar lua fiecare număr și să o compare cu fiecare dintre
și să păstreze merge la stânga. Bine >>, bine.
Deci, ia fiecare număr, comparați-o cu cea de lângă ea,
și apoi să păstreze în mișcare de-a lungul doar lista, un fel de rejiggering lucrurile ca te duci.
Deci, aici avem o șansă, poate pentru cateva mai oameni buni sa se implice.
Avem 8 voluntari care au mai multe ar plăcea să vină?
O presiune mai puțin, deoarece nu ești singura. 1, 2, 3, 4, 5, 6, 7, 8.
Vino pe jos. Voi vor fi numerele de la 1 8.
Să vedem dacă nu putem face acest lucru sortare pentru Alex mult în același fel am făcut-o în prealabil.
1, 2, 3, 4.
Du-te și dacă ar fi, linia de sus pe scenă între suportul pentru muzică și mă aici
în aceeași ordine ca și de diapozitive pe ecran.
Uh-oh.
Vă vom lucra în următorul exemplu. Oh, stai, stai. Aici vom merge. Așteaptă.
Urmatorul exemplu este acum. Aici te duci. Numărul 8. Vino sus.
Bine. Sorteaza înșivă în conformitate cu prezentul.
Glisați doar un pic pe partea de muzica sta aici.
Deci avem 4, 2, 6 - ajunge acolo, aici, chiar acolo - 3.
Da. Bine. Du-te aici. Nu, stai acolo.
Da, chiar acolo. Nu am greșit. Chiar acolo. Bine, foarte bine. Bine.
Deci, acum hai sa le sorta într-o ordine crescătoare.
>> Cum pot merge despre a face acest lucru?
Algoritmul care a fost propus un moment în urmă a fost de ce nu ne compara pur și simplu
oameni buni, care sunt un fel de una lângă alta și apoi repara orice greșeli,
deplasează de la stânga la dreapta.
Deci, aici avem 4 și 2, în mod evident din comanda. Hai să te schimbi. Bine.
Deci, acum am de gând să se mute în jos linie. 4 și 6, nope. [Râsete]
6 și 8, destul de bine. 8 și 1, lasă-mă să schimb voi. Bine.
Deci, 8 și 3, schimb de voi.
8 și 7, lasă-mă să schimb voi. 5 și 8, excelent.
Eu vă dau o listă sortată.
Bine. Deci, nu chiar.
Dar e mai bine, deoarece numerele mai mari - caz în punctul 8 -
au un fel de bule de aer de la stânga la dreapta peste.
Asa ca am luat 1 din ele drept, dar se simte ca și cum acest lucru nu rezolvă problema destul.
>> Deci, ce-ai propune să facem în continuare? >> [Elev] Continuați să faceți asta. Am >> continui să faci asta.
Și dau seama, din nou, ne-am stabilit lucrurile de care au doar toti oamenii
un fel de a aranja inteligent se bazează pe faptul că imaginea,
dar acum trebuie să fim mult mai metodic.
Trebuie să fie algoritmică despre ea ca și cum ne scrierea de cod -
în acest caz, pseudocod verbală.
Asa ca lasa-ma sa incerc din nou doar asta. Care a lucrat destul de bine. Ea nu-l rezolve.
Dar când îndoiesc, încercați doar și încercați din nou. Deci, 2 și 4, nu a ajutat mai.
4 și 6. Ah! 6 și 1, ceva mai bine acum.
6 și 3, bine. 6 și 7, 7 și 5, 7 și 8, bine.
Și tu știi, eu pot ignora, probabil, 8 acum, pentru că el este la sfârșitul listei.
Poate că nu trebuie să vă faceți griji despre cineva merge pe lângă el.
Dar să vedem dacă asta este o presupunere sigură.
Acum lista este - al naibii de - nu este sortată. Să mai încercăm o dată.
Deci, 2 și 4, 4 și 1, 4 și 3.
4 și 6, bine. 6 și 5, bine.
6, 7, și 8, bine. Dar aviz, pot opri doar aici, acum și oprim aici acum?
[Elev] Da. Da >>?
Ce se întâmplă dacă unul dintre voi a fost numărul 9 tot drumul acolo?
Acesta ar fi fost sortate. Bine >>. Acesta ar fi fost sortate prima dată în jurul valorii.
Bine. Așa că hai să ne întoarcem din nou. Suntem aproape acolo.
1 și 2, 2 și 3, 3 și 4, 4 și 5, 5 și 6, 6 și 7, 7 și 8.
>> Am terminat acum, dar, din nou, eu sunt un computer pe care se poate face numai ceea ce mi sa spus să fac,
și amintirea mea abia acum este că am făcut de fapt doar un pic de lucru.
Ceva sa schimbat aici.
Deci, eu nu am confirmat vizual punct de vedere tehnic sau algoritmic că această listă este, într-adevăr sortate.
Deci, doar pentru o bună măsură, doar pentru a fi anal cu privire la acest lucru, hai sa facem asta mai mult timp 1.
Deci, 1 și 2, 2 și 3, 3 și 4. Și știi ce?
Doar pentru o bună măsură, am de gând să păstreze piesa de pe mâna mea de data asta
câte swap-uri fac doar pentru ca stiu cat de mult munca pe care am făcut de fapt.
3 și 4, 4 și 5, 5 și 6, 6 și 7, 7 și 8. Nici un swap.
Așa că acum aș fi în mod legitim un idiot de a face acest lucru din nou
pentru că dacă am făcut nici o lucrare prin acest trecere a oamenilor,
atunci în mod clar că o să se întâmple din nou, în cazul în care nici unul dintre ei este un fel de aleatoriu
adversarially se deplasează în jurul valorii de. Asa ca acum pot opri.
Acum, haideți să punem întrebarea, cât de mult de lucru sa dureze de fapt mine?
Câți pași ai dura asta? N >> pătrat.
Da, așa n pătrat. În cazul în care nu veți obține n pătrat de la?
Trebuie să verifice fiecare cilindrilor -
Există numere n, și va trebui să verifice fiecare număr cu numerele n celelalte.
Bine. Deci, e >> n pătrat. Bine >>.
>> Deci, se simte ca și cum s-ar putea foarte bine să fie n pătrat, nu?
Au n dintre aceste tipi, 8 în mod special în acest caz,
dar de fiecare dată am trecut prin această listă am fost comparat prima persoană împotriva secunde,
doua impotriva treilea din nou și din nou și din nou,
și când am ajuns la final, ceea ce am făcut? L-am refăcut.
Deci, dacă am generaliza această explicație, ne-am n persoane
si eu sunt de luare, în mod evident, 8 etape, n trepte, de fiecare dată când mă duc prin acest algoritm.
Dar de câte ori, în cel mai rău caz nu trebuie să treacă prin această listă de persoane?
[Elev] N ori. Probabil n >>, dreapta, pentru că, în cel mai rău caz,
ceea ce este, probabil, cel mai grav caz de amenajarea acestor tipi de la get-du-te?
În cazul în care acestea sunt complet inversat ordinea
deoarece presupun doar mental, hai - Care e numele tău? >> Bowen.
Bowen. Bine. Deci Bowen, vino aici doar pentru un moment.
>> Să presupunem că Bowen a fost aici la începutul algoritmului,
și nu știm ce toată lumea este, dar aici Bowen, în conformitate cu acest algoritm -
și, dacă doriți să vă plimbați cu mine - este de gând să bubble sus, așa cum a făcut prima dată în jurul valorii de,
tot drumul până la sfârșit.
Dar să presupunem că persoana de lângă Bowen a fost numărul 7.
Trebuie să mă duc înapoi și să obțină numărul 7, ceea ce înseamnă că trebuie să merg tot drumul înapoi aici.
Acum trebuie să aibă ca plimbare același cu persoana care este numărul 7.
Dar ce se întâmplă dacă, atunci numărul 6 a fost alături de el, precum și?
Atunci am să mă întorc și să obțină 6.
Deci, din nou, la fiecare iterație a buclei acestui vorbesc cu fiecare dintre oamenii n,
și am putea avea de a face n dintre aceste plimbări să vă asigurați că mă trăgând
toate dintre cele mai mari elemente din spate și înapoi și înapoi la sfârșitul listei.
Deci, lucrurile n n ori este doar de n ori n sau n pătrat.
>> Deci, aici deja avem un algoritm care nu mai este n, care nu mai este log n,
de fapt e mai rău decât orice am făcut înainte.
Deci, un fel de Alex a avut noroc în care am făcut toate lucrările aparent în față pentru ea,
toate lucrările scumpe, astfel încât ea ar putea bucura în acest algoritm de căutare binară,
care este jurnalul de n.
Dar acest lucru este în concordanță cu tema de luni.
Am dat un pic mai mult spațiu, am folosit mai mulți biți, cu scopul de a accelera timpul nostru de funcționare.
Atât de mult ca nu e asta compromis între timp și spațiu,
s-ar putea, de asemenea, fi doar compromisuri între timpul petrecut la fel fata de a face lucrurile să meargă gata
și de executare de fapt un algoritm de căutare cum ar fi. Să încercăm altul.
Daca voi nu m-ar deranja doar rapid reamenajarea vă că pentru a se potrivi din nou,
hai să încercăm ceva puțin diferit în cazul în care nu e chiar atât de simplu
ca doar repara toate greselile perechi, care este super-intuitiv.
Să fim în schimb, un pic mai mult în mod deliberat și de a face acest lucru.
Aceasta prea aș propune este, probabil, destul de intuitiv.
>> Să selectați cea mai mică persoană din lista din nou și din nou. Deci, aici vom merge.
4, esti cea mai mică persoană pe care am văzut până acum, astfel,
așa că am de gând să-mi amintesc că, prin mental doar arătând la tine pentru acum.
2. Ooh! Uită de numărul 4. Am găsit doar elementul cel mai mic nou în această listă.
Am de gând să ne amintim că un fel de. 6, 8.
Ooh! 1. La revedere. Deci, acum am de gând să-mi amintesc numărul 1.
Știm că 1 este cel mai mic, dar eu sunt calculatorului. Ce se întâmplă dacă există un 0?
Ce se întâmplă dacă există o -1? Trebuie să continui.
Deci 3, 7, 5, nope. Bine. Deci, numarul 1 a fost mai mic.
Permiteți-mi să vă selectați din listă - Vom merge în acest fel -
și ai pus în mod arbitrar la începutul listei.
Acum, așteptați un minut. Am facut un fel de înșelat.
Dacă aceste baieti nu reprezintă o listă de 8 persoane, ci o matrice,
8 bucati de memorie contiguă - te superi pas înapoi pentru o clipă?
Nu e de fapt nici un spațiu pentru tine chiar aici.
Deci, cum putem face loc pentru - care e numele tău? Sammy >>. Sammy >>.
Cum putem face loc pentru Sammy?
>> Am muta n care sunt înaintea mea. Bine >>.
Deci, am putea muta oamenii n care sunt în fața lui,
așa că, dacă vreți să luați un pas deliberată, dramatic la stânga.
Ei au făcut tot ce la unison, dar ultima dată când am scris unele cod,
nu pot sorta de a muta mai multe lucruri deodată.
Am putea face acest lucru într-o buclă, în mișcare toată lumea o dată la un moment dat.
Deci, dacă voi nu s-ar deranja un pas înapoi spre dreapta,
și Sammy, dacă ai putea să pas înapoi, deoarece nu există încă nici o cameră pentru tine,
acum hai sa facem acest lucru. În cazul în care a fost Sammy un moment în urmă? Chiar acolo.
Deci, există un decalaj de acolo. Deci, ai putea muta în locul lui Sammy.
Acum, următoarea persoană în sus și în prezent următoarea persoană pe care, acum următoarea persoană. Acum avem loc pentru Sammy.
Acum, cineva din public - care a fost bun, că a fost actualizată,
m-am simțit un pic consumatoare de timp - ceea ce e mai rapid? Da.
[Elev] O matrice nouă? >> Ce e asta? >> [Elev] O matrice nouă? Bine >>, bine.
>> Deci, în conformitate cu această temă de doar compromisuri, de ce nu am face doar o matrice nouă
și apoi Sammy va fi de înot în spațiu în fața acestor oameni, de exemplu,
și putem începe doar completarea unui tablou cu totul nou. Că prea ar merge.
Dar eu nu sunt interesat de a petrece mai mult spațiu de astăzi. Ce e altă abordare?
[Elev] Swap. Bine >>. Am putea schimba doar aceste 2 tipi. Care e numele tău?
Mario. Mario >>. Deci Mario, ai fost prezent aici.
Sammy, puteți copii de rezervă doar pentru o clipă? Mario a fost aici.
Nu avem loc pentru tine, așa că, dacă nu te superi dacă o să Sammy este,
vom pune Sammy aici, și acum aș spune că operațiunea schimbarea lui Sammy a fost mult mai rapid.
Am făcut o operație de schimb de acești tipi, sau poate schimba la 2 la tipii ăștia,
dar nu am făcut 1, 2, 3, 4, astfel că se simte mai bine. Acum, așteptați un minut.
Am facut un fel de problema mai rău, deoarece numărul 4, a fost un fel de aproape de început.
Acum, numărul 4 este un pic mai aproape de acest scop, dar nu știam cu adevărat sau pasă de asta.
Deci, aceasta este doar ghinion că numărul 4 este un pic mai departe de locul său destinat.
Așa că hai să repete acum acest algoritm.
>> Pentru a recapitula, atâta timp cât această poveste a fost, tot ce am facut a fost sa se plimbe prin lista de
In cautare de cea mai mică persoană numerotate.
Deci, acum hai sa o facem din nou. Noi nu trebuie să vă faceți griji despre Sammy mai.
Putem merge doar aici. Ooh! Numarul 2. Asta e un număr destul de mic.
6, 8, 4, 3, 7, 5. Bine, bine.
Și din fericire, prin coincidenta, eu nu trebuie să se mute - >> Willie.
Willie pentru că e la locul lui chiar acum.
Să facem acest lucru din nou și să ignore aceste 2 tipi.
6. Asta e un număr destul de mic. Ooh! 8 este cu siguranta mai mare.
4. Să se concentreze pe 4. Ooh! 3 este chiar mai bine.
7 și 5. Deci, ce facem acum cu - >> Roger. Roger >>?
Să-l schimbe cu numărul 6.
Deci, dacă 6 și 3 ar dori să facă schimb,
am ajuns acum un fel de norocos în 6 este mai aproape de cazul în care ea ar trebui să fie,
dar e doar o coincidență aici. Așa că hai să mergem acum aici.
8 este un număr destul de mic. Ooh! 4 este mai mic.
6, 7, 5. Ce facem acum? Swap >>. Exact >>.
Deci, acum hai sa facem acest gen de repede.
8, 6, 7, 5. În cazul în care se merge 5? Bine. Bine.
6, 7, 8. 6 ajunge la stea unde este. Care e numele tău? Rosalie >>.
Rosalie ajunge să stea unde este. 7 ajunge la - Hai să vedem. 7, 8. Bine.
Deci, 7 ajunge la stea acolo unde ea este. Care e numele tău? Amna >>. Amna >>.
>> Deci, Amna ajunge să stați în cazul în care ea este, și numărul 8 este deja în cazul în care el acum ar trebui să fie.
Bine, bine. Se simte ca și cum am crea doar locul de muncă pentru noi aici, totuși.
Cât este în cele din urmă timpul de rulare al acestui algoritm?
Dacă ne gândim la acești oameni care nu ar fi 8, dar cum n? >> E nr.
E n pași, dar suntem de verificare de fiecare dată singur.
Bine. N dar tu de verificare de fiecare dată?
Bine, dar dacă e n etape, nu ar trebui să am putut să vă sorta de a merge doar 1, 2, 3, 4?
Oh! Bine, asta e o mare diferenta.
Deci, n pătrat de ce? Ce se întâmplă cu adevărat?
Sunt oameni n în această listă, dar pentru a găsi cea mai mică persoană din lista
în cel mai rău caz, câți pași trebuie sa iau? N. >>
>> N, dreapta, pentru că, în cel mai rău caz, numărul 1 este tot drumul acolo,
așa că trebuie să du-te pe el sau ea.
Și apoi, când am dat seama în cele din urmă 1 a fost mai mic, atunci este destul de rapid pentru a le schimba.
Dar acum trebuie să înceapă de la început și căutați pentru cine?
Persoana imediat mai mică, care este 2. În cazul în care, în cel mai rău caz este 2?
Oh, Doamne. E tot drumul până aici la sfârșitul anului.
Așa că acum am făcut doar un alt pași n, n alte trepte.
Și dacă avem oameni n și, în cel mai rău caz mai mic persoana este n câțiva pași,
asta e din nou de n ori n, și așa am din nou, au n pătrat.
Acest lucru nu se simte prea bine.
Și, de fapt, chiar și în cel mai bun caz - să presupunem că ele încep sortate -
câți pași e nevoie de mine folosirea acestui algoritm pentru a sorta aceste persoane n?
N pătrat. >> Am auzit n pătrat. De ce n pătrat?
Pentru că tot trebuie să verifice de fiecare dată singur. Da >>.
Și trebuie să le schimba. Chiar dacă >> noi, oamenii, sunt un fel de atotștiutor
în sensul vizual ca putem doar un fel de a vedea că acest lucru este sortat,
un computer nu este asa de destept.
O să uite aici și aici și aici,
dar dacă ceea ce se caută este cel mai mic element,
tu doar știi că ai găsit cel mai mic element de ce punct? Odată ce ești la sfârșitul anului.
Dar la acel moment le-ați găsit doar elementul cel mai mic curent.
Tu nu știi neapărat altceva despre starea lumii.
Deci, va trebui să merg din nou și din nou și din nou.
>> Deci, de data asta chiar nu arata prost pentru că eu sunt de verificare, ok, 2, tu ești cel mai mic,
dar nu știu că, în total încă.
3, 4, 5, 6, 7, 8. Bine, bine. 2 a fost într-adevăr cel mai mic.
Acum, hai să găsim cea mai mică următoare. Bine.
3, sunteți în prezent cel mai mic. Să vedem. 4, 5, 6, 7, 8. Bine, am avut noroc din nou.
3 a fost, într-adevăr, în locul potrivit. Dar am de gând să continui să faci asta din nou și din nou și din nou.
Cum putem face vreodată atât de ușor mai bine?
În loc de a avea oameni bule de până la cel mai mic perechilor cel mai mare la
și în loc de a merge înainte și înapoi prin lista de selectarea persoana cea mai mică, apoi,
de ce nu ne introduce în locul acestor persoane într-o etapă nouă listă cu pas?
Să încercăm asta. Acum, lasă-mă să sun acest fel inserarea lucru.
Deci, iată-ne aici. Numărul 1. Nu-mi pasă de nimeni altcineva în această listă.
Scopul meu acum este de a pune numarul 1 la începutul unei liste sortate.
Și am de gând să propună, deoarece am doar 8 bucăți de memorie,
arbitrar, chiar acum am zidul dintre lista mea presupune nesortate,
și oricine care este în spatele meu am de gând să pretindă este sortat.
Deci, acum avem numărul 1.
Vreau să-l introduceți în lista mea sortate, așa că am de gând să se mute peretele meu aici,
si acum am pretind această listă este sortată, această listă este nesortate - cel puțin măsura în care știu.
Eu nu pot vedea toate numerele dintr-o dată.
>> Acum se întâmplă să întâlnesc numărul 2. Ce fac cu el?
Te-am insera acum în lista sortată. Dar observați cât de ușor a fost.
Trebuie doar să te uiți. Numărul 1 este acolo. Oh, evident 2 merge la partea de numărul 1.
Acum ce fac cu 3? Te-am inserați în lista sortată. Dar asta a fost super usor.
Acest lucru este foarte usor, acest lucru este super usor, acest lucru este super usor, super usor usor, super.
Și acum totul este sortat în spatele meu, și cât de multe măsuri care să ia făcut?
[Elevii] N. >> Deci e doar n. Am avut noroc.
A fost doar n de ce? >> [Elev] Pentru că lista a fost sortate.
Lista este deja sortat. Așa că am avut noroc.
Dar am conceput un algoritm de această dată care beneficiaza acest tip de noroc,
că cel mai bun scenariu, prin faptul că nu mai pierdeti timpul inutil.
Deci, acum avem ceea ce vom numi felul bule
în cazul în care oamenii fel de bule de până perechilor.
Avem acum un fel de selecție în cazul în care ne smulge mai mic persoana din nou și din nou.
Și acum avem un fel de inserare acolo unde am cam pus în mod proactiv persoane care fac parte
într-o listă din ce în ce sortate.
Dacă am putea, o rundă de aplauze pentru tipii ăștia aici. [Aplauze]
Să luăm de 5 minute de pauză aici.
Și când ne vom întoarce, vom sufla toate aceste algoritmi de apă
cu ceva mai bun. Bine. Mulțumesc foarte mult. Aveți posibilitatea să păstrați cei ca suveniruri.
Bine. Ne-am întors.
>> Și trecerea în revistă foarte repede, am avut aceste abordări diferite la 3 sortarea,
Ideea de care a fost pentru a ajunge la punctul în care cineva ca Alex
ar putea căuta o listă de numere mai repede decât ar putea cineva ca Sean.
Și chiar dacă avem astfel de exemple simple, cu 8 numere,
ai putea extrapola cu usurinta la 8 pagini web, 8 miliarde de pagini web,
sau 800 milioane de prieteni pe Facebook.
Deci, acești algoritmi pot fi scalate cu siguranță la acele tipuri de valori,
iar ideile sunt în cele din urmă la fel.
Deci, un fel balon a fost primul care am un fel de bule de aer în sus cea mai mare persoană
tot drumul spre dreapta prin schimbarea perechilor de oameni.
Apoi am avut ceea ce vom numi un fel de selecție în cazul în care am un pic mai mult în mod deliberat
se tot uita prin lista, selectând cel mai mic număr din nou și din nou și din nou,
rezultatul logic al, care este faptul că lista este sortată în cele din urmă.
Apoi, în al treilea, am introdus oameni în locul lor corespunzătoare,
si am facut un exemplu foarte contrived în această listă a fost deja sortate,
dar care a fost pentru a trimite mesajul că, în cazul de sortare inserarea lui,
puteți obține norocos.
În cazul în care numerele sunt deja sortate, se doar de gând să ia măsuri pentru a vă N confirma cât de mult,
întrucât fel de selecție ești viziune tunel un pic mai mult
și nu-și dau seama niciodată că lista este deja sortat.
Deci, hai sa vedem un fel balon în acțiune aici.
În următorul exemplu, suntem pe cale de a vedea bare verticale
înălțimi ale căror numere reprezintă, astfel încât să putem rezolva de sortare vizualizează întâmpla.
Cel mai mic bar, este mai mic numărul, cu atât mai mare bara, cu atât mai mare numărul.
>> Și noi vom juca la această viteză prestabilită.
Se va muta prea repede pentru acum, dar rosu este ceea ce se arată 2 baruri
fiind comparat cot la cot.
Și dacă te uiți cu atenție, ceea ce se întâmplă este că, dacă barele sunt în afara de ordine,
unul mai mic este mutat la stânga, una mai mare la dreapta,
și apoi vă păstrați avansează.
Deci, dacă facem acest lucru din nou și din nou, observați că cele mai mici baruri
sunt de gând să păstreze tarasc drumul lor spre stânga
și cele mai mari barele sunt de gând să păstreze modul lor de a se tarasc dreapta.
Și într-adevăr, suntem de pornire pentru a vedea un model tot drumul pe partea dreaptă
la fel cum am vazut 8 și apoi în cele din urmă barbotare 7 până la capătul listei noastre umane.
Deci, acest lucru se întâmplă pentru a obține foarte rapid un pic plictisitor, asa ca lasa-ma opreasca asta pentru un moment.
Lasă-mă să modificați viteza de a fi mult mai rapid.
Nu mă schimbă algoritmul, eu doar a face animație se întâmple mai repede.
Totusi sortare cu bule, acelasi algoritm,
dar acum puteți vedea mult mai repede decât Demonstrația noastră verbală
faptul că cele mai mari elemente sunt într-adevăr barbotare până la partea de sus.
>> Ca o paranteza, aceste pătrate mici de la stânga jos și dreapta-jos
sunt doar mici reamintiri cu privire la cât de multe comparații faci.
Dar pentru acum, ne putem concentra pe piramida care durează formă, și acolo se duce.
Cel mai mic element este pe partea stângă, cea mai mare pe dreapta, și orice altceva în între.
Acum, haideți să aruncăm o privire la locul de sortare de selecție.
Am de gând să merg mai departe și a lovit Stop. Vom obține un nou set aleator de bare.
Sortare de selecție, rechemare, trece prin lista de nou și din nou și din nou,
plucking în cel mai mic element. Deci, aici este un fel de selecție.
Se pare ca exista lucru mai intampla acum, pentru că nu suntem compararea perechilor
dar suntem rezolva doar de cires alege cele mai mici elemente de la dreapta la stânga.
, Care a avut foarte putin timp, astfel încât există o dihotomie deja.
Doar pentru că un algoritm este declarat a lua n timp pătrat, cum ar fi un fel cu bule
și, ca un fel de selecție, cele mai grave sunt într-adevăr de ori caz de funcționare.
De exemplu, în cazul, să zicem, un fel de selecție,
Eu de fapt, am selectarea mai mic persoana si punerea el sau ea aici,
atunci eu o fac din nou, atunci o fac din nou,
dar a existat o ușoară optimizare-am putea face.
>> De îndată ce m-am mutat aici, numărul 1 - Sammy, în acest caz -
ceea ce am nevoie pentru a face cu el după aceea? >> [Elev] Lasă-l.
Lasă-l, nu? Nimic.
Nu am nevoie să vorbesc niciodată cu Sammy din nou, pentru că dacă aș fi ales cel mai mic element
și pune-l aici, de ce timp de deșeuri care merg la sfarsitul listei întreaga mea?
La urmatoarea iteratie permiteți-mi să se mute de fapt, doar la numărul 2, numai la numărul 3.
Deci, în realitate, nu am fost face lucruri n n ori.
Am fost de a face lucruri n, atunci n - 1 lucrurile, atunci n - 2 lucruri, atunci n - 3 lucruri,
apoi n - 4, punct, punct, punct.
Avem un pic de o serie geometrică, ceea ce înseamnă doar
adăugați numere progresiv mai mici.
Nu este n + n + n + n, dar n + 7 + 6 + 5 + 4 + 3 + 2 + 1.
Și ce, în general, funcționează pentru a fi -
Am de gând să încurce placa mea aici doar pentru o clipă -
care este de gând să lucreze pentru a fi ceva de genul n (n - 1) / 2
dacă ne doar un fel de privire la partea din spate a unei cărți de matematică în cazul în care aveți toate ieftin foi
pentru formulele.
Dacă adăugați ceva n + n - 1 + n - 2, funcționează pentru a fi ceva de genul asta.
Și dacă ne-am cam înmulțiți asta, care este n pătrat minus n / 2.
Am spunea n pătrat, deși, și asta pentru că am fost un fel de a lua o scurtătură mentală
deoarece, în realitate, n pătrat minus n împărțit la 2 este într-adevăr numărul real de pași
că un algoritm de sortare ca ar avea de selecție, dacă dorim cu adevărat numărate până
toate aceste comparații și toate lucrările ocupat mic făceam.
Dar sincer, o dată n ajunge să fie ca un milion sau un miliard, care naiba îi pasă
daca faci un miliard de minus squared un miliard de împărțit cu 2?
Un miliard de pătrat este un număr foarte mare.
Puteți lua un alt miliard de pe ea cu - n. Nu e o astfel de afacere mare.
Deci, mai mare cu numerele ajunge, în mai puțin importante acești termeni mai mici sunt ordonate.
Cui îi pasă dacă ai împărți la 2, dacă vorbești despre quadrillions de numărul de pași?
>> Deci, în general, oamenii de stiinta de calculator au tendinta de a arunca totul, dar cel mai mare pe termen lung,
si am doar un fel de a simplifica lumea și să spunem că algoritmul
a luat măsuri de aproximativ n pătrat. Asta e timpul de execuție al unui algoritm.
Deci, ne vom întoarce la acest lucru în doar un moment cu câteva exemple concrete,
dar pentru acum, asta e un fel de motivație din spatele intuitivă simplifică doar lumea noastră
și vorbesc despre cei mai importanți termeni, mai degrabă decât a intra în toate aceste formule de lux.
Așa că a fost un fel de selecție, și am luat un pic noroc acolo.
Să ne uităm la fel de inserție. Lasă-mă să mergeți mai departe și a începe aceasta, de asemenea.
Acum, observați modelul care se întâmplă este un pic diferit,
și am început cu numere aleatoare,
dar dacă socotim de fapt, până numărul de pași, în cel mai rău caz,
în cazul în care lista a început totul, în ordinea corectă,
ne-ar lua doar măsuri pentru a realiza n la fel de mult.
>> Dar, dacă lista au fost de fapt invers - de exemplu, în acest caz, aici -
apoi observați avem de fapt de a face munca mult mai mult în acest caz.
Și ar trebui să se simtă un fel de a vă ca aceasta este un fel de a lucra mai greu
pentru a obține aceste elemente mai mici, la stânga, și asta pentru că avem ghinion.
Lista a fost sortată accidental în sens invers.
Prin contrast, cu insertie fel, dacă ne imita ceea ce am făcut cu oamenii noștri aici
prin începând cu toată lumea sortati si apoi de a începe, este un algoritm destul de bine, nu?
E deja, de fapt, sortate.
Deci, haideți să încercăm a rezuma exact cât de mult timp aceste lucruri sunt luați-ne
prin introducerea doar un pic de jargon sau notație care este de fapt mult mai simplă
decât un fel de fanciness sugerează.
Acest lucru aici, acest O mare pe ecran, ceea ce este un om de stiinta de calculator va folosi, în general,
pentru a descrie timpul cel mai grav caz de funcționare al unui algoritm.
>> Din nou, de cel mai rău caz, e total dependentă de context.
Ceea ce vrem să spunem prin cel mai rău caz, în totalitate variază în funcție de problema despre care vorbim.
Dar, în cazul de sortare, ceea ce este cel mai rău scenariu posibil?
Totul este invers, deoarece doar se simte ca și cum ceea ce înseamnă o mulțime de lucru pentru noi.
Am notat câteva dintre algoritmi care le-am văzut până acum:
căutare liniară, cum ar fi binar de căutare cu cartea de telefon sau bucăți de hârtie,
apoi sortați balon, sortare de selecție, precum și inserarea fel cum am văzut cu oamenii noștri,
și apoi o altă natură care se în cele din urmă va fi numit un fel îmbinare.
Deci, în căutarea liniară, în cel mai rău caz, câți pași e nevoie pentru a găsi numărul 7
în cazul în care există uși n ca Sean cu care se confruntă? >> [Elev] N.
N. Deci, vom scrie mare O din nr.
Mă duc să completați în unele spații libere. Aceasta este doar o grilă a matrițelor.
Dar, în cel mai bun caz, cu căutare liniară, 7 ar fi fost la început a listei,
și Sean ar fi inceput sa caute la începutul listei.
Deci, dacă sunteți utilizând căutarea liniară și doar verificare la stânga la dreapta sau de la dreapta la stânga, poate -
sunt echivalente - în cel mai bun caz câți pași ar putea căutare liniară,
cum ar fi algoritmul lui Sean, ia? Doar 1 pas.
>> Așa că am de gând să spun că e notația omega.
Acesta este doar omega de capital.
Omega este doar modul sexy de a spune cel mai bun caz timpul de funcționare.
Deci, în cel mai bun caz timpul de rulare este un singur pas sau un număr constant de pași -
1 în acest caz -, dar, în cel mai rău caz, Big O, aceasta este, de fapt pași n.
Și asta aici, teta, nu suntem de fapt de gând să se uite la dreapta acum.
Nu e relevant pentru acest exemplu particular.
Dar acum să încercăm căutare binară.
În cel mai rău caz, cu binar de căutare, câți pași este ea de gând să ia pentru a găsi numărul 7
sau tot ce ne ce cautati? >> [Elev] n Log.
Încă de gând să ia n log, deoarece la fel ca Alex avut ghinion
când am lucrat cu adevărat, prin problema metodic
și ea nu a găsit numărul 7 până la ușa ultimul se uita la,
chiar dacă, în echitate, ea a ajuns să arunce anumite uși de-a lungul drum,
binar de căutare, în cel mai rău caz are un timp de funcționare a log n.
Și din nou, că vorbește la această divizare și cucerirea.
Dar ce se intampla in cel mai bun caz?
Și Alex experimentat de fapt, că cel mai bun caz drept, atunci când ea a venit pe scenă.
Câți pași au ca ia in cautare binara? >> [Elev] 1.
1, doar pentru că ea a avut noroc.
Dar asta e bine, deoarece omega se referă la scenarii mai bun caz,
cele mai bune intrări de caz, chiar dacă e doar noroc aleatoare prost.
>> Acum, acest lucru prea vom doar un fel de goale concediu pentru acum.
Ce zici acum de sortare cu bule?
În cel mai rău caz, cu bule de sortare, toată lumea este în ordine inversă,
așa că trebuie să facem o mulțime de bule.
Dar câți pași este faptul că va lua în cel mai rău caz? >> [Elev] pătrat N.
Aceasta a fost n pătrat, pentru că, dacă stai să te gândești,
în cazul în care lista este complet invers - 8 este aici, 1 este aici -
ca lucru începe să fiarbă, numărul 8 este de gând să se mute în acest fel, în acest fel,
în acest fel, în acest fel, dar în cazul în care este numărul 7, în cel mai rău caz?
Aici ea este încă acolo. Deci, noi trebuie să o facem din nou și din nou.
Și asta e în cazul în care vom ajunge pași n, atunci n - 1 pași, atunci n - 2 trepte.
Și dacă vă luați cuvântul meu pentru asta - că, dacă astfel de înmulțiți-l afară,
este aproximativ n pătratul în final cu unele alți termeni pe care le vom ignora doar pentru acum -
apoi, în cel mai rău caz, sortare bubble este n pătrat, da sau de a lua.
Dar ceea ce despre cel mai bun caz, cu un fel bule?
Care este cel mai bun caz? Toate numerele sunt sortate deja.
Și ce a fost euristică am folosit, am folosit trucul,
să realizez că am făcut nici o lucrare și, prin urmare, ar putea opri mai devreme?
[Elev] Check-o o dată. Verificați-l >> dată. Dar ceea ce făceam de-a lungul drum?
Am fost urmărirea de cât de multe am facut swap-urilor.
Și am dat seama daca nu am numărat nici un swap pe degetele mele, apoi am făcut nici o lucrare.
Eu cu siguranță nu ar trebui să încerce să nu faceți nicio lucrare din nou, așa că am pot opri pur și simplu.
>> Deci, în cel mai bun caz de sortare cu bule atunci când lista este deja sortate,
ce-ai spune notația omega este, cel mai bun caz de funcționare timp?
E doar n. Trebuie să facem ceva de lucru, dar trebuie doar să facă în valoare de 1 plimbare de muncă.
Și aici am de gând să părăsească această parte necompletată.
Și acum sortare de selecție.
Fel de selecție ma smulgerea mai mic persoana din nou și din nou.
Și ce am spus timpul de execuție din care a fost?
Asta a fost tăiat în n cel mai rău caz.
Și, din păcate, în cel mai bun caz este, de asemenea, n pătrat
pentru că nu am un fel de vedere omniscient din întreaga lume;
Eu știu doar pe o repetare completă pe care l-am găsit într-adevăr, cea mai mică persoană.
Deci, un fel de fel de selecție e de rahat, în acest sens,
dar capul este un fel e de intuitiv.
Este destul de ușor pentru a coda pentru că tot ce trebuie să faceți este să scrie o serie de bucle imbricate pentru,
de obicei, care trece prin căutarea pentru cel mai mic element
și apoi pune cel mai mic element din care face parte, la sfârșitul listei.
Deci și aici va fi un compromis.
Suma de timp este nevoie să te gândești și să dezvolte efectiv ceva de scrierea de cod
ar putea foarte bine să ia mai mult timp, dacă doriți o performanță mai bună și mai rapid algoritm.
>> Dar, dacă într-adevăr doar un fel de cod ceva până rapid și murdar
și doar un fel de ia ideea stupida posibil vă puteți gândi,
care ar putea dura vă câteva minute pentru a codului, dar cu seturi mari de date
Algoritmul dumneavoastră ar putea dura ore pentru a rula.
Și chiar și eu în facultate ar face, uneori, aceste compromisuri.
Ar fi 3am, am fost încercarea de a analiza o parte foarte mare set de date
legate de cercetarea în domeniul securității făceam, și a fost cheltui 5 minute
tweaking programul meu pentru a analiza datele și du-te la culcare
sau petrece 8 oră obtinerea-l doar dreptul, astfel, ruleaza instantaneu, și nu merg la culcare.
Și deci nu prea e un fel de o decizie conștientă.
Timpul de dezvoltare mai puțin, de mai mult somn.
În retrospectivă, probabil că nu ar trebui să încurajeze faptul că
atunci când scopul aici este de a optimiza calitatea codului,
dar că prea în lumea reală este un foarte rezonabil compromis.
Mai puțin timp, performanța mai puțin sau invers.
Deci, aici vom avea în sfârșit o șansă de a vorbi despre teta.
Theta notație este ceva oamenii de stiinta de calculator pot aduce în conversație
Când Big O și omega se întâmplă să fie aceeași.
Tu spui teta pentru a trimite mesajul într-adevăr că aceasta este un fel de strans legat.
Indiferent dacă scenariul este bun sau rău, e n pătrat.
Deci, nu e doar relevantă în aceste povești aici.
Fel de inserare este ultima ne-am uitat la,
unde am fost doar introducerea pe toți în locul potrivit.
În cel mai bun caz ceea ce a fost timp de funcționare de sortare inserare așa cum am văzut-o aici?
[Elev] cel mai bun caz? >> Cel mai bun caz.
>> Acesta a fost n deoarece, în cel mai bun caz toată lumea sortate,
și Sammy și nimeni altcineva într-adevăr a trebuit să se mute la toate.
Ei au fost deja la locul lor.
Deci, un fel de inserție în cel mai bun caz este, în acest caz, nr.
Dar, în cel mai rău caz e un fel de n pătrat. De ce?
În cazul în care lista mea de om este, în ordine inversă,
Prima dată am începe cu numărul 8 și l-am introduce sau de ei în poziția corectă, care este chiar aici.
Am facut un fel de mișcare în lateral. Tipii ăștia sunt sortate, el sau ea este sortat.
Dar acum se întâmplă să găsească cine urmeaza? >> [Elev] 7.
7 în cel mai rău caz, pentru că e în ordine inversă.
>> Deci, aici este de 7. În cazul în care nu aparține 7? Categoric spatele meu.
Dar acum 7 de fapt, nu apartine imediat în spatele meu, dar în spatele numărul 8,
așa că trebuie să spun, "Scuză-mă, numărul 8, poate, te rog muta în acest fel
"Pentru a face loc pentru 7?" Acum am întâlni 6.
"Oh, scuză-mă, numărul 8 și numărul 7, vă puteți muta pentru a face loc pentru 6?"
Deci, cu alte cuvinte, cu insertie de sortare, chiar dacă nu fac multa miscare,
oamenii din spatele meu fac munca mult mai mult, și că are timp sa coste pe cineva.
Se va costa timp de calculator.
Deci, în cazul de sortare inserție avem încă suferim.
Dacă începeți adunarea numărul total de pași, am sfârși prin a lovit aproximativ n pătrat
deoarece aceste tipi au nevoie pentru a face loc oamenilor de a se introduce din nou în acea listă.
Și astfel, în acest caz, teta nu este doar aplicabilă povestea special la mână.
Asta e tot frumos și bun. Avem aceste moduri diferite de a 3 vorbesc despre timpul de execuție.
Dar ce înseamnă, de fapt, în termeni reali, dacă vom încerca de fapt, pentru a coda un algoritm?
>> Permiteți-mi să propună că există un algoritm chiar mai bine acolo
care se are unele compromisuri.
Vom numi fuzioneze sortare, și e un fel de acest algoritm magic
că doar funcționează mai rapid într-un fel, și este atât de ușor să-și exprime, cel puțin în pseudocod.
Punerea în aplicare a acestui tip de îmbinare algoritm va fi, după cum urmează.
Când ai de dat n elemente - numere de N, N, indiferent de oameni - în primul rând acolo e un cec bun-simț.
Dacă n este mai mic de 2, îmbinare fel doar se oprește. Se întoarce, ca să spunem așa.
De ce ai opri daca n este mai mică de 2? >> [Elevului răspunsul neauzit]
Corect. Și din nou, n nu este numărul din lista, n este mărimea listei.
Dacă n este mai mic de 2, înseamnă că lista este fie 1,
în cazul în care sunteți în mod evident sortati dacă e un număr,
sau 0, caz în care nu mai e nimic pentru a sorta,
asa ca am nevoie de acest tip de cazul de bază.
În cazul în care lista este atât de scurtă, încât nu este nimic de a face, pur și simplu nu face nimic. A reveni.
În caz contrar, sorta jumătatea stângă a elementelor, apoi să sortați jumătatea dreaptă a elementelor,
îmbinați, apoi cele 2 jumatati sortate.
>> Acest tip de pare a fi un pic ieftin prin care îți cer cum să sortați elementele
și tu îmi spui, "Sortare jumătatea stângă, sorta jumătatea din dreapta."
Sunt genul, "În regulă Cum sortați jumătatea stângă?".
"Sortarea jumătatea stângă a jumătatea stângă, sorta jumătatea dreaptă a jumătatea stângă, și apoi făcut."
Ești un fel de ciclic definirea a ceea ce înseamnă pentru a sorta,
dar se pare că e de fapt genial în acest caz.
Nu e adevarat acest ciclu vicios care nu se termină niciodată
pentru că atunci când se încheie? >> [Elev] Când ajunge la 1 lucru.
Atunci când ajunge la 1 lucru.
Deci, chiar dacă s-ar putea începe cu 8 persoane, și spun, "Sortare jumătatea stângă a acestor oameni,
aceste 4 persoane, "atunci eu spun," Cum vă sortați jumătatea stângă? "
"Ei bine, a sorta 2 persoane aici." Și apoi ești ca, "totul bine. Bine,"
"Cum sortați jumătatea stângă a acestor oameni?"
"Doar sorta această persoană 1 aici." Care este revelația genial acum?
Trebuie să sorta 1 persoană. Adoptată. Eu nu trebuie să fac nici o lucrare.
Dar acum trebuie să rezolvăm această persoană, dar sunt o singură persoană, nimic de-a face.
>> Deci, magia aparent este, în acest al treilea pas: fuziona jumatati sortate.
Deci, un fel îmbinare ia această perspectivă genial că, dacă te rupe o problemă mare în jos
in 2 mai mici, de dimensiuni identice probleme
și apoi doar un fel de clei soluțiilor mai mici împreună la sfârșitul anului,
Eu propun ca putem face mai mult, [sunet atingând] mult mai bine
decât oricare dintre fel de selecție sau de sortare inserție.
Am fost într-adevăr ignorând că, pentru o jumătate de oră, dar eu chiar nu știu ce se întâmplă pe
în afara de astăzi. [Zbârnâit sunet] [râsete]
Deci, hai sa vedem daca putem vedea acest lucru cu un pic de ajutor de la prietenul nostru Rob Bowden.
Există 2 pași mari în procesul de sortare de îmbinare.
În primul rând, divizat continuu lista de cupe în jumatati
până când vom avea o grămadă de liste cu doar 1 ceașcă în ele.
Nu vă faceți griji în cazul în care o listă conține un număr impar
si nu poti face o tăietură perfect curată între ele.
Doar alege arbitrar, care să includă lista cupa suplimentar inch
Deci, haideți să împartă aceste liste.
Acum avem 2 liste.
Acum avem 4 liste.
Acum avem 8 Lista de preturi cu o singură ceașcă în fiecare listă.
Deci asta e tot pentru pasul 1.
Pentru pasul 2 se îmbina în mod repetat perechi de liste utilizând algoritmul de îmbinare am învățat înainte.
Fuzionarea 108 și 15 ajungem cu lista de 15, 108.
Fuzionarea 50 și 4 am termina cu 4, 50.
Fuzionarea 8 și 42 am termina cu 8, 42.
Și fuzionează 23 și 16 ajungem cu 16, 23.
Acum, toate listele noastre sunt de dimensiuni 2.
Observați că fiecare dintre cele 4 liste este sortat,
astfel încât să putem începe fuzionarea perechi de liste din nou.
Fuzionarea 15 și 108 și 4 și 50 vom lua primul 4, apoi 15,
apoi 50, apoi 108.
Fuzionarea 8, 42 și 16, 23 avem prima 8, apoi 16,
apoi 23, apoi 42.
Deci, acum avem doar 2 liste de marimea 4, fiecare dintre care este sortat.
Deci, acum am îmbina aceste două liste.
În primul rând vom lua 4, apoi vom lua 8, atunci vom lua 15
și 16 și 23 și 42 și 50 și 108.
Și am terminat. Avem acum o listă sortată.
>> Rob a fost un fel de a profita de ceva ce nu am făcut-o încă.
A fost sugerat, dar nu ne-am face de fapt.
El a fost a face ceva fizic cu cupe care sugerează
el a fost petrecut ceva timp în afară de resurse. >> [Elev] Space. A fost >> spațiu.
Faptul că el a avut acest tip de bi-nivel de masă în cazul în care el a avut spatiu aici
și spațiu aici a fost de fapt ceea ce înseamnă că el folosește spațiul de două ori la fel de mult
ca oricare dintre algoritmii noștri de până acum - un fel de inserare, sortare cu bule, sau de selecție sortare -
dar el a fost mobilizarea acest spațiu suplimentar pentru genul de lucruri muta înainte și înapoi
păstrând în același timp lucrurile în ordine.
Și chiar dacă se simte ca și cum am ajuns la o listă sortată, că simtit ca a luat un timp.
În realitate, ceea ce Rob a fost făcut a fost exact acest algoritm.
El a luat prima problema de dimensiune n, împărțit în stânga și o jumătate de jumătatea din dreapta.
Asta e, când sa mutat în cupe. Apoi, el a repetat acest proces.
El a împărțit în 4 2 seturi de 2 aici și aici.
Apoi, el a repetat că procesul împărțit și 2 în 2 seturi de 1 pentru fiecare din aceste cupe diferite.
Și asta e în cazul în care posibilitatea de genial apare.
În acel moment, în poveste, Rob a avut 8 liste de dimensiune 1,
toate din care au fost sortate deja.
>> Deci, atunci ce a proceda să facă?
Perechilor el a luat această listă sortată și această listă sortată și care a fuzionat le.
Apoi, el a luat aceasta și care a fuzionat ei, atunci aceasta și le-a fuzionat,
atunci aceasta și le-a fuzionat.
Și apoi ce a făcut în continuare?
El apoi re-unit listele mai mari și apoi re-unit listele mai mari.
Și dacă te gândești la acest lucru doar intuitiv pentru moment, ceea ce a fost el cu adevărat face?
El a fost împărțirea problema în jumătate, în jumătate, în jumătate, în jumătate
, în scopul de a obține aceste liste super-mici.
Apoi, el a fost un fel de a combina dublu, dublu, dublu matrimonial,.
Deci, el a fost de a face de două ori mai multă muncă așa cum am văzut până acum
cu nimic care implică divide et impera, dar nu e mare lucru.
Locul de muncă de două ori la fel de mult, nu este o astfel de afacere mare. E doar un factor constant.
Și la fel ca expresie aritmetica noastră înainte, mă duc să treacă din factorii constanți
ca ori 2. Cui îi pasă? Dacă e 2 miliarde de ori 2, care este încă o mulțime de pași.
Deci, acest pas care fuzionează pare a fi perspectiva cheie.
Să se plimbe prin acest lucru doar numeric înainte - Oh, asta nu e să fie continuată încă.
Să se plimbe prin această numeric doar pentru a vedea de fapt, modul în care această joacă afară.
Aceasta este cea mai mare parte doar un om mic sărac animație.
Să propune acest lucru.
Timpul de execuție al îmbinării fel - avem nevoie doar de o modalitate de a vorbi despre acest lucru.
Acest lucru nu este matematica, acest lucru este doar un fel de mod succint de exprimare noi înșine.
Deci T reprezintă timpul și n reprezintă ce? >> [Elev] Dimensiunea -
>> [Malan] Dimensiunea problemei, numărul de persoane.
Deci, eu sunt susținând că timpul de execuție pentru a sorta oamenii n va fi 0 perioada de timp
dacă n este mai mică de 2, deoarece, dacă aveți 1 ceașcă sau nu cupe, nu ai nimic pentru a sorta.
Dar, mai general, am de gând să propună ca timpul de rulare pentru a sorta n elemente
va fi timpul necesar pentru a sorta jumătatea stângă, plus jumătatea din dreapta
plus - ce e asta suplimentar + n? >> [Elev] Merge sortare.
[Malan] Este de fapt care fuzionează, pentru că în cazul în care aveți n / 2 elemente aici
și aveți n / 2 elemente aici, cât de mult timp este nevoie pentru a le îmbina?
La fel ca Rob, va trebui să smulgă asta de aici, poate smulge pe aici,
smulge aici, trage aici, trage aici.
Trebuie sa atingi fiecare dintre cupe dată.
Și dacă nu e 4 cupe, plus 4 cesti, asta e 8 cesti
sau, mai general, 8 cupe n.
Deci, pas care fuzionează ne putem exprima ca n,
și care implică literalmente numărul de ori Rob fizic atins
unul dintre cei cupe Styrofoam.
Deci, hai sa facem acum un exemplu arbitrar.
Dacă e 16 cupe, ceea ce este timpul de funcționare de sortare, folosind algoritmul lui Rob, 16 cupe?
E de 2 ori cantitatea de timp este nevoie pentru a sorta 8 cesti
Pentru că avem 8 cesti aici, 8 cupe aici.
Nu știu cât timp care ia, așa că îl generalizarea ca T pentru moment.
Cine știe ce este?
Dar acum pot sorta de recursiv sau în mod repetat cere aceeași întrebare.
Cât de mult timp este nevoie pentru a sorta 8 cesti?
8 cesti am de gând să spun ia cantitatea de timp este nevoie pentru a sorta 4 cupe, plus 4 cesti,
apoi le fuzionează împreună.
Amenzii. Primim intr-un ciclu deja. Cât timp este nevoie pentru a sorta 4 cupe?
Timpul necesar pentru a sorta 4 cupe este de 2 cupe plus 2 cupe de sortare, plus procesul de fuziune.
Amenzii. Cât timp este nevoie pentru a sorta 2 cupe?
2 cupe este cantitatea de timp este nevoie pentru a sorta 1 ceasca, plus timpul necesar pentru a sorta o ceașcă
plus cantitatea de timp este nevoie pentru a fuziona, care este la doar 2.
>> Amenzii. Ultima întrebare. Cât timp este nevoie pentru a sorta 1 cană?
Aici este cazul de bază pe care am prezis ne-ar lovi mai devreme.
Faptul că este nevoie de nici o lucrare fel de a sorta mai mic de probleme
înseamnă că, în prezent, un fel de stil școala primară,
putem merge doar începe conectarea acestor numere înapoi inch
Noi știm acum ce T de 1 este, așa că am putea conecta la 0 pentru T de 1.
Asta îmi va da răspunsul la T de 2, pe care apoi am pot conecta până în mai.
Asta va da-mi T de 4, pe care eu pot conecta în sus superior.
Asta va da-mi T de 8, pe care eu pot conecta în sus superior.
Și dacă eu fac de fapt, că matematica prin conectarea la aceste răspunsuri,
I a lua atunci T de 16 este de 64.
Și ce reprezintă 64?
Dacă T este de 16, da, e de 16 ori 4.
Deci, eu pretind acum că timpul de execuție a acestui lucru numit fuzioneze sortare -
și acest lucru va fi fanciest de cele pe care le-am văzut până acum -
va fi numit n log n
pentru că de câte ori se poate împărți Rob o gramada de cupe în jumătate? Log n.
E la fel ca exemplu cartea de telefon, e la fel ca exemplu de auto-numărare.
>> Cât de multe ori puteți împărți ceva în jumătate?
Cu toate acestea, există acest pas fuziune.
S-ar putea să împartă în jumătate cupe din nou și din nou și din nou,
dar de fiecare dată ai de gând să aibă de a fuziona.
Iar noi am spus mai devreme că fuzionează cupe n ia măsuri n
pentru că trebuie să scoată o ceașcă, smulge o ceașcă, și va trebui să atingeți fiecare ceașcă o dată,
la fel ca Rob făcut-o.
Deci, dacă facem ceva log n ori și facem lucruri n pe fiecare dintre aceste iterații,
fiecare dintre aceste halvings, avem n log n ori.
Deci, dacă am conectați la 16, în acest exemplu, de 16 ori jurnal de 16 -
nu vă faceți griji cu privire la ce este acest caz, pentru acum, pentru că eu nu am desenat de bază -
dar jurnalul de baza 2 din 16 este de 4, 16 ori 4 este 64.
Dar, prin contrast, dacă am fi folosit un fel bule de aer sau de sortare sau inserarea de selecție sortare cu 16 numere,
ceea ce ar fi fost timpul de funcționare în cazul în care n este de 16?
Acesta ar fi 16 la pătrat, care este 256, care, chiar dacă nu ați urmat toate destul de matematica,
256 este mai mare decât 64. Asta e într-adevăr magic Takeaway aici.
Și dau seama că prin acest lucru, în timp ce exemple mai mici va pe o PSET
face totul mult mai intuitiv.
Dar ce înseamnă cu adevărat în ceea ce privește simt al acestui algoritm este aceasta:
Dacă ne uităm la fel de fapt, merge aici - lasă-mă să-l trage în sus în această fereastră aici -
acesta este un exemplu ușor diferită, prin care avem toate 3 din acesti algoritmi -
balon, selecție și îmbinare - doar una lângă alta.
>> Ei au Totul a început cu bare aleatoare, și asta e bine.
Nimeni nu are un avantaj fundamental față de celălalt.
Am de gând să într-un moment faceți clic pe fiecare dintre aceste animații - Start, Start, Start -
cât de repede pot, astfel încât, în linii mari, toate au început, în același timp,
și să ia în considerare acest caz, un fel de balon mai rau timp de rulare este ceea ce? >> [Elev] pătrat N.
N pătrat. Cazul cel mai rău fel de selecție este durata de? N pătrat.
Și fel de îmbinare este aparent - chiar dacă nu a urmat destul de toată matematica acum,
acesta va deveni mult mai intuitivă a lungul timpului - este, ne susțin, de n ori log n.
Si pentru ca log n este strict mai mică decât n, odată ce vom avea numere mari,
de n ori log n este mai mic decât n ori n sau n pătrat.
Deci, ce se simte a fi de fapt un algoritm mai bun în ceea ce privește timpul de funcționare,
n log n ori, spre deosebire de pătrat n? Aici vom merge. Faceți clic pe, faceți clic pe, faceți clic pe.
>> Asta e ceea ce înseamnă să folosească ceva de genul un fel de îmbinare.
Avem o clipă. Să vedem ce se întâmplă aici.
[Chicotește] cui bani se află pe un fel cu bule?
Aceasta depinde mai degrabă de intrare, uneori.
Să vedem.
Haide. Se simte ca și cum ar prinde sus. >> [Elev] Du-te, sortare cu bule!
[Elevi murmurând]
[Malan] Da, da.
[Elevii murmurau] Du-te, du-te, du-te!
[Totul aplauze] [aplauze]
Deci, acum, cu 1 demo trecut, finala, daca e un pic complicat să-și încheie în jurul valorii de mintea ta de matematica
sau un fel de vizualizare acolo, puteți auzi de fapt, vitezele
de algoritmi diferite în mod diferit.
Aceasta este o animatie cineva a făcut ca, de fapt asociații suna
cu procesul de pompare și înălțimea barelor.
După cum vom vedea aici, nu e un algoritmi de sortare câteva mai multe acolo, care s-au gândit la oameni.
Aceasta prima se va fi un fel de inserare, iar acest lucru va zbura prin
și vă va oferi un sentiment de sonor cum functioneaza aceste diferite algoritmi.
Aici este un fel de inserare.
[Bip electronice]
[Malan] sortare Bubble.
[Mai rapid bip electronice]
[Malan] Selecție de sortare.
[Mai rapid bip electronice]
[Malan] Merge sortare.
[Bip electronice]
[Bip încetinește] [râsete]
[Malan] Gnome de sortare.
[Bip electronice]
>> Acest lucru este CS50. Ne vedem săptămâna viitoare. [Aplauze și aplauze]
>> [CS50.TV]