Analýza programů - Historie editací

Acolade: kategorizace

2014-02-20T06:34:21Z

kategorizace

← Starší verze		Verze z 20. 2. 2014, 06:34
Řádka 68:		Řádka 68:

	{{fav-kiv-bzinf}}		{{fav-kiv-bzinf}}
		+	[[Kategorie:fav-kiv-bzinf]]

Tester: /* Klasifikace složitosí */

2011-08-25T21:57:00Z

Klasifikace složitosí

← Starší verze		Verze z 25. 8. 2011, 21:57
Řádka 66:		Řádka 66:

	Postupy výše lze aplikovat i na složitosti paměťové, šířky pásma, ...		Postupy výše lze aplikovat i na složitosti paměťové, šířky pásma, ...
		+
		+	{{fav-kiv-bzinf}}

Tester: /* Očekávaná složitost */

2011-08-25T18:07:04Z

Očekávaná složitost

← Starší verze		Verze z 25. 8. 2011, 18:07
Řádka 52:		Řádka 52:
	== Očekávaná složitost ==		== Očekávaná složitost ==

−	Většina algoritmů je asymptoticky omezena pro extrémní případny na vstupu (např. Quicksort je Ω(n) (pole již seřazeno) a O(n2) (pole je seřazeno opačně) ). Chování algoritmu má však očekávanou složitost, která nastává pro většinu případů (jak víme O(n logn) pro QuickSort). Využívá se také Theta/Omikron/Omega notací.	+	Většina algoritmů je asymptoticky omezena pro extrémní případny na vstupu (např. Quicksort je Ω(n) (pole již seřazeno) a O(n2) (pole je seřazeno opačně)). Chování algoritmu má však očekávanou složitost, která nastává pro většinu případů (jak víme O(n logn) pro QuickSort). Využívá se také Theta/Omikron/Omega notací.

−	Je-li algoritmus závislý na vstupních datech (resp. na jejich uspořádání), a potřebujeme, aby složitost byla pokud možno vždy očekávaná, lze využít náhodného přeuspořádání dat na vstupu (za předpokladu, že je to možné, např pro řazení ano, pro výpis znaků na obrazovku evidentně ne), Toto přeuspořádání může být konstatní složitosti (např 100x přeházíme vzájemně prvky pole s náhodnými indexy pokud je pole rozumné odpovídající délky), případně lineární, složitost algoritmu tedy neovlivňuje (za předpokladu, že algoritmus samotný není očekávané sublineární časové složitosti)	+	Je-li algoritmus závislý na vstupních datech (resp. na jejich uspořádání), a potřebujeme, aby složitost byla pokud možno vždy očekávaná, lze využít náhodného přeuspořádání dat na vstupu (za předpokladu, že je to možné - např. pro řazení ano, pro výpis znaků na obrazovku evidentně ne). Toto přeuspořádání může být konstatní složitosti (např 100x přeházíme vzájemně prvky pole s náhodnými indexy pokud je pole rozumné odpovídající délky), případně lineární, složitost algoritmu tedy neovlivňuje (za předpokladu, že algoritmus samotný není očekávané sublineární časové složitosti).


−	~~Klasifikace složitosí:~~
−	Polynomiální - složitost O(nc) kde c je konstanta. Polynomiální algoritmy jsou použitelné. Ideální jsou algoritmy rychlejší (lineární, logaritmické,...), ne vždy j však možné takový algoritmus vymyslet

