[자료구조] 자료구조와 알고리즘의 이해 (3) - 빅-오 표기법

 빅-오
 - 함수 T(n)에서 가장 영향력이 큰 부분이 어디인가를 따지는 것이다.
 - 이 때 사용되는 표기법에 대문자 O가 사용되기 때문에 빅-오라 한다.

 T(n) = n^2 + 2n + 1

 n이 증가함에 따라서 2n+1 이 미치는 영향은 미미해지므로 다음와 같이 간략화 할 수 있다.
 
 T(n) = n^2

 그리고 이를 빅-오 표기법으로 표현하면 다음과 같다.

 O(n^2)

 

 

 

 단순하게 빅-오 구하기
 - T(n)이 다항식으로 표현된 경우, 최고차항의 차수가 빅-오가 된다.
 - ex) T(n) = n^2 + 2n + 9 ▶ O(n^2)
 - ex) T(n) = 5n^3 + 3n^2 + 2n + 1 ▶ O(n^3)

 빅-오는 '데이터 수의 증가에 따른 연산횟수의 증가 형태'를 나타내는 표기법이다.

 

 

 대표적인 빅-오

 O(1)
 - 상수형 빅-오
 - 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘을 뜻한다.
 - 연산횟수가 고정인 유형의 알고리즘을 대표한다는 의미도 담겨 있다.

 O(logn)
 - 로그형 빅-오
 - '데이터 수의 증가율'에 비해서 '연산횟수의 증가율'이 훨씬 낮은 알고리즘을 의미한다.

 O(n)
 - 선형 빅-오
 - 데이터의 수와 연산횟수가 비례하는 알고리즘을 의미한다.

 O(n^2)
 - 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다.
 - 이중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다.
 - 즉, 중첩된 반복문의 사용은 알고리즘 디자인에서 그리 바람직하지 못하다.

 O(n^3)
 - 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다.
 - 삼중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다.

 O(2^n)
 - 지수형 빅-오
 - 사용하기에 매우 무리가 있는, 사용한다는 것 자체가 비현실적인 알고리즘이다.

 

빅-오 대소 정리

시간 복잡도 함수 그래프

 

 

---

 출처 : 윤성우, 「윤성우의 열혈 자료구조」, 오렌지미디어(2019), p34-p44