[MUSIC JOC] 

PROFESORUL: Bine. Aceasta este CS50 și acest lucru este la sfârșitul săptămânii trei. Deci suntem astăzi aici, nu-Sanders în Teatru, în schimb în Weidner Library. In interiorul care este un studio cunoscut sub numele de Hauser Studio, sau să spunem Studio H, sau trebuie noi say-- Dacă va plăcut că gluma, este de fapt de la coleg de clasa, Mark, on-line, care a sugerat ca mai mult prin intermediul Twitter. Acum, ce e cool despre fiind aici, într-un studio este că eu sunt înconjurat de acestea verde pereți, un ecran verde sau chromakey, ca să spunem așa, ceea ce înseamnă că este CS50 echipa de producție, fără știrea mine acum, ar putea fi punerea ma mai oriunde în lume, pentru bine și la rău. 

Acum, ceea ce se află în perspectivă, problema set două este în mâinile tale pentru această săptămână, dar cu problema set trei în această săptămână vine, va fi contestată cu așa-numitul joc de 15, o parte favoarea vechi, care s-ar putea aminti ce a primit ca un copil care are o grămadă de numere care pot aluneca în sus, în jos, stânga și la dreapta, și există un decalaj în puzzle, în care aveți poate aluneca de fapt aceste piese de puzzle. În cele din urmă veți primi acest puzzle în unele ordine aleatorie semi, iar scopul este de a sortare-l, de sus în jos, la stânga la dreapta, de la unul tot drumul până prin 15. 

Din păcate, implementarea veți avea la îndemână va fi software-ul bazat, nu fizic. Esti de fapt va trebui să scrie cod cu care un student sau utilizator poate juca acest joc de 15. Și, de fapt, în hacker ediție de joc de 15, vei fi o provocare pentru a pune în aplicare, nu doar redarea acestei școli vechi joc, ci mai degrabă rezolvarea de ea, de punere în aplicare modul Dumnezeu, ca să spunem așa, că, de fapt rezolvă puzzle pentru om, oferindu-le cu aluzie, după indiciu, după indiciu. Cu atât mai mult cu privire la acest săptămâna viitoare. Dar asta e ceea ce se află în fața. 

Pentru moment amintesc că la începutul acestei săptămâni am avut acest Cliffhanger, dacă vreți, prin care cele mai bune faceam de sortare înțelept a fost o limită superioară de mare o de n pătrat. Cu alte cuvinte, cu bule de sortare, fel de selecție, sortare prin inserție, toate acestea, în timp ce diferite în punerea lor în aplicare, involuat intr-o n pătrat rulează timp în cel mai rău caz foarte. Și, în general, vom presupune că cel mai rău caz pentru sortarea foarte este una care intrările dvs. sunt complet înapoi. Și într-adevăr, a fost nevoie de destul de câțiva pași să pună în aplicare fiecare dintre aceste algoritmi. 

Acum, la sfârșitul clasei Reamintim, am comparat cu bule fel împotriva selecție fel împotriva unui alt că am numit merge sort la momentul respectiv, și propunem o durează Beneficiază de o lecție de la săptămână la zero, divide și cuceri. Și atingerea într-un fel un fel de logaritmică timp de funcționare în cele din urmă, în loc de ceva asta e pur pătratică. Și nu e destul de logaritmică, e un pic mai mult decât atât. Dar dacă vă amintiți de la clasă, a fost mult, mult mai repede. Să aruncăm o privire la unde am rămas. 

Bubble sort versus selecție fel versus merge sort. Acum toate acestea sunt difuzate, în teorie, în același timp. Procesorul rulează la aceeași viteză. Dar puteti simti cat de plictisitor această este foarte repede va deveni, și cât de repede, atunci când ne-am injecta un pic de algoritmi săptămâni la zero, a putem accelera lucrurile. 

Deci, un fel marcă arată uimitor. Cum putem parghie, pentru Pentru a sorta numerele mai rapid. Ei bine, sa ne gandim din nou la un ingredient pe care le a avut din nou în săptămâna de zero, ca de căutarea cineva într-o carte de telefon, și reamintească faptul că pseudocod că ne-am propus, prin care putem găsi cineva ca Mike Smith, uitat un pic ceva de genul asta. 

Acum, ia o privire, în special, la linia 7 și 8, precum și 10 și 11, care induc că bucla, prin care ne-am păstrat merge înapoi la linia 3 din nou, și din nou, și din nou. Dar se pare că putem vedea acest algoritm, aici, în pseudocod, un pic mai mult holistic. De fapt, ceea ce caut la aici pe ecran, este un algoritm pentru căutarea Mike Smith printre unele set de pagini. Și într-adevăr, am putea simplifica acest algoritm în acele linii 7 și 8, și 10 și 11 să spun doar acest lucru, care am prezentat aici, în galben. Cu alte cuvinte, dacă Mike Smith este mai devreme în carte, nu avem nevoie să specificați pas cu pas acum cum sa-l găsesc. Noi nu trebuie să specificați pentru a reveni la linia 3, de ce nu ne-am în schimb, să zicem, mai general, caută Mike în jumătate din stânga a cărții. 

În schimb, în ​​cazul în care Mike este de fapt, mai târziu în carte, de ce nu ne-am cita doar de căutare încheiat citatul pentru Mike în jumătatea din dreapta a cărții. Cu alte cuvinte, de ce nu ne-am un fel de a ne spune punt, căuta Mike în acest subset de carte, și lăsați-l să existent nostru algoritm pentru a ne spune cum pentru a căuta Mike în că jumătate din stânga a cărții. Cu alte cuvinte, ne Algoritmul funcționează dacă este o carte de telefon a acestui grosime, de această grosime, sau orice fel de grosime. Deci, putem recursiv defini acest algoritm. Cu alte cuvinte, pe ecran aici, este un algoritm pentru căutarea Mike Smith printre paginile unei cărți de telefon. Deci, în conformitate 7 și 10, să doar spun exact asta. Și am folosi acest termen un moment Acum, și într-adevăr, recursivitate este buzzword pentru acum, și este acest proces de a face ceva ciclice de cumva folosind codul pe care le au deja, și de asteptare din nou, și din nou, și din nou. Acum va fi important pe care le într-un fel de jos afară, și nu face asta infinit de mult. În caz contrar, vom au într-adevăr o buclă infinită. Dar să vedem dacă putem împrumuta această idee de o recursivitate, a face ceva nou și din nou și din nou, pentru a rezolva problema de sortare prin îmbinare sort, cu atât mai eficient. 

