i ^ k的循环复杂度

Question

考虑此循环：

// i^k as in i raised to the power of k
for (int i = 2; i <= n; i = i^k) {
    // some O(1) expressions or statements
}

为什么要运行log_k(log(n))次？

Answer 1

您的问题本质上是：我们需要多少次将2提升到k的幂，直到它大于。

请注意）t次得出]现在让我们解决： 2 ^ {log_2（N）}”>。与询问相同：”>以一个双方终于搞定了： log_k（log_2（n））”>。

Answer 2

[如果您将t视为循环中的迭代次数，则找到最大t以使以下不等式成立（我们还认为n足够大，以致不违反不等式：]]

您可以看到，迭代次数t等于问题中指定的时间复杂度。

Answer 3

在您的问题中，我们想知道for循环经过了多少次，因此我们必须找到此等式的x：2^x^k=2^k^x= n，因此我们有x^k = log(n)而不是x = logk(log(n))。