[SCRÂȘIT]
[FOSȘIT] [DĂ CLIC]
JUSTIN: OK.
Așa că este o plăcere să vă
văd pe toți.
Eu sunt Justin.
Sunt al treilea
instructor al tău pentru 6.006.
Este prima dată când particip
la acest curs.
Deși, desigur,
acesta este un material pe care cu
toții îl cunoaștem și îl iubim în
departamentul de informatică.
Recunosc, consider că
perspectiva de a preda
sortarea la 400 de oameni dintr-o
dată este terifiantă.
Dar o să
încercăm.
Și sperăm că asta se va diminua pe măsură ce
prelegerea continuă astăzi,
bine?
Așa că vom relua de unde am
rămas în ultima noastră prelegere
și vom continua
cu o temă similară pe
care o vom vedea pe
parcursul clasei noastre de algoritmi
aici în 6.006.
Cred că Jason și
colegii au
făcut o treabă grozavă
organizând această clasă în
jurul unor teme interesante.
Și așa că m-am gândit să încep
doar cu o mică trecere în revistă
a unor cuvinte cheie din vocabular.
De altfel, de obicei,
predau ora de grafică introductivă,
cursul de geometrie.
Și anul trecut, am
primit feedback care
spunea că am
scris de mână criminal în serie.
Nu sunt 100% sigur
ce înseamnă asta.
Dar vom folosi
diapozitivele puțin mai mult
decât în ​​mod normal, doar pentru a ne
asigura că puteți citi.
Și când scriu
pe tablă,
în orice moment, dacă
nu poți spune ce am scris, cu
siguranță sunt eu și nu tu.
Așa că doar anunță-mă.
Dar, în orice caz, în 6.006, tot
drumul înapoi în prelegerea noastră 1--
știu că a fost cu
mult timp în urmă--
am introdus două cuvinte cheie mari
care sunt strâns legate,
dar nu exact aceleași.
Sper că am înțeles
bine.
Dar, aproximativ,
există o temă aici,
care este că există un obiect
numit interfață, care este
doar o specificație de program.  Ne
spune doar
că există
o colecție de operațiuni
pe care vrem să le implementăm.
Deci, de exemplu, un set, așa cum vom
vedea astăzi,
este ca o grămadă mare de lucruri.
Și în culise,
modul în care aleg să-l implementez
poate afecta timpul de rulare
și cât de eficient este setul meu.
Dar modul real în care
interacționez cu el
este același, indiferent dacă folosesc o
matrice nesortată, o matrice sortată,
ce ai.
Pe de altă parte, ceea ce se
întâmplă în culise
este ceva numit
o structură de date,
care este o modalitate de a implementa
, într-un anumit sens,
o interfață.
Deci, acesta este obiectul
care pe computerul meu
stochează de fapt
informațiile
și implementează
setul de operațiuni
pe care l-am prezentat
în interfața mea.
Și așadar, cred că acest tip de
distincție
este o temă critică
în acest curs,
deoarece, de exemplu, în
primele două săptămâni, vom
vorbi despre multe
moduri diferite de a implementa
un set.
O să văd că
există o grămadă de compromisuri.
Unele dintre ele sunt foarte
rapide pentru anumite operațiuni
și lente pentru altele.
Și, în esență, avem
două decizii diferite
de luat atunci când
alegem un algoritm.
Una este să ne asigurăm
că interfața
este corectă pentru problema de
care ne preocupă.
Și celălalt este alegerea unei
structuri de date adecvate
a cărei eficiență și
utilizare a memoriei și așa mai departe se aliniază
cu prioritățile pe care le
avem pentru aplicația pe care o
avem în vedere.
Deci, sperăm că această
temă la nivel înalt are sens.
Și într-adevăr, din punct de vedere spiritual,
cred că acesta este mesajul principal
pentru a ieși din acest curs în
primele două săptămâni,
chiar dacă aceste
O, thetas
și așa mai departe sunt ușor de pierdut
pădurea printre copaci.
În orice caz, astăzi,
în prelegerea noastră,
ne preocupă o
anumită interfață,
care se numește set.
Un set este exact ceea ce
sună.
Este o grămadă mare de lucruri.
Și astfel o interfață setată
este ca un obiect
pe care doar tu poți continua să-i
adaugi lucruri.
Și apoi întrebând în interiorul
setului meu, acest obiect este aici?
Pot să-l găsesc?
Și atunci poate
asociez cu obiectele mele
din setul meu informații diferite.
Deci, de exemplu,
poate am un set
care îi reprezintă pe toți
elevii din sala noastră
de azi.
Da, și voi toți sunteți
asociați cu cartea dvs. de student
, care cred că
la MIT este un număr,
care are mai puțin de semn,
ceea ce este convenabil.
Așa că vă putem sorta pe toți.
Și asta ar putea fi
cheia care este asociată
fiecărui obiect din cameră.
Și atunci când
caut studenți,
poate introduc
numărul de student.
Și apoi vreau să întreb
setul meu, există acest număr
în setul de
studenți care sunt în 6.006?
Și dacă o face, atunci îl pot
retrage pe acel student înapoi.
Și apoi asociate
cu acel obiect
sunt o grămadă de alte informații pe
care nu le folosesc pentru a căuta,
deci, de exemplu,
numele dvs.,
nu știu...
numărul dvs. de securitate socială,
numărul cardului dvs. de credit, toate
celelalte lucruri de care am
nevoie pentru a avea o
profesie mai interesantă.
Deci, în orice caz, să completăm

