즉석 복잡도 분석

알고리즘의 수행 시간 복잡도를 분석하는 것은 효율적인 프로그램을 설계하는 데 꼭 필요한 도구이다. 같은 작업에 대해 선형 시간에 동작하는 알고리즘은 보통 이차 시간이 걸리는 알고리즘보다 훨씬 빠르므로 더 선호된다.

수행 시간은 보통 입력의 크기 $n$ 에 대한 식으로 나타낸다. 여기서 $n$ 은 정렬할 원소의 개수, 다각형의 꼭짓점의 개수 등이 될 수 있다. 수행 시간을 $n$ 에 대한 식으로 구하는 것은 일반적으로 쉬운 일이 아니므로 이를 자동화할 수 있다면 좋을 것이다. 일반적으로는 불가능하지만, 이 문제에서는 자동화가 가능한 매우 단순한 형태의 프로그램만 다룬다. 프로그램은 아래 BNF 문법을 따르며, < number > 는 임의의 음이 아닌 정수이다:

< 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 >

이러한 프로그램의 수행 시간은 다음과 같이 계산한다. OP 문을 실행하는 데에는 그 매개변수 값만큼의 시간 단위가 든다. LOOP 문이 감싸는 문 목록은 루프의 매개변수가 가리키는 횟수만큼 실행된다. 즉 숫자가 주어지면 그 상수 횟수만큼, n 이 주어지면 $n$ 번 실행된다. 문 목록의 수행 시간은 그 구성 요소들의 수행 시간의 합이다. 따라서 전체 수행 시간은 일반적으로 $n$ 에 의존한다.

첫 줄에는 프로그램의 개수 $k$ 가 주어진다. 그 뒤에 위 문법을 따르는 $k$ 개의 프로그램이 이어진다. 공백과 줄바꿈은 프로그램 안 어디에나 나타날 수 있지만, 키워드 BEGIN, END, LOOP, OP 내부나 정수 값 내부에는 나타나지 않는다. LOOP 연산자의 중첩 깊이는 최대 $10$ 이다.

각 프로그램에 대해 먼저 Program #i 줄을 출력한다. 여기서 $i$ 는 $1$ 부터 시작하는 프로그램 번호이다. 그다음 수행 시간을 $n$ 에 대한 다항식으로 출력한다. 이 다항식의 차수는 최대 $10$ 이다. 다음 형식으로 출력한다:

Runtime = a*n^10+b*n^9+...+i*n^2+j*n+k

동류항을 모은 뒤 차수가 높은 항부터 낮은 항 순서로 나열하고, 각 항을 공백 없이 + 로 이어 붙인다. 계수가 $0$ 인 항은 생략하며, 계수가 $1$ 인 경우 계수를 쓰지 않는다 (1*n^2 가 아니라 n^2, 1*n 이 아니라 n). 차수가 $1$ 인 항은 n^1 이 아니라 n 으로 쓰며, 상수항은 그 값이 $1$ 이더라도 항상 그 값을 그대로 출력한다. 전체 수행 시간이 $0$ 이면 Runtime = 0 을 출력한다.

연속된 두 프로그램의 출력 사이에는 빈 줄을 하나 출력한다.