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

Question

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

提前致谢，

剃刀

Answer 1

对于你问题的第二部分：简短的回答是肯定的，你可以。您需要以便于从 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()

Answer 2

计算处理器时间的最简单方法是使用以下clock()函数time.h：

clock_t start, elapsed;

start = clock();
run_test();
elapsed = clock() - start;

printf("Elapsed clock cycles: %ld\n", (long)elapsed);

由于您只是比较不同的实现，因此您不需要将时钟转换为实时单位。

Answer 3

有多种方法可以做到这一点。更简单的方法之一是找到一些执行高分辨率（微秒或更小）时间间隔的代码。在对 LCS 函数的调用周围包装对 start-timer 和 stop-timer 函数的调用，然后打印生成的经过时间：

#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 等图形包中。显然，您必须参数化测试大小，并在每个大小上多次计时代码。