시간 복잡도 (Time Complexity)
문제를 해결하기 위한 알고리즘의 로직을 코드로 구현할 때,
입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼만큼 걸리는가?
즉, 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다.
효율적인 알고리즘이란, 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘 을 구성했다는 것이다. 시간 복잡도는 주로 빅-오 표기법(Big-O)을 사용해 나타낸다.
일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다.
시간 복잡도 유형
시간 복잡도는 3가지 경우로 나타낸다.
- 최선의 경우 (Best Case)
- Big-Ω (빅-오메가)
- 빅 오메가 표기법 사용
- 최선의 시나리오로 최소 이만한 시간이 걸림
- 최악의 경우 (Worst Case)
- Big-O (빅-오)
- 빅 오 표기법 사용
- 최악의 시나리오로 아무리 오래 걸려도 이 시간보다 덜 걸림
- 평균적인 경우 (Average Case)
- Big-θ (빅-세타)
- 빅 세타 표기법 사용
- 평균 시간을 나타냄
빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있다. 한 마디로, "이 정도 시간까지 걸릴 수 있다." 로 표현할 수 있다. 최선의 경우 또는 평균값을 기대하는 시간 복잡도로 알고리즘을 구현한다면, 최악의 경우 어디에서 문제가 발생했는지 알아내기 위해 로직의 많은 부분을 파악해야 하므로 문제를 파악하는 데 많은 시간이 필요하다.
따라서, 최악의 경우로 알고리즘 성능을 파악하여 대비 하는 것이 바람직하기 때문에, 다른 표기법보다 빅오 표기법을 많이 사용한다.
시간 복잡도 계산
시간 복잡도는 일반적으로 최악의 경우를 계산하는 빅오 표기법으로 나타낸다.
연산 횟수가 다항식으로 표현될 경우, 최고차항을 제외한 모든 항과 최고차항의 계수를 제외시켜 나타낸다.
예를 들어 입력 크기가 n이라고 했을 때 다음과 같이 표기한다.
- 최고차항만 나타낸다. (가장 높은 차수만 남긴다.)
- T(n) = n^2+2n+1 = O(n^2)
- O(n² + n) -> O(n²)
- 최고차항의 계수는 제외한다. (계수 및 상수는 과감하게 버린다.)
- T(n) = 2n = O(n)
- O(2n + 3) -> O(n)
다음 알고리즘을 가지고 시간 복잡도를 구하면,
int func (int n) {
int sum = 0; // 대입연산 1회
int i = 0; // 대입연산 1회
for(i=0; i < n; i++) { // 반복문 n+1회
sum += i; // 덧셈 연산 n회
}
for(i=0; i < n; i++) { // 반복문 n+1회
sum += i; // 덧셈 연산 n회
}
return sum; // 리턴 1회
}위 알고리즘에 단계별 연산 횟수는 주석과 같고 총 연산 횟수는 4n+5이다.
그러므로 이 알고리즘의 시간 복잡도는 T(n) = 4n+5 = O(n) 이다.
빅오(Big O) 표기법
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)
왼쪽 O(1)으로 갈수록 실행 횟수가 적고 시간 복잡도가 낮은 것 이다. (효율성이 높다.)
오른쪽 O(n!)으로 갈수록 실행 횟수가 많고 시간 복잡도가 높은 것 이다. (효율성이 떨어진다.)
O(1) : 상수 (Constant)
입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 나타낸다. 데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않는다.
function BigO(n){
console.log("Hello Big-O");
}
O(log₂ n) : 로그 (Logarithmic)
입력 데이터의 크기가 커질수록 처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아지는 알고리즘이다.
예를 들어 데이터가 10배가 되면, 처리 시간은 2배가 된다. 이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당된다.
빅오 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
BST(Binary Search Tree) 의 경우, 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다. 이 경우 O(log n)의 시간 복잡도를 가진 알고리즘이다
O(n) : 선형 (Linear)
입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘이다.
예를 들어 데이터가 10배가 되면, 처리 시간도 10배가 됩니다. 1차원 for문이 있다.
function BigO(n){
for(let i=0; i<n; i++){
console.log(i);
}
}알고리즘이 입력한 개수인 n만큼 수행된다. 즉 입력 데이터가 증가할수록 처리시간도 증가한다.
O(n log₂ n) (Linear-Logarithmic)
데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘이다.
예를 들어 데이터가 10배가 되면, 처리 시간은 약 20배가 된다. 정렬 알고리즘 중 병합 정렬, 퀵 정렬이 대표적이다.
빅오 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
O(n²) : 2차 (quadratic)
데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘이다.
예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 됩니다. 이중 루프(n² matrix)가 대표적이며 단, m이 n보다 작을 때는 반드시 O(nm)로 표시하는 것이 바람직하다.
function BigO(n){
for(let i=0; i<n; i++){
console.log(i);
for(let j=0; j<n; j++){
console.log(j);
}
}
}알고리즘이 입력한 개수의 n^2만큼 수행된다. 즉 입력 데이터가 증가할수록 처리시간이 제곱 배로 증가한다.
O(2ⁿ) : 지수 (Exponential)
데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘이다.
대표적으로 피보나치 수열이 있으며, 재귀가 역기능을 할 경우도 해당된다.
function fibonacci(n){
if (n <= 1) {
return n;
}
return fibonacci(n-1) + fibonacci(n-2);
}위 알고리즘은 피보나치 수를 구하는 알고
빅오 표기법중 가장 느린 시간 복잡도를 가진다.
빅오 표기법 예제
- O(1) : 스택의 Push, Pop
- O(log n) : 이진트리
- O(n) : for 문
- O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
- O(n²): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
- O(2ⁿ) : 피보나치 수열
시간 측정 방법
import time
start_time = time.time() # 측정 시작
# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력위 코드로 측정 시간과 측정 종료 시간을 비교하여 확인할 수 있다.
수행 시간 비교
아래의 코드는 배열에 1~100까지의 정수를 무작위로 골라 10,000개의 정수를 삽입하는데, 가장 작은 원소의 인덱스부터 차곡차곡 넣어주는 for문을 직접 짠 코드와 파이썬 기본 라이브러리 sort를 사용하여 수행 시간 차이를 보는 코드다.
from random import randint
import time
# 배열에 10,000개의 정수를 삽입
array = []
for _ in range(10000):
array.append(randint(1, 100)) # 1부터 100 사이의 랜덤한 정수
# 선택 정렬 프로그램 성능 측정
start_time = time.time()
# 선택 정렬 프로그램 소스코드
for i in range(len(array)):
min_index = i # 가장 작은 원소의 인덱스
for j in range(i + 1, len(array)):
if array[min_index] > array[j]:
min_index = j
array[i], array[min_index] = array[min_index], array[i] # 스와프
end_time = time.time() # 측정 종료
print("선택 정렬 성능 측정:", end_time - start_time) # 수행 시간 출력
# 배열을 다시 무작위 데이터로 초기화
array = []
for _ in range(10000):
array.append(randint(1, 100)) # 1부터 100 사이의 랜덤한 정수
# 기본 정렬 라이브러리 성능 측정
start_time = time.time()
# 기본 정렬 라이브러리 사용
array.sort()
end_time = time.time() # 측정 종료
print("기본 정렬 라이브러리 성능 측정:", end_time - start_time) # 수행 시간 출력
해당 코드를 시행해보면,
선택 정렬 성능 측정: 6.268864870071411
기본 정렬 라이브러리 성능 측정: 0.0009975433349609375엄청나게 시간이 차이가 발생한다. 보통 코딩 테스트 문제를 풀 때 수행 시간으로 1~5초를 준다고 하니까 6초가 걸리는 방식으로 코드를 짜면 안 된다는 걸 알 수 있다.
다시 시도했을 경우,
선택 정렬 성능 측정: 4.549175024032593
기본 정렬 라이브러리 성능 측정: 0.000997304916381836어쨌든 성능 차이가 크다.
정렬 알고리즘 비교
| Sorting Algorithms | 공간 복잡도 | 시간 복잡도 | ||
| 최악 | 최선 | 평균 | 최악 | |
| Bubble Sort | O(1) | O(n) | O(n2) | O(n2) |
| Heapsort | O(1) | O(n log n) | O(n log n) | O(n log n) |
| Insertion Sort | O(1) | O(n) | O(n2) | O(n2) |
| Mergesort | O(n) | O(n log n) | O(n log n) | O(n log n) |
| Quicksort | O(log n) | O(n log n) | O(n log n) | O(n2) |
| Selection Sort | O(1) | O(n2) | O(n2) | O(n2) |
| Shell Sort | O(1) | O(n) | O(n log n2) | O(n log n2) |
| Smooth Sort | O(1) | O(n) | O(n log n) | O(n log n) |
자료구조 비교
| Data Structures | Average Case | Worst Case | ||||
| Search | Insert | Delete | Search | Insert | Delete | |
| Array | O(n) | N/A | N/A | O(n) | N/A | N/A |
| Sorted Array | O(log n) | O(n) | O(n) | O(log n) | O(n) | O(n) |
| Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
| Doubly Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
| Stack | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
| Hash table | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) |
| Binary Search Tree | O(log n) | O(log n) | O(log n) | O(n) | O(n) | O(n) |
| B-Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
| Red-Black tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
참고 자료
https://bangu4.tistory.com/202
https://blog.chulgil.me/algorithm/
https://yoongrammer.tistory.com/79
'Algorithm' 카테고리의 다른 글
| [알고리즘] 서로소 집합 (Disjoint Sets) - 사이클 판별 (0) | 2023.12.10 |
|---|---|
| [알고리즘] 서로소 집합 (Disjoint Sets) - 자료구조 (0) | 2023.12.09 |
| [알고리즘] 최장 증가 부분 수열(LIS) 알고리즘 (0) | 2023.09.01 |
| [알고리즘] 에라토스테네스의 체 (소수 판별) (0) | 2023.08.25 |
| [알고리즘] 이진 탐색 / 이분 탐색 (Binary Search) (0) | 2023.08.17 |