Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Polynomielle Bearbeitungszeit!?

32 views
Skip to first unread message

Marcel Huntemann

unread,
Feb 18, 2004, 7:42:37 AM2/18/04
to
Hallo!

Kann mir jemand erklaeren, was genau polynomielle Zeit bei Algorithmen
auf Graphen bedeutet? Also wenn der AUfwand eines Algorithmus
polynomiell ist?
Heisst das einfach nicht-exponentiell? Oder gibt es da ein anderes
verstaendlicheres Wort fuer?
Besten Dank im Voraus.

--
Gruss
Marcel

Hermann Kremer

unread,
Feb 18, 2004, 12:23:15 PM2/18/04
to
Marcel Huntemann schrieb in Nachricht ...

>Hallo!
>
>Kann mir jemand erklaeren, was genau polynomielle Zeit bei Algorithmen
>auf Graphen bedeutet? Also wenn der AUfwand eines Algorithmus
>polynomiell ist?
>Heisst das einfach nicht-exponentiell? Oder gibt es da ein anderes
>verstaendlicheres Wort fuer?

Die Rechenzeit wächst asymptotisch mit irgend einer Potenz k der
Problemgröße n:

t = C*n^k + ... = O(n^k) ,

wobei k beliebig, aber /endlich/ ist. "Nicht-exponentiell" ist nicht
ganz präzise, da es auch Algorithmen gibt, die stärker als exponentiell
wachsen, z.B. O(ackermann(n,n)) , und die wachsen ebenfalls
nicht-exponentiell ...

Grüße
Hermann
--

Marcel Huntemann

unread,
Feb 18, 2004, 5:23:41 PM2/18/04
to
Am Wed, 18 Feb 2004 18:23:15 +0100 schrieb Hermann Kremer:
> Die Rechenzeit wächst asymptotisch mit irgend einer Potenz k der
> Problemgröße n:
>
> t = C*n^k + ... = O(n^k) ,
>
> wobei k beliebig, aber /endlich/ ist. "Nicht-exponentiell" ist nicht
> ganz präzise, da es auch Algorithmen gibt, die stärker als exponentiell
> wachsen, z.B. O(ackermann(n,n)) , und die wachsen ebenfalls
> nicht-exponentiell ...
Besten Dank erstmal fuer Deine Hilfe. Aber irgendwie verstehe ich das
nicht. n "hoch" k ist doch schon exponentiell oder nicht?

--
Gruss
Marcel

Hermann Kremer

unread,
Feb 20, 2004, 12:18:23 PM2/20/04
to
Marcel Huntemann schrieb in Nachricht ...

Nein.
Bei n^k ist k eine Konstante, und n^k ist die höchste Potenz eines
Polynoms k-ten Grades:
P_k(n) = C_k*n^k + C_{k-1}*n^(k-1) + ... + C_1*n + C_0.
Exponentiell wären Rechenzeiten etwa der Form
t(n) = C*exp(a*n),
t(n) = C*n! ~= C*(n/e)^n ~ C*exp(n*ln(n)) // Stirling'sche Formel
t(n) = C*exp(a*n^2)
usw., und die wachsen schneller als jede endliche Potenz k von n.

Grüße
Hermann
--

>
>--
>Gruss
>Marcel


Marcel Huntemann

unread,
Feb 21, 2004, 5:06:38 AM2/21/04
to
Am Fri, 20 Feb 2004 18:18:23 +0100 schrieb Hermann Kremer:
> Bei n^k ist k eine Konstante, und n^k ist die höchste Potenz eines
> Polynoms k-ten Grades:
> P_k(n) = C_k*n^k + C_{k-1}*n^(k-1) + ... + C_1*n + C_0.
> Exponentiell wären Rechenzeiten etwa der Form
> t(n) = C*exp(a*n),
> t(n) = C*n! ~= C*(n/e)^n ~ C*exp(n*ln(n)) // Stirling'sche Formel
> t(n) = C*exp(a*n^2)
> usw., und die wachsen schneller als jede endliche Potenz k von n.
Okay, besten Dank fuer Deine Hilfe!

--
Gruss
Marcel

0 new messages