Time Complexity Calculation (시간 복잡도 계산)

1️⃣ 기본적인 시간 복잡도 계산 방법 (반복문 중심)

 

✅ 시간 복잡도를 계산하는 일반적인 방법론

시간 복잡도(Time Complexity)는 알고리즘이 실행되는 데 걸리는 시간을 입력 크기(n)에 대한 함수로 나타낸 것입니다.
시간 복잡도를 분석하는 방법은 크게 두 가지로 나눌 수 있습니다.

1. 기본적인 반복문을 포함한 경우 (반복문 분석)
2. 재귀 함수가 포함된 경우 (재귀 분석)

① 단일 루프 → O(n)

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

 

 

• i는 0부터 n-1까지 증가 → n번 반복
• 시간 복잡도: O(n)

 

 

② 중첩 루프 (이중 루프) → O(n²)

for i in range(n):  
    for j in range(n):  
        print(i, j)

 

• i가 n번 실행될 때마다 j도 n번 반복
• 전체 반복 횟수: n * n = n²
• 시간 복잡도: O(n²)

③ 중첩 루프 (삼중 루프) → O(n³)

for i in range(n):  
    for j in range(n):  
        for k in range(n):  
            print(i, j, k)

 

• n * n * n = n³번 실행
• 시간 복잡도: O(n³)

 

 

④ 로그 증가 (이진 검색 패턴) → O(log n)

i = 1
while i < n:
    i *= 2

 

• i가 1, 2, 4, 8, ...처럼 2배씩 증가
• i가 n 이상이 되는 순간 루프 종료
• i = 2^k라고 하면 2^k = n → k = log₂(n)
• 시간 복잡도: O(log n)

---

 

2️⃣ 재귀 함수의 시간 복잡도 계산 방법

재귀 함수의 시간 복잡도는 재귀 관계식을 세우고 이를 풀어서 구합니다.
이 방법론을 마스터 방법 (Master Theorem) 이라고 합니다.

 

① 선형 재귀 (O(n))

def recursive1(n):
    if n == 0:
        return
    recursive1(n - 1)

• n에서 0까지 1씩 감소
• 재귀 호출 횟수 = n
• 시간 복잡도: O(n)

② 이진 분할 재귀 (O(log n))

def recursive2(n):
    if n <= 1:
        return
    recursive2(n // 2)

 

• n을 2로 나누면서 재귀 호출
• 호출 횟수는 log₂(n)
• 시간 복잡도: O(log n)

 

③ 이진 트리 형태의 재귀 (O(n))

def recursive3(n):
    if n <= 1:
        return
    recursive3(n // 2)
    recursive3(n // 2)

• 두 개의 하위 문제를 n/2 크기로 계속 나눔
• 재귀 관계식: T(n) = 2T(n/2) + O(1)
• 풀면 O(n)

④ 피보나치 같은 지수적 증가 재귀 (O(2ⁿ))

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

 

• 피보나치 수열처럼 T(n) = T(n-1) + T(n-2)
• 매 단계에서 2개의 하위 문제를 생성 → O(2ⁿ)
• 지수 시간 복잡도(매우 비효율적!)

 

---

1. O(n)

def func1(n):
    for i in range(n):
        print(i)

# 시간 복잡도: O(n)
# 설명: 단순한 for 루프가 n번 실행됨.

 

 

2. O(n²)

def func2(n):
    for i in range(n):
        for j in range(n):
            print(i, j)

# 시간 복잡도: O(n²)
# 설명: 이중 for 루프가 각각 n번 실행되므로 전체적으로 n * n = O(n²).

 

3. O(log n)

def func3(n):
    i = 1
    while i < n:
        print(i)
        i *= 2

# 시간 복잡도: O(log n)
# 설명: i가 2배씩 증가하며 n에 도달하므로 log₂(n)번 실행됨.

 

4. O(n)

def func4(n):
    if n == 0:
        return
    func4(n // 2)
    func4(n // 2)

# 시간 복잡도: O(n)
# 설명: 분할 정복이지만, 전체적으로 n번 호출되므로 O(n).

5. O(n)

def func5(arr):
    for i in arr:
        print(i)

# 시간 복잡도: O(n)
# 설명: 리스트의 길이만큼 반복하므로 O(n).

6. O(n²)

def func6(n):
    for i in range(n):
        for j in range(i):
            print(i, j)

# 시간 복잡도: O(n²)
# 설명: 루프가 삼각수(1+2+...+n-1) 형태로 실행되어 O(n²).

 

7. O(n)

def func7(n):
    for i in range(n):
        for j in range(100):
            print(i, j)

# 시간 복잡도: O(n)
# 설명: 내부 루프는 100번 고정 실행되므로 상수 O(1), 따라서 O(n).

8. O(n log n)

def func8(n):
    for i in range(n):
        func3(i)  # func3(i)는 O(log i)

# 시간 복잡도: O(n log n)
# 설명: O(log i)가 n번 반복되므로 O(n log n).

 

9. O(2ⁿ)

def func9(n):
    if n <= 1:
        return
    func9(n - 1)
    func9(n - 1)

# 시간 복잡도: O(2ⁿ)
# 설명: 매 단계마다 2개의 재귀 호출이 발생하므로 지수적 증가.

 

10. O(n³)

def func10(n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                print(i, j, k)

# 시간 복잡도: O(n³)
# 설명: 삼중 루프이므로 O(n³).