2.1.1 알고리즘 성능 분석

어떤 자료 구조의 연산(일반적으로 함수로 구현되는 연산)이 다른 자료 구조의 특정 연산에 비해 성능이 좋다고 이야기하려면 두 연산의 성능을 비교할 수 있어야 합니다. 그렇다면 성능은 어떻게 비교할 수 있을까요? 간단히 두 가지 정도의 방법이 떠오릅니다.

첫 번째 방법은 절대 시간을 재는 것입니다. 하지만 이 방법은 현실적이지 않습니다. 두 함수를 비교하려면 같은 환경의 시스템에서 테스트해야 한다는 제약 조건이 있기 때문입니다. 두 함수의 성능을 비교하면서 한 함수의 성능은 A 컴퓨터에서 2초이고 다른 함수의 성능은 B 컴퓨터에서 5초라고 한다면, 첫 번째 함수가 두 번째 함수보다 성능이 좋은 것일까요? B 컴퓨터의 성능이 A 컴퓨터의 성능보다 월등히 좋다면 머릿속은 더 복잡해집니다. 이래서는 의미가 없습니다.

두 번째 방법은 어떤 기준을 설정하고 이에 맞추어 두 함수를 상대적으로 비교하는 것입니다. 예를 들어 함수 내에 있는 반복문이나 분기문의 실행 횟수, 덧셈이나 곱셈 같은 연산 횟수를 세는 것입니다. 이렇게 하면 실행 환경과는 분리해서 독립적으로 성능을 분석할 수 있습니다. 그럼 간단한 예로 연산 횟수를 세어 볼까요?

코드 2-1 operation_count.py

                       #   연산   빈도수
def func(arr, init):
    n = len(arr)       #      1       1
    ret = init         #      1       1
    for i in range(n): #      1       n
        ret += arr[i]  #      1       n
    return ret         #      1       1
                       #           2n + 3

arr = [1, 2, 3, 4, 5]
result = func(arr, 10)
print(result)