시간복잡도 계산해보기!

 

민철이가 짠 네 개의 소스코드를 읽어보고, 시간복잡도를 기준으로 채점 해 주세요.

빠른 알고리즘일수록 점수가 높습니다.

문제 번호를 입력하면, 그 문제의 점수를 출력 해 주세요.

 

O(N^3) = 1 점

O(N^2) = 2 점

O(N log N) = 10 점

O(N) = 11점

O(log N) = 20점

O(1) = 21점

1번 소스코드

#include <iostream>
using namespace std;

int main()
{
	for (int i = 0; i < 10000; i++) {
		cout << "#";
	}

	return 0;
}

 

2번 소스코드

#include <iostream>
using namespace std;

int main()
{
	int n;
	cin >> n;

	for (int y = 0; y < n; y++) {
		for (int x = 0; x <= y; x++) {
			cout << "#";
		}
	}

	return 0;
}

 

 

 

3번 소스코드

#include <iostream>
using namespace std;

int n;

void abc()
{
	for (int i = 0; i < n; i++) {
		cout << "#";
	}
}

int main()
{
	cin >> n;

	for (int y = 0; y < n; y++) {
		abc();
		abc();
		abc();
	}

	return 0;
}

4번 소스코드

#include <iostream>
using namespace std;

int main()
{
	cin >> n;

	for (int y = 0; y < n; y++) {

		for (int x = 0; x < 5; x++) {

			for (int z = 0; z < n; z++) {
				cout << "#";
			}
		}
	}

	return 0;
}

입력 예제

1

출력 결과

21

 

 

답은 

21 

2

2

2

나머지는 다 n^2 속도임

첫번째 문제는 1의 속도