2 fsbqsl fsbqsl 于 2016.09.07 20:15 提问

麻烦各位大神帮忙解答下 算法复杂度 问题

for语句里嵌套if语句该怎么计算复杂度?
如:
for()
{
if ()
{

 }

}
这种该怎么计算?另外,算法复杂度该怎么快速计算得出?
麻烦 各位算法大神 指点迷津 ,感激不尽

6个回答

caozhy
caozhy   Ds   Rxr 2016.09.07 22:32

总之你完全没有概念,算法复杂度不是看用了什么语句,而是要分析你的算法。

caozhy
caozhy   Ds   Rxr 2016.09.07 22:31
 这没法说
for (i = 1; i < 10; i++)
这个复杂度是O(1)
for (i = 1; i < n; i++)
这个复杂度是O(n)
for (i = 1; i < n * n; i++)
这个复杂度是O(n^2)
for (i = n; i > 0; i /= 10)
这个复杂度是O(logN)
...
ThreadP
ThreadP   2016.09.07 21:04

时间复杂度的计算,只取指数最高的例如这个为N+N,是2N,但是双重循环中,就是N平方,而忽略一些常数或N

lipei19890425
lipei19890425   2016.09.07 20:46

可以直接忽略掉If中的内容,时间复杂度应该还是n

fsbqsl
fsbqsl 能帮我看下下面的思路是否是正确的吗?
大约一年之前 回复
fsbqsl
fsbqsl   2016.09.07 21:04

for(i=1,c=0,s=a[0];i<n;i++)
{ if(a[i]<a[0]) \忽略
c++; \if语句执行的语句,忽略
s+=a[i]; \ 执行n-1次
}

还算法复杂度是n?这思路对吗?

A1161433823
A1161433823   2016.09.07 21:28

for(i=1,c=0,s=a[0];i<n;i++) ------------n*c1
{ //考虑最坏情况
if(a[i]<a[0]) ------------(n*c1-1)*c2
c++; ------------(n*c1-1)*c3
s+=a[i]; ------------(n*c1-1)*c4
}
T(n)=n*c1+n*c1*c2+n*c1*c3+n*c1*c4-c2-c3-c4
=n*(c1+c1*c2+c1*c3+c1*c4)-c2-c3-c4
所以为θ(n)

Csdn user default icon
上传中...
上传图片
插入图片