Processing math: 100%

级数求和 (n^2-1^2) + 2(n^2-2^2) +….n(n^2-n^2)

在本文中，我们将学习计算级数 (n^2 - 1^2) + 2(n^2 - 2^2) + …. n(n^2 - n^2) 的和的不同方法。在第一种方法中，我们将逐一计算范围 1 到 n 中每个 i 的级数和，并将其不断添加到最终和中。

在第二种方法中，我们将推导出一个数学公式来计算给定级数的和，这将使程序的时间复杂度从 O(n) 降低到 O(1)。

问题陈述 − 给定一个数字“n”，我们的任务是计算给定级数 (n^2 - 1^2) + 2(n^2 - 2^2) + …. n (n^2 - n^2) 的和。

示例

输入 − 数字 = 5

输出 − 当 n = 5 时，级数 (n^2 - 1^2) + 2(n^2 - 2^2) + …. n(n^2 - n^2) 的和为 150。

输入 − 数字 = 3

输出 − 当 n = 3 时，级数 (n^2 - 1^2) + 2(n^2 - 2^2) + ….n (n^2 - n^2) 的和为 18。

方法 1

这是级数求和问题最简单、也是最暴力的方法。

仔细分析该级数后，我们可以得出结论，对于任何数字 n，我们都有

Sum = ∑ i*(n^2 - i^2) 其中 i 从 1 到 n。

因此，对于暴力方法，我们可以使用上述公式在循环中从 i=1 到 n，以生成所需的求和。

示例

此方法的代码如下所示

Open Compiler
#include <bits/stdc++.h>
using namespace std;
int main () {
   int num = 3;
   long long sum=0;
   for (int i=1  ; i<num ; i++ ) {
      sum = sum+i*( num*num - i*i );
   }
   cout<< " The sum of the series (n^2 - 1^2) + 2(n^2 - 2^2) + …. n(n^2 - n^2) for n = " << num << " is " <<sum;
   return 0;
}

输出

The sum of the series (n^2 - 1^2) + 2(n^2 - 2^2) + …. n(n^2 - n^2) for n = 3 is 18

复杂度

时间复杂度 − O(n)，因为我们正在运行一个循环来迭代从 1 到 n 的数字。

空间复杂度 − 因为我们没有使用任何外部空间，所以此方法的空间复杂度为 O(1)。

方法 2

在这种方法中，我们将推导出一个公式来直接获得所需的级数和，因此不需要迭代，这种方法将以恒定的时间复杂度解决给定的问题。

如前所述，我们有由下式给出的级数的一般形式

Sum = ∑ i*(n^2 - i^2) for i = 1 to i = n.

同一个级数可以写成

Sum =  n^2∑ i - ∑ i^3

我们已经知道计算从 1 到 n 的所有数字之和以及从 1 到 n 的数字立方和的公式，如下所示

从 1 到 n 的所有数字之和

n* ( n+1 )/2

其中 n 是给定的数字。

现在，从 1 到 n 的所有数字立方和

(n*( n+1 )/2)^2

因此，给定级数可以写成 -

Sum = n^2 * ( n*( n+1 )/2 ) – ( n*( n+1 )/2 )^2

和可以进一步简化为 -

Sum = ( n * (n+1)/2 )*( n^2 - ( n * (n+1)/2 ))
Sum = n^2 * ( n+1 )/2 * ( n^2 – (n * ( n+1))/2)
Sum = n^2 * ( n+1 ) * ( n-1 )/4
Sum = n^2 * ( n^2 -1 )/4
Sum = (n^4)/4 – (n^2)/4

因此，我们只需要计算 Sum = (n^4)/4 – (n^2)/4 即可获得任何 n 的所需级数和。

示例

此方法的代码如下所示

Open Compiler
#include <bits/stdc++.h>
using namespace std;
int main () {
   int num = 5;
   long long sum = 0;
   sum = num*num*(num*num-1)/4;
   cout<< " The sum of the series (n^2-1^2) + 2(n^2-2^2) + …. n(n^2-n^2) for n = " << num << " is " <<sum;
   return 0;
}

输出

The sum of the series (n^2-1^2) + 2(n^2-2^2) + …. n(n^2-n^2) for n = 5 is 150

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

复杂度

时间复杂度 − O(1)，因为我们只是使用我们推导出的公式计算所需的和。

空间复杂度 − 因为我们没有使用任何外部空间，所以此方法的空间复杂度为 O(1)。

结论 − 在本文中，我们讨论了两种计算所需级数和的方法，在第二种方法中，我们将时间复杂度降低到常数。

更新于: 2023-08-16

66 次浏览

开启你的 职业生涯

完成课程获得认证

立即开始
广告