1. 시간 복잡도(Time Complexity)
시간 복잡도(Time Complexity)는 알고리즘이 실행되는데 얼마나 시간이 걸리는 지 입력 크기(Input Size)를 기준으로 나타낸 개념이다.
※ 알고리즘 = 문제 해결 방법
‼️ 시간 복잡도 ≠ 실제 코드 실행 시간
시간 복잡도와 실제 코드의 실행 시간이 같은 개념이라고 생각할 수 있지만, 둘은 조금 다르다.
예를 들어, 같은 코드라도 컴퓨터 성능, CPU, 메모리 환경에 따라 실제 실행 시간은 달라질 수 있다.
하지만 시간 복잡도는 입력 데이터 크기가 증가할 때 알고리즘이 얼마나 많은 연산을 수행하는지를 분석하는 개념이다.
즉, 입력이 커질수록 실행 시간이 어떤 방식으로 증가하는가 를 보는 것이다.
또, 시간 복잡도를 활용하면 같은 문제를 해결하더라도 어떤 알고리즘이나 자료구조가 더 효율적인지 비교할 수 있다.
시간 복잡도를 표현하는 방법은 3가지가 있다.
세타 표기법 (θ Notation)
- 알고리즘의 평균적인 시간 복잡도를 분석할 때 자주 사용된다.
- 알고리즘 실행 시간의 상한(upper bound)과 하한(lower bound)를 함께 고려한다
- 입력 크기가 증가하더라도 특정 범위 안에서 실행 시간이 증가하는 경우를 나타낸다.
빅-오 표기법 (O-Notation)
- 알고리즘 실행 시간의 상한(upper bound)을 표현하는 방법이다
- 알고리즘의 최악의 경우(worst case)를 분석할 때 사용한다
- 시간 복잡도를 표현할 때 가장 많이 사용되는 표기법이다
오메가(Ω) 표기법
- 알고리즘 실행 시간의 하한(lower bound)을 표현하는 방법이다
- 알고리즘이 가장 빠르게 실행되는 경우 (best case)를 분석할 때 사용한다.
- 실행 시간이 최소 어느 정도 필요함을 나타낸다.
2. 공간 복잡도(Space Complexity)
공간 복잡도는 알고리즘을 실행하는 데 필요한 메모리 양을 의미한다.
프로그램이 문제를 해결하는 과정에서 임시데이터를 저장하거나 최종 결과를 보관하기 위해서 메모리 공간이 필요하다.
이 때, 알고리즘이 문제를 해결하는데 얼마나 많은 메모리를 사용하는 지를 나타내는 개념을 공간 복잡도(Space Complexity)라 한다.
즉, 공간 복잡도는 입력데이터의 크기에 다라 알고리즘이 얼마나 많은 메모리를 사용하는 지를 나타내는 것이다.
공간 복잡도는 보통 두 가지로 나누어 분석한다.
1. 고정 부분 (Fixed Part)
입력 크기와 상관 없이 항상 일정하게 필요한 메모리 공간이다.
예를 들어,
- 프로그램 코드
- 상수
- 변수
등에 사용되는 메모리가 고정 부분에 포함된다.
2. 가변 부분 (Variable Part)
입력 크기에 따라 필요한 메모리 양이 달라지는 부분이다.
예를 들어,
- 재귀 호출 시 사용하는 스택 메모리 (recursion stack)
- 입력 데이터의 크기에 다라 추가로 생성되는 참조 변수
가 가변 부분에 포함된다.
3. 빅오 표기법(Big-O Notation)
빅오 표기법(Big-O Notation)은 알고리즘 실행 시간의 상한(upper bound)을 표현하는 방법이다.
즉, 입력 데이터가 커질 때 알고리즘이 최악의 경우 어느 정도 시간이 걸릴 수 있는지를 나타낸다.
쉽게 말하면, “최악의 상황에서도 이 정도 시간 안에는 실행된다” 라는 의미로 이해할 수 있다.
4. 시간 복잡도 비교
4.1 O(1)
O(1) 은 입력 데이터의 크기와 상관없이 항상 일정한 시간이 걸리는 경우를 의미한다.
즉 데이터의 개수가 100개가 되든 1,000,000개이든 수행해야 하는 연산 횟수가 거의 변하지 않는다.
그래서 이를 상수 시간(Constant Time) 이라고 부른다.
예시
👉 리스트는 인덱스를 이용해 원하는 위치에 바로 접근할 수 있기 때문에, 시간 복잡도는 O(1) 이다.
4.2 O(log n)
로그 시간 복잡도는 입력 데이터의 크기가 증가하더라도 실행 시간이 비교적 천천히 증가하는 경우를 의미한다.
주로 데이터를 한 번에 전부 확인하는 것이 아니라, 탐색 범위를 절반씩 줄여나가는 알고리즘에서 많이 나타난다.
예시
대표적인 예시로는 이진 탐색(Binary Search) 알고리즘이 있다.
이진 탐색은 정렬된 데이터에서 원하는 값을 찾을 때, 중간 값을 기준으로 탐색 범위를 절반씩 줄여나가는 방식이다.
예를 들어, 찾고자 하는 값이 중간값보다 작다면 왼쪽 부분만 탐색하고, 크다면 오른쪽 부분만 탐색한다.
이 과정을 반복하면서 탐색 범위를 점점 좁혀 나간다.
# 정렬된 리스트를 이진 탐색으로 몇 번 인덱스에 있는 지 확인한다.
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
# 중간값이 찾는 값인지 확인
if arr[mid] == target :
return mid
# 2. target이 중간값보다 작으면
elif target < arr[mid] :
right =mid -1 # 오른쪽 범위를 mid - 1로 줄이기
# 3. target이 중간값보다 크면
elif target > arr[mid]:
left=mid +1 # 왼쪽 범위를 mid + 1로 줄이기
# 끝까지 못 찾으면
return -1
numbers = [8,10,28,20,6,24,9,7]
numbers.sort()
wanted= 28
if binary_search(numbers,wanted) != -1:
print(f'{wanted}가 {binary_search(numbers,wanted)}번 인덱스에 있습니다')
else : print(f'{wanted} 요소가 없습니다.')
실행 결과
4.3 O(n)
선형 시간 복잡도 O(n) 은 입력 데이터의 크기가 증가할수록 실행시간도 선형적으로 증가하는 구조를 가진다.
예시
리스트의 모든 요소를 하나씩 순회하는 알고리즘이 대표적인 예시이다
numbers=[10,20,30,40,50]
for num in numbers:
print(num,end=' ')
print()
실행 결과
4.4 O(n log n)
O(n log n)은 입력 데이터가 증가할수록 선형 시간보다 빠르게 증가하지만, O(n) 보다는 훨씬 효율적인 구조이다.
대표적인 예시로는 Merge Sort, Heap Sort, 그리고 Python 리스트의 sort() 함수가 있다.
Python의 sort() 함수는 내부적으로 Timsort 알고리즘을 사용하며 평균적으로 O(nlogn) 의 시간 복잡도를 가진다.
numbers=[70,30,50,60,10,20,40]
numbers.sort()
print(numbers)
실행 결과
4.5 O(n²)
이차 시간 복잡도 O(n²) 은 입력 데이터의 크기가 증가할수록 실행 시간이 제곱 형태로 증가하는 경우를 의미한다.
즉, 입력 크기가 2배가 되면 연산량은 약 4배 정도로 증가하게 된다.
대표적인 예시로는 중첩 반복문을 사용하는 구구단 출력 프로그램이 있다.
반복문 안에 또 반복문이 들어있는 구조이기 때문에 실행 횟수가 제곱 형태로 증가한다.
n=9
for i in range(2,n+1): # 단 반복
print(f'==== {i}단 ====')
for j in range(2,n+1): # 각 단의 곱셈 결과 출력
print(f'{i} x {j}= {i*j}')
print()
위 코드에서는 바깥 반복문이 n번 실행되고, 내부 반복문도 매번 n번 실행된다. 따라서 시간 복잡도는 O(n²) 이다.
실행 결과
5. 반복문 개수에 따라 달라지는 시간 복잡도
시간 복잡도를 구할 때 반복문의 개수 뿐만 아니라 어떤 구조로 이루어져 있는 지 모두 살펴보아야 한다.
특히 반복문이 중첩되어 있는지, 순차적으로 실행되는 지에 따라 시간 복잡도를 계산하는 방식이 달라진다.
| 반복문의 구조 | 독립적인 중첩 반복문 | 의존적인 중첩 반복문 | 순차적인 반복문 |
| 반복문 개수 | O(N x M) | 개수 : m → O(N^m) | O(N) |
5.1 독립적인 중첩 반복문 (Independent Nested Loops)
내부 반복문이 외부 반복문의 변수와 관계없이 항상 같은 횟수만큼 실행되는 경우, 반복 횟수를 서로 곱해서 시간 복잡도를 구한다.
예를 들어,
- 바깥 반복문 : N번 실행
- 내부 반복문 : M번 실행
이렇게 되면 전체 연산 횟수는 N x M 이 되어 시간 복잡도는 O(N x M) 이 된다.
5.2 의존적인 중첩 반복문 (Dependent Nested Loops)
내부 반복문의 횟수가 외부 반복문의 값에 따라 달라진는 경우이다.
예를 들어 바깥 반복문은 N번 실행되지만, 내부 반복문은 i 만큼 실행된다면 총 반복 횟수는
1 + 2 + 3 + ... + N
이 되고, 이를 계산하면 N(N+1)/2 형태가 되고, 결국 빅오 표기법에서는 O(N²) 이 된다.
5.3 로그 형태의 반복문 (Logarithmic Loops)
반복문이 한 번 실행될 때마다 값이 2배씩 증가하거나 절반씩 감소하는 경우, 시간 복잡도는 보통 로그 형태를 가진다. 이때 로그 형태의 코드가 바깥 반복문 안에서 반복 실행된다면 시간 복잡도는 O(N log N) 이 된다.
5.4 순차적인 반복문 (Sequential Loops)
반복문이 중첩된 것이 아니라 앞뒤로 순서대로 실행되는 경우, 시간 복잡도는 곱하지 않고 더한다.
예를 들어,
for i in range(n):
print(i)
for j in range(n):
print(j)
위 코드는 각각 N번씩 실행되므로 O(N + N) 즉 O(N) 의 시간 복잡도를 가지게 된다.
6. 리스트(List)에서 자주 사용하는 함수들의 시간 복잡도
| 함수 | append() | insert() | pop() | remove() | sort() |
| 시간복잡도 | 보통 O(1) 최악의 경우 O(n) |
O(n) | 기본 O(1) 최악의 경우 O(n) |
O(n) | O(nlogn) |
6.1 append()
append()함수는 리스트 맨 뒤에 새로운 요소를 추가하는 함수이다.
파이썬의 리스트는 내부적으로 동적 배열 구조를 사용한다. 보통은 마지막 위치에 바로 요소를 추가하기 때문에 상수 시간 O(1) 이 걸린다.
하지만, 리스트의 저장 공간이 가득 찬 경우에는 더 큰 메모리 공간을 새로 만들고 기존 요소들을 복사해야 하는 과정이 발생할 수 있다.
이런 경우에는 시간 복잡도가 O(n) 이 될 수도 있다.
👉 평균적으로는 O(1) 이지만 최악의 경우 O(n) 이다.
6.2insert()
insert() 함수는 특정 인덱스 위치에 원하는 요소를 삽입하는 함수이다.
리스트 중간에 새로운 요소가 들어오면, 기존 요소들을 한 칸씩 뒤로 밀어야 하기 때문에 시간이 더 걸린다.
👉 insert함수의 시간복잡도는 최악의 경우 O(n) 이다.
6.3 pop()
pop() 함수는 요소를 제거하면서 해당 값을 반환(return)하는 함수이다.
기본적으로 pop() 을 사용하면 리스트 맨 마지막 요소를 제거한다. 맨 뒤 요소를 제거하는 것은 바로 접근해서 삭제하면 되기 때문에 O(1) 이다.
그러나 특정 인덱스를 지정하는 경우는 다르다.
예를 들어
numbers.pop(0)
이렇게 앞쪽 요소를 제거하면 뒤에 있는 요소들이 한 칸씩 앞으로 이동해야 하기 때문에 최악의 경우 O(n) 이 된다.
👉 기본적으로 O(1) 이지만 최악의 경우 O(n)이 된다
6.4 remove()
remove() 함수는 값(value)을 기준으로 요소를 삭제하는 함수이다.
리스트는 특정 값을 찾기 위해 앞에서부터 순차적으로 탐색해야 한다.
즉, 원하는 값을 찾는 과정에서 반복이 필요하기 때문에 시간 복잡도는 O(n) 이다.
6.5 sort()
평균적으로 O(nlogn) 이다
sort() 함수는 리스트를 정렬하는 함수이다.
파이썬의 sort() 는 내부적으로 Timsort라는 정렬 알고리즘을 사용한다.
Timesort는 Merge Sort 와 Insertion Sort를 결합한 방식이고, 평균적으로 O(nlogn) 의 시간 복잡도를 가진다.
7. 공간 복잡도가 증가하는 상황 예제 만들기
공간 복잡도가 증가하는 대표적인 상황 중 하나는 기존 데이터를 처리하면서 새로운 메모리 공간을 추가로 사용하는 경우이다.
예를 들어, 주어진 리스트의 순서를 뒤집는 상황을 생각해보자.
같은 결과를 만들더라도 새로운 리스트를 만드는 방식과 기존 리스트 내부에서 직접 바꾸는 방식은 공간 복잡도 차이가 생길 수 있다.
def reverse_list(arr):
new_arr=[] # 새로운 리스트 만들기
# 뒤에서 부터 하나씩 가져온 후 new_arr에 append
for i in range(len(arr)-1,-1,-1):
new_arr.append(arr[i])
return new_arr
👉 위 코드는 기존 리스트와 별도로 new_arr라는 새로운 리스트를 추가로 생성한다.
원래 리스트 크기가 n이라면 새로운 리스트에도 n개의 요소를 저장하기 위해 추가적인 메모리가 필요하다.
따라서 공간 복잡도는 O(n) 이다.
# 새로운 배열을 만들지 않는 함수 -> 공간 복잡도 커지지 않음
def reverse_inplace(arr):
left=0
right=len(arr)-1
# 양끝에서부터 가운데로 좁혀오면서 각자 자리를 바꾼다.
while left < right:
arr[left],arr[right]=arr[right],arr[left]
left+=1
right-=1
return arr
arr=[10,20,30,40,50,60,70,80,90,100]
print('기존 배열:',arr)
print('공간복잡도 증가시키는 함수 적용')
print('reverse_list(arr) : ',reverse_list(arr))
print()
print('공간복잡도를 증가시키지 않는 함수 적용')
print('reverse_inplace(arr):',reverse_inplace(arr))
👉 이번에는 새로운 리스트를 만들지 않고, 기존 리스트 내부에서 위치만 바꾸는 방식을 이용했다.
이 방법은 새로운 리스트를 만들지 않는다.
대신 기존 리스트 안에서 양쪽 값을 swap하는 방식으로 리스트의 순서를 뒤집는다.
이 과정에서 추가로 사용하는 변수는 left와 right 정도뿐 이고, 입력 크기가 커져도 필요한 메모리의 양이 거의 변하지 않아서
공간 복잡도는 O(1) 이다.
reverse_list 함수를 적용하면 새로운 공간을 만들어서 리스트에 요소를 넣기 때문에 공간 복잡도가 증가하지만
👉 reverse_inplace는 앞의 함수와 다르게 새로운 공간을 만들지 않아서 공간 복잡도가 거의 증가하지 않는다
8. 같은 기능을 하는 비효율적인 코드 vs 효율적인 코드
1부터 100까지의 합을 구하는 코드를 생각해보자.
파이썬을 처음 배우는 입장에서는 보통 for문을 사용해서 하나씩 더하는 방법을 먼저 떠올릴 수 있다.
하지만 수학 공식을 알고 있다면 반복문 없이도 한 번에 결과를 구할 수 있다.
즉, 같은 결과를 구하더라도 구현 방식에 따라 시간 복잡도가 달라질 수 있다.
💻 for문을 이용해 구하기
먼저 반복문을 사용해 1부터 100까지 더해보자
# for 문 이용해서 1부터 100까지 구하기
n=100
sum=0
for i in range(1,n+1):
sum+=i
print('sum=',sum)
👉 왜 O(n)일까?
위 코드는 1부터 n까지 숫자를 하나씩 모두 더하는 방식이다.
즉, n = 100이면 100번 반복하고, n = 1000이면 1000번 반복하게 된다.
입력 크기 n이 증가할수록 반복 횟수도 비례해서 증가하기 때문에 시간 복잡도는 O(n) 이다.
💻 수학 공식을 이용해 구하기
이번에는 반복문을 사용하지 않고, 등차수열의 합 공식을 이용해서 구해보자.
print('1부터 100까지의 합= ',(n * (n+1))//2)
👉 왜 O(1)일까?
위 코드는 반복문을 사용하지 않고, 공식 한 번만 계산해서 결과를 구한다.
즉, n = 100 이든 n = 1,000,000 이든 계산 횟수 자체는 거의 변하지 않는다.
입력 크기가 커져도 수행해야 하는 연산 횟수가 일정하기 때문에 시간 복잡도는 O(1) 이다.
실행 결과
'python' 카테고리의 다른 글
| 정렬 알고리즘 ① 버블정렬, 선택 정렬 , 삽입 정렬 (0) | 2026.06.10 |
|---|---|
| 자료구조 - 힙(Heap) (0) | 2026.06.08 |
| 자료구조 - 해시 테이블 (Hash Table) (0) | 2026.06.04 |
| 자료구조 - 이중 연결 리스트(Doubly Linked List) (0) | 2026.06.03 |
| 자료구조 - 트리 (0) | 2026.06.03 |