6.알고리즘 시간복잡도

알고리즘은 어려운 문제를 얼마나 빠르고 정확하게 풀 수 있느냐가 중요하다. 그래서 알고리즘이 있다면 해당 알고리즘이 얼마나 빠른지 측정할 수 있는 객관적인 지표가 필요하다. 어느 알고리즘이든 이를 적용할 수 있는 표준적인 방법이 필요할 것이다. 이것이 바로 시간복잡도이다.

 

1. 시간 복잡도

알고리즘의 실행 시간은 컴퓨터의 성능, 사용한 프로그래밍 언어, 컴파일러의 종류에 따라 결정된다. 그리고 알고리즘 자체가 가진 실행 속도도 매우 중요하다. 알고리즘의 실행 시간은 2가지 부분으로 나누어서 생각 할 수 있다. 첫번째는 입력 값이다. 같은 알고리즘을 사용한다고 가정했을 때, 1부터 100까지 더한 결과를 구하는 것과 1부터 1억까지 더하는 것의 시간 차이는 크다. 입력값이 클수록 알고리즘을 푸는데 더 오랜 시간이 걸리게된다.

그리고 다른 한 부분은 바로 ‘성장률’이다. 예를 들어 하나의 프로그래밍이 다음과 같은 구조를 갖는다고 가정해보자.

1. 하나의 입력 값을 받는다. (1)

2. 하나의 입력 값에 대해 계산해야되는 변수가 100개이기 때문에 이를 계산한다. (100n)

3. 그리고 이중 for문 3번을 돌려서 문제를 해결한다. (3n^2)

그렇다면 이 알고리즘은 입력 값의 개수가 n개라고 가정하면 ‘3n^2 + 100n + 1’의 성장률을 갖게 된다.

 

여기서 입력 값 n이 무한대로 커지게 된다면, 이 알고리즘에서 가장 큰 영향을 받는 부분은 바로 n^2부분이다. 입력 값이 하나라면 3n^2는 3이고, 100n+1은 101이므로. 뒷부분이 더 큰 영향을 미치게 되나, n이 점차 커짐에 따라 100n+1의 영향은 줄어들고. 3n^2의 시간 영향이 커진다. 그리고 상수 또한 알고리즘 성장률에 영향을 끼치지 않는다. 입력 값이 아무리 증가하더라도, 상수만 곱하기 때문에 어느 경우에서든 같은 조건이 된다. 알고리즘에 실제로 영향을 끼치는 부분은 n^2이다.

 

알고리즘 성장률에서 불필요한 상수와 최대 차수 항을 제외한 나머지 차수 항들을 지우게 되면 알고리즘에 대한 성장률에 집중 할 수 있다. 이것이 바로 ‘점근적 표기법’이다. 점근적 표기법은 알고리즘의 성능을 나타내는 대표적인 방법이다. 그 중에서도 아래 소개할 2가지 표기법이 가장 많이 쓰인다.

 

2. Big-θ (빅세타) 표기법

데이터를 무작위로 일반적 구조의 배열에 저장했다고 가정하자. 해당 배열에서 원하는 값을 찾는 알고리즘을 만들었다. 그리고 첫번째 공간부터 배열의 크기만큼 검색을 반복해 값을 찾는다고 하자. 그리고, 배열의 크기는 n이다. 컴퓨터, 컴파일러 성능 등 고려한 상수를 포함하면, ‘an+a’의 식이 나온다. 여기서 a 값은 여러 조건들로 인해 계속 변동되게 된다. 우리는 a 값을 예측 하기 매우 어렵고, 매번 그 값이 변동된다. 우리가 예측 할 수 있는 부분은 n이다. a값에 따라 알고리즘이 빠르게 돌아갈 수도 느리게 돌아갈 수도 있다. 이런 의미를 포함하는 표기법이 바로 ‘Big-θ 표기법’이고, θ(n)으로 표기한다.

위의 말을 토대로 θ(n)이 가지는 의미는, 그 알고리즘이 n이 일정 숫자 이상으로 크다면 최소 kn에서 최대 kn이 걸리게 된다는 의미다. 아래 그래프와 같은 결과가 출력된다.

(출처: 칸 아카데미 - 점근적 표기법)

 

Big-θ 표기법을 통해 해당 알고리즘의 최대 시간과 최소 시간을 예측해 볼 수 있게된다. 나쁜 컴퓨터와 컴파일러를 써도 최대 시간은 이정도가 될 것이고, 반대로 좋은 성능의 컴퓨터와 컴파일러를 쓰더라도 해당 시간의 알고리즘이 걸리게 된다는 의미다.

 

3. Big-O (빅오) 표기법

 하지만 우리가 중요하게 보는 측면은 알고리즘의 최악의 상황이다. 우리는 최대한 문제를 빨리 풀고 싶어 한다. 그렇기 때문에 항상 알고리즘이 최악의 조건에 놓여있다고 생각하고 이 알고리즘이 얼마나 빨리 문제를 해결하는지 고민한다. 이 경우를 나타내는 표기법으로 Big-O (빅오) 표기법을 사용한다.

O(n)의 의미는 입력 값 n이 충분히 크다면, 해당 알고리즘은 최대 kn의 시간이 걸린다는 의미이다. 그리고, 아래 그래프와 같이 표기가 될 것이다.

(출처 :  칸 아카데미 - 점근적 표기법)

 

이 의미를 활용한다면 θ(log n)의 시간 복잡도를 가지는 알고리즘은 O(log n)도 만족하게 된다. 그러나 역은 성립하지 않는다. O(log n)의 복잡도를 가지는 알고리즘은 θ(log n)를 만족하는 보장은 없다. 그리고, 알고리즘의 가장 좋은 성능을 나타내는 Big-Ω (빅 오메가) 표기법도 존재한다.

 

우리는 실제 알고리즘을 표현할 때, 주로 Big-O 표기법을 사용한다. Big-O 표기법은 의미 전달이 매우 간단하다. 알고리즘의 하한선만 전달하면 되기 때문에 사람들에게 직관적 이해가 가능하다. 비교 대상이 2개인 것 보다 1개인 것이 더욱 강력하다.

 

3. 시간 복잡도 판단

알고리즘을 Big-O 표기법에 따라 판단 했다면, 이제 다른 알고리즘과 비교해야한다. 대부분의 알고리즘은 아래의 시간 복잡도 안에 속할 것이다.

 

O(1): 상수 형태 (Constant)

O(log n): 로그 함수 형태 (Logarithmic)

O(n): 선형 함수 (Linear)

O(n log n): 선형 로그 형태 (Linear log)

O(n^2): 2차 선형

O(n^k): 다차 선형 (Polynomial)

O(2^n): 지수 형태 (Exponential)

O(n!): 팩토리얼 선형 (Factorial)

 

위 시간복잡도를 비교하면 아래와 같은 순서를 가진다.

O(1), O(log n), O(n), O(n log n), O(n^2), O(n^k), O(2^n), O(n!)

 

시간 복잡도와 대표적인 표기법에 대해 알아보았다. 알고리즘의 성능을 절대적인 값으로 파악 할 수 있는 방법으로 우리가 소프트웨어를 실제로 설계할 때, 어떤 알고리즘을 사용할 것인지, 기존의 프로그램보다 얼마나 성능이 좋은지 파악 할 수 있는 좋은 방법이다. 매우 간단한 개념이지만 실제 개발자들이 시간복잡도를 간과하고 설계를 하는 경우가 많다. 시간 복잡도를 잘 활용해 좋은 알고리즘을 만드는데 적극 활용하자.