complexity-theory - O(1) 是否意味着算法需要一步来执行所需的任务？

Question

我认为这意味着运行需要一定的时间。这和一步有区别吗？

标签： complexity-theory

Answer 1

O(1) 是一类函数。即，它包括以常数为界的函数。

我们说一个算法具有 O(1) 的复杂性，当且仅当它所采取的步数作为输入大小的函数时，受 a(n 任意) 常数的限制。这个函数可以是一个常数，或者它可以增长，或者表现得混乱，或者像正弦波一样波动。只要它永远不会超过某个预定义的常数，它就是 O(1)。

有关详细信息，请参阅大 O 表示法。