c - 以下代码的复杂度是多少？

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