Zeitkomplexität eines Algorithmus

T

TheP3aceguy

Mitglied
Hallo zusammen,

wir sind momentan dabei die Komplexität eines Algorithmus in Abhängigkeit von n zu berechnen. Dazu haben wir folgende Beispielfolie bekommen: 12937

Leider ist das ganze nicht tiefergehend erklärt, weshalb ich absolut keine Ahnung habe, was n+1 sowie n oder auch einfach 0 oder 1 zu bedeuten haben. Ich hoffe, dass mir da jemand weiterhelfen kann.
 
K

kneitzel

Gast
Du hast da einen Algorithmus. Spiel den doch einfach einmal durch mit n=1, 2, 3, 4, ...
Da kannst Du dann die Schritte zählen. Wobei ich im Augenblick nicht verstehe, wieso da bei den ersten beiden Befehlen 0 angenommen wird. Aus meiner Sicht müsste das auch als 1 zu zählen sein ... Aber evtl. zählt eine Zuweisung nicht als Operation. Das muss halt einmal definiert worden sein.

Die Überprüfung wird n+1 mal gemacht, denn er prüft 0<n, 1<n, ... n<n
Die Schritte in der while Schleife werden aber bei n<n aber nicht mehr ausgeführt. Der Check wird also 1 Mal mehr gemacht als die Schritte in der Schleife.

Und dann wird am Ende einfach aufsummiert.
 
T

TheP3aceguy

Mitglied
Okay, vielen Dank schonmal. Wir sollen nun für folgenden Code das ganze durchexerzieren.
Java: 
public class Complexity {
    
    //K-Klasse
    
    public static int calculate(int n) {
        int k = n + 5;                                //1
        int l = 7;
        int m = -2;
        int s = 0;
        for (int i = n; i > l; i/=2) {                //n+1
            s += i;
            for (int j = 0; j < k; j++) {            //markierung
                int t = 2;
                for (int j2 = n; j2 > 0; j2--) {    //markierung
                    t++;
                    s--;
                }
                t+=t;
                while(t>0) {                        //markierung
                    for (int o = n; o < n+k+l+m; o++) {    //markierung
                        s += o*j;
                    }
                    t--;
                }
            }
        }
        return s;
    }
}

Jeweils dort, wo die Markierungen angebracht sind, sollen wir die Komplexität eintragen. Für die ersten beiden Markierungen hab ich das auch schonmal versucht, weiß da jedoch nicht, ob das so richtig ist. Bei den weiteren Markierungen habe ich noch keine Ahnung, was ich dort einfüllen soll.
 
K

kneitzel

Gast
Hmm, Du hast eine Schleife, die bei n anfängt, den Wert immer halbiert und so lange läuft, bis der wert nicht mehr größer als 1 ist...
==> Ich denke nicht, dass dies n+1 mal durchlaufen wird...
Spiel es doch mal mit n=8 durch ....
8>1, 4>1, 2>1, 1>1 .... Da komme ich nicht auf 9 Vergleiche ... Oder habe ich übersehen, dass i in der Schleife verändert wird?
 
T

TheP3aceguy

Mitglied
Stimmt, ich habs mal versucht zu korrigieren:

Java: 
public class Complexity {
    
    //K-Klasse
    
    public static int calculate(int n) {
        int k = n + 5;                                //1
        int l = 7;
        int m = -2;
        int s = 0;
        for (int i = n; i > l; i/=2) {                //(n/2)+1
            s += i;
            for (int j = 0; j < k; j++) {            //markierung
                int t = 2;
                for (int j2 = n; j2 > 0; j2--) {    //n+1
                    t++;
                    s--;
                }
                t+=t;
                while(t>0) {                        //markierung
                    for (int o = n; o < n+k+l+m; o++) {    //markierung
                        s += o*j;
                    }
                    t--;
                }
            }
        }
        return s;
    }
}
 
H

httpdigest

Top Contributor
`(n/2)+1` ist doch ziemlich offensichtlich auch falsch, bzw. generell `(n/k)+c` wird falsch sein für jedes `k` und jedes `c`. Für `n` = 100 sind es nur 4 Schritte (100, 50, 25, 12) und nicht (100/2)+1 also 51... Spiele es doch selber einfach immer durch.
Du benötigst eine Funktion, die in der Komplexitätstheorie sehr häufig verwendet wird, z.B. für die Zeitkomplexität von Suchen und Sortieren...
 