−	Exponenciální - složitost O(cn). Tyto algoritmy nejsou příliš dobré, a je vhodné se zamyslet a pokusit se vymyslet jiný, polynomiálně složitý algoritmus. Zpravidla algoritmy hrubé síly jsou této složitosti, jelikož procházejí všechny kombinace vstupu a hledají řešení. Pro malé n jsou však použitelné díky menší režii a přípravě, paměťovým nárokům atd.	+	== Klasifikace složitosí ==
		+
		+	'''Polynomiální''' - složitost O(n * c) kde c je konstanta. Polynomiální algoritmy jsou použitelné. Ideální jsou algoritmy rychlejší (lineární, logaritmické,...), ne vždy je však možné takový algoritmus vymyslet.
		+
		+	'''Exponenciální''' - složitost O(c<sup>n</sup>). Tyto algoritmy nejsou příliš dobré, a je vhodné se zamyslet a pokusit se vymyslet jiný, polynomiálně složitý algoritmus. Zpravidla algoritmy hrubé síly jsou této složitosti, jelikož procházejí všechny kombinace vstupu a hledají řešení. Pro malé n jsou však použitelné díky menší režii a přípravě, paměťovým nárokům atd.


	Postupy výše lze aplikovat i na složitosti paměťové, šířky pásma, ...		Postupy výše lze aplikovat i na složitosti paměťové, šířky pásma, ...

Tester: /* Asymptotická složitost */

2011-08-25T18:01:01Z

Asymptotická složitost

← Starší verze		Verze z 25. 8. 2011, 18:01
Řádka 41:		Řádka 41:

	'''Omikron notace''' O(f(x)) vyjadřuje A.S. omezenou funkcí c * f(x) pouze shora. Jinými slovy, jde o maximální možnou složitost algoritmu. Jde o první podmínku theta notace.		'''Omikron notace''' O(f(x)) vyjadřuje A.S. omezenou funkcí c * f(x) pouze shora. Jinými slovy, jde o maximální možnou složitost algoritmu. Jde o první podmínku theta notace.
−	'''	+
−	Omega notace''' Ω(f(x)) vyjadřuje A.S. omezenou funkcí c * f(x) pouze zdola. Říká, že algoritmus pro alespoň jeden vstup bude této složitosti. Druhá podmínka theta notace.	+	'''Omega notace''' Ω(f(x)) vyjadřuje A.S. omezenou funkcí c * f(x) pouze zdola. Říká, že algoritmus pro alespoň jeden vstup bude této složitosti. Druhá podmínka theta notace.

	Pokud platí omikron a omega notace pro stejnou f(x), mluvíme o theta notaci.		Pokud platí omikron a omega notace pro stejnou f(x), mluvíme o theta notaci.

Tester: /* Asymptotická složitost */

2011-08-25T17:51:09Z

Asymptotická složitost

← Starší verze		Verze z 25. 8. 2011, 17:51
Řádka 35:		Řádka 35:


−	Theta notace Θ(f(x)) vyjadřuje A.S., omezenou složitostní funkcí c<sub>1,2<sub> * f(x) shora, resp zdola. Hledáme tedy 2 konstatnty, pro které je analyzovaná složitost omezena.	+	'''Theta notace''' Θ(f(x)) vyjadřuje A.S., omezenou složitostní funkcí c<sub>1,2</sub> * f(x) shora, resp zdola. Hledáme tedy 2 konstatnty, pro které je analyzovaná složitost omezena.

	Tato notace říká, že algoritmus nebude asymptoticky složitější než c<sub>1</sub> * f(x), a nebude rychlejší než c<sub>2</sub> * f(x).		Tato notace říká, že algoritmus nebude asymptoticky složitější než c<sub>1</sub> * f(x), a nebude rychlejší než c<sub>2</sub> * f(x).
	To znamená, že problém lze řešit algoritmem, který nebude asymptoticky složitější než c<sub>1</sub> * f(x), ale zároveň nikdy nebude lepší než c<sub>2</sub> * f(x).		To znamená, že problém lze řešit algoritmem, který nebude asymptoticky složitější než c<sub>1</sub> * f(x), ale zároveň nikdy nebude lepší než c<sub>2</sub> * f(x).

