[Powered by Google Translate] Pravděpodobně jste slyšeli lidé mluví o rychlý, nebo efektivní algoritmus pro provádění váš konkrétní úkol, ale co přesně to znamená pro algoritmus, který bude rychle, nebo účinný? No, to nemluvím o měření v reálném čase, jako sekundách nebo minutách. To je proto, že počítačový hardware a software radikálně lišit. Můj program může běžet pomaleji než vy, protože jsem běží to na starším počítači, nebo proto, že jsem se náhodou hrát online videohru současně, což je hogging všechny mé paměti, nebo bych mohl být spuštěn můj program prostřednictvím různých software který komunikuje se strojem jinak na nízké úrovni. Je to jako srovnávat jablka s hruškami. Jen proto, že můj pomalejší počítač trvá déle než vaše vrátit odpověď neznamená, že budete mít více efektivní algoritmus. 

Takže, protože nemůžeme přímo porovnávat runtime programů v sekundách nebo minutách, jak jsme tyto 2 různé algoritmy bez ohledu na jejich hardwarové nebo softwarové prostředí? Chcete-li vytvořit více jednotný způsob měření efektivity algoritmů, počítačové vědci a matematici vymysleli koncepty pro měření asymptotickou složitost programu a zápis názvem "Big Ohnotation" pro popis tohoto. Formální definice je to, že funkce f (x) běží na pořadí g (x) zda existuje nějaký (x) hodnoty, x ₀ a nějaká konstanta, C, pro které f (x) je menší než nebo roven že konstantní časy g (x) pro všechny x větší než x ₀. 

Ale neboj se pryč formální definici. Co to vlastně znamená v méně teoretických pojmech? No, je to v podstatě způsob, jak analyzovat Jak rychle programu runtime roste asymptoticky. To je, jak velikost vašich vstupů zvyšuje směrem k nekonečnu, řekněme, že jste třídění pole o velikosti 1000 ve srovnání s řadou velikostí 10. Jak runtime vašeho programu růst? Představte si například, počítání počtu znaků v řetězci nejjednodušší způsob, jak  pěšky přes celý řetězec Letter podle písmen a přidáním 1 k přepážce pro každého znaku. Tento algoritmus je řekl, aby spuštění v lineárním čase s ohledem na počet znaků, "N" v řetězci. Stručně řečeno, to běží v O (n). Proč to je? No, použití tohoto přístupu, čas potřebný přejít celý řetězec je úměrná počtu znaků. Počítání znaků v 20-znakový řetězec bude trvat dvakrát tak dlouho, jak bude potřeba počítat znaky v 10-znakový řetězec, protože se musíte podívat na všechny znaky a každá postava má stejné množství času podívat se na. Jak zvýšit počet znaků, runtime zvýší lineárně s délkou vstupního. 

Teď si představte, když se rozhodnete, že lineární čas, O (n), prostě není dostatečně rychlý pro vás? Možná jste ukládání obrovské řetězce, a můžete si dovolit čas navíc, že ​​by trvat přejít všechny jejich znaky počítání jeden po-one. Takže, jste se rozhodli zkusit něco jiného. Co když se stane již uložit počet znaků v řetězci, tedy v proměnné s názvem "len" na počátku programu, ještě předtím, než uloží úplně první znak ve vašem řetězci? Pak vše, co budu muset udělat, zjistit délku řetězce, je zjistit, co hodnota proměnné je. Neměla byste se podívat na řetězec sám vůbec, a přístup k hodnotu proměnné jako len se považuje asymptoticky konstantní čas operace, nebo O (1). Proč to je? No, vzpomenout si, co asymptotická složitost znamená. Jak se runtime změna, jako je velikost z vašich vstupů roste? 

Řekněme, že jste se snažili dostat počet znaků v řetězci větší. No, to by nebylo jedno, jak velký uděláte řetězec, dokonce milionů znaků, vše, co budu muset udělat, najít aktivní délku struny s tímto přístupem, je přečíst hodnotu proměnné len, které jste již provedena. Vstupní délka, to znamená, že délka řetězce, který se snažíte najít, nemá vliv vůbec, jak rychle váš program běží. Tato část programu by běžet stejně rychle na jeden řetězec znaků a tisíc znakový řetězec, a to je důvod, proč by tento program být odkazoval se na jako běh v konstantním čase s ohledem na vstupní velikost. 

Samozřejmě, je tu nevýhodu. Můžete strávit další paměť v počítači ukládání proměnné a více času to bude trvat dělat skutečné uložení proměnné, ale bod stále stojí, zjistit, jak dlouho bude řetězec byl nezávisí na délce řetězce vůbec. Takže, to běží v O (1), nebo konstantní čas. To rozhodně nemusí znamenat, že váš kód běží v 1 kroku, ale bez ohledu na to, kolik kroků je to, pokud nemění s velikostí vstupů, je to stále asymptoticky konstanta, která se představuje jako O (1). 

