시간 복잡도 계산 완벽 가이드 (코딩테스트, 알고리즘 문제 시간복잡도 계산법, 계산 팁)

 

코딩테스트를 준비하거나 문제를 풀 때, 알고리즘의 시간 복잡도를 이해하고 계산하는 건 정말 중요합니다. 오늘은 시간 복잡도가 뭔지, 어떻게 계산하는지, 실제 예제 문제와 계산 팁까지 모두 정리해보겠습니다. 이걸 잘 익히면 문제를 푸는 데 훨씬 큰 도움이 될 것입니다.

---

1. 시간 복잡도란?

시간 복잡도(Time Complexity)는 알고리즘이 실행되는 데 필요한 시간의 증가율을 나타내는 지표입니다. 입력 크기(n)가 커질수록 알고리즘이 얼마나 효율적으로 동작하는지를 보여줍니다. 쉽게 말해, 입력 크기가 커질 때 실행 시간이 얼마나 늘어나는지를 파악하는 겁니다.

 

반응형

2. 대표적인 시간 복잡도 표기법

시간 복잡도는 보통 빅오 표기법(Big-O Notation)으로 표현합니다. 아래 표에 주요 시간 복잡도와 그 특징들을 정리했습니다:

표기법	설명	예시
O(1)	상수 시간 (입력 크기에 무관)	배열의 특정 인덱스 접근
O(log n)	로그 시간 (반씩 줄어듦)	이진 탐색
O(n)	선형 시간	단일 for문
O(n log n)	선형 로그 시간	합병 정렬, 퀵 정렬 (평균)
O(n^2)	이차 시간	중첩된 이중 for문
O(2^n)	지수 시간	피보나치 수 재귀 풀이
O(n!)	팩토리얼 시간	순열 생성

---

 

3. 시간 복잡도 계산법

시간 복잡도를 계산은 아래 순서로 진행하면 좋습니다:

1. 가장 중첩된 루프부터 분석:
   • 예를 들어, 이중 for문은 O(n^2)가 됩니다.
2. 주요 연산 확인:
   • 조건문, 배열 접근, 함수 호출 등 실행에 걸리는 시간을 체크하세요.
3. 상수 항 제거:
   • O(2n + 3)은 O(n)으로 단순화합니다. 중요한 건 증가율이니까요.
4. 가장 높은 차수만 남김:
   • O(n^2 + n)은 O(n^2)로 표기합니다.

---

 

4. 시간 복잡도 계산 문제

아래 문제들을 통해 직접 시간 복잡도를 계산해보며 개념을 익히겠습니다.

문제 1: 단일 for문

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

• 해설: for문이 n번 반복되므로 O(n)

 

문제 2: 중첩 루프

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

• 해설: 이중 for문이므로 O(n^2)

 

문제 3: 이진 탐색

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

• 해설: 탐색 범위가 반씩 줄어드므로 O(log n)

 

문제 4: 병합 정렬

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

• 해설: 각 단계에서 merge시 O(n), 재귀 함수를 통해 merge_sort가 호출되는 횟수가 O(log n) -> O(n log n)

 

문제 5: 순열 생성

def permutations(arr):
    if len(arr) == 0:
        return [[]]
    result = []
    for i in range(len(arr)):
        for p in permutations(arr[:i] + arr[i+1:]):
            result.append([arr[i]] + p)
    return result

• 해설: 순열의 수는 n!이므로 O(n!)

---

 

5. 시간 복잡도 계산 팁

1. 루프를 먼저 분석하자:
   • 모든 for문과 while문이 몇 번 반복되는지 따져보세요.
2. 재귀 호출 단계 확인:
   • 재귀 함수는 호출 횟수와 각 호출에서의 작업을 계산해야 합니다.
3. 조건문도 신경 쓰자:
   • 특정 조건에서만 실행되는 코드라도 최악의 경우를 고려하세요.
4. 정렬 알고리즘 기본은 O(n log n):
   • 대부분의 정렬 문제는 이 복잡도를 가집니다.
5. 문제 유형별 암기:
   • 이진 탐색: O(log n)
   • 순열 생성: O(n!)
   • 단일 for문: O(n)