Selvä, joten, laskennallinen vaativuus. Vain vähän varoitus ennen kuin sukeltaa liian far-- tämä varmaan joukossa eniten matematiikka-raskaita asioita puhumme CS50. Toivottavasti se ei ole liian suuri ja me yritämme ja opastaa prosessin läpi, mutta vain hieman reilun varoituksen. Siellä on hieman matematiikkaa mukana täällä. Selvä, joten jotta käyttää meidän laskentaresursseja todellisessa world-- se on todella tärkeää ymmärtää algoritmeja ja miten ne käsittelevät tiedot. Jos meillä on todella tehokas algoritmi, me voi minimoida resurssien meillä on käytettävissä käsitellä sitä. Jos meillä on algoritmi, joka vie paljon työtä käsitellä todella suuri joukko tietoja, se on aikoo vaatia lisää ja enemmän resursseja, jotka on rahaa, RAM, kaikki tuollaista. 

Niin, että voimme analysoida algoritmi tällä työkalusarja, pohjimmiltaan, kysyy question-- miten tämä algoritmi asteikko kuten me heittää enemmän ja enemmän tietoja se? In CS50, datan määrä olemme kanssa on melko pieni. Yleensä meidän ohjelmat ovat menossa ajaa toisen tai less-- luultavasti paljon vähemmän erityisesti varhain. 

Mutta ajattele yritys, joka käsittelee satoja miljoonia asiakkaita. Ja he tarvitsevat prosessin että asiakkaan tiedot. Koska asiakkaiden määrä he on saa suurempia ja suurempia, se tulee vaatia enemmän ja enemmän resursseja. Kuinka monta resursseja? No, se riippuu siitä, miten analysoimme algoritmi, työkaluilla tässä työkalupakin. Kun puhumme monimutkaisuus algorithm-- joka joskus ll kuulla sen nimitystä aika monimutkaisuus tai tilaa monimutkaisuus mutta me vain menossa soittaa complexity-- me yleensä puhumme pahimmassa tapauksessa. Koska ehdoton pahin kasa tiedot että voisimme heittää sitä, miten tämä algoritmi menossa käsitellä tai käsitellä että tiedot? Olemme yleensä kutsumme pahin runtime algoritmin iso-O. Niin algoritmi voidaan sanoa ajaa O n tai O n neliö. Ja enemmän siitä, mitä ne tarkoittavat toista. 

Joskus kuitenkin, teemme hoito noin parhaassa tapauksessa. Jos tiedot on kaiken mitä halusimme sen olevan ja se oli aivan täydellinen ja olimme lähettää tämä täydellinen tietotaulukoista kautta algoritmi. Miten se hoitaa tässä tilanteessa? Joskus viittaavat että iso-Omega, joten toisin kuin iso-O, meillä on iso-Omega. Iso-Omega paras mahdollinen tilanne. Big-O pahin skenaario. Yleensä kun puhumme monimutkaisuus algoritmi, me puhumme pahimmassa tapauksessa. Niin pitää tämä mielessä. 

Ja tässä luokassa, me yleensä menossa jättää analysoitava syrjään. On tieteiden ja kentät omistettu tällaista kamaa. Kun puhumme perustelut kautta algoritmeja, joka teemme pala-by-osainen monille algoritmit puhumme luokassa. Olemme todella vain puhu päättely läpi järkeä, ei kaavat, tai todisteita, tai jotain sellaista. Joten älä huoli, Emme muuttumassa iso matematiikka luokka. 

