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