数据结构（三）算法

数据结构（三）算法

要点：解决问题方法的效率，跟算法的巧妙程度有关

思考：如何让算法更巧妙

01 如何空间的利用效率

参考：实现多项式的两种算法

public static double f1(int n,double[] a,double x) {
		double rs=a[0];
		for (int i = 1; i < a.length; i++) {
			rs+=a[i]*Math.pow(x, i);
		}
		return rs;
	}
	
public static double f2(int n,double[] a,double x) {
		double rs=a[n];
		for (int i = n; i >0; i--) {
			rs=a[i-1]+rs*x;
		}
		return rs;
	}
	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

02 案例：实现多项式的两种算法

1.循环相加

• 一般的解决方式，直观的写法

public static double f1(int n,double[] a,double x) {
		double rs=a[0];
		for (int i = 1; i < a.length; i++) {
			rs+=a[i]*Math.pow(x, i);
		}
		return rs;
	}
1
2
3
4
5
6
7

2.合并同类型相加

• 不使用冥函数，仅用加减法

public static double f2(int n,double[] a,double x) {
		double rs=a[n];
		for (int i = n; i >0; i--) {
			rs=a[i-1]+rs*x;
		}
		return rs;
	}
1
2
3
4
5
6
7

二者对比

• 但x为1.1，数组a为1到9时，执行10万次，第一个函数的执行时间是第二个函数的1000倍
• 但x为1.1，数组a为1到9时，执行100万次，第一个函数的执行时间是第二个函数的1万倍

03 我的总结

• 提高解决问题方法的效率，要提高算法的巧妙程度，减少计算量，用更多的加减法代替乘除法