数据结构基础(((x^2+1))^2+1)^2......时间复杂度为什么是2logN

Question

书上原文:

求幂运算, 要计算X^N, 如果N为偶数, 那么X^N = X^(N/2) * X^(N/2) , 如果N为奇数, 那么X^N = X^(N/2) * X^(N/2) * X.
例如: X^62次,算法将如下进行, 它只用到了9次乘法
X^3=(X^2)X, X^7=(X^3)^2X, X^15=(X^7)^2X, X^31=(X^15)^2X, X^62=(X^31)^2
显然, 所需要的乘法次数最多是2logN.

图片:

通过这个例子和一个前辈的指明, 我总结出X^N = ((((x^2)^2+1)^2+1)^2+1)...., 但是如果通过这个求出时间复杂度为2logN?

Answer 1

考虑我们的问题:$ x^n $

对于$ n\neq 1 $我们有$ x^n = (x^{\frac{n}{2}})^2 $ 若n为偶数 $x^n = (x^{\frac{n}{2}})^2 * x $ 若n为奇数.

因此 $ T(n) = T(n/2) + O(1) $

根据主定理,最后的复杂度就是 $ O(\log n) $

或者, 每次递归把把规模缩小2, 那就是 $\log n$ 层(你也可以加上取整符号..) 的递归 ($ \log n $就是求解$ 2^y = n $ 的$ y $), 每层需要最多两次乘法(一次把下一层的结果平方,一次是n为奇数的时候乘上一个x, 因此是两次).
那么很显然需要$ 2\log n $次的加法.