[Redarea muzicii] 

David J. MALAN: În regulă. Deci, bun venit înapoi. Aceasta este CS50, și este la sfârșitul săptămânii trei. 

Deci, amintesc în ultimele câteva săptămâni, Am petrecut destul de un pic de timp pe C, pe programare, pe sintaxa. Și e destul de normal, dacă sunteți încă lupta cu Set Problema 2, pentru a fi loveste cu capul de perete. Este mesaje de eroare criptic cu aspect și bug-uri pe care le nu pot urmări destul de jos. Pentru că, fiți siguri, că în doar o timp câteva săptămâni veți privi înapoi pe lucruri cum ar fi Cezar, și [? V-genair,?] poate chiar Crack, și seama cât de departe ai ajuns într-o perioadă scurtă de timp. Deci, dacă e vreo consolare, atârna acolo pentru acum. 

Astăzi, însă, vom începe să tranziție la lucrurile nivel superior. Și vom începe să ia acordat pentru că voi ști cum să program, sau la puțin la începuturile că nivelul de confort. Și vom începe să ia în considerare modul în care putem du-te cu privire la elaborarea de programe mai în mod eficient. Cum putem merge cu privire la optimizarea eficiența algoritmilor noastre, și în general, rezolvarea mai mult probleme interesante. Și începe să ia acordat pentru că, dacă am vrea, am putea cod la orice dintre exemplele pe care le avem în minte. Așa că astăzi, nu atingeți tastatura pentru orice formă de cod. Va fi nivel mult mai mare, și în cele din urmă, cu privire la rezolvarea problemelor. 

Deci, pentru a ajunge la acest punct, permiteți-mi să propună că următoarele șapte dreptunghiuri reprezintă șapte uși, în spatele care sunt o grămadă de numere, printre care este numărul 50. Lasă-mă să proiecteze acest lucru pe această Ecranul aici, de asemenea. Și propune ca avem nevoie de un voluntar pentru a ajuta-mi găsesc un număr în fața Internet aici pentru a vedea. Hai sus, în roz. Bine. Care e numele tău? 

JENNIFER: [inaudibil] 

David J. MALAN: Îmi pare rău? 

JENNIFER: Jennifer. 

David J. MALAN: Jennifer. Bine, Jennifer. Îmi pare bine. Hai sus. Deci, acestea aici sunt șapte uși, și ce Aș vrea să faci pentru noi aici, în fața tuturor colegilor dumneavoastră, ne găsim numărul, 50. Pentru a găsi un număr, puteți arunca o privire în urmă oricare dintre aceste uși prin simpla atingere pe una dintre uși, și ea va dezvălui numărul său. Și să vedem cât de repede te ne pot găsi numărul, 50. 

15. 16. 50. Bine făcut. Bine. Rundă de aplauze pentru Jennifer. 

[Aplauze] 

Bine. Deci, ce a fost strategia pentru Identificarea numărului, 50? 

JENNIFER: Um, am crezut că poate dacă - [Inaudibil] 

David J. MALAN: Oh. Dă-mi o secundă. Deci, a fost strategia dvs. pentru Identificarea numărului, 50? 

Jennifer: Deci, am începe de la începutul pentru a vedea ce primul număr a fost, și apoi m-am gândit, poate, în cazul în care acestea sunt clasificate în funcție, voi păstra doar atingând mai sus? 

David J. MALAN: OK. Și se pare că am găsit care să fie cazul. Deși, să coaja înapoi straturile doar un pic, și tu vrei să mergi înainte și dezvăluie celelalte uși ai fi putut ales? 

JENNIFER: Oh, dragă. 

David J. MALAN: Ah. 

Jennifer: Deci, am avut noroc. 

David J. MALAN: Deci, ai avut noroc. Bine. Deci, nu rău. Dar asta e un interesant înțelegere, nu? Dacă ați asumat, și nu ai luat, într-adevăr, un pic norocos acolo. Dar, dacă presupune că numerele au fost sortate, puteți fi mai precise privire la modul în care a influențat comportamentul tău? 

Jennifer: Deci, dacă ei au fost sortate, I gândit mai mic poate la cel mai mare. 

David J. MALAN: OK. 

JENNIFER: Sau, în cazul în care acest lucru sa dovedit a fi într-adevăr mare, apoi cel mai mare la cel mai mic. 

David J. MALAN: OK. Deci, cel mai mare la cel mai mic, sau cel mai mic la cel mai mare. Dar permiteți-mi propun, să presupunem că a avut ajuns ghinion, și să presupunem că ei nu au fost, de fapt, sortate, câți dintre aceste uși ar putea fi trebuit să intrați în spatele în care cel mai rău caz? 

JENNIFER: Toate acestea. 

David J. MALAN: Toți. Deci, haideți să generalizeze ca, n. Nu se întâmplă să fie 7, dar hai să mai în general spune ca exista n uși pe Ecranul aici. Deci, în cel mai rău caz, ar trebui să se uite în spatele ușilor 7, sau n uși. Și astfel aceasta este într-adevăr, e un pic de noroc azi, dar este într-adevăr un liniar Algoritmul de soiuri, chiar dacă au fost un fel de sărind peste jurul. Este corect? 

JENNIFER: Da. 

David J. MALAN: Ei bine, lasă-mă să văd dacă dumneavoastră strategia modificări dacă ne miscam al doilea exemplu aici cu 7 uși diferite. Aceleași numere, dar acest lucru timp, ele sunt sortate. Care este strategia ta aici va fi, încercarea de a pune din mintea ta ceea ce celelalte numere erau - 

JENNIFER: OK. 

David J. MALAN: - mai devreme? 

JENNIFER: Să începem cu prima. 

David J. MALAN: În regulă. Începe cu primul. 4. Acum, în cazul în care ai de gând să mergi, și de ce? 

JENNIFER: 4 este foarte mic. Deci, dacă acestea sunt un fel mai mic poate la cel mai mare, ar trebui să fie de două ori că, și -. 

David J. MALAN: OK. Să vedem, ce crezi? 

JENNIFER: Încercați ultima. Frumos. 

David J. MALAN: Foarte bine făcut. Bine. 

[Aplauze] 

David J. MALAN: OK. Deci, ce faci de fapt asta oribil, pentru că ești face foarte bine. Ceea ce ne lasă în imposibilitatea de a face anumite puncte. Deci, haideți să încercăm să se rostogolească înapoi aici. 

JENNIFER: OK. 

David J. MALAN: Foarte bine face, cu toate acestea. Deci, ai început de la început, ai văzut că el a fost de 4, atunci te mutat la sfârșit. Dar să presupunem că nu avea noroc acolo, și să presupunem că 50 era în altă parte. Ce de-a treia etapă au fost? 

JENNIFER: Du-te înapoi la început. 

David J. MALAN: Du-te înapoi la început. OK, așa că s-ar fi atins această ușă, care a fost de 8. Bine. Așa că nu e 50. În cazul în care ați fi căutat viitoare? 

JENNIFER: Dacă nu am făcut Știu că sortate. 

David J. MALAN: Corect. Ei bine, dacă ai știut acestea au fost sortate - 

JENNIFER: Oh, nu știu, da. 

David J. MALAN: - dar nu unde 50 era încă? 

JENNIFER: Doar mergi mai departe. 

David J. MALAN: În regulă. OK. Continuă. OK, că eu pot lucra cu. 

JENNIFER: OK. 

