アルゴリズム実行視覚化のためのPython

Question

私は、アルゴリズムの分析のための非常に面白い課題を持っています。これは、ダイナミックプログラミングやグリーディーなどの異なるアプローチを使って有名な問題（ナップザック問題など）をグラフィックで比較する必要があります。私は、私が使用できるPythonの視覚化（主に時間の複雑さのため）を助けるために使用できるライブラリやツールがあるかどうかを知りたかったのです。アイデアは、以下示すようなシンプルなグラフィック、次のようになります。

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