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

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 .但我仍然对如何计算 Big-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 )
因为我们只在 i<=n 时循环并且因为 i 取值 1, 2^2, 3^2,..., k^2 <=n，这意味着当 i=k 超过 sqrt(n )。因此复杂性似乎是 O(k)，这意味着 O(sqrt(n))。