주요 시간 복잡도 정리

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

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

• O(1)
• O(lgn)
• O(n)
• O(nlgn)
• O(n2)
• O(n3)
• O(n4)
• O(2n)
• O(n!)

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

 

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])

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

 

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

 

O(n)

Case 1

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

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

Case 2

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

n번 반복하는 게 아니라 n/2번 반복한다면 시간 복잡도가 어떻게 될까요? O(1/2​n)이지만, 1/2​을 버려서 결론적으로는 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])

위 코드의 경우 O(3n)인데, 결국에는 3을 버려서 이것 또한 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])

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

 

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])

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

 

O(lgn)

Case 1

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

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

 

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

 

print_powers_of_two 함수는 O(lgn)입니다.

Case 2

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

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

 

두 경우 모두 O(lgn)입니다.

 

O(nlgn)

O(n^2)은 O(n)과 O(n)이 중첩된 거죠? 같은 논리로, O(nlgn)은 O(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

위 코드에서 for문의 반복횟수는 �에 비례하는데, while문의 반복횟수는 lgn에 비례합니다. while문이 for문 안에 중첩되어 있기 때문에 위 코드의 시간 복잡도는 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

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

 

출처 코드잇