在本文中，我们将研究计算序列和的不同方法- (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)。
Example
输入 − 数字 = 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。
方法一
这是最简单的暴力方法来解决序列求和问题。
经过仔细分析这个数列，我们可以得出结论：对于任意一个数n，我们有
Sum = ∑ i*(n^2 – i^2) for i = 1 to i = n.
因此，对于暴力破解方法，我们可以在循环中使用上述公式，i从1到n，以生成所需的求和。
Example
这种方法的代码如下：
#include 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)。
方法二
在这种方法中，我们将推导出一个公式，直接得到所需的序列和，因此不需要迭代，这种方法将以常数时间复杂度解决给定的问题。
如前所述，我们得到了系列的一般版本，给定为
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可以进一步简化为-
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 )/4Sum = n^2 * ( n^2 -1 )/4Sum = (n^4)/4 – (n^2)/4
因此，我们只需要计算Sum = (n^4)/4 – (n^2)/4，对于任何n，以得到所需的序列的和。
Example
这种方法的代码如下：
#include 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
复杂性
时间复杂度 – O(1)，因为我们只是使用我们推导出的公式计算所需的总和。
空间复杂度 – 由于我们没有使用任何外部空间，因此该方法的空间复杂度为O(1)。
结论 – 在本文中，我们讨论了计算所需系列总和的两种方法，并且在第二种方法中，我们将时间复杂度降低到常数。
以上就是求和序列 (n^2-1^2) + 2(n^2-2^2) +….n(n^2-n^2)的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1443545.html
微信扫一扫 
支付宝扫一扫 
