373-時間複雑度(式の評価)
タイトルリンク:373-時間複雑度
ACMでは、複雑さの計算は非常に重要なことです.一般的な複雑さのフォーマットは3つあります.
O(n)O(lg(n))O(sqrt(n))1つのアルゴリズムには多くの解法があり、各解法の複雑度は上述した一般的な複雑度を組み合わせて、例えば並べ替えの2つのアルゴリズムがある.
クイックソート:時間複雑度O(n*lg(n))
バブルソート:時間複雑度O(n*n)
n,mのアルゴリズムの複雑さを指定し、これらの複雑さがタイムアウトするかどうかを確認します.複雑度計算結果が10000000より大きい場合はタイムアウト(TLE)であり、そうでない場合は計算の複雑度を出力し、出力結果は2桁の小数を保持する.
(lg(n)は2をベースとし、nを真とする値を表す)
入力記述:第1行はn(1≦n≦10000)、m(1≦m≦100)を入力し、ここでnはテーマ記述の数、mはアルゴリズム複雑度の個数である.次にm行、各動作の1つの列、各列はすべてO()のいかなる括弧の中のデータを含んでn,lg(),sqrt(),*だけから構成して合法的であることを保証します.sample inputに示すように.
出力記述:各列について、算出された複雑度が1000000より大きい場合、TLEが出力され、そうでない場合、その複雑度の算出回数が出力される
サンプル入力:コピー10000 6 O(n*n)O(n*n*n)O(sqrt(n))O(lg(n))O(n*lg(n))O(n*lg(n))
サンプル出力:1000000.00 TLE 100.00 13.29 132877.12 170197.33
ヒント:lg(n)に関するC言語コードはlog(n)/log(2)と書くことができます.
ここでは、3つの書き方を示します.
1つ目は暴力をシミュレートすることです
#include
#include
#include
#include
using namespace std;
const int maxn=1000000;
char a[maxn];
double n;
int t;
double dfs(int l,int r)
{
double ans=1;
for(int i=l; i<=r; i++)
{
if(a[i]=='n')
ans*=n;
else if(a[i]=='l')
{
i+=3;
int e,f1=1;
for(int j=i; f1; j++)
{
if(a[j]==')')
f1--;
if(a[j]=='(')
f1++;
if(f1==0)
{
e=j;
break;
}
}
double f=dfs(i,e-1);//
ans*=log(f)/log(2.0);
i=e;
}
else if(a[i]=='s')
{
i+=5;
int e,f1=1;
for(int j=i; f1; j++)
{
if(a[j]==')')
f1--;
if(a[j]=='(')
f1++;
if(f1==0)
{
e=j;
break;
}
}
double f=dfs(i,e-1);//
ans*=sqrt(f);
i=e;
}
}
return ans;
}
int main()
{
int g;
while(~scanf("%lf%d",&n,&t))
{
while(t--)
{
scanf("%s",a);
int la=strlen(a);
double f=dfs(2,la-2);//
if(f>100000000.0)
printf("TLE
");
else printf("%.2lf
",f);
}
}
return 0;
}
2つ目はpythonで書かれています.
import math
def lg(n):
return math.log2(n)
def sqrt(n):
return math.sqrt(n)
def O(n):
return eval(str(n))
n,m=map(int,input().split())
for case in range(m):
s=input()
ans=eval(str(s))
if ans>100000000:
print('TLE')
else:
print('%.2f' % ans)
3つ目はシミュレーションです.
#include
#include
#include
#include
#include
using namespace std;
int n,m;
string s;
string sta_c[10000];
double num[10000];
int top_c,top_n,len;
int main()
{
scanf("%d%d",&n,&m);
while(m--)
{
memset(num,0,sizeof(num));
top_c=top_n=0;
cin>>s;
len=s.size();
for(int i=0; i<=len; i++)
sta_c[i]="";
for(int i=2; i1; i++)
{
if(s[i]=='n')
num[++top_n]=n;
else if(s[i]=='(') sta_c[++top_c]="(";
else if(s[i]=='l') sta_c[++top_c]="lg";
else if(s[i]=='s') sta_c[++top_c]="sqrt";
else if(s[i]=='*') sta_c[++top_c]="*";
else if(s[i]==')')
{
while(sta_c[top_c]!="(")
{
if(sta_c[top_c]=="*")
{
num[top_n-1]=num[top_n]*num[top_n-1];
top_n--;
}
top_c--;
}
if(sta_c[top_c]=="(")
{
top_c--;
if(sta_c[top_c]=="lg")
{
num[top_n]=log(num[top_n])/log(2);
top_c--;
}
else if(sta_c[top_c]=="sqrt")
{
num[top_n]=sqrt(num[top_n]);
top_c--;
}
}
}
}
while(top_n!=1)
{
num[top_n-1]=num[top_n-1]*num[top_n];
top_n--;
}
if(num[1]>100000000)
printf("TLE
");
else
{
printf("%.2lf
",num[1]);
}
}
}