[알고리즘] 알고리즘 성능 분석

프로그램 성능에 관한 고려 사항

만약 코딩을 통해 어떤 프로그램이나 앱을 만들었는데, 예상보다 실행 속도가 느리다고 느껴진다면 느린 이유를 파악하기 위해 다음의 사항들을 고려할 수 있다.

• 어떤 특정 문제를 해결하기 위해 사용한 알고리즘이 (시간적으로나 공간적으로나) 정말 가장 효율적으로 문제를 해결하는가? 이보다 더 효율 좋은 알고리즘이 있을 수도 있다.
• 알고리즘을 수행할 때 가장 효율적인 방식으로 알고리즘을 실행시켰는가?
• 더 빠른 컴퓨터가 필요한 것인가? 똑같은 프로그램이라도 어떤 컴퓨터냐에 따라 실행 시간이 달라질 수 있다.

점근적 분석법 (Asymptotic analysis)

점근적 분석법은 충분히 큰 크기 N을 가지는 입력값의 크기에 따라 알고리즘이 특정 문제를 풀 때 얼마나 많은 수행 시간을 필요로 하는지 또는 얼마나 많은 메모리 용량을 필요로 하는지 그 양상을 나타내는 방법이다. 즉, 알고리즘의 (시간 또는 공간)복잡도를 입력값의 크기 N의 변화에 따라 그 양상을 나타내는 방법이다.

앞서 알고리즘 개요 문서에서, 입력값의 크기 N에 따른 핵심 연산 횟수를 세어 해당 알고리즘의 수행 시간을 예측했었다. 그리고 어떤 알고리즘은 입력값이 어떤 배열로 정렬되어 있느냐에 따라 그 핵심 연산의 횟수가 달라져 최악의 경우와 최선의 경우로 나눴다. 최악의 경우, 알고리즘의 수행 시간도 가장 많아져서 느리게 느껴질 것이다. 최선의 경우 알고리즘의 수행 시간도 가장 낮아 빠르게 느껴질 것이다.

다음은 어떤 알고리즘의 수행 시간을 입력값의 크기 N에 따라 최선의 경우와 최악의 경우로 나눠 예측한 그래프와 해당 알고리즘의 실제 수행 시간을 나타낸 예이다.

여기서, 알고리즘 실행 시 최악의 경우로 나올 수 있는 수행 시간을 상한선(upper bound)이라 하고, 반대로 최선의 경우로 나올 수 있는 수행 시간을 하한선(lower bound)이라 한다. 즉, 상한선이라 함은, 알고리즘 수행 시 가장 느리게 실행될 때의 시간을, 하한선은 알고리즘 수행 시 가장 빠르게 수행될 때의 시간을 말한다. 실제 알고리즘의 수행 시간은 이 상한선과 하한선 밖을 빠져나갈 수 없다. 이 사실을 이용하면 일단 알고리즘의 최선, 최악의 경우로 나눌 때 입력값에 따른 연산 횟수만 알 수 있다면 그 알고리즘의 실제 수행 시간이 대충 어느 범위 안에 있을지 예측할 수 있다.

예를 들어, 어떤 알고리즘의 연산 횟수가 입력값의 크기 N에 의존하고, 그 연산 횟수가 최악의 경우 \(N^2\) 이고, 최선의 경우 N이라고 하자. 그리고 연산을 한 번 할 때 걸리는 시간이 t로 일정하다고 가정하자. 이 때, 실제 해당 알고리즘을 수행할 때 아무리 엄청 빠른 수퍼컴퓨터에서 실행시켜도 tN 보다 더 빠를 수 없으며, 또한 아무리 느려도 tN^2보다 더 느릴 수 없다는 것이다. (즉, t가 무슨 값이든지 말이다) 또한, 입력값의 크기가 어떻든, 즉 N의 값이 무엇이든지 최악의 경우 tN^2, 최선의 경우 tN만큼 걸릴 것이다.

이렇게, 입력값의 크기에 따른 연산 횟수를 최선의 경우와 최악의 경우로 나누고 세어서 실제 알고리즘의 수행 시간을 대략적으로 예측하는 것이 점근적 분석법이다.

