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

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)).

Calculate the time complexity of the following function