在不使用位移的情况下,有什么方法可以在 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
最佳答案
我认为你想多了你的问题。 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
必须是任意长度的整数类型。
关于algorithm - 在 O(n) 时间内计算 2^n,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29788843/