分析用C编写的函数的时间复杂度

发布时间：2020-12-16 09:30:51 所属栏目：百科来源：网络整理

导读：我在C中实现了最长公共子序列问题.我希望比较执行解决方案的递归版本和动态编程版本所花费的时间.如何在各种输入的两个版本中找到运行LCS功能所需的时间？我也可以使用SciPy在图表上绘制这些值并推断时间复杂度吗？提前致谢, 剃刀解决方法对于你问题的第

我在C中实现了最长公共子序列问题.我希望比较执行解决方案的递归版本和动态编程版本所花费的时间.如何在各种输入的两个版本中找到运行LCS功能所需的时间？我也可以使用SciPy在图表上绘制这些值并推断时间复杂度吗？

提前致谢,

剃刀

解决方法

对于你问题的第二部分：简短的回答是肯定的,你可以.您需要以便于从 Python解析的格式获取两个数据集(每个解决方案一个).就像是：

x y z

在每一行上,其中x是序列长度,y是动态解决方案所用的时间,z是递归解决方案所用的时间

然后,在Python中：

# Load these from your data sets.
sequence_lengths = ...
recursive_times  = ...
dynamic_times    = ...

import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
p1 = ax.plot(sequence_lengths,recursive_times,'r',linewidth=2)
p2 = ax.plot(sequence_lengths,dynamic_times,'b',linewidth=2)

plt.xlabel('Sequence length')
plt.ylabel('Time')
plt.title('LCS timing')
plt.grid(True)
plt.show()

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!