Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
在 CLRS 一书中,第 69 页中说 nC2 在单位分而治之(U - 4)中是 Θ(n^2)。谁能解释这个结果是如何正确的?
nC2 = n*(n-1)/2 = (n^2-n)/2;
暗示 :
(n^2-n)/2将大于c1*(n^2)某些常量,例如c1 < 1/4和 的值n = 2。同样,它将小于和c2*n^2的值。所以,这是一个类似三明治的情况。类似地,它将被夹在 n 和常数 c 的其他值中。因此,。c2 = 1n = 2nC2 is Θ(n^2)
(n^2-n)/2
c1*(n^2)
c1 < 1/4
n = 2
c2*n^2
c2 = 1
nC2 is Θ(n^2)