[시간 복잡도] 빅오 표기법[Big O notation]

1. Big O notation 정의

 

알고리즘의 연산 횟수를 대략적으로 표기한 것이다. 상한으로 표기한다.

 

 

함수의 상한을 표시한다.

 

정리하자면 Big O 표기법은

1. 상수항(c)를 무시한다.

2. 영향력 없는 항을 무시한다.

 

예를 들어보자.

 

f(n) = 2n^2 + 3n + 1 → O(n^2)

f(n) =  3n^2 + 5nlogn → O(n^2)

f(n) = n(1000) + 3^n → O(3^n)

f(n) = 2n! + 5^n → O(n!)

 

 

 

2. Big O 표기법의 빠른 정도

 

O(1) -> O(logn) -> O(n) -> O(nlogn) -> O(n^2) -> O(n^k) -> O(k^n) -> O(n!)

O(1)이 가장 빠르다.

 

 

 

3. 대표적인 시간 복잡도

 

1) O(1)

- 배열의 n번째 원소에 접근

 - Stack에 push/pop

- Queue에 삽입/삭제

- Hash Table의 원소에 접근

 

2) O(logn)

- 이분 탐색 알고리즘

 

3) O(n)

- for, while loop

 

4) O(nlogn)

- 병합 정렬

- 퀵 정렬

- 힙 정렬

 

5) O(n^2)

- 버블 정렬

- 선택 정렬

- 삽입 정렬

 

6) O(2^k)

- 피보나치

 

 

https://gusdnd852.tistory.com/95

 

 

7) O(n!)

- nPr (조합)

- nCr (순열)

 

 

 

4. 추가 개념

빅오 표기법 외에도 빅 세타 표기법, 빅 오메가 표기법이 있다.

 

 

1) Ω(n) [빅 세타 표기법]

 

알고리즘의 하한을 표기한다. 즉, 알고리즘의 최상의 실행 시간, 가장 빠른 실행 시간을 표기한다.

 

 

 

 

예) n >=0 일 때, 2n + 1 >= n 이므로 Ω(n)이다.

 

 

2) Θ(n) [빅 오메가 표기법]

 

상한과 하한을 동시에 표기한다. 즉, 알고리즘 평균 실행 시간을 표기한다.

 

 

 

 

예) c1|g(n)| <= |f(n)| <= c2|g(n)|을 만족하는 3개의 상수 c1, n0, c2가 존재할 때,

f(n) = Θ(g(n))이다.

 

 

 

출처

이 글은 스터디원 분의 글을 정리해서 작성한 글입니다.