Složitost algoritmu

Verze z 17. 10. 2013, 11:48 (zobrazit zdroj) Spravce (diskuse | příspěvky) (Vytvoření stránky)		Verze z 17. 10. 2013, 11:57 (zobrazit zdroj) Spravce (diskuse | příspěvky) m (Přidán odkaz na Algoritmus) Porovnání s novější verzí →
Řá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>
−	;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 16:		Řádka 16:
	; Zjednodušení:		; Zjednodušení:
−	*Ne čas, ale počet operací (tím omezíme vliv HW).	+	*Neměříme čas, ale počet operací (tím omezíme vliv HW).
	*Nepočítáme všechny instrukce		*Nepočítáme všechny instrukce
	**obvykle počítáme pouze „významné“ (časově náročné) operace (počet porovnání, počet přístupů na disk.		**obvykle počítáme pouze „významné“ (časově náročné) operace (počet porovnání, počet přístupů na disk.
Řádka 28:		Řádka 28:
	**N... velikost dat		**N... velikost dat
	**f(N)... funkce, jejímž růstem lze limitovat růst počtu operací		**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í A+B.f(N)	+	**Pokud je velikost vstupu N, pak je složitost limitována funkcí <code>A+B.f(N)</code>
	;Příklady růstu počtu operací		;Příklady růstu počtu operací
Řádka 43:		Řádka 43:
	** 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	+	; Úkol &mdash; Navrhněte algoritmus a odhadněte složitost
	* Hledání maxima		* Hledání maxima
Řádka 49:		Řádka 49:
	; 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		; Maximální × průměrná složitost
Řádka 56:		Řádka 56:
	; 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]

---

Verze z 17. 10. 2013, 11:57

Obsah 1 Složitost jako míra pro srovnání algoritmů 2 Asymptotická složitost 3 Související pojmy 4 Viz také 5 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,
• ...

Zjednodušení

• Neměříme čas, ale počet operací (tím omezíme vliv HW).
• Nepočítáme všechny instrukce
  • 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,...
• Zajímají nás velká data, řádový růst (viz asymptotická složitost).
• Zajímá nás maximální nebo průměrná složitost. (Eliminujeme vliv zadání.)

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í A+B.f(N)

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

• O(N) — lineární
• Lepší než lineární
  • O(log(N))
  • O(sqrt(N))
• O(N.log(N))
• O(N²) — kvadratický
• O(N³) — kubický
• Polynomiální
  • roste jako libovolný polynom (omezen O(Nⁱ), kde i je lib. konstanta).
• O(2^N) — exponenciální
  • Viz například: Hanoiské věže.

Úkol — Navrhněte algoritmus a odhadněte složitost

• Hledání maxima

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.

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

Viz také

• Algoritmus

Zdroje

• Wikipedia.org > Asymptotická složitost