算法

算法定义

算法是一系列解决问题的清晰指令

算法代表着用系统的方法描述解决问题的策略机制

也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出

如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题

不同的算法可能用不同的时间、空间或效率来完成同样的任务

算法的优劣可以用空间复杂度与时间复杂度来衡量

分类

算法复杂度

定义

算法复杂度，即算法在编写写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源

复杂度表示

我们记一个算法的复杂度为O(n)，表示数据规模为n的情况下，算法使用的时间和空间资源

也可以用O(n)描述，代码执行花费的时间和空间随着n增大变化的趋势

算法复杂度从时间上考虑是时间复杂度(快不快)，从空间上考虑是空间复杂度(占的内存多不多)

时间复杂度的四种类型

最好时间复杂度

指的是在理想情况(最好情况)下，执行这段代码的时间复杂度
最坏时间复杂度

指的是在最坏情况下，执行这段代码的时间复杂度
平均时间复杂度

指的是概率论中的加权平均值，也叫作期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度
$A(n) = \sum _{I \in S}{P_It_I}$
其中$A(n)$表示平均时间复杂度，$S$是规模为$n$的实例集，实例$ I \in S$的概率为$P_I$，算法对实例$I$执行的基本运算次数是$t_I$
均摊时间复杂度

均摊时间复杂度(amortized time complexity)，它对应的分析方法为摊还分析或者平摊分析

听起来与平均时间复杂度有点类似，比较容易弄混，平均复杂度只在某些特殊情况下才会用到

而均摊时间复杂度应用的场景比它更加特殊、更加有限

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上