puțin mai mult detaliile interfeței noastre setate.
Deci setul nostru este un container.
Conține toți
elevii din această clasă,
cel puțin într-un sens virtual.
Și astfel, pentru a
ne construi setul, desigur,
avem nevoie de o operație care
preia un obiect iterabil A
și construiește un set din el.
Deci, cu alte cuvinte, îi
am pe toți elevii
din această clasă reprezentați
poate într-un alt mod.
Și trebuie să
le introduc pe toate în setul meu.  De
asemenea, pot cere setului meu
câte lucruri este în el.
Personal, aș
numi această dimensiune.
Dar și lungimea este mișto.
Și apoi, desigur,
există o mulțime de moduri diferite prin
care putem interacționa
cu setul nostru.
Deci, de exemplu, am putea spune,
acest student ia 6.006?
Deci, într-un limbaj stabilit, o
modalitate de a înțelege asta
este să spunem că cheia -
fiecare persoană din această clasă
este asociată cu o cheie.
Acea cheie k există în setul meu?
În acest caz, voi
apela această funcție de căutare,
care îmi va da înapoi
elementul cu tasta k sau poate nul
sau ceva de genul dacă
nu există.
Poate pot șterge un obiect
din setul meu sau îl pot introduce.
Observați că acestea sunt
operații dinamice, ceea
ce înseamnă că editează de fapt
ceea ce este în interiorul setului meu.
Și apoi, în sfârșit, există tot
felul de operațiuni diferite pe
care aș dori să le fac pentru a
interacționa cu setul meu dincolo de
acest lucru din interiorul lui.
Deci, de exemplu, pentru
exemplul de identificare a studentului,
probabil că găsirea
numărului minim de identificare într-o clasă
nu este un
exercițiu teribil de interesant.
Dar poate că încerc să-l
găsesc pe studentul care a
fost cel mai mult timp la MIT.
Și așa ar fi o
euristică rezonabilă.
De fapt, nu am idee
dacă ID-urile studenților MIT
sunt atribuite liniar sau nu.
Dar, în orice caz, am putut găsi cea
mai mică cheie, cea mai mare
cheie și așa mai departe în setul meu.
Și toate acestea sunt
operațiuni rezonabile
de interogat, în care
obiectul meu este doar
un lucru care stochează o mulțime de
entități diferite în interiorul său.
Acum, această descriere aici -
observați că am etichetat
asta ca o interfață setată.
Aceasta nu este o
structură de date setată.
Și modul de a-ți aminti asta
este că nu ți-am spus cum
am implementat de fapt asta.
Nu v-am spus că voi avea în
culise
o serie de informații
și voi căuta în interiorul ei,
și așa voi
implementa găsirea min sau găsirea maximă
cu o buclă for sau orice altceva.
Tot ce vă spun este
că un set este un lucru care
implementează aceste operațiuni.
Și în culise,
computerul meu face ceea ce face.
Acum, ar putea suna abstract.
Dar este mai mult sau
mai puțin ceea ce faceți voi
atunci când scrieți cod în Python.
Cred că în Python
ceea ce numim
un set este poate un dicționar.
Sunt un programator Matlab.
Îmi pare rău.
Sunt un
tip de analiză numerică.
Dar, în esență, unul
dintre lucrurile frumoase
despre codificare în aceste
limbaje de programare de nivel înalt
este că au grijă
de aceste detalii urâte.
Și ceea ce ai
rămas este doar
interfața de nivel înalt
cu acest obiect de
care ai nevoie la
sfârșitul zilei.
Deci, desigur, în
prelegerea de astăzi, acum că ne-am stabilit
obiectivul, care este să completăm...
dacă aș vrea să scriu cod
pentru un set, cum aș putea să o fac?
Acum, desigur, scopul nostru este să
oferim diferite structuri de date
care le implementează
și apoi să le înțelegem
în ceea ce privește eficiența lor,
stocarea datelor, corectitudinea,
toate acele lucruri bune.
Așa că înainte de a intra în
toate aceste detalii urâte,
permiteți-mă să mă opresc pentru o secundă.
Există întrebări
despre această interfață de bază?  Ar
trebui să vă simțiți
liberi să mă opriți oricând,
pentru că va fi
plictisitor dacă nu
primiți primul diapozitiv sau două.
Da?
PUBLIC: Poți să
explici cum [INAUDIBIL]..
JUSTIN: Este o întrebare bună.
Deci întrebarea a
fost, ce
face exact această operație de inserare?  De
aceea, lucrul
la analogia
elevilor în această
clasă este unul rezonabil.
Deci voi construi un
obiect, care este un student.
Așa că în aceste note de prelegere,
cred că am fost consecvenți.
Am prins una sau două greșeli de scriere.  Ne
vom gândi la x
ca la obiectul care conține
toate informațiile.
Și apoi asociată
cu aceasta este o singură piesă,
care se numește cheia.
Acolo vom
folosi litera k.
Și asta este ca și actul tău de student.
Acesta este lucrul pe care îl voi
folosi pentru a căuta.
Deci, ce
face operațiunea de inserare
care ia
tot acest obiect student
x, care include ID-ul tău,
numele tău, numărul tău de telefon, toate
acele lucruri bune și
îl inserează în set,
înțelegând
că atunci când îmi caut setul,
sunt  o să
caute după cheie.
Așa că, când vreau să
găsesc un student,
trebuie să introduc numărul meu de identitate.
Are sens?
Misto.
Alte intrebari?
Grozav.
Fabulos.
BINE.
Deci, acum, să vorbim despre cum să
implementăm de fapt acest lucru.
Și, din fericire, suntem deja
echipați cu cel puțin o
modalitate foarte simplă prin care putem implementa
un set bazat pe ceea ce ați
văzut deja la
cursurile anterioare de programare sau chiar
doar în ultimele două prelegeri,
care este o modalitate de a înțelege
un  set sau să-l implementez
mai degrabă ar fi doar să stochez
o gamă uriașă de obiecte
care sunt în setul meu.
Presupun că continuând cu
tema ultimelor două prelegeri,
acesta nu este un spațiu
în memorie, ci mai degrabă
o matrice metaforică,
o matrice teoretică.
Dar nu prea contează.
Și așadar, o modalitate de a-
mi stoca setul ar
fi să stochez doar o grămadă de
x-uri în nicio ordine anume.
Are sens?
Deci am o bucată mare de memorie.
Fiecare bucată de
memorie este asociată
cu un
obiect diferit din setul meu.
Evident, acesta este
destul de ușor de construit.
Fac doar o matrice mare și
arunc totul acolo.
Și întrebarea este, este
aceasta
o modalitate deosebit de eficientă sau utilă de a
implementa un set?
Deci, de exemplu, să
spunem că
am un set de toți
elevii din această clasă.
Sunteți un
număr ridicol de voi.
Deci, de fapt,
eficiența asimptotică poate
contează puțin.
Și vreau să întreb dacă acest
student există în clasa mea?
Erik Demaine ia 6.006?
Răspunsul este nu, cred.
Predarea, luarea?  Nu
știu.
Dar, în orice caz,
cum îl implementez
dacă setul meu este neordonat?  Ne
vom gândi la
asta o secundă.
Da?
PUBLIC: [INAUDIBIL]
JUSTIN: Este de fapt o
sugestie interesantă,
care va anticipa
ceea ce se întâmplă mai târziu
în această prelegere, care a fost
de a sorta setul și apoi de
căutare binară.
Dar să spunem că de fapt
trebuie să fac asta o singură dată.
Din anumite motive, am construit
un întreg set de oameni
în această clasă.
Și vreau doar să știu,
Erik Demaine este în această clasă?
Deci, acel algoritm
ar dura n log n timp
pentru că trebuie să
sortez pe toți.
Și apoi trebuie să fac
căutare binară, care
poate fi log n timp.
Dar susțin că, dacă
singurul lucru la care îmi pasă
este să-mi construiesc întregul
set și să-l caut o dată,
există de fapt un
algoritm mai rapid.
Acest lucru va fi inutil de
confuz pentru că vom
vedea că acesta nu este într-adevăr
modul corect de implementare
în aproximativ 38 de secunde.
Da?
PUBLIC: [INAUDIBIL]
JUSTIN: Da.
Repetați de la început
la această matrice și spuneți,
tipul ăsta este Erik?
Nu.
Tipul acesta este Erik?
Nu.
Tipul acesta este Erik?
Da.
Și apoi înapoi.
Deci, în cel mai rău caz, cât va
dura acel algoritm?  Ei
bine, în cel mai rău caz
de ghinion,
instructorul tău se află
la sfârșitul listei.
Deci, în acest caz, ce va
însemna asta?
Asta înseamnă că trebuie să
merg de-a lungul întregii matrice
înainte să-l găsesc.
Deci acel algoritm
ia ordine n timp.
Și astfel
intuiția colegei dvs.
că cumva acest lucru
este destul de ineficient
este absolut corectă.
Dacă știu că va trebui să
caut în
matricea mea de multe, de multe ori
diferite persoane, atunci probabil că are
sens să
lucrez puțin înainte,
cum ar fi sortarea listei.
Și atunci interogarea mea este
mult mai eficientă.
Dar toate acestea sunt doar pentru a spune
că o matrice neordonată este
o modalitate perfect rezonabilă de a
implementa această interfață setată.
Și apoi căutarea în acea matrice
va dura timp liniar de
fiecare dată când caut.
Și, bineînțeles, dacă
coborîți lista
cu toate
operațiunile diferite pe care ați
dori să le faceți pe un set, veți vedea
că toate necesită timp liniar.
Deci, de exemplu, cum mă
construiesc?  Ei
bine, trebuie să rezerv
n sloturi în memorie.
Și cel puțin
conform modelului nostru
de calcul din această clasă,
acesta ia ordine n timp.
Apoi voi copia
totul în set.  În
mod similar, dacă vreau
să inserez sau să șterg,
ce trebuie să fac?  Ei
bine, trebuie să-mi rezerv
memorie, să bag ceva
înăuntru.
În cel mai rău caz, am văzut
acest argument de amortizare înainte,
dacă setul tău are voie
să crească dinamic.
Și, în sfârșit, dacă aș vrea
să găsesc codul minim de student
în sala mea de clasă,
singurul algoritm pe care îl
pot avea dacă lista mea
de studenți nu este sortată
este la ce?
Doar repetați fiecare
elev din clasă.
Și dacă tipul la
care mă uit
are un ID mai mic decât
cel pe care l-am găsit, înlocuiți-l.
Are
sens pentru toată lumea?
Deci, practic, tot ce puteți
face într-un set îl puteți implementa -
și cred că toți
sunteți mai mult decât
calificați să implementați -
ca o matrice neordonată.
Doar că va fi lent.
Da?
PUBLIC: [INAUDIBIL]
JUSTIN: Da, așa este.
Deci, de fapt, nu
știu la această clasă.
Presupun că interfața
și modul în care am
descris-o aici sunt dinamice.
Putem continua să
adăugăm lucruri la el.
În acest caz, amintiți-vă că
acest argument amortizat
din prelegerea lui Erik
spune că, în medie,
va dura n timp.
PUBLIC: [INAUDIBIL]
JUSTIN: Ce a fost asta?
PUBLIC: [INAUDIBIL]
JUSTIN: Oh, este adevărat.
Asta e chiar mai bine... îmi pare rău.
Chiar dacă nu ar fi dinamic.
Dacă aș vrea să înlocuiesc
o cheie existentă...
ca, dintr-un motiv oarecare, doi
studenți aveau același ID.
Aceasta este o analogie teribilă.
Îmi pare rău.
Dar, în orice caz, dacă aș
vrea să înlocuiesc
un obiect cu unul nou,
ei bine, ce ar trebui să fac?
Ar trebui să caut

