Complexité temporelle d'une boucle triple imbriquée

13

Veuillez considérer la boucle triple imbriquée suivante:

for (int i = 1; i <= n; ++i)
    for (int j = i; j <= n; ++j)
        for (int k = j; k <= n; ++k)
            // statement

L'instruction ici est exécutée exactement $n(n+1)(n+2)\over6$ fois. Quelqu'un pourrait-il expliquer comment cette formule a été obtenue? Je vous remercie.

algorithms time-complexity algorithm-analysis Xin
la source

1

La formule de complexité de l'heure des boucles imbriquées pourrait également être intéressante.

Juho

14

Vous pouvez compter le nombre d'exécutions de la boucle for la plus interne en comptant le nombre de triplets pour lesquels elle est exécutée. $(i,j,k)$

Par les conditions de boucle, nous savons que: . Nous pouvons le réduire au problème de combinatoire simple suivant. $1 \leq i \leq j \leq k \leq n$

Imaginez boîtes de couleur rouge placées dans un tableau de gauche à droite. $n+2$
Choisissez 3 boîtes parmi les et peignez-les en bleu. $n+2$
Formez un triplet comme suit:
- = 1 + nombre de cases de couleur rouge à gauche de la première case bleue. $i$
- = 1 + nombre de cases de couleur rouge à gauche de la deuxième case bleue. $j$
- = 1 + nombre de cases de couleur rouge à gauche de la troisième case bleue. $k$

Donc, nous avons juste besoin de compter le nombre de façons de choisir 3 boîtes parmi boîtes qui est $n+2$ . $n+2 \choose 3$

rizwanhudda
la source

2

Bonne réponse! Les valeurs exactes de i, j, k ne sont pas importantes. Il suffit de savoir que toute case bleue peut être placée dans n positions possibles et que leurs positions sont délimitées: la 2e vient toujours après la 1ère et avant la 3ème.

Dávid Natingga

@rizwanhudda Clear sauf pour la partie

dans

. Pouvez-vous l'expliquer s'il vous plaît?

ressemble au bon nombre.

+ 2

$+2$

n + 2

$n+2$

n + 3

$n+3$

saadtaame

1

@saadtaame Oui. Vous pouvez imaginer avoir

cases rouges, mais avoir la liberté de choisir 3 cases rouges pour peindre le bleu parmi "

cases rouges", car vous ne pouvez pas colorer la première case en bleu (depuis

)

n + 3

$n+3$

n + 2

$n+2$

i \geq 1

$i \geq 1$

rizwanhudda

3

pour moi, il est plus facile de remarquer que la boucle intérieure est exécutée fois et que le nombre total d'exécutions dans la boucle intérieure est $n-i$

$(n-i)+(n-i-1)+(n-i-2)+\ldots+1$

cela peut être réécrit comme et est exécuté fois, donc le nombre total d'exécutions est $\sum_{j=0}^{n-i} n-i-j$ $n$

\sum_{i = 0}^{n} \sum_{j = 0}^{n - i} n - i - j = \frac{n (n + 1) (n + 2)}{6}

$\sum_{i=0}^{n}\sum_{j=0}^{n-i} n-i-j=\frac{n(n+1)(n+2)}{6}$

andy mcevoy
la source

Un défi pour vous: imaginez que vous avez une boucle imbriquée x. Selon la réponse précédente, il exécuterait (n + x-1) choisir x fois. Comment calculeriez-vous votre formule?

Dávid Natingga

heureusement, l'OP n'a pas demandé x-nested! Comment l'autre réponse donnée s'étend-elle à une boucle imbriquée x? Ma réponse devrait simplement obtenir plus de sommes allant de 0 à n, 0 à n-i_1, 0 à n-i_2, ..., 0 à n-i_x. Mais je ne saurais pas calculer cela.

andy mcevoy

1

La réponse ne se développe pas explicitement pour un x général, mais le processus de raisonnement présenté est facile à suivre pour les boucles imbriquées x. Vous venez d'ajouter plus de cases bleues. Je ne sais pas non plus comment je calculerais ces sommes supplémentaires.

Dávid Natingga

Complexité temporelle d'une boucle triple imbriquée

Réponses: