Big-O Notation

 

점근 표기법에서 n은 무엇인가?

점근 표기법에서 n은 특별한 의미를 가지는 것은 아니다. 우리가 함수에 매개변수를 임의로 설정하듯이 이 n 또한 임의로 설정된 인풋의 크기이다. 인풋 리스트의 크기를 x라고 부르기로 하면 O(x), O(x^2).. 이런식으로 하겠지?

 

“트리”나 “그래프” 같은 조금 특수한 자료 구조가 인풋으로 들어올 수도 있다.
트리와 그래프가 특수한 이유는 리스트처럼 “선형적”이지 않기 때문인데, 예를 들어서 그래프는 꼭짓점(vertex)과 변(edge)으로 이루어져 있다. 꼭짓점의 개수를 V라고 하고 변의 개수를 E라고 하면,
두 꼭짓점 간 최단 경로를 찾는 BFS 알고리즘의 시간 복잡도는 O(V + E)이다.

 

O(1)은 코드 한 줄의 단위?

아니다!

인풋 크기와 상관 없이 실행되는 코드만 O(1)이다. 그렇지 않은 코드는 시간 복잡도를 따져봐야 한다.

 

예를 들어서 sorted 함수나 sort 메소드를 사용하면 내부적으로 O(n*lgn)의 정렬이 이루어진다.

만약 리스트에서 in 키워드를 통해 값의 존재 여부를 확인하면 내부적으로 O(n)의 선형 탐색이 이루어진다.

 

List Operations

리스트의 길이를 n이라고 하자

OperationCodeAverage Case

인덱싱	my_list[index]	O(1)
정렬	my_list.sort() sorted(my_list)	O(nlgn)
뒤집기	my_list.reverse()	O(n)
탐색	element in my_list	O(n)
끝에 요소 추가	my_list.append(element)	O(1)
중간에 요소 추가	my_list.insert(index, element)	O(n)
삭제	del my_list[index]	O(n)
최솟값, 최댓값 찾기	min(my_list) max(my_list)	O(n)
길이 구하기	len(my_list)	O(1)
슬라이싱	my_list[a:b]	O(b - a)

Dictionary Operations

OperationCodeAverage Case

값 찾기	my_dict[key]	O(1)
값 넣어주기/덮어쓰기	my_dict[key] = value	O(1)
값 삭제	del my_list[key]	O(1)

 

 

 

시간복잡도의 종류

• 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) 함수
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개 있는 리스트를 넘겨줬다.

그런데 사실 두 경우 걸리는 시간은 거의 똑같다. 어차피 맨 앞에 있는 요소를 받아오는 것 뿐이니까, 리스트의 길이는 상관이 없는 것. 

 

**반복문이 없으면 대체로 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 가 2배씩 증가한다.

인풋 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문의 반복횟수는 n에 비례하는데, 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)이다.

 

 

 

2021-10-02