第一次循环:O(n)

第二个循环:i 平均为 n/2，你可以有一个精确的公式，但它是 O(n²)

Second loop: i is in average n/2, you could have an exact formula but it's O(n²)

第三个循环在第二个循环内发生 i 次，所以平均 n/2 次.它也是 O(n²)，估计它.

Third loop happens i times inside the second loop, so an average of n/2 times. And it's O(n²) as well, estimating it.

所以它是O(n*n²*(1 + 1/n*n²))，我会说O(n^4).1/n 来自这样一个事实，即第三个循环在第二个循环内发生了大约 1/n 次.

So it's O(n*n²*(1 + 1/n*n²)), I'd say O(n^4). The 1/n comes from the fact that the third loop happens roughly 1/n times inside the second one.

这只是一个大概的估计，没有严格的证据，但应该是正确的.您可以通过自己运行代码来确认.

It's all a ballpark estimation, with no rigorous proof, but it should be right. You could confirm it by running code yourself.