作为一名非计算机科学家,我发现理解时间复杂度及其计算方式有点困难,所以我的问题是,是否有可能通过在越来越大的输入数据上运行某个算法/程序来推导出它的时间复杂度,然后查看运行时相对于输入大小的增加如何变化 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。如果我的算法非常复杂,有没有办法从这个分析中说明它的时间复杂度?
最佳答案
有 C(4 * n) = (1.5 * 3) * C(n)
建议您在 O(n^1.08)
中有复杂性——
哪里1.08 ~ log(4.5)/log(4)
.
当然,这只是一个提示,我们不能渐近地证明什么。
关于algorithm - 从运行时分析中推导出时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62083210/