David J. MALAN: Acum, daca esti doar continua să mergi, care e Algoritmul revin susținute în. 

JENNIFER: liniar -. 

David J. MALAN: Este un fel de liniar. Dar permiteți-mi propun, să ma pus pe loc. Permiteți-mi să încărcarea paginii. același număr, același aranjament, aceleași uși. Dar cred înapoi la acea prima zi în Clasa de când am rupt-o carte de telefon în jumătate, un fel de, și ceea ce a fost Strategia noastră acolo? 

JENNIFER: Start la mijloc. 

David J. MALAN: OK. Deci, începe de la mijloc. Deci, haideți să mergem mai departe și simula asta. Începe la mijlocul de dezvaluind faptul ca usa. Astfel, numărul 16. Deci, ceea ce ar fi tipul puternic au făcut, care a rupt cartea de telefon în jumătate, pentru a ajunge la ghici următorul? 

JENNIFER: Du-te în această jumătate. 

David J. MALAN: Și de ce să nu? 

JENNIFER: Dacă ar fi fost un fel de mic la cel mai mare, atunci 50 ar trebui să fie la acest scop. 

David J. MALAN: Bine. Total rezonabil. Deci, ca o carte de telefon, te duci la drept spre deosebire de stânga, dar aici este Takeaway cheie. Acum se poate arunca, sau rupe, jumătate din această problemă, nu pleci cu 7 usi, dar într-adevăr cu doar 3. Care este de aproximativ jumătate din dimensiunea problemei. Bine. Deci, acum ce ar trebui făcut după ce te duci dreptate? 

Jennifer: Deci, 16 este încă destul de mic, în raport cu 50, așa că poate voi încerca, ca, aceasta. 

David J. MALAN: În regulă. 42. Bine, deci acum care e instinctul îți spune? 

JENNIFER: Pot să arunc acest lucru și apoi pur și simplu - 

David J. MALAN: OK. Bun, puteți arunca jumătate din stânga acolo. 

JENNIFER: - alege asta. 

David J. MALAN: și dreptul. 

JENNIFER: Da. 

David J. MALAN: Deci, chiar daca e greu pentru a vedea, probabil, atunci când există doar 7 usi, gândiți-vă, acum, consistența algoritmul pe care tocmai ați aplicat. În cazul precedent, ai făcut noroc, care a fost mare. Dar ai folosit o euristică, Aș spune. Ai folosit un fel de instinctele tale, și știind că sortate, dacă e destul de mici la început, evident, ne-am Trebuie să mergem mai la dreapta. Dar într-un sens, ai avut noroc, pentru că poate acest lucru a fost numărul 100, și poate că 50 a fost mai mult la mijloc. Poate 50 a fost chiar aici. 

Dar ce-ai făcut un pic diferit de data aceasta a fost, ai făcut același lucru din nou și din nou. Și aș spune că ceea ce tocmai a, deși influențată de telefon exemplu carte, este ceva mult mai algoritmică, și mult mai puțin de construcții casetat. Mult mai puțin instinctiv. Deci, la sfârșitul zilei, cum ar fi ce descrie eficiența Primul algoritm, unde te-ai dus la stânga la dreapta, față de al doilea algoritm aici? 

JENNIFER: aceasta ar trebui să, cum ar fi, poate înjumătăți timpul, sau chiar mai mult, da. 

David J. MALAN: OK, poate chiar mai mult. Să împinge un pic mai greu la asta. Ceea ce într-adevăr, dacă vom continua acest logică, am înjumătățit siguranta durată de funcționare cu acest al doilea algoritm aruncând jumătate din numere, dar ceea ce am făcut la următoarea repetare, atunci când Jennifer a relevat al doilea număr? 

Am înjumătățit numărul de uși din nou. Și atunci ce am făcut după aceea, în cazul în care au existat mai multe uși pentru a juca cu? Noi le-ar reduce la jumătate, și din nou, și din nou, și din nou. Și acest lucru a fost la fel ca voi toți în picioare la prima săptămână de clasă, jumătate dintre voi sta jos, pe jumătate de stai jos, jumatate din tine ședinței în jos, până când unul singur Sufletul a fost în picioare. Și am spus că timpul de funcționare a că, numărul de măsurile pe care le au fost pe ordinea de ce? 

SPEAKER 1: [inaudibil] 

David J. MALAN: Deci baza log 2 n, sau doar mai simplu, jurnal de n. Așa ceva logaritmică. Iar graficul nu a fost o linie dreaptă care tocmai a devenit mai rău și mai rău, a fost această curbă interesant, care nu au obține așa de rău în timp. Deci, haideți să stai la această idee. Să-i mulțumim lui Jennifer. Multumesc mult pentru a veni în sus. Și, unul sec. Nu lămpi de birou azi, dar nu au CS50 bile de stres. 

JENNIFER: Yay. 

David J. MALAN: Bine, aici. Vă mulțumim pentru a suporta stresul aici. Bine. Așa că haideți să vedem dacă nu putem acum formaliza acest lucru un pic mai mult. Deci, din nou, ceea ce tocmai am făcut a fost în esență, același lucru ca și am făcut în prima săptămână. Dar, mai degrabă decât se termină cu doar un liniar algoritm, care este descris înainte ca această linie dreaptă, prin care, dacă am pus o ușă mai mult pe pe ecran, apoi Jennifer ar fi au trebuit să se uite, potențial, în urmă o ușă mai mult. Dacă am pus două uși mai mult, ea ar putea avea să se uite în spatele două uși mai mult. 

Și astfel, nu a fost acest liniar Raportul dintre mărimea Problema pe, să zicem, axa x, iar cantitatea de timp este nevoie pentru a rezolva pe y. Dar imaginea am fost aluzie la a fost mai devreme această linie verde. Verde în mod deliberat, pentru că doar simțit mai bine. În teorie, algoritmul, atunci când am făcut-o cu cartea de telefon, atunci când am făcut-o cu voi numărare reciproc, și în al doilea caz, atunci când Jennifer doar a făcut-o până aici, a fost un fel de fundamental mai bine. Pentru că nu a fost doar de două ori la fel de repede. Nu a fost chiar de patru ori mai repede. Acesta a fost în întregime dependentă de ceea ce Mărimea de intrare a fost, după cum a câte măsurile pe care le în cele din urmă a luat. 

Și așa această idee simplă, care ne-a luat tot pentru a acordat cu cartea de telefon, pot fi aplicate în mod similar la ceva de genul asta. Și acest lucru ar putea fi mult mai lejer cunoscut sub numele de, cum s-ar putea imagina, dezbina si cucereste. Nu spre deosebire de ceea ce am făcut, desigur, cu cartea de telefon. 

Dar pseudocod, rechemare, a fost aceasta. Așa că nu va face acest lucru din nou, dar amintesc că prima săptămână, toți dintre noi s-au ridicat și apoi jumătate de te-ai așezat jos, jumătate din ai stat jos, jumătate dintre voi așezat. Care Algoritmul a fost implementat într-un bit al unui mod înșelăciune, prin aceea că, ea nu a fost doar unul din mine numărare, fundamental, mai eficient. În acest caz, am fost pârghie o resursă secundară. Un fel de, mai multe procesoare, mai multe creiere, mai multe persoane inteligente cameră s-au m-ai ajutat obține de la ceva liniar la ceva logaritmică, de la ceva roșu la ceva verde. 

