可能重复：
是否有任何 O(1/n) 算法？
您的代码是否有可能是 Big O 小于 O(1)？
问问题
3930 次
3 回答
9
O(1) 仅表示恒定时间操作。该时间可能是 1 纳秒或 100 万年，该符号不是绝对时间的度量。当然，除非您正在为时间机器开发操作系统，否则您的 DoTimeTravel( ) 函数可能具有 O(-1) 复杂性:-)
于 2009-08-17T06:13:22.330 回答
2
并不真地。O(1)是恒定的时间。就纯粹的大 O 表示法而言，无论您将其表达为O(1)还是真的没有什么不同。O(2)O(.5)
正如在这个问题中所指出的，在技术上可能有一个O(1/n)，但是没有现实世界的有用算法可以满足这一点（尽管有些算法确实具有1/n作为其算法复杂性的一部分）。
于 2009-08-17T06:09:05.913 回答
0
唯一需要少于 O(1)（恒定时间）的操作将是一个完全什么都不做的操作，因此花费了零时间。但即使是 NOP 通常也需要固定数量的周期......
于 2009-08-17T06:11:28.670 回答