* [DSnTA Review]는 Harry R. Lewis의 Data Structures and Their Algorithms를 읽고 정리한 내용을 모았습니다.

Abstract Data Type(ADT)

- 프로그래밍의 기본 원칙은 무엇을 하려고 하기 전에 그 "무엇"이 명확하게 이해함에 있다.

- 데이터의 표현에 앞서, 데이터에서 어떤 동작이 일어나는가를 살펴보아야 한다.

 

- Abstract Data Type(이하 ADT)은 일종의 자료구조(Data Structure)이거나 자료형(Data Type)이 아니다.

- ADT는 두가지로 이루어진다: domain과 operation

  - domain은 데이터의 집합을 의미한다.

  - operation은 domain에 속하는 임의의 element에 가해지는 연산이다.

- ADT는 세부 구현에 대해 고려하지 않는다. 즉 인터페이스만을 제공한다.

 

 

Algorithm Analysis

- 알고리즘은 컴퓨터를 이용하여 문제를 해결하기 위한 일종의 방법이다.

- 알고리즘의 중요 특성에는 유효성(effectiveness), 정확성(correctness), 종료 가능성(termination), 효율성(efficiency), 그리고 프로그램의 복잡도(program complexity)가 있다.

 

유효성(Effectiveness)

- 해당 알고리즘이 컴퓨터 프로그램으로 표현이 가능한가?

- 즉, 상식의 범주 내에서 이해가 가능하며(without leaps of imagination)

- 컴퓨터가 처리 가능한 동작만으로, (only operations that can be performed by a computer)

- 분명한 방식으로 처리가 가능한가? (in obvious way)

 

- 어떤 알고리즘이 컴퓨터 프로그램 언어로 기술되어 있다면 Effectiveness는 검증된 것

- 그렇지 않은 경우, 모호하지 않고 어려움 없이 분명한 코드로 번역될 수 있어야 함. 

정확성(Correctness)

- 알고리즘은 절대 잘못된 답을 내놓아서는 안된다. (Probabilistic Algorithm과 같은 경우는 논외)

종료 가능성(Termination)

- 모든 알고리즘은 모든 입력값에 대하여 종료될 수 있어야 한다.

효율성(Efficiency)

- 시간과 공간(여기서는 메모리)을 얼마나 효율적으로 사용할 수 있는가?

- 시간 효율성은 입력의 크기에 따라 실행시간이 얼마나 바뀔 수 있는가에 따라 결정된다.

- 실행 시간은 알고리즘에 내재된 특성에 따라 선형적으로, 혹은 지수적으로 바뀔 수 있다.

프로그램의 복잡도(Program Complexity)

- 프로그램은 계속 수정될 수 있다.

- 작성된 알고리즘은 변화를 주기 쉬워야 한다.