Dar, în acest caz, Jennifer singura care poate fundamental îmbunătăți pe performanța de primul ei algoritm de, din nou, doar gândesc un pic mai greu. Și acum, atunci când vine vorba de timp pentru a pune în aplicare aceste lucruri, imaginind ce linii de cod puteți scrie astfel de pe care le puteți repeta din nou, și din nou, și din nou, un fel de într-o manieră looping. Pentru că nu vei avea de lux, cum ar fi Jennifer a făcut la început, pentru a au doar o grămadă de FI și spune, hmm, în cazul în care acest prim număr este de 4, permiteți-mi să sari tot drumul până la sfârșit. Ooh, în cazul în care numărul este prea mare, permiteți-mi să se mute înapoi arbitrar la al doilea element. Veți găsi că va fi mult mai greu pentru a formaliza ceea ce noi, oamenii, ia acordat pentru ca foarte rezonabil euristica, dar un calculator este doar de gând să faci ceea ce-l spun să facă. 

Acum, acest lucru este foarte interesant implicații. Acest grafic este un fel de menit să rezolve de copleșească vizual, dar notificare, în cazul în care este linia dreaptă în acest grafic? În cazul în care este grafic liniar pe care o numim n? Ei bine, e un fel de către partea de jos de această imagine, nu? Deci, tot ce am făcut e că am un fel de mărită pentru axa x și axa y pentru a încerca pentru a obține un sentiment de ceea ce alte tipuri de curbe arata. 

Și de specificul matematice expresii de azi nu vor conta atât de mult, dar observați că există o mulțime de algoritmi care sunt mult mai rău decât ceva care este liniar. Într-adevăr, n cuburi arată destul de rău. 2 la n arată destul de rău. n pătrat arată destul de rău. Și vom vedea ce unii dintre cei ar putea fi în realitate azi. Și log n nu se simte la fel de rău, dar mai bine decât n este 2 log bază de n. Dar știi, ar fi fost chiar mai uimitor dacă Jennifer, sau dacă, că prima săptămână, a venit cu ceva care e jurnal de jurnal de n. 

Deci, cu alte cuvinte, nu e asta tot Gama de soluții posibile probleme, dar chiar și aici, notificare ce se va întâmpla. Când am micșora, care din aceste curbe se va dovedi a fi absolut cel mai rău de cele de pe ecran acum? Deci, n cuburi pare destul de rău în acest moment. Dar dacă ne depărta și a vedea mai mult din x și y-axa, care se va domina în cele din urmă? Deci, de fapt dovedește că 2 la n, și vă puteți da seama de acest lucru doar prin conectarea în unele ce în ce mai mare numere, și veți vedea că 2 la n, într-adevăr, se mărește mult mai rapid. Dacă vrem cu adevărat micșora, o 2 la n algoritmul absolut e de rahat. Vreau să spun acest lucru se întâmplă să ia destul de un pic de timp pentru calculator, pentru a prelucra. 

Dar veți vedea în timp, mai ales cu viitoarele seturi de probleme și chiar proiecte finale, este datele dumneavoastră Set devine mare, bine? Chiar și în prima versiune a Facebook, ca numărul de prieteni, și numărul de utilizatori înregistrați ai mare, puteti sorta de telefon ea în și implementa ceva cu căutare liniară, sau o sortare foarte simplu algoritm, așa cum vom vedea azi. Trebuie să începem să gândim mai greu și mai greu despre aceste probleme. Și tipurile de probleme de locuri, cum ar fi Facebook și Google, și Microsoft, și alții lucrează în exact aceste fel de mare fel de date de întrebări din ce în ce în aceste zile. 

Bine. Deci, succesul lui Jennifer, în care a doua algoritm, sincer, ea a făcut uimitor bine prima dată, dar hai scrie-l ca noroc, astfel încât să pot face acest punct. În al doilea caz, ea indatorare un algoritm care repetă din nou și din nou, dar ea a luat pentru a acordat un sigur presupunerea că am permis ei, dar ea a exploatat unele detalii a doua oară că ea nu a avut prima dată. Care a fost ce? 

Că lista a fost sortate. Asa ca imediat ce lista a fost sortate, ne susțin că Jennifer a fost în stare să facă fundamental mai bine. 7 usi, da, nu este interesant, dar să presupunem că suntem 7 milioane de uși. Jurnal de n este cu siguranta va pentru a efectua mult, mult mai rapidă pe termen lung. Dar ea trebuia să aibă usi clasificate în funcție de ea. Acum, mi-am luat libertatea de a face asta în prealabil pe ecranul calculatorului aici, dar să presupunem că Jennifer a trebuit să facă asta ea? Să presupunem că ușile în cauză Datele reprezentate într-o bază de date, sau Prietenii înregistrate pentru Facebook, sau orice pagini web pe internet care diverse site-uri ar putea avea nevoie să indice sau căutare pe. 

Să presupunem că tocmai ați avut de date brute stabilit și a fost lăsat la tine, sau să Jennifer a face acest lucru sortare? Că, mai degrabă, ne cere să răspundă problema, ei bine, cât de mult timp ar fi luat Jennifer, sau chiar și pe mine, pentru a sorta aceste numere în avans, astfel încât că ea ar putea profita de asta? Dreapta? Deoarece implicație, desigur, este în cazul în care este nevoie de mine ceva timp pentru a sorta numerele, care naiba ii pasa pe care le Puteți găsi un număr ca 50 atât de repede, ca și în cazul lui Jennifer, dacă am mai mult copleșit de cantitatea de timp totală a luat de sortare lucruri în avans? 

Așa că haideți să vedem dacă nu putem picteze imaginea aici. Am o grămadă mai mult stres bile, în cazul în care vă ajută sparge gheata aici. Și dacă nu te superi, am nevoie de șapte voluntar - pe, OK. Wow. Deci, noi nu trebuie să-și petreacă pe lămpi de birou, se pare. Bine. Deci, cum despre voi doi in fata. Cum despre voi doi, în spate. Așa că e patru. Cum despre tine in fata cinci, șase și șapte. Chiar acolo. Prietenul tau te-subliniind, astfel încât să obțineți un premiu. 

Bine. Hai sus. Și de ce nu ne-ai veniți pe aici. Am de gând să vă dau fiecare un număr. Și mergeți mai departe și aranjați-vă identic cu ceea ce este reprezentate pe ecran. 

[Interpune VOCI] 

David J. MALAN: OOP, îmi pare rău. Bug. Bine. Ei bine, aici vom merge. Numărul cinci. Numărul șase. Unu, doi, trei, patru, cinci, șase, șapte. Oh, asta e ciudat. 

DIFUZOR 2: Voi lua doar o -. 

David J. MALAN: afacere bună. Bine. Va multumim pentru participare. 

[Aplauze] 

OK. Bine. Deci avem patru, două, șase, unul, trei, șapte, cinci. Perfect așa că avem șapte voluntari aici care sunt egale în lățime cu matrice care ne jucam cu mai devreme. Și am ales șapte motive care va fi doar convenabil într-un pic. Și am de gând să propună mai întâi că am sorta aceste șapte voluntari. Dacă doriți, în primul rând, să-l salut, deși. Din moment ce acest lucru va fi un incomode câteva minute. Introducerea voi. 

GRACE: Bună, eu sunt Grace. Sunt un al doilea de studentie la Leverett House. 

BRANSON: Hi. Sunt Branson. Sunt un boboc în Weld. 

GABE: Hi. Sunt Gabe. Sunt un junior în Cabot. 

