Déterminer les temps d'exécution big-O de ces différentes boucles?

J'ai une série de questions auxquelles j'ai besoin de commentaires et de réponses. Je vais dire ce que je pense, ce n'est pas un devoir mais plutôt préparation pour mon examen.

Mon principal problème est de déterminer les itérations d'une boucle pour les différents cas. Comment vont tenter de comprendre ça?

Évaluer le temps d'Exécution.

T2.

 for(int i =0 ; i < =n ; i++) //runs n times
   for(int j =1; j<= i * i; j++) //same reasoning as 1. n^2
      if (j % i == 0)
         for(int k = 0; k<j; k++) //runs n^2 times? <- same reasoning as above.
            sum++;

Réponse Correcte: N × N2 × N = O(N^4)

Pour les Questions suivantes ci-dessous, je n'ai pas les réponses correctes.

T3. a)

     int x=0; //constant
     for(int i=4*n; i>=1; i--) //runs n times, disregard the constant
         x=x+2*i;

Ma Réponse: O(n)

b) Supposons pour simplifier que n = 3^k

    int z=0;
    int x=0;
    for (int i=1; i<=n; i=i*3){ //runs n/3 times? how does it effect final answer?
       z = z+5;
       z++;
       x = 2*x;
    }

Ma Réponse: O(n)

c) Supposons pour simplifier que n = k^2,

   int y=0; 
   for(int j=1; j*j<=n; j++) //runs O(logn)?  j <= (n)^1/2
   y++; //constant

Ma Réponse: O(logn)

  int b=0; //constant
  for(int i=n; i>0; i--) //n times
    for(int j=0; j<i; j++) //runs n+ n-1 +...+ 1. O(n^2) 
      b=b+5;

Ma Réponse: O(n^3)

(e)

 int y=1;
 int j=0;
 for(j=1; j<=2n; j=j+2) //runs n times
    y=y+i;
 int s=0;
 for(i=1; i<=j; i++) //runs n times
 s++;

Ma Réponse: O(n)

(f)

 int b=0;
 for(int i=0; i<n; i++) //runs n times
   for(int j=0; j<i*n; j++) //runs n^2 x n times? 
      b=b+5;

Ma Réponse: O(n^4)

(g) Supposons pour simplifier que n = 3k, pour un certain entier positif k.

   int x=0;
   for(int i=1; i<=n; i=i*3){  //runs 1, 3, 9, 27...for values of i. 
     if(i%2 != 0) //will always be true for values above
      for(int j=0; j<i; j++) //runs n times
        x++;
    }

Ma Réponse: O (n x log de la base de 3 n? )

(h) Supposons pour simplifier que n = k2, pour un certain entier positif k.

   int t=0;
   for(int i=1; i<=n; i++) //runs n times
      for(int j=0; j*j<4*n; j++) //runs O(logn)
         for(int k=1; k*k<=9*n; k++) //runs O(logn)
            t++;

Ma Réponse: x n logn x log n = O(n log n^2)

(i) Supposons pour simplifier que n = 2s, pour un certain entier positif s.

   int a = 0;
   int k = n*n;
     while(k > 1) //runs n^2
     {
       for (int j=0; j<n*n; j++) //runs n^2
          { a++; }
        k = k/2;
    }

Ma Réponse: O(n^4)

(j)

  int i=0, j=0, y=0, s=0;
  for(j=0; j<n+1; j++) //runs n times
     y=y+j; //y equals n(n+1)/2 ~ O(n^2)
  for(i=1; i<=y; i++) //runs n^2 times
     s++;

Ma Réponse: O(n^3)

(k)
int i=1, z=0;
while( z < n*(n+1)/2 ){ //l'arithmétique de la série, s'exécute n fois
z+=i; i++;
}

Ma Réponse: O(n)

(m) Supposons pour simplifier que n = 2s, pour un certain entier positif s.

  int a = 0;
  int k = n*n*n;
  while(k > 1) //runs O(logn) complexity
   {
     for (int j=0; j<k; j++) //runs n^3 times
      { a--; }
     k = k/2; 
    }

Ma Réponse: O(n^3 log n)

Question 4

http://i.stack.imgur.com/zMkt7.jpg

