알고리즘 시간복잡도

자료구조를 활용하여 어떠한 문제를 해결하는 알고리즘은 C, Java, Python 등과 같은 언어로 작성된 코드를 이용하여 구현할 수 있습니다. 이때, 코드는 C로 작성되었는지, Python으로 작성되었는지에 따라 알고리즘 성능 차이가 발생합니다. 또한, 코드는 컴퓨터에 저장되어 실행되기 때문에 HW/SW 환경에 따라서도 알고리즘의 성능 차이가 납니다. 

성능을 측정할 땐 동일한 환경에서 측정이 되어야 하므로 가상 컴퓨터(Virtual Machine), 가상 언어(Pseudo Languge), 가상 코드(Pseudo Code)를 만들어 동일한 환경에서 알고리즘 성능을 정확하게 측정할 수 있도록 합니다.

 

가상 컴퓨터

가상 컴퓨터는 수학자인 폰 노이만(von Neumann)의 RAM(Random Access Machine) 아키텍처를 사용합니다. RAM 아키텍처는 연산을 담당하는 CPU, 데이터를 저장하는 Memory, 어떤 방식으로 데이터를 연산할지 정하는 기본 연산으로 구성되어있습니다. 기본 연산은 1 단위 시간 내에 수행이 가능한 연산으로 아래와 같이 다양한 연산이 존재합니다.

- 배정, 대입, 복사 연산 : A = B

- 산술 연산 : +, -

- 비교 연산 : >, >=, <, <=, ==, !=

- 논리 연산 : AND, OR, NOT

- 비트 연산: bit를 활용한 AND, OR, NOT 연산

 

가상 언어

가상 컴퓨터가 기본 연산을 수행하기 위해 가상 컴퓨터가 이해할 수 있는 언어가 필요합니다. 가상 언어(Pseudo/Virtual Languages)는 기본 연산을 표현할 수 있고, 여러 가지 제어할 수 있는 명령어를 제공해줍니다. 가상 언어가 제공하는 기능은 아래와 같습니다.

- 기본 연산

- 반복 연산 : for 문, while 문

- 함수 : 정의, 호출, return

 

가상 코드

가상 언어를 사용하여 작성한 코드를 가상 코드(Pseudo Code)라고 합니다. 가상 컴퓨터에서 동작하는 코드이기 때문에 실제 언어(C, Java, Python 등) 보다 훨씬 자유롭게 작성할 수 있습니다. 아래는 가상 코드로 작성한 배열 안의 최댓값을 리턴하는 함수입니다.

수도코드의 예
algorithm ArrayMax(A,n):
    input: n개의 정수를 갖는 배열 A
    ouput: A의 수 중에서 최대값 리턴
    
    currentMax = A[0]
    for i = 1 to n-1 do          # C: for(i=1;i<n;i++) / Python: for i in range(1,n)
    	if currentMax < A[i]
        	currentMax = A[i]
    return currentMax

 

알고리즘 시간 복잡도

코드가 실행되는 시간이 얼마나 걸리는지 파악하면 알고리즘의 성능을 알 수 있습니다. 이를 시간 복잡도라고 합니다. 알고리즘의 시간 복잡도(Time complexity)를 측정하는 방법은 2가지가 있습니다.

 

1. 모든 입력에 대해 기본 연산 횟수를 더한 후 평균

2. 가장 안 좋은 입력(Worst Case input)에 대한 기본 연산 횟수

 

1번은 경우 무한히 많은 입력이 있을 수 있으므로 현실적으로 계산을 하는 것이 불가능합니다. 2번은 일반적으로 사용하는 방법으로, 어떤 입력에 대해서도 Worst Time Complexity 보다 수행 시간이 크지 않습니다. 측, 알고리즘 수행 시간은 최악의 입력에 대한 기본 연산의 횟수입니다. 

 

위의 수도 코드의 예를 통해 알고리즘 시간 복잡도를 구해보겠습니다.

수도코드의 예
algorithm ArrayMax(A,n):
    input: n개의 정수를 갖는 배열 A
    ouput: A의 수 중에서 최대값 리턴
    
    currentMax = A[0]			# (1) 대입 연산으로 기본 연산 + 1
    for i = 1 to n-1 do         
    	if currentMax < A[i]	        # (2) 비교 연산으로 기본 연산 + 1
        	currentMax = A[i]	# (3) 대입 연산으로 기본 연산 + 1
    return currentMax

