C++ 程序的时间和 space 复杂度
Time and space complexity of c++ program
#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) space 复杂度。
我同意这个程序的时间复杂度,因为 isFirstComeFirstServed 函数将被调用 n 次,这是 servedOrders 向量的大小,对吗? removeFirstOrder 将在 isFirstComeFirstServed 的第一次函数调用中调用 n 次,在 isFirstComeFirstServed 的第二次函数调用中调用 n-1 次,依此类推,直到 servedOrder Vector Right 中没有剩余元素?
但我的疑惑是它怎么能有 O(n^2) space 的复杂度?有人可以帮我想象一下吗?
每调用一次removeFirstOrder
返回的向量就小1
n-1 + n-2 + n-3 + ... + 1
根据arithmetic progression规则,总和为(n+1)*n / 2,即n^2阶。
Tail call 优化可以使其在幕后运行 O(n) space,但完全不能保证执行。
#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) space 复杂度。
我同意这个程序的时间复杂度,因为 isFirstComeFirstServed 函数将被调用 n 次,这是 servedOrders 向量的大小,对吗? removeFirstOrder 将在 isFirstComeFirstServed 的第一次函数调用中调用 n 次,在 isFirstComeFirstServed 的第二次函数调用中调用 n-1 次,依此类推,直到 servedOrder Vector Right 中没有剩余元素?
但我的疑惑是它怎么能有 O(n^2) space 的复杂度?有人可以帮我想象一下吗?
每调用一次removeFirstOrder
返回的向量就小1
n-1 + n-2 + n-3 + ... + 1
根据arithmetic progression规则,总和为(n+1)*n / 2,即n^2阶。
Tail call 优化可以使其在幕后运行 O(n) space,但完全不能保证执行。