有人可以告诉我以下嵌套循环的时间复杂度:
for(i=1;i<n;i+=i)
{
for(j=1;j<n;j*=j)
//O(1)
}
根据我,它将是O(log(n)* log(log(n))因为外部循环将运行log(n)次,因为我们有效地将i乘以2每次迭代。并且在内部循环中我们正在平方在每次迭代中循环计数器j。所以最终的复杂性是这两者的乘积。这是正确还是有其他答案。提前谢谢:D
是的,复杂性是O(log2(n) * log2(log2(n)))
。
内环的指数j
遵循递归关系j(k) = j(k-1)^2
,即j(k) = j(0)^(2^k)
(通过归纳证明)。假设j(0) = 2
(不是1
,因为否则你会无限循环)。
因此,内循环的迭代次数k
验证
j(k) >= n
<=> 2^(2^k) >= n
=> k >= log2(log2(n))
外循环的迭代次数是> = log2(n)
。