发布时间 : 星期六 文章大学计算机应用基础实用教程[09]第7章 软件技术基础更新完毕开始阅读
按数量级递增排列，常见的时间复杂度有：
常数阶O(1),对数阶O(log2n)(以2为底n的对数，下同),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...，
k次方阶O(nk),。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
在同一个问题规模下，如果算法执行所需的基本操作次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量.
1) 平均时间复杂度
是指用各种特定输入下的基本操作次数的加权平均值来度量算法的工作量。 2) 最坏情况下的时间复杂度
是指在规模为n时算法所执行的基本操作的最大次数。
一般情况下，讨论时间复杂度如不特别声明，就是指最坏情况下的时间复杂度。
2. 空间复杂度
一个算法的空间复杂度是指执行这个算法所需要的内存空间。与时间复杂度类似，空间复杂度S(n)是指算法在计算机内执行时所需存储空间的度量。一般以数量级形式给出，记作
S(n)=O(f(n))
其中n为问题的规模。
一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分。如果所占空间量依赖于特定的输入，则除特别声明外，均按最坏情况来分析。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术。
7.2 数据结构
计算机在进行数据处理时，实际需要处理的数据元素往往有很多，这些数据都需要存放在计算机中。因此在计算机中如何组织这些数据以便提高数据处理的效率，是进行数据处理的关键问题。
第9页共35页
7.2.1 逻辑结构和存储结构
1. 数据结构的基本概念
数据结构指相互有关联的数据元素的集合,主要研究三个方面内容：
? 数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；
? 在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储
结构； ? 对各种数据结构进行的运算。 其中，涉及到以下几个基本概念：
（1） 数据（Data）：数据时对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。例如数值、字符、声音、图像等。
（2） 数据元素（Data Element）：数据元素是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。每个数据元素中可包含一个或若干个数据项。数据项是具有独立意义的标识单位，是数据的不可分割的最小单位。
（3） 数据对象（Data Object）：数据对象是性质相同的数据元素的集合，是数据的一个子集。
（4） 数据结构（Data Structure）：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括数据的逻辑结构和数据的物理结构（也称为存储结构）。 2. 逻辑结构
数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了数据元素之间的前后件关系，通常记为 R。一个数据结构可以形式化定义为一个二元组
B=(D,R)
其中，B 表示数据结构。为了反映 D 中各数据元素之间的前后件关系，一般用二元组来表示。
例如，如果把一年四季看作一个数据结构，则可表示成：B =(D,R) D ={春季,夏季,秋季,冬季}
第10页共35页
R ={(春季,夏季),(夏季,秋季),(秋季,冬季)} 3. 存储结构
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。
由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此， 为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。
一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接等存储结构。
顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。
链式存储结构就是在每个结点中至少包含一个指针域，用指针来体现数据元素之间逻辑上的联系。
7.2.2 线性结构和非线性结构
根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。
（1）如果一个非空的数据结构满足下列两个条件： ① 有且只有一个根结点；
② 每一个结点最多有一个前件，也最多有一个后件。 则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。栈、队列、串等都为线性结构。 如果一个数据结构不是线性结构，则称之为非线性结构。数组、广义表、树和图等数据结构都是非线性结构。
（2）线性表的顺序存储结构具有以下两个基本特点： ① 线性表中所有元素所占的存储空间是连续的；
② 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
元素 ai 的存储地址为：ADR(ai)=ADR(a1)+(i-1)k，ADR(a1)为第一个元素的地址，k 代表每个元素占的字节数。
（3）顺序表的运算有查找、插入、删除 3 种。
第11页共35页
7.2.3 栈
1. 栈的基本概念
栈（stack）是一种特殊的线性表，是限定只在一端进行插入与删除的线性表。在栈中，一端是封闭的，既不允许进行插入元素，也不允许删除元素；另一端是开口的，允许插入和删除元素。通常称插入、删除的这一端为栈顶，另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是最后被插入的元素，从而也 是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删 除的元素。
栈是按照“先进后出”或“后进先出”的原则组织数据的。例如，枪械的子 弹匣就可以用来形象的表示栈结构。子弹匣的一端是完全封闭的，最后被压入弹 匣的子弹总是最先被弹出，而最先被压入的子弹最后才能被弹出。 2. 栈的顺序存储及其运算
栈的基本运算有 3 种：入栈、退栈与读栈顶元素。 ① 入栈运算：在栈顶位置插入一个新元素； ② 退栈运算：取出栈顶元素并赋给一个指定的变量； ③ 读栈顶元素：将栈顶元素赋给一个指定的变量。
第12页共35页