为什么元素两两右乘的双层循环算法时间复杂度为O(N²/2)？

我们设输入数组的长度为N，该算法的总操作数可以通过内外循环的执行次数累加得到：

• 外循环遍历数组元素，索引记为i，取值范围为0 ≤ i ≤ N-2（数组最后一个元素右侧无其他元素，不需要进入内循环）
• 对每个i，内循环从i+1的位置开始遍历到数组末尾，每个i对应的内循环执行次数为N - 1 - i

将所有内循环的执行次数加总，总操作数为：

(N-1) + (N-2) + ... + 2 + 1

这是首项为1、末项为N-1的等差数列，代入求和公式可得：

总操作数 = N*(N-1)/2 = (N² - N)/2 = N²/2 - N/2

当N的数值足够大时，低阶项N/2对整体结果的影响可以忽略，因此总操作数可以近似为N²/2，这就是书中给出O(N²/2)评估结果的来源。
需要注意的是，标准的大O时间复杂度表示法要求省略所有常数系数，因此该算法的标准复杂度写法确实是O(N²)，书中保留1/2的系数只是为了更直观地体现该算法和完整双层循环（总操作数约为N²）的执行效率差异。

你给出的长度为5的示例数组也可以验证这个推导：代入公式可得总操作数为5*4/2=10次，和示例输出的10个计算结果完全对应。

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