定义

算法（Algorithm）

算法是解决问题的步骤，是指解决问题的方案准确且完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

算法\(+\)数据结构\(=\)应用程序
算法的特征：
- 可行性
  - 一个有限指令集
  - 算法中执行的任何计算步骤都是可以被分解为基本可执行的操作步，即每个计算步都可以在有限的时间内完成（也称有效性）
- 输入项
  - 接受一些输入（有些情况下不需要输入）
  - 一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出的初始条件
- 输出项
  - 产生输出
  - 一个算法有一个或多个输出，以反映对输入数据加工后的结果，~~没有输出的算法是毫无意义的~~
- 有穷性
  - 一定在有限步骤之后终止
  - 一个算法必须总是在执行有限的步骤后结束，且每一步都必须在有限的时间内完成
- 确切性
  - 每一条指令必须：
    - 有充分明确的目标，不可以有歧义
    - 计算机能处理的范围之内
    - 描述不应该依赖于任何一种计算机语言以及具体的实现手段
  - 算法的每一步必须有确切的定义

一个算法是由控制结构（顺序、分支和循环）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。为了比较同一个问题的不同算法，通常的做法：从算法中选取一种对于研究的问题(或算法类型)来说是基本操作的原操作,以该操作的重复执行的次术作为算法的时间量度。

什么是好的算法?

虽然计算机能快速的完成运算处理，但实际上，它也需要根据输入数据的大小和算法效率来消耗一定的处理器资源。要想编写出能高效运行的程序，我们就需要考虑到算法的效率。

算法的效率主要由以下两个复杂度来评估
- 时间复杂度\(T(n)\)
  - 根据算法写成的程序在执行的时候耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效可能导致我们有生之年都等不到运行结果。
- 空间复杂度\(S(n)\)
  - 根据算法写成的程序在执行的时候占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限,造成程序非正常中断。
在分析一般算法的效率时,我们经常关注下面两种复杂度
- 最坏情况复杂度\(T_w(n)\)
- 平均复杂度\(T_a(n)\)
\(T_a(n)\leq T_w(n)\)

设计算法时,一般要先考虑系统环境,然后权衡时间复杂度和空间复杂度,选取一个平衡点。不过,时间复杂度比空间复杂度更容易产生问题,因为算法研究的主要也是时间复杂度,不特别说明的情况下,复杂度就是指时间复杂度。

时间复杂度

时间频度

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为\(T(n)\)。
时间复杂度

在刚才提到的时间频度中，\(n\)称为问题的规模，当\(n\)不断变化时，时间频度\(T(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(2n^2+n +1)\) \(=\) \(O (3n^2+n+3)\) \(=\) \(O (7n^2+n)\) \(=\) \(O(n^2)\),一般只用\(O(n^2)\)表示就可以了。

注意到大\(O\)符号里隐藏着一个常数\(C\)，所以\(f(n)\)里一般不加系数。如果把\(T(n)\)当做一棵树，那么\(O(f(n))\)所表达的就是树干，只关心其中的主干，其他的细枝末节全都抛弃不管。

在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为\(O(1)\)。另外，在时间频度不相同时，时间复杂度有可能相同，如\(T(n)=n^2+3n+4\)与\(T(n)=4n^2+2n+1\)它们的频度不同，但时间复杂度相同，都为\(O(n^2)\)。

按数量级递增排列，常见的时间复杂度有：

常数阶\(O(1)\)
对数阶\(O(log_2n)\)
线性阶\(O(n)\)
线性对数阶\(O(nlog_2n)\)
平方阶\(O(n^2)\)
立方阶\(O(n^3)\)

...
k次方阶\(O(n^k)\)
指数阶\(O(2^n)\)
阶乘阶\(O(n!)\)

随着问题规模\(n\)的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

时间复杂度的增长趋势

由此图可见，我们应该尽可能选用多项式阶\(O(n^k)\)甚至更优\(O(nlog_2n)\)的算法，而不希望用指数阶的算法

复杂度的比较

\(n\)	\(logn\)	\(\sqrt{n}\)	\(nlogn\)	\(n^2\)	\(2^n\)	\(n!\)
\(5\)	\(2\)	\(2\)	\(10\)	\(25\)	\(32\)	\(120\)
\(10\)	\(3\)	\(3\)	\(30\)	\(100\)	\(1024\)	\(3628800\)
\(50\)	\(5\)	\(7\)	\(250\)	\(2500\)	\(10^{15}\)	\(3.0*10^{64}\)
\(100\)	\(6\)	\(10\)	\(600\)	\(10000\)	\(10^{30}\)	\(9.3*10^{157}\)
\(1000\)	\(9\)	\(31\)	\(9000\)	\(1000000\)	\(10^{300}\)	\(4.0*10^{2567}\)

常见的算法时间复杂度由小到大依次为：\(Ο(1)＜Ο(log_2n)＜Ο(n)＜Ο(nlog_2n)＜Ο(n^2)＜Ο(n^3)＜…＜Ο(2^n)＜Ο(n!)\)

一般情况下，对一个问题（或一类算法）只需选择一种基本操作来讨论算法的时间复杂度即可，有时也需要同时考虑几种基本操作，甚至可以对不同的操作赋予不同的权值，以反映执行不同操作所需的相对时间，这种做法便于综合比较解决同一问题的两种完全不同的算法。

分析算法的时间复杂度
- 若两段算法分别有复杂度\(T_1(n)=O(f_1(n))和T_2(n)=O(f_2(n))\)，则
  - \(T_1(n)+T_2(n)=max(O(f_1(n)),O(f_2(n)))\)
  - \(T_1(n)*T_2(n)=O(f_1(n)*f_2(n))\)
- 若\(T(n)\)是关于\(n\)的\(k\)阶多项式，那么\(T(n)=O(n^k)\)
- 一个\(for\)循环的时间复杂度等于循环次数\(*\)循环体代码的复杂度
- \(if-else\)结构的复杂度取决于\(if\)的条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者中最大

空间复杂度

空间复杂度\((Space Complexity)\)
- 类似于时间复杂度的讨论，一个算法的空间复杂度\((Space Complexity)S(n)\)定义为该算法所耗费的存储空间，它也是问题规模\(n\)的函数。渐近空间复杂度也常常简称为空间复杂度。
- 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地"进行的，是节省存储的算法。有的算法需要占用的临时工作单元数与解决问题的规模\(n\)有关，它随着\(n\)的增大而增大，当\(n\)较大时，将占用较多的存储单元。
当一个算法的空间复杂度为一个常量，即不随被处理数据量\(n\)的大小而改变时，可表示为\(O(1)\)
当一个算法的空间复杂度与以\(2\)为底的\(n\)的对数成正比时，可表示为\(O(log_2n)\)
当一个算法的空间复杂度与\(n\)成线性比例关系时，可表示为\(O(n)\)
若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间
若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量