作者polomoss (小泽)
看板Grad-ProbAsk
标题[理工] [资结]-时间复杂度
时间Wed Dec 16 14:42:45 2009
(a)
k=0
for(i=0;i<N;i++)
for(j=0;j<i*i;j++)
for(z=0;z<j;z++)
k++;
(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++;
问题:
1.这两题怎麽计算&答案
2.请问for(;;)中间那项"<"跟"<="会影响到复杂度吗~?
eg. "<" → O(n) "<=" →O(n^2)
还是只会影响到系数?
用sigma去计算，从1~n会比从1~n-1来的容易算
所以如果不会影响到复杂度，是否可以全部都直接从1~n
谢谢
--
┌这篇文章让您觉得？─────────────────────────────┐
│ │
│ 一"一 \ / >\\\< ╯ ╰ ∩ ∩ ▁ ▁ ＞＿＜ ㄧ ㄧ+ │
│ 皿 ε □ ▽ ▇Δ ▇ ╰╯ ╯ │
│ 北七 乱喔 害羞 莎笅 爽啦 哭爸 ＸＤ 科科 │
└──────────────────────────────────────┘
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.116.14.2