Deci, eu vă dau merge sort. Hai să aruncăm o privire. Deci, aici este pseudocod, cu pe care am putea pune în aplicare de sortare, folosind acest algoritm numit merge sort. Și e destul de simplu acest lucru. Pe de intrare a n elemente, Cu alte cuvinte, dacă sunteți dat n elemente și numerele și litere sau indiferent de intrare este, dacă ți se dă elemente n, dacă n este mai mic de 2, doar reveni. Dreapta? Pentru că dacă n este mai mic decât 2, care înseamnă că lista mea de elemente este fie de dimensiuni 0 sau 1, și în ambele aceste cazuri triviale, lista este deja sortate. Dacă nu există nici o listă, este sortate. Și dacă există o listă de lungime 1, este evident sortate. Deci algoritmul are nevoie doar să într-adevăr ceva interesant, dacă avem două sau mai multe elemente ne-a dat. Deci, să ne uităm la magia atunci. Sorta altceva jumătatea stângă a elementelor, apoi sorta jumătatea dreaptă de elemente, apoi merge jumătățile sortate. Si ceea ce este un fel de spirit îndoire aici, este că nu prea par să ți-am spus nimic încă, nu? Tot ce am spus este, având în vedere o listă de n elemente, sorta jumătatea stângă, apoi jumătatea din dreapta, apoi fuziona jumatati sortate, dar în cazul în care este sos de secrete real? În cazul în care este algoritmul? Ei bine, se pare că cele două linii în primul rând, jumătate fel stânga de elemente, și un fel dreptul de jumătate din elemente, apeluri recursive, ca să spunem așa. 

La urma urmei, la acest moment, nu am un algoritm cu care sa sorta o grămadă de elemente? Da. E chiar aici. E chiar aici pe ecran, și așa că am putea folosi același set de pași pentru a sorta jumătatea stângă, ca pot jumătatea din dreapta. Și într-adevăr, din nou, și din nou. Deci, într-un fel sau altul, și vom curând vezi aceasta, magia de îmbinare fel este încorporat în acea finală line, care fuzionează jumătățile sortate. Și asta pare destul de intuitiv. Iei două jumătăți, și tu, într-un fel, merge împreună, si vom vedea acest lucru concret într-o clipă. 

Dar acest lucru este un algoritm complet. Și să vedem exact de ce. Ei bine, să presupunem că suntem dat aceste aceeași opt elemente aici pe ecran, una prin opt, dar sunt în ordine aleatorie aparent. Și obiectivul la îndemână este pentru a sorta aceste elemente. Ei bine, cum pot merge despre face asta folosind, din nou, merge sort, ca pe acest pseudocod? Și din nou, fixa acest lucru în mintea ta, doar pentru o clipă. Primul caz este destul de banal, dacă e mai mică de 2, doar întoarce, nu e nici o lucrare de făcut. Deci, într-adevăr există doar trei măsuri pentru a păstra într-adevăr în minte. Din nou, și din nou, eu sunt va doresc să aibă pentru a sorta jumătatea stângă, sorta jumătatea din dreapta, și apoi o dată lor două jumătăți sunt sortate, Vreau să le fuzioneze împreună într-o singură listă sortată. Astfel încât să păstreze în minte. 

Deci, aici e lista inițială. Să tratăm acest lucru ca pe un matrice, așa cum am început să în săptămâna doua, care este o bloc contiguu de memorie. In acest caz, conținând de opt numere, spate în spate în spate. Și să aplice acum merge sort. Deci, vreau mai întâi pentru a sorta jumătatea stângă a acestei liste, și să, prin urmare, se concentreze pe 4, 8, 6, și 2. 

Acum, cum pot să merg despre sortare o listă de dimensiuni 4? Ei bine, am să ia în considerare acum sortare în stânga jumătatea stângă. Din nou, să înapoi pentru un moment. Dacă Pseudocodul este aceasta, și am dat opt ​​elemente, 8 este evident mai mare mare sau egal cu 2. Deci, cu primul caz nu se aplică. Deci, pentru a sorta opt elemente, am mai întâi sorta jumătatea stângă de elemente, apoi m-am sorta jumătatea dreaptă, apoi m-am merge cele două jumătăți sortate, fiecare dintre dimensiuni 4. BINE. 

Dar dacă ați mi-a spus, sorta jumătate din stânga, care este acum de mărime 4, cum pot sorta jumătatea stângă? Ei bine, dacă am un intrare din patru elemente, Am sorta primul din stânga doi, apoi la dreapta cei doi, și apoi le merge împreună. Deci, din nou, acesta devine un pic de o minte îndoire joc aici, pentru că, un fel de, trebuie să amintiți-vă unde vă aflați în poveste, dar la sfârșitul zilei, dat orice număr de elemente, vrei mai întâi să sorta jumătate din stânga, apoi jumătatea din dreapta, apoi merge le împreună. Să începem să facă exact acest lucru. Aici e intrarea opt elemente. Acum ne uităm la jumătatea stângă aici. Cum pot sorta patru elemente? Ei bine, am sorta prima jumătatea stângă. Acum, cum pot sorta jumătatea stângă? Ei bine, eu am dat două elemente. Deci, haideți să sorteze aceste două elemente. 2 este mai mare decât sau egal cu 2, desigur. Așa că primul caz nu se aplică. 

Așa că am acum pentru a sorta stânga jumătate din aceste două elemente. Jumătatea stângă, desigur, este la doar 4. Deci, cum am sorta o listă de un element? Ei bine, acum, acest caz de bază special până sus, ca să spunem așa, se aplică. 1 este mai mică de 2, și mi Lista este într-adevăr de dimensiuni 1. Așa că mă întorc. Eu nu fac nimic. Și într-adevăr, uita-te la ceea ce am făcut, 4 este deja sortate. Ca eu sunt deja parțial de succes aici. 

