分析用C语言编写的函数的时间复杂度(Analyzing time complexity of a function written in C)

分析用C语言编写的函数的时间复杂度(Analyzing time complexity of a function written in C)

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