[Teoria złożoności] Złożoność w sensie notacji O()

[palcedavosa12]

Hej, mam problem z tymi zadaniami - spróbowałem je zrobić lecz nie mam absolutnej pewności, że są dobrze, szczególne wątpliwości mam przy trzecim.

Sufit/podłoga to określenia funkcji które albo zaokrąglają w górę (sufit) albo w dół (podłoga).

Polecenia dla wszystkich są takie same - Policz ilość porównań i zapisz złożoność w sensie notacji \(\displaystyle{ O \left( \right)}\).

Zad.1

Kod: Zaznacz cały

i=1;
dopóki (i<n) wykonuj:
	j=1;
	wykonuj:
		j=j*3;
	dopóki (j<n);
	i=i+3;

Liczba porównań dla pętli zewnętrznej (iterator i) => \(\displaystyle{ \left\lceil \frac{n}{3} \right\rceil + 1}\)

Liczba porównań dla pętli wewnętrzniej => \(\displaystyle{ \left\lceil \log 3n \right\rceil}\)

Liczba porównań w ogóle => \(\displaystyle{ \left( \left\lceil \frac{n}{3}\right\rceil + 1 \right) \cdot \left\lceil \log 3n \right\rceil}\)

Notacja dużego O =>\(\displaystyle{ O \left( n \cdot \log 3n \right)}\)

Zad.2

Kod: Zaznacz cały

for (i = 0; i<2*n; ++i)
{
	j= i;
	do 
	{
		T[i][j]=i*i + j;
		j=j+1;
	}
	while (j<n);
}

Liczba porównań dla pętli zewnętrznnej => \(\displaystyle{ 2n + 1}\)

Liczba porównań dla pętli wewnętrznej => \(\displaystyle{ n+1}\)

Liczba porównań w ogóle => \(\displaystyle{ \left( 2n+1 \right) \left( n+1 \right)}\)

Notacja dużego O => \(\displaystyle{ O \left( n^2 \right)}\)

Zad.3

Kod: Zaznacz cały

for (i=0; j=n; i<n; i++)
	for( ; j<n-8; j--) 
	T[i][j] = 2* i * j; 

Liczba porównań dla pętli zewnętrznnej =>\(\displaystyle{ n+1}\)

Liczba porównań dla pętli wewnętrznej => \(\displaystyle{ n-1}\)

Liczba porównań w ogóle => \(\displaystyle{ \left( n+1 \right) \left( n-1 \right)}\)

Notacja dużego O =>\(\displaystyle{ O \left( n^2 \right)}\)



Swoją drogą, zauważyłem tendencje, że ćwiczeniowcy dają na studiach zadania, lecz nie ma do nich nigdy odpowiedzi. Ponoć tym się studia różnią od liceum.