Acum, care pare un fel de prost a pretinde, dar este adevărat. 4 este o listă de dimensiuni 1. E deja sortate. Asta e jumătatea stângă. Acum am sorta jumătatea din dreapta. Intrare mea este un element, 8 În mod similar, sortate deja. Prost, de asemenea, dar, din nou, acest principiu de bază este de gând să ne permite să construim acum pe partea de sus a acestui succes. 4 sortate, 8 este sortată, acum ceea ce a fost ultimul pas? Deci a treia și ultima etapă, orice timp ce te sortare o listă, rechemare, a fost de a fuziona cele două jumătăți, stânga și dreapta. Deci, haideți să facă exact acest lucru. Jumătate meu stâng este, desigur, 4. Jumătate meu drept este de 8. 

Deci, hai sa facem acest lucru. În primul rând am de gând să aloce unele memorie suplimentară, ca voi reprezenta aici, ca doar o gamă secundar, care este destul de mare pentru a se potrivi acest lucru. Dar vă puteți imagina de extindere că dreptunghi întreaga lungime, dacă avem nevoie de mai mult mai târziu. Cum fac 4 și 8, și îmbinarea cele două liste de mărime 1 împreună? Aici, de asemenea, destul de simplu. 4 este pe primul loc, apoi vine 8. Pentru că dacă vreau să sorta jumătate din stânga, apoi jumătatea din dreapta, și apoi merge cele două jumătăți împreună, în ordine sortate, 4 este pe primul loc, apoi vine 8. 

Deci, se pare că face progrese, chiar deși nu am făcut nici o lucrare actuale. Dar amintiți-vă unde suntem în poveste. Am luat inițial opt elemente. Am sortat jumătatea stângă, care este de 4. Apoi ne-am sortat jumătatea stângă din jumătatea stângă, care era 2. Și aici vom merge. Am terminat cu acest pas. 

Deci, dacă am sortează stânga jumătate de 2, acum ne-am au pentru a sorta jumătatea dreaptă a 2. Deci jumătatea dreaptă a 2 este aceste două valori de aici, 6 și 2. Așa că haideți să luăm acum o intrare de dimensiune 2, și sortați jumătatea stângă, și apoi jumătatea dreaptă, și apoi le merge împreună. Ei bine, cum a face I a sorta o listă de dimensiuni 1, care conține doar numărul 6? Am făcut deja. Este sortata Această listă de dimensiuni 1. 

Cum pot sorta o altă listă de Dimensiunea 1, așa-numitul jumătatea din dreapta. Ei bine,, de asemenea, este deja sortate. Numărul 2 este singur. Deci, acum am două jumătăți, la stânga și la Bine, am nevoie pentru a le îmbina împreună. Permiteți-mi să mă dau un spațiu suplimentar. Și a pus acolo 2, apoi 6 acolo, astfel sortare această listă, stânga și la dreapta, și fuzionează împreună, în cele din urmă. Așa că eu sunt într-o formă puțin mai bună. Nu am terminat, pentru că în mod clar 4, 8, 2, 6 nu este ordinea finală pe care vreau. Dar am acum două liste de dimensiuni 2, care ambele au, respectiv, a fost sortate. Deci, acum, dacă vă înapoi în mintea ta ochi, în cazul în care au ca ne lase? Am început cu opt elemente, apoi m-am diminuate în jos la jumătatea stângă a 4, apoi jumătatea stângă a 2, și apoi jumătatea dreaptă a 2, Am terminat, prin urmare, sortare stânga jumătate din 2, și jumătatea dreaptă a 2, Deci, ce este de-a treia și ultima etapă de aici? Trebuie să fuzioneze împreună două liste de dimensiuni 2. Așa că hai să mergem mai departe. Și pe ecran aici, da mi ceva memorie suplimentară, deși punct de vedere tehnic, observați că Am a primit o grămadă de spațiu până gol top Acolo. Dacă vreau să fie deosebit de spațiu eficient înțelept, Am putea începe doar în mișcare elementele înainte și înapoi, sus și de jos. Dar doar pentru claritate vizuală, Am de gând să-l pună jos, pentru a menține lucrurile frumos si curat. 

Așa că am două liste de dimensiuni 2. Prima listă are 4 și 8. A doua listă are 2 și 6. Să fuziona cele împreună pentru sortat. 2, desigur, este pe primul loc, apoi 4, apoi 6, apoi 8. Și acum se pare a fi mai undeva interesant. Jumătate acum am extrase din lista, și coincidență, e toate numerele pare, dar asta este, într-adevăr, doar o coincidență. Și eu acum am sortat stânga jumătate, astfel încât este 2, 4, 6, 8 și. Nimic nu e în ordine. Care se simte ca un progres. 

Acum se simte ca am vorbit pentru totdeauna acum, astfel încât ceea ce rămâne de văzut dacă această Algoritmul este, într-adevăr, mult mai eficient. Dar vom prin o super-metodic. Un computer, desigur, ar face așa. Deci, unde suntem? Am început cu opt elemente. Am sortat jumătatea stângă a 4. Am par a fi terminat cu asta. Deci, acum următorul pas este de a sorta jumătatea dreaptă a 4. Și această parte putem merge printr-un pic mai mult repede, deși ești Bine ați venit pentru a derula sau a întrerupe, doar cred prin ea la propriul ritm, dar ceea ce avem acum este o oportunitate de a face același algoritm exact pe patru numere diferite. 

