알고리즘의 점근성능

알고리즘의 경우 알고리즘에 들어가는 데이터의 수와 알고리즘의 구성

 

또는 해당 알고리즘을 실행하는 컴퓨터에 따라서

 

알고리즘 수행시간이 유동적으로 나타납니다.

 

이때, 동일한 동직을 수행하는 알고리즘 끼리 성능을 어떻게 비교할까요?

 

이번 포스팅은 알고리즘의 점근성능에 대한 내용입니다.

 

1. 점근성능

알고리즘의 점근 성능이란, 실제 수행시간은 아니지만

 

해당 알고리즘의 성능을 대변하는 수치를 의미합니다.

 

알고리즘의 점근성능을 이야기할 때 몇가지를 가정합니다.

1. 일반 사칙연산이나 비교문은 동일한 시간이 소요된다.(Data와 상관없이 상수시간이 소요된다)

2. 알고리즘의 수행시간은 최고차항의 영향이 지배적이다.

 

아래 예시 알고리즘을 살펴보겠습니다.

#숫자를 입력받아, nxnxn 행렬을 만드는 알고리즘 입니다.
def count(n):
    temp = []    
    for i in range(2*n):
        temp.append([])
        for j in range(3*n):
            temp[i].append([])
            for k in range(n):
                temp[i][j].append([])
    return temp

count(3)
Out[4]: 
[[[[], [], []], [[], [], []], [[], [], []]],
 [[[], [], []], [[], [], []], [[], [], []]],
 [[[], [], []], [[], [], []], [[], [], []]]]

1. temp.append([])와 temp[i].append([])의 경우

   

list의 indexing과정이 추가되기 때문에 실제 실행시간을 다를 수 있습니다.

 

하지만 이 경우 두 코드의 실행시간의 거의 같다고 가정하고 계산합니다.

 

2. 위 알고리즘을 살펴보면

i를 0~n까지, 각각 i에 대해서 j가 0~n까지, 그리고 각 i,j에 대해서 0~n까지 반복됩니다.

 

2n*3n*n번의 temp[i][j].append([]), 2n*3n번의의 temp[i].append([]), 2n번의 temp.append([])가 실행됩니다.

 

이 경우 6*n^3 + 6*n^2 + n번의 명령어가 실행되지만, 해당 실행시간은 점근적으로 6*n^3과 같다고 가정합니다.

 

2. 점근성능의 표기

점근성능을 표기하는 방법으로, Big-O, Big-Omega, Big-theta가 있습니다.

이때n의 가장 높은 차수를 기준으로 표기한다는 점을 주의해주세요

 

이때 f(n) ≒ c*g(n)인 g(n)을 구하여, 점근성능을 표기하게 됩니다.

 

1. Big-O : 어떠한 경우에도 실제 수행 횟수보다 같거나&많은 값을 타내는 경우를 의미합니다.

위 알고리즘을 예시로 보면, n^3이 BigO라고 할 수 있습니다. O(n^3)으로 표기합니다.

(7*n^3보다는 낮을 것이란 의미, 이때 g(n)은 n^3입니다.)

 

2. Big-Omega : Big-O와 반대로 실제 수행 횟수보다 같거나&작은 값을 타내는 경우를 의미합니다.

위 알고리즘을 예시로 보면, n^3이 BigOmega라고 할 수 있습니다. Ω(n^3)으로 표기합니다.

(5*n^3보다는 높을 것이란 의미, 이때 g(n)은 n^3입니다.)

 

3. Big-theta : Big-O와 Big-Omega의 사이값에 해당하는 영역 입니다. 

이때 5*n^3보다는 크고, 6*n^3보다는 작기 때문에 Θ(n^3)이 됩니다.

 

 

-. 일반적으로 알고리즘의 점근성능을 나타낼때는 Big-O를 사용해서 나타내며,

 

이때의 g(n)을 시간복잡도라고 부르며 알고리즘간 수행시간의 비교는 이 시간복잡도를 가지고 비교합니다.