Komplexitätsklassen (Laufzeit, Speicher)

[LouCyphre]

Hallo,

da es den Forenabschnitt "Sonstiges" ist der Desktopversion des Forums nicht zu geben scheint, poste ich mal hier.

Ich bearbeite gerade mein erstes Übungsblatt für ADS und es geht grundlegend mit Komplexitätsklassen für Zeit und Speicherbedarf los.

In der 1. Aufgabe soll ich die kleinstmöglichen Komplexitätsklassen ( O(n), O(n²) etc.) angeben. Ich habe dazu diverse Funktionen bekommen, die sich im wesentlichen aus der Termen mit ganzrationalen Brüchen, log und Wurzel und noch ein paar mit trigonomial Ausdrücken zeigen.
Ich kenne das Master Theorem und kann das denk ich recht gut anwenden. Wie aber geh ich hier vor? Ebenfalls nach der höchsten Potenz Ausschau halten und gegebenfalls Wurzeln in Potenzen umbauen? Und was ist hier mit kleinstmögliche gemeint?



Kann wer was dazu sagen?

Danke
Lou

PS: Kann ich hier unkompliziert MatheFormatierung einfügen?

 

[NullCharm]

O(1)

die größte gängige is die Fakultät: O(n!)

Big O notation - Wikipedia

en.wikipedia.org

 

[mihe7]

Wie aber geh ich hier vor? Ebenfalls nach der höchsten Potenz Ausschau halten und gegebenfalls Wurzeln in Potenzen umbauen? Und was ist hier mit kleinstmögliche gemeint?

In der Regel kann man so etwas lösen, indem man die betreffende Funktion durch Umformung von Ungleichungen auf die Definition von groß O zurückführt.

Beispielsweise: f(n) = 2n+6, dann ist z. B. 2n+6 <= 3n für alle n >= 6. D. h. für g(n)=n und eine Konstante C=3 existiert ein x0>0 (hier z. B. x0=1), so dass für alle x > x0 gilt |f(x)| <= C*|g(x)| und damit gilt f = O(g).

Natürlich kann man ggf. vereinfachende Methoden wie das Master-Theorem anwenden.

Zum Thema "kleinstmöglich": aus der Aussage f = O(h) folgt nicht, dass es keine Funktion g mit O(g) ⊆ O(h) geben könnte, so dass f = O(g) gilt.

Etwas anschaulicher: für eine linear wachsende Funktion wäre die Aussage f = O(n²) zwar korrekt, aber wegen f = O(n) ist O(n²) eben nicht die kleinstmögliche Komplexitätsklasse.

Man kann sich das auch noch anders überlegen: mit groß O wird eine obere Schranke für das Wachstum einer Funktion angeben. Gesucht ist aber nicht irgendeine obere Schranke, sondern die kleinste.

 

[NullCharm]

Ich sehe nicht, wo nach einer Herleitung irgendeiner Funktion gefragt wurde? Die kleinstmögliche Schranke habe ich genannt. Wenn man von den üblichen weggeht, sind nach oben hin der Fantasie natürlich keine Grenzen gesetzt.

 

[kneitzel]

Ich sehe nicht, wo nach einer Herleitung irgendeiner Funktion gefragt wurde? Die kleinstmögliche Schranke habe ich genannt. Wenn man von den üblichen weggeht, sind nach oben hin der Fantasie natürlich keine Grenzen gesetzt.

Du hast die kleinstmögliche Schranke gesagt, aber nach der ist nicht pauschal gefragt worden. Sondern der TE brauchte die Herangehensweise für diverse Funktionen, die er bekommen hat:

Ich habe dazu diverse Funktionen bekommen

 

[NullCharm]

Da steht

etc.

das ist ein starkes Indiz für vereinfachende Beispiele...

Wenn das nicht dazugehört, dann wurde die Aufgabenstellung nicht richtig wiedergegeben... Aber egal, die Erklärung von mihe7 ist ja nicht falsch.

 

[LouCyphre]

Zum Thema "kleinstmöglich": aus der Aussage f = O(h) folgt nicht, dass es keine Funktion g mit O(g) ⊆ O(h) geben könnte, so dass f = O(g) gilt.

Etwas anschaulicher: für eine linear wachsende Funktion wäre die Aussage f = O(n²) zwar korrekt, aber wegen f = O(n) ist O(n²) eben nicht die kleinstmögliche Komplexitätsklasse.

Man kann sich das auch noch anders überlegen: mit groß O wird eine obere Schranke für das Wachstum einer Funktion angeben. Gesucht ist aber nicht irgendeine obere Schranke, sondern die kleinste.

