La complexité d'un algorithme (boucles imbriquées)

Je donne le code pour un algorithme en tant que tel:La complexité d'un algorithme (boucles imbriquées)

1 sum =0; 
2 for(i=0; i<n; i++) 
3  for(j=1; j<= n; j*=3) 
4  sum++;

On me dit que cet algorithme fonctionne dans O(nlogn) où log est dans la base 3. donc que je reçois la deuxième ligne court n times, et puisque la ligne 3 est indépendante de la ligne 2, je devrais multiplier les deux pour obtenir le Big O, cependant, je ne suis pas sûr de la façon dont la réponse est nlogn (log dans la base 3), est leur moyen garanti de comprendre cela à chaque fois? On dirait qu'avec des boucles imbriquées, il y a un cas différent qui peut survenir à chaque fois.

Source

2015-12-06 TTEd

L'exécution O() de la deuxième boucle, à elle seule, s'exécute exactement (1/3) * n fois, n'est-ce pas? Donc, c'est mieux que O (n), mais évidemment constant, donc nous utilisons log comme limite supérieure car c'est entre les deux. – James

avec la complexité du temps la base du logarithme est sans importance, donc il est éludé et simplement 'O (log n)' – user8

Ce qui vous a été dit est correct. L'algorithme s'exécute en O(nlog(n)). La troisième ligne: for(j=1; j<= n; j*=3) s'exécute en O(log3(n)) car vous multipliez par 3 à chaque fois. Pour le voir plus clairement résoudre le problème: combien de fois vous avez besoin de multiplier 1 par 3 pour obtenir n. Ou 3^x = n. La solution is x = log3(n)

Source

2015-12-06 03:08:13

S'il vous plaît arrêtez d'écrire des constantes dans la notation Big O, il décrit la vitesse de croissance de la fonction par rapport au paramètre d'entrée s), pas de temps d'exécution estimé. – user3707125

@ user3707125 Où voyez-vous les constantes? J'ai écrit à propos de log3 parce que l'OP demandait explicitement d'où venait log3. –

ici: "s'exécute dans' O (log3 (n)) '", il serait plus correct de dire "court environ log3 (n) fois, ce qui entraîne une complexité asymptotique de O (log (n))". – user3707125

Sur la deuxième boucle, vous avez j *= 3, ce qui signifie que vous pouvez diviser n par 3 log3 (n) fois. Cela vous donne la complexité O (logn).
Puisque votre première boucle a un O (n), vous avez O (nlogn) à la fin

Source

2015-12-06 03:03:36 Jorgel

Oui. Algo s'exécute en nlog (n) fois où log est la base 3.

La méthode la plus simple pour calculer la complexité consiste à calculer le nombre d'opérations effectuées.

La boucle for externe s'exécute n fois. Et calculons combien de fois chaque boucle interne pour chaque n. Donc, pour n = 1,2, la boucle interne est exécutée 1 fois. Pour n = 3,4,5,6,7,8 intérieur pour boucle exécute 2 fois. Et ainsi de suite ...

Cela signifie que la boucle for interne s'exécute en temps logarithmique (log (n)) pour chaque n.

Donc n * log (n) sera une complexité totale.

Source

2015-12-06 03:13:33 achin

La complexité d'un algorithme (boucles imbriquées)

Répondre

Questions connexes