algorithm - 在不使用 * 运算符且不使用时间复杂度小于 O(N) 的情况下按位相乘两个数字

Question

我需要一种算法来将两个数字相乘，而不使用乘法 (*) 运算符并且不使用复杂度低于 O(N) 的按位，我想出了最明显的一个

int m = 6, n = 5, sum = 0;
for(int i = 0, i<n, i++)
    sum += m;

但这 O(N) 对我不起作用。

Answer 1

我有以下解决方案

public static int mult(int m, int n) {
        int amount = 1;
        int bSum = 0;
        int sum = 0;
        int current = m;
        while (bSum + amount <= n) { 
            sum += current;
            current = current + current;
            bSum += amount;
            amount = amount + amount;
        }
        // bSum = 1+2+4+ ... + 2^k = 2^(k+1) - 1
        // cycle pass log(n) times

        if (bSum < n) {
            sum += mult(m, n - bSum); // n - bSum less n/2
        }
        return sum;
    }

复杂度为 O(log(n)+log(n/2)+log(n/4) + ...) =O(log(n)+log(n) - log(2) + log(n) - log(4))。总和的log(n)总数为O(log(n))。从这个解决方案的最终复杂性 O(log^2(n))。