[Algorytmy] Wartość wielomianu w punkcie i algorytm naiwny

[blackbird936]

Wielomian:
\(\displaystyle{ W(x)= a_0 x^n + a_1 x^{n-1}+...+a_n = \sum_{i=0}^{n}a_i x^{n-i}}\)

oraz pewien ustalony punkt \(\displaystyle{ x_0}\). Szukamy \(\displaystyle{ W(x_0)}\)

Algorytm "naiwny"
Obliczamy wszystkie potęgi, stosując naturalny algorytm (obliczanie \(\displaystyle{ n}\)-tej potęgi to \(\displaystyle{ n-1}\) mnożeń dla \(\displaystyle{ n \in N}\)) . Stąd
\(\displaystyle{ T^* (NAIWNY , n)=n+(n-1)+...+1= \frac{n(n+1)}{2}}\)

Gdy zapamiętujemy wyniki potęg, to \(\displaystyle{ T^*(NAIWNY, n)=1+2+...+2=2n-1}\) (\(\displaystyle{ 2+..+2=n-1}\)).
ponadto
\(\displaystyle{ T^+ (NAIWNY,n)=n}\), skąd
\(\displaystyle{ T(NAIWNY,n)=3n-1}\)


Nie rozumiem od "Gdy zapamiętujemy wyniki...". Bardzo proszę o wytłumaczenie. Nie wiem skąd się wzięły te dwójki

-- 18 wrz 2013, o 12:20 --

I nie wiem za bardzo na czym polega ten algorytm naiwny

[Mistrz]

Algorytm naiwny polega na tym, że wykonujesz wszystkie działania od lewej do prawej tak, jak są napisane, traktując \(\displaystyle{ x^k}\) jako \(\displaystyle{ (k-1)}\)-krotne mnożenie (\(\displaystyle{ x\cdot x \cdot \dots \cdot x}\)).

Ten drugi, sprytniejszy algorytm, działa tak, że najpierw sobie obliczasz wartości \(\displaystyle{ x^k}\) w ten sposób, że \(\displaystyle{ x^k}\) obliczasz jako \(\displaystyle{ x}\) razy \(\displaystyle{ x^{k-1}}\), przy czym \(\displaystyle{ x^{k-1}}\) masz już obliczone w poprzednim kroku. Dwójki biorą się stąd, że musisz wykonać dwa mnożenia: \(\displaystyle{ x^{k-1} \cdot x}\) oraz \(\displaystyle{ a_k \cdot x^k}\)