O(？)数据结构课习题

onttpi

题目：

k阶裴波那契序列的定义为：
   f(0)=0,f(1)=0,f(2)=0.....f(k-2)=0,f(k-1)=1      
   f(n)=f(n-1)+f(n-2)+.........+f(n-k)                 n=k,k+1,k+2....

编程实现K阶序列的第M个值，k,m 由用户输入

1. #include <stdio.h>
   
2. long func1(int m,int k);
   
3. long func2(int ,int);
   
4. int main(){
   
5. int m,k;
   
6. printf("请输入m(所求项数)和k(阶数)值\n输入0结束\n");
   
7. while(scanf("%d %d",&m,&k),k!=0 && m!=0){
   
8.   printf("无递归 Result=%ld\n",func2(m,k));
   
9.   printf("递归   Result=%ld\n",func1(m,k));
   
10.   printf("请输入m(所求项数)和k(阶数)值\n输入0结束\n");
    
11. }
    
12. return 0;
    
13. }
    
14. long func1(int m,int k){
    
15. /**
    
16. *  递归算法,极糟的算法... 输入 30 3 要等约一秒时间
    
17. */
    
18.   long result=0;
    
19.   int tmp=k;
    
20.   //printf("in func m=%d\n",m);
    
21. if(m<k-1)return 0;
    
22. if(m==k-1)return 1;
    
23. if(m>k-1){
    
24.   while(tmp-- /*&& m--*/)
    
25.    result+=func1(m-k+tmp,k);
    
26.   return result;
    
27. }
    
28. }
    
29. long func2(int m,int k){
    
30. /**
    
31.   非递归算法
    
32. */
    
33. long tmpResult=1;
    
34. long result=1;
    
35. int tmpk=k;
    
36. int tmpm=0;
    
37. int curPos=k;
    
38. long *tmpResults;
    
39. if(m<k-1)return 0;
    
40. if(m==k-1)return 1;
    
41. 
    
42. //初始化表
    
43. //略
    
44. //初始化结束
    
45.   
    
46. do{
    
47.   tmpk=k;
    
48.   result=0;
    
49.   while(tmpk--)
    
50.    result+=*(tmpResults+tmpk);
    
51.    //调整末尾位置   
    
52.    //略
    
53.    //调整结束
    
54.    //末尾位置赋值为当前值
    
55.    //略
    
56.    //赋值结束
    
57. }while(tmpm++<m);
    
58. free(tmpResults);
    
59. return result;
    
60. }

复制代码

想知道递归算法的时间复杂度...

[ 本帖最后由 onttpi 于 2007-3-10 14:52 编辑 ]

海上飞洪

看起来好复杂啊