Complexité temporelle de la boucle imbriquée

j'ai besoin de calculer le temps de la complexité du code suivant:

for (i = 1; i <= n; i++)
{
  for(j = 1; j <= i; j++)
  {
   // Some code
  }
}

Est-ce O (N^2)<!--5?

18
demandé sur Lii 2009-02-09 03:05:05

5 réponses

Oui, Les boucles imbriquées sont une façon d'obtenir rapidement une grosse notation O.

typiquement(mais pas toujours) une boucle imbriquée dans une autre causera O (n2).

Pensez à ce sujet, la boucle interne est exécutée j'fois, pour chaque valeur de i. La boucle extérieure est exécutée n fois.

donc vous voir un modèle d'exécution comme ceci: 1 + 2 + 3 + 4 + ... + n fois

par conséquent, nous pouvons lier le nombre d'exécutions de code en le disant de façon évidente exécute plus de n fois (limite inférieure), mais en termes de n Combien de fois exécutons-nous le code?

Eh bien, mathématiquement nous pouvons dire qu'il n'exécutera pas plus de n2 fois, nous donnant un scénario du pire et donc notre grand-oh lié de O(n2). (Pour plus d'informations sur la façon dont nous pouvons mathématiquement dire cela, regardez le Série)

Big-Oh ne mesure pas toujours exactement combien de travail est fait, mais donne habituellement une approximation fiable de scénario du pire des cas.

4 ans plus tard Modifier: Parce que ce post semble obtenir une bonne quantité de trafic. Je veux expliquer plus en détail comment nous avons lié l'exécution à O (n2) en utilisant la série de puissance

à partir du site web: 1+2+3+4...+n = (n2 + n)/2 = n2/2 + n/2. Comment transformer cela en O(n2)? Ce que nous disons (fondamentalement) est que n2 >= n2/2 + n/2. Est-ce vrai? Nous allons faire quelques simples de l'algèbre.

  • Multiplier les deux côtés par 2 pour obtenir: 2n2 >= n2 + n?
  • Développez 2n2 pour obtenir:n2 + n2 >= n2 + n?
  • Soustraire n2 des deux côtés pour obtenir: n2 >= n?

il doit être clair que n2 >= n (pas strictement plus grand que, en raison du cas où n=0 ou 1), en supposant que n est toujours un entier.

Big O complexité est légèrement différent de ce que je viens de dire, mais c'est l'essentiel. En réalité, Big O complexity demande s'il y a une constante s'appliquer à une fonction telle qu'elle est plus grande que l'autre, suffisamment grande entrée (Voir wikipédia page)

40
répondu AndyG 2018-04-10 19:35:33

un moyen rapide d'expliquer ceci est de le visualiser.

O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O

dans ce cas, c'est:

O
O O
O O O
O O O O
O O O O O
O O O O O O
O O O O O O O
O O O O O O O O
17
répondu Krys Jurgowski 2014-11-08 00:09:17

en effet, C'est O(N^2). Voir également un exemple similaire avec le même runtime ici.

9
répondu Chris Bunch 2017-05-23 11:54:04

tout d'abord, nous considérerons les boucles où le nombre d'itérations de la boucle interne est indépendant de la valeur de l'indice de la boucle externe. Par exemple:

 for (i = 0; i < N; i++) {
     for (j = 0; j < M; j++) {
         sequence of statements
      }
  }

la boucle extérieure s'exécute N fois. Chaque fois que la boucle extérieure s'exécute, la boucle intérieure s'exécute M fois. En conséquence, les instructions dans la boucle interne exécutent un total de N * M fois. Ainsi, la complexité totale des deux boucles est O(N2).

0
répondu napender 2014-04-29 10:20:19

sur la première itération de la boucle externe (i = 1), la boucle interne sera itérée 1 fois Sur la 2e itération de la boucle externe (i = 2), la boucle interne itérera 2 fois Sur la 3ème itération de la boucle externe (i = 3), la boucle interne va se répéter 3 fois

.

.

Lors de la dernière itération de la boucle externe (i = n), la boucle interne itère n fois

ainsi, le nombre total de fois que les instructions dans la boucle intérieure seront exécutées sera égal à la somme des entiers de 1 à n, qui est:

((n)*n) / 2 = (n^2)/2 = O(n^2) times 
0
répondu user2831683 2015-04-16 21:03:06