performance - 当给定迭代次数和总时间时，如何找到算法的时间复杂度？

Question

当我看到一个算法时，我明白如何找到算法的时间复杂度，但当我被给出次数时，我似乎无法理解如何计算它算法被执行，所花费的时间。

有时我可以得到它，当它是 O(n)、O(n) 或 O(n^2) 这样显而易见的事情时，但以这个问题为例:

算法运行大小为 n 的给定输入。如果 n 为 4096，则运行时间为 512 毫秒。如果 n 为 16384，则运行时间为 1024 毫秒。如果 n 为 36864，则运行时间为 1536 毫秒。

时间复杂度是多少？

我看到它是 n * 2，t * 1.5，但我不太确定如何计算。

谢谢你的帮助:)

Answer 1

我会说对于这类问题你需要的不仅仅是三个数据点，因为系统的复杂性而不仅仅是算法。

我要做的是比较迭代次数和耗时，看看您是否可以找到与标准时间复杂度之一相匹配的模式:

• 常数:O(c) 其中 c 是常数。
• 线性:O(n)
• 多项式:O(n^c)，其中 c 是常数(或者甚至像 O(n^2 + n^6) 这样复杂的东西)
• 指数:O(c^n)，其中 c 是常数。
• 对数:O(log|n|)
• 不管这叫什么:O(n log|n| )

让我们来解决您的问题:

n     | time
4096  | 512 ms
16384 | 1024 ms
36864 | 1536 ms

当 n 增加 4 倍(从 4096 到 16384)时，时间增加 2 倍(从 512 到 1024 毫秒)。

当 n 增加 9 倍(从 4096 到 36864)时，时间增加 3 倍(从 512 到 1536 毫秒)。

与此匹配的函数是 f(n) = n^(1/2)。当 n 增加 4 倍时，f(n) 增加 sqrt(4) 倍等...

所以这是 O(n^.5) 阶，它是多项式

TLDR:将其绘制出来并将其与时间复杂度的通用函数相匹配。在现实世界中，您可能需要三个以上的数据点。

编辑:我想补充一点，这真的应该更复杂。每种时间复杂度都可能有一个常数项。 IE。 O(n^c) 更可能是 O(n^c + K)，其中 K 是常数。为简单起见，我们在写出来时忽略了常量，但它会显示在您的图表中。