자료구조(2/10) - 빅오 표기법, ADT

빅오

 

어떤 자료구조가 다른 자료구조에 비해 성능이 좋다고 이야기할수 있는 방법은?

어떤 기준을 설정하고 두 함수를 상대적으로 비교하는것

 

 

다시) 자료구조: 데이터를 저장하는 구조

데이터를 저장하는 방식(함수들의 조합)이 자료구조마다 다른데

 

함수 내에 있는 반복문, 분기문의 실행횟수, 혹은 덧셈이나 곱셈 같은 연산 횟수 등을 세면 실제 물리적인 실행 환경 말고,  추상적으로? 성능을 개략적으로 어떻다고 판단할수 있다.  

 

입력값 n에 대해 이러한 연산횟수는 방정식T(n)으로 표기할수 있는데, 

알고리즘 성능을 분석할때는 점근적 표기법을 주로 사용한다. 

 

2n+3이라는 T(n)이 있을때 2n+3 = O(n) => 즉 2n+3의 빅오는 n이다라고 말할 수 있다.

                                                         (n은 어느시점에서 반드시 2n+3보다 크다)

 

                                   2n+3 = O(n^2) => 2n+3의 빅오는 n^2라고 말할 수 있다.

 

 

                                                    ... 이런식으로 어느시점에서는 반드시 큰값이 있기때문에 

 

 

2n+3 = O(2n+3) 이라고 생각하는게 속시원하다. (극한.. 개념을 쓸수 있을거같은데 쓸데없이 깊어지므로 패스..)

 

 

입력값 n에 대해 T(n)의 빅오,O(T(n))이 작을수록 성능이 좋겠쥬?

 

 

O(logN) < O(N) < O(NlogN) < ..    < O(N^2) < ... < O(N^3)

 

 

대표적으로

O(logN) : 트리계열의 자료구조의 삽입, 탐색, 삭제

O(N): 연결리스트의 탐색연산

O(NlogN): 퀵정렬, 병합정렬

 

O(N^2): 이중 for문

O(N^3): 삼중 for문

 

 

 

ADT 추상자료형

 

객체지향의 은닉처럼, 자료구조를 이야기할때 

필요한 값들의 집합, (입력값, 리턴값..) + 사용되는 연산만으로 이야기하는 방법

 

 

자료구조와 알고리즘에서 사용하는 언어.. 같은거라고 생각하면 될듯