cards-deck: 100-199_university::111-120_theoretic_cs::111_algorithms_datastructures

$O$ - Notation | Bestimmen von Laufzeiten:

anchored to [[111.00_anchor]]

Motivation:

Wir möchten irgendwie quantifizieren, wie die Laufzeit eines Algorithmus mit zunehmender Menge von Eingaben verändert werden kann / sich verändert. Dafür möchten wir mit $O$ -Notationen betrachten, wie sich mit einem sehr großen $n$ die Laufzeiten von Algorithmen verändern.

[!Summary] Also: Wir möchten die Entwicklung der Laufzeit eines Algorithmus in Abhängigkeit von $n$ beobachten.

Meistens möchte man diese Erkenntnis mit den Laufzeiten anderer Algorithmen vergleichen und so etwa herausfinden:

ob der eine Algorithmus (garantiert) schneller oder langsamer als ein anderer sein wird.
ob zwei Algorithmen in ihrer Geschwindigkeit ungefähr gleich sind.

Charakterisierende Beobachtungen:

$f \in O (g)$ | maximal so groß:

$f \in O (g)$ f is of order at most g: Wie beschreiben wir diese Notation? #card $\exists c > 0, \exists n_{0} > 0\forall n > n_{0} :$ $0 < f (n) \leq c g (n) ⟺ 0 \leq lim sup_{n ⟶ \infty} \frac{f ( n )}{g ( n )} < \infty$ there exists a number $n_{0}$ where $f < g$ follows afterwards Betrachtet man den definierten $lim sup$ , dann ist erkennbar, dass $n ⟶ \infty lim \frac{f ( n )}{g ( n )}$ kleiner $\infty$ sein muss, also $g (n)$ garantiert schneller wachsen muss, als $f (n)$

[!Tip] Intuition Mit dieser Notation beschreiben wir, dass eine Einheit maximal so groß sein kann, es aber nicht sein muss. Sie darf nicht größer sein und es gibt einen Punkt im Verlauf, ab welchem diese Funktion $f$ garantiert kleiner sein muss, als $g$ ^1704708572170

example

at some point the function f is definitely gonna be smaller than function g. A constant $c$ shouldn’t interrupt this equation so much. With this idea we can easily leave out constants in large comparisons, because they should not interfere with the proportion at some point

$f \in o (g)$ | garantiert kleiner als:

$f \in o (g)$ : $f$ is of order strictly smaller than $g$ : Wie beschreiben wir diesen Sachverhalt mathematisch? #card $\forall c > 0\exists n_{0} > 0 : \forall n > n_{0} : 0 < f (n) < c \cdot g (n)$ $⟺ 0 \leq lim sup_{n ⟶ \infty} \frac{f ( n )}{g ( n )} = 0$

[!Tip] Intuition Diese Notation beschreibt den Punkt, dass $f$ garantiert kleiner bleiben muss, als $g$ . Erkennbar ist es, wenn man betrachtet, dass hier der $lim sup_{n ⟶ \infty} (\frac{f ( n )}{g ( n )}) = 0$ muss. Während bei $\in O (g)$ noch passieren konnte, dass der Limes etwa $= 1$ sein wird, also da konvergiert bzw. ein Häufungspunkt auftritt, ist es hier nicht erlaubt. $g (n)$ muss so schnell anwachsen, dass der Limes $0$ sein wird ^1704708572178

$f \in Ω (g)$ | mindestens so groß:

$f \in Ω (g)$ : $f$ is of order at least $g$ : Wie beschreiben wir diesen Sachverhalt mathematisch? Was bedeutet es für uns? #card $\exists c > 0, \exists n_{0} > 0 : \forall n > n_{0} : f (n) \geq c \cdot g (n) > 0$ $⟺ 0 < lim in f_{n ⟶ \infty} \frac{f ( n )}{g ( n )} \leq \infty$ $⟺ g \in O (f)$

