Bine, deci, complexitatea de calcul. Doar un pic de o avertizare înainte de a se arunca cu capul în noi prea far-- Va fi, probabil, printre lucrurile cele mai grele de matematica- vorbim despre în CS50. Să sperăm că nu va fi prea copleșitoare și vom încerca să vă ghida prin acest proces, dar doar un pic de un avertisment echitabil. Există un pic de matematică implicat aici. Bine, astfel încât, în scopul de a face folosirea resurselor noastre de calcul în world-- reală este într-adevăr important să se înțeleagă algoritmi și modul în care acestea prelucrează datele cu caracter. Dacă avem un foarte algoritm eficient, am poate reduce cantitatea de resurse avem la dispoziție de a face cu ea. Dacă avem un algoritm care este de gând să ia o mulțime de muncă pentru a procesa un adevărat set mare de date, este O să solicite mai multe și mai multe resurse, care este de bani, RAM, toate acest tip de lucruri. 

Deci, fiind în măsură să analizeze o algoritm folosind acest set de instrumente, Practic, solicită question-- cum face acest lucru la scară algoritm așa cum am arunca tot mai multe date de la ea? În CS50, cantitatea de date suntem de lucru cu este destul de mic. În general, programele noastre sunt de gând pentru a rula într-un al doilea sau less-- probabil mult mai puțin în special de timpuriu. 

Dar gandeste-te la o companie care se ocupă cu sute de milioane de clienți. Și au nevoie pentru a procesa că datele clientului. Pe măsură ce numărul de clienți care le au devine mai mare și mai mare, se va necesita mai multe și mai multe resurse. Cât de mult mai multe resurse? Ei bine, asta depinde de modul în analizăm algoritmul, utilizând instrumentele din acest set de instrumente. Când vorbim despre complexitatea un algorithm-- care, uneori, veți auzi mentionat ca timp complexitate sau spațiu complexitate dar noi suntem doar de gând pentru a apela complexity-- ne, în general, vorbim despre scenariul cel mai rău caz. Având în vedere cel mai rău gramada absolută a datele pe care le-ar putea arunca la ea, cum este acest algoritm va procesa sau a face cu faptul că datele? Noi, în general, numim cel mai rău caz execuție a unui algoritm de mare-O. Deci, un algoritm poate fi spus să alerga în O de N sau O N pătrat. Si mai multe despre ceea ce cele înseamnă într-o secundă. 

Uneori, însă, facem grijă despre cel mai bun caz. În cazul în care datele sunt tot ceea ce ne-am dorit să fie și a fost absolut perfect și am fost trimiterea acestui perfectă set de date prin intermediul algoritmului nostru. Cum ar descurca în această situație? Uneori ne referim la faptul că în calitate de mare-Omega, astfel încât, în contrast cu mare-O, avem mare-Omega. Big-Omega pentru cel mai bun caz. Big-O pentru scenariul cel mai rău caz. În general, atunci când vorbim despre complexitatea unui algoritm, noi vorbim despre în cel mai rău caz. Astfel încât să păstreze în minte. 

Și în această clasă, vom merge, în general, să părăsească analiza riguroasă deoparte. Există științe și domenii dedicat acest gen de lucruri. Când vorbim despre raționament prin algoritmi, care vom face-bucata-cu bucată pentru mulți algoritmi vorbim despre în clasa. Suntem de fapt doar vorbesc despre raționamentul prin ea cu bun simț, nu cu formule, sau dovezi, sau ceva de genul asta. Deci, nu vă faceți griji, Nu vom fi transformându-se într-o mare clasă de matematică. 

Așa că am spus ne pasă de complexitate deoarece pune întrebarea, cum Nu algoritmi noastre se ocupe mai mare și seturi mari de date fiind aruncat la ei. Ei bine, ceea ce este un set de date? Ce am să spun când am spus asta? Aceasta înseamnă orice face cel mai mult sens în context, să fiu sincer. Dacă avem un algoritm, The Procese Strings-- suntem, probabil, vorbind despre dimensiunea șir. Asta e datele set-- dimensiunea, numărul de caractere care alcătuiesc șirul. Dacă vorbim despre o algoritm care procesează fișiere, am putea vorbi despre modul în care multe kilobytes cuprinde acel fișier. Și asta e setul de date. Dacă vorbim despre un algoritm care se ocupă de matrice, mai general, cum ar fi algoritmi de sortare sau căutarea algoritmi, ne, probabil vorba despre numărul de elemente care cuprind o serie. 

Acum, putem măsura o algorithm-- în special, când spun putem măsura un algoritm, am înseamnă putem măsura cât de multe resurse este nevoie de sus. Dacă aceste resurse sunt, cât de multe bytes de RAM-- sau MB de memorie RAM îl folosește. Sau cât de mult timp este nevoie pentru a rula. Și putem apela acest măsura, în mod arbitrar, f de n. Unde n este numărul de elemente în setul de date. Și f de n este cât de multe ceva de. Cât de multe unități de resurse nu nevoie de ea pentru a procesa aceste date. 

