Dobře, takže, výpočetní složitost. Jen trochu varování Než se ponoříme příliš far-- to bude pravděpodobně mezi nejvíce Math-heavy věci mluvíme o v CS50. Doufejme, že to nebude příliš ohromující a my se pokusíme a průvodce vás prostřednictvím procesu, ale jen trochu varovat. Je tu trochu matematiky zde jedná. Dobře, tak, abyste mohli provést využití našich výpočetních zdrojů v reálném world-- je to opravdu důležité pochopit, algoritmy a jak se zpracovávají data. Máme-li opravdu efektivní algoritmus, máme může minimalizovat množství zdrojů máme k dispozici, aby se s tím vyrovnat. Máme-li algoritmus, který bude trvat hodně práce zpracovat opravdu velký soubor dat, je to bude vyžadovat více a další zdroje, které jsou peníze, RAM, vše, co druh věcí. 

Takže, je schopen analyzovat algoritmus pomocí tohoto sada nástrojů, v podstatě žádá question-- jak se tento algoritmus měřítko jak jsme hodit více a více dat na to? V CS50, množství dat jsme práce s je docela malý. Obecně platí, že naše programy jdou spustit v druhé nebo less-- pravděpodobně mnohem méně zejména brzy. 

Ale přemýšlet o firmě, která se zabývá se stovkami milionů zákazníků. A oni potřebují zpracovat že údaje o zákaznících. Jak se počet zákazníků, které mají dostane větší a větší, že to bude vyžadovat více a více prostředků. Kolik dalších zdrojů? No, to záleží na tom, jak analyzujeme algoritmus, s využitím nástrojů v tomto panelu nástrojů. Když mluvíme o složitosti algorithm-- které někdy budete slyšet jen čas složitost nebo prostor složitost ale my jsme jen tak volat complexity-- my obecně mluví o nejhorší scénář. Vzhledem k tomu, absolutně nejhorší hromada údaje, které bychom mohli házet na to, jak se tento algoritmus bude zpracovávají nebo vypořádat s těmito daty? Obecně Říkáme nejhorším případě runtime algoritmu big-O. Takže algoritmus může být řekl, aby spustit v O. N nebo O n na druhou. A více o tom, co ty, které znamenají v druhém. 

Někdy, když děláme péči o nejlepším případě. Pokud data je vše, co jsme chtěli aby to bylo a bylo to naprosto perfektní a my jsme byli posílání to perfektní sada dat prostřednictvím našeho algoritmu. Jak by se to zvládnout v této situaci? Někdy jsme odkazují na, že když big-Omega, takže na rozdíl od velkých-O, máme velkou-Omega. Big-Omega pro nejlepší možný scénář. Big-O pro nejhorší možný scénář. Obecně platí, že když hovoříme o složitost algoritmu, mluvíme o nejhorší scénář. Takže mějte na paměti, že. 

A v této třídě, budeme obecně děje opustit hloubkové analýzy stranou. Tam jsou vědy a pole věnován tento druh věcí. Když mluvíme o zdůvodnění pomocí algoritmů, což uděláme kus od kusu pro mnoho algoritmy hovoříme o ve třídě. Jsme opravdu jen mluví o úvaha přes to se zdravým rozumem, ne s formulí, nebo důkazy, nebo něco takového. Takže se nemusíte bát, Nebudeme soustružení do velkého matiku. 

Tak jsem řekl: staráme se o složitosti protože klade otázku, jak se naše algoritmy zpracovávat větší a větší soubory údajů byl hozen na ně. No, a co je soubor dat? Co mám na mysli, když jsem řekl, že? To znamená, že bez ohledu je dosaženo maximálního smysl v souvislostech, abych byl upřímný. Máme-li algoritmus, na Procesy Strings-- jsme nejspíš mluví o velikosti řetězce. To jsou údaje set-- velikost, počet znaků, které tvoří řetězec. Když už se bavíme o algoritmus, který zpracovává soubory, můžeme mluvit o tom, jak mnoho kilobajtů obsahují tento soubor. A to je soubor dat. Když už se bavíme o algoritmu , který zpracovává pole obecněji jako je třídění algoritmy nebo vyhledávání algoritmy, budeme pravděpodobně mluvíme o počtu prvků, které tvoří pole. 

Nyní můžeme změřit algorithm-- zejména když říkám, že můžeme měřit algoritmus, já znamenat můžeme měřit, jak mnoho zdrojů, to zabírá. Ať už jsou tyto zdroje, kolik bajtů RAM-- nebo megabajtů paměti RAM používá. Nebo jak dlouho to trvá spustit. A můžeme volat toto změřit, svévolně, f n. Kde n je počet Prvky v sadě dat. A f n je, kolik něco přes. Kolik jednotek zdrojů dělá vyžadovat zpracování těchto dat. 