NEIL: Eu sunt Neil. Sunt un boboc în Matthews. 

JASON: Sunt Jason. Sunt un boboc în Greenough. 

MIKE: Sunt Mike. Sunt un boboc in Grays. 

JESS: Sunt Jess. Sunt un al doilea de studentie la Leverett. 

David J. MALAN: Excelent. Bine. Ei bine, vă mulțumesc pentru toate noastre voluntarii de aici până acum. Și provocarea la îndemână acum se întâmplă să fie la un fel de acesti baieti, dar apoi am de gând să trebuie să se gândească un pic tare despre cât de eficient ne de fapt le-am sortat. Deci, haideți să încercăm mai întâi acest lucru. Voi putea vedea numere reciproc doar prin plasarea în jurul colțuri. Du-te și ia câteva secunde, și Sorteaza-vă de cea mai mică pe a plecat la cel mai mare de pe dreapta. Du-te. 

OK. Bun. Asta a fost rapid chiar darn. Acum cineva aici, care a fost algoritmul că tipii ăștia aplicat? 

SPEAKER 1: cel mai puțin la cel mai mare. 

David J. MALAN: OK. Cel puțin pentru cea mai mare este într-adevăr un fel de obiectiv, dar eu nu sunt sigur că e într-adevăr un algoritm. Cel mai mare de a nu spune mi pas-cu-pas ce să facă. Da? 

SPEAKER 1: [inaudibil] 

David J. MALAN: OK. Deci, dacă vedeți o persoană mai mică decât numărul, apoi trece la dreptul de ei. Deci, care este acum devine mai expresiv, mai mult ca un algoritm, pentru că se poate spune, în cazul în care acest lucru, atunci. Deci avem un fel de construct condiționată. Și tipii ăștia păreau să faci asta câteva ori, pentru că unii dintre voi s-au mutat un pic de la distanță. Deci, nu era probabil un fel de looping întâmplă în mintea lor. 

Dar să încercăm să oficializeze acest lucru. Dacă voi putea reseta înapoi la acest aranjament. Să vedem dacă nu putem formaliza acest lucru o bit, iar apoi pune întrebarea, doar cat de eficient este acest lucru? Desigur, atunci când facem acest lucru mai lent, se va simti la fel de bine de un algoritm, dar să vedem dacă putem pune degetele pe treptele precise. 

Deci, voi doi sunt patru și doi. Sau te ordinea corectă sau incorectă? În mod evident incorecte. Așa că am schimbat. Acum am de gând să se mute la o parte aici și spune, patru la șase. Esti corect sau incorect? 

GABE: Corect. 

David J. MALAN: Corect. Sase si unul? Nope. Swap. Deci asta e două swap. Șase și trei? Nope. Swap. Șase și șapte? Arată bine. Șapte și cinci? 

JESS: [inaudibil] 

David J. MALAN: OK, schimba. Și sortate. Bine. Deci, evident, nu, corect? Deci nu a fost mai întâmplă. Dar, într-adevăr, acești oameni, chiar doar instinctiv. păstrat în mișcare. Ei nu s-au oprit doar după ce corectat o problemă. Deci. Într-adevăr, am de gând să aibă să facă același lucru. Am de gând să aibă de a sorta de derulare înapoi la începutul acestei probleme, sau la începutul acestei matrice de oameni, să începem numindu-le. 

Și acum ce ar trebui algoritmul meu pe a doua trecere să fie? 

SPEAKER 1: Același lucru. 

David J. MALAN: Același lucru. Și acest lucru, am început să-mi placă, nu? De îndată ce puteți găsi te face același lucru din nou și din nou, că este ce în ce mai mult ca un algoritm, și instinct mai puțin umane. 

Deci, acum, aici vom merge din nou. Două și patru? Nu. Patru și una? Ah, nu a existat într-adevăr un sunt încă multe de făcut. Pentru și trei? Bun. Patru și șase? Șase și cinci? Șase și șapte? OK, acum, terminat. OK, nu. Trebuie să mă întorc. 

Deci, acum, din nou, facem asta un pic mai mult în mod deliberat. Și acum, nu e doar un creier executarea acestui algoritm. Un CPU, dacă vreți. Și sincer, asta e singura resursă vom avea acces la. Și odată ce te duci înapoi la o tastatură și au ceva de genul C la noastre eliminarea, suntem doar scris un program de care pot face un singur lucru la un moment dat. Întrucât, tipii ăștia acum o clipă, am efectul de levier mintile colective cum ați făcut voi în săptămâna zero. Așa că haideți să continuăm să facem acest lucru. 

Doi și unul. Doi și trei. Trei și patru. Patru și cinci. Cinci și șase. Șase și șapte. Done? Deci, eu sunt, dar permiteți-mi să joace avocatul diavolului. Eu, un fel de calculator, care tocmai a făcut o trecere prin această serie de oameni, știu că am terminat? 

SPEAKER 1: Nu. 

David J. MALAN: Deci, de ce? Ce trebuie să fac pentru a concluziona în mod decisiv că am terminat? Probabil o trecere mai. Dreapta? Pentru că tot ce știu de la care anterior trecere este că am corectat o greșeală. Și asta înseamnă, poate exista încă o altă greșeală pe care am nevoie pentru a corecta. Deci, eu pot fi doar sigur de depanare, și apoi verificând, unul la doi, doi și trei, trei și patru, patru și cinci, cinci și șase, șase și șapte. OK, acum am făcut nici o lucrare. 

Îmi amintesc cu siguranță că am făcut nici o lucreze cu ceva ca o variabilă, ca un întreg. Spune-i swap-uri, și în cazul în care swap-uri este 0 după ce am ajunge aici, și a început la 0, atunci Mi-ar fi o prostie să continui înainte și înapoi, verificarea din nou, și din nou, și din nou, corect? Pentru că te-ai blocat în unele un fel de buclă infinită. Asa ca imediat ce există 0 swap-uri, putem afirma că această Algoritmul este într-adevăr complet. 

Acum, să punem un nume pe aceasta. Algoritmul pe care eu le propunem doar implementat este ceva numit bule sortare, cunoscut ca atare, în sensul că numerele care sunt un fel mai mari de bule modul lor de până la partea de sus, sau în sus la sfârșitul matrice de numere. Dar cât de eficient a fost acest algoritm? Câți pași aveam fizic ia, de exemplu, pentru a sorta aceste șapte oameni? 

Patru la cinci? OK, prea multe este în cele din urmă va fi răspunsul. Dar chiar și atunci, numărul specific nu este atât de interesantă. Să-l ca n generaliza. Deci, dacă am fi n oameni aici, și ei au fost, un fel de, în ordine aleatorie, la începând, în ordinea inițială. Ei bine, câți pași am avea pentru a lua cu privire la prima trecere? Acesta a fost unul, doi, trei, patru, cinci, șase, și sunt șapte persoane, astfel că e șapte, șase -, așa că e n minus unul pașii pentru prima dată. 

Acum, câți pași am avea pentru a lua atunci când am rebobinat? Ei bine, am putea dubla de fapt, că, dacă Am vrut sa, dar de acum, eu sunt doar de gând să spun, bine, încă n minus 1. Deci, n minus 1 este mergi la a lua enervant pentru a urmări, asa ca hai sa adun ușor. Deci 2n pași. Deci 14 etape, da sau ia. 