Deci, să mergem mai departe, și să se concentreze asupra jumătatea dreaptă, care suntem aici. Jumătatea stângă a care jumătate dreapta, iar acum jumătatea stângă a stânga jumătate din care jumătate drept, și cum pot sorta o listă de dimensiuni 1 conține doar numărul 1? E deja făcut. Cum pot face același lucru pentru o listă de dimensiuni 1 conține doar 7? E deja făcut. Pasul trei pentru această jumătate, apoi este să fuzioneze aceste două elemente într-o nouă listă de dimensiuni 2, 1 și 7. Nu par să fi făcut toate că de mult de lucru interesant. Să vedem ce se întâmplă în continuare. Am sortat doar jumătatea stângă a jumătatea dreaptă a de intrare meu original. Acum, haideți să sorteze dreapta jumătate, care conține 5 și 3. Să ne uităm la nou stânga jumătate, sortate, pe jumătate dreptate, sortate, și îmbinarea celor două împreună, în unele spațiu suplimentar, 3 este pe primul loc, apoi vine 5. Și așa acum, ne-am sortează jumătatea stângă a jumătatea din dreapta problemei originale, și jumătatea dreaptă a jumătatea din dreapta a problemei inițiale. Care este a treia și ultima pas? Ei bine, să fuzioneze cele două jumătăți împreună. Deci lasă-mă să-mi iau niște spațiu suplimentar, dar, din nou, am ar putea fi, folosind ca spatiul liber până sus. Dar vom continua să simplu vizual. Lasă-mă să fuzioneze acum 1, și apoi 3, apoi 5, apoi 7. Mă lăsând acum cu jumătate din dreapta a problemei originale care este perfect sortate. 

Deci, ceea ce rămâne? Mă simt ca și cum aș ține spunând aceleași lucruri din nou, și din nou, dar asta e de reflexie a fapt pe care îl utilizăm recursivitate. Procesul de a folosi un algoritm nou, și din nou, pe subseturi mai mici de problema originală. Așa că acum am un stânga sortate jumătate din problema originală. Am o jumătate de sortat drept a problemei inițiale. Care este a treia și ultima etapă? Oh, e absorbit. Așa că hai să facem asta. Să aloce unele suplimentare memorie, dar Dumnezeul meu, ne-am ar putea pune-l oriunde acum. Avem atât de mult spațiu disponibil pentru noi, dar vom păstrați-l simplu. În loc de a merge înapoi și mai departe cu memoria noastră originală, hai sa o facem vizual aici de mai jos, pentru a termina fuzionarea jumătate stânga și jumătatea din dreapta. 

Deci, prin fuziunea, ce trebuie să fac? Vreau sa iau elementele în ordine. Deci uita la jumătatea stângă, Văd primul număr este 2. Mă uit la jumătatea din dreapta, Văd primul număr este 1, deci evident care Numărul vreau să smulge, și a pus pe primul loc în lista mea finală? Desigur, 1. Acum vreau să întreb aceeași întrebare. Pe jumătatea stângă, am Încă mai am numărul 2. Pe jumătatea din dreapta, Am numărul 3. Care unul vreau să aleg? Desigur, numărul 2 și acum observa candidații sunt 4 pe stânga, 3 pe dreapta. Să, desigur, alege 3. Acum candidații sunt 4 pe stânga, 5 la dreapta. Noi, desigur, pentru a alege 4. 6 din stânga, 5 la dreapta. Noi, desigur, alege 5. 6 din stânga, 7 pe dreapta. Am ales 6, și apoi ne alege 7, iar apoi alegem 8. Voila. 

Deci, un număr foarte mare de cuvinte mai târziu, am au sortat această listă de opt elemente într-o listă de una prin opt, care este în creștere cu fiecare pas, dar cât de mult timp a făcut ne lua pentru a face asta. Ei bine, în mod deliberat Am lucrurile prevăzute pictural aici, astfel încât să putem fel de vezi sau apreciati divizia în cucerire că sa întâmplat. 

Într-adevăr, dacă te uiți înapoi la urma, Am lăsat toate aceste linii punctate în titularilor loc, puteți, un fel de, a se vedea, în ordine inversă, dacă un fel de privi înapoi în istorie acum, lista mea inițială este, desigur, de dimensiunea 8. Și apoi Anterior, am fost a face cu doua liste de mărime 4, și apoi patru liste de dimensiuni 2, și apoi opt liste de dimensiune 1. 

Deci, ce face acest lucru, un fel de, vă reamintesc de? Ei bine, într-adevăr, oricare dintre algoritmii care le-am sa uitat la până în prezent în cazul în care ne-am divide, și divide, și divide, păstra cu lucrurile din nou, și din nou, ca rezultat această idee generală. Și deci nu e ceva logaritmică se întâmplă aici. Și nu e destul de jurnal de n, dar există o componentă logaritmică a ceea ce tocmai am făcut. 

Acum, haideți să ia în considerare modul, care de fapt este. Deci, jurnal de n, din nou a fost un timp de funcționare mare, când am făcut ceva de genul căutare binară, așa cum am acum o numim, strategia divide și cuceri prin care am găsit Mike Smith. Punct de vedere tehnic acum. Asta e jurnal de bază 2 de n, chiar deși în cele mai multe clase de matematica, 10 este, de obicei de bază pe care le presupune. Dar oamenii de stiinta de calculator aproape întotdeauna gândesc și vorbesc în termeni de bază 2, astfel, în general, spunem doar jurnal de n, în loc de log in baza 2 a n, dar sunt exact unul și aceeași în lumea de calculator știință, și, ca o paranteză, există un factor constant diferență între cele două, așa că pune în dezbatere oricum, din motive mai mult formale. 

Dar pentru acum, ceea ce ne pasă despre este acest exemplu. Așa că haideți să nu se dovedesc de exemplu, dar la puțin utiliza un exemplu de numere la îndemână ca o verificare bun-simț, dacă vreți. Deci anterior formula a fost de bază log 2 de n, dar ceea ce este n în acest caz. Am avut numerele n originale, sau 8 de numărul inițial specific. Acum că a fost un pic în timp ce, dar eu sunt destul de sigur că log bază 2 din valoarea 8 este 3, și într-adevăr, ceea ce este frumos despre care este că 3 este exact numărul de ori pe care le puteți împărți o listă de nou, și din nou lungime 8, și din nou, până când rămâi cu liste de mărime doar 1. Dreapta? 8 merge la 4, se duce la 2, merge la 1, și asta e reflecta exact acest lucru imagine am avut în urmă cu doar un moment. Deci, un pic de bun-simț verifica de unde logaritm este, de fapt implicat. 

