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