常用数据结构操作与算法复杂度总结
目录
博客：blog.shinelee.me | 博客园 | CSDN
时间复杂度
如何评估一个算法的计算时间？
一个算法的实际运行时间很难评估，当时的输入、CPU主频、内存、数据传输速度、是否有其他程序在抢占资源等等，这些因素都会影响算法的实际运行时间。为了公平地对比不同算法的效率，需要脱离开这些物理条件，抽象出一个数学描述。在所有这些因素中，问题的规模往往是决定算法时间的最主要因素。因此，定义算法的时间复杂度(T(n))，用来描述算法的执行时间随着输入规模的增长将如何变化，增长速度是怎样的。
在输入规模较小时，运行时间本来就少，不同算法的差异不大。所以，时间复杂度通常关注的是输入规模(n)较大时运行时间的变化趋势，称之为渐进复杂度，采用大O记号，表示渐进上界，对于任意的(n >> 2)，若有常数(c)和函数(f(n))满足T(n)≤c⋅f(n) 则记作 T(n)=O(f(n))
可以简单地认为，O(f(n))表示运行时间与f(n)成正比，比如O(n^2)表示运行时间与输入规模的平方成正比，这样讲虽然并不严谨，但一般情况下无伤大雅。
在n很大时，常数c变得无关紧要，不同算法间的比较主要关注f(n)部分的大小。比如，在(n >> 100)时，(n^2)要比(100n)大得多，因此重点关注(n^2)和(n)增长速度的差异即可。
不同时间复杂度的增长速度对比如下，图片来自Big-O Cheat Sheet Poster，
除了大(O)记号，还有大Ω记号和Θ记号，分别表示下界和确界，
Ω(f(n)):c⋅f(n)≤T(n)Θ(f(n)):c1⋅f(n)≤T(n)≤c2⋅f(n)
他们的关系如下图所示，图片截自邓俊辉-数据结构C++描述第三版
常用数据结构操作与算法的复杂度
下面汇总摘录了常用数据结构操作和排序算法的复杂度，来源见引用。其中包含最坏时间复杂度、平均时间复杂度以及空间复杂度等，对于排序算法还含有最好时间复杂度。
输入规模较小时的情况
渐进复杂度分析的是输入规模较大时的情况，输入规模较小时呢？
在输入规模较小时，就不能轻易地忽略掉常数(c)的作用，如下图所示，图片来自Growth Rates Review。复杂度增长快的在输入规模较小时可能会小于复杂度增长慢的。
所以在选择算法时，不能无脑上看起来更快的高级数据结构和算法，还得具体问题具体分析，因为高级数据结构和算法在实现时往往附带额外的计算开销，如果其带来的增益无法抵消掉隐含的代价，可能就会得不偿失。
这同时也给了我们在代码优化方向上的启示，
- 一是从(f(n))上进行优化，比如使用更高级的算法和数据结构；
- 还有是对常数(c)进行优化，比如移除循环体中不必要的索引计算、重复计算等。
以上