Alors que les Temps de boucle de complexité
J'ai un algorithme examen.. et je suis un peu pas beaucoup les boucles du temps de la complexité :s j'ai juste commencé à obtenir les bases..
J'ai cette boucle
i=2
while (i<n)
{
i=i*i
x=x+1
}
Je crois que la solution doit être:
(i) se déroulera du 2 à 2k où k = 2me
chaque fois qu'il exécutez l'instruction 1 fois..
donc 1+1+1+.. , cela signifie 1*2k
et à partir de là je ne peux pas continuer..
la deuxième question les gars.. s'il vous plaît recommander un site ou qqch que je peux mettre en pratique certains de ces.. cherché mais n'ai pas trouver :s
Vous devez vous connecter pour publier un commentaire.
La boucle s'exécute tant que la
i
est à moins den
. En d'autres termes, vous avez besoin de trouverk
tel que 22k < n. ==> k = log2log2n. Donc itération de la boucle pour les journaux2log2n fois et à chaque itération, il effectue 2 opérations (multiplication et d'addition) - ces opérations prennentO(1)
temps.==> Le temps d'exécution de la boucle est égale à log2log2n * O(1) ==> au total, la complexité est
O(loglogn)
.n=2^64
=>O(lgn) = 64
; cependant, la boucle ne s'exécute que 6 fois.logn
si l'alimentation dei
à chaque itération a été multiplié par une constante)