此幂函数的时间复杂度

Question

我有这个代码来计算某个数字的幂func power(x, n int) int {    if n == 0 {        return 1    }    if n == 1 {        return x    }    if n%2 == 0 {        return power(x, n/2) * power(x, n/2)    } else {        return power(x, n/2) * power(x, n/2) * x    }}去游乐场：所以，执行的总数是 1 + 2 + 4 + ... + 2^k并根据几何级数公式一（1-r^n）/（1-r）执行时间的总和将是 2^k，其中 k 是二叉树的高度因此时间复杂度为 2^logn我对么？谢谢 ：） 

Answer 1

是的。

考虑递归函数复杂性的另一种方式是（调用数量）**（递归树的高度）

在每次调用中，您进行两次调用，将 n 除以 2，因此树的高度为 logn，因此时间复杂度为 2**(logn)，即 O(n)

在此处查看更正式的证明：

https://cs.stackexchange.com/questions/69539/time-complexity-of-recursive-power-code

Answer 2

每次你将 n 除以 2 时，除非 n <= 1。所以想想有多少次你可以通过除以 0 将 n 减少到 1？让我们来看看，

n = 26 n1 = 13 n2 = 6（占 13/2 的楼层） n3 = 3 n4 = 1（占 3/2 的楼层）

假设 2 的 x_th 次方大于或等于 x。然后，

2^x >= n

or, log2(2^x) = log2(n)

or, x = log2(n)

这就是您如何找到算法的时间复杂度为 log2(n)。