Dobre, takže, výpočtová zložitosť. Len trochu varovanie Než sa ponoríme príliš far-- to bude pravdepodobne medzi najviac Math-heavy veci hovoríme o v CS50. Dúfajme, že to nebude príliš ohromujúce a my sa pokúsime a sprievodca vás prostredníctvom procesu, ale len trochu varovať. Je tu trochu matematiky tu jedná. Dobre, tak, aby ste mohli vykonať využitia našich výpočtových zdrojov v reálnom world-- je to naozaj dôležité pochopiť, algoritmy a ako sa spracovávajú dáta. Ak máme naozaj efektívny algoritmus, máme môže minimalizovať množstvo zdrojov máme k dispozícii, aby sa s tým vyrovnať. Ak máme algoritmus, ktorý bude trvať veľa práce spracovať naozaj veľký súbor dát, je to bude vyžadovať viac a ďalšie zdroje, ktoré sú peniaze, RAM, všetko, čo druh vecí. 

Takže, je schopný analyzovať algoritmus pomocou tohto sada nástrojov, v podstate žiada question-- ako sa tento algoritmus mierka ako sme hodiť viac a viac dát na to? V CS50, množstvo dát sme práca s je celkom malý. Všeobecne platí, že naše programy idú spustiť v druhej alebo less-- pravdepodobne oveľa menej najmä čoskoro. 

Ale premýšľať o firme, ktorá sa zaoberá so stovkami miliónov zákazníkov. A oni potrebujú spracovať že údaje o zákazníkoch. Ako sa počet zákazníkov, ktoré majú dostane väčšie a väčšie, že to bude vyžadovať viac a viac prostriedkov. Koľko ďalších zdrojov? No, to záleží na tom, ako analyzujeme algoritmus, s využitím nástrojov v tomto paneli nástrojov. Keď hovoríme o zložitosti algorithm-- ktoré niekedy budete počuť len čas zložitosť alebo priestor zložitosť ale my sme len tak volať complexity-- my všeobecne hovorí o najhorší scenár. Vzhľadom k tomu, absolútne najhoršie hromada údaje, ktoré by sme mohli hádzať na to, ako sa tento algoritmus bude spracovávajú alebo vysporiadať s týmito dátami? Všeobecne Hovoríme najhoršom prípade runtime algoritmu big-O. Takže algoritmus môže byť povedal, aby spustiť v O. N alebo O n na druhú. A viac o tom, čo tie, ktoré znamenajú v druhom. 

Niekedy, keď robíme starostlivosť o najlepšom prípade. Ak dáta je všetko, čo sme chceli aby to bolo a bolo to úplne perfektný a my sme boli posielanie to perfektné sada dát prostredníctvom nášho algoritmu. Ako by sa to zvládnuť v tejto situácii? Niekedy sme odkazujú na, že keď big-Omega, takže na rozdiel od veľkých-O, máme veľkú-Omega. Big-Omega pre najlepší možný scenár. Big-O pre najhorší možný scenár. Všeobecne platí, že keď hovoríme o zložitosť algoritmu, hovoríme o najhorší scenár. Takže majte na pamäti, že. 

A v tejto triede, budeme všeobecne deje opustiť hĺbkovej analýzy stranou. Tam sú vedy a polia venovaný tento druh vecí. Keď hovoríme o zdôvodnenie pomocou algoritmov, čo urobíme kus od kusu pre mnoho algoritmy hovoríme o v triede. Sme naozaj len hovorí o úvaha cez to so zdravým rozumom, nie s formulou, alebo dôkazy, alebo niečo také. Takže sa nemusíte báť, Nebudeme sústruženie do veľkého matiku. 

