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