Acum, noi de fapt nu-mi pasă despre ceea ce f de n este exact. De fapt, am foarte rar will-- cu siguranță nu va fi niciodată în această I class-- se arunca cu capul în orice într-adevăr profund analiză a ceea ce f de n este. Noi doar vorbi despre ceea ce f de n este de aproximativ sau ceea ce tinde sa. Și tendința unui algoritm este dictate de termen sa cea mai mare comanda. Și putem vedea ceea ce am înseamnă că prin luarea de o privire la un exemplu mai concret. 

Deci, haideți să spunem că avem trei algoritmi diferite. Prima dintre care are n tocati, unele unități de resurse pentru a procesa un set de date de dimensiune n. Avem un al doilea algoritm care ia n tocata plus resurse n patrat pentru a procesa un set de date de dimensiune n. Și avem un al treilea algoritm care rulează in-- care preia n minus tocata 8N pătrat plus 20 de unități de resurse n pentru a procesa un algoritm cu un set de dimensiune n date. 

Acum, din nou, cu adevarat nu vom pentru a obține în acest nivel de detaliu. Sunt foarte Trebuie doar astea aici ca o ilustrare a unui punct că am de gând să fie face într-un al doilea, care este că ne pasă cu adevărat numai despre tendința de lucruri ca seturile de date devin mai mari. Deci, dacă setul de date este mic, nu e de fapt, o diferență destul de mare în aceste algoritmi. Al treilea Algoritmul acolo durează de 13 ori mai mult, De 13 ori cantitatea de resurse pentru a rula în raport cu primul. 

Dacă setul de date este dimensiunea noastră 10, care este mai mare, dar nu neapărat frumos, putem vedea că nu există de fapt, un pic de o diferenta. Al treilea Algoritmul devine mai eficientă. Este vorba despre de fapt 40% - sau 60% mai eficient. Este nevoie 40% cantitatea de timp. Se poate run-- poate dura 400 de unități de resurse pentru a procesa un set de date de dimensiune 10. Întrucât primele algoritm, prin contrast, ia 1.000 de unități de resurse pentru a procesa un set de date de dimensiune 10. Dar uite ce se întâmplă ca numerele noastre obține chiar mai mare. 

Acum, diferența între aceste algoritmi începe să devină un pic mai puțin evidente. Iar faptul că există inferior-comanda terms-- sau, mai degrabă, termeni cu exponents-- inferior începe să devină irelevante. În cazul în care un set de date este de mărime 1000 și primul algoritm ruleaza in un miliard de pași. Și al doilea algoritm rulează în un miliard și un milion de pași. Și a treia algoritmul rulează în doar timid de un miliard de pași. E destul de mult de un miliard de pași. Acești termeni de ordin inferior începe pentru a deveni cu adevărat lipsită de relevanță. Și într-adevăr la ciocan acasă point-- în cazul în care intrarea de date este de dimensiuni un million-- toate trei dintre acestea destul de mult ia una quintillion-- dacă matematica mea este la câțiva pași correct-- pentru a procesa o intrare de date de dimensiuni un milion. Asta-i o mulțime de pași. Iar faptul că unul dintre ei ar putea ia un cuplu de 100.000, sau un cuplu de 100 milioane mai puțin atunci când vorbim despre un număr că big-- e un fel de irelevant. Toate acestea au tendința de a lua aproximativ n tocata, și așa ne-ar referi de fapt la toate aceste algoritmi ca fiind de ordinul a n tocata sau mare-O din n tocata. 

Iată o listă a unora dintre mai mult clasele comune complexitate de calcul că vom întâlni în algoritmi, în general. Și, de asemenea, în mod special CS50. Acestea sunt comandate de la în general, cel mai rapid în partea de sus, să general mai lent în partea de jos. Deci, algoritmi de timp constant tind să fie cel mai rapid, indiferent de dimensiunea introducere de date treci la. Ei iau întotdeauna o singură operație sau o unitate de resurse pentru a face față. S-ar putea fi de 2, s-ar putea fie de 3, ar putea fi de 4. Dar e un număr constant. Aceasta nu variază. 

Algoritmi de timp logaritmice sunt ceva mai bine. Și un foarte bun exemplu de un algoritm de timp logaritmică le-ați văzut cu siguranță de acum este ruperea în afară de cartea de telefon pentru a găsi Mike Smith în cartea de telefon. Am tăiat problema în jumătate. Și așa cum n devine mai mare și mai mare și larger-- De fapt, de fiecare dată când dublu n, este nevoie de doar un pas. Așa că e mult mai bine decât, să spunem, timp liniar. Care este, dacă n dubla, aceasta ia un număr dublu de pași. Dacă vă tripla n, este nevoie de tripla numărul de pași. Un pas pe unitate. 

Apoi lucrurile devin un pic more-- mai puțin mare de acolo. Ai timp ritmic liniar, uneori numit timp liniar jurnal sau doar n log n. Și vom exemplu de un algoritm care ruleaza in n log n, care este mai bine decât pătrată time-- n pătrat. Sau timp polinomial, n două orice număr mai mare decât doi. Sau timp exponențială, care este chiar worse-- C n. Deci, un numar constant ridicat la puterea mărimii de intrare. Deci, dacă există 1,000-- dacă introducerea datelor este de mărime 1,000, ar fi nevoie de C la puterea 1000-lea. E mult mai rău decât timp polinomial. 

