[과제 6] 시간 복잡도 (Time Complexity) 와 공간 복잡도 (Space Complexity)

프로그램은 단순히 실행만 된다고 좋은 프로그램이 안디ㅏ.

같은 결과를 만들더라도 얼마나 빠르게 실행되는지, 메모리를 얼마나 효율적으로 사용하는지가 중요하다.

시간 복잡도는 실행 시간의 증가 흐름을 설명하고, 공간 복잡도는 메모리 사용량의 증가 흐름을 설명한다.

1. 시간 복잡도란?

시간 복잡도(Time Complexity) 는 입력 데이터의 크기가 커질 때, 알고리즘의 실행 시간이 얼마나 증가하는지를 나타내는 개념이다.

여기서 중요한 것은 실제 실행 시간이 몇 초인지가 아니다.

입력 크기 n이 커질수록 연산 횟수가 어떤 방식으로 증가하는지를 본다.

시간 복잡도를 계산하는 이유

• 데이터가 많아졌을 때 성능을 예측할 수 있다.
• 여러 코드 중 더 효율적인 코드를 선택할 수 있다.
• 알고리즘 문제를 풀 때 시간 초과를 피할 수 있다.
• 실무에서 대용량 데이터를 처리할 때 중요하다.

2. 공간 복잡도란?

공간 복잡도(Space Complexity) 는 입력 데이터의 크기가 커질 때, 알고리즘이 사용하는 메모리 양이 얼마나 증가하는지를 나타내는 개념이다.

예를 들어 리스트를 하나 더 만들면 추가 메모리를 사용한다.

3. 빅오 표기법이란?

빅오 표기법(Big-O Notation) 은 알고리즘의 성능을 입력 크기 n 에 따라 표현하는 방법이다.

정확한 실행 시간을 계산하는 것이 아니라, 입력 크기가 커질 때 성능이 어떻게 증가하는지 큰 흐름을 나타낸다.

O(1)				입력 크기와 관계없이 일정
O(log n) 	  입력 크기가 커져도 조금씩 증가
O(n) 				입력 크기에 비례해서 증가
O(nlog n) 	O(n)보다 느리지만 O(n²)보다 빠른 경우가 많음
O(n²)				입력 크기의 제곱만큼 증가

빅오 표기법에서는 보통 가장 영향이 큰 항만 남긴다.

3n + 10       ➡ O(n)
n² + n + 1    ➡ O(n²)
5             ➡ O(1)

상수나 작은 항은 입력이 매우 커졌을 때 영향이 상대적으로 작기 때문에 생략한다.

4. 시간 복잡도 종류와 예제

4.1 O(1) : 상수 시간

O(1) 은 입력 크기와 관계없이 실행 시간이 일정한 경우이다.

리스트에서 인덱스로 값을 조회하는 코드는 대표적인 O(1) 예시이다.

numbers = [10, 20, 30, 40, 50]

print(numbers[0])

리스트의 길이와 상관없이, 특정 인덱스에 바로 접근할 수 있다.

따라서 시간 복잡도는 O(1) 이다.

4.2 O(log n) : 로그 시간

O(log n) 은 입력 크기가 커져도 실행 시간이 천천히 증가하는 경우이다,

대표적인 예시는 이진 탐색(Binary Search) 이다.

이진 탐색은 정렬된 데이터에서 가운데 값을 기준으로 탐색 범위를 절반씩 줄인다.

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

numbers = [1, 3, 5, 7, 9, 11, 13, 15]

print(binary_search(numbers, 11)) # 5

탐색 과정:

전체 데이터 8개
1번 비교 후 4개로 줄어듦
2번 비교 후 2개로 줄어듦
3번 비교 후 1개로 줄어듦

데이터를 절반씩 줄이므로 시간 복잡도는 O(log n) 이다.

4.3 O(n): 선형 시간

O(n)은 입력 크기에 비례해서 실행 시간이 증가하는 경우이다.

리스트의 모든 값을 한 번씩 출력하는 코드는 O(n)이다.

numbers = [10, 20, 30, 40, 50]

for number in numbers:
    print(number)

출력 결과:

10
20
30
40
50

데이터가 5개면 5번 반복하고, 100개면 100번 반복한다.

입력 크기 n만큼 반복

따라서 시간 복잡도는 O(n)이다.

---

4.4 O(n log n)

O(n log n)은 정렬 알고리즘에서 자주 등장하는 시간 복잡도이다.

파이썬의 sort()와 sorted()는 평균적으로 O(n log n) 시간 복잡도를 가진다.

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

numbers.sort()

print(numbers)

출력 결과:

[1, 2, 3, 5, 8]

정렬은 단순히 한 번 순회하는 것보다 복잡하다.
하지만 모든 쌍을 비교하는 O(n²) 방식보다 훨씬 효율적이다.

O(n)       전체를 한 번 확인
O(n log n) 효율적인 정렬
O(n²)      모든 쌍을 비교

---

4.5 O(n²): 제곱 시간

