从运行时分析得出时间复杂度

Question

作为非计算机科学家，我发现很难理解时间复杂度及其计算方式，因此我的问题是，是否有可能通过在越来越大的运行时间来推导出某个算法/程序的时间复杂度输入数据，然后查看运行时间相对于输入大小n的增加如何变化。

我问这个问题是因为我用C ++编写了一种算法，该算法基本上使用单个cpu内核和单个线程（3GHZ处理器）在2D图像上进行像素着色。我测量了从2^4到2^30的输入大小的运行时间，这是32,768 ** 2大小的矩阵。现在，我有了运行时间如何根据输入大小n进行操作的图表：

因此，对于n = 2^4 to 2^30的输入大小，确切的运行时间是（按行）：

 [1]  0.000  0.000  0.000  0.000  0.000  0.000  0.000
 [8]  0.000  0.000  0.000  0.000  0.001  0.000  0.000
[15]  0.002  0.004  0.013  0.018  0.053  0.079  0.231
[22]  0.358  0.963  1.772  4.626  9.713 25.582

现在，这有点奇怪，因为当2的幂从奇数变为偶数时，运行时间仅增加1.5，但是当其从偶数变为奇数时，运行时间增加了三倍。因此，当我加倍输入时，我的运行时间平均增加(3 + 1.5) / 2 = 2.25的倍数。实际上，似乎当n任意大时，Odd to even和even to Odd的幂参数的两个变化都导致运行时间乘以常数2.25，换句话说：随着n变大，运行时间乘数收敛到2.25。

如果我的算法非常复杂，是否可以通过此分析来说明其时间复杂性？

Answer 1

我认为，对于许多算法来说，找出一条很好地拟合数据的曲线，然后将该表达式用作工作复杂度是完全合理的。为了使此方法正常工作，您可能需要为算法放弃“较小”的输入大小，而将注意力放在较大的输入大小上，以最大程度地减少非渐近开销的影响。

例如，我们可以说它很可能比平方增长快，因为求解f（30）的常数然后计算对f（20）的期望给出了一个太大的数字，这意味着我们的函数渐近地增长速度比平方增长快得多。如果我们假设一个指数函数并求解f（30）的常数，我们会得到一个f（20）的期望值，该期望值与实际数字更接近（尽管稍低一些，所以我们的函数可能会增长得更慢）比A * 2 ^ n…，但是我们可能可以引入一个新的因子B来找到A * 2 ^（Bn）并变得更近一点。]

这不是计算您要查看其图的函数的理论渐近时间复杂度的有效方法或可接受的方法，但是我认为基于此图可以很好地说明您的渐近复杂度可能是指数级的，基数约为2。

实际上，您的函数看起来像是将值加倍并将它们交替三倍。如果确实如此，那么您希望n的每两个增量都会产生六倍的增长； 6的平方根约为2.45，因此您的函数实际上可能是像A * 2.45 ^ n这样的指数，或者至少比使用基数2更适合。

Answer 2

C(4 * n) = (1.5 * 3) * C(n)提示您在O(n^1.08)中具有复杂性-1.08 ~ log(4.5)/log(4)。

当然，这只是一个提示，我们不能渐进地证明任何事情。