Zeitkomplexität eines Algorithmus

Diskutiere Zeitkomplexität eines Algorithmus im Hausaufgaben Bereich.
T

TheP3aceguy

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.
 
J

JustNobody

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

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.
 
J

JustNobody

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

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

`(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

`(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...
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

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

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)`
Okay, alles klar, dankeschön. Und wie kommt man als "Laie" auf sowas?
 
H

httpdigest

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.
 
J

JustNobody

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

Aber das muss er ja noch prüfen....
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

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....
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

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

JustNobody

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 :)
 
T

Tobias-nrw

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

Ich glaub @httpdigest ist Mathematikprofessor oder Ähnliches, er beharrt immer so darauf, irgendetwas zu wissen...
Ich beharre nicht darauf, etwas zu wissen... Ich sage nur, wie es ist.

musst du einfach nur für jede for und jede while ausbaldowern wie oft diese durchlaufen wird.
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

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:
Thema: 

Zeitkomplexität eines Algorithmus

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben