Gerai, taip, skaičiavimo sudėtingumas. Tiesiog įspėjimas tiek kol mes pasinerti per far-- tai tikriausiai bus tarp Labiausiai matematikos sunkiųjų dalykai mes kalbame apie į CS50. Tikimės, kad tai nebus per didele ir mes pasistengsime ir padės jums per procesą, bet tik iš sąžiningai perspėta tiek. Yra šiek tiek matematikos dalyvauja čia. Visos teisės, todėl, siekiant, kad naudojimas mūsų skaičiavimo išteklių realiame world-- tai tikrai Svarbu suprasti algoritmai ir kaip jie apdoroti duomenis. Jei mes turime tikrai efektyvus algoritmas, mes gali sumažinti išteklių suma mes turime rasti kovoti su ja. Jei mes turime algoritmą, kuris ketina imtis daug darbo apdoroti tikrai didelis duomenų rinkinys, tai ketina reikalauti daugiau ir daugiau išteklių, kurie yra pinigai, RAM, visa tai stuff natūra. 

Taigi, kad galėtų panagrinėti algoritmas naudojant šią priemonę rinkinį, iš esmės, prašo question-- Kaip tai algoritmas skalę kaip mes išmetame daugiau ir daugiau duomenų iš jo? Be CS50, duomenų kiekį mes dirba su gana maža. Apskritai, mūsų programos vyksta paleisti antrą ar less-- tikriausiai daug mažiau ypač anksti. 

Bet pagalvokite apie kompanija, kuri užsiima su šimtais milijonų klientų. Ir jiems reikia apdoroti kad klientų duomenų. Kaip klientų skaičiaus jie turi gauna didesni ir didesni, jis ketina reikalauti vis daugiau ir daugiau išteklių. Kiek daugiau išteklių? Na, tai priklauso nuo to, kaip mes analizuoti algoritmus, naudojant įrankius šiame rinkinį. Kai kalbame apie sudėtingumo algorithm-- kurie kartais jums išgirsti tai vadinama metu sudėtingumas ar kosmoso sudėtingumas bet mes tik ketina skambinti complexity-- mes paprastai kalbame apie blogiausias scenarijus. Kadangi absoliutus blogiausias krūva duomenų, kad galėtume būti mesti į jį, kaip tai algoritmas ketina apdoroti arba kovoti su tais duomenimis? Mes paprastai vadiname blogiausio atvejo Trukmė algoritmą Big-O. Taigi algoritmas gali būti sakė paleisti O N arba O n kvadratu. Ir daugiau apie tai, ką tie reiškia per sekundę. 

Kartais, nors mes darome priežiūros apie geriausią scenarijų. Jeigu duomenys yra viskas, ką norėjau ji būtų, ir tai buvo visiškai tobula ir mes siunčiant tai puikus nustatyti duomenų per mūsų algoritmas. Kaip tai dirbti tokioje situacijoje? Mes kartais skaitykite, kad didelis omega, todėl priešingai Big-O, mes turime didelis Omega. Big-omega už geriausią scenarijų. Big-O už blogiausią scenarijų. Paprastai, kai mes kalbame apie algoritmą sudėtingumą, mes kalbame apie blogiausio atvejo scenarijus. Taigi keep that in mind. 

Ir šioje klasėje, mes paprastai vyksta palikti griežtą analizę nuošalyje. Yra mokslai ir laukai Orientacinis šios stuff natūra. Kai kalbame apie samprotavimo per algoritmų, kuri mes padarysime gabalas po gabalo, nes daugelis algoritmai mes kalbame apie klasėje. Mes tikrai tik kalbame apie aiškinosi per jį su sveiku protu, ne formules, arba įrodymų, ar kas nors panašaus. Taigi nesijaudinkite, mes negali būti virsta dideliu matematikos klasės. 

