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 能帮我看下下面的思路是否是正确的吗?
接近 2 年之前 回复
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
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
64位机子,vs2010配置opencv2.4.9遇到问题解决
最近换了64位的主机,准备把之前做过的程序都整理一下,然后之前
MyEclipse+Tomcat 问题 麻烦各位帮忙看一下
Tomcat启动之后我的MyEclipse上面Console框里这些信息的颜色是红色的啊?我也没有设置颜色、可是运行工程的时候又不报错啊。很是纠结啊! 麻烦高手来看一看!  详细的信息如下: 2010-5-21 22:33:07 org.apache.catalina.core.AprLifecycleListener init信息: The APR based Apa
欢迎各位大神解答
一、课程设计的目的: 1 进一步熟悉C语言的基本理论,语法和程序结构,增强实战编程能力,为后续课程的学习和将来的工作打下良好的基础。 2 熟悉文件系统的编程方法和文件的操作过程,掌握文件系统系统函数的调用。 3 掌握在C语言中文件的类型、打开方式,读写方法及关闭。 题目:Text文件的加密/解密以及大写/小写字母转换程序设计/英文文本文件的句式自动更正   二
偏微分方程数值解法习题
偏微分方程数值解法常见习题,麻烦各位朋友帮忙解答。
求各位大神帮忙(java)
我遇到一个问题,就是: 下拉框里共有10个元素,第一个下拉框选中其中一个元素 ,第二个下拉框就会剔除掉这个元素,也就是只有9个元素,依次类推 请问大神,我js或者jquery该怎么写,跪求了
求助各位高手,帮忙做下,谢谢了
由计算机“想”一个四位数,请人猜出这个四位数是多少。人输入四位数字后,计算机首先判断这四位数字有几位是猜对了,并且在对的数字中又有几位位置也是对的,将结果显示出来,给人以提示,请人再猜,直到人猜出计算机所想的四位数是多少时为止。 
有问题的懒加载,框架还可以使用
有问题的懒加载,有大神帮忙修改么?
一个类似于相册的小demo
一个类似于相册的小demo,简单实用,有不足的地方请各位大神帮忙指点
TXT在线小说管理器
不知道哪里写错了,各位大神帮忙指点下,告诉怎么进行修改
一个简单游戏的程序
简单游戏的程序代码,大神们帮忙看看。简单游戏的程序代码,大神们帮忙看看。简单游戏的程序代码,大神们帮忙看看。简单游戏的程序代码,大神们帮忙看看。简单游戏的程序代码,大神们帮忙看看。