[Python] Basic #07: 시간복잡도

프로그램의 효율성을 판단하는 기준인 시간복잡도를 다룹니다.

 

같은 결과를 만드는 코드라도 데이터가 많아지면 실행 시간에 큰 차이가 생길 수 있습니다.

시간복잡도를 이해하면 단순히 정답을 만드는 것을 넘어, 입력 크기에 맞는 풀이를 선택할 수 있습니다.

---

1. 시간복잡도란?

시간복잡도는 입력 데이터의 크기가 증가할 때 연산 횟수가 얼마나 증가하는지를 나타냅니다.

실제 실행 시간을 초 단위로 계산하는 것이 아니라, 입력 크기에 따른 연산량의 증가 정도를 표현합니다.

 

입력 크기는 일반적으로 N으로 나타냅니다.

numbers = [1, 2, 3, 4, 5]

 

위 리스트의 길이가 N이라면, 모든 값을 한 번씩 확인하는 코드는 약 N번의 연산을 수행합니다.

for number in numbers:
    print(number)

• 이 코드의 시간복잡도는 O(N)입니다.

---

2. Big-O 표기법

시간복잡도는 주로 Big-O 표기법으로 나타냅니다.

 

Big-O는 입력이 충분히 커졌을 때 연산량이 어떤 형태로 증가하는지 표현합니다.

 

대표적인 시간복잡도는 다음과 같습니다.

시간복잡도	의미	예시
O(1)	입력 크기와 관계없이 일정	인덱스로 리스트 값 조회
O(log N)	탐색 범위를 반복해서 줄임	이분 탐색
O(N)	데이터를 한 번 순회	최댓값 찾기
O(N log N)	효율적인 정렬에서 자주 등장	sort(), sorted()
O(N²)	모든 데이터 쌍을 확인	이중 반복문
O(2ⁿ)	선택에 따라 경우의 수가 두 배씩 증가	부분집합 완전탐색

 

일반적으로 아래로 갈수록 입력 크기가 커졌을 때 실행 시간이 빠르게 증가합니다.

O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(2ⁿ)

---

3. O(1)

입력 크기와 관계없이 연산 횟수가 일정한 경우입니다.

numbers = [10, 20, 30, 40]

print(numbers[0])

• 리스트의 길이가 4이든 1,000,000이든 첫 번째 값에 접근하는 연산 횟수는 크게 달라지지 않습니다.

 

딕셔너리와 집합의 조회도 평균적으로 O(1)입니다.

scores = {"Alice": 90, "Bob": 80}

print(scores["Alice"])

---

4. O(N)

입력 데이터를 한 번 순회하는 경우입니다.

numbers = [3, 8, 2, 7, 5]
maximum = numbers[0]

for number in numbers:
    if (number > maximum):
        maximum = number

print(maximum)

• 데이터가 N개라면 반복문도 약 N번 실행되므로 O(N)입니다.

 

연속된 반복문이 여러 개 있어도 O(N)일 수 있습니다.

for number in numbers:
    print(number)

for number in numbers:
    print(number * 2)

• 전체 연산량은 약 2N이지만 Big-O에서는 증가 형태에 집중하므로 상수 2를 제외하고 O(N)으로 표현합니다.

---

5. O(N²)

중첩 반복문에서 각 반복문이 N번 실행되면 O(N²)이 됩니다.

numbers = [1, 2, 3, 4]

for a in numbers:
    for b in numbers:
        print(a, b)

• 데이터가 N개일 때 가능한 모든 쌍을 확인하므로 약 N × N번 실행됩니다.

 

하지만 중첩 반복문이라고 해서 항상 O(N²)인 것은 아닙니다.

for i in range(N):
    for j in range(10):
        print(i, j)

• 안쪽 반복문은 항상 10번만 실행되므로 전체 연산량은 10N입니다.
• 상수를 제외하면 시간복잡도는 O(N)입니다.

---

6. 리스트와 집합의 차이

특정 값이 존재하는지 확인하는 코드를 비교해보겠습니다.

numbers = [1, 2, 3, 4, 5]

print(5 in numbers)

 

리스트는 앞에서부터 값을 확인할 수 있으므로 존재 여부 확인에 O(N)이 필요합니다.

numbers = {1, 2, 3, 4, 5}

print(5 in numbers)

• 집합은 평균적으로 O(1)에 존재 여부를 확인할 수 있습니다.

 

여러 값을 반복해서 검색해야 한다면 자료구조의 차이가 커집니다.

registered = [101, 102, 103, 104]
queries = [102, 105, 103]

for member_id in queries:
    if member_id in registered:
        print(member_id)

• registered와 queries의 길이가 모두 N이라면 리스트에서는 최대 O(N²)이 필요할 수 있습니다.

 