mai întâi acel obiect și apoi să-l înlocuiesc.
Și această căutare va lua
ordine de n timp din argumentul nostru
de mai înainte.
Mulțumesc.
BINE.
Deci, într-un anumit sens, am terminat.
Acum am implementat
interfața.
Viata e buna.
Și, desigur, aceasta
este diferența
dintre existență și
grija de detaliile din
interiorul acestui lucru.
Am arătat că se
poate implementa un set.
Dar nu este un
mod îngrozitor de eficient
de a face asta prin stocarea unei
liste
de numere dezorganizate, dezordonate, fără nicio ordine.
Deci, în loc de
asta, în mod convenabil,
colegul nostru din
primul rând de aici
a sugerat deja o
structură de date diferită,
care este să stocăm setul nostru nu doar
ca o matrice dezorganizată
în orice ordine arbitrară, ci
mai degrabă să păstrăm elementele
din setul nostru organizate după  cheie.
Deci, cu alte cuvinte, dacă
am această matrice a tuturor
elevilor
din sala noastră de clasă,
primul
element din matricea mea
va fi studentul
cu cel mai mic număr de identificare,
al doilea este al doilea
cel mai mic număr, până
la  sfârșitul
matricei, care
este studentul cu
cel mai mare număr de identificare.
Acum, asta înseamnă că
vreau să fac aritmetica
numerelor de identificare a studenților?
Absolut nu.
Dar este doar o modalitate de a
impune ordinea acelei liste,
astfel încât să o pot căuta
foarte repede mai târziu.
BINE.
Deci, dacă vreau să completez
interfața setată
și am cumva o
gamă sortată de studenți -
deci din nou, ei sunt organizați
după numărul de identificare al studentului -
atunci timpul meu de rulare începe să devină
puțin mai interesant.
Da.
Așa că acum, inserarea,
ștergerea ar dura în continuare
aceeași perioadă de timp.
Dar să spunem că
vreau să găsesc
studentul cu numărul minim de identificare
, această funcție find min.  Ei
bine, cum aș putea să
o fac într-o matrice sortată?
Cuvântul cheie este sortat aici.
Unde este
elementul min al unui tablou?
Da?
PUBLIC: [INAUDIBIL]
JUSTIN: Da.
De fapt, pot oferi un
algoritm moderat mai rapid, care
este doar uitați-vă la primul.
Dacă vreau elementul minim
al unei matrice și matricea
este în ordine sortată, știu că acesta
este primul lucru.
Deci este ordinea 1 dată pentru a
răspunde la acest tip de întrebare.
Și la fel, dacă vreau
chestia cu cel mai mare
număr de identificare, mă uit până la
capăt.
Acum, în 6.006,
numerele de la cursurile studenților MIT
sunt foarte confuze pentru mine.
În 6.0001, 6.042,
băieți,
cred că ați învățat deja
despre căutarea binară
și chiar este posibil să fi
implementat-o.
Deci ce știm?
Dacă matricea mea este sortată,
cât timp
îmi ia pentru a căuta un
anumit element?
Da?
PUBLIC: Log n timp.
JUSTIN: Înregistrează-te în timp.
Este absolut corect pentru că
îmi pot tăia matricea în jumătate.
Dacă cheia mea este mai mare
sau mai mică, atunci mă
uit în stânga sau în dreapta.
Și deci acesta este un
mijloc mult mai eficient
de a căuta un set.
Deci, în special, 6.006
anul acesta are 400 de studenți.
Poate anul viitor are 4.000.
Și în cele din urmă, va
avea miliarde.
Atunci ce se va întâmpla?  Ei
bine, dacă îmi folosesc
matricea neordonată
și am un miliard de
studenți în această clasă,
ce se va întâmpla?  Ei
bine, atunci îmi va lua
aproximativ un miliard de calcule
pentru a găsi un
student la acest curs,
în timp ce log de un miliard
este mult mai rapid.
Pe de altă parte, am
măturat sub covor
aici, care este cum
obțin de fapt
o matrice sortată pentru început.
Și ceea ce vom
vedea în prelegerea de astăzi
este că asta necesită mai mult
timp decât construirea dacă am doar
o listă dezorganizată.
Construirea unei
liste dezorganizate este un lucru ușor de făcut.
Probabil că toți o faceți acasă
când faceți curățenie.
Dar, de fapt, sortarea
unei liste de numere
necesită puțin mai multă muncă.
Și deci acesta este un
exemplu grozav în care există cel puțin
o cantitate mică de compromis.
Acum, construirea matricei mele sortate
pentru a reprezenta setul meu
va necesita un
pic mai mult de calcul.
Vom vedea că este
timpul.
Dar apoi, odată ce am
făcut acel pas 0,
acum multe dintre aceste
alte operații la
care îmi
pasă de obicei într-un set,
cum ar fi căutarea
unei chei date,
vor merge mult
mai rapid folosind căutarea binară.
Deci acesta este motivatorul nostru de bază
aici.
Și așa că acum, am văzut
interfața de configurare și două
structuri de date potențiale.
Iar scopul nostru pentru
ziua respectivă va
fi să completăm
detaliile celei de-a doua.
Și din moment ce cu toții ați
văzut deja căutarea binară,
probabil că ați
văzut deja și sortarea.
Dar, în orice caz,
astăzi, ne vom
concentra mai ales pe
pătratul din stânga jos
, despre cum să iau
o listă dezorganizată de obiecte
și să o pun în ordine, astfel
încât să o pot căuta mai târziu.
Deci, cu alte cuvinte, marea noastră
problemă pentru prelegerea de astăzi
este al doilea lucru
aici, această sortare.
De altfel, în
următoarele două prelegeri,
vom vedea alte
seturi de date-- sau
structuri de date, mai degrabă.
Ne pare rău, seturi de date.
Obișnuiam să predau
cursuri de învățare automată.
Și vom vedea că au
diferite operațiuni de eficiență pe
care le putem completa în acest tabel.  Deci
încă nu am terminat.
Dar acesta este un pas înainte.
BINE.
Deci, sper că am
justificat ad nauseum
de ce s-ar putea dori să
rezolvăm lucrurile.
Și într-adevăr, există
câteva cuvinte din vocabular
care merită remarcate.
Așadar, unul, deci amintiți-vă că
algoritmul dvs. de sortare
este destul de simplu în ceea ce privește
modul în care îl specificați.
Deci, în sortare, intrarea dvs.
este o matrice de n numere.
Presupun că de fapt ar

