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

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

有 C(4 * n) = (1.5 * 3) * C(n)建议您在 O(n^1.08) 中有复杂性——
哪里1.08 ~ log(4.5)/log(4) .

当然，这只是一个提示，我们不能渐近地证明什么。