알고리즘 분석

1. 개요

알고리즘 분석은 알고리즘의 효율성을 평가하고 개선하는 데 사용되는 방법론으로, 실행 시간과 메모리 사용량과 같은 자원 사용량을 측정하고 예측하는 데 중점을 둔다. 알고리즘 분석은 균등 비용 모델과 대수 비용 모델을 사용하여 비용을 측정하며, 빅 오 표기법을 통해 알고리즘의 성장률을 표현한다. 실험적 측정은 알고리즘의 성능을 비교하는 데 한계가 있어, 알고리즘의 구조를 분석하고 단순화된 가정을 통해 실행 시간 복잡도를 평가하는 것이 중요하다. 한국은 IT 강국으로서 알고리즘 효율성이 사용자 경험과 기업 경쟁력에 중요한 영향을 미치며, 실용적인 측면에서 비효율적인 알고리즘 사용은 시스템 성능에 심각한 영향을 미칠 수 있다.

2. 비용 모델

알고리즘의 시간 효율성을 분석하려면 먼저 각 연산에 소요되는 비용을 정의해야 한다. 비용 모델은 알고리즘 분석의 기초를 이루는 중요한 개념이다.

시간 효율 추정은 한 단계를 무엇으로 정의하는지에 달려 있다. 실제 실행 시간과 분석 결과가 실질적으로 부합하려면, 한 단계 수행 시 요구되는 시간은 어떤 상수값 이하로 제한되어야 한다. 예를 들어, 두 숫자의 덧셈 연산을 한 단계로 간주할 때, 매우 큰 숫자를 계산하는 경우에는 덧셈에 필요한 시간을 더 이상 상수(constant)로 가정할 수 없다.

일반적으로 다음 두 가지 비용 모델이 사용된다:

* [[균등 비용 모델]](Uniform Cost Model): 모든 기계 작동에 대해 수의 크기와 관계없이 일정한 비용을 할당한다.
* [[대수 비용 모델]](Logarithmic Cost Model): 모든 기계 작동에 대해 관련된 비트 수에 비례하는 비용을 할당한다. 암호학 분야 등 임의 정밀도 연산 알고리즘 분석과 같이 필요한 경우에만 사용된다.

문제에 대해 발표된 하한(최적 실행 시간)이 실제 사용 가능한 연산 집합보다 더 제한적인 계산 모델에 대해 제시되는 경우가 많으므로, 처음 예상보다 더 빠른 알고리즘이 존재할 수 있다는 점을 유념해야 한다.

2.1. 균등 비용 모델 (Uniform Cost Model)

균등 비용 모델(uniform cost model)은 단위 비용 모델이라고도 하며, 관련된 숫자의 크기에 관계없이 모든 기계 연산에 일정한 비용을 할당하는 방식이다.

시간 효율을 추정할 때는 각 단계를 어떻게 정의하는지가 중요하다. 실제 실행 시간과 분석 결과가 의미 있게 부합하려면, 한 단계를 수행하는 데 걸리는 시간의 상한이 일정해야 한다. 예를 들어, 두 숫자의 덧셈을 한 단계로 가정하는 경우가 있다. 하지만 숫자가 매우 커지면 덧셈이 일정한 시간 안에 완료된다고 보장할 수 없다. 예를 들어, 종이와 연필로 2자리 숫자를 더하는 것과 1000자리 숫자를 더하는 것을 비교해 보면, 후자가 훨씬 더 많은 시간이 걸리는 것을 알 수 있다.

균등 비용 모델에서는 이러한 숫자의 크기 차이를 고려하지 않고, 모든 연산에 동일한 비용을 할당한다.

2.2. 대수 비용 모델 (Logarithmic Cost Model)

대수 비용 모델(logarithmic cost model)은 각 기계 작동에 대해, 계산되는 숫자의 비트 수에 비례하는 비용을 할당하는 방식이다. 이는 균등 비용 모델과 비교된다.

대수 비용 모델은 사용하기 더 복잡하기 때문에, 임의 정밀도 산술 알고리즘(예: 암호화에 사용되는 알고리즘) 분석과 같이 필요한 경우에만 사용된다.

