time-complexity - 测量一段代码的运行时复杂度的最佳实践

Question

我有一段粗糙的代码，我想衡量它的时间效率。由于从代码本身估计这种复杂性很困难，我想把它放在一个循环中并对结果计时。一旦收集到足够的数据点(大小 -> 时间)，我就可以看到哪条曲线最适合。

使用给定大小的随机输入数据重复操作多次可以消除由于操作系统决定在糟糕的时刻执行多任务而产生的波动，从而产生更精确的时间。增加问题的大小会提供更多的点，理想情况下间隔良好。

我的测试代码工作正常(初始的非定时预热循环以减少加载时间；然后，从 10 的大小开始，以 10% 的增量扩展到 1000000，重复运行直到 5s已过去或 5 次完整运行已完成)。但是，我通过猜测得出了这些数字。

是否有一种公认的“科学”方法来缩放重复和问题大小，以实现更快、更准确的时间与大小图？ 是否有代码(或库)可以支撑所有无聊的部分，而在我自己动手之前我应该​​知道这些？特别是，我可以认为，当发现时间上的颠簸时，可能需要采取更多措施——而相对平稳的读数可以简单地被认为“足够好”。

编辑

我知道计算大 O 复杂度的经典方法。它适用于具有良好代表性操作(例如“比较”或“交换”)的自包含算法。当这些条件不满足时，它不会像宣传的那样工作(例如:LLVM 的编译时 C++ 模板实例化成本，这是一个庞大而复杂的，我不知道相关的代表性操作是什么)。这就是为什么我把它当作一个黑匣子，并试图从外部而不是通过代码检查来测量时间。

Answer 1

测量时间复杂度可能非常困难(如果可能的话)，我从未在算法论文中看到过这一点。如果您无法从(伪)代码或算法描述中计算时间复杂度，那么也许您可以使用启发式方法来简化分析。

也许您还可以计算算法某些部分的复杂度，如果其他部分的复杂度明显要小得多，则可以忽略它们。

如果没有任何帮助，正常的方法将显示算法如何在机器上扩展，就像你写的那样。
但是有很多事情会影响结果。只是要注意其中的一些:

内存类型:如果您的输入小到足以放入 L1 缓存，那么您的算法运行得非常快，因为内存很快。如果您的输入变大，因此不再适合 L1 缓存，则将其存储在 L2 缓存中，如果输入更大，则将其存储在 RAM 中。并且每次您的程序都会因一个巨大的因素而变慢(除了不断增长的输入因素)。最糟糕的是，当它变得如此之大以至于算法必须在您的硬盘上存储一些薄输入时。

多任务处理:如果您的操作系统决定将 CPU 交给其他程序，您的算法似乎会变慢。这也很难处理。

硬件:在 big-O 中，每个操作都计为 1 个时间单位。如果您的算法执行大量操作，而您的 CPU 已针对这些操作进行了优化，这也会影响您的测量。

软件:软件可以像硬件一样影响您的测量。例如。如果你有很多使用库的大整数运算，你可以通过使用 GMP 大大加快程序的速度。

预热:如果开始测量，必须先预热 CPU。首先在更大的输入上运行算法(不测量)。

输入案例:您只能在某些选定或随机生成的特定长度的输入案例上运行您的程序。在大多数情况下，很难判断(或根本不可能)输入是否会导致更短或更长的运行时间。所以也许你测试了错误的例子。如果你使用随机输入，你会得到更多不同的结果。

总而言之:我认为你只能得到一个想法，你的算法如何扩展，但你不能通过测量运行时间来准确地获得复杂性的上限。也许这适用于非常小的例子，但对于较大的例子，你不会得到正确的结果。

你能做的最好的事情是:

写下您用于测量的计算机的确切硬件和软件。

多次重复测试(以不同的顺序)

如果您更改硬件或软件，则应从头开始。

仅使用所有存储在相同内存类型中的输入，因此跳过适合缓存的所有情况。

通过这种方式，您可以查看更改是否改进了算法，其他人可以验证您的结果。

关于输入:

如果可能，您应该使用最坏情况的输入。如果你不能说一个输入是否是最坏的情况，你应该使用许多不同的情况或随机输入(如果可能的话)。

您必须运行测试(针对每个输入长度)，直到运行时间的平均值稳定。