含嵌套while循环的算法时间复杂度计算及O(n³)可能性问询

首先，你的时间复杂度计算是正确的，我们可以通过更严谨的推导验证结论：

• 外层for循环执行次数为n-1次（i从1到n-1）
• 对于每个i，内层while循环的执行次数是i² - 1次（j从1开始，直到满足j < i²停止，总共递增i² - 1次）
• 总执行次数为求和式：$\sum_{i=1}^{n-1} (i² - 1)$

展开并计算这个求和式：
$\sum_{i=1}^{n-1} i² - \sum_{i=1}^{n-1} 1$
根据平方和公式$\sum_{i=1}^k i² = \frac{k(k+1)(2k+1)}{6}$，代入k = n-1后：
$\frac{(n-1)n(2n-1)}{6} - (n-1)$

该多项式的最高次项为$\frac{n³}{3}$，因此时间复杂度确实是O(n³)。

针对你的核心疑问：仅含两个循环的算法完全可以具有O(n³)的时间复杂度，你自己写的这段代码就是典型实例。

时间复杂度的本质是描述算法执行次数随输入规模n增长的渐近趋势，它和循环嵌套层数没有绝对的一一对应关系——循环层数只是影响复杂度的因素之一，更关键的是每层循环的迭代次数与输入规模的关联方式。

再举几个双循环实现O(n³)复杂度的例子：

• 外层循环i从1到n，内层循环j从1到n*i：总执行次数为$\sum_{i=1}^n n*i = n * \frac{n(n+1)}{2} = O(n³)$
• 外层循环i从1到n，内层循环j从1到i²：总执行次数为$\sum_{i=1}^n i² = O(n³)$

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