Re: [問卦] 美國人數學這麼差為何科技這麼強大?

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

然後把index換成m-1,m-2,...1:

Q(m-1) - aQ(m-2) = θ(a^(m-1)*((m-1)logb)^k) --------(2)

Q(m-2) - aQ(m-3) = θ(a^(m-2)*((m-2)logb)^k) --------(3)

...

Q(1) - aQ(0) = θ(a*(logb)^k) -----------------------(m)

接著把(1)+(2)乘上a+(3)乘上a^2+....+(m)乘上a^(m-1)
可以發現左式中間的那些項都被消掉了只剩下Q(m)-a^mQ(0)
而右式會變成θ(a^m*(mlogb)^k)+θ(a^m*((m-1)logb)^k)+....+θ(a^m*(logb)^k)

所以只要知道m^k+(m-1)^k+...+1^k的order是什麼就知道答案了
而這個可以模仿以前高中如何求1^3+2^3+....+m^3的求和公式做，或是用integral估計
可知道這個級數是一個k+1次多項式

所以 Q(m) = a^mQ(0) + θ(a*m*P_(k+1)(m))
因為n = b^m => m = log_b(n)

a^(log_b(n)) = n^(log_b(a)) (對兩邊同取log_b即可驗證)

所以 T(n) = n^(log_b(a)) Q(0) + θ(n^(log_b(a))P_(k+1)(log_b(n)))

= θ(n^(log_b(a))*(logn)^(k+1))

而整個求解的過程就很像無窮等比級數的典型證明:
把原級數乘上公比後減過去

所以學數學要學習背後思考的想法，這樣也許你可以用相同的方法解出沒看過的問題~~

--

收斂? 關收斂什麼事?

那你就繼續背公式然後馬上忘掉，嘻嘻~~