U redu, pa, računalna složenost. Samo malo upozorenje Prije nego što zaronite u previše far-- to vjerojatno će biti među Najviše math-teških stvari govorimo o u CS50. Nadam se da neće biti previše neodoljiv a mi ćemo pokušati vas kroz proces, ali Samo malo fer upozorenje. Tu je malo matematike koji su uključeni ovdje. U redu, tako da bi se napraviti korištenje naših računalnih resursa u stvarnom svijet-to je stvarno važno razumjeti algoritme i kako su obradu podataka. Ako smo doista učinkovit algoritam, mi može smanjiti količinu resursa imamo na raspolaganju kako bi se bavio s njom. Ako imamo algoritam koji će potrajati puno posla obraditi stvarno veliki skup podataka, to je će zahtijevati više i više sredstava, je novac, RAM, sve to vrsta stvari. 

Dakle, biti u mogućnosti analizirati Algoritam koristeći ovaj alat set, osnovi, pita question-- Kako ovo algoritam razmjera kao što smo baciti sve više i više podataka na njemu? U CS50, količinu podataka smo rad s prilično mala. Općenito, naši programi idu prikazivati ​​u drugi ili less-- Vjerojatno puno manje Posebno rano. 

Ali razmišljam o tvrtka koja se bavi sa stotinama milijuna kupaca. I oni moraju obraditi da kupac podataka. Kako je broj kupaca se imaju dobiva veći i veći, to će zahtijevati sve više i više resursa. Koliko više resursa? Pa, to ovisi o tome kako analiziramo algoritam, pomoću alata u ovom alata. Kada govorimo o složenosti algorithm-- koji Ponekad ćete čuti što se naziva vrijeme složenosti ili prostora složenost ali mi jednostavno ide nazvati complexity-- mi općenito govorimo o najgori scenarij. S obzirom na apsolutno najgore hrpa Podaci koje smo mogli biti bacanje na to, kako je to algoritam će obraditi ili se bave s tim podacima? Mi obično nazivamo najgorem slučaju Runtime algoritma big-O. Dakle, algoritam se može reći da izvoditi u O n ili O n na kvadrat. A više o tome što one znače u sekundi. 

Ponekad, međutim, mi njegu o najboljem scenariju. Ako podaci sve što smo htjeli da se i to je apsolutno savršena i bili smo slanje ovo savršena skup podataka putem našeg algoritma. Kako bi se nositi u toj situaciji? Ponekad se odnosi na to što je velika Omega, tako da je u suprotnosti s velikom-O, imamo veliku-Omega. Big-Omega za najboljem scenariju. Big-O za najgorem slučaju. Općenito, kada govorimo o složenost algoritma, govorimo o najgorem slučaju. Pa imajte to na umu. 

A u ovoj klasi, mi općenito ide napustiti strogu analizu stranu. Postoje znanosti i polja posvećen ove vrste stvari. Kada govorimo o zaključivanju kroz algoritme, što ćemo činiti dio-po-dio za mnoge Algoritmi govorimo o u klasi. Mi smo zapravo samo govori o razmišljanje kroz njega sa zdravim razumom, ne s formulama, ili dokaze, ili bilo što slično. Dakle, ne brinite, nećemo biti pretvara u velikom satu matematike. 

Zato sam rekao da je stalo složenosti jer postavlja pitanje, kako ne naši algoritmi nositi veći i veće setovi podataka koji se baca na njih. Pa, što je skup podataka? Što mislim kada sam rekao da je? To znači da sve što čini većinu smisla u kontekstu, da budem iskren. Ako imamo algoritam, na Procesi Strings-- smo vjerojatno govori o veličini niza. To su podaci set-- veličina, broj znakova koji čine niz. Ako govorimo o algoritam koji obrađuje datoteke, bismo mogli razgovarati o tome kako mnogi kilobajta sadrže tu datoteku. I to je skup podataka. Ako govorimo o algoritmu koje obrađuje polja općenito, kao što su sortiranje algoritama ili u potrazi algoritama, vjerojatno govorimo o broju elemenata koji čine niz. 

Sada, možemo mjeriti algorithm-- posebno, kad kažem možemo mjerenje algoritam, ja znači možemo mjeriti koliko mnogo resursa zauzima. Jesu li ti resursi su, koliko bajtova RAM-- ili megabajta RAM koristi. Ili koliko vremena je potrebno za pokretanje. I možemo zvati mjerenje, samovoljno, f n. Pri čemu je n broj elementi u skupu podataka. I f n je koliko somethings. Koliko jedinica resursa radi to zahtijevaju obraditi te podatke. 

