1-3 수행시간의 점근표기법

자료구조 : (프로그램에서 저장하는 데이터에 대해 탐색, 삽입, 삭제 등의 연산을 효율적으로 수행하기 위해서)

일련의 동일한 타입의 데이터들을 정돈해서 저장한 구성체이다. 

 

추상데이터타입 : 데이터와 그 데이터에 대한 추상적인 연산들

- 구체적인 구현의 의미는 포함하고 있지 않다.

- 이 추상적인 데이터 타입을 구체적으롤 구현하는 것이 자료구조이다. 

 

추상데이터타입 : 자바 인터페이스 (윤곽)

자료구조 : 자바 클래스 (구조)

 

수행시간 분석

효율성 측정하는 게 중요해

1. 시간복잡도 : 수행시간은 짧고

2. 공간복잡도 : 메모리 공간은 덜 사용하는 게

더 효율적인 알고리즘

 

대부분은 공간복잡도 말구 시간복잡도로 구성

시간복잡도 측정은 어떻게 할까? 직접 재?? NO

 

시간복잡도 : 알고리즘 실행 동안 사용된 기본적인 연산 횟수를 입력 크기의 함수로 나타낸다.

* 기본연산 : 데이터 간의 크기 비교, 데이터 읽기 및 갱신, 숫자 계산과 같은 단순한 연산

 

 

4가지 수행시간 분석

최악의 경우 : 수행 시간이 가장 느린 경우를 분석 (Upper Bound : 이거보다 더 느려질 수는 없다.)

평균적인 경우 : 입력의 확률 분포를 가정하여 분석  (계산 어려움)

최선의 경우 : 수행 시간이 가장 빠른 경우를 분석 (Lower Bound : 이거보다 더 빠를 수는 없다.)

상각분석 : 일련의 연산을 수행하여 총 연산 횟수를 합하고 이를 연산 횟수로 나누어 분석 (대부분 수행시간이 짧은데 가끔 길게 소요되는 경우 사용한다)

 

- 주로 최악의 경우를 사용

 

점근표기법

가장 차수 높은 항만 고려해 수행시간 분석

빅오 : 상한 (최고 차항 데려와서 계수 제거하면 끝)

빅오메가 : 하한

빅세타 : 유사한 증가율 (빅오 = 빅오메가일 경우에 사용)

 

- 주로 빅오 사용