计算以下函数的时间复杂度

Question

如何计算以下函数的时间复杂度？

int Compute (int n)
{
   int j = 0;
   int i = 0;
   while (i<=n)
   {
       i = 2*j + i + 1;
       j++;
   }
   return j-1;
}

现在，我知道循环具有O（n）时间复杂度，但在这种情况下，I以更快的速度增长。一次又一次地迭代，我发现，对于每一个第m次迭代，I=m^2。但我仍然不知道如何计算大O。

Answer 1

如果您查看i和j的值进行几次迭代：

i=1
j=1

i=4
j=2

i=9
j=3

i=16
j=4

等等。通过数学归纳，我们可以证明i取平方值：（2*n n^2 1=（n 1）^2）

因为我们只有在我