알고리즘: 시간 복잡도(Time complexity)와 공간 복잡도(Space complexity)

1. 시간 복잡도란?

 

 

 

시간 복잡도란 문제를 해결하는데 걸리는 시간과 입력함수의 관계를 나타내는 것입니다. 

 

쉽게 말해서 문제 해결에 시간이 얼마나 걸리냐? 를 정량적으로 나타낸것입니다.

 

 

그래서 보통 시간 복잡도가 적은 알고리즘을 빠른 알고리즘

 

시간 복잡도가 큰 알고리즘을 느린 알고리즘이라고 합니다. 

 

 

알고리즘의 시간복잡도 표기법은 점근표기법(Big-O)을 통해서 나타내는데

 

오늘 여러가지 경우의 시간 복잡도과 공간 복잡도를 알아보겠습니다.

 

 

주로 O(1), O(lgn), O(n), O(nlgn), O(n​2​^​2), O(n^3) 정도가 많이 사용되고, 나머지는 흔치 않습니다.

 

 

 

< O(1) >

 

def my_print(my_list):
    print(my_list) 

my_print([2, 3])
my_print([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53])

 

O(1)은 어떠한 크기의 인풋의 크기 들어오던 간에 소요시간에 영향이 없다는 뜻입니다.

 

 

< O(n) > 

 

def print_repeat(my_list):
    for i in range(0: len(my_list)):
        print(my_list[i])

 

반복문 안에서 n번 반복하므로 O(n)이며, 일반적으로도 반복문이 하나 있으면 O(n)입니다.

 

 

def my_print(my_list):

    for i in range(len(my_list)):
        print(my_list[i])

    for i in range(len(my_list)):
        print(my_list[i])

    for i in range(len(my_list)):
        print(my_list[i])

 

위 코드의 경우 O(3n)인데, 점근 표기법에서는 3을 무시하므로 O(n)입니다. 

 

 

< O(n^2) >

 

def my_print(my_list):

    for i in range(len(my_list)):
        for j in range(len(my_list)):
            print(my_list[i], my_list[j])

 

반복문 안에 반복문이 있는 경우, 똑똑한 분들은 눈치 바로 채셨겠지만 그렇습니다!

 

반복문안에서 한번 더 반복이 되므로 O(n^2)이라 할 수 있습니다. 

 

 

< O(n^3) >

 

def my_print(my_list):

    for i in range(len(my_list)):
        for j in range(len(my_list)):
            for k in range(len(my_list)):
                print(my_list[i], my_list[j], my_list[k])

 

동일한 원리로 반복문이 세 번 중첩 되면서 O(n^3)이 됩니다.

 

 

< O(lg(n)) >

 

# 이번 인풋은 그냥 정수

def make_power_of_two(n):
    
    i = 1
    
    while i < n:
        print(i)
        i = i * 2
    
    return i    

 

이번에는 반복문은 i가 두 배씩 증가합니다. 인풋 n이 128일때 몇번이나 실행될까요?

 

i가 1일 때부터 2, 4, 8, 16, 32, 64, 128까지 총 7번 실행됩니다.

 

lg2(128) = 7 이므로 이 함수는 O(lgn)입니다.

 

 

< O(nlgn) >

 

def my_print(n):

    for i in range(n): # 반복횟수: n에 비례
        j = 1
        
        while j < n: # 반복횟수: lg n에 비례
            print(i, j)
            j = j * 2
            
    return j

 

위 코드에서 for문의 반복횟수는 n에 비례하는데, while문의 반복횟수는 lgn에 비례합니다.

 

while문이 for문 안에 중첩되어 있기 때문에 위 코드의 시간 복잡도는 O(nlgn)이라고 할 수 있습니다.

 

 

 

 

2. 공간 복잡도란? 

 

 

공간 복잡도(Space Complexity)는 인풋 크기에 비례해서 알고리즘이 사용하는 메모리 공간을 나타냅니다.

 

물론 공간 복잡도 또한 마찬가지로 점근표기법으로 나타낼 수 있습니다. 

 

 

< O(1) >

 

def multi(x, y, z):
    result = x * y * z
    return result

 

어떤 인풋이 들어오던 간에 result가 차지하는 메모리 공간은 무관합니다. 따라서 mulit 함수의 공간 복잡도는 O(1)입니다.

 

 

< O(n) >

 

def get_half(my_list):
    my_half = my_list[::2]
    
    return my_half

 

인풋 my_list의 길이가 n이라고 할때, my_half는 my_list의 짝수 인덱스 값들을 참조하게 됩니다. 

 

따라서 n/2개의 값을 가진 리스트가 저장되게 됩니다. 그러므로 이 함수의 공간 복잡도는 O(n/2)가 되고

 

점근 표기법 상 /2는 생략하므로 O(n)이 됩니다. 

 

 

< O(n^2) >

 

def my_product(my_list):

    products = []

    for a in my_list:
        for b in my_list:
            products.append(a * b)
    
    return max(products)

 

인풋 my_list의 길이를 n이라고 했을 때, 위 함수 안에는 변수 products, a, b가 공간을 차지합니다.

 

a와 b는 그냥 정수 값을 담기 때문에 O(1)이 되고 product는 my_list에서 가능한 모든 조합의 곱이 들어갑니다.

 

그렇게 products는 n^2개의 값을 갖게 되면서 my_product함수의 공간 복합도는 O(n^2 + 2)가 되고 점근 표기법

 

상 O(n^2)이 됩니다.