一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 850|回复: 11
收起左侧

[其他] 时间复杂度代表的真正的运行时间是多少?

[复制链接] |试试Instant~ |关注本帖
FiroEuro 发表于 2014-1-1 01:10:39 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 FiroEuro 于 2014-1-1 08:23 编辑

大家都知道算法分析里的时间复杂度O(1), O(N)代表什么,但是在实际应用中具体指代多长时间呢?我知道这应该具体问题具体分析,但还是很好奇

真正的运行时间肯定跟CPU相关,比如时钟频率,假设我们不考虑CPU结构的异同,不考虑cache这类会将问题复杂化的东西,那么O(1)是否近似等于1个clock cycle呢?O(N)是否近似等于N个clock cycle呢?但我觉得不同的编程语言应该有影响,毕竟编译过程不一样,无论如何汇编里的O(1),JAVA里的O(1)和MATLAB里的O(1)应该是不一样的吧。农友们对这个怎么看?

——————————————————————————————————————————————————————————————————
楼主承认自己不懂算法,让这贴沉了吧
swift_sweep1 发表于 2014-1-1 01:13:45
本帖最后由 swift_sweep1 于 2014-4-3 03:57 编辑

m你i . le发的sil飞e .n的et飞/ ind发的ex. p hp 去掉中文及空格即为草榴网址
支持 反对

 楼主| FiroEuro 发表于 2014-1-1 02:58:01 | 显示全部楼层
本帖最后由 FiroEuro 于 2014-1-1 02:59 编辑

我的问题跟刷题有什么关系吗?不想回答问题请点右上角叉叉,不要假设别人没看过算法书。我是不是还应该请你看逻辑学书籍呢。
回复 支持 反对

使用道具 举报

RonHe 发表于 2014-1-1 03:25:54 | 显示全部楼层
本帖最后由 RonHe 于 2014-1-1 03:37 编辑

O(1), O(N)指的不是时间

“汇编里的O(1),JAVA里的O(1)和MATLAB里的O(1)”
等同于“月球上的质量,地球上的质量和火星上的质量”

质量是物体的属性,类比地说,时间复杂度是算法的属性,都是不变的
但物体所受重力,算法运行时间是变的

一点拙见
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-1-1 03:42:40 | 显示全部楼层
本帖最后由 1guangnian 于 2014-1-1 03:50 编辑

很好奇楼主是否真的好好看过算法书
1是O(1), 2也是O(1),N是O(N), 2N也是O(N)


回复 支持 反对

使用道具 举报

nevery123 发表于 2014-1-1 04:03:14 | 显示全部楼层
很明显,楼主自己不明白O(1)和O(N)代表什么,O代表的是一个算法的渐进复杂度,是衡量输入值趋近于无穷的情况下算法的运行上限,是不能和实际的运行时间挂钩的。O(1)代表一个算法的运行时间为常数,比如哈希表查找一个制定元素,和表中的元素数目无关,O(N)代表算法的运算时间和输入成线性关系,比如从无序数组中找制定元素。具体的运算时间不能用大O来比较,比如在元素数目小的情况下简单的冒泡排序效率会比归并排序,快速排序还高。
回复 支持 反对

使用道具 举报

 楼主| FiroEuro 发表于 2014-1-1 04:16:11 | 显示全部楼层
RonHe 发表于 2014-1-1 03:25
O(1), O(N)指的不是时间

“汇编里的O(1),JAVA里的O(1)和MATLAB里的O(1)”

谢谢回答,看来是我问的不清楚,我就是想知道这个属性在不同的环境里是如何不同的。用不同语言写出一个O(N)的算法,给最坏的输入,然后执行,最后运行的时间不一样的话,差异是怎么形成的,都受哪些因素影响。还有就是运行时间跟时钟频率的关系,比如写一个循环,循环里只有一条语句做加或减的操作,循环100次和1000次的运行时间差别是什么,后者是不是前者的10倍。
回复 支持 反对

使用道具 举报

 楼主| FiroEuro 发表于 2014-1-1 04:43:39 | 显示全部楼层
nevery123 发表于 2014-1-1 04:03
很明显,楼主自己不明白O(1)和O(N)代表什么,O代表的是一个算法的渐进复杂度,是衡量输入值趋近于无穷的情况 ...

谢谢解答,虽然我知道N是O(N),2N 3N也是O(N),但潜意识里还是把O(N)跟N划等号了,惭愧。我想知道的就是在不同的编程语言里写程序,里面一次运算操作实际用掉的时间是不是等于一个时钟沿,如果是100次又如何,不同的运行时间的差异受哪些因素影响
回复 支持 反对

使用道具 举报

Kimurate 发表于 2014-1-1 05:44:58 | 显示全部楼层
感觉你对复杂度的概念不理解吧,复杂度不是代表算法运行时间,是代表运行时间随处理数据量增大而增加的速度。
回复 支持 反对

使用道具 举报

monkerek 发表于 2014-1-1 06:14:34 来自手机 | 显示全部楼层
一条c指令会对应多个时钟周期      一般不会只是一个   
回复 支持 反对

使用道具 举报

asdfyou6 发表于 2014-1-1 06:31:23 | 显示全部楼层
本帖最后由 asdfyou6 于 2014-1-1 06:33 编辑

O(x)里面的x指的不是具体的时间,而是程序执行中要执行的#of basic statement,意思是这个是评价一个算法的复杂度的,而不是具体程序运算的复杂度,我的理解是这个当然就language independent了,纯粹是算法level上的
另外楼主一定没上过算法课,这东西第一节课都要讲明白的
回复 支持 反对

使用道具 举报

 楼主| FiroEuro 发表于 2014-1-1 08:21:41 | 显示全部楼层
asdfyou6 发表于 2014-1-1 06:31
O(x)里面的x指的不是具体的时间,而是程序执行中要执行的#of basic statement,意思是这个是评价一个算法的 ...

不幸的是我上过算法课……好吧我对不起老师。
回复 支持 反对

使用道具 举报

readman 发表于 2014-1-1 09:10:39 | 显示全部楼层
不是时间. 是量级.
量级的意思是: 不能具体说清楚有多少, 但是可以模糊的认为一个大的量级的区间比小的要大.
例如million vs billion
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 07:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表