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

Question

我正在阅读维基页面，上面写着：

但是，在无序数组中找到最小值并不是一个恒定时间操作，因为需要扫描数组中的每个元素才能确定最小值。因此，它是一个线性时间操作，需要 O(n) 时间。但是，如果预先知道元素的数量并且不改变，那么这样的算法仍然可以说是在恒定时间内运行的。

如果事先知道元素的数量，我无法理解时间复杂度如何变得恒定？它仍然不是O（n）吗？

标签： algorithm

Answer 1

看一下Big-O的定义：

f(n) = O(g(n)) 表示存在正常数 c 和 k，因此对于所有 n ≥ k，0 ≤ f(n) ≤ cg(n)。对于函数 f，c 和 k 的值必须是固定的，并且不能依赖于 n。

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

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

100 ≤ 1 * 100

这意味着（根据定义）：

100 = O(1)

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

如果您仍然无法理解，请尝试为 n 大小的数组证明它。