关于组合数C(n,2)的Big O复杂度及转换公式的问询

复杂度结论 #

f(n) = C(n,2)的Big O表示是O(n²)，同时它的渐近紧确界为Θ(n²)——这是因为C(n,2)本身属于二次多项式级别的函数。

公式n(n-1)/2的含义 #

C(n,2)是组合数学中的概念，代表从n个不同元素中选出2个元素的无顺序组合总数，它的计算公式为：
$$C(n,2) = \frac{n(n-1)}{2}$$
将其展开后得到$\frac{1}{2}n^2 - \frac{1}{2}n$。在渐近复杂度分析中，我们只关注函数增长的主导项（即最高次项），并且可以忽略最高次项的常数系数——当n趋近于无穷大时，低次项和常数对整体增长趋势的影响可以忽略不计。因此，$\frac{n(n-1)}{2}$的渐近复杂度为Θ(n²)，对应的Big O表示自然是O(n²)。

内容的提问来源于stack exchange，提问作者Agastya Krothapalli