标签： Python

前几天刷 Leetcode 算法题，有一道求幂的相对容易的题目，常规思路自然是将数字 x 连续相乘 n 次，再考虑 n 的正负，我用 Python 3 去实现，算法大致如下：

def myPow(x, n):
    s = 1
    if n == 0:
        return 1
    if n > 0:
        while n > 0:
            n -= 1
            s *= x
        return s
    else:
        m = -n
        while m > 0: 
            m -= 1
            s *= x
    return 1/s

看似面面俱到，提交测试一遍，傻眼了。

超出时间限制：291 / 304 个通过测试用例

细节主要卡在了 0.00001 的 2147483647 次方上，指数太大，上述的遍历相乘算法，把 x连续乘 n 次，时间复杂度为 O(n)，随着 n 的增长而线性增长，指数一大，时间自然会超出限制。这时我便开始想方法把时间复杂度降低下来。Python 是通过 C 语言实现的，内置的 pow() 函数的实现原理可以用来参考。我开始找 Cpython 的源码。

里面最核心的部分如下：

if (Py_SIZE(b) <= FIVEARY_CUTOFF) {
/* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
/* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf */
    for (i = Py_SIZE(b) - 1; i >= 0; --i) {
	digit bi = b->ob_digit[i];
	for (j = (digit)1 << (PyLong_SHIFT-1); j != 0; j >>= 1) {
		MULT(z, z, z);
		if (bi & j)
		MULT(z, a, z);
	}
    }

我惊呆了。不是代码本身，而是它给出的注释。Python 作为一款开源语言，成百上千的程序员时时刻刻给它贡献代码，这内置的 pow() 函数参考了 HAC 聚类算法的二进制快速幂，其理论来源是一份 pdf 文献。

至此，我刷 Leetcode 时候的眼界彻底放开，我不在乎题目求解本身，我开始尝试挖掘背后算法的来源。