JASON KU: Eu sunt Jason.
Sper că
m-ați văzut marți.
Aceasta este prima noastră
sesiune cu probleme 6.006 pe
care o vom avea
vineri în acest trimestru.
Este într-adevăr un experiment.
Nu am mai făcut asta până acum.
Dar unul dintre lucrurile despre care am
fost discutat în timpul pregătirii
pentru această clasă este că
avem două metode diferite
de instruire, formal, de
obicei în această clasă -
o prelegere, care este
acolo pentru a vă prezenta
materialul fundamental,
structurile de date,
și algoritmii care stau la
baza, fundamentul ce--
cum veți aborda
problemele din această clasă;
și apoi seturile de probleme la
care veți lucra,
aplicațiile noastre
ale materialului respectiv.
Dar, de obicei, există
o senzație mult diferită
între acele probleme pe
care ți-o vom oferi apoi

materialul fundamental de bază.
Deci aplicarea
acelui material se
va simți foarte diferit.
Și de multe ori,
există trucuri
pentru abordarea problemelor
sau modalități de abordare
a problemelor pe care
trebuie doar să le
înțelegi
lucrând la problemă,
uneori mergând la orele de birou.
Dar ceea ce dorim să
facem în acest termen a fost să...
deoarece am avut ocazia
să fim înregistrați de OCW,
a fost să ne înregistrăm trecând prin
unele probleme pe
care le-am avut în
seturi de probleme în trecut,
astfel încât să puteți vedea cum
ne-am aborda.
lucrând la aceste probleme la
care veți lucra,
cel puțin într-un mod similar.
Deci acesta este scopul
acestor sesiuni cu probleme.
În trecut, pentru OCW, am
înregistrat o recitare,
dar am simțit că aceasta a fost puțin
utilă pentru voi,
băieți, deoarece
recitarea este menită
pentru interacțiune, întrebări--
întrebări unu-la-unu.
Vrem să fim un
spațiu sigur pentru a
interacționa cu
materialul cu...
într-un mediu mai mic,
care ar putea să nu fie înregistrat.
Așa că acesta este scopul acestei--
aceste sesiuni pe care le vom
face vineri.
Aveți întrebări despre ce vom
face astăzi?
BINE.
Deci avem o fișă
aici, lângă ușă, pe care s-ar putea să o
avem sau nu în viitor.
Acesta este tot un
experiment, așa că va
trebui să lucrați cu noi pe măsură ce
descoperim aceste lucruri.  Au
fost postate pe LMOD cu aproximativ
o oră înainte de această sesiune.
Vom încerca să păstrăm
asta ca standard.
Dar vă arată doar
întrebările la care vom
lucra astăzi
în sesiune.
Nu este doar problema
stabilită din ultimul trimestru.
Este o selecție de probleme
din termenii anteriori,
iar unele dintre ele
au fost editate
pentru a fi poate puțin mai scurte
și lucruri de genul ăsta.
Deci ceea ce vom
face este să
trecem prin
probleme una câte una.
Voi încerca să vă arăt cum
abordez problemele,
dar în orice moment, dacă
doriți, puteți pune întrebări.  Asta e
bine.
BINE?  În
regulă, deci prima
întrebare pe care o avem este --
are o configurație care este
foarte asemănătoare cu cea pe care o
veți avea pe Pset1.  În
esență, spune că
are de obicei multe părți.
Acesta are două părți, o
parte A și o parte B.
Am omis un B
și un C care se
aflau în setul de probleme al termenului trecut.
Și are cinci funcții
fiecare, iar tu încerci
să le ordoni crescând ca... pe
baza
comportamentului lor asimptotic.
Deci, iată care sunt
funcțiile pe care le avem.
Poate o voi lipi în schimb.
Bine, deci avem
câteva seturi de funcții
și vrem doar să le comandăm.
Și unele dintre funcții pot
fi echivalente asimptotic --
în acest caz, atunci când
comandăm aceste lucruri,
vom pune
acele numere într-un set.
Deci, ceea ce avem ca
exemplu sunt trei funcții -
n, rădăcina n și n plus rădăcina n.
Acesta este unul, doi, trei.
Și ceea ce
vă vom cere să faceți
este să ordonați acele funcții
pe baza complexității lor asimptotice.
Așa că sperăm că îl
puteți obține pe acesta.
Care este cea mai lentă
creștere în termeni--
rădăcina n, deci numărul doi.
Deci, dacă spunem f din 2
va fi primul nostru.
Și apoi, ce zici de
ceilalți doi?
STUDENT: [INAUDIBIL]
JASON KU: Sunt la fel.
Ambii sunt ordinul n.
Deci am pune între
paranteze f1 și f3.
Și pe setul tău de probleme, dacă ai
pune doar 2, și 1 și 3 aici,
probabil că ar fi bine.
Dar dacă ar fi să
pui 2 aici sau să nu
ai aceste
bretele pe aici,
acestea nu ar fi corecte și
ai avea puncte marcate.
Are sens?
OK, deci vom aborda
primul set de probleme -
primul set de funcții,
care este puțin
diferit de
al doilea set de funcții.
Sper că acesta este
puțin mai ușor.
Una dintre
abordările comune pe care le am
în trecerea prin aceste lucruri --
unele dintre acestea sunt într-o
formă care îmi este greu
să spun cum s-ar
compara cu alte lucruri.
De fapt, cele mai multe dintre acestea
sunt în regulă, dar în general...
poate cineva, doar aruncând o
privire, să-mi spună
o comandă care funcționează pentru ei?
Da?
STUDENT: OK--
JASON KU: Acest lucru este
puțin dificil
de făcut la fața locului
cu cinci funcții.
STUDENT: Da.
Puțin nesigur în privința f1.
JASON KU: OK.
STUDENT: Dar f5 este cu siguranță
mai mic decât f2, care este...
mai mic decât f2 care
este mai mic decât f4.
Și f1 în dublă.
JASON KU: OK, grozav.
Asta e excelent.
Deci, ceea ce avem aici
este, pe f2, f3 și f5,
aveți într-un fel
acest n termen principal.
Dacă factorăm un n din asta,
atunci comparăm log cu...
practic, ne uităm aici
la funcția polinomială.
Acesta este cel mai mic dintre
ele, iar apoi factorul log
este mai mic decât un
factor polinomial.
Buștenii crește mai lent decât liniar.
Și astfel acest tip este mai mic
decât f2 este mai mic decât f3.
E grozav... a
spus colegul tău.
Sperăm că s-a dovedit în
recitarea de astăzi -
nu, miercuri - acest fapt frumos,
cred, că a este mai mic decât,
asimptotic,
acest polinom -
acest log n la orice putere
este asimptotic mai mic
decât orice polinom pentru
orice pozitiv a și b.
Și în special, există
de fapt un lucru mai puternic pe care îl
poți spune, care este o mică.  Ați
vorbit despre
micul o în recitare?
Probabil ca nu.
Este cam la fel ca
O mare, cu excepția că este O mare minus theta.
Deci lucrurile care sunt
echivalente asimptotic
nu vor fi
incluse în acest set.
Deci, de fapt, aceste
lucruri sunt strict
asimptotice - cresc
strict asimptotic
mai lent decât orice polinom.
Are sens?
BINE.
Deci, cunoscând această identitate,
sau această relație,
putem spune ceva despre f1?
Poate altcineva...
STUDENT: Oricare a și b, nu?
JASON KU: Orice a și b--
orice a și B pozitiv-- mai are
cineva o ghicire?
Da?
STUDENT: Acel f1
este mai mic de f5--
JASON KU: Da, f1 este
mai mic de f5, nu?
Pentru că doar folosind acea
identitate, asta-- îmi pare rău--
un aici care a șters, prostește,
este mai mic decât, să zicem--
acesta este mai mare decât n, iar n
la b, fiind 1, este mai mare.
Și apoi, așa cum a subliniat colegul tău
mai devreme,
acest lucru este exponențial,
deci cu siguranță mai mare
decât un polinom.
OK, deci a fost
foarte ușor, nu?
Deci răspunsul aici
este, dacă am primit --
dacă îmi amintesc corect, f1,
f5, f2, f3 și apoi f4 --
grozav.
Deci acela a fost destul de ușor.
Ce zici de b-- sau d, cred?
Da?
STUDENT: Pot doar o
altă întrebare...
JASON KU: Sigur.
STUDENT: [INAUDIBIL] Cum ați
proceda pentru a demonstra asta?
JASON KU: Cum ai
proceda pentru a dovedi asta?
Deci există o dovadă în
fișa de recitare acolo.
Metoda prin care au demonstrat
că în fișa de recitare
a fost punerea celor două -
luând un raport dintre
cele două funcții
și luând limita lor
pe măsură ce n merge la infinit.
Și dacă cel de sus--
crește în mod arbitrar, atunci cel de
sus ar fi--
crește asimptotic mai repede.
Și dacă ar ajunge
la 0, cel de jos
ar crește
asimptotic mai repede.
Și dacă ar merge la
o constantă, atunci
aceasta ar fi
echivalentă asimptotic.
Are sens?
De fapt, pentru a face
limita mai ușor de luat,
luăm limita
logaritmului raportului.  Pur și
simplu a făcut totul mai ușor.
Are sens?
OK, deci să trecem la b.
b-- avem un polinom
și un exponențial
și apoi avem aceste
lucruri aici jos.
Ce înseamnă aceste lucruri
din paranteze?
STUDENT: Alege.
JASON KU: Alege, corect.
Este un coeficient binom.
Știe cineva care
este coeficientul binom?
Da?
Sperăm că de la
6.042 sau ceva de genul
ăsta, sau oricare ar fi experiența
dvs. de matematică în competiție,
dar, în general,
avem această definiție.
Chestia asta ce?
Își amintește cineva?
Ce înseamnă n alege k?
Da?
STUDENT: Numărul de moduri
de a alege k obiecte din n
[INAUDIBIL]
JASON KU: Da,
numărul de moduri de a alege
k obiecte din n lucruri--
Nu îmi amintesc niciodată această formulă.
Și probabil, mulți dintre voi
ați memorat această formulă.
Nu am de gând să-
ți cer s-o faci.  Am să
vă spun
cum cred eu despre asta.
Ce se întâmplă dacă vreau să știu
numărul de permutări ale lui n
alege k-- sau vreau să spun de n?
Îmi pare rău.
Câte permutări
există pentru n elemente?
Ce este asta?
Este doar n factorial, nu?
Deci ceea ce facem aici este că
am dori să alegem
un număr n de lucruri.
Am n moduri factoriale diferite
de a le alege,
dar, în esență, aici
și aici, k și n minus k--
Nu prea îmi pasă
care este ordinea lor.
Așa că voi
împărți permutările
acestor lucruri și ale acestor lucruri.
Are sens?
Deci formula de aici, așa
cum mi-o amintesc,
care sper că este corectă,
este n minus k factorial.
Așa că primesc toate
permutările întregului lucru
împărțit de constituenții lor.
Are sens?
Am făcut asta corect?
OK, mișto... deci este
o transformare frumoasă.
Deci, primul pas este să scrieți
acestea în termeni de factoriali.
Asta nu mă ajută cu
nimic, pentru că nu știu
cât de mare se bazează factorial--
cu privire la
celelalte lucruri.
Știe cineva cât de
mare este factorial?
Da?
STUDENT: Puteți folosi
aproximarea lui Sterling.
JASON KU: Puteți folosi
aproximarea lui Sterling.
Deci e frumos.  Își
amintește cineva care
este aproximarea lui Sterling?
Nu.
Nici eu nu-mi amintesc.
Mereu trebuie să caut.
Aproximația lui Sterling spune că
n factorial este aproximativ -
și acest lucru aproximativ
este mult mai puternic
decât un comportament asimptotic.  De
fapt, pe măsură ce aceste lucruri--
pe măsură ce n se apropie de infinit,
aceste lucruri sunt egale.
Limita este identitatea.
Dar aproximarea
este rădăcina pătrată
a lui 2 pi n n/3 la n.
OK, e distractiv.
Deci, ce fel de creștere este aceasta?
Super rău, nu?
Este cu siguranță exponențial
sau mai mare decât exponențial.
Este n la n--
ceva de genul asta--
împărțirea unui e--
aceasta este e, baza
logaritmului natural.
Și aceasta este o
constantă, la fel și pi.
Pi este o constantă - un
fel de interesant
că avem două
numere transcendentale aici.
E un fel de matematică distractivă.
Sunt sigur că cineva... unul dintre cei
6.042 de instructori ai tăi îți
poate spune de ce.
Nu pot să-mi dau
capul acum.
Dar aceasta este o aproximare
foarte bună.
Și de fapt,
uneori, alții
vor crede - asta este ceea ce oamenii
numesc aproximarea lui Sterling.
O noțiune mai slabă, care
uneori vă este utilă
este că, dacă luați
logaritmul ambelor părți,
asta este asimptotic ce?
Dacă aș lua jurnalul
acestui lucru--
STUDENT: Polinom--
JASON KU: Este un
lucru polinom.
STUDENT: [INAUDIBIL]
JASON KU:
Practic este n log n.
Dacă luăm un jurnal din chestia asta,
ar fi diverse lucruri.
Bine, hai să o facem.
2 pi n n/e la n--
deci atunci când suntem în interiorul unui
logaritm, înmulțirea-- o
putem împărți--
devine adunare.
Împărțirea devine scădere.
Și acest lucru crește mai repede
decât toate celelalte lucruri,
așa că le putem ignora atunci când
le adăugăm asimptotic.
Și deci ceea ce ajungem să
obținem este acest n la n.
N iese
pe logaritm
și obțineți ceva care
este theta n log n.
Oh, e distractiv.
Acesta este ceva ce am putea
folosi mai târziu în clasă.
Bine, dar când
comparăm aceste funcții,
unul dintre lucrurile frumoase
de făcut este să le transformăm
în ceva
care ne este familiar,
astfel încât să
le putem compara cu ușurință.
Deci, aici, acest lucru este
oricare ar fi acel lucru, aproximativ
rădăcină pătrată n n/e la n.
Acesta este, am să
spun, theta.
Asta e un pic
mai precis.
Bine, atunci cum rămâne cu
aceste două lucruri?  Să
începem cu cel de jos.
Poate cineva să-mi spună ce
este asta, asimptotic?
Da?
STUDENT: n cub--
JASON KU: n cub-- de
ce?  Ei
bine, dacă conectăm aceste lucruri
în definiția respectivă aici,
avem n factorial peste 3
factoriali n minus 3 factoriali.
n factorial peste n
minus 3 factorial
ne lasă doar
un n, un n minus 1
și un n minus 2 peste 6.
Și dacă înmulțiți
toate acestea,
termenul principal este un
n cub, deci acest lucru
este asimptotic n cub.  .
Am sărit câțiva pași,
dar sper că ați
putea urma asta.
Și apoi ultimul lucru care
rămâne este acesta chiar acolo.
Acela e un pic cam complicat.
Vrea cineva să mă ajute aici?
Ceea ce putem face este să
o putem lipi în această formulă
și apoi să aplicăm
aproximarea lui Sterling
pentru a înlocui factorii.
Are sens?
OK, deci ceea ce voi face este să
facem asta în doi pași.
Acesta va fi
n factorial peste...
ce este asta?  n/2
factorial-- și atunci
cât este n minus n peste 2?
Acesta este, de asemenea, n/2.
Deci, acesta va fi
n/2 pătrat factorial.
Este ok?
Da?
Acum să înlocuim aceste lucruri
cu aproximarea lui Sterling
și să vedem dacă putem simplifica.
Deci, în partea de sus, avem 2
pi n n/e la n peste--
și apoi avem
un pătrat aici, pi n.
Am anulat 2--
n/2 peste e la n/2.
Am făcut asta corect?
BINE.
Nu pot scrie și
de multe ori,
fac erori de aritmetică, așa că
prinde-mă dacă fac una.
OK, deci haideți să simplificăm
acest jos aici.
Nu am de gând să
rescriu partea de sus.
Partea de jos... îl
îndreptăm pe tipul ăsta.
Este pi ori n.
Și apoi tipul ăsta, n/2 pătrat--
care rămâne este un n.
Apoi avem n/2 la n/e--
ceva de genul ăsta.  n/2 peste
e la n-- asta mă face mai
fericit.
OK, deci acum avem
asta peste asta.
Cum simplificăm?  Ei
bine, putem anula
unul dintre rădăcinile n.
Deci avem rădăcina pătrată a lui pi
n aici jos și rădăcina pătrată a lui 2
sus.
Și atunci ce avem?
Avem n la n jos aici
și n la n jos... acolo sus,
așa că acestea se anulează.
Am luat 1 peste e la n,
1 peste e la n acolo sus.
Acele se anulează.
Ce mai rămâne în acest termen,
când... după ce anulăm?
1 peste 2 la n la
numitor, care este
2 la n la numărător -
deci acest lucru este ceea ce
este corect.
Asimptotă.
Putem scăpa de
aceste constante.
Și este rădăcina n--
Adică, este 2 la n
peste rădăcina n, asimptotic.
Are
sens, toată lumea?
BINE.
Cu aceste cunoștințe -- și îmi pare
rău pentru munca mea dezordonată la bord --
care este ordinea
acestor funcții atunci?
Ma poate ajuta cineva?
Altcineva... Eric, îmi pare rău.
Nu poți răspunde.
Haide, băieți.
Ai urmat ce am spus.
Începeți-l pentru mine.
STUDENT: Cred că [INAUDIBIL]
f2 și f5 [INAUDIBIL]
JASON KU: Corect.
Deci ambele lucruri sunt
echivalente asimptotic,
așa că ar trebui să
le punem între paranteze -
f2, f5.
STUDENT: Și atunci ar
merge f--
[INAUDIBIL] 3.
JASON KU: f3.
Aceasta?
De ce acesta?
STUDENT: Nu contează.
JASON KU: Îți cer doar
să justifici ceea ce spui.
STUDENT: Ei bine, pentru că simt
că avem [INAUDIBIL]
JASON KU: Uh-huh.
STUDENT: [INAUDIBIL]
JASON KU: Acesta
este cel mai mare?
STUDENT: [INAUDIBIL]
JASON KU: f4 este
cel mai mare, nu?
Deci acesta este cu siguranță
mai mare decât acesta,
pentru că este n la n,
spre deosebire de 2 la n.
Deci, pentru orice n mai mare
de 2 plus e
este destul de evident
că este mai mare.
STUDENT: Deci nu ar
fi f3 înainte de f1?
JASON KU: De ce ar
fi f3 înainte de f1?
STUDENT: [INAUDIBIL] 2 la
n împărțit la [INAUDIBIL]
JASON KU: Dar împărțim
la un factor polinomial, nu?
Deci va fi
mai lent asimptotic
decât primul de acolo.
Deci ai inteles bine.
Ce este?
F3, f1 și f4--
OK?
Cool-- deci este
puțin complicat,
dar doar aplicând niște
reguli de logaritm și exponent,
înțelegând că
factorii logaritmici cresc mai lent
decât cei polinomi
și, din nou, cresc mai lent
decât cei exponențiali.
Și posibilitatea de a face unele
transformări ale unora
dintre aceste
mărimi matematice pentru a le obține
într-o formă polinomială

