[Algorithm] 점근 표기법, 빅오 표기법(big-O notation)

점근 표기법

어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 방법

이것을 시간 복잡도, 공간 복잡도를 표현할 수 있다. 

 

시간 복잡도 : 알고리즘을 수행하는 데 걸리는 시간 효율성

공간 복잡도 : 알고리즘을 수행하는 데 걸리는 메모리 효율성

 

 

대표적 세 가지 유형의 점근 표기법

 

1. 빅 오(big-O) - 점근적 상한선(upper bound) 기준  

2. 빅 오메가(big-Ω) - 점근적 하한선(lower bound) 기준

3. 빅 세타(big-θ) - 점근적 평균 기준

 

예를 들어 복잡한 함수 f(n)이 있을 때, 실행시간이 가장 빠른게 하한, 실행시간이 가장 느린게 상한이라고 보면 된다.

 

빅 오(big-O) -> f(n) = O(g(n))

f(n)의 복잡도는 최악의 경우라도 g(n)보다 작거나 같다는 의미 

 

빅 오메가(big-Ω) -> f(n) = Ω(g(n))

f(n)의 복잡도는 최선의 경우라도 g(n)보다 작거나 같다는 의미 

 

빅 세타(big-θ) -> f(n) = θ(g(n))

f(n)의 복잡도는 g(n)의 범위 내에 있다는 의미 

 

 

 

---

빅오(big-O)

- 알고리즘의 시간 복잡도, 공간 복잡도를 나타내는 표기법

- 점근적 상한선

- 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용

- 빅오의 시간 복잡도는 최고차항만을 표기 (상수항 무시)

ex) 7n^2 + 3n + 6 이라면 n^2만 고려하고 나머지는 무시한다. -> 시간 복잡도를 O(n^2)으로 표기

 

 

---

빅오 표기법의 종류

 

• O(1) 

입력 값에 상관없이 항상 실행 시간이 일정하다. 

ex) 스택 push & pop, 해시 테이블 조회 & 삽입

 

----------------------------------------------- 실행 시간 영향 받음 -----------------------------------------------

• O(log n)

매우 큰 입력값에도 크게 영향을 받지는 않는다. 

필요한 단계들이 연산마다 특정 요인에 의해 줄어든다. 

ex) 이진 검색

 

• O(n)

입력값이 수행시간이 비례한다.

ex) for 문

 

• O(n log n)

효율적인 정렬 알고리즘

ex) 병합 정렬, 힙 정렬, 퀵 정렬, timsort 

 

• O(n^2)

비효율적인 정렬 알고리즘

ex) 이중 for문, 거품정렬, 삽입정렬, 선택정렬

 

• O(2^n)

n^2보다 2^n이 훨씬 크다. 

ex) 피보나치 수열(재귀)