#3 알고리즘 성능 분석: 시간 복잡도 분석, 빅오(Big-O) 표기법

어느 한 문제에 대하여 많은 해답이 있을 수 있다. 수학 문제만 하더라도 여러 풀이 방법이 존재한다.

예시로 1부터 100까지 더한 값을 구하라는 문제를 푼다면. 어떤 사람은 1부터 100까지 하나씩 더하는 사람이 있고

(1+100) + (2+99) + (3+98) + ... = 101*50 = 5050

와 같은 방법으로 푸는 사람도 있을 것이다.

어느 풀이 방식이 효율적일까?

당연히 두 번째 풀이 방식이 더 빠르고 간단하게 풀 수 있으므로 효율적이다.

 

알고리즘도 이와 마찬가지로 어느 한 문제에 대하여 많은 방법이 존재한다.

앞 절에서 자료구조에 따라 적용가능한 알고리즘이 다르다고 하였다.

같은 문제라도 어떤 자료구조를 사용하고 어떤 알고리즘을 선택하느냐에 따라 프로그램의 성능은 달라지게 된다.

프로그램을 높은 성능으로 만들기 위해서는 여러 알고리즘에 대해 성능 비교가 필요하다.

 

알고리즘의 성능 분석 기법은 크게 두 가지로 나뉜다.

 

1. 공간 복잡도 분석: 메모리(RAM)를 얼마나 사용하는가?

2. 시간 복잡도 분석: 수행시간이 얼마나 되는가?

 

하지만, 우리는 시간 복잡도 분석에 대하여만 알아볼 것이다. 그 이유는 과거에 비해 메모리 가격이나 크기가 매우 커졌기에 공간의 의미가 줄어들었기 때문이다.

 

먼저 프로그램 내에서 수행 시간을 측정하는 방법을 알아보자.

대표적으로 c언어에서는 clock() 함수를 이용하는 방법이 있다. 자바에서는 System.currentTimeMillis() 함수를 이용하면 된다.

구현한 알고리즘의 시작과 끝에 시간 측정 함수를 이용하여 수행시간을 출력하는 방법이다.

다음은 자바로 구구단을 저장하여 출력하는 코드와 그 실행 결과이다.

 

하지만 이렇게 직접 측정하는 것은 문제점이 존재한다.

우선 알고리즘을 구현하고 테스트를 해야 한다. 알고리즘이 단순한 경우 직접 짜서 비교하기 쉽지만, 알고리즘이 복잡하면, 구현이 부담으로 다가온다.

또한, 이 방법을 이용하면 컴퓨터 성능에 따라 수행시간이 달라질 수 있어 같은 컴퓨터 내에서 측정해야 한다.

그 외에도 데이터에 따라서 수행 시간이 달라질 수 있으므로, 수학적으로 이를 계산하는게 더욱 좋다.

시간 복잡도 함수 [T(n)] 를 이용하여 구현없이 알고리즘의 수행시간을 분석하는 방법을 알아보자.

 

1이 아닌 양의 정수 n을 n번 더하는 문제가 존재한다. 이 문제에 대해 두 가지 알고리즘을 구현했다.

 

1. n*n을 구한다.

sum = n;

sum *= n;

 

2. n을 n번 더한다.

sum = 0;

for (int i = 0; i<n; i++){

 sum += n;

}

 

시간 복잡도 함수를 이용하여 수행 시간을 비교하려면, 각 알고리즘 내에 존재하는 기본 연산들 (대입 연산, 비교 연산, 반환 연산 등) 의 개수를 구하여 그를 비교한다.

그렇다면 1번 알고리즘은 연산의 개수가 세 번이고, 2번 알고리즘은 연산의 개수가 1+2n 번이다.

 

여기서, 어떤 연산인가에 따라 시간이 다를 수 있지만, 우린 모든 연산의 수행 시간이 같다고 가정해보자.

하나의 연산이 시간 t가 걸린다고 하자.

그렇다면 1번 알고리즘은 3t의 시간이 걸릴 것이고 2번 알고리즘은 (1+2n)t의 시간이 걸린다.

따라서 우리는 n>1일 때, 1번 알고리즘을 선택하면 된다.

이를 통해 우리는 가장 효율적인 알고리즘을 선택할 수 있다.

 

하지만, 일반적으로 기본 연산의 개수 n과 시간 복잡도 함수 T(n)의 관계는 복잡할 수 있다.

이 때, 자료의 개수가 많으면 차수의 가장 큰 항이 영향을 가장 크게 미치고 다른 항들은 상대적으로 영향이 적으니 무시 할 수 있다.

빅오 표기법을 알아보자.

 

빅오 (Big-O) 표기법 O(n)은 연산의 횟수를 대략적으로 표기한 것으로, 시간 복잡도 함수의 "계수를 모두 제거"하고 "고차항만 남겨" 표현한다. 즉, 가장 좋지 않은 경우를 남겨 비교하는 방법이다.

방금 알고리즘의 시간 복잡도를 빅오 표기법으로 표현하면, 1번 알고리즘은 O(1)의 시간 복잡도를 보이고

2번 알고리즘은 O(n)의 시간 복잡도를 보이는 것이다. 따라서 1번이 더욱 좋은 효율의 알고리즘이다.

 

간단한 예제를 보자.

 

f(n)= 3n^2 + 2n + 100

다음 식을 빅오 표기법으로 표현하면,

O(n^2)가 된다.

 

빅오 표기법도 다양한 종류가 있다. 빅오 표기법의 종류는 다음과 같다.

 

-빅오 표기법의 종류-

O(1) : 상수형

O(log n) : 로그형

O(n) : 선형

O(n log n): 로그 선형

O(n^2): 2차형

O(n^3): 3차형

O(n^k): k차형

O(2^n): 지수형

O(n!): 팩토리얼형