a) Vrai - depuis sa délimitée ci-dessous par n^2
b) Faux - f(n) ne sont pas strictement plus petit que g(n)
c) Vrai
d) Vrai -bornée par n^10
e) Faux - f(n) ne sont pas strictement plus petit que g(n)
f) Vrai
g) Vrai
h) faux - car n'est pas égale à O(nlogn)
i) vrai
j) pas sûr
k) vous ne savez pas
l) pas sûr - comment devrais-je même essayer ces?*

Merci d'avance.

source d'informationauteur warpstar

27

Allons par le biais de ces une à la fois.

La partie (a)
```
 int x=0; //constant
 for(int i=4*n; i>=1; i--) //runs n times, disregard the constant
     x=x+2*i;
```
Ma Réponse: O(n)

Yep! C'est correct. La boucle s'exécute en O(n) fois et ne O(1) travailler par itération.

La partie (b)
```
int z=0;
int x=0;
for (int i=1; i<=n; i=i*3){ //runs n/3 times? how does it effect final answer?
   z = z+5;
   z++;
   x = 2*x;
}
```
Ma Réponse: O(n)

Pas tout à fait. Réfléchir sur les valeurs de i que la boucle progresse. Il va prendre la série de valeurs 1, 3, 9, 27, 81, 243, ..., 3^k. Depuis i est triplé à chaque itération, il prend des puissances successives de trois.

La boucle clairement seulement O(1) par itération, la question principale ici est de savoir comment le nombre total d'itérations, il y aura. La boucle s'arrête lorsque i > n. Si nous laissons k être arbitraire itération de la boucle, la valeur de i à l'itération k sera de 3^k. La boucle s'arrête lorsque la 3^k > n, ce qui arrive lorsque k > log₃ n. Par conséquent, le nombre d'itérations n'est O(log n), de sorte que le total de la complexité est O(log n).

La partie (c)
```
int y=0; 
for(int j=1; j*j<=n; j++) //runs O(logn)?  j <= (n)^1/2
    y++; //constant
```
Ma Réponse: O(logn)

Pas tout à fait. Notez que j est encore augmente de façon linéaire, mais la boucle s'exécute tant que j² ≤ n. Cela signifie que dès que j dépasse √ n, la boucle s'arrête. Par conséquent, il n'y aura que O(√n) itérations de la boucle, et puisque chacun ne O(1) le travail, le travail total réalisé est O(√n).

La partie (d)
```
int b=0; //constant
for(int i=n; i>0; i--) //n times
   for(int j=0; j<i; j++) //runs n+ n-1 +...+ 1. O(n^2) 
      b=b+5;
```
Ma Réponse: O(n^3)

Pas tout à fait. Vous êtes doublement de comptage de beaucoup de travail que vous devez faire. Vous avez raison que l'intérieur de la boucle sera exécuté n + (n-1) + (n-2) + ... + 1 fois, ce qui est O(n²) temps, mais vous êtes déjà résumant à travers toutes les itérations de la boucle externe. Vous n'avez pas besoin de multiplier cette valeur par O(n) une fois de plus. La réponse la plus précise serait O(n²).

La partie (e)
```
int y=1;
int j=0;
for(j=1; j<=2n; j=j+2) //runs n times
   y=y+i;

int s=0;
for(i=1; i<=j; i++) //runs n times
   s++;
```
Ma Réponse: O(n)

Yep! Exactement droite.

Partie (f)
```
int b=0;
for(int i=0; i<n; i++) //runs n times
    for(int j=0; j<i*n; j++) //runs n^2 x n times? 
       b=b+5;
```
Ma Réponse: O(n^4)

Encore une fois, je crois que vous êtes surévalué. La boucle intérieure va exécuter 0 + n + 2n + 3n + 4n + ... + n(n-1) = n(0 + 1 + 2 + ... + n - 1) fois, de sorte que le total des travaux est de O(n³). Vous ne devriez pas multiplier par le nombre de fois que la boucle externe fonctionne parce que vous êtes déjà résumant à travers toutes les itérations. Le plus précis d'exécution serait O(n³).

Partie (g)
```
int x=0;
for(int i=1; i<=n; i=i*3){  //runs 1, 3, 9, 27...for values of i. 
   if(i%2 != 0) //will always be true for values above
      for(int j=0; j<i; j++) //runs n times
         x++;
 }
```
Ma Réponse: O (n x log de la base de 3 n? )

