Informatiker Board | Druckvorschau: O-Notation die Zweite...

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- O-Notation die Zweite... (http://www.informatikerboard.de/board/thread.php?threadid=2911)

Geschrieben von Shizmo am 10.03.2016 um 14:57:

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

Geschrieben von eulerscheZahl am 10.03.2016 um 15:32:

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

Geschrieben von Shizmo am 10.03.2016 um 19:38:

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

Geschrieben von eulerscheZahl am 11.03.2016 um 08:02:

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.