O (log n) et la relation de l'algorithme

Question

je ne peux pas toujours bien à analyser O (log n) algorithme

Donc, s'il est emboîté à boucle où les augmentations de boucle interne/diminue par l'une de la multiplication ou la division, alors c'est Big-theta (logn) où sa base est combien elle est divisée par ou multipliée par?

Par exemple:

for(int i=0;i<n;i++) { 
for(int j=1; j<n; j*=5) ... 

this is Big-theta(logn) with base 5 since it is multiplied by 5? 

Un autre exemple:

for(int i=n;i>0;i--) { 
for(int j=i; j>0; j/=10) ... 

this is 
Big-theta(logn) with base 10 since it is divided by 10? 

Je veux dire, je reçois correctement?

Une autre question:

Big-theta (logn) ne fonctionne que pour seule boucle imbriquée? (pour la boucle à l'intérieur de la boucle for)

Answer 1

Si nous pouvons compter combien de fois une boucle for particulière est exécutée, nous pouvons facilement avoir une idée de la complexité. Nous pouvons commencer avec un exemple de boucle simple.

Considérez ce qui suit pour la boucle,

for(int i=1;i<=m;i++) 
{ 
    //.... 
} 

Maintenant ici si nous voulons constater que combien de fois cette boucle for fonctionne alors nous pouvons le faire en écrivant la série (comme il est une série uniforme) et de trouver celui qui est > m(limit). De cette façon, nous pouvons facilement trouver le nombre d'itérations requis par cette boucle for.

Dans cet exemple, si nous écrivons toutes les valeurs possibles de i,

1,2,3,4,5,......,m 

Cette série est Arithmetic Progression. Maintenant, nous avons une équation pour trouver n-th terme de la série comme {a(n) = a(1)+(n-1)*d}. Ici d=1, a(1)=1 maintenant nous devons trouver la valeur maximale n telle que a(n)<=m.

Nous pouvons le faire en plaçant simplement a(n)=m et trouver la valeur n. Voici donc

m = 1+ (n-1)*1 
m = 1+n-1 
m = n 
n = m. 

Voici itérations au total seraient m et nous pouvons donc dire que la complexité de cette boucle est O(m).

Considérons maintenant un exemple que vous avez donné,

for(int j=1; j<n; j*=5)... 

ici si vous écrivez toutes les valeurs de j alors la série serait 1,5,25,125,..... et cette série est maintenant Geometric Progression. Formule pour trouver n-th terme est a(n) = a(1)*(r^(n-1)) et ici a(1)=1 and r=5.

Maintenant mis n(limit) en place de a(n) pour voir combien de fois la boucle est exécutée et laissez-nous renomme limite n que m pour éliminer la confusion,

a(n) = a(1)*(r^(n-1)) 
m = 1*(5^(n-1)) 
m = 5^(n-1) 
Now take log of base 5 on both side 
log (m) = (n-1) //log is of base 5 
n = log(m)+1 

De cette façon, nous pouvons trouver ici que itérations total requis sont n = log(m)+1 où log est de base 5. Après suppression de la constante, nous pouvons dire que cette boucle a une complexité de O(log m) avec la base 5.

De la même manière pour le deuxième exemple de votre question, Si vous écrivez la série de j, vous obtiendrez n,n/10,n/100,.... il est donc aussi Geometric Progression avec a(1)=n , r= 1/10 et ici a(n) serait 1 que nous devons constater que vous trouvez term.If itérations au total, vous obtiendrez comme log n avec la base 10.

Big -theta (logn) ne fonctionne que pour les boucles imbriquées? (pour boucle à l'intérieur de la boucle for)

Ce n'est pas nécessaire. Supposons que nous ayons une seule boucle qui a le format suivant,

for(int i=1;i<=n;i*=2) 

Cette boucle a aussi O(log n) complexité et il n'est pas une boucle intérieure. Cela dépend donc de l'opération d'incrémentation de votre boucle for. Il définit la complexité globale de la boucle for.