알고리즘 성능 분석

Sep 20, 2021

알고리즘 성능 분석

🗣️ 출처

Introduction to Algorithm, 3rd, Cormen을 토대로 정리한 내용입니다.

알고리즘 비용에는 메모리, 통신 대역폭, 필요 하드웨어 등이 있겠지만, 가장 중요시 여기는 자원 기준은 역시 연산 시간이다.

사실, 알고리즘의 성능은 입력 값, 컴퓨터의 구조, 사용자의 목적에 따라 다르게 평가될 수 있지만, 일반적인 RAM 구조의 컴퓨터를 대상으로 한다.

알고리즘 성능 자세히 분석하기 : 삽입 정렬

다음과 같은 삽입 정렬 알고리즘을 예시로 분석해보겠다.

// 삽입 정렬 예시 코드
for j = 2 to A.length
    key = A[j]
    i = j - 1
    while i > 0 and A[i] > key
        A[i+1] = A[i]
        i = i - 1
    A[i+1] = key

각 코드의 연산 비용 합산 구하기

입력 크기를 n으로 설정한 뒤, 각 코드의 한번의 기본적인 연산이나 명령 수행의 시간적 비용을 $c_i$로 가정하고, 이를 연산 횟수와 곱하여 구해보자. (주석의 경우, 무시됨.)

순서	코드	비용	연산 횟수
1	for j = 2 to A.length	$c_1$	$n$
2	key = A[j]	$c_2$	$n-1$
3	i = j - 1	$c_3$	$n-1$
4	while i > 0 and A[i] > key	$c_4$	$\sum^n_{j=2}t_j$
5	A[i+1] = A[i]	$c_5$	$\sum^n_{j=2}(t_j-1)$
6	i = i - 1	$c_6$	$\sum^n_{j=2}(t_j-1)$
7	A[i+1] = key	$c_7$	$n-1$

• 첫번째 줄 코드 : 두번째 원소부터 연산을 시작하여, 입력 크기를 1 넘어가는 순간에 종료 조건이 만족되어 종료되므로, $n-1$이 아니라 $n$번 연산이다.

• 2, 3, 7번째 줄 코드: 첫번째 줄 코드가 종료 조건이 만족되는 순간을 제외하고 모두 연산되므로 $n-1$번 연산이다.

• 4, 5, 6번째 줄 코드: 마찬가지로 j가 2부터 $n$까지 $n-1$번의 연산을 거치겠지만, 각각의 연산은 미리 정렬된 부분배열의 원소들의 크기와 현재 A[j]의 비교 결과에 따라 달라지므로, $t_j$로 둘 것이다.

  • 연산 결과의 달라짐을 알아보기 위해, 오름차순으로 정렬의 극단적인 예 두가지를 들어보자.

    • A[j] 값이 5이고, 부분배열 A[1...j-1]이 [1,2,3,4]일 때 $\rightarrow$ 첫 번째 연산에서 종료조건이 만족되어 연산이 종료되므로 연산 횟수 $t_j$는 단 1번만 이루어진다.

    • A[j] 값이 0이고, 부분배열 A[1...j-1]이 [1,2,3,4]일 때 $\rightarrow$ A[j]는 맨 앞에 위치해야하므로, 연산은 부분 배열의 크기인 4번에 종료조건 확인을 위한 1번을 추가해 $t_j$는 총 5가 될 것이다.

• 5, 6번째 줄 코드 : 4번의 while문의 종료 조건이 만족될 때는 실행되지 않으므로 $t_j-1$번 수행된다.

이러한 연산들의 비용과 연산 횟수를 곱해서 모두 더하면 알고리즘의 총 비용, $T(n)$을 계산 할 수 있다.

\[T(n)=c_1n+c_2(n-1)+c_3(n-1)+c_4\sum^n_{j=2}t_j+c_5\sum^n_{j=2}(t_j-1)+c_6\sum^n_{j=2}(t_j-1)+c_7(n-1)\]

이러한 방법을 이용해 연산 비용 뿐만 아니라 메모리 사용량 등 또한 계산할 수 있다.