La boucle externe ici en effet exécuter en O(log n) fois, mais nous allons voir comment beaucoup de travail à l'intérieur de la boucle. Vous avez raison que la if instruction renvoie toujours true. Cela signifie que la boucle intérieure va le faire 1 + 3 + 9 + 27 + ... + 3^{₃ n} de travail. Cette sommation, cependant, fonctionne à (3^{₃ n + 1} - 1) /2 = (3n + 1) /2. Par conséquent, le travail total réalisé ici est seulement O(n).

Partie (h)
```
int t=0;
for(int i=1; i<=n; i++) //runs n times
   for(int j=0; j*j<4*n; j++) //runs O(logn)
      for(int k=1; k*k<=9*n; k++) //runs O(logn)
         t++;
```
Ma Réponse: x n logn x log n = O(n log n^2)

Pas tout à fait. Regardez la deuxième boucle. Ce fait s'exécute en O(√n) fois à l'aide de la même logique que l'une des parties précédentes. Cette troisième boucle interne également s'exécute en O(√n) fois, et ainsi tout le travail fait en O(n²).

Partie (i)
```
int a = 0;
int k = n*n;
while(k > 1) //runs n^2
{
    for (int j=0; j<n*n; j++) //runs n^2
       { a++; }
     k = k/2;
}
```
Ma Réponse: O(n^4)

Pas tout à fait. La boucle externe commence par k initialisé à n²mais remarquez que k est divisé par deux à chaque itération. Cela signifie que le nombre d'itérations de la boucle externe sera log (n²) = 2 log n = O(log n), de sorte que l'extérieur de la boucle ne s'exécute que O(log n) fois. Que la boucle interne est O(n²) de travail, de sorte que le total d'exécution est O(n² log n).

Partie (j)
```
int i=0, j=0, y=0, s=0;
for(j=0; j<n+1; j++) //runs n times
   y=y+j; //y equals n(n+1)/2 ~ O(n^2)
for(i=1; i<=y; i++) //runs n^2 times
   s++;
```
Ma Réponse: O(n^3)

Proche, mais pas tout à fait! La première boucle s'exécute en temps O(n) et par le temps qu'il fait, la valeur de j est Θ(n²). Cela signifie que la deuxième boucle pistes pour le temps Θ(n²), de sorte que le total du temps passé est en Θ(n²).

Partie (k)
```
 int i=1, z=0;
 while( z < n*(n+1)/2 )//arithmetic series, runs n times
 {
       z+=i; i++;
 }
```
Ma Réponse: O(n)

C'est correct!

Partie (l)

C'est bizarre, il n'y a pas de partie (l).

Partie (m)
```
int a = 0;
int k = n*n*n;
while(k > 1) //runs O(logn) complexity
{
   for (int j=0; j<k; j++) //runs n^3 times
   { a--; }
   k = k/2; 
}
```
Ma Réponse: O(n^3 log n)

Proche, mais pas tout à fait. Vous avez raison que la boucle externe s'exécute en O(log n) et que la boucle interne ne O(n³) le travail sur la première itération. Cependant, regardez le nombre d'itérations de la boucle interne de plus près:

n³ + n³ /2+ n³ /4 + n³ /8 + ...

= n³ (1 + 1/2 + 1/4 + 1/8 + ...)

≤ 2n³

Ainsi tout le travail effectué ici est en fait seulement O(n³), même si il y a des log n itérations.

Question 4

Vos réponses sont correctes, sauf pour ces:

f) Vrai

C'est en fait faux. L'expression de gauche est

(3/2)n^3/2 + 5n² + lg n

qui est pas Ω(n² √n) = Ω(n^5/2)

For (j), note que log n⁶ = 6 n log. Est-ce que c'?

Pour (k), demandez-vous si les deux côtés sont O et Ω l'un de l'autre. Que trouvez-vous?

Pour (l), utiliser le fait que a^{_b c} = c^_ba. Est-ce que c'?

Espérons que cette aide!

Vous devez vous connecter pour publier un commentaire.

La partie (a)

La partie (b)

La partie (c)

La partie (d)

La partie (e)

Partie (f)

Partie (g)

Partie (h)

Partie (i)

Partie (j)

Partie (k)

Partie (l)

Partie (m)

Question 4