알고리즘 시간 복잡도(Time Complexity)

 

알고리즘 시간 복잡도(Time Complexity) – 빠르고 정확한 알고리즘의 핵심

코딩 문제를 풀다 보면 꼭 등장하는 용어가 있습니다. 바로 시간 복잡도(Time Complexity)입니다. "이 알고리즘은 O(n²)이니까 느려요", "O(1)이니까 효율적이에요" 같은 표현을 접해본 적 있으실 겁니다. 하지만 이게 정확히 무슨 뜻인지, 왜 중요한지 궁금하셨다면 오늘 이 글을 통해 확실하게 이해할 수 있습니다.

 

---

시간 복잡도란 무엇인가?

시간 복잡도(Time Complexity)는 알고리즘이 문제를 해결하는 데 걸리는 시간의 증가량을 수학적으로 표현한 것입니다. 쉽게 말해, 입력 데이터가 많아질수록 얼마나 시간이 오래 걸리는지를 측정하는 기준입니다.

예를 들어 어떤 알고리즘이 100개의 데이터를 1초 만에 처리한다면, 1,000개는? 10,000개는? 이 증가 패턴을 분석하고 예측할 수 있는 것이 바로 시간 복잡도입니다.

---

왜 시간 복잡도가 중요한가?

단순히 코드가 ‘돌아가기만 하면 된다’고 생각하기 쉽지만, 입력 데이터의 양이 많아질 경우 시간 차이는 매우 커집니다. 예를 들어,

• O(n) 알고리즘: 10만 개 → 약 10만 번 연산
• O(n²) 알고리즘: 10만 개 → 약 100억 번 연산 ❗️

입력의 크기에 따라 수행 시간이 기하급수적으로 증가할 수도 있으므로, 시간 복잡도는 실용적인 알고리즘 선택의 핵심 지표입니다.

---

시간 복잡도 표기법 – Big-O Notation

시간 복잡도는 일반적으로 빅오(Big-O) 표기법으로 표현합니다. 이는 가장 빠르게 증가하는 항만 남긴 간단한 수학 표기입니다.

주요 시간 복잡도 유형

복잡도 설명 예시

O(1)	상수 시간 – 입력 크기와 무관	배열 인덱스 접근
O(log n)	로그 시간 – 절반씩 줄여나가는 방식	이진 탐색
O(n)	선형 시간 – 입력에 비례	단순 반복
O(n log n)	선형 로그 – 정렬 알고리즘	병합정렬, 퀵정렬 평균
O(n²)	이차 시간 – 중첩 반복문	버블 정렬
O(2ⁿ), O(n!)	지수/팩토리얼 시간 – 매우 느림	피보나치 재귀, 순열 생성

---

시간 복잡도 예제 – 쉽게 이해하기

예제 1: O(1)

def get_first_element(arr):
    return arr[0]

• 입력 크기와 상관없이 항상 1번만 연산
• 시간 복잡도: O(1)

예제 2: O(n)

def print_all_elements(arr):
    for element in arr:
        print(element)

• 입력 길이에 따라 실행 횟수 비례
• 시간 복잡도: O(n)

예제 3: O(n²)

def print_pairs(arr):
    for i in arr:
        for j in arr:
            print(i, j)

• 이중 반복문 → 입력 n개일 때 n * n번 실행
• 시간 복잡도: O(n²)

---

시간 복잡도 계산 시 고려할 점

1. 중첩 루프
   반복문이 중첩될수록 시간 복잡도는 급격히 증가합니다.
2. 조건문, 함수 호출
   조건문은 보통 영향이 적고, 함수 호출 시 내부 로직의 복잡도를 따져야 합니다.
3. 재귀 호출
   재귀는 반복문보다 이해하기 어렵지만, 호출 깊이에 따라 시간 복잡도가 결정됩니다.

---

시간 복잡도 분석 요령

시간 복잡도를 빠르게 파악하는 팁:

• 단일 for문 → O(n)
• 이중 for문 → O(n²)
• while문 안에서 n을 반씩 줄이면 → O(log n)
• 재귀에서 두 번씩 호출 → O(2ⁿ)

예를 들어, 아래 함수는?

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

→ 매 반복마다 검색 범위를 절반으로 줄이므로 O(log n)입니다.

---

시간 복잡도 줄이는 방법

1. 효율적인 자료구조 선택
   리스트보다 딕셔너리(dict), 셋(set)을 활용하면 탐색 속도가 빨라집니다.
2. 불필요한 연산 제거
   중복 계산을 피하고, 루프 내 불필요한 작업을 최소화합니다.
3. 정렬 최적화 알고리즘 사용
   퀵정렬, 병합정렬처럼 효율적인 정렬 방법을 사용해 성능 개선
4. 메모이제이션(Memoization)
   중복 호출되는 재귀함수를 캐시 처리해 반복 연산 방지

---

실무와 코딩 테스트에서 시간 복잡도의 중요성

시간 복잡도는 단순히 시험용 개념이 아닙니다. 실제 서비스에서도 수천만 명의 요청을 빠르게 처리해야 하는 상황에서는 알고리즘의 속도가 곧 사용자의 경험이 됩니다.

또한 코딩 테스트에서는 제한 시간 안에 문제를 해결해야 하므로, 효율적인 시간 복잡도 분석과 설계 능력이 중요합니다.

---

 

알고리즘에서 시간 복잡도는 그 성능을 좌우하는 핵심 지표입니다. 코드가 돌아가는 것에 만족하지 않고, 얼마나 효율적으로 작동하는가까지 고민하는 습관이 중요합니다.

특히 대용량 데이터를 다룰수록 시간 복잡도는 체감 차이를 크게 만들며, 실력 있는 개발자로 성장하기 위한 필수 개념입니다. 앞으로 문제를 풀 때 ‘내 코드의 시간 복잡도는 몇일까?’를 먼저 생각해 보세요.

 

 

 

 

쇼어 알고리즘의 원리 – 양자컴퓨터가 RSA를 깨는 방식