Une autre grande question de notation ... Quel est le Big O pour le code de folling: Mes pensées:
Donc, le casser, je pense que la boucle extérieure est question n ° 2:
Lors de la combinaison des boucles imbriquées, est-il toujours aussi simple que multirmploi le gros o de chaque boucle? O (log2 (n)) , puis chacune des boucles internes est o (n) qui aboutirait à O (n ^ 2 * log2 (n)) question n ° 1 est-ce correct?
4 Réponses :
logn , les deux autres sont n chacun, pour le total de O (n ^ 2 * logn )
- Dans les cas simples, oui. Dans des cas plus complexes, lorsque les index de boucle commencent à des chiffres indiqués par d'autres index, les calculs sont plus complexes.
Lorsque les compteurs de boucle ne dépendent pas de l'autre, il est toujours possible de travailler de l'intérieur vers l'extérieur.
La boucle la plus intérieure prend toujours le temps en O (n), car il boucle n fois quelles que soient les valeurs de i et j.
Lorsque la deuxième exécution de la boucle, il fonctionne pour O (N) d'itérations, chaque itération faisant O (n) pour exécuter le travail de la boucle la plus interne. Cela prend du temps O (n 2 ).
Enfin, lors de l'exécution de la boucle externe, il le fait en O (n 2 ) de travail par itération. Il fonctionne aussi pour O (log n) itérations, car il fonctionne égal au nombre de fois que vous devez diviser par deux n avant d'arriver à 1. Par conséquent, le travail total est O (n 2 log n).
En général, vous ne pouvez pas simplement les boucles se multiplient ensemble, puisque leurs limites peuvent dépendre les uns des autres. Dans ce cas, cependant, car il n'y a pas de dépendance, les runtimes peuvent simplement être multipliées. Espérons que le raisonnement ci-dessus met en lumière les raisons pour lesquelles cela est - c'est parce que si vous travaillez à l'intérieur réflexion sur la quantité de travail chaque boucle fait et combien de fois il le fait, les runtimes finissent par obtenir multipliés ensemble .
J'espère que cela vous aidera!
Pour répondre légèrement (Remarque: légèrement) plus formellement, dire Ensuite, utilisez le théorème suivant:
si f 1 (n) = O (g 1 (n)) et f 2 (n) = O (g < SUB> 2 (N)), puis F 1 (N) × F 2 (N) = O (G 1 (n) × g 2 (n)) Cela nous laisse avec T (n) = O (n 2 logn).
"Combiner des boucles imbriquées" n'est qu'une application de ce théorème. Le problème peut être en déterminant exactement combien d'opérations utilisées par chaque boucle, ce qui est simple. t (n) est l'heure (ou le nombre d'opérations) requis pour terminer l'algorithme. Ensuite, pour la boucle extérieure, t (n) = journal n * t2 (n) , où t2 (n) est le nombre d'opérations à l'intérieur la boucle (ignorer les constantes). De même, T2 (N) = N * T3 (N) = N * N.
(source et preuve)
Vous pouvez procéder formellement à l'aide de la notation Sigma, pour imiter fidèlement vos boucles:
1) Oui 2) Seulement si les boucles ne dépendent pas l'une de l'autre.
Vous pouvez les multiplier si elles sont indépendantes.