3. 실행 시간 분석

실행 시간 분석은 알고리즘의 입력 크기가 증가함에 따라 실행 시간이 얼마나 늘어나는지 예측하고 분류하는 이론적인 방법이다. 컴퓨터 과학에서 알고리즘의 효율성은 매우 중요하며, 프로그램의 실행 시간은 어떤 알고리즘을 사용하느냐에 따라 크게 달라질 수 있다. (알고리즘의 실행 시간을 실측하여 분석하는 것은 성능 분석이라고 한다).

3.1. 실험적 측정법의 단점

알고리즘의 실행 시간을 실제로 측정하는 실험적 방법에는 여러 가지 문제점이 있다. 알고리즘은 플랫폼 독립적이므로 (즉, 주어진 알고리즘은 임의의 컴퓨터에서 임의의 운영 체제와 임의의 프로그래밍 언어로 구현될 수 있다), 여러 알고리즘의 성능을 비교하기 위해 실험적 접근법을 사용하는 것은 심각한 문제를 야기할 수 있다.

예를 들어, 크기가 n인 정렬된 리스트에서 특정 항목을 찾는 프로그램을 생각해 보자. 최신 컴퓨터 A에서는 선형 검색 알고리즘을 사용하고, 훨씬 느린 컴퓨터 B에서는 이진 검색 알고리즘을 사용한다고 가정해 보자. 두 컴퓨터에서 각 프로그램을 벤치마크 테스트하면 다음과 같은 결과를 얻을 수 있다.

이러한 측정값을 바탕으로 컴퓨터 A가 컴퓨터 B보다 훨씬 효율적인 알고리즘을 실행하고 있다고 결론 내리기 쉽다. 그러나 입력 리스트의 크기가 충분히 커지면 이 결론은 완전히 틀리게 된다.



선형 검색 프로그램을 실행하는 컴퓨터 A는 선형 증가율을 보인다. 프로그램의 실행 시간은 입력 크기에 정비례한다. 입력 크기를 두 배로 늘리면 실행 시간도 두 배로 늘어나고, 입력 크기를 네 배로 늘리면 실행 시간도 네 배로 늘어난다. 반면에 이진 검색 프로그램을 실행하는 컴퓨터 B는 로그 증가율을 나타낸다. 입력 크기를 네 배로 늘리면 실행 시간이 상수만큼만 증가한다(이 예에서는 50,000 ns). 컴퓨터 A가 겉으로는 더 빠른 기계이지만, 컴퓨터 B는 훨씬 느린 증가율을 가진 알고리즘을 실행하고 있기 때문에 결국 컴퓨터 A의 실행 시간을 능가하게 된다.

따라서 알고리즘의 실행 시간을 분석할 때는 이론적인 접근이 필요하다.

3.2. 성장률 (Order of Growth)

성장률(Order of growth^영어)은 알고리즘의 입력 크기가 커짐에 따라 실행 시간이 늘어나는 정도를 나타낸다. 이를 표현하는 표준적인 방법으로 빅 오 표기법이 사용된다. 빅 오 표기법은 알고리즘의 최악의 경우, 평균적인 경우, 최선의 경우를 모두 나타낼 수 있다.

비공식적으로, 어떤 알고리즘의 실행 시간이 특정 입력 크기를 넘어설 때, 양의 상수와 함수의 곱으로 상한을 정할 수 있다면, 그 알고리즘은 함수의 차수에서 성장률을 보인다고 할 수 있다. 즉, n₀보다 큰 입력 크기 n과 상수 c에 대해, 알고리즘의 실행 시간은 c × f(n)보다 결코 크지 않다.

예를 들어, 삽입 정렬은 입력 크기가 커짐에 따라 실행 시간이 2차 함수적으로 증가하므로, O(n²) 차수라고 할 수 있다.

빅 오 표기법은 알고리즘의 최악의 경우를 표현하는 편리한 방법이지만, 평균적인 경우를 표현하는 데에도 사용할 수 있다. 예를 들어, 퀵 정렬의 최악의 경우는 O(n²)이지만, 평균 실행 시간은 O(n log n)이다.

