계산 복잡도 이론 이해를 위한 간단한 그림

 

 

 

오늘은 알고리즘의 성능과 효율을 예측하고 분석하기 위해 탄생한 이론,

 

'계산 복잡도' 에 대해서 알아보겠습니다.

 

계산 복잡도 이론은  주어진 문제에 대한 최적의 알고리즘을 찾는 것을 목표로 알고리즘의 복잡도를 분석하고 연구하는 이론입니다.

 

쉽게말해 특정 알고리즘이 문제를 해결하기 위해 필요로 하는 시공간적 리소스를 정량화하여 측정해보기 위한 것이죠.

 

 

일명 알고리즘 전투력 측정기

 

 

 

이때 시간적 리소스, 그러니까 문제해결에 걸리는 시간을 분석하는 것을 ' 시간 복잡도 ' 라고 하고,

 

공간적 리소스, 그러니까 문제해결에 필요한 메모리 공간의 양을 분석하는 것을 ' 공간 복잡도 ' 라고 합니다.

 

계산 복잡도 이론은 세부적으로 시간 복잡도와 공간 복잡도로 나누어 지는 것이죠.

 

 

 

 

 

하지만 어떠한 알고리즘이 동작하는데 걸린 실제시간을 측정하거나

 

실제로 사용된 정확한 메모리의 양을 측정해서 비교 분석한다는 것은 매우 힘든 일입니다.

 

사용된 언어가 다를 수도 있고 기록 당시  컴퓨터(하드웨어)의 사양이나 상태,

 

하다못해 그 순간 공급되는 전력 등 무수히 많은 변수가 존재하기 때문이죠.

 

 

 

 

 

알고리즘 간 성능을 예측하고 비교하여 최적의 알고리즘을 찾으려고 하는데,

 

정작 다른 요소에 의해서 알고리즘 차제의 성능 비교가 안된다면 분석을 하는데 의미가 없어집니다.

 

그렇기 때문에 계산 복잡도 이론은 알고리즘의 과정을 정량화 하는 것이 중요합니다.

 

이를 위해 계산 복잡도를 평가할 때는 튜링 기계 의 동작방식에서 착안한 정량화된 방법으로 측정됩니다.

 

 튜링 기계 : 현대 검퓨터의 기본 개념을 제공한 계산 기계로, 한 단위시간에 한번의 이동을, 즉 하나의 연산을 수행한다. 

 

 

 

 

 

 시간 복잡도의 경우, 실제 알고리즘이 실행되는데 걸린 물리적인 시간을 계산하는 것이 아닌

 

하나의 작업(Operation) 의 실행 횟수당 1의 시간으로 계산합니다.

 

여기서 말하는 작업(Operation) 이란 하나의 구체적이고 논리적인 코드의 단위를 의미하며

 

다시말해 어떠한 알고리즘이 있을 때 시간 복잡도를 구한다는 것은,

 

알고리즘을 동작시키는데 필요한 작업의 실행 횟수를 구하는 것입니다.

 

 

 

 

 

공간 복잡도의 경우에도 마친가지로 실제 사용된 정확한 메모리를 구한다기 보다는,

 

일반적으로 알고리즘을 실행하는데 할당된 자료의 갯수당 1의 크기의 공간으로 계산됩니다. 

 

이때 ' 고정 공간 '( 정적 변수, 상수 등 요소를 담은 공간 전체 )뿐만 아니라

 

' 가변 공간 '(재귀 알고리즘, 임시 변수, 자료 구조 등) 까지도 모두 고려할 수 있도록 주의해야합니다.

 

 

 

 

 

이렇게 계산된 복잡도를 표기할 때는 특정 알고리즘이 어느 정도의 복잡도를 가졌는지 직관적으로 알기 쉽게 하기 위해,

 

그리고 두 알고리즘 간의 성능 비교를 빠르고 효율적으로 하기 위해  ' 점근 표기법 ' 을 사용합니다.

 

 점근 표기법 : 점점 가까워지는 값들에 대하여 생략과 단순화를 통해 뭉뚱그려 표현하는 표기법입니다. 

 

 

 

 

 

점근 표기법에는 크게 3가지 방법이 있습니다.

 

