arrays - 空间中的固定数组大小是 O(n) 还是 O(1)？

Question

是这样声明的数组：
int array[M]，O(1)在空间中还是O(n)？其中 M 是某个固定值。对我来说O(n)是有道理的，因为它不仅仅是一个变量，而是一个完整的数组。但后来我认为这可能是O(1)因为我们有一个固定的大小并且它没有改变！

Answer 1

如果您的数组具有固定大小并且它不随输入的大小而变化，O(1)因为它可以表示为c * O(1)= O(1)，并且c是一些常数。例如，如果您需要一个大小为 5 的数组来保存算法中运行超过一百万（或其他任意数量）整数的状态。重要的是M并且N是独立的。

但是，如果M表示您的输入的大小或直接取决于输入大小的值（即N/2或其他一些线性函数），那么它确实M会随着您N的输入大小而增长O(N)。一个例子是一个数组，它包含您想要对其运行算法的所有输入数字（即确定平方和）。

Answer 2

当 M 是常数时，我会说 O(1)。如果它是 O(n)，它的大小必须是 M 的线性函数，在这种情况下不是。

Answer 3

您给出的其他答案是正确的，正式是O(1)。

但是要非常仔细地思考“常数”的含义。O(...) 表示法并不是用来衡量实际计算机程序的性能，而是按照复杂性对算法进行分类。

如果您正在实现一个算法，该算法对一组对象只读取一次（例如），您可能会说“好的，让我们将元素的数量固定为 N”，但这不会将算法移动到O(1) 复杂度类，算法仍然是 O(n) 但您将测试用例限制为 n = N，其中 N 是固定的。