O(n²)은 입력 크기의 제곱만큼 실행 시간이 증가하는 경우이다.

대표적인 예시는 이중 반복문이다.

numbers = [1, 2, 3, 4]

for i in numbers:
    for j in numbers:
        print(i, j)

데이터가 4개이면 4 * 4 = 16번 실행된다.
데이터가 n개이면 n * n번 실행되므로 시간 복잡도는 O(n²)이다.

입력 크기가 커질수록 매우 빠르게 느려진다.

---

5. 반복문 개수에 따른 시간 복잡도

반복문은 시간 복잡도를 판단할 때 가장 먼저 확인해야 하는 구조이다.

5.1 반복문이 없는 경우

print("Hello")

입력 크기와 관계없이 한 번 실행되므로 O(1)이다.

5.2 반복문 하나

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

for number in numbers:
    print(number)

리스트 길이만큼 반복하므로 O(n)이다.

5.3 이중 반복문

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

for i in numbers:
    for j in numbers:
        print(i, j)

바깥 반복문이 n번, 안쪽 반복문도 n번 실행된다.

n * n = n²

따라서 O(n²)이다.

5.4 반복문이 나란히 두 개 있는 경우

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

for number in numbers:
    print(number)

for number in numbers:
    print(number * 2)

첫 번째 반복문이 n번, 두 번째 반복문도 n번 실행된다.

n + n = 2n

빅오에서는 상수를 생략하므로 O(n)이다.

5.5 입력을 절반씩 줄이는 반복문

n = 16

while n > 1:
    print(n)
    n = n // 2

출력 결과:

16
8
4
2

값이 매번 절반으로 줄어든다.
이런 구조는 O(log n)이다.

---

6. 리스트에서 자주 사용하는 함수들의 시간 복잡도

파이썬 리스트는 배열처럼 인덱스를 이용해 빠르게 접근할 수 있다.
하지만 중간에 데이터를 삽입하거나 삭제하면 뒤쪽 요소들을 이동시켜야 하므로 비용이 커질 수 있다.

함수	평균 시간 복잡도	설명
append(value)	O(1)	리스트 끝에 값을 추가한다
insert(index, value)	O(n)	중간에 값을 넣으면 뒤 요소들을 밀어야 한다
pop()	O(1)	마지막 값을 제거한다
pop(index)	O(n)	중간 값을 제거하면 뒤 요소들을 당겨야 한다
remove(value)	O(n)	값을 찾기 위해 순차 탐색 후 삭제한다
sort()	O(n log n)	리스트를 정렬한다

6.1 append()

numbers = [1, 2, 3]

numbers.append(4)

print(numbers)

출력 결과:

[1, 2, 3, 4]

리스트 끝에 값을 추가하므로 평균적으로 O(1)이다.

6.2 insert()

numbers = [1, 2, 3, 4]

numbers.insert(1, 99)

print(numbers)

출력 결과:

[1, 99, 2, 3, 4]

인덱스 1에 99를 넣기 위해 기존의 2, 3, 4를 뒤로 밀어야 한다.
따라서 시간 복잡도는 O(n)이다.

6.3 pop()

numbers = [1, 2, 3, 4]

last = numbers.pop()

print(last)
print(numbers)

출력 결과:

4
[1, 2, 3]

마지막 요소를 제거하는 pop()은 평균적으로 O(1)이다.

6.4 pop(index)

numbers = [1, 2, 3, 4]

value = numbers.pop(1)

print(value)
print(numbers)

출력 결과:

2
[1, 3, 4]

중간 요소를 제거하면 뒤 요소들이 앞으로 당겨져야 하므로 O(n)이다.

6.5 remove()

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

numbers.remove(2)

print(numbers)

출력 결과:

[1, 3, 2, 4]

remove()는 삭제할 값을 먼저 찾아야 한다.
최악의 경우 리스트 끝까지 찾아야 하므로 O(n)이다.

6.6 sort()

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

numbers.sort()

print(numbers)

출력 결과:

[1, 2, 3, 4, 5]

파이썬의 정렬은 Timsort를 사용하며 평균적으로 O(n log n)이다.

---

7. 공간 복잡도가 증가하는 상황

공간 복잡도는 추가 메모리를 얼마나 사용하는지와 관련이 있다.

7.1 새 리스트를 만드는 경우

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

doubled = []

for number in numbers:
    doubled.append(number * 2)

print(doubled)

출력 결과:

[2, 4, 6, 8, 10]

입력 리스트 크기만큼 새 리스트가 만들어진다.
따라서 공간 복잡도는 O(n)이다.

7.2 딕셔너리를 추가로 만드는 경우

words = ["apple", "banana", "apple", "orange", "banana", "apple"]

counter = {}

for word in words:
    if word in counter:
        counter[word] += 1
    else:
        counter[word] = 1

print(counter)

출력 결과:

{'apple': 3, 'banana': 2, 'orange': 1}

