Časová efektivita programu podle odpovídajícího algoritmu. Koncepce složitosti a účinnosti algoritmů a datových struktur. Co uděláme s přijatým materiálem?

Účinnost algoritmu je vlastnost algoritmu, která je spojena s výpočetními zdroji používanými algoritmem. Algoritmus musí být analyzován, aby se určily zdroje vyžadované algoritmem. Účinnost algoritmu lze považovat za analogickou s produktivitou výroby opakujících se nebo kontinuálních procesů.

Abychom dosáhli maximální efektivity, chceme snížit spotřebu zdrojů. Různé zdroje (jako je čas a paměť) však nelze přímo porovnávat, takže který ze dvou algoritmů je považován za efektivnější, často závisí na tom, který faktor je důležitější, jako je požadavek na vysokou rychlost, minimální využití paměti nebo jiné měřítko. účinnost.

Vezměte prosím na vědomí, že tento článek NE o optimalizaci algoritmů, o které pojednávají články optimalizace programu, optimalizace kompilátoru, optimalizace cyklu, optimalizátor objektového kódu, a tak dále. Samotný termín „optimalizace“ je zavádějící, protože vše, co lze udělat, spadá pod „zlepšení“.

Pozadí

Důležitost efektivity s důrazem na dobu provedení zdůraznila Ada Lovelace v roce 1843 ohledně mechanického analytického motoru Charlese Babbage:

„Téměř ve všech výpočtech existuje velký výběr možných konfigurací pro úspěšné dokončení procesu a různé konvence by měly ovlivnit výběr pro účely provádění výpočtu. Podstatné je zvolit takovou konfiguraci, která povede k minimalizaci času potřebného k provedení výpočtu.“

Rané elektronické počítače byly velmi omezené jak v rychlosti, tak v paměti. V některých případech bylo zjištěno, že existuje kompromis mezi časem a pamětí, kdy úkol musí buď použít velké množství paměti k dosažení vysoké rychlosti, nebo použít pomalejší algoritmus, který používá malé množství pracovní paměti. V tomto případě byl použit nejrychlejší algoritmus, pro který stačila dostupná paměť.

Moderní počítače jsou mnohem rychlejší než ty rané počítače a mají mnohem více paměti (gigabajty místo kilobajtů). Donald Knuth však zdůrazňuje, že účinnost zůstává důležitým faktorem:

"Ve zavedených inženýrských disciplínách je 12% zlepšení snadno dosažitelné a nikdy nebylo považováno za neúměrné a věřím, že totéž by mělo platit v programování."

Posouzení

Algoritmus je považován za účinný, pokud je jeho spotřeba zdrojů (nebo náklady na zdroje) na nebo pod nějakou přijatelnou úrovní. Zhruba řečeno, "přijatelné" zde znamená "algoritmus poběží po rozumnou dobu na dostupném počítači." Protože od 50. let minulého století došlo k výraznému nárůstu výpočetního výkonu a dostupné paměti počítačů, nebyla současná „přijatelná úroveň“ přijatelná ani před 10 lety.

Výrobci počítačů pravidelně uvolňují nové modely, často výkonnější. Náklady na software mohou být poměrně vysoké, takže v některých případech je snazší a levnější získat lepší výkon zakoupením rychlejšího počítače, který je kompatibilní s vaším stávajícím počítačem.

Existuje mnoho způsobů, jak měřit zdroje používané algoritmem. Dvě nejpoužívanější měření jsou rychlost a použitá paměť. Další měření mohou zahrnovat přenosovou rychlost, dočasné využití disku, dlouhodobé využití disku, spotřebu energie, celkové náklady na vlastnictví, dobu odezvy na externí signály a tak dále. Mnoho z těchto měření závisí na velikosti vstupních dat algoritmu (tedy na veličinách vyžadujících zpracování dat). Měření mohou také záviset na způsobu, jakým jsou data prezentována (například některé třídicí algoritmy fungují špatně na již setříděných datech nebo když jsou data řazena v opačném pořadí).

V praxi existují další faktory, které ovlivňují účinnost algoritmu, jako je požadovaná přesnost a/nebo spolehlivost. Jak je vysvětleno níže, způsob implementace algoritmu může mít také významný vliv na skutečný výkon, ačkoli mnoho aspektů implementace je otázkami optimalizace.

Teoretická analýza

V teoretické analýze algoritmů je běžnou praxí odhadovat složitost algoritmu v jeho asymptotickém chování, to znamená odrážet složitost algoritmu jako funkci velikosti vstupu. n Používá se notace velkého O. Tento odhad je obecně poměrně přesný pro velké n, ale při malých hodnotách může vést k nesprávným závěrům n(Tedy bublinové třídění, které je považováno za pomalé, může být rychlejší než rychlé třídění, pokud potřebujete seřadit pouze několik prvků).

Označení	název	Příklady
O(1) (\displaystyle O(1)\,)	trvalý	Určení, zda je číslo sudé nebo liché. Použití vyhledávací tabulky konstantní velikosti. Pomocí vhodné hashovací funkce vyberte prvek.
O (log ⁡ n) (\displaystyle O(\log n)\,)	logaritmický	Hledání prvku v seřazeném poli pomocí binárního vyhledávání nebo vyváženého stromu, podobně jako operace na binomické haldě.
O(n) (\displaystyle O(n)\,)	lineární	Hledání prvku v netříděném seznamu nebo nevyváženém stromu (nejhorší případ). Přidání dvou n-bitová čísla pomocí přenosu end-to-end.
O (n log ⁡ n) (\displaystyle O(n\log n)\,)	kvazilineární, logaritmicky lineární	Počítejte rychlou Fourierovu transformaci, heapsort, quicksort (nejlepší a průměrný případ), slučovací třídění
O (n 2) (\displaystyle O(n^(2))\,)	náměstí	Násobení dvěma n-ciferná čísla pomocí jednoduchého algoritmu, bublinové třídění (nejhorší případ), Shell sort, quicksort (nejhorší případ), výběrové třídění, vkládání
O (c n) , c > 1 (\displaystyle O(c^(n)),\;c>1)	exponenciální	Nalezení (přesného) řešení problému obchodního cestujícího pomocí dynamického programování. Určení, zda jsou dva logické příkazy ekvivalentní pomocí vyčerpávajícího vyhledávání

