[理工] [資結]時間複雜度 Time Complexity
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)
推
09/06 21:09, , 1F
09/06 21:09, 1F
→
09/06 21:10, , 2F
09/06 21:10, 2F
→
09/06 21:11, , 3F
09/06 21:11, 3F
→
09/06 21:11, , 4F
09/06 21:11, 4F
推
09/06 21:21, , 5F
09/06 21:21, 5F
→
09/06 21:22, , 6F
09/06 21:22, 6F
→
09/06 21:23, , 7F
09/06 21:23, 7F
→
09/06 21:24, , 8F
09/06 21:24, 8F
→
09/06 21:26, , 9F
09/06 21:26, 9F
→
09/06 21:41, , 10F
09/06 21:41, 10F
→
09/06 21:42, , 11F
09/06 21:42, 11F
→
09/06 21:43, , 12F
09/06 21:43, 12F
→
09/06 23:16, , 13F
09/06 23:16, 13F
→
09/06 23:16, , 14F
09/06 23:16, 14F
→
09/08 21:01, , 15F
09/08 21:01, 15F
→
09/08 21:03, , 16F
09/08 21:03, 16F