数据结构（六）什么是好的算法

数据结构（六）什么是好的算法

要点：好的算法的最坏复杂度低

思考：如何降低复杂度

01 什么是复杂度

• 复杂度分为时间复杂度和空间复杂度
  • 时间复杂度是T(n),空间复杂度是S(n)
  • 时间复杂度可以简单视为函数实现目标过程中执行的乘除法次数
  • 空间复杂度可以简单视为函数实现目标过程中占用的系统内存

02 例子：递归和多项式

1.空间复杂度是S(n)

例子：递归

• 循环，设for循环占用的空间为N，则S(n)=N;

public static void printN1(int n) {
    for (int i = 1; i <= n; i++) {
        System.out.println(i);
    }
}

• 递归，设函数占用的空间为N，函数执行的次数为C次，则S(n)=CN;所以递归的空间复杂度随调用次数线性增加

public static void printN2(int n) {
		while (n>0) {
			printN2(n-1);
			System.out.println(n);
			return;
		}
}

• 当递归执行10万次时，报错且程序终止，是因为当一个函数在调用的时候，会把函数的参数记录在栈空间（简单理解为系统空间），栈的空间是有序的，函数调用次数过多导致栈空间爆满，程序就终止了。

Exception in thread "main" java.lang.StackOverflowError

2.时间复杂度是T(n)

例子：多项式

• 循环，设for循环了n次，每次循环执行i（i的值为0到n）乘法，则T(n)=(n²+n)/2;

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;
}

• 循环，设for循环了n次，每次循环执行1次乘法，则T(n)=n;

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;
}

03 我的总结

• 算法的优劣一般就看复杂度，平均复杂度和最坏复杂度，但平均复杂度不容易计算，一般都是计算最坏复杂度，且平均复杂度<=最坏复杂度
• 时间复杂度过高运行时间过久，数据量越大越要考虑好T(n)，空间复杂度过高会导致系统终止，这都是不被允许的