시간 복잡도 정리

바로가기

시간 복잡도란?

시간 복잡도의 중요성(In Python)

Big-O 종류와 시간 차이

파이썬 코드로 비교하는 시간 차이

헷갈리기 쉬운 O(n)

마무리

시간 복잡도란?

---

  컴퓨터 환경이나 성능에 따라, 또는 프로그래밍 언어에 따라 실행 시간은 제각각입니다. 그렇기에 데이터의 개수(n)가 늘어날 때, 연산의 횟수가 어떤 패턴으로 늘어나는지를 측정하고 어떤 환경에서도 예상을 할 수 있도록 지표를 만들었습니다.

 

 

시간 복잡도의 중요성(In Python)

---

  보통의 환경에서는 체감할 수 없을 정도로 컴퓨터는 빠릅니다. 하지만 실무에서는 100만 개, 1,000만 개... 매우 많은 데이터를 다루기 때문에 n만큼 실행 시간이 늘어나는 게 아닌 n제곱만큼 늘어난다면 현재의 컴퓨터로는 해결할 수 없게 됩니다.

  그렇기에 Big-O(빅 오) 표기법을 사용해 데이터의 양에 따라 연산량이 얼마나 늘었는지, 최악의 상황에 얼마나 걸리게 되는지 예측을 하고 그 예측을 통해 대응을 하거나 문제 해결을 할 수 있게 됩니다.

 

 

 

Big-O 종류와 시간 차이

---

1. 최적의 영역

  아무리 데이터가 많아져도 문제없는 알고리즘입니다.

  (1) O(1) - (Constant Time, 상수 시간)

    데이터가 1개든 100만 개든 연산  시간이 같습니다.

    ex. 리스트의 인덱스로 값 찾기, 해시맵 조회

 

  (2) O(log n) - (Logarithmic Time, 로그 시간)

    데이터가 2배로 늘어나도 연산은 딱 1번 늘어납니다.

    ex. 이진 탐색, 균형 잡힌 이진트리 조회

2. 합리적 영역

이정도면 합리적으로 넘어갈 수 있는 알고리즘입니다.

  (1) O(n) - (Linear Time, 선형 시간)

    데이터 양에 비례해서 시간이 늘어납니다.

    ex. for 문, 리스트 전체 합

 

  (2) O(n log n) - (Linerarithmic Time, 선형 로그 시간)

    효율적인 정렬의 표본으로 O(n)보다는 조금 느리지만 대규모 정렬에서 이보다 잘하기 어렵습니다.

    ex. 파이썬의 sort(), 병합 정렬

3. 위험 영역

  데이터가 많아지면 서비스가 터진다,라고 확신할 수 있는 알고리즘입니다.

  (1) O(n^2) - (Quadratic Time, 이차 시간)

    중첩 루프로 데이터 10배가 늘어날 동안 시간은 100배 늘어납니다.

    ex. 2중 for문, 버블 정렬

 

  (2) O(2^n) - (Exponetial Time, 지수 시간)

    데이터가 조금만 커져도 절대 끝나지 않을 수 있습니다.

    ex. 피보나치수열의 단순 재귀 구현

 

한눈에 알아볼 수 있도록 표로 정리해 보았습니다.

데이터의 수(n)	O(1)	O(lon n)	O(n)
10	1	3.3	10
1,000	1	10	1,000
1,000,000	1	20	1,000,000

 

 

파이썬 코드로 비교하는 시간 차이

---

  실제 코드를 이용해 체감할 수 있도록 해보겠습니다. 단 시간은 환경이나 실행에 따라 차이가 있으니 유의해주세요.

import time

def sum_linear(n):
    # (n): 숫자를 하나씩 더함    
    result = 0
    for i in range(n):
        result += i
    return result

def sum_quadratic(n):
    # O(n^2): 불필요한 중복 루프
    result = 0
    for i in range(n):
        for j in range(n):
            pass # 아무것도 안 해도 루프 횟수 자체가 폭발함
    return result

n = 10000
# O(n) 측정
start = time.time()
sum_linear(n)
print(f"O(n) 걸린 시간: {time.time() - start:.5f}초")

