algorithm - 在无序数组中寻找最小值的时间复杂度

Question

我正在阅读 wiki page其中说:

However, finding the minimal value in an unordered array is not a constant time operation as scanning over each element in the array is needed in order to determine the minimal value. Hence it is a linear time operation, taking O(n) time. If the number of elements is known in advance and does not change, however, such an algorithm can still be said to run in constant time.

如果事先知道元素的数量，我无法理解时间复杂度如何变为常量？还是不是O(n)吗？

Answer 1

看一下 Big-O 的定义:

f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.

如果我们知道数组的大小，比如说 100，很明显我们需要 100 步来检查数组中的最小值是多少。

因此，对于每个 n ≥ 1，c = 100:

100 ≤ 1 * 100

这意味着(根据定义):

100 = O(1)

所以时间复杂度变为O(1)。

如果还是不明白，请尝试证明它对 n 大小的数组。