时间复杂度代表的真正的运行时间是多少？

大家都知道算法分析里的时间复杂度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)应该是不一样的吧。农友们对这个怎么看？

——————————————————————————————————————————————————————————————————
楼主承认自己不懂算法，让这贴沉了吧

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

swift_sweep1 发表于 2014-1-1 01:13
我觉得LZ还是找本算法书好好看一下吧 真是一开口就知道是直接刷题的急性子...

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

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

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

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

一点拙见

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

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

RonHe 发表于 2014-1-1 03:25
O(1), O(N)指的不是时间

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

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

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

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

感觉你对复杂度的概念不理解吧，复杂度不是代表算法运行时间，是代表运行时间随处理数据量增大而增加的速度。

一条c指令会对应多个时钟周期      一般不会只是一个