este modul în care veți
aborda aceste probleme.
Are sens?
În regulă, deci vom
trece la întrebarea 2 acum.
Da, ai o întrebare?
STUDENT: Da,
am o întrebare.
Ce ai spus că
este legatul theta pentru 4?
JASON KU: Theta legat pentru 4?
Acest băiat?
STUDENT: [INAUDIBIL]
JASON KU: Deci doar atât.
Nu știu cum să
simplific asta mai mult.
Aveți un
factor polinom aici,
și atunci acesta este un termen n la n
împărțit la un exponențial.
Da?
STUDENT: Pentru f3,
care ai făcut--
cum ai redus--
care este f3 [INAUDIBIL]
JASON KU: f3 a luat acest
mic ciclu aici.
Ceea ce am făcut a fost că am
extins definiția

coeficientului binomial aici.
Apoi am aplicat
Sterling, apoi am
simplificat și ne-am întors.
Are sens?
Da?
STUDENT: [INAUDIBIL]
JASON KU: Sigur.
STUDENT: Există vreun motiv pentru
care f3 este înainte de f1?
JASON KU: De ce este f3 înainte de f1?
Dacă șterg 2 și pi,
acest lucru este theta acela--
2 la n peste un
factor polinomial.
Este peste n la 1/2.
n la 1/2 crește
netrivial.
Dreapta?
Și astfel, acest lucru va reduce
timpul de funcționare al acestui lucru
cu un factor polinomial.
Te-ai putea gândi la --
înmulțim și asta cu
n la minus 1/2.
Acesta este un alt mod
de a gândi.
Alte intrebari?
Bine, deci vom trece
la problema 2, cred.
Am nevoie de o radieră.
Deci problema 2 este
o problemă cu aspect amuzant.
Scopul acestei
probleme este de a
vă face să vă gândiți la utilizarea
unora dintre lucrurile pe care le vom
folosi în această
clasă ca o cutie neagră.
Ceea ce înseamnă folosirea a ceva
ca o cutie neagră
este că are un fel de
interfață publică cu care ai
voie să lucrezi,
dar nu am voie
să văd ce se află în interiorul ei.
Și de multe ori, ceea ce
vom face în această clasă
este să încercăm să folosim o
cutie neagră și să
încercăm doar să folosim
funcțiile exterioare abstracte, astfel încât să
putem demonstra lucruri despre ea.
Putem doar să
le acceptăm ca fiind adevărate
și apoi să le folosim pentru a ne
ocupa de analiza noastră.
Deci, ceea ce ni se oferă
în această problemă
este o structură de date care susține
o interfață secvență
despre care ați auzit ieri.
Ce este din
nou o interfață secvență?
Cum depozitează articolele?
Îți amintește cineva?
Da?
STUDENT: [INAUDIBIL]
JASON KU: Ei bine, e...
OK.
STUDENT: [INAUDIBIL]
JASON KU: Bine.
Deci, ceea ce spune colegul tău
aici
este că le enumerăm într-
o matrice contiguă.
Are cineva vreo problema
cu aceasta definitie?
Da, acolo sus...
STUDENT: [INAUDIBIL]
JASON KU: OK.
Deci, unul dintre
lucrurile importante despre această clasă
este abstractizarea acestei
idei de interfață
versus o implementare.
Și ceea ce mi-a vorbit acest student de
aici de jos
despre o matrice ca
implementare de bază,
și despre ce
vorbea studentul de acolo
este o listă legată.
Acestea sunt ambele lucruri care
pot implementa acea interfață.
Dar, în realitate, interfața
este ceva abstractizat în afara
acelor idei.
Am putea implementa cu oricare
dintre aceste structuri de date.
Deci, ce face ca
interfața de secvență să fie o interfață de secvență?
Da?
STUDENT: Este în
ordine, sau cel puțin este
indexat într-un mod specific
care permite [INAUDIBIL]
JASON KU: Deci este vorba despre
datele pe care le stocăm.
Stocăm un
număr de lucruri,
iar lucrul important
este că structura de date
menține
posibilitatea de a găsi articole
din acel set, menținând
o ordine asupra lor.  De
obicei îmi place să
o numesc o ordine extrinsecă
a acestor lucruri.
Nu are nimic de-a face
cu ceea ce sunt articolele.
Are de-a face cu modul în care
le-am pus în ordine.
Există un prim lucru,
există un al 10-lea lucru,
există un ultim lucru.
Dreapta?
Asta
e corectă o succesiune de elemente.
Și deci ceea ce
face această structură de date
, aceasta este intrarea pe care o avem la
dispoziție
în această problemă, este un
fel de structură de date care
stochează o secvență de lucruri.
Și poate suporta
aceste patru operațiuni -
o inserare prima, inserare ultima,
ștergere prima și ștergere ultima.
Și susține fiecare dintre aceste
lucruri în timp constant.  Încă
nu aveți o structură de date
care să facă asta.
Veți vorbi despre
setul de probleme 1 și vom
vorbi despre o altă
modalitate de a face asta astăzi.
Dar nu ne interesează
cum este implementat.
Vă oferim doar această
cutie neagră care realizează aceste lucruri.
Da... minunat.
Și deci ceea ce încercăm să
facem este că avem acest lucru
și vreau să pot
manipula secvența stocată în
interior, dar tot ce am acces
sunt aceste operațiuni externe.
Deci ideea va fi să
implementăm algoritmi
pentru aceste
operațiuni de nivel superior
în ceea ce privește aceste
lucruri de nivel inferior care ne sunt date.
Are sens?
Și aceasta este de fapt o
întrebare destul de ușoară.
Sperăm că vom avea
unele ceva mai dificile pentru dvs. --
într-un context diferit
în setul de probleme 1.
OK, deci prima operație pe care o vom
sprijini --
sau vom încerca să o susținem --
este o operațiune
numită swap_ends.
Și ceea ce va face acest lucru
este să luăm structura de date
pe care am dat-o --
un alt mod în care ai putea face acest lucru
este să punem asta ca metodă pe acea
structură de date, dar hai să
facem asta separat --
va lua acea
structură de date pe care am  a dat--
ceea ce ți-am dat, asta înseamnă
stocarea secvenței,
ca singur argument.
Și ceea ce
vă cerem să faceți este
să descrieți un algoritm pentru a schimba
primul și ultimul element.  Era
o matrice, puteam să mă
uit doar la indexul 0, să mă uit la asta, să mă uit la
ultimul
și să le schimb.
Dar nu am acces la ceea ce este
reprezentarea de bază
, așa că cum aș face asta
folosind lucrurile pe care le
avem la dispoziție?
Aceasta este o întrebare destul de ușoară.
Ce avem?
STUDENT: Doar o întrebare rapidă.
JASON KU: Da.
STUDENT:
Metoda de ștergere returnează și tot
ceea ce șterge?
JASON KU: Da.
Da, da.
Deci, în general, dacă
aruncați o privire la
notele sesiunii, vă oferă
un mic memento frumos --
reamintim, operațiunile de ștergere
returnează elementul șters.
BINE?
Se spune chiar
acolo pe lucru.
Da?
STUDENT: Oh, am avut și eu
o întrebare.
JASON KU: Sigur.
STUDENT: Și asta
de fapt [INAUDIBIL]
JASON KU: Mm-hmm.
STUDENT: Nu este
legat de [INAUDIBIL]
dacă nu specifică un spațiu
[INAUDIBIL] înseamnă asta
[INAUDIBIL]
JASON KU: Da, deci
unul dintre lucrurile despre
care a vorbit Eric ieri
a fost, în general, la această clasă,
dacă aveți  --
de obicei, ceea ce vă vom oferi
este un timp de funcționare
legat de lucrurile pe care le-ați
cerut.
Și pentru că alocarea
spațiului de către modelul nostru
necesită acea perioadă de
timp, cantitatea de timp -
cantitatea de spațiu pe
care o folosim
va fi
limitată asimptotic superioară de timpul
pe care îl vom
folosi pentru algoritm.
Și, în general, vă vom cere
să rămâneți într-un timp limitat
și nu vă vom cere să faceți
ceva separat cu spațiul,
dar probabil că există probleme
la sfârșitul acestei unități
în care am putea vorbi
despre complexitatea spațiului.
Dar, de obicei, vom
fi foarte specifici
dacă vrem să vă
gândiți la spațiu.
Alte intrebari?  În
regulă, deci cum
implementăm chestia asta cu swap_ends?
Da.
Acesta este unul destul de ușor.
Da?
STUDENT: [INAUDIBIL] spune că
primul este egal cu [INAUDIBIL]
JASON KU: OK, deci un alt
lucru despre această clasă --
colegul tău
de aici încearcă
să-mi scrie cod, ceea ce
este grozav pentru un computer
și asta e grozav dacă
ești  luând 6.009.
Nu este grozav dacă
vorbești cu prietenii tăi
sau dacă vorbești cu mine.
Nu pot analiza codul din capul meu
și să-l compilez tot timpul.
Uneori pot, dar
nu tot timpul,
mai ales când ajunge
să fie un program mare.
Așa că vreau să-
mi explici în cuvinte
și vrem să explici în
cuvinte în trimiterile tale LaTeX
ce
face algoritmul.
Deci poți începe de la capăt
cu descrierea ta?
STUDENT: Cuvintele sunt grele.
JASON KU: Cuvintele sunt grele.
Sunt de acord cu tine.
STUDENT: Aceasta este o
clasă de informatică.
STUDENT: Aș șterge
ultimul [INAUDIBIL]
și apoi aș lua acea
valoare [INAUDIBILĂ]
JASON KU: OK.
Deci propunere... avem
o secvență de lucruri.
Din nou, așa cum făcea Eric
la prelegerea de ieri,
aceasta nu
reprezintă o matrice.
Reprezintă o secvență.
Deci acesta este
primul pe care l-am ghicit și ultimul.
Și ceea ce spunea colegul tău
era să ștergi acest tip
și să-l lipești pe față,
poate folosind ștergerea ultimului
și introducerea întâi.
Sună destul de bine.
Asta face ceea ce
face swap_ends?
Swap_ends - schimbă primul și
ultimul element din secvență.
STUDENT: Probabil că este
mai bine dacă o stocăm mai întâi
într-o altă variabilă, astfel încât să
putem obține... șterge
n [INAUDIBIL]
JASON KU: Deci ceea ce
spune colegul tău este că
am făcut cam
jumătate.  a muncii noastre.
Primul e încă aici.
Nu e bine.
Are cineva vreo
modalitate de a modifica asta?
Da?
STUDENT: Înainte de a modifica,
puteți [INAUDIBLE] pentru a modifica.
[INAUDIBIL] despre cantitatea
de lucruri pe care le stocăm.
JASON KU: Da.
Deci, cât spațiu suplimentar
putem folosi, de exemplu?
STUDENT: Cea
mai ușoară modalitate ar fi
să ștergeți ultimul
[INAUDIBIL] primul
și apoi doar, dacă
le avem deja păstrate [INAUDIBIL],
dar nu știu dacă pot
păstra două variabile diferite
în același timp.
JASON KU: Bună întrebare--
deci întrebarea-- pot
folosi spațiu suplimentar?
Și, în general, dacă
nu îți dăm
nicio restricție cu privire la ceea ce
poți stoca, atunci poți să te dezlănțui.
Faceți ce doriți, în afara
acestei structuri de date.
Unul dintre lucrurile pe care le
puteți face este să eliminați mai întâi
toate aceste lucruri, să
le stocați și o structură de date care
vă place, să
o manipulați cât de mult doriți,
apoi să introduceți mai întâi
până la capăt
și să rescrieți chestia.
Dar asta nu ne va
oferi timp constant, ceea ce
cerem.
Dar dacă nu vă spunem
altfel, nu ezitați să...
probabil, aveți voie
să stocați doar un număr constant
de lucruri, deoarece
avem timp constant,
dar, în general, dacă nu
spunem, nu,
nu puteți utiliza  spațiu suplimentar,
puteți folosi spațiu suplimentar.
BINE?
Deci cum ai face asta?
STUDENT: Probabil le-aș șterge
pe ultima și pe prima, le-aș
păstra pe amândouă, apoi i-aș
răspunde la primul, aș
răspunde la toate celelalte și
apoi i-aș răspunde la ultimul.
JASON KU: Asta e grozav.
Deci, ceea ce
spune colegul tău -- le
ștergem pe amândouă,
le stochăm în variabile temporare
și apoi, una câte una,
le inserăm pe fiecare
în
locul corespunzător folosind funcțiile
pe care le avem la dispoziție.
Bine, deci dacă ar fi să scriu un
pseudocod mic pentru asta, s-
ar putea să-l iau pe primul... L-
aș șterge mai întâi.
Chiar abuzez de
notație aici.
Asta e ok.
Înțelegi ce spun.
Ștergeți-le pe ultimele
și apoi stocați-le
în locurile respective.
Inserați în față - pe care o voi
introduce?  Care-i
treaba?
Vorbește, băieți.
STUDENT: x2--
JASON KU: x2-- da.
Mulțumesc.
Și introduceți ultimul, x1...
OK, e destul de ușor.
Da?
STUDENT: În acest
caz, ce ar fi
[INAUDIBIL] Cred că
acest lucru ar putea fi relevant.
[INAUDIBIL] Ce ar
constitui un pseudocod
față de [INAUDIBIL]
scrierea accidentală a
sintaxei Python [INAUDIBIL]
JASON KU: Bine,
deci pentru această problemă,
veți vedea soluțiile
postate la aceasta mai târziu.
În acela, am
scris o descriere
a ceea ce urma să fac și
apoi, de fapt, pentru că a
fost destul de ușor, am
notat un cod Python
pentru a face orice ar fi acest lucru.
Dar, în general,
și este de fapt
OK să scrieți Python sau pseudocod
de această formă pe seturile dvs. de probleme
, sau la un examen
sau ceva de genul.
Dar dacă nu putem înțelege
ce înseamnă variabilele tale,
dacă nu putem înțelege ce
face pseudocodul tău,
atunci asta nu este suficient.
Deci motivul pentru care
cerem cuvinte
este ca tu să poți
comunica bine acele idei.
STUDENT: Doar o
continuare a asta...
deci poți
avea și o combinație
de pseudocod și descriere?
JASON KU: Sigur.
STUDENT: OK.
JASON KU: Da,
includerea pe ambele
poate fi clarificatoare
pentru tine, potențial.
Alte intrebari?
Aceasta nu este o
întrebare atât de interesantă
din punct de vedere al algoritmului.
Aceasta este o
problemă de dimensiune constantă.
Am această structură de date.
Fac două operații.
Trebuie sa fac ceva.
Și acest lucru este atât de ușor încât nici măcar
nu voi
argumenta corectitudinea-- Nici măcar
nu va
trebui să vă argumentez corectitudinea
, pentru că
în esență facem
exact ceea ce am cerut.  De cele
mai multe ori în această clasă,
când faci ceva care
nu este banal -- mai ales când
faci ceva care
trebuie să se repete într-
un fel --
vrem să argumentezi corectitudinea.
Dar în acest caz, de exemplu,
analiza timpului este foarte ușoară.
Facem pentru operațiuni.
Fiecare durează constant
, așa că această operațiune
durează constant... gata
.
Da?  În
regulă, ce zici de
a doua operație?  A
doua operațiune măcar ne permite
să folosim puțin mai mult.
Deci
Shift_left D, K-- aceasta este
operația pe care o susținem acum
este că ni se oferă această secvență
și ceea ce vrem să facem este să luăm
primul K, aici și să-l lipim
aici în spate, astfel încât...
K du-te aici.
Deci elementul K-a ajunge
să fie ultimul element,
iar elementul K plus al 1-lea articol
devine acum primul articol.
Are sens?
BINE.  Din
nou, acesta nu este de fapt un
algoritm atât de interesant
din punct de vedere al algoritmului,
dar sperăm că este
util să vorbim despre acest lucru din
punct de vedere instrucțional.
BINE?
Deci cum as
aborda aceasta problema?
Am nevoie ca această operație să se
întâmple în ordinea K timp.
Da?
STUDENT: OK.
Deci, mai întâi, mergeți și ștergeți--
setați o variabilă x1 ca să fie
primul element d dot delete.
Apoi introduceți d dot la
ultimul x1, scrieți o buclă for
și apoi faceți asta de K ori.
Și asta ar trebui să necesite
2.000 de pași, ceea ce este în regulă.
JASON KU: OK.
Deci, ceea ce
spunea colegul tău
este că îl vom
șterge pe tipul ăsta,
îl vom lipi acolo, o vom face de
K ori.
Suna bine?
Da.
Unul dintre lucrurile pe
care le aveți în această clasă, în ceea ce privește
implementarea -
de obicei, există două moduri -
cel puțin două moduri în care
puteți face ceva
care durează mai mult
decât timp constant.
Ai putea scrie o buclă de patru
în care ai putea folosi recursiunea.
Uneori, abordarea unei
probleme ar fi bine într-un fel,
mai degrabă decât în ​​altul.
De ce o mulțime
de informaticieni,
spre deosebire de
inginerii de codificare, preferă să se gândească
la un algoritm recursiv?
Stie cineva de ce?
Cel puțin o fac, când
explic
din punct de vedere teoric.
De fapt, s-ar putea să nu fie
bun din
punct de vedere al implementării, deoarece
computerul poate vectorizat
pentru bucle și lucruri de genul...
dar nu este ceva despre care
trebuie să vorbim.
De ce am vrea să vorbim
despre un algoritm recursiv
poate mai mult?
STUDENT: Vă permite să împărțiți
problema în bucăți mult mai mici,
mai ușor de gestionat.
JASON KU: OK, deci recursiunea
vă permite să împărțiți problema
în bucăți mici măsurabile.
Este adevărat
într-un anumit context.
Cum îmi place să mă gândesc la
recursivitate de multe ori este că,
dacă am o cantitate neconstantă
de muncă pe care trebuie să-l fac,
de obicei ușor pentru mine--
îmi este greu să păstrez
o cantitate neconstantă
de informații în mine.  cap.
Ceea ce vreau să fac este să mă gândesc
la o cantitate constantă
de informații la un
moment dat,
pentru că îmi este mai ușor să mă
cert.  Îmi
este mai ușor să mă gândesc
la argumente,
analize de caz pe aceste
mici cantități de lucruri.
Și, așadar, unul dintre
lucrurile pe care le puteți face
este, dacă o descompuneți astfel
încât să rezolv o
problemă puțin mai mică
recursiv și apoi să
lucrez constant
și să mențin o anumită invarianță,
atunci este foarte ușor să
argumentez lucrurile despre asta.  Îmi
este foarte ușor
să mă conving
că acest lucru este corect.
Așa că voi
oferi o modalitate recursivă
de a rezolva această problemă.
Poate cineva să stabilească
un mod recursiv
de a gândi această
problemă, în loc să
pună asta într-o buclă for,
așa cum spunea colegul tău?
Da?
STUDENT: [INAUDIBIL]
oamenii fac este
doar să ia în considerare ce se va întâmpla
când k este egal cu 0, nu ești
[INAUDIBIL] deloc.
JASON KU: OK.
STUDENT: [INAUDIBIL]
ceea ce a fost inițial.
Și apoi-- dar dacă acel
k este mai mare decât 0,
tu doar [INAUDIBIL] și
apoi [INAUDIBIL] k este cu 1 mai puțin
[INAUDIBIL]
JASON KU: Deci ceea ce
spune colegul tău
este configurarea...
un lucru foarte frumos.
Ea spune că, dacă ne
gândim la asta în mod recursiv, ne
vom gândi la un caz de bază -
care, colegul tău
spunea că poate K este egal cu 0.
Și altfel, dacă
nu suntem la 0,
ceea ce vom face este să  Vom
începe, vom muta unul dintre acești tipi
și apoi avem
un exemplu în care vrem
să schimbăm K minus 1 lucruri.
Vrei să faci același lucru,
dar cu K minus 1 lucruri.
Și așa putem numi acest
lucru doar pentru o valoare mai mică
a lui K. Are sens?
Bine, deci hai să
încercăm să scriem asta.
Primul lucru pe care îl voi
scrie este un fel de pauză.
Dacă sunt la un caz de bază, să
nu facem nimic la chestia asta.
Și poate
vreau, de asemenea, niște
verificări de respingere pentru a mă asigura
că suntem în raza de acțiune.
Bine, așa că voi spune,
dacă K este mai mic de 1,
nu cred că ar trebui să facem
ceva acestei matrice.
Deci să nu facem nimic.
Dacă K este mai mică de
1 sau K este mai mare
decât lungimea lui D minus
1-- deci nu știu ce
să fac dacă îmi ceri să
schimb mai mult decât lucrurile pe care le
am, așa că hai să nu facem asta.
Da... pentru că dacă ar
fi lungimea D,
oricum nu am
muta nimic,
pentru că am schimba
totul.
Deci nu trebuie să facem nimic.  În
regulă.
Dacă ne aflăm în oricare
dintre aceste cazuri, ne vom
întoarce,
pentru că fie nu ar trebui să
fac nimic matricei,
fie nu am idee despre ce
vorbești,
dacă este negativ
sau ceva de genul ăsta.
OK, deci acesta este primul lucru.
Altfel, ce facem?
Schimbăm un lucru și
apoi facem un apel recursiv.
Are sens?
BINE.
Deci vom șterge primul
lucru ca variabilă temporară -
ștergeți mai întâi.
Și apoi vom introduce ultimul, x.
Și apoi trebuie să
facem apelul recursiv.
Deci, cum
arată un apel recursiv?
Da?
STUDENT: Shift_left
D, K minus 1--
JASON KU: Da.
Deci shift_left D, K minus 1--
OK?
Și apoi ne putem întoarce.
Chestia asta nu trebuie
să returneze nimic.  Doar
face
ceva cu chestia.
Dreapta?
Și ori de câte ori
primim acest K, facem
un apel, care scade
la 0, vom termina
pentru că ne vom întoarce.
Suntem în acest interval
undeva între noi...
avem o intrare după această linie.
Știm că K este undeva
între 1 și n minus 1.
Și ceea ce vom face este, de fiecare
dată prin această recursivitate,
vom scădea 1
din K. Deci aceasta este
o secvență frumoasă, bine ordonată.
Facem lucrul corect,
evident, în cazul de bază,
și atâta timp cât acest lucru
a fost corect pentru o valoare mai mică
a lui K, acest lucru face, de asemenea,
lucrul corect,
pentru că trecem
peste unul, așa cum ni se cere,
și"  lasă asta să
facă treaba celorlalți.
Nu trebuie să mă
gândesc la asta.
Trebuie doar să mă gândesc la
această buclă, la această parte
din lucrul pe care îl fac.

