J'ai un programme court ici:
Given any n:
i = 0;
while (i < n) {
k = 2;
while (k < n) {
sum += a[j] * b[k]
k = k * k;
}
i++;
}
3 Réponses :
pour la preuve mathématique, la boucle interne peut être écrite comme suit: puis le temps total est O (n loglogn). Pourquoi la boucle interne est-elle T (n) = t (sqrt (n)) +1?
Tout d'abord voir lorsque la boucle interne pause, lorsque K> n, signifie avant que k était au moins sqrt (n) ou à deux niveaux avant sa croissance SQRT (N), le temps d'exécution sera donc T (sqrt (n)). + 2 ≥ T (n) ≥ t (sqrt (n)) + 1.
@Tymek, j'ai mis à jour la réponse, espérons que cela vous aide, mais faites attention à ce que la boucle intérieure ne soit pas sqrt (n) + 1, j'ai prouvé la boucle intérieure est journal de journal n , j'ai dit dans la boucle intérieure nous avoir t (n) = t (sqrt (n)) + 1 .
La complexité du temps d'une boucle est O (journal de journal n) si les variables de boucle sont réduites / augmentées de manière exponentielle par une quantité constante. Si la variable de boucle est divisée / multipliée par une quantité constante, la complexité est O (logn).
par exemple: dans votre valeur de cas de k est comme suit. Que je parle entre parenthèses désignant le nombre de fois où la boucle a été exécutée. pour la prise d'assomption permet de supposer que n est 2 ^ 64 . Maintenant, journal (2 ^ 64) = 64 et journal 64 = journal (2 ^ 6) = 6. Par conséquent, votre programme a couru 6 fois lorsque n est 2 ^ 64 .
Je pense que si les codes sont comme ça, il devrait être n * journal n;
Pour une explication plus détaillée de pourquoi, voici une question à rechercher: Stackoverflow.com/Questtions/487258/...