Složitosti algoritmu

Algoritmus je popis nějakého postupu.

• délka kódu
• počet provedených instrukcí
• doba běhu programu
• počet cyklů

for(i = 0; i < n; i++){
	printf("*");
}

slozitost je $3n+1$, tj. $O(n)$.

• 1 prirazeni
• n porovnani
• n souctu
• n print

for(i = 0; i < n; i++){
	for(j = 0; h < n; j++>){
		printf("*");
	}
}

slozitost je $n*(3n+1)+1+n = 3n^2+3n+1$, tj. $n^2$.

• 1 prirazeni
• n i++
• n prirazeni
• n^2 j++

for(i = 0; i < n; i++){
	for(j = 0; j < i; j++){
		printf("*");
	}
}

$0+1+2+3+...+n = \frac{(n^2+n)}{2} = \frac{1}{2}n^2 + \frac{1}{2}n^2 = O(n)^2$

while(n >= 1){
	printf("*");
	n = n/2;
}

Bubble sort ma slozitorst $O(n^2)$

Tagy

unix algoritmy