În această secțiune este efectuată o cantitate constantă de muncă.
Și de câte ori
apelez o funcție?
STUDENT: [INAUDIBIL]
JASON KU: Da.
Cred că K minus 1 ori, sau...
Nu știu.
Am uitat.
Dar este comandat
K cu siguranță, nu?
Și facem o
cantitate constantă de muncă pe apel,
ignorând acest apel suplimentar.
Are sens?
Deci acest lucru rulează în
ordinea K, după cum se dorește.
BINE?
Are sens?  În
regulă.
Deci acum vom trece
la întrebarea 3.
Aveți întrebări despre întrebarea 2?
Aceasta este probabil
una dintre cele mai ușoare probleme pe care le-am
avut vreodată la un set de probleme.
Îmi pare rău că te sperii.
Deci problema 3--
OK, deci acesta este un mic
bloc de text chiar aici.
O matrice dinamică poate suporta
o interfață de secvență care
acceptă indexarea în timp constant în cel mai rău caz,

precum și inserarea
și îndepărtarea elementelor
din spatele matricei
în timp constant amortizat.
Deci asta am făcut
ieri la prelegere, nu?
Am arătat cum o matrice dinamică -
este rapid să faci
operații dinamice la sfârșit.
BINE.
Cu toate acestea, inserarea și
ștergerea din față
nu sunt foarte eficiente, deoarece,
dacă ai încerca să faci asta,
ar trebui să schimbi
totul.
Are sens?
Bine, pe de altă parte,
despre ce am vorbit ieri
au fost liste legate.
Ele pot fi făcute pentru a sprijini
inserarea și ștergerea
la ambele capete în timp constant.
OK, deci este o mică
prefigurare a ceva ce vei
face pe Pset1.
Dar în prelegere, am vorbit
despre acea operațiune -
acea structură de date,
o listă unică legată,
fiind bun la operațiuni dinamice
din partea de sus a listei,
pentru că, în esență,
ne-am putea
aminti unde era
partea din față a listei
și să schimbăm lucrurile
în  după cum este necesar.
Are sens?
Deci, pe setul dvs. de probleme,
ceea ce veți face
este să faceți operațiunile finale bune și
pe lista legată,
precum și să susțineți o
altă operație.
Dar care este problema
cu listele legate,
în comparație cu matricele dinamice?
Da?
STUDENT: Căutările în listele conectate
pot dura până la un timp liniar.
JASON KU: Da,
căutările în listele conectate
pot dura timp liniar,
pentru că nu am...
Nu am avantajul
unei matrice, unde pot
accesa aleatoriu ceva la mijloc
făcând, în esență,
un singur
calcul aritmetic offset
din față  adresa și să
puteți găsi acest lucru mai
jos în timp constant folosind
modelul nostru de calcul
al
mașinii de acces aleatoriu la rețea.
Într-o listă legată,
aceste lucruri ar putea
fi stocate peste tot
în memorie
și trebuie să traversez acești
indicatori până ajung la cel pe
care îl caut.
Acesta este un avantaj al
unei structuri de date bazate pe matrice
față de una
legată, bazată pe pointer.
OK, atunci ajungem la
miezul acestei întrebări.
Arătați că putem avea ce este
mai bun din ambele lumi --
putem avea o
structură de date care
acceptă căutarea în timp constant în cel mai rău caz
, la fel
ca o matrice, dar operațiuni
dinamice în timp constant amortizate
din partea din spate și din
față a secvenței.
Are sens?  În
regulă.
Aceasta este întrebarea sau...
OK.
STUDENT: Puteți defini
amortizarea încă o dată?
JASON KU: Da.
Îmi pare rău pentru asta.
Pot defini amortizarea
încă o dată?
OK, deci acesta este un
lucru greu de definit în general,
dar nu atât de mult.
În regulă, deci amortizarea o
puneți de obicei... cel
puțin în această
clasă, o vom
pune în termeni de
structură de date.
Deci ai chestia asta.
Acceptă unele
operațiuni și vei
face o grămadă de
operațiuni pe acel lucru.
Nu există cu adevărat un motiv
pentru a avea o structură de date,
cu excepția cazului în care veți
face o mulțime de lucruri pentru aceasta.  În
caz contrar,
scrieți un singur algoritm
pentru a face orice
doriți să faceți.
Valoarea
structurii de date este
că puteți
lucra în avans
făcând ca acest lucru să facă unele
dintre aceste operațiuni mai rapide.
BINE?
Deci ceea ce
înseamnă amortizarea este, OK,
dacă am, să zicem, o
matrice dinamică, în care voi
insera
lucruri la sfârșit,
uneori, când
adaug ceva,
voi petrece mult
timp pentru a adăuga  acel lucru.
Voi petrece timp liniar.
Dar ce
rost are această
structură de date în primul rând?
Ideea este că vreau să pot
adăuga potențial
o mulțime de lucruri la acest lucru.
Are sens?
Amortizarea spune
că, deși uneori
această operațiune va fi proastă, în
medie pe multe operațiuni,
aceasta va avea
un timp de funcționare mai bun.
Asta e amortizarea.
Deci, mai formal, ceea ce va
spune este că,
dacă am o operație,
definiția acesteia care rulează
într-o anumită perioadă
de timp -- să zicem K timp sau --
da, sigur -- asta înseamnă
că, dacă fac n operațiuni  ,
în general, pentru N mare --
dacă fac acea operație de n
ori, timpul total pe care mi-l ia
pentru a face toate aceste
operații nu va
fi mai mare de n
ori K. Deci, în medie,
îmi va lua K timp.
Acum, în O-4-6 veți obține o
definiție mai formală a acesteia
și veți obține o mulțime de
moduri de a analiza lucrurile,
cum ar fi o funcție potențială și-- vom
folosi în ceea ce
numim argumente de taxare
chiar și astăzi.
Deci, este o paradigmă de analiză mult mai largă

