부록 : i, j로 이루어진 이중 for문 에서 j < i가 조건일 때 시간복잡도 계산

cin >> n;
for (int i = 0; i < n; ++i)
	for (int j = 0; j < i; ++j)
		int a = 0; // No used

- 이 코드의 시간복잡도는 O(n^2)이다.

- 왜 O(n^2)인가? 궁금해서 이게 어떻게 수식으로 표현되는지 알아봤다.

 

 

- i는 n만큼 반복하고, j는 i-1만큼 반복한다.

- 그렇다면 이 식은 i가 증가함에 따라 매 루프마다 i-1번만큼 반복하는 식이다.

- i가 10이라면 j는 아래의 횟수만큼 반복한다. (행 : i, 열: j)

 

0	1 (j)	2	3	4	5	6	7	8	9
1 (i)
2	V
3	V	V
4	V	V	V
5	V	V	V	V
6	V	V	V	V	V
7	V	V	V	V	V	V
8	V	V	V	V	V	V	V
9	V	V	V	V	V	V	V	V

- j는 i-1만큼만 반복하므로 i가 8일때 j는 7만큼 반복한다.(빨간색)

- 이 코드의 시간복잡도는 두 번째 반복문이 얼만큼 반복되는 횟수로 계산할 수 있다.

- 두 번째 반복문은 매 루프마다 1부터 i - 1까지 실행되므로, 아래와 같은 횟수로 실행된다.

- (0번 + 1번 + 2번 + 3번 + 4번 + 5번 + 6번 + 7번 + 8번) 이 식은 i - 1까지의 합이다. (i는 0~9의 범위를 갖는다)

- 1부터 i-1까지의 자연수의 합은 아래와 같이 구할 수 있다.

S = 1 + 2 + 3 + ... + (n-1)

- 이 합을 역순으로 더하면 다음과 같다.

S = (n-1) + (n-2) + ... + 1

- 두 식을 더하면 아래와 같다.

2S = n + n + n ... + n (n-1개의 항)

- 따라서 2S = n(n-1)이므로, S = n(n-1)/2가 된다.

- 빅오 표기법은 최고차항의 상수항을 제외하고 표기하므로 n^2이 된다.