※ 引述《charliejack (charliejack)》之銘言： : n : 求 Σi^4 的 Big-O : i=1 : 我知道答案是O(n^5) : 但不知道在考卷上如何寫算式~"~ 或是證明 比較簡單的國中解法在下面一點 先說用生成函數的解法 1+x+x^2+... = 1/(1-x) => 1+2x+3x^2+... = 1/(1-x)^2 (對上式左右微分) => x+2x^2+3x^3+... = x/(1-x)^2 (將上式左右同乘以x) => 1+(2^2)x +(3^2)x^2+... = (1+x) / (1-x)^3 (再將上式左右微分)...過程省略 => x+(2^2)x^2 +(3^2)x^3+... = x(1+x) / (1-x)^3 (再將上式左右同乘以x) (PS.到這裡可以準備求Σk^2,但現在要求到k^4,所以得繼續.) =>1+(2^3)x+(3^3)x^2+...= (x^2+4x+1) / (1-x)^4 (將上式左右微分)...過程省略 =>x+(2^3)x^2+(3^3)x^3+...= x(x^2+4x+1) / (1-x)^4 (將上式左右同乘以x) =>1+(2^4)x+(3^4)x^2+...= (x^3+11x^2+11x+1) / (1-x)^5 (再將上式左右微分) =>x+(2^4)x^2+(3^4)x^3+...= x(x^3+11x^2+11x+1) / (1-x)^5 = x(x^3+11x^2+11x+1)[(1-x)^(-5)] ... 微分差不多練習完了 又因為1+x+x^2+... = 1/(1-x) , 將此式等號左邊還有等號右邊分別和上式相乘 可得0^4 + (0^4+1^4)x + (0^4+1^4+2^4)x^2 + ... + (0^4+1^4+...+n^4)x^n + ... = (x^4+11x^3+11x^2+x)[(1-x)^(-6)] ... 算到這邊差不多昏死一半了 n 再來觀察上式可了解所要求的Σ k^4即是 (0^4+1^4+...+n^4)也就是上式 k=0 中x^n的係數 所以要來展開該式右方 ∞ -6 i (x^4+11x^3+11x^2+x)[(1-x)^(-6)] = (x^4+11x^3+11x^2+x)*Σ C *(-x) i=0 i (負二項式定理) ∞ 5+i = (x^4+11x^3+11x^2+x)*Σ (C )*x^i i=0 i (把負n取r換成正數以便運算) 因為所求為 x^n項的係數 所以sigma內的i值要分別代入 n-4 , n-3 , n-2 , n-1 來分別跟左方的x^4 ,11x^3 ,11x^2 , x 相乘 , 然後再把這幾個結果相加可得 n+1 n+2 n+3 n+4 所求的x^n項的係數 = C + 11*C + 11*C + C 5 5 5 5 =[ (n+1)n(n-1)(n-2)(n-3) + 11(n+2)(n+1)n(n-1)(n-2) + 11(n+3)(n+2)(n+1)n(n-1) + (n+4)(n+3)(n+2)(n+1)n ] / 5! = n(n+1)(24n^3 + 36n^2 + 4n - 4)/120 ... (計算過程略) =n(n+1)(6n^3 + 9n^2 + n - 1)/30 =n(n+1)(2n+1)(3n^2+3n-1)/30 .......................終於有答案了 所以可得Σk^4 公式為 n(n+1)(2n+1)(3n^2+3n-1)/30 也看的出來是O(n^5) ============================================================================== 但也有國中的方法,以下用個國中的方法來驗證: n 以下Σ都是指Σ , 但我省略一點 這樣比較好打 k=0 令 A = Σk^5 = 0^5 + 1^5 + 2^5 + ...+ n^5 B = Σ(k+1)^5 = 1^5 + 2^5 + ...+ n^5 + (n+1)^5 S = 所求 = Σk^4 把A跟B等號右方直接互減可得 B-A = (n+1)^5 ... (1) 把A跟B等號左方互減可得 B-A = Σ[(k+1)^5 - k^5] 展開得B-A = Σ(5k^4 + 10k^3 + 10k^2 + 5k + 1) = 5S + 10*[n^2(n+1)^2]/4 + 10*n(n+1)(2n+1)/6 + 5*n(n+1)/2 + (n+1) ...(2) (因為是0~n所以共有n+1項) (這邊在複習國中sigma公式) 由(1)(2)比較通分化簡之後可得 30S = 6n^5 +15n^4 +10n^3 -n = n(n+1)(2n+1)(3n^2+3n-1) (計算過程就省略了) => S = Σk^4 = n(n+1)(2n+1)(3n^2+3n-1)/30 也當然可以看出是O(n^5)了 不過不管用哪種方法好像都不用求到最後 因為這兩種方法都把答案求出來了 所以如果只是要求big O 應該都不用做到最後 就自己看看該做到哪囉 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.167.75.13 ※ 編輯: jameschou 來自: 218.167.75.13 (02/12 09:15) ※ 編輯: jameschou 來自: 218.167.75.13 (02/12 09:17)