complexity-theory - 2n^2 + n 的复杂度

Question

如果一个复杂的问题2n^2 + n可以在 24 个单位时间内解决n = 2，需要多长时间n = 4？

有人告诉我答案是 48。但我相信它应该是 24^2，因为算法的复杂度是O(n^2).

感谢是否有人可以启发我。

score 2 · Accepted Answer

大 O 符号只是渐近符号。严格来说，f(n)=O(n^2) 的意思是，存在 A,B 个实数和 n0 个整数，使得 An^2 <= f(n) <= Bn^2，对于 n >= n0。

因此，首先如果 n < n0 趋势甚至不必遵循 n^2。其次，对于 n >= n0，您只能保证 f(n) 是有界的（如上所述）。如果您想近似，O(n^2) 意味着对于较大的 n，您可以删除低阶项 f(n) --> 2n^2，但是，对于较小的 n，这将引入重大错误。

在您的情况下，您具有性能的确切函数形式，f(n) = 2n^2+2，所以您应该使用它！

假设每一步都需要时间 T0 和恒定时间 C，则 T(n) = T0*(2n^2+n) + C。如果 C = 0，则：

score 2 · Accepted Answer

复杂度 O(f(n)) 包括所有需要 c*f(n)+d 时间的计算，其中 c 和 d 是常数。如果 d=0 则：

在 n=2 且复杂度 O(2n^2+2) 为 24 的情况下：

24 = (2*2^2 + 2)*c，因此 c = 24/10 = 2.4

现在我们计算 n=4：

(2*4^2+4)*2.4= 36*2.4 = 86.4 个时间单位

如果 d 不为 0，则 c = (24-d)/10 并且对于 n=4，它需要

36*(24-d)/10 +d = 86.4 +0.9d

因此，答案不可能是 48，这还意味着线性算法

score 1 · Accepted Answer

我当然不认为会这样24^2。由于您在谈论O(n^2)，并且给您一个示例，该示例需要 24 个单位的时间n = 2，因此对于 n = 4，完成时间大约需要 4 倍（2^2 = 4; 4^2 = 16- 大约 4 次）。

如果你要以不同的方式计算它，插入n = 2你2*n^2 + n得到10. 如果10 = 24这意味着每个周期需要 2.4 个单位的时间。然后，插入n = 4你得到2*4^2 + 4 = 36并乘以2.4你得到86.4

score 0 · Accepted Answer

使用 Ruby 作为数学语言，OP 的公式是

f = -> x { 2 * x ** 2 + x }

(1) 假设算法的一步需要 1 个单位的时间，答案是50，因为常数项c是

c = 24 - f.( 2 ) #=> 10
# and
c + f.( 4 ) #=> 50

在这个假设下，答案是 50。

(2) 但是，如果我们允许算法的一步采用e时间单位而不是 1 个时间单位，那么常数c将是：

24 - e * 10

运行时间n == 4为

24 + e * 26        # gives 50 for e == 1

(3) 加上一个额外的假设，即常数时间为零（即，给定的公式是精确的），我们有

24 - e * 10 == 0

Candide、bcorso和Milky Dinescu的回答也适用。

虽然 OP 问题并没有从字面上说明 1 step == 1 time unit，但我仍然觉得这是作者的意图，也是基于50.

4 回答 4