这个函数的 complexity/BIG O 是什么 "loops"

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 ==> 2次迭代（同时）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) 复杂度。

Answer 2

我想你是把它看成一个标准的整数递减循环，我一开始也是这样做的，但是数字是双倍的，delta 不是 1 但实际上是 1 / (double)i，因此完全递减 x 所需的内循环迭代次数不会随着 n 的增加而线性增加，而是急剧增加，因为 delta 随着 n 变小]变大。

这个函数的 complexity/BIG O 是什么 "loops"

what is the complexity/BIG O of this function "loops"

c

complexity-theory

big-o

loops

time-complexity