알고리즘 시간복잡도로 평가하기

주요 시간 복잡도 총정리

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

 

 

O(1)

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

 

Tip♤ 반복문이 없으면 대체로 O(1) 입니다.

 

 

O(n)

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

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

 

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

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

 

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

for문이 3개 입니다. O(3n)이지만 3을 버려서 이것 또한 O(n)입니다.

 

 

O($n^2$)

이전 코드블럭과 달리 for문 안에 for문이 있는 경우입니다.

# 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(n2)이라고 할 수 있습니다.

 

O(lg n)

# 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번 실행됩니다. $lg{128}$도 77인 건 우연이 아닙니다!

 

2의 거듭제곱을 출력하는 함수 print_powers_of_two 함수는 O(lg n)입니다.

 

 

List Operation

Operation	Code	Average 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

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