[問題]關於如何計算complexity
Consider the problem of evaluating a polynomial at a point.
Given n coefficients a0, a1, …, an-1 and a real number x,
we wish to compute [summation i=0~n-1] ai*x^i
(1)
Describe a straightforward Θ(n^2)-time algorithm for this problem.
(2)
Describe a Θ(n) algorithm that uses the following method
for rewriting the polynomial:
[summation i=0~n-1] ai*x^i = (…(an-1*x + an-2)*x + … +a1 )*x + a0
能不能幫我看看第一小題polynomial的複雜度怎麼算
a0*x^0+a1*x1^1+a2*x2^2.......+an-1*xn-1^n-1
--------------------------------------------------
第二小題是也是
不過他有提示用右邊那樣去算
請問這兩小題的複雜度怎麼計算呢?
thanks
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.231.194.218