固定数组大小为O（n）或O（1）空间？ [英] Is fixed array size O(n) or O(1) in space?

问题描述

声明一个这样的数组：结果
int数组[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!

推荐答案

如果您的数组大小是固定的，它不随输入它的大小而有所不同 O（1），因为它可以pssed为 C * O（1） = O（1）与 C 是某个常数。如果需要的大小为5的数组中的算法运行超过一百万（或一些其它任意数）的整数，以保持状态的一个例子是。最重要的是 M 和 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 as c * O(1) = O(1), with c being 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 is M and N are independent.

然而，如果 M 重新presents您的输入，或者直接取决于输入的大小（即 N / A值的大小2 或其它一些线性函数），那么真的 M 与 N 一起成长，输入的大小，因此这将是 O（N）。一个例子是包含其中要在运行一个算法（即确定所述平方之和）中的所有输入数的阵列。

If however M represents the size of your input or a value that is directly dependent of the input size (i.e. N/2 or some other linear function), then really M grows along with your N, the input size so it would be O(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).

这篇关于固定数组大小为O（n）或O（1）空间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！