遍历数组元素的空间复杂度[关闭]

Question

我有一个 C++ 代码片段。

int sumOfArray( int * arr, int size )
{
    int res=0;
    for ( int i=0 ; i<size; i++ )
        res= res+arr[i];
    return res;
}

我对该代码片段的空间复杂度感到困惑。你能指导我它的复杂度是恒定的还是线性的？

Answer 1

程序中使用的空间通常是衡量除输入之外还读取/写入多少空间的指标。 在您的情况下，

int * arr

是您程序的输入（您可以使其成为

const

，而无需以任何其他方式修改您的程序）。

int sumOfArray( int const*const arr, int size )
{
  int res=0;
  for ( int i=0 ; i<size; i++ )
    res= res+arr[i];
  return res;
}

由于您没有使用

arr

作为暂存空间，因此您用作暂存和输出空间的唯一数据是

res

。

res

的大小是

sizeof(int)

，它不是输入参数的函数。 这意味着你的时间复杂度为 O(1)。

然而，这实际上并非如此，因为

arr

 的元素总和的最大值随着 

arr

 中元素的数量而增长。  您编写的程序有一个错误 - 如果 

arr

 的元素加起来超过 

int

 的最大值，您的程序将无法回答问题。

要解决此问题，您需要将大小字段设置为 BigInt，并将返回值设置为 BigInt。 BigInt 以其大小的对数增长。

因此，“正确”的无错误版本的总和实际上会使用 O(log(n)) 空间。 然而，人们经常忽略由整数大小限制引起的 log(n) 因子，并假装整数可以容纳无限量的数据。 有趣的是，这个假设实际上使所有程序都占用 O(1) 空间，因为您可以细分无限的整数以在其中存储无限的数据。 ;)