题目重点：按外层 i、中层 i² 次、内层约 i 次求和，区分代码真实边界与只数循环层数的错误。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- n 为非负整数，内层确实执行与 i 成正比的 Θ(i) 次基本操作；各循环界互不被内部修改。
- 若内层有提前 break、步长倍增或 i² 实为别的表达式，应以真正执行次数重算，不能套用本结论。
解题路线
- 固定一个 i：中层有 i² 次迭代，每次内层 Θ(i)，所以该 i 的工作 Θ(i³)；i=0 的零工作不影响渐近阶。
- 对 i=1…n−1 求和，Σi³=(n(n−1)/2)²，所以总工作 Θ(n⁴)。给上界和下界都由同一多项式阶支撑，比只报 O(n⁴) 更精确。
- 可代 n=2、3 手算各外层成本：n=3 时 i=1 贡献 1、i=2 贡献 8，总 9；公式 `(3×2/2)²=9`。
- 如果 j 从 0 到 n−1 而非 i²−1，总和会变为 nΣi=Θ(n³)；看变量依赖才能判断，不能‘三层循环=立方’。
手动走一遍
n=4：外层 i=0,1,2,3 各约 0,1,8,27 次，合 36；公式 `(4×3/2)²=36`。若内层每次还做 O(log n) 工作，整体会乘上该成本。
规模与取舍
时间 Θ(n⁴)；若只是累加计数器且不分配随 n 增长的存储，辅助空间 O(1)。n 很大时数学计数值在固定宽度整数中可能溢出，但不改变算法操作次数。
易错点与追问
容易失分的边界
- 机械地数三层得到 O(n³)。
- 把 i² 与 i 的依赖当独立 n。
- 只给 O(n⁴) 上界，却忽略该条件下也有 Ω(n⁴)。
- 没核实内层是否真的每次做 i 步。
继续深挖
- 若中层到 i 而非 i²，复杂度如何变？
- 若内层每次 i/2 步，阶数变吗？
- 若 i 每次翻倍，求和怎么变？
- 用公式怎样验证小 n 的操作数？
