시간복잡도 (Time Complexity), Big-O
개요
우리가 작성한 코드는 실행시간이 얼마나 걸릴까요? 🤔
컴퓨터는 매우 빠르지만 계산이 복잡하거나 데이터의 양이 많다면 결과를 얻는 시간은 점차 길어질 것입니다.
예를 들면 무작위의 수 5개 중에서 "어떻게 하면 가장 큰 수를 찾을 수 있을까?" 를 고민하는 것을 알고리즘(algorithm) 이라고 합니다.
알고리즘 : 문제를 해결하기 위한 방법이나 절차
Big-O 표기법
큰 수를 찾는 알고리즘에서 만약 그 수열이 1, 2, 3, 4, 5 와 같다면 가장 처음 만나는 수1을 기록하고 그 다음 수와 비교해가며 큰 수를 만나면 바꿔 기록하는 것이죠.
결국 우리는 수열의 크기인 다섯번을 반복하면 가장 끝에서 만난 5가 가장 큰 수라는 결과를 얻게 됩니다.
다섯번을 반복해 5가 가장 큰 수임을 찾았으니 위 알고리즘을 푸는데 걸린 시간은 5회 라고 볼 수 있습니다.
그것을 시간복잡도라고 하고 Big-O 표기법으로 O(5) 라고 합니다.
시간복잡도 : 알로리즘을 수행하는데 걸리는 시간의 양
만약 수열이 5, 4, 3, 2, 1의 순서로 나열되어 있더라도 가장 끝수인 1까지 가야만 첫 수인 5가 가장 크다는 것을 확신할 수 있으므로 O(5) 입니다.
좀 더 수학적인 표현으로 수열의 크기(n)이 5와 같으므로 O(n) 이라고 표기합니다.
왜 하필 용어가 Max-O도 아니고 Long-O가 아닌지는 너무 고민하지 말고 표준(Standard, 남들이 다 쓰는 말)으로 받아들이면 됩니다.
시간복잡도라는 용어가 조금 이해가 된다면 좀 더 다양한 시간복잡도들을 예시와 함께 살펴보겠습니다.
O(1) 시간 복잡도
좀전에 O(n)으로 하자더니 갑자기 O(1)은 뭔가 혼란스럽네요.😩
서로 다릅니다. 예제를 보면서 설명하겠습니다.
#include <iostream>
using namespace std;
void printFirstElement(int arr[], int size) {
if (size > 0) {
cout << "First element: " << arr[0] << endl; // O(1)
}
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
printFirstElement(arr, 5);
return 0;
}
배열 1, 2, 3, 4, 5를 만들고 0번째 인덱스를 갖는 요소(Emement)를 출력하니 배열 arr[0] 즉, 1이 출력됩니다.
만약 arr[4] 라고 하면 5가 출력이 되겠죠. (배열 인덱스는 0부터 임을 유의)
배열을 키워 1억개 크기로 만들더라도 해당 인덱스에 접근해 값을 읽어오는 것은
오직 1회의 시간이 필요합니다. (연결리스트 자료구조의 경우 시간복잡도는 O(n))
이것을 상수 시간복잡도 O(1)라고 합니다.
상수 시간복잡도 : 입력 크기에 관계없이 항상 같은 시간이 걸리는 알고리즘
처음에 봤던 O(n)은 입력의 크기에 비례해 시간이 증가됩니다.
O(n) 시간 복잡도
앞서 언급한 최대,최소값 찾기 처럼 입력 크기에 비례해 시간복잡도가 증가합니다.
선형 시간복잡도라고 합니다
선형 시간 복잡도 : 입력크기에 비례해 시간이 증가하는 알고리즘
#include <iostream>
using namespace std;
void printAllElements(int arr[], int size) {
for (int i = 0; i < size; i++) { // O(n)
cout << arr[i] << ' ';
}
cout << endl;
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
printAllElements(arr, 5);
return 0;
}
배열에 1, 2, 3, 4, 5라는 5가지 원소를 넣고 모든 배열의 값을 출력하려면 5회 반복하며 arr[0], arr[1], arr[2], arr[3], arr[4]에 접근해야 합니다.
만약 배열의 크기가 100개라면 100회 반복하며 접근해야 하겠죠.
n이 수열의 크기라면 O(n) 이라고 할 수 있습니다.
O(n2) 시간 복잡도
앞서 O(n)에서 n=5라면 5회였지만 여기서는 O(52)=25회 라는 개념입니다.
#include <iostream>
using namespace std;
void printPairs(int arr[], int size) {
for (int i = 0; i < size; i++) { // O(n)
for (int j = 0; j < size; j++) { // O(n)
cout << "(" << arr[i] << ", " << arr[j] << ")" << endl;
}
}
}
int main() {
int arr[] = {1, 2, 3};
printPairs(arr, 3);
return 0;
}
배열 1, 2, 3이 있다면 각 원소의 수와 모든 원소의 수를 짝지어 표현하면 아래와 같습니다.
(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)
3가지 원소이므로 하나의 원소에 대해 3회씩 반복해야 하므로 3x3=9, 즉 32=9 회 시간이 소요됩니다.
O(n2)은 2중 반복문의 형태로 구현되는 모습을 보입니다.
만약 3중 반복문이라면 O(n3)의 시간복잡도를 갖게 됩니다.
O(log n) 시간 복잡도
로그 시간복잡도는 일반적으로 이진탐색트리 (Binary Search Tree) 자료구조가 갖는
시간복잡도 입니다.
여러분 마음속으로 1~64 사이 숫자 중 하나를 마음속으로 정해 보세요.
저는 그 수를 찾아야 하는 알고리즘 입니다.
제가 "그 수는 32보다 큰수입니까?" 라는 질문에 Yes라면 n은 절반이 줄어들게 됩니다. No라도 시간 복잡도가 줄어드는 것은 마찬가지 입니다.
(대답이 Yes라면 33~64사이 수이므로 다음은 48보다 큰 수 인지
물어보겠지요)
만약 수를 찾기 위해 1부터 순차적으로 마음속의 수가 맞는지 접근해 간다면 최악의 경우 64가 찾는 수라면 64회, 50이라면 50회, 1이라면 바로 찾게 됩니다.
하지만 n=64 일 때, log2 64를 계산하면,
log2 64 = log2(26) = 6 회 입니다. 와~😮
만약 n=1024 라면 10회 입니다. Amazing~
#include <iostream>
using namespace std;
int binarySearch(int arr[], int size, int target) {
int left = 0, right = size - 1;
while (left <= right) { // O(log n)
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Not found
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int target = 3;
int result = binarySearch(arr, 5, target);
if (result != -1) {
cout << "Element found at index: " << result << endl;
} else {
cout << "Element not found" << endl;
}
return 0;
}
시간 복잡도 비교
시간복잡도를 구체적으로 수치화 해서 살펴보겠습니다.
|
| 이미지 출처 : 나무위키(시간복잡도) |
그래프로 보면 좀 더 이해가 쉽습니다.
|
|
이미지 출처 : draw by chatGPT |
정리
-
O(1) : 상수 시간 복잡도로 입력 크기 nn에 상관없이 일정한 시간을 소요
-
O(log n) : 로그 시간 복잡도로 입력 크기가 증가함에 따라 완만하게 증가
-
O(n)) : 선형 시간 복잡도로 입력 크기에 비례하여 시간도 증가
-
O(n log n) : 입력 크기와 로그를 곱한 형태로, 정렬 알고리즘에서 자주 등장하는 시간 복잡도
-
O(n2) : 이차 시간 복잡도로, 입력 크기가 증가할수록 시간도 제곱으로 증가
-
O(2n) : 지수 시간 복잡도로, 아주 가파르게 증가
왜 효율적인 코드를 짜야하는지 조금 이해가 됩니다.
감사합니다.
댓글
댓글 쓰기