이상적인 상황과 최악의 상황에서의 삽입 정렬

$t_j$를 설명할 때 사용했던 이상적인 상황과 최악의 상황에 따른 성능을 알아보자.

이상적인 상황에서는 첫번째 연산에서 종료조건을 만족하므로 $t_j=1$일 때, 순서 5, 6 코드의 연산 횟수는 $\sum^n_{j=2}(1-1)$은 0이 되며, 나머지는 다음과 같이 계산 된다.

\[\displaylines{ T(n)=c_1n+c_2(n-1)+c_3(n-1)+c_4(n-1)+c_7(n-1)\\=(c_1+c_2+c_3+c_4+c_7)n-(c_2+c_3+c_4+c_7) }\]

이상적인 상황에서 삽입정렬은 다항식 $an+b$ 형태로, n에 대한 선형 함수가 된다.

최악의 상황에서의 삽입 정렬의 경우, 정렬된 부분 배열의 모든 원소에 대해 연산이 진행되므로 A[1...j-1]의 길이, 즉 j-1번의 자리 바꿈 연산과, 마지막 종료조건 확인 연산이 합해져, $t_j=j$가 되게 된다.

시그마 값들에 대입해 연산해보면,

\[\sum^n_{j=2}j=(\sum^n_{j=1}j)-1=\frac{n(n+1)}{2}-1\\ \sum^n_{j=2}(j-1)=\sum^{n-1}_{j=1}j=\frac{n(n-1)}{2}\]

알고리즘의 총 비용은 다음과 같이 된다.

\[\displaylines{ T(n)=\\c_1n+c_2(n-1)+c_3(n-1)+c_4 \left(\frac{n(n+1)}{2}-1\right)+c_5\left(\frac{n(n-1)}{2}\right)+c_6\left(\frac{n(n-1)}{2}\right)+c_7(n-1)\\=\left(\frac{c_4}{2}+\frac{c_5}{2}+\frac{c_6}{2}\right)n^2+\left(c_1+c_2+c_3+\frac{c_4}{2}-\frac{c_5}{2}-\frac{c_6}{2}+c_7\right)n -(c_2+c_4+c_5+c_8) }\]

최악의 상황에서 삽입정렬은 다항식 $an^2+bn+c$ 형태로, n에 대한 이차 함수(quadratic function)가 된다.

이러한 표기는 성능을 표기하는데 복잡하고, 정수의 입력값만 받기 때문에 사용되지 않고, 주로 점근적인 표기법인 시간복잡도를 이용해 표기한다.

현실적인 대회에서의 알고리즘 분석

대회의 성능 합격 기준은

• 연산 시간
• 메모리 사용량
  즉, 입력값의 양 $N$과 성능 제한을 비교하여 알고리즘의 합격 여부를 구현 이전에 예측 가능

시간 복잡도

보통의 CPU 구조의 개인 PC나 채점용 서버, C, C++ 언어 기준으로 대략 10억번의 연산에 1초 이상의 시간이 걸림.

⚠️ warning

다만, 컴파일러, CPU, 세부 구현 등에 따라 성능이 수십배 차이 날 수 있으므로, 절대 맹신하지 말자

예시

만약 입력값의 양 $N$이 최대 2,000이고, 시간 제한이 1초 이내인 문제에서 시간 복잡도 $O(n^3)$인 알고리즘을 구현했다면, 대략적인 연산량과 예상 연산 시간은 다음과 같다.

\[\displaylines{ operations\ = 2000^3 = 8,000,000,000\\ estimated\ operation\ time = 8,000,000,000 \times \frac{1s}{1,000,000,000}\approx8s }\]

시간 복잡도 $O(n^3)$의 알고리즘은 제한을 통과하지 못할 것이다.

따라서, 시간 복잡도가 $O(\log{n} \cdot n^2)$ 이하인 알고리즘을 구현해야할 것이다.
\(\displaylines{ operations\ = \log{2000} \cdot 2000^2 \approx 4.386\times 10^7 = 43,860,000\\ estimated\ operation\ time = 43,860,000 \times \frac{1s}{1,000,000,000}\approx0.44s }\)

