用这个简单的方程改进你的算法

成为一名优秀的程序员并不需要数学天才，但你需要掌握一些技巧来提升算法的性能，并在技术面试中留下深刻印象。在本教程中，你将学习如何用一个简单易记的公式对一系列从 1 到 n 的连续整数求和。这个公式对于将函数复杂度从 O(n) 重构为 O(1) 以及计算带有偏移量的嵌套迭代的复杂度非常有用。

本文最初发表于jarednielsen.com

如何计算 1 到 n 的整数之和

怎样把这些数字加起来？

[1,2,3,4,5,6,7,8,9,10]

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

1 + 2 = 3
3 + 3 = 6
6 + 4 = 10
10 + 5 = 15
15 + 6 = 21
21 + 7 = 28
28 + 8 = 36 
36 + 9 = 45
45 + 10 = 55

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

如果数组包含 100、1,000 或 1,000,000 个元素会怎样？

暴力手段太残酷。

编程就是解决问题

什么是编程？

编程就是解决问题。

我们解决什么问题？

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

• 自动化
• 算法

我们可以轻松编写一个 for 循环来自动添加我们的系列：

const nums = [1,2,3,4,5,6,7,8,9,10];

const sumHarder = arr => {
   let sum = 0;
   for (let i = 0; i < arr.length; i++) {
       sum += arr[i];
   }
   return sum;
}

const result = sumHarder(nums);

这解决了需要手动求和数字的问题。

它会扩大吗？

什么是 Big O？

在）。

为什么？

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

一定有更好的方法！

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

再看看我们的数组。有没有其他方法可以求和？

[1,2,3,4,5,6,7,8,9,10]

当您添加系列时，您很可能从一端开始，然后向另一端努力。

或者你也可以从末尾开始倒着做，像这样：

10 + 9 = 19
19 + 8 = 27
27 + 7 = 34
34 + 6 = 40
40 + 5 = 45
45 + 4 = 49
49 + 3 = 52
53 + 2 = 54
54 + 1 = 55

如果我们将前进和后退的方法并列起来会怎样？

注意到什么了吗？

如果我们将表格中每一行的总和相加，我们会得到 11 的倍数。

有趣…🤔

如果我们从两端开始，然后向中间努力，会怎么样？

1 + 10 = 11
2 + 9 = 11
3 + 8 = 11
4 + 7 = 11
5 + 6 = 11

看到图案了吗？

我们有五对，每对之和为 11。这些对的乘积是，你猜对了，55。

🤯

如果不知道数组的长度，该如何进行计算？

我们仍然会进行配对，但我们将使用变量n作为数组长度的占位符。

1 + n    = (n+ 1)
2 + n -1 = (n + 1)

等等！什么？为什么n -1？

我们希望将数组中的第二个元素与倒数第二个元素配对。第二个元素是 2，倒数第二个元素是数组长度减 1，所以n-1。 2 + n -1 的和是多少？

n + 1

我想你已经知道事情会如何发展了。

3 + n - 2 = n + 1
4 + n - 3 = n + 1
5 + n -4  = n + 1

在某个点，我们会到达数组的中位数。这个值就是n / 2。这里，中位数是 5，也就是 10 除以 2 的商。

n / 2乘以什么n + 1？

n ( n + 1) / 2

之前我们手动绘制货币对时，是如何计算的呢？我们将最高值和最低值之和 11 乘以 5，也就是 10 除以 2。让我们代10入公式。

10 ( 10 + 1) / 2 = 55

按照操作顺序：

10 + 1 = 11
11 * 10 = 110
110 / 2 = 55

数学魔法！✨

但！

仔细观察就会发现，如果数组长度是偶数，这种方法就很好用。但如果不是呢？如果数组包含奇数个元素呢？

[1,2,3,4,5,6,7,8,9]

如果我们绘制出高/低值对，我们会发现我们有一个孤独的中位数：

1 + 9 = 10
2 + 8 = 10
3 + 7 = 10
4 + 6 = 10
5

请注意，所有值的总和都为偶数，这与我们的偶数长度数组不同，其中低/高对的总和为奇数。

那么 5 是多少？它是我们所有对数之和的一半。换句话说，我们的中位数是 的一半n + 1。

我们可以将其写成一个方程来确定中位数：

(n + 1) / 2

看起来很熟悉？是不是少了点什么？

如果我们知道中位数，下一步我们需要做什么？

我们只需将这个值乘以数组的长度。

n(n + 1) / 2

无论数组长度如何，这个等式对于帮助我们提高算法效率都非常有用。

让我们再看看上面的函数。我们如何重构它来改进它的 O 函数？

const nums = [1,2,3,4,5,6,7,8,9,10];

const sumHarder = arr => {
   let sum = 0;
   for (let i = 0; i < arr.length; i++) {
       sum += arr[i];
   }
   return sum;
}

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

const sumSmarter = arr => arr.length * (arr.length + 1)/2;

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

O(1)。

无论数组的长度如何，我们的函数总是执行相同数量的操作。

如何计算 1 到 n 的整数之和

成为一名优秀的程序员并不需要数学高手，但你仍然需要掌握一些公式来帮助你解决问题。在本教程中，你学习了如何用一个简单易记的公式对一系列连续整数进行求和。这就像一个技术面试的派对小技巧。

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