※ 引述《lovebridget (′‧ω‧‵)》之铭言：
: 分享十年前美国留学跟一个白人同学讨论的亲身经验
: 当然只是一个个案 没统计意义 纯聊天
: 碰到要用到等比级数和的问题 a(rn-1)/r-1 那个
: 那我们国中都背过麻 也不可能忘 但他好像没背过
: 原本想马上讲答案 但想看看他怎做 就压下炫技欲望跟他一起看
: 结果他列出前面几项 慢慢看 找规则
: 大概十几分钟后推出那等比级数公式
: 注意当时问题并不是"请证明等比级数和公式"喔 不是专为了这个背证明的
: 只是需要用到 是随机意外碰到这问题
: 他就在十几分钟内"发明"了这公式
: 我只有背脊发凉 现在想到都会流冷汗
说到等比级数，我想起以前有人问了一个问题:
T(n)=64T(n/16)+n(logn)^4+n√n(logn)^4
为什么是T(n)=n^1.5(logn)^5
为什么不是n^1.5(logn)^4甚至是(logn)^k，k的更低次方呢？
这个如果查一下wiki的master theorem会有一条:
T(n) = n^(log_b(a))(logn)^(k+1) if f(n) = θ(n^(log_b(a))(logn)^k)
但这个怎么来的呢? 先回到原来的问题:
T(n)=64T(n/16)+n(logn)^4+n√n(logn)^4
这里可以用Cormen Introduction to Algorithms提到的变量代换:
令n = 2^m
=> T(2^m) = 64T(2^(m-4))+2^m(mlog2)^4+2^(3m/2)(mlog2)^4
然后改成Q(m) = T(2^m)
=> Q(m) = 64Q(m-4)+2^m*m^4(log2)^4+2^(3m/2)*m^4(log2)^4
可以发现这是一个nonhomogeneous recurrence relation with constant coefficients
这个要解，可以先解出homogeneous的解+particular solution
对于homogeneous，特征方程式为 r^4-64 = 0 => (r^2+8)(r^2-8) = 0
=> r = 2√2i or ±2√2
=> Q (m) = c1cos(2√2m)+c2sin(2√2m)+c3(2√2)^m+c4(-2√2)^m
h
虽然可以做，但这个比较麻烦...
不过我们可以用相同的想法，改成令n=16^m
=> T(16^m) = 64T(16^(m-1))+16^m(mlog16)^4+16^(3m/2)(mlog16)^4
令Q(m) = T(16^m)
=> Q(m) = 64Q(m-1)+16^m*m^4(log16)^4+16^(3m/2)*m^4(log16)^4
这是个1阶的方程式，其homogeneous解为c*64^m
接下来分析nonhomogeneous项:
1. 16^m*m^4(log16)^4的底数部分和homogeneous不同
=> 假设第一个特解 = 16^m*(c1m^4+c2m^3+c3m^2+c4m+c5)
=> 16^m*(c1m^4+c2m^3+c3m^2+c4m+c5)
= 64*16^(m-1)*[c1(m-1)^4+c2(m-1)^3+c3(m-1)^2+c4(m-1)+c5]+16^m*m^4(log16)^4
经过一连串的计算，总之这个特解是个16^m*4次多项式
2. 16^(3m/2)*m^4(log16)^4 = [(4^2)^(3m/2)]m^4(log16)^4 = 64^m*m^4(log16)^4
这个底数和homogeneous相同
所以第二个特解要改成 = 64^m*m(d1m^4+d2m^3+d3m^2+d4m+d5)
=> 64^m*m(d1m^4+d2m^3+d3m^2+d4m+d5)
= 64*64^(m-1)*(m-1)[d1(m-1)^4+d2(m-1)^3+d3(m-1)^2+d4(m-1)+d5]+64^m*m^4(log16)^4
总之这个特解就是个64^m*5次多项式
=> Q(m) = c*64^m + 16^m*P4(m) + 64^m*P5(m)
依先前的设定n = 16^m => m = log_16(n)
=> T(n) = c*64^(log_16(n))+16^(log_16(n))P4(log_16(n))
+ 64^(log_16(n))P5(log_16(n))
64 = 16^(3/2)
=> T(n) = c*n^(3/2) + n*P4(log_16(n)) + n^(3/2)P5(log_16(n))
log换成其他底数只差常数，多项式最高次方dominate其他低次方
所以就可以知道 T(n) = θ(n^(3/2)(logn)^5)
而这个想法可以推广到T(n) = aT(n/b) + f(n), f(n) = θ(n^(log_b(a))*(logn)^k)
只要想想看哪个用底数可以把方程式换成Q(m) = Q(m-1)+OOXX这种形式
就发现若令n=b^m，则
T(b^m) = aT(b^(m-1)) + θ(b^(mlog_b(a))*(mlogb)^k)
= aT(b^(m-1)) + θ(a^m*(mlogb)^k)
令Q(m) = T(b^m)
=> Q(m) = aQ(m-1) + θ(a^m*(mlogb)^k)
而这个当然可以用离散或组合数学学到的recurrence技巧解掉
但如果忘记的话，提供另一个方法:
写成
Q(m) - aQ(m-1) = θ(a^m*(mlogb)^k)