1. 추상 데이터 타입(ADT: Abstract Data Type)
프로그래머가 데이터 타입을 추상적으로 정의한 자료형
(어떤 자료를 다루고 이들에 대해 어떤 연산이 제공되는지를 기술)
-데이터나 연산이 무엇(What)인가를 정의함
-데이터나 연산을 어떻게(How) 구현할 것인지는 정의하지 않음
추상화(abstraction)-> 정보은닉기법(information hiding)-> 추상 자료형(ADT)
예) 가방(Bag)의 추상 자료형
-데이터(객체)
중복된 항목을 허용하는 자료의 모임
항목들 사이에 순서는 없지만 서로 비교할 수는 있어야 함
-연산 (추상 데이터 타입과 외부를 연결하는 인터페이스 :함수로 정의)
insert(e): 가방에 항목 e를 넣는다
remove(e): 가방에 e가 있는지 검사해 있으면 이 항목을 꺼낸다.
contains(e): e가 들어있으면 True를, 없으면 False를 반환한다.
count(): 가방에 들어 있는 항목들의 수를 반환한다.
: : = "~으로 정의된다"를 의미함
2. 알고리즘의 성능 분석 방법
1. 수행 시간 측정
알고리즘을 프로그래밍 언어로 작성해 실제 컴퓨터상에서 실행시킨 다음, 그 수행 시간을 측정함
두 개의 알고리즘의 실제 수행시간을 측정하는 것
실제로 구현하는 것이 필요함
동일한 HW/SW 환경에서 실행해야 함
2. 알고리즘의 복잡도 분석
알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지를 숫자로 표시
직접 구현하지 않고서도 수행시간을 분석하는 것
알고리즘이 수행하는 연산의 횟수를 측정하여 비교
일반적으로 연산의 횟수는 n의 함수
복잡도의 종류
+시간 복잡도(time complexity) 분석: 수행 시간 분석
+공간 복잡도(space complexity): 필요한 메모리 공간 분석 (요즘은 메모리 가격이 저렴해져서 잘 안함)
시간 복잡도 함수 T(n): 연산의 수를 입력의 개수 n의 함수로 나타낸 것