algorithm - 如何在恒定时间内仅使用算术运算来计算指数？

Question

我正在尝试找到一种方法来遍历大小为 N 的整数数组并将这些整数中的每一个乘以 128^((N-1) - i)，其中 N 是数组的长度，i 是索引整数，然后将所有这些结果加在一起。

例如，[1, 2, 3, 4] 的数组输入将返回 1 * (128^3) + 2 * (128^2) + 3 * (128^1) + 4 * (128^0)。

我的算法需要在 O(N) 时间内运行，但指数运算很昂贵，例如，2^3 需要三个运算。所以，我需要找到一种方法来在 O(1) 时间内对数组中的每个整数进行操作，只使用算术运算（-、+、*、/、%）。我能想到的最明显（不正确）的方法是简单地将每个整数（Ni）乘以，但这并不需要恒定的时间。我也在考虑通过平方使用求幂，但这需要 log_2(Ni) 时间来对每个整数进行运算，这不是恒定的。

标签： algorithmcomplexity-theoryexponent

Answer 1

128 是 2^7，将一个数字乘以 128^k 会将其二进制表示左移 7*k 个位置。

1 * (128^3) + 2 * (128^2) + 3 * (128^1) + 4 * (128^0)
= 1000000000000000000000 + 1000000000000000 + 110000000 + 100