Ověřovací testy: Měření výkonu

Pro nové verze softwaru nebo pro srovnání s konkurenčními systémy se někdy používají benchmarky k porovnání relativního výkonu algoritmů. Pokud je například uvolněn nový třídicí algoritmus, lze jej porovnat s předchůdci, aby bylo zajištěno, že algoritmus bude na známá data přinejmenším stejně účinný jako ostatní. Testy výkonu mohou uživatelé použít k porovnání produktů různých výrobců, aby vyhodnotili, který produkt bude nejlépe vyhovovat jejich požadavkům z hlediska funkčnosti a výkonu.

Některé srovnávací testy poskytují srovnávací analýzu různých kompilačních a interpretačních jazyků, jako je Roy Longbottom's PC Benchmark Collection a Srovnávací hra počítačového jazyka porovnává výkon implementací typických úloh v některých programovacích jazycích.

Problémy s implementací

Problémy s implementací mohou také ovlivnit skutečný výkon. To zahrnuje volbu programovacího jazyka a způsobu, jakým je algoritmus skutečně kódován, volbu překladače pro zvolený jazyk nebo použitých možností kompilátoru a dokonce i použitý operační systém. V některých případech může být jazyk implementovaný jako interpret výrazně pomalejší než jazyk implementovaný jako kompilátor.

Existují další faktory, které mohou ovlivnit časování nebo využití paměti, které jsou mimo kontrolu programátora. To zahrnuje zarovnání dat, detailování, garbage collection , paralelismus na úrovni instrukcí a volání podprogramů .

Některé procesory mají schopnost provádět vektorové operace, což umožňuje jedné operaci zpracovat více operandů. Může nebo nemusí být snadné používat takové funkce na úrovni programování nebo kompilace. Algoritmy navržené pro sekvenční výpočty mohou vyžadovat kompletní přepracování, aby vyhovovaly paralelním výpočtům.

Další problém může nastat s kompatibilitou procesoru, kde mohou být instrukce implementovány odlišně, takže instrukce na některých modelech mohou být na jiných modelech relativně pomalejší. To může být problém pro optimalizační kompilátor.

Měření využití zdrojů

Míry se obvykle vyjadřují jako funkce velikosti vchodu n.

Dva nejdůležitější rozměry jsou:

Čas: Jak dlouho trvá algoritmus na CPU.
Paměť: Kolik pracovní paměti (obvykle RAM) je potřeba pro algoritmus. To má dva aspekty: velikost paměti pro kód a velikost paměti pro data, se kterými kód pracuje.

Pro počítače napájené bateriemi (jako jsou notebooky) nebo pro velmi dlouhé/velké výpočty (jako jsou superpočítače) je zajímavý jiný druh měření:

Přímá spotřeba energie: Energie potřebná k provozu počítače.
Nepřímá spotřeba energie: Energie potřebná pro chlazení, osvětlení atd.

V některých případech jsou zapotřebí jiná, méně běžná měření:

Velikost ozubeného kola: Limitujícím faktorem může být šířka pásma. Ke snížení objemu přenášených dat lze použít kompresi. Zobrazení grafiky nebo obrázku (jako je logo Google) může vést k přenosu desítek tisíc bajtů (v tomto případě 48 kB). Porovnejte to s přenosem šesti bajtů ve slově „Google“.
Externí paměť: Požadovaná paměť na disku nebo jiném externím úložném zařízení. Tuto paměť lze použít pro dočasné uložení nebo pro budoucí použití.
Doba odezvy: Toto nastavení je důležité zejména pro aplikace v reálném čase, kde musí počítač rychle reagovat na vnější události.
Celková cena vlastnictví: Parametr je důležitý, když je zamýšlen pro provedení jediného algoritmu.

Čas

Teorie

Tento typ testu také výrazně závisí na volbě programovacího jazyka, kompilátoru a jeho možnostech, takže porovnávané algoritmy musí být implementovány za stejných podmínek.

Paměť

Tato část se zabývá použitím hlavní paměti (často RAM) potřebné pro algoritmus. Stejně jako u analýzy načasování výše se obvykle používá analýza algoritmu prostorová složitost algoritmu odhadnout požadovanou runtime paměť jako funkci vstupní velikosti. Výsledek je obvykle vyjádřen jako "O" velké.

Existují čtyři aspekty využití paměti:

Množství paměti potřebné k uložení kódu algoritmu.
Množství paměti potřebné pro vstupní data.
Množství paměti požadované pro jakýkoli výstup (některé algoritmy, například řazení, často mění uspořádání vstupu a nevyžadují další paměť pro výstup).
Množství paměti požadované výpočetním procesem během výpočtu (to zahrnuje pojmenované proměnné a jakýkoli zásobníkový prostor potřebný pro volání podprogramů, což může být významné při použití rekurze).

Rané elektronické počítače a domácí počítače měly relativně malou kapacitu pracovní paměti. V roce 1949 měl EDSAC maximální pracovní paměť 1024 17bitových slov a v roce 1980 byl vydán Sinclair ZX80 s 1024 bajty pracovní paměti.

Moderní počítače mohou mít relativně velké množství paměti (možná gigabajty), takže komprimování paměti používané algoritmem do určitého daného množství paměti je méně nutné než dříve. Nicméně existence tří různých kategorií paměti je významná:

Cache (často statická RAM) – běží rychlostí srovnatelnou s CPU
Hlavní fyzická paměť (často dynamická RAM) – běží o něco pomaleji než CPU
Virtuální paměť (často na disku) – vytváří iluzi obrovské paměti, ale pracuje tisíckrát pomaleji než RAM.

