Chapter 2. Algorithm Analysis

1. Algorithm이란?

컴퓨터를 이용하여 문제를 해결하는 잘 정의된 절차

 

알고리즘 풀이 전략

1. Problem : 입력과 출력을 정의한다.
2. Strategy : 환경에 따른 알고리즘 설계 기법을 정의한다. Ex) 메모리 비중이 큰 경우 Time cost보다 Memory Cost에 중점을 두어 알고리즘을 설계한다. 이때, Problem이 달라지면 전략 역시 달라질 수 있다.
3. Algorithm : 절차를 세운다. Ex) PseudoCode
4. Analysis : Correctness, Time/Space 성능, Optimal Check와 같은 분석
5. Implementation : 구현
6. Verification : Test를 진행하는 검증 단계

2. Analysis

우리는 알고리즘이 최적인지를 알기 위해 수행시간 혹은 공간을 분석한다.

우리는 기본적으로 RAM 모델에서 알고리즘을 분석한다. 이는 메모리가 충분하고 1개의 프로세서와 메모리 접근 시간이 모두 동일한 컴퓨터 모델이다.

예를 들어, 교수님이 홍길동을 찾을 때 한번에 하나씩 비교하여 n번의 탐색을 할 수 있고 - One Processor,

교수님이 출석을 불러 1번에 탐색 할수 있다. - 병렬 Processor

즉, 알고리즘은 어떤 모델을 사용하냐에 따라 수행 연산수가 다르다.

 

기본연산의 클럭이 모두 같다는 전제하에 기본연산의 실행횟수를 세는것으로 알고리즘의 실행시간을 측정한다. 여기서 클럭이 같다는 의미는 실행시간이 같다는 의미를 가지며, 기본연산의 실행횟수는 곧 일의 양을 의미한다.

기본연산이란 보통 사칙연산, 비교, 메모리 대입/읽기를 말한다.

 

보통 Input Size가 작으면 실행 시간이 오래 걸리지 않지만, 크기가 클 경우 문제가 되어 Input Size를 기준으로 수행 시간 / 사용 공간이 얼마나 되는지 함수[연산 횟수]로 표현한다.

3. Analysis

Asymptotic Analysis

점근분석은 상수, 작은 입력을 무시하고 연산 횟수가 큰 증가율을 기준으로 분석하는 방식이다.

 

Amortized Analysis

평소 실행 시간이 작지만 특정 Case에서 실행 시간이 크다면 점근 분석의 Worst Case는 실행 시간이 큰것에 의존한다. 하지만 이는 자주 일어나는 경우가 아닌 가끔 일어나므로 아깝다.

 

정의 : 연속된 연산을 수행하면서 최악의 경우가 발생 했을 때 그 연산의 평균 비용이다

• n번의 총 연산시간 / n이며 이는 최악의 상황이 일어나도록 구성한다.

우리는 "Accounting Method"방식을 이용해 평균비용을 구한다.

Amortized Cost = Actual Cost + Accounting Cost : 매월 넣는 금액 = 실제 금액 + 계좌에 입근/뺼 돈이다.

 

Example)

은행에 매월 말 1, 1, 2, 1, 1, 3 ~ 반복 [Actual Cost] 이런 형태로 계좌에서 가져가고, 매월 초 우리가 일정금액[Amortized Cost]을 입금 한다고 했을 때를 가정하자. 단 이때 매월 말 통장에 Actual Cost만큼 금액이 없는 경우가 일어나서는 안된다. 쉽게 생각하면 매월 3씩 입금하면 돼지만 아깝다!

 

Example)

Vector의 Array Doubling

배열의 원소가 꽉찼을 때 크기를 2배로 하여 공간을 재할당 한다. 이후 모든 원소를 Transfer하는 작업을 수행한다. 이떄 한원소가 이동하는데 t의 cost가 든다고 가정하자.

 

벡터는 STL로 구현시 배열을 사용한다. 배열의 공간이 꽉차면 크기를 2배로 재할당[ArrayList는 1.5배 할당]한다. 배열 크기의 1/4 데이터를 가지면 크기를 1/2로 줄인다.

 

[그림 1] Array Doubling 시각화

