Re: [理工] [資結]-時間複雜度
※ 引述《polomoss (小澤)》之銘言：
: (a)
: k=0
: for(i=0;i<N;i++)
: for(j=0;j<i*i;j++)
: for(z=0;z<j;z++)
: k++;
這種轉成summation比較方便
N-1 i*i-1 j-1 N-1 i*i-1 N-1
Σ Σ Σ 1 = Σ Σ j = Σ (i*i-1)(i*i-2)/2 = O(N^5)
i=0 j=0 z=0 i=0 j=0 i=0
: (b)
: k=0
: for(i=1;i<N;i++)
: for(j=1;j<i*i;j++)
: if(j%i==0)
: for(z=0;z<j;z++)
: k++;
N-1 i*i-1 j-1 N-1 i*i-1 N-1 i-1 N-1
Σ Σ [j%i==0] Σ 1 = Σ Σ [j%i==0] * j = Σ i Σ j = Σ i * (i+1)*i/2
i=1 j=1 z=0 i=1 j=1 i=1 j=1 i=1
= O(N^4)
: 問題:
: 1.這兩題怎麼計算&答案
: 2.請問for(;;)中間那項"<"跟"<="會影響到複雜度嗎~?
: eg. "<" → O(n) "<=" →O(n^2)
你這兩題不會..
: 還是只會影響到係數?
: 用sigma去計算，從1~n會比從1~n-1來的容易算
: 所以如果不會影響到複雜度，是否可以全部都直接從1~n
: 謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50
推
12/16 18:56, , 1F
12/16 18:56, 1F
推
12/16 19:05, , 2F
12/16 19:05, 2F
→
12/17 12:36, , 3F
12/17 12:36, 3F
討論串 (同標題文章)