算法的复杂度分析
1.什么是大O
- 定义
- n表示数据规模
- O(f(n))表示运行算法所需要执行的指令数，和f(n)成正比。
a,b,c,d都是常数，与算法复杂度的关系不大，故可以舍去。
- 在业界，我们就是用O来表示算法执行的最低上界。
- 算法复杂度取最大值,注意此时n的规模是一样的
- O(nlongn+n)=O(nlongn)
- O(nlongn+n^2)=O(n^2)
- O(AlongA+B),此时不能取最大值，因为A，B的数据规模不确定。
- 实例：
设字符串最长的长度为s个，字符串的个数为n个，则：
n个字符串按照字母序排序：O(n*s*logs)
整个字符串数组按照字典序排序：O(s*n*logn)[nlogn只是比较的次数，对于整数而言，为常数1，但是对于长度为s的字符串，其要加上系数s]
整个的时间复杂度：O(n*s*（logs+logn))
2.数据规模要的概念
- 对数据规模为10^5进行选择排序，计算机会假死
- 要想在1s之内解决问题
- O(n^2)的算法可以处理大约10^4级别的数据
- O(n)的算法可以处理大约10^8级别的数据
- O(nlogn)的算法可以处理大约10^7级别的数据
-
空间复杂度
- 多开一个辅助的数组：O(n)
- 多开一个辅助的二维数组：O(n^2)
- 常数变量：O(1)
- 递归调用是有空间代价的，递归的深度是多少，空间复杂度就是多少
3.常见的复杂度分析
- O(1)
- O(n)
- O(n^2)
- O(logn) [注意分析为什么是logn，分析的十分透彻]
- 注意有两个for循环不一定是O(n^2),如下是O(nlogn)
4.复杂度实验
如何检验自己写出的算法的复杂度？
实验，观察趋势
每次将数据规模提高两倍，看时间的变化
| 复杂度 | 提高两倍时间的变化 |
|---|---|
| O(N) | 2 |
| O(N^2) | 4 |
| O(logN) | log2N/logN=1+log2/logN |
| O(NlogN) | 比2多一点 |
5.递归算法的时间复杂度分析
- 递归中进行一次递归调用的复杂度分析
在这种情况下，只计算递归调用的深度就可以。如下即为O(logn)
如果递归函数中，只进行一次递归调用，递归深度为depth；在每个递归函数中，时间复杂度为T，则总体的时间复杂度为O(T*depth)
如下，是一个求n次幂的解法，此解法比连乘O(N)的快了不少。
- 递归中进行多次递归调用
应该计算递归的次数，使用递归树。
那为什么归并排序的时间复杂度为O(NlogN)呢？第一：其深度为logN，第二：每个节点处理的数据规模会越来越小；所以总共logn层，每层处理的为n
6.均摊复杂度的分析
比如动态数组。可以看一下源码，其中的resize方法是说在capacity<size时会扩容，同时会将之前的数组的值复制到新数组中，时间复杂度为O(N),但是整体来看，之前的前N次操作的时间复杂度为O(1),总计为N，第N+1次的时间复杂度为N，总体来说是O(2),所以总体的时间复杂度还是O(1).
7.复杂度震荡
8.参考
玩转算法面试 ，这门课非常好，值得大家购买！