[!Tip] Intuition Hier beschreiben wir einen Sachverhalt, bei welchem $f$ mindestens so groß sein muss, wie $g$ . Das wird damit beschrieben, dass ab einem gesetzten $n_{0}$ $f (n), \forall n > n_{0}$ selbst unter Anwendung einer Konstante $c$ immer größer sein wird, als $c \cdot g (n)$ Anders beschrieben heißt das, dass der Limes von $0 < \frac{f ( n )}{g ( n )} \leq \infty$ sein muss, was wiederum ein Indikator dafür ist, dass $f (n)$ schneller wachsen muss ( dann ist es $\infty$ ) oder aber mindestens schneller als $g (n)$ , da der Limes größer 0 sein muss! ^1704708572184

$f \in ω (g)$ | garantiert größer als:

$f \in ω (g)$ : f is of order strictly larger than $g$ : Wie beschreiben wir diesen Sachverhalt mathematisch? Was folgt für $g$ ?: #card $\forall c > 0\exists n_{0} > 0 : \forall n > n_{0} : f (n) > c \cdot g (n) > 0$ $⟺ lim in f_{n ⟶ \infty} \frac{f ( n )}{g ( n )} = \infty$ $⟺ g \in o (f)$

[!Tip] Intuition: Wenn wir wissen, dass $f (n)$ stetig schneller wachsen wird, als $g (n)$ , dann ist es auch logisch, dass der limes von $\frac{f ( n )}{g ( n )} = \infty$ sein muss, denn $f$ wächst schneller als $g$ . Da hier somit $f$ auf jeden Fall größer ist, kann man den Sachverhalt auch umgekehrt betrachten und sagen, dass $g \in o (f)$ ist. ( also echt kleiner sein muss, als f) ^1704708572189

$f \in Θ (g)$ | ist von gleicher Ordnung:

$f \in Θ (g)$ : $f$ has exactly the same order as $g$ : Wie beschreiben wir diesen Sachverhalt mathematisch? Was folgt daraus für $g$ ? #card $\exists c_{1}, c_{2} > 0\exists n_{0} > 0 : \forall n > n_{0} : c_{1} \cdot g (n) \leq f (n) \leq c_{2} \cdot g (n)$ $⟺ 0 < lim in f_{n ⟶ \infty} \frac{f ( n )}{g ( n )} \leq lim sup_{n ⟶ \infty} \frac{f ( n )}{g ( n )} < \infty$ $⟺ f \in O (g) \land f \in Ω (g)$

[!Tip] Intuition Wir beschreiben hiermit, dass $f$ von gleicher Ordnung, wie $g$ ist hier muss sowohl $f \in O (g)$ als auch $f \in Ω (g)$ liegen. Das heißt dann folgend:

dass $f$ maximal so groß,wie $g$ , aber auch mindestens so groß wie $g$ ist.

Beides vereint gibt an, dass der Limes größer $0$ und kleiner $\infty$ sein muss! ^1704708572193

Aus weiterer Betrachtung können wir weiter betrachten: Diese Eingrenzung wird damit vorgenommen, dass wir zwei Konstanten $c_{1}, c_{2}$ definieren müssen, sodass mit $c_{1}$ die untere Schranke gebildet werden kann und mit $c_{2}$ die obere Schranke. Wir wollen also zeigen, dass wir mit einer Konstante die gegebene Funktion $f$ unter Anwendung von $g$ “einschließen können”. Denn das ist nur möglich, wenn wir entsprechend auf gleichen Größenordnungen unterwegs sind.

Beispiele zur Bestimmung der Laufzeit

Unter der Anwendung eines Beispieles möchten wir betrachten, wie sich die Algorithmen mit großem N verhalten oder verhalten. Wir betrachten ferner: $f : 3 n^{3} + 50 n^{2} = O (n^{3})$ wir wollen also sehen, dass $f \in O (n^{3})$ liegt. Dafür müssen wir uns zuvor eine Konstant $C$ überlegen:

