4. Fragen zur komplexitäts- klassen Theta.

Fragen zur komplexitäts- klassen Theta.

  • M

    Ich habe da ein paar fragen zur komplexitäts- klasse Theta.

    Wenn ich log log n habe dann darf ich die doch in den klasse Theta(log n) einordnen.
    Wenn ich 1/x^2 dann darf ich darf ich die doch in den klasse Theta(1) einordnen. Manche Bucher sagen auch Theta(1/x^2).
    Wenn ich x^1/2 was für eine komplexitäts- klasse hat da (in theta?).
    Und noch eins log n! ist doch Theta(nlogn) oder, bin mir nicht 100% sicher.

    Theta ist scheise 😡 😡 😡 .

    0
  • W

    Schau dir halt an wie Theta definiert ist.
    http://de.wikipedia.org/wiki/Landau-Symbole#Formale_Definition

    Von daher würde ich z.B. sagen, dass du 1x2\frac{1}{x^2} nicht einfach so in Θ(1)\Theta(1) einordnen darfst.

    0
  • ?

    Ich geh mal davon aus, dass du die Komplexitätsklassen für x->unendlich bzw n->unendlich meinst.

    "Wenn ich log log n habe dann darf ich die doch in den klasse Theta(log n) einordnen."

    log log n liegt in O(log n), nicht aber in Omega(log n), somit auch nicht in Theta(log n)

    "Wenn ich 1/x^2 dann darf ich darf ich die doch in den klasse Theta(1) einordnen."

    Nach der Definition auf Wikipedia muss c_0 >0 sein (bei x gegen unendlich). 1/x^2 wird aber beliebig klein weshalb es nicht in Theta(1) liegen kann. In O(1) liegt es aber.

    "Und noch eins log n! ist doch Theta(nlogn) oder, bin mir nicht 100% sicher."

    log(n!) <= log(n^n) = nlog(n) also ist log(n!) in O(nlog(n))

    Damit es in Omega(nlog(n)) liegt, muss ein c>0 und ein n_o existieren, s.d. für alle n>n_0 gilt: log(n!) >= c nlog(n)

    <=> c <= log(n!) / log(n^n) -> 0 für n -> unendlich

    du findest also kein entsprechendes c>0, womit log(n!) nicht in Omega(nlog(n)) und somit auch nicht in Theta(nlog(n)) liegt.

    "Wenn ich x^1/2 was für eine komplexitäts- klasse hat da"
    Na Theta(x^1/2).

    Für jedes e>1/2 ist x^1/2 nicht mehr in Omega(x^e).

    0
Anmelden zum Antworten