알고리즘3. 알고리즘과 문제 분석

1. Analyzing Algorithms and Problems: Principles and Examples

 

1-3. Analyzing Algorithms and Problems 알고리즘과 문제 분석

 

 Analyzing Algorithms and Problems

알고리즘을 분석하는 이유

1. 알고리즘 개선(☞R&D(Research and development)영역)

2. 문제를 풀 수 있는 다양한 알고리즘 중 가장 최적의 알고리즘을 선택하기 위해(☞사용자 측면. 누군가 개발한 알고리즘을 사용)

 

알고리즘 분석 요소

- Correctness 정확성

- Efficiency 효율성

• Amount of work done(시간 복잡도 Time Complexity)
• Space used(공간 복잡도 Space Complexity)

- Optimality, Simplicity 최적성, 간결함

 

Correctness 정확성

알고리즘은 inputs (preconditions)을 outputs (postconditions)으로 변환하는 데 필요한 연산, 명령, 실행문 등의 일련의 단계로 구성된다. 

출처: 위키백과 <함수>

증명

• precondition (전제조건)을 만족한다면, 알고리즘이 종료될 때 postconditions (사후조건)은 참이 됨을 증명할 수 있어야 함.
• 알고리즘 구현 시 루프문을 자주 이용 → *루프 불변성을 사용해서 correctness 증명 가능

*루프 불변성 loop invariant

• 알고리즘이 타당함을 증명하기 위해 사용된다.
• 프로그램의 루프 반복 전 precondition이 참이었다면, 루프 실행 이후 postcondition도 참이어야 한다. 
• 수학적 귀납법과 유사

 

Amount of Work Done 시간 복잡도

일의 양 측정

• 일의 양을 측정함으로써 알고리즘의 효율성을 측정할 수 있다. 
• 일의 양 측정 시 이론적인 방법을 사용한다. 따라서 일의 양은 컴퓨터 하드웨어, 프로그래밍 언어, 프로그래머의 능력, 기타 디테일한 구현 내용에 독립적으로 분석 가능하다. 
• input size(주로 n으로 표현)에 영향을 많이 받는다.

 

Basic Operation

• Primitive Operation(사칙연산, %, 비교연산 등) 중에서 문제의 기본 연산을 선택

ex. 비정렬 탐색 알고리즘의 비교 연산

if(K==E[index])	//basic operation

• Basic Operation으로 두 개 이상의 연산을 선택할 수 있다. 
• 일의 양을 측정하기 위해 해당 알고리즘에서 사용하는 Basic Operation의 수를 카운트한 후 n에 대한 함수로 나타낸다.

알고리즘의 수행에 영향을 미치는 input의 특성 파악

입력의 특성이나 제한 조건이 문제마다 조금씩 다를 수 있으며, 이로 인해 알고리즘의 효율이 달라질 수 있다. 

 

Worst-Case Complexity

• 가장 보수적인 분석 방법.
• 아무리 늦어도 해당 시간 안에는 알고리즘 수행 가능

• Dn : input data. 문제에서 고려하는, size가 n인 모든 input들의 집합
• I : Dn의 임의의 한 원소. 입력으로 주어지는 특정 사례(Instance)라고 이해할 수도 있다. 
• t(I) : 특정 input I에 대해서 알고리즘이 수행하는 Basic Operation의 수
• 알고리즘의 Worst-Case Complexity W(n) = max {t(I) | I ∈ Dn} : 사이즈가 n인 임의 입력에 대해 알고리즘이 수행하는 Basic Operation의 최대 수
• 입력에 따라 알고리즘의 효율이 달라지며, 이러한 입력은 알고리즘에 따라 다르다. 

 

Average Complexity ★(이해가 잘 안 될 수 있으니 여러 번 복습)

Average-case analysis

• Average: Worst case와 Best case 사이의 대략적인 평균
• 다양한 임의의 데이터들에 대해 평균적으로 이 수행시간 안에 수행가능(기대 가능한 시간. / 산술평균이 아님)

• Pr(I) : 특정 input I가 발생할 확률
• t(I) : 그때 사용한 Basic Operation 수
• ∑ : 발생할 수 있는 경우들을 모두 더해준다. 
• 알고리즘을 분석함으로써 t(I)를 결정할 수 있다.(Basic Operation의 수를 세기만 하면 됨)
• 그러나 Pr(I)은 알고리즘을 분석함으로써 정확한 계산을 할 수가 없다.→ 통계적 수치를 이용하거나, 또는 가정을 통해 분석 진행.(알고리즘에서는 우선적으로 모든 사건이 발생할 확률을 동등하다고 가정한다. ex. 주사위에서 1 - 6의 숫자가 나올 확률은 1/6로 모두 같다고 가정)

 

