我在C中实现了最长的公共子序列问题。我希望比较执行递归版本解决方案和动态编程版本所需的时间。 我怎样才能找到在两个版本中为各种输入运行LCS功能所需的时间? 我是否也可以使用SciPy在图表上绘制这些值并推断时间复杂度?
提前致谢,
剃刀
I was implementing Longest Common Subsequence problem in C. I wish to compare the time taken for execution of recursive version of the solution and dynamic programming version. How can I find the time taken for running the LCS function in both versions for various inputs? Also can I use SciPy to plot these values on a graph and infer the time complexity?
Thanks in advance,
Razor
最满意答案
对于你问题的第二部分:简短的回答是肯定的,你可以。 您需要以便于从Python解析的格式获取两个数据集(每个解决方案一个)。 就像是:
XYZ
在每一行上,其中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()For the second part of your question: the short answer is yes, you can. You need to get the two data sets (one for each solution) in a format that is convenient to parse with from Python. Something like:
x y z
on each line, where x is the sequence length, y is the time taken by the dynamic solution, z is the time taken by the recursive solution
Then, in 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()更多推荐
发布评论