De câte ori nu am luat un pas data viitoare? Ei bine, e 3N. într-adevăr. Și acum, în cel mai rău caz, pentru exemplu, de câte ori aș avea plecat înainte și înapoi, înainte și înapoi, executarea acestui algoritm, schimbarea oamenii de pe fiecare trecere, aproximativ? Este de fapt n pătrat, nu? 

Pentru că în cel mai rău caz, puteți fel a gândi despre acest lucru intuitiv, chiar dacă s-ar putea să ia un pic pic de timp să se scufunde inch În cel mai rău caz, ceea ce ar fi acestea sapte persoane s-au uitat ca, în termenii acordului de numerele lor? Complet înapoi, nu? Și doar pentru a simula că, ceea ce a fost din nou numele tău? 

MIKE: Mike. 

David J. MALAN: Mike? Bine, Mike, poți să vii cu mine peste aici pentru o secunda? De fapt, nu. Ne pare rău Mike, hai înapoi. Care e numele tău din nou? 

NEIL: Neil. 

David J. MALAN: Neil. OK, Neil, ai venit cu ma, daca nu te superi. Așa că am de gând să propună, doar pentru simplitate, că Neil este acum în balonul cel mai rău caz posibil. Dar amintesc cum am implementat algoritmul meu. Am comparat, comparat, comparat, compararea, compararea, oh. Acum, acești oameni sunt în afara de ordine, așa că am rezolva. Deci, voi schimba. Dar ia în considerare acum, cât de mult mai departe are Neil trebuie să te duci? Este aproximativ n. Știi, nu e de fapt n. E ca si cum, n minus 1, dar eu sunt obtinerea urmări enervat păstrarea mic numărul, deci hai să spunem n. 

Deci, dacă Neil se mută cu un pas la maximum fiecare timp, și pentru a muta Neil un pas, Trebuie să facă acest pas foarte plictisitor înainte și înapoi, acest lucru este de aproximativ face acest lucru, n pași, un total de n ori, pentru că o să mă ia că mulți pași pentru a obține Neil toate modul de unde îi este locul. Să nu mai vorbim toți ceilalți dacă voi au fost toate mis-a ordonat, de asemenea. 

Deci, sa-i spunem un fel bubble n pătrat. Timpul de funcționare a acestui algoritm, performanța acestui algoritm, Eficiența acestui algoritm, vom descrie doar mai mult în general, ca pătrat n. Ceea ce este frumos, pentru că am putea face același exemplu cu opt oameni, nouă oameni, un milion de oameni, și că Răspunsul nu se va schimba. 

Deci, dacă voi nu m-ar deranja, să ați resetat de unde ai pornit. Și să încercăm alte două abordări și a se vedea dacă nu putem face în mod fundamental mai bine decât aceasta. Deci, de data aceasta, am de gând să propună un fel de algoritm diferit. Asta a fost foarte inteligent de noi data trecută, și voi au dreptul de a avea instinctele corecte de doar un fel de pompare perechi. Dar, dacă am vrut să abordeze această pur și simplu, iar scopul meu este de a muta toate numerele mici în acest fel, și împinge toate numerele mari care fel, de ce nu am face asta, în cel mai naiv mod posibil și să văd dacă se poate face mai bine decât ceea ce a fost un destul de algoritm complex? 

Deci, haideți să vedem. Patru este un număr destul de mic, așa că eu sunt O să te las acolo moment. Ooh, numărul doi este chiar mai bine. Deci, poți să pas înainte pentru o clipă? Aceasta este în prezent meu mai mic numerotate candidat, și am de gând să-mi amintesc că cu, ca, o variabilă. Dar am de gând să păstreze controlul. Există cineva a cărui Numărul este mai mic? Șase, nu. Oh, nu e din nou Neil. 

Așa că am de gând să te împinge înapoi un fel de punct de vedere conceptual. Neil va veni înainte. Și acum, variabila pe care îl folosesc pentru a ține evidența care are cea mai mică Numărul este actualizat pentru a conține Locația lui Neil. Ei bine, să vedem. Trei, șapte, cinci. OK, știu că Neil era cel mai mic. Care este cel mai simplu lucru pentru mine să fac acum? Eu nu am de gând să-mi pierd timpul cu doar barbotare Neil un loc la stânga. De ce nu am pus doar Neil, unde a îi aparține, care este, desigur, în cazul în care? 

Tot drumul de la început. Deci, Neil, vino cu mine. Și ce a fost din nou numele tău? 

GRACE: Grace. 

David J. MALAN: Grace. OK. Deci Grace, din păcate, tu ești cam în mod. Deci, cum putem rezolva această problemă? Dreapta? Dacă aceasta este o matrice, există doar șapte locuri. Amintiti-va ca, cu Rob, am vorbit despre declararea vârstele, și am avut doar o număr finit de varsta? Aceeași idee aici. Avem doar un număr finit de int. Grace este un fel de la noi Astfel, așa cum am rezolva? 

Cea mai simplă cale este ca, Grace, îmi pare rău. Ai de gând să trebuie să treacă peste acolo astfel încât să putem face loc. Acum, dacă te gândești la asta, poate ne-am facut problema mai rău. Și poate că am făcut-o, pentru că ceea ce în cazul în care Grace au fost în locul potrivit? Dar noi știm că nu e, pentru că altfel, ar fi fost în picioare înainte în loc de Neil la acest moment, nu? Am verificat deja numărul ei afară. 

Bine. Deci, acum, Neil este în locul potrivit, și Pot face o optimizare ușoară. Pentru minutul următor, am de gând să ignore Neil toate împreună, astfel încât să nu pierde timpul, sau accidental schimba-l la locul nepotrivit. Deci, acum, cum pot găsi la următoarea element care e mai mic? Două. Asta e un număr destul de bun, în cazul în care pe care doriți să pas înainte și O să vă amintiți. Șase, nu bine. Patru, trei, șapte, cinci, nu e bine. Deci, permiteți-mi să vă mutați la locul potrivit. Și am avut noroc de data asta. 

Acum, am de gând să ignore aceste doi tipi, iar acum nu o mai trece prin aceasta. Șase, că un număr destul de mic. Haide înainte. Oh, îmi pare rău. Numărul harul este mai bine, așa pas pe mai departe. Patru. Îmi pare rău, Grace. Du-te înapoi din nou. Numarul trei este mai bine. Șapte. Cinci. Și acum, ce e numele tău din nou? 

JASON: Jason. 

David J. MALAN: Jason. Deci, Jason este acum cel mai mic Elementul am selectat. Unde se duc? Deci, unde șase este. Si numele tau este din nou? 

GABE: Gabe. 

David J. MALAN: Gabe. Gabe este în mod. Care este cel mai ușor lucru de făcut? Swap doi tipi și continuă. Deci, acum să vedem. Cine este cel mai mic? Patru. Permiteți-mi doar un fel de ieftin. Cinci va fi mai mic. Mi se pare viitoare, în cazul în care, vrei să-și intensifice înainte, ce trebuie să fac cu acesti baieti, cu Gabe? Swap din nou. Deci, acum, încă ușor de ordine. Am găsit Gabe este cel mai mic, astfel încât L-am ieși, muta voi peste. Și făcut. 

Deci răspunsul este același. Rezultatul final este același. Care dintre aceste două algoritmi este mai bine? A doua, am auzit. De ce? 

SPEAKER 3: Este n pași [inaudibil]. 

