此幂函数的时间复杂度

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

go playground:

所以，总执行次数为1 + 2 + 4 + ... + 2^k

并根据等比级数公式

a(1-r^n) / (1-r)

执行次数总和为2^k，其中k为二叉树的高度

因此时间复杂度为2^logn

我说的对吗？谢谢:)

Answer 1

是的。

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

在每次调用中，您进行两次调用，将 n 除以二，因此树的高度为 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)。

此幂函数的时间复杂度

Time complexity of this power function

big-o

go