Algoritmus, jehož požadovaná paměť se vejde do mezipaměti počítače, je mnohem rychlejší než algoritmus, který se vejde do hlavní paměti, která bude zase mnohem rychlejší než algoritmus využívající virtuální prostor. Vše komplikuje skutečnost, že některé systémy mají až tři úrovně mezipaměti. Různé systémy mají různé množství těchto typů paměti, takže paměťový efekt na algoritmus se může mezi jednotlivými systémy výrazně lišit.

V počátcích elektronických počítačů, pokud se algoritmus a jeho data nevešly do hlavní paměti, nemohl být použit. V dnešní době používání virtuální paměti poskytuje obrovskou paměť, ale za cenu výkonu. Pokud se algoritmus a jeho data vejdou do mezipaměti, lze dosáhnout velmi vysoké rychlosti, takže minimalizace požadované paměti pomáhá minimalizovat čas. Algoritmus, který se zcela nevejde do mezipaměti, ale poskytuje lokalita odkazů, může pracovat poměrně rychle.

Příklady efektivních algoritmů

Kritika současného stavu programování

Programy se stávají pomalejšími rychleji než počítače.

May uvádí:

V rozšířených systémech může snížení provádění instrukcí na polovinu zdvojnásobit životnost baterie a velká data poskytují příležitost pro lepší algoritmy: Snížení počtu operací z N x N na N x log(N) má silný účinek pro velké N... Pro N = 30 miliard, tyto změny jsou podobné 50 letům technologických vylepšení.

Soutěž o nejlepší algoritmus

Následující soutěže vyzývají k účasti na vývoji nejlepších algoritmů, jejichž kvalitativní kritéria určují porotci:

viz také

Aritmetické kódování je druh entropického kódování s variabilní délkou kódu pro efektivní kompresi dat
Asociativní pole je datová struktura, kterou lze při použití zefektivnit stromy PATRICIA nebo Judy pole
Performance test - metoda měření komparativního času provádění v určitých případech
Nejlepší, nejhorší a průměrný případ- konvence pro odhadování doby provádění pro tři scénáře
Binární vyhledávání je jednoduchá a efektivní technika pro vyhledávání v seřazeném seznamu
Pobočkový stůl

Cíle a cíle přednášky: úvod do metod analýzy složitosti a účinnosti algoritmů a datových struktur

Hlavní problémy: experimentální a analytická analýza účinnosti algoritmů.

Klasický výrok N. Wirtha „Dobrý program je jednota dobře promyšleného algoritmu a efektivních datových struktur.“

Analýza algoritmů
Pojmy „algoritmus a datové struktury“ jsou v oblasti výpočetní techniky stěžejní, ale aby bylo možné nazvat určité datové struktury a algoritmy „vysoce kvalitními a účinnými“, musí být použity přesné techniky pro jejich analýzu. Jako přirozené kritérium kvality je přirozené vyzdvihnout za prvé dobu provedení. Důležité je také množství vynaložené paměti a diskového prostoru, rychlost přístupu k datům (efektivita datové struktury). Pozornost je třeba věnovat i spolehlivosti a spolehlivosti rozhodnutí, jejich stabilitě.

Algoritmus by neměl být vázán na konkrétní implementaci. Vzhledem k rozmanitosti používaných programovacích nástrojů mohou algoritmy, které se liší v implementaci, poskytovat výsledky, které se liší v účinnosti.

Doba provádění algoritmu nebo operace na datové struktuře závisí zpravidla na řadě faktorů. Nejjednodušší způsob, jak určit čas potřebný k provedení algoritmu, je změřit čas před a po spuštění algoritmu.

Je však třeba mít na paměti, že tato metoda odhadu času není přesná; především je třeba si uvědomit, že v moderních operačních systémech lze paralelně provádět několik úloh a provedení testovacího případu lze kombinovat s jinými typy. činnosti. Dále je třeba chápat, že stabilní závislosti lze dosáhnout pouze prováděním opakovaných testů, jinak v důsledku vlivu na konečný výsledek práce náhodných faktorů v závislosti na specifikách počátečních dat a dalších faktorech, provedení čas algoritmu bude také náhodná veličina. Při provádění výzkumu je nutné spustit algoritmus s jinou sadou počátečních dat, obvykle jsou data sama generována náhodně, takže kvůli různým sadám dat se bude lišit i strávený čas.

Jakmile je získána sada odhadů, lze sestavit a aproximovat graf.

Taková analýza by se měla používat vždy při použití netriviálních algoritmů, je to podobné jako doporučení vyvinout aplikaci, která k ladění nepoužívá zkušební sadu několika desítek záznamů nebo prvků, ale skutečná data v plném rozsahu, čímž se vyhnete úpravám nebo dokonce úplné přepracování dat algoritmu nebo struktur, pokud se následně ukáží jako nepraktické. Se sadou experimentálních výsledků můžete provádět interpolaci a extrapolaci a určit chování algoritmu v reálných podmínkách.

Obecně lze říci, že doba provádění algoritmu nebo metody datové struktury se zvyšuje s rostoucí velikostí zdrojových dat, i když to také závisí na typu dat, i když je velikost stejná. Doba provádění navíc závisí na hardwaru (procesor, taktovací frekvence, velikost paměti, místo na disku atd.) a softwaru (operační prostředí, programovací jazyk, kompilátor, interpret atd.), pomocí kterého se implementace, kompilace provádí a provedení algoritmu. Například, pokud jsou všechny ostatní věci stejné, doba provádění algoritmu pro určité množství zdrojových dat bude kratší při použití výkonnějšího počítače nebo při zápisu algoritmu jako programu ve strojovém kódu ve srovnání s jeho prováděním virtuálním strojem. interpretovat to do bajtkódů.