Tak som povedal: staráme sa o zložitosti pretože kladie otázku, ako sa naše algoritmy spracovávať väčšie a väčšie súbory údajov bol hodený na ne. No, a čo je súbor dát? Čo mám na mysli, keď som povedal, že? To znamená, že bez ohľadu je dosiahnuté maximálneho zmysel v súvislostiach, aby som bol úprimný. Ak máme algoritmus, na Procesy Strings-- sme nejspíš hovorí o veľkosti reťazca. To sú údaje set-- veľkosť, počet znakov, ktoré tvoria reťazec. Keď už sa bavíme o algoritmus, ktorý spracováva súbory, môžeme hovoriť o tom, ako mnoho kilobajtov obsahujú tento súbor. A to je súbor dát. Keď už sa bavíme o algoritme , Ktorý spracováva pole všeobecnejšie ako je triedenie algoritmy alebo vyhľadávanie algoritmy, budeme pravdepodobne hovoríme o počte prvkov, ktoré tvoria pole. 

Teraz môžeme zmerať algorithm-- najmä keď hovorím, že môžeme merať algoritmus, ja znamenať môžeme merať, ako veľa zdrojov, to zaberá. Či už sú tieto zdroje, koľko bajtov RAM-- alebo megabajtov pamäte RAM používa. Alebo ako dlho to trvá spustiť. A môžeme volať toto zmerať, svojvoľne, f n. Kde n je počet Prvky v sade dát. A f n je, koľko niečo cez. Koľko jednotiek zdrojov robí vyžadovať spracovanie týchto dát. 

Teraz sme v skutočnosti nezaujíma o tom, čo f n je presne. V skutočnosti sme veľmi zriedka will-- Rozhodne sa nikdy v tomto class-- I Ponorte sa do žiadnej naozaj hlbokej analýza toho, čo f o n je. Sme jednoducho hovoriť o tom, čo f n je približne alebo čo má tendenciu. A tendencia algoritmu je diktoval jeho najvyššieho rádu termíne. A my môžeme vidieť, čo mám na mysli, že tým, že Pozrite sa na viac konkrétny príklad. 

Takže povedzme, že máme tri rôzne algoritmy. Prvý z nich je uvedené n Cubed, niektoré jednotky zdrojov pre spracovanie dát sadu veľkosti n. Máme druhý algoritmu, ktorý berie n kocky a n štvorcový zdroje pre spracovanie dát sadu veľkosti n. A máme tretina algoritmus, ktorý beží in-- že zaberá n kocky mínus 8N na druhú plus 20 n jednotiek zdrojov spracovať algoritmus s údajmi uvedenými veľkosti n. 

Teraz znovu, naozaj nebudeme sa dostať do tejto úrovni detailu. Som naozaj sa len týchto hore tu ako ilustráciu bodu že ja budem čo v druhom, ktorý je, že sme len naozaj záleží o tendenciu vecí ako dátové súbory získať väčšie. Takže v prípade, že dátová sada je malý, je tu vlastne celkom veľký rozdiel V týchto algoritmov. Tretí algoritmus tam trvá 13 krát dlhšie, 13 krát množstvo zdrojov bežať vo vzťahu k prvej. 

Ak sa náš súbor dát je veľkosť 10, ktorý je väčší, ale nie nevyhnutne veľké, môžeme vidieť, že je tu vlastne trochu rozdiel. Tretí algoritmus sa stáva účinnejšia. Je to o vlastne o 40% - alebo 60% efektívnejšia. To trvá 40% množstvo času. To môže run-- to môže trvať 400 jednotiek zdrojov pre spracovanie dát sadu veľkosti 10. Kým prvý algoritmus, naopak berie 1.000 jednotiek zdrojov pre spracovanie dát sadu veľkosti 10. Ale pozrite sa, čo sa deje, keď náš počet sa ešte väčší. 