Deci, acum, ce altceva este vorba aici? n. Deci observăm că fiecare timp am împărțit lista, chiar dacă în ordine inversă în istorie aici, am fost mai faci n lucruri. Acest pas fuzionează necesar ca Ating fiecare dintre numerele, în scopul de a glisați-l în locația sa corespunzătoare. Deci, chiar dacă înălțimea acestei Diagrama este de mărime log n n sau 3, în mod specific, cu alte cuvinte, Am făcut trei divizii aici. Cât de mult de lucru am făcut orizontal de-a lungul această diagramă de fiecare dată? 

Ei bine, am făcut-o n trepte de locul de muncă, pentru că dacă am Trebuie patru elemente și patru elemente, și am nevoie pentru a le îmbina împreună. Am nevoie pentru a merge prin aceste patru și aceste patru, în cele din urmă pentru a le îmbina înapoi în opt elemente. Dacă dimpotrivă Am opt degete aici, ceea ce nu face, și opt fingers-- sorry-- Dacă am Trebuie patru degete aici, care fac, de patru degete aici, pe care o fac, atunci asta e la fel exemplu ca și mai înainte, în cazul în care fac au opt degete deși, în totală, pe care eu pot fel de, nu,. Eu pot face exact aici, Atunci pot siguranță fuzioneze toate aceste liste de dimensiune 1 împreună. Dar am avea cu siguranță să te uiți la fiecare element de exact o dată. Deci înălțimea acestui proces este log n, lățimea acestui proces, ca să spunem așa, este N, asa ca ceea ce am par de a avea, în cele din urmă, este un timp de funcționare de mărime n ori log n. 

Cu alte cuvinte, ne-am impartit lista, jurnalul de n ori, dar de fiecare dată am făcut asta, am avut pentru a atinge fiecare dintre elementele în scopul de a le îmbina toate împreună, care a fost n pas, așa că avem de n ori log n, sau ca un om de stiinta de calculator ar spune, asimptotic, care ar fi cuvântul mare pentru a descrie partea superioară legat la un timp de funcționare, ne se execută într-o o mare log n timp, ca să spunem așa. 

Acum, acest lucru este important, deoarece amintesc care au fost ori de funcționare cu bule de sortare, și de selecție sortare, și sortare prin inserție, și chiar un alte câteva care există, n pătrat a fost în cazul în care am fost la. Și puteți, un fel de, a se vedea acest lucru aici. Dacă n pătrat este, evident, de n ori n, dar aici avem de n ori log n, si stim deja de la săptămână la zero, că log n, logaritmică, este mai bine decât ceva liniar. La urma urmei, amintesc imaginea cu roșu și galben și liniile verzi pe care le scoteau, line logaritmică verde a fost mult mai mic. Și, prin urmare, mult mai bine și mai repede decât drepte linii galbene și roșii, de n ori log n este, într-adevăr, mai bine decât de n ori n, sau n pătrat. 

Deci, se pare că avem a identificat o îmbinare algoritm fel care se execută în mare timp mai rapid, și într-adevăr, de aceea, la începutul acestei săptămâni, atunci când am văzut că concurs între bule sortare, selectare fel, și îmbinarea sort, merge sort foarte, foarte castigat. Și într-adevăr, ne-am nici măcar nu așteptați pentru bule de sortare și selecție de sortare a termina. 

Acum să luăm un alt trecere la această, la o puțin mai perspectivă formală, doar în caz, acest rezonează mai bine decât că discuția nivel mai ridicat. Deci, aici e din nou algoritmul. Să ne întrebăm, ce timpul de rulare este de acest algoritmi diferite etape? Să-l împartă în primul caz și al doilea caz. IF și altcineva în cazul dacă, Dacă N este mai mică de 2, doar reveni. Se simte ca constantă de timp. E, un fel de, cum ar fi două etape, IF n este mai mic de 2, apoi să se întoarcă. Dar, așa cum am spus, luni, constantă de timp, sau de mare o de 1, pot fi două etape, trei pași, chiar 1.000 de trepte. Ceea ce contează este faptul că este un număr constant de pași. Deci galben evidențiat pseudocod aici se execută în, vom numi, constantă de timp. Deci mai formal, și vom sa-- acest va fi măsura în care ne formaliza acest drept now-- T de n, timpul de rulare a unei probleme care ia n ceva de ca intrare, este egal cu mare o de unul, IF n este mai mică de 2. Deci, este condiționată de asta. Deci, pentru a fi clar, dacă N este mai mică de 2, avem o listă foarte scurtă, apoi timpul de rulare, T de n, unde n este 1 sau 0, în acest caz foarte specific, este doar de gând să fie constantă de timp. Se va lua o pas, doi pași, indiferent. Este un număr fix de pași. 

Deci partea suculent trebuie să fie cu siguranță în alt caz în pseudocod. Cazul altceva. Un fel de jumătate din stânga de elemente, un fel dreptul jumătate din elemente, îmbinare jumătăți sortate. Cât timp durează fiecare dintre aceste etape să ia? Ei bine, în cazul în care derularea timp pentru a sorta n elemente este, să-i zicem foarte generic, T de n, apoi de sortare stânga jumătate din elementele este, un fel de, cum ar fi zis: T de n împărțit la 2, și sortarea în mod similar jumătatea din dreapta de elemente este, un fel de, cum ar fi zis: T de n divizat 2, și apoi fuzionarea jumatati sortate. Ei bine, dacă am niște Numărul de elemente aici, cum ar fi patru, iar unele numărul de elemente aici, cum ar fi patru, și am să fuzioneze fiecare dintre aceste patru în, și fiecare dintre aceste patru în, unul după altul, astfel încât în cele din urmă am opt elemente. Se simte ca e mare o de n pași? Dacă am n degete și fiecare dintre ei are să fie integrate în loc, asta e ca un alt n pași. 

