此幂函数的时间复杂度

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 >= nor, log2(2^x) = log2(n)or, x = log2(n)这就是您如何找到算法的时间复杂度为 log2(n)。