O (logn) und Algorithmus Beziehung

Question

I nicht noch gut O (logn) Algorithmus zu analysieren

Wenn es also verschachtelt ist für Schleifen bekommen kann, wo seine innere Schleife erhöht/verringert durch einen von Multiplikation oder Division, dann ist es Big-Theta (logn), wo seine Basis ist, wie viel es durch geteilt oder multipliziert wird?

Zum Beispiel:

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? 

Ein weiteres Beispiel:

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? 

Ich meine, bin ich es richtig zu bekommen?

Eine weitere Frage:

Big-Theta (log n) nur nur für verschachtelte Schleife arbeiten? (for-Schleife innerhalb der for-Schleife)

Answer 1

Wenn wir zählen können, wie oft eine bestimmte for Schleife ausgeführt wird, können wir uns leicht ein Bild von der Komplexität machen. Wir können mit einem Beispiel einer einfachen for-Schleife beginnen.

Betrachten Sie die folgende for-Schleife,

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

Jetzt hier, wenn wir finden wollen, dass wie oft diese for Schleife läuft, dann können wir es tun, indem die Serie zu schreiben (wie es einheitliche Serie ist) und finden welcher Begriff ist > m(limit). Auf diese Weise können wir leicht die Anzahl der Iterationen finden, die von dieser for Schleife benötigt werden.

In diesem Beispiel, wenn wir schreiben alle möglichen Werte von i,

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

Diese Serie ist Arithmetic Progression. Jetzt haben wir eine Gleichung für die Suche nach n-th Begriff der Serie als {a(n) = a(1)+(n-1)*d}. Hier d=1, a(1)=1 müssen wir jetzt den maximalen Wert n so finden, dass a(n)<=m.

Wir können es tun, indem Sie einfach a(n)=m setzen und den Wert n finden. Also hier

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

Also hier insgesamt Iterationen würde m sein und deshalb können wir die Komplexität dieser for-Schleife sagen O(m) ist.

Betrachten wir nun ein Beispiel, das Sie gegeben haben,

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

Hier, wenn Sie alle Werte von j dann Serie schreiben würde 1,5,25,125,..... und jetzt diese Serie Geometric Progression ist sein. Formel zum Finden n-th Begriff ist a(n) = a(1)*(r^(n-1)) und hier .

setzen nun n(limit) anstelle von a(n) um zu sehen, wie oft die Schleife ausgeführt und lassen Sie uns Grenze umbenennen n als m die Verwirrung zu beseitigen,

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 

So können wir hier, dass die gesamte erforderliche finden Iterationen n = log(m)+1 wo Logbuch der Basis 5. nach konstant Entfernen wir, dass diese Schleife Komplexität von O(log m) mit Basis hat sagen können, 5.

gleiche Art und Weise für das zweite Beispiel für Sie in Frage, wenn Sie die Serie vonschreiben, werden Sie n,n/10,n/100,.... erhalten, so ist es auch Geometric Progression mit a(1)=n , r= 1/10 und hier a(n)1 sein würde, wie wir finden müssen, dass term.If Sie insgesamt Iterationen finden, Sie es als log n mit Basis 10.

Big bekommen -theta (logn) funktioniert nur für verschachtelte Schleifen? (für die Schleife innerhalb der for-Schleife)

Es ist nicht notwendig. Angenommen, wir nur eine Schleife haben, die das folgende Format hat,

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

Diese Schleife hat auch O(log n) Komplexität und es ist nicht eine innere Schleife. Das hängt also von der Inkrement-Operation Ihrer for-Schleife ab. Es definiert die Gesamtkomplexität der for-Schleife.