5

入力を受け取り、それが多項式かどうかを判断するプログラムの漸近的な複雑さを判断しようとしています。

「入力式の長さが m 文字の場合、m に対するプログラムの複雑さはどれくらいですか?」

私の推測では、最初の m は m 回反復する for ループであり、log m は 1 桁を超える指数をカウントする while ループである O(m*log m) です。

また、多項式の実行時の複雑さを計算するために、最大の指数を保持する「最大」の値を保存しようとしています。ただし、指数を正しく格納することに混乱しています。誰でも簡単な方法をお勧めできますか?

入力例: "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;
}
4

1 に答える 1

0

これまでの最高指数を追跡している限り、プログラムは入力文字のO(N)複雑さ (線形) を持つ必要があります。Nこれにより、前の文字を読み直す必要がなくなります。

于 2013-01-22T08:31:12.470 に答える