Big O?
어떠한 문제를 해결하는데에 사용되는 자료 구조와 알고리즘의 효율성을 설명하기 위한 것으로 수학적 개념을 차용하여 빅 오 표기법 이라 부른다.
알고리즘의 효율성을 평가할 때에는 두 가지의 기준으로 나뉘는데, 한정된 메모리 공간을 분석하는 공간 분석과 알고리즘이 어느 정도 빠른지 알아보는 시간 분석이 있다.
시간과 공간 복잡성을 계산할 때 최상, 최악, 평균 복잡성을 고려하게 되지만, 보통은 최악의 시나리오를 의미한다. 이는 비관적인 접근이 유용한 도구일 수 있기 때문이다. 알고리즘이 얼마나 비효율적인지 알면 최악을 대비함과 동시에 알고리즘의 선택에 중요한 영향을 미칠 수 있다.
빅 오의 본질
데이터 원소가 N개 일 때 알고리즘에 몇 단계가 필요할까?
빅 오가 진정 의미하는 것은 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는지를 뜻한다.
- 할당이나 변수 초기화와 같은 간단한 명령문은 O(1)의 복잡성을 지닌다. k개의 명령문이 있다면 O(k)가 된다.
- if-else 블록에서는 if가 O(1), else가 O(n)의 복잡성을 지녔을 경우 if-else 블록은 O(n)이 된다.
- 간단한 명령문을 포함하고 N번 반복되는 순환문에서는 순환문 내부 코드는 O(k) 이고 N번 반복된다 했을 때, 전체 코드는 O(n*k)이다.
- 중첩 순환문의 경우 외부 순환문이 O(n), 내부 순환문 O(n)이 되어 O(n^2)이다.
시간 복잡도
1) O(1)
상수형 알고리즘, 단 하나의 명령만 실행되어 어떤 값이 입력되든지 실행 시간이 항상 일정하다
2) O(n)
선형 알고리즘, 실행 시간이 데이터 양(n)에 비례해 증가
3) O(logn)
로그형 알고리즘, O(1)과 O(n)의 중간
데이터가 두 배로 증가할 때마다 한 단계씩 늘어난다.
여기에서 log가 사용되는 이유는 수학의 밑이 2인 logN과 같이 동작하기 때문이다. 2의 3제곱은 2*2*2 = 8 이므로, 밑이 2인 log8 = 3이다. 즉, O(logN)은 원소가 하나가 될 때까지 데이터 원소를 계속해서 반으로 줄이는 만큼의 단계 수가 걸린다는 뜻이다.
| 원소 개수(N) | O(N) | O(logN) |
| 8 | 8 | 3 |
| 16 | 16 | 4 |
| 32 | 32 | 5 |
| 64 | 64 | 6 |
4) O(nlogn)
선형-로그형 알고리즘, O(n)보다 좋지 않은 경우
대규모 데이터 입력 시 우수한 성능을 발휘한다.
5) O(n^2)
2차 알고리즘, 중첩된 두 개의 순환문의 경우
6) O(2^n)
지수형 알고리즘, 알고리즘이 각 단계별로 진행될 때마다 데이터 처리량이 두 배로 늘어나는 경우
7) O(n!)
팩토리얼형 알고리즘
참고 도서
누구나 자료구조와 알고리즘
코드 없는 알고리즘과 데이터 구조
스위프트 데이터 구조와 알고리즘
댓글