Deci, într-adevăr formulaically, putem exprima acest lucru, deși un pic scarily la prima vedere, dar este ceva care surprinde exact această logică. Timpul de funcționare, T de n, n IF este mai mare sau egal cu 2. În acest caz, cazul altceva, este T de n împărțit la 2, plus T de n împărțit la 2, mare plus o de n, unele Numărul liniar de etape, , poate exact n, poate de 2 ori n, dar e aproximativ, ordinea n. Așa că, de asemenea, este modul în care putem exprima acest formulaically. Acum, tu nu ar ști acest lucru, cu excepția cazului l-ai înregistrat în mintea ta, sau căutați-l în sus în din spate a unui manual, care ar putea avea un pic de trișeze foaie la sfârșitul anului, dar acest lucru este, într-adevăr, o să să ne dea o mare o de n log n, deoarece recurența care vedeți aici, pe ecran, dacă tu de fapt făcut-o, cu un număr infinit de exemple, sau ai făcut formulaically, ar trebui să vedea că acest lucru, pentru că această formulă în sine este recursiv, cu t n peste ceva pe dreapta, și T de n pe stânga, acest lucru poate de fapt este exprimată, în cele din urmă, la fel de mare du-te de n log n. Dacă nu convins, asta e amendă pentru acum, doar ia pe credință, că e, într-adevăr, ce care duce la reapariția, dar acest lucru este doar un pic mai mult de un Abordarea matematică să caute la momentul de funcționare a merge fel pe baza pseudocod sa numai. 

Acum, haideți să ia un pic de un aerisire din toate astea, și să ia o privire la o anumite fostul senator, care a s-ar putea uita-te un pic familiar, care se așeză cu Eric Google Schmidt, ceva timp în urmă, pentru un interviu pe scena, in fata o grămadă de oameni, vorbind în cele din urmă despre un subiect, care e destul de acum familiar. Hai să aruncăm o privire. 

Eric Schmidt,: Acum Senator, esti aici, la Google, și îmi place să cred că a președinție ca un interviu de angajare. Acum e greu pentru a obține un loc de muncă în calitate de președinte. Președintele Obama: dreapta. Eric Schmidt, Și tu ești de gând să faci [neauzit] acum. Este, de asemenea, greu pentru a obține un loc de muncă la Google. Președintele Obama: dreapta. 

Eric Schmidt,: Avem întrebări, si cerem candidaților întrebările noastre, iar acesta este de la Larry Schwimmer. 

Președintele Obama: OK. 

Eric Schmidt,: Ce? Credeți că glumesc? E chiar aici. Care este cel mai eficient mod de a sorta un milion de 32 de biți numere întregi? 

Președintele Obama: Well-- Eric Schmidt,: Uneori, Poate Îmi pare rău, maybe-- Președintele Obama: Nu, nu, Nu, nu, nu, eu think-- Eric Schmidt,: Asta nu e it-- Președintele Obama: I cred, cred că bula fel ar fi calea greșită de a merge. Eric Schmidt,: Haide. Cine-i asta a spus? BINE. Nu am stiinta de calculator on-- 

Președintele Obama: Avem Trebuie spioni noastre acolo. PROFESORUL: Bine. Să lăsăm în urma noastră acum din lume teoretică a algoritmilor în analiza asimptotică acestora, și să se întoarcă la unele subiecte de la zero și săptămână, și start pentru a elimina niște roți de formare, dacă vrei. Astfel încât să înțeleg cu adevărat în cele din urmă de la sol în sus, ceea ce este întâmplă sub capotă, atunci când scrie, compila, și să execute programe. Reamintim, în special, că aceasta a fost primul program C ne-am uitat la, un program de canonic, simplu de soiuri, relativ vorbind, care, se imprimă, Hello World. Și reamintească faptul că i-am spus, procesul de codul sursă trece prin este exact acest lucru. Iei codul sursă, trece printr-un compilator, cum ar fi zăngănit, și în afara vine cod obiect, care s-ar putea arata ca acest lucru, zerouri și cele că CPU computerului, Central unitate de procesare sau a creierului, în cele din urmă înțelege. 

Se pare că asta-i o bit de o simplificare, că suntem acum într-o Poziția sa tachineze in afara pentru a intelege ce a fost foarte întâmplă sub capota de fiecare dată când a alerga Zăngăni, sau mai general, de fiecare dată când face un program, folosind Marca și CF 50 IDE. În special, chestii de genul acest lucru este primul generat, atunci când compilați programul prima. Cu alte cuvinte, atunci când ia codul sursă și compila, ceea ce este în primul rând fiind scoase de zăngănit este ceva cunoscut sub numele de cod de asamblare. Și, de fapt, se pare ca acest lucru exact. 

Am fugit o comandă la linie de comandă mai devreme. Hello.c capitalul bord zăngănit s, și acest lucru a creat un fișier pentru ma sunat hello.s, interiorul din care au fost exact aceste conținuturi, și un pic mai mult deasupra și un pic mai jos, dar am pus juiciest informații aici pe ecran. Și dacă te uiți atent, veți vedea cel puțin câteva cuvinte cheie familiar. Avem principal în partea de sus. Am printf în mijloc. Si ne-am, de asemenea, salut lume backslash n ghilimele jos. 

Și orice altceva aici este instrucțiuni foarte slabe că CPU computerului intelege. Instrucțiuni CPU care se mișcă de memorie în jurul valorii de, că siruri de caractere de încărcare din memorie, și în cele din urmă, de imprimare lucruri pe ecran. Acum, ce se întâmplă, deși după este generat acest cod de asamblare? În cele din urmă, ai face, într-adevăr, încă genera cod obiect. Dar pașii care au într-adevăr fost întâmplă sub capota uite un pic mai mult ca aceasta. Codul sursă devine codul de asamblare, care apoi devine cod obiect, iar cuvintele operative aici sunt ca, atunci când compilați codul sursă, out vine codul de asamblare, și apoi atunci când asambla codul de asamblare, out vine cod obiect. 

