Olgu, nii, arvutuslik keerukus. Veidi hoiatuse enne kui me sukelduda liiga far-- see ilmselt seas Kõige matemaatika-rasked asjad me räägime in CS50. Loodetavasti see ei tohi olla liiga suur ja püüame ja juhendab teid protsessi kaudu, kuid lihtsalt natuke õiglane hoiatus. Seal on natuke matemaatika seotud siin. Olgu, nii et muuta kasutada meie arvutiressursse reaalses world-- see on tõesti oluline mõista, algoritmid ja kuidas nad andmeid töödelda. Kui meil on tõesti tõhus algoritm, me võib vähendada ressursside hulga meil saadaval, et sellega tegeleda. Kui meil on algoritm, mis see aega võtab palju tööd töödelda tõesti suure hulga andmeid, siis on läheb vaja rohkem ja rohkem ressursse, mis on raha, RAM, kõik muu selline. 

Niisiis, olles võimeline analüüsima algoritmi kasutades seda tööriista komplekti, Põhimõtteliselt palub question-- Kuidas see algoritm skaala kui me visata rohkem ja rohkem andmeid ta? In CS50 kogus andmeid me oleme töötades on üsna väike. Üldiselt meie programmid lähevad sõidetud teise või less-- ilmselt palju vähem eriti varakult. 

Aga mõtle ettevõte, mis tegeleb sadu miljoneid kliente. Ja neil on vaja töödelda et kliendi andmed. Nagu mitmed kliendid nad on muutub suuremaks ja suuremaks, see läheb vaja rohkem ja rohkem ressursse. Mitu rohkem ressursse? Noh, see sõltub sellest, kuidas Analüüsides algoritm, kasutades vahendeid selle tööriistakasti. Kui me räägime keerukust algorithm-- mis mõnikord saate kuule seda nimetatakse aega keerukuse või ruumi keerukus aga me lihtsalt läheb helistada complexity-- me tavaliselt räägime halvima stsenaariumi. Arvestades absoluutne halvim kuhja andmed, et saaksime viskamine seda, kuidas see algoritm läheb töödelda või tegeleda, et andmed? Me üldiselt helistada halvima Runtime algoritmi big-O. Nii algoritm võib öelda, et sõidetud O n või O n ruudus. Ja veel sellest, mis need tähendavad teine. 

Mõnikord, kuigi me hoolime umbes parimal juhul. Kui andmed on kõik, mida me tahtsime seda ja see oli täiusliku ja me saadame selle täiuslik andmekogum meie algoritm. Kuidas see hakkama selles olukorras? Me mõnikord räägivad, et kui big-Omega, nii erinevalt big-O, meil big-Omega. Big-Omega parima stsenaariumi. Big-O jaoks halvima stsenaariumi. Üldiselt, kui me räägime keerukust algoritmi, me räägime Halvimal juhul. Nii et hoidke seda silmas pidades. 

Ja selles klassis, me tavaliselt läheb lahkuda põhjalik analüüs kõrvale. On teadused ja väljad pühendatud sellist kraami. Kui me räägime põhjendusi läbi algoritmide mis me teeme tükk-by-piece palju algoritme me räägime klassis. Me tõesti räägi põhjendades seda läbi terve mõistus, mitte valemeid, või tõendid, või midagi sellist. Nii et ärge muretsege, me ei ole muutumas suur matemaatika klassi. 

Ma ütlesin me hoolime keerukus sest see esitab küsimuse, kuidas ei meie algoritmid hakkama suuremate ja suurem andmekogud visatakse neid. Noh, mis on andmete kogum? Mida ma mõtlen, kui ma ütlesin, et? See tähendab iganes teeb kõige mõtet kontekstis, kui aus olla. Kui meil algoritm Protsessid Strings-- me ilmselt Rääkides suurus string. See on andmeid set-- suurus, arv märke, mis moodustavad string. Kui me räägime algoritm, mis töötleb faile, me võiks rääkida, kuidas palju kilobaiti koosnevad et fail. Ja see andmete hulk. Kui me räägime algoritmi mis tegeleb massiivid üldisemalt näiteks sorteerimine algoritme või otsides algoritme, me ilmselt räägime number elemente, mis sisaldavad hulgaliselt. 

Nüüd saame mõõtmisel algorithm-- eelkõige kui ma ütlen, saame mõõta algoritmi, ma keskmine saame mõõta, kui palju ressursse kulub. Kas need ressursid on, kui palju baiti RAM-- või MB RAM ta kasutab. Või kui palju aega kulub, et käivitada. Ja me nimetame seda mõõta, omavoliliselt, f n. Kui n on arv elemendid andmekogumi. Ja f n on mitu midagid. Mitu ühikut ressursse ei see nõuab töödelda, et andmeid. 

