※ 引述《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)