상한 점근, 그러니까 최악의 경우를 기준으로 표기하는 Big-O 표기법과

 

하한 점근, 그러니까 최선의 경우를 기준으로 표기하는 Big-Omega 표기법,

 

상,하한 점근의 교집합으로 평균을 표현하는 Big_Theta 표기법 이 그것입니다.

 

대부분의 경우, Big-O 표기법을 사용하기 때문에 이번 글에서도  Big-O 표기법을 사용하여 몇가지 예시를 살펴보겠습니다.

 

 

 

 

 

아래는 list 를 인자로 전달받아 최대값을 구하는 find_max 라는 이름의 함수를 Python으로 작성한 코드입니다.

def find_max(list_):
    max_value = 0

    for i in range(1, len(list_)):   # 1

        if list_[i] > max_value:     # 2
            max_value = list_[i]     # 3
            
    return max_value


# Big-O 표기법을 사용한 시간 복잡도: O(n)
# Big-O 표기법을 사용한 공간 복잡도: O(1)

 

해당 함수는

 

1. for 문을 돌면서 리스트 내의 모든 요소를 순회

 

2. if 문으로 max_value의 담긴 값과 비교

 

3. 비교해서 더 클 경우 max_value 값 업데이트

 

로 총 세단계의 작업을 수행합니다. 

 

리스트의 길이가 n 이라고 했을 때, 최악의 경우 ( n-1 )번 전체 작업을 반복해야합니다.

(처음 요소는 이미 현재 값이기 때문에 연산에서 제외되어 -1) 

 

그러니까 해당 알고리즘의 시간 복잡도는  3n-1   이 됩니다. 

 

여기서  Big-O 표기법을 사용하면,

 

상수의 곱과 더하기, 빼기 같이 입력 크기에 따른 변화가 없는 수치들은 생략되고 n의 최고 차수만을 취하여 표기합니다.

 

여기서는 3 과 -1 은 제외되고, 최고차수는 1차이기 때문에 n 만을 표기하여  O(n)  와 같이 표기합니다.

 

왜냐하면 Big-O 표기법은 결국 입력의 크기에 따른 작업 실행 횟수의 증가률을 나타내기 위함이고,

 

입력 크기가 계속 늘어나 무한대로 향할 수록 최고차수 외의 숫자들은 의미가 없어지기 때문입니다.

 

 

전투력이 무한에 가까워질수록 사소한 설정은 의미가 없어집니다

 

 

 

공간 복잡도는 변수 max_value만을 사용하며,

 

입력값이 커져도 사용하는 변수의 갯수에 변함이 없기 때문에  O(1)  로 표기합니다.

 

 

 

 

 

좀 더 이해를 돕기 위해 예시를 하나만 더 들어보겠습니다.

 

아래는 리스트 내의 모든 인접한 두 요소를 반복 비교하여 정렬하는 방식인

 

'버블 정렬 ( Bubble sort )' 을 Python 으로 구현한 코드입니다.

def bubble_sort(list_):
    for i in range(len(list_) - 1):                                  # 1

        for j in range(len(list_) - i - 1):                          # 2

            if list_[j] > list_[j + 1]:                              # 3
                list_[j], list_[j + 1] = list_[j + 1], list_[j]


# Big-O 표기법을 사용한 시간 복잡도: O(n^2)
# Big-O 표기법을 사용한 공간 복잡도: O(1)

 

해당 함수는

 

1. 리스트내 모든 요소를 비교하기 위한 for 문 반복. 한번의 비교에 두 요소가 사용되기 때문에 전체 요소의 -1 번 반복.

 

2. 반복 비교 1회 당 리스트의 뒤에서 부터 가장 큰 수가 하나 씩 쌓이기 때문에 앞에서 부터 진행하는 비교 횟수도 하나씩 줄여 나감.

 

3. 각 반복마다 인접한 두 요소를 비교하고 필요에 따라 교환.

 

로 총 세 단계의 작업을 수행합니다.

 

리스트의 길이가 n 이라고 했을 때, 최악의 경우 1. 에서 n-1 번 을, 2. 에서 n-1 번을

