파이썬 알고리즘 시간 측정 방법

알고리즘에는 시간복잡도라는 것이 있는데요. 코드를 다 작성하고 나서, 점근적 표기법인 빅오 표기법(Big-O notation)을 사용하여 대략적인 수식으로 시간복잡도를 나타낼 수 있습니다.  

 

하지만, 만약 실제로 자신이 작성한 알고리즘이 얼마만큼의 시간이 걸리나 측정해보고 싶다면 어떻게 해야 할까요??  

 

방법은 정말 간단합니다. 여러 언어들이 시간 관련 프레임워크나 모듈을 제공 할텐데, 저는 파이썬 기준으로 설명드리겠습니다.

파이썬에는 time 모듈이 있는데요. 이 모듈의 time 메서드를 사용하시면 됩니다 ㅎㅎ (쉽죠??)

오늘 시간 측정을 해보기 위해 사용할 녀석은 정렬입니다. 

정렬을 하는 방법에는 정말 다양한 방법이 존재 하는데요.  그래서 어떻게 알고리즘을 작성하느냐에 따라서 시간복잡도도 달라지게 됩니다.

오늘 이 time모듈을 갖고 선택 정렬(시간 복잡도: O(n^2))과 퀵 정렬(시간 복잡도: O(nlogn))을 비교해 볼까 합니다.  시간 측정은 함수 실행 전에 start = time.time() 메서드를 실행 후 end = time.time() - start를 해줌으로써 가능합니다. 즉, 함수를 실행할때의 시간을 변수에 저장 후 함수가 끝났을 때의 시간에서 빼주는 것이죠. 간단하죠?? ㅋㅋ  

 

아래는 코드입니다! 

import time # 시간 측정 위해 time 모듈 추가
import random # 리스트를 무작위로 섞기위해 random 모듈 추가

# 선택 정렬
def sel_sort(a):
    n = len(a)
    
    for i in range(0, n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]

# 퀵 정렬    
def quick_sort(ls):
    if len(ls) <= 1:
        return ls
    
    pivot = ls[len(ls) // 2]
    less_ls, equal_ls, greater_ls = [], [], []
    for num in ls:
        if num < pivot:
            less_ls.append(num)
        elif num > pivot:
            greater_ls.append(num)
        else:
            equal_ls.append(num)
    return quick_sort(less_ls) + equal_ls + quick_sort(greater_ls)

   
ls = [x for x in range(10001)] # 10000개의 원소를 갖는 리스트
random.shuffle(ls) # 정렬하기 전 무작위로 섞기
ls2 = ls[:] # 퀵 정렬에 사용할 리스트

start = time.time()   
sel_sort(ls) # 선택 정렬 실행 시간
sel_time = time.time() - start 

start = time.time()
quick_sort(ls2) # 퀵 정렬 실행 시간
quick_time = time.time() - start

print('선택 정렬 실행시간: ', sel_time)
print('퀵 정렬 실행시간: ', quick_time)

 

결과는 제 노트북 기준(맥북 프로) 선택 정렬의 경우 약 5.86초가 걸리고 퀵 정렬의 경우 약 0.028초로 엄청나게 큰 차이를 보이네요 (이래서 변별력 있는 알고리즘 문제는 효율성 테스트를 거치나 봅니다 ㅎㅎ)  

 

아무쪼록 다들 제 포스팅이 도움이 되셨길 바랍니다. 감사합니다.