Okay. Das versteh ich soweit.

Was mich aber noch ein bisschen verwirrt: Wir haben in der VL quasi 3 mögliche Notation besprochen : O(n) für obere Schranke, Omega(n) für die untere Schranke, Theta( n) für die exakte Schranke.

Dazu wurden noch Best, Average und Worst Case bzgl. der Komplexität genannt.

Was mich verwirrt, ist das O(n) ja die obere Grenze notiert, also die Grenze die asymptotisch über der Funktion liegt ( oder ist hier der Denkfehler?)

Es geht ja darum bei einer konkreten Funktion, die so runter zubrechen und das erstmal ohne formalen Beweis, das man eine Funktion findet die
asymptotisch zu f ist.

Also mal an einem konkreten Beispiel: n -> (3n/12n + 7) wäre O(1) da die Vorfaktoren und Konstanten erstmal keine Rolle spielen, dividieren wir n/n also 1.

So mein Problem ist jetzt : ist das auch die kleinstmögliche KK? in dem Fall schon, da es nicht kleiner als O(1) geht, aber wisst ihr auf was ich hinaus will? was wäre bei n -> (2n² / log (4n³ + 8))?

Sondern der TE brauchte die Herangehensweise für diverse Funktionen, die er bekommen hat:

Genau! Hab ich mich wo bisschen unpräzise Ausgedrückt. Generell habe ich die Liste der Reihenfolge von O(1) bis O(n!) im Kopf. Es geht um das spezielle Auffinden der KK.

Aber ich habe auch zusätzlich noch gesehen, ich muss mirt nochmal die Logarithmusgesetze ansehen.

 

[LimDul]

So aus dem Bauch heraus würde ich sagen, es ist f(n) kleinstmögliche Komplexitätsklasse, wenn O(f(n)) = Omaga(f(n)) = Theta(f(n)) gilt.

Sprich, wenn es nicht nur eine obere Schranke ist, sondern auch gleichzeitig eine untere (und damit exakte Schranke)

 

[LouCyphre]

So aus dem Bauch heraus würde ich sagen, es ist f(n) kleinstmögliche Komplexitätsklasse, wenn O(f(n)) = Omaga(f(n)) = Theta(f(n)) gilt.

Das macht schon Sinn. Die Frage ist aber dennoch, wie sehe ich, was hier O, Omega oder Theta ist?

 

[LimDul]

Beides beweisen.

n -> (3n/12n + 7)

Beweis, dass die Funktion in O(1) liegt (also f(n) = 1): Es gibt Werte a>0 und b so das gilt a*f(n) + b > (3n/12n + 7)
Beweis, dass die Funktion in Omega(1) liegt: Es gibt Werte a>0 und b so das gilt a*f(n) + b < (3n/12n + 7)

Bzw. wenn man es genauer braucht, kann man sich die Definitionen hier ansehen:

Landau-Symbole – Wikipedia

de.wikipedia.org

Das muss man im Endeffekt nur beweisen, durch Angabe des Wertes von C bzw. c

 

[NullCharm]

Was mich verwirrt, ist das O(n) ja die obere Grenze notiert, also die Grenze die asymptotisch über der Funktion liegt ( oder ist hier der Denkfehler?)

Nein, kein Denkfahler. Es ist üblich, die obere Schranke anzugeben (in seltenen Fällen auch Theta...), denn die untere Schranke würde bei dieser Aufgabenstellung ja nicht so viel Sinn ergeben. Praktisch ist Omega(1) für alles eine untere Schranke und O(n^n) für fast alles eine obere.

 

[LouCyphre]

Nein, kein Denkfahler. Es ist üblich, die obere Schranke anzugeben (in seltenen Fällen auch Theta...), denn die untere Schranke würde bei dieser Aufgabenstellung ja nicht so viel Sinn ergeben. Praktisch ist Omega(1) für alles eine untere Schranke und O(n^n) für fast alles eine obere.

OK und mit kleinst möglich ist dann einfach die gemeint die sich am nächsten anschmiegt.

 

[mihe7]

Was mich verwirrt, ist das O(n) ja die obere Grenze notiert, also die Grenze die asymptotisch über der Funktion liegt ( oder ist hier der Denkfehler?)

f = O(g) bedeutet nicht, dass die Funktion g asymptotisch über der Funktion f liegt. Es heißt einfach nur, dass f "nicht wesentlich schneller wächst" als g.

Nehmen wir mal f(n) = 100*n, g(n) = n. Dann ist f = O(g). d. h. 100n wächst nicht wesentlich schneller als n.

