[자료구조] chap1. 자료구조와 알고리즘

1.1 자료구조와 알고리즘

 

- 자료구조: 스택(먼저들어온게 나중에나감), 큐(먼저들어온게 먼저나감), 리스트, 사전, 그래프, 트리

 

- 프로그램=자료구조+알고리즘

 

- 알고리즘의 조건: 입력-0개이상/ 출력-1개이상/명백성(명령어 의미 명확해야함), 유한성(한정된 수의 단계 후 반드시 종료), 유효성(각 명령어가 실행가능해야 함)

 

- 알고리즘 기술방법: 자연어(영어,한국어 등), 흐름도, 의사코드, 프로그래밍 언어

 

- 자료형(데이터의 종류): 정수, 실수, 문자열

 

1.2 추상 데이터 타입

 

- 추상데이터타입(ADT:abstract data type) 데이터 타입 추상적으로 정의한것): 데이터나 연산을 어떻게 적용할건지는 정의 안함. >정보은닉기법>추상자료형(ADT)

  ㄴ객체: 추상데이터타입에 속하는 객체 정의/ 연산: 이들 객체 사이의 연산이 정의(인터페이스 역할)

 

 

1.3 알고리즘의 성능 분석

 

- 알고리즘의 성능분석: 수행시간 측정(실제 구현 필요, 동일한 하드웨어 사용 필요), 알고리즘 복잡도 분석(직접 구현 필요x, 알고리즘의 수행연산횟수 측정, 일반적으로 연산횟수: n의 함수-입력의 개수에 따른 식)

  ㄴ복잡도분석 종류: 시간복잡도와 공간복잡도(수행에 필요한 메모리크기)

 

- 빅오표기법: 연산의 횟수를 점근적으로 표시(함수의 상한 표시)

   ㄴ모든 n>=n0에 대하여 |f(n)|<=c|g(n)| 을 만족하는 2개의 상수 c와 n0가 존재하면 f(n)=O(g(n)).

   ㄴ시간복잡도: 1  logn  n  nlogn  n^2  n^3  2^n  n!  (함수로 생각하면 직관적으로 와닿음)

  +빅오메가 표기법: |f(n)|>=c|g(n)| 을 만족하는 2개의 상수 c와 n0가 존재하면 f(n)=Ω(g(n)).

  +빅세타 표기법: 모든 n>=n0에 대하여 c1|g(n)|<=|f(n)|<=c2|g(n)|을 만족하는 3개의 상수 c1, c2, n0가 존재하면 f(n)=θ(n).함수의 하한인 동시에 상한 표시, f(n)=O(g(n))이면서 f(n)=Ω(g(n))이면 f(n)= θ(n).

 

-최선의 경우(의미x)-평균의 경우(계산어려움)-최악의경우(가장 널리사용, 계산 쉬움, 중요)= 수행시간 가장빠름-평균-늦음