−	Omikron notace O(f(x)) vyjadřuje A.S. omezenou funkcí c * f(x) pouze shora. Jinými slovy, jde o maximální možnou složitost algoritmu. Jde o první podmínku theta notace.	+	'''Omikron notace''' O(f(x)) vyjadřuje A.S. omezenou funkcí c * f(x) pouze shora. Jinými slovy, jde o maximální možnou složitost algoritmu. Jde o první podmínku theta notace.
−		+	'''
−	Omega notace Ω(f(x)) vyjadřuje A.S. omezenou funkcí c * f(x) pouze zdola. Říká, že algoritmus pro alespoň jeden vstup bude této složitosti. Druhá podmínka theta notace.	+	Omega notace''' Ω(f(x)) vyjadřuje A.S. omezenou funkcí c * f(x) pouze zdola. Říká, že algoritmus pro alespoň jeden vstup bude této složitosti. Druhá podmínka theta notace.

	Pokud platí omikron a omega notace pro stejnou f(x), mluvíme o theta notaci.		Pokud platí omikron a omega notace pro stejnou f(x), mluvíme o theta notaci.
Řádka 49:		Řádka 49:

	Předchozí příklad je tedy složitosti Θ(n) , jelikož je vždy lineární vzhledem k délce pole (netrvá kratší, ani delsí dobu/počet operací)		Předchozí příklad je tedy složitosti Θ(n) , jelikož je vždy lineární vzhledem k délce pole (netrvá kratší, ani delsí dobu/počet operací)
−

	== Očekávaná složitost ==		== Očekávaná složitost ==

Tester: /* Asymptotická složitost */

2011-08-25T17:42:22Z

Asymptotická složitost

Tester: /* Časová náročnost */

2011-08-25T17:30:21Z

Časová náročnost

← Starší verze		Verze z 25. 8. 2011, 17:30
Řádka 19:		Řádka 19:
	* operaci inkrementace lze definovat jako c<sub>inkrement</sub> = c<sub>přiřazení</sub> + c<sub>součet</sub>		* operaci inkrementace lze definovat jako c<sub>inkrement</sub> = c<sub>přiřazení</sub> + c<sub>součet</sub>
	* řekněme, že generování náhodného čísla trvá konstantní čas c<sub>rand</sub>		* řekněme, že generování náhodného čísla trvá konstantní čas c<sub>rand</sub>
		+
		+

	* Inicializace cyklu for: alokace + přiřazení = c<sub>aloc</sub> + c<sub>přiřazení</sub>		* Inicializace cyklu for: alokace + přiřazení = c<sub>aloc</sub> + c<sub>přiřazení</sub>
Řádka 24:		Řádka 26:
	* Cyklus for proběkne n-krát, tedy: n * ( c<sub>porovnání</sub> + c<sub>přiřazení</sub> + c<sub>rand</sub> + c<sub>inkrement</sub> )		* Cyklus for proběkne n-krát, tedy: n * ( c<sub>porovnání</sub> + c<sub>přiřazení</sub> + c<sub>rand</sub> + c<sub>inkrement</sub> )
	* Celkem: c<sub>aloc</sub> + c<sub>přiřazení</sub> + n * ( c<sub>porovnání</sub> + c<sub>přiřazení</sub> + c<sub>rand</sub> + c<sub>inkrement</sub> )		* Celkem: c<sub>aloc</sub> + c<sub>přiřazení</sub> + n * ( c<sub>porovnání</sub> + c<sub>přiřazení</sub> + c<sub>rand</sub> + c<sub>inkrement</sub> )
−

	== Asymptotická složitost ==		== Asymptotická složitost ==

Tester: /* Časová náročnost */

2011-08-25T17:29:15Z

Časová náročnost

← Starší verze		Verze z 25. 8. 2011, 17:29
Řádka 20:		Řádka 20:
	* řekněme, že generování náhodného čísla trvá konstantní čas c<sub>rand</sub>		* řekněme, že generování náhodného čísla trvá konstantní čas c<sub>rand</sub>

