时间戳

首页 > 解决方案 > 仅使用总和将 2 提高到 n 次方的最有效算法？

python - 仅使用总和将 2 提高到 n 次方的最有效算法？

问题描述

以下算法需要 O(n) 时间。这可以改进吗？

def powerOfTwo(n):
  a = 1
  if (n>0):
    a=2
    while (n>1):
      a=(a+a)
      n=(n-1)
  return a

标签： pythonalgorithm

解决方案

如评论中所述（并由@Mark Ransom 指出），您可以将代码简化为：

def powerOfTwo(n):     
    a = 1     
    for _ in range(n):       
        a += a    
    return a

除非您预先计算2^n了 differentn的值，否则您无法2^n仅使用小于 O(n) 的求和运算来计算。

证明

让我们证明一下。假设有用于计算的k初始值a[i]（在您的示例中为 ） 。k=12^n

然后，在第一次迭代中，你做了一些m添加。因此，您可以获得的最大数量是max(a[i])*m。在第二次迭代中，您m再次进行加法，最大数量是max(a[i])*m*m等等。

我们需要达到多少次循环迭代2^n？为此，我们需要解决一个不等式：

max(a[i])*(m^l) >= 2^n         | take log from both sides
->
log(max(a[i])*(m^l)) >= n
->
log(max(a[i]) + log(m^l) >= n  |  
->
log(m^l) >= n - log(max(a[i])  | exclude log(max(a[i]) because it's constant 
->
log(m^l) >= n
->
l*log(m) >= n
->
l >= n / log(m)

迭代次数l线性取决于n因为log(m)是有限数。因此，时间复杂度保持为 O(n)。

推荐阅读