Taigi sakiau, mes rūpinamės sudėtingumo nes ji klausia, kaip darome algoritmai tvarkyti didesnis ir didesni duomenų rinkiniai buvo išmesti į juos. Na, kas yra duomenų rinkinys? Ką aš turiu galvoje, kai sakiau, kad? Tai reiškia, ką daro pats jausmas kontekste, turi būti sąžiningas. Jei mes turime algoritmą, kad Procesai Strings-- mes tikriausiai kalbame apie eilutę dydžio. Štai duomenys set-- dydis, numeris, simbolių, kurie sudaro eilutę. Jei mes kalbame apie algoritmas, kuris apdoroja failus, mes galime kalbėti apie tai, kaip daug kilobaitų sudaro tą failą. Ir tai duomenų rinkinys. Jei mes kalbame apie algoritmą kad rankenos masyvus apskritai, pvz rūšiavimo algoritmai ar ieškoti algoritmus, mes tikriausiai kalbame apie skaičius elementų, sudarančių masyvo. 

Dabar mes galime išmatuoti algorithm-- ypač kai aš sakau, mes galime matuoti algoritmą, aš reiškia, kad mes galime įvertinti, kaip daug išteklių ji užima. Nesvarbu, ar tie ištekliai, kiek baitų RAM-- ar megabaitų RAM ji naudoja. Arba, kiek laiko užtrunka paleisti. Ir mes galime tai vadiname matuoti, savavališkai, f n. Kur n yra skaičius elementai duomenų rinkinį. Ir f n yra kiek septyniasdešimties. Kiek resursų vienetų daro ji reikalauja, kad procesas, duomenis. 

Dabar mes iš tikrųjų nerūpi apie tai, ką f n yra tiksliai. Tiesą sakant, mes labai retai will-- tikrai niekada šiame class-- I pasinerti į bet tikrai giliai analizė, ką f n yra. Užtenka tik ketiname kalbėti apie tai, ką f n yra maždaug ar ką jis linkęs. Ir algoritmą tendencija diktuoja savo aukščiausią užsakymo laikotarpiu. Ir mes galime pamatyti, ką aš reiškia, kad atsižvelgiant pažvelgti labiau konkretus pavyzdys. 

Taigi tarkime, kad mes turime trys skirtingi algoritmai. Iš kurių pirmasis trunka n kubeliais, kai išteklių vienetai apdoroti duomenis rinkinį dydžio n. Mes turime antrą algoritmą, kuris turėjo N kubeliais plius n kvadrato ištekliai apdoroti duomenis rinkinį dydžio n. Ir mes turime trečioji algoritmas, kuris veikia in-- kad užima n kubeliais atėmus 8N kvadrato plius 20 N resursų vienetų apdoroti algoritmą su rinkiniu dydžio n duomenis. 

Dabar vėl, mes tikrai neketiname patekti į šį detalumo lygiu. Aš tikrai tereikia juos iki čia kaip taško iliustracijoje kad aš ruošiuosi būti priėmimo per sekundę, kuris yra tai, kad mes tik tikrai rūpi apie dalykus tendencija kaip duomenų rinkinių gauti didesnį. Taigi, jei duomenų rinkinys yra mažas, ten iš tikrųjų gana didelis skirtumas Šiose algoritmo. Trečiasis algoritmas yra trunka 13 kartų ilgiau, 13 kartų išteklių suma paleisti, lyginant su pirmojo. 

Jei mūsų duomenų rinkinys yra 10 dydžio, kuris yra didesnis, bet nebūtinai didžiulis, matome, kad ten faktiškai skirtumo tiek. Trečiasis algoritmas tampa efektyvesnis. Tai apie faktiškai 40% - arba 60% efektyvesnis. Tai užtrunka 40%, kiek laiko. Jis gali run-- tai gali užtrukti 400 resursų vienetų apdoroti duomenis rinkinį 10 dydžio. Kadangi pirmasis algoritmas, priešingai, užima 1000 resursų vienetų apdoroti duomenis rinkinį 10 dydžio. Bet pažiūrėkite, kas atsitinka, kaip Mūsų numeriai gauti dar didesni. 

