数据结构与算法分析JAVA 2.14 考虑下列算法（Horner法则）

问题
解析
关于这个式子，如果 N 取 4，a这个数组是{4,8,0,1,2}，那么

一般来说，程序会写成一个累加，比如：

public static void fun(int[] a, int n, int x) {  long sum = 0; for(int i=0; i<n; i++) {  sum += a[i]*Math.pow(x, i); } System.out.println(sum); } 

此时，这个程序的运行时间是多少？
是O(N)吗？
答案不是，虽然我们只用了一个循环，但是每次循环中，Math.pow(x, i) 又会做 i 个步骤，所以肯定是比N大的

那么如何让运行时间变成 N 呢？

此题给出的方法如上图所述
这样做的缘由是将 F(X) 这个式子，拆成了由（aX+b）这样的简单式子累加
如：

变成

X [ X ( X ( X ( 4 ) + 8 ) ) + 1] + 2

这样就能使得运行时间为O（N）了
代码：

public static void Hornor(int[] a, int n,int x) {  long poly = 0; for(int i=0; i<n; i++) {  poly = (long)(x * poly + a[i]); } System.out.println(poly); } 

最后附上测试代码（包括随机生成一个数组）

package Chapter2; import java.util.Random; /** * * @author Crissu * */ public class Two_forteen {  public static void main(String[] args) {  // TODO Auto-generated method stub int N = 10000000; int[] a = new int[N]; CreateArray(a, N); Hornor(a, N, 2); } public static void CreateArray(int[] a, int n) {  Random rr = new Random(); for(int i=0; i< n; i++) {  a[i] = i+1; } for(int i=1; i<n; i++) {  int tmp = a[i]; int tt = rr.nextInt(i)+1; a[i] = a[tt]; a[tt] = tmp; } } public static void Hornor(int[] a, int n,int x) {  long poly = 0; for(int i=0; i<n; i++) {  poly = (long)(x * poly + a[i]); } System.out.println(poly); } }