Sada, mi zapravo nije briga što f n je točno. U stvari, mi smo vrlo rijetko will-- sigurno nikada neće u ovoj class-- I. zaroniti u bilo stvarno duboko Analiza ono f n. Samo ćemo razgovarati o tome što f nje otprilike i što je sklon. A tendencija algoritam je diktiraju najvišoj narudžbe pojam. I možemo vidjeti što sam znači po tome uzimajući Pogled na konkretniji primjer. 

Dakle, recimo da imamo tri različite algoritme. Od kojih je prvi uklanja n kubu, neke jedinice resursa obraditi skup podataka veličine n. Imamo drugi algoritam koji uzima n kubu plus n kvadratna resursi obraditi skup podataka veličine n. I mi smo treća algoritam koji radi in-- da zauzima n kubu minus 8N kvadrat plus 20 n jedinica resursa obraditi algoritam s podacima skupa veličine n. 

Sada opet, mi stvarno ne ide da se u ovoj razini detalja. Ja sam stvarno samo ove gore ovdje kao ilustracija točke da ću biti što u sekundi, što je da mi je samo stalo o tendencijom stvari kao setovi podataka dobiti veći. Dakle, ako skup podataka je mala, ima zapravo prilično velika razlika u tim algoritmima. Treći algoritam tamo traje 13 puta duže, 13 puta iznos sredstava za pokretanje u odnosu na prvi. 

Ako je naš skup podataka je veličina 10, koji je veća, ali ne nužno velika, možemo vidjeti da postoji zapravo malo razlika. Treći algoritam postaje učinkovitija. To je oko 40% zapravo - ili 60% učinkovitiji. Potrebno 40% u iznosu od vremena. To može run-- to može potrajati 400 jedinica resursa obraditi skup podataka veličine 10. A prvi Algoritam, za razliku od, Potrebno 1.000 jedinica resursa obraditi skup podataka veličine 10. Ali pogledajte što se događa dok naši brojevi dobili još veći. 

Sad, razlika između tih algoritama početi postati malo manje očiti. A činjenica da postoje nižeg reda terms-- odnosno, Pojmovi s nižim exponents-- početi postati irelevantna. Ako je skup podaci o veličini 1000 i prvi algoritam radi u milijardu koraka. I drugi algoritam radi u milijardu i milijun koraka. A treći algoritam radi u samo sramiti milijardu koraka. To je prilično puno milijardu koraka. Ti pojmovi nižeg reda početak postati doista nevažno. I samo da se stvarno čekić kući point-- ako su ulazni podaci o veličini a million-- sve tri od njih prilično uzeti jedan quintillion-- ako moja matematika correct-- koraka obraditi unos podataka veličine milijuna. To je mnogo koraka. A činjenica da je jedan od njih možda potrajati nekoliko 100,000 ili par 100 milijuna još manje kada govorimo o broju da big-- to je vrsta nevažno. Svi oni imaju tendenciju da se oko nje kubu, pa bismo se zapravo odnosi svim tim algoritama kao na red n kubu ili velika-O n kubu. 

Ovdje je popis nekih od više zajedničke računalne složenosti klasa da ćemo se susresti u algoritmi općenito. I također posebno u CS50. Oni su naručili od obično najbrži na vrhu, općenito najsporije na dnu. Dakle, konstantna vremena algoritmi često biti najbrži, bez obzira na veličine od unos podataka prođe u. Oni uvijek uzeti jednu operaciju ili jedna jedinica resursa da se bave. To bi moglo biti 2, to bi moglo biti 3, to bi moglo biti 4. No, to je konstantni broj. To se ne razlikuju. 

Logaritamska vrijeme algoritmi su nešto bolje. I stvarno dobar primjer logaritamska vrijeme algoritam sigurno ste vidjeli do sada je razdire od telefonskog imenika naći Mike Smith u telefonskom imeniku. Snizili smo problema na pola. I tako je n dobiva veći i veći i larger-- Zapravo, svaki put kada se udvostručiti nje, to traje samo još jedan korak. Dakle, to je puno bolje nego, recimo, linearno vrijeme. Koji je ako udvostručite nje, ona vodi dvostruki broj koraka. Ako utrostručiti nje, to traje utrostručiti broj koraka. Jedan korak po jedinici. 

Tada se stvari malo more-- malo manje sjajno od tamo. Imate linearno ritmičke vremena, ponekad zove dnevnik linearno vrijeme ili samo n prijavite n. A mi ćemo kao primjer algoritma koji radi u n log n, što je još bolje od kvadratnog time-- n na kvadrat. Ili polinom vrijeme, n dva bilo koji broj veći od dva. Ili eksponencijalna vrijeme, koje još worse-- C u n. Tako su neki konstantni broj povećan na moć veličine ulaza. Dakle, ako postoji 1,000-- ako mu je ulazni podaci veličine 1000, to bi se C do 1,000th vlast. To je puno gore nego polinomnom vrijeme. 

