[자료구조] Ⅰ-5,6,7. 알고리즘 성능 분석, 복잡도

5. 알고리즘

● 알고리즘이란 문제를 풀기 위한 방식으로, 예시로는 10장의 카드가 무작위로 펼쳐져 있고 그 중 85를 찾기 위해 순서대로 찾기(Sequential Search - 순차탐색) , 반으로 나누어 중간과 먼저 비교하여 큰지 작은지를 통해 절반씩 탐색 범위를 줄여가며 찾기(Binary Search - 이진탐색), 가장 적은 수의 동전으로 거스름돈을 받기 위한 방법(그리디 알고리즘), 한붓 그리기 등이 있다.

● 알고리즘은 자료구조의 기본적 연산을 구현하기 위한 것으로, 같은 자료라고 해도 어떻게 저장, 표현되느냐에 따라 사용 가능한 알고리즘이 달라지며 알고리즘의 성능은 자료구조에 종속된다.

● 알고리즘의 표현 방식

● 알고리즘의 조건

1) input: 외부에서 제공되는 자료 0개 이상

2) output: 적어도 1개 이상의 결과 생성

3) definiteness: 각 명령어는 의미가 명확해야 함

4) finiteness: 무한히 동작해서는 안됨

5) effectiveness: 불필요한, 오류 발생 연산(나누기 0과 같은) 을 포함해서는 안된다.

6. 알고리즘 성능 분석

● 프로그램 평가 기준: 성능 측정(machine dependent) , 성능 분석(machine independent)

(1) 공간 복잡도

1) Fixed Space Requirements(C) : 입출력의 특성과 무관하게 일정한 크기의 공간을 필요로 한다. 이는 프로그램의 실행에 필요한 기본적인 공간(instruction space(명령어 공간))으로 simple variable, fixed-size structured variable, constants 등을 위한 공간이다.

2) Variable Space Requirements(SP(I)): 입력의 특성에 따라 변하는 공간으로, 입출력의 수, 크기, 값들에 따라 달라진다. 예를 들어 recursive stack space(재귀함수에서 사용되는 스택 공간), formal parameters, local variables 등이 있다.

(2) 시간 복잡도

1) Compile Time(C): insance characteristics와 독립적으로, 컴파일 시 필요한 시간을 뜻하는데 이는 주로 알고리즘의 구조를 분석하고 코드를 변환하는데 필요한 시간을 나타낸다. 한번 컴파일이 되면 이후에 계속 실행됨.

2) Run(Execution) Time (Tp): 입력의 특성에 따라 달라지는 실행 시간으로, 알고리즘이 실행되는 동안 소요되는 시간을 뜻한다.

① System Clock을 이용하여 수행시간을 측정: 실제로 구현이 필요하다.

② 프로그램이 수행하는 연산의 횟수(명령문의 개수)를 계산: 직접 구현하지 않고서도 수행 시간을 분석할 수 있다.

● 시간 복잡도 함수 T(n)은 알고리즘이 수행하는 기본적 연산 횟수를 input size(n) 에 대한 함수로 표현하는 것으로, 연산 횟수를 계산하기 위해 프로그램을 여러 단계로 분할해야 한다. 이 때 프로그램 단계란, 의미있고 / 실행 시간이 인스턴스의 특성에 독립적인 프로그램 단위이다.