이러한 예측은 N이 충분히 커야 그 정확성이 높아진다는 특징을 가진다.

개념을 좀 더 쉽게 설명하기 위해 시간을 예로 들었는데, 시간복잡도 뿐만 아니라 공간복잡도에서도 동일하게 적용할 수 있다.

알고리즘 성능의 종류

빅오 표기법 (Big O notation)

컴퓨터 과학에서는 입력값의 크기 N에 따른 최선 또는 최악의 경우에서의 알고리즘의 성능을 분류하기 위해 빅오 표기법을 사용한다. 여기서 O는 N의 함수의 차수 (Order of a function)를 뜻한다. 예를 들어 어떤 알고리즘의 연산 횟수가 다음과 같다면,

\[2N^2 + 3N + 1\]

이 알고리즘의 최고 차항은 2이므로 2차 함수라고 표현할 수 있다. 이를 빅오표기법으로 나타내면 \(O(N^2)\)이다. 빅오표기법으로 나타낼 때 최고차항을 제외한 나머지 항들을 제거한 후, 최고차항의 계수도 제거하여 표현한다. 어차피 \(2N^2 + 3N + 1\)이나 \(N^2\)이나 계수와 나머지 항들만 다를 뿐, 둘 다 그래프 상에서 포물선의 양상을 띠는 2차 함수라는 것에는 변함이 없기에 이렇게 간략하게 표기하는 것 같다.

보통 “이 알고리즘의 최선(또는 최악)의 경우의 복잡도는 O(N)이다” 식으로 표현한다.

성능 계층 (performance class)

입력값의 크기 N에 대해 어떤 알고리즘의 연산 횟수를 함수로 f(N)으로 나타낼 때, 다음과 같이 여러 성능 계층이 존재한다.

1. O(1) : 상수 복잡도 계층(constant complexity class). 임의의 상수 c에 대해 f(N) = c일 경우.
2. O(log N) : 로그 복잡도 계층 (logarithmic complexity class)
3. O(N) : 선형 복잡도 계층(linear complexity class). f(N) = N인 경우.
4. \(O(N \log N)\)
5. \(O(N^{1.585})\): 카라추바 복잡도 계층 (Karatsuba complexity). \(f(N)=N^{1.585}\)인 경우.
6. \(O(N^2)\) : 이차 복잡도 계층 (quadratic complexity class). \(f(N) = N^2\)인 경우.
7. \(O(N^3)\) : 3차 복잡도 계층 (cubic complexity class)
8. \(O(2^N)\) : 지수 복잡도 계층 (Exponential complexity class)
9. \(O(N!)\) : 팩토리얼 복잡도 계층 (Factorial complexity class)
   • \(N^{1.585}>NlogN\) 증명

   1.585는 사실 \(log_23=1.5849…\)에서 반올림한 값이다.

   

1번의 상수 복잡도 계층으로 갈수록 해당 알고리즘은 효율적이란 뜻이고, 8번의 팩토리얼 복잡도 계층으로 갈수록 해당 알고리즘은 비효율적이란 뜻이다.

이를 이용하여 똑같은 문제를 푸는 서로 다른 알고리즘들 중 효율적인 알고리즘이 무엇인지를 판별할 수 있다. 예를 들어 똑같은 문제를 푸는 두 알고리즘 중 가장 수행 시간이 빠른 알고리즘을 찾고자 한다. 그러면 먼저 각 알고리즘마다 코드를 분석하여 입력값의 크기 N에 따른 연산 횟수 f(N)을 구한다. 예로, A 알고리즘의 연산 횟수는 f(N) = N-1이라 하고, B 알고리즘의 연산 횟수는 g(N) = 2N^2+3이라 하자. 그 후, O(f(N))을 구한다. 즉, 연산 횟수의 함수를 빅오표기법으로 나타낸다. A 알고리즘의 시간복잡도는 O(N), B 알고리즘의 시간복잡도는 O(N^2)이다. 이렇게 두 복잡도를 비교하면 된다. 여기선 A 알고리즘이 더 시간적으로 효율적임을 알 수 있다.

range()가 list보다 더 효율적인 이유

입력값의 크기 N에 대해 range(N)와 list(range(N))의 공간복잡도를 분석해보자.

