我还要说这是不正确的。我的直觉是,如果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)
,因为可能会发明一些相当曲折的反例。