Závěr je, že provádění empirické analýzy algoritmů není skutečně spolehlivé. Hlavní nevýhody lze zredukovat na následující tři body:

1) experimenty lze provádět pouze s použitím omezeného souboru počátečních dat; výsledky získané pomocí jiné sady se neberou v úvahu.

2) pro porovnání účinnosti dvou algoritmů je nutné, aby experimenty k určení doby jejich provádění byly prováděny na stejném hardwaru a softwaru;
3) pro experimentální studium doby provádění algoritmu je nutné provést jeho implementaci a provedení.

Dostáváme se tedy k potřebě používat obecné analytické metody pro analýzu algoritmů, které umožňují:

1) zohledňuje různé typy vstupních dat;

2) umožňuje vyhodnotit relativní účinnost libovolných dvou algoritmů bez ohledu na hardware a software;

3) lze provést podle popisu algoritmu bez jeho přímé implementace nebo experimentů.

Podstatou obecné analýzy je, že funkce f=f(n1, .., nm) je přiřazena určitému algoritmu. V nejjednodušší podobě je funkcí jedné proměnné n1 – množství vstupních dat. Mohou však existovat i další proměnné – například přesnost výpočtu nebo jeho spolehlivost. K určení, zda je určité číslo prvočíslo v případě velkých čísel (délka binární reprezentace je více než 200 bitů), se tedy používá pravděpodobnostní metoda, jejíž spolehlivost lze měnit. Nejznámější funkce jsou lineární, mocninné a logaritmické. Proto byste si měli udělat čas a zapamatovat si základy práce s nimi.

Při konstrukci algoritmů nastává první fáze s použitím nikoli programovacího jazyka, ale popisu v lidském jazyce. Takové popisy nejsou programy, ale zároveň jsou strukturovanější než běžný text. Zejména popisy „na vysoké úrovni“ kombinují přirozený jazyk a běžné struktury programovacího jazyka, díky čemuž jsou přístupné a zároveň informativní. Takové popisy usnadňují analýzu datové struktury nebo algoritmu na vysoké úrovni. Takové popisy se obvykle nazývají pseudokód. Je třeba také poznamenat, že pseudokód je pro analýzu často užitečnější než kód ve specifickém programovacím jazyce.

Někdy je potřeba prokázat určitá tvrzení ve vztahu k určité datové struktuře nebo algoritmu. Například musíte prokázat správnost a rychlost provádění algoritmu. K striktnímu dokazování tvrzení je nutné používat matematický jazyk, který poslouží jako důkaz či zdůvodnění tvrzení. Existuje několik jednoduchých způsobů, jak to dokázat.

Někdy jsou výroky zapsány v zobecněné podobě: „Množina s obsahuje prvek x s vlastností v. K prokázání tohoto tvrzení stačí uvést příklad x „patří“ do s, které má tuto vlastnost. V takto zobecněné formě se zpravidla píší nepravděpodobné výroky, například: „Každý prvek x množiny s má vlastnost P“. Abychom dokázali mylnost tohoto tvrzení, stačí jednoduše uvést příklad: x „patří“ do s, které nemá vlastnost P. V tomto případě bude prvek x fungovat jako protipříklad.

Příklad: Uvádí se, že jakékoli číslo ve tvaru 2^n - 1 je prvočíslo, pokud n je celé číslo větší než 1. Tvrzení je nepravdivé.

Důkaz: Abyste někomu dokázali, že se mýlí, musíte najít protipříklad.

Toto je protipříklad: 2^4 - 1 = 15, 15= 3 * 5.

Existuje další způsob, založený na důkazu kontradikcí (pomocí negace). Hlavními metodami jsou v tomto případě kontrapozice a rozpor. Použití kontrastních metod je podobné zrcadlení: abychom dokázali, že „pokud je x pravdivé, pak je y pravdivé“, budeme tvrdit opak, „pokud je y nepravdivé, pak je x nepravdivé“. Z logického hlediska jsou tato tvrzení totožná, ale vhodnější je druhý výraz, který je kotropozicí prvního.

Příklad: Je-li a*b liché číslo, pak a je liché nebo b je liché.

Důkaz: k prokázání tohoto tvrzení zvažte kontrapozici: „Je-li a sudé číslo a b liché, pak a*b je sudé. Nechť a = 2*x, pro nějaké celé číslo x. Pak a*b = 2*i*b, a proto je součin a*b sudý.

Při použití metod důkazu kontradikcí je užitečné použít logiku.

A nebo b = vyžaduje provedení a nebo b, nebo obou a a b současně.
. a a b = vyžaduje, aby a a b byly provedeny současně.
. a xor b = vyžaduje provedení a, ale ne b, nebo b, ale ne a.

Při použití metody kontradikce k prokázání, že tvrzení q je pravdivé, se nejprve předpokládá, že q je nepravdivé, a pak se ukáže, že takový předpoklad vede k rozporu (například 2 * 2<>4). Když jsme došli k takovému rozporu, můžeme tvrdit, že situace, ve které je q nepravdivé, neexistuje, a proto je q pravdivé.

Ve většině případů používají příkazy o použití času nebo prostoru provádění programu celočíselný parametr n (představující „velikost“ problému). Když pak formulujeme výrok x(n), pak pro množinu hodnot n jsou takové výroky ekvivalentní. Protože toto tvrzení platí pro „nekonečnou“ množinu čísel, není možné poskytnout vyčerpávající přímý důkaz. V takových situacích se používají indukční metody. Metoda indukce je založena na skutečnosti; že pro libovolné n > 1. Existuje konečná posloupnost akcí, která začíná něčím, o čem je známo, že je pravdivá, a nakonec vede k důkazu, že q(n) je pravdivé. Důkaz indukcí tedy začíná tvrzením, že q(n) platí pro n=1,2,3 atd. až do nějaké konstantní k. Dále dokážeme, že další „krok“ indukcí q(n+1), q(n+2) platí i pro n > k.

