infinity - O 表示法，O(∞) = O(1)？

Question

所以一个快速的想法；有人会说 O(∞) 实际上是 O(1) 吗？

• 我的意思是它不取决于输入大小？
• 所以在某种程度上它是恒定的，即使它是无限的。

或者是表达它 O(∞) 的唯一“正确”方式？

Answer 1

Infinity 不是一个数字，或者至少不是一个实数，所以表达式格式不正确。表达这一点的正确方法是简单地声明程序不会终止。注意：program，而不是algorithm，因为 algorithm 保证会终止。

（如果你愿意，你也许可以在超限数上定义大 O 表示法。不过，我不确定这是否有用。）

Answer 2

你的论点并不完全正确。

大 O 表示法忽略常数倍数；O(1)和O(42)或O(log(n))和之间没有区别O(3π log(n))。

标准约定是不使用任何常数倍数。

然而，O(∞)这意味着一个永远不会终止的“算法”，而不是O(1)在某个时候终止。

Answer 3

要回答这个问题：

O 表示法，O(∞) = O(1)？

不

主要区别在于 O(1) 将在某个点结束，而 O(∞) 永远不会结束。

它们都不包含变量，但具有不同的含义：

O(1)（或 O(121) 或 O(whatever but not infinity) ：独立于函数参数，但结束

O(∞): 独立于函数参数，并且没有结尾

正如在另一个答案中指出的那样，无穷大实际上并不在大 O 表示法的范围内，但简单的“不”当然仍然存在，O(1) 和 O(∞) 是不一样的。

Answer 4

Big-Oh 是衡量所需资源如何随着 N 增加而扩展的量度。O(5 小时) 和 O(5 秒) 都是 O(1)，因为随着 N 的增加不需要额外的资源。