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

Answer 2

复杂度为： (log n + 1)*(-1 + squareroot(1+4n))/2 = O(squareroot(n)*log n)

---

log n 以 2 为底。

假设 n 是 36。

外部循环将迭代 log n + 1 次，因为每次 36、18、9、4、2、1 时该值减半。

内循环有 j 个值 = 1,3,6,10,15,21,28,36。每个 j 值都可以计算为 AP 1+2+3+4+5....w 中项的总和= w(w+1)/2。所以 w(w+1)/2 = n。求解这个二次方程我们得到 w=(-1+sqrt(1+4n))/2 即内循环的迭代次数。对于 n=36，w=8。

因此，总复杂度为：log n * sqrt(n)。