trebui să ne gândim la ele ca la chei.
Nu va
conta foarte mult.
Iar rezultatul nostru --
sunt întotdeauna foarte
îngrijorat că, dacă
scriu pe tablă de pe
spate, trebuie să o acoper --
va fi sortat.
Și îl vom numi
B. Pe acesta îl vom numi
A. Această clasă
nu este optimizată pentru oameni scunzi.
Deci, există o mulțime de variații cu privire
la problema de sortare de bază
și la diferiții
algoritmi care există.
Două cuvinte din vocabular se vor
evidenția foarte repede -
unul este dacă sortarea dvs.
este distructivă, ceea ce
înseamnă că, în loc să
rezerv o memorie nouă
pentru matricea mea sortată B și apoi
să pun o versiune sortată a lui A
în B, un algoritm distructiv
este  unul care doar suprascrie A
cu o versiune sortată a lui A.
Cu siguranță interfața C++
face asta.
Presupun că și cel Python o
face.
Uit mereu acest detaliu.
Pe lângă
sortările distructive,
există unele tipuri, ceea ce
înseamnă că nu numai că sunt
distructive, dar
nici nu folosesc memorie suplimentară
în procesul de sortare.
Într-adevăr, ți-ai putea imagina
un algoritm de sortare
care trebuie să-și rezerve o grămadă de
spațiu de lucru pentru a-și face treaba
și apoi să-l pună înapoi în A.
De exemplu,
cea mai proastă sortare distructivă din lume
ar putea fi să-ți numești
non-distructiv
și apoi să-l copiezi.  înapoi
în A. Dar asta ar
necesita ordine n spațiu pentru a face.
Deci, dacă algoritmul meu
are în plus
proprietatea că nu
rezervă spațiu suplimentar,
cel puțin până la o constantă,
atunci numim asta în loc.
BINE.
Deci acestea sunt cuvintele noastre de bază ale
vocabularului.
Și sunt modalități de a
înțelege diferențele
dintre diferiții
algoritmi de sortare.
Da?
PUBLIC: [INAUDIBIL]
JUSTIN: De ce ajung să
folosească spațiu suplimentar O(1)?
Da, sigur.  De
fiecare dată când fac doar
o variabilă temporară,
cum ar fi un contor de buclă,
aceasta va
conta pentru acea ordine 1.
Dar lucrul important este că
numărul de variabile de care am nevoie
nu se scalează în
lungimea listei.
BINE.
Așa că vă prezint
începutul și sfârșitul
prelegerii noastre de sortare, care
este cel mai simplu algoritm de sortare din lume
.
Eu o numesc sortare permutată.
Cred că este foarte ușor
să dovedești corectitudinea
pentru această tehnică specială.
Deci, în
felul de permutare, ce pot face?  Ei
bine, știu că dacă am o
intrare care este o listă de numere,
există o permutare
a acelei liste de numere care
este sortată după definiție,
deoarece o sortare este
o permutare a
listei tale originale.
Deci, ce este un
algoritm de sortare foarte simplu?  Ei
bine, enumerați fiecare
permutare posibilă
și apoi verificați
care este în ordinea corectă.
Deci, există două piese cheie pentru
această tehnică specială,
dacă vrem să o analizăm.
Nu văd un motiv pentru care să
o chinui prea mult.
Dar una este că trebuie să
enumerăm permutările.
Acum, dacă am o
listă de n numere,
câte permutări diferite
de n numere există?
Da?
PUBLIC: n factorial.
JUSTIN: n factorial.
Deci, doar în virtutea numelui
funcției acestei permutări,
știu că suport cel
puțin n timp factorial.
S-ar putea să fie mai rău.  S-ar putea ca, de
fapt,
listarea permutărilor să dureze
mult timp dintr-un anumit
motiv, așa cum fiecare permutare
în sine are ordine n timp.
Dar cel puțin,
fiecare dintre aceste lucruri
arată ca n factorial.
Te-am avertizat că
scrisul meu de mână este groaznic.
Deci asta face chestia asta cu omega
, dacă îmi amintesc bine.
Și apoi, în al doilea rând, ei
bine,
trebuie să verificăm dacă acea
permutare anume este sortată.
Cum vom face asta?
Există o modalitate foarte simplă de a
verifica dacă o listă este sortată.  O să
fac poate pentru
i egal cu 1 la n minus 1.
Observați că nu este un codificator Python.
O să arate diferit.
Apoi verificați, este Bi mai mic
sau egal cu Bi plus 1?
Și deci, dacă această relație
este adevărată pentru fiecare i--
ar trebui să
fie un semn de întrebare.
Aceasta a fost mai mică sau egală
cu un semn de întrebare deasupra.
Aici este notația mea specială.
Deci, dacă ajung până la
sfârșitul acestei bucle for
și acest lucru este adevărat peste tot,
atunci lista mea este sortată
și viața este bună.
Deci, cât
durează acest algoritm?
Ei bine,
te holbează drept în față
pentru că ai
un algoritm, care
face buclă de la 1 la n minus 1.
Deci, acest pas implică ordine n
timp pentru că theta de n timp
pentru că trebuie să meargă
până la sfârșitul  listă.
Așa că, când am pus aceste lucruri
împreună, sortarea permutărilor...
Ei bine, amintiți-vă că această
verificare dacă este sortată are loc
pentru fiecare permutare.
Deci, la sfârșitul
zilei, algoritmul nostru
ia cel puțin n
ori factorial n timp.
Este un
exemplu grozav de ceva
care este chiar mai rău decât
factorial n, care
cumva în mintea mea este ca cel
mai prost algoritm posibil.
Deci, credeți că Python
implementează sortarea permutării?  Cu
siguranță sper că nu.
Da?
PUBLIC: [INAUDIBIL]
JUSTIN: Corect.
Deci întrebarea a fost, de ce
este omega și nu mare O?
Ceea ce este o
întrebare fabuloasă în acest curs.
Deci iată problema de bază.
Nu ți-am dat
un algoritm pentru cum
să calculezi setul
de permutări
pentru o listă de numere.
Tocmai am numit o
funcție magică pe care am inventat-o.
Dar știu că acel algoritm
durează cel puțin n timp factorial
într-un anumit sens.
Sau, dacă nimic altceva,
lista de permutări
este n factorială
mare, deoarece asta este
tot ce trebuie să calculeze.
Deci nu ți-am spus cum să
rezolvi această problemă.
Dar sunt convins că este cel
puțin această perioadă de timp.
Deci, amintiți-vă că omega
înseamnă limita inferioară.
Deci, când le-am pus pe toate cap
la cap, într-un anumit sens...
OK, acest lucru nu este
satisfăcător în sensul
că nu v-am dat exact timpul de
rulare al acestui algoritm.
Dar sper ca te-am convins
ca este super inutil.
Da, OK.
Alte întrebări despre asta?
Dar grozav.
Deci, dacă ne întoarcem la
tabelul nostru pentru interfața setată,
ei bine, într-un anumit sens,
dacă am implementat-
o ​​folosind acest algoritm prost,
atunci intrarea din stânga jos
din tabelul nostru ar
fi n ori factorial
n, ceea ce nu ar fi atât de fierbinte  .
Dar observați că, de fapt, toate
restul operațiunilor noastre
sunt acum destul de eficiente.
Pot folosi căutarea binară.
Tocmai am obținut
algoritmul care--
mai degrabă, am obținut
matricea sortată într-un mod amuzant.
BINE.
Deci, să completăm niște
algoritmi mai interesanți.
Ca de obicei, vorbesc prea mult.
Și sunt nervos în privința timpului.
Dar putem sări peste unul
dintre ele dacă avem nevoie.
Deci câți dintre noi au mai
văzut sortarea selecției?
Văd mâna ta.
Dar o să
amânăm puțin.
Îmi pare rău?
PUBLIC: [INAUDIBIL]
JUSTIN: E fabulos.
De ce nu amânăm până
la sfârșitul prelegerii?
Și o vom face atunci.
BINE.
Deci, primul algoritm despre care vom
vorbi pentru sortare,
care este oarecum
sensibil, este ceva
numit sortare prin selecție.
Sortarea selecției este exact
ceea ce sună.
Deci, să presupunem că avem o
listă de... hopa, laptopul meu
și ecranul nu sunt de acord.
BINE.
Să presupunem că am o
listă de numere--
8, 2, 4, 9, 3.
Există un mesaj
pe care Jason cred că mi-l
trimite în
notele de curs.
Dar nu mi-am dat seama.
Dar, în orice caz, vreau să
sortez această listă de numere.
Iată un algoritm simplu
pentru cum să o fac,
adică pot găsi cel mai mare
număr din toată această listă
și îl pot lipi la sfârșit.
Deci, în acest caz, care este cel
mai mare număr
din această listă pentru toată lumea?
9.
Bine.
Vezi, de asta mergi la MIT.
Așa că o să iau acel 9. Îl
găsesc.
Și apoi schimbă-l cu
3, care este la sfârșit.
Și acum, care este
ipoteza mea inductivă?
Ei bine, într-un anumit sens,
totul
în dreapta acestei mici
linii roșii pe care am trasat-o aici
este în ordine, în acest caz,
pentru că există un singur lucru.
Deci acum, ce am de gând să fac?
Mă voi uita în
stânga liniei roșii, voi
găsi următorul lucru cel mai mare.
Ce-i asta?
Haide.
PUBLIC: 8.
JUSTIN: Iată-ne.
Da, trezește-te.
BINE.
Deci, corect, următorul cel
mai mare este 8.
Așa că îl vom schimba
cu 3, îl vom pune la sfârșit
și așa mai departe.
Cred că ați putea
termina asta cu toții.
Presupun că ar trebui să existe o
ultimă linie aici în care totul
este verde și suntem fericiți.
Dar, într-un anumit sens, suntem destul de
siguri că o matrice de un articol
este în ordine sortată.
Și, în esență, de la un
nivel înalt, ce face sortarea de selecție
?
Ei bine, a continuat să aleagă
elementul care era cel mai mare
și l-a schimbat în
spate și apoi a repetat.
Acum, în 6.006, vom
scrie sortarea selecției într-un mod cu
care s-ar putea să nu
fiți familiarizat.
Într-un anumit sens, acest lucru nu este
atât de greu de implementat cu două
bucle for.
Cred că ați putea
face asta acasă.
De fapt, s-ar putea să ai deja.
Dar în această clasă,
pentru că ne preocupă să
dovedim corectitudinea, să
dovedim eficiența,
toate acele lucruri bune, o vom
scrie
într-un fel amuzant,
care este recursiv.
Acum, nu pot sublinia
suficient de puternic cât de puțin ar
trebui să implementați acest lucru acasă.
Aceasta este în mare parte o
versiune teoretică a sortării de selecție,
mai degrabă decât una pe care
ați
dori să o scrieți în cod,
deoarece există, evident,
o modalitate mult mai bună de a face acest lucru.
Și vei vedea asta în
recitarea ta săptămâna aceasta,
cred.
Dar în ceea ce privește
analiza, există
o modalitate drăguță și ușoară
de a o nota.
Deci vom lua
algoritmul de sortare a selecției.
Și
o vom împărți în două bucăți.
Una dintre ele este să mă găsești cel
mai mare lucru din primele k
elemente ale matricei mele.
Nu ar trebui să folosesc k
pentru că înseamnă cheie.
Primele i elemente
ale matricei mele.
Iar următorul este
să-l schimbi la loc
și apoi să sortezi
totul la stânga.
Acestea sunt cele două piese de aici.
Deci hai să scriem asta.
Deci ce am făcut?
Ei bine, într-un anumit sens, la
pasul 1 aici, am
găsit cel mai mare cu indice
mai mic sau egal cu i.
Așa că am început de la sfârșitul
listei și apoi m-am mutat înapoi.
Și apoi pasul 2 a fost să
schimb asta în locul.
Observați când spun
schimb, de exemplu,
când am pus 8
acolo, ei bine, a trebuit să
fac ceva cu acel 3.
Așa că l-am pus acolo unde era
8.
Și apoi, în sfârșit, ei
bine, am terminat?
Nu, am pus cel mai mare
lucru la sfârșitul matricei mele.
Așa că acum, trebuie să sortez
de la indicele 1 la i minus 1
pentru că acum știu că
ultimul tip este în ordine sortată.
Te văd.  Îți voi
preda
în doar o secundă.
Da?
PUBLIC: [INAUDIBIL]
JUSTIN: Nu poți
citi scrisul de mână?
PUBLIC: [INAUDIBIL]
JUSTIN: Acesta este un indice
mai mic sau egal cu i.
Mare întrebare.
Te-am avertizat.
Va fi o problemă.
Deci, să facem mai întâi pasul 1.
Așa că o să pun
cod pe placă.
Și apoi vom
completa detaliile.
Erik postează pe Facebook.
Voi dezactiva această
funcție pe ceas mai târziu.
Deci, corect, să implementăm
această funcție de ajutor aici.
Acesta este ceva pe care îl vom
numi prefixul max.
Și asta
mă va găsi cel mai mare
element de matrice între
indexul 0 și indexul i inclusiv,
cred.
Da?
PUBLIC: [INAUDIBIL]
JUSTIN: Ei bine, iată o
observație interesantă,
într-adevăr una profundă, și anume
că cel mai mare element de la 0
la i--
este un i, îmi pare rău.
Sunt două cazuri.
Fie este la indexul i,
adică am primele 10
elemente din dreapta mea -
fie este elementul numărul
10, fie care este celălalt caz?
Nu este, da?
Cu alte cuvinte,
are un indice mai mic decât i.
Aceasta este o tautologie, rata?
Ori cel mai mare lucru este
la acest index, ori nu este.
În acest caz, trebuie
să fie la stânga.
Are sens?
Deci, acest lucru ne oferă un
algoritm foarte simplu
pentru găsirea celui mai mare element
din tabloul dintre indexul 0
și indexul i, ceea ce v-am
arătat pe ecran aici.  L-
aș scrie pe tablă.
Dar sunt un scriitor lent
și deja la timp.
Și, în esență,
ce am implementat?
Ei bine, am găsit cel mai mare
element între indicele 0
și indicele i minus 1.
Deci, să spunem că
am o matrice -- Am
uitat
succesiunea de numere --
8, 3, 5, 7, 9.
Asta o să facă.
Și așa cum dau un
indiciu aici, care este i.
Și primul
lucru pe care îl fac
este să calculez cel mai mare
număr din stânga
acestor lucruri.
In acest caz, adica?
PUBLIC: 8.
JUSTIN: 8.
Iată-ne.
Acum, mă uit la ultimul
element al matricei mele, care este...
9.
Mă omorâți astăzi, băieți.
Si atunci ce sa ma intorc?  Ei
bine, vreau cel mai mare
între 0 și indicele i.
Deci, în acest caz, returnez 9.
Are sens?
Așa că știu că lui Jerry Cain
de la Stanford îi place
să vorbească despre
saltul recursiv de credință care se întâmplă.  Un
alt termen pentru
aceasta este inducția.
Deci vrem să demonstrăm că
algoritmul nostru funcționează.
Ei bine, ce trebuie să facem?
Trebuie să arătăm că atunci când
apelez această funcție,
îmi oferă maximul
matricei mele între indicele 0
și indicele i pentru tot i.
Deci, să facem poate această
dovadă inductivă cu puțină atenție.
Și apoi restul, vom fi
neglijenți.
Deci, cazul de bază este i egal cu 0.
Ei bine, în acest caz, există
un singur element în matricea mea.
Deci este destul de clar
că este maxim.
Și acum, trebuie să facem
pasul nostru inductiv, ceea ce
înseamnă că dacă numesc
prefixul max cu i minus 1,
chiar obținem maximul
matricei mele între 0
și indicele i minus 1.
Și atunci, într-adevăr, pot doar să mă
uit la  afirmația mea foarte profundă,
care este că fie obiectul meu
este la sfârșitul matricei,
fie nu este.
Și tocmai de asta
avem nevoie
pentru a justifica pasul inductiv.
În esență,
există două cazuri.
Fie cel mai mare element al
matricelor mele, fie ultimul, fie
nu este.
Deja, prin
ipoteza noastră inductivă,
am susținut că
codul nostru poate găsi
cel mai mare element între
indicele 0 și indicele i minus 1.
Așadar, atâta timp cât luăm maximul
acela și ultimul tip,
suntem în formă bună.
Deci aceasta este dovada noastră foarte informală
de corectitudine.
BINE.
Deci, acum, trebuie să justificăm
timpul de rulare pentru acest algoritm.
Și asta de fapt nu este
100% evident din felul în care am
scris-o aici.
Nu există buclă pentru.
Dar ce fac?  Ei
bine, într-un anumit sens,
dacă timpul meu de rulare
este o funcție s, ei
bine, în primul rând,
dacă matricea mea are
un element în ea, ei
bine, timpul meu de rulare ar putea
fi 7, ar putea fi 23.
Dar la sfârșitul zilei  ,
face un singur lucru.
Se întoarce doar eu.
Deci, cu alte cuvinte,
este teta de 1.
Acest lucru nu este îngrozitor de perspicace.
Dar ce mai știm?  Ei
bine, când îmi apelez funcția, o
apelez recursiv pe
un index mai mic.
Și apoi fac o
cantitate constantă de muncă.
Deci știu că s din n este
egal cu s din n minus 1
plus theta de 1.
Fac un pic de
calcul suplimentar pe deasupra.
Poate cineva să ghicească care va
fi această durată totală de rulare?
Da?
PUBLIC: [INAUDIBIL]
JUSTIN: Da, comanda nr.
Deci, să presupunem că emitem ipoteza
că acest lucru durează n timp.
Puteți vedea că pentru că la
pasul n numim n minus 1,
îl numim minus 2 și așa mai
departe, până la 1.
Dacă vrem să demonstrăm acest lucru,
unul dintre modalitățile prin care noi...
cred că, în  Teoria, băieți,
ați învățat în trecut--
și
o veți acoperi în recitare--
este o tehnică
numită substituție.
Ceea ce facem este că ne vom
uita la această relație.
Și vom emite ipoteza
că credem că s din n
poate arăta ceva ca
cn pentru o constantă c care
nu depinde de n.
Atunci tot ce trebuie să
facem este să verificăm
dacă acea relație
este în concordanță
cu ipoteza noastră inductivă
, sau mai degrabă
doar ca o funcție recursivă.
Și dacă este, atunci
suntem în formă bună.
Deci, în acest caz,
ei bine, ce știu?
Am ghicit că s
din n este theta din n.
În special, dacă mă conectez la
această relație recursivă
aici, în
partea stângă, voi obține cn.
În partea dreaptă, voi
obține c n minus 1
plus theta de 1.
Trebuie doar să ne asigurăm
că acesta este un semn egal OK.
Deci ce pot face?
Pot scădea cn
din ambele părți,
poate pune acel 1 pe
cealaltă parte aici.
Apoi obținem c este
egal cu I mare de 1.
c este, desigur, o constantă.
Deci suntem într-o formă bună.

