[파이썬 기초] 알고리즘의 개념 / 코딩 연습 - 시간 복잡도

# 시간 복잡도(Time complexity) : 데이터가 많아질수록 알고리즘이 답을 찾는 데 걸리는 시간이 얼마나 급격히 증가하는지를 나타내는 개념. 시간 복잡도가 작은 알고리즘이 더 빠른 알고리즘이다.

 

# 점근표기법(Big-O Notation)

시간 복잡도를 근사치로 표현하는 방법으로, 해당 알고리즘 내에서 답을 가장 늦게 찾을 경우(Worst cast)의 시간 복잡도를 빅 오 표현법이라 한다. 

 

소요 시간이 20n + 40인 알고리즘의 점근 표기법(Big-O)은 O(n)이 될 것이다.

각 소요시간(예시)에 따른 점근 표기법은 다음과 같다.

n이 크지 않은 숫자라면 알고리즘이 좋지 않아도 상관없으나, n이 크면 어떤 시간 복잡도를 갖고 있느냐에 따라 걸리는 시간이 기하급수적으로 증가하기 때문에 알고리즘이 어떤가가 중요해진다.

 

각 시간 복잡도에 대한 간단한 설명은 다음과 같다.

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

 

→ 요소가 2개 있는 리스트든, 16개 있는 리스트든 어차피 맨 앞에 있는 요소를 호출하는 것이므로 답을 찾는 데 걸리는 시간은 리스트의 길이와 상관 없다 → O(1)

 

O(n) : 소요 시간이 인풋의 크기에 비례해서 늘어난다(반복문).  

 

예시 1

def print_each(my_list) :

     for i in range(len(my_list)) :

         print(my_list[i])

 

→ 리스트의 길이(인풋)에 비례하여 소요 시간이 늘어남(n번 반복) → O(n)

 

예시 2

def print_half(my_list) :

     for i in range(len(my_list) // 2) :

         print(my_list[i]) 

 

→ 리스트의 길이(인풋)의 1/2에 비례하여 소요 시간이 늘어남(n/2번 반복) → O(n/2) → O(n)

 

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

 

→ 리스트의 길이(인풋)의 3배에 비례하여 소요 시간이 늘어남(3n번 반복)  → O(3n) → O(n)

 

O(n²) : 소요 시간이 인풋의 제곱에 비례해서 늘어난다(반복문 안에 반복문이 있는 경우)

 

예시

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

 

→ 리스트의 길이(인풋)의 제곱에 비례하여 소요 시간이 늘어남(n²번 반복)  → O(n²)

 

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

 

→ 리스트의 길이(인풋)의 세제곱에 비례하여 소요 시간이 늘어남(n³번 반복)  → O(n³) 

 

이 외에도 대표적인 시간 복잡도로 O(lg n), O(n lg n)등이 있다.