시간복잡도

Created At

2022/01/25 23:21

Updated At

2022/03/14 09:51

분류

기타

다른 개발자들과 함께 알고리즘에 대한 의논을 하게 되면, 자연스럽게 “시간 복잡도” 이야기가 나올 수밖에 없습니다. 시간 복잡도를 계산할 줄 알아야 원활한 대화가 이루어질 수 있겠죠.

다행히, 알고리즘의 시간 복잡도는 대개 이 중 하나입니다.

•

O(1)

•

O(lgn)

•

O(n)

•

O(nlgn)

•

O(n^2)

•

O(n^3)

•

O(n^4)

•

O(2^n)

•

O(n!)

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

O(1)

O(1)O(1)은 인풋의 크기가 소요 시간에 영향이 없다는 뜻입니다.

# O(1) 함수def print_first(my_list):
    print(my_list[0]) 

print_first([2, 3])
print_first([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53])
Plain Text
복사

print_first 함수를 처음 호출할 때는 요소가 2개밖에 없는 리스트를 넘겨줬는데, 두 번째 호출할 때는 요소가 16개 있는 리스트를 넘겨줬습니다. 그런데 사실 두 경우 걸리는 시간은 거의 똑같습니다. 어차피 맨 앞에 있는 요소를 받아오는 것 뿐이니까, 리스트의 길이는 상관이 없는 거죠. 길이가 10만씩이나 되는 리스트를 넘겨줘도 똑같을 것입니다.

나름의 팁을 드리자면, 반복문이 없으면 대체로 O(1)O(1)입니다.

O(n)

Case 1

# O(n) 함수def print_each(my_list):
    for i in range(len(my_list)):
        print(my_list[i])
Plain Text
복사

반복문이 있고, 반복되는 횟수가 인풋의 크기와 비례하면 일반적으로 O(n)O(n)입니다.

Case 2

# O(n) 함수def print_half(my_list):
    for i in range(len(my_list) // 2):
        print(my_list[i])
Plain Text
복사

nn번 반복하는 게 아니라 n/2n/2번 반복한다면 시간 복잡도가 어떻게 될까요? O(\frac{1}{2}n)O(21n)이지만, \frac{1}{2}21을 버려서 결론적으로는 O(n)O(n)이라고 할 수 있습니다.

Case 3

# O(n) 함수def print_three_times(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])
Plain Text
복사

위 코드의 경우 O(3n)O(3n)인데, 결국에는 33을 버려서 이것 또한 O(n)O(n)이라고 할 수 있겠죠?

O(n^2)

그런데 반복문이 연속해서 나오는 게 아니라, 반복문 안에 반복문이 있는 경우가 있습니다.

# O(n^2) 함수def print_pairs(my_list):
    for i in range(len(my_list)):
        for j in range(len(my_list)):
            print(my_list[i], my_list[j])
Plain Text
복사

지금처럼 두 반복문 다 인풋의 크기에 비례하는 경우, O(n^2)O(n2)이라고 할 수 있습니다.

O(n^3)

# O(n^3) 함수def print_triplets(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])
Plain Text
복사

동일한 원리로, 인풋의 크기에 비례하는 반복문이 세 번 중첩되면 O(n^3)O(n3)이 되겠죠?

O(lgn)

Case 1

# O(lg n) 함수# 2의 거듭제곱을 출력하는 함수# (이번에는 인풋이 리스트가 아니라 그냥 정수입니다)def print_powers_of_two(n):
    i = 1
    while i < n:
        print(i)
        i = i * 2
Plain Text
복사

이번에는 반복문이 조금 특이합니다. i가 두 배씩 증가하네요.

인풋 n이 128이면 반복문이 총 몇 번 실행될까요? i가 1일 때부터 2, 4, 8, 16, 32, 64까지 총 7번 실행됩니다. \lg{128}lg128도 77인 건 우연이 아닙니다!

print_powers_of_two 함수는 O(\lg{n})O(lgn)입니다.

Case 2

# O(lg n) 함수# 2의 거듭제곱을 출력하는 함수# (이번에는 인풋이 리스트가 아니라 그냥 정수입니다)def print_powers_of_two(n):
    i = n
    while i > 1:
        print(i)
        i = i / 2
Plain Text
복사

i를 1부터 시작해서 두 배씩 곱하는 게 아니라, n부터 시작해서 반씩 나눠봅시다. 이 경우에도 i가 128일 때부터 64, 32, 16, 8, 4, 2까지 반복문이 7번 실행됩니다.

두 경우 모두 O(\lg{n})O(lgn)입니다.

O(nlgn)

O(n^2)O(n2)은 O(n)O(n)과 O(n)O(n)이 중첩된 거죠? 같은 논리로, O(n\lg{n})O(nlgn)은 O(n)O(n)과 O(\lg{n})O(lgn)이 겹쳐진 것입니다.

Case 1

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

위 코드에서 for문의 반복횟수는 nn에 비례하는데, while문의 반복횟수는 \lg{n}lgn에 비례합니다. while문이 for문 안에 중첩되어 있기 때문에 위 코드의 시간 복잡도는 O(n\lg{n})O(nlgn)이라고 할 수 있습니다.

Case 2

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

Case 1의 코드를 살짝 바꿔서 이제 for문이 while문 안에 중첩되어 있습니다. 이 경우에도 시간 복잡도는 O(n\lg{n})O(nlgn)입니다.