数据结构与算法 - 概述

数据结构与算法 - 概述，基本概念、相关术语、时间复杂度、空间复杂度。

三个层次五个要素

	数据表示	数据处理
抽象	逻辑结构	基本运算
实现	存储结构	算法
评价	不同数据结构的比较及算法分析

算法与算法分析

算法与数据结构的关系紧密，在算法设计时先要确定相应的数据结构，而在讨论某一种数据结构时也必然会涉及相应的算法。

算法的特性
算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。一个算法应该具有下列特性：

有穷性：一个算法必须在有穷步之后结束，即必须在有限时间内完成；
确定性：算法的每一步必须有确切的定义，无二义性。算法的执行对应着的相同的输入仅有唯一的一条路经；
可行性：算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现；
输入：一个算法具有零个或多个输入，这些输入取自特定的数据对象集合；
输出：一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。

算法与数据结构是相辅相承的
解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率；
反之，一种数据结构的优劣由各种算法的执行来体现，要设计一个好的算法通常要考虑以下的要求：

正确：算法的执行结果应当满足预先规定的功能和性能要求；
可读：一个算法应当思路清晰、层次分明、简单明了、易读易懂；
健壮：当输入不合法数据时，应能作适当处理，不至引起严重后果；
高效：有效使用存储空间和有较高的时间效率。

如何描述算法
算法描述是指对设计出的算法，用一种方式进行详细的描述，以便与人交流。描述可以使用自然语言、伪代码，也可使用程序流程图，但描述的结果必须满足算法的五个特征。

使用自然语言描述算法显然很有吸引力，但是自然语言固有的不严密性使得要简单清晰的描述算法变得很困难。因此，使用伪代码来描述算法是一个很好的选择。

伪代码是自然语言和类编程语言组成的混合结构。它比自然语言更精确，描述算法很简洁；同时也可以很容易转换成计算机程序。虽然如此，但计算机科学家们从来就没有对伪代码的形式达成共识，不同作者的教材会设计他们自己的“方言”（伪代码）。幸运的是，这些伪代码都十分相似，任何熟悉一门现代编程语言的人都完全能够理解。使用伪代码描述算法可以让程序员很容易将算法转换成程序，同时还可以避开不同程序语言的语法差别。

算法性能分析与度量
我们可以从一个算法的时间复杂度与空间复杂度来评价算法的优劣（大 O 表示法）。

当我们将一个算法转换成程序并在计算机上执行时，其运行所需要的时间取决于下列因素：

硬件的速度：例如使用 486 机还是使用 586 机；
书写程序的语言：实现语言的级别越高，其执行效率就越低；
目标代码的质量：对于代码优化较好的编译程序其所生成的程序质量较高；
问题的规模：例如，求 100 以内的素数与求 1000 以内的素数其执行时间必然是不同的。

显然，在各种因素都不能确定的情况下，很难比较出算法的执行时间。也就是说，使用执行算法的绝对时间来衡量算法的效率是不合适的。为此，可以将上述各种与计算机相关的软、硬件因素都确定下来，这样一个特定算法的运行工作量的大小就只依赖于问题的规模（通常用正整数 n 表示），或者说它是问题规模的函数。

通常，对于一个给定的算法，我们要做两项分析：
第一步：从数学上证明算法的正确性，这一步主要用到形式化证明的方法及相关推理模式，如循环不变式、数学归纳法等；
第二步：分析算法的时间复杂度，算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。因此作为程序员，掌握基本的算法时间复杂度分析方法是很有必要的。

算法执行时间需通过依据该算法编写的程序在计算机上运行所消耗的时间来度量，度量一个程序的执行时间通常有两种方法：

事后统计的方法：这种方法可行，但不是一个好的方法。该方法有两个缺陷：
- 一是要想对设计的算法的运行性能进行评测，必须先依据算法编写相应的程序并实际运行；
- 二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优势。
事前分析估算的方法：因事后统计方法更多的依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣，因此人们常常采用事前分析估算的方法，在编写程序前，依据统计方法对算法进行估算。一个算法是由控制结构（顺序、分支和循环）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。为了便于比较同一个问题的不同算法，通常的做法是：从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作的重复执行的次数作为算法的时间量度。

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

时间复杂度
在刚才提到的时间频度中，n 称为问题的规模，当 n 不断变化时，时间频度 T(n) 也会不断变化。但有时我们想知道它变化时呈现什么规律，为此，我们引入时间复杂度概念。

