Složitost algoritmu

Verze z 17. 10. 2013, 11:48 (zobrazit zdroj) Spravce (diskuse | příspěvky) (Vytvoření stránky)		Aktuální verze z 18. 10. 2021, 13:21 (zobrazit zdroj) Spravce (diskuse | příspěvky) (→Asymptotická složitost: Doplněny příklady algoritmů dané složitosti.)
(Nejsou zobrazeny 4 mezilehlé verze od 1 uživatele.)
Řádka 3:		Řádka 3:
	== Složitost jako míra pro srovnání algoritmů ==		== Složitost jako míra pro srovnání algoritmů ==
	Hledáme nástroje pro porovnání efektivity algoritmů.		Hledáme nástroje pro porovnání efektivity algoritmů.
−	*máme <code>N</code> prvků vstupních dat (<code>N</code> zákazníků, <code>N</code> čísel,...)	+	*Máme <code>N</code> prvků vstupních dat (<code>N</code> zákazníků, <code>N</code> čísel,...),
−	*zajímá nás, který ze dvou algoritmů vrátí výsledek dříve	+	*zajímá nás, který ze dvou algoritmů vrátí výsledek dříve.
−	Rychlejší algoritmus &rarr; lepší algoritmus!	+	<div class="Poznamka">Rychlejší algoritmus &rarr; lepší algoritmus!</div>
		+	<div class="Varovani">Má to ale jeden háček &mdash; musí nám stačit systémové prostředky pro daný algoritmus, zejména operační paměť. ;)</div>
−	;Problém: čas je ovlivněn i:	+	;Problém &mdash; čas je ovlivněn:
	* volbou konkrétního zadání stejného problému,		* volbou konkrétního zadání stejného problému,
−	* výkonem počítače,	+	* výkonem počítače (pozor také na další běžící procesy),
	* kvalitou implementace algoritmu,		* kvalitou implementace algoritmu,
	* použitým programovacím jazykem,		* použitým programovacím jazykem,
Řádka 15:		Řádka 16:
	* ...		* ...