registered를 집합으로 바꾸면 각 조회가 평균 O(1)이므로 전체 조회는 평균 O(N)이 됩니다.

registered = {101, 102, 103, 104}

for member_id in queries:
    if member_id in registered:
        print(member_id)

---

7. 주요 Python 연산의 시간복잡도

리스트

연산	평균 시간복잡도
list[i]	O(1)
append()	O(1)
pop()	O(1)
insert(0, value)	O(N)
pop(0)	O(N)
value in list	O(N)
sort()	O(N log N)

• 리스트의 앞에 값을 추가하거나 제거하면 나머지 값을 이동해야 하므로 O(N)이 필요합니다.

 

딕셔너리와 집합

연산	평균 시간복잡도
key 또는 값 조회	O(1)
값 추가	O(1)
값 삭제	O(1)
value in set	O(1)

• 딕셔너리와 집합의 연산은 평균적으로 O(1)이지만, 충돌이 많이 발생하는 최악의 경우에는 더 느려질 수 있습니다.

 

deque

연산	시간복잡도
append()	O(1)
appendleft()	O(1)
pop()	O(1)
popleft()	O(1)

• 앞과 뒤에서 값을 자주 추가하거나 제거한다면 리스트보다 deque가 적합합니다.

---

8. 입력 크기로 풀이 예상하기

문제를 풀기 전에 입력 제한을 확인하면 사용할 수 있는 풀이를 예상할 수 있습니다.

정확한 기준은 언어와 문제 환경에 따라 달라지지만, 일반적으로 다음과 같이 생각할 수 있습니다.

입력 크기	고려할 수 있는 시간복잡도
N ≤ 20	O(2ⁿ), 완전탐색
N ≤ 500	O(N³), O(N²)
N ≤ 10,000	O(N²)은 주의
N ≤ 100,000	O(N log N), O(N)
N ≤ 1,000,000	O(N), O(log N)

• 예를 들어 N = 100,000일 때 O(N²) 풀이는 최대 약 100억 번의 연산이 필요합니다.
• 반면 O(N log N) 또는 O(N) 풀이는 훨씬 현실적입니다.

---

9. 공간복잡도

공간복잡도는 프로그램이 사용하는 메모리의 양을 나타냅니다.

N = 100
visited = [False] * N

• 입력 크기 N에 비례하는 리스트를 만들었으므로 추가 공간은 O(N)입니다.

 

total = 0

for number in range(N):
    total += number

• 입력 크기가 커져도 몇 개의 변수만 사용하므로 추가 공간은 O(1)입니다.

 

실행 시간을 줄이기 위해 집합이나 딕셔너리를 추가로 사용하는 경우가 많습니다.

이처럼 시간과 메모리 사이에는 선택이 필요할 수 있습니다.

---

10. 종합 예제

리스트에서 중복된 값을 찾는 두 가지 방법을 비교해보겠습니다.

 

모든 값의 쌍 비교

def has_duplicate(numbers):
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if (numbers[i] == numbers[j]):
                return True

    return False

• 최악의 경우 모든 값의 쌍을 확인하므로 시간복잡도는 O(N²)입니다.

 

집합 활용

def has_duplicate(numbers):
    seen = set()

    for number in numbers:
        if number in seen:
            return True

        seen.add(number)

    return False

• 집합의 조회와 추가는 평균 O(1)이므로 전체 시간복잡도는 평균 O(N)입니다.
• 대신 최대 N개의 값을 집합에 저장하므로 공간복잡도는 O(N)입니다.

---

11. 자주 하는 실수/주의점

• 실제 실행 시간과 시간복잡도는 같은 의미가 아닙니다.
• 반복문이 두 개 있다고 무조건 O(N²)인 것은 아닙니다.
• 중첩 반복문의 각 반복 횟수를 확인해야 합니다.
• Big-O에서는 보통 상수와 영향력이 작은 항을 제외합니다.
• 딕셔너리와 집합 연산의 O(1)은 평균적인 경우입니다.
• 실행 시간을 줄이기 위해 추가 메모리를 사용할 수 있습니다.
• 문제의 입력 제한을 확인하지 않고 풀이 방법부터 정하지 않도록 주의해야 합니다.

---

12. 종합 요약

• 시간복잡도: 입력 크기에 따른 연산량의 증가 정도
• O(1): 입력 크기와 관계없이 일정
• O(N): 전체 데이터를 한 번 순회
• O(N log N): 효율적인 정렬에서 자주 등장
• O(N²): 모든 데이터 쌍을 확인할 때 자주 등장
• 리스트 조회는 위치 접근과 값 검색의 복잡도가 다름
• 집합과 딕셔너리는 평균적으로 빠른 검색이 가능
• 입력 제한을 확인하고 적절한 알고리즘과 자료구조를 선택
• 공간복잡도까지 함께 고려하면 더 효율적인 코드를 작성할 수 있음