2013
12-11

# Instant Complexity

Analyzing the run-time complexity of algorithms is an important tool for designing efficient programs that solve a problem. An algorithm that runs in linear time is usually much faster than an algorithm that takes quadratic time for the same task, and thus should be preferred.

Generally, one determines the run-time of an algorithm in relation to the size’ n of the input, which could be the number of objects to be sorted, the number of points in a given polygon, and so on. Since determining a formula dependent on n for the run-time of an algorithm is no easy task, it would be great if this could be automated. Unfortunately, this is not possible in general, but in this problem we will consider programs of a very simple nature, for which it is possible. Our programs are built according to the following rules (given in BNF), where < number > can be any non-negative integer:

< Program > ::= "BEGIN" < Statementlist > "END"
< Statementlist > ::= < Statement > | < Statement > < Statementlist >
< Statement > ::= < LOOP-Statement > | < OP-Statement >
< LOOP-Statement > ::= < LOOP-Header > < Statementlist > "END"
< LOOP-Header > ::= "LOOP" < number > | "LOOP n"
< OP-Statement > ::= "OP" < number >

The run-time of such a program can be computed as follows: the execution of an OP-statement costs as many time-units as its parameter specifies. The statement list enclosed by a LOOP-statement is executed as many times as the parameter of the statement indicates, i.e., the given constant number of times, if a number is given, and n times, if n is given. The run-time of a statement list is the sum of the times of its constituent parts. The total run-time therefore generally depends on n.

The input starts with a line containing the number k of programs in the input. Following this are k programs which are constructed according to the grammar given above. Whitespace and newlines can appear anywhere in a program, but not within the keywords BEGIN, END, LOOP and OP or in an integer value. The nesting depth of the LOOP-operators will be at most 10.

For each program in the input, first output the number of the program, as shown in the sample output. Then output the run-time of the program in terms of n; this will be a polynomial of degree Y <= 10. Print the polynomial in the usual way, i.e., collect all terms, and print it in the form “Runtime = a*n^10+b*n^9+ . . . +i*n^2+ j*n+k”, where terms with zero coefficients are left out, and factors of 1 are not written. If the runtime is zero, just print “Runtime = 0”.
Output a blank line after each test case.

2
BEGIN
LOOP n
OP 4
LOOP 3
LOOP n
OP 1
END
OP 2
END
OP 1
END
OP 17
END
BEGIN
OP 1997 LOOP n LOOP n OP 1 END END
END

Program #1
Runtime = 3*n^2+11*n+17

Program #2
Runtime = n^2+1997

#ifdef _MSC_VER
#define DEBUG
#define _CRT_SECURE_NO_DEPRECATE
#endif

#include <fstream>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <limits.h>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <functional>
#include <ctype.h>
#define MAX  20
using namespace std;

int order[1000][2];

void func(const int &beg,const int &end,int *num)
{
for(int i=beg;i<end;)
{
if(order[i][0]==3)
{
num[0]+=order[i][1];
++i;
}
else if(order[i][0]==2)
{
int temp[20];
memset(temp,0,sizeof(temp));
int sum=1;
int t=i+1;
while(sum)
{
if(order[t][0]==2)
++sum;
else if(order[t][0]==1)
--sum;
++t;
}
func(i+1,t-1,temp);

if(order[i][1]==INT_MAX)
for(int j=0;j<MAX-1;++j)
num[j+1]+=temp[j];
else
for(int j=0;j<MAX;++j)
num[j]+=temp[j]*order[i][1];

i=t;
}
}
}

int main(void)
{
#ifdef DEBUG
freopen("../stdin.txt","r",stdin);
freopen("../stdout.txt","w",stdout);
#endif

string str,cost;
int ncases;
scanf("%d",&ncases);
cin>>str;

for(int nc=1;nc<=ncases;++nc)
{
int n=0;
int sum=1;
while(sum)
{
if(str=="BEGIN" )
order[n++][0]=0;
else if(str=="END")
{
order[n++][0]=1;
--sum;
}
else
{
cin>>cost;
int temp;
if(cost=="n")
temp=INT_MAX;
else
temp=atoi(cost.c_str());
if(str=="LOOP")
{
order[n][0]=2;
++sum;
}
else
{
order[n][0]=3;
}
order[n++][1]=temp;
}
cin>>str;
}

int ans[MAX];
memset(ans,0,sizeof(ans));
func(1,n-1,ans);
printf("Program #%d\nRuntime =",nc);

bool flag=false;
for(int i=MAX-1;i>1;--i)
if(ans[i]>1)
{
printf("%c%d*n^%d",flag?'+':' ',ans[i],i);
flag=true;
}
else if(ans[i]==1)
{
printf("%cn^%d",flag?'+':' ',i);
flag=true;
}

if(ans[1]>1)
{
printf("%c%d*n",flag?'+':' ',ans[1]);
flag=true;
}
else if(ans[1])
{
printf("%cn",flag?'+':' ');
flag=true;
}

if(ans[0])
{
printf("%c%d",flag?'+':' ',ans[0]);
flag=true;
}

if(!flag)
printf(" 0");
printf("\n\n");

}

return 0;
}`

1. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

2. “可以发现,树将是满二叉树,”这句话不对吧，构造的树应该是“完全二叉树”，而非“满二叉树”。