Informatiker Board | Theoretische Informatik | O-Notation die Zweite...

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

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 5 Beiträge

Shizmo

Okay alles klar, vielen Dank Wink

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.

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

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.

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