algorithm - 从运行时分析推导出时间复杂度

Question

作为一名非计算机科学家，我发现很难理解时间复杂度及其计算方式，所以我的问题是，某个算法/程序的时间复杂度是否可以通过在越来越大的输入数据上运行而得出，然后看看运行时间如何随着输入大小的增加而变化n。

我问这个是因为我用 C++ 编写了一个算法，它基本上使用单个 cpu 内核和单个线程（3GHZ 处理器）对 2D 图像进行像素着色。我测量了输入大小的运行时间，从2^4到2^30是 size 的矩阵 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 变得任意大时，power 参数的变化Odd to even和even to Odd导致运行时乘以常数 2.25，换句话说：随着 n 变大，运行时乘数收敛到 2.25。

如果我的算法非常复杂，有没有办法从这个分析中说出它的时间复杂度？

标签： algorithmtime-complexityruntimebig-o

Answer 1

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

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