Joten sanoin välitämme monimutkaisuus koska se kysyy, miten teemme algoritmeja käsitellä suurempia ja Suuremmat tietokokonaisuuksien heitetään niitä. No, mikä on tietojen joukko? Mitä minä tarkoitan, kun sanoin, että? Se tarkoittaa mikä tekee eniten järkeä yhteydessä, olla rehellinen. Jos meillä on algoritmi, Prosessit Strings-- olemme luultavasti puhumme koko merkkijono. Se tietojen set-- koko, lukumäärä merkkien, jotka muodostavat merkkijono. Jos puhumme algoritmi, joka käsittelee tiedostoja, voisimme puhua miten monet kilotavua käsittävät tiedoston. Ja se on tietojen käyttöä. Jos puhumme algoritmi joka käsittelee paneelit yleisemmin, kuten lajittelualgoritmeja tai etsivät algoritmeja, me luultavasti puhumme numero elementtejä, jotka käsittävät erilaisia. 

Nyt voimme mitata algorithm-- erityisesti, kun sanon voimme mitata algoritmi, I voimme mitata, kuinka paljon resursseja se vie. Ovatko nämä resurssit ovat, kuinka monta tavua RAM-- tai megatavua RAM-muistia se käyttää. Tai kuinka paljon aikaa se vie ajaa. Voimme kutsua tätä mitata, mielivaltaisesti, f n. Jossa n on määrä elementtejä tietokokonaisuutta. Ja f n on, kuinka monta somethings. Kuinka monta resurssia ei se edellyttää käsitellä näitä tietoja. 

Nyt oikeastaan ​​välitä mitä f n on täsmälleen. Itse asiassa olemme hyvin harvoin will-- varmasti koskaan tässä class-- I sukeltaa mitään todella syvä analyysi siitä, mitä f n on. Olemme juuri menossa puhua siitä, mitä f n on noin tai mitä se pyrkii. Ja taipumus algoritmi on sanelee sen huipputasolla aikavälillä. Ja voimme nähdä, mitä minä tarkoitamme, että ottamalla katso enemmän konkreettinen esimerkki. 

Joten sanoa, että meillä on kolme eri algoritmeja. Joista ensimmäinen kestää n kuutioitu, jotkut resurssia käsitellä datasarjan koko on n. Meillä on toinen algoritmi, joka vie n kuutioitu plus n potenssiin resurssit käsitellä datasarjan koko on n. Ja meillä on kolmasosa algoritmi, joka toimii in--, että vie n kuutioitu miinus 8n potenssiin plus 20 n resurssia käsitellä algoritmi tietoja asettaa koko on n. 

Nyt taas, emme todellakaan aio päästä tämän tason yksityiskohtia. Olen todella vain on näitä ylös täällä esimerkki pisteen että aion olla jolloin toisessa, joka on, että me vain todella varovainen noin taipumus asioita kuten aineistoja saada isompi. Joten jos tiedot joukko on pieni, siellä oikeastaan ​​aika iso ero näissä algoritmit. Kolmas algoritmi siellä kestää 13 kertaa pidempään, 13 kertaa enemmän resursseja juosta suhteessa ensimmäiseen palloon. 

Jos meidän tietokokonaisuus on koko 10, joka on suurempi, mutta ei välttämättä suuria, voimme nähdä, että on olemassa itse asiassa hieman eroa. Kolmas algoritmi tehostuu. Se on noin oikeastaan ​​40% - tai 60% tehokkaampi. Se kestää 40% aikaa. Se voi run-- se voi kestää 400 resurssia käsitellä tietoja joukko koko 10. Kun taas ensimmäinen algoritmi, sen sijaan, ottaa 1000 resurssia käsitellä tietoja joukko koko 10. Mutta katsokaa mitä tapahtuu meidän numerot saada isompi. 