decât ceea ce vom
vorbi.  Vom

vorbi despre asta doar
pentru acest material
cu matrice dinamice
și vom face doar un fel de--
este doar un fel de
introducere la asta.
Dar asta are sens?
STUDENT: Da.
JASON KU: Amortizat ca
termen financiar, dacă
știi din termen financiar,
înseamnă pe termen lung,
asta este în medie.  Te
poți gândi la...
dar asta e diferit
de timpul de rulare.
Acesta este timpul mediu de rulare
al unui algoritm.
Este un concept mult diferit.
Care este durata medie de funcționare?  Ei
bine, este greu de
definit, pentru că se
vorbește despre o medie pentru
toate intrările posibile și apoi...
OK, deci poate că unele intrări
sunt mai probabile decât altele,
și așa că ai o
distribuție a intrărilor
și încerci.  pentru a media
durata de funcționare a...
asta nu are nimic
de-a face cu asta.
Amortizarea înseamnă că
aveți o -- de obicei o
structură de date pe care
operați, și
efectuați o
operațiune de mai multe ori
și obțineți un
beneficiu pentru că faceți
acea operațiune de multe ori.
Și atunci când
instanțiați o listă Python
și faceți operațiuni push și
pop pe spate,
asta este...
sau este atașare...
STUDENT: [INAUDIBIL]
JASON KU: Adăugați și pop?
BINE.
Am scris JavaScript
puțin recent.
Dar deci adăugați și pop --
acele operațiuni, deși
nu sunt ieftine tot timpul,
sunt destul de ieftine încât, atunci când
analizăm un întreg algoritm
care ar putea face un număr liniar
de anexări la această listă,
toate aceste anexări
adăugate
vor dura doar
timp liniar, pentru că am
făcut un număr liniar dintre ele.
Are sens?
STUDENT: Da.
Mulțumesc.
JASON KU: OK--
răspuns lung la întrebarea ta.
Îmi pare rău pentru asta.
Alte întrebări
înainte de a pleca?  În
regulă.
Are cineva vreo
idee despre cum putem
folosi ideile unei matrice dinamice
și să o facem bună pentru operațiuni
la ambele capete?  O să
las pe altcineva să răspundă.  Îți voi
acorda o secundă,
apoi merg la tine într-o secundă.
Da?
STUDENT: Deci [INAUDIBIL] dinamic
[INAUDIBIL] lăsat adevărat la un
capăt [INAUDIBIL]
JASON KU: Sigur.
STUDENT: [INAUDIBIL] aici am
putea lăsa niște [INAUDIBIL]
JASON KU: Este
o idee excelentă.
Vom vorbi despre
două moduri de a face acest lucru.
Dreapta.
Deci, ceea ce spunea colegul tău
a fost că, la prelegere,
când vorbim despre
modalități dinamice și vrem să facem
operațiuni pe
partea dreaptă - la sfârșit --
rapid, ceea ce am făcut a fost că am
alocat puțin spațiu suplimentar
la sfârșit.  , iar apoi,
când am adăugat lucruri,
nu a trebuit să realocăm.
Aveam spațiu să
punem acele lucruri.
Deci, ceea ce spunea colegul tău
a fost, să
facem același
lucru la ambele capete.  Să
lăsăm ceva spațiu suplimentar
în față și spațiu suplimentar
în spate atunci când
instanțiem acest lucru,
iar apoi putem reconstrui
mai rar decât dacă
nu am avea acel spațiu suplimentar.
Are sens?
OK, deci ce aveam pentru,
să spunem, aici jos --
deci aceasta este întrebarea 3 --
ideea
matricei dinamice din dreapta
a fost că am lăsat ceva
spațiu în plus aici la sfârșit,
astfel încât, sigur, am alocat
mai mult decât am  trebuia,
dar când introducem
lucrurile acum, este ieftin.
Și nu trebuie să alocăm
mai mult spațiu pentru acest lucru
până când nu facem un
număr liniar de inserții.
Acesta a fost n.
Acesta a fost n.
Într-adevăr, orice
factor constant va face aici.
Dar dacă ai avea n
lucruri aici, am
fi siguri că
nu va trebui să reconstruiesc
acest lucru până nu voi face un
număr liniar de operații.
Și astfel, într-un anumit sens, pot încărca
operația de timp liniară
de re-extindere a acestui lucru la
fiecare dintre aceste operațiuni.
Și așa, în medie,
va fi constant.
Are sens?
Dreapta.
Deci, în schimb, ceea ce
spunea colegul tău...
haideți să instanțiem acest
lucru cu puțin spațiu suplimentar
pe ambele părți.
BINE?
Așa că acum, pe măsură ce inserez ceva aici,
inserați lucrul aici-- bla, bla,
bla, bla, bla...
cu siguranță voi ști că, după
un număr liniar de inserții,
când voi reconstrui acest
lucru, voi fi
făcut  suficiente operațiuni pentru a plăti
acea operațiune costisitoare.
Are sens?
Deci, aceasta este ideea din spatele
extinderii acestei matrice dinamice
pentru a fi un fel de acest pachet dinamic.
Este un
tip de sistem de coadă dublu
în care pot face
operațiuni dinamice eficient
la ambele capete.
Așa că unul dintre lucrurile
despre care am vorbit ieri
a fost și eliminarea chiar
la sfârșit.
Eliminarea articolelor din
spatele acestui lucru
va reduce numărul de
articole pe care le stocăm, nu?
Are sens.
Și poate că suntem în
regulă cu acest drept.
Ca programator, de ce
nu ți-ar plăcea să
eliminați elemente
până nu ajungeți la nimic
și să lăsați
spațiul unde se află?
Da?
STUDENT: S-ar putea să blocheze
multă memorie [INAUDIBIL]
JASON KU: Da.
Deci, să presupunem că, pe
parcursul programului meu,
folosesc această structură de date.
Încerc doar să-l
umplu cu chestii,
apoi elimin toate, cu
excepția a două lucruri,
și apoi mă ocup de treburile mele.
Execut programul.
Dar nu folosesc niciodată cu adevărat
altceva decât acele două lucruri
pentru restul programului meu.
Dar acum am...
nu știu... poate că am
pus 1.000, sau un milion,
sau un miliard de lucruri în
chestia aia, și apoi, când am... pe măsură ce am
scăzut, pe măsură ce am eliminat
lucruri din asta.  element,
încă mai am tot acel
spațiu acolo fiind ocupat
de nimic, pentru că
am îndepărtat totul din
el,
cel puțin în concepția mea.
Deci, ceea ce aș dori cu adevărat
să mențin cu această
structură de date este că
în niciun moment nu
folosesc mai mult decât o
cantitate liniară de spațiu
în raport cu numărul de
lucruri care sunt stocate în ea.
Are sens?
Deci, într-o
matrice dinamică, ceea ce facem
este că, când devenim suficient de mici, să
redimensionăm acest lucru în jos,
astfel încât să avem...
folosim mai puțin spațiu.
Pe măsură ce scad, pe măsură ce
scot lucruri
de la sfârșitul acestui
lucru, în ce moment
crezi că ar trebui să-mi
reconstruiesc matricea?
Când nu mai sunt
o sumă liniară?  Ei
bine, este puțin greu de
spus ce este asta în viața reală,
pentru că scopurile noastre
nu sunt arbitrare.
Trebuie să avem de fapt un moment
în care trebuie să
trecem și să copiem lucrurile.
Deci când am putea dori
să facem asta?
STUDENT: [INAUDIBIL]
JASON KU: Spune din nou.
STUDENT: După n/2 [INAUDIBIL]
JASON KU: După n/2 eliminări--
OK.
Așa că elimin n/2 lucruri.
OK, deci acum suntem într-un fel de
umplere n/4,
așa că folosim o
pătrime din spațiu.
Și acum... grozav.
Deci spui reconstruire.
OK, așa că voi înfige totul
în ceva care este acum...
acesta este m.
O să-l numesc
m, iar acum
îl lipim în ceva
care are dimensiunea m/4.
Suna bine?
Da?
Da?
Toți sunt de acord cu asta?
STUDENT: [INAUDIBIL]
m/4 [INAUDIBIL]
JASON KU: O, OK.
Deci ceea ce spui
este că de fapt
vrem să păstrăm un
spațiu suplimentar aici.  De
ce, mă rog?
Pentru că imaginați-vă dacă am
alocat această cantitate de spațiu
și am eliminat m/4
plus al 1-lea element de aici, ne-am
redimensionat la
acest lucru și apoi
vreau să fac o inserare din nou.  Ei
bine, atunci trebuie să mă extind din nou
la așa ceva
și poate că nu
va fi un lucru bun.  S-
ar putea să trebuiască să ne întoarcem
mult înainte și înapoi.  Mi-
e greu să mă gândesc
la ce vom face.
Dar dacă redimensionăm întotdeauna
la un raport de umplere care
include o cantitate liniară
de lucruri la sfârșit,
atunci știu că,
atunci când redimensionez în jos, voi
face fie un
număr liniar de ștergeri,
fie un număr liniar de inserări
înainte de a avea  pentru a reconstrui din nou.
Deci, acest
argument de încărcare din nou -
trebuie să fac un
număr liniar de lucruri ieftine
înainte de a trebui să fac din
nou un lucru scump.
BINE?
Așa că am redimensionat pentru a fi...
încă păstrez o cantitate liniară
de spațiu suplimentar la sfârșit.
Și cu
chestia dublu,
puteți scrie același
tip de politică.
Cu spațiul suplimentar, așa cum
spunea colegul tău,
putem să redimensionăm întotdeauna în jos
pentru a muta aceste lucruri pentru a fi
plasate în mijloc cu o
cantitate liniară de spațiu suplimentar
la capete.
Are sens?
Fără întrebări?  În
regulă.
Acesta a fost un mod în care a
trebuit să redefinim
o structură de date complet nouă.
Am preluat ideile
din spatele matricelor dinamice
și le-am extins
pentru a face ca acest lucru să aibă
spațiu suplimentar la ambele capete.
Dar a trebuit să facem
acea reimplementare
singuri.
Dacă am face cod,
ar fi cam nodur.
Dar dacă cineva ne-ar
oferi o matrice dinamică?
Ce se întâmplă dacă cineva
ți-a dat o listă Python
și ți-ai dori
această funcționalitate?
Nu vreau să reimplementez
o matrice dinamică,
dar vreau acest
comportament, deci cum-- cum
aș putea
face asta reducând
la utilizarea unei matrice dinamice--
să obțin acest tip de timp de rulare?
Nu?
Nimeni nu crede că
putem face asta.
Este imposibil.
Nu?
Fara idei?
Fără idei, să presupunem că am avut...
Am o matrice dinamică
care este bună pe o parte.
Există ceva ce pot face
pentru a sprijini operațiuni dinamice
pe ambele părți ale unei secvențe?
Da?
STUDENT: Putem
folosi pur și simplu [INAUDIBLE]
JASON KU: Oh, ar
trebui să fie gol, nu?
Da.
Deci, ce spune colegul tău...
da, hai să facem asta.  Să
avem unul
îndreptat înainte,
unul îndreptat înapoi.
Acesta este primul
dintr-un anumit lucru.
Când făceam doar
o matrice dinamică aici,
în care trebuia să
reconstruim totul,
era important
să ținem evidența
unde se afla chestia din față, astfel
încât să putem face indexarea timpului.  Pe
măsură ce acest lucru
s-a schimbat, acum ar
trebui să calculăm unde se afla
indexul nostru în acest lucru
adăugându-l acolo
unde se afla frontul.
În aceasta, avem
câteva probleme similare.
Deci, ceea ce voi
face este
să împart
secvența pe care încerc
să o stochez în două secțiuni,
poate cam de aceeași dimensiune.
Deci fiecare dintre acestea conține
un număr liniar de elemente.
Așa o să-mi
instanțiez
lucrul cu o cantitate liniară
de spațiu suplimentar la ambele capete.
Așa că acum, pe măsură ce inserez
pe ambele părți
sau șterg din ambele părți,
va funcționa exact
ca o matrice dinamică.
Trebuie să fac niște aritmetice
aici pentru a-mi da seama unde--
dacă aș încerca să
accesez aceste elemente,
ar trebui să scad din
oriunde acest lucru--
Trebuie să fac niște
aritmetice de index, dar asta e plictisitor,
dar ai putea face  aceasta.
BINE.
Există o avertizare,
o problemă cu care te
confrunți când folosești
așa ceva.
Și care ar fi asta?
Da?
STUDENT: Nu sunt
sigur, dar stocați
lucrurile în a doua
jumătate a unui tablou dinamic.
JASON KU: Aici?
STUDENT: În primul.
JASON KU: Aici?
STUDENT: [INAUDIBIL]
JASON KU: Corect.
Deci ceea ce fac
aici este, de fapt,
mă gândesc la asta
ca la două matrice dinamice,
dar îl văd pe
acesta invers.
Deci, acesta este de fapt
ultimul din această matrice dinamică.
Are sens?  În
regulă.
Deci, dacă asta este
situația în care mă aflu, este... am
terminat?
Trebuie să-mi pese de
altceva?
Voi băieți sunteți ca
, am terminat
și nu v-aș da
puncte întregi.
De ce nu am terminat?
Da?
STUDENT: [INAUDIBIL]
JASON KU: OK, deci ceea ce
spune colegul tău este că
cumva trebuie să
le îmbinăm într-o singură matrice.
Așa că ocolim asta
păstrând indici aici
și fiind capabili să facem
aritmetica indicilor pentru a simula
o matrice dedesubt.
Deci putem calcula unde
ar trebui să fie acești indici.
Are cineva o altă problemă
cu o structură de date subspecificată
aici?
Da?
STUDENT: [INAUDIBIL]
ar putea fi că [INAUDIBIL]
JASON KU: Înțeleg.
Deci, ceea ce
spune colegul tău,
care este exact corect --
dacă aș scoate
lucruri, aș scoate lucruri, aș
elimina lucruri, nu am nimic altceva
aici.
Dacă încerc să ies din
nou de la capătul ăsta, va
trebui să ies de la
începutul acestui lucru,
ceea ce nu prea-- asta o să
rupă
ceva din ceea ce fac.
Nu menține
invarianții a ceea ce
vreau pe structura mea de date.
Și deci singurul avertisment aici
este că, când mă reduc
la unul dintre acestea este
gol, ce fac?
STUDENT: Trebuie să-l tai pe
celălalt în jumătate [INAUDIBIL]
JASON KU: Tai chestia asta în
jumătate, mută aceste elemente peste.
Dar asta va lăsa
aceste lucruri la mijloc
aici, nu?
Lucrul frumos care se
întâmplă aici este că am
făcut un
număr liniar de opțiuni--
operații.
Acum am o
acumulare de costuri amortizate
pe care o pot cheltui pentru a reconstrui acum
întreaga structură de date.
Are sens?
Acum pot, odată ce ajung
la chestia asta, să iau orice sunt
lucrurile rămase
, să le împart în jumătate, să
le pun în două matrice complet noi
, să le copiez peste tot
și acum mi-am restaurat
invariantul, unde sunt.  , din nou,
o cantitate liniară
de operații departe
de a fi nevoit să facă din
nou o operațiune costisitoare.
Are sens?
Așa că, deși am reușit să ne reducem
la utilizarea acestor matrice dinamice
pentru o mulțime de
cazuri, a trebuit de fapt să lucrăm
puțin mai mult
pentru ca acest lucru să funcționeze.
Asta are sens?
OK, cool... deci sunt două moduri
de abordare a problemei 3.
În ultimul
moment, vom
vorbi despre ultima problemă.
Bine, asta are sens.
Voi șterge această poză,
dacă este în regulă cu voi
băieți.
STUDENT: [INAUDIBIL]
JASON KU: Ce e?
Nu este în regulă?  Ei
bine, păcat... uită-te la videoclip.
OK, deci problema 4--
de asemenea, o întrebare destul de accesibilă, să
zicem, de codificare--
ceea ce facem la
problema 4 este că
avem această mică poveste drăguță
la început, care
este despre această femeie
Jen și prietena ei.
Barry, care încearcă să vândă
înghețată copiilor de școală elementară
.
Practic, sunt
aliniați la camionul lui Jen
și ea spune că sunt
prea mulți studenți aici.
Așa că îl sună pe
prietenul ei Barry.
Are o altă mașină de înghețată,
piese la capătul firului,
iar studenții--
ceea ce vor să facă
este, ca să fie mai
corect, ei vor
lua
ultima jumătate a firului,
o vor întoarce la  fă-o mai corectă.  Nu
știu.
Este o situație stupidă, dar
lucrul de bază este ceea ce
facem este... partea
A, aici avem...
vă oferim o listă legată...
o listă legată individual și
ceea ce vreau să faceți...
lista legată individual --
tot ce are este o noțiune
de dimensiune, cât de lungă este.
Are o dimensiune și are
un cap această listă--
are o dimensiune și are un cap.
Și acest cap este un
pointer către un nod,
iar nodul are doar unul--
două lucruri stocate în el.
Are cine... numele
copilului care este acolo
și următorul indicator
către următorul nod.
Asta
este o listă legată individual.
Deci nodul are o
cheie de element și un indicator următor.
Acest indicator următor indică
următorul nod din secvență.
BINE?
Și întrebarea este: dacă
vă oferim o listă legată care
are 2n noduri, vreau
să luați ultimele n noduri
și să le inversați ordinea și să
faceți acest lucru cu structura de date.
Nu veți returna
o nouă structură de date.
Veți modifica
nodurile existente.
Și de fapt, aici este...
revine la întrebarea ta.
La ce ne limităm în
modul în care abordăm această problemă?
La ce servește această problemă,
algoritmul dvs. nu ar trebui să
creeze noi noduri de listă conectată
sau să instanțieze orice noi
structuri de date de dimensiuni neconstante.
Deci nu este ca și cum aș putea scrie
prin toată această chestiune, să
aflu unde
este nodul n plus al 1-lea, să
citesc toate acele
nume, să le stochez
într-o matrice undeva și
apoi să le rescriu înapoi.
Nu am voie să stochez
mai mult de o cantitate constantă
de lucruri în afara
acestei liste legate
și nu pot
face noduri noi.
În esență, trebuie doar să
păstrez aceste elemente
acolo unde sunt și să mă
deplasez în jurul nodurilor.
Da?
STUDENT: Puteți folosi
spațiu non-constant
fără a crea
o structură de date?
JASON KU: Deci, dacă
utilizați spațiu non-constant,
instanțiați un
fel de structură de date,
fie că este într-o matrice sau...
STUDENT: [INAUDIBIL]
JASON KU: Sigur.
Vreau să nu faci asta.
Da.
Alte intrebari?
Deci, cum vom
face această problemă?
Cineva?
Are cineva o abordare pentru cum as
putea aborda aceasta problema?
Da?
STUDENT: Pentru a
ajunge la a doua jumătate,
nu trebuie să faci
toate astea [INAUDIBIL]
JASON KU: Sigur.
STUDENT: Ați putea începe...
probabil să începeți să
numărați înapoi, astfel
încât să le puteți primi
în ordine,
apoi întâlniți-l la
mijloc, astfel încât [INAUDIBIL]
JASON KU: Interesant.
Deci sunt o mulțime de lucruri...
haideți să dezvăluim asta.
Deci, de multe ori,
când
vă cerem să construiți un
algoritm, de multe ori, are
sens să dezvoltați
o schiță sau un
plan de joc al
părților constitutive cu care ați putea dori să
abordați această problemă.
Așa că primul lucru pe care l-a
spus colegul tău de aici
a fost, la un moment dat,
trebuie să aflăm unde
este mijlocul acestei chestii.
Are sens?
Deci, poate că primul lucru pe care vrem să-l facem
pentru a aborda această problemă
este, unul, găsirea nod-al-lea.
Acesta este sfârșitul
primului set de copii.
BINE?
Apoi am un al doilea
lucru pe care vreau să-l fac.
Care este următorul
lucru pe care trebuie să-l fac?
Trebuie să invers
pointerii tuturor
după nodul n-lea, nu?
OK, deci al doilea lucru --
invers, cred, următorii indicatori
ai tot după al-lea
nod --
nodurile n plus de la 1 la 2n.
Are sens?
Și după ce am inversat toate
aceste lucruri, ce am?
Am un prim bloc.
Asta arată așa.
Și acum avem
chestia asta și am inversat
toate indicațiile astfel.
Asta după pasul 2.
Asta ne dorim?
Da?
STUDENT: Pasul 3
ar fi [INAUDIBIL]
JASON KU: Deci acesta este noul meu final.
Voi numi acest
nod a, și acest nod b
și acest nod C. Deci spuneți-
mi, în termeni de a, b
și c, ce ar trebui să fac.
Da?
STUDENT:
Întrebare rapidă - cum am
inversa următorul indicator?
Înțeleg ce spui, dar...
JASON KU: Corect.
STUDENT: --pentru a
face asta să se întâmple--
JASON KU: Da.
Deci, pentru a face acest lucru să se întâmple,
acest lucru are un următor indicator.
Este îndreptat spre...
arătând către un nod.
Trebuie să-l reconectam
la lucrul dinaintea mea,
așa că mai bine îmi amintesc
ce era înaintea mea,
astfel încât să pot seta nodul b.next
egal cu lucrul dinaintea mea,
în loc de lucrul de după mine.
Are sens?
Deci asta ar fi reconectarea...
STUDENT: Și apoi
deconectează lista legată.
JASON KU: Deconectează
lista legată,
eventual, temporar.
STUDENT: Oh, bine.
Este temporar și, prin urmare,
încă funcționează [INAUDIBIL]
JASON KU: Ei bine, trebuie să
reconectam totul
pentru a ne asigura că este temporar.
Este foarte posibil, atunci când
aveți de-a face cu structuri de date legate
, să deconectați ceva
și să nu aveți o referință înapoi
la el, iar acum acest
lucru este în memorie pe
care, sperăm, colectorul de gunoi îl
va ridica.
Dar dacă scrii
într-o limbă care
nu este colectată de gunoi, atunci
asta se numește o scurgere de memorie.
Nu e bine.
OK, deci cum pot
reconecta aceste lucruri?
Aceasta este poza pe care o
am chiar acum.
Cum transform asta într-
o listă legată, unde
este aici și apoi inversată?
Da?
STUDENT: Puteți lega
a la c [INAUDIBIL]
JASON KU: Da.
Așa că înlocuiesc acest
indicator de la a la b pentru a-l
face să indice în
schimb către c și apoi,
orice ar fi indicatorul meu către b--
de la b-- b este inversat--
indică către a-- să
-l setăm egal cu niciunul.
Deci, practic, ultimul
pas aici este curățarea capetelor.
Și în
scrisul LaTeX, ați dori
să specificați, care sunt
lucrurile pe care le reconectați?
Dar aceasta a fost o
întrebare de codificare și, de fapt,
v-am dat cod cu care să lucrați.
Așa că o să văd dacă
pot codifica în direct acest lucru pentru tine
în fața ta.
BINE.
Deci, aici a fost site-ul nostru de trimitere a codului
din ultimul trimestru.
Și ceea ce am aici este
șablonul meu din ultimul trimestru, Pset1.
Deschide acest folder.
Are o grămadă
de lucruri în el,
șablonul LaTeX
pe care îl aveți
și apoi o grămadă de
aceste fișiere Python.
Deci mă duc la...
unde este?
Aici.
OK, deci acestea sunt fișierele
care se află în directorul meu.
Ți-am oferit o versiune a
acestei secvențe de listă legată.
Și apoi mai avem două
întrebări despre cod -- un fișier teste
și un fișier reorder_students.
Deci reorder_students arată
cam așa.
Are un șablon al
codului pe care vom
dori să-l scrieți,
cu intrări și ieșiri.
Și îți pui
codul aici.
Și această funcție nu
trebuie să returneze nimic.
În regulă, și apoi
vă oferim și
această implementare a listei legate
, care
este ceea ce este în
fișa de recitare.  De
fapt, voi
ignora cele mai multe dintre aceste chestii--
de fapt doar că acest lucru
conține un articol în următorul
nod-- de fapt,
nu mă voi
uita deloc la articole--
și un cap și o dimensiune în mine
lista legată la nivelul superior.
BINE?
Dar asta este doar pentru a
vă spune ce este acolo.
Așa că asta va fi
introdus în treaba mea
și dacă mă duc aici și
rulez
documentul de teste pe care mi l-ai
dat, eșuează
pentru că nu am nimic.
Nu a făcut
nimic listei.
BINE?  În
regulă.
Și de fapt, dacă intru
aici la teste și eu...
ce este?
Reordonează
studenții aici.
Tipăresc lista cu linkuri pe
care mi-ai dat-o.  O să
am
o întrerupere de linie aici.
Ceea ce putem vedea este că,
când fac asta...
iată cazurile mele de testare.
Iată o listă legată.
Și ceea ce se întâmplă
este că doar
scuipă aceleași liste legate.
Nu i-am făcut nimic.
Bine, așa că trebuie
să facem ceva.
Cum vom face asta?
Bine, deci să
implementăm această funcție.
Și o să scap
de chestiile astea, pentru că...
scăpa de asta.
Bine, așa că trebuie
să reordonăm studenții.
Așa că voi
împărți asta în trei părți pe
care le avem aici.
Vom
găsi al n-lea nod.
Deci, cum găsim al n-lea nod?
Acest lucru are o dimensiune
pe el, așa că să ne dăm seama cel puțin
ce este n.
Deci, să setăm n egal cu--
Cred că pot folosi
lungimea, pentru că am
implementat asta pe
treaba mea și va
fi oricare ar fi
lungimea peste 2.
Și sunt definit de
declarația problemei
că sunt  va avea doar
intrări egale.
Și voi stabili, la început, ca a
mea să fie locul de plecare.
Voi avea doar o mică
variabilă temporară care va
spune că aceasta va
fi egală cu capul listei mele.
Și ceea ce am de gând să fac este ceea ce
spunea colegul tău --
este că voi
trece de n ori
până ajung la a n-a.
De fapt, de câte
ori trebuie să
călătoresc prin următorii
indicatori pentru a ajunge la nodul a?
n minus 1, de fapt... da.
Deci asta va fi pentru.
Nu-mi pasă de
această variabilă de buclă,
așa că voi folosi doar
acel n minus de 1 ori.
Ce urmeaza sa fac?
Vreau să înlocuiesc a cu
lucrul spre care este indicat,
așa că voi merge doar pe
acest lucru.  a este egal cu a.next.
Și acum, după sfârșitul
acestei bucle, ce este a?
a este al n-lea nod.
Acum l-am făcut al
n-lea nod - fantastic.
Și acum voi spune că
b va fi următorul.
Doar în ceea ce privește scrisul meu,
am etichetat aceste lucruri
ca a, și b și c,
și așadar, în mintea mea, o să
vreau să folosesc
același tip de notație
aici, astfel încât să îmi pot
înțelege codul.
OK, deci b va
fi următorul lucru.
Și acum, în acest proces, pe măsură ce voi
răsturna lucrurile,
ceea ce voi
face este să
țin evidența a trei noduri.
O să țin evidența lui
x, care este nodul pe care îl voi
reconecta.
Și ce altceva
trebuie să țin evidența?
Dacă sunt...
STUDENT: [INAUDIBIL]
destinație.
JASON KU: Da, de
unde am venit
și unde mă
duc, pentru că asta va
trebui să mă reconectam.
În special, voi
avea pe cineva care să mă arate,
pe care îl voi
numi următorul precedent --
sau x anterior.
Când o să-l etichetez,
va fi următorul lucru.
În regulă?
Are sens?
Deci, în prima mea situație, eu sunt...
primul lucru pe care
trebuie să-l relinkez este
b, așa că acesta va fi x-ul meu.
Și x anterior va fi a.
Are sens?
Deci voi instanția
acele două variabile.
x și x_p vor
fi b și a.
Îmi pare rău.
Asta e corect.
Da.
Poate că are mai mult sens să
avem x anterior și x egal cu ab.
Bine, asta e
în ordinea corectă.
Ambele sunt ok.
Și apoi vreau să
trec printr-o buclă.  O să