Acum zăngănit este super sofisticat, ca o mulțime de compilatoare, și-l face toate aceste etape împreună, și aceasta nu neapărat ieșire orice intermediar Fișierele pe care le puteți vedea chiar. Doar compilează lucruri, care este termenul general care descrie acest proces. Dar daca vrei cu adevarat pentru a fi special, nu e mult mai mult întâmplă acolo, de asemenea. 

Dar să considerăm, de asemenea, că, chiar acum acest program super-simplu, hello.c, numit o funcție. Acesta a invitat printf. Dar nu am scrie printf, într-adevăr, care vine cu C, ca să spunem așa. Este o rechemare funcție care este a declarat în io.h standard care este un fișier antet, care este un subiect vom fapt se arunca cu capul în mai multă profunzime, înainte de mult timp. Dar un fișier header este de obicei însoțite printr-un fișier de cod, sursă fișier de cod, astfel încât la fel ca exista io.h. standard de 

Candva acum, cineva, sau cuiva, de asemenea, a scris un fișier numit io.c standard în care definițiile reale, sau implementari de printf, și ciorchini de alte funcții, sunt de fapt scrise. Deci având în vedere că, dacă luăm în considerare având aici, pe stânga, hello.c, că, atunci când compilat, ne dă hello.s, chiar dacă Zăngăni nu deranjează economisire într-un loc putem vedea, și că codul de asamblare devine asamblate în hello.o, care este, într-adevăr, numele implicit având în vedere ori de câte ori compila sursa cod în cod obiect, dar nu sunt destul de gata să-l execute încă, deoarece un alt pas trebuie să se întâmple, și are se întâmplă pentru ultimele săptămâni, probabil fără știrea pentru tine. 

Mai exact undeva în CS50 IDE, și acest lucru, de asemenea, va fi un pic de o simplificare pentru un moment, există, sau a fost la un moment dat, un fișier numit io.c standard că cineva compilat în io.s standard sau echivalentul, că cineva apoi asamblate în io.o standard sau se dovedește într-un ușor diferite fișier format care poate avea un alt fișier prelungire cu totul, dar în teorie și conceptual, exact aceste măsuri trebuia să se întâmple într-o formă. Care este de a spune, că acum când am scris un program, hello.c, ca doar spune, Hello lume, și eu sunt, folosind codul de altcuiva ca printf, care a fost o dată la un timp, într-un fișier numit io.c standard apoi într-un fel am să-mi iau cod obiect, zerouri și cele mei, și obiect care persoane cod, sau zerouri și cele, și într-un fel le lega împreună într- un fișier final numit salut, că are toate zerourile și cei de la funcția mea principală, și toate zerourile iar cele pentru printf. 

Și într-adevăr, că ultimul proces este numit, care leagă codul obiect. Din care producția este un fișier executabil. Deci, în echitate, la sfârșitul zilei, nimic sa schimbat din saptamana, cand am Primul a început compilarea programelor. Într-adevăr, toate acestea au fost întâmplă sub capota, dar acum suntem într-o poziție în cazul în care putem de fapt tachineze pe langa aceste diferite etape. Și într-adevăr, la sfârșitul a zilei, suntem încă a plecat cu zero și cele care, este de fapt o mare Segue acum într-un alt capacitatea de C, care noi nu am avut să impulsioneze, cel mai probabil până în prezent, cunoscut sub numele de operatori la nivel de bit. Cu alte cuvinte, până acum, oricând ne-am tratate cu date în C sau variabile în C, am avut lucruri de genul caractere, pluteste si ins și tânjește și duble și altele asemenea, dar toate acelea sunt cel puțin opt biți. Noi nu am fost încă în măsură să manipula biți individuale, chiar dacă un pic individ, am știu, poate reprezenta un 0 și 1. Acum se pare că, în C, vă pot avea acces la biți individuali, daca stii sintaxa, cu care pentru a ajunge la ei. 

Deci, haideți să aruncăm o privire operatorilor la nivel de bit. Deci, imagine aici sunt câteva simboluri care am, un fel de, un fel de, văzut înainte. Văd un ampersand, un vertical bar, și altele, precum și, și reamintească faptul că ampersand ampersand este ceva ce am văzut până acum. Operatorul logic, în cazul în care aveți doi dintre ei împreună, sau logică sau Operatorul, în cazul în care au două bare verticale. Operatorii la nivel de bit, pe care le vom vezi operează pe biți individual, folosi doar un singur ampersand, un bar vertical unic, simbolul caret urmeaza, puținul tilda, și apoi a plecat suport stânga suport, sau Suport drept suport dreapta. Fiecare dintre acestea au sensuri diferite. 

De fapt, hai să aruncăm o privire. Să mergem vechea școală astăzi, și utilizarea un ecran tactil de odinioară, cunoscut ca o tablă albă. Și această tablă este de gând să ne permită să-și exprime unele simboluri destul de simplu, sau mai degrabă niște formule destul de simpli, că putem, atunci în cele din urmă efectul de levier, în scopul de pentru a accesa individuale biți în cadrul unui program C. Cu alte cuvinte, să facem acest lucru. Să vorbim mai întâi pentru o clipă despre ampersand, care este la nivel de bit operatorul AND. Cu alte cuvinte, aceasta este un operator care permite să am o variabilă stânga de obicei, și o variabilă dreapta, sau o valoare individuală, că, dacă noi și le împreună, îmi dă un rezultat final. Deci, ce vreau sa spun? Dacă într-un program, aveți o variabilă care stochează unul dintre aceste valori, sau să-l păstrați simplu, și doar scrie zerouri și cele individuale, Iată cum funcționează operatorul ampersand. 0 0 ampersand va egala cu 0. Acum, de ce este asta? 