Nyt ero näiden algoritmien alkaa tulla hieman vähemmän ilmeinen. Ja se, että on olemassa alemman asteen terms-- tai pikemminkin, toimeen alempi exponents-- alkaa tulla merkityksettömiä. Jos datasarja on koko 1000 ja ensimmäinen algoritmi toimii miljardia vaiheita. Ja toinen algoritmi toimii miljardi ja miljoona vaiheita. Ja kolmas algoritmi toimii vain ujo miljardin vaiheita. Se on aika paljon miljardia vaiheita. Ne alemman asteen termit alkaa tulla todella merkitystä. Ja vain todella hammer koti point-- jos tietojen syöttö on koko million-- kaikki nämä kolme melko paljon ottaa yksi quintillion-- jos minun matematiikka on correct-- vaiheet käsitellä tietojen syöttö koosta miljoonaa euroa. Se on paljon portaita. Ja se, että yksi heistä voisi ottaa pari 100000, tai pari 100 milj vielä vähemmän kun puhumme numero että big-- se on eräänlainen merkitystä. Ne kaikki on taipumus ottaa noin n kuutioitu, ja niin me todella viitata kaikki nämä algoritmit olevan suuruusluokkaa n kuutioitu tai iso-O n kuutioitu. 

Tässä luettelo joistakin enemmän yhteinen laskennallinen vaativuus luokat että me kohtaamme algoritmeja, yleensä. Ja nimenomaan myös CS50. Nämä tilataan yleensä nopein huipulla, yleisesti hitain alareunassa. Joten jatkuva aika algoritmeja yleensä olla nopein, riippumatta koon Tietojen syöttäminen ohitat. He aina ottaa yksi toiminnan tai yhden yksikön resursseja käsitellä. Se voi olla 2, se saattaa olla 3, se voi olla 4. Mutta se on vakiomäärä. Se ei muutu. 

Logaritminen aika algoritmit ovat hieman paremmat. Ja todella hyvä esimerkki logaritminen aika algoritmi olet varmasti nähdä nyt on repimällä puhelinluettelon löytää Mike Smith puhelinluettelosta. Leikkaamme ongelma kahtia. Ja niin n suurenee ja suurempia ja larger-- Itse asiassa joka kerta kun kaksinkertainen n, se kestää vain yksi askel. Niin, että on paljon parempi kuin vaikkapa lineaarisen ajan. Joka on jos kaksinkertainen n, se ottaa kaksinkertainen määrä vaiheita. Jos kolminkertaistaa n, se kestää kolminkertaistaa useita vaiheita. Yksi askel kohti. 

Sitten asiat saavat hieman more-- hieman vähemmän suuria sieltä. Sinulla on lineaarinen rytminen aikaa, joskus nimeltään loki lineaarisen ajan tai vain n log n. Ja me esimerkki ja algoritmi, joka kulkee n log n, joka on vielä parempi kuin asteen time-- n potenssiin. Tai polynomiaikainen, n kaksi mikä tahansa luku suurempi kuin kaksi. Tai eksponentiaalisesti enemmän aikaa, joka on jopa worse-- C n. Joten jotkut vakio numero nostetaan voima koko panos. Joten jos on 1,000-- jos tietojen syöttö on koko 1000, se veisi C 1000. valtaa. Se on paljon pahempi kuin polynomiajassa. 

Kertoma aika on vielä pahempi. Ja itse asiassa, ei todellakaan tee olemassa ääretön aika algoritmeja, kuten ns tyhmä sort-- joiden työ on satunnaisesti shuffle array ja sitten tarkistaa, onko se lajitellaan. Ja jos se ei ole, satunnaisesti shuffle array uudelleen ja tarkista, onko se lajitellaan. Ja kuten voitte luultavasti imagine-- voit kuvitella tilanne jossa pahimmassa-tapauksessa, että tahto koskaan todella alkaa kanssa jono. Tämä algoritmi kulkisi ikuisesti. Ja että olisi ääretön aika algoritmi. Toivottavasti et kirjallisesti kaikki kertoma tai ääretön aika algoritmeja CS50. 

Niin, sallikaa hieman enemmän betoni tarkastelemme joitakin yksinkertaisempi laskennallinen monimutkaisuus luokat. Meillä on siis example-- tai kaksi esimerkkiä here-- jatkuvasti ajan algoritmeja, joka aina yksittäinen operaatio pahimman. Joten ensimmäinen example-- meillä funktio kehotti 4 sinulle, joka ottaa taulukon koko 1000. Mutta sitten ilmeisesti ei varsinaisesti katso klo it-- ei välitä mitä sen sisällä, ja että jono. Aina vain palauttaa neljä. Niin, että algoritmi, huolimatta siitä, että se vie 1000 elementtejä ei niitä mitenkään. Palaa aivan neljä. On aina yksi askel. 

