算法设计的时间空间权衡原则

❶ 算法复杂度：时间复杂度和空间复杂度

本文部分摘抄于此
算法复杂度分为时间复杂度和空间复杂度。
时间复杂度是指执行算法所需要的计算工作量；
而空间复杂度是指执行这个算法所需要的内存空间。
（算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度）。

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

并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。

将基本语句执行次数的数量级放入大Ο记号中。

如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。

第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο( n 2)，则整个算法的时间复杂度为Ο(n+ n 2)=Ο( n 2)。

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

（4）在计算算法时间复杂度时有以下几个简单的程序分析法则:

(1).对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间

(2).对于顺序结构,需要依次执行一系列语句所用的时间可采用大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))

(3).对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间

(4).对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下"乘法法则"

乘法法则 : 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则T1 * T2=O(f(n) * g(n))

(5).对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度

另外还有以下2个运算法则:(1) 若g(n)=O(f(n)),则O(f(n))+ O(g(n))= O(f(n))；(2) O(Cf(n)) = O(f(n)),其中C是一个正常数

（5）下面分别对几个常见的时间复杂度进行示例说明：

(1)、O(1)

​ Temp=i; i=j; j=temp;

以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。 注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

(2)、O(n2)

2.1. 交换i和j的内容

解： 因为Θ(2n2+n+1)=n2（Θ即：去低阶项，去掉常数项，去掉高阶项的常参得到），所以T(n)= =O(n2)；

2.2.

​

解： 语句1的频度是n-1

一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

(3)、O(n)

解：

(4)、O(log2n)

解：

(5)、O(n3)

解：

（5）常用的算法的时间复杂度和空间复杂度

一个经验规则： 其中c是一个常量，如果一个算法的复杂度为c 、 log2n 、n 、 n log2n ,那么这个算法时间效率比较高 ，如果是 2n * , 3n ,n!，那么稍微大一些的n就会令这个算法不能动了，居于中间的几个则差强人意。

​ 算法时间复杂度分析是一个很重要的问题，任何一个程序员都应该熟练掌握其概念和基本方法，而且要善于从数学层面上探寻其本质，才能准确理解其内涵。

2、算法的空间复杂度

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

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

算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。

算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地"进行的，是节省存储的算法，如这一节介绍过的几个算法都是如此；

有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如将在第九章介绍的快速排序和归并排序算法就属于这种情况。

如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)；当一个算法的空I司复杂度与n成线性比例关系时，可表示为O(n).

【1】如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

解答：
T(n)=O(1)，
这个程序看起来有点吓人，总共循环运行了1100次，但是我们看到n没有?
没。这段程序的运行是和n无关的，
就算它再循环一万年，我们也不管他，只是一个常数阶的函数

【2】当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(5)的执行次数：
则该程序段的时间复杂度为T(n)=O(n3/6+低次项)=O(n3)

【3】算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。

在数值A[0..n-1]中查找给定值K的算法大致如下：

此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关:

（5）时间复杂度评价性能

有两个算法A1和A2求解同一问题，时间复杂度分别是T1(n)=100n2，T2(n)=5n3。
（1）当输入量n＜20时，有T1(n)＞T2(n)，后者花费的时间较少。
（2）随着问题规模n的增大，两个算法的时间开销之比5n3/100n2=n/20亦随着增大。
即当问题规模较大时，算法A1比算法A2要有效地多。它们的渐近时间复杂度O(n2)和O(n3)从宏观上评价了这两个算法在时间方面的质量。

在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。

其实生活很美好，只是你想的太多了。没有，不会，有差距很正常，因为我不会

❷ 算法的设计原则是什么

1.穷举算法思想

穷举算法思想就是从所有的可能结果中一个一个的试验，知道试出正确的结果。具体的操作步骤如下：

1)对每一种可能的结果，计算其结果；

2)判断结果是否符合题目要求，如果符合则该结果正确，如果不符合则继续进行第1)步骤。

穷举算法思想的经典例子为鸡兔同笼为题（又称龟鹤同笼问题），题目为“一个笼子里有鸡兔，共15个头、46条腿，问鸡兔各有多少只？”。代码如下：

public static void main(String[] args) {

int head = 0;
int leg = 0;
System.out.println( "输入鸡兔头数：");
Scanner input=new Scanner(System.in);
head = input.nextInt();
System.out.println( "输入鸡兔腿数：");
Scanner input1=new Scanner(System.in);
leg = input1.nextInt();

boolean existence = false;
for( int i = 0; i <= head; i++){
if( 2 * i + 4 * ( head - i) == leg){
System.out.println( "鸡的个数 :" + i);
System.out.println( "兔的个数 :" + ( head - i));
existence = true;
}
}

if( !existence){
System.out.println( "你输入的数据不正确");
}
}

2.递推算法思想

递推算法算法就是根据已知条件，利用特定关系推导出中间推论，直到得到结果的算法。

递推算法思想最经典的例子是斐波那契数列 : 1,1,2,3,5,8,13......

上面的数列符合F(n) = F(n-1) + F(n-2).代码如下：

public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n = input.nextInt();
System.out.println( fibonacci( n));
}

public static int fibonacci( int n){
if( n == 1){
return 1;
}else if( n == 2){
return 1;
}else{
return fibonacci( n - 1) + fibonacci( n - 2);
}
}

3.递归算法思想

递归算法思想是把大问题转换成同类问题的子问题，然后递归调用函数表示问题的解。

在使用递归的时候一定要注意调回递归函数的终止条件。

递归算法比较经典的例子是求阶乘。代码如下：

public static void main(String[] args) {
System.out.println( "输入一个大于零的数：");
Scanner input=new Scanner(System.in);
int n = input.nextInt();
System.out.println( factorial( n));
}