Doubling이 일어나는 최악의 상황은 지속해서 Push 연산이 일어난다. 이는 총 tn + tn/2 + tn/4 + --- = 2tn만큼의 transfer cost가 생성된다. 또한 각 연산마다 n번의 push가 일어나므로

Amortized Cost = (2tn + n) / n = 2t + 1

이때, Doubling이 일어나지 않았을 때 Actual Cost 는 1이며 통장에 2t만큼 저금을 하고

Doubling이 일어났을 때 Actual Cost는 tn + 1이며 통장에서 -tn + 2t만큼 빼온다.

4. 성능분석

Experimental Studies

실험 분석으로 이론분석보다 좀 더 정확한 측정 결과를 얻을 수 있다. 하지만 구현 후 분석을 해야하므로 시간, 비용면에서 비효율적이다. 또한 입력한 크기에 대해서만 실행시간을 나타내고 그 이후의 값들은 모르는 단점이 있다.

만약 2개의 알고리즘을 분석하기 위해서 같은 HW, SW가 준비되어야 한다.

 

Theoretical Analysis

HW, 개발 언어 등 외적요인이 모두 동일하다는 가정하에 분석을 진행한다. 가능한 Input을 다 따지는것이 아니라 논리적으로 예측하여 분석을 진행한다.

5. 표기법

1. Big-O Notation

O(g) : 함수 g보다 더 느린 함수들의 집합이다. 이는 Worst case 분석시 자주 사용된다.

예를 들어 어떤 알고리즘은 아무리 안 좋아도 g(n)의 연산보다는 빠르거나 같다. 즉, 최악의 경우 g(n)이다.

[그림 2] Big O

2. Big-Omega Notation

Ω(g) : 함수 g보다 더 빠른 함수들의 집합이다. 이는 문제의 복잡도 분석시 자주 사용된다.

예를 들어 어떤 알고리즘은 아무리 좋아도 g(n)의 연산보다는 느리거나 같다.

 

[그림 3] Big Omega

3. Big-Theta Notation

Θ(g) = O(g) ∩ Ω(g)

6. Complexity

1. Worst Complexity Case

여러 입력 중 기본 연산 횟수의 총합이 최대가 되는 복잡도이다.

[그림 4] Worst Complexity 정의

2. Average Complexity Case

모든 입력의 평균적으로 수행한 연산 수를 나타내는 복잡도이다. 입력이 일어날 확률 x 그때 연산 수의 합으로 나타낸다.

이때 각 입력에 대해 일어날 확률을 예측하지 못하지만 우리는 입력들이 일어날 확률이 모두 같다는 가정하에 진행한다.

 

예를 들어 한 학생이 교실의 30개의 자리 중 맨 앞자리를 선택할 확률은 1/30은 아닐 수 있다. 이 학생이 창가 근처 자리를 선호 할수도, 혹은 뒷자리를 선호 할수도 있기 때문이다.

[그림 5] Average Complexity 정의

 

7. Optimality

우리는 알고리즘이 최선인지를 알기 위해 수행시간을 분석하였다. 지금 우리는 이 알고리즘이 더 좋아질수는 없나를 알기 위해 최적성에 대해 공부를 한다.

 

Complexity of Problem [문제의 복잡도]

문제에는 고유의 복잡도가 존재하며 어떤 문제를 풀기 위한 일의 최소양을 뜻한다. [Big-Omega 이용]

 

해결 방식

1. Algorithm의 Class를 결정한다. -> RAM 가정
2. W(N) 최악 연산 수를 계산한다.
3. F(N) 문제의 복잡도를 계산한다.

당연히 W(N)이 F(N)보다 크거나 같지만 최대한 비슷하게 증가율을 맞출수록 좋은 알고리즘이다. 만약 W(N)과 F(N)이 같다면 정말 좋은 알고리즘일 수도 있지만 F(N)을 잘못 구해 더 Lower Bound를 찾을 수도 있다.

Ex) 대수 비교 알고리즘은 최대 O(n logn) 보다 좋아질 수 없다.

 

[그림 6] Average Complexity Example

 

[그림 7] Order Array Seq Search Average Complexity Example

[그림 8] Bineary Search Example

[그림 9] Optimal Binary Search Check Example

[그림 10] Binary Search Proof Example