David J. MALAN: Este pași n cel mult. Interesant. Deci, este totuși? Deci, cum am găsi mic element? Cati pasi a trebuit să ia găsi cel mai mic element? Am avut o privire tot drumul la final, nu? Deoarece în care cel mai rău caz, ceea ce dacă Neil s-au terminat aici? Deci, doar a găsi cel mai mic element ia-ma n trepte, sau n minus 1. Dar, OK. Deci repara Neil. Amintiți-vă că, un minut sau cam asa ceva în urmă. 

Dar cum am găsit următoarea mic element? Este n minus 1, sau n minus 2 într-adevăr, din numărul de pași. Deci OK. Așa că am făcut n minus 2. Bine. Astfel că se simte un pic mai bine. Bine. Câți pași data viitoare pentru a găsi numărul trei? Deci n minus 4. Deci, este în scădere, una mai pas la fiecare iterație. Deci, acest lucru se simte mai bine, nu? În cazul în care ultima data a fost de aproximativ n ori n, de data aceasta n minus 1, plus n minus 2, n plus minus 3, plus n minus 4, punct, punct, punct. Dar, dacă vă amintiți de la liceu manuale, mic cheat foaie la spate care are formule, dacă să adăugați la această serie de numere, ceea ce este numărul total de etape O să fie ca iau aici? 

Acesta este unul dintre cei care, ca, n minus 1, ori n, împărțit la 2. Deci, lasă-mă să văd dacă pot trage asta doar pentru o clipă. Și din nou, eu sunt un fel de rotunjire unor Numerele doar pentru a menține viața noastră simplă, dar din cate imi amintesc, e ceva de genul dacă Eu fac n minus 1 lucruri, atunci n minus 2, atunci n minus 3, este aproximativ ceva de genul asta de peste 2, și dacă am multiplica acest lucru, că este de fapt n pătrat. Asta nu se simte prea bine. n minus n peste 2. 

Dar aici e de lucru. În informatică, atunci când problemele începe pentru a obține interesant este atunci când n devine foarte mare. Și când n devine foarte mare, care a aceste valori se va domina toate de ceilalți? Este un fel de n pătrat, nu? Da, împărțind cu 2 este destul de bun. Dar dacă vorbim despre miliarde de fragmente de date, sau trilioane de piese de date, OK, ești de două ori mai repede. Dar care într-adevăr îi pasă dacă acest număr mare, dacă acest factor este ceea ce devine mai mare și mai mare. Și cu siguranță, face mai mult de o diferență de acest tip. Deci, chiar dacă voi dreptate, algoritm al doilea rând, vom numi un fel de selecție, este, în lumea reală, o bit mai repede posibil, pentru că eu sunt având mai puține și mai puține pași de fiecare dată. 

Nu este într-adevăr fundamental mai repede. Pentru că dacă vom juca de fapt acest lucru pentru valori mari ale lui n, la sfârșitul a doua zi, de mare n suficient, este încă de gând să se simtă destul de lent. Ei bine, lasă-mă să iau un trecere trecut la asta. Asta e ceea ce aș numi un fel de selecție. Poate voi putea suporta singuri pentru ultima oară? Și în acest ultim caz, am de gând să propună ceva numit un fel de inserare. Un fel de inserare fiind, conceptual, un pic diferit. 

Mai degrabă decât a merge înainte și înapoi și selectarea cel mai mic element, sunt doar de gând să se ocupe cu fiecare dintre aceste baieti ca le-am întâlni, și introduceți le în locul lor corecta. Deci, eu sunt doar de gând să înceapă cu Grace, și văd că e numărul patru. În cazul în care este numărul patru aparține? Nu am început sortarea nimic, Deci harul ajunge să stai acolo. Și acum am de gând să solicite, dacă ai putea ia un pas la dreapta ta, acest lucru Lista mea de sortat, acest lucru este meu lista rămasă nesortate. Așa că acum am de gând să procedeze viitor, și ceea ce este numele tau din nou? 

BRANSON: Branson. 

David J. MALAN: Branson. Deci, Branson este numărul doi. Așa că am de gând să vă luați pentru o clipă. Și acum, unde ți-e locul în acest tablou? Deci, pentru dreptul de Grace. Deci, din nou, suntem un fel de a face Grace face o mulțime de muncă aici. Unde ne-ai pus? Așa că am de gând să vă deplasați la a plecat, și introduceți Branson acolo. Dar acum eu susțin că voi terminat. Dar preaviz, eu nu folosesc spațiu suplimentar. Este încă 2 elemente aici, 5 aici. Dimensiunea totală matrice este 7, așa că eu sunt nu inseala, bine? 

Deci, acum avem, cu Gabe aici, număr de șase, unde ți-e locul? Ai din nou noroc. Astfel încât să obțineți pentru a rămâne acolo. Doar să ia o ușoară pas la dreapta doar pentru a face clar că ai sortat. Și acum avem Neil nou, numărul unul, unde te duci? Și acum este în cazul în care vom începe să vedem că acest algoritm, deși la prima vedere, se simte destul de inteligent, ceas ce e pe cale să se întâmple. Dacă ați putea pas înainte. 

În cazul în care vrem să Neil? Deci, evident aici, așa cum ajungem Neil acolo? Să facem acest pas-cu-pas. Gabe, în cazul în care aveți nevoie pentru a merge? Da, astfel încât să ia un pas mare, sau două jumătăți de măsuri pentru a face un pas de acolo. Grace, unde te duci? Bun. Deci, un alt pas. Și, în sfârșit, Branson? Un alt pas. Și acum putem pune Neil în loc. 

Deci, acum, continua această logică. Chiar dacă nu se schimbă Neil peste, si peste, si peste, să-l pună unde se duce, în cel mai rău caz, Numărul următor am putea întâlni putea fie numărul, spune, a existat un număr zero, atunci vom schimba toate tipii ăștia. Să presupunem că există un număr, negativ una, atunci avem de a schimba toate aceste baieti. Deci, suntem într-adevăr doar un fel de flipping problema în jurul, astfel încât suntem transferarea cheltuiala de Procesul de selecție astfel inserție proces, astfel că voi a avut doar să se mute aproximativ n minus ceva număr de pași. Și că numărul de pași este doar de gând să crească așa cum am selecta mai multe numere, dacă trebuie să țină împinge voi înapoi, și înapoi, și înapoi. 

Deci, lucru trist este acum toate acestea algoritmi sunt n pătrat. Să mergem mai departe și datorită acestor baieti, si sa vizualizeze acestea un pic diferit. Foarte bine facut. 

[Aplauze] 

Bine. Acolo te duci. Vă mulțumim pentru - 

BRANSON: [inaudibil] păstra numerele. 

David J. MALAN: Nu, s-ar putea păstra numerele de asemenea. Bine. Bine făcut. Bine. Așa că haideți să vedem dacă nu putem acum rezuma mai rapid, și mai vizual, exact ceea ce sa întâmplat aici după cum urmează. Am de gând să merg mai departe și trage Firefox. Vom lega această demonstrație pe site-ul cursului. Java este un pic enervant pentru a obține de lucru în unele browsere in aceste zile. Deci, dacă te joci cu acest lucru la domiciliu, dai seama ca ar putea avea nevoie să utilizați Firefox să-l de lucru. Și ceea ce am de gând să fac cu acest Demonstrația este următoarea. 

