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!
一个数组是这样声明的:int数组[M]， O(1) in space还是O(n)?M是某个固定值。对我来说，O(n)是有意义的，因为它不仅仅是一个变量，而是整个数组。但是我认为它可以是O(1)因为我们有固定的尺寸，而且它不变!
3 个解决方案
#1
4
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.
如果数组的大小是固定的，并且不随输入的大小而变化，那么它就是O(1)，因为它可以表示为c * O(1) = O(1)， c是某个常数。例如，如果您需要一个大小为5的数组，在您的算法中保持状态，它运行超过100万(或其他任意数)整数。重要的是M和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).
如果M表示输入的大小或者一个直接依赖于输入大小的值(例如N/2或其他线性函数)，那么M就会随着N而增长，输入的大小就是O(N)一个例子是一个数组，它包含所有你想在i上运行算法的输入数。e决定平方和)
#2
1
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)当M是一个常数。如果它是O(n)它的大小必须是M的线性函数，在这种情况下不是。
#3
0
The other answers you were given are correct, formally it's O(1).
你得到的其他答案是正确的，形式上是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.
但是仔细想想“常数”的含义。O(…)表示法不是用来度量实际计算机程序的性能，而是根据复杂性对算法进行分类。
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.
如果你实现一个算法作用于一个对象数组阅读他们每个人只有一次(例如),你可能会说“好的,让我们解决N”元素的数量,但这不会移动到O(1)算法复杂性类,该算法仍然是O(N)但是你限制你的测试用例N = N,N是固定的。
#1
4
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.
如果数组的大小是固定的，并且不随输入的大小而变化，那么它就是O(1)，因为它可以表示为c * O(1) = O(1)， c是某个常数。例如，如果您需要一个大小为5的数组，在您的算法中保持状态，它运行超过100万(或其他任意数)整数。重要的是M和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).
如果M表示输入的大小或者一个直接依赖于输入大小的值(例如N/2或其他线性函数)，那么M就会随着N而增长，输入的大小就是O(N)一个例子是一个数组，它包含所有你想在i上运行算法的输入数。e决定平方和)
#2
1
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)当M是一个常数。如果它是O(n)它的大小必须是M的线性函数，在这种情况下不是。
#3
0
The other answers you were given are correct, formally it's O(1).
你得到的其他答案是正确的，形式上是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.
但是仔细想想“常数”的含义。O(…)表示法不是用来度量实际计算机程序的性能，而是根据复杂性对算法进行分类。
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.
如果你实现一个算法作用于一个对象数组阅读他们每个人只有一次(例如),你可能会说“好的,让我们解决N”元素的数量,但这不会移动到O(1)算法复杂性类,该算法仍然是O(N)但是你限制你的测试用例N = N,N是固定的。