만약 실행 시간이 t ≈ kn^a (k는 상수) 법칙을 따른다고 가정하면, 실행시간 {t₁, t₂}과 문제 크기 {n₁, n₂}의 실험적 측정을 통해 계수 a를 찾을 수 있다. t₂/t₁ = (n₂/n₁)^a 이기 때문에, a = log(t₂/t₁) / log(n₂/n₁) 과 같다. 즉, 실행시간-문제크기의 로그-로그 그래프에서 실험적 라인의 경사도를 측정하는 것이다.

만약 증가 차수가 실제로 다항식의 미적분을 따른다면, 실험적 a 값은 다른 범위에서 상수로 유지될 것이고, 아니면 바뀔 것이다. 다음 표는 이러한 예시를 보여준다.

위 표에서 첫 번째 알고리즘은 선형 차수 증가를 보이지만, 두 번째 알고리즘의 실험적 값들은 급격히 감소하며, 다른 증가 규칙을 따른다는 것을 알 수 있다.

3.3. 실행 시간 복잡도 평가

알고리즘의 최악의 경우 실행 시간 복잡도는 알고리즘의 구조를 분석하고 단순화된 가정을 통해 평가할 수 있다. 다음 의사 코드를 통해 실행 시간 복잡도를 분석하고, 빅 오 표기법으로 표현하는 과정을 단계별로 살펴보자.

```
1 입력에서 양의 정수 n을 가져온다
2 if n > 10
3 print "시간이 좀 걸릴 수 있습니다..."
4 for i = 1 to n
5 for j = 1 to i
6 print i * j
7 print "완료!"
```

각 단계별 실행 시간을 T₁, T₂, ..., T₇로 가정한다. 1, 2, 7단계는 한 번씩 실행되고, 최악의 경우 3단계도 실행된다고 가정하면, 1~3단계와 7단계를 실행하는 데 걸리는 총 시간은 다음과 같다.

:$T\_1\; +\; T\_2\; +\; T\_3\; +\; T\_7\; \backslash ,$

4, 5, 6단계는 루프이므로 평가가 더 복잡하다. 4단계의 외부 루프는 (n + 1)번 실행되므로 T₄(n + 1) 시간이 걸린다. 내부 루프는 i 값에 따라 1부터 i까지 반복한다.

내부 루프의 실행 시간은 등차수열로 표현할 수 있다.

:$T\_6\; +\; 2T\_6\; +\; 3T\_6\; +\; \backslash cdots\; +\; (n-1)\; T\_6\; +\; n\; T\_6$

이를 인수 분해하면 다음과 같다.

:$\backslash left[\; 1\; +\; 2\; +\; 3\; +\; \backslash cdots\; +\; (n-1)\; +\; n\; \backslash right]\; T\_6\; =\; \backslash left[\; \backslash frac\{1\}\{2\}\; (n^2\; +\; n)\; \backslash right]\; T\_6$

내부 루프의 테스트(5단계) 실행 시간도 비슷하게 계산할 수 있다.

:$\backslash begin\{align\}$
& 2T_5 + 3T_5 + 4T_5 + \cdots + (n-1) T_5 + n T_5 + (n + 1) T_5\\
=\ &T_5 + 2T_5 + 3T_5 + 4T_5 + \cdots + (n-1)T_5 + nT_5 + (n+1)T_5 - T_5
\end{align}

이를 인수 분해하면 다음과 같다.

:$\backslash begin\{align\}$
& T_5 \left[ 1+2+3+\cdots + (n-1) + n + (n + 1) \right] - T_5 \\
=& \left[ \frac{1}{2} (n^2 + n) \right] T_5 + (n + 1)T_5 - T_5 \\
=& \left[ \frac{1}{2} (n^2 + n) \right] T_5 + n T_5 \\
=& \left[ \frac{1}{2} (n^2 + 3n) \right] T_5
\end{align}

따라서 전체 실행 시간은 다음과 같다.

:$f(n)\; =\; T\_1\; +\; T\_2\; +\; T\_3\; +\; T\_7\; +\; (n\; +\; 1)T\_4\; +\; \backslash left[\; \backslash frac\{1\}\{2\}\; (n^2\; +\; n)\; \backslash right]\; T\_6\; +\; \backslash left[\; \backslash frac\{1\}\{2\}\; (n^2+3n)\; \backslash right]\; T\_5$

