[시간복잡도] 점근 표기법 - 2 | JusticeHui가 PS하는 블로그

빅-오 표기법

빅-오 표기법은 최악의 경우를 나타냅니다. 다시 말해 아무리 열악한 환경일지라도 빅-오 표기법으로 표현한 수준에서 종료됩니다.

표기 방법은 다음과 같습니다.
O(증가 함수) 증가 함수는 데이터의 크기에 대해 알고리즘의 수행 시간이 늘어나는 비율을 함수로 나타낸 것 입니다.

예를 들어 최대 수행시간이 5n^2 + 10n + 5 인 알고리즘이 있다고 하면,
가장 먼저 최고차항을 제외한 모든 항을 제거합니다. 그러면 5n^2 가 남습니다.
그리고 문자에 곱해진 계수를 제거합니다. 이러한 과정을 거쳐서 나온 증가 함수는 n^2입니다. 이것을 빅-오 표기법으로 나타내면
O(n²) 입니다.

최대 수행시간이 (n^2 / 2) 인 경우에도 위에서 설명한 과정을 거치면 최종적으로 나오는 증가 함수는 n^2가 됩니다.

꼭 알아야 할 것이 한 가지가 더 있습니다. O(n²) 는 상한 수행시간이 n^2를 넘지 않는 모든 증가 함수들의 “집합” 입니다. 5n^2 + 8이나 9n+17 같은 증가 함수는 모두 n^2를 넘지 않으므로 이들의 수행 시간은 O(n²) 라고 할 수 있습니다.

이 코드의 시간 복잡도를 분석해봅시다.

for(int i=0; i<n; i++){
    for(int j=0; j<i; j++){
        //do something...
    }
}

이 코드는 바깥쪽 for문이 n번, 안쪽 for문은 i번 돌아가며, i는 [0, n)범위입니다.
0부터 n-1까지 모두 더하면 n(n-1)/2 이고, 점근 표기법으로 나타내면 n²입니다.

빅-오메가 표기법

빅-오메가 표기법은 최선의 경우를 나타냅니다. 다시 말해 아무리 상황이 좋아도 빅-오메가 표기법으로 표기한 수준보다 빠를수는 없습니다.

표기법은 다음과 같습니다.
Ω(증가함수)
와 같이 표기합니다.

Ω(n²)은 O(n²)과 반대로 하한 수행 시간이 n^2보다 크거나 같은 증가 함수들을 부분 집합으로 가집니다. 9n^2 + 17n이나 3n^3 + n^2 + 15 같은 증가 함수는 모두 n^2보다 크거나 같기 때문에 Ω(n²) 집합에 포함됩니다.

빅-세타 표기법

마지막으로 빅-세타 표기법에 대해 알아봅시다.
빅-세타 표기법은 평균의 경우를 나타냅니다. 빅-세타 표기법의 증가함수는 빅-오 표기법(상한),과 빅-오메가 표기법(하한)을 모두 만족시키는 증가 함수입니다.
Θ( f(n) ) = O( f(n) ) ∩ Ω( f(n) )
빅-오 표기법은 자신의 증가 함수를 “넘어서지 않는” 모든 증가 함수를 포함하고,
빅-오메가 표기법은 자신의 증가 함수보다 “작지 않은” 모든 증가 함수를 포함합니다.
빅-세타 표기법은 위 두 표기법과는 다르게 자신의 증가율과 “같은” 증가 함수만을 포함합니다.

자주 사용하는 시간복잡도

아래 표는 자주 나오는 알고리즘과 시간 복잡도를 표현한 표 입니다.

증가함수	알고리즘
O(1)	해시 테이블
O(log n)	이진 탐색
O(n)	순차 탐색
O(n log n)	합병정렬, 퀵정렬
O(n²)	버블, 선택, 삽입 정렬
O(n³)	플로이드 와샬 알고리즘
O(2ⁿ)	하노이탑