Jak asi tušíte, existuje mnoho různých velkých O běhové měřit algoritmy s. O (n) ² algoritmy jsou asymptoticky pomalejší než algoritmy O (n). To znamená, že jako počet prvků (n) roste, nakonec O (n) ² algoritmy budou mít více času než O (n) algoritmy pro spuštění. To neznamená, O (n) algoritmy vždy běžet rychleji než O (N) ² algoritmů, a to i ve stejném prostředí, na stejném hardwaru. Možná, že pro malé vstupní velikosti,  O (n) ² algoritmus ve skutečnosti může pracovat rychleji, ale, nakonec, jako vstupní velikosti zvyšuje k nekonečnu, O (n) ² algoritmu runtime nakonec zastínit runtime O (n) algoritmu. Stejně jako nějaké kvadratické matematické funkce  nakonec předběhnou všechny lineární funkce, bez ohledu na to, kolik z hlavy kdo lineární funkci začíná s. Pokud pracujete s velkým množstvím dat, algoritmy, které pracují v O (n) ² doba se může opravdu skončit zpomalení programu, ale pro malé vstupní velikosti, pravděpodobně ani nevšimnete. 

Další asymptotická složitost je, logaritmické čas, O (log n). Příkladem algoritmu, který běží tak rychle je klasický binární vyhledávací algoritmus, pro zjištění prvku v již tříděném seznamu prvků. 

Pokud nevíte, co binární vyhledávací dělá, Vysvětlím ti to pro tebe opravdu rychle. Řekněme, že hledáte pro číslo 3 v tomto poli celých čísel. Zdá se na střední prvku matice a ptá se: "Je element chci větší, rovna nebo menší než toto?" Pokud je to stejné, pak skvělé. Našli jste prvek, a máte hotovo. Pokud je to větší, pak víte, že prvek musí být v pravé části pole, a můžete se podívat na, že v budoucnu, a, pokud je to menší, pak víte, že má být na levé straně. Tento proces se opakuje s menší velikosti pole až do dosažení správné prvek nalezen. 

Tento výkonný algoritmus snižuje velikost pole na polovinu každé operaci. Takže, najít element v tříděném poli o velikosti 8, nejvýše (log ₂ 8), nebo 3 z těchto operací, kontrolu střední prvek, pak dělení pole na polovinu bude nutné, vzhledem k tomu, pole o velikosti 16 má (log ₂ 16), nebo 4 operace. To je pouze 1 více provoz na dvojnásobek velikosti pole. Zdvojnásobení velikosti pole zvyšuje runtime pouze 1 kus tohoto kódu. Opět, kontrola prostřední prvek seznamu, pak rozdělení. Takže, je to údajně v provozu v logaritmickém čase, O (log n). Ale počkejte, vy říkáte, není to závisí na tom, kde v seznamu prvek, který hledáte, je? Co když první prvek se podíváte na stane, že je správná? Pak, to trvá jen 1 operaci, bez ohledu na to, jak velký je seznam. 

No, to je důvod, proč počítačoví odborníci mají více pojmů pro asymptotické složitosti, které odrážejí nejlepší případ a nejhorší vystoupení algoritmu. Více správně, horní a dolní hranice na běhu. V nejlepším případě pro binární vyhledávání, náš prvek přímo tam uprostřed, a dostanete ho v konstantním čase, bez ohledu na to, jak velká zbytek pole je. Symbol použitý pro toto je Ω. Takže, je tento algoritmus říká běžet Ω (1). V nejlepším případě, že najde prvek rychle, bez ohledu na to, jak velký je pole, ale v nejhorším případě, má provést (log n) roztřepené kontroly z pole najít ten správný prvek. Nejhorší horní hranice jsou odkazoval se na s velkým "O", které už znáte. Takže, je to O (log n), ale Ω (1). 

Lineární vyhledávání, naopak, , ve kterém se projdete každý prvek pole najít ten, který chcete, je v nejlepším případě Ω (1). Opět, první prvek, který chcete. Takže, nezáleží na tom, jak velký je pole. V nejhorším případě, je to poslední prvek v poli. Takže, budete muset projít všechny n prvků v poli najít, jako když hledali 3. Takže, to běží v O (n) čas , protože je to přímo úměrná počtu prvků v poli. 

A ještě jedna použitý symbol je Θ. To může být použit k popisu algoritmů, kde je nejlepší a nejhorší případy jsou stejné. To je případ string-length algoritmů jsme hovořili o dříve. To znamená, že pokud uložíme ji do proměnné před uložíme řetězec a přístup později v konstantním čase. Bez ohledu na to, jaký počet jsme skladování v této proměnné, budeme se muset podívat na to. Nejlepší věc je, že jsme se na to podívat a najít délku řetězce. Takže Ω (1) nebo best case konstantní čas. Nejhorší případ je, Podíváme se na to a najít délku řetězce. Takže, O (1), nebo konstantní čas v nejhorším případě. Takže, protože nejlepší věci a nejhorší případy jsou stejné, Tento lze říci, že běží v Θ (1), je čas. 

Stručně řečeno, máme dobré způsoby, jak uvažovat o účinnosti kódy aniž by věděl něco o real-světového času kdy přijmou běžet, která je ovlivněna spoustou vnějších faktorů, včetně odlišného hardwaru, softwaru, nebo specifika vašeho kódu. Také, to nám umožňuje rozum, dobře o tom, co se stane kdy velikost vstupů zvyšuje. 

Pokud běží v O (n) ² algoritmus, nebo ještě hůře, O (2 ⁿ) algoritmus, jeden z nejrychleji rostoucích typů, budete opravdu začnete si uvědomovat, zpomalení když začnete pracovat s velkým množstvím dat. 

To je asymptotická složitost. Díky.