Faktorijalni vrijeme je još gore. A u stvari, ima zaista Postoje beskonačni put algoritama, kao što je tzv glupo sort-- čija posao je slučajno shuffle niz a zatim provjerite je li je li to riješeno. A ako to nije, slučajno opet vrpoljiti niz i provjerite da li je to riješeno. I kao što vjerojatno možete imagine-- možete zamisliti situaciju gdje je u najgorem slučaju, da će Nikad zapravo početi s nizom. To algoritam će se izvoditi zauvijek. A kako bi bilo beskonačan put algoritam. Nadam se da se neće pisati bilo faktorijalni ili beskonačan vrijeme Algoritmi u CS50. 

Dakle, neka je uzeti malo više beton pogled na neke jednostavnije računske složenosti klasa. Dakle, imamo example-- ili dva primjera here-- stalnih vremenskih algoritama, koji uvijek uzeti jedan rad u najgorem slučaju. Dakle, prvi example-- imamo funkciju pozvao 4 za vas, koji traje niz veličine 1.000. Ali onda očito ne zapravo izgleda na it-- zapravo ne briga što je unutar nje, te niz. Uvijek samo vraća četiri. Dakle, da je algoritam, unatoč činjenici da se Potrebno 1.000 elemenata ne ništa s njima. Samo vraća četiri. To je uvijek jedan korak. 

U stvari, dodati 2 nums-- koji smo vidjeli kako je well-- Samo obrađuje dva prirodna broja. To nije jedan korak. To je zapravo par koraka. Možete dobiti, dobivate B, možete ih dodati zajedno, a vi izlazni rezultati. Tako da je 84 koraka. Ali to je uvijek konstantna, Bez obzira na, ili b. Morate dobiti, dobiti b, dodajte ih zajedno, izlazni rezultat. Dakle, to je konstanta vrijeme algoritam. 

Evo primjera od a linearno vrijeme algorithm-- algoritam koji gets-- da traje jedan dodatni korak, eventualno, kao svoj ulaz raste za 1. Dakle, recimo da smo u potrazi za broj 5 unutar niza. Možda ćete imati situaciju u kojoj možete smatraju da je prilično rano. Ali, također mogu imati situacija u kojoj je možda posljednji element niza. U nizu veličine 5, ako mi smo u potrazi za broj 5. Bilo bi 5 koraka. A u stvari, zamislite da postoji Nije 5 bilo gdje u tom nizu. Još uvijek zapravo pogledati svaki element polja kako bi se utvrdilo da li ili ne 5 je tu. 

Dakle, u najgorem slučaju, što je to element je posljednja u nizu ili ne postoji uopće. Mi i dalje morati gledati na sve n elemenata. I tako ovaj algoritam radi u linearnom vremenu. Možete potvrditi da je ekstrapoliranja malo govoreći, ako smo imali 6-element matrice A i bili smo u potrazi za broj 5, to bi moglo potrajati 6 koraka. Ako imamo 7-element matrice A i mi smo u potrazi za broj 5. To bi moglo potrajati 7 koraka. Kao što smo dodali još jedan element na naš polje, potrebno je još jedan korak. To je linearni algoritam u najgorem slučaju. 

Par brzih pitanja za vas. Što je runtime-- što je najgorem slučaju izvođenja ovog posebnog isječak koda? Dakle, imam 4 petlje ovdje koji radi od j = 0, pa sve do m. A ono što sam vidio ovdje, je da je Tijelo petlje radi u stalnom vremenu. Dakle, koristite terminologiju koja već smo razgovarali about-- što bi bio najgori slučaj Runtime ovog algoritma? Uzmite trenutak. Unutarnji dio petlje radi u stalnom vremenu. A vanjski dio od Petlja će se izvoditi m puta. Dakle, što je najgori slučaj runtime ovdje? Jeste li pogoditi veliki-o m? Ti bi biti u pravu. 

Kako o drugom? Ovaj put imamo petlje unutar petlje. Imamo vanjski petlju koji traje od nula do str. I mi imamo unutarnji petlju koja teče od nule do p, a unutar toga, Tvrdim da je tijelo petlje radi u stalnom vremenu. Dakle, što je najgori slučaj izvođenja ovog posebnog isječak koda? Pa, opet, imamo Vanjska petlja koja teče str puta. I svaki time-- iteracija tog procesa, a. Imamo unutarnju petlju koje također vodi p puta. I onda unutar toga, tu je i stalna time-- mali isječak postoji. 

Dakle, ako imamo vanjski petlje da radi se p puta unutar kojih je unutarnja petlja koja radi p times-- ono što je najgorem slučaju izvođenja ove isječak koda? Jeste li pogoditi velika O p kvadrat? 

Ja sam Doug Lloyd. Ovo je CS50.