Average-Behavior Analysis e.g.

비정렬 배열 탐색 알고리즘의 예

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;

 

Average Complexity | 발생 가능한 모든 경우의 수를 따져준다. 

Average Complexity = (탐색 성공 확률 * 성공 시 평균 수행 시간) + (탐색 실패 확률 * 실패 시 평균 수행 시간)

☞ 문제에 따라 알고리즘의 식은 조금씩 달라질 수 있다. 

 

 

탐색 성공 시 average complexity

위의 average complexity 공식 이용.

• 비정렬 배열의 인덱스 0부터 n-1까지 모두 탐색에 성공할 수 있으므로 i의 범위는 0부터 n-1까지이다.
• i + 1번의 비교 연산이 필요하다. 

E : 입력된 배열

K : 사용자가 입력하는 임의의 수

 

만약 K의 값이 5라면, 0번째 배열과 한번, 1번째 배열과 한 번, 2번째 배열과 한 번, 총 3번의 비교가 필요하다.

 

(탐색 성공 시) I 확률.

배열의 사이즈가 n이므로 K는 n개의 성공case를 갖는다. K가 임의의 인덱스에서 발견될 확률이 모두 동등하다고 가정했을 때 각 배열에 K가 존재할 확률은 1/n.

(각 인덱스 별 확률을 모두 합치면 1이 됨)

 

수행시간 계산 결과.

 

 

탐색 실패 시 average complexity

(탐색 실패 시 ) 입력 I 확률.

K가 배열에 없는 경우 1가지 밖에 없다.

 

n-1개의 배열을 모두 비교하고 난 뒤에야 배열에 K가 존재하지 않는다는 것을 알 수 있다. 따라서 비교횟수는 n회.

 

수행시간 계산 결과.

 

 

*A(n) 정리

탐색에 성공할 가능성을 q, 실패할 확률을 (1-q)로 두었을 때, 최종 평균 수행시간은

q[(n + 1) / 2] + (1 - q)n

 

노트 정리

 

 

Space Usage and Simplicity

Space Usage 메모리 사용량

 

- 특정 input에 따라 사용되는 메모리 공간이 달라진다면 Space complexity에 대해서도 worse-case와 average-case 분석 가능

(그러나 특정 input에 따라 메모리 공간의 사용량이 달라지는 알고리즘은 일반적이지는 않음)

ex.

• int a; 변수 선언 ☞ 4byte : O(1) space (상수 크기의 공간 사용)
• int *a = new int[n]; 동적할당 사용 ☞ O(n) space (input size n의 일차식에 비례하는 크기의 공간 사용)
• 이차원 배열의 경우 ☞ O(n²) space

- 대부분의 경우 Time / Space는 Trade-off반비례 관계

(시간 효율성을 높이면 공간 효율성이 작아지고 시간 효율성을 낮추면 공간 효율성이 높아진다)

 

Simplicity 간결성

1. 불필요한 연산이 없으므로 알고리즘 correctness에 대한 증명을 더 쉽게 할 수 있다. 

2. 가독성이 좋기 때문에 프로그램의 작성, 디버깅, 수정이 더 쉽다. 

 

 

Optomality 최적성

• 각 문제는 고유의 복잡도를 가지고 있다. 즉, 문제를 해결하기 위한 최소한의 작업량(Basic Operation 수)이 존재한다. 
• 문제의 복잡도를 분석하기 위해서는

        1. 해당 문제에 대한 Basic Operation을 선택해 주어야 한다.

        → 이를 class of algorithms(문제를 해결하기 위해 사용하는 연산들의 타입을 명시)을 선택한다고도 표현한다.

        2. 적어도 이 정도는 필요하다는 생각으로 문제의 Basic Operation 수를 카운트하면 이것이 문제의 complexity가 된다.

        3. 이를 통해 실제로 문제를 해결하기 위해 얼마나 많은 Basic Operation이 필요한지 알 수 있다. 

 

Optimal

"the best known" vs "the best possible"

• "the best known" : 현재까지 알려진 알고리즘 중 best
• "the best possible" : 아직 개발되지 않은 알고리즘을 포함해서 best (지향)

 

How to Show an Algorithm is Optimal

효율적인 알고리즘 A를 개발했다고 가정해 보자.

 