배열의 크기가 n이라고 했을 때 (1)의 경우 한번 수행됩니다. (3)의 경우 (2)가 참일 경우에만 수행이 됩니다. 최악의 경우가 시간 복잡도이기 때문에 항상 (2)가 참이어서 (3)이 수행이 된다고 가정합니다. (2), (3)의 경우에는 for문을 수행하기 때문에 2번의 연산이 n-1번 수행되므로 2(n-1) 번 수행됩니다. 즉, 위 예시의 시간 복잡도는 2(n-1)+1이 됩니다.

 

이 방법을 통해 여러 알고리즘의 수행 시간을 서로 비교할 수 있습니다. 아래는 3가지 알고리즘에 대한 시간 복잡도 예시입니다.

Algorithm1 : 2n-1
Algorithm2 : 4n+1
Algorithm3 : 3/2n^2-+1

이 3가지 알고리즘을 그래프로 그려보면 다음과 같습니다.

3가지 알고리즘에 대한 시간복잡도

이 3가지 알고리즘의 시간 복잡도를 서로 비교해보면 다음과 같습니다.

1. Algorithm2가 Algorithm1보다 2배 느리다.
2. Algorithm3은 모든 n에 대해서 Algorithm1보다 느리다
3. Algorithm3은 n<8/3면 Algorithm2보다 빠르다
4. Algorithm3은 n>8/3이면 Algorithm2 보다 느리다

그래프를 보면 Algorithm1과 Algorithm2는 n에 대해 선형적으로 증가합니다. Algorithm3는 제곱으로 증가합니다. 즉, 시간 복잡도에서 가장 큰 영향을 끼치는 값은 최고차항입니다. n이 무한대로 갈수록 최고차항을 제외한 다른 값은 의미가 미미해지므로 시간 복잡도를 계산할 때 최고차항만 고려하는 계산법이 있습니다. 이를 빅오(Big-O) 표기법이라고 합니다. 

 

빅오 표기법

빅오 표기법은 앞서 구한 시간 복잡도에서 최고차항만을 기입하면 되므로 다음과 같이 간단한 순서로 구할 수 있습니다.

 

1. 최고 차항만 남긴다.

2. 최고 차항 계수(상수)는 생략한다.

3. O(최고 차항)

 

아래는 앞서 살펴본 알고리즘 3개를 빅오 표기법으로 시간 복잡도를 나타낸 것입니다.

Algorithm1 : O(n)
Algorithm2 : O(n)
Algorithm3 : O(n^2)

빅오 표기법에는 이 외에도 아래와 같이 상수 시간과 로그 시간이 존재합니다.

# (1) 상수 시간
def end_one(x):
    return x*10+1		# +2
    
# (2) 로그 시간    
def number_of_bits(n):
    count = 0			# +1
    while n > 0:
        n = n // 2		# +2
        count += 1		# +2
    return count

end_one 함수는 x값 끝에 1을 붙이는 연산을 수행합니다. x가 무한히 큰 값이라도 기본 연산을 두 번 시행하므로 시간 복잡도의 차이가 없습니다. 즉 end_one의 시간 복잡도는 '2'가 됩니다. 상수의 시간은 1이나 1000이나 100000이나 무한대와 비교했을 땐 한없이 작은 수입니다. 그렇기에 이를 상수 시간을 빅오 표기법으로 표기하면 O(1)이 됩니다.

number_of_bits 함수는 n이 2진수로 표현되었을 때 몇 비트가 필요한지 연산하는 함수입니다. 이 함수의 시간 복잡도를 구하기 위해서는 가장 먼저 while 문이 몇 번 수행하는지 알아야 합니다. n이 100이라면 아래와 같이 연산됩니다.

100    →   50  →    25    → ... →      1         → 0
n       →  n/2  → n/2^2  → ... → n/2^count

즉, 1 = n/2^count로 n = 2^count 됩니다. 이는 밑이 2인 log(n)이 됩니다. 즉, 빅오 표기법으로 나타내면 O(logn)이 됩니다.