[資結]時間複雜度 Time Complexity

[fbukevin (Veck)]

for(i=0; i<n; i++)              =>O(n)
   for(j=n; j>0; j=j/2)         =>O(logn)

的 Time Complexity 是 O(n logn)

因為總次數是 logn + logn +  ... + logn 共 n 個 logn

那麼下面的情況:

for(i=0; i<n; i++)
   for(j=i; j>0; j=j/2)

這個的時間複雜度怎麼算???

這樣子不是變成是 log0 + log1 + log2 + ... +logn

就不是 n 個 logn 次了

接著我想請問這一題今年在台大電機丙資結出來的變化題:
void foo(int n)
{
 for(i=0; i<n; i++)
   for(int j=i; j>=0; j=j/2)
   {
        goo(m);                 //已知 goo(m) 的 Time Complexity = O(m)
   }
}

(A)O(n)
(B)O(nlogn)
(C)O(n^2)
(D)O(n^2 logn)
(E)O(n^3)

請問要怎麼算呢????

前面有一則發問我看不太懂，推文說答案是 (C)O(n^2)   (?)


http://ppt.cc/3Wq8 (感謝借圖!)

謝謝!!!!

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.46.83.168
※ 編輯: fbukevin        來自: 114.46.83.168        (09/06 19:21)
推 fenir:第一題的確是log1+log2+..+logn =ln1+ln2+ln3...ln n(e為底)
→ fenir:然後用ln x的積分(0~n) =n*(ln n) - n
→ fenir:畫那個長條柱狀圖(夾擊法)，最後算出來是n*(ln n) = nlgn
→ fenir:有錯請指正@@
推 fenir:剛想了一下第二題
→ fenir:第二層迴圈假設i=8, 所以j是從8>4>2>1>0
→ fenir:goo(m)在i=8這輪總共花了O(8)+O(4)+O(2)+O(1)的時間
→ fenir:用等比公式算1*(2^lgi-1)/(2-1)= i-1
→ fenir:sigma(i=0~n-1)(i-1)  = O(n^2)
→ fbukevin:第一題我有想到長條圖，不過總覺得沒把握
→ fbukevin:我也不知道第一題對不對XDDD 不過謝謝你!
→ fbukevin:看第二題答案有match，我想應該是這樣了，謝謝f大!!!
→ chia228:第一題log1+log2+..logn=log(n!)   n! <= n^n  同取log
→ chia228:log(n!) = O(nlogn)
→ fbukevin:喔!c大的做法也是倒出nlogn，這樣答案應該就是了吧!
→ fbukevin:感謝兩位解答!