−	Inicializace cyklu for: alokace + přiřazení = ~~caloc~~ + ~~cpřiřazení~~	+	* Inicializace cyklu for: alokace + přiřazení = c<sub>aloc</sub> + c<sub>přiřazení</sub>
		+	* Běh cyklu: porovnání (i < length) + přiřazení (do pole) + náh. číslo + inkrementace (i++) = c<sub>porovnání</sub> + c<sub>přiřazení</sub> + c<sub>rand</sub> + c<sub>inkrement</sub>
		+	* Cyklus for proběkne n-krát, tedy: n * ( c<sub>porovnání</sub> + c<sub>přiřazení</sub> + c<sub>rand</sub> + c<sub>inkrement</sub> )
		+	* Celkem: c<sub>aloc</sub> + c<sub>přiřazení</sub> + n * ( c<sub>porovnání</sub> + c<sub>přiřazení</sub> + c<sub>rand</sub> + c<sub>inkrement</sub> )

−	~~Běh cyklu: porovnání (i<length) + přiřazení (do pole) + náh.číslo + inkrementace (i++) = cporovnání + cpřiřazení + Crand + Cinkrement~~

−	~~Cyklus for proběkne n-krát, tedy: n * ( cporovnání + cpřiřazení + Crand + Cinkrement )~~	+	== Asymptotická složitost ==

−	~~Celkem: caloc + cpřiřazení + n * ( cporovnání + cpřiřazení + Crand + Cinkrement )~~
−
−	~~Asymptotická složitost:~~
	Ve většině případů neznáme čas potřebný pro konstantní operace, ale víme, že je velmi malý. Dobu výpočtu předchozího příkladu můžeme tedy přepsat na a + nb, kde a a b jsou doby, které mají určitou délku, která nás však přísliš nezajímá.		Ve většině případů neznáme čas potřebný pro konstantní operace, ale víme, že je velmi malý. Dobu výpočtu předchozího příkladu můžeme tedy přepsat na a + nb, kde a a b jsou doby, které mají určitou délku, která nás však přísliš nezajímá.

Tester: /* Časová náročnost */

2011-08-25T15:33:20Z

Časová náročnost

← Starší verze		Verze z 25. 8. 2011, 15:33
Řádka 13:		Řádka 13:
	}		}

−	máme pole délky n = pole.Length	+	* máme pole délky n = pole.Length:
−	alokace proměnné trvá ~~caloc~~	+	* alokace proměnné trvá c<sub>aloc</sub>
−	operace přiřazení trvá ~~cpřiřazení~~	+	* operace přiřazení trvá c<sub>přiřazení</sub>
−	operace porovnání trvá ~~cporovnání~~	+	* operace porovnání trvá c<sub>porovnání</sub>
−	operaci inkrementace lze definovat jako ~~Cinkrement~~ = ~~cpřiřazení~~ + ~~csoučet~~	+	* operaci inkrementace lze definovat jako c<sub>inkrement</sub> = c<sub>přiřazení</sub> + c<sub>součet</sub>
−	řekněme, že generování náhodného čísla trvá konstantní čas ~~Crand~~	+	* řekněme, že generování náhodného čísla trvá konstantní čas c<sub>rand</sub>

	Inicializace cyklu for: alokace + přiřazení = caloc + cpřiřazení		Inicializace cyklu for: alokace + přiřazení = caloc + cpřiřazení
		+
	Běh cyklu: porovnání (i<length) + přiřazení (do pole) + náh.číslo + inkrementace (i++) = cporovnání + cpřiřazení + Crand + Cinkrement		Běh cyklu: porovnání (i<length) + přiřazení (do pole) + náh.číslo + inkrementace (i++) = cporovnání + cpřiřazení + Crand + Cinkrement
		+
	Cyklus for proběkne n-krát, tedy: n * ( cporovnání + cpřiřazení + Crand + Cinkrement )		Cyklus for proběkne n-krát, tedy: n * ( cporovnání + cpřiřazení + Crand + Cinkrement )

81.201.60.162 v 25. 8. 2011, 13:12

2011-08-25T13:12:58Z

