Was wäre die Big O-Notation für die folgenden verschachtelten Loops?Java Große O-Notation von 3 verschachtelten Loops von Log (n)
for (int i = n; i > 0; i = i/2){
for (int j = n; j > 0; j = j/2){
for (int k = n; k > 0; k = k/2){
count++;
}
}
}
Meine Gedanken sind: jede Schleife ist O(log2(n)) so ist es so einfach wie mehrfach
O(log2(n)) * O(log2(n)) * O(log2(n)) = O(log2(n)^3)
Ja, das ist richtig.
Eine Möglichkeit, die große O-Komplexität von verschachtelten Schleifen herauszufinden, deren Grenzen nicht unmittelbar voneinander abhängen, besteht darin, von innen nach außen zu arbeiten. Die innerste Schleife funktioniert O (log n). Die zweite Schleife läuft O (log n) mal und funktioniert O (log n) jedes Mal, so dass es O (log n) Arbeit. Schließlich läuft die äußerste Schleife O (log n) mal und arbeitet O (log n) bei jeder Iteration, so dass die gesamte geleistete Arbeit O ist (log n).
Hoffe, das hilft!
Was ist die korrekte Schreibweise? O (log2 (n)^3) oder wie du es hast? oder sind sie beide akzeptabel? –
Ich habe das in beide Richtungen geschrieben gesehen. Ich persönlich mag log^3 n im Stil von sin^2 x, gehe aber mit der Konvention, die im Kontext verwendet wird. – templatetypedef
ok danke! wird tun –
Ja, Sie haben Recht.
einfache Art und Weise zu berechnen -
for(int i=0; i<n;i++){ // n times
for(int j=0; j<n;j++){ // n times
}
}
Dieses Beispiel einer einfachen verschachtelten Schleife. Hier Big-O jeder Schleife O (n) und es ist so verschachtelt, so typisch O (n * n), die O (n^2) tatsächlichen Big-O ist. Und in Ihrem Fall -
for (int i = n; i > 0; i = i/2){ // log(n)
for (int j = n; j > 0; j = j/2){ // log(n)
for (int k = n; k > 0; k = k/2){ // log(n)
count++;
}
}
}
, die in verschachtelter Schleife ist, wo jede Schleife Big-O ist O(log(n)) so alle zusammen Komplexität würde O(log(n)^3)
die Tat sein, Ihre Annahme richtig ist. Sie können es zeigen methodisch wie folgt aus:
Meine Vermutung wäre auch 'O (log 2 (n)^3)'. –