该C++函数的运行时间复杂度是多少？请说明原因

步骤1：计算sum的最终值 #

• 外层循环执行n次，每次外层循环对应的内层循环也执行n次，内层循环每次执行sum += i。
• 对每个i，内层循环会给sum累加n次i，即每个i贡献n*i到sum中。
• 因此sum的总值为：n*(1+2+...+n)，而1到n的等差数列和为n(n+1)/2，代入后可得sum = n * [n(n+1)/2] = n²(n+1)/2。当n趋近于无穷大时，(n+1)/2可近似为n/2，所以sum的量级为O(n³)。

步骤2：分析各循环的时间复杂度 #

• 前两层嵌套循环的总执行次数是n*n = n²，对应的时间复杂度为O(n²)。
• 第三个循环的执行次数等于sum的最终值，也就是O(n³)，这是整个函数中耗时最长的部分。

结论 #

整个函数的运行时间复杂度由第三个循环主导，最终为O(n³)。

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