g liegt für positive n aber immer "unterhalb" von f, d. h. g(n) < f(n), also n < 100n für alle n > 0. Das ist aber nicht die Frage, denn es geht um das Wachstum.

Die Frage ist, ob es möglich ist, einen konstanten Faktor anzugeben, mit dem man g nur multiplizieren muss, damit ab einem gewissen n die Werte von C*|g(n)| stets größer als die von |f(n)| sind.

 

[LouCyphre]

Ich habe zum Thema nochmal ein paar Fragen.

Wie bestimme ich am einfachsten die Komplexität ( Laufzeit und Speicher ) direkt am (Pseudo)code?

Was ich (vermeintlich) schon verstanden habe:

Laufzeit - Eine Initialisierung von Variablen, Arrays etc. haben die Laufzeit O(1)

int Array[n] // O(1)
    
int anderesArray[n*n +2] // ebenfalls O(1) ? hier bin ich nicht ganz sicher

Einfache Schleifen wären O(n) und je nach Tiefe der Verschachtelung erhöht sich der Exponent um 1. Das gilt nicht generell aber oft.

for(int i = 0) i < A.length; i++){    //
    print(A[i];                        // O(n)
}

Speicher - hier werden nur Initialisierungen beachtet und erneuter Zugriff aufs z.B. Array verbraucht keinen erneuten Speicher.
Allerdings weiß ich im Falle der Speicherkomplexität nicht wie ich die einzelnen Vorfälle bewerten soll. Wie wiegt eine Initialisierung, wie eine Schleife oder Rechenanweisung?

Gibts dafür generell ( Zeit, Speicher) Faustregeln, Tricks?

Exkurs: Wie oft wird sowas in der Praxis benutzt, beachtet ? Oder ist das nur eine theoretische "Spielerei"?

 

[LimDul]

Laufzeit: Einzelne Anweisungen haben in der Regel - sofern nicht anders angegeben eine Laufzeit von O(1), also auch das Array-Beispiel von dir.

Bei Schleifen gilt, wie oft wir die Schleife durchlaufen. Das heißt, man muss ich die Schleifengrenzen anschauen, den Code anschauen und dann mit Mathematik ermitteln wie oft die Schleife in Abhängigkeit von n durchlaufen.

Bei inneren Schleifen gilt dann in der Regel für die Laufzeit: Anzahl Schleifendurchläufe äußere Schleife * Anzahl Schleifendurchläufe innere Schleife.

Bzgl. Speicher sind Schleifen, Rechenanweisungen etc. quasi vollkommen irrelevant. Dich interessiert nur, was wird in den Speicher geschrieben, dass heißt wie viele Variablen werden angelegt und wie viel Speicher verbrauchen die (Da kommen Schleifen halt schon ins Spiel, wenn in Schleifen Speicher reserviert wird)

In Praxis braucht man - außer in extremen Ausnahmenfällen - das in der Detailtiefe nie mehr. Aber extrem wichtig ist es schon, um ein Gefühl für Laufzeiten zu bekommen und um einem Code anzusehen, dass er schlecht ist.

 

[mihe7]

Jetzt ist mir @LimDul zuvorgekommen. Egal, ich lass es jetzt stehen...

Was ich (vermeintlich) schon verstanden habe:

Ja, das geht schon stark in die richtige Richtung

Grundsätzlich ist die Rede von Elementaroperationen. Allerdings muss man sich entscheiden, was man dazu zählt, d. h. was man sinnvollerweise als Elementaroperation betrachtet. Wenn Du Dich für die Laufzeit eines Verfahrens zur Indizierung von Datenbanken auf einem Speichermedium interessierst, sind für die Laufzeit in der Regel nur die Zugriffe auf das Speichermedium von Interesse, weil diese um Größenordnungen langsamer sind als interne Berechnungen.

Daher:

Eine Initialisierung von Variablen, Arrays etc. haben die Laufzeit O(1)

Ja.

ebenfalls O(1) ? hier bin ich nicht ganz sicher

Wenn man die Initialisierung mit O(1) rechnet, dann sicher: Multiplikation O(1), Addition O(1), Initialisierung O(1) -> gesamt O(1).

Einfache Schleifen wären O(n) und je nach Tiefe der Verschachtelung erhöht sich der Exponent um 1. Das gilt nicht generell aber oft.

Als Daumenregel kann man das durchgehen lassen.

hier werden nur Initialisierungen beachtet

Nein, es geht um Speicher-Allokation, nicht um Variablen-Initialisierung.

Allerdings weiß ich im Falle der Speicherkomplexität nicht wie ich die einzelnen Vorfälle bewerten soll.

Genau das gleiche Spiel: eine Variable oder ein Array mit konstanter Größe hat einen Speicherbedarf mit einer Komplexität von O(1). Ist der Speicherbedarf dagegen linear abhängig von der Eingabe, hast Du O(n) usw.

Auch hier ist wieder die Frage sinnvoller Größenordnungen gegeben. Manchmal interessiert man sich für jeden einzelnen Buchstaben der Eingabe (Eingabelänge n), manchmal für die Anzahl der Strings (egal, welche Länge), manchmal für den Platzbedarf auf dem Speichermedium usw.

Praxisrelevanz: abhängig davon, in welchem Bereich man unterwegs ist, braucht man es mehr oder weniger häufig in unterschiedlicher Intensität. In vielen Fällen ist das auch eine Frage der Einschätzung: man setzt sich nicht hin und macht eine Analyse aber man achtet darauf, keinen totalen Mumpitz zu schreiben. Man kann damit auch argumentieren, warum etwas nicht möglich ist (marketing meets reality). Sitzt man umgekehrt vor einem Problem, kann man sich überlegen, welche Laufzeit optimal wäre und ob man nicht einen Algorithmus findet, so dass man da irgendwie hinkommt usw.

 

[LouCyphre]

Ist der Speicherbedarf dagegen linear abhängig von der Eingabe, hast Du O(n) usw.

Kannst du dafür ein (Code)beispiel geben?

Ich kann mir darunter gerade nur vorstellen, dass bei jedem Schleifenaufruf ein oder mehrere Objekte erzeugt werden.

 

[LimDul]

Kannst du dafür ein (Code)beispiel geben?

Ich kann mir darunter gerade nur vorstellen, dass bei jedem Schleifenaufruf ein oder mehrere Objekte erzeugt werden.

Ein Array der Größe N hat Speicherbedarf in der Komplexität O(N)
Ein 2D Array der Größe NxN hat Speicherbedarf in der Komplexität O(N²)

 

[mihe7]

Schon wieder dieser @LimDul ... EDIT: das nimmt ja @kneitzel sche Ausmaße an.

 

[LouCyphre]

LouCyphre hat gesagt.:


ebenfalls O(1) ? hier bin ich nicht ganz sicher

Wenn man die Initialisierung mit O(1) rechnet, dann sicher: Multiplikation O(1), Addition O(1), Initialisierung O(1) -> gesamt O(1)

Ein 2D Array der Größe NxN hat Speicherbedarf in der Komplexität O(N²)

?
Wir reden hier von der Laufzeit?

Ich meinte hier in #17 die Platzkomplexität.

int anderesArray[n*n +2] // ebenfalls O(1) ? hier bin ich nicht ganz sicher

Das wäre ja ein Array mit N*N

Falls wir uns missverstanden haben, dann mein ich nach wie vor

Kannst du dafür ein (Code)beispiel geben?

Ich kann mir darunter gerade nur vorstellen, dass bei jedem Schleifenaufruf ein oder mehrere Objekte erzeugt werden.

 

[mihe7]

@LouCyphre sprichst Du immer mit Dir selbst? In #17 hast Du nach der Platzkomplexität gefragt und @LimDul hat Dir darauf die Antwort gegeben.

Also, nochmal: wenn Du ein Array mit n Elementen erzeugst, dann hast Du eine Platzkomplexität von O(n) und eine Laufzeitkomplexität von O(1). Wenn Du ein Array mit n*n Elementen erzeugst, hast Du eben eine Platzkomplexität von O(n²) und eine Laufzeitkomplexität von O(1).

Wenn Du die Arrays im Code in einer Schleife befüllst, dann ändert sich natürlich auch die Laufzeitkomplexität zu O(n) bzw. O(n²).

 

[LouCyphre]

@LouCyphre sprichst Du immer mit Dir selbst?

Meistens nur wenn ich fluche oder mich selbst beweihräuchere
Mein Arzt meinte aber dies sei noch kein Grund für eine Behandlung.

Also, nochmal: wenn Du ein Array mit n Elementen erzeugst, dann hast Du eine Platzkomplexität von O(n) und eine Laufzeitkomplexität von O(1). Wenn Du ein Array mit n*n Elementen erzeugst, hast Du eben eine Platzkomplexität von O(n²) und eine Laufzeitkomplexität von O(1).

Wenn Du die Arrays im Code in einer Schleife befüllst, dann ändert sich natürlich auch die Laufzeitkomplexität zu O(n) bzw. O(n²).

Ich denke ich habs jetzt. Danke nochmal