O-Notation die Zweite...

Neue Frage »

10.03.2016, 14:57

Auf diesen Beitrag antworten »

Shizmo

O-Notation die Zweite...

Hallo, weiter gehts mit meinen Fragen zur O-Notation. Die folgende Aufgabe lautet:

Zitat:

Geben Sie für folgende Funktionen [latex]f1[/latex]

bis

passende $[latex]\mathcal{O}-,\Omega-[/latex]$ und $[latex]\Theta[/latex]$ -Klassen an!

$[latex]f_1(n) = 1^{n+1}+278log(n)[/latex]$

Also ich denke die Theta-Klasse gibt die ?durchschnittliche? Laufzeit an? Also für [latex]f_1[/latex]

dürfte es so ausschauen: $[latex]f_1 = \Theta(log(n))[/latex]$
Da man die Konstanten ja streichen kann und 1 hoch irgendwas immer 1 ist, ist es auch nicht exponentiell.

Bei [latex]f_2[/latex]

dann: $[latex]f_2 = \Theta(n^4)[/latex]$
usw.

Aber was gibt denn die Groß-O bzw. Groß-Omega Klasse an. Vermutlich Groß-O die maximale Laufzeit, also die Worst-Case Laufzeig und Omega das Gegenteil?
Falls ja, wie wird das berechnet?

LG

10.03.2016, 15:32

Auf diesen Beitrag antworten »

eulerscheZahl

$[latex]\mathcal{O}[/latex]$ heißt, die Laufzeit ist nicht schlechter. Das hattest du ja schonmal definiert:
$[latex]$\mathcal O(g(n))$[/latex]$ [latex]:= f(n):[/latex]

Es existierten Konstanten $[latex]c>0, n_{0}[/latex]$ , sodass für alle $[latex]n \geq n_{0}[/latex]$ gilt $[latex]0 \leq f(n) \leq c \cdot g(n)[/latex]$

$[latex]\Omega[/latex]$ heißt, es ist nicht besser. Du musst einfach nur f und g vertauschen:
$[latex]$\Omega(f(n))$[/latex]$ [latex]:= g(n):[/latex]

Es existierten Konstanten $[latex]c>0, n_{0}[/latex]$ , sodass für alle $[latex]n \geq n_{0}[/latex]$ gilt $[latex]0 \leq f(n) \leq c \cdot g(n)[/latex]$

$[latex]\Theta[/latex]$ heißt, dass $[latex]\mathcal{O}[/latex]$ und $[latex]\Omega[/latex]$ erfüllt sind.
Somit ist die Laufzeit genau so gut oder schlecht (bis auf Konstanten).

Du hast ja bereits $[latex]\Theta[/latex]$ angegeben, damit hast du die anderen beiden auch schon abgedeckt.

10.03.2016, 19:38

Auf diesen Beitrag antworten »

Shizmo

Danke für deine Antwort, ja das mit den Definitionen habe ich eigentlich verstanden, mich verwirrt nur dieses "Klassen".

Eben wenn da steht, geben Sie jeweils passende O-,Omega-,Theta-Klassen an.

Also reicht als Lösung (vorausgesetzt es ist richtig): ??

$[latex]f_1 = \Theta(log(n))[/latex]$
$[latex]f_2 = \Theta(n^4)[/latex]$
$[latex]f_3 = \Theta(n)[/latex]$
$[latex]f_4 = \Theta(n^4)[/latex]$

Was wäre denn dann zB für f1 eine passende O-Klasse??

11.03.2016, 08:02

Auf diesen Beitrag antworten »

eulerscheZahl

Die $[latex]\Theta[/latex]$ Notation ist richtig.
Du kannst jetzt einfach das $[latex]\Theta[/latex]$ durch $[latex]\Omega[/latex]$ und $[latex]\mathcal O[/latex]$ ersetzen und bist fertig.

Theoretisch kann $[latex]\mathcal O[/latex]$ aber auch eine schneller wachsende Funktion sein, deshalb wäre auch $[latex]f_1 = \mathcal O(n)[/latex]$ möglich.
Analog: $[latex]f_3 = \Omega(\log(n))[/latex]$
Ob das sinnvoll ist, sein mal dahingestellt: wenn man logarithmische Laufzeit hat, gibt man keine Linearzeit an. Aber nach Definition wäre es möglich.

11.03.2016, 12:07

Auf diesen Beitrag antworten »

Shizmo

Okay alles klar, vielen Dank Wink

Neue Frage »

Antworten »

O-Notation die Zweite...

Verwandte Themen