Algorithm Efficiency(알고리즘 효율성)

  저번 포스팅에서 알고리즘을 평가할 때 'Efficiency'라는 항목이 있었다. 이번에는 이것에 대해 자세히 알아볼 것이다.

---

Basic concepts Algorithm Efficiency

  Efficiency는 두가지로 나눌 수 있다.

• Time Efficiency(Time complexity): 얼마나 빠르게 알고리즘이 동작하는가?
• Space Efficiency(Space complexity): 알고리즘이 동작하는데 필요로하는 메모리 단위의 양

  우리는 알고리즘의 시간/공간 효율성을 파악하기 위해 general analytical framework를 따를 것이다. 그 전에 몇가지 질문에 대한 답을 확인해보자.

How to express the efficiency of an algorithm?

  우선, 알고리즘의 효율성을 어떻게 표현하는지에 대해 알아보자. 이를 위해 알고리즘에 대한 input size를 나타내는 일부 input parameter 'n'에 대한 함수로 표현할 수 있다.

  그렇다면 input parameter는 어떻게 측정할 수 있는지 알아야 한다. input에 둘 이상의 데이터 항목을 포함한다고 하면 input parameter size는 데이터 항목의 개수라고 할 수 있다. 만약 input이 하나의 데이터 항목만을 가진다면 해당 항목의 크기가 해당 알고리즘의 input size와 관련이 있다.

What is the unit(metric) to measure the running time of an algorithm?

  알고리즘의 실행 시간을 측정하는 단위는 무엇일까? 두 가지 케이스로 나눠보자.

  첫번째 경우는 실질적, 경험적으로 알고리즘을 분석할 때이다. 즉 평소 우리가 시간을 측정할 때 사용하는 단위인 sec, msec, ...을 사용하는 것이다. 하지만 프로그램의 속도는 컴퓨터, 알고리즘 구현의 quality, 코드를 생성하는 compiler의 quality마다 상이하다. 때문에 우리는 알고리즘에 대한 이론적 분석이 필요하다.

  이론적 분석, 말은 어려워 보이지만 중요한 건 해당 방법은 basic operation을 단위로 한다는 것이다. basic operation은 알고리즘 실행 시간의 대부분을 차지한다. 만약 탐색 알고리즘이라면 basic operation이 '찾는 값이 있는지 비교'하는 것일거고, 두 행렬의 곱을 구하는 알고리즘이라면 두 수를 곱하는 것이 basic operation이 될 수 있다. 때문에 이런 basic operation과 이것이 실행되는 횟수를 알아내면 알고리즘을 분석할 수 있다. 경험적 분석과는 달리 이론적 분석은 컴퓨팅 환경과는 무관하고 문제와 알고리즘의 본질에 의존한다. 즉, 확립된 이론적 분석은 입력크기 n에 대해 알고리즘의 basic operation이 실행되는 횟수를 계산하는 것이다.

Theoretical Framework to Analyze an Algorithm

  input size를 n이라고 하면, 알고리즘의 theoretical time complexity는 다음으로 표현될 수 있다.

• \(t_{bop}\): 단위 시간동안 특정 컴퓨터에서 알고리즘의 basic operation 하나를 수행하는데 걸리는 시간. 상수
• \(f(n)\): 알고리즘의 basic operation이 실행되는 횟수. basic operation의 실행빈도와 관련됨
• \(T(n)\): 특정 컴퓨터에 알고리즘이 적용된 전체 실행시간

  따라서 \(T(n) \approx t_{bop} * f(n)\)이라는 식을 얻을 수 있다. 보통 basic operation은 매우 빈번히 발생하기에(= n이 매우 큰 값), n값이 극도로 작으면 \(T(n)\)으로 알고리즘의 실행시간을 합리적으로 추정할 수 없다. 그리고 우리가 중점을 두고 있는 건 이론적 분석이다. 때문에 \(t_{bop}\)는 무시해도 된다. 그리고 n값이 매우 커지면 곱셈 상수는 실행 시간에 큰 영향을 미치지 않기에, 곱셈 상수도 무시한다. 따라서 \(f(n)\)의 차수만 고려하면 된다. 

 위의 내용을 예시로 이해해보자.