Profesorul meu de algoritmi mi-a
spus să nu scriu niciodată un
semn de victorie la sfârșitul unei dovezi.
Trebuie să faci un pătrat.
Dar el nu este aici.
Deci acum, te văd.
Dar avem puțin timp.
Așa că îl vom păstra
pentru prelegere.
BINE.
Deci, dacă vrem să implementăm
algoritmul de sortare a selecției, ei bine,
ce facem?
Ei bine, ne vom gândi la
i ca la indexul acelei linii roșii
pe care ți-o arătam înainte.
Totul dincolo de I
este deja sortat.
Deci, în sortarea prin selecție,
primul lucru pe care îl voi face
este să găsesc elementul maxim
între 0 și i.
Și apoi o să-
l schimb la loc.
Deci aceasta este doar o
versiune de cod a tehnicii
despre care am vorbit deja.
Sper că acest lucru are sens.
Deci găsiți cel mai mare
element între 0 și indicele i.
Așa vom
numi j aici.
Îl schimb cu
cel din indexul i.
Acesta este pasul 2.
Și apoi pasul 3 este că mai
trebuie să sortez totul
în stânga indexului i și
acesta este apelul recursiv.
Deci, dacă vreau să
justific timpul de rulare
al acestei
tehnici, ei bine, acum să
numim asta t pentru timp.  Ei
bine, ce să fac?  Ei
bine, pentru unul, numesc
sortarea selecției cu indicele i minus 1.
Deci, aceasta implică un timp
care arată așa.
Dar o numesc și
funcție de prefix max.
Și cât timp
durează asta?
Asta necesită ordine n timp.
Deci, la sfârșitul zilei,
am o relație
care arată așa.
Are sens?
Deci, apropo, observați că
acest ordin n a
înghițit calculele de ordinul 1 pe care
a trebuit să le fac pentru a schimba și așa mai departe.
Așa că amintiți-vă, există această
relație drăguță, pe care
probabil ați învățat-o la
ora de combinatorie, și anume
că 1 plus 2 plus
punct, punct, punct plus n.
BINE.
Nu-mi amintesc niciodată
exact formula.
Dar sunt destul de sigur că
arată ca n pătrat.
Deci, pe baza acestui lucru
și aruncând o privire
la acest lucru recursiv, care,
în esență, face exact
asta--
n plus n minus 1 plus
n minus 2 și așa mai departe--
aș putea emite ipoteza că
acest lucru este într-adevăr de
ordine n pătrat.
Deci, dacă o să
fac asta, atunci din nou
dacă vreau să folosesc
aceeași tehnică pentru dovezi,
trebuie să conectez această
relație și apoi să
verific dacă este consecventă.
Așa că poate emetez că
t din n este egal cu cn pătrat.
În acest caz,
îl conectez aici.
Am cn pătrat egal
cu un semn de întrebare peste
cn minus 1 pătrat plus
O mare sau chiar theta n aici.
Deci, dacă extind
pătratul, observă că
voi obține
c ori n pătrat
plus o grămadă de lucruri liniare.
Acesta este într-adevăr cn pătrat-- Ar
trebui să fiu atent cu asta--
minus 2 cn plus c
plus theta de n.
Observați că există un cn pătrat
pe ambele părți ale acestei ecuații.
Ei pleacă.
Și ceea ce am rămas este
o formulă drăguță, consistentă,
că teta lui n este
egal cu 2 cn minus c.
Și într-adevăr, aceasta este
o expresie de ordin n.
Deci există ordine
în univers.
Viata e buna.
Da, aceasta este
metoda de înlocuire.
Și din nou, cred că o vei acoperi
mai mult în recitarea ta.
Deci ce am făcut?  Am
derivat
sortarea de selecție.
Am verificat dacă
rulează în timp n pătrat.
Și prin această strategie frumoasă,
inductivă,
știm că este corectă.
Deci viața este destul de bună.
Din păcate, v-am promis
pe diapozitive
că sortarea
durează cu adevărat n log n timp.
Și acesta este un
algoritm de ordine n pătrat.
Deci nu am terminat încă.
Sunt mult peste timp.
Așa că vom sări peste un
alt algoritm, care
se numește sortare prin inserție, care
rulează, de asemenea, la n timp.
În esență, sortarea prin inserare
rulează în ordine inversă.
Voi sorta
totul la stânga,
apoi voi insera un nou obiect,
în timp ce, în selecție, voi
alege
cel mai mare obiect
și apoi voi sorta
totul la stânga.
Dar vă las să
treceți peste asta acasă.  În
esență, este
același argument.
Și, în schimb, ar trebui să
trecem la un algoritm
care contează de fapt, care
este ceva numit sortare de îmbinare.
Câți dintre noi au
mai întâlnit sortarea de îmbinare?
Fabulos.
Bun.
Atunci am terminat.
Deci, să spunem că am o listă.
Acum, îi trimit un
mesaj înapoi lui Jason.  L-am
inventat aseară.
Deci am 7, 1,
5, 6, 2, 4, 9, 3.
Acesta nu este în ordine sortată.
Dar pot face o
observație foarte profundă, și
anume că fiecare număr
în sine este în ordine sortată
dacă mă gândesc la el ca la
o matrice de lungime 1.
Este cu adevărat profund, ca
deep learning deep.
Deci acum, ce pot face?  Ei
bine, aș putea lua fiecare pereche de
numere, aș putea desena o căsuță roșie.
Ei bine, acum,
nu mai sunt în ordine sortată în
interiorul
cutiilor roșii.
Așa că voi sorta în
interiorul fiecărei cutii.
În acest caz,
nu este prea interesant
pentru că sunt doar perechi.
Și acum, sunt în ordine
pentru că au spus că sunt.
Acum, voi continua să
dublez dimensiunea cutiilor mele.
Deci, acum, să presupunem că am o
cutie cu lungimea 4.
Ce știu despre
părțile din stânga și din dreapta
ale liniilor punctate de aici?
Pe cele două laturi ale
liniilor punctate,
matricea este în ordine sortată.
Există un 1 și apoi un 7.
Acestea sunt în
ordine sortată, 5 și 6.
Asta pentru că, în
pasul anterior, am sortat fiecare pereche.
Deci, când îmbin aceste
două părți,
am o informație suplimentară utilă
, și
anume că cele două
părți ale liniei punctate
sunt deja în ordine sortată.
Acesta va fi
pasul nostru inductiv de bază aici.
Deci, în acest caz,
îmbin cele două părți.
Primesc 1, 5, 6, 7
și 2, 3, 4, 9.
Apoi, în sfârșit, am pus aceste
două lucruri împreună.
Și trebuie să le sortez pe acestea două.
Trebuie să îmbin aceste
două liste sortate.
Dar sunt în ordine.
Și asta îmi va oferi un
mare avantaj pentru că... hopa,
mi-am pierdut creta.
Presupun că am spațiu
pe această tablă aici.
Oh nu.
Deci, dacă vreau să îmbinăm 1,
5, 6, 7 și 2, 3, 4, 9,
există o tehnică frumoasă și inteligentă pe
care o
putem face și care va
dura doar timp liniar.
Jason îmi spune că este
algoritmul cu două degete.
Cred că este o
analogie drăguță aici.
Deci iată cele două degete ale mele.  Vor
indica
sfârșitul listei.
Și voi construi
matricea îmbinată înapoi.
Deci câte elemente sunt
în matricea mea îmbinată, dacă
îmbin două lucruri cu lungimea 4?  Nu
vă pun
întrebări grele.
E 8, da?
4 plus 4.
8, da?
Deci ce știu?
Știu că matricea mea de îmbinare--
5, 6, 7-- are opt elemente.
Și acum, voi avea două
degete la sfârșitul matricei mele.
Pe care ar trebui să-l pun la
sfârșitul tipului fuzionat?
7 din 9?
PUBLIC: Cei 9
JUSTIN: Cei 9.
Corect, mulțumesc.
Așa că acum, îmi pot mișca
degetul de jos la stânga
pentru că l-am adăugat deja.
Observați că nu trebuie să mă
uit niciodată în stânga unde
se află degetul meu, deoarece sunt
deja în ordine sortată.
Acum ce ar trebui să
adaug, 4 sau 7?
PUBLIC: 7.
JUSTIN: 7.
Și așa mai departe, punct, punct, punct, da?
Deci asta va fi
ideea de bază a sortării de îmbinare.
Am de gând să iau
două liste sortate.
Și voi face o
nouă listă sortată, care
este de două ori mai lungă,
folosind două degete
și deplasându-mă de la
și înapoi.
Deci aceasta este intuiția de bază
aici.
Într-adevăr, există lista noastră sortată.
Mă stresează
că nu există opt.
Am nevoie de puterea lui 2.
Așa că cred că merge sort,
îl vom prezenta
într-un mod invers
față de cel precedent,
unde vă voi oferi
algoritmul de nivel înalt.
Și apoi, de fapt,
durerea de cap este acel pas de fuziune,
pentru care am patru minute.
Și îmi cer scuze pentru asta.
Deci, ce face sortarea fuziunii?  Ei
bine, calculează
un index c, care
este mijlocul matricei mele.
Și va face un
apel recursiv care este sortarea
din stânga, care este totul
între indexul A și indexul C.
Și apoi sortează totul din
dreapta, care este totul
de la indexul C la indexul B.
Știu că acest lucru este confuz
pentru că de obicei literele
apar în ordine.
Dar C, dacă te gândești că
reprezintă centru,
atunci are sens ca.
Iată matricea mea.  O să
aleg un
index chiar în mijloc.
Mi-am făcut un deserviciu
nefolosind o putere de 2.
Dar asta e în regulă.  Voi
spune mai întâi sortați totul
în stânga liniei punctate
.
Sortați totul în dreapta
liniei punctate secunde.
Acum, am două
liste sortate pe cele două
părți ale liniei punctate.
Și apoi îmi voi folosi cele două
degete pentru a le aduna.
Deci asta
implementează aici.
Vezi, sunt două
apeluri recursive -
sortează de la A la C, apoi
sortează de la C la B. Hopa, de
fapt nu am etichetat asta.
Deci, acesta este A, C, B. Și
apoi trebuie să numesc merge.
Acum, implementarea noastră
a merge-- ei
bine, putem face acest lucru și
într-un mod recursiv.
Dar personal, mi se pare
un pic complicat.
Am de gând să recunosc.
Dar aici este ideea de bază
, pe care acum mă grăbesc.
Așa că mă voi gândi la
degetul meu superior ca degetul i
și degetul inferior ca degetul j.
Are sens?
Deci am două liste sortate.
Deci poate așa.
Nu știu, 1, 3, 5, 7.
Și apoi am o
a doua listă sortată aici,
care este poate 2, 4,
6, 72, așa cum o face.
Apoi voi avea un
indicator ca acesta, care este i,
și un indicator
aici în jos, care este j.
Și scopul meu este să
construiesc o matrice A
cu o grămadă de elemente în ea.
Și modul în care o voi
face este că voi
folosi exact același
tip de argument recursiv,
că pot fie ca cel
mai mare element al meu
să fie ultimul element
al primului tip,
fie ultimul element
al  al doilea.
Deci, aici va fi
apelul nostru recursiv.
Și în plus,
pentru comoditate, vom
avea un al treilea index, care este B,
care indică acest lucru din
interiorul matricei mele sortate pe care îl
procesez în prezent. Da?  O să
înceapă
de la A, mergi la B.
De altfel,
văd o mulțime de oameni care
fac fotografii cu diapozitivele.
Acestea sunt doar copii
lipite din note.
BINE.
Deci, în acest caz, ce ar trebui să
pun în B pentru cele două matrice ale mele?
am 1, 3, 5, 7;  2, 4, 6, 72.
72, da?
Grozav.
Deci acum, ce am de gând să fac?
Voi apela doar
funcția de îmbinare.
Dar o să scad
B pentru că acum sunt
mulțumit de ultimul element.
Și în plus,
am să decremenez j
pentru că l-am folosit deja.
Și acesta este
apelul nostru recursiv aici.
Se spune, dacă j este
mai mic sau egal cu 0 -
deci, cu alte cuvinte,
am un element
de folosit într-una dintre
listele celeilalte.
Și poate cel din stânga este
mai mare decât cel din dreapta.
Acesta este primul nostru caz.
Acest lucru nu se aplică
în acest exemplu de aici.  Ei
bine, atunci ar trebui să
fac ultimul element al lui
a din prima
listă și apoi să recurg
cu un element mai puțin
i și, în mod similar,
cazul invers pentru j.
Deci, dacă ne facem timpul de rulare
în două minute sau mai
puțin - cu mine băieți - ei
bine, ce va
face această funcție de îmbinare?  Ei
bine, într-un anumit sens,
există două ramuri.
Există o declarație if
cu două bucăți.
Dar ambele
piese se unesc
cu o piesă mai puțin în el.
Deci, într-un anumit sens, avem s
de n egal cu s de n minus 1
plus theta de 1,
ceea ce știm deja
din demonstrația noastră anterioară
înseamnă că s din n
este egal cu theta lui n.
Deci, cu alte cuvinte, este
nevoie de timp liniar pentru a fuziona.
Are sens intuitiv
pentru că, în esență,
atingeți fiecare
dintre aceste lucruri
o dată cu cele două degete.
Și acum, probabil cea mai
grea parte
a prelegerii, pentru care am
lăsat zero timp,
este derivarea timpului de rulare pentru
algoritmul real de sortare de îmbinare.
Și cum arată asta?  Ei
bine, acesta este puțin mai
complicat pentru că, desigur,
numesc
algoritmul de sortare de îmbinare de două ori, de fiecare dată
pe o listă care are jumătate din dimensiune.
În această clasă, vom
presupune că lista noastră este întotdeauna
o putere de 2 în lungime.
În caz contrar, această analiză
este un pic mai mult
o durere de cap.
Deci, în primul rând,
cât timp
durează sortarea unei
matrice de lungime 1?
Nu am de gând să
pun întrebări grele.
Toata lumea?
Da, este doar 1, nu?
Pentru că nu e nimic de făcut.
O matrice cu lungimea 1 are
un element și este sortată.
Este, de asemenea, cel mai mare element
și cel mai mic element.
Și acum, ce
face algoritmul nostru?  Ei
bine, face două
apeluri recursive
pe liste care au
jumătate din lungime.
Și apoi numește
acea funcție de îmbinare.
Și știm că
funcția de îmbinare ia teta de n timp.
Are sens?  Așa
că un lucru pe care l-am putea face,
pentru că avem o anumită intuiție
din cursul tău 6042
, este că
credem că acest lucru este ordine
n log n deoarece face cele două
apeluri recursive.
Și apoi le pune împreună.
Și să verificăm de două ori dacă acest lucru
este adevărat foarte rapid folosind
metoda de înlocuire.
Deci, în special, în
partea stângă
aici, poate am cn log n.
Acum, am 2 c.  Ei
bine, trebuie să pun un n peste
2 log n peste 2 plus theta de n.
Și vreau să verific dacă
această expresie este consecventă.  Am
cam un
picior în care să o fac.
Amintește-ți... să vedem.
Dacă folosim identitățile noastre preferate
din
clasa de liceu pe care probabil le-ați
uitat, amintiți-vă
că jurnalul de 2 lucruri
împărțite unul de celălalt
este diferența de jurnalele.
Deci acesta este într-adevăr 2.
OK.
2 împărțit la 2 este 1.
Deci acesta este de c ori de n ori log
n minus log de 2 plus theta n.  Am
epuizat deja timpul.
Dar observați că există un c n
log n în partea dreaptă.
Există un c n log n
în partea stângă.
Deci acele două lucruri dispar.
Și cu ce voi
rămâne?
Voi rămâne cu
theta de n egal cu cn log de 2.
Observați că c și log
2 sunt ambele constante.
Avem un eveniment theta
în partea stângă.
Deci există ordine
în univers.
Și ne-am derivat timpul de rulare.
Așa că știu că mă odihnesc
puțin prin sortarea îmbinării.
Sunt sigur că Erik și Jason o
pot revizui puțin
data viitoare.
Dar cu asta, ne
vedem, ce?
Joi și vineri.
Și a fost o plăcere
să vorbesc cu voi toți.