算法
算法定义
算法（Algorithm）： 是解决 特定问题 求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
算法特性
算法有五个基本特性： 有限性、确定性、输入、输出和可行性。
输入输出： 算法具有至少一个或多个输出，具有零个或多个输入。
有限性： 算法在执行有限步骤后，自动结束而不会出现无限循环，并且每一个步骤都在可接受的时间内完成。
确定性： 算法的每一步骤都具有正确的定义，不会出现二义性。
可行性： 算法的所有操作都必须是可行的，每一步骤都可以通过已经实现的基本操作运算执行有限次来实现。
算法设计要求（评价优劣的基本标准）
（1） 正确性： 在合理的数据输入下，能够在有限的运行时间内通过优先步骤得到正确的结果。
（2） 可读性： 算法设计的另一个目的是为了便于阅读、理解和交流
（3） 健壮性： 当输入不合法时，算法能对其做出相关处理，而不是产生异常或莫名其妙的结果
（4） 高效性： 高效性包括时间和空间两方面，设计算法一个尽量满足时间效率高和存储量低的需求
算法效率的度量方法
衡量算法效率的方法 主要有两类： 事后统计法 和 事前分析估计法 。
事后统计法
事后统计法： 这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。
这个方法是有很大的 缺陷 的：
- 必须算法事先编制好程序，需要花费大量时间和精力，还不能确定是不是糟糕的算法；
- 时间的比较很依赖计算机硬件和软件等环境因素，有时会掩盖算法本身的优劣；
- 算法的测试数据设计困难，并且程序的运行时间通常与测试数据的规模有很大关系，效率高的算法在小的测试数据面前往往得不到体现，比如10个数的排列，无论用什么算法，差异几乎为零。
事前分析估计法
事前分析估计： 在计算机程序编制前，依据统计方法对算法进行估算。
不考虑计算机的软硬件等环境因素，影响算法时间的因素有问题规模和算法好坏，其中最主要因素是问题规模。
问题规模： 算法求解的输入量的多少，是问题大小的本质表示，一般用 n 表示
语句频度（Frequency Count）： 一条语句的重复执行次数
函数的渐近增长
渐近增长的函数： 输入规模 n 在没有限制的情况下，只要超过一个数值 N ，这个函数就总是大于另一个函数。给定两个函数 f(n) 和 g(n) ，如果存在一个整数 N ，当 n > N 时， f(n) > g(n) 总成立，则 f(n) 的增长渐近快于 g(n) 。
①我们可以忽略加法常数；
②与最高次项相乘的常数并不重要；
③最高次项的指数越大，函数增长越快；
④判断一个算法的效率时，函数的常数和其他次要项常常被忽略，而更应该关注主项（最高阶项）的阶数。
某个算法，随着问题规模 n 的增大，它会越来越优于另一个算法，或是越来越劣于另一个算法。
算法的时间复杂度的定义
为了客观地反映一个算法的执行时间，可以只用算法中的“基本语句”的执行次数来度量算法的工作量。
基本语句： 指的是算法中 重复执行次数和算法的执行时间成正比的语句 。
算法中基本语句重复执行的次数是问题规模 n 的某个函数 f(n) ， 算法的渐近时间复杂度 也被称为 算法的时间量度 ，简称 时间复杂度 记作： T(n)=O(f(n))
①其中 语句总的执行次数 T(n) 是关于问题规模 n 的函数。
②其中数学符号 “O” 表示 数量级 。
T(n)=O(f(n)) 表示了 随问题规模 n 的增大，算法执行时间的增长率和 f(n) 的增长率相同 ，也被称作时间复杂度
算法的渐近时间复杂度 = 算法的时间量度 = 时间复杂度
像这样用数学符号 O 来体现算法时间复杂度的记法，被称为 大O记法
最优算法： 随着问题规模 n 的增大， T(n) 增长最慢的算法。
推导大 O 阶方法
推导大 O 阶：
- 用常数 1 取代语句频度中所有的加法常数
- 在修改后的运行次数函数中，只保留最高阶项
- 如果最高阶项存在且不是1，则去除所有与这个项相乘的常数
得到的结果就是大 O 阶
以下是常见的时间复杂度：
最坏、最好和平均时间复杂度
对于某些问题的算法，它的时间复杂度不仅仅与问题的规模相关，还依赖于其他因素。
最好时间复杂度： 算法在最好情况下的时间复杂度，指的是算法计算量可能达到的最小值；
最坏时间复杂度： 算法在最坏情况下的时间复杂度，指的是算法计算量可能达到的最大值；
平均时间复杂度： 是所有情况中最有意义的，它是最期望的运行时间，但是一般都是通过运行一定数量的实验数据后估算出来的。
一般在没有特殊说明的情况下，都是指最坏时间复杂度。
算法空间复杂度
算法的渐近空间复杂度 = 算法所需存储空间的量度 = 空间复杂度
算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式为： S(n)=O(f(n))
一般情况下，一个程序在机器上执行，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要一些 对数据进行操作 的 辅助存储空间 。其中，对于输入数据所占的具体存储量取决于问题本身，与算法无关，这样只需要分析该算法在实现时所需要的辅助空间即可。
若算法执行时所需的辅助空间相对于输入数据量是个常数，则称此算法为 原地工作 ，空间复杂度 S(n)=O(1)
对于一个算法，时间复杂度和空间复杂度往往是相互影响的，好的时间复杂度往往会导致空间复杂度变坏，反之亦然。但由于内存空间较为充足，所以一般首先考虑的是时间复杂度。
