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

Question

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

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

我用C语言编写了这个程序，并使用time命令和gettimeoftheday函数(两者都使用)来计算具有64位四核处理器(每个内核800mhz)的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. 如果我使用时间命令，我应该考虑哪个输出?真实的，用户的还是系统的?
2. 是否有计算程序运行时间的标准方法?
3. 每次执行这些命令时，我都会得到不同的读数。在代码不变的情况下，我应该采样多少次才能使平均值始终相同?
4. 如果我想使用多个线程，并通过在这些程序上调用execute来测量每个线程中的时间，该怎么办?

从我所做的研究来看，我还没有遇到任何标准的方法。此外，无论我使用什么命令/方法，每次都会给我不同的输出(我理解这是因为上下文切换和cpu周期)。我们可以假设我甚至可以得到一个与机器相关的解。

Answer 1

回答您的问题:

1. 取决于您的代码正在做什么time输出的每个组件可能是重要的。这个问题涉及到这些组件的含义。如果您计时的代码没有利用系统调用，那么计算"用户"时间可能就足够了。我可能会使用"实时"时间。
2. time怎么了?如果你需要更好的粒度(例如，你只想对一段代码而不是整个程序进行计时)，你总是可以在你正在分析的代码块之前得到开始时间，运行代码，然后得到结束时间，然后计算差值来给出运行时间。永远不要使用gettimeofday，因为时间不是单调递增的。系统时间可由管理员或NTP进程修改。你应该用clock_gettime代替。
3. 为了尽量减少运行时的差异，我会检查cpu频率缩放是OFF，特别是如果你得到非常不同的结果。
4. 一旦你开始进入多线程，你可能想要开始查看一个分析器。gprof是一个很好的开始。