一般情况下，算法中基本操作重复执行的次数是问题规模 n 的某个函数，用 T(n) 表示；若有某个辅助函数 f(n)，使得当 n 趋近于无穷大时，T(n)/f(n) 的极限值为不等于零的常数；则称 f(n) 是 T(n) 的同数量级函数，记作T(n) = Ｏ(f(n))，称Ｏ(f(n))为算法的渐进时间复杂度，简称时间复杂度。

T(n) = Ο(f(n))表示存在一个常数 C，使得在当 n 趋于正无穷时总有T(n) ≤ C*f(n)。简单来说，就是 T(n) 在 n 趋于正无穷时最大也就跟 f(n) 差不多大，也就是说当 n 趋于正无穷时 T(n) 的上界是 C*f(n)，其虽然对 f(n) 没有规定，但是一般都是取尽可能简单的函数。

例如，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(logn)、线性阶O(n)、线性对数阶O(nlogn)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低。注意，在大 O 表示法中的 log 如果省略底数，则默认为 2。

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

求解算法的时间复杂度的具体步骤

找出算法中的基本语句
算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
计算基本语句的执行次数的数量级
计算执行次数数量级时，只需保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
用大 Ο 记号表示算法的时间性能
将基本语句执行次数的数量级放入大 Ο 记号中。
如果算法中包含嵌套的循环，则基本语句通常是最内层循环体；
如果算法中包含并列的循环，则将并列循环的时间复杂度相加。

来看一个简单的例子：

第一个 for 循环的时间复杂度为O(n)，第二个 for 循环的时间复杂度为O(n^2)，所以整个算法的时间复杂度为O(n + n^2) = O(n^2)（只保留最高次幂即可）。

时间复杂度的其它知识
Ο(1) 表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是 Ο(1)。其中 Ο(logn)、Ο(n)、Ο(nlogn)、Ο(n^2) 和 Ο(n^3) 称为多项式时间，而 Ο(2^n) 和 Ο(n!) 称为指数时间。计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法，把这类问题称为 P（Polynomial，多项式）类问题，而把后者（即指数时间复杂度的算法）称为 NP（Non-Deterministic Polynomial，非确定多项式）问题。

时间复杂度的分析法则

对于一些简单的输入输出语句或赋值语句，近似认为需要O(1)时间。
对于顺序结构，需要依次执行一系列语句所用的时间可采用大 O 下求和法则。
求和法则是指若算法的 2 个部分时间复杂度分别为T1(n)=O(f(n))和T2(n)=O(g(n))，则T1(n)+T2(n)=O(max(f(n), g(n)))。特别地，若T1(m)=O(f(m))，T2(n)=O(g(n))，则T1(m)+T2(n)=O(f(m) + g(n))。
对于选择结构，如 if 语句，它的主要时间耗费是在执行 then 字句或 else 字句所用的时间，需注意的是检验条件也需要 O(1) 时间。
对于循环结构，循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费，一般可用大 O 下乘法法则。
乘法法则是指若算法的 2 个部分时间复杂度分别为T1(n)=O(f(n))和T2(n)=O(g(n))，则T1*T2=O(f(n)*g(n))。
对于复杂算法，可以将它分成几个容易估算的部分，然后利用求和法则和乘法法则计算整个算法的时间复杂度。
另外还有以下 2 个运算法则：
1、O(Cf(n)) = O(f(n))，其中 C 是一个正常数；
2、若g(n) = O(f(n))，则O(f(n)) + O(g(n)) = O(f(n))。

空间复杂度
类似于时间复杂度的讨论，一个算法的空间复杂度（Space Complexity），S(n)，定义为该算法所耗费的存储空间，它也是问题规模 n 的函数，渐近空间复杂度也常简称为空间复杂度。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面：

存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法；
算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变；
算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是就地进行的，是节省存储的算法；有的算法需要占用的临时工作单元数与解决问题的规模 n 有关，它随着 n 的增大而增大，当 n 较大时，将占用较多的存储单元。

常见的空间复杂度（从好到坏）
当一个算法的空间复杂度为一个常量，即不随问题规模 n 的大小而改变，可表示为O(1)；
当一个算法的空间复杂度与以 2 为底 n 的对数成正比时，可表示为O(logn)；
当一个算法的空间复杂度与 n 成线性比例关系时，可表示为O(n)。

条条大路通罗马，不如出生在罗马