51. 算法

• 数据结构与算法关系

  数据结构与算法之间的关系类似于：梁山伯与祝英台或者说是罗密欧与朱丽叶

• 算法定义

  算法：解决特定问题求解步骤的描述，在计算机中变现为指令的有限序列，并且每条指令表示一个或多个操作。

• 算法的特性

  1. 输入
  2. 输出
  3. 有穷性
  4. 确定性
  5. 可行性

• 算法设计的要求

  1. 正确性：
     1. 层次：
        1. 算法程序没有语法错误
        2. 算法程序对于合法的输入数据能够产生满足要求的输出结果
        3. 算法程序对于非法的输入数据能够得出满足规格说明的结果
        4. 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果
     2. 算法的正确性在大部分情况下都不可能用程序来证明，而是用数学方法证明的
     3. 一般情况下，我们把层次3作为一个算法是否正确的标准
  2. 可读性
     1. 算法设计的另一个目的是为了便于阅读、理解和交流
  3. 健壮性
     1. 当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果
  4. 时间效率高和存储量低
     1. 时间效率：算法的执行时间
     2. 存储量需求：算法在执行过程中需要的最大存储空间，主要指算法程序运行时所占用的内存或外部硬盘存储空间
     3. 设计算法应该尽量满足时间效率高和存储量低的需求

• 算法效率的度量方法

  1. 事后统计方法
     1. 存在各种各样的缺陷，一般不予考虑
  2. 事前分析估算方法
     1. 时间取决因素：
        1. 算法采用的策略、方法
        2. 编译产生的代码质量
        3. 问题的输入规模
        4. 机器执行指令的速度

           其中：第1条是算法好坏的根本；第2条由软件来支持；第3条看硬件性能。

           抛开这些与计算机硬件软件有关的因素，一个程序的运行时间，依赖于算法的好坏和问题的输入规模。所谓 问题输入规模是指输入量的多少

     2. 最终，再分析程序的运行时间时，最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤

• 函数的渐近增长

  1. 给定两个函数$f(n)$ 和 $g(n)$，如果存在一个整数N，使得对于所有的 n > N，$f(n)$ 总是比 $g(n)$大，那么我们说 $f(n)$的增长渐近快于 $g(n)$
  2. 与最高次相乘的常数并不重要
  3. 判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而应该关注主项（最高阶项）的阶数

• 算法时间复杂度

  1. 算法时间复杂度定义：
     
     在进行算法分析时，语句总的执行次数 $T(n)$是关于问题规模n的函数，进而分析 $T(n)$随n的变化情况并确定 $T(n)$的数量级。算法的时间复杂度，也就是算法的时间量度，记作：$T(n)$=$O(f(n))$。它表示岁问题规模n的增大，算法执行时间的增长率和$f(n)$的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中$f(n)$是问题规模n的某个函数。
  2. 一般情况下，随着n的增大，$T(n)$增长最慢的算法为最优算法。

• 常见的时间复杂度

  $O(1) < O(logn) < O(n) < O(nlogn) < O(n ^ 2) < O(n ^ 3) < O(2 ^ n) < O(n!) < O(n ^ n)$