[자료구조] 시간복잡도
in Study on Data Structure
자료구조에서 많이 따지는 시간복잡도에 대해서 알아보자.
시간복잡도란?
어떤 알고리즘의 로직이 실행되는데 얼마나 오래걸리는지 나타내는 지표이며,
보통 O(n)과 같은 빅오 표기법을 사용한다.
예를 들어, 아래와 같은 코드를 보자.
for (int i = 0; i < 10; ++i)
{
for (int j = 0; j < n; ++j)
{
for (int k = 0; k < n; ++k)
cout << arr[j][k] << '\n';
}
}
2차원 배열 arr의 모든 원소으 출력을 10번 반복하는 구조이다.
이 코드의 시간복잡도는 O(10n^2)이다.
그리고 이 코드에다가 아래의 코드가 추가 된다고 생각해보자.
for (int i = 0; i < N; ++i)
cout << i << '\n';
이 코드의 시간복잡도는 O(n)이다.
따라서, 전체 코드의 시간 복잡도는 O(10n^2 + n)이라고 할 수 있다.
그렇다면, 전체 코드의 시간복잡도는 어떻게 표기할까?
숫자 n을 무한대와 같이 큰 수로 보낸다고 생각해보자.
이 때, 극한 값에 따라서 n이 무한대로 갈때, lim(10n^2 + n)의 값은
lim(10n^2)와 같다고 할 수 있다.
그리고 최고차항이 n^2로 같다고 한다면
lim(10n^2)의 값은 lim(n^2)와 같다고 볼 수 있을 것이다.
따라서 O(10n^2 + n)는 O(n^2)로 표기가 가능하다.
빅오 표기법에서는 상수나 항에 붙어 있는 계수는 생략한다.
그리고 따지고 보면 lim(n^2)와 lim(n) 그리고 lim(logn)도 n이 무한대로 가면
결과는 무한대로 같지만,
logn에 비해서 n이 압도적으로 크고, 마찬가지로 n에 비해서 n^2이 압도적으로 크다.
그렇기 때문에 최고차항만 남기고 나머지는 모두 생략해서 표기한다.
체감을 해보자.
n = 3일때, n^2 = 9, n = 3, (int)logn = 0이다.
(이때, log의 밑은 10)
하지만 n = 10000 이라고 한다면?
n^2 = 100000000, n = 10000, (int)logn = 4이다.
(이때, log의 밑은 10)
즉, n이 커지면 커질수록 세 수의 차이는 크게 차이가 난다.
시간복잡도가 O(logn)인 알고리즘을 처리하는데 4번의 연산이면 될 것이
O(n)은 10000번, O(n^2)은 100000000번의 연산이 필요한 것이다.
n값이 더 커진다면 체감은 더욱 커질 것이다.
한번더 생각해보자.
2^32 = 2147483648이다.
이 값이 n이라고 생각한다면
O(n)의 시간복잡도를 가지는 알고리즘을 처리하는데 2147483648초가 걸리는데
O(logn)의 시간복잡도를 가지는 알고리즘으로 처리하면 단 32초가 걸린다. (이때, log의 밑은 2)
엄청나게 체감이 되지 않는가?
효율적인 코드를 짜고 개선하는데 이렇게 시간복잡도가 필요한 것이다.
자료구조 별 시간복잡도
자료구조는 구성이 다르다.
예를 들어보자.
ArrayList 같은 경우 연속된 메모리를 할당하기 떄문에
접근을 하는데 O(1)의 시간밖에 걸리지 않는다.
그러나 중간의 원소를 삽입하거나 삭제하는 경우 데이터를 옮겨줘야하기 때문에
이 때에는 O(n)의 시간이 걸린다.
하지만 LinkedList 같은 경우 불연속적인 메모리를 연결해서 사용하는 것이기 때문에
접근, 탐색을 하는데 O(n)이 걸린다. (탐색을 시작, 끝에서 시작해야한다. 무조건.)
하지만 삽입, 삭제를 하는데에는 그렇게 많은 연산이 필요하지 않아서 O(1)의 시간이 걸린다.
이렇게 상황에 따라서 다른 자료구조를 사용하는 것이 유리하다.
자료구조의 평균 시간복잡도를 나타내면?
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열 | O(1) | O(n) | O(n) | O(n) |
| 스택 | O(n) | O(n) | O(1) | O(1) |
| 큐 | O(n) | O(n) | O(1) | O(1) |
| 연결 리스트 | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블 | O(1) | O(1) | O(1) | O(1) |
| 이진 탐색 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
| AVL 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
| 레드 블랙 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
자료구조의 최악 시간복잡도를 나타내면?
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열 | O(1) | O(n) | O(n) | O(n) |
| 스택 | O(n) | O(n) | O(1) | O(1) |
| 큐 | O(n) | O(n) | O(1) | O(1) |
| 연결 리스트 | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블 | O(n) | O(n) | O(n) | O(n) |
| 이진 탐색 트리 | O(n) | O(n) | O(n) | O(n) |
| AVL 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
| 레드 블랙 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