(정확한 계산은 아니지만 어차피 제외될 값이기 떄문에 생략하겠습니다.)

3. 에서는 2.의 반복 횟수와 동일한 횟수만큼 실행됩니다.

 

그러니까 해당 알고리즘의 시간 복잡도는  (n-1) x (n-1) x 2   ->   2(n-1)^2  가 됩니다. 

 

여기서  Big-O 표기법을 사용하면, 입력 크기에 따른 변화가 없는 수치들은 생략되고 n의 최고 차수만을 취하여,

 

최종적인 시간 복잡도는  O(n^2)  가 됩니다.

 

 

공간 복잡도는 변수 i와 j만 사용하기 때문에 자료의 갯수 2 만큼을 복잡도로 가지지만

 

입력값이 늘어남에 따라 사용되는 자료의 갯수가 증가하지는 않기 때문에

 

이러한 경우 (변수를 2개 쓰든 100개 쓰든 입력값에 따른 증가가 없다면) 의미없는 수를 제거하고 통틀어  O(1)  로 표기합니다. 

 

 

 

 

 

조금 아쉬워서 딱 하나만 더 살펴보겠습니다.

 

아래는 재귀 함수를 이용하여 팩토리얼을 계산하는 함수 입니다.

def factorial(n):
    if n == 0:                           # 1
        return 1
    else:                                
        return n * factorial(n - 1)      # 2    # 3


# 시간 복잡도: O(n)
# 공간 복잡도: O(n)

 

해당 함수는

 

1. n 과 0이 일치하는지 비교. ( 마지막 0 까지 포함하기 때문에 n + 1 번 반복.)

 

2. n 과 factorial(n - 1) 을 곱하는 연산. (n - 1 번 반복)

 

3. factorial(n - 1) 함수를 재귀 호출. (n -1 번 반복)

 

로 총 세 단계의 작업을 수행합니다.

 

리스트의 길이가 n 이라고 했을 때, 최악의 경우  3n -1  번의 작업 실행이 필요하고

 

여기서  Big-O 표기법을 사용하면, 최종적인 시간 복잡도는  O(n)  이 됩니다.

 

 

이번에는 공간 복잡도를 한번 알아보겠습니다. 

 

재귀 함수의 경우, 스택 자료구조를 사용하며 이때 스택 프레임은

 

1. 현재 재귀 호출에서 사용되는 값을 담는 변수

 

2. 이전 재귀 호출의 결과값을 담는 변수

 

3. 함수 호출 후 반환할 위치를 담는 변수

 

로 총 세 개의 변수가 필요합니다.

 

각 재귀 호출 마다 스택 프레임이 쌓이기 때문에 공간 복잡도는  3n  이 됩니다.

 

입력값이 늘어남에 따라 사용되는 자료의 갯수도 비례하여 증가하는 것이죠

 

여기서  Big-O 표기법을 사용하면, 최종적인 공간 복잡도도  O(n)  이 되겠네요.

 

 

 

 

 

 

오늘은 이렇게 시간 복잡도와 공간 복잡도를 포함하는 계산 복잡도 이론에 대해서 알아보았습니다.

 

복잡도를 계산하여 알고리즘의 성능을 예측하고 비교 분석하며 더 좋은 알고리즘을 탐구하려는 자세는 중요합니다.

 

하지만 세상에는 너무나 다양한 알고리즘들이 존재하며 시시각각으로 새로운 기술들이 연구되고 등장하고 있습니다.

 

예를 들어 "어떠한 알고리즘이 평균 성능이 너무 압도적일 때 굳이 최악을 고려해야하는가" 라는 문제에 대해

 

무조건 복잡도의 관점이 해답이 되지 않을 수도 있습니다.

 

혹은 복잡도를 평가하는 기준이 되는 튜링 기계 이후, 기하급수적으로 발전한 컴퓨터 기술에 맞지 않는,

 

즉 튜링 기계의 한계에서 오는 복잡도 이론의 한계를 생각해 볼 수도 있겠죠.

 

이렇듯 항상 고민해보고 자신에게 필요한 것들은 잘 활용하는 것이 현명한 개발자가 되는 방법인 것 같습니다.