c++ 这个递归插入排序算法的空间复杂度是多少？

yhived7q 于 2023-05-02 发布在其他

关注(0)|答案(3)|浏览(134)

void recursiveInsertionSort(vector<int> &arr, int n) {
    if (n <= 1)
        return;
    recursiveInsertionSort(arr, n - 1);
    int val = arr[n - 1], j = n - 2;
    for (j = n - 2; j >= 0 && arr[j] > val; --j)
        arr[j + 1] = arr[j];
    arr[j + 1] = val;
}

我认为空间复杂度是常数（O（1）），因为我通过引用传递数组。
但我被告知它实际上是O（n）。为什么会这样呢？

c++

来源：https://stackoverflow.com/questions/76032459/what-is-the-space-complexity-of-this-recursive-insertion-sort-algorithm

3条答案

按热度按时间

mtb9vblg1#

数据向量仍然在某个地方占用空间，即使你的函数通过引用获得它。
但是即使你不想考虑这个空间，你的代码仍然需要O（n）空间。
这是因为你将有O（n）递归调用，每个调用占用（在你的情况下）**O（1）**调用堆栈上的空间（用于存储调用上下文-参数等）。）。当您在最内层的递归调用中时，将需要所有这些空间。
这是一个复杂度为O（n）的问题。

注：

在这种情况下，val在任何给定时间实际上只有1个示例是活动的，因为它是在递归调用之后分配的。
但是即使在调用之前定义并使用它，每次调用的空间仍然是O（1），最终结果也是一样的。

赞(0）回复(0）举报 2023-05-02

nvbavucw2#

它消耗O（N）线性空间复杂度，因为在每个递归调用中，你都是O（1）空间，并且函数调用是数组大小的N倍，因此值占用O（1）* N空间，这导致算法的总体空间复杂度为O（N）。