[AL] 알고리즘 성능 판단 (시간복잡도/공간복잡도/Big-O Notation)

1. 알고리즘

 알고리즘은 입력 값(Input)을 받아 의도에 맞는 출력 값(Output)을 내는 과정이라고 할 수 있다. 그렇기 때문에 문제를 해결하는 방식에 따라 한 가지 문제에서도 다양한 알고리즘이 나올 수 있다.

 

 우리는 그러한 문제들을 해결할 때 주어진 상황에 따라 적절한 알고리즘을 사용해야 되며, 우리가 사용하고자 하는 알고리즘의 성능을 파악할 수 있어야 된다.

 

 알고리즘의 성능 파악하는 방법은 시간 복잡도 (Time Complexity)와 공간 복잡도 (Space Complexity)로 구분된다.

 

2. 시간복잡도 (Time Complexity) / 공간 복잡도 (Space Complexity)

 쉽게 풀어서 시간 복잡도는 '문제를 해결하는 데 소요되는 시간이 얼마인가?'이고,

공간 복잡도는 '문제를 해결하는 데 필요한 메모리 용량이 얼마인가?'이다.

 

 과거에는 한정된 용량 내에서 구현이 가능해야 하기 때문에 공간 복잡도가 중요하였다. 하지만, 현재 우리가 사용하고 있는 컴퓨터는 대체적으로 큰 용량을 가지고 있기 때문에, 우리는 주로 시간 복잡도에 집중하여 알고리즘의 성능을 판단하게 된다. (그렇다고 공간 복잡도를 신경쓰지 않아도 된다는 의미는 아니다!)

 

 알고리즘의 시간 복잡도를 측정하는 데에 있어서 항상 최악의 경우를 염두해 두어야 한다. 이는 대부분의 문제에서 특정 경우는 최악의 경우가 될 수 있고, 우리는 그러한 경우를 피할 수 있는 확률이 크지 않기 때문이다.

 

 즉, 해당 알고리즘을 사용하였을 때 가장 오래 걸리는 시간에 대해 파악하고, 그렇게 측정된 알고리즘들 중에서 가장 빠르게 문제를 해결 할 수 있는 알고리즘을 선택해야 된다.

 

 위와 같은 상황에서 알고리즘의 시간 복잡도를 측정할 수 있는 방법은 무엇일까?

바로, Big-O Notation을 사용하여 주어진 알고리즘의 경향성을 파악하고 성능을 판단할 수 있게 된다. 

 

3. Big-O Notation

Big-O Notation의 정의는 다음과 같다.

 두 개의 함수 f(n)와 g(n)이 주어졌을 때, 모든 n >= K에 대하여 f(n) <= Cg(n)을 만족하는 두 개의 상수 C와 K가 존재한다면, f(n)의 Big-O는 g(n)이다. (O(f(n) = g(n))

쉽게 풀어쓰자면 '가장 영향력이 큰 부분(경향성)만 고려하는 것'이라 볼 수 있다.

 

 위의 정의에서 상수 C와 K는 무수히 큰 숫자여도 상관없다.

 이는 경향성을 판단하는 것이기 때문이고, 상수 C는 이에 영향을 줄 수 없기 때문에 C의 값이 크게 영향을 미치지 않으며, K는 어떠한 순간부터 f(n) <= Cg(n)을 만족하기만 하면 되기 때문이다.

 

 대표적인 Big-O Notation은 다음과 같다.

O(l) [상수] -> 가장 빠름

O(logn) [로그]

O(n) [일차 다항식]

O(nlogn) [로그와 일차다항식의 곱]

O(n^2) [이차 다항식]

O(n^3) [삼차 다항식]

O(2^n) [지수] -> 가장 느림

 

 위의 정리된 Notation 중에서 위에서 밑으로 내려갈수록 n이 증가함에 따라 성능 저하가 크게 일어나게 된다.

또한, 한 단계 위로 성능을 발전시키는 과정은 대단히 힘들기도 하다. 이는 대체적으로 성능이 좋은 알고리즘은 그것을 구현하는 데 다양한 지식과 많은 시간을 소비해야하기 때문이다.

 

 우리가 문제를 해결하는 것이 있어 제일 중요한 것은, 주어진 상황에 알맞는 알고리즘을 사용하는 것이다. 무작정 시간 복잡도를 통한 알고리즘 선택은 좋지 않은 상황을 만들 수도 있다.

 

 그렇기 때문에, 우리는 위에서 언급한 시간 복잡도를 우선적으로 고려하되, 개발 환경과 문제 조건을 파악하면서 어느 정도 타협할 수 있는 유연한 생각을 가질 수 있도록 노력해야 된다.