[Powered by Google Translate] [Secțiunea 3 - mai confortabil]
[Rob Bowden - Universitatea Harvard]
>> [Acest lucru este CS50. - CS50.TV]
>> Deci, prima întrebare este formulată ciudat.
GDB vă permite să vă "debug" un program, dar, mai ales, ceea ce nu-l lăsa să faci?
Voi răspunde că, și nu știu exact ce se așteaptă,
așa că eu sunt ghicitul că e ceva de-a lungul liniilor de aceasta vă permite să pas cu pas
plimbare prin programul, interacționează cu ea, variabilele de schimbare, fac toate aceste lucruri -
practic control complet asupra execuției unui program
și de a inspecta orice parte dat de execuție a programului.
Deci, aceste caracteristici vă permit să depanați lucrurile.
Bine.
De ce căutarea binară impune ca o matrice să fie sortate?
Cine vrea să răspund la asta?
[Elev] Pentru că nu funcționează dacă nu este sortat. Da >>. [Râsete]
În cazul în care nu este sortat, atunci este imposibil să-l împartă în jumătate
și știu că totul este mai puțin stânga și la dreapta totul
este mai mare decât valoarea de mijloc.
Deci, aceasta trebuie să fie sortate.
Bine.
De ce este un fel de balon în O pătrat de n?
Vrea cineva primul care îi lasă o foarte rapid la nivel înalt imagine de ansamblu a ceea ce fel bubble este?
[Elev] Tu du-te în principal prin fiecare element și să verificați elemente primele câteva.
Daca nu mai au de unde le-ai schimba, atunci verificați următoarele elemente puține și așa mai departe.
Atunci când ajunge la sfârșitul anului, atunci știi că cel mai mare element este plasat la sfârșitul anului,
astfel încât să ignore că unul, atunci vă păstrați pe trece prin,
și de fiecare dată când trebuie să verificați un element mai puțin, până când nu va aduce modificări. Da >>.
Se numește fel balon pentru că dacă întoarceți matrice pe partea sa, astfel că este în sus și în jos, pe verticală,
apoi valorile mari se va scufunda pe fundul și valorile mici vor bule până la partea de sus.
Asta e modul în care aceasta a primit numele său.
Și da, du-te doar prin.
Tu continui sa mergi prin matrice, schimbarea valoarea mai mare
pentru a obține cele mai mari valori la partea de jos.
>> De ce este O pătrat de n?
În primul rând, nimeni nu vrea să spună ce e de n pătrat O?
[Elev] Deoarece pentru fiecare termen merge de n ori.
Puteți fi siguri că ați luat cea mai mare elementul tot drumul în jos,
atunci va trebui să repet faptul că pentru cât mai multe elemente. Da >>.
Deci, tineti minte ceea ce înseamnă mare O, și ce înseamnă mari Omega.
O mare este ca superioară cu privire la modul lent se poate rula, de fapt.
Deci, prin a spune o Este de pătrat n, nu este de n O altfel ar fi capabil să ruleze
în timp liniar, dar este de n O tocata
deoarece este delimitată de O n cub de.
În cazul în care este delimitată de O din pătrat n, atunci este delimitată, de asemenea, de n tocata.
Deci, este n pătrat, iar în cel mai rău caz, absolut nu se poate face mai bine decât pătrat n,
care este de ce este O de n pătrat.
Deci, pentru a vedea matematica ușoară la cum se face a fi n pătrat,
dacă avem cinci lucruri în lista noastră, prima dată cât de multe am putea swap potential nevoie pentru a face
, în scopul de a obține acest lucru? Să fapt doar -
Câte swap-uri vom avea de a face, în primul tur al bulei fel prin matrice?
[Elev] n - 1. Da >>.
>> Dacă există 5 elemente, vom avea nevoie de a face n - 1.
Apoi, pe cea de a doua câte swap vom avea de a face?
[Elev] n - 2. Da >>.
Iar al treilea va fi n - 3, iar apoi pentru comfortul voi scrie ultimele două
ca si atunci vom avea nevoie de a face operațiunile de swap 2 și 1 de swap.
Cred că ultima poate sau nu poate nevoie de fapt să se întâmple.
Este un swap? Nu știu.
Deci, acestea sunt valorile totale ale swap-urilor sau cel puțin comparații pe care trebuie să o facă.
Chiar dacă nu schimbați, tot trebuie să compare valorile.
Deci, există n - 1 comparații în primul tur prin matrice.
Daca aranjati aceste lucruri, să facem de fapt sase lucruri atât de lucruri se adune frumos,
si apoi voi face 3, 2, 1.
Deci, reamenajarea doar aceste sume, vrem să vedem cât de multe comparații facem
în algoritmul intreaga.
Deci, dacă aducem pe tipii ăștia aici,
atunci suntem încă însumând doar comparatii cu toate acestea au existat mai multe.
Dar dacă ne rezuma acestea și am rezuma acestea și însumăm acestea,
e încă aceeași problemă. Noi rezuma doar acele grupuri particulare.
>> Deci, acum suntem însumând 3 a lui n. Nu este vorba doar 3 N lui.
Este întotdeauna o să fie n / 2 n lui.
Deci, aici se întâmplă să avem 6.
Dacă am avea 10 lucruri, atunci am putea face acest lucru grupare pentru 5 perechi diferite de lucruri
și se încheie cu n + n + n + n + n.
Deci, tu ești mergi la a lua mereu n / 2 n lui, și astfel aceasta ne vom jot pentru a pătrat n / 2.
Și așa, chiar dacă e factor de jumătate, care se întâmplă să vină în
din cauza faptului că, prin fiecare iterație peste matrice am compara 1 mai puțin
asa ca asta e modul în care vom ajunge peste 2, dar este încă n pătrat.
Noi nu le pasă de factor constant de o jumătate.
Deci, o mulțime de lucruri mari O astfel se bazează pe doar un fel de a face acest tip de matematica,
faci sume aritmetice si alte chestii serie geometrică,
dar cele mai multe dintre ele în acest curs sunt destul de simple.
Bine.
De ce este un fel de inserție în Omega de n? Ce înseamnă omega înseamnă?
[Doi studenți vorbind la o dată - neinteligibile] >> Da.
Omega vă puteți gândi ca limita inferioară.
>> Deci, indiferent de cât de eficient algoritm de sortare ta de inserare este,
indiferent de lista care a trecut, în, ea are întotdeauna să compare cel puțin n lucrurile
sau trebuie să itera peste lucrurile n.
De ce este asta?
[Elev] Pentru că, dacă lista este deja sortate, apoi prin prima iterație
vă poate garanta că numai elementul prima este cel,
și a doua iterație se poate garanta doar primele două sunt
pentru că nu știi că restul Lista este sortata. Da >>.
Dacă treci într-o listă sortată complet, cel puțin trebuie să te duci peste toate elementele
pentru a vedea că nimic nu trebuie să fie mutate.
Deci, trecerea listă și spunând oh, acest lucru este deja sortat,
este imposibil pentru tine să știi că e sortati până când verificați fiecare element de
pentru a vedea că acestea sunt sortate în ordine.
Deci, limita inferioară la fel de inserare este de n Omega.
Ce se mai rău caz de funcționare timp de sortare îmbinare,
cel mai grav caz fiind O mari din nou?
Deci, în cel mai rău caz, cum se sortează de îmbinare a rula?
[Elev] n log n. Da >>.
Cele mai rapide algoritmi generali de sortare sunt n log n. Nu poti sa faci mai bine.
>> Există cazuri speciale, și dacă avem timp de astăzi -, dar noi won't probabil -
am putut vedea unul care face mai bine decât n log n.
Dar, în cazul general, nu puteți face mai bine decât n log n.
Și îmbinarea fel se întâmplă să fie cel pe care îl trebuie să știți pentru acest curs, care este n log n.
Și așa vom fi de fapt de punere în aplicare ca astazi.
Și, în sfârșit, în nu mai mult de trei fraze, cum se sortează de selecție?
Are cineva vrea să răspundă, iar eu voi conta Exemple de dvs.
pentru că dacă te duci peste 3 -
Are cineva aminte de sortare de selecție?
Sortare de selecție este, de obicei, destul de ușor să vă amintiți doar de nume.
Ai repeta doar peste matrice, găsiți oricare ar fi cea mai mare valoare este mai mică sau -
orice ordine ai de sortare inch
Deci, haideți să spunem suntem de sortare de la cel mai mic la cel mai mare.
Ai itera peste matrice, căutați pentru orice elementul minim este,
selectați-l, și apoi schimbați doar ceea ce este în primul rând.
Și apoi pe a doua trecere peste matrice, căutați elementul minim din nou,
selectați-l, apoi schimbați-l cu ceea ce este în poziția a doua.
Deci, noi suntem doar cules și alegerea valorilor minime
și introducerea lor în partea din față a matrice până când acesta este sortat.
Întrebări cu privire la asta?
>> Acestea apar în mod inevitabil la formularele pe care trebuie să completați atunci când sunteți trimiterea PSET.
Acestea sunt practic răspunsuri la cele.
Ok, deci acum codificare probleme.
Am deja trimis prin e-mail - Nu pe nimeni aia e-mail? Bine.
Am deja trimis prin e-mail spațiul pe care vom folosi,
și dacă faceți clic pe numele meu - deci cred ca am de gând să fie în partea de jos
din cauza r spate - dar dacă faceți clic pe numele meu vei vedea 2 revizii.
Revizia 1 va fi deja am copiat și inserat codul în spațiile
pentru lucrul căutare ai de gând să trebuie să pună în aplicare.
Și Revizie 2 va fi lucrul pe care punem în aplicare un fel după aceea.
Deci, puteți să faceți clic pe Revizuirea mea 1 și de a lucra de acolo.
Și acum vrem să pună în aplicare cautare binara.
>> Vrea cineva să dau doar un pseudocod nivel înalt explicația
din ceea ce am de gând să aibă de a face pentru căutare? Da.
[Elev] Tu iei doar mijlocul de matrice și de a vedea dacă ceea ce căutați pentru
este mai mică decât cea sau mai mult decât atât.
Și dacă e mai putin, te duci la jumătate mai puțin,
si daca e mai mult, te duci la jumătate e mai mult și să repeți până când veți obține doar un singur lucru.
[Bowden] Da.
Observați că numerele noastre de matrice este deja sortat,
și astfel acest lucru înseamnă că putem profita de acest lucru și am putea verifica în primul rând,
ok, caut numărul 50.
Deci, eu pot merge în mijloc.
Mijlociu este greu de definit, atunci când este un număr par de lucruri,
dar hai să spunem că vom trunchia mereu la mijloc.
Deci, aici avem 8 lucruri, astfel încât mijloc ar fi 16.
Caut 50, deci 50 este mai mare de 16.
Asa ca acum pot trata practic matrice mea ca aceste elemente.
Pot să arunc totul, de la 16 de peste.
Acum matrice mea este doar aceste 4 elemente, și repet.
Deci, atunci vreau să găsesc mijlocul din nou, care va fi 42.
42 este mai mică de 50, așa că am putea arunca departe aceste două elemente.
Aceasta este matrice mea rămasă.
Am de gând să găsească mijloc din nou.
Cred că 50 a fost un exemplu rău pentru că am fost mereu arunci lucrurile la stânga,
dar de aceeași măsură, în cazul în care caut ceva
și e mai puțin decât elementul mă caută în prezent,
apoi m-am de gând să arunce totul pentru dreapta.
Deci, acum avem nevoie de a pune în aplicare acest lucru.
Observați că avem nevoie să treacă în dimensiune.
Noi nu putem, de asemenea, nevoie pentru a hard-cod dimensiune.
Deci, dacă vom scăpa de faptul că define # -
Bine.
Cum pot da seama ce frumos dimensiunea matrice numere prezent este?
>> Câte elemente sunt în număr de matrice?
[] Studențești numere, console,. Lungime?
[Bowden] care nu există în C.
Nevoie. Lungime.
Matricele nu au proprietăți, astfel încât nu există nici o proprietate lungime de matrice
care vă va oferi doar tu oricât de mult se întâmplă să fie.
[Elev] A se vedea cât de mult de memorie are și împartă de cât de mult - >> Da.
Deci, cum putem vedea câtă memorie are? >> [Elev] sizeof. Da >>, sizeof.
Sizeof este operatorul care va reveni dimensiunea matrice de numere.
Și asta va fi intregi toate acestea, de multe ori, există dimensiunea de un număr întreg
din moment ce e cât de mult de memorie este de fapt inițierea.
Deci, dacă vreau număr de lucruri în matrice,
apoi m-am de gând să doriți să împartă cu dimensiunea de un număr întreg.
Bine. Așa că lasă-mă să trec în mărime aici.
De ce am nevoie pentru a trece în dimensiune, la toate?
De ce nu pot doar să fac aici dimensiunea int = sizeof (carul cu fân) / sizeof (int)?
De ce nu funcționează asta?
[Elev] Nu este o variabilă globală.
Haystack [Bowden] există și ne trece în număr cât carul cu fân,
și aceasta este un fel de prefigurare a ceea ce va urma. Da.
[Elev] Haystack este doar referire la ea, așa că va reveni cât de mare este această trimitere.
Da.
Mă îndoiesc în curs pe care le-ați văzut încă stivă într-adevăr, nu?
Tocmai am vorbit despre asta.
Deci, în cazul în care toate stiva este de variabile dvs. vor fi stocate.
>> Orice memorie care este alocată pentru variabilele locale se întâmplă în stivă,
și fiecare funcție devine propriul spațiu pe stivă, cadrul său stiva proprie este ceea ce se numește.
Deci principal are rama stiva, și în interiorul acestuia este de gând să existe această matrice numere,
și o să fie de mărime sizeof (numere).
Se va avea dimensiunea de numere separate de o mărime de elemente,
dar faptul că toate viețile în interiorul cadrului stiva principal.
Când ne-am numi căutare, căutarea devine cadrul acestuia stivă proprie,
propriul spațiu pentru a stoca toate variabilele sale locale.
Dar aceste argumente - deci carul cu fân nu este o copie a acestui tablou întreg.
Noi nu trec în întreaga matrice ca o copie în căutare.
Ea trece doar o trimitere la matrice.
Deci, de căutare pot accesa aceste numere prin acest referință.
Este accesarea încă lucrurile care traiesc in interiorul cadrului principal pentru stivă,
dar în esență, când vom ajunge la pointeri, care ar trebui să fie în curând,
aceasta este ceea ce sunt indicii.
Pointeri sunt doar referiri la lucruri, și puteți utiliza indicii pentru a accesa lucruri
care sunt în cadre stack alte lucruri ".
Deci, chiar dacă numere este local principal, putem accesa încă o prin acest indicator.
Dar din moment ce e doar un pointer si e doar o referință,
sizeof (carul cu fân) returnează doar mărimea de referință în sine.
Ea nu se întoarce dimensiunea lucru este îndreptat spre.
Ea nu se întoarce dimensiunea reală a numerelor.
Și astfel acest lucru nu este de gând să lucreze ca vrem sa-l.
>> Întrebări cu privire la asta?
Pointeri va fi plecat în mod semnificativ mai mult în detaliu gory, în săptămânile care vor urma.
Și acesta este motivul pentru care o mulțime de lucruri pe care le vedeți, cele mai multe lucruri de căutare sau de sortare lucruri,
ei aproape toate de gând să nevoie pentru a lua dimensiunea reală a matrice,
deoarece în C, nu avem nici o idee despre ce dimensiunea matrice este.
Ai nevoie să treci manual inch
Și nu poți trece manual în întreaga matrice pentru ca esti doar in trecere în referință
și nu poate obține dimensiunea de referință.
Bine.
Deci, acum vrem să pună în aplicare ceea ce a fost explicat mai înainte.
Puteți lucra pe el pentru un minut,
și nu trebuie să vă faceți griji despre obținerea totul perfect 100% de lucru.
Doar scrie până pseudocod jumătate pentru modul în care credeți că ar trebui să funcționeze.
Bine.
Nu este nevoie să fie complet terminat cu asta încă.
Dar nimeni nu se simt confortabil cu ceea ce au până în prezent,
ca ceva putem lucra împreună?
Vrea cineva să se ofere voluntari? Sau voi alege la întâmplare.
Aceasta nu trebuie să fie dreptul de orice măsură, dar ceva ce putem modifica într-o stare de lucru.
[Elev] Sigur. Bine >>.
Deci, nu te poate salva de revizuire făcând clic pe pictograma mica Salvare.
Ești Ramya, nu? >> [Elev] Da. >> [Bowden] Ok.
Asa ca acum pot vedea revizuire dvs. și toată lumea poate trage în sus de revizuire.
Și aici avem - Ok.
Deci, sa dus cu Ramya soluție recursivă, care este cu siguranta o soluție valabilă.
Există două moduri în care puteți face aceasta problema.
Puteți face, fie ea iterativ sau recursiv.
Cele mai multe probleme pe care le întâmpină, care se poate face recursiv poate fi, de asemenea, face iterativ.
Deci, aici l-am făcut recursiv.
>> Are cineva vrea să definească ce înseamnă să facă o funcție recursivă?
[Elev] Când aveți o funcție în sine apel
și apoi apel în sine până când se iese cu adevărat și adevărat. Da >>.
O funcție recursivă este doar o funcție care se numește.
Există trei lucruri mari care o funcție recursivă trebuie să aibă.
Primul este evident, ea însăși cheamă.
A doua este cazul de bază.
Deci, la un moment dat funcția trebuie să se oprească de asteptare el însuși,
și asta e ceea ce cazul de bază este pentru.
Deci, aici, știm că ar trebui să ne oprim, ar trebui să ne dea în noastre de căutare
atunci când este egal cu începutul sfârșit - și vom trece peste ceea ce înseamnă că.
Dar în cele din urmă, ultimul lucru pe care e important pentru funcțiile recursive:
funcțiile trebuie să se apropie cumva cazul de bază.
Ca și în cazul în care nu ești actualizarea de fapt nimic, atunci când face al doilea apel recursiv,
dacă sunteți literalmente de asteptare doar funcția din nou cu aceleași argumente
și nu variabile globale s-au schimbat sau ceva,
niciodată nu va ajunge la cazul de bază, caz în care e de rău.
Acesta va fi o recursivitate infinită și un preaplin stivă.
Dar aici vedem că actualizarea se intampla deoarece suntem actualizarea începe sfârșitul + / 2,
suntem actualizarea argumentul final aici, suntem actualizarea argumentul început aici.
Deci, în toate apelurile recursive suntem actualizarea ceva. Bine.
Vrei să ne plimbe prin soluția? Sigur >>.
Sunt folosind SearchHelp, astfel încât de fiecare dată când fac acest apel de funcție
Am inceput de unde am caut în matrice și sfârșitul
de unde mă uit matrice.
>> La fiecare pas în cazul în care se spune că este elementul din mijloc, care este începutul sfârșitul anului + / 2,
este egal cu faptul că ceea ce căutăm?
Și dacă este, atunci l-am găsit, și cred că devine trecut la nivelul de recursivitate.
Și dacă asta nu e adevărat, atunci vom verifica dacă valoarea de mijloc a matrice este prea mare,
caz în care ne uităm la jumătatea stângă a matrice de gând la început până la indicele de mijloc.
Și în caz contrar vom face jumătate final.
[Bowden] Ok.
Sună bine.
Ok, deci un cuplu lucruri, și de fapt, acesta este un lucru foarte mare la nivel
că nu va trebui niciodată să știe de acest curs, dar este adevărat.
Funcții recursive, mereu auzit că sunt o afacere proastă
pentru că dacă te sun recursiv de prea multe ori, veți obține Stack Overflow
deoarece, așa cum am spus mai înainte, orice funcție devine cadru de stivă proprie.
Astfel, fiecare apel al funcției recursive devine rama stiva proprie.
Asa ca daca faceti 1000 apeluri recursive, veți obține 1000 de cadre stack,
și repede va conduce la a avea prea multe cadre stack și lucruri rupe doar.
Deci, de aceea funcțiile recursive sunt, în general, de rău.
Dar există un subset de funcții recursive frumos numit coada-recursive funcții,
și acest lucru se întâmplă să fie un exemplu de unul în care, dacă compilatorul observă acest
și ar trebui, cred că - în zăngănit dacă se trece-O2 de pavilion
atunci se va observa acest lucru este coada recursiv și va face lucrurile bine.
>> Acesta va reutiliza același cadru stiva de peste si peste din nou, pentru fiecare apel recursiv.
Și așa din moment ce te folosind aceeași stivă cadru, nu aveți nevoie să vă faceți griji cu privire la
stivă vreodată debordant, și, în același timp, cum ai spus mai înainte,
în cazul în care odată ce te vei întoarce adevărat, atunci ea trebuie să se întoarcă la toate aceste cadre stivei
și apelul de a zecea SearchHelp trebuie să se întoarcă la nouă, trebuie să se întoarcă la al 8-lea.
Așa că nu trebuie să se întâmple atunci când funcțiile sunt coada recursiv.
Și astfel ceea ce face ca această funcție recursivă este coada observa ca pentru orice apel dat la SearchHelp
apelul recursiv care se face este ceea ce se întoarce.
Deci, în primul apel pentru a SearchHelp, ne fie reveni imediat false,
imediat return true, sau vom face un apel recursiv la SearchHelp
în cazul în care ceea ce ne revin ca apelul este ceea ce se întoarce.
Și nu am putut face acest lucru, dacă am făcut ceva de genul int x = SearchHelp, retur x * 2,
doar cateva aleatoare schimbare.
>> Deci, acum, acest apel recursiv, acest int x = SearchHelp apelul recursiv,
nu mai este coada recursiv, pentru că, de fapt nu trebuie să se întoarcă
inapoi la un cadru teancului anterior, astfel că apelul precedent la funcția de
pot apoi face ceva cu valoarea de returnare.
Deci, acest lucru nu este recursiv coada, dar ceea ce am avut înainte de a se frumos coada recursiv. Da.
[Elev] nu ar trebui cazul a doua bază se verifică prima
pentru că ar putea exista o situație în care, atunci când se trece argumentul
ați începe = sfârșitul anului, dar ele sunt o valoare acul.
Problema a fost nu putem rula în cazul în care sfârșitul este valoarea ac
sau de a începe = sfârșitul anului, în mod corespunzător, start = sfârșitul
și nu ați verificat de fapt, ca o valoare deosebită încă,
apoi începe sfârșitul + / 2 este doar de gând să fie aceeași valoare.
Dar ne-am întors deja false și nu am verificat, de fapt valoarea.
Deci, cel puțin, în primul apel, în cazul în care dimensiunea este 0, atunci vrem să se întoarcă fals.
Dar dacă dimensiunea este 1, atunci pornire nu se va sfârși egal,
iar noi vom verifica cel puțin un element unic.
Dar cred că ai dreptate în care putem ajunge într-un caz în care încep + final / 2,
pornire se termină prin a fi la fel ca punct de pornire + sfârșit / 2,
dar niciodata nu am verificat, de fapt acel element.
>> Deci, dacă vom verifica Primul este elementul din mijloc valoarea căutăm,
atunci ne putem întoarce imediat adevărat.
Altfel, dacă acestea sunt egale, atunci nu e nici un punct în a continua
deoarece suntem doar de gând să actualizeze la un caz în care ne aflăm pe o matrice cu un singur element.
În cazul în care singur element nu este cel pe care îl căutăm,
atunci totul e bine. Da.
[Elev] lucru este că, deoarece dimensiunea este de fapt mai mare decât numărul de elemente din matrice,
există deja un decalaj - >> Deci va dimensiona -
[Elev] Spune dacă matrice a fost dimensiunea 0, atunci SearchHelp va verifica, de fapt carul cu fân de la 0
privind primul apel.
Matrice are dimensiunea 0, deci 0 este - >> Da.
Nu e un alt lucru pe care - ar putea fi bine. Să ne gândim.
Deci, dacă matrice a avut 10 elemente și un mijloc vom verifica este indicele 5,
deci suntem de verificare 5, și să spunem că valoarea este mai mică.
Deci suntem aruncat totul departe la 5 mai departe.
Deci, începe sfârșitul + / 2 va fi sfârșitul nostru nou,
Deci da, este întotdeauna o să rămână dincolo de sfârșitul matrice.
Dacă e un caz în cazul în care a fost par sau impar, atunci ne-ar verifica, să zicem, 4,
dar suntem încă departe aruncat -
Deci da, finalul este întotdeauna o să fie dincolo de sfârșitul efectiv al matrice.
Deci, avem toate elementele sunt axate pe, sfârșitul este întotdeauna o să fie unul după asta.
Și astfel, în cazul în care se începe niciodată sfârșit egal, suntem într-o matrice de dimensiune 0.
>> Un alt lucru m-am gândit e că sunt actualizarea început să se înceapă + sfârșitul / 2,
astfel încât acesta este cazul în care am avea probleme cu, în cazul în care încep + final / 2
este elementul suntem verificare.
Să zicem că am avut această matrice 10-element. Oricare ar fi.
Deci, începe sfârșitul + / 2 va fi ceva de genul acesta,
si daca asta nu e valoarea, spune că vrem să actualizați.
Valoarea este mai mare, așa că vrei să te uiți la această jumătate de matrice.
Deci, cum suntem actualizarea început, suntem actualizarea început să fie acum acest element.
Dar acest lucru poate încă mai funcționează, sau cel puțin foarte, puteți face de start + sfârșit / 2 + 1.
[Elev] Nu trebuie să fie înceapă + sfârșitul [neauzit] >> Da.
Am verificat deja acest element și știu că nu e cel pe care îl căutăm.
Deci, nu avem nevoie să actualizați început să fie acest element.
Ne putem sări peste ea și actualizarea începe să fie acest element.
Și există niciodată un caz, să spunem, că acest scop au fost,
așa începe atunci ar fi aceasta, porniți + sfârșitul / 2 ar fi aceasta,
încep + END - Da, cred că pot ajunge în recursivitate infinită.
Să zicem că e doar o matrice de dimensiune 2 sau o matrice de dimensiune 1. Cred că acest lucru va funcționa.
Deci în prezent, acest element de pornire este și la sfârșitul este 1 dincolo de ea.
Deci, elementul care vom verifica este aceasta,
și apoi când am actualizat început, suntem actualizarea început să fie 0 + 1/2,
care ne va termina din nou cu pornire fiind acest element.
>> Deci suntem de verificare același element de peste si peste din nou.
Deci, acesta este cazul în care la fiecare apel recursiv trebuie să actualizeze efectiv ceva.
Deci, avem nevoie să facem pornire + sfârșit / 2 + 1, sau altceva nu e un caz
în cazul în care nu suntem de fapt, actualizarea de pornire.
Toată lumea vedea că?
Bine.
Are cineva întrebări cu privire la această soluție sau orice comentariu mai mult?
Bine. Are cineva o au iterativ soluție care să ne putem uita la toate?
Credeți facem tot recursiv?
Sau, de asemenea, cred că, dacă ei deschis, atunci este posibil să aveți înlocuite cel anterior.
Are o salvați în mod automat? Eu nu sunt pozitive.
Are cineva au iterativ?
Putem merge pe jos prin ea împreună, dacă nu.
Ideea va fi aceeași.
Iterativ soluție.
Am de gând să doriți să faceți în esență aceeași idee
în cazul în care dorim să urmărească sfârșitul noua matrice și nou început de matrice
și de a face asta de peste si peste.
Și dacă ceea ce suntem urmărirea ca de început și de sfârșit vreodată se intersectează,
atunci nu l-am găsit și ne putem întoarce false.
Deci, cum fac asta? Oricine au sugestii sau cod pentru mine de a trage în sus?
[Elev] Fă o buclă în timp ce. Da >>.
Ai de gând să vrei să faci o buclă.
>> Credeți că aveți codul aș putea trage în sus, sau ce aveai de gând să sugereze?
[Elev] Cred că da. >> Regulă. Acest lucru face lucrurile mai ușor. Care a fost numele tău?
[Elev] Lucas.
Revizia 1. Bine.
Minima este ceea ce am numit începe înainte.
Up nu este destul de ceea ce am numit sfârșitul înainte.
De fapt, sfârșitul este acum în matrice. E un element ar trebui să ia în considerare.
Atat de scazut este 0, este de până dimensiunea matrice - 1,
iar acum suntem looping, și suntem de verificare -
Cred ca te poti plimba prin ea.
Care a fost gândirea ta prin asta? Plimbare ne codul.
[Elev] Sigur. Uită-te la valoarea carul cu fân în mijloc și să o compare cu acul.
Deci, dacă e mai mare decât acul, apoi doriți să - oh, de fapt, că ar trebui să fie invers.
Ai de gând să doriți să aruncați jumătatea dreaptă, și astfel da, care ar trebui să fie calea.
[Bowden] Deci, aceasta ar trebui să fie mai puțin? Este că ceea ce ai spus? >> [Elev] Da.
[Bowden] Ok. Mai puțin.
Deci, dacă ceea ce căutăm este mai mică decât la ceea ce ne dorim,
atunci da, vrem să aruncați jumătatea stângă,
ceea ce înseamnă că actualizarea se tot suntem în considerare
prin mutarea scăzut de la dreptul de matrice.
Acest lucru arată bine.
Cred că are aceeași problemă pe care am spus pe cel anterior,
în cazul în care în cazul în care scăzută este 0 și până este 1, atunci scazut + sus / 2 se va configura pentru a fi același lucru din nou.
>> Și chiar dacă nu e cazul, este încă mult mai eficient, cel puțin
pentru a arunca pur și simplu elementul de care tocmai am uitat la ceea ce știm este greșit.
Atât de jos în sus + / 2 + 1 - >> [elev] Asta ar trebui să fie o altă cale.
[Bowden] Sau acest lucru ar fi - 1 și celălalt ar trebui să fie + 1.
[Elev] Și ar trebui să existe o dublă semnul egalității. >> [Bowden] Da.
[Elev] Da.
Bine.
Și, în sfârșit, acum că avem această 1 + - 1 lucru,
este - ar putea să nu fie - este vreodată posibil pentru scăzut pentru a termina cu o valoare mai mare decât până?
Cred că singurul mod în care se poate întâmpla - Este posibil? >> [Elev] Nu stiu.
Dar, în cazul în care devine trunchiat și apoi devine minus 1 și că apoi - >> Da.
[Elev] Aceasta ar fi, eventual, dat peste cap.
Cred că ar trebui să fie bun doar pentru că
pentru ca aceasta să ajung mai mici ar trebui să fie egal, cred.
Dar dacă ele sunt egale, atunci nu ne-ar fi făcut în timp ce bucla pentru a începe cu
și ne-am întors ar fi valoarea. Deci, eu cred că suntem bine acum.
Observați că, deși această problemă nu mai este recursiv,
același tip de idei se aplică în cazul în care putem vedea cum acest atât de ușor se pretează
la o soluție recursivă de faptul că suntem doar actualizarea indicilor de peste si peste, din nou,
facem problema mai mici și mai mici, ne concentrăm pe un subset de matrice.
[Elev] Dacă scăzut este 0 și până este 1, acestea ar fi ambele 0 + 1/2, care ar merge la 0,
și apoi s-ar fi + 1, s-ar fi - 1.
[Elev] În cazul în care ne verificarea egalitate?
Ca și în cazul cel din mijloc este, de fapt acul?
Noi nu facem în prezent asta? Oh!
În cazul în care este -
Da. Noi nu doar putem face testul de aici pentru ca să spunem mijloc de fabricație -
[Elev] E ca si cum, de fapt, nu aruncați legat.
Deci, dacă vă aruncați legat, trebuie să-l verificați mai întâi sau orice altceva.
Ah. Da. >> [Elev] Da.
Deci, acum ne-am aruncat pe care am uitat la prezent,
ceea ce înseamnă că acum trebuie să aibă, de asemenea,
în cazul în care (carul cu fân [(low + sus) / 2] == ac), atunci ne putem întoarce adevărat.
Și dacă am pus altceva sau doar în cazul în care, literalmente înseamnă același lucru
deoarece acest lucru ar fi adevărat întors.
Asa ca am sa pun altceva, dacă, dar nu contează.
>> Deci, în cazul în care acest altceva, altceva acest lucru, și acesta este un lucru comun să fac
în cazul în care, chiar dacă acesta este cazul în care totul este bine aici,
cum ar fi scăzut nu poate fi mai mare decât în ​​sus, nu e raționamentul în valoare de aproximativ dacă asta e adevărat.
Deci, s-ar putea la fel de bine spune în timp ce mică este mai mică sau egală cu
sau în timp ce mică este mai mică de
așa că, dacă acestea sunt vreodată egale sau foarte scăzute se întâmplă să treacă în sus,
atunci putem iesi din aceasta bucla.
Întrebări, probleme, comentarii?
Bine. Acest lucru arată bine.
Acum vrem să facem un fel.
Dacă mergem la revizuirea a doua mea, vom vedea aceste aceleași numere,
dar acum nu mai sunt sortate în ordine.
Și dorim să pună în aplicare un fel folosind orice algoritm în O de n log n.
Deci, care algoritmul crezi că ar trebui să pună în aplicare aici? >> [Elev] Merge sortare.
[Bowden] Da. Merge fel este O (n log n), asa ca asta e ceea ce am de gând să fac.
Și problema va fi destul de asemănătoare,
în cazul în care acesta se pretează cu ușurință la o soluție recursivă.
Ne poate veni, de asemenea, cu o soluție iterativ, dacă vrem,
dar recursivitate va fi mai ușor aici, iar noi ar trebui să facem recursivitate.
Cred că vom merge prin sortare îmbinare în primul rând,
deși există un video minunat pe un fel de îmbinare deja. [Râsete]
Îmbinare așa fel, există - Sunt pierd atât de mult din această lucrare.
Oh, există o singură stânga.
Deci îmbinare.
Oh, 1, 3, 5.
Bine.
Merge ia două matrice distincte.
Individual, aceste două tablouri sunt ambele sortate.
Deci această matrice, 1, 3, 5, sortate. Această matrice, 0, 2, 4, sortate.
Acum, ce trebuie să faceți este de îmbinare a le combina într-o singură matrice, care este ea însăși sortate.
Deci, vrem o serie de marimea 6, care va avea aceste elemente în interiorul acestuia
sortate în ordine.
>> Și astfel putem profita de faptul că aceste două matrice sunt sortate
pentru a face acest lucru în timp liniar,
sensul timpului liniar în cazul în care această matrice este format x si y este dimensiunea,
apoi algoritmul totală ar trebui să fie O (x + y). Bine.
Deci, traduceri.
[Elev] Putem porni de la stânga?
Deci, vă veți pune 0 în jos mai întâi și apoi 1 și apoi aici, esti la 2.
Deci e un fel de ai o filă care se mișcă spre dreapta. >> [Bowden] Da.
Pentru ambele aceste tablouri, dacă ne concentrăm doar pe elementul cel mai din stânga.
Deoarece ambele matrice sunt sortate, știm că aceste 2 elemente
sunt cele mai mici elemente din matrice, fie.
Deci asta înseamnă că 1 din aceste 2 elemente trebuie să fie mai mic element din gama noastră îmbinată.
Pur și simplu așa se întâmplă că cea mai mică este cea de pe dreapta de data asta.
Deci, vom lua 0, introduceți-l în stânga deoarece 0 este mai mic decât 1,
astfel încât să ia 0, introduceți-l în poziția noastră în primul rând, și apoi vom actualiza acest
să se concentreze acum pe primul element.
Și acum vom repeta.
Deci, acum vom compara 2 și 1. 1 este mai mică, așa că vom introduce 1.
Noi actualizăm acest indicator pentru a indica tipul ăsta.
Acum, o facem din nou, așa 2. Acest lucru se va actualiza, compara aceste 2, 3.
Acest actualizări, apoi 4 și 5.
Așa că este de îmbinare.
>> Ar trebui să fie destul de evident că este timpul liniar, deoarece vom merge doar pe fiecare element de dată.
Și asta este cel mai mare pas pentru punerea în aplicare sortare îmbinarea face acest lucru.
Și nu e așa de greu.
Câteva lucruri să vă faceți griji despre este să zicem că a fost fuzionarea 1, 2, 3, 4, 5, 6.
În acest caz, vom ajunge în scenariul în care aceasta va fi mai mică,
atunci vom actualiza acest indicator, acesta va fi mai mic, actualiza această,
asta e mai mic, iar acum va trebui să recunoască
atunci când v-ați alerga efectiv de elemente pentru a compara cu.
Din moment ce am folosit deja acest tablou întreg,
totul în această matrice este acum doar introdus în aici.
Deci, dacă vom rula vreodată în punctul în care unul din tablouri noastre este complet fuzionat deja,
atunci vom lua doar toate elementele altă matrice și introduceți-le în capătul matrice.
Deci, putem insera doar 4, 5, 6. Bine.
Acesta este un lucru să fiți atenți pentru.
De punere în aplicare, care ar trebui să fie pasul 1.
Merge apoi sortați pe baza asta, e 2 pasi, 2 trepte stupide.
Să-i dăm doar această matrice.
Îmbinare așa fel, pasul 1 este de a sparge recursiv matrice în jumătăți.
Împărțit astfel încât această matrice în jumătăți.
Avem acum 4, 15, 16, 50 și 8, 23, 42, 108.
Și acum o facem din nou și ne-am despărțit în aceste jumatati.
Vreau doar să-l fac pe partea asta.
Deci 4, 15 și 16, 50.
Ne-ar face același lucru aici.
Și acum am impartit in jumatati din nou.
Și avem 4, 15, 16, 50.
Așa că este cazul nostru de bază.
Odată ce matrice sunt de dimensiune 1, apoi ne oprim cu divizare în jumătăți.
>> Acum ce facem cu asta?
Am ajuns, de asemenea, acest lucru va rupe în jos în 8, 23, 42, și 108.
Deci, acum că suntem la acest punct, pasul acum doi fel de fuziune este fuzionează doar perechi la listele.
Așa că vrem să fuzioneze acestea. Noi numim doar îmbinare.
Stim îmbinare va reveni la acestea pentru sortat.
4, 15.
Acum vrem să fuzioneze acestea, și că se va întoarce o listă cu cele în ordine sortate,
16, 50.
Noi cei îmbinare - Eu nu pot scrie - 8, 23 și 42, 108.
Deci avem perechi îmbinate dată.
Acum ne uni din nou doar.
Observați că fiecare dintre aceste liste sunt sortate în sine,
și apoi putem îmbina doar aceste liste pentru a obține o listă de marimea 4, care este sortată
și îmbinarea acestor două liste pentru a obține o listă de marimea 4, care este sortat.
Și, în sfârșit, putem fuziona cele două liste de marimea 4 pentru a obține o listă de dimensiune 8, care este sortat.
Deci, pentru a vedea că acest lucru este total n log n, am văzut că deja de îmbinare este liniar,
asa ca atunci cand avem de a face cu fuziunea acestora, astfel cum ar fi costul total al îmbinării
pentru aceste două liste se află la doar 2, deoarece -
Sau bine, e de n O, dar n aici este doar aceste 2 elemente, asa ca e 2.
Și aceste 2 vor fi 2 si aceste 2 vor fi 2 si aceste 2 va fi de 2,
deci peste toate se contopește de care avem nevoie pentru a face, am ajunge să faci n.
Ca 2 + 2 + 2 + 2 este 8, care este n,
astfel încât costul de a fuziona în acest set este n.
Și apoi același lucru aici.
Vom fuziona aceste 2, atunci acestea 2, și individual această îmbinare va dura patru operațiuni,
această îmbinare va dura patru operații, dar, din nou, între toate acestea,
vom ajunge fuzionarea n lucruri totale, și așa acest pas ia n.
Și astfel fiecare nivel are n elemente fiind îmbinate.
>> Și cum de multe niveluri sunt acolo?
La fiecare nivel, gama noastră crește de dimensiunea 2.
Aici matrice noastre sunt de dimensiune 1, aici sunt de dimensiuni 2, aici sunt de marimea 4,
și, în sfârșit, sunt de dimensiune 8.
Deci, din moment ce este dublarea, se va fi un total de log n dintre aceste niveluri.
Deci, cu log n niveluri, fiecare nivel individual, ținând n totalul operațiunilor,
avem un log n n algoritm.
Întrebări?
S-au făcut deja progrese persoane cu privire la modul de a pune în aplicare acest lucru?
Este cineva deja într-o stare în care pot trage doar până codul lor?
Pot să dau un minut.
Acesta va fi mai mare.
Am foarte recomanda repete -
Tu nu trebuie să faci recursia pentru îmbinare
pentru că a făcut recursie pentru îmbinare, ai de gând să trebuie să treacă un buchet de diferite dimensiuni.
Poți, dar e enervant.
Dar recursia pentru sortare în sine este destul de ușor.
Trebuie doar sunați pur și simplu un fel pe jumătatea din stânga, sortare pe jumătatea din dreapta. Bine.
Oricine are ceva ce poate trage încă?
Sau altceva să-ți dau un minut.
Bine.
Oricine are ceva ce putem lucra cu?
Sau altfel vom lucra doar cu acest lucru și apoi extindeți de acolo.
>> Oricine are mai mult decât aceasta, care pot trage în sus?
[Elev] Da. Puteți trage în sus a mea. >> Regulă.
Da!
[Elev] Au fost o mulțime de condiții. Oh >>, trage. Poți -
[Elev] Trebuie să-l salveze. Da >>.
Așa că am făcut îmbinare separat.
Oh, dar nu e așa de rău.
Bine.
Deci, este ea însăși un fel de asteptare la doar mergeSortHelp.
Să ne explice ce face mergeSortHelp.
[Elev] MergeSortHelp destul de mult face două etape principale,
care este de a sorta fiecare jumătate din matrice și apoi să fuzioneze amândoi.
[Bowden] Ok, deci da-mi o secundă.
Cred că acest lucru - >> [elev] am nevoie pentru a -
Da. Îmi lipsește ceva.
În îmbinare, îmi dau seama că am nevoie pentru a crea o gamă nouă
pentru că nu am putut face in locul. Da >>. Tu nu poți. Corectează.
[Elev] Așa că am crea o matrice nouă.
Am uitat la sfârșitul anului îmbinare a re-schimbe.
Bine. Avem nevoie de un nou tablou.
Intr-un fel de îmbinare, acest lucru este aproape întotdeauna adevărat.
O parte din costul unui algoritm mai bine timpul-înțelept
este aproape întotdeauna nevoie pentru a utiliza memoria un pic mai mult.
Deci, aici, indiferent cum faci îmbinare sortare,
va trebui în mod inevitabil de a utiliza unele de memorie suplimentar.
El sau ea a creat o matrice nouă.
Și apoi spui la sfârșitul trebuie doar să copiați matrice nou în matrice originală.
[Elev] Cred că da, da.
Nu știu dacă asta funcționează în termeni de numărare de referință sau orice -
Da, acesta va funcționa. >> [Elev] Ok.
Credeți că încercați să rulați acest lucru? >> [Elev] Nu, nu încă. Bine >>.
Încercați să rulați-l, iar apoi voi vorbi despre asta pentru o secunda.
[Elev] am nevoie pentru a avea toate prototipurile de funcții și totul, totuși, nu?
Funcția de prototipuri. Oh, vrei sa spui ca - Da.
Sortare este de asteptare mergeSortHelp.
>> Deci, în scopul de a apela pentru sortare mergeSortHelp, mergeSortHelp trebuie să fie au fost definite
înainte de a sortare sau am nevoie doar de prototip. Doar copiați și lipiți acest lucru.
Și în mod similar, mergeSortHelp este de asteptare îmbinare,
dar îmbinării nu a fost definit încă, astfel încât să putem lăsa să știu mergeSortHelp
că asta e ceea ce se întâmplă fuziona pentru a arata ca, și cu asta basta.
Deci, mergeSortHelp.
Avem o problemă aici, în cazul în care nu avem nici un caz de bază.
MergeSortHelp este recursiv, astfel încât orice recursiv funcția
este de gând să nevoie de un fel de scenariu de bază să știu când să se oprească recursiv se asteptare.
Ceea ce este cazul nostru de bază va fi aici? Da.
[Elev] Dacă dimensiunea este de 1? >> [Bowden] Da.
Deci, cum am văzut acolo, ne-am oprit matrice de divizare
odată ce am intrat în matrice de dimensiune 1, care în mod inevitabil, sunt ele însele sortate.
Deci, în cazul în care dimensiunea este egal cu 1, știm matrice este deja sortat,
astfel încât să putem reveni pur și simplu.
>> Observați că e nul, așa că nu se mai întorc nimic special, doar ne întoarcem.
Bine. Așa că e cazul nostru de bază.
Cred cazul nostru de bază ar putea fi, de asemenea, în cazul în care se întâmplă să fie fuzionarea o serie de mărimea 0,
am dori probabil să se oprească la un moment dat,
astfel încât să putem spune doar dimensiune mai mică de 2 sau mai mic sau egal cu 1
astfel că aceasta va lucra pentru orice matrice acum.
Bine.
Așa că e cazul nostru de bază.
Acum, vrei să ne plimbe prin îmbinare?
Ce înseamnă toate aceste cazuri?
Până aici, facem doar aceeași idee, -
[Elev] am nevoie pentru a fi trece dimensiunea cu toate apelurile mergeSortHelp.
Am adăugat dimensiune ca un primar suplimentară și nu e acolo, cum ar fi dimensiunea / 2.
[Bowden] Oh, mărimea / 2, marimea / 2. >> [Elev] Da, și, de asemenea, în funcție de mai sus, precum și.
[Bowden] Aici? >> [Elev] Doar dimensiune. >> [Bowden] Oh. Dimensiune, dimensiunea? >> [Elev] Da.
[Bowden] Ok.
Lasă-mă să mă gândesc o secundă.
Nu am alerga într-o problemă?
Suntem mereu tratarea lăsat ca 0. >> [Elev] Nr
Asta e bine prea. Scuze. Ar trebui să fie început. Da.
[Bowden] Ok. Îmi place că o mai bună.
Și sfârșitul. Bine.
Deci, acum vrei să ne plimbe prin îmbinare? >> [Elev] Ok.
Sunt doar de mers pe jos prin acest matrice nou pe care l-am creat.
Dimensiunea acesteia este dimensiunea porțiunii de matrice pe care ne-o dorim să fie sortate
și încercarea de a găsi elementul pe care ar trebui să pună în pasul matrice nou.
Deci, pentru a face acest lucru, în primul rând mă verifica dacă jumătatea stângă a matrice continuă să aibă elemente de nici mai mult,
si daca nu, atunci te duci la altcineva această condiție, care spune doar
bine, trebuie să fie în matrice dreapta, și vom pune că, în indicele actual de newArray.
>> Și apoi altfel, eu sunt de verificare în cazul în partea dreaptă a matrice este, de asemenea, terminat,
caz în care am pus în stânga.
Asta nu s-ar putea fi de fapt necesar. Nu sunt sigur.
Dar oricum, celelalte două verificarea care dintre cele două este mai mic, în stânga sau dreapta.
Și, de asemenea, în fiecare caz, în funcție de incrementare eu am substituent incrementa.
[Bowden] Ok.
Asta arată bine.
Are cineva comentarii sau nelămuriri sau întrebări?
Deci, cele patru cazuri pe care le avem pentru a aduce lucrurile în doar a fi - sau se pare ca cinci -
dar trebuie să ia în considerare dacă matrice stânga a alerga afară de lucruri pe care trebuie să fuzioneze,
dacă matrice dreptul de a alerga afară de lucruri pe care trebuie să fuzioneze -
Mă îndreptat de la nimic.
Deci, dacă matrice stânga a alerga afară de lucruri sau de matrice dreapta a alerga afară de lucruri.
Acestea sunt două cazuri.
Avem nevoie, de asemenea, cazul banal dacă chestia din stânga este mai mică decât un lucru bun.
Apoi ne-am dori să alegeți ceva din stânga.
Acestea sunt cazuri.
Deci asta a avut dreptate, așa că e asta.
Matrice a plecat. E 1, 2, 3. Bine. Deci da, acelea sunt cele patru lucruri pe care le-ar putea dori să facă.
Și nu vom trece peste o soluție iterativ.
Eu nu as recomanda -
Merge fel este un exemplu de o funcție care este atât de coada nu recursiv,
nu e ușor să-l facă coadă recursiv,
dar, de asemenea, nu este foarte ușor de a face iterativ.
Acest lucru este foarte ușor.
Acest fel de punerea în aplicare a îmbinării,
îmbinare, indiferent de ceea ce faci, te duci pentru a construi merge.
>> Deci, îmbinare fel construit pe partea de sus a îmbinării recursiv este doar aceste trei linii.
Iterativ, este mai enervant și mai greu să se gândească.
Dar observați că nu e coadă recursiv deoarece mergeSortHelp - atunci când se solicită în sine -
trebuie încă să facă lucruri după acest întoarce apelul recursiv.
Deci, acest cadru trebuie să stiva continuă să existe chiar și după acest apel.
Și apoi când apelați acest lucru, cadru stiva trebuie să continue să existe
deoarece chiar și după acest apel, avem încă nevoie de a fuziona.
Și este netrivial de a face acest coada recursiv.
Întrebări?
Bine.
Deci, merge înapoi pentru a sorta - oh, sunt două lucruri pe care vreau să le arăt. Bine.
Revenind la fel, vom face acest lucru rapid.
Sau de căutare. Sortare? Sortare. Da.
Revenind la începuturile fel.
Dorim să creați un algoritm care sortează matrice folosind orice algoritm
în O de n.
Deci, cum este posibil acest lucru? Are cineva orice fel de -
Am sugerat mai sus la -
Dacă suntem pe cale de a îmbunătăți de la n log n O din N,
ne-am îmbunătățit algoritmul nostru de timp-înțelept,
ceea ce înseamnă că ceea ce vom avea nevoie să facă pentru a compensa pentru asta?
[Elev] Space. Da >>. Vom folosi mai mult spațiu.
Și nici măcar nu doar de mai mult spațiu, e mai mult spațiu exponențial.
Deci, eu cred că acest tip de algoritm este ceva pseudo, pseudo polynom -
pseudo - nu mi le amintesc. Pseudo ceva.
Dar e pentru că avem nevoie de a utiliza atât de mult spațiu
că acest lucru este realizabil, dar nu este realist.
>> Și cum putem realiza acest lucru?
Putem realiza acest lucru, dacă putem garanta faptul că orice element special în matrice
este sub o anumită dimensiune.
Deci, hai să spunem că dimensiunea este de 200,
orice element într-o matrice este sub dimensiunea 200.
Și acest lucru este de fapt foarte realist.
Puteți foarte ușor avea o matrice ca stii totul în ea
va fi mai mică de un numar.
Ca și în cazul în care aveți unele vector absolut masiv sau ceva de genul
dar tu știi totul va fi între 0 și 5,
atunci va fi mult mai rapid de a face acest lucru.
Și legat pe oricare dintre elementele este de 5,
Deci, acest legat, care este cât de mult de memorie ai de gând să fie folosind.
Deci, legat este de 200.
În teorie, există întotdeauna o legat, deoarece un număr întreg poate fi doar până la 4 miliarde de euro,
dar asta e nerealist, deoarece atunci am fi folosind spațiul
pe ordinea de 4 miliarde de euro. Deci asta e nerealist.
Dar aici vom spune legat nostru este de 200.
Trucul pentru a face-o în O a lui n este facem un alt array numit număr de dimensiuni legat.
Deci, de fapt, aceasta este o scurtătură pentru - Eu de fapt nu știu dacă zăngănit face acest lucru.
Dar, în CCG, cel puțin - zăngănit Sunt presupunând că nu prea -
acest lucru va inițializa doar matrice întregul să fie 0s.
Deci, dacă nu vreau să fac asta, atunci am putea face separat pentru (int i = 0;
i <Bound; i + +) și a numărului de [i] = 0;
Deci, acum totul este initializat cu 0.
Am itera peste matrice mea,
și ceea ce fac este Contez numărul fiecărui - Să mergem în jos aici.
Avem 4, 15, 16, 50, 8, 23, 42, 108.
Ceea ce am de numărare este numărul de apariții ale fiecăruia dintre aceste elemente.
Să adăugăm, de fapt un cuplu mai în aici cu unele repetă.
Deci, valoarea avem aici, valoarea de care se va fi matrice [i].
Deci val ar putea fi 4 sau 8 sau orice altceva.
Și acum mă bazez cât de mulți dintre valoarea pe care le-am văzut,
deci conteaza [val] + +;
După ce se face acest lucru, numărul este de gând să arate ceva de genul 0001.
Să facem conteaza [val] - RESPECTAȚI + 1.
>> Acum, că e doar pentru a explica faptul că suntem incepand de la 0.
Deci, în cazul în care 200 va fi cel mai mare număr noastră,
apoi 0 la 200 este de 201 lucruri.
Deci contează, o să arate ca și cum 00001 pentru că avem un 4.
Apoi vom avea 0001 în cazul în care vom avea un 1 în indicele de 8 count.
Vom avea un 2 în indexul 23 a numărului de.
Vom avea un 2 în indicele a 42-a conta.
Astfel încât să putem folosi numărătoarea.
Deci, num_of_item = numărul [i].
Și astfel, în cazul în care num_of_item este 2, ceea ce înseamnă că doriți să inserați 2 din numărul I
în gama noastră sortate.
Deci, avem nevoie pentru a urmări cât de departe suntem în matrice.
Deci, indicele = 0.
Array - Voi scrie doar.
Numără -
array [index + +] = i;
Asta e ceea ce vreau? Cred că e ceea ce vreau.
Da, asta arata bine. Bine.
Deci, nu toată lumea înțelege ce scopul de matrice mea contează este?
Acesta este de numărare numărul de apariții ale fiecăruia dintre aceste numere.
Apoi am iterarea peste asta contează matrice,
și poziția lea în matrice contează
este numărul de i e că ar trebui să apară în matrice mea sortate.
De aceea, numărul de 4 va fi 1
și capete de acuzare de 8 este de gând să fie de 1, 23 capete de acuzare de va fi 2.
Deci, asta e modul în care mulți dintre ei doresc să inserați în matrice mea sortate.
Apoi am făcut asta.
Sunt inserarea num_of_item i e în matrice mea sortate.
>> Întrebări?
Și astfel, din nou, aceasta este timpul liniar, deoarece suntem doar iterarea peste această dată,
dar este, de asemenea, liniară în ceea ce acest număr se întâmplă să fie,
și așa mult depinde de ceea ce este legat.
Cu o consolidat de 200, care nu e așa de rău.
Dacă legat dumneavoastra va fi 10.000, atunci asta e un pic mai rău,
dar daca legat dumneavoastră va fi de 4 miliarde de euro, care este complet nerealist
și această matrice va trebui să fie de marimea 4 miliarde de euro, ceea ce este nerealist.
Deci asta e. Întrebări?
[Răspuns studentul nu pot fi auzite] >> Ok.
Am realizat un lucru atunci când am trecut prin.
Eu cred că problema a fost în Lucas lui și, probabil, fiecare dintre noi am văzut.
Am uitat complet.
Singurul lucru pe care am vrut să comenteze este că atunci când ai de a face cu lucruri cum ar fi indici,
nu veți vedea niciodată cu adevărat acest lucru atunci când scrii un pentru buclă,
dar punct de vedere tehnic, ori de câte ori ai de a face cu aceste indici,
ar trebui să destul de mult întotdeauna a face cu numere întregi fără semn.
Motivul pentru acest lucru este atunci când ai de a face cu numere întregi semnate,
așa că, dacă ai 2 numere întregi semnate și le adăugați împreună
și ei sfârșesc prea mare, atunci va termina cu un număr negativ.
Deci, asta e ceea ce este de tip integer overflow.
>> Dacă am adăuga 2 miliarde de 1 miliard, am termina cu negativ 1 miliard.
Asta e modul în care întregi funcționează pe computere.
Deci, problema cu ajutorul -
Asta e bine, cu excepția, dacă se întâmplă să fie redusă 2 miliarde pana se întâmplă să fie 1 miliarde de euro,
atunci aceasta va fi negativă 1 miliard și apoi vom împărți că la 2
și se încheie cu negativ 500 de milioane.
Deci, aceasta este doar o problemă în cazul în care se întâmplă să fie în căutarea printr-o matrice
de miliarde de lucruri.
Dar dacă se întâmplă + mic până la revărsare, atunci este o problemă.
De îndată ce am să le facă nesemnate, apoi 2 miliarde și 1 miliard este de 3 miliarde de euro.
3 miliarde împărțit la 2 este de 1,5 miliarde de euro.
Asa ca imediat ce acestea sunt nesemnat, totul este perfect.
Și așa e, de asemenea, o problemă atunci când scrii pentru bucle,
si de fapt, probabil că o face în mod automat.
Acesta va țipa de fapt, doar la tine.
Deci, în cazul în care acest număr este prea mare pentru a fi în doar un întreg, dar s-ar potrivi într-un număr întreg fără semn,
se va țipa la tine, asa ca asta e motivul pentru nu vă place foarte rula în cauză.
Puteți vedea că un index nu este niciodată de gând să fie negativ,
și așa că atunci când ești iterarea peste o matrice,
poti spune aproape întotdeauna nesemnate int i, dar nu aveți cu adevărat să.
Lucrurile sunt de gând să lucreze destul de mult la fel de bine.
Bine. [Șoptește] Cât e ceasul?
Ultimul lucru pe care am vrut să arate - și voi face doar o foarte repede.
Știi cum ne-am # define astfel încât să putem defini # MAX ca 5 sau ceva?
Să nu facem MAX. # Define RESPECTAȚI ca 200. Asta e ceea ce am făcut înainte.
Care definește o constantă, care este doar de gând să fie copiat și inserat
ori de câte ori se întâmplă să scrie legat.
>> Astfel încât să putem face de fapt mai mult cu # definește.
Putem defini # funcții.
Ei nu sunt cu adevărat funcții, dar vom numi funcții.
Un exemplu ar fi ceva de genul MAX (x, y) este definit ca (x <y y:? X). Bine.
Deci, ar trebui să te obișnuiești cu sintaxa operatorul ternar,
dar este mai mic decât y x? Întoarceți-y, x reveni altceva.
Deci, puteți vedea puteți face această funcție separată,
și funcția ar putea fi ca bool MAX are 2 argumente, returnați.
Aceasta este una dintre cele mai comune pe care le văd făcut așa. Noi le numim macrocomenzi.
Aceasta este o macrocomandă.
Acesta este doar sintaxa pentru ea.
Puteți scrie o macrocomandă pentru a face tot ce vrei.
Veți vedea frecvent macro-uri pentru depanare printfs si alte chestii.
Deci, un tip de printf, sunt constante speciale în C ca subliniere LINE subliniere,
2 subliniază LINE subliniere,
și nu există, de asemenea, cred ca 2 subliniaza FUNC. Asta ar putea fi ea. Ceva de genul asta.
Aceste lucruri vor fi înlocuite cu denumirea funcției
sau numărul liniei pe care esti pe.
Cele mai frecvente, scrii printfs depanare că aici am putea apoi a scrie pur și simplu
DEBUG și va imprima numărul de linie și funcția pe care I se întâmplă să fie în
că a întâlnit această declarație DEBUG.
Și puteți imprima, de asemenea, alte lucruri.
Deci, un lucru pe care ar trebui să fiți atenți pentru este dacă se întâmplă să definească # DOUBLE_MAX
ca ceva de genul 2 * 2 * y și x.
Deci, pentru un motiv, se întâmplă să faci asta foarte mult.
Deci, face o macrocomandă.
Aceasta este de fapt rupt.
Mi-ar numi de a face ceva de genul DOUBLE_MAX (3, 6).
Deci, ce ar trebui să fie returnate?
[Elev] 12.
Da, ar trebui să fie returnate 12, și 12 este returnat.
3 se înlocuiește pentru x, 6 se înlocuiește pentru y, și ne întoarcem 2 * 6, care este de 12.
Acum, ce zici de asta? Ce ar trebui să fie returnate?
[Elev] 14. În mod ideal >>, 14.
Problema este că modul în care hash definește locul de muncă, nu uitați că este o copie literală și lipire
de tot ceea ce destul de mult, deci ce acest lucru se întâmplă să fie interpretat în sensul că
este de 3 mai puțin de 1 plus 6, de 2 ori 1 plus 6, 2 ori 3.
>> Deci, pentru acest motiv aproape întotdeauna infasurati totul în paranteze.
Orice variabilă, aproape întotdeauna înveliți în paranteze.
Există cazuri în care nu trebuie să, așa cum știu că nu am nevoie să faci asta aici
pentru că este mai puțin destul de mult întotdeauna doar de gând să lucreze,
deși faptul că ar putea să nu fie chiar adevărat.
Dacă există ceva ridicol ca DOUBLE_MAX (1 == 2),
apoi că va fi înlocuit cu 3 mai puțin de 1 egal este egal cu 2,
și așa mai departe, apoi se va face 3 mai puțin de 1, nu ca egal 2,
care nu este ceea ce ne dorim.
Deci, în scopul de a preveni orice probleme de operator de precedență,
întotdeauna înveliți în paranteze.
Bine. Și asta e tot, 5:30.
Dacă aveți orice întrebări cu privire PSET, anunțați-ne.
Ar trebui să fie distractiv, iar ediția hacker, de asemenea, este mult mai realist
decât ediția hacker de anul trecut, așa că am speranța că o mulțime dintre voi încerca.
Anul trecut a fost foarte copleșitoare.
>> [CS50.TV]