[Algorithm 이론#1] 시간 복잡도 계산법 (상수항, 2중, 3중 for문)

알고리즘 문제 풀이에서 시간 복잡도를 계산하는 가장 기본적이고 확실한 방법은

"반복문이 총 몇번 실행되는가?"를 세는 것입니다. 

 

중첩된 for문은 깊어질수록 연산량이 기하급수적으로 폭발하므로, 

정확한 계산법을 알아야 시간 초과를 피할 수 있습니다. 

 

---

1. 반복문이 없거나 횟수가 고정된 경우: 상수 시간 O(1)

# N이 10만이든 100억이든 무조건 10번만 실행됨
for i in range(10):
    print(i)

• 계산법 : 10번
• 시간 복잡도 : O(1) (상수 시간)

---

2. 1중 for문: 선형 시간 O(N)

for i in range(N):
    print(i)

• 계산법 : n번
• 시간 복잡도 : O(N) 

---

3. 2중 for문 : 직사각형 면적 구하기 O(N^2)

2중 for문은 바깥쪽 루프가 1번 돌 때마다 안쪽 루프가 처음부터 끝까지 다시 도는 구조입니다. 

가로와 세로의 길이를 곱해 직사각형의 넓이를 구하는 것과 완전히 똑같습니다. 

# N이 1,000이라고 가정
for i in range(N) :			# 바깥 루프    : N번 실행
   for j in range(N) :		# 안쪽 루프    : 바깥 루프 1번당 N번 실행
    	print(i, j) 		# 총 실행 횟수 : N * N 번

• 계산법 : N * N = N^2
• 시간 복잡도 : O(N^2) (이차 시간)
• 파이썬 실전 한계 : N이 대략 2,000~5,000 이하일 때만 1초 안에 통과할 수 있습니다. N이 10,000을 넘어가면 1억 번의 연산을 초과하므로 파이썬에서는 위험합니다.

---

4. 3중 for문 : 정육면체 부피 구하기 O(N^3)

루프가 하나 더 깊어지면, 이제는 3차원 정육면체의 부피를 구하는 것과 같습니다. 

for i in range(N) :			# 1단계 : N번
   for j in range(N) : 	# 2단계 : N번
    	for k in range(N) : # 3단계 : N번
        	print(i, j, k)	# 총 실행 횟수 : N * N * N 번

• 계산법 : N * N * N = N^3
• 시간 복잡도 : O(N^3) (삼차 시간)
• 파이썬 실전 한계 : N이 커질 때 연산량이 폭발적으로 늘어납니다. N이 대략 300~500 이하로 주어지는 아주 작은 규모의 문제에서만 사용 가능합니다. 

---

5. 내부 루프의 범위가 변할 때

1. 2중 for문에서 내부 루프 범위가 변할 때

# 안쪽 루프의 시작점이 i와 연관된 경우 (조합이나 쌍을 구할 때 자주 사용)
for i in range(1, n-1)
    for j in range(i+1, n)
        sum = sum + a[i] × a[j]

 

이 코드는 과연 몇 번 돌까요?

• i = 1 일 때 : 안쪽 루프는 N - 1 번 실행
• i = 2 일 때 : 안쪽 루프는 N - 2 번 실행
• i = 3 일 때 : 안쪽 루프는 N - 3 번 실행
• ...
• i = n - 1 일때 : 안쪽 루프는 n부터 n까지 1번 실행

총 실행 횟수를 더해보면 (N-1) + (N-2) + ... + 1이 됩니다. 

이는 1부터 N-1까지의 합을 구하는 등차수열의 공식이자, 수학에서 n개 중 2개를 고르는 조합의 수와 같습니다.
공식으로 풀면 n(n-1)/2가 됩니다. (처음 수)+(마지막수) * (전체수량 / 2)

 

전개해보면

$$\frac{1}{2}n^2 - \frac{1}{2}n$$

이 됩니다. 

빅오 표기법에서는 가장 높은 차수만 남기고 상수와 낮은 차수는 버린다는 절대 규칙이 있으므로, 

이 경우 역시 결국 O(N^2)으로 취급합니다.

 

2. 3중 for문에서 내부 루프 범위가 변할 때

마찬가지로 안쪽으로 들어갈수록 범위가 좁아지는 3중첩 구조입니다. 서로 다른 3개의 원소를 뽑아 쌍을 만들 때 사용합니다.

for i in range(1, n - 2)
    for j in range(i + 1, n - 1)
        for k in range(j + 1, n)

 

이 코드 역시 바깥쪽 루프 변수에 안쪽 루프의 시작점이 종속되어 있습니다. 

실행 횟수를 계산해 보면, 수학에서 n개 중 3개를 고르는 조합의 수와 완벽하게 일치합니다. 

 

이 조건은 i < j < k 라는 규칙이 절때 깨지지 않습니다. 즉, 세 숫자가 모두 달라야 하고, 뒤로 갈수록 무조건 커야 합니다.

 

예로 1부터 10까지 숫자가 적힌 공이 주머니에 들어있다고 상상해 보면, 여기서 아무 공이나 3개를 동시에 꺼냅니다.

• 내가 뽑은 공이 { 7, 2, 5 }라고 칩시다. 
• 이 3개의 숫자를 가지고 i < j < k 조건을 만족하게 배치할 수 있는 방법은?
• 무조건 i = 2, j = 5, k = 7 딱 한 가지 경우뿐입니다. 

즉, 주머니에서 숫자 3개를 뽑기만 하면(조합), 그 숫자들이 for문의 i, j, k가 되어 '코드 1회 실행'으로 직행하게 됩니다. 

• 조합으로 1세트 뽑기 = for문 안쪽 코드가 딱 1번 실행됨

그래서 해당 조건을 공식으로 전개 하면

 

1. 일단 순서대로 나열하기 (n * (n-1) * (n-2))

• 첫 번째 숫자(i)로 뽑을 수 있는 후보 : n개
• 두 번째 숫자(j)로 뽑을 수 있는 후보 : n-1개 
• 세 번째 숫자(k)로 뽑을 수 있는 후보 : n-2개

2. 중복된 세트 제거하기 ( / 6 )

• 하지만 우리는 { 1, 2, 3 } 을 뽑으나 { 3, 2, 1 }을 뽑으나 똑같은 한 번의 실행으로 쳐야 합니다.
• 숫자 3개를 순서만 바궈서 나열하는 방법은 3 * 2 * 1 = 6가지입니다. 

따라서 다항식은 

$$\frac{n(n-1)(n-2)}{6}$$

가 되며, 이를 전개하면.

$$\frac{n^3-3n^2+2n}{6}$$

이 됩니다. 

이 경우 O(N^3)으로 취급합니다.

 

---

6. 3중 for문 내부의 혼합 및 독립 패턴

변수가 N 하나만 있는 것이 아니라, 입력값이 여러 개(N, M, K) 주어졌을 때의 패턴입니다.

1. 2개는 엮여있고, 1개는 독립적일 때

두 개의 루프는 서로 범위가 종속되어 O(N^2)을 형성하고, 나머지 하나는 완전히 다른 변수 M만큼 고정 반복하는 경우입니다. 

for i in range(N):
    for j in range(i, N): # i와 종속됨 (N^2 패턴)
        for k in range(M): # 완전히 독립적인 변수 M
            pass

 

• 총 연산 횟수 : N(N+1)/2 * M 
• 시간 복잡도 : O(N^2 * M)

 

2. 3개의 루프가 각각 완전히 독립적일 때

모든 루프의 범위가 각기 다른 변수로 지정된 경우입니다. 

for i in range(N):
    for j in range(M):
        for k in range(K):
            pass

• 시간 복잡도 : 셋 중 어느 변수가 가장 클지 모르므로 퉁치치 않고 모두 명시하여 O(N * M * K) 가 됩니다. 

 

---

7. 값이 띄엄띄엄 반복될 때

반복문이 1씩 증가하지 않고 일정한 간격으로 뛰거나, 배수로 커지는 패턴입니다. 

여기서 시간 복잡도가 극적으로 갈립니다. 

 

1. 덧셈/ 뺄셈으로 건너뛸 때 : 여전히 O(N)

for i in range(0, N, 2): # 2씩 건너뛰기
    pass

 

• 총 연산 횟수 : N/2
• 시간 복잡도 : 연산량이 반으로 줄었지만 차수는 1차식이므로 상수항을 버려 O(N)입니다. 

2. 곱셉/나눗셈으로 건너뛸 때 : O(log N) 

i = 1
while i < N:
    i *= 2 # 1, 2, 4, 8, 16... 배수로 뜀

 

값이 2배씩 커지거나 절반씩 줄어들면, 목표치 N에 도달하는 속도가 기하급수적으로 빨라집니다. 

• 총 연산 횟수 : log2 N번
• 시간 복잡도 : O(log N)