c++程序的时间和空间复杂性

Question

#include<iostream>
#include<vector>

using namespace std;

vector <int> removeFirstOrder(const vector<int>& orders)
{
    return vector<int>(++orders.begin() , orders.end());
}

bool isFirstComeFirstServed(const vector<int>& takeOutOrders,
                            const vector<int>& dineInOrders,
                            const vector<int>& servedOrders)
{
    //base case
    if(servedOrders.empty())
    {
        return true;
    }

    if(!takeOutOrders.empty() && takeOutOrders[0]==servedOrders[0])
    {
        return isFirstComeFirstServed(removeFirstOrder(takeOutOrders),
                                      dineInOrders,removeFirstOrder(servedOrders));

    }

    else if(!dineInOrders.empty() && dineInOrders[0]==servedOrders[0])
    {
        return isFirstComeFirstServed(takeOutOrders, removeFirstOrder(takeOutOrders),
                                        removeFirstOrder(servedOrders));

    }

    else
    {
        return false;
    }
}


int main()
{
    vector<int> takeOutOrders{17,8,4};

    vector<int> dineInOrders{12,19,2};
    vector<int> servedOrders{17,8,12,19,24,2};
    isFirstComeFirstServed(takeOutOrders,dineInOrders,servedOrders);



    return 0;
}

我的疑问是这个程序的作者在这里说它有O(n^2)的时间复杂度和O(n^2)的空间复杂度，我同意这个程序的时间复杂度，因为isFirstComeFirstServed函数会被调用n次，也就是servedOrders Vector的大小，对吗？

我同意这个程序的时间复杂度，因为isFirstComeFirstServed函数会被调用n次，也就是servedOrderers向量的大小，而removeFirstOrder会在isFirstComeFirstServed的第一次函数调用中被调用n次，在isFirstComeFirstServed的第二次函数调用中被调用n-1次，以此类推，直到servedOrder向量中没有元素了为止。

但我的疑惑是，它的空间复杂度如何能达到O(n^2)呢？ 有人能帮我把它可视化吗？

Answer 1

每次 removeFirstOrder 被称为返回的向量小于1。

n-1 + n-2 + n-3 + ... + 1

从 等差数列 规则，和为(n+1)*n 2，即阶数为n^2。

尾数调用 优化可以使其在幕后O(n)空间，但根本无法保证执行。