→ sevenpu:另外想問這題怎麼解T(n) = 5T(n/5) + n/logn 02/25 14:13
推 FRAXIS:O(nlglgn).. 02/25 14:59
※ 引述《sevenpu (pu)》之銘言：
: int fib(int n){
: if (n==0 || n==1) return 100;
: else return 2*fib(n-1)+3*fib(n-2); }
漏掉了fib> <
: 我有兩種想法來解，不知道哪一種是對的
: 請大家幫我看看
: (1) t(n)= t(n-1)+t(n-2)+1 <= 2*t(n-1)+1
: = 2^2*t(n-2)+2^2-1
: = ............
: = 2^(n-1)*t(n-(n-1))+2^(n-1)-1
: = 2^(n-1)*t(1)+2^(n-1)-1
: = 2^n-1
: = O(2^n)
第一種是用big O 的定義來解，就是用 f(n) <= c*g(n)
求得 f(n)=O(g(n))
不知道除了下面用離散的特性方程式來解
還有其它的方法嗎?
: (2)t(n)= t(n-1)+t(n-2)
: = x1((1+√5)/2)^n + x2((1-√5)/2)^n
: x1= 1/√5 , x2= - 1/√5
: t(n) = O(((1+√5)/2)^n)
: 用離散去解
如果t(n)= t(n-1)+t(n-2)+1 特性方程式又該怎麼解?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.173.246.226