当前位置：文江博客话题详情

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

发布于 2024-10-02 15:23:58 字数 142 浏览 2 评论 0原文

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

预先感谢，

剃刀

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

金兰素衣 2024-10-09 15:23:58

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

回复收藏 0 原文

舟遥客 2024-10-09 15:23:58

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

clock_t start, elapsed;

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

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

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

The simplest way to account processor time is to use the clock() function from time.h:

clock_t start, elapsed;

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

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

Since you are simply comparing different implementations, you don't need to convert the clocks into real time units.

回复收藏 0 原文

捂风挽笑 2024-10-09 15:23:58

有多种方法可以做到这一点。更简单的方法之一是找到一些可以执行高分辨率（微秒或更小）间隔计时的代码。将对开始计时器和停止计时器函数的调用包装在对 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 等绘图包中。显然，您必须参数化测试大小，并在每种大小下对代码进行多次计时。

There are various ways to do it. One of the simpler is to find some code that does high resolution (microsecond or smaller) timing of intervals. Wrap calls to the start-timer and stop-timer functions around the call to the LCS function, then print the resulting elapsed time:

#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)));

Similarly for the lcs_dynamic() function.

If the time for a single iteration is too small, then wrap a loop around the function. I usually put the timing code into a function, and then call that a few times to get consistent results.

I can point you to the package illustrated.

Yes, you could feed the results, with care, into a graphing package such as SciPy. Clearly, you'd have to parameterize the test size, and time the code several times at each size.

回复收藏 0 原文

~没有更多了~