求和序列 (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)。

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 <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)。

方法二

在這種方法中，我們將推導出一個公式，直接得到所需的序列和，因此不需要迭代，這種方法將以常數時間複雜度解決給定的問題。

如前所述，我們得到了系列的一般版本，給定為

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 )/4
Sum = n^2 * ( n^2 -1 )/4
Sum = (n^4)/4 – (n^2)/4

因此，我們只需要計算Sum = (n^4)/4 - (n^2)/4，對於任何n，以獲得所需的序列的和。

Example

這種方法的程式碼如下：

#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

複雜性

時間複雜度 - O(1)，因為我們只是使用我們推導出的公式計算所需的總和。

空間複雜度 - 由於我們沒有使用任何外部空間，因此此方法的空間複雜度為O(1)。

結論 - 在本文中，我們討論了計算所需係列總和的兩種方法，並且在第二種方法中，我們將時間複雜度降低到常數。

以上是求和序列 (n^2-1^2) + 2(n^2-2^2) +….n(n^2-n^2)的詳細內容。更多資訊請關注PHP中文網其他相關文章！