ผลรวมอนุกรม 1 + (1+3) + (1+3+5) + ... + (1+3+...+(2n-1)) ใน C++

บทนำ

หาผลรวมของอนุกรม: S = Σᵢ₌₁ⁿ (Σⱼ₌₁ⁱ (2j-1)) โดยที่ Σⱼ₌₁ⁱ (2j-1) = i² (ผลรวมเลขคี่ i ตัวแรก)

วิธีที่ 1: Nested Loops (O(n²))

int calcSum(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        int value = 1;
        for (int j = 1; j <= i; j++) {
            sum += value;
            value += 2;
        }
    }
    return sum;
}

วิธีที่ 2: สูตรคณิตศาสตร์ (O(1))

S = Σᵢ₌₁ⁿ i² = n(n+1)(2n+1)/6

int calcSum(int n) {
    return (n * (n + 1) * (2 * n + 1)) / 6;
}

ตัวอย่าง

n = 35 → ผลลัพธ์ = 14910 (ทั้งสองวิธีให้ผลลัพธ์เท่ากัน)

คำอธิบาย

อนุกรมในวงเล็บแต่ละอันคือผลรวมเลขคี่ i ตัวแรก = i² ดังนั้นอนุกรมทั้งหมด = Σ i² = n(n+1)(2n+1)/6

สรุป

ควรใช้สูตรคณิตศาสตร์ O(1) แทน Nested Loops O(n²) โดยเฉพาะ n ใหญ่ นี่คือตัวอย่างดีของการลดความซับซ้อนด้วยคณิตศาสตร์