級數求和 (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，以生成所需的求和。

示例

此方法的程式碼如下所示

#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 的所需級數和。

示例

此方法的程式碼如下所示

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

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