如題，在
T(n) = T(a*n) + T(b*n) + g(n) , n>=n0
T(n) = c , n<n0
其中 1>a>b>0, g(n) = θ(n)
的遞迴式中，我可以處理後得到
sigma{ g(a^α*b^β) }
可以被
sigma{ c1(a+b)^k, k=0,1,...p1 }, sigma{ c2(a+b)^k, k=0,1,...p2 }
這兩個包住，其中 c1, c2 為二正常數
p1, p2 都會是 θ(log n )
但是，當我想處理 T(n) 遞迴展開的常數項 T(n) = c 的部份時出了問題....
我要找的是特定的 (i,j) 集合可以滿足 (a^i)(b^j)n 剛剛好小過 n0
然後算出集合的大小，定為 M
則常數所造成的 complexity 就是 M*c = θ(M),
M 會是一個和 n, a, b, n0 有關的函數
以上看似ok ，但是我卻不知道要如何說明 M = θ(n)...
有強者可以看得出來嗎@@
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.91.5