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

Question

数组是这样声明的：
int array[M], O(1)in space 还是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)。一个例子是一个数组，其中包含您想要运行算法的所有输入数字（即确定平方和）。