java数据结构知识点自我总结
课前复习:
二分查找 时间复杂度(O(N)) 空间复杂度:范围最大的长度 复杂度:粗略衡量算法好坏的刻度尺(工具) 两个维度:快慢 时间复杂度(重点) 使用空间的情况 空间复杂度 时间复杂度:直接利用允许时间衡量不现实,测试环境多变,不好控制变量 前提:如果指定cpu的情况下,单位时间内运行的基本指令个数是固定的 如果一个算法需要的指令比另一个算法需要的指令个数小,就可以推出算法A运行的时间更快 前提:算法计算的快慢和输入的数据的规模是有关系的 粗略计算算法的快慢: n:数据的规模 f(n): n的数据规模情况下,需要的大概基本指令个数 引入大O渐进表示法: 1.只保留最高次项 2.保留的最高次项系数化为1 f(n)=2n+10 表示为O(n) 算法的快慢还和最好的情况,平均的情况,最好的情况 一般优先关注最坏的情况,其次平均情况,最好情况关注比较少 时间复杂度是o(log(n)) 空间复杂度: 考虑 数组容量(array.length)和已有数据个数(size)的关系1.容量是够用的size<array.length2.容量不够用搬家(1.5、2倍)int newCapacity=array.length*2;1.找新家;int[] newArray=new int[newCapacity]2.搬家for(int i=0;i<size;i++){newArray[i]=array[i];}3.发朋友圈this.array=newArray;4.老房子退掉原来的数组对象,没有引用指向,变成垃圾扩容的空间越小,空间的浪费越小扩容的空间越大,需要扩容的频率越小经验值1.5或者2倍 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |