作者FRAXIS (喔喔)
看板Grad-ProbAsk
标题Re: [理工] [资结]-时间复杂度
时间Wed Dec 16 16:56:22 2009
※ 引述《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
1F：推 polomoss:谢^ 12/16 18:56
2F：推 polomoss:下面那题的 j%i==0 怎麽变成2个Σ相乘~? 12/16 19:05
3F：→ FRAXIS:[j%i == 0]是一个表示法 当j被i整除时为1 否则为0 12/17 12:36