이를 정리하면 다음과 같다.

:$f(n)\; =\; \backslash left[\; \backslash frac\{1\}\{2\}\; (n^2\; +\; n)\; \backslash right]\; T\_6\; +\; \backslash left[\; \backslash frac\{1\}\{2\}\; (n^2\; +\; 3n)\; \backslash right]\; T\_5\; +\; (n\; +\; 1)T\_4\; +\; T\_1\; +\; T\_2\; +\; T\_3\; +\; T\_7$


함수에서 가장 높은 차수 항이 증가율을 결정하므로, 이 예시에서는 f(n) = O(n²)이다.

이를 증명하면 다음과 같다.

> $\backslash left[\; \backslash frac\{1\}\{2\}\; (n^2\; +\; n)\; \backslash right]\; T\_6\; +\; \backslash left[\; \backslash frac\{1\}\{2\}\; (n^2\; +\; 3n)\; \backslash right]\; T\_5\; +\; (n\; +\; 1)T\_4\; +\; T\_1\; +\; T\_2\; +\; T\_3\; +\; T\_7\; \backslash le\; cn^2,\backslash \; n\; \backslash ge\; n\_0$
>


> $\backslash begin\{align\}$
> &\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7\\
> \le &( n^2 + n )T_6 + ( n^2 + 3n )T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \ (\text{for } n \ge 0 )
> \end{align}
>


> k를 [T₁..T₇] 보다 크거나 같은 상수라 가정하면
>


> $\backslash begin\{align\}$
> &T_6( n^2 + n ) + T_5( n^2 + 3n ) + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le k( n^2 + n ) + k( n^2 + 3n ) + kn + 5k\\
> = &2kn^2 + 5kn + 5k \le 2kn^2 + 5kn^2 + 5kn^2 \ (\text{for } n \ge 1) = 12kn^2
> \end{align}
>


> 그러므로 $\backslash left[\; \backslash frac\{1\}\{2\}\; (n^2\; +\; n)\; \backslash right]\; T\_6\; +\; \backslash left[\; \backslash frac\{1\}\{2\}\; (n^2\; +\; 3n)\; \backslash right]\; T\_5\; +\; (n\; +\; 1)T\_4\; +\; T\_1\; +\; T\_2\; +\; T\_3\; +\; T\_7\; \backslash le\; cn^2,\; n\; \backslash ge\; n\_0\; \backslash text\{\; for\; \}\; c\; =\; 12k,\; n\_0\; =\; 1$

더 간단하게, [T₁..T₇]를 모두 하나의 단위 시간으로 가정하면 실행 시간은 다음과 같이 간소화된다.

> $4+\backslash sum\_\{i=1\}^n\; i\backslash leq\; 4+\backslash sum\_\{i=1\}^n\; n=4+n^2\backslash leq5n^2\; \backslash \; (\backslash text\{for\; \}\; n\; \backslash ge\; 1)\; =O(n^2).$

3.4. 다른 자원들의 증가 비율 분석

실행 시간 분석 방법은 메모리 공간과 같은 다른 자원의 증가 비율을 예측하는 데에도 활용될 수 있다. 예를 들어, 컴퓨터 파일 크기에 기반하여 프로그램의 메모리 사용량 관리 및 재할당을 수행하는 다음 의사 코드를 보자.

```
while (파일이 열려 있는 동안)
let n = 파일 크기
for 파일 크기가 100,000 킬로바이트 증가할 때마다
예약된 메모리 양을 두 배로 늘린다
```

이 경우, 파일 크기 n이 증가함에 따라 메모리는 지수적 증가 비율로 소모되며, 이는 O(2ⁿ) 차수이다. 이는 매우 빠르고 관리 불가능한 메모리 자원 소모 증가 비율이다.

4. 알고리즘 분석의 중요성

