插入的空间复杂度不应该是O(N)吗？

Question

这包括来自https://stackoverflow.com/help/on-topic的"软件算法"

这是来自课堂的讲座幻灯片

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

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;
     }
}

我同意局部变量的空间复杂度将是O(1),因为它每次都是相同的局部变量,无论输入大小,i,j和temp都会占用一块内存.

但是我对阵列的空间复杂性感到困惑.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,这意味着它的空间复杂度是O(N)？

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

Answer 1

Array passed by reference表示您就地排序,输出数据不需要额外的空间.

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

在最后的代码段的条款,该太是O(1)简单地因为数组降解为第一元素指针时传递给函数.作者似乎在链接页面底部的评论中理解了这个概念:

但是在这里要小心.如果通过指针或引用传递内容,则共享空间.如果A将C样式数组传递给B,则不会分配新空间.

但是,出于某种原因,他们似乎相信传递数组会复制^(b).

^(a)如果空间复杂性包括原始数据集,则O(1)复杂性是不可能的.

^(b)而且,由于能够代表提交人发言的最佳人选是作者本人,我提出了一个问题,并且答复解释了两个案件之间的区别.我希望他不介意,因为作为一名教育工作者,我认为他和我一样有"增加全面的知识在世界"的态度,并且它表明我对这种态度的尊重程度令人耳目一新:

额外的空间通常被称为辅助空间复杂性.没有限定符,空间复杂性包括输入空间要求.

我的页面至少应该参考这个区别.一个更好的页面将显示一些简单的实际例子,说明算法如何权衡时间,空间和算法的简单性,但由于我多年没有教过我们的数据结构课程,我没有返回维护任何这些页面.我也不会声称自己是复杂性理论方面的专家.自然语言理解,基于案例的推理和敏捷软件开发是我的优势.

我认为它支持页面顶部关于缺乏关于空间复杂性的简单写作的声明,这个微不足道的页面在Google上排名与它一样高.

感谢您与我联系,我希望这会有所帮助.

所以它似乎是术语上的差异,而不是任何人的完全错误.我不完全确定我看到非辅助空间复杂度(包括原始数据集的大小)的有用性,因为无论选择何种算法,这都是沉没成本.

此外,我一直将复杂性视为算法的属性,并且由于所选择的算法无法控制原始数据集的大小,因此我倾向于不包含它.

但是,我将来会更具体一点,确保我说明空间复杂性的意思,以防读者不确定:-)

无论如何,至少可以澄清为什么你的课程笔记和西北大学的课程注意事项不同.无论您选择哪种空间复杂度定义,都应调整其中一个以将其考虑在内.