数据结构（六）什么是好的算法
要点：好的算法的最坏复杂度低
思考：如何降低复杂度
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)，空间复杂度过高会导致系统终止，这都是不被允许的
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/50094.html