Komplexität von Algorithmus [gelöst]



  • Guten Abend,

    ich soll überprüfen ob folgende Behauptung stimmt:

    n517Ω(n4)\frac{n^5}{17}\in\Omega(n^4)

    Die Definition von fΩ(g)f\in\Omega(g) lautet:

    fΩ(g) n0N, cR+: nn0:cg(n)f(n)f\in\Omega(g)\Leftrightarrow\exists~n_0\in\mathbb{N},~c\in\mathbb{R}^+:\forall~n\ge n_0: c\cdot g(n)\le f(n)

    Mein Lösungsansatz lautet:

    cn4n517cn17c17nc\cdot n^4\le\frac{n^5}{17}\Leftrightarrow c\le\frac{n}{17}\Leftrightarrow c\cdot 17\le n

    Mit der Wahl von c1c\ge1 und n0=17n_0=17, ist diese Ungleichung erfüllt und die Behauptung bewiesen.

    Ich stehe grade total auf dem Schlauch und weis nicht ob dies richtig ist. Kann mir da eventuell wer helfen?

    Liebe Grüße



  • @Francesco Guten Morgen, ich bin mir nicht ganz sicher aber du hast

    n517Ω(n4)\frac{n^5}{17}\in\Omega(n^4)

    Gesucht ist also cR+,n0Nc\in\mathbb{R}^+, n_0\in\mathbb{N} so dass :

     nn0:n517cn4\forall~n\ge n_0: \frac{n^5}{17}\ge c\cdot n^4

    n17c\Leftrightarrow \frac{n}{17}\ge c

    nc17\Leftrightarrow n\ge c \cdot 17

    @hustbaer stimmt



  • @Liz
    Er muss nur zeigen dass für passend gewählte n0 und c die Ungleichung erfüllt ist.
    Nicht dass sie für alle n0 und c erfüllt ist. Das wäre Quatsch, da man bei fast allen Funktionen mit c = 0 ein Problem bekommt.

    @Francesco
    Bin kein Mathematiker, aber ich denke das ist so korrekt.



  • @Liz
    ps: Da steht auch cR+c\in\mathbb{R}^+, also ist c=0c=0 gar nicht erlaubt. Wäre auch Quatsch es zu erlauben 🙂



  • @hustbaer da hast du natürlich recht, in dem Fall wäre aber für n=0n = 0 und c=0c = 0 die Ungleichung sogar erfüllt. Hatte gestern verpeilt das es um Ω\Omega geht.



  • Vielen Dank 🙂