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

Question

我正在读wiki页面，上面写着：

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

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

Answer 1

看看大O的定义：

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

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

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

100≤1* 100

这意味着(根据定义)：

100 = O(1)

因此，时间复杂度变成O(1)。

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