T

TheP3aceguy

Mitglied
httpdigest hat gesagt.:
`(n/2)+1` ist doch ziemlich offensichtlich auch falsch, bzw. generell `(n/k)+c` wird falsch sein für jedes `k` und jedes `c`. Für `n` = 100 sind es nur 4 Schritte (100, 50, 25, 12) und nicht (100/2)+1 also 51... Spiele es doch selber einfach immer durch.
Du benötigst eine Funktion, die in der Komplexitätstheorie sehr häufig verwendet wird, z.B. für die Zeitkomplexität von Suchen und Sortieren...
Zum Vergrößern anklicken....

Ich bin jetzt einmal den Foliensatz sowie den Wikipedia Artikel zu Sortierverfahren durchgegangen und habe keine Funktion gefunden, die mir für n=100 4 ausspuckt. Ich hab wirklich keine Ahnung, wie man auf die Funktion kommen soll o_O
 
H

httpdigest

Top Contributor
Du benötigst den Logarithmus zur Basis 2. Und ganz konkret ist die Anzahl der Schritte in dieser Schleife `log2(n) - log2(7)`. Da aber `log2(7)` eine additive Konstante ist, wird diese bei der asymptotischen Laufzeit weggelassen. Also: `log2(n)`.
Desweiteren verwendet man ja meist nicht den Logarithmus zur Basis 2, sondern zur Basis `e` (Eulersche Zahl), geschrieben `ln(n)`, auch "natürlicher Logarithmus" genannt.
Das kann man hier auch machen, denn: `ln(n) = log2(n) * 1/log2(e)`. Hier ist `1/log2(e)` ein konstanter Faktor und kann ebenfalls entfallen.
Es ergibt sich also: `ln(n)`
 
T

TheP3aceguy

Mitglied
httpdigest hat gesagt.:
Du benötigst den Logarithmus zur Basis 2. Und ganz konkret ist die Anzahl der Schritte in dieser Schleife `log2(n) - log2(7)`. Da aber `log2(7)` eine additive Konstante ist, wird diese bei der asymptotischen Laufzeit weggelassen. Also: `log2(n)`.
Desweiteren verwendet man ja meist nicht den Logarithmus zur Basis 2, sondern zur Basis `e` (Eulersche Zahl), geschrieben `ln(n)`, auch "natürlicher Logarithmus" genannt.
Das kann man hier auch machen, denn: `ln(n) = log2(n) * 1/log2(e)`. Hier ist `1/log2(e)` ein konstanter Faktor und kann ebenfalls entfallen.
Es ergibt sich also: `ln(n)`
Zum Vergrößern anklicken....

Okay, alles klar, dankeschön. Und wie kommt man als "Laie" auf sowas?
 
H

httpdigest

Top Contributor
Ich nehme mal stark an, dass die Logarithmusfunktion bereits in einer Komplexitätslehren-Vorlesung erwähnt wurde. Sonst wird's schwer, von selbst darauf zu kommen. Aber im Allgemeinen beantwortet dir der Logarithmus von `n` zur Basis `k` quasi die Frage: "Wie oft muss ich `k` mit sich selbst multiplizieren, um `n` zu erhalten.". Es ist also quasi die Umkehrfunktion zur Exponentiation.
Das sollte man auch schon in der Schule gehabt haben.
 
K

kneitzel

Gast
Ohh ... ich habe mich gerade total gewundert.... das ist >l und nicht >1 ... das nur als kleine Anmerkung zu meinem Beitrag #4. Denn das ist da natürlich falsch.... und ich wundere mich, dass @httpdigest bei 12 aufhört.

Wobei sich da auch ein kleiner Fehler eingeschlichen hat, denn die Prüfung wird doch auch noch für die 6 durchgeführt und da die nicht größer 7 ist, bricht die Schleife ab. Aber das muss er ja noch prüfen....
 
H

httpdigest

