Divide-and-conquer algorithm in multiplication

$$ x^n=x\cdot x\cdot x\cdots x $$

时间复杂度为O(n)，有n-1个乘法

$$ x^n=x^\frac n2\cdot x^\frac n2\qquad\mbox{if x is even}\\ x^n=x^\frac{n-1}{2}\cdot x^\frac{n-1}{2}\cdot x\qquad\mbox{if x is odd} $$

变成了两个相同的子问题和一次乘法

$T(N)=T(N/2)+\Theta(1)$

时间复杂度为：$T(N)=O(\log_2 n)$

C语言实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int divide(int x, int n) {
    if (n == 1 || n == 0) // 递归出口，
        return x;
    else {
        if (n % 2 == 0) // 如果是偶数
            return divide(x, n / 2) * divide(x, n / 2);
        else // 如果是奇数
            return divide(x, (n + 1) / 2) * divide(x, (n - 1) / 2);
    }
}