Nüüd, me tegelikult ei hooli mida f n on täpselt. Tegelikult me ​​väga harva will-- Kindlasti ei kasuta kunagi selles class-- ma sukelduda ühtegi tõeliselt sügav analüüsi, mida f n on. Me lihtsalt ei kavatse rääkida, milline f n on umbes või mis see kipub. Ja tendents algoritm on määrab selle kõrgeima järjekorras perspektiivis. Ja me saame aru, mida ma mõtlen, et võttes pilk rohkem konkreetse näite. 

Ütleme, et meil on kolmes erinevas algoritme. Esimene mis võtab n kuubis, mõned üksused ressursside töödelda andmeid komplekt suurus n. Meil on teise algoritmi, mis leiab n kuubis pluss n ruudus ressursid töödelda andmeid komplekt suurus n. Ja meil on kolmanda algoritm, mis töötab in-- et võtab n kuubis miinus 8n ruuduline pluss 20 n ühikut ressursse töödelda algoritmi andmekogumi mõõtmetega n. 

Nüüd jälle, me tõesti ei kavatse sattuda detailsuse tase. Ma tõesti lihtsalt need üles siin näitena punkti et ma lähen tegemist teise, mis on see, et me ainult tõesti hoolivad umbes kalduvus asju kui andmekogud saada suurem. Nii, kui andmekogum on väike, ei tegelikult päris suur erinevus Nende algoritme. Kolmas algoritm seal võtab 13 korda pikem, 13 korda rohkem ressursse joosta võrreldes esimesega. 

Kui meie andmed ei size 10, mis on suurem, kuid mitte tingimata suur, näeme, et seal on tegelikult natuke erinev. Kolmas algoritm muutub tõhusamaks. See on umbes tegelikult 40% - või 60% tõhusam. See võtab 40%, kui palju aega. See võib run-- see võib võtta 400 ühikut ressursse töödelda andmeid komplekt suurus 10. Kui esimene algoritmi, seevastu võtab 1000 ühikut ressursse töödelda andmeid komplekt suurus 10. Aga vaata, mis juhtub, kui Meie numbrid saada isegi suurem. 

Nüüd, vahe vahel nende algoritmide puhul hakkavad veidi vähem ilmne. Ja asjaolu, et seal on madalama et terms-- või mitte, poolest madalama exponents-- alustab olla tõsiseltvõetav. Kui andmed ei suurusega 1000 ja esimene algoritmi jookseb miljardit samme. Ja teine ​​algoritm töötab miljardi ja miljoni samme. Ja kolmas algoritm töötab vaid häbelik miljardi samme. See on päris palju miljardit samme. Need madalama järku alustada saada tõesti ebaoluline. Ja just tõesti haamer koju point-- Kui sisestatud andmed on Suurus A million-- kõik need kolm päris palju võta üks quintillion-- kui minu matemaatika on correct-- samme töödelda andmeid sisestada suurus miljon. See on palju samme. Ja asjaolu, et üks neist võivad võtta paar 100.000 või paar 100 miljonit isegi vähem kui me räägime number et big-- see on selline ebaoluline. Nad kõik kipuvad võtma umbes n kuubis, ja nii me tegelikult viidata Kõigi nende algoritmide nagu oleks tellimusel n kuubis või big-O n kuubis. 

Siin on nimekiri mõned rohkem ühise arvutuslik keerukus klassi et me kohata algoritme, üldiselt. Ja ka konkreetselt CS50. Need tellitakse üldiselt kiiremini tipus, üldiselt aeglasem allosas. Nii konstantset aega algoritme kipuvad kiireim, sõltumata suuruse kohta andmesisestuse sa läbima. Nad alati üks operatsioon või üks ühik ressursse tegeleda. See võib olla 2, see võib olla 3, siis võib olla 4. Aga see on pidev number. See ei muutu. 

Logarithmic aega algoritme on veidi parem. Ja tõesti hea näide logaritmiline algoritm olete kindlasti näinud nüüd on rebides telefoniraamatust leida Mike Smith telefoniraamatus. Me lõigatud probleemi poole. Ja nii nagu n muutub suuremaks ja suuremate ja larger-- Tegelikult iga kord, kui kahekordistada n, see võtab vaid üks samm. Nii et see on palju parem kui näiteks lineaarset aega. Milline on siis, kui sa topelt n, siis võtab kaks korda rohkem samme. Kui te kolmekordistub n, mis kulub kolmekordistab mitmeid samme. Üks samm ühiku kohta. 

Siis asjad natuke more-- Veidi vähem suuri sealt. Sul on lineaarne rütmiline aega, mõnikord nimetatakse Logi lineaarne ajal või lihtsalt n log n. Ja me näide algoritmi, mis jookseb n log n, mis on ikka parem kui quadratic AEG_ n ruudus. Või polünomiaalset, n kaks suvaline arv suurem kui kaks. Või eksponentsiaalne aeg, mis on isegi worse-- C kuni n. Nii mõned pidev arv tõuseb võimu suurusest sisend. Nii et kui seal on 1,000-- kui andmesisestuse on suurus 1000, see võtaks C kuni 1000. võim. See on palju hullem kui polünomiaalset. 

