Quel est le Big-O d'une boucle imbriquée, où nombre d'itérations dans la boucle interne est déterminée par l'itération courante de la boucle externe?

Question

Quelle est la complexité du temps Big-O des boucles imbriquées suivantes:

for(int i = 0; i < N; i++) 
{
    for(int j = i + 1; j < N; j++)
    {
        System.out.println("i = " + i + " j = " + j);
    }

}

Serait-il O (N ^ 2) encore?

Answer 1

Yep, il est toujours O (n ^ 2), il a un plus petit facteur constant, mais qui ne porte pas atteinte à la notation O.

Answer 2

Oui. Rappelons la définition du Big-O: O (f (n)) par définition dit que le temps d'exécution T (n) ≤ kf (n) pour une constante k . Dans ce cas, le nombre d'étapes sera (n-1) + (n-2) + ... + 0 , qui se réarrange à la somme de 0 à n-1; c'est

T (n) = (n-1) ((n-1) +1) / 2 .

Réorganiser et que vous pouvez voir que T (n) sera toujours ≤ 1/2 (n²); par la définition, ainsi T (n) = O (n²) .

Answer 3

Il est N au carré si vous ignorez le System.out.println. Si vous supposez que le temps pris par qui sera linéaire dans sa sortie (ce qui peut bien ne pas être, bien sûr), je suppose que vous vous retrouvez avec O ((N ^ 2) * log N).

Je mentionne cela ne pas être pointilleux, mais juste pour signaler que vous ne tout simplement pas besoin de prendre les boucles évidentes en compte lors de l'élaboration de la complexité -. Vous devez regarder la complexité de ce que vous appelez ainsi

Answer 4

Oui, ce serait N carré. Le nombre réel d'étapes serait la somme de 1 à N, qui est 0,5 * (N - 1) ^ 2, si je ne me trompe pas. Big O ne prend en compte le plus exponant et pas constantes, et donc, cela est encore N carré.

Answer 5

Si vous avez eu N = 10, vous itérations serait la suivante: 9 + 10 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1. (Ce qui est:. Dix itérations et neuf itérations plus huit itérations ... etc).

Maintenant, vous devez trouver dans la plus combien de fois vous pouvez obtenir un N (10 dans l'exemple):

1: (10) 2: (9 + 1), 3: (8 + 2) 4: (7 + 3), 5: (6 + 4). Ce qui est 5 fois ... et repose 5 itérations.

Maintenant, vous savez que vous avez cinq dizaines + 5:

10 (5) + 5

En termes de f (n) (ou N), on peut facilement voir que ce serait:

f (n) = n (n / 2) + n / 2 = (n ^ 2) / 2 + n / 2 = (n ^ 2 + n) / 2 ... ceci est exactement la complexité de ceux-ci boucle imbriquée.

Mais, compte tenu du comportement asymptotique de Big O, on peut se débarrasser des valeurs moins importantes de f (n), qui sont le seul n et le dénominateur.

Résultat: O (n ^ 2)

Answer 6

AFAIL, étant commencée à partir de la boucle interne à travers les extérieurs est de manière adéquate pour le calcul de la complexité de la boucle imbriquée.