找出以下代码的时间复杂度。 给出的答案是 O(log(n)*n^1/2),但我不明白。 我希望有人对此进行解释。
i=n;
while(i>0)
{
k=1;
for(j=1;j<=n;j+=k)
k++;
i=i/2;
}
最佳答案
取这段代码:
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))
。
关于c - 以下代码的复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19921828/