Itse asiassa, lisätään 2 nums-- joka olemme nähneet ennen kuin well-- vain käsittelee kaksi kokonaislukua. Se ei askeltakaan. Se on oikeastaan ​​pari askelta. Saat, saat b, lisäät ne yhteen, ja te tuotos tuloksia. Joten se on 84 vaiheet. Mutta se on aina vakio, riippumatta tai b. Sinun täytyy saada, saada b, lisätä ne yhteen, tuotos tulos. Niin, että jatkuva algoritmi. 

Tässä on esimerkki lineaarinen aika algorithm-- algoritmi, joka gets--, joka vie yksi ylimääräinen vaihe, mahdollisesti, kuin panos kasvaa 1. Joten sanokaamme etsimme numero 5 sisällä array. Saatat olla tilanteessa, jossa löydät sen melko aikaisin. Mutta voit myös olla tilanteessa, jossa se ehkä viimeinen alkiota. Riviksi nro 5, jos etsimme numero 5. Se veisi 5 askelta. Ja itse asiassa, kuvitella, että on olemassa ei 5 missään tässä array. Meillä on vielä todella on tarkasteltava jokainen alkio jotta voidaan määrittää onko 5 on siellä. 

Joten pahimmassa tapauksessa, joka on, että elementti on viimeinen array tai ei ole olemassa lainkaan. Meillä on vielä tarkasteltava kaikki n elementtiä. Ja niin tämä algoritmi toimii lineaarisessa ajassa. Voit vahvistaa, että ekstrapoloimalla hieman sanomalla, jos meillä oli 6-elementti array ja etsimme numero 5, se saattaa kestää 6 askelmaa. Jos meillä on 7-elementti array ja etsimme numero 5. Se saattaa kestää 7 porrasta. Kuten me lisätä vielä yhden elementin meidän array, se vie yksi askel. Se lineaarinen algoritmi pahimmassa-tapauksessa. 

Muutaman nopeaa kysymyksiin sinulle. Mikä runtime-- mitä pahin runtime tämän nimenomaisen koodinpätkä? Joten minulla on 4 silmukka täällä joka kulkee vaiheesta j on 0, kaikki tavalla jopa metrin. Ja mitä näen täällä, on että elin silmukka kulkee jatkuvasti ajan. Joten käyttämällä termeistä olemme jo puhuneet about-- mitä olisi pahin runtime Tämän algoritmin? Ota toinen. Sisäosan silmukan toimii jatkuvasti ajan. Ja ulompi osa silmukka tulee ajaa m kertaa. Niin mitä pahin runtime täällä? Arvasit iso-O, m? Olisit oikeassa. 

Entä toinen? Tällä kertaa meillä silmukka silmukan sisällä. Meillä ulomman silmukan joka kulkee nollasta s. Ja meillä on sisemmän silmukan, joka toimii nollasta p, ja sisältä että, Totean, että elin silmukka toimii jatkuvasti ajan. Niin mitä pahin runtime tämän nimenomaisen koodinpätkä? No, taas, meillä on ulompi silmukka, joka kulkee s kertaa. Ja kukin time-- iteroinnin Tämän silmukan, melko. Meillä sisemmän silmukan että myös toimii s kertaa. Ja sitten sisällä että siellä vakio time-- pikku pätkä siellä. 

Joten jos meillä on ulompi silmukka, joka kulkee p kertaa jonka sisällä on sisemmän silmukan, joka juoksee p times-- mikä on pahin runtime Tämän koodinpätkä? Arvasit iso-O p potenssiin? 

Olen Doug Lloyd. Tämä on CS50.