2. Time complexity

시간복잡도의 엄밀한 수학적 정의는 나도 사실 정확하게 모른다.

 

하지만 알고리즘에서 시간복잡도를 분석하는 것은 매우 중요하다.

 

합의 합 문제를 통해 시간복잡도를 체감해보자.

 

문제에서 주어진 식을 의미 그대로 구한다면 코드를 다음과 같이 구현할 수 있다.

#include <stdio.h>
typedef long long ll;
int main() {
	int T; scanf("%d", &T);
	while (T--) {
		int N; scanf("%d", &N);
		ll ans = 0;
		for (int k = 1; k <= N; k++) {
			for (int i = 1; i <= k; i++) ans += i;
		}
		printf("%lld\n", ans);
	}
	return 0;
}

이대로 제출을 하면 아쉽게도 시간초과가 난다.

ans += i;

각 테스트 케이스마다 이 문장은 총 몇 번 실행이 될까?

\(N\)의 크기에 따라 다를 것 같다.

 

계산을 해보면 \(\displaystyle\frac{N(N+1)}{2}\) 번 실행이 됨을 알 수 있다.

 

우리는 이 알고리즘의 시간복잡도를 \(O(N^2)\) 이런 식으로 나타낸다.

 

이를 \(T\) 번 반복해야 하므로 전체 시간복잡도는 \(O(TN^2)\)이다.

 

이 문제에서 \(T\) 는 최대 \(10\,000\) 이고 \(N\)은 최대 \(1\,000\,000\) 이다.

 

어림잡아서 최대 \(10^{16}\) 번의 연산이 수행 될 것 같다.

 

보통 \(1\) 초에 \(10^8\) 번의 연산을 할 수 있다고 생각하고 문제를 풀면 편하다.

 

이 문제를 시간 안에 해결하려면 어떻게 해야 할까? 식 정리를 잘 하면 다음과 같은 결과를 얻을 수 있다.

 

\(\displaystyle\sum_{k=1}^N \sum_{i=1}^k i=\frac{N(N+1)(N+2)}{6}\)

 

따라서 이 문제는 \(O(T)\) 시간에 해결할 수 있다!

 

이제 시간복잡도를 더 체험해보도록 하자.

 

문제	난이도	태그
구간 합 구하기 4	Silver III	누적 합
수 정렬하기 3	Bronze I	정렬
귀찮아 (SIB)	Silver V	수학