！关于时间复杂度的计算问题！

spiderjun

:em12:
试编写程序求一元多项式a0+a1*(1+x)+a2*(1+x+x^2)+a3*(1+x+x^2+x^3)... 的值 ,并确定算法中每一语句的执行次数和整个程序的时间复杂度. 注意选择你认为较好的输入和输出方法. 本题的输入为 (i=0,1…,n), 和n输出为 .

复杂性计算要求有证明过程(归纳法证明), 程序中插入时间测试,并得出结果.

++++++++++++++++
我的做法如下
++++++++++++++++

int p(int n,int x)
{
int s=a[0]+a[1]*(1+x),t=1+x,i,y;
if (n=0)
return(s=a[0]);
else if (n=1)
return(s);
else
{
for(i=2；i<n;i++)
{
x=x*x;
t=x+t;
y=t*a;
s=s+y;
}
return(s);
}

}

我的问题
1、是：复杂性计算要求有证明过程(归纳法证明)，怎么证法？？
我得理解是：O(n)=5n-14（只看i从2=>;n-1的那段for loop），可是当n=2时，O(n)=-4！？莫名其妙，不知其所以然。

2、程序中插入时间测试，就是调用clock函数，可是调用完得出的时间居然是0.000000！！！这个又是怎么回事？

该函数用法如下：
函数名: clock
功 能: 确定处理器时间
用 法: clock_t clock(void);
程序例:

#include <time.h>;
#include <stdio.h>;
#include <dos.h>;

int main(void)
{
clock_t start, end;
start = clock();

delay(2000);

end = clock();
printf("The time was: %f\n", (end - start) / CLK_TCK);

return 0;
}

大家帮忙看看吧，谢谢了！

win_hate

InPut: x, a_0, a_1, ..., a_n
OutPut: f=a_n x^n + a_n+a_{n-1} x^{n-1} + ... + (a_0 + a_1 + ... + a_n)

0. {f, c} <-- {0, 0}
1. for i form n downto 0 do
1.1 c<-- c+a_{i}
1.2 f<-- f*x + c
1.3 done
2. 输出 f

加法次数为： 2n+2
乘法次数为： n+1

归纳证明类似：
f = g*x + (c+a_0)

g 为 n-1 次, c 在计算 g 时已经得到