평소에 알고리즘들의 시간복잡도를 미리 파악하고 정리를 통해 구현 시, 이를 기준으로 알고리즘을 바꾸거나 프루닝 등의 최적화를 고려하여 시간 절약 가능

시간의 측정

파이썬의 경우 다음과 같은 방식으로 수행 시간을 측정할 수 있다.

import time
start_time = time.time() # 측정 시
# 
# 당신의 알고리즘 코드
# 
end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력(초 단위)

파이썬은 C 계열 언어보다 느리므로 1초에 2000만 연산 정도, pypy3는 초당 1억번 연산으로 계산해도 된다.

공간 복잡도

메모리 사용량의 경우 MB 단위로 제시되는 경우가 많음. ex) 메모리 제한 128MB

대부분 문제는 정수형 자료형인 int의 배열을 이용하며 하나에 4byte임.

자료형 크기 파악

단, 컴파일러에 따라 자료형의 크기는 달라질 수 있으므로, 사용하는 기술의 자료형 크기를 미리 파악하자.

• Java, C 계열 int : 4 Bytes
  범위 : -2,147,483,648 ~ 2,147,483,647 ($-2^{31} \sim 2^{31}-1$)
• Java, C 계열 long long : 8 Byte
  범위 : -9223372036854775808 ~ 9223372036854775807 ($-2^{63} \sim 2^{63}-1$)

💡 tip

Java의 표준 혹은 C 계열의 외부 라이브러리인 BigInter 클래스를 이용하면 무제한의 범위를 가질 수 있다.

• C 계열 char : 1 Byte
  범위 : $-128 \sim 127$

• Java 계열 char : 2 Byte
  범위 : 0 ~ 65535

• Python 계열 int : 정수형의 제한 범위가 존재하지 않아 엄밀히 말하면 무제한 이지만, python3의 list 기준으로 정수 하나는 8 byte를 차지한다.

  즉 일반적으로 2배 정도 사용하지만, $O(n)$으로 비례하는 것은 같으므로 점근적으로 4byte로 보아도 무방하다.

  ```python
  import sys
  print(sys.getsizeof([0])) # 64
  print(sys.getsizeof([0 for i in range(10)])) # 184
  print(sys.getsizeof([0 for i in range(100)])) # 920
  print(sys.getsizeof([0 for i in range(1000)])) # 8856
  lst = []
  print(sys.getsizeof(lst)) # 56
  lst.append(1)
  print(sys.getsizeof(lst)) # 88 # 32만큼 증가
  lst.append(1)
  print(sys.getsizeof(lst)) # 88
  lst.append(2)
  print(sys.getsizeof(lst)) # 88
  lst.append(2)
  print(sys.getsizeof(lst)) # 88, 32만큼 증가
  lst.append(2)
  print(sys.getsizeof(lst)) # 120
  lst.append(2)
  print(sys.getsizeof(lst)) # 120
  lst.append(2)
  print(sys.getsizeof(lst)) # 120
  lst.append(2)
  print(sys.getsizeof(lst)) # 120
  lst.append(2)
  print(sys.getsizeof(lst)) # 184, 64 만큼 증가

  python의 `list`는 C++의 `Vector` 처럼 `list`의 크기를 미리 크게 잡아놓고, 사이즈 한도가 커질 때 마다 사이즈 증가량을 2배로 키우는 방식으로 증가한다.
- Python 계열 `str` : 무제한
만약, 기억나지 않거나 컴파일러가 생소한 경우 다음과 같이 직접 코드로 알 수 있다.

```c
#include <stdio.h>

int main()
{
    printf("char: %d, short: %d, int: %d, long: %d, long long: %d\n", 
        sizeof(char), 
        sizeof(short),
        sizeof(int),
        sizeof(long),
        sizeof(long long)
    );
    // char: 1, short: 2, int: 4, long: 4, long long: 8

    return 0;
}

예시

• int a[1000];: 4KB
• int a[1000000];: 4MB
• int a[2000][2000];: 16MB