Ex1) 컴퓨터B가 컴퓨터A보다 10배 더 느리다면 동일한 알고리즘이 적용될 때, B의 실행속도는 A의 실행속도보다 얼마나 느린가?

: 너무나 쉽다. 당연히 B가 10배 더 느리다.

Ex2) 동일한 컴퓨터에서, 어느 알고리즘의 \(f(n)\)이 \(\frac{1}{2}n^2\)일 때, input size 두 배로 높이면 실행시간이 얼마나 더 길어지는가?

: \(T(2n)/T(n)\)을 하면 알 수 있다. \(4n^2/n^2\)이 되므로 input size를 두배로 높이지 않았을 때보다 4배 더 오래 걸린다.

  하지만 두 예시에서 각 \(f(n)\)의 n의 차수에는 차이가 없었다. 때문에 실제 실행속도는 차이가 있겠지만, 두 예시 모두 theoretical time complexity는 동일하다고 볼 수 있다.

Intuitive concept of order of complexity function

\(T(n)\)에 대해 더 알아보자. \(T(n) = 5n^2 + 100\)인 경우에는 \(5n^2\)부분만 고려하면 된다는 걸 이제는 알 수 있다. 그럼 \(T(n) = n^2 + 3n + 120\)일때는 어떻게 하면 될까? \(f(n)\)의 차수를 고려하면 되는데 해당 식에서는 이차항과 일차항이 존재한다. 여기서 n은 무수히 큰 수(=∞)임을 기억하자. 그렇게 된다면 최고차항이 \(T(n)\) 값에 지배적인 부분을 차지한다. 때문에 \(T(n)\)의 최고차항만 생각하면 되는 것이다.

<표1>

  흔하게 볼 수 있는 complexity classes이다. 밑에 행으로 갈 수록 n이 커질수록 \(T(n)\)값이 기하급수적으로 상승한다.

 

Precise definition of order of a complexity function using Asymptotic Notation

  여기서는 복잡도 함수를 비교하기 위해 사용하는 세가지 점근 표기법에 대해 알아볼 것이다. (표기문자)(g(n)) = c * g(n)  (c는 상수)라고 정의하고 가자.

O (Big-O): 작거나 같음

  특정 n이상부터 f(n)의 값이 O(g(n))의 값 이하면 O(g(n))은 f(n)을 포함(= 집합에 속함)한다. 즉 해당 알고리즘이 big-o로 표현된 시간보다 짧으면 된다. 극단적으로 말하면 f(n) = n이라면 O(g(n))은 \(n^2\)이나 \(n^5\)가 될 수도 있는 것이다.

Ω (Big-Omega): 크거나 같음

  O와는 반대되는 표현이다. 특정 n이상부터 f(n)의 값이 O(g(n))의 값 이상이면 Ω(g(n))은 f(n)을 포함한다. 즉 해당 알고리즘이 big-omega로 표현된 시간보다 길면 된다.

\(\theta\) (Big-Theta)

  사실 위에 두 표현법은 어찌보면 되게 쓸모가 없다고 볼 수 있다. O(n!)해버리던가 Ω(1)해버리면 거의 모든 f(n)에 대해 맞는 말이 되기 때문이다. 때문에 이 두 경우를 만족하는 \(\theta\)를 사용한다. 그냥 f(n)과 g(n)의 최고차항 계수가 같으면 성립한다(수학적 지식이 부족해서 log나 지수함수일 때 어떻게 표현할지 모르겠다...ㅠ <표1>을 참고해서 같은 형태의 모양을 가지면 성립한다고 생각하자)그리고 이 표현법이 실제로 우리가 사용하는 Big-O표기법과 동일하다. 길이 n의 일차원 배열의 탐색 알고리즘의 복잡도를 \(\theta(n)\)이 아닌 O(n)이라고 부르는 것처럼 말이다.

Using a Limit to Determine Order of Growth of a Complexity Funtion

  위에서 확인한 세가지의 점근 표기법은 동일한 문제에 적용된 서로 다른 두 알고리즘의 복잡성 함수를 비교할 때는 거의 사용되지 않는다. 그래서 이때는 두 함수의 극한의 비율을 판단하는 것이 가장 간단한 방법이다.