Teraz je rozdiel Medzi tieto algoritmy začnú byť o niečo menej viditeľné. A skutočnosť, že existujú nižšia-objednávať terms-- alebo skôr, termíny s nižším exponents-- začnú byť irelevantné. Ak je súbor dát o veľkosti 1000 a prvý algoritmus prebieha v miliardy krokoch. A druhý algoritmus beží v miliarda a milión krokov. A tretí algoritmus beží V tesne pred miliardy krokov. Je to celkom veľa miliardu krokov. Tí menej náročné podmienky spustení aby sa stal naozaj irelevantné. A len preto, aby naozaj kladivo domov point-- v prípade, že vstupné dáta je veľkosť A million-- všetci traja z nich celkom veľa mať jednu quintillion-- if moja matematika je correct-- kroky spracovať vstup dát veľkosti milióna. To je veľa schodov. A skutočnosť, že jeden z nich by mohol trvať niekoľko 100.000, alebo pár 100 miliónov, aj keď menej hovoríme o počte že big-- je to trochu irelevantné. Tí všetci majú tendenciu brať približne n kocky, a tak by sme vlastne odkazovať pre všetky z týchto algoritmov ako na poradie n kubický alebo big-O n kubický. 

Tu je zoznam niektorých z viacerých spoločné výpočtovej triedy zložitosti že s ktorými sa stretnete v algoritmy, všeobecne. A tiež konkrétne v CS50. Títo sú organizovaní od všeobecne najrýchlejší v hornej časti, všeobecne najpomalší v dolnej časti. Takže konštantnom čase algoritmy majú tendenciu byť najrýchlejší, bez ohľadu o veľkosti Vstupné dáta odovzdáte. Oni vždy jednu operáciu, alebo jeden celok zdrojov riešiť. To by mohlo byť 2, by to mohlo byť 3, môže to byť 4. Ale to je konštantná číslo. To sa nemení. 

Logaritmickej algoritmy času sú o niečo lepšie. A naozaj dobrý príklad logaritmickou algoritmus ste iste videli už je odtrhnutie telefónneho zoznamu nájsť Mike Smith v telefónnom zozname. Režeme problém na polovicu. A tak ako n sa zväčší a väčšie a larger-- V skutočnosti, zakaždým, keď sa zdvojnásobí n, len to trvá ešte jeden krok. Tak to je oveľa lepšie, než, povedzme, lineárny čas. Čo je, pokiaľ zdvojnásobiť n, to berie dvojnásobný počet krokov. Ak strojnásobiť n, trvá strojnásobiť počet krokov. Jeden krok za jednotku. 

Potom sa veci trochu more-- trochu menej skvelé odtiaľ. Máš lineárny rytmické čas, niekedy volal log lineárny čas, alebo len n log n. A Budeme príklad of algoritmus, ktorý prebieha v n log n, čo je ešte lepšie než kvadratická time-- n na druhú. Alebo polynóm čas, n dvoch ľubovoľné číslo väčšie než dve. Alebo exponenciálny čas, ktorý je dokonca worse-- C až n. Takže nejaká konštanta číslo zvýši na sila veľkosť vstupu. Takže či je 1,000-- keď signál Vstupné dáta o veľkosti 1000, to bude trvať C do 1000. moci. Je to oveľa horšie, než polynomiálním čase. 

Faktoriál čas je ešte horšia. A v skutočnosti, tam naozaj Existujú nekonečného času algoritmy, ako je napríklad tzv hlúpy sort-- ktorých úlohou je náhodne zamiešať pole a potom skontrolovať, či už je to triediť. A ak to nie je, náhodne Znovu zamiešajte pole a skontrolujte, či je to triediť. A ako môžete pravdepodobne imagine-- môžete si predstaviť situáciu, kde sa v najhoršom prípade, že bude vlastne nikdy začať s poľa. To algoritmus pobeží navždy. A tak to by bolo nekonečný čas algoritmus. Dúfajme, že nebudete písať akýkoľvek faktoriál alebo nekonečný čas algoritmy v CS50. 

