Question

求大神帮忙算一下时间复杂度，要过程，代码如下 vector<int> calculate(string

求大神帮忙算一下时间复杂度，要过程，代码如下

vector<int> calculate(string str)
{
int leftLength = 0;
int result = 0;
vector<int> temp;

for(leftLength = 1;leftLength < str.length();leftLength += 2)
{
vector<int> templ,tempr;
string left = str.substr(0,leftLength);
string right = str.substr(leftLength+1,str.length() - leftLength);
char op = str[leftLength];
int l,r,tl,tr;

if(left.length() == 1)
{
templ.push_back(left[0]-'0');
}

if(right.length() == 1)
{
tempr.push_back(right[0]-'0');
}

if(left.length() > 1)
{
templ = calculate(left);
}

if(right.length() > 1)
{
tempr = calculate(right);
}

for (tl = 0;tl < templ.size();tl++)
{
for(tr = 0;tr < tempr.size();tr++)
{
l = templ[tl];
r = tempr[tr];

switch(op)
{
case '+': result = l + r; temp.push_back(result);break;
case '-': result = l - r; temp.push_back(result);break;
case '*': result = l * r; temp.push_back(result);break;
}
}

}

}

return temp;

}

Answer 1

这个时间复杂度是O(N)的。

追问

怎么算的？应该不是O（n），里面有递归