\(\lim_{n \to \infty}\frac{T(n)}{g(n)}\)의 결과값 c를 생각해보자.

• c = 0이라는 것은 g(n)의 성장률이 T(n)보다 클 때 성립한다. 즉 \(T(n)\in O(g(n))\)라고 할 수 있다.
• c > 0이라는 것은 T(n)과 g(n)의 성장률이 동일하다고 볼 수 있다. 즉 \(T(n)\in \theta(g(n))\)이라고 할 수 있다.
• c = \(\infty\)라는 것은 T(n)의 성장률이 g(n)의 성장률 보다 클 때 성립한다. 즉 \(T(n)\in \Omega(g(n))\)라고 할 수 있다.

Summary of Asymptotic notation

  상수 인자와 작은 input size를 무시하는 함수 비교 방법

• O(g(n)): n이 무한대로 갈 때, g(n)보다 성장률이 같거나 낮은 모든 함수 f(n)의 집합
• \(\Omega(g(n))\): n이 무한대로 갈 때, g(n)과 성장률이 같거나 높은 모든 함수 f(n)의 집합
• \(\theta(g(n))\): n이 무한대로 갈 때, 성장률이 동일한 모든 함수 f(n)의 집합

 

Mathematical Analysis of Iterative Algorithms

  이제 두가지 유형의 알고리즘을 수학적으로 분석해보자. 그 중에 하나인 iterative(반복) algorithm부터 살펴보자. '수학적'분석이지만 본인은 수학에 소질이 없으므로 서술 내용이 부정확할 가능성이 높다.

반복 알고리즘의 시간 효율성을 분석하는 순서

  분석에는 밑의 순서를 따른다. 감이 안잡힐수 있지만 이후 설명할 예시에 적용해보면 이해하는데 도움이 될 것이다.

1. input size를 나타내는 parameter n을 정한다.
2. 해당 알고리즘의 basic operation을 확인한다.
3. 기본 연산의 횟수가 문제의 인스턴스마다 다른 경우 n에 대한 worst, average, best cases를 결정한다.
4. basic operation이 실행되는 횟수의 합을 설정한다.
5. 공식 및 규칙을 이용하여 4.에서 구한 합을 단순화한다.

EX1. Maximum Element Problem

// 주어진 배열의 요소 중 가장 큰 값을 결정하는 문제
// Input: 실수로 이루어진 배열 A[0...n-1]
// Output: A의 요소 중 가장 큰 값
maxval <- A[0]
for i <- 1 to n-1 do
	if A[i] > maxval
    	maxval <- A[i]
return maxval

  알고리즘은 pseudo code로 적혀있다. 위에서 말한 순서대로 분석해보자.

1. input size: 배열의 요소의 개수(n)
2. basic operation: A[i]>Maxval (n값에 따라 수행횟수가 정해짐)
3. 해당 경우에는 어떤 경우든 basic operation 횟수가 n값에 따라 정해지므로 최악, 평균, 최선의 경우를 구분할 수 없다.
4. basic operation이 수행되는 총합을 구한다.
   • \(C(n) = \sum_{i=1}^{n-1}1\)
5. n이 무한대가 될 때 시간 복잡도 함수의 클래스를 찾기 위해 합을 단순화 한다. \(n-1 \in \theta(n)\)

  4.처럼 합을 정하면 급수 공식(summation formulas)을 참고하면 단순화하는데 도움이 된다.

EX2. Checking Uniqueness of elements of an array

// 주어진 배열의 모든 요소가 구분이 되는지(중복이 없는지) 결정하는 문제
// Input: 배열 A[0...n-1]
// Output: 모든 배열이 구분되면 "ture" 아니면 "false" 반환
for i <- to n-2 do
	for j <- i+1 to n-1 do
    	if A[i] = A[j] return false
