求含受外层循环影响的嵌套循环函数的Big-O复杂度

你的判断是正确的，这段代码的整体时间复杂度确实是O(N⁴)，可以通过求和推导严谨验证：

• 外层循环执行次数：i从0到N²-1，总共执行N²次。
• 内层循环执行次数：对于每个i，j从0到i-1，执行i次。总操作次数是等差数列求和：0 + 1 + 2 + ... + (N² - 1)
• 用等差数列求和公式计算总和：
  总和 = (N²) * (N² - 1) / 2 = (N⁴ - N²) / 2
• 当N趋向于极大值时，低阶项N²和常数系数1/2对复杂度的影响可以忽略，因此最终时间复杂度为O(N⁴)。

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