|
各位大大~因小弟對該演算法不了解,想請教各位大大,
能否請您教導小弟,小弟愚笨,希望可以詳敘該過程,謝謝!!
已知下面程式fib(n)及fib2(n),試依下列敘述計算其執行次數。
(a) n=3 時,fib(n)之T(n) =? fib2(n)之T(n) =?
(b) n=5 時,fib(n)之T(n) =? fib2(n)之T(n) =?
(c) n=10 時,fib(n)之T(n) =? fib2(n)之T(n) =?
fib(n)之T(n) =? fib2(n)之T(n) =?
int fib(int n)
{
int (n<=1)
return 1;
else
return fib(n-1) + fib(n-2);
}
================================================================
int fib2(int n)
{
index i;
int A[0…n];
A[0]=0;A[1]=1;
for(i=2;i<=n;i++)
A=A[i-1]+A[i-2];
return A[n];
} |
|