Při analýze algoritmů, výpočtu počtu operací a doby jejich provádění by se nemělo brát v úvahu „malé detaily“, konstantní faktory a konstanty by měly být zanedbány. V praxi se používá koncept velké funkce O. předpokládejme, že existují dvě funkce f(n) a g(n), předpokládá se, že f(n)<= O(g(n)) , т.е. функция О ограничивает сверху значения функции f, начиная с n=n0.

Například algoritmus pro počítání počtu prvků rovný nule v poli je popsán pomocí O(n), kde n je počet prvků.

1) 20n3+7,2n2-21,78n + 5 je popsáno jako O(n3)

2)xn-2 + a(0) je popsán jako O(xn).

2) 3*log(n) + log(log(n)) je popsáno jako O(log(n)).

3) 2100 je popsáno jako O(1)

4) 5/n je popsán jako O(l/n).

Vezměte prosím na vědomí, že funkce o(n) omezuje funkci cílové časové náklady shora, ale vždy byste se měli snažit zvolit takovou funkci O(n), aby byla maximální přesnost.

Nejznámější funkce O ve vzestupném pořadí:

Při použití asymptotické analýzy buďte opatrní, že když používáte zápis O, často zanedbáváte konstantní faktory a konstanty sčítání. Pokud je však tato hodnota dostatečně velká, ačkoli je tvar funkce O(1) výhodnější než algoritmus popsaný funkcí O(n), je to samozřejmě druhý algoritmus, který najde praktické uplatnění.

V závislosti na typu funkce f(n) se rozlišují následující třídy složitosti algoritmů.

Třídy složitosti algoritmu v závislosti na funkci složitosti
Zobrazit f(n)	Charakteristika třídy algoritmů
	Většina instrukcí pro většinu funkcí se provádí jednou nebo vícekrát. Pokud všechny instrukce v programu mají tuto vlastnost, pak je doba provádění programu konstantní.
log N	Když je doba provádění programu logaritmická, program se zpomaluje se zvyšujícím se N. Takové doby provádění jsou obvykle spojeny s programy, které redukují velký problém na sadu menších dílčích problémů, čímž se velikost problému snižuje o nějaký konstantní faktor v každém kroku. Změna základu nemá velký vliv na změnu hodnoty logaritmu: n
N	Když je doba provádění programu lineární, obvykle to znamená, že každý vstupní prvek prochází malým zpracováním.
N log N	Doba běhu úměrná N log N nastane, když algoritmus vyřeší problém tak, že jej rozdělí na menší dílčí problémy, vyřeší je nezávisle a pak řešení zkombinuje.
N 2	Když je doba běhu algoritmu kvadratická, je užitečný pro praktické použití při řešení relativně malých problémů. Kvadratická doba provádění se obvykle objevuje v algoritmech, které zpracovávají všechny páry datových položek (možná ve dvojitě vnořené smyčce).
N 3	Podobný algoritmus, který zpracovává trojice datových prvků (případně ve smyčce s trojitým vnořením), má kubickou dobu provádění a je prakticky použitelný pouze pro malé problémy.
2N	Pouze několik algoritmů s exponenciální dobou běhu má praktické aplikace, ačkoli takové algoritmy přirozeně vznikají při pokusu o přímé řešení problému, jako je hrubá síla.

Na základě matematických metod pro studium asymptotických funkcí složitosti v nekonečnu je identifikováno pět tříd algoritmů.

1. Třída rychlých algoritmů s konstantní dobou provádění, jejich funkce složitosti je O(1). Mezistav je obsazen algoritmy se složitostí O(log N), které jsou rovněž zařazeny do této třídy.

