用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?

由于提前，

剃须刀

推荐答案

有关你问题的第二部分：简单的答案是肯定的，你可以。需要的格式是方便从Python来解析，以获得两个数据集（每个溶液）。是这样的：

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ž

每一行上，其中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

然后，在Python：

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

这篇关于用C语言编写的函数的分析时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！