空间中固定数组大小是 O(n) 还是 O(1)？
数组是这样声明的：int array[M]、空间中的O(1)还是O(n)？其中 M 是某个固定值。对我来说，O(n) 很有意义，因为它不仅仅是一个变量，而是整个数组。但后来我认为它可能是 O(1) 因为我们有固定的大小并且它不会改变！
Is an array declared like this:int array[M], O(1) in space or O(n)? where M is some fixed value. To me O(n) makes sense because it is not just a single variable but an entire array. But then i think it could be O(1) since we have a fixed size and it is not changing!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果您的数组具有固定大小并且不随输入大小变化，则其时间复杂度为
O(1)，因为它可以表示为c * O(1)> =O(1)，其中c是某个常数。例如，如果您需要一个大小为 5 的数组来保存运行超过一百万（或其他任意数字）整数的算法中的状态。重要的是M和N是独立的。但是，如果
M表示输入的大小或直接依赖于输入大小的值（即N/2或其他一些线性函数），那么实际上M随输入大小N一起增长，因此它将是O(N)。一个示例是一个数组，其中包含要对其运行算法（即确定平方和）的所有输入数字。If your array is of a fixed size and it does not vary with the size of the input it is
O(1)since it can be expressed asc * O(1)=O(1), withcbeing some constant. An example would be if you needed an array of size 5 to hold state in your algorithm that runs over a million (or some other arbitrary number) integers. The important thing isMandNare independent.If however
Mrepresents the size of your input or a value that is directly dependent of the input size (i.e.N/2or some other linear function), then reallyMgrows along with yourN, the input size so it would beO(N). An example would be an array that holds all input numbers of which you want to run an algorithm over (i.e determining the sum of the squares).当 M 是常数时，我会说 O(1)。如果它是 O(n)，那么它的大小必须是 M 的线性函数，但在本例中不是。
I would say O(1) when M is a constant. If it is O(n) its size must be linear function of M, which in this case is not.
您得到的其他答案是正确的，形式上是O(1)。
但请仔细思考“常数”的含义。 O(...) 表示法并不是为了衡量实际计算机程序的性能，而是为了按复杂性对算法进行分类。
如果您正在实现一个算法，该算法适用于仅读取每个对象一次的对象数组（例如），您可能会说“好吧，让我们将元素数量固定为 N”，但这不会将算法移至O(1) 复杂度类，算法仍然是 O(n) 但您将测试用例限制为 n = N，其中 N 是固定的。
The other answers you were given are correct, formally it's O(1).
But think very carefully about the meaning of "constant". The O(...) notation is not meant to measure the performance of an actual computer program, but to categorize algorithms by complexity.
If you are implementing an algorithm that works on an array of objects reading each of them only once (for example), you may say "ok, let's fix the number of elements to N", but that won't move the algorithm into the O(1) complexity class, the algorithm is still O(n) but you're limiting your test cases to n = N where N is fixed.