T(n) = θ(1) + 2T(n/2) + θ(n) + θ(1) = 2T(n/2) + θ(n) 怎么可能成立呢？
How could it be true that T(n) = θ(1) + 2T(n/2) + θ(n) + θ(1) = 2T(n/2) + θ(n)?
我对这段伪代码的时间复杂度有疑问。
enter image description here
如下，
T(n) = θ(1) + 2T(n/2) + θ(n) + θ(1)
= 2T(n/2) + θ(n)
你能解释一下为什么这两个 'θ(1)' 在第二个等式中被忽略了吗？
是不是因为和'θ(n)'相比没有意义？
它们是常数，不会根据 n
的值而改变
我对这段伪代码的时间复杂度有疑问。 enter image description here
如下，
T(n) = θ(1) + 2T(n/2) + θ(n) + θ(1)
= 2T(n/2) + θ(n)
你能解释一下为什么这两个 'θ(1)' 在第二个等式中被忽略了吗？
是不是因为和'θ(n)'相比没有意义？
它们是常数，不会根据 n
的值而改变