2. Třída racionálních nebo polynomiálních algoritmů, jejichž funkce složitosti je určena polynomiálně ze vstupních parametrů. Například O(N), O(N2, O(N3).

3. Třída subexponenciálních algoritmů se stupněm složitosti O(N log N).

4.Třída exponenciálních algoritmů se stupněm složitosti O(2 N).

5.Třída nadexponenciálních algoritmů. Existují algoritmy s faktorovou složitostí, ale obecně nemají praktické využití.

Stav paměti během provádění algoritmu je určen hodnotami, které vyžadují přidělení určitých oblastí. V tomto případě lze v průběhu řešení problému použít další počet buněk. Velikostí paměti požadované algoritmem A pro vstup D rozumíme maximální počet paměťových buněk použitých při provádění algoritmu. Kapacitní složitost algoritmu je definována jako asymptotický odhad funkce kapacity paměti v nejhorším případě algoritmu.

Složitost zdrojů algoritmu v nejhorším, průměrném a nejlepším případě je tedy definována jako uspořádaná dvojice tříd funkcí časové a kapacitní složitosti, specifikovaná asymptotickou notací a odpovídající uvažovanému případu.

Hlavními algoritmickými konstrukcemi v procedurálním programování jsou následující, větvení a smyčkování. Pro získání funkcí složitosti pro nejlepší, průměrný a nejhorší případ s pevnou vstupní dimenzí je nutné vzít v úvahu rozdíly ve vyhodnocení hlavních algoritmických struktur.

Složitost konstrukce „Následující“ je součtem složitosti bloků následujících za sebou: f=f 1 +f 2 +...+f n .
Složitost návrhu "Větvení" je určena pravděpodobností přechodu na každou z instrukcí, určenou podmínkou. Kontrola stavu má přitom i určitou složitost. Pro výpočet složitosti nejhoršího případu lze vybrat větvený blok, který má největší složitost, v nejlepším případě lze vybrat blok s menší složitostí. f if =f 1 +f pak p pak +f jinak (1-p pak)
Složitost konstrukce "Loop" je určena výpočtem podmínky ukončení smyčky (obvykle řádu 0(1)) a součinem počtu dokončených iterací smyčky největším možným počtem operací těla smyčky. Pokud jsou použity vnořené smyčky, jejich složitost se násobí.

Pro odhad složitosti algoritmu lze tedy formulovat obecnou metodu pro získání funkce složitosti.

Dekompozice algoritmu zahrnuje identifikaci základních struktur v algoritmu a odhad složitosti. V tomto případě jsou zvažovány následující hlavní algoritmické struktury.
Řádková analýza pracnosti pro základní jazykové operace zahrnuje buď kumulativní analýzu (s přihlédnutím ke všem operacím) nebo operativní analýzu (s přihlédnutím ke složitosti každé operace).
Inverzní složení funkce složitosti založené na metodice analýzy základních algoritmických struktur pro nejlepší, průměrný a nejhorší případ.

Rysem hodnocení efektivity zdrojů rekurzivních algoritmů je potřeba vzít v úvahu dodatečné náklady na paměť a mechanismus pro organizování rekurze. Složitost rekurzivních implementací algoritmů proto souvisí s počtem operací provedených během jednoho rekurzivního volání a také s počtem takových volání. Zohledněny jsou také náklady na vracení hodnot a přenos kontroly na hlásič požáru. Při odhadování potřebné paměti zásobníku je třeba vzít v úvahu, že v určitém časovém okamžiku se na zásobníku neukládá fragment rekurze, ale řetězec rekurzivních volání. Velikost zásobníku je tedy určena maximálním možným počtem současně přijatých rekurzivních volání.

Programátorská knihovna

"Pokud je ladění procesem odstraňování chyb, pak by programování mělo být procesem jejich zavádění."

E. Dijkstra

1.2. Proč studovat algoritmy? Efektivita algoritmů

Za prvé, algoritmy jsou životně důležité komponenty pro řešení jakýchkoli problémů v různých oblastech informatiky. Algoritmy hrají v současné fázi vývoje technologií klíčovou roli. Zde si můžete připomenout takové běžné úkoly jako:

řešení matematických rovnic různé složitosti, hledání součinu matic, inverzní matice;
nalezení optimálních způsobů přepravy zboží a osob;
nalezení optimálních možností distribuce zdrojů mezi různé uzly (výrobci, stroje, pracovníci, zpracovatelé atd.);
nalezení sekvencí v genomu, které se shodují;
vyhledávání informací na globálním internetu;
přijímání finančních rozhodnutí v elektronickém obchodování;
zpracování a analýza audio a video informací.

Tento seznam pokračuje a ve skutečnosti je téměř nemožné najít oblast počítačové vědy a informační vědy, kde se nepoužívají určité algoritmy.

Za druhé, kvalitní a efektivní algoritmy mohou být katalyzátorem průlomů v odvětvích, která jsou na první pohled vzdálená informatice (kvantová mechanika, ekonomie a finance, evoluční teorie).

A za třetí, studium algoritmů je také neuvěřitelně zajímavý proces, který rozvíjí naše matematické schopnosti a logické myšlení.

1.3. Efektivita algoritmů

Předpokládejme, že rychlost počítače a množství jeho paměti lze zvyšovat donekonečna. Bylo by pak potřeba studovat algoritmy? Ano, ale pouze pro demonstraci toho, že metoda decouplingu má konečnou dobu trvání a že dává správnou odpověď. Kdyby byly počítače nekonečně rychlé, stačila by libovolná správná metoda řešení problému. Samozřejmě by se pak nejčastěji volila ta metoda, která je snadněji implementovatelná.

Dnes jsou počítače velmi výkonné, ale jejich rychlost není nekonečná a paměť také ne. V kalkulu je to tedy stejně omezený zdroj jako množství požadované paměti. Tyto zdroje by měly být využívány moudře, což je usnadněno použitím algoritmů, které jsou efektivní z hlediska využití časových a paměťových zdrojů.

Algoritmy navržené k řešení stejného problému se mohou často velmi lišit v účinnosti. Tyto rozdíly mohou být mnohem znatelnější než rozdíly způsobené různým hardwarem a softwarem.

Jak je uvedeno výše, tato část se zaměří na úkol řazení. První algoritmus, který budeme uvažovat, inkluzní třídění, vyžaduje čas na práci, jehož množství se odhaduje jako c 1 n 2, kde n je velikost vstupních dat (počet prvků v sekvenci, které mají být seřazeny), c 1 je nějaká konstanta. Tento výraz udává, jak závisí doba běhu algoritmu na objemu zdrojových dat. V případě inkluzního řazení je tato závislost kvadratická. Druhý algoritmus, merge sort, vyžaduje čas, jehož množství se odhaduje na 2 nLog 2 n. Typicky je konstanta řazení zahrnutí menší než konstanta řazení sloučení, to znamená, že c12 roste rychleji, když se zvyšuje n než funkce ILog 2 n. A pro nějakou hodnotu n = n 0 dojde k okamžiku, kdy přestane mít vliv rozdíl konstant a v budoucnu bude funkce c 2 nLog 2 n pro libovolné n > n 0 menší než c 1 n 2.

Abychom to demonstrovali, uvažujme dva počítače - A a B. Počítač A je rychlejší a běží na něm třídicí algoritmus a počítač B je pomalejší a spouští algoritmus řazení sloučení. Oba počítače musí seřadit sadu skládající se z milionu čísel. Řekněme, že počítač A provede miliardu operací za sekundu a počítač B jen deset milionů, tam A běží 100krát rychleji než B. Aby byl rozdíl patrnější, řekněme, že kód pro metodu enable napsal ten nejlepší programátor na světě pomocí instrukcí do procesoru a k seřazení n čísel pomocí tohoto algoritmu je třeba provést 2n 2 operací (tj. C 1 = 2). Slučovací řazení na počítači B bylo napsáno začínajícím programátorem pomocí vysokoúrovňového jazyka a výsledný kód vyžaduje 50nlog 2 n operací (tj. c 2 = 50). K seřazení milionu čísel by tedy počítač A potřeboval

a do počítače B -

Proto použití kódu, jehož doba běhu narůstá pomaleji, dokonce i se špatným počítačem a špatným kompilátorem, vyžaduje řádově méně CPU! U třídění 10 000 000 číslic se výhoda slučovacího třídění stává ještě patrnější: zatímco třídění podle inkluze vyžaduje na takový úkol asi 2,3 dne, pak u slučovacího třídění to trvá méně než 20 minut. Obecným pravidlem je, že čím větší je počet prvků k řazení, tím větší je výhoda slučovacího řazení. Výše uvedený příklad ukazuje, že algoritmy, stejně jako počítačový software, jsou technika. Celkový výkon systému závisí na účinnosti algoritmu stejně jako na výkonu hardwaru.

Zvažují se tedy různé možnosti výpočetních strojů, od nejjednodušších Turingových strojů až po homogenní výpočetní prostředí. Všechny lze použít k řešení problémů, pro které existuje algoritmus. Na základě těchto modelů se budují specializovanější modely výpočtů, konkrétně: nevětvené aritmetické programy, bitové výpočty, binární vektorové výpočty a rozhodovací stromy.

Algoritmy mají následující vlastnosti:

a) složitost;

