算法的优劣评判

  程序 = 数据结构 + 算法，同一问题可用不同算法解决，一个好的算法能够使程序运行变得更高效，可能你在编程为了解决某一类问题，经常会用到算法，但你知道这个算法的效率怎么样吗？有没有比它效率还高的算法呢？所以今天我就想跟大家分享一下如何判断一个算法的好坏。

五大评判条件

  1、时间复杂度
  2、空间复杂度
  3、正确性（要能使程序正确运行）
  4、可读性（供人阅读的容易程度）
  5、健壮性（算法对不合理数据输入的反应能力和处理能力，即容错性）
  我们主要是根据时间复杂度和空间复杂度来比较算法的好坏。

算法复杂度

时间复杂度

1、理解：

  它是指运行算法需要的计算工作量，是一个函数，描述了该算法的运行时间，时间复杂度常用大 O 符号表示。

2、计算方法：

  第一步：定义符号
  n：表示问题规模
  T(n)：表示重复执行的次数，定义域是 n，T(n) 是 n 的一个函数。
  f(n)：表示一个与 T(n) 同数量级的辅助函数

  第二步：考察当输入值大小趋近无穷
  当 n 趋近于无穷大时，T(n)/f(n) 的极限值为不等于零的常数，则称 f(n) 是 T(n) 的同数量级函数，记作 T(n)=O(f(n))
  其中 O(f(n)) 为算法的渐进时间复杂度，简称就是时间复杂度。可以看出，主要就是要求得 f(n) 就行。
  随着规模 n 的增大，算法执行的时间的增长率和 f(n) 的增长率成正比，f(n) 越小，时间复杂度越低。

3、例子

  上面做法就是，先算出基础操作的次数，然后再找出它的同数量级，最后比一下为常数。栗子如下：

1
2
3
4
5
6
7
8
9
10

int sum = 0;

for(int i = 0; i < n; i++){
  for(int j = 0; j < n; j++){
    s = i;//基本操作执行次数：n^2
    for(int k = 0; k < n; k++){
        s += j + k;//基本操作执行次数：n^3
    }
  }  
}

  总次数为 T（n）= n^2 + n^3，同数量级的一般取数量级高的 n^3，最后 T(n)/f(n) = 1/n + 1，当 n 趋近无穷时，T(n)/f(n) = 1，为一个常数，所以时间复杂度为 O(n^3)
  口算的计算方法是：看看有几重 for 循环，只有一重则时间复杂度为 O(n)，二重则为 O(n^2)，依此类推，如果有二分则为 O(logn)，二分例如二分查找，如果一个 for 循环套一个二分，那么时间复杂度则为 O(nlogn)。

空间复杂度

1、理解：

  它是指运行算法需要消耗的内存空间，详见百科空间复杂度。

2、时间复杂度函数

  O(1)：表示为一个常量，即不随被处理数据量 n 的大小而改变。
  O(log2n)：表示一个算法的空间复杂度与以 2 为底的 n 的对数成正比。
  O(n)：表示一个算法的空间复杂度与 n 成线性比例关系。
  等等, 以此类推……

时间复杂度与空间复杂度的关系

  时间复杂度和空间复杂度往往是相互影响，一个好另一个坏，反之。所以我们常会结合实际的需求来选择牺牲某一个换取另一个。

总结

  选择一个高效的算法，主要是看时间复杂度和空间复杂度，当两者不能同时达到最优时，我们应该根据实际软件的要求，有舍有得，达到在时间上的高效利用或空间上的高效利用。