algorithm - 在 O(n) 时间内计算 2^n

Question

在不使用位移的情况下，有什么方法可以在 O(n) 时间内计算出 2^n 吗？

我正在考虑使用内存的解决方案，因为我总是先从较低的 n 开始计算。即

d = dict()
def pwr2(n):
    if n == 0:
       return 1
    if n == 1:
       return 2
    if n in d:
       return d[n]
    d[n] = 2 * pwr2(n-1)
    return d[n]

但我不太确定复杂度是多少。

编辑:我应该补充一点，我正在使用算法的这一部分以比 O(n^2) 更快的时间将二进制转换为十进制。作为我的分而治之算法的一部分，我必须乘以 2 的递增幂，这就是我尝试内存的原因。

EDIT2:在这里发布我的完整算法以帮助解决困惑pwr2dict = 字典()

def karatsuba(x, y):
    // use karatsuba's algorithm to multiply x*y


def pwr2(n):
    if n == 0:
        return 1
    if n == 1:
        return 2
    if n in pwr2dict:
        return pwr2dict[n]
    pwr2dict[n] = karatsuba(pwr2(n-1),2)
    return pwr2dict[n]


def binToDec(b):
    if len(b) == 1:
        return int(b)
    n = int(math.floor(len(b)/2))
    top = binToDec(b[:n])  # The top n bits
    bottom = binToDec(b[n:])  # The bottom n bits
    return bottom + karatsuba(top, pwr2(len(b)-n))

print binToDec("10110") // Prints 22

Answer 1

我认为你想多了你的问题。 2^n 只是意味着将二乘以自身 n 次。所以从 1 到 n 的简单循环就可以解决问题:-)

r = 2
for 1 to n do
  r = r * 2
end

这是在 O(n) 中运行的解决方案，计算 2^n 的真正问题是，在现代计算机上你会达到架构字长对于非常小的 n，例如 32、64 或 128。然后您必须使用任意长度的整数，这可能不会给您足够的 O(n) 时间，但这是一个不同的问题 :-) 理论上，它可以在 O(n) 中轻松完成。

编辑

好的，如果我理解正确的话，您有一个非常长的二进制字符串，并且您想将其转换为十进制。

我会按如下方式实现它:

将长度为 n 的二进制字符串放入数组 s(可以是位图以节省空间，也可以是支持这些的编程语言中的字符串)。反转字符串，使 LSB 位于索引 0(如果不是这样的话)。

e := 1
r := 0
for i := 0 to (n - 1) 
  if s[i] = 1
    r := r + e
  end
  e := e * 2
end

反转字符串可以在 O(n) 中完成，伪代码只有一个从 0 到 n - 1 的循环>，所以这也在 O(n) 中。位串取反可以避免循环中一点点简单的运算。而不是 r 必须是任意长度的整数类型。