分析C中写入的函数的时间复杂性

StackOverflow https://stackoverflow.com/questions/4191658

  •  10-10-2019
  •  | 
  •  

题

我在C中实现了最长的常见子序列问题。我希望比较执行解决方案和动态编程版本所花费的时间。如何找到在两个版本中运行LCS功能所花费的时间？我还可以使用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()

其他提示

说明处理器时间的最简单方法是使用 clock() 功能来自 time.h:

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之类的图形包。显然，您必须将测试大小参数化，并以每个大小为代码几次。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top