第一章 时间复杂度和空间复杂度

一  集合框架

1.作用：对数据进行管理，方便高效地进行增删改查，其管理有多种数据结构来实现，在java中利用集合框架来实现不同的数据结构

2.在Java中学习集合框架的要求

（1）学会如何使用

（2）学会其内部实现原理

二  时间复杂度

1.作用：用于衡量某个数据结构执行效率的时间指标，用于消除直接计算时间时机器不同带来的差异，只以代码结构为唯一变量，衡量运行快满

2.判断方法：大O渐进法，通过比较次数来比较谁更好

（1）首先找到问题规模

注：问题规模如果有数组，则为数组长度，无数组，则为其对应的循环次数，或区间长度（包括递归所隐藏起来的循环）

（2）找到重复性的操作，以它为基准，大概写出次数与问题规模N的关系

注：由于for循环内部的条件都较为简单，一般不会将其作为基准，而套在循环内部的内容可能较为复杂，都是以循环内的内容作为基准

（3）进行化简（只保留N的最高项，以及化N前面的系数为1）

注：只需要大概表示次数与N的关系即可，看的是趋势，而不是具体的次数

3.特殊：

（1）重复性操作与问题规模无关时，时间复杂度为O（1），即为常量级时间复杂度

（2）二分查找：其关系满足2的查找次数方等于其数组的区间长度（相当于N），但由于我们求的是次数与问题规模N的关系，所以要对其取对数，得到O（logN）

（3）有些情况，时间复杂度是不确定的，但是我们一般考虑它最坏的情况，或是平均的情况，最好的情况没什么参考价值

注：在计算机中以2为底可以不用写出来，以其他数为底则需要显示标明

4.应用：通过比较时间复杂度的大小，就可以评判各个数据结构的执行效率，判断其适合增删改查的哪一个方面，以及不适合哪个方面

5.大小排序：越小越高效

O（1）<O(logN)<O(N)<O(NlogN)<O(N^2)<O(2^N)

三  空间复杂度

1.作用：评判代码占用资源

2.区别：

硬盘：持久化存储

内存：支持程序运行，但关机后就不存在了

3.判断：大O渐进法，与时间复杂度相类似 

注意：（1）其计算的时候不计入问题规模N本身的大小

（2）注意时间流逝了就没了，空间是重复利用的，所以我们认为其反复创建和销毁的变量为消耗一份

（3）是在方法快结束之前进行计算

所以内部有方法调用虽然会占用栈帧，但是在结束前调用结束释放栈帧了那就不在算入了