În partea de jos, am o grămadă de opțiuni de meniu, inclusiv un început și un butonul de oprire. De asemenea, ca o parte, se pare că există un bug în aceste programe, prin care nu se poate vedea, de fapt, de început sau Butonul dacă nu vă țineți de comandă sau Alt plus și zoom in, care curios, vă arată mai multe butoane. Deci, doar FYI, dacă joci cu acest lucru la domiciliu. Acum am de gând să faceți clic pe Start în doar o clipă, după care specifică o întârziere de, cum ar fi, de 200 de milisecunde aici, doar astfel încât să putem vedea ce se întâmplă. 

Deci, eu susțin că aceasta este o vizualizare a primului algoritm tipii ăștia a făcut, un fel balon, prin care am schimbat oamenii pe perechi. Perspectiva cheie în această vizualizare este că înălțimea barelor reprezintă mărimea numărului. Deci, mai inalt bar, mai mare număr. Mai scurt bara, mai mic numărul. Și dacă observați, vom merge prin prima iterație a acestui algoritm, schimbarea numerelor mari și mici, astfel încât numărul mic este pe primul loc și numărul mare merge spre dreapta. 

Și, de îndată ce ajungem la sfârșitul anului matrice de mai multe numere de șapte, suntem merge înapoi la început. Și anticipa acest lucru. Pe extrema stângă, că micuțul va a schimba la o parte, și această procesul se repetă. Acum, această vizualizare devine rapid plictisitor, asa ca lasa-mă să merg mai departe și se va opri l, schimba ceva întârziere mult mai repede doar pentru a obține acum, o simt pentru acest algoritm. 

Deci, chiar dacă l-am accelerat, acest lucru este cum ar fi modernizarea procesor mea, cumpărare un nou calculator. Nu m-am schimbat fundamental meu algoritm, dar puteți vedea într-adevăr mai mult clar decât cu oamenii, că mare Numerele sunt bule până la partea de sus, și cifrele mici sunt barbotarea până la fund. Iar acum acest lucru aici sortat. Și, ca o paranteză, în piețe, există doar câteva contabilitate acolo pentru a ajuta să conta cât de multe comparații, sau cât de multe swap-uri au de fapt, sa făcut. 

Ei bine, hai sa incercam unul din ceilalți am văzut. Permiteți-mi să faceți clic pe un fel bule aici, și lasă-mă să aleg, iar aceasta pagina web tot este un pic buggy. Să accepte riscul și executați din nou. Acolo mergem. Deci, haideți să facem un fel de selecție. Nu știu de ce meniul apare acolo. Să zoom în a stabili care bug-ul, schimba aceasta la 50. Ah, hai să facem de fapt că mult mai rapid. Cinci milisecunde sau cam asa ceva, și să înceapă. 

Deci, aceasta este un fel de selecție. Deci, din nou, cred despre ceea ce am a făcut cu oamenii de aici. Am trecut prin matrice și selectat cel mai mic element din nou, și din nou, și din nou. Acum, eu pretind că era încă destul de rău. Acesta a fost încă n patrat, da sau de a lua, dar a fost, în lumea reală, un pic mai repede, pentru că am fost într-adevăr a lua ușor mai puține etape de fiecare dată. Dar vorbim doar ce? Poate 40 sau cam asa ceva baruri aici? Nu vorbim de 40 de milioane. Deci, nu este clar în totalitate la mine că a fost într-adevăr un câștig semnificativ. 

Lasă-mă să mă întorc și să modificați la noastre treilea algoritm, care a fost selectați un fel de inserare. Și acum este într-adevăr buggy, deoarece Meniul într-adevăr nu ar trebui să fie acolo. Deci, acum vom derula înapoi aici și de a începe acest algoritm. Tuși, porni și opri. Deci, aceasta un fel de are un model destul de să-l, prin care suntem din nou inserarea om, sau în acest caz, barele în locația corespunzătoare a acestora. Și este deja făcut înainte M-am întors. Dar aceasta, de asemenea, în teorie, este încă n pătrat. 

Așa că haideți să vedem dacă nu putem rezuma acestea, după cum urmează. Am de gând să merg mai departe și doar pentru a da ne un fel de mod comun de a vorbi despre aceste lucruri, permiteți-mi să introducă doar un pic de notație aici. Esti pe cale de a vedea ceva numit mare O, pentru că este pur și simplu o mare O. Și acesta este un mod care un calculator om de stiinta sau un matematician chiar folosește pentru a descrie timpul de execuție de unele algoritm. Câți pași nu-l ia de fapt? 

Acum am de gând să mă face de râs cu scrisul meu aici, în doar o clipă. Dar lasă-mă să merg mai departe și spune că acest lucru va fi mare O aici. Și permiteți-mi să introducă un alt simbol, un omega de capital. Omega va fi opusul, în esență, de mare O. întrucât Big O înseamnă, în cel mai rău caz, cât de mult timp ar putea un algoritm ia, în termeni de n, omega va fi cât de mult timp s-ar putea ia, în cel mai bun caz. Și vom vedea ce se înțelege prin cel mai bun caz, într-o clipă. 

Așa că haideți să începem ceva simplu. Permiteți-mi să încep cu o căutare liniară. Deci, nu de sortare. Vom numi această căutare liniară. Și acum, face un pic Tabelul din acest. Și acum, în cazul de căutare liniară, în cel mai rău caz, cât de multe etape este merge să mă ia pentru a găsi o Numărul de alegere arbitrară? Și există uși Total N sau n numere totale. Cel mai rău caz. Câți pași am de gând să trebuie să ia de a găsi numărul 50 într-o matrice de n uși? Și de ce? Deoarece ar putea fi tot mult peste pe final. Atât de mult ca Jennifer întâlnite, Numărul 50 a fost tot drumul peste, astfel încât, în cel mai rău caz de căutare liniară este mare O, de n, vom spune. 

Ce despre cel mai bun caz, dacă aveți într-adevăr norocos? Este doar de gând să ia un pas, sau un număr constant de pași. Deci, vom descrie ca ca 1. Deci, acest lucru este destul de bun. Acum, ce dacă am făcut ceva cum ar fi căutare binar? De căutare, astfel binar, în cel mai rău caz, a luat cât de mult timp? 

[Interpune VOCI] 

David J. MALAN: Deci, de fapt, am auzit-o în câteva locuri. Deci, de fapt log n, da sau de a lua, pentru că așa cum am împărți lista de la jumătate din nou, și din nou, și din nou, suntem capabili pentru a găsi, în cele din urmă, valoarea, daca e acolo, dar există o captură. Ce-i de la premisa că trebuie să ia pentru a acordat pentru căutarea binar? Ea trebuie să fie sortate. Nu este sortat, puteți împărți lucrul în jumătate din nou și din nou, și tu pot merge la stânga, și puteți merge drept, și poti sa te duci la stânga și la dreapta, dar tu esti Nu merge pentru a găsi elementul dacă lista nu este sortată, deoarece s-ar putea dor de ea. Deoarece euristică dvs., pentru a merge la stânga sau drept va fi eronată, dacă este într-adevăr nu sortat. Deci, există un fel de cost ascuns de a folosi ceva de genul asta. 

Acum, să mergem în sortarea nostru algoritmi nu caută - oh, de fapt, să mergem în acest gol. Binar de căutare în cel mai bun caz? Este, de asemenea, 1 în cazul în care se întâmplă să fie în foarte mijlocul matrice, sau mijlocul de cartea de telefon. Acum, hai să facem un fel bule. Deci, din nou, acum intrăm felul, nu de căutări. 

