算法的空间复杂度

Question

Example1:给出了n个元素的数组A的输入。

见下面的阿尔戈：

Algo(A, I, n)
{
    int i, j = 100;
    for (i = 1 to j)
        A[i] = 0;
}

空间复杂度=变量i +变量'j'所需的额外空间

在这种情况下，我的空间复杂度是: O(1) =>常数

Example2：大小为n的数组，作为输入

A(A,I,n)
{
    int i;
    create B[n]; //create a new array B with same number of elements
    for(i = 1 to n)
      B[i] = A[i]
}

空间复杂性：i + new Array B => 1+n => O(n)占用的额外空间

即使我在这里使用了5个变量，空间复杂度仍然是O(n)。

如果按照计算机科学的说法，我的空间复杂度对于第一位总是不变的，而O(n)则是第二位的，即使我在上面的算法中使用了10个变量，为什么总是建议程序使用较少的变量呢？

我确实理解，在实际的场景中，它使代码更加可读性更强，更易于调试等等。

但只是在这里才能从空间复杂性的角度来寻找答案。

Answer 1

在性能分析中，大O复杂度并不是所有的考虑因素.当您看到渐近(大O)复杂性时，您正在下降的全部是常量。两种算法可以具有相同的大O复杂度，但其中一种算法的代价可能是另一种算法的数千倍。

例如，如果一种解决问题的方法总是以10s单位为单位，而另一种方法为300 S单位，则无论输入大小如何，它们都具有O(1)时间复杂度。当然，这并不意味着两者都同样好；如果没有真正的好处，使用后一种方法就是浪费大量的时间。

这并不是说，性能是唯一的，甚至是首要的考虑，当有人建议你节约使用局部变量。其他考虑因素，如可读性，或避免微妙的错误也是因素。

Answer 2

用于此代码段

Algo(A, I, n)
{
    int i, j = 100;
    for (i = 1 to j)
        A[i] = 0;
}

空间复杂度为:数组为O(1)，变量i和j为常数空间。

建议使用较少的变量，因为，每个变量占用常数空间，如果您有'k‘变量，k变量将使用k*常量空间，如果考虑每个变量是int类型的，那么int占用2字节，所以k*2字节，让k作为10，所以它在这里20字节。

它类似于使用int A10 =>20字节空间复杂度。

我希望你能理解