Rendben, szóval, számítási komplexitás. Csak egy kis figyelmeztetés mielőtt belevetik túl far-- ez akkor valószínűleg körében A legtöbb matematikai nehéz dolog beszélünk a CS50. Remélhetőleg nem lesz túl nyomasztó és megpróbáljuk, és végigvezeti Önt keresztül a folyamat, de Csak egy kicsit tisztességes figyelmeztetést. Van egy kicsit A matematikai részt itt. Rendben, így annak érdekében, hogy felhasználása a számítási erőforrások A valós world-- ez tényleg Fontos megérteni algoritmusok és hogyan dolgozzák fel az adatokat. Ha van egy igazán hatékony algoritmust, mi csökkenti a források összege a rendelkezésünkre álló foglalkozni vele. Ha van egy algoritmus, amely fog tartani a sok munka feldolgozni egy igazán nagy adathalmazt, ez lesz szükség több és több erőforrást, amely pénz, RAM, minden ilyesmi. 

Tehát, hogy képes elemezni a algoritmust használja ezt az eszközt sor, Alapvetően arra kéri a question-- hogyan működik ez az algoritmus skálán ahogy dobja egyre több adat kerül ez? Ebben CS50, az adatok mennyisége vagyunk dolgozik elég kicsi. Általában a programok folynak futtatni egy második vagy less-- Valószínűleg sokkal kevesebb Különösen az elején. 

De gondolj olyan cég, amely foglalkozik több száz millió ügyfél. És kell feldolgozniuk hogy az ügyfelek adatait. Mivel az ügyfelek száma általuk van egyre nagyobb és nagyobb, ez fog igényelni több és több erőforrást. Hány több forrást? Nos, ez attól függ, hogy elemezzük az algoritmust, eszközeivel eszköztár. Amikor arról beszélünk, összetettsége Egy algorithm-- amely néha akkor hallani nevezik idő bonyolultsága vagy térben összetettsége de mi csak megy hívni complexity-- mi általában beszélünk A legrosszabb forgatókönyv. Mivel az abszolút legrosszabb halom adatok, hogy mi lehetne dobott rajta, hogyan van ez algoritmust fog feldolgozni és kezelni az adatokat? Általánosságban az a legrosszabb futásidejű algoritmus nagy O. Tehát egy algoritmus lehet mondani, futnak O n vagy O n négyzeten. És még mit azokat jelenti a második. 

Néha azonban, mi ellátás a legjobb esetben. Ha az adatok mindent, amit akartunk hogy legyen, és ez abszolút tökéletes volt és mi volt küldése tökéletes adathalmazt keresztül algoritmus. Milyen lenne kezelni ebben a helyzetben? Néha arra utalnak, hogy a nagy-Omega, így szemben a nagy-O, már nagy-Omega. Nagy-Omega a legjobb eset. Big-O a legrosszabb forgatókönyv. Általában, ha beszélünk összetettsége egy algoritmus, beszélünk a a legrosszabb esetben. Tehát hogy tartsa szem előtt. 

És ebben az osztályban, mi általában lesz elhagyni a szigorú elemzés félre. Vannak tudományok és mezők szentelt ilyen cucc. Amikor arról beszélünk, indokolás algoritmusok segítségével, amit megteszek darab-by-darab a sok algoritmusok beszélünk az osztályban. Mi tényleg csak beszél érvelés rajta a józan ész, Nem képletek, vagy bizonyítékokat, vagy ilyesmi. Szóval ne aggódj, nem lesz fordult egy nagy matekórán. 

Szóval azt mondtam törődünk összetettsége mert azt a kérdést, hogy hogyan nem az algoritmusok kezelni a nagyobb és Nagy adathalmazok dobálnak rájuk. Nos, mi egy adathalmaz? Mit gondolok, amikor azt mondta, hogy? Ez azt jelenti, bármi is okozza a legtöbb értelme az összefüggésben, hogy őszinte legyek. Ha van egy algoritmus, a Folyamatok Strings-- akkor alighanem beszél a méret a húr. Ez az adat set-- a méret, a szám karakterek alkotják a húr. Ha beszélünk egy algoritmust, amely feldolgozza a fájlokat, mi lehet beszélni, hogyan Sok kilobyte tartalmaznak, hogy a fájl. És ez az adathalmaz. Ha beszélünk egy algoritmus amely kezeli tömbök általában mint például a rendezési algoritmusok vagy keresőalgoritmust, akkor alighanem beszélünk száma Az alkotó elemek egy tömbben. 

Most tudjuk mérni egy algorithm-- különösen, amikor azt mondom, amit lehet mérésére egy algoritmus, azt jelenti azt, hogy mennyire sok erőforrást vesz fel. Hogy ezek a források, hogy hány byte RAM-- vagy megabájt RAM-mal használ. Vagy mennyi idő kell ahhoz, hogy fusson. És nevezhetjük ezt mérésére, önkényesen, f n. Ahol N a száma elemek a adathalmaz. És f n hány asok. Hány egységnyi nyersanyagot nem követeli, hogy feldolgozza az adatokat. 