Takže, poďme sa trochu viac betón pozrieť na niektoré jednoduchšie výpočtovej zložitosť triedy. Takže máme example-- alebo dva príklady here-- konštantných časových algoritmov, ktorý vždy brať jedna operácia v najhoršom prípade. Takže prvý example-- my máme funkciu volal 4 pre vás, ktorý berie poľa veľkosti 1000. Ale potom zrejme nie je v skutočnosti vyzerať na to-- nie je naozaj jedno, čo je vnútri nej, z tejto matice. Vždy iba vráti štyri. Tak, že algoritmus, a to napriek skutočnosti, že trvá 1000 prvky nemusia robiť niečo s nimi. Len vráti štyri. Je to vždy jeden krok. 

V skutočnosti, sa pridajú 2 nums--, ktoré sme nevideli za well-- práve spracováva dve celé čísla. Nie je to jediný krok. V skutočnosti je to pár krokov. Získate, dostanete b, je pridáte dohromady, a vy výstupné výsledky. Takže je to 84 krokov. Ale je to vždy konštantný, ohľadu na to, a alebo b. Musíte sa dostať, dostať b, pridajte je dohromady, výstup výsledok. Takže to je konštantná algoritmus. 

Tu je príklad lineárny čas algorithm-- algoritmus, ktorý gets--, ktorý berie jeden ďalší krok, prípadne ako vaše vstupné rastie o 1. Takže, povedzme, že hľadáme počet 5 vnútri poľa. Možno budete v situácii, keď môžete nájsť to celkom skoro. Ale môžete tiež mať situácie, kedy ju môže byť posledný prvok poľa. V poli o veľkosti 5, pokiaľ hľadáme číslo 5. Chcelo by to 5 krokov. A v skutočnosti, predstavte si, že je tu Nie je 5 kdekoľvek v tomto poli. Stále v skutočnosti sa pozrieť na každý prvok poľa za účelom zistenia, či 5 je tam. 

Takže v najhoršom prípade, čo je to, že prvok je posledný v poli alebo neexistuje vôbec. Stále sa pozrieť na všetky z n prvkov. A tak tento algoritmus beží v lineárnom čase. Môžete potvrdiť, že by extrapolácie trochu tým, že hovorí, keby sme mali 6-prvok poľa a sme hľadali na číslo 5, to môže trvať 6 krokov. Ak máme 7-prvok poľa a hľadáme číslo 5. To by mohlo trvať 7 krokov. Ako sme pridať ešte jeden prvok do nášho poľa, trvá ešte jeden krok. To je lineárny algoritmus v najhoršom prípade. 

Pár rýchlych otázok pre vás. Čo je to, čo je runtime-- najhorší prípad runtime z tohto konkrétneho fragmentu kódu? Takže mám 4 slučku tu, ktorý beží od j rovná 0, celú cestu až do m. A to, čo som videl tu, je to, že telo slučky prebieha v konštantnom čase. Takže používať terminológiu sme už hovorili, čo about-- by bol najhorší runtime tohto algoritmu? Vezmite chvíľku. Vnútorná časť slučky beží v konštantnom čase. A vonkajšiu časť slučka bude bežať m-krát. Takže to, čo je tu najhorší prípad runtime? Vedeli ste asi veľký-O M? Vy by ste mať pravdu. 

Ako sa asi iný? Tentoraz máme slučka vnútri slučky. Máme vonkajšej slučky ktorá beží od nuly do str. A máme vnútorný slučku, ktorá sa spúšťa od nuly do p, a vnútorné časti, ktoré, Vyhlasujem, že orgán pre slučka beží v konštantnom čase. Takže čo je najhoršie runtime z tohto konkrétneho fragmentu kódu? No, zase máme Vonkajšie slučka, ktorá sa spúšťa p krát. A každý time-- iterácie tejto slučky, skôr. Máme vnútorný slučky že tiež beží p krát. A potom vnútri to, že je tu konštantný time-- malý úryvok tam. 

Takže ak máme vonkajšej slučka, ktorá beží p časy vnútri ktorej je vnútorné slučky, ktorá beží p times-- to, čo je najhorší prípad runtime tento fragment kódu? Vedeli ste asi veľký-O P na druhú? 

Som Doug Lloyd. To je CS50.