Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » O-Notation die Zweite...

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

O-Notation die Zweite...

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

O-Notation die Zweite...

Zitatantwort auf diesen Beitrag erstellen

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

Nehmen Sie Shizmo in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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

__________________
Syntax Highlighting fürs Board (Link)

10.03.2016 15:32

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

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

10.03.2016 19:38

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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.

__________________
Syntax Highlighting fürs Board (Link)

11.03.2016 08:02

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Okay alles klar, vielen Dank Wink

11.03.2016 12:07

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » O-Notation die Zweite...