作者SHANGEE (璇玑)
看板TransCSI
标题[问题]关於如何计算complexity
时间Thu Jun 23 23:31:01 2005
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