我正试图找到一种方法，在大小为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(时间内对数组中的每个整数进行运算，只使用算术运算(-，+，*，/，%(。我能想到的最明显(不正确(的方法是简单地将每个整数(N-I(乘以，但这并不需要恒定的时间。我也想过用平方取幂，但对每个整数进行运算需要log_2(N-I(时间，而这个时间不是常数。
128是2^7，将一个数字乘以128^k会使其二进制表示向左移动7*k个位置。
1 * (128^3) + 2 * (128^2) + 3 * (128^1) + 4 * (128^0)
= 1000000000000000000000 + 1000000000000000 + 110000000 + 100
为了回答标题问题：可以证明，如果这些运算的数量不变，就无法使数字足够大，以获得足够大的指数。
为了回答根本问题：您可以使用有时归因于Horner的多项式评估方法：((1 * 128 + 2) * 128 + 3) * 128 + 4。请注意，除非您通过某种方式进行修改，否则操作bignums仍将花费您的时间(n2(。
如果你确实在使用bignum，那么有一种更复杂的分治方法，假设bignum乘法比学校方法运行得更快，那么它应该更快。其思想是将输入一分为二，使用递归分别计算下半部分和上半部分，然后将它们放在一起。在你的例子中，这看起来像
(1 * 128 + 2) * 128^2 + (3 * 128 + 4),
其中我们通过重复平方来计算项128^2(即128^(n/2)(。操作计数仍然是O(n(，因为我们有递归
T(n) = 2 T(n/2) + O(log n),
属于情况1。在实践中，无论特定实现具有何种渐进复杂性，运行时间都将由大乘法决定。