【考研数据结构知识点详解及整理——C语言描述】第一章算法和算法评价

25计算机考研，数据结构知识点整理（内容借鉴了王道408＋数据结构教材），还会不断完善所整理的内容，后续的内容也会不断更新（可以关注），若有错误和不足欢迎各位朋友指出!

一.算法的基本概念

1.算法定义

2.算法的特性

3.算法设计的要求

二.算法性能评价

1.性能评价

2.算法的时间性能分析

2.1时间复杂度

3.算法的空间性能分析

3.1空间复杂度

一.算法的基本概念

1.算法定义

算法(Algorithm)是对特定问题求解步驶骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。

2.算法的特性

此外，一个算法还具具有下列五个重要特性:

1)有穷性。一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
2)确定性。算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出，无二义性。
3)可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
4)输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
4)输出。一个算法有零个或多个输出，这些输出是与输入有着某种特定关系的量

最基本的是有限性、确定性和可行性这三个特性。

3.算法设计的要求

通常，设计一个“好”的算法应考虑达到以下目标:

1)正确性。算法应能够正确地解决求解问题。
2)可读性。算法应具有良好的可读性，从帮助人们理解，
3)健壮性。算法能对输入的非法数据做H反应或处理，而不会产生莫名其妙的输出。
4)高效率与低存储量需求。效率是指算法执行的时间，存储量需求是指算法执行过程中所需要的最大存储空间，这两者都与问更的规模有关。

二.算法性能评价

1.性能评价

算法性能度量主要是从时间复杂度和空间复杂度描述。

2.算法的时间性能分析

2.1时间复杂度

（1）一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n)，它是该算法问题规模n的函数，时间复杂度主要分析 T(n)的数量级。算法中基本运算(最深层循环中的语句)的频度与T(n)同数量级，因此通常将算法中基本运算的执行次数的数量级作为该算法的时间复杂度。于是，算法的时间复杂度记为T(n)= O(f(n))
式中，0的含义是 T(n)的数量级，其严格的数学定义是：若(n)和n)是定义在正整数集合上的两个函数，则存在正常数C和 n0，使得当 n≥n0时，都满足 0≤ T(n)< Cf(n)。

（2）算法的时间复杂度不仅依赖于问题的规模n，也取决于待输入数据的性质(如输入数据元素的初始状态)。例如，在数组A[0...n-1]中，查找给定值k的算法大致如下:

(1)i=n-1;
(2)while(i>=0&&(A[i]!=k))
(3) i--;
(4)return i;

该算法中语句3(基本运算)的频度不仅与问题规模n有关，而且与下列因素有关:

① 若A中没有与k相等的元素，则语句3的频度f(n)=n。

②若A的最后一个元素等于k，则语句3的频度f(n)是常数 0。

最坏时间复杂度是指在最坏情况下，算法的时间复杂度。
平均时间复杂度是指所有可能输入实例在等概率出现的情况下，算法的期望运行时间。
最好时间复杂度是指在最好情况下，算法的时间复杂度。

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长在分析一个程序的时间复杂性时，有以下两条规则:

1)加法规则:T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

2)乘法规则:T(n)=T1(n)xT2(n)=O(f(n))xO(g(n))=O(f(n)xg(n))

例如，设 a{}、b{}、c{}三个语句块的时间复杂度分别为 O(1)、0(n)、O(n)，则

① a{b{ }c{ }}       //时间复杂度为O(n方),满足加法规则② a{b{c{ }}}       //时间复杂度为O(n的3次方)，满足乘法规则

渐近时间复杂度为
O(1)< O( $log_{2}n$ )< O(n)< O( $nlog_{2}n$ )<O( $n^{2}$ )< О( $n^{3}$ )< О( $2^{n}$ ) < O(n!)< O( $n^{n}$ )

3.算法的空间性能分析

3.1空间复杂度

（1）算法的空间复杂度S(n)定义为该算法所需的存储空间，它是问题规模n的函数S(n)=O(g(n))
（2）一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需一个程序在执行时除需要存储空间来存放为实现计算所需信息的辅助空间。若输入数据所占要一些对数据进行操作的工作单元和存储一些分析除输入和程序之外的额外空间。例如，若算法空间只取决于问题本身，和算法无关，则只需中新建了几个与输入数据规模n相同的辅助组，则空间复杂度为 O(n)。算法原地工作是指算法所需的辅助空间为常量，即 O(1)。