以下代码的复杂性是什么？

Question

找到以下代码的时间复杂度.给出的答案是O(log(n)*n ^ 1/2),但我没有得到它.我希望有人解释一下.

i=n;
while(i>0)
{
  k=1;
  for(j=1;j<=n;j+=k)
    k++;
  i=i/2;
}

Answer 1

以此代码段为例:

k=1;
for(j=1;j<=n;j+=k)
  k++;

j各种迭代的值将是1, 3, 6, 10, 15, 21, 28, ....

请注意,这些数字具有封闭形式(m+1)(m+2)/2,其中m是经过的迭代次数.如果我们想知道这个循环将运行多少次迭代,我们需要解决(m+1)(m+2)/2 = n,这有解决方案m = (sqrt(8n + 1) - 3))/2 = O(sqrt(n)).所以这个循环会运行O(sqrt(n))一次.

外循环将运行O(log(n))一次(这很容易看到).总的来说,我们有O(log(n)sqrt(n)).

编辑:或者比(m+1)(m+2)/2 = n直接解决更容易只是注意到(m+1)(m+2)/2 = O(m^2),所以O(m^2) = n暗示m = O(sqrt(n)).