这个函数"循环"的复杂性/大O是多少

Question

void mystery2 (int n)
{
  int i;
 for (i = 1; i <= n; i++) {
   double x = i;
   double delta = 1 / (double)i;
   while ( x > 0 )
     x -= delta;
  }
return 0;
}

为什么是BIG O,这个函数的时间复杂度是O(n ^ 3)而不是O(n ^ 2)？

我做的是当i = 1 ==> 1次迭代时,i = 2 ==> 2iterations(in while)i = 3 ==> 3次迭代........ i = n ==> n次迭代,如果我们总结所有迭代,我们得到1 + 2 + 3 + 4 .... + n = n*(n + 1)/ 2.所以我在这里错过了什么？

Answer 1

这是因为内部循环像这样运行.

For i=1, inner loop runs 1 time,
For i=2, inner loop runs 4 time,
 //because x=2 and delta=0.5 so for x to become 0 it has to iterate 4 time 
For i=3, inner loop runs 9 time
 //because x=3 and delta=0.33 so for x to become 0 it has to iterate 9(atleast) time 
and so on..

因此内循环运行i^2时间和等式变为1^2+2^2+3^2+...+n^2=n(n+1)(2n+1)/6等于O(n ^ 3)复杂度.