public static int factorial( int n){
if( n == 0){
return 1;
}else if( n == 1){
return 1;
}else{

❸ 设计算法的原则

设计算法的原则：

1、正确性：算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需要、能够得到问题的正确答案。

2、可读性：设计算法的目的，一方面是为了让计算机执行，但还有一个重要的目的就是为了便于他人的阅读，让人理解和交流，自己将来也可阅读。如果可读性不好，时间长了自己都不知道写了什么，可读性是评判算法（也包括实现它的程序代码）好坏很重要的标志。

3、健壮性：当输入的数据非法时，算法应当恰当地做出反应或进行相应处理，而不是莫名其妙的输出结果。并且处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便于在更高的抽象层次上进行处理。

4、高效率与低存储量：通常，算法的效率指的是算法的执行时间；算法的存储量指的是算法执行过程中所需要的最大存储空间，两者的复杂度都与问题的规模有关。算法分析的任务是对设计的每一个具体的算法，利用数学工具，讨论其复杂度，探讨具体算法对问题的适应性。

(3)算法设计的时间空间权衡原则扩展阅读：

算法的“正确”通常在用法上有很大的差别，大体分为以下4个层次：

1、算法程序没有语法错误；

2、算法程序能够根据正确的输入的值得到满足要求的输出结果；

3、算法程序能够根据错误的输出的值满足规格说明的输出结果；

4、算法程序对于精心设计、极其刁难的测试数据都能满足要求的输出结果。

对于这4层含义，层次要求最低，因为仅仅没有语法错误实在谈不上是好的算法。而层次（4）是最困难的，人们几乎不可能逐一验证所有的输入都得到正确的结果。因此，算法的正确性在大部分情况下都不可能用程序来证明，而是用数学方法证明的。

❹ 算法设计原则是什么

原则：首先说设计的算法必须是"正确的"，其次应有很好的"可读性"，还必须具有"健壮性"，最后应考虑所设计的算法具有"高效率与低存储量"。

所谓算法是正确的，除了应该满足算法说明中写明的"功能"之外，应对各组典型的带有苛刻条件的输入数据得出正确的结果。

在算法是正确的前提下，算法的可读性是摆在第一位的，这在当今大型软件需要多人合作完成的环境下是换重要的，另一方面，晦涩难读的程序易于隐藏错误而难以调试。算法的效率指的是算法的执行时间，算法的存储量指的是算法执行过程中所需最大存储空间。

算法是程序设计的另一个不可缺的要素，因此在讨论数据结构的同时免不了要讨论相应的算法。这里有两重意思，即算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。

确定性表现在对算法中每一步的描述都没有二义性，只要输入相同，初始状态相同，则无论执行多少遍，所得结果都应该相同。

可行性指的是，序列中的每个操作都是可以简单完成的，其本身不存在算法问题，例如，"求x和y的公因子"就不够基本。

输入值即为算法的操作对象，但操作的对象也可以由算法自身生成，如"求100以内的素数"，操作对象是自然数列，可以由变量逐个增1生成。

算法的健壮性指的是，算法应对非法输入的数据作出恰当反映或进行相应处理，一般情况下，应向调用它的函数返回一个表示错误或错误性质的值。

❺ 一文讲透算法中的时间复杂度和空间复杂度计算方式

作为一名“程序猿”，大家应该都听过这么一句话：程序=数据结构+算法。

这句话是由瑞士计算机科学家尼古拉斯·沃斯（Niklaus Wirth）在 1984 年获得图灵奖时说的一句话，这位大佬还以这句话为名出了一本书《Algorithms + Data Structures=Programs》，从此这句话就成为了大家耳熟能详的一句名言。

随着时间的推移，不管这句话是不是非常准确，但至少能说明数据结构与算法对程序来说是非常核心的基础，如果我们想要写出更多优秀优雅的代码，那么数据结构与算法是必须要掌握好的。

很多人可能觉得，我不会算法，代码一样写得很"溜"，算法这东西似乎用处不大。现在互联网的发达，我们想要什么几乎都可以在网上找到现成的，各种框架功能十分强大，似乎看起来确实不用算法也可以写出“好代码”。然而假如我们不懂算法，比如项目中用到了排序，我们如何评估代码的执行效率？再比如最常用的 ArrayList 和 LinkedList ，我们该如何选择，又比如说我们需要去集合中找某一个数，又该如何写出性能优秀的代码呢？

同样的代码，如何判断谁的代码是优秀的代码？可读性，可扩展性，健壮性可能都可以用来判定，然而这些东西我觉得并不能直接体现出你代码的优秀，因为对用户而言，访问你的代码响应速度快那就是优秀的代码，相反，动辄响应几秒甚至更长时间的接口，恐怕就算你可读性再好，再健壮也称不上是好代码。

所以说一段代码是否优秀，最直接的判断标准就是性能，而如果要写出高性能的代码，那么就必须要了解算法，而且抛开这个因素，但凡不想一辈子都写 CRUD 代码的，也需要去了解算法，我们使用的很多框架和中间件底层都有数据结构和算法的身影，学好算法对我们源码阅读时理解其设计思想也是大有裨益的。

要说功利性的目的，那就是面试，目前很多大厂的面试，算法基本必面，所以想进大厂的话，咱们也得好好学学算法。

提到算法，很多人的第一反应就是太难学了，学不会，或者说经常是看完就忘了，但是其实对于我们一个普通的开发者而言，因为并不需要我们去发明算法，我们需要的仅仅只是去灵活的运用算法，所以并不需要非常扎实的数据基础，当然基本的数学常识还是要有的。

如果说需要去发明设计一款算法，那就要去推导去证明算法的可行性，这种是需要具有非常扎实的数学基础的，一般人确实无法做到，然而我们普通程序员口中提到算法无非是二分查找法，哈希算法等，高级一点的就还有回溯，贪心，动态规划等等，这些所谓的算法都是已经有现成的公式了，我们要做的无非就是理解它，然后灵活的运用它。这就和我们以前学习数学公式一样，给你一个公式，然后你去做题，做题的过程其实就是去灵活地运用这个公式。

算法也是同理，都是有特定方法和特定思路的，我们也并不需要去推导证明这种方式为什么可行，所以学习算法没有其他诀窍，就是先理解思路，然后多练，等熟练了，自然就可以灵活运用了，也不会说学了立刻就忘了。学完就忘无非两个原因，一是没理解，二是没有练习巩固。

数据结构与算法经常是放在一起讲，这两者是没办法独立的，因为算法是为了达到某种目的的一种实现方式，而数据结构是一种载体，也就是说算法必须依赖数据结构这种载体，否则就是空谈。换句话说：数据结构是为算法服务的，而算法又需要作用在特定的数据结构之上。

一个算法到底好不好，我们如何去评价？前面我们提到了，你的代码好不好，最直观的就是看响应速度，算法也一样，同样实现一个目的（比如说排序），谁的算法速度快，我们就可以认为谁的算法更优，如果说两种算法实现的速度差不多，那么我们还可以去评价算法所占用的空间，谁占用的空间少，那么就可以认为谁的算法更优，这就是算法的基础：时间复杂度和空间复杂度。

学习算法之前，我们必须要学会如何分析时间复杂度和空间复杂度（也就是“快”和“省”），否则自己写出来的算法自己都不知道算法的效率。

接触过算法的都知道，算法的时间复杂度是用大写的“O”来表示的，比如： O(1) ， O(n) ， O(logn) ， O(nlogn) ， O(n²) 等等。

变量指的是变量，也就是一段代码的执行时间是随着变量的变化而变化的，而不变指的是常量，也就是不论我的变量如何改变，执行时间都不会改变。

接下来我们就实际的来分析下常用时间复杂度的例子来练习一下。

0(1) 复杂度算法也称之为常数阶算法。这里的 1 是用来代指常量，也就是说这个算法的效率是固定的，无论你的数据量如何变化，效率都一样，这种复杂度也是最优的一种算法。

上面的示例中不论有多少行代码，时间复杂度都是属于常数阶段。换言之：只要代码不存在 循环 ， 递归 等循环类调用，不论代码有多少行，其复杂度都是常数阶。

O(n) 复杂度算法也称之为线性阶段。比如下面这个示例我们应该怎么分析复杂度呢？

前面常量阶没分析是因为常量阶比较容易理解，接下来我们就以线性阶这个为例子来分析下具体是怎么得到的。

我们假设每一行代码的执行时间是 T ，那么上面这段代码的执行复杂度是多少呢？

答案很明显，那就是 T+n*T ，也就是 (n+1)T ，而在算法中有一个原则，那就是常量可以被忽略，所以就得到了 nT ，换成大 O 表示法就是 O(n) 。

这只是一个简略的计算过程，大家也不用较真说每行代码执行时间可能不一样之类的，也不要较真说 for 循环占用了一行，下面的大括号也占用了一行，如果要较真这个，那我建议可以去想一下 1=1 为什么等于 2 。

算法中的复杂度反应的只是一个趋势，这里 O(n) 反应的就是一个趋势，也就是说随着 n 的变化，算法的执行时间是会降低的。

知道了上面的线性阶，那么平方阶就很好理解了，双层循环就是平方阶，同理，三次循环就是立方阶， k 次循环就是 k 次方阶。

O(logn) 也称之为对数阶，对数阶也很常见，像二分查找，二叉树之类的问题中会见到比较多的对数阶复杂度，但是对数阶也是比较难理解的一种算法复杂度。

下面我们还是来看一个例子：

这段代码又该如何分析复杂度呢？这段代码最关键的就是要分析出 while 循环中到底循环了多少次，我们观察这个循环，发现 i 并不是逐一递增，而是不断地翻倍： 1->2->4->8->16->32->64 一直到等于 n 为什么才会结束，所以我们得到了这样的一个公式： 2^x=n 。

也就是说我们只要计算出 x 的值，就得到了循环次数，而根据高中的数学知识我们可以得到 x=log2n （ 2 在下面，是底数，试了几种方法都打不出来，放弃了），所以根据上面线性阶的分析方法，我们省略常量，就得到了示例中的算法复杂度为 O(log2n) 。

同样的分析方式，下面的例子，我们可以很快地分析出复杂度就为 O(log3n) ：

上面得到的 log3n 我们可以再做进一步的转换： log3n=log32 * log2n ，而 log32 （注意这几个地方的情况 3 是底数，在下面） 是一个常量，常量可以省略，所以也就得到了： O(log3n)=O(log2n) 。同样的道理，不论底数是多少，其实最终都可以转化成和 O(log2n) 相等，正因为如此，为了方便，我们算法中通常就会省略底数，直接写作 O(logn) 。

上面的数学公式大家如果忘了或者看不懂也没关系，只要记住不论对数的底数是多少，我们都算作 O(logn) ，而对于一个算法的复杂度是否是对数阶，还有一个简易的判断方法： 当循环中下标以指定倍数形式衰减，那么这就是一个对数阶 。

如果理解了上面的对数阶，那么这种线性对数阶就非常好理解了，只需要在对数阶的算法中再嵌一层循环就是线性对数阶：

分析了前面这些最常用的时间复杂度，其实我们可以得到以下规律：

除了上面常用的复杂度之外，另外还有指数阶，阶层阶，根号阶等，这些接触的相对会较少，我们就不特意做分析了，如果大家感兴趣的话，可以自己去了解下。

前面我们分析的都是只有一段代码比较复杂的情况下得到的复杂度结果，那么假如我一个算法中，有多段代码都比较复杂呢？这时候复杂度该如何分析？

我们先看下面这个例子：

这个例子中有三个循环，首先第一个，是一个常量，那么根据前面的结论，不论这个常量是多大，都属于常量级，所以第一个循环中的复杂度为 O(1) ，第二个和第三个循环我们前面也分析过，复杂度分别为 O(n) 和 O(n²) 。

也就是这一段代码中有三段代码产生了三种不同复杂度，而且这三个复杂度可以很明显得到的大小关系为： O(1)<o(n)<o(n²) span=""> </o(n)<o(n²)> ，像这种在同一个算法中有明确大小关系的，我们就可以直接取最大值作为这个算法的复杂度，所以这个例子中算法的复杂度就是 O(n²) 。

接下来我们再来看一个例子：

这个例子我们同样对三段循环分别分析可以分别得到如下复杂度： O(1) ， O(m) ， O(n) 。这时候我们只能知道 O(1) 最小可以忽略，但是后面两个无法却无法确定大小，所以这时候我们需要取两段循环复杂度之和来作为算法的复杂度，所以可以得到这个例子的算法复杂度为： O(m+n) 。

上面分析的时间复杂度都是比较简单的，实际算法中可能会比示例中复杂的多，而且我们示例中只要是循环都是无脑循环，也就是一定从头循环到尾，然而实际中我们有时候并不需要从头循环到尾，可能中途就会结束循环，所以我们根据实际情况，又可以将时间复杂度从以下四个方面来进一步分析：

这四种类型的时间复杂度在这里只会介绍前面三种，因为第四种比较复杂，而且使用场景也非常有限，而且对于这四种复杂度的分析，大家也作为了解就可以，不敢兴趣的朋友们可以跳过这一小部分，因为在绝大部分情况我们只需要分析最坏复杂度就行，也就是假设循环全部执行完毕场景下的时间复杂度。

我们通过一个例子来理解下最好时间复杂度：

这个方法就是在一个指定数组中找到指定元素的下标，找不到就返回 -1 ，这个方法比较简单，应该比较好理解。

注意这个方法中的循环体，如果找到元素，那么就直接返回，这就会有一个现象，那就是我这个循环体到底会循环多少次是不确定的，可能是 1 次，也可能是 n （假设数组的长度） 次，所以假如我们要找的元素就在数组中的第一个位置，那么我循环一次就找到了，这个算法的复杂度就是 O(1) ，这就是最好情况时间复杂度。

理解了最好时间复杂度，那么最坏时间复杂度也很好理解了，那就是数组中不存在我要找到元素，或者说最后一个值才是我要找的元素，那么这样我就必须循环完整个数组，那么时间复杂度就是 O(n) ，这也就是最坏时间复杂度。

最好时间复杂度和最坏时间复杂度毕竟只有特殊情况才会发生，概率还是相对较小，所以我们很容易就想到我们也需要有一个平均时间复杂度。

我们简单的来分析一下，为了便于分析，我们假设一个元素在数组和不在数组中的概率都为 1/2 ，然后假如在数组在，那么又假设元素出现在每个位置的概率也是一样的，也就是每个位置出现元素的概率为： 1/n 。

所以最终得到的平均时间复杂度应该等于元素在数组中和元素不在数组中两种情况相加。

因为元素在数组中的概率为 1/2 ，然后在每个位置出现的概率也为 1/n 。假如元素出现在第一个位置，复杂度为 1*(1/2n) ；假如元素出现在第二个位置，复杂度为 2 * (1/2n) ，最终得到当前场景下时间复杂度为： 1*(1/2n) + 2 * (1/2n) + ... + n*(1/2n) =(n+1)/4。

前面已经假定了元素不在数组中的概率为 1/2 ，所以当前场景下的时间复杂度为： n * (1/2) ，因为元素不在数组中，那么这个算法必然会将整个循环执行完毕，也就循环是 n 次。

最后我们把两种情况的复杂度之和相加就得到了平均时间复杂度： (n+1)/4 + n/2 = (3n+1)/4 ，最终我们将常数类的系数忽略掉，就得到了平均时间复杂度为 O(n) 。

均摊时间复杂度的算法需要使用摊还分析法，计算方式相对有点复杂，而且使用场景很有限，本文就不做过多介绍了。

空间复杂度全称就是渐进空间复杂度，用来表示算法的存储空间与数据规模之间的增长关系。和时间复杂度一样，空间复杂度也是用大 O 进行表示。

其实学会了分析时间复杂度，那么空间复杂度的分析就简单了，主要就看我们在一个算法当中到底有没有使用到了额外的空间来进行存储数据，然后判断这个额外空间的大小会不会随着 n 的变化而变化，从而得到空间复杂度。

我们来看一个给数组赋值例子，假设这就是一个算法，我们可以来分析下这个算法的空间复杂度：

一开始定义了一个变量，这里需要空间，但是这是一个常量级的（不随 n 的变化而变化），然后再定义了一个数组，数组的长度为 n ，这里数组也需要占用空间，而且数组的空间是随着 n 的变化而变化的，其余代码没有占用额外空间，所以我们就可以认为上面示例中的空间复杂度为 O(n) 。

对于算法的空间复杂度也可以简单的进行总结一下：

本文主要讲述了为什么要学习算法，也简单减少了数据结构与算法之间的关系，随后主要介绍了算法中的入门知识：时间复杂度和空间复杂度。想要学好算法，必须要掌握如何分析一个算法的时间复杂度和空间复杂度，只有自己会分析这两个个衡量算法主要性能的标准，才能更好的写出性能优秀的算法，同时我们也讲到了最好时间复杂度，最坏时间复杂度，平均时间复杂度和均摊时间复杂度，不过这四种复杂度的计算方式大家作为了解即可，等实际确实需要使用到再来回顾也不迟。

❻ 衡量算法效率的方法与准则

算法效率与分析
数据结构作为程序设计的基础，其对算法效率的影响必然是不可忽视的。本文就如何合理选择数据结构来优化算法这一问题，对选择数据结构的原则和方法进行了一些探讨。首先对数据逻辑结构的重要性进行了分析，提出了选择逻辑结构的两个基本原则；接着又比较了顺序和链式两种存储结构的优点和缺点，并讨论了选择数据存储结构的方法；最后本文从选择数据结构的的另一角度出发，进一步探讨了如何将多种数据结构进行结合的方法。在讨论方法的同时，本文还结合实际，选用了一些较具有代表性的信息学竞赛试题举例进行了分析
【正文】一、引论
“数据结构＋算法＝程序”，这就说明程序设计的实质就是对确定的问题选择一种合适的数据结构，加上设计一种好的算法。由此可见，数据结构在程序设计中有着十分重要的地位。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。因为这其中的“关系”，指的是数据元素之间的逻辑关系，因此数据结构又称为数据的逻辑结构。而相对于逻辑结构这个比较抽象的概念，我们将数据结构在计算机中的表示又称为数据的存储结构。
建立问题的数学模型，进而设计问题的算法，直至编出程序并进行调试通过，这就是我们解决信息学问题的一般步骤。我们要建立问题的数学模型，必须首先找出问题中各对象之间的关系，也就是确定所使用的逻辑结构；同时，设计算法和程序实现的过程，必须确定如何实现对各个对象的操作，而操作的方法是决定于数据所采用的存储结构的。因此，数据逻辑结构和存储结构的好坏，将直接影响到程序的效率。

二、选择合理的逻辑结构

在程序设计中，逻辑结构的选用就是要分析题目中的数据元素之间的关系，并根据这些特定关系来选用合适的逻辑结构以实现对问题的数学描述，进一步解决问题。逻辑结构实际上是用数学的方法来描述问题中所涉及的操作对象及对象之间的关系，将操作对象抽象为数学元素，将对象之间的复杂关系用数学语言描述出来。
根据数据元素之间关系的不同特性，通常有以下四种基本逻辑结构：集合、线性结构、树形结构、图状（网状）结构。这四种结构中，除了集合中的数据元素之间只有“同属于一个集合”的关系外，其它三种结构数据元素之间分别为“一对一”、“一对多”、“多对多”的关系。
因此，在选择逻辑结构之前，我们应首先把题目中的操作对象和对象之间的关系分析清楚，然后再根据这些关系的特点来合理的选用逻辑结构。尤其是在某些复杂的问题中，数据之间的关系相当复杂，且选用不同逻辑结构都可以解决这一问题，但选用不同逻辑结构实现的算法效率大不一样。
对于这一类问题，我们应采用怎样的标准对逻辑结构进行选择呢？
下文将探讨选择合理逻辑结构应充分考虑的两个因素。

一、 充分利用“可直接使用”的信息。
首先，我们这里所讲的“信息”，指的是元素与元素之间的关系。
对于待处理的信息，大致可分为“可直接使用”和“不可直接使用”两类。对于“可直接使用”的信息，我们使用时十分方便，只需直接拿来就可以了。而对于“不可直接使用”的这一类，我们也可以通过某些间接的方式，使之成为可以使用的信息，但其中转化的过程显然是比较浪费时间的。
由此可见，我们所需要的是尽量多的“可直接使用”的信息。这样的信息越多，算法的效率就会越高。
对于不同的逻辑结构，其包含的信息是不同的，算法对信息的利用也会出现不同的复杂程度。因此，要使算法能够充分利用“可直接使用”的信息，而避免算法在信息由“不可直接使用”向“可直接使用”的转化过程中浪费过多的时间，我们必然需要采用一种合理的逻辑结构，使其包含更多“可直接使用”的信息。
〖问题一〗 IOI99的《隐藏的码字》。
〖问题描述〗
问题中给出了一些码字和一个文本，要求编程找出文本中包含这些码字的所有项目，并将找出的项目组成一个最优的“答案”，使得答案中各项目所包含的码字长度总和最大。每一个项目包括一个码字，以及该码字在文本中的一个覆盖序列（如’abcadc’就是码字’abac’的一个覆盖序列），并且覆盖序列的长度不超过1000。同时，“答案”要求其中每个项目的覆盖序列互相没有重叠。
〖问题分析〗
对于此题，一种较容易得出的基本算法是：对覆盖序列在文本中的终止位置进行循环，再判断包含了哪些码字，找出所有项目，并最后使用动态规划的方法将项目组成最优的“答案”。
算法的其它方面我们暂且不做考虑，而先对问题所采用的逻辑结构进行选择。
如果我们采用线性的逻辑结构（如循环队列），那么我们在判断是否包含某个码字t时，所用的方法为：初始时用指针p指向终止位置，接着通过p的不断前移，依次找出码字t从尾到头的各个字母。例如码字为“ABDCAB”，而文本图1-1，终止位置为最右边的箭头符号，每个箭头代表依次找到的码字的各个字母。
指针p的移动方向
A B D C A B

C D A C B D C A D C D B A D C C B A D

图1-1

由于题目规定码字的覆盖序列长度不超过1000，所以进行这样的一次是否包含的判断，其复杂度为O(1000)。
由于码字t中相邻两字母在文本中的位置，并非只有相邻(如图1-1中的’D’和’C’)这一种关系，中间还可能间隔了许多的字母(如图1-1中’C’和’A’就间隔了2个字母)，而线性结构中拥有的信息，仅仅只存在于相邻的两元素之间。通过这样简单的信息来寻找码字的某一个字母，其效率显然不高。
如果我们建立一个有向图，其中顶点i(即文本的第i位)用52条弧分别连接’a’..’z’,’A’..’Z’这52个字母在i位以前最后出现的位置（如图1-2的连接方式），我们要寻找码字中某个字母的前一个字母，就可以直接利用已连接的边，而不需用枚举的方法。我们也可以把问题看为：从有向图的一个顶点出发，寻找一条长度为length(t)-1的路径，并且路径中经过的顶点，按照码字t中的字母有序。

C D A C B D C A D C D B A D C C B A D

图1-2
通过计算，用图进行记录在空间上完全可以承受(记录1000个点×52条弧×4字节的长整型=200k左右)。在时间上，由于可以充分利用第i位和第i+1位弧的连接方式变化不大这一点(如图1-2所示，第i位和第i+1位只有一条弧的指向发生了变化，即第i+1位将其中一条弧指向了第i位)，所以要对图中的弧进行记录，只需对弧的指向进行整体赋值，并改变其中的某一条弧即可。
因此，我们通过采用图的逻辑结构，使得寻找字母的效率大大提高，其判断的复杂度为O(length(t))，最坏为O(100)，比原来方法的判断效率提高了10倍。
（附程序codes.pas）

对于这个例子，虽然用线性的数据结构也可以解决，但由于判断的特殊性，每次需要的信息并不能从相邻的元素中找到，而线性结构中只有相邻元素之间存在关系的这一点，就成为了一个很明显的缺点。因此，问题一线性结构中的信息，就属于“不可直接使用”的信息。相对而言，图的结构就正好满足了我们的需要，将所有可能产生关系的点都用弧连接起来，使我们可以利用弧的关系，高效地进行判断寻找的过程。虽然图的结构更加复杂，但却将“不可直接使用”的信息，转化成为了“可直接使用”的信息，算法效率的提高，自然在情理之中。。
二、 不记录“无用”信息。
从问题一中我们看到，由于图结构的信息量大，所以其中的信息基本上都是“可用”的。但是，这并不表示我们就一定要使用图的结构。在某些情况下，图结构中的“可用”信息，是有些多余的。
信息都“可用”自然是好事，但倘若其中“无用”（不需要）的信息太多，就只会增加我们思考分析和处理问题时的复杂程度，反而不利于我们解决问题了。
〖问题二〗 湖南省1997年组队赛的《乘船问题》
〖问题描述〗
有N个人需要乘船，而每船最多只能载两人，且必须同名或同姓。求最少需要多少条船。
〖问题分析〗
看到这道题，很多人都会想到图的数据结构：将N个人看作无向图的N个点，凡同名或同姓的人之间都连上边。
要满足用船最少的条件，就是需要尽量多的两人共乘一条船，表现在图中就是要用最少的边完成对所有顶点的覆盖。这就正好对应了图论的典型问题：求最小边的覆盖。所用的算法为“求任意图最大匹配”的算法。
使用“求任意图最大匹配”的算法比较复杂(要用到扩展交错树，对花的收缩等等)，效率也不是很高。因此，我们必须寻找一个更简单高效的方法。
首先，由于图中任两个连通分量都是相对独立的，也就是说任一条匹配边的两顶点，都只属于同一个连通分量。因此，我们可以对每个连通分量分别进行处理，而不会影响最终的结果。
同时，我们还可以对需要船只s的下限进行估计：
对于一个包含Pi个顶点的连通分量，其最小覆盖边数显然为[Pi/2]。若图中共有L个连通分量，则s=∑[Pi/2](1<=i<=L)。
然后，我们通过多次尝试，可得出一个猜想：
实际需要的覆盖边数完全等于我们求出的下限∑[Pi/2](1<=i<=L)。
要用图的结构对上述猜想进行证明，可参照以下两步进行：
1． 连通分量中若不存在度为1的点，就必然存在回路。
2． 从图中删去度为1的点及其相邻的点，或删去回路中的任何一边，连通分量依然连通，即连通分量必然存在非桥边。
由于图的方法不是这里的重点，所以具体证明不做详述。而由采用图的数据结构得出的算法为：每次输出一条非桥的边，并从图中将边的两顶点删去。此算法的时间复杂度为O(n3)。（寻找一条非桥边的复杂度为O(n2)，寻找覆盖边操作的复杂度为O(n)）
由于受到图结构的限制，时间复杂度已经无法降低，所以如果我们要继续对算法进行优化，只有考虑使用另一种逻辑结构。这里，我想到了使用二叉树的结构，具体说就是将图中的连通分量都转化为二叉树，用二叉树来解决问题。
首先，我们以连通分量中任一个顶点作为树根，然后我们来确定建树的方法。
1． 找出与根结点i同姓的点j（j不在二叉树中）作为i的左儿子，再以j为树根建立子树。
2． 找出与根结点i同名的点k（k不在二叉树中）作为i的右儿子，再以k为树根建立子树。
如图2-1-1中的连通分量，我们通过上面的建树方法，可以使其成为图2-1-2中的二叉树的结构(以结点1为根)。（两点间用实线表示同姓，虚线表示同名）

图2-1-2

图2-1-1
接着，我就来证明这棵树一定包含了连通分量中的所有顶点。
【引理2.1】
若二叉树T中包含了某个结点p，那么连通分量中所有与p同姓的点一定都在T中。
证明：
为了论证的方便，我们约定：s表示与p同姓的顶点集合；lc[p,0]表示结点p，lc[p,i](i>0)表示lc[p,i-1]的左儿子，显然lc[p,i]与p是同姓的。
假设存在某个点q，满足qs且qT。由于s是有限集合，因而必然存在某个lc[p,k]无左儿子。则我们可以令lc[p,k+1]=q，所以qT，与假设qT相矛盾。
所以假设不成立，原命题得证。

由引理2.1的证明方法，我们同理可证引理2.2。
【引理2.2】
若二叉树T中包含了某个结点p，那么连通分量中所有与p同名的点一定都在T中。

有了上面的两个引理，我们就不难得出下面的定理了。
【定理一】
以连通分量中的任一点p作为根结点的二叉树，必然能够包含连通分量中的所有顶点。
证明：
由引理2.1和引理2.2，所有与p同姓或同名的点都一定在二叉树中，即连通分量中所有与p有边相连的点都在二叉树中。由连通分量中任两点间都存在路径的特性，该连通分量中的所有点都在二叉树中。

在证明二叉树中包含了连通分量的所有顶点后，我们接着就需要证明我们的猜想，也就是下面的定理：
【定理二】包含m个结点的二叉树Tm，只需要船的数量为boat[m]=[m/2](mN)。
证明：
(i) 当m=1,m=2,m=3时命题显然成立。

图2-2-1

图2-2-2

图2-2-3
(ii) 假设当m<k(k>3)时命题成立，那么当m=k时，我们首先从树中找到一个层次最深的结点，并假设这个结点的父亲为p。那么，此时有且只有以下三种情况（结点中带有阴影的是p结点）：
(1) 如图2-2-1，p只有一个儿子。此时删去p和p唯一的儿子，Tk就成为了Tk-2，则boat[k]=boat[k-2]+1=[(k-2)/2]+1=[k/2]。
(2) 如图2-2-2，p有两个儿子，并且p是其父亲的左儿子。此时可删去p和p的右儿子，并可将p的左儿子放到p的位置上。同样地，Tk成为了Tk-2，boat[k]=boat[k-2]+1=[k/2]。
(3) 如图2-2-3，p有两个儿子，并且p是其父亲的右儿子。此时可删去p和p的左儿子，并可将p的右儿子放到p的位置上。情况与(2)十分相似，易得此时得boat[k]=boat[k-2]+1=[k/2]。
综合(1)、(2)、(3)，当m=k时，boat[k]=[k/2]。
最后，综合(i)、(ii)，对于一切mN，boat[m]=[m/2]。

由上述证明，我们将问题中数据的图结构转化为树结构后，可以得出求一棵二叉树的乘船方案的算法：
proc try(father:integer;var root:integer;var rest:byte);
{输出root为树根的子树的乘船方案，father=0表示root是其父亲的左儿子，
father=1表示root是其父亲的右儿子，rest表示输出子树的乘船方案后，
是否还剩下一个根结点未乘船}
begin
visit[root]:=true; {标记root已访问}
找到一个与root同姓且未访问的结点j;
if j<>n+1 then try(0,j,lrest);
找到一个与root同姓且未访问的结点k;
if k<>n+1 then try(1,k,rrest);
if (lrest=1) xor (rrest=1) then begin {判断root是否只有一个儿子，情况一}
if lrest=1 then print(lrest,root) else print(rrest,root);
rest:=0;
end
else if (lrest=1) and (rrest=1) then begin {判断root是否有两个儿子}
if father=0 then begin
print(rrest,root);root:=j; {情况二}
end
else begin
print(lrest,root);root:=k; {情况三}
end;
rest:=1;
end
else rest:=1;
end;

这只是输出一棵二叉树的乘船方案的算法，要输出所有人的乘船方案，我们还需再加一层循环，用于寻找各棵二叉树的根结点，但由于每个点都只会访问一次，寻找其左右儿子各需进行一次循环，所以算法的时间复杂度为O(n2)。（附程序boat.pas）

最后，我们对两种结构得出不同时间复杂度算法的原因进行分析。其中最关键的一点就是因为二叉树虽然结构相对较简单，但已经包含了几乎全部都“有用”的信息。由我们寻找乘船方案的算法可知，二叉树中的所有边不仅都发挥了作用，而且没有重复的使用，可见信息的利用率也是相当之高的。
既然采用树结构已经足够，图结构中的一些信息就显然就成为了“无用”的信息。这些多余的“无用”信息，使我们在分析问题时难于发现规律，也很难找到高效的算法进行解决。这正如迷宫中的墙一样，越多越难走。“无用”的信息，只会干扰问题的规律性，使我们更难找出解决问题的方法。

小结
我们对数据的逻辑结构进行选择，是构造数学模型一大关键，而算法又是用来解决数学模型的。要使算法效率高，首先必须选好数据的逻辑结构。上面已经提出了选择逻辑结构的两个条件（思考方向），总之目的是提高信息的利用效果。利用“可直接使用”的信息，由于中间不需其它操作，利用的效率自然很高；不不记录“无用”的信息，就会使我们更加专心地研究分析“有用”的信息，对信息的使用也必然会更加优化。
总之，在解决问题的过程中，选择合理的逻辑结构是相当重要的环
三、 选择合理的存储结构
数据的存储结构，分为顺序存储结构和链式存储结构。顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；链式存储结构则是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。
因为两种存储结构的不同，导致这两种存储结构在具体使用时也分别存在着优点和缺点。
这里有一个较简单的例子：我们需要记录一个n×n的矩阵，矩阵中包含的非0元素为m个。
此时，我们若采用顺序存储结构，就会使用一个n×n的二维数组，将所有数据元素全部记录下来；若采用链式存储结构，则需要使用一个包含m个结点的链表，记录所有非0的m个数据元素。由这样两种不同的记录方式，我们可以通过对数据的不同操作来分析它们的优点和缺点。
1． 随机访问矩阵中任意元素。由于顺序结构在物理位置上是相邻的，所以可以很容易地获得任意元素的存储地址，其复杂度为O(1)；对于链式结构，由于不具备物理位置相邻的特点，所以首先必须对整个链表进行一次遍历，寻找需进行访问的元素的存储地址，其复杂度为O(m)。此时使用顺序结构显然效率更高。
2． 对所有数据进行遍历。两种存储结构对于这种操作的复杂度是显而易见的，顺序结构的复杂度为O(n2)，链式结构为O(m)。由于在一般情况下m要远小于n2，所以此时链式结构的效率要高上许多。
除上述两种操作外，对于其它的操作，这两种结构都不存在很明显的优点和缺点，如对链表进行删除或插入操作，在顺序结构中可表示为改变相应位置的数据元素。
既然两种存储结构对于不同的操作，其效率存在较大的差异，那么我们在确定存储结构时，必须仔细分析算法中操作的需要，合理地选择一种能够“扬长避短”的存储结构。

一、合理采用顺序存储结构。
我们在平常做题时，大多都是使用顺序存储结构对数据进行存储。究其原因，一方面是出于顺序结构操作方便的考虑，另一方面是在程序实现的过程中，使用顺序结构相对于链式结构更便于对程序进行调试和查找错误。因此，大多数人习惯上认为，能够使用顺序结构进行存储的问题，最“好”采用顺序存储结构。
其实，这个所谓的“好”只是一个相对的标准，是建立在以下两个前提条件之下的：
1． 链式结构存储的结点与顺序结构存储的结点数目相差不大。这种情况下，由于存储的结点数目比较接近，使用链式结构完全不能体现出记录结点少的优点，并且可能会由于指针操作较慢而降低算法的效率。更有甚者，由于指针自身占用的空间较大，且结点数目较多，因而算法对空间的要求可能根本无法得到满足。
2． 并非算法效率的瓶颈所在。由于不是算法最费时间的地方，这里是否进行改进，显然是不会对整个算法构成太大影响的，若使用链式结构反而会显得操作过于繁琐。

二、必要时采用链式存储结构。
上面我对使用顺序存储结构的条件进行了分析，最后就只剩下何时应该采用链式存储结构的问题了。
由于链式结构中指针操作确实较繁琐，并且速度也较慢，调试也不方便，因而大家一般都不太愿意用链式的存储结构。但是，这只是一般的观点，当链式结构确实对算法有很大改进时，我们还是不得不进行考虑的。
〖问题三〗 IOI99的《地下城市》。
〖问题描述〗
已知一个城市的地图，但未给出你的初始位置。你需要通过一系列的移动和探索，以确定初始时所在的位置。题目的限制是：
1． 不能移动到有墙的方格。
2． 只能探索当前所在位置四个方向上的相邻方格。
在这两个限制条件下，要求我们的探索次数（不包括移动）尽可能的少。
〖问题分析〗
由于存储结构要由算法的需要确定，因此我们首先来确定问题的算法。
经过对问题的分析，我们得出解题的基本思想：先假设所有无墙的方格都可能是初始位置，再通过探索一步步地缩小初始位置的范围，最终得到真正的初始位置。同时，为提高算法效率，我们还用到了分治的思想，使我们每一次探索都尽量多的缩小初始位置的范围(使程序尽量减少对运气的依赖)。
接着，我们来确定此题的存储结构。
由于这道题的地图是一个二维的矩阵，所以一般来讲，采用顺序存储结构理所当然。但是，顺序存储结构在这道题中暴露了很大的缺点。我们所进行的最多的操作，一是对初始位置的范围进行筛选，二是判断要选择哪个位置进行探索。而这两种操作，所需要用到的数据，只是庞大地图中很少的一部分。如果采用顺序存储结构(如图3-1中阴影部分表示已标记)，无论你需要用到多少数据，始终都要完全的遍历整个地图。

4
3
2
1
1 2 3 4
图3-1

head

图3-2
然而，如果我们采用的是链式存储结构(如图3-2的链表)，那么我们需要多少数据，就只会遍历多少数据，这样不仅充分发挥了链式存储结构的优点，而且由于不需单独对某一个数据进行提取，每次都是对所有数据进行判断，从而避免了链式结构的最大缺点。
我们使用链式存储结构，虽然没有降低问题的时间复杂度(链式存储结构在最坏情况下的存储量与顺序存储结构的存储量几乎相同)，但由于体现了前文所述选择存储结构时扬长避短的原则，因而算法的效率也大为提高。（程序对不同数据的运行时间见表3-3）
测试数据编号 使用顺序存储结构的程序 使用链式存储结构的程序
1 0.06s 0.02s
2 1.73s 0.07s
3 1.14s 0.06s
4 3.86s 0.14s
5 32.84s 0.21s
6 141.16s 0.23s
7 0.91s 0.12s
8 6.92s 0.29s
9 6.10s 0.23s
10 17.41s 0.20s

表3-3
（附使用链式存储结构的程序under.pas）
我们选择链式的存储结构，虽然操作上可能稍复杂一些，但由于改进了算法的瓶颈，算法的效率自然也今非昔比。由此可见，必要时选择链式结构这一方法，其效果是不容忽视的。
小结
合理选择逻辑结构，由于牵涉建立数学模型的问题，可能大家都会比较注意。但是对存储结构的选择，由于不会对算法复杂度构成影响，所以比较容易忽视。那么，这种不能降低算法复杂度的方法是否需要重视呢？
大家都知道，剪枝作为一种常用的优化算法的方法，被广泛地使用，但剪枝同样是无法改变算法的复杂度的。因此，作用与剪枝相似的存储结构的合理选择，也是同样很值得重视的。
总之，我们在设计算法的过程中，必须充分考虑存储结构所带来的不同影响，选择最合理的存储结构。

四、 多种数据结构相结合

上文所探讨的，都是如何对数据结构进行选择，其中包含了逻辑结构的选择和存储结构的选择，是一种具有较大普遍性的算法优化方法。对于多数的问题，我们都可以通过选择一种合理的逻辑结构和存储结构以达到优化算法的目的。
但是，有些问题却往往不如人愿，要对这类问题的数据结构进行选择，常常会顾此失彼，有时甚至根本就不存在某一种合适的数据结构。此时，我们是无法选择出某一种合适的数据结构的，以上的方法就有些不太适用了。
为解决数据结构难以选择的问题，我们可以采用将多种数据结构进行结合的方法。通过多种数据结构相结合，达到取长补短的作用，使不同的数据结构在算法中发挥出各自的优势。
这只是我们将多种数据结构进行结合的总思想，具体如何进行结合，我们可以先看下面的例子。
我们可以采用映射的方法，将线性结构中的元素与堆中间的结点一一对应起来，若线性的数组中的元素发生变化，堆中相应的结点也接着变化，堆中的结点发生变化，数组中相应的元素也跟着变化。
将两种结构进行结合后，无论是第一步还是第二步，我们都不需对所有元素进行遍历，只需进行常数次复杂度为O(log2n)的堆化操作。这样，整个时间复杂度就成为了O(nlog2n)，算法效率无疑得到了很大提高。

五、 总结
我们平常使用数据结构，往往只将其作为建立模型和算法实现的工具，而没有考虑这种工具对程序效率所产生的影响。信息学问题随着难度的不断增大，对算法时空效率的要求也越来越高，而算法的时空效率，在很大程度上都受到了数据结构的制约。

❼ 算法的时间和空间的概念

1.空间复杂度:
比如java中int是4个字节,long是8个字节,你可以用long表示一个数字,long a=100,同样可以用int b=100;这样我们用int肯定比long要节省空间,再者就是同样让许多人编写一个C程序,其中用的变量的个数可能大不一样,变量越多可能你的程序越容易让别人看懂,但变量越少,程序可能看懂的人不多,不过现在都不再强调这复杂度,1G的内存多的是了,几个字节也不算什么了,不过在硬件驱动开发的时候比较讲究这个
2.时间复杂度:
这是一个相对的概念,比如我用p2的电脑和p4的同样运行一个程序,你说哪个快?只能在一定的硬件环境下谈时间复杂度
;所以程序步的方式来说时间复杂度比较方便
打个比方:
for(int i=0;i<100;i++)
{
sum=sum+i;
}
sum=sum+i;这条语句执行了100次,就说这条语句的程序步是
100;像注释,声明语句的程序步都为0;