알고리즘 실행 시각화 용 Python

Question

알고리즘 분석 클래스에 대한 매우 흥미로운 과제가 있는데, 동적 프로그래밍과 욕심쟁이 같은 다른 접근법을 사용하여 유명한 문제 (예 : 배낭 문제)를 그래픽으로 비교해야합니다. 나는 내가 사용할 수있는 파이썬에서 시각화 (주로 시간 복잡성)를 돕기 위해 사용할 수있는 라이브러리 나 도구가 있는지 알고 싶었다. 아이디어는 아래 그림과 같은 간단한 그래픽, 다음과 같습니다

Answer 1

첫째, 당신은 당신의 알고리즘의 실제 시간 복잡도를 계산해야합니다. 이는 timeit.timeit (실제 벽 시간) 또는 수동으로 작업 수를 계산하여 수행 할 수 있습니다.

def bubble_sort(a): 
    not_sorted = True 
    operations = 0 
    while not_sorted: 
     not_sorted = False 
     for i in range(len(a)-1): 
      operations += 1 
      if a[i] > a[i+1]: 
       a[i], a[i+1] = a[i+1], a[i] 
       not_sorted = True 
    return operations 

지금 당신이 다른 크기의 배열이 함수를 공급 작업의 수는 각각의 시간이 필요 수집하고 그래프를 만들 수 있습니다 여기에

는 거품 정렬 알고리즘에 대한 예입니다.

import matplotlib.pyplot as plt 
from random import sample 

# assuming we are in Jupyter: 
%matplotlib inline 

ns = range(10, 1000, 10) 
ops = [] 
for n in ns: 
    my_list = sample(range(n), n) 
    ops.append(bubble_sort(my_list)) 
plt.plot(ns, ops) 

당신은이 같은 통계와 근성을 확인할 수 있습니다

from statsmodels.formula.api import ols 
import pandas as pd 
df = pd.DataFrame(dict(n=ns, ops=ops)) 
model = ols('ops ~ n + I(n**2)', df) 
model = model.fit() 
plt.plot(ns, ops) 
plt.plot(ns, model.predict()) 

실제 벽 시간을 찾으려면 바로 사용

from timeit import timeit 
time = timeit('bubble_sort(a)', number=10, globals=globals())