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 毫秒 =~ 814 秒。

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