Wähle ein C: sodass $0 \leq f (n) \leq c \cdot g (n)$ Weiterhin benötigen wir ein $n_{0}$ , sodass anschließend $\forall n \geq n_{o}$ gilt, dass $0 \leq f (n) \leq c \cdot g (n)$ ! Für unser Beispiel wählen wir so etwa:

$c = 4$ , denn dann: $0 \leq 3 n^{3} + 40 n^{2} \leq 4 (n^{3})$ (( was wir ja wissen, denn schon $3 n^{3} \leq 4 n^{3}$ ))

wir müssen jetzt noch ein entsprechendes $n_{0}$ definieren, ab welchem dann diese Aussage gilt

[!Important] $n_{o}$ darf hierbei frei gewählt werden! Am einfachsten wäre es, wenn wir jetzt ein $n_{0}$ bestimmen, ab welchem die Aussage zutrifft. Danach bzw. ausgehend von diesem Grundwert sollten alle höheren auch stimmen!

Also können wir jetzt etwa $n_{0} = 50$ wählen, denn dann gilt die Aussage: $3 \cdot 5 0^{3} + 50 \cdot 5 0^{2} < 4 \cdot 5 0^{3} ⟺ 3 (50 \cdot 50 \cdot 50) + 50 \cdot 50 \cdot 50 < 4 \cdot (50 \cdot 50 \cdot 50)$ Was folgend: $⟺ 4 \cdot (50 \cdot 50 \cdot 50 \leq 4 \cdot (50 \cdot 50 \cdot 50)$ wäre.

Wir könnten alternativ auch annehmen, dass: $f \in O (n^{4})$ . Auch hier wollen wir dann zuerst ein $c$ bestimmen, und anschließend noch $n_{0}$ passend setzen:

Wählen wir etwa $c = 1$ muss jetzt also gelten: $0 \leq 3 n^{3} + 50 n^{2} \leq 1 \cdot n^{4}$ Wenn wir jetzt schauen, dann ist ab $n_{0} = 10$ diese Gleichung gelöst, denn ab diesem Punkt: wächst $n^{4}$ definitiv schneller, als $f$

Daraus folgt dann auch: $f \in o (n^{4})$ –> also definitiv kleiner als und $f \neq \in o (n^{3})$ , denn $\frac{3 n ^{3}}{n ^{3}} \neq = 0$

weitere kleine Beispiele:

Definieren wir folgend: $f (n) = n^{2} + 7$ dann stimmen folgende Aussagen ( offensichtlich): $f \in O (n^{10})$ , $f \in o (n^{10})$ -> denn $n^{2}$ wächst zwingend kleiner als $n^{10}$ aber auch: $f \in ω (lo g (n))$ -> Logarithmen sind immer kleiner als exponentielle Wachstumsraten! $f \in Θ (n^{2})$ -> Konstanten können wir weglassen!

Addition zweier Integer der Länge n: -> $O (n)$ ( denn wir addieren $n + n$ ) Multiplikation zweier Integer, Länge n und m -> $O (n \cdot m)$ , denn wir müssen entsprechend multiplizieren

Spezialfälle von Laufzeiten:

Es können noch einige Spezialfälle betrachtet werden, die das Rechnen und Arbeiten von Laufzeiten vereinfachen können:

Ist $f$ ein Polynom mit Grad $d$ , so ist $f \in Θ (n^{d})$ . Warum gilt das? #card

[!Tip] Grund, warum das größte Glied eines Polynom die Laufzeit festlegt. Das kommt daher, dass das größte Monom in dem Polynom bei einer Betrachtung gegen unendlich (bzw. wenn $n$ sehr groß wird) viel stärker wächst, als alle Monom, bei welchen der Grad $< d$ ist. Aus dieser Betrachtung heraus ist es so, dass ^1704708572198

Außerdem gilt: Jede polynomielle Funktion $f$ ist: $f \in o (e x p (n))$ und auch $f \in ω (lo g n)$ Warum? #card

[!Tip] Grund, warum polynomielle Funktionen garantiert kleiner als exp und garantiert gröser, als $lo g (n)$ Die spezielle Exponentialfunktion $exp (n)$ beschreibt den Wachstum mit $e^{n}$ , welche sehr sehr schnell stark ansteigt Logarithmen sind in ihrem Wachstum immer schwächer ansteigend, weswegen sie auch immer kleiner sind, als eine exponentielle Funktion ^1704708572202

Die Basis von Logarithmen ist trivial bzw. nicht relevant: warum ist sie zu vernachläsigen? #card

[!Tip] Basis von Logarithmen egal Wenn wir einen Logarithmus betrachten, ist die Basis egal: $lo g_{a} \in Θ (lo g_{b} (n))$ Das folgt aus: $lo g_{b} n = \frac{lo g _{a} n}{lo g _{a} b}$ ( wir können Konstanten bei der Betrachtung vernachlässigen!) ^1704708572206

[!Explanation] Reason for this: $l o g_{b} (n) = l o g_{b} n / l o g_{a} b$ , es werden Konstanzen beschrieben weswegen es nicht relevant ist, welcher Log genau gemeint ist, weil sie alle ungefähr gleich konvergieren

Eine Funktion, die durch eine Konstante $b > 0$ resultiert, wobei $b$ unabhängig von $n$ ist, hat eine Laufzeit von $O (1)$ Wie folgt das? #card

[!Tip] Grund: Wenn wir eine Funktion betrachten, welche nur durch die Verwendung einer Konstante $> 0$ ist, dann ist der Faktor $n$ im Wachstum dieser Funktion nicht so relevant und kann bei einer Betrachtung der Laufzeit vernachlässigt werden. ^1704708572211

Rechenregeln:

Folgend möchten wir grundlegende Rechenregeln mit Werten der $O$ -Notation betrachten, die es vereinfachen mit diesen zu arbeiten / rechnen:

ist $f \in O (g_{1} + g_{2})$ und $g_{1} \in O (g_{2})$ :: $⟹ f \in O (g_{2})$ ^1704708572215

Also wenn $g_{2}$ in der Konkatenation der größte “Part” bzw. die größte Funktion ist, dann wird $f$ auch maximal so groß, wie $g_{2}$ sein –> also $f \in O (g_{2})$

Ist $f_{1} \in O (g_{1}) \land f_{2} \in O (g_{2)}$ :: $⟹ f_{1} + f_{2} \in O (g_{1} + g_{2})$ ^1704708572219

Wenn wir die oberen Schranken von zwei Funktionen wissen, ist die Konkatenation dieser ebenfalls entsprechend der Konkatenation der Schranken, die gesetzt wurden.

Ist $f \in g_{1} \cdot O (g_{2})$ :: $⟹ f \in O (g_{1} \cdot g_{2})$ ^1704708572223

bedeutung dieser regel

Wenn wir eine Funktion $f$ betrachten, die in eventuell mit weiteren Funktionen ( $g 1$ ) multipliziert wird, kann man dieses Produkt auch aufteilen und somit $f \in O (g_{1} \cdot g_{2})$ resultieren.

Bei Konstanten gilt; $c > 0, O (c \cdot g)$ :: $⟺ O (g)$ ^1704708572228
Transitivität: $f \in O (g_{1}), g_{1} \in O (g_{2})$ :: $⟹ f \in O (g_{2})$ ^1704708572233

[!Tip] Bedeutung Wir betrachten hier mehr oder weniger eine Transitivität von den $O$ -Notationen. Wenn wir also wissen, dass $f \in O (g_{1})$ und weiter auch $g_{1} \in O (g_{2})$ , dann können wir diese Abhängigkeit zusammenschließen und quasi folgendes resultieren: $f \in O (g_{1}) \in O (g_{2})$

Abuse of Notation: Whenever one writes $f = O (g)$ :: they actually mean $f \in O (g)$ , most of the time at least. ^1704708572238

Weiterführende Betrachtungen:

Mit dieser Grundlage lassen sich weitere Themen besprechen und folgern:

[[111.06_algo_runtimeanalysis]]
[[111.99_algo_ProblemComplexity]]

scattered-lenity