algorithm - 当 N 以大 O 表示法翻倍时的运行时间比

Question

我了解到，使用大 O 表示法

O(f(n)) + O(g(n)) -> O(max(f(n),g(n))

O( f(n) )* O( g(n)) -> O( f(n) g(n))

但是现在，我有这个输入大小 N 的运行时间 T 等式

T(N) = O(N^2)  // O of N square

我需要找到比例T(2N) / T(N)

我试过这个

T(2N) / T(N) --> O((2N)^2) /O( N^2)  --> 4

它是否正确？还是上述划分无效？

Answer 1

我还要说这是不正确的。我的直觉是，如果T(N)是O(N^2)，那么T(2N)/T(N)是O(1)，与您的建议一致T(2N)/T(N) = 4。然而，我认为直觉是错误的。

考虑一个反例。

T(N)如果是奇数，如果是偶数，则为 1 ，N如下N^2所示N。

这很清楚O(N^2)，因为我们可以选择一个常数p=1，这样T(N) ≤ pN^2就足够大了N。

是什么T(2N)？这是(2N)^2 = 4N^2，如下所示，因为2N总是偶数。

因此T(2N)/T(N)，什么4N^2/1 = 4N^2时候N是奇数，4N^2/N^2=4什么时候N是偶数，如下所示。

显然T(2N)/T(N)不是 4。然而，它是 ，O(N^2)因为我们可以选择一个常数q=4，使得T(2N)/T(N) ≤ qN^2足够大N。

下图的 R 代码

x=1:50
t1=ifelse(x%%2, 1, x^2)
plot(t1~x,type="l")

x2=2*x
t2=ifelse(x2%%2, 1, x2^2)
plot(t2~x,type="l")

ratio=t2/t1
plot(ratio~x,type="l")

这个问题很有趣，我觉得它属于纯数学领域，即序列限制等。我没有受过纯数学方面的训练，我会害怕声称T(2N)/T(N)总是如此 O(N^2)，因为可能会发明一些相当曲折的反例。

Answer 2

即使 T(N) = Θ(N²) (big-theta) 这也行不通。（我什至不打算谈论大 O。）

c1 * N² <= T(N) <= c2 * N²
c1 * 4 * N² <= T(2N) <= c2 * 4 * N²

T(N) = c_a * N² + f(N)
T(2N) = c_b * 4 * N² + g(N)

对于 c_a 和 c_b 介于 c1 和 c2 之间，以及 f(N) 和 g(N) N² 的小-o。（感谢 G. Bach！）因为 c_a、c_b、f(N) 和 g(N) 都可以是各种各样的东西，所以没有什么可以保证商等于 4。例如，取 c_a = 1, c_b = 2 和 f(N) = g(N) = 0。除以它们，你得到

T(2N)/T(N) = (2 * 4 * N²)/N² = 8

Answer 3

好问题！

这是不正确的。

运行时间与时间复杂度不同（此处为 Big O）。时间复杂度表示它的运行时间不会比常数N^2更差。运行时间可能完全不同，可能非常低，可能接近渐近极限。这完全取决于隐藏常数。如果有人问你这个问题，这是一个技巧问题。

隐藏常量是指执行的原始指令的实际数量。因此在这种情况下，操作的总数可能是：

5*N^2

或者

1000*N^2.

或许

100*N^2+90N

或者也许只是

100*N (Recall this is also O(N^2))

该因素取决于实现和执行的实际指令。这是从算法中发现的。因此，无论哪种情况，我们都简单地说 Big-O 是O(N^2)。