※ 引述《shinehsnu (張小光)》之銘言：
: n m-n
: Σ i*(m-n+i) + Σ n*j
: i=1 j=1
: 請教一下大家這個式子的複雜度為何
: 答案寫 O(m*n)
: 但我一直算 O(m*(n*n))
: 所以想問一下
: 看是不是我哪裡理解錯誤了
: 謝謝大家
n m-n
Σ i*(m-n+i) + Σ n*j
i=1 j=1
n n m-n
= (m-n)*Σ i + Σ i^2 + n*Σ j
i=1 i=1 j=1
= (m-n)n(n+1)/2 + n(n+1)(2n+1)/6 + n(m-n+1)(m-n)/2
= n* [ (m+2)(m-n)/2 + (n+1)(2n+1)/6]
= n *( 3m^2 + 6m - 3mn - 3n + 2n^2 + 1)/6
= O(nm^2 + n^3)
算出來的感覺跟解答差很多...
感覺應該是解答有錯 或是題目有抄錯之類的
雖然我有可能計算錯誤
可是大致上用估計的 看起來就應該不太可能是O(m*n)了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.139.82