Factorial aega on veel hullem. Ja tegelikult, seal tõesti olemas lõpmatu aeg algoritme, nagu nn loll sort-- kelle töö on juhuslikult shuffle massiivi ja siis vaadata, kas see on järjestatud. Ja kui see ei ole juhuslikult shuffle massiiv uuesti ja vaadake, kas see on järjestatud. Ja kui saab ilmselt imagine-- võite ette kujutada olukorda kus halvima, mis tegelikult kunagi alustada massiivi. See algoritm läheks igaveseks. Ja nii, et oleks lõpmatu aeg algoritm. Loodetavasti sa ei saa kirjutada mis tahes faktoriaali või lõpmatu aeg algoritme CS50. 

Niisiis, võtame natuke rohkem betooni mõningaid lihtsamaid arvutuslik keerukus klassid. Nii on meil example-- või kaks näidet siin-- Pideva aja algoritme, mis alati ühe operatsiooni halvima. Nii et esimene example-- meil on funktsioon nimetatakse 4 teid, mis võtab massiivi suurus 1000. Aga siis ilmselt tegelikult ei vaata kell see-- ei huvita, mida on sees on, selle massiivi. Alati lihtsalt tagasi neli. Nii, et algoritm, vaatamata asjaolule, et see võtab 1,000 elemendid ei midagi teha nendega. Just naaseb neli. See on alati ühe sammu. 

Tegelikult lisada 2 nums-- mis oleme näinud nii well-- lihtsalt töötleb kaks täisarvu. See ei ole ühe sammu. See on tegelikult paar sammu. Sa saad, saad b, kui lisate neid koos, ja sa väljund tulemusi. Nii et see on 84 astet. Aga see on alati konstantne, sõltumata a või b. Sa pead saada, saada b, lisada need kokku, saadab tulemuse. Nii et pidev algoritm. 

Siin on näide lineaarne aeg algorithm-- algoritmi, mis gets-- mis võtab täiendav aste võimalusel oma panus kasvab 1.. Niisiis, oletame, et me otsime arvu 5 sees massiivi. Sul võib olla olukord, kus leiad selle üsna varakult. Aga sa võid ka olukorrast, kus ta võib olla viimane element massiivi. In massiivi suurus 5, kui me otsime arv 5. See võtaks 5 sammu. Ja tegelikult ette kujutada, et seal on ei 5 kõikjal selle massiivi. Meil on ikka tegelikult on vaadata iga element massiivi et teha kindlaks kas 5 on olemas. 

Nii et halvimal juhul, mis on selle element on viimase massiivi või ei ole üldse. Meil on veel vaadata kõik n elemente. Ja nii see algoritm jookseb lineaarne aeg. Võite kinnitada, et ekstrapoleerimise natuke juurde, kui meil oleks 6-element massiivi ja otsisime arv 5, see võib võtta 6 samme. Kui meil on 7-element massiivi ja me otsime arv 5. See võib võtta 7 astet. Nagu me lisada veel üks element meie massiiv, mis kulub ühe sammu. See on lineaarne algoritm aasta halvima. 

Paar kiiret küsimust sinu jaoks. Mis runtime-- mis on halvima runtime Selle konkreetse koodilõige? Nii et mul on 4 loop siin, mis töötab alates j võrdub 0, kõik viis kuni m. Ja mida ma näen siin, on see, et keha silmus jookseb pidevalt aega. Nii kasutades terminoloogiat me oleme juba rääkinud about-- mida oleks halvima Runtime selle algoritmi? Võtke teine. Sisemine osa loop töötab pidevas aega. Ja välisosas loop läheb jooksma m korda. Mis siis halvima runtime siin? Kas sa vist suur-O m? Sa oleks õige. 

Kuidas teine? Seekord on meil loop sees silmus. Meil on välimine loop mis jookseb nullist p. Ja meil on sisemine loop, mis töötab nullist p ja sees, et Ma väita, et keha loop töötab konstantse ajaga. Mis siis halvima runtime Selle konkreetse koodilõige? Noh, jälle oleme välimine mis kulgeb p korda. Ja iga AEG_ iteratsiooni Selle loop, pigem. Meil on sisemine loop mis töötab ka p korda. Ja siis sees, et seal on pidev AEG_ vähe koodijupi seal. 

Nii et kui meil on välimine loop et jookseb lk korda, mille sees on sisemine loop et jookseb p korda-- mis on halvima runtime Selle koodilõige? Kas sa vist suur-O p ruudus? 

Ma olen Doug Lloyd. See on CS50.