n	lg n		n lg n	n (lg n)^2	n^3/2	n^2
10	3	3	33	18	32	100
20	4	4	86	42	89	400
30	5	5	147	66	164	900
40	5	6	213	92	253	1 600
100	7	10	664	258	1 000	10 000
200	8	14	1 529	553	2 828	40 000
300	8	17	2 469	861	5 196	90 000
400	9	20	3 458	1 176	8 000	160 000
500	9	22	4 483	1 497	11 180	250 000
600	9	24	5 537	1 823	14 697	360 000
1 600	11	40	17 030	5 220	64 000	2 560 000
2 600	11	51	29 495	8 757	132 575	6 760 000
3 600	12	60	42 530	12 374	216 000	12 960 000
4 600	12	68	55 970	16 046	311 987	21 160 000
14 600	14	121	201 972	54 303	1 764 125	213 160 000
24 600	15	157	358 825	93 953	3 858 359	605 160 000

liczba operacji na sek.	zadanie o rozmiarze 1 miliona			zadanie o rozmiarze 1 miliarda
		n	n lg n	n^2	n	n lg n	n^2
10^6	sekundy	sekundy	tygodnie	godziny	godziny	nigdy
10^9	natychmiast	natychmiast	godziny	sekundy	sekundy	dziesiątki lat
10^12	natychmiast	natychmiast	sekundy	natychmiast	natychmiast	tygodnie

funkcja	nazwa	przykład	przybliżenie
	podłoga		x
	sufit		x
lg n	logarytm o podstawie dwa	log 1024=10	1,44 ln n
Fn lub F(n)	liczby Fibonacciego	F10=55
Hn lub H(n)	liczby harmoniczne	H10=2,9	ln n +γ
n!	silnia	10!=3628800	(n/e)^n
lg (n!)		lg(100!)≈520	n lg n -1,44 n

Ciąg Iiczb:

0, 1, 1,2,3,5,8, 13,21,34,55,89, 144,233,377...

można uzyskać na podstawie następującego wzoru rekurencyjnego:

void szukaj(int *a, int lewy, int prawy, int x);

main()

{

int tab[]={1,2,3,6,-7,56,5,1,0,-34};

szukaj(tab,0,9,67);

}

void szukaj(int *a, int lewy, int prawy, int x)

{

if (lewy>prawy)

printf("Element %d nie zostaa znaleziony",x);

else

if(*(a+lewy)==x)

printf("Znalazlem %d szukany element",x);

else

szukaj(a,lewy+1,prawy,x);

}

float fibona(float i);

main()

{

float c;

c=fibona(10);

}

float fibona(float i)

{

if(i<2)

return 1;

else

return fibona(i-1)+fibona(i-2);

}

float fibona1(float i)

{

float h[20],j;

h[0]=1;h[1]=1;

for(j=2;j<i;j++)

h[j]=h[j-1]+h[j-2];

return h[i-1];

}

y=n³

y=2ⁿ

y= n ²

y=n log ₁₀ n

y= n

y=ln n

c*O(f(n)) = O(f(n))

O(f(n)) + O(f(n)) = O(f(n))

O(O(f(n))) = O(f(n))

O(f(n))O(g(n)) = O(f(n)g(n))

O(f(n)g(n)) = f(n)O(g(n))

int tab[n][n];

void zerowanie()

{

int i,j;

i=0; t_a

while(i<n) t_c

{

j=0; t_a

while(j<=i) t_c

{

tab[i][j]=0; t_a

j=j+1; t_a

}

i=i+1; t_a

}

}

t_a czas wykonania instrukcji przypisania,

t_c czas wykonania instrukcji orównania,

float silnia(float i)

{

if(i==0) return 1;

return i * silnia(i-1);

}

float silnia1(float x)

{

float t,i;

for(t=1,i=1;i<=x;i++) t*=i;

return t;

}

---