>> Vorbitor: Bine, acest lucru este CS50.
Acesta este sfârșitul de săptămână trei, iar în cazul în care nu au profitat deja,
știu că nu va fi masa de pranz vineri, ca de obicei, în cazul în care
vă puteți bucura de conversație bună și alimente la Fire and Ice
cu unele dintre lui CS50 personal și colegii de clasă.
Mergeți la acest URL aici.
>> Acum, vă amintiți, sau te poate fi în curând familiarizat cu,
aceste lucruri de aici, care sunt date la sfârșitul
semestrului pentru mai multe clase.
Așa-numitele examen de cărți albastre, în care scrii răspunsurile tale la examene.
Acum am aici 26 astfel de cărți albastre, pe fiecare dintre ele
este scris un nume, de la A la Z. Și într-adevăr, numele sunt atât de simple, A
prin Z. Și unul din obiectivele de la mână astăzi
va fi de a continua ceea ce am început luni, care nu este
atât de mult se uită la cod, dar într-adevăr uita la idei și de rezolvare a problemelor.
Unul dintre obiectivele și promisiuni de acest curs
este să te învețe să gândească mai mult cu atenție, mai metodic,
și pentru a rezolva problemele mai eficient.
Și într-adevăr, putem face asta într-adevăr fără chiar a atinge o linie de cod.
Deci, am o pereche de elefanți aici astăzi, portocaliu și albastru,
dacă am putea obține un voluntar, Poate din spate mai departe decât de obicei.
Ce zici de acolo, haide jos.
Scopul care va fi de ajuta plus administra acest examen aici.
Care e numele tău?
>> Audiența: Mary Beth.
Vorbitor: Mary Beth, haide sus.
Lasă-mă să microfonul aici pentru tine.
Mă bucur să te cunosc.
>> Audiența: Mă bucur să te cunosc.
Vorbitor: Bine, așa că am aici carti albastru de la A la Z,
și am de gând să mă prefac că Am unul dintre elevi,
și vin în oarecum la întâmplare la sfârșitul unui bloc de trei examene ore,
astfel încât acestea sunt încheie până în unele Pentru semi-aleatorie ca asta.
Acum, de locuri de muncă într-o clipă se întâmplă a fi-- aceasta este de fapt cum au ajuns
transformat în la sfârșitul clasa, cel mai probabil.
Treaba ta acum va fi, destul de pur și simplu, pentru a sorta aceste cărți albastre pentru noi
de la A la Z.
>> Audiența: Oh, acesta este de gând să ia pentru totdeauna.
>> SPEAKER: Și vom urmări cum sa faci acest lucru, nici o presiune.
Audiența: Nu, nici o presiune sau nimic.
>> SPEAKER: Și pentru distracție, hai sa pus un timer.
>> Audiența: atât de distractiv, atât de distractiv.
>> SPEAKER: Pot ține microfonul pentru tine.
Bine, tocmai am dublat viteza noastră.
Deci, în același timp, lasă-mă să pun ce-i va fi întrebarea de Mary Beth
este ceea ce face ea, cum este ea merge cu privire la rezolvarea acestei?
Și, de fapt, nu s-ar putea avea gândit vreodată despre ceva
atât de simplu ca atunci când te iau up 26 cărți de acest gen,
care au un naturale prin care se dispune pentru a le.
Ce este procesul de pe care le folosesc de fapt?
Este destul de aleatoriu doar alege primul cel pe care îl vedeți
și punerea sa în locul ei?
Nu vă deplasați mai întâi pe mâini în jurul Cauti un apoi caută B?
Ai arunca o privire la o pereche de partea lor prin lateral
și doar spun, așteptați un minut, acest nu este corect, iar apoi schimba ordinea?
Am văzut deja pe luni că există o serie de moduri
în care putem face acest lucru, și într-adevăr, așa cum ne apropiem de sfârșit aici,
Mi-ar lua notă, probabil, de ce Mary Beth face.
Avem câteva grămezi se pare, o unul mai mare, de trei mai mici.
>> Audiența: Eu le comanda când am găsi două scrisori
că știu că sunt împreună într-o secvență, Le-am pus împreună, astfel încât să nu
trebuie să vă faceți griji cu privire la menținerea cale de un șir întreg de cărți.
E doar, oh, A este primul, Am o stivă de aici.
Vorbitor: Deci, aproape ca o piese de puzzle care
au forma potrivită pentru a se potrivesc unele cu altele.
Audiența: Destul de mult, da.
Vorbitor: Bine, excelent.
Și acum fiecare dintre acestea piloți sunt sortate probabil?
>> Audiența: Da.
>> Vorbitor: Bine, de la A la Z. Toate drept, felicitări, ai făcut-o.
Ai alegerea ta.
Albastru?
Bine, vă mulțumesc pentru asta.
Deci, Mary Beth a propus ce abordare ei a fost,
dar ceea ce este o altă abordare modul în care s-ar putea merge cu privire la sortarea aceste lucruri?
Ce-ai fi făcut?
Recordul de a bate ar fi fost un minut și 50 de secunde sau cam asa ceva,
plus cei care am uitat să numere.
Ce-ai fi făcut?
Da?
Audiența: Ia stiva.
Începe de la început.
Verifică actele.
Și dacă cel de sus este mai mare decât, poate, ele sunt,
cel de jos este mai mare, apoi trece-le.
>> Vorbitor: OK, deci începând cu în partea de sus și de jos,
și apoi de lucru-ți de drum interior de genul asta, schimbarea ei?
OK, deci un pic asemănător în spirit de bule de sortare,
dar alegerea extreme Nu perechile adiacente.
Dar pe termen scurt de ea este că nu există cu siguranță o grămadă de moduri diferite
am putea face acest lucru, și sincer, eu te cred un fel de
a adoptat câteva abordări, corect?
Ai făcut un fel de patru piloți sortate, și apoi le-au fuzionat în mod eficient împreună.
Și asta e, îndrăznesc să spun, un alt tehnica cu totul.
Nu l-ai trata ca pe o mare grămadă, tu divizat problema în patru quad-uri,
dacă vreți, și apoi într-un fel le fuzionat în cele din urmă.
>> Deci, haideți să considerăm, în cele din urmă, cum altfel am putea face acest lucru.
Am formalizat notiunea de bule fel ultimul timp,
și bule fel de rechemare a fost un algoritm care ne-am vizualizat
cu opt dintre colegii dvs. aici, aparent sortate aleatoriu la început.
Și ne-am hotărât apoi pe perechi, dacă două elemente sunt în ordine,
pur și simplu a le schimba.
Deci, patru și două sunt în mod evident, în ordine,
astfel încât cele două colegii de clasă a schimbat locul.
Și apoi am repetat cu patru și șase, apoi șase și opt, pe fiecare iterație,
se deplasează spre dreapta.
>> Deci, având opt oameni, pe perechi câte comparații am făcut în timp ce mersul pe jos de la
stânga la dreapta într-o astfel de iterație?
Câte comparații?
Seven, nu?
Pentru că dacă există opt oameni, dar aveți o pereche
le și păstrați-vă în mișcare un hop la dreapta,
tu nu vei avea opt comparații pentru că nu se poate compara
un element împotriva ei însăși, sau că ar fi doar să fie lipsită de sens, astfel încât să aveți șapte.
Sau, mai general, în cazul în avem n oameni, ne-am
face n minus 1 comparații cu bule de sortare.
>> Deci, haideți să considerăm acum cât de bun sau bubble rău fel de fapt a fost, și încercați
pentru a ne da vocabular cu care a algoritmi critici, cum ar fi acest lucru,
și, în curând propriul nostru.
Deci, prima trecere prin bubble sort, pentru prima dată
M-am dus de la stânga la dreapta peste etapă, mi-a luat n minus 1 comparații.
Și care va fi mea unitate de măsură, nu?
Am fost un fel de a vorbi și vă plimbați, oarecum rapid, oarecum lent,
astfel de numărare numărul meu de secunde nu este deosebit de spus,
dar numărarea operații care le-am făcut, luni,
compararea a două persoane, care se simte ca o unitate de frumos de măsură.
>> Deci, n minus 1 pașii pentru prima dată, dar apoi ce sa întâmplat după aceea?
Care este unul din susul o singură trecere printr-o listă de altfel nesortate?
Ce-mi poți spune despre elementul care a fost tot drumul de acolo?
Da?
Asta a fost cel mai mare element, nu?
Numărul opt, chiar dacă ea a început aici, de fiecare dată când
în comparație ei împotriva un vecin, ea a păstrat
barbotare spre dreapta în partea stângă a listei.
Și într-adevăr, acolo algoritmul devine numele său.
>> Acum, prin care logica, cât de multe comparații Trebuie sa fac pe a doua oară
Eu fac că trece de la stânga la dreapta?
n minus 2, corect?
Ar fi doar pierd timpul dacă am păstra compararea opt împotriva cuiva
altfel pentru ca stim deja ea a fost la locul potrivit.
Deci, asta e un pic de o optimizare, astfel încât următoarea trecere
va fi plus n minus două etape, unde n este numărul de persoane.
Acum puteți fel de extrapola, chiar dacă nu ești un om de știință de calculator,
cum se termină.
La finalul acestui algoritm, probabil ai doar o comparație a plecat.
Trebuie să fixați un fel de începând din lista de la caz două
și unul este în ordine și ar trebui să fie una și două,
astfel încât aceasta la fund afară la plus 1 comparație finală.
>> Acum, punct, punct, punct fel de valuri este mâinile la unele dintre cele mai juicier detalii,
dar hai să mergem mai departe și de a simplifica.
Dacă vă amintiți de la mare școală, sincer, o mulțime de tine
au avut carti de matematica care au avut o foaie de ieftin mic
pe capacul frontal sau capacul din spate care ți-a arătat
somații ce serie, cum ar fi aceasta în cele din urmă a adăugat până la.
În cazul general, dacă aveți o variabilă ca n, și într-adevăr aceasta,
dacă te-ai uitat la dumneavoastră carte de matematica școală veche,
ați vedea că acest fapt adaugă până la această sumă aici,
n ori n minus 1 tot împărțit la 2.
Deci, de acum lasă-mă să prevadă acest lucru este adevărat, așa pe un salt de credință,
asta e ceea ce rezumă acest până la, și ne-am putea
dovedi că într-un caz mai general.
Dar acum să se extindă acest lucru.
Așa că haideți să multiplica acest lucru, astfel încât este n patrat, n minus, toate împărțit la 2.
Asta este într-adevăr n pătrat, împărțit la 2, minus n peste 2,
asa ca asta e tot frumos și interesant.
Dar ce se întâmplă dacă acum plug-in-o valoare?
Să presupunem că eu nu am avut opt oameni, dar spun un milion.
Și un milion doar pentru că este un număr destul de mare,
să conectați că în și vedem ce se întâmplă.
Deci, dacă am conectați un milion în care formula Am de gând pentru a obține un milion de pătrat,
împărțit la 2, minus o milioane, împărțit la 2.
Acum, ce care merge la egal?
Deci 500 de miliarde, minus 500.000.
Și dacă de fapt, nu că matematica afară, că mijloacele
că sortarea un milion oameni cu genul bubble
mi-ar putea lua 499999500000 trepte sau comparații în cele din urmă,
suntem doar extrapolarea.
>> Că se simte destul de lent, dar sincer măsurarea unul special de intrare
in acest fel, nu este tot ceea ce spun.
Dar, într-adevăr aceasta nu sugereaza ca n devine mai mare și mai mare, acest algoritm
un fel de se simte mai rău și mai rău, sau chiar
începe să se simtă durerea pe care exponentiala, că n pătrat,
care se adaugă destul de repede.
Si acest detaliu nu este pierdut pe oameni, de fapt
în urmă cu câțiva ani un anumit senator care a fost campanie, se așeză pentru un interviu
cu Eric Google Schmidt, CEO la momentul respectiv,
și a fost provocat de o întrebare la fel ca explorăm astăzi.
Să aruncăm o privire.
>> [VIDEO PLAYBACK]
>> -Senator, Tu ești aici la Google, și-mi place
să se gândească la președinția ca un interviu de angajare.
Acum, este greu pentru a obține un loc de muncă în calitate de președinte,
și te duci prin rigorile acum.
Este, de asemenea, greu pentru a obține un loc de muncă la Google.
Avem întrebări, și noi cere candidaților întrebările noastre,
iar aceasta este de la Larry Schwimmer.
Ce-- voi că eu sunt glumesc, e chiar aici.
Care este cel mai eficient mod de a a sorta un milion de numere întregi pe 32 de biți?
>> -Well--
>> Îmi pare rău, Poate--
>> Nu, nu, nu.
Cred că genul bubble ar fi în mod greșit de a merge.
>> Haide, care l-a spus asta?
N-am văzut calculator știința în fundal.
>> -Avem Spionii noștri acolo.
>> -Bine, Să ceară un alt întrebare interviu.
>> [END VIDEO PLAYBACK]
>> SPEAKER: Deci, vorbim despre anumite numere, deși,
nu va fi tot ceea ce util.
Nu este o lectie de viata care cu bule fel, având în vedere un milion de intrări,
s-ar putea să ia cât mai multe 500 de miliarde de pași.
Nu poti generaliza într-adevăr prea eficient din care
și să ia decizii de proiectare bune atunci când scrieți programe.
Așa că haideți să ne concentrăm totuși asupra modului am putea simplifica acest rezultat.
>> Așa că m-am evidențiat în galben aici rezultatul n pătrat împărțit la 2,
astfel încât un milion la pătrat împărțit la 2, și apoi
Am subliniat ce răspunsul final a fost
odată ce scade off n împărțit la 2.
Și afirmația am de gând să fac acum este, Cui îi pasă naiba dacă scădem off
un pic de n vechi de peste 2, atunci când primul o parte din această formulă este mult mai mare?
Acesta domina pe celalalt termen, n la patrat impartit la 2
este mult mai mare, în mod clar, ca n devine mare ca un milion,
că există într-adevăr o mare diferență la sfârșitul zilei între 500 de miliarde
și 499999500000?
Nu chiar.
Și așa cum vom face ca oamenii de stiinta de calculator este
ignora aceste condiții de ordin inferior și ia ceva de genul asta și într-adevăr
doar se simplifica la termen care va conta.
Cele mai mari Seturile noastre de date a obține, cu atât mai mare bazele noastre de date ajunge, mai multe pagini web
avem de a căuta, cu atât mai mult prietenii aveti pe Facebook.
>> Ca n devine mai mare, suntem într-adevăr O să aibă grijă de cel mai mare
Termenul în orice astfel de analiză a performanța noastră algoritmi.
Și am de gând să spun, știi ce, bubble sort este pe ordinea de mare O,
de ordinul a n pătrat.
Nu e chiar n pătrat cum am văzut,
dar cui îi pasă cu adevărat despre acei termeni mai mici,
și sincer, care într-adevăr îi pasă dacă vom împărți cu 2?
Asta e doar un factor constant.
Și este 500 de miliarde, comparativ cu 250 miliarde de adevărat că mare lucru?
Aș putea aștepta doar un an, lasa laptop-ul meu propriu
obține de două ori mai repede în hardware, și că un fel de diferență
doar dispare în mod natural în timp.
>> Ce ne pasă este expresia, partea
expresiei care va varia ca intrare noastră devine mai mare și mai mare.
Și, într-adevăr, în lumea reală, asta e ceea ce se întâmplă din ce în ce
Este intrările la problemele noastre și algoritmi sunt ce mai mare.
Atat de mare O va fi notația, notația asimptotică, că ne-am
utilizați ca oamenii de stiinta de calculator pentru a descrie de performanță, sau timpul de execuție,
unui algoritm.
Astfel încât să putem compara algoritmi pe computere diferite scrise
de diferite persoane, prin utilizarea unele metric fundamental similară
cum ar fi numărul de comparații esti a face, sau poate că numărul de swap-uri
faci.
>> Ceea ce nu vom număr este cantitatea de timp
care trece pe ceas pe peretele de obicei.
Ceea ce nu vom să vă faceți griji despre este cât de mult de memorie
pe care îl utilizați în prezent la în ultimul rând, deși asta e
o altă resursă am putea măsura.
Vom încerca să-și bazeze analizele noastre doar pe operațiunile de bază, cele,
sincer, pe care le puteți vedea mai vizual.
Deci, cu ceva de genul O mare de n pătrat, eu susțin că O de n la patrat
este o limită superioară pe așa-numitele timp de bule tip de funcționare.
Cu alte cuvinte, dacă a vrut să pretindă că nu există
această limită superioară de cât de multe pașii unui algoritm s-ar putea lua,
ea va fi în O mare de n pătrat în acest caz, o limită superioară.
>> Ce dacă în loc să schimb Povestea a fi nu despre bubble sort,
dar despre acest limită superioară.
Vă puteți gândi la un algoritm că ne-am uitat la deja
a cărui limită superioară, maxim măsura de timp sau operațiuni,
ar fi spus să fie delimitate de n, o funcție liniară,
nu una de gradul doi care este curbat?
Ce este un algoritm care Intotdeauna este nevoie de nu mai mult
decât ca n trepte, sau Pași 2n, sau etape 3n?
Da?
>> Audiența: Găsirea cel mai mare număr într-o listă?
>> Vorbitor: Perfect, găsirea cel mai mare număr într-o listă.
Dacă am dat o listă de oameni, de exemplu,
fiecare dintre care deține un număr, ceea ce este numărul maxim
de măsuri ar trebui să mă ia, o persoană rezonabil inteligent,
pentru a găsi cea mai mare persoană în această listă?
n, corect?
Pentru că, în cel mai rău caz, în cazul în care ar putea fi cea mai mare valoare?
Corect, tot drumul de la sfârșitul.
Deci, în cel mai rău caz limita superioară, s-ar putea
trebuie să meargă până la capăt aici și să fie ca,
oh, aici e numărul opt, sau orice care valoare este.
Acum, ar fi o prostie dacă am continuat drumul, nu?
Privind pentru mai multe și mai multe elemente în cazul în care ultimul dintre ei este acolo?
Deci cu siguranță, n este o limită superioară.
Nu am nevoie să ia mai multe etape decât atât.
>> Deci, ceea ce, dacă în schimb am propus ca există algoritmi în această lume care
au un timp de funcționare care este delimitată de O mare de log n, log n?
În cazul în care am văzut acest lucru înainte?
Da?
>> Audiența: În problema cartea de telefon?
SPEAKER: Ca problema cartea de telefon.
Care a fost măsura de modul în care mult timp sau cât de multe lacrimi IT
Mi-a luat pentru a găsi pe cineva ca Mike Smith în cartea de telefon?
Am pretins că a fost log n, și chiar dacă necunoscut sau este
un pic neclar ce o logaritm sau exponent a fost,
amintesc doar că log n în general, se referă la procesul,
în acest caz, de divizare ceva în jumătate din nou, și din nou,
și din nou, și din nou, astfel încât să devine din ce în ce mic ca sa faci asta.
>> Deci, jurnal de n se referă, sigur, de exemplu cartea de telefon,
a binar de căutare în teorie, când ne-am a avut ușile virtuale de pe bord,
sau când Sean a fost căutând ceva.
Dacă ar fi folosit binar de căutare, log n ar fi limita superioară a de cât de mult
timp care ia.
Dar aceste algoritmi, care a fugit în log n asumat ceea ce detaliu cheie?
Aceasta lista a fost sortate, nu?
Algoritmul tau este greșit dacă datele introduse nu sunt sortate,
și totuși îl utilizați ceva de genul binar de căutare
pentru că s-ar putea sari drept asupra elementului
fără să realizeze că e într-adevăr acolo.
>> Acum, ceea ce ar putea însemna aceasta, O mare de unul?
Acest lucru nu înseamnă că algoritmul dvs. ia unul și numai un singur pas,
aceasta înseamnă doar este nevoie de o număr constant de pași.
Poate e un, poate e 10, poate e 1000,
dar este independent de dimensiunea problemei.
Nu contează cât de mare n este, un algoritm de timp constant
are întotdeauna același număr de pași.
Deci, ceea ce ar putea fi un algoritm am vorbit despre sau doar
intuitiv care vine la tine că întotdeauna se execută în așa-numita constanta de timp?
Da?
>> Audiența: Adăugați două numere.
SPEAKER: Adăugați două numere, 2 plus 2 egal 4, terminat.
Deci, care ar putea lucra, ce altceva?
Cum despre lumea mai real, da?
>> Audiența: Găsirea primul lucru într-o listă.
SPEAKER: Găsirea primul element dintr-o listă, sigur.
Am fost de fapt vorbesc despre tablouri deja,
cum a face tu a lua de la primul element dintr-o matrice,
indiferent de cât de mult matrice este în cod C?
Tocmai ai folosi ca suportul notație de zero, bam, tu esti acolo.
Și într-adevăr, tablouri, ca o parte, suport ceva cunoscut în general
ca acces aleator, cu acces aleator memorie, pentru că puteți pur și simplu
sări la un singur loc.
Putem face acest lucru chiar mai mult, pur și simplu putem derula la săptămână la zero
când am făcut Scratch.
Cât timp a durat pentru spune bloc în Scratch pentru a executa?
Doar constantă de timp, nu?
Spune ceva, spune ceva, nu contează
cum zgârieturi mari mondial este, este întotdeauna de gând să ia aceeași cantitate de timp
a spune pur și simplu ceva.
>> Deci, asta e constanta de timp, dar ceea ce este de cealaltă parte?
În cazul în care a fost superior limite, dacă vrem
pentru a descrie limitele inferioare a algoritmilor de funcționare timp?
Aproape un cel mai bun caz potențial, dacă vreți,
deși acești termeni ar putea aplica cel mai bine cazuri, mai grave cazuri, cazuri medie, mai
în general, dar să ne concentrăm pe limite mai mici, mai general.
Ce este un algoritm care are o limită inferioară de n pași,
sau etape 2n, sau etape 3n?
Unele factor de n pași, care este mai mic de legat.
Da?
>> Audiența: Bubble fel?
>> SPEAKER: Bubble sort ia tu n minim trepte, de ce?
De ce este asta?
De ce ar trebui ca început să vină la tine intuitiv, chiar dacă o face doar
încă?
Da?
>> Audiența: [inaudibil].
SPEAKER: Exact.
În cel mai bun scenariu posibil de bule fel, și o mulțime de algoritmi,
dacă am mână opt persoane care sunt deja sortate,
ar fi o prostie pentru tine, algoritmul,
pentru a merge înainte și înapoi mai mult de o dată, nu?
Pentru că de îndată ce de mers pe jos prin lista dată,
ar trebui să realizeze, oh, am făcut nici o swap-uri, această listă este sortată, ieșire.
Dar asta nu te va lua n pași.
>> Și invers, ceea ce este un alt mod de gândire despre el?
Bubble sort este un omega, ca să spunem așa, de n,
pentru că dacă te uiți la mai puțin de n elemente, ceea ce
este problema fundamentală acolo?
Nu știi dacă e sortate, chiar.
Noi, oamenii, s-ar putea privire la opt oameni și să fie ca, oh, e sortate,
că nu m-n pași iau, dar a făcut-o.
Ochii tăi, chiar daca natură a avea un domeniu mare de vizibilitate,
te-ai uitat la opt elemente, te-ai uitat la opt persoane,
E opt trepte în mod eficient.
Și numai dacă am mers prin toată Lista nu îmi dau seama, da, sortate.
Dacă mă opresc la jumătatea drumului de gândire, toate drept, e destul de sortat până acum,
care sunt sansele nu e sortate?
Asta nu algoritmi va fi corect.
S-ar putea fi mai rapid, dar incorect.
>> Deci, acum avem un fel de descrie o limite inferioare,
și ce despre constanta de timp?
Ce este un algoritm care are o mai mică legat pe timp de funcționare de unul?
1 pas, 2 trepte, 10 pași, dar constantă, independent de n,
mărimea de intrare?
Da, în spate.
>> Audiența: printf?
SPEAKER: Ce-i asta?
Audiența: printf?
SPEAKER: printf.
OK, sigur.
Deci, este nevoie de un număr fix de pași.
Și ar trebui să acum-- acum că vorbim despre cod C
și nu Scratch, ceva ca să zicem, cu printf,
noi ar trebui să înceapă să se atent.
Pentru ca printf ia de intrare, este un șir de caractere,
și siruri de caractere nu au punct de vedere tehnic lungime.
Deci, dacă acum ne-o dorim pentru a alege pe tine, dacă nu te superi,
punct de vedere tehnic am putea argumenta că printf se ia o intrare de lungime variabilă,
și cu siguranță ar putea dura mai mult timp pentru a imprima un șir atât de mult,
decât acest timp.
>> Deci, ceea ce, dacă luăm în considerare doar sortarea și căutarea exemple?
Ce despre Mike Smith în telefon carte, sau binar de căutare, mai general?
În cel mai bun caz, ceea ce s-ar putea întâmpla?
Am deschis cartea de telefon și, bam, există numărul lui Mike Smith.
Pot să-l sun imediat.
>> A luat un pas, poate doi pași, dar un număr constant de pași
dacă am avut noroc.
Și sincer, am văzut pe Luni colegul tău
obține destul de norocos de două ori la rând.
Și asta a fost, într-adevăr constant timp într-o limite inferioare
pe algoritmul în cauză pentru a găsi numărul 50 în spatele celor închis
usi.
>> Acum, ca o paranteza, dacă veți descoperi că atât de mare O, marginea superioară,
și omega, limita inferioară, sunt una în același, că
este aceeași formulă în paranteze, puteți, de asemenea
spune, doar pentru a fi de lux, că ceva este în theta
de n sau teta de o alta valoare.
Asta înseamnă că, atunci când mare O și omega sunt aceleași.
Acum, ce zici de selecție fel?
Să folosim acest nou vocabular.
În selecție fel, ceea ce am fost noi face din nou, și din nou, și din nou?
Am fost de gând înainte și înapoi prin lista, în căutarea pentru cine?
Cel mai mic număr.
>> Deci, cum de multe etape, cum mai multe comparații am făcut
trebuie să facă, în scopul de a da seama cine cel mai mic element din listă a fost?
n minus 1, corect?
Pentru că dacă am începe cu cel pe care îl am dat și eu încep el sau ea a comparat,
atunci el sau ea, l- sau ei, el sau ea, eu
poate asocia numai elemente împreună n minus 1 de ori.
Deci selecție are un fel similar n minus 1 pașii pentru prima dată.
>> Câți pași nu-l mă ducă la găsi de-al doilea mai mic element?
n minus 2, pentru că eu sunt prost fiind dacă mă tot uitam la aceiasi oameni
din nou, în cazul în care l-am ales deja sau ei și le-a pus în locul lor.
Și a treia etapă, n minus 3, atunci n minus 4.
Am văzut acest model înainte, și într-adevăr
selecție fel similar a legat un superior
de n pătrat dacă facem aia de sumare.
Ce este limita inferioară, selecție fel ei?
Minim, cât de mult timp de selecție trebuie să fel ia, așa cum l-am definit pe luni?
Propune două opțiuni.
Poate e n, la fel ca înainte.
Poate e n patrat, așa cum se este acum ca marginea superioară.
>> Audiența: n patrat.
SPEAKER: n patrat.
De ce?
>> Audiența: Pentru că ai pentru a defini [neauzit].
>> SPEAKER: Exact.
Cel puțin așa cum am definit selecție fel a fost destul de naiv, continua,
găsi cel mai mic element.
Du-te din nou, a găsi cel mai mic element.
Nu e nici un fel de optimizare acolo că
s-ar putea să-mi abandona după doar n sau cam asa ceva pași.
Deci, într-adevăr, selecție fel, omega de n la patrat.
>> Ce fel de inserție, unde am luat cine a fost dat, iar apoi l-am plopped
sau ei în locul potrivit?
Apoi am procedat la persoana a doua, el sau ea se trânti în locul potrivit.
Apoi, următoarea persoană, trânti el sau ea în locul potrivit.
Observați că acest lucru este foarte liniar, ca să spunem așa.
Sunt o linie dreaptă, eu sunt Nu merge înainte și înapoi,
N-am mai uita înapoi într-adevăr, dar ceea ce se întâmplă atunci când l-am insera
sau ei în începutul de lista așa cum am făcut-o luni?
Ce se întâmplă?
Da?
Audiența: [inaudibil].
Vorbitor: Da, a fost captura, corect?
S-ar putea aminti de colegii dumneavoastră, în cazul în care
s-au a face orice mișcare cu picioarele lor, că a fost o operație.
Deci, dacă au fost trei oameni aici și noua persoana a apartinut mod acolo,
pe o scenă mult timp ca aceasta, sigur, el sau ea ar putea merge chiar până la capăt.
Dar dacă ne gândim la o calculator și o serie de memorie,
aceste persoane vor să aibă de a amesteca peste
pentru a face loc pentru acea persoană.
Și astfel încât n minus 1 shufflings, n minus 2 shufflings, n
minus 3 shufflings este doar un fel de întâmplă în spatele meu, nu în fața mea
ca și mai înainte, într-un sens.
Acum, ca o paranteza, și ca este posibil să fi văzut on-line
dacă începe să bagi în jurul despre felul, există atât de multe altele diferite
acolo, unele dintre ele mai bine decât altele.
Într-adevăr, este unul bogosort că e un fel de distractiv să se uite în sus.
Bogosort ia un set de numere sau spune un pachet de cărți,
le amesteca la întâmplare, și verifică dacă acestea sunt clasificate în funcție.
Și dacă nu, o face din nou.
Dacă nu, o face din nou.
Incredibil de prost.
>> Și, într-adevăr, dacă ai citit ca articolul din Wikipedia,
porecla ei este un fel de prost.
Acesta va funcționa în cele din urmă, sperăm, dat fiind suficient timp,
dar acea cantitate de timp ar putea dura ceva timp.
Deci, dacă aș putea, hai sa lucruri de viteză de la exemplul Mary Beth lui mai devreme,
de a avea ceva mai multe elemente, dar mai mult de două procesoare.
Doi oameni, dacă nu m-ar deranja alaturi de mine.
Ce zici de o aici, și Să go-- nimeni pe acolo?
Nimeni de acolo?
OK.
Tu cu negru cămașă, da, vin pe jos.
Bine, care e numele tău?
>> Audiența: Peter.
>> SPEAKER: Ce-i asta?
>> Audiența: Peter.
Vorbitor: Peter, David, mă bucur să te cunosc.
În regulă, avem Peter aici, dacă Vrei să vii pe masa aici.
Și cum te cheamă?
>> Audiența: Elena.
SPEAKER: Elena.
OK, mă bucur să te cunosc.
Elena întâlni Peter.
Peter, Elena.
Și vom avea nevoie de Andrew până aici, de asemenea, vă rog.
Iar provocarea se întâmplă să fie pentru a sorta un pachet de cărți.
Și dacă nefamiliare, punte de carduri ar trebui în cele din urmă
fi sortate ceva ca aceasta în cazul în care vom face cluburilor, apoi
de pică, apoi inimile și diamante, de la as fi unul,
tot drumul până la rege.
>> Cardurile am de gând să vă dau vor fi 52 în cantitate.
Vom similar tu timp, într-o clipă.
Vom arunca Andrew pe ecran aici,
astfel încât să privesc cum faci acest lucru.
Si pentru ca toate acestea este cu atât mai vizibil,
acestea sunt cărțile am primit pe Amazon.
Deci, ele sunt deja la întâmplare sortate, iar noi te vom cronometra.
Și vom păstrați-l real, de data aceasta,
așa că vom încerca să te presez pentru că în caz contrar aceasta va primi plictisitor
repede.
Dacă ai putea continua să sortați 52 elemente împreună prin intermediul unor mijloace, acum.
>> Și, din nou, ca ne uitam acestea baieti fac ceea ce, în cele din urmă
se va produce o evidentă urmare, cred că într-adevăr despre
cum acestea sunt fiecare o face, cum s-ar putea descrie.
Pentru că din nou, acestea sunt toate procesele, algoritmi
pe care le ia pentru a acordat ca un om.
Dar ai avut, probabil, mult timp intuiție, cu mult înainte de tine, chiar
gândit de a lua o tu clasă de informatică
ar fi avut intuiția cu care pentru a rezolva problemele de acest gen.
Dar, odată ce recunoaște modele și începe
pentru a formaliza pașii cu care te rezolvarea acestor probleme,
veți găsi pe care le poate rezolva mult mai interesant și mult mai complex
Probleme rapid.
Deci, cineva din public, ceea ce este cel puțin un element al algoritmului
pe care le utilizați aici?
>> Audiența: [inaudibil]
SPEAKER: Ce-i asta?
Audiența: Prin costum.
SPEAKER: Prin costum.
Deci, în primul rând ei se grupează toate diamantele împreună
se pare, tot de la inimile împreună, se pare,
și așa mai departe, fără respectarea pentru numerele de pe carduri.
Și acum apar, de exemplu, să fie sortarea acestea în număr.
Foarte bine.
>> Bine, deci ce se întâmplă la fi ultimul pas, atunci aici?
După ce vom avea patru costume sortate, ceea ce avem nevoie pentru a face la cele patru piloți
pentru a realiza o clasificate în funcție de punte, pur și simplu?
Deci, avem nevoie pentru a le îmbina din nou.
>> Deci, există o idee interesantă care din nou, îndrăznesc să spun, este foarte intuitiv chiar
daca nu s-ar fi pălmuit acest tip de eticheta pe ea.
Această noțiune fundamentală de divizare problema nu în jumătate de data aceasta,
dar cel puțin în patru bucăți.
Rezolvarea destul de mult Probleme fundamental identice
izolat unul de celălalt, și apoi fuzionarea rezultatele.
Și, excelent, terminat.
Bine, o rundă de mare de aplauze, dacă am putea.
>> [Aplauze]
>> Difuzor: Nu am nici o idee despre ceea ce veți face cu acestea, dar aici te duci.
Vă mulțumesc foarte mult.
Deci, hai sa vedem, la doua minute și opt secunde,
dacă doriți să conteste prietenii tăi.
Ce apoi se va fie o ia de la această
că ne putem mobiliza mai mult, în general?
Ei bine, cred că înapoi la această matrice de numere,
și cred că înapoi acum la unele dintre cele mai pseudocod am scris in trecut,
iar acest lucru a fost Pseudocodul pentru rezolvarea problemei cartea de telefon.
Din ce în pseudocod I enumerat un mod mai metodic
de a descrie cum am facut-o foarte intuitiv Algoritmul uman de împărțire a telefonului
carte în jumătate, repeta, repeta, repeta, până găsesc pe cineva ca Mike Smith,
dacă el este într-adevăr în cartea de telefon.
>> Dar am un fel de folosit ceea ce voi numi o abordare foarte iterativ aici,
în aviz special linia 8 si linia 11.
Acestea sunt dovezi ale unei iterativ abordare, o abordare looping,
pentru că exact comportamentul ei induce.
Aceste linii ambele spun du-te la fel linie de trei, și puteți de
cred că de la dvs. ochii minții lui ca fiind o buclă.
Acesta îți spune să te întorci până la pasul trei și se repetă, din nou, și din nou,
și din nou.
>> Dar dacă ne folosim o idee cheie aici că am făcut nu ultima oară,
și simplifica linia 8 și linia 11 și vecinii lor
ca doar acest lucru, în galben.
Nu este fundamental scurtarea Pseudocodul foarte mult,
dar este fundamental în schimbare natura algoritmul meu.
Ceea ce vreau să spun acum în etapa 7, în etapa 10,
este de a căuta pentru Mike în același mod exact,
dar doar în partea stângă jumătate sau jumătatea din dreapta.
>> Cu alte cuvinte, dacă Am început de la pasul unu,
ridica cartea de telefon, deschis la mijloc din cartea de telefon, uita-te la nume,
dacă Smith este unul dintre numele lui, suna Mike, altfel
dacă Smith este mai devreme în carte, pas șapte căuta Mike la jumătate din stânga a cărții.
Dar acest tip de se simte ca ea mă părăsește agățat, nu?
In galben, este un instrucțiuni, dar cum nu am
cauta Mike în stânga jumătate din cartea de telefon?
În cazul în care nu am un algoritm cu care am
Puteți căuta pe cineva ca Mike Smith?
Ei bine, ne-a mirat în față.
Eu pot folosi literalmente exact la fel Programul va efectiv până la partea de sus
din nou și re-alergare aceleași linii de cod.
>> Deci, chiar dacă acest lucru ar trebui să se simtă ca un pic de o definiție ciclic
în cazul în care răspunzi cuiva întrebare cu doar un fel de a cere
aceeași întrebare din nou, cum ar fi de ce, de ce, de ce?
Realitatea este că ne-am codat greu o pereche de linii speciale, etapa 4,
care este un dacă, și 12, care este efectiv o altă ramură,
pentru că avem aceste măsuri masura provizoare, acest algoritm va termina dacă vom
găsi Mike, sau dacă nu o facem.
Dar, în pasul 7 și 10 acum, ne-am ceea ce vom numi un algoritm recursiv.
Și recursivitate este într-adevăr o idee puternic că e un pic mintea îndoire la început,
pe care le putem aplica acum, după cum urmează.
>> Merge fel va fi ultima genul asta ne uităm la, cel puțin în clasa oficial.
Și este fundamental diferit de la cei trecut trei, și, desigur,
Ultima patru dacă includem bogosort.
Iată Pseudocodul pentru îmbinare fel.
Când la intrare de n elemente, astfel încât dat o matrice de dimensiune n, în cazul în care n este mai mic de 2,
reveni.
Deci, de ce nu am că bun-simț verificați mai întâi?
Care este implicarea, dacă am mână o matrice a cărui lungime n este mai mic de 2?
Este deja sortate, în mod evident, nu?
Deoarece lista are fie un element, care este trivial
clasificate în funcție pentru că e singurul lucru acolo.
Sau, este de dimensiunea zero, ceea ce înseamnă nu e nimic pentru a sorta, astfel de natură
este sortat.
Nu este nimic în neregulă acolo.
Deci, asta e așa-numitul caz noastră de bază.
>> Aceasta este similară în spirit pentru ceea ce am făcut cu Mike.
Dacă lui Mike în cartea de telefon, suna-l.
Dacă nu e acolo, renunta.
Este o așa-numită caz ​​de bază, pentru a se asigura acest algoritm, la sfârșitul zilei
va opri în anumite circumstanțe.
>> Dar aici e un salt de credință acum, altceva, sorta jumătatea stângă a elementelor,
apoi sorta dreapta jumătate a elementelor,
și apoi îmbinați jumătățile sortate.
Și aici e în cazul în care se simte ca și cum am tocmit afară.
Te-am rugat să sortați n elemente, și eu sunt
zis, OK, nu prin sortarea partea stângă și sortarea dreapta.
Dar eu spun una alt lucru, și aceasta
este tema cheie se pare în intuiția până acum,
există acest al treilea pas de fuziune.
Care chiar dacă Pare atât de prost în spirit,
ca fuzioneze doar lucrurile împreună, se pare
pentru a fi un pas cheie spre reasamblare a două probleme care
au fost împărțiți în cele din urmă la jumătate.
>> Deci fuzioneze fel, să facem acest lucru, dacă veți umor mine, cu mai mult de o demonstrație,
doar astfel încât să avem o anumită numere de a lucra cu.
Pot să schimb opt stres bile pentru opt persoane?
Bine, ce zici tu trei, patru te în această secțiune, cinci, șase, și să
Nu 7, 8, haide sus.
OK, da OK.
Minus 8, acolo mergem, plus 1.
Excelent.
Toate veni chiar pe sus, să da repede numere.
Numărul doi, numărul trei, numărul patru, număr de cinci, șase, șapte, opt.
Am făcut opt ​​corect de data asta.
>> OK, merge atât de departe, dacă ai putea, și Să sortate în ordinea originală
că am avut ieri care a analizat ca aceasta, dacă nu te superi.
Și să o facem în fața mesei.
În regulă, deci fuziona fel.
Acest lucru este în cazul în care se va pentru a obține un fel de interesant,
pentru că mi se pare a fi oferindu-mă atât de mult mai puține informații de astăzi.
>> Deci fuzioneze fel în primul rând, pe de intrare de n elemente,
și este, evident, nu mai puțin de două, este opt, așa că am ceva mai mult de lucru.
Deci, acum ne-am mental ca o clasă sunt acum în altă ramură,
ceea ce înseamnă trei etape.
În primul rând, trebuie să SORT jumătate din stânga a elementelor.
Deci, cum merg faci acest lucru?
Ei bine, am de gând să fel de împărți mental lista de aici,
nu trebuie să muta punct de vedere fizic, și eu sunt
O să se concentreze doar pe jumătate din stânga a elementelor de aici.
Deci, cum să mă duc despre sortarea o listă acum de dimensiune patru?
Care este algoritmul meu?
În primul rând am verificat este n mai puțin de două, nu, așa că am proceda la blocul altceva din nou.
Sortare lăsat jumătate de elemente.
>> Deci, acum, din nou, mental, și aici
va trebui să acumuleze o mulțime de istorie mental, dacă vreți.
Acum, eu sunt de sortare stânga jumătate din jumătatea stângă.
Bine, acum eu numesc aceeași îmbinare meu sortare algoritm, este pentru n mai puțin de doi?
Nu, aceasta este de două, așa că trebuie să rezolve jumătatea din stânga, și jumătatea din dreapta.
Deci, aici vom merge, sorta jumătatea stângă.
De ce nu doar ia un pas înainte.
Care e numele tău?
>> Audiența: Darren.
>> Difuzor: Dan.
Dan a făcut un pas înainte.
>> Audiența: Darren.
Vorbitor: Darren, făcut.
Ai spus Darren sau Dan?
>> Audiența: Darren.
>> SPEAKER: Darren.
OK, Darren și-a intensificat el este acum clasificate în funcție înainte și.
Și acest lucru este aproape o cerere stupid, nu?
Eu nu par într-adevăr să fie realizarea nimic, dar hai continua.
Acum, permiteți-mi să rezolve dreapta jumătate a elementelor.
Care e numele tău?
>> Audiența: Luke.
>> SPEAKER: Luke.
Haide, un pas înainte.
Adoptată, am sortat Luke.
Jumătatea din stânga este acum clasificate în funcție și jumătatea din dreapta este acum clasificate în funcție,
dar din nou, nu e un pas cheie aici.
De ce am lângă trebuie să fac?
Merge jumătățile sortate.
Acum vom avea doar toți înainte și înapoi, în acest fel,
pentru ca am un fel de nevoie spațiu zero.
E ca și cum acestea Voi sunteți pe o masă,
și am nevoie de camera pentru a le muta în jurul pe.
Așa că am de gând să fuzioneze voi uitandu
la jumătatea stângă și jumătatea din dreapta.
Și care, evident, este pe primul loc, jumătate stânga sau pe jumătate dreptate?
Deci jumătate dreptate, așa că să trecem peste Luca aici la poziția inițială Darren lui.
Și acum să fuzioneze jumătatea lor din stânga în, Darren se va muta acolo.
>> Deci, se simte ca aproape un efect balon fel,
dar algoritmul meu fundamental, foarte diferit de data asta.
Dar acum este în cazul în care lucrurile devin un putin enervant pentru ca
Trebuie să înapoi mental unde am plecat de pe.
Tocmai am fuzionat jumatati sortate, ceea ce înseamnă că sunt în cazul în care în algoritmul meu?
Trebuie să sorteze jumătatea din dreapta, nu?
>> Daca înapoi, la propriu pe video, veți
vedea că am ajuns la această punct de Luca și Darren
de sortare stânga jumătate din jumătatea stângă.
Apoi ne-am unit pe cei jumătăți sortate, care
înseamnă că următorul pas este genul jumătate chiar din jumătatea stângă.
Bine, hai să face acest lucru mult mai repede.
În regulă, șase, am de gând să pretindă ce sunt acum clasificate în funcție, haide înainte.
Care e numele tău?
>> Audiența: Adriano.
>> SPEAKER: Adriano.
Adriano este acum clasificate în funcție.
Și cum te cheamă?
>> Audiența: Alex.
>> SPEAKER: Alex este acum clasificate în funcție.
Jumătate la stânga, pe jumătate dreptate, Care este pasul final?
Merge.
Destul de banal, așa că eu sunt O să fuzioneze în șase,
ia un pas înapoi, opt, să ia un pas înapoi.
Și acum observa acest lucru este un Takeaway util, ceea ce
este acum adevărat despre jumătatea din stânga a lista, indiferent de cum am început?
Acesta este sortat.
>> Acum nu este sortate în schema mare a lucrurilor,
dar este sortată în mod independent de cealaltă jumătate.
Acum, ce pas sunt eu pe dacă am păstra rebobinare cum a început povestea?
Acum trebuie să rezolve jumătatea din dreapta.
Deci, acum suntem mult înainte, la începutul poveștii,
și să facem acest lucru mai rapid.
Așa că am de gând pentru a sorta jumătate chiar din toata lista.
Care este următorul pas?
Sortarea jumătatea din stânga a jumătatea din dreapta.
Sortarea jumătatea stângă a jumătatea stângă a jumătatea din dreapta.
Și cum te cheamă?
>> Audiența: Omar.
>> Vorbitor: Omar, un pas înainte, gata.
Jumătate stânga este sortat.
Și cum te cheamă?
>> Audiența: Chris.
>> Vorbitor: Chris, ia un pas înainte, vă sunt acum clasificate în funcție.
Care este pasul cheie acum?
Merge.
Deci, una este de gând să fuzioneze în loc aici, dacă ai putea lua un pas înapoi,
și trei se va ia un pas înapoi, merge.
Astfel, jumătatea stângă a jumătate chiar, este acum clasificate în funcție.
Sincer, acest algoritm se simte ca și cum am se pierde mult mai mult timp decât înainte,
dar dacă am făcut acest lucru în timp real, vom vedea ce takeaways va fi.
Acum, iată-mă, chiar jumătate din jumătatea din dreapta,
lasă-mă să merg mai departe și sorta jumătatea stângă.
Un pas înainte, care e numele tău?
Audiența: Ramsey.
SPEAKER: Ramsey este acum clasificate în funcție.
Care e numele tău?
>> Audiența: Marina.
>> SPEAKER: Marina este acum clasificate în funcție de bine, dacă luați un pas înainte.
Key pas aici este acum fuzioneze, eu sunt O să smulgă de la cei doi liste,
la stânga și la dreapta.
Cinci este de gând să vină în primul rând, și șapte va veni următorul.
Și din nou, aceasta este în mod deliberat.
Faptul că o duc pași înainte și înapoi
are menirea de a reprezenta că nu putem face acest algoritm în loc de ușor
ca bule fel, și selecție de sortare, și inserare fel în care ne-am
păstrat schimbarea oameni.
Am literalmente nevoie de un fel de hârtie zero în care
pentru a pune acești oameni în timp ce eu fac fuziunea,
și apoi le pot pune la loc.
Și asta e cheia pentru că eu sunt, folosind un noi resurse, spatiu, nu doar timp.
>> OK, asta e uimitor.
Jumătate stânga este sortat, pe jumătate dreptate este sortat, acum că cheia fuzionează pas.
Cum am de gând să fuzioneze asta?
Deci, dacă voi urma mea mâna stângă și mâna dreaptă,
Am de gând să arate mâna stângă la jumatatea stanga, dreapta mea
la jumătatea din dreapta, iar acum trebuie să decidă pas cu pas care să fuzioneze în.
Cine evident este pe primul loc?
Numărul unu.
Deci, vino aici, aici e pad nostru zero.
Deci, acum numărul unu, și notificare ce voi face cu mâna dreaptă,
Am de gând să se mute o mâna mea dreaptă pas pe la punctul numărul trei,
iar acum trebuie să facă aceeași decizie.
Și, de fapt sta chiar în fata de Luca aici dacă ai putea,
pentru că aceasta este pad noastră zero.
Deci, cine urmeaza?
Avem Luca cu numărul doi sau Chris cu numărul trei.
Evident Luca, număr doi, așa că ai venit aici.
>> Dar mâna stângă este acum de gând să care crește de la punctul de la Darren,
și aici e cheia ia cu fuzionează, am de gând să face asta,
evident, dacă aveți un fel a urma logica.
Dar mâinile mele nu sunt niciodată merge înapoi,
ceea ce înseamnă că sunt numai vreodată în mișcare a a plecat cu procesul meu de fuziune,
și care va fi cheia pentru Analiza noastră într-o clipă.
>> Deci, acum, să terminăm asta rapid.
Deci, trei urmeaza, apoi patru urmeaza,
și acum cinci urmeaza, apoi șase, și șapte, și apoi în cele din urmă opt.
Se simte ca cel mai lent algoritmul încă, dar nu dacă suntem de fapt
rulați-l în același fel de viteza de ceas, ca să
vorbi, cu aceeași ticăie ceasul ca înainte.
De ce?
Ei bine, haideți să aruncăm o uita-te la rezultatul final.
>> Să ne întoarcem aici, lasă-mă să trage o demonstrație de vedere vizual
din ceea ce am făcut.
Zoom-ul aici, pe acest Pagina de aici, spune Firefox
care ne-o dorim să stau la coadă în această casetă, să
spune balon fel, cu care acum suntem bine familiarizați,
fel de selecție, care este un alt destul de un simplu,
iar acum astăzi tip merge, care va fi sfârșit nostru culminant.
Motivul pentru care a durat atât de mult mai mult timp aici cu oamenii și mi-verbal este,
evident, am explicat fiecare pas.
Dar dacă pur și simplu executați acest lucru, mult ca am facut un fel de bule și selecție
fel nu numai vizual, ceas cat de mult mai eficient
această pârghie de divizare și cucerirea
poate fi aplicat pe un set de date care este nu chiar dimensiune opt, dar chiar mai mult,
mult mai mare.
Eu vă dau fuzioneze fel, partea de laterale cu aceste alți algoritmi.
Acest lucru se întâmplă pentru a obține dureros repede, și se încheie
nu este deosebit de culminant, ei doar ajung sortate.
Dar cheia ia este că Uite cât de mult mai repede fuzioneze fel
a fost, dacă nu crezi că sunt doar un fel de joc cu tine.
Dacă vom face acest lucru o dată finală, hai sa reincarci aceasta, să mergem înapoi
și alege bule de sortare, și doar pentru lovituri,
Să alegem inserare fel, doar pentru o bună măsură.
Și de această dată, din nou, să alegeți Combinare fel și să
rula de fapt acestea cot la cot.
>> Și nu este vorba, de fapt, o întâmplare.
Ce am făcut în mod eficient este de am împărțit intrare meu la jumătate, din nou,
și din nou, și din nou.
Și nu e doar atât de multe ori puteți împărți dvs. de intrare în jumătăți, stânga
și drept.
Care este formula pe care o tot văd care descrie împărțirea în jumătate
din nou, și din nou, și din nou, și din nou?
>> Audiența: log n.
>> SPEAKER: log n.
Dar există un alt pas cheie, acest algoritm nu este log n pasi.
În cazul în care au fost conectați doar n pași, am fi în aceeași problemă
ca și mai înainte, unde nu putem fi că totul e sortate.
Trebuie sa te uiti minim la n elemente pentru a fi sigur că n elemente sunt clasificate în funcție,
altfel e un salt de credință.
>> Deci, este jurnalul minim n pași, dar ce despre acest pas cheie fuziune
unde am fuzionat jumătate stâng și drept jumătate și a mers pe scena?
Câți pași este că, pentru a fuziona?
Este n, dar n-am făcut doar fuziona timpul final.
Pe fiecare dintre aceste apeluri imbricate, pe fiecare din aceste fuziuni imbricate, eu încă sortate.
Am fuzionat aceste doi tipi, atunci aceste două baieti, atunci aceste doi tipi și așa mai departe.
>> Așa că m-am fuzionează din nou, și din nou.
De câte ori?
Deci, de fiecare dată am împărțit Lista în jumătate, am făcut o fuziune.
Împărțiți lista de la jumătate, face o fuziune.
Deci, dacă împărțirea pe lista se poate face log n ori,
și fuziunea în cele din urmă ia n trepte, ceea ce ar putea fi acum de sus
legat de funcționare timp de algoritmul nostru?
n log n.
>> Și într-adevăr, asta e ceea ce am realizat aici.
Deci, simt că voi vedea vizual atunci când aceste trei lucruri alerga cot la cot
este n pătrat împotriva n pătrat împotriva n log n.
Care fundamental vom vedea, nu numai astăzi, ci în viitor,
este mult, mult mai rapid.
O rundă de aplauze pentru aceste baieti, Eu îi va răsplăti cu bile de stres.
Să suspenda aici astăzi, și va vom vedea pe luni.