Dabar, skirtumas tarp šių algoritmo pradėti tapti šiek tiek mažiau akivaizdus. Ir tai, kad yra žemesnės eilės terms-- arba, tiksliau, terminai su mažesne exponents-- pradėti tapo nereikšmingi. Jeigu duomenų rinkinys yra dydžio 1000 ir pirmasis algoritmas veikia milijardą žingsnius. Ir antra algoritmas veikia milijardas ir milijonas žingsniai. Ir trečia algoritmas veikia į tiesiog drovus milijardą žingsnius. Tai gana daug milijardų žingsnių. Tos mažesnės pavedimo sąlygas pradėti tapti tikrai nesvarbus. Ir tik tikrai kartojami point-- jei duomenų įvesties yra Dydis A million-- visi šie trys gana daug išgerkite vieną quintillion-- jei mano matematika yra correct-- žingsniai apdoroti įvesties duomenų dydžio milijono. Štai keletas žingsnių daug. Ir faktas, kad vienas iš jų gali per porą 100.000 ar pora 100 milijonų net mažiau, kai mes kalbame apie skaičius kad big-- tai tipo nesvarbus. Jie visi linkę imtis maždaug n kubeliais, ir todėl mes iš tikrųjų kreiptis visų šių algoritmo kaip ant n tam kubeliais arba didelis O n cubed. 

Štai keletas iš daugiau Sąrašas bendrieji skaičiavimo sudėtingumas klasės kad mes susiduriame algoritmai, dažniausiai. Ir taip pat konkrečiai CS50. Tai yra užsakomi iš paprastai greičiausiai viršuje, apskritai lėčiausiai apačioje. Taigi nuolatinis laiko algoritmai linkę greičiausias, nepriklausomai nuo dydžio duomenų įvedimo pereisite į. Jie visada vieną operaciją ar vienas vienetas išteklių spręsti. Tai gali būti 2, tai gali būti 3, tai gali būti 4. Bet tai pastovus skaičius. Ji neturi skirtis. 

Logaritminė laiko algoritmai yra šiek tiek geriau. Ir tikrai geras pavyzdys logaritminis laikas algoritmas Jūs tikrai pamatėte dabar yra Patempimai iš telefonų knygos rasti Mike Smith telefonų knygoje. Pjauname problemą per pusę. Ir taip n gauna didesni ir didesni ir larger-- Tiesą sakant, kiekvieną kartą jums dvigubai n, tai trunka tik dar vieną žingsnį. Taigi, kad daug geriau nei, tarkim, linijinis laikas. Kuris yra, jei jūs dvigubai n, tai trunka dvigubai žingsnių skaičių. Jei trigubai N, ji užima patrigubės žingsnių skaičių. Vienas žingsnis vienetui. 

Tada viskas pasidaro šiek tiek more-- šiek tiek mažiau puikus iš ten. Turite linijinis ritmišką laiką, kartais vadinamas žurnalas linijinis laikas arba tiesiog n log n. Ir mes pavyzdį algoritmą, kad eina n log n, kuris yra dar geriau nei kvadratinė LAIKĄ_ n kvadratu. Arba daugianario laikas, N du bet koks skaičius didesnis negu du. Arba eksponentinis laikas, kuris net worse-- C n. Taigi kai pastovus skaičius padidintas iki iš įvesties dydžio jėga. Taigi, jei ten 1,000-- jei duomenų įvedimas yra dydis 1,000, tai užtruktų C į 1,000th galia. Tai daug blogiau nei polinomo metu. 

Faktorinė laikas yra dar blogiau. Ir iš tiesų, ten tikrai egzistuoja begalinis laiko algoritmai, pvz, vadinamasis kvaila sort-- kurio darbas yra atsitiktinai shuffle masyvą ir tada patikrinkite, ar tai rūšiuojamos. Ir jei taip nėra, atsitiktinai shuffle masyvo vėl ir patikrinkite, ar jis rūšiuojami. Ir kaip jūs galite galbūt imagine-- galite įsivaizduoti situaciją kur blogiausiu atveju, kad valia niekada iš tikrųjų pradėti su masyvo. Tai algoritmas būtų paleisti amžinai. Ir taip, kad būtų begalinis laikas algoritmas. Tikimės, kad jums nebus raštu bet faktorialas arba begalinis laikas algoritmai CS50. 

Taigi, galime imtis šiek tiek daugiau betono pažvelgti į kai paprastesnis skaičiavimo sudėtingumas klasės. Taigi, mes turime example-- arba du pavyzdžiai here-- pastovaus laiko algoritmai, kuri visada viena operacija blogiausiu atveju. Taigi pirmą example-- turime funkciją vadinamas 4 už jus, kurie trunka dydis 1,000 masyvo. Bet tada matyt iš tikrųjų nėra surasti ne it-- tikrai ne rūpintis, kas viduje ji, tos masyvo. Visada tik grįžta keturi. Taigi, tai algoritmas, Nepaisant to, kad jį užima 1000 elementus nėra nieko su jais daryti. Tiesiog grįžta keturi. Jis visada vienas žingsnis. 