알고리즘의 최악의 수행시간 W

input size n에 대한 A의 worst-case complexity는 다음과 같은 함수로 표현할 수 있다.

함수 F (문제복잡도)

• input size n에 대한 알고리즘은 적어도 F(n)단계를 수행해야 한다.
• 알고리즘에서 수행하는 연산과 동일한 연산들의 class를 고려한다.

 

만약 W(n) = F(n)이라면?

• 알고리즘 복잡도와 문제 복잡도가 동일할 시 해당 알고리즘은 optimal하다.
• 두 함수가 서로 일치하지 않는다면, 더 효율적인 알고리즘이 존재하거나 더 좋은 lower bound(문제 복잡도)가 존재할 수 있다.

 

*알고리즘 복잡도의 upper bound, 문제 복잡도의 lower bound

 

upper bound

• 주황색 실선: 알고리즘이 아무리 복잡해도 A 시간 안에 해결이 된다는 것이 보장됨.
• 노란색 실선: 이후 더 효율적인 알고리즘이 등장한다면 해당 알고리즘은 A보다 빠른 시간 내 해결이 가능하다. 
• 새로 개발한 알고리즘이 아무리 복잡해도 그 복잡도는 기존 알고리즘과 같거나 더 효율적이다.
• 따라서 알고리즘의 복잡도를 upper bound로 표현한다.

 

lower bound

• 파란색 실선: 문제마다 고유의 복잡도가 존재한다.
• 이러한 고유한 복잡도를 처음부터 정확히 계산할 수 없으므로 프로그래머는 초기에는 F를 대략적으로 파악한다.
• F를 추가적으로 증명해가는 과정에서 필요한 연산의 수가 더 많아질 수 있다. 
• 이때 F는 문제를 해결하는 데 필요한 최소 연산을 뜻하므로 문제 복잡도를 lower bound로 표현한다.

 

 

Optimal Example: Devise A

문제

• 정렬되지 않은 n개의 원소를 가진 배열에서 최댓값 찾기
• input: 정렬되지 않은 n개 정수 배열
• output: 최댓값 정수

 

알고리즘 A

int findMax(int[] E, int n)
1. int max;
2. max = E[0]; // Assume the first is max.
3. for (index = 1; index < n; index++)
4. if (max < E[index])	// Basic Operation
5. max = E[index];
6. return max;

 

 

Optomal Example: Find W(n)

Basic Operation

배열의 요소를 다른 배열 요소 또는 저장된 변수(최댓값)와 비교

 

 

Worst-Case Analysis

- input size가 n인 배열이므로 인덱스 1부터 n-1까지 n-1번의 비교가 필요하다. 

max값은 계속 갱신된다

☞ W(n) = n-1

 

 

Optimal Example: Find F(n)

Class of Algorithms (어떤 연산을 허용할 것인가? 즉, operation type)

A는 숫자를 비교 및 복사할 수 있다. 그 외 다른 작업은 수행하지 않는다.

따라서 class of Algorithms = 비교 연산, copy 연산

 

Finding (or proving) F(n) 문제복잡도 증명 ★(이해가 잘 안 될 수 있으니 여러 번 복습)

- 배열의 모든 숫자 entry가 다르다고 가정

• worst case에서의 lower bound를 찾을 수 있게 한다.
• 편리한 증명을 위해 가정을 이렇게 하지만, 중복 값이 존재하더라도 해당 문제 복잡도 적용 가능

- n개의 다른 entry 중에서, n-1개는 최댓값이 아니다.

- entry가 최댓값이 아니라고 결론 지으려면 해당 entry는 적어도 하나 이상의 다른 entry보다 작아야 한다. 그리고 이를 위해 한 번의 비교(Basic Operation)가 필요하다.

- 따라서 적어도 n-1개의 Basic Operation이 필요하다.

☞ F(n) = n-1

 

따라서 W(n) = F(n)

알고리즘 A는 optimal하다. 

 

* 두 값이 같을 때도 optimal이지만 점근적으로 같을 때도 optimal이다.

ex. W(n) = n + 5, F(n) = n + 19999 

☞ 둘 다 빅오로 표기할 시 O(n)이므로 optimal이라고 표현 가능

 

 

 

 

---

자료 출처

Computer Algorithms

(Sara Baase, Allen Van Gelder저, Addison Wesley, 2000)

 

 

 

---

 

공부할 때 추가로 참고하면 좋을 블로그

https://johngrib.github.io/wiki/average-complexity/

평균 계산 복잡도 구하기