Most, hogy igazából nem érdekel mit f n pontosan. Sőt, mi nagyon ritkán will-- biztosan nem ebben a class-- I belevetik magukat a valóban mély elemzést, amit f n van. Mi csak beszélgetünk, milyen f n kb vagy mit is hajlamos. És az a tendencia, az algoritmus diktálta a legmagasabb rendű távon. És azt látjuk, amit én ez alatt azáltal, hogy Egy pillantás egy konkrét példát. 

Tehát mondjuk, hogy van Három különböző algoritmusok. Az első, amely úgy n kockára vágott, néhány egység erőforrások feldolgozni egy adathalmaz n méretű. Van egy másik algoritmust tartalmaz, n kockára vágott + n faragva erőforrások feldolgozni egy adathalmaz n méretű. És van egy harmadik algoritmus fut in--, hogy felveszi n kockára vágott mínusz 8 n faragva plusz 20 n egységnyi nyersanyagot feldolgozni egy algoritmus A adatállomány n méretű. 

Most újra, igazán nem megy bejutni ilyen szintű részletesség. Én tényleg csak e fel Itt az illusztráció egy pont hogy én leszek így egy második, amely hogy mi csak igazán érdekel a tendencia a dolgokat mint az adatsorok kap nagyobb. Tehát, ha az adathalmaz kicsi, van valójában egy elég nagy különbség Ezekben algoritmusok. A harmadik algoritmus létezik úgy 13-szer hosszabb, 13-szer annyi erőforrások futtatni képest az első. 

Ha mi adathalmaz mérete 10, amely nagyobb, de nem szükségszerűen hatalmas, azt látjuk, hogy van valójában egy kicsit a különbség. A harmadik algoritmus hatékonyabbá válik. Arról van szó, valójában 40% - vagy 60% -kal hatékonyabb. Tart 40% az az idő. Ez run-- is eltarthat 400 egység erőforrások feldolgozni egy adathalmaz mérete 10. Míg az első algoritmus, ezzel szemben, úgy 1000 egységnyi nyersanyagot feldolgozni egy adathalmaz mérete 10. De nézd mi történik, amint a számok, hogy még nagyobb. 

Most, a különbség ezek között algoritmusok kezd válni egy kicsit kevésbé nyilvánvaló. És az a tény, hogy vannak alacsonyabb rendű terms-- vagy inkább, szempontjából alacsonyabb exponents-- kezd válni. Ha egy adathalmaz mérete 1,000 és az első algoritmus fut egy milliárd lépéseket. És a második algoritmus fut Egy milliárd millió lépés. És a harmadik algoritmus fut A Röpke egy milliárd lépéseket. Ez nagyjából egymilliárd lépéseket. Ezeket az alsó-rendű tagokat indul válni igazán releváns. És csak azért, hogy valóban kalapács haza a point-- ha az adatbevitel a méret a million-- mindhárom elég sok hogy egy quintillion-- ha én matek correct-- lépések feldolgozni egy adatbeviteli A méret egy millió. Ez egy csomó lépést. És az a tény, hogy egyikük talán hogy pár 100.000, vagy egy pár 100 millió még kevésbé, ha beszélünk több hogy big-- ez a fajta lényegtelen. Mindannyian hajlamosak arra, hogy mintegy n kockára vágott, alatt, ezért ténylegesen hivatkozni hogy az összes ilyen algoritmusok mint a sorrendben a N kockára vágott, vagy a nagy O-n a köbön. 

Itt van egy lista néhány a több közös számítási komplexitás osztályok hogy mi lesz találkozás algoritmusok, általában. És azt is, konkrétan a CS50. Ezek megrendelt általában leggyorsabb a tetején, hogy általában leglassabb az alján. Tehát állandó idejű algoritmusok hajlamosak hogy a leggyorsabb, függetlenül attól, A méret a adatbevitel elmész. Ők mindig egy művelet vagy egységnyi erőforrás áll rendelkezésére. Lehet, hogy a 2., talán legyen 3, lehet, hogy 4. De ez egy állandó számot. Ez nem változik. 

Logaritmikus időben algoritmusok valamivel jobb. És egy igazán jó példa logaritmikus algoritmust amit biztosan látott már a tépte szét a telefonkönyv találni Mike Smith a telefonkönyvben. Vágjuk a probléma felét. És így n nagyobb lesz és nagyobb és larger-- sőt, minden alkalommal, ha kétszer n, csak úgy egy lépést. Szóval ez egy sokkal jobb mint mondjuk a lineáris idő. Amely, ha kétszeresére n, akkor veszi kettős a lépések számát. Ha megháromszorozódik n, tart megháromszorozza a lépések számát. Egy lépés egységenként. 

Aztán a dolgok egy kicsit more-- kicsit kevésbé jó onnan. Van lineáris ritmikus, néha úgynevezett log lineáris idő, vagy csak n log n. És mi egy példa Az egy algoritmus, hogy fut n log n, ami még mindig jobb, mint másodfokú time-- n faragva. Vagy polinomiális n két meghaladó tetszőleges kettő. Vagy exponenciális időt, amely még worse-- C és az N. Szóval néhány állandó számú emelt A hatalom a bemenet mérete. Szóval, ha van 1,000-- ha a adatbevitel mérete 1000, telne C a 1000. hatalom. Ez sokkal rosszabb, mint polinomiális időben. 

