Algorithmus Polynomwert

[Sixtycent]

kann mir jemand bei diesem algorithmus helfen?

Algorithmus (Polynomwert)

Eingabe: A = (a0; a1; a2; ... ; an); x € R

Ausgabe: pol = a0 + a1*x + a2*x^2 + ... + an*x^n

Polynomwert(A, x)

1 pol <- A[0]

2 for i <- 1 to n

3 do pol <- pol + A * x^i

4 return pol

undzwar ergibt sich als komplexität: BC-Kompl(n)=WC Kompl(n)=

1/2 n^2 + 7/2 n + 1

nur wie komm ich dadrauf?

danke schonmal im vorraus

[Schroenser]

Möglicherweise habe ich ein Brett vorm Kopp... aber irgendwie seh ich da nur eine for-Schleife. Das Schreit eigentlich nach einer Komplexität der Grösse O(n), also linear.

[Sixtycent]

ja es ist doch so:

nach jedem durchlauf (1-n) erhöht sich die anzahl der multiplikatoren.

also beim ersten -> ein multiplikator

beim zweiten-> zwei usw.

so das ich n*(n+1)/2 multiplikatoren habe

anzahl additionen,zuweisungen,fortschaltenschleifenindex = n mal

+ die erste zuweisung in zeile 1: pol <- A[0], also +1

daraus schliesst sich:

Tp(n) = 1/2 n^2 + 7/2n +1 // ????????????????????

und dann kann man jeweils nach oben und unten abschätzen.

zum schluss ergibt sich Teta (n²).

das ergebniss ist von meinem dozenten also denke das n nicht richtig ist, doch danke für deine unterstützung.

ich muss nur wissen wie man auf 1/2 n^2 + 7/2n +1 kommt. den rest verstehe ich

[Sixtycent]

argh!ich ziehe die frage zurück

einfach arbeitsaufwände zusammenzählen.

n(n+1)/2 + 3n +1 = 1/2 n² + 7n/2 +1

:upps

[Schroenser]

Achso... jau... hatte vercheckt das sich hinter x^i ja auch nochmal

for j <- 1 to i

verbirgt. Dann simma natürlich bei quadratischer Laufzeit...

War mir ein Vergnügen, nicht geholfen zu haben... äh... genau! =D

[Dr.House]

kann mir jemand bei diesem algorithmus helfen?

Algorithmus (Polynomwert)

Eingabe: A = (a0; a1; a2; ... ; an); x € R

Ausgabe: pol = a0 + a1*x + a2*x^2 + ... + an*x^n

Polynomwert(A, x)

1 pol <- A[0]

2 for i <- 1 to n

3 do pol <- pol + A * x^i

4 return pol

und zwar ergibt sich als komplexität: BC-Kompl(n)=WC Kompl(n)=

1/2 n^2 + 7/2 n + 1

nur wie komm ich dadrauf?

danke schonmal im vorraus

Ich würde mal in der Wikipedia unter Horner-Schema nachsehen!

Oder Hier

Horner-Schema

Das ist allerdings die harmloseste Variante!

Man kann damit auch Zahlensysteme in Zahlensysteme umrechnen!

Noch besser kommt, das man nach Abspaltung eines Liniarfaktors unter gewissen Bedingungen auch die Funktionsableitungen bekommen kann und somit eine polynomiale Kurvendiskussion fahren kann.

In dem Text gibts viele Quellen und ich denke mal du kannst lesen ?

Dr.House

[Klotzkopp]

ich denke mal du kannst lesen ?

Kann es sein, dass du für jemanden, der anscheinend die Aufgabe nicht verstanden hat, und trotzdem einen fast 6 Monate alten Thread ausgräbt, in dem eigentlich alles geklärt ist, den Mund ganz schön voll nimmst?

[Dr.House]

Kann es sein, dass du für jemanden, der anscheinend die Aufgabe nicht verstanden hat, und trotzdem einen fast 6 Monate alten Thread ausgräbt, in dem eigentlich alles geklärt ist, den Mund ganz schön voll nimmst?

Offensichtlich ist, wie ich gesehen habe nix geklärt, denn der Frager suchte nach dem Weg wie er die Komplxität des Algorithmus berechnen kann.

Ich denke mal, das diese Aufgabe nicht einmalig ist und sicherlich mehrfach wieder erfragt wird. Hornerschema ist Standard und kommt immer wieder vor.

Also was soll der Geiz. Ausserdem stehen im genannten Text Hinweise zur Komplexität des Algorithmus.

linux-related.de

Es ist natürlich eine Folge von Rechenoperationen zu erstellen, die man sukzessive aufstellt wieviele Multiplikationen bzw. Additionen brauche ich ?

Das ist eine gewöhnliche Folge von Zahlen, deren Bildungsgesetz wir suchen.

Frage nur wie geht das, diese berüchtigte Formel herzuleiten ?

Antwort:

Der alte Newton hat dafür eine Formel entwickelt um solchen Bildungsgesetzen der O(n) Notation in gewissen Fällen auf die Schliche zu kommen:

Juttas Mathe-Newsletter

Damit dürfte man ein wirkungsvolles Mittel in der Hand haben. Wenn man die Formel letztlich hat, muss man sie noch mittels vollständiger Induktion beweisen.

Sorry ihr "Fach-Korifeen", leider kann man sich sowas nicht mit MicroMurcs.NET ganz FACHLICH zusammenklicken...:-)

Dr.House

[Klotzkopp]

Offensichtlich ist, wie ich gesehen habe nix geklärt, denn der Frager suchte nach dem Weg wie er die Komplxität des Algorithmus berechnen kann.

Soweit richtig. Allerdings hat er auch eine Antwort gefunden.

Ich denke mal, das diese Aufgabe nicht einmalig ist und sicherlich mehrfach wieder erfragt wird. Hornerschema ist Standard und kommt immer wieder vor.

Diese Aufgabe hat rein gar nichts mit dem Hornerschema zu tun. Es ist schön, dass du Fragen beantworten kannst, die niemand gestellt hat, das gehört aber nicht hierher.

Sorry ihr "Fach-Korifeen", leider kann man sich sowas nicht mit MicroMurcs.NET ganz FACHLICH zusammenklicken...:-)

Es scheint mir, dass du nur schreibst, um Frust abzubauen. Aber auch das gehört nicht hierher.

Ich möchte bei deinen zukünftigen Beiträgen etwas mehr Sachlichkeit und etwas mehr Themenbezug erkennen.