这个幂函数的时间复杂性

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

并根据几何级数公式

a(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=26n1=13n2=6(13/2层(n3=3n4=1(占用3/2的楼层(

假设2的x_th次方大于或等于x。那么，

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

这就是你如何找到你的算法的时间复杂性为log2(n(。