# Komplexitätsklassen (Laufzeit, Speicher)



## LouCyphre (15. Okt 2021)

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 (15. Okt 2021)

O(1)

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









						Big O notation - Wikipedia
					






					en.wikipedia.org


----------



## mihe7 (15. Okt 2021)

LouCyphre hat gesagt.:


> 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 (15. Okt 2021)

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 (15. Okt 2021)

NullCharm hat gesagt.:


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


LouCyphre hat gesagt.:


> Ich habe dazu diverse Funktionen bekommen


----------



## NullCharm (15. Okt 2021)

Da steht


LouCyphre hat gesagt.:


> 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 (16. Okt 2021)

mihe7 hat gesagt.:


> 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))?



kneitzel hat gesagt.:


> 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 (16. Okt 2021)

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 (16. Okt 2021)

LimDul hat gesagt.:


> 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 (16. Okt 2021)

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 (16. Okt 2021)

LouCyphre hat gesagt.:


> 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 (17. Okt 2021)

NullCharm hat gesagt.:


> 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 (18. Okt 2021)

LouCyphre hat gesagt.:


> 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 (23. Okt 2021)

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 (23. Okt 2021)

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 (23. Okt 2021)

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



LouCyphre hat gesagt.:


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


LouCyphre hat gesagt.:


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


Ja.



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



LouCyphre hat gesagt.:


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



LouCyphre hat gesagt.:


> hier werden nur Initialisierungen beachtet


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



LouCyphre hat gesagt.:


> 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 (23. Okt 2021)

mihe7 hat gesagt.:


> 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 (23. Okt 2021)

LouCyphre hat gesagt.:


> 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 (23. Okt 2021)

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


----------



## LouCyphre (23. Okt 2021)

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



LimDul hat gesagt.:


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



LouCyphre hat gesagt.:


> 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



LouCyphre hat gesagt.:


> 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 (23. Okt 2021)

@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 (23. Okt 2021)

mihe7 hat gesagt.:


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



mihe7 hat gesagt.:


> 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


----------