import sys
# sys.getsizeof(object) : 객체의 크기를 바이트 단위로 알려줌.

def print_size(repeat_num: int):
    print("range")
    N = 1
    for i in range(repeat_num):
        print(f"{N} -> {sys.getsizeof(range(N))}")
        N = N * 10

    print("list")
    N = 1
    for i in range(repeat_num):
        print(f"{N} -> {sys.getsizeof(list(range(N)))}")
        N = N * 10

if __name__ == '__main__':
    print_size(5)

range
1 -> 48
10 -> 48
100 -> 48
1000 -> 48
10000 -> 48
list
1 -> 64
10 -> 136
100 -> 856
1000 -> 8056
10000 -> 80056

range(N)는 입력값의 크기에 상관없이 항상 48 byte를 가진다. 즉, 입력값의 크기에 상관없이 공간복잡도가 일정하다. O(1)이다. 반면, 리스트는 입력값의 크기가 증가할수록 그에 따른 용량도 증가함을 알 수 있다. 위 출력결과를 토대로 입력값의 크기 N에 따른 리스트가 차지하는 용량은 8N+56임을 알아냈다. 즉, 리스트의 공간복잡도는 O(N)인 것이다. 따라서 range()가 리스트보다 메모리 공간을 덜 차지하여 공간적으로 더 효율적인 자료구조임을 알 수 있다. 사실, 리스트는 모든 숫자값들의 배열을 그 숫자값들의 개수만큼 메모리 상에 저장하는 것에 반해, range()는 제너레이터로, 한 번에 하나의 값만 생산하는 구조라서 입력값의 크기가 커져도 추가 메모리 용량을 필요로 하지 않는 구조이다.

\(O(N^c)\) (c는 상수) 에 해당하는 다항 계층을 넘어선 지수 계층과 팩토리얼 계층 이 두 계층은 효율성이 매우 떨어진다고 한다. 그래서 입력값의 크기가 매우 작은 경우에만 문제를 풀 수 있다고 한다. 입력값의 크기가 커지면 아마 최악의 경우 인간의 평균 수명 내에 그 결과값을 보지 못할 수도 있다.

O(1)과 O(log N)은 매우 효율적인 복잡도 계층이라고 한다. (보통 O(NlogN)까지가 효율적인 알고리즘이라고 하는 것 같다)

어떤 한 알고리즘 내부에서 총 두 단계를 거쳐야한다고 가정하자. 첫 번째 단계에서의 시간복잡도는 \(O(logN)\)이라 치자. 그리고 두 번째 단계에서의 시간복잡도는 \(O(N^3)\)이라고 해보자. 그러면 해당 알고리즘의 총 시간복잡도는 무엇일까? 이 때는 복잡도 계층이 더 큰 복잡도를 따른다. 따라서 해당 알고리즘의 시간복잡도는 \(O(N^3)\)이다.

알고리즘의 하한선 계층을 나타낼 때 O대신 \(\Omega(f(N))\) (omega)으로 표기하기도 한다. O 표기법은 상, 하한선 모두 쓸 수 있으나 실무에서는 상한선 계층을 나타낼 때 주로 쓰인다고 한다. 상한선 계층과 하한선 계층이 같을 경우, \(\Theta\) (theta) 표기법을 사용한다고 한다. 상한선이 O(N)이고, 하한선도 \(\Omega(N)\)일 경우 이를 \(\Theta(N)\)으로 표기한다.

---

Reference

[1] George T. Heineman, “Learning Algorithms: A Programmer’s Guide to Writing Better Code”, (O’Reilly, 2021)

[2]

[알고리즘] 알고리즘의 점근적 분석 : 상한, 하한, 동등

[3]

Complexity Analysis (2) - Asymptotic Analysis (점근적 분석)

[4]

[알고리즘의 분석] 시간복잡도 점근적 분석

[5]

점근적 분석과 표기법 : 시간 복잡도와 공간 복잡도

[6] 지은이: 미아 스타인, 옮긴이: 최길우, “파이썬 자료구조와 알고리즘”, (2019, 한빛미디어)

This content is licensed under CC BY-NC 4.0