inarizuuuushi https://blog.hatena.ne.jp/inarizuuuushi/ Sabrou-mal サブロウ丸 https://inarizuuuushi.hatenablog.com/ アルゴリズム周辺 Hornerの公式という多項式の計算を高速に行う方法があります。 と言っても仕組みは簡単で以下のような式変形を行うだけです。 単純に項ごとを足し合わせるよりも、掛け算の回数が減っていることが分かりますね。 計算量はそれぞれ となっています。 実験 # P(x) y = 0 for i in range(n): y = y + a[i]*(x**i) # Horner_P(x) z = 0 for i in range(n): z = a[i] + z*y a_iは全て1(ノートPCで計測) n x 計測時間(P(x))(s) 計測時間(Horner_P(x))(s) 10000 3 0.196… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finarizuuuushi.hatenablog.com%2Fentry%2F2017%2F07%2F21%2F142257" title="Hornerの公式 - Sabrou-mal サブロウ丸" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/i/inarizuuuushi/20170721/20170721133458.png Hatena Blog https://hatena.blog 2017-07-21 14:22:57 rich https://inarizuuuushi.hatenablog.com/entry/2017/07/21/142257 1.0 100%