http://vitas.matfyz.cz/cv/slozitost.html

Složitost programu

aneb počítání hvězdiček.

Tato stránka se snaží na jednoduchých příkladech ukázat počítání složitosti algoritmu. Byla vytvořena jako doplněk k cvičení Programování I. pro Informatiky.

Poznámka 1: Příklady jsou různě těžké. Myslím, že prvák informatik by je mohl zvládat asi asi takto:

Příklady 1 a 2: úšklebek nad tím, proč vás otravuji s takovou trivkou.

Příklady 3, 5, 7 a 8: na první pohled jasná třída složitosti (O(.) . Po kratším zamyšlení přesný počet hvězdiček.

Příklad 4: na první pohled jasná složitost. Kdybyste znali vzoreček na i ² přesný počet hvězdiček není problém.

Příklad 9: po chvilce počítání na papíře třída složitosti, kdyby někdo moc chtěl tak vypotíte i přesný počet hvězdiček.

Příklady 6, 11, 12 a 13: po krátkém zápase třída složitosti.

Příklady 14 a 15: Když si přečtete důkaz, pochopíte ho a jste ho schopni vysvětlit někomu jinému.

Poznámka 2: Protože html není žádný , nejsem si jistý jak mnou vysázené vzorce zobrazí váš prohlížeč (dělal jsem co jsem mohl). Pro jistotu však uvedu slovní překlad:

ⁿ_i=1 znamená "suma pro i od jedné do n",
x znamená "horní celá část x".
log₂(n) znamená "logaritmus n o základu 2".
x znamená "dolní celá část x".
a ^b znamená "a na b'tou".
x $\in$ M znamená "x je prvkem M".

Množina funkcí O(g(n))

O(g(n)) = { f(n) | $\exists$ c ,n₀ $\forall$ n > n₀: f(n) < c . g(n)}

Lidsky řečeno: f(n) je z O(g(n)) , pokud je (až na multiplikativní konstantu) menší než g(n) (pro všechna dostatečně velká n ).

Příklady:

3n + 5 $\in$ O(n)

5 n ² + 7 n - 15 $\in$ O(n ²)

O(5 n ² + 7 n - 15) = O(n ²)

O(n ⁵⁰) < O(1.5 ⁿ) < O(2 ⁿ ) < O(2 ²ⁿ)

Dobré vědět:

1 + 2 + ... + n = ⁿ_i=1 i = ¹/₂ (n+1)n

1 + 4 + 9 + ... + n ² = ⁿ_i=1 i ² = ¹/₆ n(n + 1)( 2 n + 1)

ⁿ_i=1 i ^a $\in$ O(n ^a+1)

ⁿ_i=0 2 ⁱ = 2 ⁿ⁺¹ - 1

Příklad č.1


	for i:= 1 to N do 
		write('*');

Hvězdičky: h = n .

Složitost: O(n) .

Příklad č.2


	for i := 1 to N do 
		for j := 1 to N do 
			write('*');

Hvězdičky: h = n ² .

Složitost: O(n ²) .

Příklad č.3


	for i := 1 to N do 
		for j := 1 to i do
			write('*');

Hvězdičky: h = 1 + 2 + ... + n = ¹/₂ n(n+1) .

Složitost: O(n ²)

Příklad č.4


	for i := 1 to N do begin
		for j := 1 to i * i do
			write('*');

	end;

Hvězdičky: h = 1 + 4 + 9 + .. n ² = ¹/₆ n(n+1)(2n+1)

Složitost: O(n ³)

Příklad č.5


	for i := 1 to N do begin
		for j := 1 to N do
			for k := 1 to j do
				write('*');

	end;

Hvězdičky: h = n ⁿ_i=1 i = ¹/₂ n ²(n+1)

Složitost: O(n ³)

Příklad č.6


	for i := 1 to N do begin
		for j := 1 to i do
			for k := 1 to j do
				write('*');

	end;

Hvězdičky: h = ⁿ_i=1 ( ⁱ_j=1 j) = ⁿ_i=1 ¹/₂ i (i+1) = ¹/₂ (ⁿ_i=1 i ² + ⁿ_i=1 i ) = ¹/₂ ( ¹/₆ n(n+1)(2n+1) + ¹/₂ n(n+1)) < n ³ )

