…sehr komplex
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Komplexitätslehre
Woher weiß ich eigentlich, dass O(2^sqr(ld n)) < O(sqr(n)) ? Ich dachte, O(2^n) ist das Schlimmste, was es gibt, unschlagbar langsam, NP-hart :wand: :wand: :wand:
entweder du siehst es einfach oder du rechnest es aus …
lim 2^(ld(n)*ld(n)) / 2^n
(n->∞)
dann noch ein l’hopital (wird der so geschrieben?) und wenn es gegen 0 geht war wohl 2^n groesser und wenn gegen ∞ geht wohl 2^(ld(n)*ld(n))
@yves: kann man hier irgendwas einfuegen damit der latex code erkennt und darstellt? also sowas wie [tex] irgendne math. formel [\tex]
z.z: Für eine nat Zahl m und eine konstante c gilt: ∀n>m 2^sqr(ld n)) < csqr(n)
OE ist n>0 (ach was!) und damit auch die sqrt(n). also können wir teilen und haben zu zeigen:
f(n):= 2^sqr(ld n)) / sqr(n) < c
(1) f(n)>0 Beweis: klar.
(2) f(n) ist streng monoton fallend für n>2.
Beweis: z.z: d/dn f(n) < 0
2^sqr(ld n)) = e^sqr(ln(n)/ln(2))ln(2) = e^sqr(ln(n)ln(2)) = e^sqr(ln(n+2))
Also: f(n)= e^sqr(ln(n+2)) /sqr(n)
Ableiten:
d/dn f(n) = …= ((1/2) e^sqr(ln(n+2)) [ (1/sqr(ln(n+2)) (sqr(n)/(n+2)) -1/sqr(n) ] )/n
Ich hoffe, dass ich mich bis hier noch nicht verrechnet habe.
Etzerla ist der Term vor der eckigen Klammer und der Term unter dem Bruchstrich nach Vorr. >0.
Es bleibt also z.z:
(1/sqr(ln(n+2)) (sqr(n)/(n+2)) -1/sqr(n) < 0
und das geht so:
(1/sqr(ln(n+2)) (sqr(n)/(n+2)) -1/sqr(n) < (Wir ziehen 2 von einem Nenner ab)
(1/sqr(ln(n+2))* (sqr(n)/n) -1/sqr(n) =
(1/sqr(ln(n+2))* (1/sqr(n)) -1/sqr(n) =
(1/sqr(n))[(1/sqr(ln(n+2)) -1] <0
denn für n>2 ist ln(n+2) > 1.
qed. (mod ERRORS)
Kennst du schon Co-HyperExponential-R.E.-Vollständig ??
Naja… Manche Leute fangen ja schon bei NP an zu heulen!
[ot]
@PoLL: Hab vor einiger Zeit mal TeX->MathML-Konverter angeschaut, aber die gingen noch nicht so richtig und ich hatte dann anderes zu tun.
[/ot]
Wo steht das? Gibt’s nicht mal in Google.
In manchen konstruktiven Beweisen der PDL (Propositional dynamic Logic)
2^n kennt man ja. Das ist gerade NP
Hyperexp ist 2^(2^(2^n)), was schon ein bisserle schneller wächst.
Co sagt, dass du die Negation der Formel in Hyperexp entscheiden kannst.
(das negieren kann aber auch ein bisserle dauern…)
R.E. bedeutet das es schneller Wächst als jede Rekursive Folge im jew komplexitätsbereich.