插入排序的space复杂度不应该是O(N)吗？

Question

中的 "software algorithm"

这是来自 class 的讲座幻灯片

这是我们使用的插入排序的实现

public static void insertionSort(int[] a) {
     for (int i = 1; i < a.length; i++) {
          int temp = a[i];
          int j = i;
          while (j >= 1 && a[j - 1] > temp) {
                a[j] = a[j - 1];
         }
         a[j] = temp;
     }
}

我同意局部变量的 space 复杂度为 O(1)，因为无论输入大小如何，每次都是相同的局部变量，i、j 和 temp 将各自占用一块内存。

但是我对数组的 space 复杂性感到困惑。 http://www.cs.northwestern.edu/academics/courses/311/html/space-complexity.html有一个类似的例子，

int sum(int a[], int n) {
    int r = 0;
    for (int i = 0; i < n; ++i) {
       r += a[i];
    }
    return r;
}

并说这个算法需要 N 个内存单元来存储 a，这意味着它的 space 复杂度是 O(N)?

这是哪个？ O(N) 因为数组需要 N 个内存单元（取决于输入大小）或 O(1) 因为通过引用传递？

Answer 1

Array passed by reference 表示您正在就地排序，不需要 extra space 输出数据。

因此 space 复杂性（您需要的超出原始数据集 ^(a)）是一个常数 O(1) 而不是线性O(n).

就最终代码片段而言，也是 O(1)，因为数组在传递给函数时会退化为第一个元素指针。作者在链接页面底部的评论似乎理解了这个概念：

But be careful here. If things are passed by pointer or reference, then space is shared. If A passes a C-style array to B, there is no new space allocated.

但是，出于某种原因，他们似乎认为传递数组会生成一个副本 ^(b)。

^(a) 如果 space 复杂度包括原始数据集，那么 O(1) 复杂度将是 不可能的。

^(b) 而且，由于能够代表作者发言的最佳人选是作者本人，所以我提出了一个问题，回复解释了区别两种情况之间。我希望他不介意，因为作为一名教育工作者，我认为他和我一样有“增加世界上的整体知识”的态度，这表明我发现对这种态度的尊重程度令人耳目一新：

Additional space is usually referred to as auxiliary space complexity. With no qualifier, space complexity includes the input space requirements.

My page of mine should at least reference that distinction. A better page would show some simple practical examples of how algorithms trade off time, space, and the simplicity of the algorithm, but since I haven't taught our data structures course in years, I've not returned to maintain any of those pages. Nor would I ever claim to be an expert on complexity theory. Natural language understanding, case-based reasoning, and agile software development are my strengths.

I suppose it supports the claim on the top of the page about the lack of simple write ups on space complexity that this paltry page ranks as high on Google as it does.

Thanks for contacting me and I hope this helps.

所以这似乎是术语上的差异，而不是任何人的彻头彻尾的错误。我不完全确定我看到了非辅助 space 复杂性（包括原始数据集的大小）的有用性，因为无论选择何种算法，这都是沉没成本.

此外，我一直将复杂性视为算法的属性，并且由于所选算法无法控制原始数据的大小设置，我倾向于不包括它。

不过，我以后会更具体一些，确保我陈述我所说的 space 复杂性的意思，以防读者不确定:-)

无论如何，这至少澄清了为什么你的课程笔记和西北大学的课程笔记在他们的争论中存在差异。无论您选择哪种 space 复杂性定义，都应调整其中之一以将其考虑在内。

Answer 2

本质上两个课程是一致的。

来自西北链接页面：

If a function A uses M units of its own space (local variables and parameters), and it calls a function B that needs N units of local space, then A overall needs M + N units of temporary workspace. What if A calls B 3 times? When a function finishes, its space can be reused, so if A calls B 3 times, it still only needs M + N units of workspace.

重点是函数 A 以及它需要多少 space ，但解释表明 B 复杂度并不高' 考虑 A 已经需要的内容。如果是这种情况，您可以证明程序的任何部分需要与整个程序一样多的内存，这将使任何复杂性评估的用处都非常有限。

将此应用于您的示例，数组来自调用 B 的函数 A（此处为函数 sum），并将数组传递给它。 sum 不分配或构造数组，也不需要复制它，因此它不计入 sum 的要求。

Answer 3

我认为西北的作者是不正确的。用于函数的 space 取决于向函数传递了多少 space，但在函数使用期间分配了多少 space。

在求和示例中，space 在调用函数之前分配，而不是在函数内分配，因此它将计入 space 使用。

插入排序的space复杂度不应该是O(N)吗？

Shouldn't the space complexity of insertion sort be O(N)?

java

arrays

algorithm

sorting

insertion-sort