Složitost: O(n ³)

Příklad č.7


	for i := 1 to N do begin
		for j := 1 to N * N do
			write('*');

		for k := 1 to N do
			write('*');
	end;

Hvězdičky: h = n ³ + n ²

Složitost: O(n ³ + n ² ) = O(n ³) . Třetí for-cyklus (s proměnou k ) se ve výsledné (asymptotické) složitosti ztratí.

Příklad č.8


	for i := 1 to N do begin
		for j := 1 to 100 do
			write('*');
	end;

Hvězdičky: h = 100 * n

Složitost: O(100n) = O(n) . For-cyklus s konstantním počtem průchodů výslednou (asymptotickou) složitost také neovlivní.

Příklad č.9


	i := 1;	
	h := 0;
	while i <= N do begin
		i := i * 2;

		h := h + 1;
		write('*');
	end;

Hvězdičky: po vytisknutí h 'té hvězdičky bude i = 2 ^h . Podmínka n i = 2 ^h je splněna pro log₂(n) h , nejmenší h , které je vyšší je: h = log₂(n) + 1

Složitost: O(log₂(n)) = O(log(n))

Příklad č.10


	i := 1;	
	while i <= N do begin
		for j := 1 to N do
			write('*');
		i := i * 2;
	end;

Hvězdičky: while-cyklus se provede (log₂(n)+1) )'krát. V každém z kroků pak proběhne vnitřní for-cyklus n 'krát. tj. h = (log₂(n)+1)n .

Složitost: O(n log(n))

Příklad č.11


	i := 1;	
	while i <= N do begin
		for j := 1 to i do
			write('*');
		i := i * 2;
	end;

Hvězdičky: Počet otoček while-cyklu označme L = log₂(n)+1 . Počet hvězdiček pak bude: h = ^L_i=1 2 ⁱ = 2 ^L+1 - 1 = 2 ^{log₂(n) + 1} = nejbližší_vyšší_mocnina_dvou_než(n) < 2n .

Složitost: O(2n) = O(n)

Příklad č.12


	for j := 1 to N do begin
		i := 1;	
		while i <= j do begin
			write('*');
			i := i * 2;
		end;
	end;

Hvězdičky: ⁿ_i=1 log₂(i) + 1 =(asi) log₂(n!) =(asi) n log₂(n)

Složitost: O(n log₂(n)) , to je vidět už jen z toho, že kdyby while-cyklus běžel až do n vytisklo by se n log₂(n) hvězdiček. Předchozí odstavec naznačuje, že tento odhad je i minimální.

Příklad č.13


var
	a: array [1..N+1] of Boolean;

	{ pole a je na začátku vyplněno hodnotou False}
begin
	
	while not a[N+1] do begin

		i := 1;
		while a[i] do begin
			a[i] := False;
			i := i + 1;
			write('*');
		end;
		a[i] := True;
		write('@');
	end;
end.

Hvězdičky: Nejprve se zamyslíme, co vlastně algoritmus děla: vnitřní while-cyklus (+následující řádek) přičte jedničku k binárnímu číslu zapsanému v poli a (nejvýznamnější bity jsou na konci). Pokud si toto uvědomíme, zjistíme, že vnější while cyklus skončí až se napočítá do 1000...00 (nul je N ) je zřejmé, že počet znaků '@' bude přesně @ = 2 ^N .

