[자료구조] # 03

 

 

1) primative type

2) user data type

 

1. 선형 데이터 구조

2. 비선형 데이터 구조 

 

- Abstract Data type

모델링 단계에서는 관심있는 분야까지만 생각하고 관심없는 분야는 생략해라.

 

---

 

- 알고리즘이란?

thing들을 잘 표현한게 데이터 스트럭쳐고 action은 알고리즘이다.

 

- 세타 표기법 (Tight bound) == 빅오 표기법

주어진 알고리즘의 상한과 하한이 같은지 아닌지를 결정한다.

알고리즘 평균 수행시간은 항상 하한과 상한 사이에 존재한다.

만약 상한과 하한이 같다면 세타 표기법 역시 같은 증가율을 갖는다.

 

 

- 오메가 표기

: 빅오와 반대되는 개념, '최선의 경우' 라고 한다.

빅오가 '넌 언젠가 내 안의 함수보다 작아질거야' 라면, 오메가는 '넌 언젠가 내 함수보다 커질거야' 라고 하는 거

 

- 세타 표기

세타는 빅오와 오메가의 공통 부분임

최소와 최악의 중간인 평균적인 복잡도

' 넌 내 안의 함수와 동등한 비율로 증가해' 라고 의미하는 것