알고리즘의 효율성을 표현하는 Big-O 표기법

Big-O표기법을 사용하여 알고리즘의 복잡도^[각주:1]를 표현할 수 있습니다.

 

현대에 들어 컴퓨팅 파워가 올라가고 탑재되는 메모리량이 비약적으로 늘어남에 따라 공간 복잡도 보다 시간 복잡도를 줄이는데 비중을 두는 것이 일반적입니다. 따라서 이하 복잡도는 시간 복잡도만 다루도록 하겠습니다.

 

Big-O는 데이터 증가량에 따른 알고리즘의 성능을 예측하기 위한 표기법이므로 상수항은 모두 무시하게 됩니다.

(e.g) O(2n + 1) -> O(n), O(3000n² + 10000000) -> O(n²)

 

대표적인 복잡도와 sample code

1. O(1) - 상수시간

data = [1, 2, 3, 4, 5]
def function(n):
    return n[0] == 1
function(data)

데이터량과 상관없이 항상 일정한 수행 시간을 기대할 수 있습니다.

(graph here - data/time)

 

 

2. O(n) - 선형시간

data = [1, 2, 3, 4, 5]
def function(n):
    for elem in data:
        print(elem)
function(data)

늘어난 데이터량만큼만 수행 시간이 늘어나는 알고리즘입니다.

(graph here)

 

 

3. O(n²)

data = [1, 2, 3, 4, 5]
def function(n):
    for i in n:
        for j in n:
            print(j, end=' ')
        print()
function(data)

늘어난 데이터량의 제곱에 비례하여 수행 시간이 늘어나는 알고리즘입니다.

(graph here)

 

 

4. O(nm) - 서로 수량이 다른 두 데이터를 사용한 2중 반복문

n = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
m = [1, 2]
for i in n:
    for j in m:
        print(i, j)

서로 다른 수량의 데이터 n, m으로 2중 반복문을 수행할 경우 O(n²)이 아니라 O(n*m)이 됨에 유의합니다. 예를 들어 n과 m의 범위가 각각 0 <= n <= 1000000000와 0 <= m <= 3과 같이 극단적으로 차이가 날 수 있기 때문입니다.

(graph here)

 

 

5. O(n³)

data = [1, 2, 3, 4, 5]
def function(n):
    for i in n:
        for j in n:
            for k in n:
                print(i, j, k)
function(data)

늘어나는 데이터량의 3 제곱에 비례하여 연산량이 증가하는 알고리즘입니다. 데이터량이 늘어감에 따라 n² 보다 가파른 증가세를 보입니다.

 

 

6. O(2^n)

import time


def fibonacci(n, r):
    if n <= 0:
        return 0
    elif n == 1:
        r[n] = 1
        return r[n]
    else:
        r[n] = fibonacci(n - 1, r) + fibonacci(n - 2, r)
        return r[n]


n = 33
data = [0] * (n + 1)
start_time = time.time()
fibonacci(n, data)
data = data[1:]
print(f"time elapsed : {round(int((time.time() - start_time)*1000), 0)}ms")
print(data)

재귀호출을 사용하여 피보나치수열을 구하는 알고리즘입니다. n번 쨰 요소의 값을 구하기 위해서는 n-2와 n-1번째 요소의 값을 먼저 구해야 하므로 O(2^n) 복잡도의 알고리즘이라 할 수 있습니다. 매우 안 좋은 케이스의 알고리즘으로 데이터가 늘어남에 따라 실행시간이 현저하게 증가되는 것을 확인할 수 있습니다.

 

이 코드는 다이내믹 프로그래밍을 통한 최적화를 통해 어느 정도 효율적인 실행이 가능하도록 할 수 있습니다.(

2021/02/15 - [Data Structure & Algorithm] - 동적 프로그래밍(Dynamic Programming)

)

import time


def fibonacci(n, r):
    if n <= 0:
        return 0
    elif n == 1:
        r[n] = 1
        return r[n]
    elif r[n] > 0:	#특정 배열 인덱스에 대한 연산이 완료된 경우는 다시 재귀호출을 통한 연산을 수행하지 않고 배열 요소 값을 반환합니다.
        return r[n]
    else:
        r[n] = fibonacci(n - 1, r) + fibonacci(n - 2, r)
        return r[n]


n = 500
data = [0] * (n + 1)
start_time = time.time()
fibonacci(n, data)
data = data[1:]
print(f"time elapsed : {round(int((time.time() - start_time)*1000), 0)}ms")
print(data)

이렇게 불필요한 연산을 제거하게 되면 이 코드의 복잡도는 O(n)이 됩니다.

 

7. O(log n)

data = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
n = 13


def binary_search(data, start, end, n):
    mid = (start + end) // 2
    if start > end or mid > len(data)-1:
        return None
    if data[mid] == n:
        return mid
    elif data[mid] > n:
        return binary_search(data, start, mid - 1, n)
    else:
        return binary_search(data, mid + 1, end, n)


print(binary_search(data, 0, len(data), n))

연산을 거듭할 때마다 연산에 필요한 데이터를 ½씩 줄여가는 알고리즘입니다. 이진탐색 알고리즘이 대표적입니다.

 

 

 

1. 복잡도(complexity)
   1. 시간 복잡도(time complexity) : 알고리즘을 수행하는데 소요되는 시간을 기준으로 하는 복잡도입니다. 입력 데이터량에 비례하여 연산량이 폭증하는 알고리즘일수록 시간 복잡도가 높습니다.
   2. 공간 복잡도(space complexity) : 알고리즘을 수행하는데 필요한 메모리 공간을 기준으로 하는 복잡도입니다. 알고리즘의 수행에  많은 메모리를 요구할수록 공간복잡도가 높습니다.

   시간 복잡도와 공간 복잡도는 일반적으로 반비례 관계입니다. 실행 속도가 안정적이고 빠른 알고리즘일수록 많은 메모리를 필요로 합니다. [본문으로]