C# 計算 1¹ + 2² + 3³ + … + nⁿ 級數和

問題描述

計算級數 S(n) = Σ(i=1 to n) iⁱ。直接雙重迴圈實作：外層遍歷 1~n，內層計算 iⁱ 並累加。

實作程式碼

public long Sum(int num)
{
    long sum = 0;
    for (int i = 1; i <= num; i++)
    {
        long pow = 1;
        // 計算 i 的 i 次方
        for (int j = 1; j <= i; j++)
        {
            pow *= i;
        }
        sum += pow;
    }
    return sum;
}

複雜度分析

• 時間：O(n²) 乘法運算。n=20 時 20²⁰ 已超 long 範圍（溢位）。
• 空間：O(1)。

優化建議

1. 快速冪：內層改用二進位指數法，將單次冪運算從 O(i) 降為 O(log i)。
2. 大整數：改用 System.Numerics.BigInteger 避免溢位，支援任意大 n。
3. 快取冪值：若多次查詢不同 n，可預計算或記憶化。

優化版範例

using System.Numerics;

public BigInteger SumOptimized(int n)
{
    BigInteger sum = 0;
    for (int i = 1; i <= n; i++)
    {
        sum += BigInteger.Pow(i, i); // 內建快速冪 + 大整數
    }
    return sum;
}