b) pracovní náročnost;

c) spolehlivost atd.

Existuje mnoho kritérií pro hodnocení složitosti algoritmů. Nejčastěji nás bude zajímat růstový řádčas a paměťová kapacita potřebná k vyřešení problému s rostoucím množstvím vstupních dat. Spojme s každým konkrétním úkolem určité číslo, které se nazývá jeho velikost. Například velikost problému násobení matic může být největší velikostí faktorových matic; velikost problému na grafu může být počet hran daného grafu atp.

Nazývá se čas, který algoritmus zabere jako funkce velikosti problému časovou složitost tento algoritmus. Chování této složitosti v limitu se zvětšováním velikosti problému se nazývá asymptotická časová složitost. Podobně definováno kapacitní složitost A asymptotická kapacitní složitost.

Důležitou motivací pro uvažování o formálních výpočetních modelech je touha odhalit výpočetní složitost různých problémů za účelem získání nižších odhadů doby výpočtu. Ukázat, že neexistuje žádný algoritmus, který by dokázal dokončit daný úkol za méně než určitou dobu, vyžaduje přesnou a někdy vysoce specializovanou definici toho, co je algoritmus. Jedním z příkladů takové definice jsou Turingovy stroje.

4.1.1. Rámové a rámové stroje*

Zvažte dvě auta:

1. Stroje s náhodným přístupem do paměti (equal access address machine - RAM) modelují počítač s jednou sčítačkou, ve kterém se programové instrukce nemohou samy měnit.

2. Uložený programový model je stroj s náhodným přístupem do paměti a schopností upravovat instrukce (RAM*).

Obr.2.9 Struktura strojů RAM (RAM*)

U RAM se program nezapisuje do paměti, takže se program sám nemodifikuje. Program je posloupnost označených příkazů. Existují aritmetické instrukce, I/O instrukce, instrukce pro nepřímé adresování a instrukce větvení. Všechny výpočty jsou prováděny v registru r 0 (sčítačka), který jako každý jiný paměťový registr může ukládat libovolné celé číslo. Každý příkaz se skládá ze dvou částí – kódu operace a adresy. Příkazy PAM jsou podmnožinou příkazů jazyka assembler; tuto podmnožinu lze libovolně rozšiřovat, ale pořadí složitosti úkolů se nezmění.

Operand může být jednoho z následujících typů:

1. =i znamená celé číslo samotné i a nazývá se doslovný;

2. i- obsah registrace i (i musí být nezáporné);

3. *i znamená nepřímé adresování, to znamená, že hodnotou operandu je obsah registru j,Kde j- celé číslo, které je v registru já;Li j<0, auto zastaví.

Můžete určit hodnotu programu R pomocí dvou objektů: mapování c ze množiny nezáporných celých čísel na množinu celých čísel a „počítadlo příkazů“, které určuje další příkaz, který se má provést. Funkce c je paměťový displej, a to c(i)- celé číslo obsažené v čísle registru já (obsah Registrovat já).

Na začátku с(i)=0 pro všechny i 0 , čítač programů je nastaven na první instrukci v P a výstupní páska je prázdná. Po provedení k tým z R počítadlo se automaticky přepne na (k+1)-th (tedy k dalšímu) příkazu, jestliže k-můj tým nebyl tým jako JUMP, HALT, JGTZ a podobně.

Program RAM* je umístěn v paměťových registrech. Každý příkaz RAM* zabírá dva po sobě jdoucí paměťové registry: první registr obsahuje operační kód, druhý - adresu. Sada instrukcí pro RAM* se shoduje s odpovídající sadou pro RAM ve všem kromě nepřímého adresování, které je vyloučeno: RAM* může simulovat nepřímé adresování změnou instrukcí během provádění programu.

Kromě kontroly, že algoritmus implementovaný studentem jako řešení je schopen produkovat správnou odpověď na problém s určitými počátečními údaji, se při kontrole řešení bere v úvahu také doba běhu programu. To neznamená, že je životně důležité napsat optimální algoritmy pro všechny úlohy bez výjimky (což může často zabrat spoustu času na jejich kompetentní implementaci a ladění). To jednoduše znamená, že v některých jednotlivých úlohách může časový parametr hrát velmi důležitou roli. Klidně se může stát, že na některém kole olympiády nenastane jediný problém, ve kterém je nutná optimalizace. Může se však stát i opak.

Studenti i učitelé by tedy měli být schopni porovnávat různé algoritmy na základě jejich účinnosti. Školáci - aby si učitelé ve správnou chvíli zvolili nejvhodnější způsob řešení problému, aby kvalifikovaně vybírali úkoly a pochopili, jaké řešení měl autor konkrétního problému na mysli, když přesně takové časové limity stanovil.

