Složitost algoritmu - Historie editací

Spravce: /* Asymptotická složitost */ Doplněny příklady algoritmů dané složitosti.

2021-10-18T13:21:58Z

Asymptotická složitost: Doplněny příklady algoritmů dané složitosti.

← Starší verze		Verze z 18. 10. 2021, 13:21
Řádka 39:		Řádka 39:

	;Příklady růstu počtu operací		;Příklady růstu počtu operací
−	* <code>O(N)</code> — lineární	+	* <code>O(N)</code> — lineární ... např. hledání maxima posloupnosti
	*Lepší než lineární		*Lepší než lineární
−	** <code>O(log(N))</code>	+	** <code>O(log(N))</code> ... např. hledání prvku v seřazeném seznamu
	** <code>O(sqrt(N))</code>		** <code>O(sqrt(N))</code>
−	* <code>O(N.log(N))</code>	+	* <code>O(N.log(N))</code> ... př.: rychlé algoritmy pro řazení
−	* <code>O(N<sup>2</sup>)</code> — kvadratický	+	* <code>O(N<sup>2</sup>)</code> — kvadratický ... například řazení opakovaným hledáním maxima
	* <code>O(N<sup>3</sup>)</code> — kubický		* <code>O(N<sup>3</sup>)</code> — kubický
	*Polynomiální		*Polynomiální
Řádka 50:		Řádka 50:
	* <code>O(2<sup>N</sup>)</code> — exponenciální		* <code>O(2<sup>N</sup>)</code> — 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].
		+
		+	<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 telefonním seznamu:
		+	* Běžné hledání v telefonním seznamu má složitost <code>O(N.log(N))</code>.
		+	* Složitost <code>O(N)</code> — lineární, tedy stále dobrou — by mělo hledání v telefonním seznamu podle telefonního čísla. Museli byste projít všechny položky a 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 telefonního seznamu museli zavolat, on by vám řekl telefonní číslo svého nejlepšího kamaráda a vaším úkolem by bylo nalézt v 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 seznamu zavolejte, tam vám řeknou telefonní číslo kamaráda, najděte jeho jméno, zavolejte mu, oslovte ho jménem a 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		<div class="Priklad">Úkol: Navrhněte algoritmus a odhadněte složitost
	* Hledání maxima		* Hledání maxima
	</div>		</div>
−

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

Spravce: Přidáno upozornění na omezení kapacity paměti.

2017-10-02T09:08:25Z

Přidáno upozornění na omezení kapacity paměti.

← Starší verze		Verze z 2. 10. 2017, 09:08
Řádka 6:		Řádka 6:
	*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.
	<div class="Poznamka">Rychlejší algoritmus → lepší algoritmus!</div>		<div class="Poznamka">Rychlejší algoritmus → lepší algoritmus!</div>
		+	<div class="Varovani">Má to ale jeden háček — musí nám stačit systémové prostředky pro daný algoritmus, zejména operační paměť. ;)</div>

	;Problém — čas je ovlivněn:		;Problém — čas je ovlivněn:
Řádka 27:		Řádka 28:
	# ''Zajímá nás maximální nebo průměrná složitost!''		# ''Zajímá nás maximální nebo průměrná složitost!''
	#* Tím eliminujeme vliv konkrétního zadání.		#* 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 ==
Řádka 51:		Řádka 54:
	* Hledání maxima		* Hledání maxima
	</div>		</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 nehodě na silnici, může se stát, že se zpozdím. Ale je to málo pravděpodobné a vyrážet o hodinu dříve pro případ nehody by bylo nepraktické — řeším ''průměrnou'' délku cesty.
		+	* Na druhou stranu pokud jdu k maturitě, čtvrthodinové zpoždění by znamenalo, že budu muset maturovat až na podzim a proto raději hodinu počkám — zajímá mě spíše délka cesty ''v nejhorším případě''.
		+	</div>
		+

	== Související pojmy ==		== Související pojmy ==
Řádka 56:		Řádka 71:
	*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

Spravce: /* Asymptotická složitost */ Oprava vzhledu

2014-09-25T10:29:01Z

Asymptotická složitost: Oprava vzhledu

← Starší verze		Verze z 25. 9. 2014, 10:29
Řádka 31:		Řádka 31:
	*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í <code>A+B.f(N)</code>	+	**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) — lineární	+	* <code>O(N)</code> — lineární
	*Lepší než lineární		*Lepší než lineární
−	**O(log(N))	+	** <code>O(log(N))</code>
−	**O(sqrt(N))	+	** <code>O(sqrt(N))</code>
−	*O(N.log(N))	+	* <code>O(N.log(N))</code>
−	*O(N<sup>2</sup>) — kvadratický	+	* <code>O(N<sup>2</sup>)</code> — kvadratický
−	*O(N<sup>3</sup>) — kubický	+	* <code>O(N<sup>3</sup>)</code> — 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>) — exponenciální	+	* <code>O(2<sup>N</sup>)</code> — 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">Úkol: Navrhněte algoritmus a odhadněte složitost
	* Hledání maxima		* Hledání maxima
		+	</div>

	== Související pojmy ==		== Související pojmy ==

Spravce: /* Složitost jako míra pro srovnání algoritmů */ Měření složitosti jako samostatná kapitola.

2014-09-25T10:20:02Z

Složitost jako míra pro srovnání algoritmů: Měření složitosti jako samostatná kapitola.

← Starší verze		Verze z 25. 9. 2014, 10:20
Řá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 ==

Spravce: Přidán odkaz na Algoritmus

2013-10-17T11:57:02Z

Přidán odkaz na Algoritmus

← Starší verze		Verze z 17. 10. 2013, 11:57
Řá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 → lepší algoritmus!	+	<div class="Poznamka">Rychlejší algoritmus → lepší algoritmus!</div>

−	;Problém: čas je ovlivněn i:	+	;Problém — č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 — 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]

Spravce: Vytvoření stránky

2013-10-17T11:48:02Z

Vytvoření stránky

Nová stránka

[[Category:VSE]][[Category:Informatika]][[Category:Programování]]

== Složitost jako míra pro srovnání 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,...)
*zajímá nás, který ze dvou algoritmů vrátí výsledek dříve
Rychlejší algoritmus → lepší algoritmus!

;Problém: čas je ovlivněn i:
* volbou konkrétního zadání stejného problému,
* výkonem počítače,
* kvalitou implementace algoritmu,
* použitým programovacím jazykem,
* použitými knihovnami,
* ...

; Zjednodušení:
*Ne č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 <code>O(f(N))</code>
**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(N2) — kvadratický
*O(N3) — kubický
*Polynomiální
**roste jako libovolný polynom (omezen O(Ni), kde i je lib. konstanta).
*O(2N) — exponenciální
** 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
* 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

== Zdroje ==
*[http://cs.wikipedia.org/wiki/Asymptotick%C3%A1_slo%C5%BEitost Wikipedia.org > Asymptotická složitost]