前面讲了基础的数据结构,而算法作为程序的灵魂,对同样的事情拥有不同的操作,那么如何比较不同的算法之间,哪个的效率好,哪个的空间更省就需要用到算法分析相关的知识
算法分析
算法分析简单的就是分析一个算法运行需要多少时间以及需要多少内存,通常主要就是分析出算法的时间效率和空间效率
时间效率/时间复杂度
时间效率,也就是时间复杂度,例如在一个长度为n的数据中找到一个符合条件的值,最简单的就是直接遍历数组，通过这样的算法找到目标值的期望为(n + 1) / 2，这个值便是遍历查找的是时间效率
例如下图有个含有1-7的数组,现在需要从中找到6
现在开始查找,从左到右依次查找,经过6次后就招到了,这里执行的操作便是6次
但是查找的次数和数据量的大小、查找的目标数据的位置有关，当数据无穷大的时候，数据的位置随机的时候，如何对一个算法的效率进行估计呢？
这个算法的运气最好的时候的效率，当然是一下就找到了，也就是T(n)=1,当然也有最倒霉的时候，将数据遍历完了才找到需要的数据T(n)=n,在遍历中查找我们可以获取,
这里的运气最好的情况被称为最优时间复杂度，用Ω(n)来表示，意味着在数据量为n的情况下，算法运行时间至少是Ω(n)
这里的运气最差的情况被称为最差时间复杂度，用O(n)来表示，意味这在数据量为n的情况下，算法运行时间最多是O(n)
除此以外当然还有一个居中的平均时间复杂度，通Θ(n)来表示，这个表示的算法运行的期望时间
例如上面提到的遍历查找算法的效率就是Ω(n)=1, Θ(n)=(n + 1) / 2, O(n)=n,但在n特别大的时候，不同的量级之间的差距很小，较小的量级都可以忽略掉，例如(n+1)/2就可以简写未n/2,同时一般还会省去常量，所以Θ(n)=(n + 1) / 2可以写为Θ(n)≈n
对算法进行分析如何估算，也很简单，特别是通过代码来估算算法的复杂度，一般每多一层循环就需要多一个量级，比如一层循环就是n，两层循环就是n^2，以此类推，而其他的普通操作都是O(n)级别的，而递归则更容易导致对数级的复杂度log(n)、2^n
空间效率/空间复杂度
空间效率，也就是空间复杂度其实表示规则和时间效率相同，空间复杂度需要注意的是
- 空间复杂度通常不计入原始输入本身所占用的空间大小
- 空间复杂度主要记录这个算法自身需要的空间大小
- 在算法递归中，递归也是要消耗空间的，过多的递归也会占据不可忽视的空间
量级
这里给出大小从低到高的一些常见量级，这个表也能在《算法（第四版）》中的117页找到
|描述|数量级|说明|举例|
|—|—|—|—|—|
|常数级别|1|普通语句|两数相加|
|对数级别|logN|二分策略|二分查找|
|线性级别|N|循环|找出最大的元素|
|线性对数级别|NlogN|分治|归并排序|
|平方级别|N^2|双重循环|检查所有元素对|
|立方级别|N^3|三重循环|检查所有三元组|
|指数级别|2^N|穷举查找|检查所有子集|
END
2019-02-21 立项
2019-01-18 立项