Big O pour une série imbriquée de boucles for

J'ai une question sur le calcul des temps de fonctionnement Big O pour une série de boucles, qui sont imbriquées dans une boucle for externe.Big O pour une série imbriquée de boucles for

Par exemple:

 

for (50,000 times) 
{ 
    for (n times) 
    { 
     //Do something 
    } 
    for (n-2 times) 
    { 
     //Do something 
    } 
    for (n times) 
    { 
     //Do something 
    } 
    for (n-2 times) 
    { 
     //Do something 
    } 
}

La boucle extérieure est une constante, donc je pense que c'est ignoré. Est-ce alors aussi facile que de faire le calcul suivant?

N + N-2 + N + N-2

2N + 2 (N-2)

4N - 4

O (4N - 4)

O (4N) - après avoir retiré la constante -4

Est-ce correct?

Merci.

Source

2010-11-28 Tom W

Je pense que c'est correct, mais vous avez une autre constante à supprimer: O (4n) est juste O (n). –

Ceci est O (n)

(vous ne souhaitez que ce qui est le « plus grand » partie de l'équation, et vous arrachez la constante).

Si vous aviez une boucle i de 1..n et une autre boucle à l'intérieur j de i..n, il serait O (n^2).

Source

2010-11-28 01:01:19

Merci. Je pensais que cela pourrait être le cas, mais cela ne semblait pas correct. Je suppose que ce cas avec 50 000 itérations a montré une limitation de Big O, car toutes les constantes sont ignorées. –

@Tom, non, Big-O montre comment le pire scénario _scales_. Si vous doublez la taille d'entrée, comment l'algorithme fonctionnera-t-il? Pour un algorithme s'exécutant dans O (n^2), alors le pire temps d'exécution peut être double lorsque vous doublez l'entrée. La boucle de 50.000 annule dans cette équation. –

OK merci ... Je le comprends maintenant. –

Ceci est correct. Vous ajoutez juste quatre boucles qui est O(N). Donc, il est 4O(N), alors il est multiplié par 50, 000 qui est un grand nombre mais il n'est pas N dépendant.

Source

2010-11-28 01:52:48 fastcodejava

Ceci est O (N). Mais dans ce contexte, en fonction de ce que vous avez pour N, la constante pourrait avoir un impact important sur les performances de votre algorithme.

Source

2010-11-28 02:42:56 Shuo

Big O pour une série imbriquée de boucles for

Répondre

Questions connexes