return true

  여기서는 basic operation이 A[i]와 A[j]를 비교하는 것이다. 그리고 바깥 loop에서의 결정된 요소를 내부 loop에서 다른 요소들과 비교한다. 때문에 비교 횟수는 동일한 두 요소의 존재 여부와 그러한 원소가 위치한 index에 따라 달라진다. 즉 여기서는 n값이 같아도 instance마다 비교 횟수가 달라질 수 있다. 

  그럼 해당 경우의 best case는 무엇일까? 바로 동일한 두 원소가 배열의 첫번째, 두번째에 위치할 때이다. 그러면 한번의 basic operation 실행 후 바로 "false"를 반환한다. 반대로 worst case는 array의 요소가 모두 구분이 되거나 동일한 두 개의 원소가 배열의 가장 끝에 연달아 위치하는 것임을 예상할 수 있다.

  그럼 worst case의 basic operation 횟수의 합을 구해보면 \(C_{worst}(n) = \sum_{i=0}^{n-2}\sum_{j=i+1}^{n-1}1\)이다. 이를 단순화 하면 \(\frac{1}{2}n^2 \in \theta(n^2)\) 임을 확인할 수 있다.

Mathematical Analysis of Recursive

  이번에는 재귀 알고리즘에 대해 살펴보자.

재귀 알고리즘의 시간 효율성을 분석하는 순서

1.  
2. 1~3까지는 반복 알고리즘의 경우와 동일하다.
3.  
4. 기본 연산이 실행되는 횟수를 나타내는 적절한 초기 조건과 재귀 관계를 설정한다.
5. 위에서 설정한 반복 관계를 해결: 암시적 함수를 명시적 함수로 변경한다.
6. n이 무한대가 될 때 복잡도 함수의 클래스를 찾기 위해 명시적 함수를 단순화한다.

  글이 이해하기에는 어려운 것 같다... 설명을 덧붙이자면 재귀 알고리즘은 어떤 큰 문제가 있다면 이것을 더 이상 쪼갤 수 없을 만큼 작은 문제(초기조건)로 쪼개어 이것을 해결함으로써 점차적으로 큰 문제를 해결해나가는 것이다. 때문에 초기 조건과 재귀 관계를 제대로 설정하는 것이 중요하다. 역시 예시를 확인하는게 체감이 쉬울 것이다. 

EX. Factorial Problem: f(n) = n!

  문제에 대한 정의를 하고 넘어가자면 'n! = 1 * 2 * ... * (n-1) for n>=1 and 0! = 1'이다. 순차적으로 분석해보자.

1. input size는 n이라는 수다.
2. baisc operation은 곱셈(*)으로 설정하자.
3. n에 따라 횟수가 결정되므로 best, average, worst case는 따질 필요가 없다.
4. recurrence relation 설정: M(n)을 곱셈 연산의 횟수에 대한 함수라고 하자
   
   • 그렇다면 M(n) = M(n-1) + 1, M(0) = 0이라는 관계를 세울 수 있다.
   • 함수 f와 헷갈릴 수 있는데, f(n)이라는 결과값을 없기 위해 M(n)번의 곱셈이 필요한 것이다.
   • 그러므로 n=0이라면 f(0) = 1, M(0) = 0이다.

// ALGOLITHM F(n)
// Compute n! recursively
// Input: A nonnegative integer n
// Output: The value of n!
if n = 0 return 1
	else return F(n-1) * n

  위 처럼 알고리즘을 구체화할 수 있다. M(n)은 f(n)과 달리, n의 관점에서 명시적으로 정의되지 않고, n-1에서의 값의 관점에서 표현된다. 이것이 재귀 관계이다.

  5. backward substitution을 이용해 재귀 관계를 해결한다.

• M(n) = M(n-1) + 1 = M(n-2) + 2 = ... = M(n-i) + i(i번째 F 호출) = M(n-n) + n = n, 그러므로 M(n) = n이다. 

  6. n이 무한대로 갈 때 이를 단순화: \(M(n) \in \theta(n)\)

※ instance를 best, average, worst로 나눌 수 있다고 했는데 보통은 worst case를 우선적으로 고려한다. 다른 두 case를 우선하면 그 시간보다 오래 걸리는 instance가 존재할 수 있지만 worst case는 그것들을 모두 포함하기 때문이다.