Nyní jsme ve skutečnosti nezajímá o tom, co f n je přesně. Ve skutečnosti jsme velmi zřídka will-- Rozhodně se nikdy v tomto class-- I Ponořte se do žádné opravdu hluboké analýza toho, co f o n je. Jsme prostě mluvit o tom, co f n je přibližně nebo co má tendenci. A tendence algoritmu je diktoval jeho nejvyššího řádu termínu. A my můžeme vidět, co mám na mysli, že tím, že Podívejte se na více konkrétní příklad. 

Takže řekněme, že máme tři různé algoritmy. První z nich je uvedeno n cubed, některé jednotky zdrojů pro zpracování dat sadu velikosti n. Máme druhý algoritmu, který bere n kostičky a n čtvereční zdroje pro zpracování dat sadu velikosti n. A máme třetina algoritmus, který běží in-- že zabírá n kostičky minus 8N na druhou plus 20 n jednotek zdrojů zpracovat algoritmus s údaji uvedenými velikosti n. 

Teď znovu, opravdu nebudeme se dostat do této úrovni detailu. Jsem opravdu se jen těchto nahoru zde jako ilustraci bodu že já budu což v druhém, který je, že jsme jen opravdu záleží o tendenci věcí jako datové soubory získat větší. Takže v případě, že datová sada je malý, je tu vlastně docela velký rozdíl V těchto algoritmů. Třetí algoritmus tam trvá 13 krát déle, 13 krát množství zdrojů běžet ve vztahu k první. 

Pokud se náš soubor dat je velikost 10, který je větší, ale ne nutně velké, můžeme vidět, že je tu vlastně trochu rozdíl. Třetí algoritmus se stává účinnější. Je to o vlastně o 40% - nebo 60% efektivnější. To trvá 40% množství času. To může run-- to může trvat 400 jednotek zdrojů pro zpracování dat sadu velikosti 10. Zatímco první algoritmus, naopak bere 1.000 jednotek zdrojů pro zpracování dat sadu velikosti 10. Ale podívejte se, co se děje, když náš počet se ještě větší. 

Nyní je rozdíl Mezi tyto algoritmy začnou být o něco méně patrné. A skutečnost, že existují nižší-objednávat terms-- nebo spíše, termíny s nižším exponents-- začnou být irelevantní. Pokud je soubor dat o velikosti 1000 a první algoritmus probíhá v miliardy krocích. A druhý algoritmus běží v miliarda a milion kroků. A třetí algoritmus běží V těsně před miliardy kroků. Je to docela hodně miliardu kroků. Ti méně náročné podmínky spuštění aby se stal opravdu irelevantní. A jen proto, aby opravdu kladivo domů point-- v případě, že vstupní data je velikost A million-- všichni tři z nich docela hodně mít jednu quintillion-- if moje matematika je correct-- kroky zpracovat vstup dat velikosti milionu. To je hodně schodů. A skutečnost, že jeden z nich by mohl trvat několik 100.000, nebo pár 100 milionů, i když méně mluvíme o počtu že big-- je to trochu irelevantní. Ti všichni mají tendenci brát přibližně n kostičky, a tak bychom vlastně odkazovat pro všechny z těchto algoritmů jako na pořadí n krychlový nebo big-O n krychlový. 

Zde je seznam některých z více společné výpočetní třídy složitosti že se kterými se setkáte v algoritmy, obecně. A také konkrétně v CS50. Tito jsou organizováni od obecně nejrychlejší v horní části, obecně nejpomalejší v dolní části. Takže konstantním čase algoritmy mají tendenci být nejrychlejší, bez ohledu o velikosti Vstupní data předáte. Oni vždy jednu operaci, nebo jedna jednotka zdrojů řešit. To by mohlo být 2, by to mohlo být 3, může to být 4. Ale to je konstantní číslo. To se nemění. 

Logaritmické algoritmy času jsou o něco lepší. A opravdu dobrý příklad logaritmickou algoritmus jste jistě viděli už je odtržení telefonního seznamu najít Mike Smith v telefonním seznamu. Řežeme problém na polovinu. A tak jak n se zvětší a větší a larger-- Ve skutečnosti, pokaždé, když se zdvojnásobí n, jen to trvá ještě jeden krok. Tak to je mnohem lepší, než, řekněme, lineární čas. Což je, pokud zdvojnásobit n, to bere dvojnásobný počet kroků. Pokud ztrojnásobit n, trvá ztrojnásobit počet kroků. Jeden krok za jednotku. 

Pak se věci trochu more-- trochu méně skvělé odtamtud. Máš lineární rytmické čas, někdy volal log lineární čas, nebo jen n log n. A Budeme příklad of algoritmus, který probíhá v n log n, což je ještě lepší než kvadratická time-- n na druhou. Nebo polynom čas, n dvou libovolné číslo větší než dvě. Nebo exponenciální čas, který je dokonce worse-- C až n. Takže nějaká konstanta číslo zvýší na síla velikost vstupu. Takže jestli je 1,000-- když signál Vstupní data o velikosti 1000, to bude trvat C do 1000. moci. Je to mnohem horší, než polynomiálním čase. 

