big-o - 查找算法运行时间的常数部分

Question

我有一个在 O(n log n) 中运行的算法的实现，对于 n=10^7，该算法需要 570 毫秒。有谁知道如何找到我的算法运行时间的常数部分（C）？我想要这个，所以我可以计算算法“应该”花费多长时间来处理任意输入大小。

Answer 1

我不认为你可以精确计算它，但如果你确定复杂性是O(n log n)那么我会推荐一个简单的比例来估计你的运行时间：

10^10 log 10^10   unknown run time
--------------- = ----------------
10^7 log 10^7           570 ms

在这种情况下，这应该是大约1428.6 * 570 ms =~ 814 sec。

这在数学上并不完全正确，但如果您没有多个数据点来尝试拟合曲线以计算出各种常数，那么这不是一个不合理的起点。

Answer 2

如果您知道算法的渐近复杂度为 O(n log n)，那么仅使用单个数据点就无法（准确地）确定未来操作的运行时间。想象一下，例如，你有一个你知道在 O(n) 时间内运行的算法，并且在大小为 N 的输入上，运行时间是 T。你无法准确预测运行时间在输入为大小为 2T，因为不清楚有多少 T 由线性函数的斜率解释，多少由截距解释。

如果您假设 N“足够大”以至于大部分运行时间 T 来自斜率，那么您可以对未来输入的算法运行时间进行合理估计。具体来说，由于函数线性增长，你可以假设如果你将输入的大小乘以某个常数 k，那么运行时间应该是 Tk。在您的情况下，函数 n log n主要呈线性增长。由于log增长非常缓慢，对于足够大的 n，它的增长非常平坦。因此，如果您认为 N “足够大”，您可以通过将大小 N 的运行时间缩放 k 倍来估计大小为 kN 的输入的运行时间。

为了更准确，您还可以尝试收集更多关于运行时的数据点并进行回归。在线性情况下，如果您知道两个准确的数据点，则可以恢复实际的线性函数，然后进行外推以获得非常准确的运行时预测。对于 n log n 形式的东西，假设运行时具有 c ₀ n log n + c ₁ n + c ₂ n 的形式可能会很好。如果您收集了足够多的数据点，您可能可以将其插入 Excel 并恢复系数，您可以从中非常准确地进行推断。

希望这可以帮助！