[理工] 資結 103 複雜度

[qqoo1234 (MU)]

先分享爬文剛剛看到一篇可以參考 #1BAA2uNc

http://imgur.com/jBuWeZT


不好意思,因是個人獨自看書,卡住但不知道如何解
下面是我個人想到一半但卡住了不知道如何繼續往下
(不是要考一班生,是上班族 所以沒有補習,沒有學友可以討論@@)

(b) 這一題和103的交大資結考古題 很類似
但是他的j<i*i 變為 j<i*i*i

(b). i = 0~1 時k不會執行到

i=2

k會執行2^0 + 2^1 + 2^2 ....+2^7

i=3

k會執行2^0+ .... +^26

到這邊我觀察不出一個可以統整的規律.. 只看出2的次方相加
就卡了..

(c) 有爬過文
參考本版的
#1KopJvy
#1KovhKSD

我這邊卡住的點是
化簡到最後一步不知道是帶什麼公式而可以看出是O(n^4)

n-1  i(i-1)  要帶什麼公式呢
Σ i(───) ============>
i=2    2

我有印象常用的1+2+3+..+n
或是1^2 + 2^2 + 3^2 +.....n^2 我知道該帶什麼
但是對於上面的沒印象



謝謝各位大大幫忙




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.105.242.235
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1453038121.A.1C9.html
※ 編輯: qqoo1234 (27.105.242.235), 01/17/2016 21:43:06
※ 編輯: qqoo1234 (27.105.242.235), 01/17/2016 21:56:42
推 OppOops: 只是要算複雜度 不用特別把公式待入求解
→ OppOops: 像是(c)的型式大約是 1^3 + 2^3 + ... + n^3
→ OppOops: 故 O(n^4) 可為上界
→ OppOops: 理由用T(n) = (n+1)^4 - n^4 = 6n^3 + 4n^2 + 6n + 1
→ OppOops: T(n) + T(n-1) + ... + T(1) = (n+1)^4 - 1
→ OppOops: = 4Σi^3 + 6Σi^2 + 4Σi + Σ1
→ OppOops: 可得知實際公式(上面系數有打錯 不影響結果)
→ qqoo1234: O大 謝謝你 我大致有個方向了
推 iam30719: 遇到同類QQ  一起加油啊