Diskussion:Pseudopolynomiell

Mich verwirrt da grad was; ist der beschriebene Additionsalgorithmus nicht linear in der Eingabe?

"Der Unterschied wird deutlich, wenn man dies mit einem echt polynomiellen Algorithmus vergleicht wie z. B. dem Algorithmus zur Addition von Zahlen: Das Addieren zweier 9-stelliger Zahlen benötigt etwa 9 Schritte, d. h. dieser Algorithmus ist wirklich polynomiell in der Länge der Eingabe".

-- 85.179.91.104 17:57, 26. Jan. 2008 (CET)

Ja, ist er. --85 ^[?!] 18:01, 26. Jan. 2008 (CET)

Warum sollte für die Feststellung der Primzahl n-1 Elemente durchgangen werden, wenn es bereits sqrt(n) ausreichen? Artikel ist verwirrend. (nicht signierter Beitrag von 77.8.134.243 (Diskussion) 17:27, 8. Feb. 2014 (CET))

Für den zu illustrierenden Sachverhalt ist es unerheblich, ob linear oder wurzlig viele Berechungen nötig sind (bezogen auf den numerischen Wert), da $O(n^{\frac {1}{2}})$ ja ebenfalls ein Polynom in $n$ ist. Nur eben mit kleinerem Exponenten.

Der entscheidende Punkt ist, dass die Länge der Eingabe $|n|=\Theta (\log n)$ logarithmisch im Wert der Eingabe wächst. Daher hat der Ansatz nur bis ${\sqrt {n}}$ zu testen, immernoch exponentiellen Aufwand $O(2^{\frac {|n|}{2}})$.

Für die O-Notation siehe auch Landau-Symbole. Liebe Grüße.

-- 2A02:8109:A7BF:E964:2C33:299A:D4E5:1790 19:21, 1. Nov. 2015 (CET)