组合函数的时间复杂度：O(nC2)还是O(n²)？

你的函数的时间复杂度是O(n²)，原因如下：

大O符号的核心规则 #

大O描述的是算法运行时间随输入规模n增长的增长趋势，它会忽略常数系数和低阶项，只保留最高阶的主导项——因为当n足够大时，常数和低阶项对整体运行时间的影响可以忽略不计。

计算你的函数的迭代次数 #

你的函数的总迭代次数是组合数n choose 2，展开后是：

nC2 = n*(n-1)/2 = (n² - n)/2 = (1/2)n² - (1/2)n

这里的最高阶项是(1/2)n²，根据大O的规则，我们忽略系数1/2和低阶项-(1/2)n，最终时间复杂度记为O(n²)。

为什么不用O(nC2)？ #

虽然nC2是你函数的精确迭代次数，但在算法分析中，我们更关注算法的增长量级。nC2和n²属于同一个增长量级——当n翻倍时，两者的运行时间都会变为原来的4倍左右。因此行业内统一用更简洁的O(n²)来归类这类算法的时间复杂度，而非具体的O(nC2)。

举个直观的例子：当n=1000时，nC2=499500，n²=1000000；当n=10000时，nC2=49995000，n²=100000000。可以看到，随着n增大，两者的差距比例会稳定在约1:2，但增长的核心趋势都是平方级的。

内容的提问来源于stack exchange，提问作者Salty Sodiums