多項式計算效率對比：庫函數 pow() vs 秦九韶算法（Horner 規則）C++ 實測

多項式計算效率對比：庫函數 pow() vs 秦九韶算法（Horner 規則）C++ 實測

計算多項式 f(x) = 1 + Σ(xi/i) (i=1..m) 時，直接調用 pow() 與使用秦九韶算法（Horner 規則）的性能差距驚人。本文通過 C++ 實測數據，直觀展示算法優化的威力。

一、兩種算法實現

1. 直接調用 pow()

double Fn1(double x) {
  double f = 1.0;
  for (int i = 1; i <= m; i++) {
    f += pow(x, i) / i; // 每次調用 pow，重複計算 x^i
  }
  return f;
}

2. 秦九韶算法（遞推結構）

double Fn2(double x) {
  double f = 0.0;
  for (int i = m; i >= 1; i--) {
    f = f * x + 1.0 / i; // 利用上一次結果，僅一次乘法
  }
  return f * x + 1.0;
}

原理：f(x) = 1 + x/1 + x²/2 + ... + xm/m 重寫為遞推形式，消除冪次運算。

二、測試環境與代碼

• 編譯器：GCC / MSVC Release 模式
• 輸入：x = 0.9，m 從 100 到 10⁹
• 計時：clock() 精度約毫秒

#include 
#include 
#include 
#define m 1000000000 // 修改此處測試不同規模
using namespace std;
double Fn1(double x); double Fn2(double x);
int main() {
  double x = 0.9;
  clock_t start, stop;
  start = clock(); cout << Fn1(x) << endl; stop = clock();
  cout << "Fn1 time: " << double(stop-start)/CLOCKS_PER_SEC << "s" << endl;
  start = clock(); cout << Fn2(x) << endl; stop = clock();
  cout << "Fn2 time: " << double(stop-start)/CLOCKS_PER_SEC << "s" << endl;
  return 0;
}

三、實測數據對比表

四、複雜度分析

秦九韶算法將指數運算降維為線性遞推，隨 m 增長優勢指數級擴大。

五、工程啟示

1. 算法選型決定性能上限：同樣硬件，O(m) vs O(m log m) 差距 40 倍。
2. 數學重構威力：多項式、級數求和、動態規劃轉移常可通過遞推消除冗餘計算。
3. 庫函數非銀彈：pow() 通用但昂貴，熱路徑務必檢查是否可替換為增量計算。
4. 數值穩定性：秦九韶算法從高次向低次遞推，對浮點數累積誤差控制優於正向求和。

這個發現於宋代（秦九韶《數書九章》1247年）的算法，至今仍是計算機科學教科書級的優化典範。

1. 上一篇文章： PHP 學習路線圖與實戰總結：從基礎語法到電商系統的完整進階指南
2. 下一篇文章： PHP 內建函式速查手冊：Session、類/物件、MySQL、數學、日期時間、陣列、字串、檔案系統

PHP 相關知識

PHP 導出 Excel (Simple Excel / XML Spreadsheet) 完整實作：UTF-8、中文檔名、大數據優化

方案選擇：Simple Excel (XML Spreads

WAMP 環境陷阱：Web 與 CLI 使用不同 php.ini 導致擴展生效不一致

WAMP 環境陷阱：Web 與 CLI 使用不同 php.i

PHP Cookie 鍵名不能使用點號：自動轉換為下劃線的機制與影響

PHP Cookie 鍵名不能使用點號：自動轉換為下劃線的機

PHP 生成隨機字符串實戰：支援中英混合、可配置長度與字符集

核心需求 生成含中英文、數字、符號的隨機字符串，用於驗證碼、