단어 종류가 많아질수록 딕셔너리 크기도 커진다.
따라서 공간 복잡도는 O(k)이다. 여기서 k는 서로 다른 단어의 개수이다.
최악의 경우 모든 단어가 다르면 O(n)이 된다.

7.3 재귀 호출이 쌓이는 경우

재귀 함수는 함수 호출이 스택 메모리에 쌓인다.

def countdown(n):
    if n == 0:
        return

    print(n)
    countdown(n - 1)


countdown(5)

출력 결과:

5
4
3
2
1

countdown(5)는 내부적으로 다음처럼 호출이 쌓인다.

countdown(5)
countdown(4)
countdown(3)
countdown(2)
countdown(1)
countdown(0)

재귀 깊이가 n만큼 증가하므로 공간 복잡도는 O(n)이다.

---

8. 비효율적인 코드와 효율적인 코드 비교

같은 기능을 하더라도 코드 작성 방식에 따라 성능이 크게 달라질 수 있다.

8.1 중복 데이터 찾기

리스트에 중복 값이 있는지 확인하는 코드를 비교해보자.

비효율적인 코드: O(n²)

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

    return False


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

print(has_duplicate_slow(numbers))

출력 결과:

True

이 코드는 모든 숫자 쌍을 비교한다.

1과 2 비교
1과 3 비교
1과 4 비교
...

이중 반복문을 사용하므로 시간 복잡도는 O(n²)이다.

효율적인 코드: O(n)

def has_duplicate_fast(numbers):
    seen = set()

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

        seen.add(number)

    return False


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

print(has_duplicate_fast(numbers))

출력 결과:

True

set은 값을 빠르게 찾을 수 있는 자료구조이다.
각 숫자를 한 번씩만 확인하므로 시간 복잡도는 평균적으로 O(n)이다.

다만 seen이라는 집합을 추가로 사용하므로 공간 복잡도는 O(n)이다.

시간을 줄이는 대신 추가 메모리를 사용한다.

---

8.2 특정 값이 있는지 여러 번 확인하기

여러 개의 값을 리스트 안에서 찾는 상황을 생각해보자.

비효율적인 코드: O(n * m)

members = ["apple", "banana", "orange", "melon", "cherry"]
targets = ["melon", "berry", "apple"]

result = []

for target in targets:
    if target in members:
        result.append(target)

print(result)

출력 결과:

['melon', 'apple']

target in members는 리스트를 순차 탐색한다.
targets의 개수가 m, members의 개수가 n이면 시간 복잡도는 O(n * m)이다.

효율적인 코드: O(n + m)

members = ["apple", "banana", "orange", "melon", "cherry"]
targets = ["melon", "berry", "apple"]

member_set = set(members)
result = []

for target in targets:
    if target in member_set:
        result.append(target)

print(result)

출력 결과:

['melon', 'apple']

members를 set으로 바꾸면 포함 여부를 평균적으로 O(1)에 확인할 수 있다.

set 생성: O(n)
targets 순회: O(m)
전체 시간 복잡도: O(n + m)

대신 member_set을 만들기 위한 추가 메모리가 필요하므로 공간 복잡도는 O(n)이다.

---

9. 시간과 공간은 자주 trade-off 관계이다

효율적인 알고리즘은 시간과 공간을 함께 고려해야 한다.

어떤 코드는 메모리를 적게 쓰지만 느릴 수 있다.
반대로 어떤 코드는 메모리를 더 사용하지만 훨씬 빠를 수 있다.

느리지만 메모리 적게 사용:
이중 반복문으로 직접 비교

빠르지만 메모리 더 사용:
set, dict 같은 자료구조 활용

따라서 좋은 코드는 상황에 따라 적절한 균형을 선택하는 코드이다.

---

10. 시간 복잡도 빠른 순서

일반적으로 자주 보는 시간 복잡도를 빠른 순서대로 나열하면 다음과 같다.

O(1)
O(log n)
O(n)
O(n log n)
O(n²)

하지만 입력 크기가 아주 작을 때는 실제 실행 시간이 다르게 느껴질 수도 있다.
빅오는 입력 크기가 커질 때의 성장 흐름을 설명하는 도구이다.

---

11. 핵심 요약

개념	설명
시간 복잡도	입력 크기가 커질 때 실행 시간이 얼마나 증가하는지
공간 복잡도	입력 크기가 커질 때 메모리 사용량이 얼마나 증가하는지
빅오 표기법	알고리즘 성능의 증가 흐름을 표현하는 방법
O(1)	입력 크기와 관계없이 일정
O(log n)	입력을 절반씩 줄이는 구조
O(n)	입력 크기만큼 한 번 순회
O(n log n)	효율적인 정렬에서 자주 등장
O(n²)	이중 반복문에서 자주 등장

오늘 과제의 핵심은 다음 한 문장으로 정리할 수 있다.

좋은 코드는 동작하는 코드에서 끝나지 않고, 입력이 커져도 빠르고 효율적으로 동작하는 코드이다.