Faktoriál čas je ještě horší. A ve skutečnosti, tam opravdu Existují nekonečného času algoritmy, jako je například tzv hloupý sort-- jejichž úkolem je náhodně zamíchat pole a pak zkontrolovat, ať už je to třídit. A pokud to není, náhodně Znovu zamíchejte pole a zkontrolujte, zda je to třídit. A jak můžete pravděpodobně imagine-- můžete si představit situaci, kde se v nejhorším případě, že bude vlastně nikdy začít s pole. To algoritmus poběží navždy. A tak to by bylo nekonečný čas algoritmus. Doufejme, že nebudete psát jakýkoli faktoriál nebo nekonečný čas algoritmy v CS50. 

Takže, pojďme se trochu více beton podívat na některé jednodušší výpočetní složitost třídy. Takže máme example-- nebo dva příklady here-- konstantních časových algoritmů, který vždy brát jedna operace v nejhorším případě. Takže první example-- my máme funkci volal 4 pro vás, který bere pole o velikosti 1000. Ale pak zřejmě není ve skutečnosti vypadat na to-- není opravdu jedno, co je uvnitř ní, z této matice. Vždy jen vrátí čtyři. Tak, že algoritmus, a to navzdory skutečnosti, že trvá 1000 prvky nemusí dělat něco s nimi. Jen vrátí čtyři. Je to vždycky jeden krok. 

Ve skutečnosti, se přidají 2 nums--, které jsme neviděli za well-- právě zpracovává dvě celá čísla. Není to jediný krok. Ve skutečnosti je to pár kroků. Získáte, dostanete b, je přidáte dohromady, a vy výstupní výsledky. Takže je to 84 kroků. Ale je to vždy konstantní, ohledu na to, a nebo b. Musíte se dostat, dostat b, přidejte je dohromady, výstup výsledek. Takže to je konstantní algoritmus. 

Zde je příklad lineární čas algorithm-- algoritmus, který gets--, který bere jeden další krok, případně jako vaše vstupní roste o 1. Takže, řekněme, že hledáme počet 5 uvnitř pole. Možná budete v situaci, kdy můžete najít to docela brzy. Ale můžete také mít situace, kdy ji může být poslední prvek pole. V poli o velikosti 5, pokud hledáme číslo 5. Chtělo by to 5 kroků. A ve skutečnosti, představte si, že je tu Není 5 kdekoli v tomto poli. Stále ve skutečnosti se podívat na každý prvek pole za účelem zjištění, zda 5 je tam. 

Takže v nejhorším případě, což je to, že prvek je poslední v poli nebo neexistuje vůbec. Stále se podívat na všechny z n prvků. A tak tento algoritmus běží v lineárním čase. Můžete potvrdit, že by extrapolace trochu tím, že říká, kdybychom měli 6-prvek pole a jsme hledali na číslo 5, to může trvat 6 kroků. Pokud máme 7-prvek pole a hledáme číslo 5. To by mohlo trvat 7 kroků. Jak jsme přidat ještě jeden prvek do našeho pole, trvá ještě jeden krok. To je lineární algoritmus v nejhorším případu. 

Pár rychlých otázek pro vás. Co je to, co je runtime-- nejhorší případ runtime z tohoto konkrétního fragmentu kódu? Takže mám 4 smyčku zde, který běží od j rovná 0, celou cestu až do m. A to, co jsem viděl tady, je to, že tělo smyčky probíhá v konstantním čase. Takže používat terminologii jsme již mluvili, co about-- by byl nejhorší runtime tohoto algoritmu? Vezměte chvilku. Vnitřní část smyčky běží v konstantním čase. A vnější část smyčka bude běžet m-krát. Takže to, co je tady nejhorší případ runtime? Věděli jste asi velký-O M? Vy byste mít pravdu. 

Jak se asi jiný? Tentokrát máme smyčka uvnitř smyčky. Máme vnější smyčky která běží od nuly do str. A máme vnitřní smyčku, která se spouští od nuly do p, a vnitřní části, které, Prohlašuji, že orgán pro smyčka běží v konstantním čase. Takže co je nejhorší runtime z tohoto konkrétního fragmentu kódu? No, zase máme Vnější smyčka, která se spouští p krát. A každý time-- iterace této smyčky, spíše. Máme vnitřní smyčky že také běží p krát. A pak uvnitř to, že je tu konstantní time-- malý úryvek tam. 

Takže pokud máme vnější smyčka, která běží p časy uvnitř které je vnitřní smyčky, která běží p times-- to, co je nejhorší případ runtime tento fragment kódu? Věděli jste asi velký-O P na druhou? 

Jsem Doug Lloyd. To je CS50.