i ^ k的循环复杂度

Question

考虑以下循环（k-正整数）：

// 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

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

注意 ，因此继续将其提高（k）t倍会导致。

现在让我们解决： 。与询问相同：。拿一个 双方终于得到： 。