[시간 복잡도를 이해하는 법] 효율적인 알고리즘을 위한 첫걸음

백준이나 프로그래밍 문제 푸는 사이트에서 코딩테스트를 준비하다보면 시간복잡도? 라는 것을 들을 수 있습니다

저는 비전공자라 정보처리기사를 공부하면서 너무 복잡하기 때문에 찾아보며 정리할 수 밖에 없죠 그래서 한번 정리를 해보겠습니다!

---

1. 시간 복잡도란?

1) 정의

시간 복잡도는 알고리즘이 입력 크기(n)에 따라 실행되는 연산 횟수를 수학적으로 표현한 것입니다.

2) 주요 개념

• 입력 크기(n): 문제를 해결하기 위해 처리해야 할 데이터의 양.

• 실행 시간: 알고리즘이 완료되는 데 걸리는 시간(보통 연산 횟수로 측정).

3) 시간 복잡도의 중요성

• 입력 데이터가 증가할수록 알고리즘의 성능이 어떻게 변화하는지 파악.

• 더 효율적인 알고리즘 설계를 가능하게 함.

2. 시간 복잡도의 표기법

시간 복잡도는 주로 **빅오 표기법(Big-O Notation)**으로 표현합니다. 이는 최악의 경우를 기준으로 알고리즘의 성능을 나타냅니다.

1) 빅오 표기법

• 알고리즘의 실행 시간이 입력 크기(n)에 따라 얼마나 빨리 증가하는지 나타냅니다.

• 높은 차수의 항만 고려하며, 상수는 생략합니다.

예: T(n) = 3n² + 2n + 1 → O(n²)

2) 시간 복잡도 유형

시간복잡도	설명	예시
O(1)	상수 시간 (입력 크기에 무관)	배열에서 특정 위치 데이터 접근
O(log n)	로그 시간	이진 탐색
O(n)	선형 시간	배열에서 최대값 찾기
O(n log n)	선형 로그 시간	병합 정렬, 퀵 정렬
O(n²)	제곱 시간	버블 정렬, 선택 정렬
O(2ⁿ)	지수 시간	피보나치 수 재귀 구현

3. 시간 복잡도 계산 방법

1) 기본 연산

• 루프, 조건문, 재귀 등 주요 연산을 분석하여 전체 실행 시간을 계산.

2) 반복문

• 단일 루프: O(n)

for i in range(n):  # n번 반복
    print(i)  # O(1)

• 중첩 루프: O(n²)

for i in range(n):
    for j in range(n):  # 내부 루프 n번 반복
        print(i, j)  # O(1)

3) 조건문

• 조건문 자체는 O(1), 하지만 각 분기에서 실행되는 연산의 시간 복잡도를 고려.

if x > 0:
    print("Positive")  # O(1)
else:
    for i in range(n):  # O(n)
        print(i)

4) 재귀 함수

• 재귀 함수는 재귀 관계식으로 표현.

• 예: 피보나치 수 계산의 시간 복잡도는 O(2ⁿ).

def fib(n):
    if n <= 1:
        return n  # O(1)
    return fib(n-1) + fib(n-2)

4. 시간 복잡도의 시각적 비교

입력 크기(n)가 증가할수록 시간 복잡도에 따른 실행 시간 변화:

시간 복잡도	10	100	1,000	10,000
O(1)	1	1	1	1
O(log n)	4	7	10	14
O(n)	10	100	1,000	10,000
O(n log n)	40	700	10,000	140,000
O(n²)	100	10,000	1,000,000	100,000,000

5. 실전에서 시간 복잡도 이해하기

1) 배열 검색

• 배열에서 특정 요소를 찾는 시간 복잡도:

• 정렬되지 않은 배열: O(n) (선형 탐색).

• 정렬된 배열: O(log n) (이진 탐색).

2) 정렬 알고리즘

• 버블 정렬: O(n²).

• 병합 정렬: O(n log n).

3) 그래프 탐색

• 너비 우선 탐색(BFS): O(V + E), V: 노드 수, E: 엣지 수.

• 깊이 우선 탐색(DFS): O(V + E).

4) 해시 테이블

• 데이터 검색: O(1) (평균), O(n) (최악).

6. 시간 복잡도 최적화를 위한 팁

• 데이터 구조 선택: 문제에 맞는 데이터 구조를 선택하여 시간 복잡도를 줄일 수 있습니다

• 예: 해시 테이블을 사용하면 선형 탐색을 상수 시간 탐색으로 변환.

• 불필요한 반복 제거: 중첩 루프를 최소화하거나 더 효율적인 알고리즘으로 대체.

• 예: 브루트포스 대신 이진 탐색.

• 알고리즘 변경: 더 효율적인 알고리즘으로 문제 해결.

• 예: 버블 정렬 대신 병합 정렬 사용.

시간 복잡도는 알고리즘의 성능을 분석하는 데 중요한 도구입니다. 문제를 해결하는 데 드는 시간을 예측하고, 더 효율적인 알고리즘을 설계하는 데 큰 도움이 됩니다. 항상 문제를 해결할 때 시간 복잡도를 고려하여 최적화된 해결책을 찾아가는 것이 중요합니다.

이 포스트에서 다룬 시간 복잡도와 관련된 개념들을 이해하면 코딩테스트나 실제 개발에서 발생할 수 있는 성능 문제를 미리 예방할 수 있습니다. 알고리즘의 효율성을 개선하려는 노력은 프로젝트의 성공과 직결되기 때문입니다!