Python 用于算法执行可视化
Python for Algorithm Execution Visualization
我有一个非常有趣的 class 算法分析作业,我应该使用不同的方法(例如动态规划和贪心算法)对著名问题(例如背包问题)进行图形比较.我想知道在 Python 中是否有我可以使用的库或工具来帮助可视化(主要是时间复杂度)。这个想法将是一个简单的图形,如下所示:
首先,您必须计算算法的实际时间复杂度。这可以通过 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())
我有一个非常有趣的 class 算法分析作业,我应该使用不同的方法(例如动态规划和贪心算法)对著名问题(例如背包问题)进行图形比较.我想知道在 Python 中是否有我可以使用的库或工具来帮助可视化(主要是时间复杂度)。这个想法将是一个简单的图形,如下所示:
首先,您必须计算算法的实际时间复杂度。这可以通过 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())