用这个简单的公式增强你的编程能力

成为一名优秀的程序员并不需要数学天才，但你需要掌握一些技巧来提升算法的性能，并在技术面试中留下深刻印象。在本教程中，你将学习如何用一个简单易记的公式来计算2的连续幂的和。了解这个公式将有助于你理解递归运行时间，并快速计算大O时间和空间复杂度。

本文最初发表于jarednielsen.com

如何计算 2 的连续幂的和

怎样把这些数字加起来？

2^0 + 2^1 + 2^2 + 2^3 

您首先想到的是采取‘蛮力’方法吗？

2^0 = 1
2^1 = 2, + 1 = 3
2^2 = 4, + 3 = 7
2^3 = 8, + 7 = 15

这没有什么不对，而且你可能不需要用笔和纸或者计算器就可以实现这一点。

如果最终的幂不是 2^3，而是 2^30，或者 2^300，会怎么样？

暴力手段太残酷。

如果您遇到这种情况该怎么办？

2^0 + 2^1 + 2^2 + … + 2^n = ?

您将如何解决这个问题？

编程就是解决问题

什么是编程？

编程就是解决问题。

我们解决什么问题？

作为程序员，我们主要解决两类问题：

• 自动化
• 算法

我们可以编写一个 for 循环来自动执行 2 的幂的加法：

const sumPowers2 = power => {
 let sum = 0;

 for (let i = 0; i < power; i++) {
   sum += 2**i;
 }
 return sum;
}

它会扩大吗？

什么是 Big O？

在）。

为什么？

我们的函数需要对每个输入执行一次操作，因此我们的算法的阶数是O(n) 或线性时间复杂度。

一定有更好的方法！

除了自动化暴力破解方法，我们如何才能通过算法来解决这个问题？

数学钟🧮🕐

我即将让你大吃一惊。

看看这个：

1 = 1

😐

请忍耐一下。

🐻

如果1等于1，则

1 = 2 - 1

如果

1 + 2 = 3

那么

1 + 2 = 4 - 1

让我们再进一步。如果

1 + 2 + 4 = 7

然后

1 + 2 + 4 = 8 - 1

凉爽的？

😎

让我们加油吧！

x这个等式是什么？

2^x = 8

或者，用简单的英语来说，“多少个 2 相乘才能得到 8？”

我们也可以将其写成对数：

log2(8) = 3

我们可以说，“将 2 的幂乘以 8 得到多少次方？”

🧐

我们知道2^2 = 4。

和2^1 = 2

和2^0 = 1。

“等等，什么？”

为什么2^0 = 1？

餐桌时间到了！🏓

看到图案了吗？

什么是2^4？

16

的幂之和是多少2^4？

1 + 2 + 4 + 8 + 16 = 31

我们可以用什么其他方式来描述31？

31 = 32 - 1

什么是2^5？

32

你看到那里发生了什么吗？

两个幂的和比下一个幂的乘积小一。

🤯

我们再做一张桌子吧！🏓🏓

下一个指数是多少？

2^6

啥2^6？

64

那么的幂之和是多少2^6？

🤔

让我们将这个模式转换成一个方程来找出答案。

如果我们的指数未知，或者怎么办n？

2^n

的总和是多少2^n？

☝️ 2 的幂的和比下一个幂的乘积小一。

如果我们的力量是n，那么下一个力量是什么？

n + 1

如果n等于1，则

2^n = 2
2^(n + 1) = 4

如果n等于2，则

2^n = 4
2^(n + 1) = 8

看起来不错！

我们如何得到比下一个幂的乘积小一的数？

我们只需减去1：

2^(n + 1) - 1

🎉 这就是我们的等式！

编程就是解决问题

让我们再看看上面的函数。如何重构它来提高它的时间复杂度？

const sumPowers2 = power => {
 let sum = 0;

 for (let i = 0; i < power; i++) {
   sum += 2**i;
 }
 return sum;
}

我们只需将我们的方程式转换成 JavaScript！

const sumPowers2 = power => 2**(power + 1) - 1;

我们的新功能的顺序是什么？

O(1)。

无论输入的大小如何，我们的函数总是执行相同数量的操作。

如何计算 2 的连续幂的和

成为一名优秀的程序员并不需要数学天才，但你仍然需要掌握一些公式来帮助你解决问题。在本教程中，你学习了如何用一个简单易记的公式来计算2的连续幂的和。掌握这个公式将有助于你理解递归运行时间，并快速计算大O时间和空间复杂度。

想提升你的解决问题能力吗？我每周都会写一篇关于编程、解决问题和终身学习的新闻通讯。

注册解决方案