[Data Structure] basic concepts

자료구조

프로그램(Software) = Data Structures + Algorithms is authored by Niklaus Wirth

Data Structure
데이터를 저장하거나 조직하는 특정한 방법, 논리적이나 수학적인 모델을 사용한다. (Array, Linked-List, Stack, Queue, Hash, Tree)

Algorithms
문제를 해결하기 위한 방법. 특정한 일을 수행하는 유한 집합. (Sort, Search, Numerical, Geometric, Greedy)

시스템 생명 주기

• 요구
  프로젝트의 목적을 명시하고, Input과 Output을 명시한다.
• 분석
  관리 가능한 문제로 분할 한다. 2가지 방식이 있는데, Bottom-Up & Top-Down 중 Top-Down을 사용함.
• 설계
  데이터 구조(Abstract Data Type), 알고리즘 , 언어 의존성
• 정제 및 코딩
  데이터 객체의 표현, 각각의 연산에 대한 알고리즘 작성
• 검증
  정확도 증명, 테스팅, 에러제거

Algorithm Specification

알고리즘은 특정한 일을 하는 명령의 유한 집합이다. 모든 알고리즘은 다음과 같은 5가지를 명세해야함.

• Input
  There are zero or more quantities that are externally supplied.
• Output
  At least one quantity is produced.
• Definiteness
  Each instruction is clear and unambiguous.
• Finiteness
  If we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after a finite number of steps.
• Effectiveness
  Every instruction must be basic enough to be carried out, in principle, by a person using only pencil and paper

추상 자료형(Abstract Data Type)

: (객체들의 명세 + 그 객체들에 작용하는 연산들의 명세)을 함께 선언하며, 그 선언이 (그 객체들의 표현 + 그 연산들 의 구현)과는 분리되어 있는 것.

" ::= " 표기는 "is defined as" 로 읽으면 됨.

Performance Analysis

• 성능 분석(Performance Analysis)
  기기와 무관하게 시간과 공간을 예측하는 것.
• 성능 측정(Performance Measurement)
  기기와 관련하여 실행 시간을 분석 하는 것.
• 공간 복잡도(Space Complexity)
  수행하는데 필요한 메모리의 크기
• 시간 복잡도(Time Complexity)
  수행하는데 필요한 연산 시간

공간 복잡도(Space Complexity) S(P) = c + S_P(I)

1. Fixed space requirements (denoted by c)
2. Variable space requirements (denoted by S_P(I))

시간 복잡도(Time Complexity) T(P) = c + Tp(n)

c : 컴파일 시간, Tp : 실행 시간, n : instance characteristics