다른 개발자들과 함께 알고리즘에 대한 의논을 하게 되면, 자연스럽게 시간 복잡도 이야기가 나올 수밖에 없다.
시간 복잡도를 계산할 줄 알아야 원활한 대화가 이루어질 수 있다.
다행히, 알고리즘의 시간 복잡도는 대개 이중 하나다.
이 중에서도 O(1), O(lg n), O(n), O(n lg n), O(n^2), O(n^3) 정도가 많이 사용되고, 나머지는 흔치 않다.
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) 이다.
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/2n) 이지만, 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) 함수
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)이다.
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번 실행된다.
lg 128 도 7인 건 우연이 아니다.
print_powers_of_two 함수는 lg n 이다.
(2 로 n을 몇번 나눠야 1이 되는가?!)
Case2
# 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(lg n) 이다.
O(n^2)은 O(n) 과 O(n) 이 중첩된 것이다.
같은 논리로, O(n lg n)은 O(n)과 O(lg n) 이 겹쳐진 것이다.
Case1
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) 이라고 할 수 있다.
Case2
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
Case1 의 코드를 살짝 바꿔서 이제 for 문이 while 문 안에 중첩되어 있다.
이 경우에도 시간 복잡도는 O(n lg n) 이다.