complexité pour les boucles imbriquées

Question

J'essaie de comprendre la complexité d'une boucle for utilisant la notation Big O. Je l'ai déjà fait dans mes autres cours, mais celui-ci est plus rigoureux que les autres parce qu'il est sur l'algorithme actuel. Le code est le suivant:

for(i=n ; i>1 ; i/=2) //for any size n 
{ 
    for(j = 1; j < i; j++) 
    { 
     x+=a 
    } 
} 

et

for(i=1 ; i<=n;i++,x=1) //for any size n 
{ 
    for(j = 1; j <= i; j++) 
    { 
     for(k = 1; k <= j; x+=a,k*=a) 
     { 

     } 
    } 
} 

je suis arrivé que la première boucle est de O (n) la complexité, car il va dans la liste n fois. Quant à la deuxième boucle je suis un peu perdu! Merci pour votre aide dans l'analyse. Chaque boucle est dans son propre espace, ils ne sont pas ensemble.

Answer 1

Considérons le premier fragment de code,

for(i=n ; i>1 ; i/=2) //for any size n 
{ 
    for(j = 1; j < i; j++) 
    { 
     x+=a 
    } 
} 

L'instruction x+=a est exécutée pour un total de n + n/2 + n/4 + ... + 1 fois.

Somme du premier journal n termes d'un G.P. avec départ terme n et un rapport commun 1/2 est, (n (1- (1/2) ^{log n}))/(1/2). Ainsi, la complexité du premier fragment de code est O (n).

Considérons maintenant le deuxième fragment de code,

for(i=1 ; i<=n; i++,x=1) 
{ 
    for(j = 1; j <= i; j++) 
    { 
     for(k = 1; k <= j; x+=a,k*=a) 
     { 

     } 
    } 
} 

Les deux boucles externes appellent ensemble de la boucle la plus interne d'un total de n(n+1)/2 fois. La boucle la plus interne est exécutée au maximum log<sub>a</sub>n fois. Ainsi, la complexité temporelle totale du second fragment de code est O (n log _a n).

Answer 2

EDIT: Je suis d'accord le premier bloc de code est O (n)

Vous décrémenter la boucle extérieure i en plongeant par 2, et dans la boucle intérieure vous exécutez i fois, de sorte que le nombre d'itérations soit une somme sur toutes les puissances de deux inférieures ou égales à N mais supérieures à 0, qui est n ^{log (n) +1} - 1, donc O (n).

Le deuxième bloc de code est O (log _un (n) n) en supposant a est une constante.

Les deux boucles extérieures équivalent à une somme de tous les nombres inférieurs ou égaux à n, qui est n (n-1)/2, de sorte que O (n). Enfin, la boucle interne est la puissance d'une borne inférieure à n, qui est O (log _a n).

Answer 3

Vous pouvez procéder officiellement comme ce qui suit:

Fragment 1:

Fragment 2 (Pochhammer, G-fonction et Approximation de Stirling) :

Avec log(G(n)).

[Mise à jour du fragment 2]:

Avec quelques améliorations de la publication "BOUCLES DISCRET ET PIRE PERFORMANCE DE CAS", par le Dr Johann Blieberger (Tous les cas vérifiés pour a = 2):

Où:

Par conséquent,