[SCRÂȘIT]
[FOSȘIT]
[CLIC]
ERIK DEMAINE: Bine.
Bine ați venit la exersarea
sesiunii de probleme 3, 006.
Astăzi, vom trece
printr-o grămadă de probleme,
pe care ar trebui să le aveți deja.
Mă gândeam să omit
chiar prima problemă,
pentru că este doar
o chestie mecanică.
Dacă avem timp la sfârșit,
putem reveni la el.
Dar nu există nicio
perspectivă pe care să ți-o pot oferi despre cum să
abordezi această problemă.
Doar,
înțelegi hashingul?
Așa că vreau să intru
mai întâi în problemele mai creative.  Să
începem cu problema
3.2, secvența hash.
Așa că o voi citi doar.
Și apoi prima noastră sarcină este
să transformăm problema cuvântului
într-un lucru concis de algoritmi formali pe care
trebuie să îl realizăm.
Apoi trebuie să venim cu
idei despre cum să o atingem.
Și trebuie să
verificăm detaliile.
Acesta va fi tiparul nostru general.
Deci această problemă
spune că tabelele hash
nu sunt utile doar pentru
implementarea operațiunilor de set, ci
pot fi folosite și
pentru a implementa secvențe.
Amintiți-vă, din cursul 2,
avem o interfață setată,
care se referă la interogarea
elementelor după cheia lor
și un fel de
ordine intrinsecă care se
referă la elementele în sine,
față de o
interfață de secvență cu care am
început, cu liste legate
și așa mai departe, și matrice,
unde ni se dă un ordin
și vrem să
menținem acea ordine.
Și este posibil ca această comandă să
nu aibă nimic
de-a face cu articolele în sine.
Deci asta numim
o ordine extrinsecă.  Ni se
spune care
este ordinea spunând:
inserați acest articol după acesta
sau adăugați-l pe acesta la sfârșit
sau adăugați-l înaintea începutului.
Deci, în prelegerea de săptămâna trecută, am
văzut seturi de implementare a tabelelor hash.
Și permiteți-mi doar să vă reamintesc
câteva lucruri pe care le pot face.
Deci avem, pe de o
parte, setat hashingul.
Deci vom avea
nevoie de asta într-o clipă.
Acesta este doar un
memento de la prelegere.
Putem construi unul în
timpul liniar așteptat.
Putem găsi un articol în
timp constant așteptat prin cheie.
Și putem insera
sau șterge un articol
în stare constantă amortizată.
OK, deci aceasta este o
cutie neagră pe care ni s-a oferit.
Și declarația problemei
spune că, imaginați-vă că vi se
oferă un tabel hash
ca o cutie neagră, ceea ce
înseamnă că oferim un lucru
care se comportă exact ca...
mulțumesc, 2. Ni
se oferă ceva
care este un tabel hash.  .
Dar este o cutie neagră în
sensul în care nu avem
voie să intrăm și să schimbăm
detaliile de implementare.  Ar
trebui să-l folosim așa cum este,
doar apelând interfața.
Deci, în special,
oferim aceste trei operațiuni.
Poate voi folosi și iter pentru a
itera elementele.
Așa că avem voie să construim
ceva în timp liniar, să
găsim și să inserăm și să ștergem în mod
constant amortizat așteptat.
Și
problema este
să construim din
această structură de date
o secvență cu un
echilibru de timp special.
Deci, aceasta este ceea ce numim
o reducere în sensul că vom
converti -
cred că din punct de vedere tehnic,
reducem problema secvenței
la problema setului,
pentru că
arătăm cum să rezolvăm
problema secvenței folosind
problema setului.
Dar modul în care ne vom gândi la
asta este în altă direcție.
Ni se oferă o
structură de date care rezolvă set.
Și
îl vom converti într-o structură de date care
rezolvă secvența.
Așa că, având în vedere că deja știm
cum să facem asta din prelegere,
vom învăța
cum să facem asta.
Acesta vă învață
lucruri noi într-un set de probleme.
Deci
limitele specifice pe care ni se
spune să le atingem sunt construirea
în timpul așteptat constant,
obținerea și set_at în
timp așteptat constant,
inserarea și ștergerea_at în
timpul așteptat liniar
și inserarea și ștergerea
primul și ultimul în--
rămânem fără  Cameră aici...
constant estimat amortizat.
BINE.
Așa că asta
ni se spune să facem.
Și acum începem să ne gândim.
Așa că ni se dă asta.
Vrem să construim asta.
Și așa o să vă spun
puțin despre procesul meu de gândire
.
Când mi se prezintă
o problemă ca aceasta,
primul lucru este
să citesc problema
și să văd, OK, care este
partea grea aici?
Care sunt provocările?
Deci, în mod clar,
trebuie să facem toate
aceste patru tipuri de operațiuni.
Construiți în timpul liniar așteptat --
practic, asta este tot ce am
văzut.
Obține sau set_at într-un
timp constant așteptat-- este rapid.
Și asta se simte cam
ca această operațiune de găsire.
Deci ambele par
destul de potrivite.
Așa că pare
o hartă bună.
Voi încerca să construiesc
aceste operațiuni folosind
acele operațiuni.
Inserați și ștergeți într-
o anumită locație
în timpul așteptat constant-- îmi
pare rău, timpul așteptat liniar--
este mare.
Timpul liniar așteptat înseamnă că
pot reconstrui întreaga
structură de date de fiecare dată când
fac o operație.
Deci acest lucru este ușor.
OK, acesta este primul
lucru de realizat.
Acesta este mare.
Grozav.
Deci nu trebuie să-mi fac
griji cu privire la aceste operațiuni.
Adică, trebuie
să le implementez.
Dar nu este greu să o fac atât de
repede, pentru că pot reconstrui.
Și apoi aici, inserați și ștergeți
la începutul și la sfârșitul
matricei, acestea sunt operațiunile DEQ,
Double-Ended Queue,
inserați și ștergeți la
fiecare capăt, în
timp amortizat constant așteptat.
Acesta, cred că
este unul complicat.
Ați văzut o modalitate de a
face acest lucru într-un set de probleme.
Dar acum vom
vedea un alt mod cu...
OK, celălalt lucru de observat
sunt aceste cuvinte „așteptate”.
În acest caz, ni se
spune să folosim hashing.
Dar cu multe probleme,
nu ți se spune cum să o rezolvi
sau pe ce ar trebui să te
bazezi.
Așadar, „așteptat” este
întotdeauna un cuvânt cheie bun,
deoarece înseamnă că
este implicată cumva randomizarea.
Dacă vi se spune că se va
aștepta limita,
probabil că trebuie să
utilizați randomizarea.
Și în această clasă, singura formă
de randomizare pe care o vei folosi
este, în esență, hashing.
Deci ăsta e un indiciu bun.
În acest caz, știm ce
ar trebui să folosim hashing.
Bine, deci asta va
fi provocarea.
Dar vreo idee despre cum am
putea rezolva această problemă?
Cum putem... să setăm, amintiți-vă,
fiecare articol are o cheie.
Într-o secvență, elementele
sunt doar elemente.
Și ni se spune să le
inserăm și să le ștergem
în anumite locații.
Dar nu au chei.
Așa că una dintre
provocări va
fi să ne luăm articolele
aici, să le dăm cheile
pentru a
le putea stoca într-un set.
În caz contrar, nu putem folosi find.
Dacă nu există chei
acolo,
nu există nicio modalitate de a căuta după cheie.
Idei?
Deci, să ne gândim la
ce vrem să facem.  Să
începem cu... așa că
construirea, cred, e bine.
Dacă doriți doar să
construiți o structură de date,
nu trebuie să faceți nimic.
Partea grea sunt
interogările sau actualizările pe care
doriți să le puteți face
asupra structurii dvs. de date.  Să
începem cu această
operație, get și set_at.
Așa că nu uitați, get_at,
vi se dă un index i
și doriți să găsiți
elementul în poziția i.
Și set_at, ni se
dă o poziție
și vrem să schimbăm
elementul stocat la acea poziție,
la acel index, adică.
Acum, aici,
ceea ce ni s-a dat,
putem introduce și șterge.
Dar tipul principal de căutare - să ne
gândim la get_la început.
O mapare naturală, având în vedere
această săgeată, este găsirea.
Find va căuta
un articol după cheie.
Așa că iată-- doar
uitându-mă la asta, să ne
uităm la toate
împerecherile posibile pe care le-ai putea face.
Avem găsirea prin cheie aici.
Și trebuie să implementăm
get_at prin index.
Deci, să facem cheile indicilor.
OK, deci aceasta este ideea numărul unu -
index - atribuiți o
cheie fiecărui element
egală cu indexul în secvență.
OK, atunci când fac--
pentru a implementa get_at,
pot doar apela
find of i dacă i este și o cheie.
Și asta ar trebui să-mi dea
lucrul pe care mi-l doresc.
Poate pentru ca asta să
aibă sens, lasă-mă să-
ți spun cum construiesc.
Deci, dacă mi se oferă, să zicem, o matrice
A de articole și sunt ambele --
singurul conflict de nume
aici este construirea.
Așa că permiteți-mi să numesc aceasta o
singură secvență de construcție.
Și îl voi implementa
folosind set build.
Și voi folosi o
notație scurtă aici.
Să presupunem că vreau să
fac un obiect care
are o cheie egală cu i și
o valoare egală cu A a lui i--
aceasta este notația mea de obiect--
pentru că i este egal cu 0, 1, până
la dimensiunea lui A minus 1.
Asta este puțin  cod asemănător,
dar nu chiar un cod literal.
Așa că voi
folosi asta doar pentru a spune, să
facem un obiect
care are două părți.
Una se numește cheia.
Deci putem vorbi despre
object.key, ca să putem...
ce seturi vor să facă.
Și vom stoca, de asemenea, o
valoare, care este elementul real pe
care ni l-am dat.
Deci sunt doar... pentru că acestea
sunt date în secvență,
reprezint doar
ordinea secvenței,
atribuind i să fie cheia.
Și așa că acum, dacă vreau să
găsesc elementul la indexul i,
pot găsi i.
Și din punct de vedere tehnic,
probabil că ar trebui să fac .value.
Asta îmi va oferi
articolul real
care este stocat în acea poziție.
Când voi găsi de i,
voi obține tot acest obiect
cu cheia lui i.
Și apoi vreau să obțin
partea de valoare a ei.
Deci set_at,
pot folosi doar această
operație de căutare pentru a obține
obiectul și a-i seta valoarea la x.
Bum.
Am implementat semantică asemănătoare matricei
, get_at i
și set_at i, folosind un set.
Dacă ați
programat vreodată în JavaScript,
acest lucru ar trebui să vă pară foarte familiar,
deoarece JavaScript implementează de fapt
matrice, cel puțin
la nivel conceptual, doar
ca tipuri de mapare generale
, care sunt --
le numesc obiecte, dar
sunt în principiu seturi.
Și este și mai groaznic.
Ei convertesc numerele întregi
în șiruri de caractere și apoi
indexează totul după
șiruri, semantic, oricum.
Detaliile de implementare
pot fi mai eficiente.
Dar conceptual,
asta este ceea ce se întâmplă.
Și asta este ideea pe care o
facem aici, care pare grozavă.
Ceva probleme?
Deci, să vedem.
Există insert_at și delete_at.
După cum am menționat,
ceea ce voi face
pentru aceste operațiuni este doar să
reconstruiesc întreaga structură.  O să
scriu doar pe scurt.
Practic, să
repetăm ​​toate elementele.
Repetați toate elementele, să
spunem, într-o matrice.
Inserați, ștergeți unul dintre ele.
Și apoi reconstruiește.
OK, și dacă aș
scrie un răspuns P set,
aș spune puțin
mai detaliat
ce vreau să spun în acest pas.
Am făcut-o în note.
Nu chiar atât de greu.
Dar ne putem permite
timpul liniar așteptat.
Îmi permit să
sun din nou la build.
Bănuiesc că, din punct de vedere tehnic,
numesc
această build, build secvență.
Așa că îmi pot permite doar să
extrag lucrurile într-o matrice, să
fac operația de timp liniară
pe matrice
cu deplasarea
și tot,
și apoi să apelez din nou la build.
Da, întrebare?
PUBLIC: Am avut o
întrebare despre get_at.
ERIK DEMAINE: Da.
PUBLIC: [INAUDIBIL] get_at.
ERIK DEMAINE: Îmi pare rău, nu.
Acestea sunt
definiții separate, da?
Scuze, s-au apropiat puțin.
PUBLIC: Oh.
ERIK DEMAINE: Deci aceasta este
definiția lui get_at.
Aceasta este definiția
construcției secvenței.
PUBLIC: Oh, înțeleg.
ERIK DEMAINE: Da.
Multumesc de intrebare.
OK, totul bine, da?
PUBLIC: Puteți explica
inserarea și ștergerea din nou?
ERIK DEMAINE: Explicați
inserarea și ștergerea.
OK, deci poate ar trebui să
notez unul dintre ele,
sau o să fac
o imagine, poate.
Deci avem această structură de date,
care este acum o structură de date secvență
, reprezintă
o secvență de elemente.
Și scopul meu este să spun,
șterge al-lea element.
Deci, există câteva elemente
aici, x0 până la xn minus 1.
Vreau să elimin xi
din secvență.
Sau cred că ar trebui să
o desenez așa.
Iese.
Deci, ceea ce voi face este să
extrag mai întâi toate elementele
din secvență.
Și nu am scris-
o, dar există
o interfață aici numită
iter, care îmi dă
toate elementele în ordine.
Așa că voi extrage
asta într-o secvență matrice.  Să
presupunem că voi construi doar
o matrice statică de dimensiunea n.
Am și o
operație de lungime care îmi spune
câte articole sunt aici.
Și operațiunea iter
îmi va oferi toate articolele în ordine.
Și așa voi pune în
matricea mea x0 și apoi x1
și așa mai departe, pe măsură ce ies.
Apoi ma duc in pozitia i.
Și vreau să șterg acel element
și să le schimb pe toate celelalte.
Acesta este plictisitor--
Cred că am spus chiar cum să facem
delete_at în matrice dinamice
în recitarea 2, destul de sigur.
Așa că doar immit asta.
Construiesc asta doar pentru a
obține noua ordine a lucrurilor.
Și apoi aplic,
prin operația de construire,
construiesc o
secvență complet nouă.
Și așa aș
implementa delete_at, într-un fel.
Există și alte moduri.
Da?
PUBLIC: Aveți
spațiu [INAUDIBIL] [INAUDIBIL],
sau...
ERIK DEMAINE: Cât
spațiu folosește?
Oh, problemă cu spațiul
dacă inserați--
dacă inserați,
probabil că
doriți să alocați o
matrice statică de dimensiune n plus 1.
Știți exact
ce se va întâmpla.
Deci, alocați un
pic mai mare.
Apoi poți face tura.  De
asemenea, puteți utiliza
matrice dinamice.
Dar atunci ai putea
obține o...
nu este o
legătură amortizată, pentru că faci doar o
singură inserție.
Ideea este că acest lucru
este foarte ușor.
Putem petrece timp liniar.
Deci putem reconstrui...
putem reconstrui această matrice de
trei ori dacă dorim.
Întrebare?
PUBLIC: Ce se întâmplă dacă
nu ți s-ar permite
spațiu extern non-constant?
ERIK DEMAINE: Huh.  Mă
vei arunca
și vei deschide problema.
Ce se întâmplă dacă ai doar
spațiu suplimentar constant?
Dreapta.
Apoi cred că trebuie să
folosim insert și ștergere.
Deci am putea... bună întrebare.  Din punct
de vedere conceptual, am putea
face această schimbare,
dar o facem folosind
insert și delete.
Deci putem... deci să facem din
nou ștergerea cazului.
Deci vrem să...
iată xi.
Vrem să-l înlocuim
cu xi plus 1 și așa mai departe.
Și astfel putem începe prin a
șterge elementul cu tasta i.
Asta va scăpa de tipul ăsta.
Apoi putem șterge
elementul cu tasta i plus 1.
Și asta ne oferă articolul.
Și apoi putem reatribui
cheia lui i în loc de i plus 1
și apoi reintroducem-o.
Deci putem scoate acest articol.
Are o cheie, care este...
Voi desena asta corect.
Deci avem cheia i
plus 1 și valoarea xi
plus 1 stocate în
această structură de date.
Apoi actualizăm cheia la i.
Și apoi îl reintroducem.
Și ia
locul acestui tip.
Deci ai putea face asta.
Ați putea merge în jos în această
listă și-- sau nu în listă,
dar puteți repeta
pentru i egal -- îmi pare rău,
pentru j este egal cu i la n minus 1
și pentru fiecare dintre aceste elemente,
ștergeți-l, schimbați cheia,
reintroduceți-l  cu noua cheie.
Și apoi nu trebuie să
construiți această structură de date intermediară
.
Deci, dacă vi se spune să
minimizați spațiul, grozav.
Și poate te gândești
la asta ca fiind mai simplu.
Îmi place să cred că asta este
mai simplu, pentru că eu...
ideea este că am timp liniar.
Pot face lucruri nebunești, prostii, care
nu sunt structuri de date, în
care încep doar de la zero.
Bine, minunat.
Dar mai există un
set de operațiuni,
inserare, ștergere, primul și ultimul.
Acestea sunt ușoare?
Bun?
Să încercăm?
Putem introduce ultimul.
Deci, acesta primește un element,
x, dorim să-l adăugăm
la sfârșitul structurii.
Deci, asta înseamnă că indicele său va
fi egal cu -- pentru că
începem de la 0, va
fi egal cu lungimea,
lungimea curentă a structurii.
Deci, să introducem
un obiect nou, care
are cheia egală cu lungimea.
Și are valoare egală cu x.  Au fost
efectuate.
Șterge ultimul, similar.
Doar ștergeți elementul
cu lungimea cheii minus 1.
OK, ce zici mai întâi?
Acesta ar trebui să adauge x la
începutul secvenței mele.
Ei bine, acum îmi dau seama că
am o problemă,
pentru că vreau ca acest
nou articol să aibă cheia 0,
deoarece după ce fac
mai întâi o inserare, get_at of 0
ar trebui să returneze acest articol.
Dar am deja un articol cu
cheia 0 și un articol cu ​​cheia 1
și un articol cu ​​cheia 2
și așa mai departe.
Și așa că, dacă am vrut
să dau lui x o cheie de 0,
trebuie să schimb tastele
tuturor acelor elemente,
exact așa cum făceam noi aici.
Și asta va
dura timp liniar.
Dar trebuia să facem asta
în timpul amortizat constant așteptat
.
Deci nu e bine.
Deci această idee nu este suficientă.
Nu este o idee rea.
Este încă o idee bună.
Dar nu mai este ceea ce
vrem de fapt să facem.
Este doar moral
ceea ce vrem să facem.
Deci, aveți vreo idee
despre cum am putea rezolva
această problemă?
Se pare că inserez
la poziția 0,
trebuie să schimb totul în
jos, timp liniar.
Asta chiar e nasol.
Da?
PUBLIC: Ai putea crea un
fel de link către altceva.
ERIK DEMAINE: Conectați această
structură de date cu alta.
Deci am putea construi
mai mult de un set.
Asta cu siguranță este permis.
Nu știu cum să
fac... oh, înțeleg.  Vrei să
spui că poate construi
o cu totul altă structură
pentru elementele care
vin înainte de 0?
PUBLIC: Da.
ERIK DEMAINE: Da, de fapt.
Asta ar merge, cred, poate.
Este ca în setul P.
Atunci trebuie să te ocupi
de când... dacă ștergi
unul dintre ele, acesta devine gol.
Apoi lucrurile devin dezordonate.
Ștergeți mai întâi va fi, de asemenea,
o problemă, deoarece
șterg începutul
acestei structuri de date,
apoi îmi pierd elementul 0.
Și vreau ca noul
element 0 să fie elementul 1.
Și din nou, toți
indicii se schimbă.
Deci ștergerea și inserarea
la prima este dificilă.
Deci am putea face acel truc
ca în setul P, dar--
sau ca în ultima
sesiune cu probleme și așa mai departe.
Dar există o idee mult mai simplă.
PUBLIC: Puteți
avea o variabilă suplimentară
pentru a urmări unde
este începutul?
ERIK DEMAINE: Frumos.
Pot avea o
variabilă suplimentară pentru a urmări
unde este începutul.
Sună asta mai întâi.
Aceasta va fi cheia
primului element, indicele 0. Un
alt mod de a spune
acest lucru este, să
folosim doar numere întregi negative, nu?
Seturile funcționează pentru orice
chei, orice chei întregi.
Bine, de fapt, am
spus din punct de vedere tehnic,
asigurați-vă că utilizați
tastele de la 0 la u minus 1.
Dar apoi, dacă aveți
numere negative, puteți plia cu ușurință--
PUBLIC: Așteaptă, nu-i așa că
[INAUDIBIL] să-ți placă
[INAUDIBIL]  ?
ERIK DEMAINE: Ah.
Numerele negative Python
înseamnă altceva.
Dar nu folosim
o interfață Python.
Folosim interfața noastră personalizată cu
set magic, pe
care arătăm cum să o implementăm
în notele de recitare, care
poate lua o cheie arbitrară.
Așează cheia respectivă și găsește
un loc pentru a pune acel element.
Deci nu
stocăm lucrurile în ordine aici.
Stocăm lucrurile
într-un tabel hash.
Dar nu ar trebui să
intrăm în
detaliile implementării.
Cred că modul în care am prezentat
hashing-ul cu funcțiile noastre universale hash
, am
permis doar numere pozitive.
Deci, poate, din punct de vedere tehnic, ar
trebui să subliniez,
dacă aveți
numere pozitive și negative,
puteți să le îndoiți în jumătate prin
maparea de la 0 la 0, de la 1 la 2, de la 2 la 4,
răspândindu-l.
Și apoi puteți lua
minus 1 și îl puteți mapa
la plus 1 și minus 2
și îl puteți mapa cu plus 3.
Deci, este ca și cum ați înmulți
fiecare dintre acești tipi cu 2
și ați înmulți fiecare dintre acești
tipi cu minus 2 și adăugați 1.
Și  apoi obțineți
numere întregi nenegative din toate numerele întregi.
Acesta este un
truc tipic de matematică pentru a arăta
că numărul de numere întregi
este egal cu numărul
de numere întregi nenegative,
ceea ce ți se poate părea ciudat.
Dar ambele sunt
infinite numărătoare.
Deci, ați putea... dacă
structura dvs. acceptă doar
chei nenegative, puteți
mapa cheile negative în acest fel
și le puteți arunca în
tabelul hash, OK?
Așa că acum, permit
lucruri negative pentru...
așa ceva.
Și așa, grozav.
Dacă vreau să inserez la
început, ceea ce pot face
este să reduc
prima mea variabilă, care
urmărește indexul.
Deci, inițial, primul
va fi 0.
Așa că voi
adăuga în versiunea mea.  În
primul rând, voi
spune că primul este egal cu
0, pentru că încep cu
cheia 0 când construiesc inițial
o structură.
Și dacă vreau să-- dacă am
nevoie de mai mult spațiu înainte de 0,
am setat mai întâi la minus 1.
Și dacă am deja
un element minus 1,
îl voi reduce la minus 2.
Decrement înseamnă scădere cu 1--
arată
programarea mea în limbaj de asamblare.
Aceasta este de obicei o
operațiune încorporată pe majoritatea computerelor.
Și apoi pot introduce un element
cu cheia mai întâi și valoarea x.
Grozav.
Și dacă vreau să
șterg primul articol,
aș șterge mai întâi elementul cu cheia
și apoi aș incrementa mai întâi.
Și acum toate operațiunile mele trebuie să se
schimbe puțin --
permiteți-mi să folosesc o altă culoare --
pentru că am
presupus implicit aici
că toți indicii mei
au început la i.
Dar acum încep la început.
Indexul 0 se mapează mai întâi cu cheia.
Și astfel,
lucrul corect de făcut aici
este plus primul și plus primul.
Practic, adăugați o grămadă
de prime plus pe tot parcursul.
Acesta este probabil bine.
Dacă reconstruiesc la nivel global,
îmi pot reatribui toate etichetele.
Dar acesta ar trebui să
fie primul plus lungime.
OK, așa că doar ținând evidența de
unde încep cheile mele,
pot face această schimbare și
nu trebuie să-mi fac griji pentru lucruri.
Și acest lucru este mult mai ușor
decât să vă faceți griji cu privire la
menținerea a două structuri și la
menținerea lor negoală
și chestii de genul
asta, din cauza...
dacă presupun că
mentalitatea mea are această putere
de a face față
numerelor întregi negative și șirurilor de caractere,
și  orice altceva.
Misto?
Da?
PUBLIC: Există vreun
motiv pentru care nu ți-a
plăcut sortarea -
cum ar fi, ai [INAUDIBLE]?
ERIK DEMAINE: Oh, de ce
nu am folosit o listă legată?
Pentru că asta.
Listele legate sunt foarte proaste la
obținerea și setarea la un anumit index.
AUDIENTĂ: Asta este
ideea de jos, este
o listă legată?
ERIK DEMAINE: Aceasta
nu este o listă legată.
Aceasta este doar stocarea
unui singur număr
ca întreg în structura dvs. de date
care spune,
care este cea mai mică cheie
din structura mea de date?
Asta e tot asta.
Este un contor.
PUBLIC: Ah.
ERIK DEMAINE: OK,
deci structura datelor
ține evidența lungimii.
Și ține evidența
cheii minime.
Și așa va
consta întotdeauna-- invariantul este că
veți
avea întotdeauna chei de la prima
până la prima plus lungimea minus 1.
Și asta este ceea ce
exploatăm aici.
Nu avem idee
unde va fi primul.
Depinde câte
operații ai făcut,
câte inserții la
început și așa mai departe.
Dar cheile-- cheile vor
fi întotdeauna de la primul la primul plus
lungimea minus 1.
Acesta este ceea ce
numim un invariant.  Este
util să notezi
aceste lucruri, astfel încât să
poți înțelege
ce naiba--
de ce este
corectă structura ta de date?
Din cauza unor invarianți
ca acesta, pe care îi
puteți dovedi prin
inducție, arătând, de
fiecare dată când faceți
o operație, aceasta
se menține, chiar și atunci când
mă schimb primul pentru a
menține acest invariant.
Misto.
Uneori vii mai
întâi cu invariantul.
În acest caz, am venit cu
el post facto, după fapt.
Misto.  Să
trecem la problema 3,
care se numește critter sort.
Și celălalt lucru cheie despre care
vreau să înveți...
întrebare?
Îmi pare rău.
PUBLIC: Da.
Deci, când faci
primul, primul plus 1,
este o reconstrucție
a [INAUDIBILĂ]?
ERIK DEMAINE: Aceasta
este doar o propoziție.
Nu este un algoritm
sau o structură de date.
Aceasta este o proprietate matematică.
PUBLIC: [INAUDIBIL]
ERIK DEMAINE: Aceasta
nu este o misiune.
Acesta este un matematic
este egal cu.
PUBLIC: Dar îl
reindexezi,
pentru că
faci primul plus 1.
ERIK DEMAINE: Deci întrebi
despre una dintre aceste operațiuni,
ca aceasta?
PUBLIC: Oh, bine.
Nu face nimic.
Înțeleg.
BINE.
ERIK DEMAINE: Da.
BINE.
Deci, cealaltă
concluzie importantă pe care
vreau să o înțelegeți despre a
citi seturile noastre de probleme
este că au
umor ascuns în interior.
Nu stiu daca ai observat.
Dar iată un exemplu de
problemă numită critter sort.
Ashley Gettem colectează
și antrenează creaturi de buzunar
pentru a lupta cu alte
creaturi de buzunar în luptă.  La
ce este aceasta o referire?
PUBLIC: Digimon.
ERIK DEMAINE: Digimon.
Uau, sunteți atât de tineri.
Pokemon, forma antică.
Pokemon este prescurtarea
pentru monștri de buzunar.
Și de fapt, în original--
PUBLIC: [INAUDIBIL]
ERIK DEMAINE: --anime--
PUBLIC: De fapt,
există [INAUDIBIL]..
ERIK DEMAINE: Nu știu.
Toate acestea sunt după timpul meu.
Putem dezbate după.
Deci, creaturi de buzunar
este o referință
la monștrii de buzunar,
care este Pokemon.
Cine este Ashley Gettem?
PUBLIC: Ash.
ERIK DEMAINE: Ash
Ketchum este numele său complet
în versiunea în limba engleză.
Nume total diferit
în versiunea japoneză.
Dar amândoi sunt jocuri de cuvinte pentru a
le aduna pe toate, nu?
Bine, deci acestea sunt
lucrurile importante.
Vom vedea mai multe glume mai târziu.
Deci există această configurație.
Dar, practic,
avem n creaturi.
Și vrem să le sortăm
după patru lucruri diferite.
Și deci voi
abstrage această problemă pentru a
sorta n obiecte după
următoarele tipuri de chei.
Și pentru fiecare, vrem să
știm care este cel mai bun
algoritm de sortare.
Și există această notă de subsol
care este foarte importantă care spune că
algoritmii corecti mai rapidi
vor primi mai multe puncte
decât algoritmii corecti mai lenți.  De
asemenea, algoritmii corecti
vor primi mai multe puncte
decât algoritmii incorecți.
Dar asta e implicit.
Incorect devine, în general, zero.
OK, deci partea a,
spune, ID-ul speciei.
Dar, practic, avem numere întregi
și intervalul minus n la n.
Deci, dacă vreau să sortez n numere întregi
în intervalul minus n la n,
ce ar trebui să fac?
Aceasta este o referire la
prelegerea de ieri.
Da?
Radix sort, da.
Întotdeauna un răspuns bun.
Sau aproape întotdeauna un
răspuns bun când aveți numere întregi.
Este un răspuns bun ori de câte ori ai
numere întregi mici.
Acum, radix sort, așa cum
am formulat-o...
lasă-mă, poate, să o pun aici.
Sortarea radiculară sortează n numere întregi în
intervalul de la 0 la u minus 1 în n
plus n log bază n de u timp.
Și în special,
acesta este timpul liniar
dacă u este n la o
putere constantă.
OK, deci pot să aplic asta
așa cum este acestor numere întregi?
Nu, pentru că sunt negative.
Si ce ar trebui sa fac?
Poate ar trebui să-
mi fac trucul de pliere.
Tocmai am văzut cum să luăm
numere negative și să le împăturim,
intercalate cu
numere pozitive.
Dacă rezolv asta, va funcționa?
Nu, pentru că asta
nu menține ordinea.  S-ar
intercala.
Vrem ca toate
numerele negative să vină înaintea tuturor
numerelor pozitive.
Da?
PUBLIC: Puteți
adăuga n la toate numerele întregi?
ERIK DEMAINE: Doar adăugați n, da.
Bum.
Plus n.
Acum avem numere întregi
în interval-- să fim
atenți-- de la
0 la 2n.
Misto.
Acum putem aplica asta.
Acum u este egal, din punct de vedere
tehnic, 2n plus 1,
pentru că ar trebui
să mergem doar la u minus 1.
Dar e bine.
Asta e liniar.
Și astfel putem sorta
în timp liniar, ușor.
Aceasta este o problemă super ușoară.
Dar în fiecare dintre ele, ar putea fi nevoie
să facem o transformare.
Partea B este puțin
mai interesantă.
Deci avem șiruri de peste 26 de
litere cu lungimea de cel mult
10 jurnal de tavan n.
OK, asta este puțin mai complicat.  Ce as
putea sa fac?
Din nou, aș dori să văd
dacă se aplică sortarea radix.  Ar
trebui să spun sortarea radix.
Aș dori să văd dacă se
aplică sortarea radix.
Pentru a face asta, trebuie să mapez aceste
șiruri în numere întregi cumva.
Vreo modalitate de a face asta?
Acest lucru este ușor dacă
înțelegeți sortarea radix.
Da?
PUBLIC: Puteți doar să
indexați literele?
ERIK DEMAINE:
Index, literele.
Da.
Da, putem să hărțim...
corect.
Deci putem mapa A la 0, B la 1.
Atunci ce?
PUBLIC: Oh, stai.
Lungimea...
ERIK DEMAINE: Deci
asta e pentru fiecare literă.
Dar avem o mulțime de scrisori.
Sunt doar 26 de litere.
Dar apoi avem 10 log
n litere într-un șir.
Adică, împreună, o singură
cheie pe care trebuie să o sortăm.
Da?
Publicul: Nu putem sorta mai
întâi după prima literă, apoi...
ERIK DEMAINE: Sortați după prima
literă, apoi a doua literă.
Acesta este exact
opusul sortării radix.
Amintiți-vă, sortarea la bază,
vrem să începem
cu ultima literă, apoi până
la ultima literă
și, în final, cu prima literă.
PUBLIC: Dar doriți
să sortați după primul
pentru a alfabetiza lucrurile.
ERIK DEMAINE: Nu,
pentru a alfabetiza...
vrem, în final, să
sortăm după prima literă.
Dar asta e la final.
Deci, la sfârșit,
amintiți-vă, sortarea radix
merge întotdeauna înapoi
de la cea mai puțin semnificativă
la cea mai semnificativă.
Și, într-adevăr, asta
este ceea ce vrem să facem.
Vrei doar să spui,
folosește sortarea radix.
Dar pe ce sunt radix sort?
Pe ce sortez radix?
PUBLIC: Da, la ultimele
litere, nu la primele litere.
ERIK DEMAINE: Deci, din punct de vedere
tehnic,
ar fi folosirea
sortării de numărare pe ultima literă, a
numărării sortării de până la ultima literă,
punct,
punct, punct, sortare de numărare
pe prima literă.
Dar asta înseamnă, împreună,
sortarea radix pe ceva,
sau lui Jason îi place să numească
această sortare de tuplu.
Sortarea tuplelor este chestia -
este algoritmul care spune,
sortați după ultimul lucru,
apoi sortați după
lucrul anterior și așa mai departe.
Puteți, de asemenea, să vă gândiți la
asta ca la sortarea radix
pe un număr scris în baza 26.
Sunt același lucru.
Dar în cele din urmă, putem
sorta în timp liniar.
PUBLIC: Cum vă
asigurați că literele sunt
sortate în ordine, totuși?
Cum te asiguri că...
cum îi spui algoritmului
că vrei A să vină...
la fel ca nu... 0 este mai mic
decât 1, A este mai mic decât B.
ERIK DEMAINE: Corect.
Deci, din punct de vedere tehnic,
când apelezi la
ceva de genul tuple sort--
sau poate este chiar mai clar
când apelezi radix sort.
Radix sort, îi dai o
grămadă de numere.
Deci, luați aceste șiruri
și le mapați la numere.
Și când faci asta,
poți decide care literă
este cea mai
semnificativă, care este cea
mai puțin semnificativă, nu?
Așa că veți alege să mapați întotdeauna
prima literă din șirul dvs.
la poziția--
la valoare, sau la--
cum o numiți?
Poziția în notația pozițională.
Poziția 26 la puterea 10
log n ca cea mai semnificativă.
Deci este întotdeauna cea
mai semnificativă.
Chiar dacă șirul tău
are lungimea 1,
vrei să-l pui în
cifra cea mai semnificativă.
Și vei completa cu
zerouri la sfârșit
dacă rămâi fără
litere din șirul tău.
PUBLIC: De câte ori
rulați să numărați sortați aici?
ERIK DEMAINE: De câte ori
rulez sortarea de numărare?
Oh, de 10 log n ori.
Hopa.
Da, bună întrebare.
Buna observatie.
Da, am calculat greșit.
Deci corect.
Există jurnal n
cifre în șir.  Deci e
rău.
Adică, e în regulă.
Vom ajunge cu n log n
timp de rulare prin sortarea tuplelor.
Totuși... deci acesta este
tipul de tuplu.
Așa că ar trebui să fac
acest lucru să nu fie echivalent.
Dacă rulez tuple scurte literă
cu literă, voi face...
Voi rula numărarea
jurnalului de sortare de n ori.
Și astfel obțin n log n, pentru că
fiecare are timp liniar.
Dacă îmi mapez
mai întâi șirurile în numere,
sortarea radix nu folosește baza 26.
Folosește baza n.
Și apoi va
rula doar de 10 ori,
pentru că 2 la 10
log n este n la 10.
Și astfel numerele pe care le
sortăm sunt între 0 și n
la 10.
Și deci u este n la 10.
Și  deci acesta este cazul când
sortarea radix rulează în timp liniar.
Deci, dacă rulați tuple scurt
literă cu literă, este lent.
Dacă rulați radix sort,
face o grămadă
de litere simultan.
În mod efectiv,
înregistrează n litere
la un moment dat într-un singur
apel la sortarea de numărare.
Și astfel sortarea radix va
câștiga de fapt și va deveni liniară.
Există o subtilitate
aici, și anume,
presupun că putem de
fapt să luăm aceste șiruri
și să le convertim în numere întregi
în timp constant fiecare.
Și acest
set de probleme era ambiguu.
Și ambele răspunsuri au fost acceptate.
Dacă presupuneți că aceste litere
sunt drăguțe și
stocate compact și se
potrivesc în 10 cuvinte,
deoarece un cuvânt are
cel puțin log n biți,
atunci puteți face acest lucru.
Dacă stocați fiecare literă
într-un cuvânt separat,
atunci doar citirea întregii
intrări va dura n log n timp.
Deci, aceasta este o subtilitate pentru care
nu trebuie să ne îngrijorăm prea mult
în această clasă.
Da?
PUBLIC: Deci [INAUDIBIL]
limitând literele
la cifre.
Și cum ar ajuta asta?
Pentru că mai trebuie să facem 26--
ERIK DEMAINE: Da,
există 26 de litere posibile,
numerotându-le de la 0 la 25.
Și apoi, când luăm
un șir, cum ar fi AA,
mapăm acesta în 00 în baza 26.
Acesta este un număr.
Dacă facem BB, de
exemplu, aceasta se mapează la 11
în baza 26, ceea ce înseamnă 1
ori 26 plus 1, care este 27.
OK, deci asta e
maparea la care vreau să spun.
PUBLIC: Cartografiați
întregul șir [INAUDIBIL]?
ERIK DEMAINE: Întregul șir
la un singur număr, da.
Și există o subtilitate,
pentru că vreau lexicografic.
Trebuie să adaug lucrurile
cu spații la sfârșit
sau să le amplă cu As
la sfârșit, în cazul în care
sunt mai scurte de 10 log n.
Bine, in regula.
Asta a fost b.
c nu este foarte interesant.
Sunt numere întregi în
intervalul de la 0 la n pătrat.
Acest lucru, îl pot
rezolva doar cu sortarea radix,
deoarece sortarea mea radix
, în acest moment, am
făcut-o a treia oară.
Sortare prin bază, putem sorta atâta timp
cât numerele întregi sunt
mărginite de un polinom.
Aici, este un polinom fix
cu un exponent constant.
Deci, acest lucru va-- și
acesta este sortarea radix,
așa cum am văzut, care doar
numește sortarea numărării de două ori,
timp liniar.
d este locul unde lucrurile
devin mai interesante.
Lasă-mă să iau această
frază la fel.
Deci, în d, avem
numere raționale de forma w peste f.
Acesta este un raport de câștig.
Întotdeauna în intervalul 0 la 1.
Deci am văzut că w este cel mult f.
Și 0 este mai mic decât w, este
mai mic decât f, este mai mic decât n
pătrat, pentru că --
asta este într-adevăr confuz --
este mai mic decât n pătrat --
acestea sunt declarații separate --
pentru că f provine de fapt
din partea c.
Și c este într-adevăr o
configurație pentru aceasta.
Chiar nu contează
ce înseamnă asta.
Doar că
avem numere w și f,
unde w este întotdeauna mai mic decât f.
Și sunt între
0 și n pătrat.
Așa că ar trebui să te gândești, aceasta este
o gamă bună pentru mine, nu?
Că reprezint
acest rațional
în termeni de două numere
între 0 și n pătrat.
Deci, există ca n până la
a 4-a opțiuni posibile
pentru ceea ce sunt w și f.
Deci intervalul
valorilor mele este de la n la a 4-a.
Aceasta este setarea în care
sortarea radix ar trebui să ruleze rapid.
Din păcate, aceste numere--
ceea ce vreau să sortez
nu este un număr întreg.
Este un rațional.
Și asta e enervant.
Deci, există câteva
moduri de a rezolva această problemă.
În general, o modalitate bună de a rezolva
sortarea este să utilizați sortarea prin îmbinare.
Sortarea prin îmbinare este întotdeauna
un răspuns bun.
Nu este cel mai bun răspuns.
În aceste cazuri, am
bărbierit un buștean.  Am
ajuns la timpul liniar.
Dar n log n este destul de bun.
Este destul de aproape de n.
Deci, primul obiectiv ar putea
fi, putem chiar să obținem
n log n prin sortare de îmbinare?
Ce ar trebui să fac pentru a
aplica efectiv sortarea de îmbinare
acestei instanțe?
Ce face
sortarea de îmbinare cheilor sale?  Îmi
pare rău?
PUBLIC: Izolează-le
și compară-le.
ERIK DEMAINE: Le izolează și le
compară, da, corect.
Deci există o
structură de date matrice.
Și se indexează în matrice.
Asta e izolarea.
Dar atunci lucrul pe care îl face de fapt
cu articolele în sine
este întotdeauna o comparație.
Și acesta este motivul pentru care am introdus
modelul de comparație
și am demonstrat o limită inferioară n log n
în modelul de comparație,
deoarece sortarea prin îmbinare,
sortarea prin inserție
și sortarea selecției sunt
toți algoritmi de comparație.
Sortarea Radix nu este.
Dar acesta este.
Dar pentru a aplica sortarea de îmbinare, trebuie
să spun, cum compar wi
peste fi versus wj peste fj?
Computerul meu se
ocupă doar de numere întregi.  De
fapt, nu putem
reprezenta wi peste fi în
mod explicit în binar, deoarece
are infinit de biți.
Dar îl pot reprezenta
implicit
prin stocarea wi și fi.
Da?
PUBLIC: Înmulțiți cu fi și fj.
ERIK DEMAINE: Înmulțiți
cu fi și fj, da.
Când m-am dus...
nu m-am dus la școală,
dar apoi am învățat
înmulțirea încrucișată,
care este la fel cu
înmulțirea ambelor părți cu fi
și înmulțirea ambelor
părți cu fj, așa cum ai spus.
Deci, obținem fi fj mai puțin
decât semnul de întrebare f--
orice-- fi wj.
Când facem asta, mai bine ne
asigurăm că lucrurile cu care ne
înmulțim
sunt nenegative.
În caz contrar, semnul se răstoarnă.
Dar aici, presupunem că
toate sunt nenegative.
Deci asta e bine.
Și acum doar
înmulțim două numere întregi aici,
înmulțim două numere întregi
aici și comparăm.
Acestea sunt toate lucrurile pe care le
pot face într-un cuvânt RAM.
Deci aceasta a fost de fapt
soluția intenționată
atunci când a fost pusă această problemă.
Iată o modalitate de a face
sortarea prin comparație.
Obținem n log n.
Dar, de fapt, puteți
obține timp liniar.
Da?
AUDIENTĂ: [INAUDIBILĂ] acea
soluție, cum ați
spune rapid care este mai mare?
Pentru că cu ori f
de j, unul dintre ei
aparține unuia dintre
Pokemoni, iar celălalt
este [INAUDIBIL].
ERIK DEMAINE: Simt că e
o glumă aici, cum ar fi...
PUBLIC: [INAUDIBIL]
ERIK DEMAINE:
Pikachu este superior.
Acesta este întotdeauna răspunsul.
Deci, cum îmi dau seama
dacă un Pokemon
este superior celuilalt?
Dacă înmulțesc my--
înmulțesc valoarea f a lui i
cu valoarea w a lui j.
Și văd dacă aceasta este
mai mare decât
valoarea i a w înmulțită cu valoarea f a lui j.
Și dacă este...
deci acestea sunt echivalente.
Dacă acesta este
mai mare decât acesta,
știu că acesta este
mai mare decât acesta.
Acestea sunt propoziții echivalente
prin matematică, prin algebră.
Și asta este ceea ce
vreau să știu.
Aceasta ar spune că j
este superior lui i.
Și așa determin asta făcând
acest lucru.
Deci nu trebuie să împart
și să mă ocup de numere reale,
pentru că nu știu cum,
pentru că sunt computer.
Toți suntem computere până la urmă.
BINE.
Așa că ar fi grozav
dacă numerele mele ar
avea toate același numitor.
Dacă toți ar avea același f, atunci
aș putea doar compara w-urile.
Deci, aceasta este o intuiție
de ce putem
face acest lucru în timp liniar.
Dar felul în care îmi place să mă
gândesc la asta... deci să
desenăm
intervalul real de la 0 la 1.
Și există diverse puncte
peste tot aici care reprezintă...
Nu pot să calculez asta.
Dar conceptual, fiecare dintre
aceste wi fi-uri se încadrează undeva
în acel interval de la 0 la 1.
Și vreau să le sortez cumva.
Deci, un lucru care
ar fi grozav este
dacă aș putea lua
aceste numere reale
și le-aș mapa cumva
la numere întregi,
care sunt uniform distanțate,
poate încă câteva dintre ele.
Dar acestea merg de la
0 la u minus 1.
Și dacă aș putea să
vă fac relativ mic,
și aș putea mapa fiecare dintre acestea -
așa că vreau ca maparea
să fie păstrarea ordinii.
Și vreau două elemente foarte apropiate,
dar distincte pe care să le mapez la...
chei distincte aici.
Vreau să se mapeze la
numere întregi distincte aici jos.
Dacă aș putea face asta, atunci aș
sorta doar după numere întregi.
Și asta e același cu
sortarea după numere reale.
Și, în acest moment,
mă întreb, cât de aproape
pot fi două dintre aceste numere?
Deci cât de apropiate pot fi două chei?
Deci vreau să iau în considerare wi
peste fi minus wj peste fj
în valoare absolută.
Acum fac algebră.
Deci asta este...
Aș dori să aduc
asta într-un singur raport.
Deci asta este --
Pot face asta înmulțind
1 cu fi, 1 cu fj.
Acum asta este wi fj minus
wj fi, care ar trebui să
semene foarte mult cu ceva aici.
Dar nu conteaza.
Sunt sigur că există o
legătură profundă aici.
Probabil că pot folosi asta pentru a
dovedi asta și invers.
Misto.
Deci, cu niște
valori absolute, același lucru.
Poate că acestea nu sunt negative,
așa că pot
pune
valori absolute în partea de sus.
Și OK, wi este un număr întreg, fj este
un număr întreg, wj este un număr întreg,
fi este un număr întreg, toate
mai mari sau egale cu 0.
Deci acest lucru este un număr întreg.
Deci ar putea fi egal cu 0.
Este un întreg nenegativ,
deoarece toate lucrurile
sunt nenegative.
Ar putea fi egal cu 0.
Dar dacă sunt
egali cu 0, acestea sunt
de fapt
rapoarte identice, nu?
Dacă acesta este 0,
totul este 0.
Și astfel aceste două
valori au fost aceleași.
OK, dar să
presupunem că nu este 0.
Dacă nu este 0,
de fapt este cel puțin 1,
valoarea absolută,
pentru că este un număr întreg.  Dar
fundul?
fi-- deci acum vrem asta--
Vreau să știu cât de
mic poate fi acest raport.
Va fi mic când
acesta este mic și acesta este mare.
Cât de mare ar putea fi fi fj?
Ei bine, ni se spune că toate
f-urile sunt mai mici decât n pătrat.
Deci acest lucru este
cel mult n pătrat,
n la al patrulea, mai puțin
decât n al patrulea--
n pătrat minus 1 pătrat,
mai puțin de n la al patrulea.
PUBLIC: [INAUDIBIL]
ERIK DEMAINE: fi este cel
mult n pătrat.
fj este cel mult n pătrat.
Deci este n pătrat pătrat.
Deci, acesta este cel puțin
1 peste n la al patrulea.
Deci, cel mai aproape se
pot apropia cele două puncte aici
este 1 peste n până la al patrulea.
Deci, ce pot face pentru a
extinde asta pentru a le face un
fel de numere întregi?
Înmulțiți cu n la a 4-a.
Deci, doar înmulțiți cu n până la
al 4-lea și apoi etaj.
Așa că vom
lua fiecare fi peste...
Aș dori să calculez acest raport.
Dar nu știu cum.
Deci, în schimb, voi
lua fi, înmulți...
OK.
Conceptual, ceea ce vreau să
fac este să înmulțesc cu n până la al patrulea
și să iau cuvântul.
Cum fac asta de fapt
într-o mașină care nu
are numere reale ca acesta?
Deci nu am o
operație la podea.
Am doar operații cu numere întregi.
Apoi pot lua fi,
îl pot înmulți cu n până la al patrulea
și pot împărți întregul cu wj.
Este la fel,
care calculează exact
acest lucru, pentru că
pot face înmulțirea
și împărțirea
în orice ordine în spațiul real.
Și apoi aceasta face podeaua
la momentul potrivit.
Dar acestea sunt doar
operații pe numere întregi.
Și acum acestea sunt
numere întregi care reprezintă
cât de buni sunt Pokemonii mei.
Au proprietatea că
oricare două distincte...
înainte de a lua cuvântul, oricare
două distincte sunt la cel puțin 1
depărtare.
Așa că după ce voi lua cuvântul,
vor rămâne 1 depărtați.  Vor
rămâne
numere întregi distincte.
Și așa am
mapat cu succes numerele mele reale
la numere întregi în care
numere reale distincte se potrivesc cu
numere întregi distincte.
Da?
PUBLIC: Așteaptă.
Deci, de ce fi este acum
la numărător și wi
la numitor?
ERIK DEMAINE: Le-am răsturnat?
Da scuze.
Te rog inversează
totul... doar aici.
Acesta este w și fi.  A
fost doar o greșeală de tipar.
Asta sunt toate.
BINE.
PUBLIC:
Amândoi sunt i sau j?
ERIK DEMAINE: Acestea ar
trebui să fie ambele i, da.
Mulțumesc.
Aceasta a fost pentru fiecare
Pokemon, i, vom
calcula
asta ca cheie.
Și apoi vom
sorta după acele chei întregi.
Și asta îi va sorta pe
Pokemon după proporțiile lor.
Să scriem mon pentru monstru.
Da?
PUBLIC: [INAUDIBIL]
u minus 1 [INAUDIBIL]??
ERIK DEMAINE: Deci ai fost doar un...
scuze, aceasta este... o etichetă pe
chestia asta te-ar putea ajuta.
PUBLIC: Oh.
ERIK DEMAINE: Da.
Așa că acum... oh, corect.  care
esti tu al meu?
Care este cea mai mare cheie a mea?
Îmi vine prin minte, chiar mi-ar
plăcea ca fi să fie mai mare decât 0.
Dar să nu ne facem griji.
Cât de mare poți fi?  Ei
bine, cel mai mare lucru
poate fi dacă fi este mic
și acesta este mare.  Să
presupunem că fi poate
coborî doar la 1.
Altfel, vom
obține o împărțire cu 0.
Trebuie să ne ocupăm
mai ales de infinit.
Probabil că problema nu este nici
măcar bine definită atunci.
Cât de mare ar putea fi asta?
Ei bine, știu că wi--
PUBLIC: f sunt
definite ca pozitive.
ERIK DEMAINE: Oh, bine.
Mulțumesc.
Deci, există și o
constrângere pozitivă aici.
Doar că nu am reușit să păstrez
această constrângere în maparea mea
de la cuvântul problemă
în problema formală.
Deci f este cel mai mic 1.
Bun.
Dar cel mai rău caz este când are 1.
Și când wi-- cât de
mare ar putea fi?
Ei bine, n pătrat minus 1.
Deci, acesta ar putea fi,
practic, n pătrat
ori n la al patrulea împărțit
la 1, care este n la al șaselea.
Deci w-- sau scuze, u, cea
mai mare cheie pe care o pot avea plus 1,
este n la a 6-a.
Dar este în regulă, deoarece
sortarea radix poate gestiona
orice polinom fix în n.
Deci va ajunge să facă
șase treceri de sortare de numărare.
OK, asta e problema 3. Să
trecem la problema 4.
Deci problema 4, MIT l-a
angajat pe Gank Frehry.
Cine e?
Frank Gehry, da.
Aceasta este o codificare comună
care îi place foarte mult lui Jason.
Am ajuns să-mi placă.
Acest lucru se numește spoonerism,
în care înlocuiți o parte
din începutul lucrurilor dvs.
OK, asta e o glumă.  Mai
este o glumă
în această problemă.
Oricum, ei construiesc o
nouă aripă a Centrului Stata,
așa cum face cineva.
Avem o grămadă de cuburi.
Dacă citești suficient de mult, îți
dai seama că este un hering roșu.
Cuburile nu joacă un
rol în această problemă.
În cele din urmă,
avem o grămadă
de numere întregi, care se întâmplă să fie
lungimea laterală a cuburilor.
Dar ne pasă doar de
lungimile laturilor, nu de
volumul lor sau de nimic --
s n minus 1.
Și vrem două numere
în s însumând h.
PUBLIC: Este o
prostie, dar cum pot cuburile să
aibă mai mult de șase laturi?
ERIK DEMAINE: Aceasta
este lungimea laturii, nu
numărul de laturi.
Deci un cub--
PUBLIC: Oh, OK.
ERIK DEMAINE: Cool.
Nu știam că vom
face geometrie 3D astăzi.
Asta e si.
Bine, deci ai cuburi mici.
Ai cuburi mari.
Acesta este un mic si.
Acesta este un si mare.
Nu contează, totuși.
Sunt doar numere.
Nu le folosim deloc.
În problemă,
încercați să vă place să
stivuiți un cub pe celălalt.
Dar tot ce ne pasă cu adevărat
sunt două numere a căror
sumă, sumă veche obișnuită
, este exact h, în mod ideal.  Vor
exista două
versiuni ale acestei probleme.
Și astfel primul obiectiv
este de a rezolva acest lucru exact
în timpul liniar așteptat.
Asta spune problema.
Deci ce știm?  Ei
bine, timpul liniar, asta--
nu poate deveni mult mai rapid decât
atât, pentru că avem nevoie de asta doar
pentru a citi intrarea.
Timp așteptat... hashing, nu?  Ni sa
spus, practic, ar
trebui să folosim hashing.
Acum, dacă suntem cu adevărat
enervanti, poate
îl aruncăm chiar și
atunci când nu ai nevoie.
Dar asta e destul de rar.
Așa că atunci când vedem de așteptat, ar
trebui, într-un set de probleme
ca
acesta, în viața reală,
nu știi niciodată ce
ar trebui să folosești.
Dar la noi... cu
învățarea ta în această clasă, o să-ți
spunem
practic ce
trucuri ai voie să folosești.
Aici, aveți voie
să utilizați randomizarea.
Deci, probabil, avem nevoie.
Într-adevăr, ai nevoie de el
pentru a atinge această limită.
Misto.
Hashing.
Nu este evident cum să abordăm
această problemă cu hashing.
Așa că o să-ți
spun modul în care...
îmi este greu să nu
cunosc acest algoritm.
Dar pentru mine, primul lucru la care ar
trebui să te gândești
este dacă am
timp liniar și n lucruri
și voi folosi hashing,
lucrul evident de făcut
este să iau acele n lucruri
și să le pun într-un tabel hash.
Construi.
De ce nu?
Deci, să construim un
tabel hash pe toate cheile din s.  Asta e
ideea unu.
Pare
primul lucru de încercat.
Deci ce mă lasă să fac?
Îmi permite...
Tocmai am șters
interfața pentru tabelele hash.
Dar pot construi o
secvență din ea.
Dar, în mod normal,
îmi oferă o interfață setată.
Așa că pot apela găsi
acum în timp constant.  Îmi
permite, având în vedere
numărul, să stabilesc imediat
dacă acel număr este în s.
Ei bine, asta sună
interesant, pentru că
caut două numere în s.
Așa că îmi permite să găsesc una dintre ele.
Deci îl sun de două ori?
Nu.
Apelarea de două ori și doar
petrecerea timpului constant
pe această structură de date frumoasă
nu
vă va oferi nimic util.
Dar avem timp liniar, nu?
Deci, pe lângă
construirea unui tabel,
am putea numi găsire pe
acel tabel de un număr liniar
de ori, deoarece fiecare găsire ia
doar
timp amortizat așteptat constant.
Deci, dacă fac n dintre ele,
va dura timp liniar așteptat.
Amortizarea dispare,
pentru că o folosesc de n ori.
PUBLIC: [INAUDIBIL]
ERIK DEMAINE: Oh, corect.
Find nu are niciodată amortizare.
Deci nu dispare,
pentru că nu a fost niciodată acolo.
Nu face nimic.
Îmi permit n apeluri,
sau 5n apeluri, pentru a găsi,
deoarece fiecare costă
constant așteptat.
Și totalul pentru asta
va fi timp liniar.
Deci următoarea idee este să sunăm
cumva să găsim
un număr liniar de ori, OK?
Deci vreau să găsesc două numere
care însumează o valoare dată, h.
Poate că nu a fost
clar, dar h este dat.
PUBLIC: Îmi pare rău.
Cât durează
construirea tabelului hash?
ERIK DEMAINE: Cât
durează construirea unui tabel hash?  A
fost anterior pe această
placă - timp liniar așteptat.
Vezi prelegerea anterioară.
Nu, acum doi ani.
BINE.  Ei
bine, dacă vom face
asta de un număr liniar de ori,
cred că ar trebui să
avem o buclă for.
Să facem o buclă for
peste numere.
Asta e următoarea idee.
Bucla peste s.
Și în acest moment,
am terminat, aproape.
Vreau spatiu.
Așa că vreau să fac o buclă
peste numere.
Și fiecare,
vreau să fac o descoperire.
Cam asta e tot ce
am timp să fac.
Deci pare un
lucru firesc de încercat.
Acest lucru nu este deloc ușor.
Nu mă înțelege greșit.  A
avea aceste idei este...
deși le explic ca
fiind idei evidente,
ele nu sunt evidente.
Dar sunt ușor,
cel puțin, pur și simplu nu sunt
evidente să vină
cu idei ușoare.
Deci haideți să trecem peste
s, să apelăm cumva find,
folosind tabelul nostru hash.
Deci, ordinea este de fapt, vom
construi tabelul hash,
apoi vom bucla.
Și în interiorul buclei, vom
apela find o dată
pe iterație de buclă.
Deci hai sa o facem.  Să
spunem, pentru si în S--
deci vreau să găsesc două numere.
Aici, am făcut o
buclă exhaustivă peste un număr.
Trebuie doar să găsesc
al doilea număr care se
poate aduna, nu?
Vreau să aflu dacă
există un sj în S astfel
încât si plus sj să fie egal cu h.
Pot face acea interogare cu find?
Cum?
Deci, ce face găsirea?
Find spune, dacă îți dau o cheie,
îmi va spune dacă... de exemplu,
dacă aș ști ce
este sj, mi-ar spune
dacă este în S. Da?
PUBLIC: Nu poți
doar să scazi h din si
și apoi să vezi dacă [INAUDIBIL]?
ERIK DEMAINE: Scădeți h din
si și vedeți dacă există.
Ați înțeles bine?
PUBLIC: h minus si.
ERIK DEMAINE: h minus si.
Întotdeauna înțeleg greșit.
Nu te simți rău că
și ai greșit.  Mă
face să mă simt mai bine,
pentru că întotdeauna înțeleg greșit.
Deci afirmația este aceasta.
De ce?
Pentru că ceea ce
vrem să facem este să găsim...
bine, bine.
Să vedem ce
scrie aici.
Deci, dacă facem h minus
si este egal cu sj--
deci acestea sunt
declarații echivalente,
doar prin mutarea si peste.
Și aceasta este o întrebare pe care o putem face.
Deci, să ne amintim, acestea
sunt lucruri pe care le știm.
Și s.j este ceva ce
nu știm.
Tot ceea ce știm
este că este un s.
Bine, deci știm aceste două lucruri.
Deci, dacă îi aducem
pe aceeași parte,
căutăm
un lucru necunoscut,
care este egal cu exact acest
lucru pe care îl putem calcula.
Deci doar calculăm h minus si.
Sunăm găsi.
Asta ne va spune dacă
există un sj egal cu acesta.
OK, deci acesta este ca un comentariu.
Și asta facem de fapt.
Și dacă există o pereche
de numere care însumează la h,
aceasta o va găsi.
Cât timp a durat?  Ei
bine, facem n
iterații ale acestei bucle.
Fiecare, numim
o singură operație de căutare.
Și să găsească costurile
constant în timpul așteptat.
Și astfel totalul este
timpul așteptat liniar.
Grozav.
Partea A gata.
Apoi ne aruncă partea b
, o îngreunează.
Acei instructori plini de rău.
Deci citim partea b.
Partea B spune două lucruri
pentru a face totul mai greu.
Deci, în primul rând, vrem
timp liniar în cel mai rău caz.
Și în plus... așa că
nu mai putem folosi hashing.
În plus,
aici, trebuie doar
să rezolvăm problema exactă
pentru a afla dacă cele două
numere se însumează exact la h.
Acum am dori să găsim cea
mai bună soluție mai mică
sau egală cu h.
Deci, găsiți cea mai mare
sumă pe perechi care este
mai mică sau egală cu h dacă
nu există o pereche perfectă.
Dar ni se oferă puține
informații suplimentare, adică
putem presupune că h este
egal cu 600 n cu al 6-lea.
Este un polinom ciudat.
Mi-a luat ceva timp să observ
că a fost o glumă aici...
6006, ascuns într-un polinom.  În
regulă, deci polinom.
Hm.
Asta ar trebui să te facă să te
gândești la un tip de radix.
Este o săptămână de tip radix.
Deci este un
lucru firesc de încercat.
Dar, în general, chiar și
mai târziu în semestru,
când vedeți un
polinom frumos cu o
constantă fixă ​​ca aceasta
și are cumva
legătură cu numerele întregi cu care
avem de-a face,
ar trebui să vă gândiți la sortarea radix.
Mai ales că acum,
vrem timp constant în cel mai rău caz,
sortarea radix pare a fi
un lucru bun de făcut.
Nu stiu
inca ce sa fac cu el.
De fapt, nici nu pot
aplica sortarea radix.
Dar ideea unu este tipul radix.
Doar pentru că văd
acel polinom,
cred că ar trebui să-l încerc.
Acum, există o problemă aici,
pentru că ni se dau niște
numere, niște numere întregi, și.
Ni se dă și h.
Ni se spune acum că este un
polinom mic și frumos.
Dar nu avem idee cât de
mari sunt aceste cifre.
Deci problema cu
această idee este că...
dar si ar putea fi mai mare decât h.
Nu avem idee cât de
mari sunt si-urile.
Ce pot spune
despre si-urile care sunt
mai mari decât h pentru această problemă?
Însumând la h.
Oh.
Nu am spus-o, dar toate aceste
numere sunt nenegative.
Asta este important.
Asta arată ca [INAUDIBIL].
Mai mare sau egal cu 0.
Da?
AUDIENTĂ: [INAUDIBILĂ]
soluție [INAUDIBILĂ]..
ERIK DEMAINE: Corect.
Dacă găsesc o sumă
mai mică sau egală cu h,
acestea nu sunt negative.
Și orice număr care este mai mare
decât h, îl pot arunca.
Nu vor fi niciodată într-o soluție.
Deci deja... o sumă a
unui număr este mai mare decât h.
Deci doi vor deveni
mai mari doar dacă nu sunt negativi.
Așa că ideea numărul doi este să
aruncăm toate marile si-uri,
orice mai mare decât h.
Acum, asta nu va schimba
răspunsul, pentru că acestea nu pot
fi niciodată într-o soluție.
Și acum am toate si-urile
având
proprietatea că sunt
mai mici sau egale cu h.
Și deci sunt mici,
mărginite de un polinom fix.
Și acum pot aplica sortarea radix.
Deci, după această idee,
pot aplica această idee.
OK, asta vă oferă
o aromă a modului în care îmi
place să mă gândesc la probleme.
Văd indicii, ca un polinom.
Cred că sortarea radix nu funcționează.
Dar cu mai multe idei, o
pot face să funcționeze.
BINE.
Ce se întâmplă cu...
așa că acum am sortat.
Bine, minunat.
S este sortat.
Bănuiesc că putem încerca să
facem același algoritm,
doar că nu
mai am un tabel hash.
Deci să încercăm să facem o
buclă for peste S. De ce nu?
Deci hai să facem pentru si în
S. Dar acum e sortat.
Deci, probabil, ar trebui să
exploatez ordinea sortată.
Deci haideți să le facem în ordine.
Deci i este egal cu 0, 1,
până la n minus 1. Să
presupunem că s0
este cel mai mic.
s1 este următorul cel mai mic.
sn minus 1 este cel mai mare.
Asa ca vreau sa fac ceva cu...
asa ca am si.
Și vreau să-mi dau seama
dacă h minus si este acolo.  Este
greu să fac asta mai bine decât...
de fapt, aș putea face
asta cu căutare binară.
Caut aceasta valoare.
Și acum am o matrice sortată.
Așa că aș putea
căuta binar pentru h minus si.
Și în log n time, voi afla
dacă acel tip este acolo.
Și dacă nu, continuă să faci bucla.
Pot să urmăresc
cel mai bun lucru pe care l-am găsit.
Și astfel, în n log n timp, cu
siguranță pot rezolva acest lucru.
Dar aș dori să obțin timp liniar.
Ai o intrebare?
PUBLIC: Ei bine,
mă întreb doar,
cum ai fi [INAUDIBIL]?
Cum ar fi, de ce ați
[INAUDIBIL] dacă
este acolo [INAUDIBIL]?
ERIK DEMAINE:
Nu-l caut pe si.
Am de gând să calculez h minus si.
Deci aceasta este... poate nici nu ar trebui să
notez asta, dar...
PUBLIC: Ea întreabă despre
constrângerea [INAUDIBILĂ] a,
nu căutăm h.
Căutăm
ceva mai mic decât h.
ERIK DEMAINE: Acesta?
Sau--
PUBLIC: Ceva mai mare.
ERIK DEMAINE: Oh, chestia asta.
PUBLIC: Un
lucru mare mai puțin decât h.
ERIK DEMAINE: Corect.
Deci, în special, dacă
există două elemente care însumează h,
vreau să-l găsesc.
Deci, să începem cu asta.
Deci sunt binar căutând
h minus si în S.
Așa că cu siguranță aș putea face asta.
Și dacă îl găsesc, grozav.
Am găsit o pereche care
însumează exact h.
Dacă nu îl găsesc,
căutarea binară îmi spune nu numai
că nu este acolo,
dar îmi spune
care
sunt valoarea anterioară și următoare.
Deci, deși h
minus si nu este acolo,
pot obține următorul lucru cel mai mare
și următorul lucru cel mai mic.
Ceea ce vreau este
următorul lucru cel mai mic.
Și asta va fi cea mai mare
sumă pe care o pot obține folosind si.
Și atunci acesta este un
candidat pentru o sumă mai mică
sau egală cu h.
Vreau să-l găsesc pe cel mai mare.
Așa că fac o buclă for.
Întotdeauna țin evidența...
Iau o listă cu toți
candidații pe care i-am primit.  De
fiecare dată când fac o iterație a
acestei bucle, primesc un candidat.
Apoi o iau pe cea mai mare.
OK, deci returnează cel mai mare candidat.
Deci asta îmi oferă un candidat,
doar articolul anterior.
Acesta este ceea ce am numit găsiți
anterior sau găsiți anterior,
probabil, în interfața noastră setată.
Și dacă aveți un set sortat,
puteți face asta în log n time.
Deci aceasta este o soluție n log n,
deoarece facem n iterații
prin buclă.
Fiecare căutare binară ia log n.
Vreau să devin liniar.
Acest lucru nu este evident.
Cea mai bună intuiție la care mă pot
gândi pentru această idee următoare
este, ei bine, încep cu
cel mai mic articol din S.
Și vreau să rezumam la
ceva care este cam mare,
nu?
Am aruncat toate
obiectele mai mari decât h.
Dacă s0 este ca mic,
ca aproape de 0,
pentru că este cel mai mic
, atunci poate ar
trebui să mă uit la
sfârșitul matricei,
pentru că vreau să
compar, sau vreau
să adaug cel mai mic
lucru probabil
cu cel mai mare lucru.
E cât de aproape
îmi pot imagina.
Deci... deci iată S-ul meu sortat.
Este cel mai mic articol, cel mai mare
articol.
Așa că voi trece peste
aceste elemente unul câte unul.
Deci, să începem prin a-l compara pe
primul cu ultimul.
Algoritmul cu două degete, ok?
Aceasta este ideea mare.  O
faci tot
timpul la această clasă.
Este super util.
Am văzut-o în sortări de îmbinare, de
exemplu, și îmbinând două liste.
Avem degete în două
liste care avansează.
Și pentru că doar avansează,
este nevoie de timp total liniar.
Așa că vom face acest tip
de pliat în spate aici.
Vom începe aici.
Acesta pare a fi un
candidat bun pentru început.
Acum, cu ce altceva
ar putea adăuga asta?  Ei
bine, poate articole mai mici.
Și poate că trebuie să trec până
aici.
Și apoi trebuie să
avansez cu degetul stâng.
Da, OK.
Deci iată ideea.
Deci, să ne uităm la...
așa că voi numi acest
deget i și acest deget j.
Deci vrem să însumăm două lucruri.
Deci, cred că o altă
inspirație aici este că
vrem să adăugăm două lucruri.
Și avem un algoritm
care conține cuvântul „doi”.
Și este
algoritmul cu două degete.
Deci hai să încercăm asta.
Deci vom
începe de la i egal cu 0
și j este egal cu n minus 1. Ne vom
uita la si plus
sj și vom vedea, cât de bun este?
Cât de aproape de însumarea la h este?
Ei bine, în special, este
fie mai mic sau egal cu h,
fie mai mare decât h.
Dacă este mai mare decât h...
deci această sumă este prea mare.
Nici măcar nu-l pot folosi
ca candidat.  Ei
bine, asta înseamnă că chiar
nu am nevoie de tipul ăsta, nu?
Este prea mare per total.
Adaug cel mai mic
articol la acest articol.
Și e prea mare.  Ei
bine, atunci ar trebui să
merg la stânga.  Ar
trebui să-mi mișc
degetul drept spre stânga.
Deci, în acest caz, decrementăm j.
Mutați
degetul drept spre stânga.
Deci, bănuiesc că, în acest
caz, incrementez i.
De ce?
Dacă adun aceste două elemente
, iar acesta este prea mic,
este mai mic decât h, atunci acest
element probabil era prea mic.  S-ar
putea de fapt...
este o soluție OK.
Este mai mic sau egal cu h.
Așa că ar trebui să-
l păstrez ca candidat.  Să
spunem că adăugați un candidat.
Așa că voi păstra o
listă de candidați pe care îi văd.
Deci aceasta este o posibilă soluție.  S-ar
putea să nu fie cel mai bun.
Dar este unul de adăugat pe lista mea.
Și apoi voi crește i
și acum voi lucra la această sub-matrice,
pentru că va fi
puțin mai mare.
Nu pot merge în acest fel ca să-l
fac mai mare,
pentru că sunt la ultimul articol.
Și nu este evident
că acest lucru funcționează.
Cred că există un invariant frumos
care va ajuta undeva.
Unde mi-am pus bucata de hârtie?
Da.
Deci iată un invariant.
O da.
Este foarte clar că acesta
este lucrul corect
de făcut în primul pas.
Și partea dificilă este să argumentez
că funcționează în toți pașii,
pentru că atunci când am într-adevăr
cel mai mic și cel mai mare
articol, e clar că ar trebui să
avansez pe unul sau pe altul
dacă sunt prea mic sau prea mare.
Dar modalitatea de a demonstra acest lucru
în general prin inducție
este de a arăta acestui invariant că --
deci la un moment dat
prin această execuție,
i și j sunt undeva.
Și vreau să spun că, dacă
iau orice j de la dreapta -
orice j prim la dreapta lui
j și orice i prim la stânga
lui i, nestrict, atunci
toate acele perechi,
toate acele sume pe perechi,
sunt fie prea  mare--
și atunci scădem j--
sau sunt mai mici sau egali
cu cel mai mare candidat pe
care l-am văzut până acum.
Asta pentru că am adăugat
acești candidați acolo.
Deci, acel invariant va
ține prin inducție,
pentru că ori de câte ori există un
lucru posibil care este bun,
îl adaug pe lista mea de candidați.
Și apoi, la sfârșitul
algoritmului,
parcurg
lista mea de candidați, calculez maximul,
returnez acea pereche.
OK, deci acesta este un
algoritm cu două degete,
care rezolvă
problema non-exactă
în cel mai rău caz liniar.
Da?
PUBLIC: nu pot
egala j, nu?
ERIK DEMAINE: Oh, nu
pot... corect.
Deci care sunt
condițiile de reziliere?
Când i este egal cu j,
probabil că atunci vrei să te oprești.
Depinde.
Ai putea spune, dacă i este
mai mare decât j, oprește-te.
Returnează max candidat.
Există două moduri de a
interpreta această problemă.
Una este că cele două
valori pe care le alegeți în S
trebuie să fie
valori diferite sau le
permiteți să fie aceeași valoare,
ca și cum ar putea fi ambele h peste 2.
Și oricum este mai
ușor de rezolvat.
Dacă doriți să permiteți
s peste 2, atunci
aș pune mai mare decât aici.
Dacă nu doriți
să permiteți h peste 2,
atunci aș pune mai mare
decât sau egal cu...
oricum.
Ambele probleme, le
puteți rezolva în ambele moduri.
Sau ambii algoritmi pot
face față ambelor situații.
OK, încă o problemă.  În
regulă.
Da, nu am timp.
Dar devin din ce în ce
mai repede.
Desigur, la cea mai
grea problemă, o
pot face cel mai rapid.
În regulă, deci Meff Ja...
aceasta este o referire la Jeff
Ma din echipa MIT Blackjack
, despre care am avut să vorbesc aici
la LSC cu câțiva ani în urmă.
Dar apare în
filmul 21 și așa mai departe...
ficționalizat.
Deci jucam acest joc.
Este o configurație grozavă.  Cu
siguranță ar trebui să
citiți această problemă...
Po- k -er.
Și are un pachet de
cărți, unde fiecare carte are
o literă a alfabetului pe ea.
Bănuiesc că acesta este
drumul corect.
Deci, desigur,
am o astfel de punte.
Nu toată lumea?
Puteți cumpăra acestea.
Am mai multe, de fapt.
Și astfel putem face un
truc de magie rapid,
cum ar fi să alegem o carte, orice
carte... aici, alege o carte.
[INAUDIBIL] OK, alegere bună.
Nu pot forța, așa că
nu prea contează.
OK, și deci acesta este
cardul tău, nu?
Și cardul tău este un s, nu?
OK bine.
Nu, nu toate cărțile sunt ale lui.
[Râsete]
Dar are oglinzi
în ochelari.
Nu.
Pot dezvălui mai târziu
cum se face asta.
OK, deci un pachet de cărți.
Fiecare card are 26 de
litere posibile pe ea.
Și există acest
proces ciudat de tranzacționare.
Chiar și doar definirea
acestei probleme
va dura puțin.
Oh, iată bucata mea de hârtie.
Deci avem acest proces de tranzacționare.
Iată un exemplu care se află
în program, abcdbc.
Deci știți
ordinea cărților.
Aceasta este cartea de sus.
Acesta este cardul de jos.
Și acum, la întâmplare, faci o tăietură.
Cut este asta.
Așa că iau o bucată din
partea de sus, o mut în jos,
o dată, la întâmplare.
Deci, de exemplu, aș
putea lua această tăietură.
Și apoi, ceea ce aș obține
este cdbc pentru această parte care este
copiată aici și ab ca...
deci acesta este... deci primul
lucru pe care îl facem este să tăiem la i.
Aceasta este pozitia I.
În acest exemplu, i este egal cu 2.
OK, atunci împărțim
primele k cărți.
Deci, să presupunem că împărțim
primele patru cărți, k este egal cu 4.
Deci, aceasta este împărțirea k.
Deci obținem cdbc, în această ordine.
Dar ordinea nu contează,
pentru că ultima operație pe care o
facem în problemă este
sortarea lor, care este bccd,
așa cum o faci când
primești o mână de cărți.  Ai
tendința să le sortezi.
OK, deci acesta este un proces.
Dată o punte... deci
puntea aici este reparată.
Numim acest proces,
cred, P din D virgulă și virgulă k.
Ni se spune ce este D.
Ni se spune ce este k.
i este ales aleatoriu.
Și am dori să știm ce
se întâmplă cu diferite i-uri.
Deci, dacă te uiți suficient la această problemă
, începe să se simplifice.
Deci, aceasta este o configurație complicată.
Dar ceea ce se întâmplă cu adevărat este că
începem de la poziția i.
Și luăm următoarele k
cărți de acolo în mod ciclic.
Așa că aici, tocmai le-am
luat pe cele patru.
Dacă i ar fi egal cu 3, am avea
d, apoi b, apoi c, apoi a.
Dar apoi le sortăm.
OK, deci obținem diferite
subșiruri de lungime k,
ciclic.
Dar apoi
sortăm acele scrisori.
Sortarea este cu adevărat
crucială pentru ca această problemă
să fie deloc fezabilă.
Mi-a luat ceva timp chiar și să
văd cum să rezolv această problemă.
Dar cheia este sortarea,
că acestea sunt sortate,
pentru că asta înseamnă... pentru că
noi sortăm,
nu contează dacă
aveți aaba, baaa sau abaa.
Acestea sunt toate la fel.
Dacă iei aceste
cărți împărțite,
le triezi după
același lucru, care este
cel pe care nu l-am scris eu, aaab.
Toate acestea sunt ordonate
la același lucru.
Așa că am pierdut unele informații
când am sortat, am pierdut comanda.
Prima întrebare
pentru a vă face să vă gândiți
în această direcție, partea a,
spune, construiți o structură de date
date D și k care să-mi spună,
având în vedere doi indici, i și j,
ajung cu
exact aceeași mână?
Acest lucru se numește mână.
Și este exact acest P D, i, k.
Deci vreau să fac P D,
i, k și P, d, j, k.
Și vreau să știu...
JK.
Și vreau să știu dacă
acele două lucruri sunt
egale în timp constant.
Asta spune asta...
timp constant.
Nu spune cel mai rău caz,
dar cel mai rău caz este posibil.
Și asta sună greu,
pentru că, vreau să spun,
există k simboluri pentru unul
dintre ei, alți k simboluri
pentru celălalt tip.
Dar nu trebuie să
comparăm simbolurile.
Trebuie doar să comparăm
sortarea acelor șiruri.
Și asta, o putem comprima.
Deci aceasta este o subtilitate.
Dar tot ce trebuie să știu
este că aici sunt trei a,
și un b și zero
c, și zero d și zero e
și așa mai departe.
Dar pentru că există doar
26 de litere în acest pachet -
și într-adevăr, în acest pachet, se
întâmplă cu litere mari și mici de la
z la z.
Dar s-ar putea să avem n cărți.
Dar există doar
26 de etichete posibile.
Deci, de fapt, multe
dintre ele vor
fi egale dacă n este mare.
Deci, aceasta este o
schemă bună de compresie,
deoarece pentru a reprezenta lucrurile pe care le
obțin după sortare,
trebuie doar să vă dau 26 de numere.
Și pentru noi, 26 este mic,
pentru că 26 este o constantă.
Indiferent de numărul de
cărți, trebuie doar să spun,
câte a sunt?
Ar putea fi oriunde
între 0 și n.
Câte b-uri sunt?
Între 0 și n.
Câte c sunt?
Între 0 și n.
Deci 26 de numere în
intervalul 0 la n--
Îmi place să mă gândesc la asta ca la o
bază de numere de 26 de cifre n plus 1.
O putem mapa
în baza n plus 1.
Și obținem 26 de
cifre în acea bază.
Un alt mod de a spune este
că numărul de
combinații posibile aici - câte
a, câte b, câte
c - nu
este nici măcar theta.
Este n plus 1, orice între
0 și n, la puterea lui 26.
Acesta este un polinom bun.
Așa că pot face lucruri
precum radix sort.
Misto.
Așa că permiteți-mi să rezumam
puțin cum rezolvăm partea a.  Așa
că vreau să construiesc o
structură de date, adică,
pentru fiecare valoare i,
știu că voi
ajunge să servesc aceste patru
carduri sau, în general, k carduri.
Deci, pentru acele carduri,
aș dori să calculez
câte a, câte b,
câte c sunt?
Și apoi
notează acest număr.
Acesta este un număr pe
care îl pot scrie
în cel mult 26 de cuvinte, deoarece
putem reprezenta numere între 0
și n într-un singur cuvânt.
Aceasta este w este cel
puțin log n ipoteza.
Deci are dimensiune constantă.
Într-un
număr constant de numere,
pot reprezenta tot ce trebuie să
știu despre un lucru de mărime--
de lungime k aici.
Deci nu trebuie să știu
ce litere sunt unde.
Trebuie doar să știu
ordinea sortată.
Deci trebuie doar să știu -- asta
se numește un tabel de frecvență --
câte a, câte b?
Și deci, dacă pot să le calculez,
atunci având în vedere acea reprezentare
pentru a începe de la i și
având în vedere acea reprezentare
pentru a începe de la j,
să zicem, care ar
fi aceste două și acestea
două, le pot compara
doar comparând
acele 26 de numere.
Dacă toate sunt
egale, atunci sunt
același șir după sortare.
Și dacă există vreo diferență,
atunci sunt diferite.
Așa aș putea
face asta în timp constant
dacă pot calcula
aceste reprezentări.
Și nu este greu să faci asta.  Se
numește o tehnică cu ferestre glisante
, în care o calculezi
pentru primii k băieți.
Și apoi eliminați acest
articol și adăugați acest articol.
Și doar prin creșterea
contorului pentru b,
scăderea
contorului pentru a, acum
știu reprezentarea
pentru acești tipi.
Faceți o copie a acesteia, care este
o copie a acelor 26 de numere,
constantă.
Apoi adaug pe c, elimin b.
Apoi adaug pe a, elimin c,
adaug pe d, elimin d, adaug pe c
, elimin b și adaug pe
d și elimin c.  Ei
bine, m-am întors
la început.
Deci acum am
reprezentare a acestora.
OK, așa că glisând
această fereastră, mă
schimb doar la cele două capete.
Adaug un tip.
Eu cresc unul
dintre aceste contoare.
Am decrementat unul
dintre aceste contoare.
Deci, în timp constant,
având în vedere reprezentarea
unuia dintre aceste subșiruri,
pot calcula reprezentarea
următorului.
Și așa,
în timp liniar,
pot construi o astfel de
structură de date care să-
mi permită să spun dacă
oricare două mâini sunt egale.
Următoarea problemă,
partea b, este, având în vedere
toate aceste
reprezentări, puteți
găsi care dintre ele este cea
mai comună?
Pentru că am ales
i uniform la întâmplare,
vreau să știu care este cea mai
probabilă mână pe care o obțineți.
Și cred că
cel mai simplu mod de a spune
acest lucru este că poți face
asta prin sortarea radix.
Tu iei toate aceste
reprezentări.
Sunt numere frumoase
în intervalul de la 0
la n plus 1 la puterea a 26-a.
Așa că pot rula radix
sort și le pot sorta pe toate.
Și apoi, cu o singură
scanare prin matrice,
pot vedea care dintre ele
este cea mai comună.
Sau, mai degrabă, pot...
într-o singură scanare, pot calcula,
OK, câte dintre aceleași lucruri
sunt în față?
Dacă sunt sortate, atunci toate
cele egale vor fi împreună.
Deci câți sunt?
Atunci câte egale mai departe?
Și câte egale mai departe?  De
fiecare dată, comparând fiecare
articol cu ​​cel anterior.
Apoi primesc numărătoare de frecvență
pentru toate aceste mâini.
Și apoi fac o altă scanare
pentru a găsi cea mai comună.
Și pot face o altă scanare pentru a
găsi cea mai bună din punct de vedere lexical,
ultima din punct de vedere lexical.
Și așa
rezolvi problema 5.