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 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 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 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.