Hi guys, I'm pretty new to C ++ and trying to determine the asymptotic complexity of my program, which takes input and determines if it is a polynomial or not.
"If the length of the input expression is m characters, what is the great complexity of your program with respect to m?"
My guess is O (m * log m), in which the first m is a for loop that iterates m times, and log m is a while loop that counts metrics over 1 digit.
In addition, I am trying to preserve the “largest” value that contains the largest metric in order to calculate the complexity of polynomial execution. However, I got confused about the proper storage of the exponent. Can anyone recommend an easier way?
Input example: "n ^ 23 + 4n ^ 10 - 3" should have 23 as the largest indicator
#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; }
source share