fac un mod în buclă.
Puteți face acest lucru într-un
mod recursiv, dacă doriți.
Iată un mod în buclă, în
care voi trece doar de
câte ori?
Câte indicații voi
reconecta pe măsură ce merg la acest lucru?
Trebuie să refac indicațiile
tuturor acestor tipi.
Cât de multe sunt acolo?
STUDENT: [INAUDIBIL]
JASON KU: Câte?
STUDENT: [INAUDIBIL]
JASON KU: n--
sunt n dintre ele.
Deci for-- Nici aici nu-mi pasă de
variabila buclă.  O să
fac asta de n ori.
Și ce am de gând să fac?  O să-mi dau
seama mai întâi
cine este următorul meu tip.
Voi seta x_n
egal cu ce?  x.next-- în
regulă, așa că acum știu
cine este lângă mine,
așa că pot merge acolo mai târziu
după ce îmi relinkez indicatorul.
Îmi amintesc asta.
Acum, nu-mi pasă de ce este
stocat în x.next, pentru că
l-am stocat local.
Are sens.  În
regulă, acum sunt liber
să relinkez următorul indicator
la tipul meu anterior.
Și acum
îmi pot schimba perspectiva,
așa că lucrul pe care îl voi
reconecta acum este următorul.
Deci, x anterior și x
acum este egal cu x, x_next.
Are sens?
Tocmai am reconectat lucrurile peste -
deci acesta este sfârșitul pasului 2.
Acum, când am găsit asta la
sfârșitul acestei bucle for,
unde este x?
Ce este x_p, x și
x_next-- sau x_n?
Într-adevăr, eu urmăresc doar
x și x_p aici.
Deci, ce sunt x_p și x
la sfârșitul acestei bucle?
Am făcut asta de n ori.
Am început cu b la x.
Deci ce este x?
Da?
Deci avem un vot că x este c.
STUDENT: [INAUDIBIL]
JASON KU: Deci asta este
puțin interesant.  În
regulă.
Vă voi spune că c
este fie x_p, x, fie x_n.
Deci avem un vot pentru x.
Cine mai spune ceva?  Lui
Eric nu-i place x.
Există doar
două alte variante.
Spune cineva ceva?
x_p-- Voi argumenta
că este x_p.
De ce?
Pentru că sunt la b.
Sunt n lucruri.
Am făcut n operații, și la fiecare
operație, am mutat 1 peste.
Deci, când am făcut n minus 1
lucruri, sunt la c, al n-a.
Acum x nu este niciunul, pentru că
există indicatorul nul
la sfârșitul listei.
Deci x_p este c, așa că voi
seta p egal cu x_p, care este --
este doar pentru mine să-mi amintesc
care sunt aceste lucruri.
Și am reconectat
aceste două indicații.
a.next ar trebui să fie c și
b.next ar trebui să fie niciunul.
Are sens, toată lumea?
Să vedem dacă am procedat bine.
Așa că salvăm acel lucru și
rulăm Python pe cazurile de testare
și a făcut ceea ce trebuia
aparent... poate.  Să
vedem... a rulat
cinci cazuri de testare...
OK.
Bine, deci hai să
aruncăm o privire la asta.
Aveam această listă legată --
Lilly, Sally, Cindy,
Maisy, Sammy, Davey.
Și ceea ce se transformă în este Lilly,
Sally, Cindy, ceea ce este corect.
Și apoi inversează această
ultimă parte a listei --
Danny, Sammy, Maisy --
grozav, grozav.
Dar acestea sunt
cazurile de testare pe care vi le-am oferit.
Deci, hai să încercăm asta
cu verificatorul nostru de cod.
Așa că selectez fișierul.
Unde merg?
Cred că sunt în desktopul meu aici
în sesiunea 1 și șablon
și reordonez studenții.  o
depun.
Vă rog să lucrați.
Vă rog să lucrați.
Vă rog să lucrați.
Și 100%... și acum suntem
fericiți și putem merge la petrecere.
BINE.
Bine, deci asta e
prima problemă.
Sper că acest lucru v-a fost de
ajutor.
Vom lansa setul de probleme 1
mâine și mult succes.