Timp factorial este chiar mai rău. Și, de fapt, acolo într-adevăr Există algoritmi timp infinit, cum ar fi, așa-numitele sort-- prost, acesta de locuri de muncă este de a amesteca aleator o serie și apoi verificați pentru a vedea fie că este vorba sortate. Și dacă nu e, la întâmplare shuffle nou matrice și verificați pentru a vedea dacă este sortate. Și, după cum puteți, probabil, imagine-- vă puteți imagina o situație în cazul în care, în cel mai rău caz, ceea ce va nu începe de fapt cu matrice. Că algoritmul ar fi pentru totdeauna. Și așa ar fi o algoritm de timp infinit. Sperăm că nu va fi scris orice moment factorial sau infinit algoritmi în CS50. 

Deci, să ia un pic mai mult uite la un simplu beton clase de complexitate de calcul. Deci, avem o example-- sau două exemple here-- algoritmilor timp constant, care întotdeauna o singură operațiune în cel mai rău caz. Deci, primul example-- avem o funcție chemat 4 pentru tine, care ia o serie de dimensiuni 1000. Dar apoi se pare că nu uita de fapt la it-- nu pasă cu adevărat ceea ce este interiorul ei, de care matrice. Întotdeauna doar întoarce patru. Deci, faptul că algoritmul, în ciuda faptului că aceasta ia 1.000 de elemente nu face nimic cu ei. Doar întoarce patru. Este întotdeauna un singur pas. 

De fapt, se adaugă 2 nums-- care am văzut înainte ca well-- doar procesele două numere întregi. Nu este un singur pas. Este de fapt un cuplu pași. Ai un, te b, ce le adăugați împreună, și voi ieșire rezultatele. Deci, este de 84 pași. Dar e mereu constant, indiferent de a sau b. Aveți pentru a obține un, pentru a primi b, se adaugă le împreună, de ieșire rezultatul. Așa că e un algoritm de timp constant. 

Iată un exemplu de algorithm-- timp liniar un algoritm care gets-- care are un pas suplimentar, eventual, ca intrare creste cu 1. Deci, să spunem că suntem în căutarea pentru numărul 5 interiorul unui tablou. S-ar putea avea o situație în care puteți găsi destul de devreme. Dar ai putea avea, de asemenea o situație în care ar putea fi ultimul element de matrice. Într-o serie de dimensiuni 5, în cazul în care căutăm numărul 5. Ar fi nevoie de 5 pași. Și, de fapt, imaginați-vă că nu există nu 5 oriunde în această matrice. Noi încă mai trebuie de fapt să se uite la fiecare singur element de matrice în scopul de a determina dacă este sau nu de 5 este acolo. 

Deci, în cel mai rău caz, care este faptul că elementul este ultimul în matrice sau nu există deloc. Noi încă mai trebuie să se uite la toate n elemente. Și așa acest algoritm se execută în timp liniar. Puteți confirma că, prin extrapolarea un pic, spunând: dacă am avut o serie de 6 elemente și am fost în căutarea pentru numărul 5, ar putea dura 6 pași. Dacă avem o gama de 7 element și căutăm numărul 5. Ar putea dura 7 trepte. Așa cum am mai adăuga un element nostru matrice, este nevoie de încă un pas. Asta e un algoritm liniar în cel mai rău caz. 

Cuplu întrebări rapide pentru tine. Care este runtime-- ceea ce este cel mai rău caz, runtime- din acest fragment special de cod? Deci, am o buclă de 4 aici care ruleaza de la J este egal cu 0, tot drumul pana la m. Și ceea ce văd aici, este faptul că corp din bucla se execută în timp constant. Deci, folosind terminologia care am vorbit deja about-- ce ar fi cel mai rău caz, execuție a acestui algoritm? Ia-o a doua. Partea interioară a buclei se execută în timp constant. Iar partea exterioară a bucla este de gând să ruleze ori m. Deci, ce este runtime cel mai rău caz aici? Ai ghicit mare-O de m? Ai avea dreptate. 

Ce zici de un altul? De data aceasta avem o buclă în interiorul unei bucle. Avem o buclă exterioară care ruleaza de la zero la p. Și avem o buclă interioară care ruleaza de la zero la p, și în interiorul acestuia Am afirmă că trupul buclă se execută în timp constant. Deci, ce este runtime mai rău caz din acest fragment special de cod? Ei bine, din nou, avem o buclă exterioară care ruleaza ori p. Și fiecare iterație time-- din bucla, mai degrabă. Avem o buclă interioară care ruleaza, de asemenea, ori p. Și apoi în interiorul că, nu e constantă fragment time-- puțin acolo. 

Deci, dacă avem o buclă exterioară care ruleaza p ori în interiorul căruia este o buclă interioară care ruleaza p times-- ceea ce este cel mai rău caz, runtime- de acest fragment de cod? Ai ghicit mare-O din p pătrat? 

Sunt Doug Lloyd. Acest lucru este CS50.