转载本文请联系程序新视野公众号。前言算法是指用于操作数据和解决程序问题的一组方法。算法是大厂和外企面试必考的项目，也是每一位资深程序员必备的技能。针对同一个问题，可以有很多种算法来求解，但是不同的算法在效率和存储空间上可能会有很大的差异。那么，用什么指标来衡量算法的优劣呢？其中，上面提到的效率可以用算法的时间复杂度来描述，占用的存储空间可以用算法的空间复杂度来描述。时间复杂度：用来评价程序执行所消耗的时间，可以估计程序对处理器的使用程度。空间复杂度：用来评价执行程序占用的内存空间，可以估计程序对计算机内存的使用程度。在实践或者面试中，我们不仅要能够写出具体的算法，还要了解算法的时间复杂度和空间复杂度，这样才能评价算法的优劣。当时间复杂度和空间复杂度不能同时满足时，也需要选择一个平衡点。一个算法通常有三种情况：最佳、平均和最差。我们通常关注最坏的情况。最坏情况是算法运行时间的上限，对于某些算法，最坏情况发生的频率更高，这意味着平均情况与最坏情况一样糟糕。通常，时间复杂度比空间复杂度更容易出现问题。更多的研究是在时间复杂度上进行的。面试中如果没有特别说明，时间复杂度也有讲到。时间复杂度获取算法的时间复杂度，最直观的思路是将算法程序运行一次，自然可以得到。但在实践中，往往受到测试环境、数据规模等因素的限制。直接测试算法要么难以实现，要么误差大。理论上，没必要每个算法都测试一次。只需要找到一个评估指标。获取算法执行所耗时间的基本趋势即可。时间频率一般情况下，一个算法所花费的时间与代码语句被执行的次数成正比。算法执行的语句越多，消耗的时间就越多。我们称一个算法中语句执行的次数为时间频率，记为T(n)。渐近时间复杂度在时间频率T(n)中，n表示问题的规模。当n连续变化时，T(n)也会随之变化。那么，如果我们想知道T(n)随着n的变化会呈现什??么样的规律，那么就需要引入时间复杂度的概念。一般来说，算法基本操作的重复执行次数是问题规模n的函数，用时间频率T(n)表示。若存在函数f(n)使得当n趋于无穷大时，T(n)/f(n)的极限值为非零常数，则f(n)与T(n)大小相同)记为T(n)=O(f(n))的函数，称为O(f(n))作为算法的渐近时间复杂度，简称时间复杂度。渐近时间复杂度用大写的O表示，所以也称为大O表示法。该算法的时间复杂度函数为：T(n)=O(f(n))；T(n)=O(f(n))表示存在常数C，所以当n趋于正无穷大时，总有T(n)≤C*f(n)。简单来说，当n趋于正无穷大时，T(n)和f(n)的大小差不多。也就是说，当n趋于正无穷时，T(n)的上界为C*f(n)。f(n)虽无规定，但一般取函数越简单越好。常见的时间复杂度有：O(1)常量类型；O(logn)对数型、O(n)线性型、O(nlogn)线性对数型、O(n2)平方型、O(n3))立方型、O(nk)k次幂型、O(2n)指数型。上图展示了不同类型功能的增长趋势。随着问题规模n的增大，上述时间复杂度增大，算法的执行效率降低。常用算法的时间复杂度从小到大如下：〇(2^n)
