프로그램을 개발할때에는 같은 결과를 만들어 내는 코드라도 실행 속도는 천차만별이다.
예를 들어 특정 데이터를 찾을 때
처음부터 끝까지 순서대로 하나씩 확인하는 방법이 있고,
정렬된 데이터를 활용해서 훨씬 빠르게 찾아내는 방법도 있다.
데이터의 개수가 적을때는 큰 차이를 못느끼지만,
수백개, 수만개의 데이터를 처리하게 되면 알고리즘의 성능 차이는 매우 극명하게 나타난다.
이때 알고리즘의 성능 분석을 하기 위해 사용되는 개념이 시간 복잡도이다.
시간 복잡도란?
시간 복잡도는 프로그램이 실행될 때 걸리는 시간을
입력 크기에 따라 나타낸 것이다.
여기서 말하는 시간은 실제 시간(몇시, 몇분, 몇초)를 뜻하는게 아니라
프로그램이 실행되면서 수행되는 연산의 횟수를 말하는 것이다.
쉽게 말해 시간 복잡도는
'데이터가 많아졌을 때 이 코드가 얼마나 느려질까?'에 대한
답을 내리는 기준이 된다고 보면 쉽다.
※ 입력크기 n이 증가할수록 + 위쪽에 있는 알고리즘일수록 빠르게 연산횟수가 증가한다.
즉, 효율적인 알고리즘일수록 아래쪽에 위치한다.
💡 시간 복잡도 왜 사용할까?
예를 들어 영어 사전에서 'Koala'라는 단어를 찾으려고 할 때
K단락을 펼쳐서 찾으면 효율적으로 빠르게 단어를 찾을 수 있지만
사전의 첫 페이지(A)부터 마지막 페이지(Z)까지 한글자씩 모두 읽어가며 단어를 찾으면 매우 비효율적이다.
즉, 시간 복잡도는 내 코드가 무식하게 일하는 코드인지,
스스로 판단하고 성능을 지키며 효율적이게 일하는 코드인지 확인하기 위해 사용된다.
빅오 표기법
빅오 표기법은 시간 복잡도를 표현할 수 있는 가장 대표적인 방법이다.
입력 크기가 커질 때 연산량이 어떻게 증가하는지 간단하게 나타내며,
보통 O(1), O(n), O(n²)과 비슷한 형태로 작성된다.
※ n = 데이터 개수
※ log n = 데이터를 절반씩 나누었을 때 1이 될 때까지의 횟수 (데이터 8이면 log n은 3, 데이터 16이면 log n은 4) 실제로는 log₂(n) 형태로 작동하는것을 log n으로 표기한것이다.
자주보는 빅오 표기법 종류
O(1) : 상수 시간
데이터가 많아져도 연산 횟수가 항상 일정한 경우이다.
가장 빠른 시간 복잡도이며, 데이터가 아무리 많아져도 성능에는 큰 변화가 없다.
데이터 1개 → 1번 실행
데이터 100개 → 1번 실행
데이터 1000개 → 1번 실행
대표 예시
- 배열(Array)의 인덱스 접근
- 스택(Stack)의 Push, Pop
예제 코드
데이터가 1개든 100만개든 상관없이 연산 횟수가 고정되어있어
입력값 n이 실행시간에 전혀 영향을 주지 않는다.
# 입력값 n이 아무리 커져도 반복 횟수는 3 고정
n = 1000000
for i in range(3): # n과 관계없이 항상 3번만 실행 (상수 연산)
print("실행")
O(log n) : 로그 시간
데이터를 절반씩 줄여가며 탐색하거나 처리하는 방식으로
데이터가 매우 많아져도 연산 횟수가 크게 증가하지 않아 효율적이다.
데이터 8개 → 약 3번
데이터 16개 → 약 4번
데이터 32개 → 약 5번
데이터 1024개 → 약 10번
대표 예시
- 이진 탐색(Binary Search)
- 이진 탐색 트리(BST)
예제 코드
실행할 때마다 처리해야 할 데이터의 양이 절반씩 줄어든다.
n = 1024
while n > 1:
print(f"현재 남은 데이터 크기: {n}")
n //= 2 # 루프를 한 번 돌 때마다 n이 절반으로 감소 (O(log n))
# 데이터가 1024개일 때, 10번의 연산으로 종료
O(n) : 선형 시간
데이터 전체를 한 번씩 확인해야 하는 방식으로
데이터 개수에 비례하여 연산 횟수가 증가한다.
데이터 10개 → 10번 실행
데이터 100개 → 100번 실행
데이터 1000개 → 1000번 실행
대표 예시
- 선형 탐색(Linear Search)
- 리스트 전체 순회
예제 코드
입력값 n의 크기에 비례하여 실행 시간이 직선적으로 증가한다.
n = 10
for i in range(n): # n의 크기만큼 n번 반복 수행
print(f"{i+1}번째 데이터 처리 중")
# n이 10배 커지면 실행 시간도 10배 늘어남
O(n log n) : 선형 로그 시간
데이터를 나누면서 동시에 전체 데이터를 처리하는 방식으로
효율적인 정렬 알고리즘에서 자주 등장한다.
O(n)보다는 조금 더 느리지만, O(n²)보다는 훨씬 효율적이다
데이터 10개 → 약 33번
데이터 100개 → 약 664번
데이터 1000개 → 약 9966번
대표 예시
- 병합 정렬(Merge Sort)
- 퀵 정렬(Quick Sort, 평균)
- 힙 정렬(Heap Sort)
예제 코드
가장 대표적인 예시는 이진 탐색으로
1부터 100까지 숫자 중 하나를 맞출 때,
매번 업/다운을 통해 범위를 절반씩 줄여나간다.
데이터가 2개 늘어나도 연산 횟수는 단 1번만 늘어난다.
n = 16
for i in range(n): # 바깥 루프 : n번 반복 (O(n))
x = n
while x > 1: # 안쪽 루프 : 데이터를 절반씩 줄임 (O(log n))
x //= 2
# 결과적으로 n * log n 만큼 실행됨
O(n²) : 제곱 시간
데이터를 서로 비교해야하는 경우 자주 나타나며,
이중 반복문 구조에서 많이 발생하게 된다.
데이터가 10배 증가하면 연산횟수는 100배 증가하는 방식이다.
데이터 10개 → 100번 실행
데이터 100개 → 10,000번 실행
데이터 1000개 → 1,000,000번 실행
대표 예시
- 버블 정렬(Bubble Sort)
- 선택 정렬(Selection Sort)
- 삽입 정렬(Insertion Sort, 평균)
예제 코드
중첩 반복문 사용 시 나타나며,
데이터가 조금만 늘어나도 실행 시간이 많이 증가한다.
데이터가 10배 늘어나면 시간은 100배가 된다.
n = 10
for i in range(n): # 첫 번째 루프 (n번)
for j in range(n): # 두 번째 루프 (n번)
# n x n 번의 연산이 발생
print(f"좌표 ({i}, {j}) 처리")
# 모든 원소를 서로 비교해야 할 때 발생(버블 정렬)반복문 개수에 따른 시간 복잡도
시간 복잡도는 반복문의 개수와 형태에 따라 달라질 수 있다.
1) 반복문이 1개일 경우
데이터를 n번 반복하기 때문에 시간 복잡도는 O(n)이다.
for i in range(n):
print(i)
2) 중첩 반복문 사용할 경우
n x n번 실행되기 때문에 시간 복잡도는 O(n²)이다.
for i in range(n):
for j in range(n):
print(i, j)
3) 중첩 반복문이 3개 사용될 경우
n x n x n번 실행되기 때문에 시간 복잡도는 O(n³)이다.
for i in range(n):
for j in range(n):
for k in range(n):
print(i, j, k)
4) 연속된 반복문이 사용될 경우
n + n = 2n이지만 빅오 표기법에선 상수를 제거하기 때문에 O(n)으로 표현된다.
for i in range(n):
print(i)
for j in range(n):
print(j)시간 복잡도 비교
일반적으로 O(1)에 가까울수록 효율이 좋으며,
O(n²) 이상부터는 데이터가 많아질 경우 성능 저하가 크게 발생할 수 있다.
따라서 자료구조와 알고리즘을 선택할 때는 시간 복잡도를 함께 고려하는 것이 중요하다.
| 시간 복잡도 | 증가 속도 | 대표 예시 |
| O(1) | 일정 | 배열 인덱스 접근 |
| O(log n) | 매우 느리게 증가 | 이진 탐색 |
| O(n) | 데이터와 비례하여 증가 | 선형 탐색 |
| O(n log n) | 비교적 효율적 | 병합 정렬, 퀵 정렬 |
| O(n²) | 빠르게 증가 | 버블 정렬 |
자료구조별 시간복잡도
1) 배열(Array)
배열은 연속된 메모리 공간에 데이터를 저장하는 자료구조로
인덱스를 통해 원하는 위치에 바로 접근할 수 있어 데이터 조회가 매우 빠른 특징이 있다.
연속된 메모리 공간이기 때문에
중간에 데이터를 삽입하거나 삭제할 경우 많은 데이터 이동이 발생할 수 있다.
- 접근 → O(1)
- 탐색 → O(n)
- 삽입 → O(n)
- 삭제 → O(n)
2) 연결리스트(Linked List)
연결리스트는 노드가 데이터와 다음 노드의 주소를 저장하는 방식으로
배열과 다르게 메모리가 연속적이지 않기 때문에
특정 위치의 데이터를 찾기 위해선 처음부터 순서대로 탐색하여 찾아야한다.
노드 간 연결을 통하여 데이터를 관리하기 때문에
노드 연결 정보만 변경하면 삽입과 삭제가 빠르게 가능하다.
- 접근 → O(n)
- 탐색 → O(n)
- 삽입 → O(1)
- 삭제 → O(1)
3) 스택(Stack)
스택은 LIFO구조로 가장 마지막에 들어온 데이터가 가장 먼저 제거되는 방식이다.
그렇기 때문에 테이터 추가와 삭제가 매우 빠른 반면
중간 데이터에 대한 접근은 비효율적인 구조이다.
- 접근 → O(1)
- 탐색 → O(n)
- 삽입(Push) → O(1)
- 삭제(Pop) → O(1)
4) 큐(Queue)
큐는 FIFO구조로 가장 먼저 들어온 데이터가 가장 먼저 제거되는 방식이다.
스택과 구조는 다르지만 데이터 추가와 삭제가 빠르고
중간 데이터를 찾는 경우 순차 탐색이 필요해 비효율적이다.
- 접근 → O(1)
- 탐색 → O(n)
- 삽입(Enqueue) → O(1)
- 삭제(Dequeue) → O(1)
5) 트리(Tree)
트리는 부모-자식 관계를 가지고 있는 자료구조로
이진탐색트리는 데이터를 효율적으로 탐색할 수 있다.
트리구조는 계층형 자료구조이기 때문에 균형이 유지 될 경우 빠른 탐색이 가능하지만
트리가 한쪽으로 치우치게 된다면 탐색과정이 O(n)이 될수도 있다.
- 접근 → O(log n)
- 탐색 → O(log n)
- 삽입 → O(log n)
- 삭제 → O(log n)
리스트 함수 시간복잡도
Python의 리스트는 내부적으로 동적 배열 구조를 사용하고 있다.
그렇기 때문에 리스트와 함께 사용되는 함수마다 시간 복잡도가 다르게 나타난다.
1) append()
append() 함수는 리스트의 맨 뒤에 데이터를 추가하는 방식으로
기존 데이터 이동하지 않고 마지막 위치에 추가 데이터를
바로 저장하기 때문에 매우 빠르게 동작한다.
- 평균 시간복잡도 → O(1)
2) insert()
insert() 함수는 원하는 위치에 데이터를 추가하는 방식으로
추가 위치 뒤에 데이터가 있을경우 한 칸씩 뒤로 이동시켜야한다.
그렇기 때문에 데이터가 많을수록 시간이 증가한다.
- 평균 시간복잡도 → O(n)
3) pop()
pop() 함수는 리스트의 맨 뒤에 데이터를 삭제하는 방식으로
마지막 데이터만 톡 삭제해주면 되기 때문에
별다른 데이터 이동이 발생하지 않는다.
※ pop(0) 으로 앞쪽 요소를 제거 할 경우 : 뒤의 데이터들을 모두 앞으로 이동해야하기 때문에 O(n)이 된다.
- 평균 시간복잡도 → O(1)
4) remove()
remove() 함수는 지정한 값을 찾아 삭제하는 방식으로
삭제 전, 먼저 데이터를 순차적으로 탐색한다.
그렇기 때문에 데이터가 많을수록 탐색 할 데이터가 많아지기 때문에 시간이 증가한다.
- 평균 시간복잡도 → O(n)
5) sort()
sort() 함수는 리스트 전체를 정렬하는 방식으로
파이썬의 Timsort라는 알고리즘을 사용하여
많은 데이터를 효율적으로 정렬할 수 있다.
- 평균 시간복잡도 → O(n log n)
💡 Timsort란 무엇인가?
Python의 list.sort()와 sorted() 함수에서 사용하는 정렬 알고리즘으로
병합 정렬과 삽입 정렬의 장점을 합쳐서 만든 정렬 알고리즘이다.
❓ 왜 만든걸까?
실제로 데이터가 어느정도 정렬이 되어있는 경우(대부분 정렬이 되어있고 일부만 섞임)
Timsort는 이미 정렬된 구간을 찾고, 해당 구간을 분석하여
정렬되지 않은 부분들을 정렬해주는 기능을 한다.
그렇기 때문에 Timsort는 사용할 수 있는 상황이 주어지면
안정적이고 성능이 좋은 정렬 알고리즘으로 사용될 수 있다.
- 최선(Best) → O(n)
- 평균(Average) → O(n log n)
- 최악(Worst) → O(n log n)
정렬알고리즘 시간복잡도
1) 버블 정렬(Bubble Sort)
버블 정렬은 인전한 두 데이터를 비교하면서
큰 값은 뒤로 이동시키는 정렬방식으로
데이터가 많아질수록 비교횟수가 많아져 비효율적이다.
- 평균 시간복잡도 → O(n²)
2) 선택 정렬(Selection Sort)
선택 정렬은 가장 작은값을 찾아 앞으로 이동시키는 정렬방식으로
버블정렬과 동일하게 데이터가 많아질수록 비교횟수가 많아진다.
- 평균 시간복잡도 → O(n²)
3) 삽입 정렬(Insertion Sort)
삽입 정렬은 이미 정렬된 영역의 적절한 위치에 데이터를 추가하는 방식이다.
이는 데이터가 거의 정렬되어있을 때 효율적으로 사용할 수 있다.
- 평균 시간복잡도 → O(n²)
4) 병합 정렬(Merge Sort)
병합 정렬은 데이터를 계속 반으로 나누고 합치는것을 반복하는 정렬방식으로
안정적이고 성능이 매우 효율적인 방식이다..
- 평균 시간복잡도 → O(n log n)
5) 퀵 정렬(Quick Sort)
기준값을 선택해서 작은값과 큰값을 분할해가며 정렬하는 방식이다.
- 평균 시간복잡도 → O(n log n)
- 최악 시간복잡도 → O(n²)
정리
※ 표의 색상 의미
🟢 초록색 : 성능, 특성 우수
🟡 노란색 : 보통 수준
🔴 빨간색 : 상대적으로 불리함
1) 자료구조 시간복잡도 비교
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
| 배열 | O(1) | O(n) | O(n) | O(n) |
| 연결리스트 | O(n) | O(n) | O(1) | O(1) |
| 스택 | O(1) | O(n) | O(1) | O(1) |
| 큐 | O(1) | O(n) | O(1) | O(1) |
| 트리 | O(log n) | O(log n) | O(log n) | O(log n) |
2) 리스트 함수 시간복잡도 비교
| 함수 | 시간복잡도 | 설명 |
| append() | O(1) | 맨 뒤에 데이터 추가 |
| insert() | O(n) | 중간 위치 삽입 시 데이터 이동 발생 |
| pop() | O(1) | 맨 뒤 데이터 삭제 |
| remove() | O(n) | 삭제할 값을 탐색 후 제거 |
| sort() | O(n log n) | 전체 데이터 정렬 |
3) 정렬 알고리즘 시간복잡도 비교
| 정렬 알고리즘 | 최선 | 평균 | 최악 |
| 버블 정렬 | O(n) | O(n²) | O(n²) |
| 선택 정렬 | O(n²) | O(n²) | O(n²) |
| 삽입 정렬 | O(n) | O(n²) | O(n²) |
| 병합 정렬 | O(n log n) | O(n log n) | O(n log n) |
| 퀵 정렬 | O(n log n) | O(n log n) | O(n²) |
'Python > 자료구조 & 알고리즘' 카테고리의 다른 글
| [자료구조와 알고리즘] 공간 복잡도 (0) | 2026.06.07 |
|---|---|
| [자료구조] 해시 테이블(Hash Table), 해시 함수, 해시 충돌, 해결방법 (0) | 2026.06.04 |
| [자료구조] 트리(Tree), 이진 트리(Binary Tree), 트리 순회 (0) | 2026.06.03 |
| [자료구조] 선형 리스트(Linear List), 연결 리스트(Linked List), 이중 연결 리스트(Doubly Linked List) (1) | 2026.06.01 |
| [자료구조] 배열(Array), 스택(Stack), 큐(Queue) 정리 (0) | 2026.05.30 |