← Starší verze		Verze z 25. 8. 2011, 13:12
Řádka 4:		Řádka 4:
	== Časová náročnost ==		== Časová náročnost ==

−	Nejčastěji nás zajímá časová náročnost programu. Analyzujeme, jakou dobu bude implementovanému algoritmu trvat výpočet. Tuto dobu ovlivňuje způsob implementace (počet nutně provedených operací) a velikost vstupních dat (počet prvků, které algoritmus zpracovává, případně jejich uspořádání). Definujeme elementární čas pro všechny operace ~~coperace~~ a jejich skádáním počítáme celkový čas potřebný pro provedení algoritmu.	+	Nejčastěji nás zajímá časová náročnost programu. Analyzujeme, jakou dobu bude implementovanému algoritmu trvat výpočet. Tuto dobu ovlivňuje způsob implementace (počet nutně provedených operací) a velikost vstupních dat (počet prvků, které algoritmus zpracovává, případně jejich uspořádání). Definujeme elementární čas pro všechny operace c<sub>operace</sub> a jejich skádáním počítáme celkový čas potřebný pro provedení algoritmu.

	Příklad: Naplnění již alokovaného pole náhodnými čísly (c#)		Příklad: Naplnění již alokovaného pole náhodnými čísly (c#)

−	for (int i = 0, i < pole.Length; i++)	+	for (int i = 0, i < pole.Length; i++)
−	{	+	{
−	pole[i] = rand.Next();	+	pole[i] = rand.Next();
−	}	+	}

	máme pole délky n = pole.Length		máme pole délky n = pole.Length

← Starší verze		Verze z 25. 8. 2011, 17:42
Řádka 29:		Řádka 29:
	== Asymptotická složitost ==		== Asymptotická složitost ==

−	Ve většině případů neznáme čas potřebný pro konstantní operace, ale víme, že je velmi malý. Dobu výpočtu předchozího příkladu můžeme tedy přepsat na a + nb, kde a a b jsou doby, které mají určitou délku, která nás však přísliš nezajímá.	+	Ve většině případů neznáme čas potřebný pro konstantní operace, ale víme, že je velmi malý. Dobu výpočtu předchozího příkladu můžeme tedy přepsat na '''a''' + '''n''' * '''b''', kde '''a''' a '''b''' jsou doby, které mají určitou délku, která nás však přísliš nezajímá.

	Více než doba výpočtu nás tedy zajímá počet operací, které je třeba vykonat (stejně budou operace na každém systému vykonávány jinou dobu (PC vs. mobilní telefon např.)). Složitostí programu myslíme právě počet operací potřebný pro výpočet vzhledem k počtu prvků na vstupu algoritmu, omezený shora a/nebo zdola. Tato složitost se pro libovolný počet prvků asymptoticky blíží k určité funkci. Nás zajímá, ke které.		Více než doba výpočtu nás tedy zajímá počet operací, které je třeba vykonat (stejně budou operace na každém systému vykonávány jinou dobu (PC vs. mobilní telefon např.)). Složitostí programu myslíme právě počet operací potřebný pro výpočet vzhledem k počtu prvků na vstupu algoritmu, omezený shora a/nebo zdola. Tato složitost se pro libovolný počet prvků asymptoticky blíží k určité funkci. Nás zajímá, ke které.
Řádka 35:		Řádka 35:


−	Theta notace Θ(f(x)) vyjadřuje A.S., omezenou složitostní funkcí c1,2 * f(x) shora, resp zdola~~, hledáme~~ tedy 2 konstatnty, pro které je analyzovaná složitost omezena.	+	Theta notace Θ(f(x)) vyjadřuje A.S., omezenou složitostní funkcí c<sub>1,2<sub> * f(x) shora, resp zdola. Hledáme tedy 2 konstatnty, pro které je analyzovaná složitost omezena.

−	Tato notace říká, že algoritmus nebude asymptoticky složitější než c1 * f(x), a nebude rychlejší než c2 * f(x).	+	Tato notace říká, že algoritmus nebude asymptoticky složitější než c<sub>1</sub> * f(x), a nebude rychlejší než c<sub>2</sub> * f(x).
−	~~Tato notace říká~~, že problém lze řešit algoritmem, který nebude asymptoticky složitější než c1 * f(x), ~~a neexistuje řešení~~ lepší než c2 * f(x).	+	To znamená, že problém lze řešit algoritmem, který nebude asymptoticky složitější než c<sub>1</sub> * f(x), ale zároveň nikdy nebude lepší než c<sub>2</sub> * f(x).

	Omikron notace O(f(x)) vyjadřuje A.S. omezenou funkcí c * f(x) pouze shora. Jinými slovy, jde o maximální možnou složitost algoritmu. Jde o první podmínku theta notace.		Omikron notace O(f(x)) vyjadřuje A.S. omezenou funkcí c * f(x) pouze shora. Jinými slovy, jde o maximální možnou složitost algoritmu. Jde o první podmínku theta notace.

−	Omega notace Ω(f(x)) vyjadřuje A.S. omezenou funkcí c * f(x) pouze zdola. Říká, že algoritmus pro alespoň jeden vstup bude této složitosti~~, respektive že problém nelze řešit jednodušeji, než algoritmem složitosti f(x)~~. Druhá podmínka theta notace.	+	Omega notace Ω(f(x)) vyjadřuje A.S. omezenou funkcí c * f(x) pouze zdola. Říká, že algoritmus pro alespoň jeden vstup bude této složitosti. Druhá podmínka theta notace.

	Pokud platí omikron a omega notace pro stejnou f(x), mluvíme o theta notaci.		Pokud platí omikron a omega notace pro stejnou f(x), mluvíme o theta notaci.

−	Konstanty v notaci zanedbáváme, jelikož vzhledem k většímu n nehrají roli. Sčítáním složitostí tedy nedochází k jejich zhoršení, jsou-li stejného řádu (např n2 + n2 = ~~2n2~~ => n2, 200 operací je asymptoticky stejné jako 100, ale n2 + n3 => n3 , 100 * 100 operací je vzhledem k 100 * 100 * 100 zanedbatelné)	+	Konstanty v notaci zanedbáváme, jelikož vzhledem k většímu n nehrají roli. Sčítáním složitostí tedy nedochází k jejich zhoršení, jsou-li stejného řádu (např n<sup>2</sup> + n<sup>2</sup> = 2n<sup>2</sup> => n<sup>2</sup>, 200 operací je asymptoticky stejné jako 100, ale n<sup>2</sup> + n<sup>3</sup> => n<sup>3</sup> , 100 * 100 operací je vzhledem k 100 * 100 * 100 zanedbatelné).

	Předchozí příklad je tedy složitosti Θ(n) , jelikož je vždy lineární vzhledem k délce pole (netrvá kratší, ani delsí dobu/počet operací)		Předchozí příklad je tedy složitosti Θ(n) , jelikož je vždy lineární vzhledem k délce pole (netrvá kratší, ani delsí dobu/počet operací)

−	Očekávaná složitost:	+
		+	== Očekávaná složitost ==
		+
	Většina algoritmů je asymptoticky omezena pro extrémní případny na vstupu (např. Quicksort je Ω(n) (pole již seřazeno) a O(n2) (pole je seřazeno opačně) ). Chování algoritmu má však očekávanou složitost, která nastává pro většinu případů (jak víme O(n logn) pro QuickSort). Využívá se také Theta/Omikron/Omega notací.		Většina algoritmů je asymptoticky omezena pro extrémní případny na vstupu (např. Quicksort je Ω(n) (pole již seřazeno) a O(n2) (pole je seřazeno opačně) ). Chování algoritmu má však očekávanou složitost, která nastává pro většinu případů (jak víme O(n logn) pro QuickSort). Využívá se také Theta/Omikron/Omega notací.