algorithm - 算術アルゴリズム

Question

私はいくつかのインタビューの質問を受けていて、この質問に出くわしました。p(x) = a0 + a1x + a2x^2 + ... + anx^n. O(N^2) の p(x) の値を計算するには、どのアルゴリズムを使用できますか? この問題にアプローチする方法について、私はまったく無知です。

Answer 1

O(N)直接評価またはホーナーの方法でそれを行うことができます。さまざまな操作の複雑さと関連する方法を示す便利なチャートは、次の場所にあります。

数学的演算の計算複雑性

ホーナーの方法は、「一部のアーキテクチャでネイティブの積和命令を使用して評価される形式 (A+ Bx) の部分式」を最適化する一連の手順です。より類似したバージョンは、エストリンのスキームです。

p(x)時間内に計算できるため、O(N)このメソッドNを何度も適用して達成しO(N^2)ます（それが本当に目的である場合...）。

Answer 2

各項は独立しており、N個の項がO(N)あるため、多項式項の計算を実行する必要があります。最悪のキャスト項は計算可能で(a_n)*(x^n)ありx^n、計算できるので、アルゴリズムの素朴な実装のためのO(N)正確な時間があります。O(N^2)

x^nただし、O（N）時間未満で計算するためのトリックがあります。これにより、さらに優れた処理を実行できます。pow（）の実装を参照してください。また、他の回答で説明されているHoenerの方法は、O(N)時間であり、したがって時間でもある高速な実装を提供しますO(N^2)。