在 O(lgn) 中计算 2^n 的算法

Question

我需要一个计算 2^n 的算法，即 O(lgn) 。我做了这样的事情：

    algorithm func (n){
      if ( n == 0 ) return 1;
      else if ( n % 2 == 0) return 2 * func (n/2);
      else return 2 * func (n-1);
     }

这是正确的吗？如果正确的话，当有一些if时，如何得到递推关系？是 T(n) = 2T(n-2) + 2T(n-1) + O(1) ？

Answer 1

您可以移动位。例如。 1 << n == 2^n.

> 1<<6
=> 64
> 2**6
=> 64

Answer 2

正确吗？

不，不是。下面是 JS 代码，它针对 0 到 10 之间的参数运行算法：

 function func(n) {
      if (n == 0) return 1;
      else if (n % 2 == 0) return 2 * func(n/2);
      else return 2 * func(n-1);
 }
 
 for (let i = 0; i < 11; i++) {
     console.log(`2^${i}  = ${func(i)}`);
 }

问题出在表达方式

2 * func (n/2)

。这应该是

func(n/2)**2

，即递归获得结果的平方：

 function func(n) {
      if (n == 0) return 1;
      else if (n % 2 == 0) return func(n/2) ** 2;
      else return 2 * func(n-1);
 }
 
 for (let i = 0; i < 11; i++) {
     console.log(`2^${i}  = ${func(i)}`);
 }

有if的情况下如何得到递推关系？

你可以采取最坏的情况。

是 T(n) = 2T(n-2) + 2T(n-1) + O(1) ？

不。在这里，您似乎将计算的值与计算的努力混合在一起。您将

2 * func(n-1)

“翻译”为 2T(n-1)，但后者表示您做了 T(n-1) 的两次工作，但事实并非如此，因为您只调用

func(n-1)

一次，然后将其加倍。该加倍操作不需要再次重做相同的工作，只算作一个工作单元。

如果我们假设算术运算需要恒定时间（这是进行分析的一种方法，但请参阅计算复杂性和计算模型），那么我们就有成本：

• 𝑇₀ = 1
当 𝑛 为偶数时，
• 𝑇_𝑛 = 1 + 𝑇_𝑛/2 当 𝑛 为奇数时，
𝑇
• 𝑛 _{= 1 + 𝑇}𝑛−1
但是后一个等价可以扩展到使用

even

情况： 当 𝑛 为奇数时（使用整数除法）

𝑇

𝑛
• = 2 + 𝑇_𝑛/2 ...常数项可以设置为1:

当 𝑛 为奇数时（使用整数除法）

𝑇

𝑛

= 1 + 𝑇
• 𝑛/2 _{所以现在我们实际上对奇数和偶数 𝑛 都有相同的定义。如果我们将此表达式替换 log}2
𝑛 次，我们得到：

_𝑇𝑛

= 1 + 1 + ... + 1（log

2
• 𝑛 项）= log₂𝑛 _{所以复杂度是 O(log𝑛)}