ホーナー法とは

・In English
＜前提知識＞
・オーダー記法

■ホーナー法とは

ホーナー法(Horner's rule)とは、多項式の乗算回数を減らす為の計算手法で、用途としてはプログラムの実行時間を減らす為に用いられます。 具体的に以下多項式を例に考えた場合、通常は乗算回数は10回となります。

ホーナー法は以下の様に式変形する事をいい、乗算回数を4回に減らす事ができます。



＜ホーナー法の使用上の注意＞
一般的に、プログラムはその実行時間が短い程良いとされてますが、アルゴリズムのもともとの意図をくみ取れない様な作り方は好ましくありません。 そういう意味でホーナー法は、もとの式の形が若干崩れてしまうので、プログラムのソースにコメントを残しておいた方が良と思います。

＜計算量を一般化して見積もる＞
(1)式の乗算回数は多項式の次数をnとした場合、以下等差数列の和で表すことができ、nの二乗に比例します。一方(2)式の乗算回数は多項式の次数と等しくなり、 ホーナー法で大幅に乗算回数を減らす事ができます。なお計算量を表すのには以下の様にオーダー記法を用います。

サブチャンネルあります。⇒ 何かのお役に立てればと

関連記事一覧 トップメニュー ソフトウェア アルゴリズムの計算量 ホーナー法 二分探索法 プログラムとスクリプト モデルベース開発 ValidationとVerification アジャイルとウォーターフォール ブートローダ DX ブロックチェーン 情報エントロピー 暗号化技術 ・エンコード,デコード ・ハッシュ関数 ・暗号化の仕組み 自然言語処理 ・青空文庫の本文抽出 ・形態素解析 ・単語にIDを付与し辞書作成 ・Bag Of Words(BOW) ・Word2Vec 画像処理 ・画像フィルタ ・アフィン変換 スクレイピング ・スクレイピングとは ・webの画像ダウンロード ・malformed AAC bitstream