我正在尝试确定我的程序的渐近复杂度，该程序接受输入并确定它是否是多项式。
“如果输入表达式的长度是 m 个字符，那么你的程序相对于 m 的复杂度是多少？”
我的猜测是 O(m*log m) 其中第一个 m 是迭代 m 次的 for 循环，而 log m 是计算大于 1 位的指数的 while 循环。
另外，我正在尝试保存一个“最大”值，该值包含最大指数，以计算多项式运行时复杂度。但是，我对正确存储指数感到困惑。谁能推荐一个更简单的方法？
示例输入：“n^23 + 4n^10 - 3”应该有 23 作为最大指数
#include <iostream>
#include <string>
using namespace std;
int main() {
string input;
int pcount = 1; //count for # of variables( min 3 to be poly)
int largest = 0; // used for complexity
int temp=0;
cout << "Enter equation below. " << endl;
getline(cin,input); //to input polynomial
cout << endl << input << endl;
if (input[0] == '-' || input[0] == '+') //to check for '-' as first char
pcount--;
bool pcheck = true;
for (unsigned i = 0; i < input.size(); i++)
{
temp = 0;
cout << input[i] << endl;
if ( input[i] == '+' || input[i] == '-' )
pcount++;
if ( input[i] == 'n') //checks for integer
{
if ( input[i+1] && input[i+1] == '^' )
{
if (input[i+2] == 46 || input[i+2] == 43 || input[i+2] == 45)
{
cout << "fail" << endl;
pcheck = false;
}
temp = input[i+2]-48; // to check for largest exp
while ( input[i+2] != 43 && input[i+2] != 45)
{
if ( i+3 == input.size())
{
cout << "break";
break;
}
if( input[i+2] < 48 || input[i+2] >57) // 48-57 is ascii
{
cout << "fail" << endl;
pcheck = false;
}
i++;
temp = temp * 10;
temp = temp + (input[i+2]-48);
if (temp > largest)
largest = temp;
}
}
}
}
if ( pcheck == true && pcount >= 3) //valid ints and at least 3 variables
{
cout << "polynomial detected!" << endl << "The big-Oh complexity is O(n^" <<
largest << ")." << endl;
}
else
cout << "not a poly" << endl;
return 0;
}