gpt4 book ai didi

algorithm - i^k 的循环复杂度

转载 作者:行者123 更新时间:2023-12-03 02:36:56 25 4
gpt4 key购买 nike

考虑这个循环(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)) 次?

最佳答案

你的问题本质上是:我们需要多少次2k次方,直到它大于n = 2^{log_2(n)} .

请注意(2^k)^k = 2^{k*k} ,因此继续提高它(k)t次会导致 2^{(k^t)} .

现在我们来解决:2^{(k^t)} > 2^{log_2(n)} 。与询问相同:k^t > log_2(n) 。拍个log_k两边求最后得到:t > log_k (log_2 (n)) .

关于algorithm - i^k 的循环复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59115571/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com