一个简单的例子提高你的算法能力

你不需要成为一个数学天才才能成为一个优秀的程序员，但是有一些技巧你可以添加到你的问题解决包中，以提高你的算法的性能，并在技术面试中给人留下深刻的印象。 在本教程中，您将学习如何用一个简单且容易记住的等式来求和一系列从 1 到 n 的连续整数。这个等式对于将一个函数从 O(n)重构为 O(1)的复杂度很有用.

我相信 90% 的人都会等差数列，但 50% 的人在看到求1到n的和是会第一时间想到循环遍历, 更少人会考虑算法复杂度.

1 如何计算 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 个元素，该怎么办?

2 代码实现

我们可以很容易地编写一个 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);

再稍微优雅一点, 你可能会使用 reduce

const nums = [1,2,3,4,5,6,7,8,9,10];
const x = nums.reduce((a,b) => a+b);

这就解决了求和的问题。

• 那上面的算法复杂度是多少?
• O(n).

为什么?

我们的函数需要对每个输入执行一个操作，所以我们的算法的阶数是 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)
……

将数组中的第二个元素与倒数第二个元素配对。第二个元素是 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

好了, 我们把上面的规律找到了, 接下来我们将 10 代入上面的方程.

10 ( 10 + 1) / 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

不管数组长度是多少，都可以使用这个数组来解决求和问题. 这个等式在帮助我们提高算法效率方面是非常有用的。

我们再来看看上面的函数。我们如何重构它来改进它的算法复杂度?

我们只需将等式转换成 JavaScript!

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

上面函数的算法复杂度降低成 O(1) 了. 不管数组的长度如何，我们的函数总是执行相同数量的操作。

3 如何计算 1 到 n 的总和

在本教程中，您学习了如何用一个简单且容易记住的等式来对一系列连续整数求和。

我们在面试的时候, 面试官偶尔会问, 请写出从 1 到 100 的累计求和. 通过上面的讲解, 相信你至少知道如何去降低算法复杂度.

在日常的编码中, 我们可以通过一些找规律, 套公式降低算法复杂度~ 用起来吧

翻译原文地址: [https://dev.to/nielsenjared/improve-your-algorithms-with-this-simple-equation-3g1c]

最后

• 欢迎关注「前端加加」, 定期分享优质文章
• 回复加群，邀你进技术群，长期技术交流学习