# O(n^2) 측정
start = time.time()
sum_quadratic(n)
print(f"O(n^2) 걸린 시간: {time.time() - start:.5f}초")

  코드를 실행함으로써 둘의 차이는 겨우 1만 개 데이터로도 엄청난 차이가 발생했습니다. 그렇기에 시간 복잡도를 고려해서 코드를 짜는 것이 매우 중요하다는 점을 다시금 알 수 있었습니다.

 

 

 

헷갈리기 쉬운 파이썬의 O(n)

---

헷갈리기 쉬운 파이썬의 O(n)에 대해서 정리해 보겠습니다.

 

1. List와 Set

리스트에서 값을 찾을 때 O(n)이지만 셋(Set)에서는 O(1)입니다.

import time

# 1,000만 개의 데이터 준비
large_list = list(range(10000000))
large_set = set(large_list)
target = 9999999

# 리스트 검색 (O(n) - 선형 탐색)
start = time.time()
print(f"List 검색 결과: {target in large_list}")
print(f"List 검색 시간: {time.time() - start:.5f}초")

# 셋 검색 (O(1) - 상수 시간 / 해시 테이블)
start = time.time()
print(f"Set 검색 결과: {target in large_set}")
print(f"Set 검색 시간: {time.time() - start:.5f}초")

 

2. 리스트의 0번 인덱스 삭제

리스트에서 맨 앞 요소를 삭제하면 뒤의 모든 데이터를 한 칸씩 앞으로 당기는 데, 이때 O(n)만큼 걸립니다. 하지만 deque로 구현하면 데이터 이동 없이 즉시 삭제됩니다.

import time
from collections import deque

# 테스트 설정: 10만 개의 데이터를 가진 객체에서 맨 앞 요소를 1,000번 추출
n = 100000
repeat = 1000

# 1. 리스트 pop(0) 성능 측정
my_list = list(range(n))
start_time = time.time()

for _ in range(repeat):
    my_list.pop(0)  # O(n) 연산이 repeat만큼 반복됨

list_duration = time.time() - start_time
print(f"--- 리스트(List) 결과 ---")
print(f"pop(0) {repeat}회 수행 시간: {list_duration:.5f} 초")

# 2. 데큐(deque) popleft() 성능 측정
my_deque = deque(range(n))
start_time = time.time()

for _ in range(repeat):
    my_deque.popleft()  # O(1) 연산이 repeat만큼 반복됨

deque_duration = time.time() - start_time
print(f"\n--- 데큐(deque) 결과 ---")
print(f"popleft() {repeat}회 수행 시간: {deque_duration:.5f} 초")

 

이런 결과가 나오는 이유?

list.pop(0)을 할 때 메모리에서 일어나는 일

1. 제거 : 0번 인덱스의 주소값을 삭제합니다.

2. 쉬프트(Shift) : 1번 인덱스 주소값을 0번으로, 2번 인덱스 주소값을 1번으로 ... n번 인덱스 주소값을 n-1번으로 모든 주소값을 한 칸씩 앞으로 복사해서 옮깁니다.

=> 시작 주소는 고정이지만 그 안의 주소값이 물리적으로 이동이 일어납니다.

 

deque.popleft()를 할 때 메모리에서 일어나는 일

1. 포인터 변경 : 첫 번째 노드가 가리키는 다음 노드를 새로운 시작 노드로 지정합니다.

2. 연결 끊기 : 기존 첫 번째 노드의 연결을 끊어 버립니다.

=> 헤드 포인터가 가리키는 메모리 주소만 이동합니다.

 

 

마무리

---

  빅데이터 시대에서 시간 복잡도를 고려하는 것은 필수라고 생각합니다. 코드를 완성했더라도 시간 복잡도를 줄일 수는 없는지, 쓸 때 없이 자원을 사용하지 않는지 등 늘 고려하는 개발자가 되어야겠습니다.

 

핵심 요약

1. 시간 복잡도 = 효율성

2. 파이썬의 함정을 조심할 것 (적절한 자료구조, 함수의 선택)

3. 최적화 -> 비용 절감