Factorial idő még rosszabb. És valóban, ott tényleg létezik végtelen idő algoritmusok, mint például, az úgynevezett buta sort-- akinek feladata, hogy véletlenszerűen összekeveri a tömb elemeit és nézze meg, hogy legyen szó válogatni. És ha ez nem, véletlenszerűen shuffle a tömb újra és nézze meg, hogy ez válogatni. És ahogy tudod talán imagine-- el lehet képzelni olyan helyzetet ahol a legrosszabb eset, hogy akarata sosem kezdeni a tömbben. Ez az algoritmus állna örökké. És így, hogy lenne végtelen idejű algoritmus. Remélhetőleg nem lesz írás minden faktoros vagy végtelen idő algoritmusok CS50. 

Tehát, vessünk egy kicsit beton pillantást néhány egyszerűbb számítási komplexitás osztályok. Tehát van egy example-- -két példát here-- Az állandó idejű algoritmusok, amely mindig egyetlen művelettel a legrosszabb eset. Tehát az első example-- van egy funkció az úgynevezett 4 az Ön számára, amely vesz egy sor mérete 1000. De akkor nyilván valójában nem néz ki A it-- nem nagyon érdekli, mi van belsejében is, a tömb. Mindig csak visszatér a négy. Szóval, ez az algoritmus, annak ellenére, hogy ez úgy 1000 elemeket nem mit kezdeni velük. Csak visszatér a négy. Ez mindig egy lépéssel. 

Tény, adjunk hozzá 2 nums-- amely amit látott, mint well-- Csak feldolgozza két egész szám. Ez nem egy lépésben. Ez valójában egy pár lépésre. Kapsz egy, kapsz b, felveszi őket együtt, és akkor az eredmény kimentése. Tehát ez a 84 lépést. De ez mindig állandó, függetlenül attól, hogy egy vagy b. Van, hogy egy, kap b, add őket, kimeneti eredményét. Szóval ez egy állandó algoritmust. 

Íme egy példa egy lineáris idő algorithm-- egy algoritmus, hogy gets-- vevő egy további lépés, esetleg, a bemenet növekszik 1. Tehát, mondjuk keresünk Az 5-ös szám belsejében egy tömbben. Lehet, hogy olyan helyzetben, amikor akkor ez egy nagyon jó korán. De akkor is van olyan helyzetben, hogy Lehet, hogy az utolsó elem a tömbben. Az egy tömbben méretű 5, ha keresünk száma 5. Telne 5 lépésben. És valóban, képzeljük el, hogy van Nem 5 sehova ebben a tömbben. Még mindig ténylegesen meg kell nézni minden egyes eleme a tömb annak érdekében, hogy meghatározzák e vagy sem 5 ott van. 

Tehát a legrosszabb eset, ami az, hogy Az elem utolsó a tömbben vagy nem is létezik. Még mindig meg kell nézni mind az n elemekkel. És így ez az algoritmus fut a lineáris időben. Te is megerősíti, hogy a extrapolációjára egy kicsit, mondván, ha lenne egy 6-elem tömb és kerestünk száma 5, ez eltart 6 lépésben. Ha van egy 7 tömböt és keresünk száma 5. Ez eltarthat 7 lépéseket. Ahogy hozzá még egy eleme, hogy a tömb, tart még egy lépést. Ez egy lineáris algoritmus a legrosszabb esetben. 

Pár gyors kérdés az Ön számára. Mi a runtime-- mi A legrosszabb futási Ezen adott kódrészletet? Szóval van egy 4 hurok van, hogy fut a j értéke 0, egészen a m. És mit látok itt, hogy a hurok teste fut állandóan időben. Tehát terminológiát használva, hogy Már beszéltünk about-- mi lenne a legrosszabb futási az algoritmus? Vegyünk egy pillanatra. A belső része a hurok fut állandóan időben. És a külső része a hurok fog futni m alkalommal. Szóval mi a legrosszabb eset runtime itt? Találta ki a nagy O-m? Igazad van. 

Mit szólnál egy másikat? Ezúttal egy hurok belsejében egy hurok. Van egy külső hurok futó nulláról p. És van egy belső kör, amely fut nulláról p, és aztán az, Megállapítom, hogy a testület a hurok fut állandóan időben. Szóval mi a legrosszabb eset runtime Ezen adott kódrészletet? Nos, megint van egy külső hurok fut p-szer. És minden time-- ismétlés Az, hogy a hurok, inkább. Van egy belső hurok futtatására is képes p-szer. És akkor aztán az, ott van a állandó time-- kis részlet van. 

Tehát ha van egy külső hurok, amely fut p-szer belsejében, amely egy belső hurok fut p times-- mi A legrosszabb futási E kódrészletet? Találta ki a nagy O-p faragva? 

Én Doug Lloyd. Ez CS50.