Top Contributor
JustNobody hat gesagt.:
Aber das muss er ja noch prüfen....
Zum Vergrößern anklicken....
Die Prüfung der Schleifenbedingung selbst zählt hier nicht zur Komplexität, sondern die tatsächliche Iteration, also was in dem Schleifen-Body getan wird. Denn das multiplizieren wir ja dann mit der Komplexität der Schleife. Spielt aber sowieso alles keine Rolle, da das eben nur ein konstanter Faktor sein wird.
 
T

TheP3aceguy

Mitglied
JustNobody hat gesagt.:
Ohh ... ich habe mich gerade total gewundert.... das ist >l und nicht >1 ... das nur als kleine Anmerkung zu meinem Beitrag #4. Denn das ist da natürlich falsch.... und ich wundere mich, dass @httpdigest bei 12 aufhört.

Wobei sich da auch ein kleiner Fehler eingeschlichen hat, denn die Prüfung wird doch auch noch für die 6 durchgeführt und da die nicht größer 7 ist, bricht die Schleife ab. Aber das muss er ja noch prüfen....
Zum Vergrößern anklicken....

Jap, ist mir auch erst aufgrund von @httpdigest aufgefallen.

Nun Folgendes bei der nächsten Markierung:
Java: 
for (int j = 0; j < k; j++) {            //markierung

n hat doch mit der Zeile augenscheinlich ja erstmal nichts zu tun. Hab ich dann dort eine Null oder wie ist das aufzulösen?
 
H

httpdigest

Top Contributor
Augenscheinlich ist richtig. Da aber `k = n + 5` ist (siehe oben), gilt quasi:
Java: 
for (int j = 0; j < n + 5; j++) {...}
 
K

kneitzel

Gast
Ok, dann bin ich da jetzt irgendwie zu lange aus dieser Thematik raus. Ich hatte in #1 den Punkt 3 so verstanden, dass die letzte Prüfung auch mitgezählt wird, denn da ist es ja auch n+1 und nicht n ... Aber evtl. ist es dann einfach das Beste, wenn ich dies nur noch lesend verfolge, um hier niemanden zu verwirren, denn ich bezweifle, dass ich groß mehr beitragen kann als Du :)
 
X

Xyz1

Gast
Ich glaub @httpdigest ist Mathematikprofessor oder Ähnliches, er beharrt immer so darauf, irgendetwas zu wissen...

Ganz pragmatisch gesehen musst du einfach nur für jede for und jede while ausbaldowern wie oft diese durchlaufen wird.
 
H

httpdigest

Top Contributor
Tobias-nrw hat gesagt.:
Ich glaub @httpdigest ist Mathematikprofessor oder Ähnliches, er beharrt immer so darauf, irgendetwas zu wissen...
Zum Vergrößern anklicken....
Ich beharre nicht darauf, etwas zu wissen... Ich sage nur, wie es ist.

Tobias-nrw hat gesagt.:
musst du einfach nur für jede for und jede while ausbaldowern wie oft diese durchlaufen wird.
Zum Vergrößern anklicken....
Genau meine Rede. Aber wie gesagt, ist es irrelevant, ob man nun die Prüfung der letzten Iteration mit reinrechnet oder nicht. Es ist dann nur eine Konstante die noch hinzukommt, also egal.
 
T

TheP3aceguy

Mitglied
Gut, dann schätze ich einfach mal:
Java: 
for (int j2 = n; j2 > 0; j2--) {    //n-1 EDIT: Müsste eigentlich nur n sein oder?


Für die letzten beiden bräuchte ich dann aber auch nochmal Unterstützung:
Java: 
            while(t>0) {                        //markierung
                    for (int o = n; o < n+k+l+m; o++) {    //markierung
                        s += o*j;
                    }
                    t--;

und wenn ich o < n+k+l+m mal auflöse, bekomme ich ja n < 2n+10 raus, richtig?
 
Zuletzt bearbeitet:
M

misterx09

Mitglied
TheP3aceguy hat gesagt.:
Gut, dann schätze ich einfach mal:
Java: 
for (int j2 = n; j2 > 0; j2--) {    //n-1 EDIT: Müsste eigentlich nur n sein oder?


Für die letzten beiden bräuchte ich dann aber auch nochmal Unterstützung:
Java: 
            while(t>0) {                        //markierung
                    for (int o = n; o < n+k+l+m; o++) {    //markierung
                        s += o*j;
                    }
                    t--;

und wenn ich o < n+k+l+m mal auflöse, bekomme ich ja n < 2n+10 raus, richtig?
Zum Vergrößern anklicken....

Hallo,

habe bei den 2 unteren, habe ich das selbe Problem.

TheP3aceguy hast du vllt. ne Lösung oder jemand anders?
 
P

Plauzi92

Aktives Mitglied
Hänge auch an der gleichen Aufgabe :D

Gut, dann schätze ich einfach mal:
Java:
for (int j2 = n; j2 > 0; j2--) { //n-1 EDIT: Müsste eigentlich nur n sein oder?
Zum Vergrößern anklicken....

n-1 wäre es doch so oder so nicht. Wenn n = 1, wird die Schleife einmal durchlaufen also n.

Für die Komplexität der While Schleife musst du ja wissen wie groß t in Abhängigkeit von n ist. Das bekomme ich aber auch nicht wirklich hin weil sich n ja nach jedem Aufruf um 1 erhöht und dann verdoppelt. Ich kenne keinen mathematischen Ausdruck dafür.

Meine Idee wäre ( n * (n+1) + n) * 2

Das stimmt zumindest annähernd.


Hast du es mittlerweile gelöst?
 
H

httpdigest

Top Contributor
Java: 
int k = n + 5;
int l = 7;
int m = -2;
int s = 0;
for (int i = n; i > l; i /= 2) { // log2(n) - log2(7)
  s += i;
  for (int j = 0; j < k; j++) { // n + 5, da k = n + 5
    int t = 2; // <- Achtung, t wird hier immer auf 2 gesetzt!
    for (int j2 = n; j2 > 0; j2--) { // n
      t++;
      s--;
    }
    // hier ist t immer n + 2, da t in der oberen Schleife n Mal um 1 inkrementiert wird
    t += t;
    // hier ist t immer 2n + 4, da t einfach verdoppelt wird
    while (t > 0) { // 2n + 4, da t ganz unten immer um 1 dekrementiert wird
      for (int o = n; o < n + k + l + m; o++) {
        /*
         * Für die Betrachtung der Anzahl der Iterationen,
         * ist diese Schleife quasi dasselbe wie:
         * for (int o = 0; o < k + l + m; o++) {
         *
         * wenn wir jetzt noch Variablenwerte einsetzen
         * und vereinfachen, erhalten wir:
         * for (int o = 0; o < n + 10; o++) {
         *
         * Somit läuft die ganze Schleife für: n + 10
         */
        s += o * j;
      }
      t--;
    }
  }
}
 
M

misterx09

Mitglied
httpdigest hat gesagt.:
Java: 
int k = n + 5;
int l = 7;
int m = -2;
int s = 0;
for (int i = n; i > l; i /= 2) { // log2(n) - log2(7)
  s += i;
  for (int j = 0; j < k; j++) { // n + 5, da k = n + 5
    int t = 2; // <- Achtung, t wird hier immer auf 2 gesetzt!
    for (int j2 = n; j2 > 0; j2--) { // n
      t++;
      s--;
    }
    // hier ist t immer n + 2, da t in der oberen Schleife n Mal um 1 inkrementiert wird
    t += t;
    // hier ist t immer 2n + 4, da t einfach verdoppelt wird
    while (t > 0) { // 2n + 4, da t ganz unten immer um 1 dekrementiert wird
      for (int o = n; o < n + k + l + m; o++) {
        /*
         * Für die Betrachtung der Anzahl der Iterationen,
         * ist diese Schleife quasi dasselbe wie:
         * for (int o = 0; o < k + l + m; o++) {
         *
         * wenn wir jetzt noch Variablenwerte einsetzen
         * und vereinfachen, erhalten wir:
         * for (int o = 0; o < n + 10; o++) {
         *
         * Somit läuft die ganze Schleife für: n + 10
         */
        s += o * j;
      }
      t--;
    }
  }
}
Zum Vergrößern anklicken....

Danke für die schnelle Antwort.

Habe noch eine Frage, wir müssen jetzt noch die Komplexitätsklasse berechnen.

Die Formel habe ich auf gestellt aber ich komme nicht auf das Ergebnis.

// 1 + log2 (n) – log2 (7) + n+5 + n+ 2n+4 + n+10
// 5n + 19 + ?? hier weis ich nicht wie ich es auflösen soll, kann mir jemand vllt. einen Hinweis geben?
 
H

httpdigest

Top Contributor
Du musst doch einfach nur die Laufzeiten für verschachtelte Schleifen miteinander multiplizieren und für Schleifen auf derselben Ebene addieren...
So schwer ist das doch nun wirklich nicht.
Wenn:
Java: 
for (int i = 0; i < n; i++) { // n
  for (int j = 0; j < n + 5; j++) { // n + 5
    ...
  }
}
dann: n * (n + 5)
 
M

misterx09

Mitglied
httpdigest hat gesagt.:
Du musst doch einfach nur die Laufzeiten für verschachtelte Schleifen miteinander multiplizieren und für Schleifen auf derselben Ebene addieren...
So schwer ist das doch nun wirklich nicht.
Wenn:
Java: 
for (int i = 0; i < n; i++) { // n
  for (int j = 0; j < n + 5; j++) { // n + 5
    ...
  }
}
dann: n * (n + 5)
Zum Vergrößern anklicken....

das ist mir klar, ich habe mich eher auf der 1+log2(n)-log2(7) teil bezogen.
 
H

httpdigest

Top Contributor
Irgendwie will ich das ganze hier mal abkürzen. Hier erstmal der Ausdruck, der die Anzahl an Operationen beschreibt und den man erhält, wenn man nach dem genannten Schema vorgeht (Laufzeiten von verschachtelten Schleifen multiplizieren und von Schleifen auf selber Ebene addieren):

(log₂(n) - log₂(7)) * (n + 5) * (n + (2n + 4) * (n + 10))

Ganz genau: ceil(log₂(n) - log₂(7)) * (n + 5) * (n + (2n + 4) * (n + 10))
wobei ceil() die "Aufrunden"-Funktion ist, aber das vernachlässigen wir hier mal.

Den hinteren Teil noch in eine schöne polynomielle Form ausmultiplizieren, um den größten Exponenten von n zu erkennen:
(log₂(n) - log₂(7)) * (2n³ + 35n² + 165n + 200)

Um davon die Komplexitätsklasse zu ermitteln, einfach erstmal alle Faktoren von jeder Potenz von n (auch 0, also Konstanten) entfernen:

log₂(n) * (n³ + n² + n)

Dann bei Polynomen einfach den größten Exponenten von n verwenden, hier 3:

log₂(n) * n³

Wenn man will, kann man jetzt auch zu dem natürlichen Logarithmus wechseln, da (wie in einem anderen Beitrag erklärt) log₂(n) dasselbe ist wie ln(n)/ln(2), also der konstante Faktor 1/ln(2) entsteht und konstante Faktoren können vernachlässigt werden:

ln(n) * n³

Schieben wir noch den Faktor nach ganz vorne, der sich am schnellsten erhöht, erreichen wir das Ergebnis:

O(n³ln(n))
 
J

jono

Top Contributor
Java: 
public class Complexity { 
// O(nˆ3 log (n))
 public static int calculate ( int n) {
 int k = n + 5; // 1
 int l = 7;
 int m = −2; 
int s = 0;
 for ( int i = n; i > l ; i /=2) { // log (n) − 3 
s += i ; for ( int j = 0; j < k ; j++) { //( log (n) − 4) (n + 6) 
int t = 2; 
for ( int j2 = n; j2 > 0; j2−−) { //( log (n) − 4) (n + 5)
 (n + 1)
 t++; 
s−−; 
} t+=t ; // t = (n + 2) 2 = 2n + 4
 while(t>0) //( log (n) − 4) (n + 5)
5) (2n + 5)
 for ( int o = n; o < n+k+l+m; o++) //( log (n) − 4) (n + 5)
 (2n + 4) (n + 11)
 s += o∗j ;
t −−; 
} 
} return s ; 
}
 }
Kann mir jemand erklären wie ich hier z.B bei der ersten for-Schleife auf log(n)-3 komme? Habe es nicht wirklich verstanden , weil das hier ja nicht genannt worden ist in der Lösung, die ich hier poste
 
H

httpdigest

Top Contributor
jono hat gesagt.:
Kann mir jemand erklären wie ich hier z.B bei der ersten for-Schleife auf log(n)-3 komme?
Zum Vergrößern anklicken....
Also log₂(n) deswegen, weil hier `i` immer halbiert wird. Und wir wollen wissen, wie häufig halbiert werden muss. Und die Subtraktion von log₂(7) (was aufgerundet gleich 3 ergibt), weil `i` ja nur bis größer als 7 gehen soll (das ist ein kleines "L" und keine Eins in der Schleifenbedingung).
Alternativ kann man auch log₂(n/7) schreiben.
 
H

httpdigest

Top Contributor

Zeitkomplexität eines Algorithmus

Hallo zusammen, wir sind momentan dabei die Komplexität eines Algorithmus in Abhängigkeit von n zu berechnen. Dazu haben wir folgende Beispielfolie bekommen: Leider ist das ganze nicht tiefergehend erklärt, weshalb ich absolut keine Ahnung habe, was n+1 sowie n oder auch einfach 0 oder 1 zu...
www.java-forum.org
 
H

httpdigest

Top Contributor
Die von dir präsentierte Lösung nicht nicht 100%ig korrekt. Es gibt keinen Grund, warum aus `log₂(n)-3` der äußeren Schleife plötzlich `log₂(n)-4` bei der inneren Schleife wird.
Die ganz exakte Lösung für die Anzahl an Operationen (Ausführungen der inneren Schleifen) ist:
ceil(log₂(n/7)) * (n + 5) * (n + (2n + 4) * (n + 10))
 
H

httpdigest

Top Contributor
jono hat gesagt.:
Das hilft mir jetzt nicht wirklich weiter :D
Zum Vergrößern anklicken....
Mehr als, dass deine Lösung falsch ist, kann ich halt auch nicht dazu sagen. Und wie man auf `(log(n) - 4) (n+6)` für die zweite innere Schleife kommt, kann ich dir auch nicht sagen, weil das ebenfalls falsch ist.
jono hat gesagt.:
Geringe Abweichungen sind ja erlaubt
Zum Vergrößern anklicken....
Die "Abweichungen", wie du sie bezeichnest, kommen erst dann zum Tragen, wenn du für die Anzahl der Operationen eine Komplexitätsklasse bestimmen willst. Dort und nur dort kannst du dann Konstanten und lineare Faktoren eliminieren.
jono hat gesagt.:
wäre es dann mit (log(n) -3) (n+5) richtig bei der 2. for schleife
Zum Vergrößern anklicken....
Ja.
 
J

jono

Top Contributor
Ja, dann haben die ja eine super Lösung hochgeladen. Liegt nicht an mir ^^
Du meintest ja "Also log₂(n) deswegen, weil hier `i` immer halbiert wird."
Wo besteht denn ein Zusammenhang zwischen der Halbierung und dem log₂?
Und warum kommt bei den nächsten Schleifen dann auch das log(n)-3 hin ?
Wird das weiterhin übernommen, weil das die inneren Schleifen sind ?
Wäre dann bei
Java: 
while(t > 0)
for(int o = n; o < n+k+l+m; o++)  // (n+10)
korrekt?
 
Zuletzt bearbeitet:
J

jono

Top Contributor
Java: 
public static int[] bubblesort(int[] a) {     // n = a.length
int temp; // 1
for(int i=1; i<a.length; i++) { // n
for(int j=0; j<a.length; j++) { // (n-1)*(n+1)
if(a[j]>a[j+1]) { // (n-1)*n
temp=a[j]; // (n-1)*n
a[j]=a[j+1]; // (n-1)*n
a[j+1]=temp; // (n-1)*n
Wie komme ich hier in der zweiten for-Schleife auf (n-1)*(n+1) und warum (n-1)*n für die if-Bedingung?
 
J

jono

Top Contributor
Ich habe schon einiges verstanden, diese Aufgabe auch versucht nachvollziehen zu können hinsichtlich meiner Fragen, jedoch keine Idee.
Bitte um verständnisvolle Weiterhilfe
 

Aktuelle Jobs

Neue Themen


Oben