问解释nC2是如何Θ(n^2)的
EN

Stack Overflow用户

提问于 2014-06-20 10:59:40

回答 1查看 1.6K关注 0票数 1

在CLRS一书中，第69页中说nC2是Θ(n^2)中的单位划分和征服(U-4)。有人能说明这一结果是如何正确的吗？

回答已采纳

发布于 2014-06-20 11:12:27

nC2 = n*(n-1)/2 = (n^2-n)/2；

提示:

对于某些常量，如(n^2-n)/2和n = 2的值，c1 < 1/4将大于c1*(n^2)。同样，对于c2 = 1和n = 2的值，它也将小于n = 2。所以，这是一个类似三明治的情况。类似地，它将被夹在n和常量c的其他值中。因此，nC2 is Θ(n^2)。

票数 6

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/24325732

复制

相似问题

问解释nC2是如何Θ(n^2)的EN