算術算法

Question

我正在經歷一些面試問題，並偶然發現了這個問題。 p（x）= a0 + a1x + a2x^2 + ... + anx^n。你可以用什麼算法來計算O（N^2）中p（x）的值？我對如何解決這個問題完全無能爲力。

Answer 1

您可以在O(N)直接評估或Horner's method。用於各種操作的複雜性和所涉及的方法的有用的圖表可以在這裏找到：

Computational complexity of mathematical operations

Horner的方法是，優化形式（A + Bx的），其使用本機進行評價的「子表達式的串行過程在某些體系結構上乘加指令「。更平行的版本是Estrin's scheme。

由於您可以在O(N)時間內計算p(x)，因此您可以使用此方法N來實現O(N^2)（如果那真的是您之後的......）。

Answer 2

由於每個學期都是獨立的，有N個條件，必須執行O(N)計算多項式項。由於最差的演員任期爲(a_n)*(x^n)，而x^n可以在O(N)中計算出來，因此您確切地具有O(N^2)時間來實現算法的天真實施。

然而，有些技巧在小於O（N）的時間內計算x^n，因此您可以做得更好：請參閱an implementation of pow()。另外Hoener的方法如其他答案所描述的那樣提供了一個快速的實現，其時間是O(N)，因此也是O(N^2)時間。