Zajímavější je určit počet hvězdiček. Počet N -bitových čísel končících (v binárním zápise) na nulu je ^{2 ^N}/₂=2 ^N-1 , končících na právě 1 jedničku 2 ^N-2 . Obecněji: čísel končících na pravě i jedniček je 2 ^N-i-1 . Pro číslo končící na právě i jedniček vytiskne program i hvězdiček (pro i=N je jich N). Takže dohromady: N+^N-1_i=0 i 2 ^N-i-1= N + ^N-1_i=0 ^N-1_j=i 2 ^N-j-1= N + ^N-1_i=0 2 ^N-i-1= N + 2 ^N - 1 - N = 2 ^N - 1 . Tedy (možná poněkud překvapivě) hvězdiček bude méně (přesně o jednu) než '@'.

Složitost: O(2 ^N) .

Příklad č.14


procedure rozdel_a_panuj(a,b:Integer);
var
	i:Integer;
begin
	write('@')
	if a = b then
		write('*')
	else
	begin
		for i := a to b do
			write('*');

		rozdel_a_panuj(a, (a + b)div 2);
		rozdel_a_panuj((a + b) div 2 + 1, b);
	end;
end;

begin
	rozdel_a_panuj(1,N);
end.

Hvězdičky: Průběh procedury rozdel_a_panuj si můžeme představit, jako binární strom jehož listy odpovídají jednomu z čísel 1 .. N, a vnitřní vrcholy sjednocení svých synů. Znak '@' se vytiskne přesně tolikrát kolik má tento strom vrcholů. Protože počet listů je o jedna větší než počet vnitřních vrcholů (snadné cvičení na matematickou indukci) je @=2N-1 ,

Strom bude mít hloubku log₂(N) , v každém patře se vytiskne N hvězdiček (až na poslední patro, které nemusí být úplné). Proto N log₂(N) h N log₂(N) $\in$ O(N log(N)) . (pokud bychom chtěli být přesní: h = N log₂(N) + (N+1) - 2 ^log₂(N) )

Složitost: O(h) = O(N log(N)) .

Příklad č.15


function Fibonacci(N:Integer) : Integer;
begin
	write('*')
	if N = 0 then
		Fibonacci := 0
	else if N = 1 then begin
		write('@');
		Fibonacci := 1;
	end
	else
		Fibonacci := Fibonacci(N-1) + Fibonacci(N-2);
	end;
end;

Hvězdičky: Toto je odstrašující příklad, jak se nemají počítat Fibonačiho čísla. Je vidět, že znak '@' se vytiskne přesně tolikrát, kolik bude výsledek (za každou jedničku jednou). Všeobecně se ví, že N-té Fibonačiho číslo je:

Fib(n) = $\sqrt5/5(((1+\sqrt5)/2)^n-((1-\sqrt5)/2)^n)$

Druhý člen v závorce se dá odhadnout konstantou, takže počet '@' bude O((1+ $\sqrt5$ ) ^N) (<O(1.62 ^N) ).

Počet hvězdiček je dán rekurzivním předpisem (trošku jiným než Fibonačiho čísla, ale podobným) h(0)=1; h(2)=1; h(N) = 1 + h(N-1) + h(N-2) . Je vidět, že Fib(N) h(N) . Nebudeme se trápit přesným explicitním vyjádřením h(N) , bude nám stačit odhad: h(N)<3 Fib(N) . Důkaz indukcí: h(N+2)= h(N+1) + h(N) + 1 < 3 Fib(N+1) + h(N) + 1 3 Fib(N+1) + h(N) < 3 Fib(N+1) + 3 Fib(N) = 3 Fib(N+2) (qed). Počet hvězdiček je tedy také O((1+ $\sqrt5$ ) ^N) .

Paměťové nároky jsou O(N) . Při každém volání si totiž musíme na zásobníku pamatovat minimálně výsledek Fibonacci(N-1).

Implementovat tuto fci v O(N) (a s konstantní pamětí) necháme pro laskavého čtenáře jako cvičení.

Složitost: O((1+ $\sqrt5$ ) ^N)

Zpět:

http://vitas.matfyz.cz/cv/slozitost.html