Python 用于算法执行可视化

Question

我有一个非常有趣的 class 算法分析作业，我应该使用不同的方法（例如动态规划和贪心算法）对著名问题（例如背包问题）进行图形比较.我想知道在 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())

Python 用于算法执行可视化

Python for Algorithm Execution Visualization

python

algorithm

time-complexity

paradigms