În cel mai rău caz, câți pași am făcut cerere bule de sortare va lua? n patrat. Așa că am de gând să atragă asta. Ooh, scrisul meu arata chiar mai rău atunci când este proiectat atât de mare. Bine. Deci asta este n pătrat. Și, în cel mai bun caz de fel de bule, câți pași este de gând să ia? 1, am auzit. 

SPEAKER 1: n. 

David J. MALAN: N-am auzit. 

DIFUZOR 1: 2. 

David J. MALAN: 2, am auzit. Am auzit 3? Bine. Așa am auzit 1, n, 2, dar să alegeți în afară cel puțin primul dintre cele sugestii, 1. Nu e un instinct rău, pentru că un fel de urmează un model aici. Dar dacă este nevoie de doar un pas, cum în Lumea aș putea pretinde că lista este sortat, pentru că dacă eu sunt doar permis să ia 1 pas, cât de multe elemente aș putea chiar verifica pentru a fi sigur? Ei bine, doar 1, ceea ce înseamnă că există n minus 1 elemente care ar putea fi de ordine, și Mă duc la credință, după uită la 1 element care lucru este sortat. Deci 1 nu este corect aici. Deci, minim, câte trebuie să mă uit la? 

[Interpune VOCI] 

David J. MALAN: n minus 1, sau într-adevăr, n, pentru că am nevoie să se uite la fiecare Elementul să vă asigurați că nu este în ordine. Dar, din nou, vom rezolva de val nostru mâinile la numerele mai mici și presupune că, așa cum n devine mare, sunt neinteresante oricum. Deci, asta e un fel balon. Și acum, hai sa facem aceste ultimele două. Un fel de selecție, iar apoi vom face un fel de inserare. Și apoi vom sufla dvs. mintea cu ceva mult mai bine decât toate acestea. Bine. 

Care este cel mai rau caz de funcționare timp de fel de selecție? 

DIFUZOR 4: N patrat. 

David J. MALAN: n pătrat, aud. Dar de ce n pătrat, intuitiv? 

DIFUZOR 4: Pentru ca ne-am făcut-o. 

David J. MALAN: Pentru că ne-am făcut-o. OK. Bun răspuns. Dar intuitiv, ce este selectarea fel n pătrat? Ce am avut de a face din nou și din nou? Am avut de a păstra scanarea prin, sunt te cel mai mic, tu esti mai mici, sunteți cel mai mic. Și a acordat, am fost în măsură să ia n etape, atunci n minus 1, atunci n minus 2. Dar, dacă aveți un fel de adăuga celor toate în sus, sau l ia pe credință care le-am adăugat le în avans, avem aproximativ n pătrat minus câteva numere mai mici. Așa că am de gând să numim această n pătrat. Dar, cu un fel de selecție, în cel mai bun caz, câți pași este O să mă ia? 

DIFUZOR 5: [inaudibil] 

David J. MALAN: Este, din păcate, încă n pătrat, nu? Pentru că dacă eu sunt alegerea cea mai mică elemente, și am avut șapte persoane aici, Știu doar, o dată ce am ajunge la foarte sfârșit, că am găsit cel mai mic număr, ori de câte ori el sau ea ar fi fost. Dar cum pot găsi la următoarea cel mai mic număr? Trebuie să fac o altă trecere. Deci, în cel mai bun caz, ceea ce este de intrare la fel de selecție? Este o listă deja un fel, numărul unu, Numărul doi, numarul trei, numărul patru. Dar eu sunt un calculator. Eu pot uita doar la un singur lucru la un moment dat. Eu nu pot sorta a lua un pas spate, ca un om și spune, ooh, acest lucru pare corect. 

Eu pot pronunța doar corectitudinea în selectare Sortare prin selectarea cel mai mic număr. Dar chiar dacă am găsi numărul unu în primul rând, dacă nu știu nimic altceva despre cu alte numere, pe care eu nu fac, tot ce am Știu că am fost înmânat un tablou sau un set de uși în spatele cărora sunt numere, singurul mod in care stiu ca o a fost mai mic? Dacă am lua tot drumul aici și dau seama, La naiba, unul a fost într-adevăr cel mai mic. 

Dar cum pot apoi să determine care doi este următoarea cea mai mică? Făcând același ineficiența din nou și din nou. Deci, în final, cu un fel de inserție, cum, în cel mai rău caz, am spune că efectuează? Acesta este de asemenea n pătrat. Și cum despre cu cel mai bun caz? Vom lăsa ca pe un Cliffhanger. Vom completa acest timp gol viitoare, dar mai întâi permiteți-mi propun să fundamental face mai bine decât toate acestea, în regulă? 

Deci, cred că pentru tine ceea ce inserare fel va fi. Ei bine, că nu a fost foarte dramatic, pentru că eu sunt singurul care a văzut schimbarea. Wow. OK. Deci, aici avem o oarecum diferite demonstrație. Dacă aș apropia aici, veți vedea că pe stânga avem un fel bule, în Orientul Mijlociu, avem un fel de selecție, și pe în dreapta, avem ceva ce nu s-au uitat la încă numit fuziona fel. Dar ia în considerare ceea ce am fost aici până acum astăzi. Când Jennifer venit prima dată pe scenă, am trecut prin matrice de numere din nou, și din nou, cu căutare liniară, și ne-am timp de funcționare liniară, mare O de n, ca să spunem așa. 

Când luăm în considerare acum prima săptămână de clasă, atunci când ne-am dezbina si cucereste, și am avut cartea de telefon rupere, și Jennifer, și am colectiv indatorare că perspectiva cheie, care a fost de a repeta-te din nou și din nou de într-un fel aruncați, aruncați, aruncați, jumătate din problemă, sau în general, împărțind o problemă în jumătate, și apoi tratarea bucată mică de problema ca conceptual echivalent la alții, am făcut într-un fel fundamental mai bine. Dar cu un fel bule, cu selecție fel, cu un fel de inserție, ne-am putea nici o astfel de perspective pe care Jennifer a făcut. Am destul de mult tocmai a intrat înapoi și mai departe o grămadă de ori, și am lucrurile optimizat un pic, schimbarea în această ordine, poate introducerea sau selectarea. Dar la sfarsitul zilei, am făcut o mulțime de mers pe jos de ciudat înainte și înapoi. Noi nu într-adevăr ceva de pârghie inteligent ca Jennifer a făcut ca împărțirea și cucerirea. 

Deci fuziona fel, prin contrast, noi care nu va vedea până săptămâna viitoare, se va pentru a pârghie ideea cheie prin împărțirea intrare, și apoi reducerea la jumătate, iar apoi reducerea la jumătate, și apoi înjumătățirea. Și pe fiecare iterație a buclei, sortare jumătatea din stânga, și dreapta jumătate, apoi jumătatea din stânga a jumătate din stânga, și jumătatea din dreapta a stânga, apoi jumătatea stângă a jumătatea din dreapta, și jumătatea dreaptă a jumătatea din dreapta. Și se repetă din nou și din nou. 

Deci, veți vedea acest punct de vedere vizual, dar acest lucru este ceea ce ne așteaptă săptămâna viitoare. Și, în general, atunci când ne gândim un pic mai greu cu privire la orice astfel de problemă. Am n pătrat pe stânga, n pătrat la mijloc, și n log n pe dreapta. Deci, nu e Cliffhanger tau real. Ne vedem luni. 

[Aplauze]