|
1.时间复杂度： 什么是Big O：O(f(n))表示运行算法所需要执行的指令数，和f(n)成正比。n表示数据规模 例： 随着输入规模n的增大，时间复杂度的增长模式 2.数据规模概念： 该时间针对的是简单的求和运算，针对算法在该基础上大约除10即可 3.空间复杂度： 递归的深度是多少，空间复杂度就是多少 4.常见的复杂度分析 O(1) O(n）:一般存在一个for循环且与n有关
O(n^2):一般是双重循环且都与n有关，注意增量
O(logn): 二分查找法：
整形转成字符串：
其他： O(nlogn):虽然是双循环，但是外循环增量是logn级别
O(sqrt(n)):
5.递归算法的复杂度分析 不是有递归的函数就一定是O(nlogn) 如果递归函数中， 只进行一次递归调用，递归深度为depth，在每个递归函数中，时间复杂度为T，则总体时间复杂度为O(T*depth)
进行多次递归调用，建立一棵递归树 该函数的递归，在n=3时，有1次f(3)，有2次f(2)递归，4次f(1)递归，8次f(0)递归，调用次数就是递归树的节点数（即调用深度)
归并排序算法属于分而治之，其两次递归，排序时间复杂度是logn级别，每一层递归其节点总数n=8没有改变，所以其时间复杂度是nlogn
6.均摊复杂度分析（动态数组、动态栈、动态队列） 动态数组：每一次push耗费O(1),当达到容量n时，resize数组（扩充或缩减）容量耗费O(n)，这些n+1次操作耗费O(2n)的时间，均摊下来就是O(2)即O(1)级别。缩减时为了避免复杂度震荡（在数组元素个数为n时，重复着添加元素删除元素，反复扩充或缩减，使复杂度变为O(n)），因此需要当元素个数缩减至1/4时才resize，给添加元素留出余地
|
|
|
