小网站大全,欧美教育网站模板,济南做网站企业,宣传片制作模板目录
什么是数据结构#xff1f;
什么是算法#xff1f;
1、算法的特性
1.1 五个特征
1.2 设计原则
1.3 评价算法的两个总要指标#xff1a;时间复杂度和空间复杂度
2、时间复杂度分析
2.1 时间复杂度表示方法#xff1a;大O表示法
2.2 时间复杂度如何分析
2.3 复…目录
什么是数据结构
什么是算法
1、算法的特性
1.1 五个特征
1.2 设计原则
1.3 评价算法的两个总要指标时间复杂度和空间复杂度
2、时间复杂度分析
2.1 时间复杂度表示方法大O表示法
2.2 时间复杂度如何分析
2.3 复杂度比较
2.4 时间复杂度分析
3、空间复杂度分析 什么是数据结构
就是一组能组在一起的集合对象。比如数组、链表、队列等。
什么是算法
就是解决问题的
1、算法的特性
1.1 五个特征
有穷性、确定性、可行性、有输入、有输出
while(true){}//死循环不是算法
1.2 设计原则
正确性、可读性、健壮性bug写出的代码很少有bug且系统比较稳定
高效率与低存储内存CPU内存占用最小CPU占用最小运算速度最快
1.3 评价算法的两个总要指标时间复杂度和空间复杂度
时间复杂度运行一个程序所花费的时间O()表示
空间复杂度运行程序所需要的内存尽可能避免出现OOM内存溢出 2、时间复杂度分析
2.1 时间复杂度表示方法大O表示法
O(1),O(n),O(logn),O(nlogn),O(n^2),O(2^n)
2.2 时间复杂度如何分析
1找for、while、递归而且要找循环量大的那一段
2有网络请求的地方httprpc远程调用数据库请求
就是测试时间打印log计算平均时间
2.3 复杂度比较
O(1) O(logn) O(n) O(nlogn) O(n^2) O(n^3)
2.4 时间复杂度分析
计算时间复杂度 往往是计算比较大的 而且是不确定的数如果已经确定了那么就不用计算了也是我们说的常量。
常数级O(1) public static void main(String[] args) {int a 1; //1次 O(1)for(int i 0 ;i 3;i){//这里会运行几次4次 在第4次的时候结束 跳出 i3 (0 1 2 3)a a 1; //这里运行几次 3次 O(1)? n1 n 1 O(3)? O(1)}} 对数级O(logn)
public static void main(String[] args) {int n Integer.MAX_VALUE; //表示n是未知int i 1;while( i n){i i * 2; //O(logn)}//i的值2 4 8 16 32,》2^0,2^1,2^2,2^3,.....2^n// 2^xn 求出x就是我们运行的次数 xlog2n 计算机忽略掉常数 x logn O(logn)//二分查找 为什么是logn的算法//1~100 找69这个数//50:(1100)/2 50
}
线性对数级O(nlogn)
public static void main(String[] args) {int n Integer.MAX_VALUE; //表示n是未知int i 1;for(int j 0 ; j n ;j){//O(n)while ( i n){i i * 2;//O(logn)}}
}
线性级O(n)
public static void main(String[] args) {int n Integer.MAX_VALUE; //表示n是未知int a 1; //1次 O(1)for(i 0 ; i n;i){a a 1; //运行了多少次O(n) n一定是一个未知的如果n是已知6的则是O(1)}
}
平方级别O(n^2
public static void main(String[] args) {int n Integer.MAX_VALUE; //表示n是未知int a 1; //1次 O(1)for(i 0 ; i n;i){ // 乘法 n次for(int j 0 ; j n ;j ){ //n次a a 1; //运行了多少次O(n^2)n*(n1)/2 O(n^2); (n^2n)/2 //注意有个规律有加减法的时候找次数最高的那个}}
}
指数级O(2^n)
long aFunc(int n) { //运行多少次if (n 1) { return 1;} else { return aFunc(n - 1) aFunc(n - 2);}
}
//运行次数T(0)T(1)1,同时T(n)T(n-1)T(n-2)11是其中的加法算一次执行
//显然T(n)T(n-1)T(n-2)是斐波那契数列通过归纳证明法可以证明,
//当n1 时T(n)(5/3)^n,同时n4时T(n)(3/2)^n,
//所以该方法的时间复杂度可以表示为O(5/3)^n简化后为O(2^n)
3、空间复杂度分析
如何查找空间复杂度
1找花了内存的地方。数据
2找开了空间的地方比如数组、链表、缓存对象map、递归
总结
学了时间复杂度那我们的目的就是要把代码写到最优效率最高
效率有高到低O(1) O(logn) O(n) O(nlogn) O(n^2) O(n^3)
比如排序冒泡算法的时间复杂度是O(n^2)找更优秀的排序算法快速排序、归并排序、堆排序
优化的目标就是要往O(1)靠近
本文来源于小编的另一分享平台算法基础 - 知乎 (zhihu.com)