Este foarte asemănător cu Expresii booleene, pe care le-am discutat până acum. Dacă credeți că la urma urmei, este de 0 false, 0 este falsă, fals și fals este, așa cum am discutat în mod logic, de asemenea fals. Deci, vom ajunge la 0 aici, de asemenea. Dacă luați 0 ampersand 1, bine că, de asemenea, va fi 0, pentru că în acest expresie stanga, pentru a fi adevărat sau 1, acesta ar trebui să fie adevărat și adevărat. Dar aici avem false și adevărat, sau 0 și 1. Acum, din nou, în cazul în care avem un ampersand 0, care, de asemenea, va fi 0, iar dacă avem un ampersand 1, În cele din urmă avem un pic de 1. Deci, cu alte cuvinte, nu facem ceva interesant cu acest operator încă, acest operator ampersand. Este la nivel de bit AND operatorul. Dar acestea sunt ingredientele prin care putem face lucruri interesante, cum vom vedea în curând. 

Acum să ne uităm la doar single- bară verticală pe aici, pe dreapta. Dacă am un pic si am 0 Sau cu, la nivel de bit Sau a operatorului, un alt 0 pic, care va să-mi dea 0. Dacă am lua un pic 0 și sau cu un pic 1, apoi am de gând pentru a obține 1. Și, de fapt, doar pentru claritate, lasă-mă să mă întorc, astfel încât barele verticale mele nu sunt confundat cu un lui. Permiteți-mi să rescrie toate mea 1 este un pic mai mult în mod clar, astfel încât să putem vedea în continuare, dacă am au un 1 sau 0, care va fi un 1, și dacă am un 1 sau 1, care, de asemenea, va fi un 1. Deci, puteți vedea în mod logic că RUP Operatorul se comporta foarte diferit. Acest lucru îmi dă 0 sau 0 îmi dă 0, dar orice altă combinație dă-mi o. Atâta timp cât am o 1 în formula, rezultatul va fi o. 

Prin contrast cu AND Operatorul, ampersand, numai dacă am două 1 în ecuație, primesc de fapt, un 1. Acum există o altă câteva operatorii de asemenea. Una dintre ele este un pic mai implicat. Așa că lasă-mă să merg mai departe și șterge acest lucru pentru a elibera spațiu. Și haideți să aruncăm o privire la simbol caret, pentru o clipă. Aceasta este de obicei o Caracterul aveți posibilitatea să tastați pe dumneavoastră exploatație tastatură Shift și atunci unul dintre numerele de varful US ta tastatură. 

Deci, acesta este exclusiv Sau a operatorului, SAU exclusiv. Deci, am văzut doar operator sau. Aceasta este exclusiv sau operatorul. Care este de fapt diferența? Ei bine, hai să uităm la formula, și de a folosi acest lucru ca ingrediente în cele din urmă. 0 XOR 0. Am de gând să spun este întotdeauna 0. Asta e definiția XOR. 0 XOR 1 va fi de 1. 1 XOR 0 va fi 1, și 1 XOR 1 va fi? Greșit? Sau nu? Eu nu stiu. 0. Acum, ce se întâmplă aici? Ei bine, Gândiți-vă la Numele acestui operator. SAU exclusiv, în așa fel încât numele, un fel de, sugerează, raspunsul este doar de gând să fie 1 în cazul în care intrările sunt exclusive, exclusiv diferit. Deci, aici intrările sunt același, astfel încât rezultatul este 0. Aici intrările sunt același, astfel încât rezultatul este 0. Aici sunt rezultatele sunt diferite, ele sunt exclusive, și astfel ieșirea este 1. Deci, este foarte similar cu Și, este foarte asemănătoare, sau mai degrabă este foarte similar cu SAU, dar numai într-un mod exclusiv. Acesta nu mai este un 1, pentru că avem două 1 lui, și nu exclusiv, doar una dintre ele. In regula. Ce zici de ceilalți? Ei bine tilda, între timp, este de fapt, frumos și simplu, din fericire. Și aceasta este o unar Operatorul, ceea ce înseamnă este aplicat la o singură intrare, un operand, ca să spunem așa. Nu la un stânga și un drept. Cu alte cuvinte, dacă luați tilda de 0, răspunsul va fi opusul. Și dacă luați tilda de 1, The răspuns nu va fi opusul. Deci operatorul tilda este un mod de negarea un pic, sau flipping un pic de 0 la 1, sau 1 până la 0 ° C. 

Și asta ne lasă în cele din urmă cu doar doi operatori finale, așa-numita schimbare stânga, și așa-numita operator de schimbare dreapta. Să aruncăm o privire la modul în care aceste locul de muncă. Operatorul de schimbare stânga, scris cu două paranteze unghiulare, cum ar fi faptul că, funcționează după cum urmează. Daca intrarea mea, sau operand mea, la stânga Operatorul schimbare este pur și simplu un 1. Și am apoi spune computerul pentru a schimbare lăsat 1, spun șapte locuri, rezultatul este ca și cum am iei 1, și mutați-l șapte locuri pe la stânga, și în mod implicit, vom presupune că spațiul din dreapta va fi căptușit cu zerouri. Cu alte cuvinte, o schimbare a plecat 7 se va să-mi dea că 1, urmat de 1, 2, 3, 4, 5, 6, 7 zerouri. Deci, într-un fel, aceasta vă permite să ia un număr mic ca 1, și în mod clar face mult mult, mult mai mare în acest fel, dar ne vom vedea de fapt abordări mai inteligent pentru el în schimb, precum și, 

In regula. Asta e săptămâna trei. Vă vom vedea data viitoare. Acest lucru a fost CS50. 

[MUSIC JOC] 

SPEAKER 1: A fost la snack- bar manca o inghetata Fudge fierbinte. El a avut toate peste față. Poartă că ciocolata ca o barbă SPEAKER 2: Ce faci? SPEAKER 3: Hmmm? Ce? 

SPEAKER 2: Ai doar dublu baie? Tu de întâlnire dublă chip. SPEAKER 3: Scuzați-mă. SPEAKER 2: Ai întâlnire cip, aveți a luat o muscatura, si te întâlnire din nou. SPEAKER 3: SPEAKER 2: Deci asta e ca punerea întreaga dreptul de gura in dip. Data viitoare să luați un cip, doar o dată dip, și se încheie o. 

SPEAKER 3: Știi ce, Dan? Tu dip modul în care doriți să se scufunde. Voi dip modul în care vreau să se scufunde.