알고리즘 분석은 알고리즘의 효율성을 판단하고 개선하는 데 필수적인 도구이다. 비효율적인 알고리즘은 시스템 성능 저하, 과도한 자원 소비, 결과의 지연 또는 무용화를 초래할 수 있다. 특히, 한국처럼 IT 인프라가 고도화되고 경쟁이 치열한 환경에서는 효율적인 알고리즘의 중요성이 더욱 강조된다.

실행 시간 분석은 알고리즘의 입력 크기(일반적으로 n으로 표기)가 증가함에 따라 실행 시간의 증가를 평가하고 추정하여 알고리즘을 이론적으로 분류하는 것이다. 실행 시간 효율은 컴퓨터 과학에서 중요한 관심사이다. 프로그램이 완료되기까지 몇 초가 걸릴지, 몇 시간이 걸릴지, 1년 이상 걸릴지는 구현된 알고리즘에 따라 달라진다.

방대한 데이터를 처리하는 경우, 비효율적인 알고리즘은 (그 시점의 컴퓨터 사양과 비교하여) 시간이나 기억 공간을 낭비하여 쓸모가 없을 수 있다.

"실행 시간이 중요한 용도이기 때문에"라는 이유만으로 알고리즘에 심혈을 기울이는 것은 대개는 쓸데없는 짓이다. 예를 들어 탐색에 대해, 데이터 수가 적은 경우에는 배열에 모든 데이터를 넣고 처음부터 찾는 단순한 구현이 실행 시간이 가장 짧은 경우가 많다.

5. 점근적 분석과 실제 성능

알고리즘 분석은 주로 점근적 성능, 즉 입력 크기가 무한대로 커질 때의 성능에 초점을 맞춘다. 그러나 실제 응용에서는 상수 인자도 중요하며, 실제 데이터는 항상 크기가 제한되어 있다. 예를 들어, 32비트 장치는 4GiB의 메모리, 64비트 장치는 16EiB의 메모리 용량 제한을 갖는다. 따라서 제한된 크기에서는 시간 또는 공간의 증가 차수를 상수 인자로 대체할 수 있으며, 충분히 큰 상수나 충분히 작은 데이터에 대해 모든 실제 알고리즘은 O(1)이 된다.

이러한 점은 매우 느리게 증가하는 함수에서 특히 유용하다. 예를 들어, 반복 로그(log^*)는 실제 데이터(2⁶⁵⁵³⁶ 비트)에서 5보다 작고, 이진 로그-로그(log log n)는 거의 모든 실제 데이터(2⁶⁴ 비트)에서 6보다 작으며, 이진 로그(log n)는 거의 모든 실제 데이터(2⁶⁴ 비트)에서 64보다 작다. 따라서 실제 데이터에서는 상수 시간이 아닌 알고리즘이 상수 시간 알고리즘보다 더 효율적일 수 있다.

하지만 점근적으로 비효율적인 알고리즘이 작은 크기의 데이터에서는 더 효율적일 수 있다. 이러한 점을 활용하여 Timsort와 같은 하이브리드 알고리즘은 입력 크기에 따라 다른 알고리즘을 사용한다. Timsort는 점근적으로 효율적인 합병 정렬을 사용하지만, 작은 데이터에서는 점근적으로 비효율적인 삽입 정렬로 전환한다.

다음은 크기 n의 정렬된 리스트에서 특정 항목을 찾는 프로그램의 예시이다. 컴퓨터 A는 선형 검색 알고리즘을, 컴퓨터 B는 이진 검색 알고리즘을 사용한다.

처음에는 컴퓨터 A가 더 빨라 보이지만, 입력 크기가 커지면 컴퓨터 B가 더 효율적이 된다.



컴퓨터 A는 선형 증가율을, 컴퓨터 B는 대수적 증가율을 나타내기 때문이다.

6. 한국의 특수한 상황

한국은 높은 인터넷 보급률과 모바일 사용률을 가진 IT 강국이다. 이러한 환경에서 알고리즘의 효율성은 사용자 경험에 직접적인 영향을 미치며, 기업의 경쟁력을 좌우하는 중요한 요소가 된다. 특히, 온라인 게임, 전자상거래, 스트리밍 서비스 등 실시간 상호작용이 중요한 분야에서는 알고리즘의 최적화가 필수적이다.