Tiesą sakant, pridėti 2 nums-- kuris mes matėme prieš pat well-- tik perdirba du sveikieji skaičiai. Tai ne vienas žingsnis. Tai tikrai pora žingsnių. Gauni, gausite B, pridėsite juos kartu, ir jūs išvesties rezultatus. Taigi, tai 84 žingsnių. Bet ji visada pastovus, nepriklausomai nuo to, A arba B. Turite gauti, gauti B, įlašinama juos kartu, išvesties rezultatas. Taigi, kad pastovus laikas algoritmas. 

Štai Kurių pavyzdys linijinis laikas algorithm-- algoritmas, kuris gets--, kad mano vienas papildomas etapas, galbūt, kaip jūsų indėlis auga 1 d. Taigi, tarkime, mes ieškome numeris 5 viduje masyvą. Jūs galite turėti padėtį, kai Jūs galite rasti jį gana anksti. Bet jūs taip pat gali turėti situacija, kai ją gali būti paskutinis elementas masyvo. Be dydžio 5 masyvas, jei mes ieškome skaičius 5. Tai būtų 5 žingsnius. Ir iš tiesų, įsivaizduokite, kad ten ne 5 bet šiame masyve. Mes vis dar realiai pažvelgti į kiekvienas elementas masyve siekiant nustatyti, ar 5 yra. 

Taigi blogiausiu atveju, kuri yra tai, kad elementas yra paskutinis masyvo arba neegzistuoja ne visiems. Mes vis dar turime pažvelgti į visi n elementų. Ir todėl šis algoritmas veikia linijinio laiko. Jūs galite patvirtinti, kad ekstrapoliuojant truputį, sakydamas, jei mes turėjome 6 elementų masyvą ir Mes ieškojome skaičiumi 5, tai gali užtrukti 6 žingsnius. Jei mes turime 7-elementų masyvas ir mes ieškome skaičius 5. Tai gali užtrukti 7 veiksmus. Kaip mes pridėti dar vieną elementą į mūsų masyvas, ji užima dar vieną žingsnį. Štai linijinis algoritmas blogiausiu atveju-. 

Pora greitai klausimai jums. Koks runtime-- kas blogiausiu atveju Runtime būtent šio kodo fragmentą? Taigi turiu 4 kilpa čia, kad veikia iš j yra lygus 0, visą kelią iki m. Ir ką aš matau čia yra tas, kad kūno kilpos veikia pastoviu laiku. Taigi, naudojant terminologijos, mes jau kalbėjome about-- ką būtų pats blogiausias atvejis Trukmė šio algoritmo? Paimkite sekundę. Vidinis dalis kilpą veikia nuolat laiko. Ir išorinė dalis iš kilpa ketina paleisti m kartus. Taigi, kas yra blogiausio atvejo Runtime čia? Ar galite atspėti, BIG-O m? Jūs norite būti teisus. 

Kaip apie vienas kitą? Šį kartą mes turime kilpa viduje kilpa. Mes turime išorinį kontūrą , kuri veikia nuo nulio iki p. Ir mes turime vidinį kontūrą, kuris veikia nuo nulio iki p, ir viduje, kad, Aš pareiškiu, kad įstaiga kilpa veikia nuolat laiko. Taigi, kas yra blogiausio atvejo Runtime būtent šio kodo fragmentą? Na, vėlgi, mes turime išorinis kontūras, kuris veikia p kartus. Ir kiekvienas LAIKĄ_ iteracijos tos kilpos, o. Mes turime vidinį kontūrą kad taip pat veikia p kartus. Ir tada viduje, kad ten-aisiais pastovus LAIKĄ_ mažai fragmentą ten. 

Taigi, jei mes turime išorinis kontūras, kad veikia p kartus viduje, kuri yra vidinis kilpa, kad veikia p times-- kas blogiausiu atveju Runtime Šio kodo fragmentą? Ar galite atspėti, didelis O p kvadrato? 

AÅ¡ Doug Lloyd. Tai CS50.