[자료구조] 분석 도구

자료구조(data structure): 자료를 구성하고 접근하는 체계적인 방법

알고리즘: 유한한 시간내에 어떤 일을 수행하는 단계적인 절차

 

보통 최악의 경우에 관한 실행시간을 특정 지음

최악의 경우에서 잘 수행되는 알고리즘에 대한 성공의 기준을 만드는 것은 모든 입력에서 잘 수행된다는 것을 필수적으로 요구한다!!

 

Big-Oh 표기법

위 식을 만족하는 실수 상수 c>0와 정수 상수 n0≥1이 존재한다면 f(n)을 O(g(n))이라고 한다!!

그니까 어떤 지점 n0에서부터는 아무리 나빠도 cg(n)보다 좋다는 상한을 의미한다!!! (=최악의 경우)

대충 이런 그래프!!

Big-Oh 표기법은 함수 증가에 영향을 미치는 주요 구성요소에만 초점을 맞추고 낮은 차수와 상수 인자는 무시할 수 있도록 허용한다.

이렇게 제일 큰 차수만 남겨놓을 수 있다!!

 

Big-Omega

빅오 표기법이 '어떤 함수보다 적거나 같다'라고 말하는 점근적 방법을 제공하는 것처럼, 빅 오메가 표기법은 함수가 어떤 함수보다 크거나 같은 것을 말한다!

빅오랑 똑같은데 부등호 방향만 다르다!! 이 함수가 아무리 좋아도 이 함수보다는 나쁘다는 것을 의미한다. (=최선의 경우)

이미지 출처: https://ko.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-omega-notation

Big-Theta

빅 오와 빅 오메가의 사이! 두 개의 함수가 상수인자까지도 같은 비율로 증가한다는 것을 말해주는 표기법이다.

f(n)이 O(g(n))이고 f(n)이 Ω(g(n)) 이라면 f(n)은 θ(g(n))이라고 한다!!

출처: https://ko.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation

 

---

참고 문헌

[1] Michael T. Goodrich, Roberto Tamassia, Davaid M. Mount, C++로 구현하는 자료구조와 알고리즘, WILEY, 2013.

[2] https://ko.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation