1. Analyzing Algorithms and Problems: Principles and Examples
-알고리즘 & 문제 complexity 분석
1-1. Introduction
컴퓨터 알고리즘
상세한 단계별(step-by-step) 방법으로 유한 시간(finite time) 이내 컴퓨터를 이용해 문제를 해결하는 것
Problem Solving의 체계적 절차
Problem(문제 정의) > Strategy(문제풀이 전략) > Algorithm(알고리즘, 의사코드 서술) > Anaysis(서술한 알고리즘을 분석) > Implementation(구현) > Verification(검증)
1. Problem 문제 정의 ex. 비정렬 배열을 정렬하는 알고리즘
input : 5, 3, 67, 1, 2 -> n개의 정수
output: 1, 2, 3, 5, 67 -> 오름차순 정렬된 n개의 정수
2. Strategy 전략
3. Algorithm 알고리즘 서술(의사코드)
Input
Output
Step
세 가지 요소를 작성
4. Analysis 서술한 알고리즘 분석
Correctness 정확성
Time & Space 효율성(efficiency)
- Time(수행시간이 얼마나 빠른지)
- Space(storage usage, 저장공간을 얼마나 사용하는지)
Optimality 최적성
- 더 이상 빠르게 문제를 풀 수 없음
- 알고리즘 복잡도 = 문제 복잡도: Optimal algorithm
- 복잡도 complexity: 문제를 해결하기 위한 일의 양의 최솟값
Example: 비정렬 배열 탐색
Problem 문제정의
Input
배열 E(원소 n개를 포함, 원소들은 정렬되지 않은 상태)
Output
1. 특정 key K가 배열 내에 존재한다면, K의 인덱스를 출력
2. K가 배열 내에 존재하지 않는다면, -1 출력
Strategy 전략
- 남은 배열이 없을 때까지, 배열의 처음부터 끝까지 순차적으로 K와 비교
- 만약 K가 배열 내에 존재하지 않는다면, -1 출력
Algorithm 알고리즘 서술(의사코드)
Input
- E(배열)
- n(배열의 항목 갯수)
- K(찾는 key)
- → 모두 정수라고 가정
Output
- E에서 K의 위치인 ans를 반환(K를 찾지 못하면 -1 반환)
Algorithm: Step
int seqSearch(int[]E, int n, int K)
int ans, index;
ans = -1; //Assume failure.
for(index = 0; index < n; index++)
if(K==E[index]) //basic operation
ans = index; //success
break; //done
return ans;
Analysis 서술한 알고리즘 분석
<의사코드를 이용해 이론적 분석을 이용하는 이유>
- 실험적 방식을 사용하기 위해서는 알고리즘 구현이 필수적이다(프로그래머의 역량 필요)
- 테스트 케이스 이외의 input에 대한 실행결과를 알 수 없음
- 하드웨어 및 소프트웨어의 성능에 따른 실행결과의 차이 배제
- 모든 가능한 input에 대한 고려 가능
<알고리즘에 의해 수행된 일의 양을 측정하는 방법>
기본연산(primitive operation) 일일이 카운팅
- primitive operation: 컴퓨터 시스템이나 패키지 내에서 가장 근본이 되는 최소 단위의 연산으로서 마이크로 연산으로 간주되는 기본 연산. 원시 연산의 몇 단계가 모여 보통 하나의 매크로 연산으로 정의된다.(출처: 네이버 지식백과 it용어 사전) ex. memory access, +, - , *, /, %, store, ....
Basic Operation
- 해당 알고리즘에서 가장 기본이 되는 연산
- 해당 예제의 경우 basic operation은 비교연산
Worst-Case Analysis 최악의 수행시간
- 함수로 표현☞ W(n): 알고리즘이 임의의 input size n에 대해 수행하는 최대 기본 연산 수.
- 해당 예제의 경우, W(n) = n이다. → 최악의 경우(K가 배열의 인덱스 n-1에 존재할 시 or K가 배열 내에 존재하지 않을 시), 인덱스 0부터 n-1까지 n번 비교연산이 필요하다.
추가적인 알고리즘 분석 방법
- Average-Behavior Analysis 평균수행시간 비교
- Optimality
- Correctness
알고리즘 언어(의사코드 서술 방식)
- 언어제약이 없다
- 알고리즘의 각 단계는 pseudo-code로 명시되어야 한다.
- 지나치게 디테일한 내용을 작성하기 보다 문제 해결 시 전략이나 테크닉에 초점을 맞추어 영어식 표현으로 서술한다.
자료 출처
Computer Algorithms
(Sara Baase, Allen Van Gelder저, Addison Wesley, 2000)
'Computer Science > 알고리즘' 카테고리의 다른 글
알고리즘: Mergesort 합병 정렬 (0) | 2021.11.11 |
---|---|
알고리즘6. Searching on Ordered Array(정렬된 배열 탐색)(2) - binary search(이진탐색) (0) | 2021.10.03 |
알고리즘5. Searching on Ordered Array(정렬된 배열 탐색)(1) (0) | 2021.09.27 |
알고리즘4. 점근적 증가율에 따른 함수 분류 (0) | 2021.09.13 |
알고리즘3. 알고리즘과 문제 분석 (0) | 2021.09.07 |
알고리즘2. 수학적 배경지식 (0) | 2021.09.02 |