c - 测量任何编程语言的程序的时间复杂度

Question

我正在寻找一种标准方法来识别程序的运行时间复杂度。 如上所述here ，我并不是在寻找通过查看代码来分析相同问题的解决方案，而不是通过程序运行时的其他一些参数。

考虑一个程序，它要求用户将二进制字符串转换为其等价的十进制字符串。当一次处理每个二进制数字时，这样的程序的时间复杂度最坏应该是 O(n)。通过一些智能，运行时间可以减少到 O(n/4)(一次处理二进制字符串中的 4 个数字，假设二进制字符串有 4k 个数字，所有 k=1,2,3...)

我用 C 语言编写了这个程序，并使用了 time 命令和一个使用 gettimeoftheday 的函数(两者)来计算具有 64 位四核处理器(每个核心为 800 MHZ)的 Linux 机器上的运行时间，分为两个类别:

1. 系统正常负载时(核心使用率5-10%)
2. 系统负载较重时(核心使用率80-90%)

以下是O(n)算法的读数，二进制字符串长度为100000，在正常负载下:

Time spent in User (ms) - 216
Time Spent in Kernel (ms) - 8
Timed using gettimeofday (ms) - 97

以下是O(n)算法的读数，二进制字符串长度为200000，在高负载下:

Time spent in User (ms) - 400
Time Spent in Kernel (ms) - 48
Timed using gettimeofday (ms) - 190

我在寻找什么:

1. 如果我使用 time 命令，我应该考虑哪个输出？真实的、用户的还是系统的？
2. 有计算程序运行时间的标准方法吗？
3. 每次执行这些命令时，我都会得到不同的读数。在代码不变的情况下，我应该采样多少次才能使平均值始终相同。
4. 如果我想使用多个线程并通过在此类程序上调用 execve 来测量每个线程的时间，该怎么办？

根据我所做的研究，我还没有遇到任何标准方法。另外，无论我使用什么命令/方法，每次都会给出不同的输出(我知道这是因为上下文切换和 CPU 周期)。我们可以在这里假设我什至可以使用依赖于机器的解决方案。

Answer 1

回答您的问题:

1. 取决于您的代码正在执行的操作，时间 输出的每个组成部分可能很重要。 This问题涉及这些组件的含义。如果您计时的代码不使用系统调用，则计算“用户”时间可能就足够了。我可能只会使用“真实”时间。
2. 时间出了什么问题？如果您需要更好的粒度(即您只想对一段代码而不是整个程序进行计时)，您始终可以在要分析的代码块之前获取开始时间，运行代码，然后获取结束时间，然后计算差异给你运行时间。 永远不要使用gettimeofday，因为时间不会单调增加。系统时间可以由管理员或 NTP 进程更改。您应该改用clock_gettime。
3. 为了最大限度地减少运行时的运行时差异，我会检查 CPU 频率缩放是否关闭，特别是当您得到的结果差异很大时。这曾经让我感到困惑。
4. 一旦开始使用多线程，您可能需要开始查看分析器。 gprof 是一个很好的起点。