−	; Zjednodušení:	+
−	*Ne čas, ale počet operací (tím omezíme vliv HW).	+	== Měření složitosti ==
−	*Nepočítáme všechny instrukce	+	# ''Neměříme čas, ale počet operací!''
−	**obvykle počítáme pouze „významné“ (časově náročné) operace (počet porovnání, počet přístupů na disk.	+	#* Tím omezíme vliv konkrétního HW.
−	**Tím eliminujeme vliv použitého překladače, knihoven, jazyka,...	+	# ''Nepočítáme všechny dílčí operace!''
−	*Zajímají nás velká data, řádový růst (viz asymptotická složitost).	+	#* Obvykle počítáme pouze „významné“ (časově náročné) operace (počet porovnání, počet přístupů na disk).
−	*Zajímá nás maximální nebo průměrná složitost. (Eliminujeme vliv zadání.)	+	#* Tím eliminujeme vliv použitého překladače, knihoven, jazyka, procesorové architektury,...
		+	# ''Zajímají nás velká data, řádový růst!''
		+	#* Viz [[#Asymptotická složitost|asymptotická složitost]].
		+	#* Malé instance skončí v rozumném čase, i když se budou počítat neefektivně.
		+	# ''Zajímá nás maximální nebo průměrná složitost!''
		+	#* Tím eliminujeme vliv konkrétního zadání.
		+	#* Viz [[#Maximální a průměrná složitost|průměrná složitost]].
		+
	== Asymptotická složitost ==		== Asymptotická složitost ==
	*Jakým způsobem se složitost algoritmu (počet operací) mění při změně objemu vstupních dat.		*Jakým způsobem se složitost algoritmu (počet operací) mění při změně objemu vstupních dat.
	*Zapisujeme <code>O(f(N))</code>		*Zapisujeme <code>O(f(N))</code>
−	**N... velikost dat	+	** <code>N</code>... velikost dat
−	**f(N)... funkce, jejímž růstem lze limitovat růst počtu operací	+	** <code>f(N)</code>... funkce, jejímž růstem lze limitovat růst počtu operací
−	**Pokud je velikost vstupu N, pak je složitost limitována funkcí A+B.f(N)	+	**Pokud je velikost vstupu <code>N</code>, pak je složitost limitována funkcí: <code>y = A+B.f(N)</code>
	;Příklady růstu počtu operací		;Příklady růstu počtu operací
−	*O(N) &mdash; lineární	+	* <code>O(N)</code> &mdash; lineární ... např. hledání maxima posloupnosti
	*Lepší než lineární		*Lepší než lineární
−	**O(log(N))	+	** <code>O(log(N))</code> ... např. hledání prvku v&nbsp;seřazeném seznamu
−	**O(sqrt(N))	+	** <code>O(sqrt(N))</code>
−	*O(N.log(N))	+	* <code>O(N.log(N))</code> ... př.: rychlé algoritmy pro řazení
−	*O(N<sup>2</sup>) &mdash; kvadratický	+	* <code>O(N<sup>2</sup>)</code> &mdash; kvadratický ... například řazení opakovaným hledáním maxima
−	*O(N<sup>3</sup>) &mdash; kubický	+	* <code>O(N<sup>3</sup>)</code> &mdash; kubický
	*Polynomiální		*Polynomiální
−	**roste jako libovolný polynom (omezen O(N<sup>i</sup>), kde i je lib. konstanta).	+	**roste jako libovolný polynom (omezen <code>O(N<sup>i</sup>)</code>, kde <code>i</code> je lib. konstanta).
−	*O(2<sup>N</sup>) &mdash; exponenciální	+	* <code>O(2<sup>N</sup>)</code> &mdash; exponenciální
	** Viz například: [http://cs.wikipedia.org/wiki/Hanojsk%C3%A9_v%C4%9B%C5%BEe Hanoiské věže].		** Viz například: [http://cs.wikipedia.org/wiki/Hanojsk%C3%A9_v%C4%9B%C5%BEe Hanoiské věže].
−	; Úkol: Navrhněte algoritmus a odhadněte složitost	+	<div class="Priklad">
		+	Abyste si lépe uvědomili, jaký vliv má růst složitosti algoritmu, můžete si to zkusit představit na hledání v&nbsp;telefonním seznamu:
		+	* Běžné hledání v&nbsp;telefonním seznamu má složitost <code>O(N.log(N))</code>.
		+	* Složitost <code>O(N)</code> &mdash; lineární, tedy stále dobrou &mdash; by mělo hledání v&nbsp;telefonním seznamu podle telefonního čísla. Museli byste projít všechny položky a&nbsp;hledat člověka, který má zadané telefonní číslo.
		+	* Kvadratickou složitost <code>O(N<sup>2</sup>)</code> by měla úloha, kdy byste každému člověku z&nbsp;telefonního seznamu museli zavolat, on by vám řekl telefonní číslo svého nejlepšího kamaráda a&nbsp;vaším úkolem by bylo nalézt v&nbsp;seznamu jméno toho kamaráda (opět hledáním položku po položce). (Tady už by se vyplatilo si telefonní seznam nejprve seřadit podle telefonních čísel. To by sice zabralo čas <code>O(N.log(N))</code>, ale pak už byste hledali se složitostí <code>O(log(N))</code>.)
		+	* Kubická složitost: na každé číslo v&nbsp;seznamu zavolejte, tam vám řeknou telefonní číslo kamaráda, najděte jeho jméno, zavolejte mu, oslovte ho jménem a&nbsp;on vám řekne číslo svého kamaráda. Jeho jméno najděte. ;)
		+	</div>
		+
		+	<div class="Priklad">Úkol: Navrhněte algoritmus a odhadněte složitost
	* Hledání maxima		* Hledání maxima
		+	</div>
		+
		+	== Maximální a průměrná složitost ==
		+	* Počet vykonaných operací se může lišit podle podoby konkrétních dat.
		+	* Třeba při řazení podle abecedy může být počet operací jiný pro ''téměř setříděná'' data a jiná pro data, která jsou úplně přeházená.
		+	* Některé algoritmy mohou mít velmi dobré chování ve většině případů, ale pro nešťastně uspořádaná data mohou mít složitost větší. (Viz třeba známý řadící algoritmus ''QuickSort''.)
		+
		+	<div class="Priklad">
		+	* Při cestě do školy vstanu tak, abych v průměrném případě dorazil včas. Pokud dojde k&nbsp;nehodě na silnici, může se stát, že se zpozdím. Ale je to málo pravděpodobné a vyrážet o&nbsp;hodinu dříve pro případ nehody by bylo nepraktické &mdash; řeším ''průměrnou'' délku cesty.
		+	* Na druhou stranu pokud jdu k&nbsp;maturitě, čtvrthodinové zpoždění by znamenalo, že budu muset maturovat až na podzim a&nbsp;proto raději hodinu počkám &mdash; zajímá mě spíše délka cesty ''v&nbsp;nejhorším případě''.
		+	</div>
		+
	== Související pojmy ==		== Související pojmy ==
	; Složitost problému		; Složitost problému
	*Složitost nejlepšího algoritmu, který řeší daný problém.		*Složitost nejlepšího algoritmu, který řeší daný problém.
−	*× složitost nejlepšího ZNÁMÉHO algoritmu.	+	*× složitost nejlepšího ''známého'' algoritmu.
−		+
−	; Maximální × průměrná složitost	+
−	*viz QuickSort	+
−	*Aneb: Pojedete do školy o 4 hodiny později proto, že v nejhorším možném případě Vám cesta bude trvat pěšky 4 hodiny?	+
	; Paměťová × časová složitost		; Paměťová × časová složitost
		+
		+	== Viz také ==
		+	* [[Algoritmus]]
	== Zdroje ==		== Zdroje ==
	*[http://cs.wikipedia.org/wiki/Asymptotick%C3%A1_slo%C5%BEitost Wikipedia.org > Asymptotická složitost]		*[http://cs.wikipedia.org/wiki/Asymptotick%C3%A1_slo%C5%BEitost Wikipedia.org > Asymptotická složitost]

---

Aktuální verze z 18. 10. 2021, 13:21

Obsah 1 Složitost jako míra pro srovnání algoritmů 2 Měření složitosti 3 Asymptotická složitost 4 Maximální a průměrná složitost 5 Související pojmy 6 Viz také 7 Zdroje

Složitost jako míra pro srovnání algoritmů

Hledáme nástroje pro porovnání efektivity algoritmů.

• Máme N prvků vstupních dat (N zákazníků, N čísel,...),
• zajímá nás, který ze dvou algoritmů vrátí výsledek dříve.

Problém — čas je ovlivněn

• volbou konkrétního zadání stejného problému,
• výkonem počítače (pozor také na další běžící procesy),
• kvalitou implementace algoritmu,
• použitým programovacím jazykem,
• použitými knihovnami,
• ...

Měření složitosti

1. Neměříme čas, ale počet operací!
   • Tím omezíme vliv konkrétního HW.
2. Nepočítáme všechny dílčí operace!
   • Obvykle počítáme pouze „významné“ (časově náročné) operace (počet porovnání, počet přístupů na disk).
   • Tím eliminujeme vliv použitého překladače, knihoven, jazyka, procesorové architektury,...
3. Zajímají nás velká data, řádový růst!
   • Viz asymptotická složitost.
   • Malé instance skončí v rozumném čase, i když se budou počítat neefektivně.
4. Zajímá nás maximální nebo průměrná složitost!
   • Tím eliminujeme vliv konkrétního zadání.
   • Viz průměrná složitost.

Asymptotická složitost

• Jakým způsobem se složitost algoritmu (počet operací) mění při změně objemu vstupních dat.
• Zapisujeme O(f(N))
  • N... velikost dat
  • f(N)... funkce, jejímž růstem lze limitovat růst počtu operací
  • Pokud je velikost vstupu N, pak je složitost limitována funkcí: y = A+B.f(N)

Příklady růstu počtu operací

• O(N) — lineární ... např. hledání maxima posloupnosti
• Lepší než lineární
  • O(log(N)) ... např. hledání prvku v seřazeném seznamu
  • O(sqrt(N))
• O(N.log(N)) ... př.: rychlé algoritmy pro řazení
• O(N2) — kvadratický ... například řazení opakovaným hledáním maxima
• O(N3) — kubický
• Polynomiální
  • roste jako libovolný polynom (omezen O(Ni), kde i je lib. konstanta).
• O(2N) — exponenciální
  • Viz například: Hanoiské věže.

Maximální a průměrná složitost

• Počet vykonaných operací se může lišit podle podoby konkrétních dat.
• Třeba při řazení podle abecedy může být počet operací jiný pro téměř setříděná data a jiná pro data, která jsou úplně přeházená.
• Některé algoritmy mohou mít velmi dobré chování ve většině případů, ale pro nešťastně uspořádaná data mohou mít složitost větší. (Viz třeba známý řadící algoritmus QuickSort.)

Související pojmy

Složitost problému

• Složitost nejlepšího algoritmu, který řeší daný problém.
• × složitost nejlepšího známého algoritmu.

Paměťová × časová složitost

Viz také

• Algoritmus

Zdroje

• Wikipedia.org > Asymptotická složitost