推 triumphant10: 謝謝你！講的淺顯易懂！ 03/19 14:36
推 triumphant10: 你4幫我解答quotient ring的大大！再推 03/19 14:40
※ 引述《triumphant10 (Look-three-small)》之銘言：
: sum = 0;
: for (i = 0; i < n; i++){
: for (j = 0; j < i*i; j++){
: if (j % i == 0){
: for (k = 0; k < j; k++){
: sum++;
: }
: }
: }
: }
: 大家好
: 這題的Big O 我算出來得到的是 O(n^4)，不曉得對不對?
: 以及
: 想問一下各位都是如何去思考這種題目的?
: 如果要嚴謹一點的寫法該如何是好?
: 想問各位的思路
: 謝謝!
有一個比較容易理解的方式是直接把 for 迴圈寫成 Σ
不過要注意 Σ 只有 +1, 所以碰到像這裡有條件的就要做點變換
這裡的 j 有條件是 i 的倍數
所以如果令 j = j'*i 那就可以有一個一直 +1 的變數 j', 由 0 到 i-1
同時 k 的上限也要從 j-1 改成 j'*i-1
這樣整個迴圈就能寫成
n-1 i-1 j'*i-1
Σ Σ Σ O(1)
i=0 j'=0 k=0
那麼
j'*i-1 i-1 i-1
Σ O(1) = O(j'*i), Σ O(j'*i) = O(i)* Σ O(j) = O(i)*O(i^2) = O(i^3)
k=0 j'=0 j'=0
n-1
Σ O(i^3) = O(n^4) ←即是答案了
i=0
如果你要精確算出例如 sum 是多少那也可以把 O(1) 就寫 1 然後做數學求和
--
◢ ˊ_▂▃▄▂_ˋ. ◣ ▅▅ ▅▅ ι●╮ █▄▄▄▄▄
▍./◤_▂▃▄▂_◥ \'▊ ＨＡＲＵＨＩ █████ ＜■┘ ▄▄▄▄▄▄▄
▎⊿ ◤◤◥█◥◥█Δ ＩＳＭ By-gamejye ￠|\ ▌▌▌▌▌▄▌▌
▏ζ(▏●‵◥′●▊)Ψ ▏ █ ⊿Δ ▄▄▄ ▄▄▄▄
█/|▊ 〃 、 〃▋ |\ ▎ ハルヒ主義 █▄▄▄█▄▄
◥◥|◣ ‵′ ◢/'◢◢S.O.S 世界を大いに盛り上げるための涼宮ハルヒの団
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.192.32
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1552955780.A.1A1.html