K vyhodnocení účinnosti algoritmu se používá funkce složitosti, označovaná jako O (čti „o velkém“). Ve skutečnosti existují i jiná hodnocení, ale ve fázi, kdy se student teprve začíná seznamovat s různými algoritmy, nejsou vlastně potřeba. Funkce složitosti odráží vzorec, ve kterém se bude prodlužovat doba provádění programu v závislosti na zdrojových datech nebo jejich množství.

Příkladem algoritmu, jehož doba provádění závisí na počátečních datech, je algoritmus pro nalezení všech přirozených dělitelů čísla N. Je zřejmé, že čím větší číslo, tím více kroků smyčky bude nutné provést. Příkladem algoritmu, jehož doba provádění závisí na množství vstupních dat, by bylo hledání největšího čísla v poli. Čím delší je pole, tím více operací porovnání je třeba provést, aby bylo možné určit, které číslo je největší.

Hlavní funkce jsou:

l O(1) - taková funkce složitosti indikuje, že doba běhu programu je konstantní pro všechna počáteční data;

l O(N) - počet operací roste úměrně k N (zde N může být buď parametr úlohy nebo počet prvků v poli).

l O(log N) - počet operací roste úměrně s logaritmem N (to je právě složitost např. metody polovin při hledání prvku v uspořádaném poli). Když N řádově vzroste, počet operací se změní o jednu. Základ logaritmu obvykle není specifikován, zajímá nás povaha růstu (rychlý/pomalý), nikoli přesná hodnota času.

l O(N2) - počet operací se zvyšuje úměrně druhé mocnině N. Obecně to může být O(Nk) v závislosti na složitosti problému.

l O(N!) - počet operací se zvyšuje úměrně faktoriálu N.

Je zde řada jemností způsobených tím, že ne všechny operace se provádějí ve stejném čase, takže při odhadu časové složitosti se používají ty operace, které vyžadují nejvíce času.

Nejčastěji se při popisu algoritmů uvádí odhad jejich provozní doby v čisté podobě, tedy bez zohlednění vstupně/výstupních operací.

Příklad: odhadněme složitost programu, který zadá pole z klávesnice a najde v něm největší prvek.

Sečteme počet operací N+(N-1)+1=2N. To znamená, že existuje taková konstanta, že pro žádné N počet operací nepřekročí CN. Proto je složitost algoritmu O(N).

Příklad: odhadněme složitost programu, který zadá z klávesnice pole a najde v něm prvek s danou vlastností (například roven určité hodnotě).

Algoritmus se skládá z následujících kroků:

Zadání pole (N vstupních operací) hledání prvku s danou vlastností (jaké štěstí: prvek může být umístěn buď blíže začátku pole, nebo úplně na konci; pokud prvek neexistuje, musíte proveďte všech N porovnání, abyste se o tom ujistili) a výsledek .

V nejlepším případě bude tento algoritmus vyžadovat N+2 operací (vstup celého pole, jediné porovnání, výstup), v nejhorším případě (když takový prvek neexistuje - 2N+1 operací). Je-li N velké číslo, například asi 106, pak lze jednotu zanedbat. Proto je složitost algoritmu O(N).

Příklad: určeme funkci složitosti algoritmu šifrování slova délky L pomocí substituční metody. Nechť existuje tabulka, ve které je pro každý znak abecedy zapsán znak, kterým je třeba jej nahradit. Označme počet písmen abecedy S.

Algoritmus se skládá z následujících kroků:

Zadání slova (jedna operace) prochází všechny znaky

1. pro každý znak najděte v tabulce jeho náhradu (pokud tabulka není uspořádaná a nemá žádné vlastnosti usnadňující hledání, tak v nejhorším případě je S operací pro jeden znak, pokud je hledaný prvek na samém konec)

2. výstup nalezeného symbolu

Konec cyklu

Celkový počet operací je 1+(S+1)*L. V případě dostatečně velkých jednotek S a L lze zanedbat, ukazuje se, že funkce složitosti tohoto algoritmu je O(S*L).

Příklad: definujme funkci složitosti algoritmu pro převod přirozeného čísla N do dvojkové číselné soustavy (bez operací vstupu a výstupu dat).

Algoritmus se skládá z následujících kroků:

Opakujte, dokud výsledek dělení čísla 2 nebude 0

1. vydělte číslo 2 a zapamatujte si zbytek

2. vezměte výsledek dělení jako nové číslo

Konec cyklu

Celkový počet operací nepřesahuje 1+log2N. Proto má tento algoritmus složitost O(log N).

Pokud se program skládá z několika částí s různými funkcemi složitosti, pak Ó Větší funkce složitosti „pohltí“ ty menší. Pokud například provedete vstup pole O(N), řazení O(N2) a výstup O(N) uspořádaného pole, můžete říci, že celý program má složitost O(N2).

Praktická aplikace znalostí o funkcích složitosti algoritmů je dvojí. Za prvé, pro určitý úkol lze zvolit optimálnější algoritmus, pokud o něm existují relevantní údaje v literatuře. Za druhé, když student zná dobu běhu svého řešení na jedné sadě počátečních dat, může přibližně odhadnout dobu běhu stejného programu na datech, která odpovídají maximálním omezením pro daný problém.

Otázky

Tyto úlohy slouží k vlastnímu testování předloženého materiálu a nejsou povinné.

1. Určete funkci složitosti algoritmu pro řešení kvadratické rovnice.

2. Určete funkci složitosti algoritmu pro kreslení pravidelného mnohoúhelníku na základě daného počtu stran.

3. Určete funkci složitosti algoritmu pro vkládání prvku do pole na dané pozici (s předběžným posunem všech prvků s čísly větším nebo rovným danému o jednu pozici doprava).

4. Určete funkci složitosti algoritmu pro sčítání dvou přirozených čísel do sloupce (nechť A je počet číslic prvního čísla, B počet číslic druhého).

5. Určete funkci složitosti algoritmu pro násobení dvou přirozených čísel ve sloupci.