>> 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.