→ jameschou :還算何理 但把n-1,n-2這些數當成常數有點不太合理 02/12 09:14
→ Sfly :it just 1+2^4+..+n^4 < n^4 * n = n^5 02/12 09:21
→ MOONY135 :當成常數是比較好看出來兩者是一樣的東西 02/12 09:22
※ 引述《charliejack (charliejack)》之銘言：
: n
: 求 Σi^4 的 Big-O
: i=1
: 我知道答案是O(n^5)
: 但不知道在考卷上如何寫算式~"~ 或是證明
這樣寫不知道對不對
題目是
1 + 2^4 + 3^4 +......(n-1)^ + n^4
換過來我們也可以看成
[n-(n-1)]^4 + [n-(n-2)]^4 +......(n-1)^ + n^4
這兩個是一樣的式子
接下來把n以外的數都看成常數
所以每一項我都會有一個n^4
又因有n個
全部加起來 我最大的次方數 就會是 n*n^4 =n^5
接下來再用Big-O的原理去解釋 應該就可以了吧?
這樣不知道算證完了沒
請大家指教
--
█◤◢█ ◢█◣ ◤◢█◣◥█◤ ◢█◣◥█ ◢█ ◢◣◥ █◣◥█◣◥█
█ █◤◢███ ◢███◣◥ ◢███◣◥ █◤◢██ ██ ██ █
█ █◢████ ██◤ █◣ ██◤ █◣ █◢███ ◣◥█◣█◤◢█
█◣◥█◤█◤█ ██ ██ ██ ██ ◥█◤ █ ◤ ███◤◢█
█◤◢█◢█◢█ ◥█ ◢█◤ ◥█ ◢█◤ ◢█ ◢█ ◢◤◥█◤◢██
█ █◤█◤█◤ ◣◥██◤◢◣ ◥██◤◢ █◤ █◤ ◥██◤ ωRyoko
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.135.42.53
※ 編輯: MOONY135 來自: 140.135.42.53 (02/12 08:40)