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))。