演算法優化實戰：從 O(n) 迴圈累加到 O(1) 高斯公式的效能飛躍

問題描述

計算 1 + 2 + 3 + ... + n。兩種實作：

方法一：迴圈累加 O(n)

private static long cycle(long n) {
    long sum = 0;
    for (long i = 1; i <= n; i++) sum += i;
    return sum;
}

方法二：高斯公式 O(1)

private static long gauss(long n) {
    return (n + 1) * n / 2;
}

效能測試程式碼

public static void main(String[] args) {
    long n = 10_000_000;
    System.gc();
    long start = System.currentTimeMillis();
    long sum = cycle(n);
    System.out.println("迴圈耗時: " + (System.currentTimeMillis() - start) + "ms, 結果: " + sum);

    System.gc();
    start = System.currentTimeMillis();
    sum = gauss(n);
    System.out.println("高斯耗時: " + (System.currentTimeMillis() - start) + "ms, 結果: " + sum);
}

實測結果（參考）

迴圈耗時: 24ms, 結果: 50000005000000
高斯耗時: 0ms,  結果: 50000005000000

隨 n 增長，迴圈時間線性增長，高斯公式恆為常數時間。展現演算法複雜度優化的威力：正確選擇數學公式或資料結構，能帶來數量級效能提升。