주요 시간 복잡도 총정리

코드잇 강의를 통해 알고리즘에 대해 공부하며 배운 내용들을 기록한 글입니다.

---

$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(n)$

Case 1

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

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

Case 2

def print_half(my_list):
    for i in range(len(my_list) // 2):
        print(my_list[i])

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

Case 3

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

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

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

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(\lg n)$

Case 1

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번 실행된다. $\lg 128$은 $7$이다.
따라서, print_powers_of_two 함수는 $O(\lg n)$이다.

Case 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(\lg n)$이다.

$O(n\lg n)$

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문의 반복횟수는 $n$에 비례하는데, while문의 반복횟수는 $\lg n$에 비례한다. while문이 for문 안에 중첩되어 있기 때문에 위 코드의 시간 복잡도는 $O(n\lg n)$이라고 할 수 있다.

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(n\lg n)$이다.