algorithm - 对具有 n 个元素的列表执行 O(1) 操作需要多少条指令？

Question

一个。总是一个
b. 不超过 n
c。一些固定的数字
d. 不超过 3

我选择了“不超过n”，但我的老师告诉我这是错误的。她没有给出错的原因，如果错了，答案是什么？

Answer 1

答案是否定的。下面的方法是O(1)。

1. 显然，它并不总是一个。
2. 有时大于 n。
3. 显然这不是一个固定的数字。
4. 它总是超过三个。

//

public void run ( List of size n )
{
     for ( int i = 0 ; i < 100 + ( n  % 100 ) ; i ++ )
     {
          step ( ) ;
     }
}

Answer 2

正确答案是c。一些固定的数字。这个想法是无论元素的数量如何，操作总是花费相同的时间。 见常数时间

Answer 3

一些固定的号码。

O(1)意味着恒定时间，或者意味着执行时间不取决于输入的大小（即使它可能需要比宇宙尽头更长的时间来执行）。

Answer 4

一些固定的数字将是正确的答案。您可以让函数执行 n-1 或 n+1 次操作，并且 b)/d) 会得到满足，但仍会在 O(n) 时间内完成。O(1) 时间要求有一个固定数 C，使得函数在 C 操作中运行，而与 n 无关。

也应该有一个算法标签而不是 Java 标签：P