分析用C编写的函数的时间复杂度
我在C中实现了最长公共子序列问题。我希望比较执行解决方案的递归版本和动态编程版本所花费的时间。 如何在各种输入的两个版本中找到运行LCSfunction所需的时间？ 我也可以使用SciPy在图表上绘制这些值并推断时间复杂度吗？
提前致谢，
剃刀
对于你问题的第二部分：简短的回答是肯定的，你可以。 您需要以便于从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() 计算处理器时间的最简单方法是使用time.h的clock()函数：
clock_t start, elapsed; start = clock(); run_test(); elapsed = clock() - start; printf("Elapsed clock cycles: %ld\n", (long)elapsed);
由于您只是简单地比较不同的实现，因此您无需将时钟转换为实时单位。
有各种方法可以做到这一点。 其中一个更简单的方法是找到一些能够实现高分辨率（微秒或更小）间隔时间的代码。 在调用LCS函数的周围调用启动定时器和停止定时器函数，然后打印生成的经过时间：
#include "timer.h" Clock clk; char elapsed[32]; clk_start(&clk); lcs_recursive(); clk_stop(&clk); printf("Elapsed time (recursive): %s\n", clk_elapsed_us(&clk, elapsed, sizeof(elapsed)));
类似地，对于lcs_dynamic()函数。
如果单次迭代的时间太小，则在函数周围包装一个循环。 我通常将定时代码放入一个函数中，然后调用它几次以获得一致的结果。
我可以指出你所说的包装。
是的，您可以小心地将结果输入到SciPy等图形包中。 显然，您必须参数化测试大小，并在每个大小上多次为代码计时。