1

在 CLRS 一书中,第 69 页中说 nC2 在单位分而治之(U - 4)中是 Θ(n^2)。谁能解释这个结果是如何正确的?

4

1 回答 1

6

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)

于 2014-06-20T11:12:27.810 回答