一，两种不同的求幂运算
求解x^n（x 的 n 次方）
①使用递归，代码如下：
1 private static long pow(int x, int n){ 2 if(n == 0) 3 return 1; 4 if(n == 1) 5 return x; 6 if(n % 2 == 0) 7 return pow(x * x, n / 2); 8 else 9 return pow(x * x, n / 2) * x; 10 }
分析：
每次递归，使得问题的规模减半。2到6行操作的复杂度为O(1)，第7行pow函数里面的x*x操作复杂度为O(1)
故时间复杂度公式：T(N)=T(N/2)+O(1) => T(N)=O(logN)
②普通方式求幂
1 private static long pow2(int x, int n){ 2 if(x == 0) 3 return 0;//0^n == 0 4 long p = 1; 5 for(int i = 0; i < n; i++) 6 p *= x; 7 return p; 8 }
显然，时间复杂度为O(N)
二，求解多项式乘法
公式：f(x,n) = a(0)x^0 + a(1)x^1 + a(2)x^2+...+a(n)x^n
比如：f(10,4)=a(0)10^0 + a(1)10^1 + a(2)10^2 + a(3)10^3+a(4)10^4
代码如下：
1 public static long poly(int[] arr, int x, int n){ 2 long sum = 0; 3 for(int i = 0; i <= n; i++){ 4 sum += arr[i] * pow(x, i); 5 } 6 return sum; 7 } 8 9 private static long pow(int x, int n){ 10 if(n == 0) 11 return 1; 12 if(n == 1) 13 return x; 14 if(n % 2 == 0) 15 return pow(x * x, n / 2); 16 else 17 return pow(x * x, n / 2) * x; 18 }
Horner法则求解多项式乘法，参考：
1 public static long poly2(int[] arr, int x, int n){//arr存储系数, x 表示基数, n 表示幂 2 long poly = 0; 3 for(int i = n; i >= 0; i--) 4 poly = poly * x + arr[i]; 5 return poly; 6 }
对比采用Horner法则计算多项式乘法与这篇文章： 字符串转换成数字
1 public int atoi(char[] s){ 2 int result = 0; 3 for(int i = 0; i < s.length; i++) 4 result = result * 10 + s[i] - '0';// 相当于 poly2(...)中的 x=10 5 return result; 6 }
可以看出，二者有很大的相似性。其实，不难看出，字符串转换成数字使用的正是Horner法则。
由此，得到启发，在进制转换中，如：八进制转十进制，相当于 x = 8。
故可写出一个常用的进制转换程序，如下：
//x 表示进制, 若x=8,表示将8进制转换成10进制 public static long convert(char[] arr, int x){ long result = 0; for(int i = 0; i < arr.length; i++) result = result * x + arr[i] - '0'; return result; } //str 表示原来进制的数,如：convert("456", 8) 456 --> 302 public static long convert2(String str, int x){ long result = 0; for(int i = 0; i < str.length(); i++) result = result * x + Integer.valueOf(str.charAt(i) - '0'); return result; }
十六进制转十进制，相当于 x = 16。
public static long convert2(String str, int x){//x = 16 long result = 0; char c; str = str.toUpperCase();//"abF8"-->"ABF8" for(int i = 0; i < str.length(); i++) { c = str.charAt(i); if(c >= 'A' && c <= 'F') result = result * x + (c - 'A') + 10; else result = result * x + c - '0'; } return result; }
因此，进制转换、字符串转换成数字、多项式求值都可以使用Horner法则来求解。
本文转自hapjin博客园博客，原文链接：http://www.cnblogs.com/hapjin/p/5372930.html，如需转载请自行联系原作者
