Složitost algoritmu

Verze z 17. 10. 2013, 11:57 (zobrazit zdroj) Spravce (diskuse | příspěvky) m (Přidán odkaz na Algoritmus) ← Porovnání se starší verzí		Verze z 25. 9. 2014, 10:20 (zobrazit zdroj) Spravce (diskuse | příspěvky) (→Složitost jako míra pro srovnání algoritmů: Měření složitosti jako samostatná kapitola.) Porovnání s novější verzí →
Řádka 15:		Řádka 15:
	* ...		* ...
−	; Zjednodušení:	+
−	*Neměříme č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í.
	== Asymptotická složitost ==		== Asymptotická složitost ==

---

Verze z 25. 9. 2014, 10:20

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

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