依据统计方法对算法进行估算。m = f(n)，m是语句总的执行次数， n是输入的规模。
和问题输入规模相关，独立于程序设计语言和计算机软硬件
03/10/2020
12
算法时间复杂度
在进行算法分析时，语句的总执行次数 T(n)是关于问题规 模 n 的函数，进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。
（3）可行性：算法中描述的每一步操作都可以通过已有的 基本操作执行有限次实现。
（4）输入：一个算法应该有零个或多个输入。 （5）输出：一个算法应该有一个或多个输出。这里所说的
输出是指与输入有某种特定关系的量。
算法设计的要求
❖ 正确性（四个境界）
没有语法错误 对于合法的输入数据能够产生满足要求的输出 对于非法的输入数据能够得出满足规格说明的结果 对于任何测试数据都有满足要求的输出结果
基本概念和术语
【数据结构】相互之间存在一种或多种特定关系的数据 元素的集合
【数据】是对信息的一种符号表示。是可以输入计算机中， 能被计算机识别处理和输出的一切符号集合。
【数据元素】是数据的基本单位，在计算机中通常作为一个 整体进行考虑和处理。也称为记录。
【数据项】一个数据元素可由若干个数据项组成。是数据不 可分割的最小单位。
（3）索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引 表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼 有静态和动态特性。
【数据对象】是性质相同的数据元素的集合。是数据的一个 子集。
03/10/2020
4
计算机如何解决问题
问题
机外表示 处理要求
数学模型
建模 逻辑结构 基本运算
实现
求精 存储结构 编程实现
研究数据结构是为了帮计算机解决问题！
03/10/2020
5
数据结构的研究内容
【数据结构的三个方面研究内容】具体来说，数据结构包 含三个方面的内容，即数据的逻辑结构，数据的存储结构 和对数据所施加的运算（操作）。
❖ 可读性：便于阅读、理解和交流 ❖ 健壮性：不合法数据也能合理处理 ❖ 时间效率高和存储量低
03/10/2020
11
算法效率的度量方法
❖ 事后统计方法
通过设计好的测试程序和数据，利用计算机测量其运行时间。 缺陷：需要先编写程序；和计算机软硬件相关；和测试数据相关。
❖ 事前分析估算方法（我们的选择）
算法 != 程序
算法是供人阅读的，程序是让机器执行的 算法用计算机语言实现时就是程序 程序不具有算法的有穷性
算法的概念
❖ 算法是解决某个特定问题的求解步骤的描述。 ❖ 算法在计算机中表现为指令的有限序列，每条指令表示一
个或多个操作。 ❖ 计算机对数据的操作可以分为数值性和非数值性两种类型。
在数值性操作中主要进行的是算术运算；而在非数值性操 作中主要进行的是检索、排序、插入、删除等等。 ❖ 程序不等于算法：计算机程序是算法的具体实现。
03/10/2020
9
算法的性质
（1）有穷性：一个算法必须在执行有穷步之后结束。
（2）确定性：算法中的每一步，必须有确切的含义，在他 人理解时不会产生二义性。
03/10/2020
13
大O阶的数学定义
当n→∞时，有f(n)/g(n)=常数≠0，则称函数f(n) 与g(n)同阶,或者说，f(n)与g(n)同一个数量级，记作
f(n)=O(g(n))
称上式为算法的时间复杂度,或称该算法的时间复杂 度为O(g(n)) 。其中, n为问题的规模(大小)的量度。
若lim(f(n)/g(n)) =lim((2n3 + 3n2 + 2n + 1)/n3) =2
【例1】数据元素之间的关系在计算机中有几种表示方法？各有 什么特点？
答：四种表示方法
（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映 数据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。
（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指 针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操 作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。
【线性结构】—— 1对1的 关系比如线性表、栈、队列 。
【树形结构】—— 1对多的 关系比如树。
【图形结构】—— 多对多的 关系比如图。
03/10/2020
7
算法与数据结构
算法与数据结构关系密切
选择的数据结构是否恰当直接影响算法的效率； 而数据结构的优劣由算法的执行来体现。
“算法 + 数据结构 = 程序”
n→∞
n→∞
则算法的时间复杂度为O(n3)
算法空间复杂度
算法的空间复杂度通过计算算法所需的存储空间实现， 算法空间复杂度的计算公式记作：S(n) = O(f(n))， 其中， n 为问题的规模，f(n)为语句关于 n 所占存 储空间的函数。
我们主要讨论时间复杂度问题。
03/10/2020
15
例题解析
算法的时间复杂度，也就是算法的时间量度，用“大O记法 ”记作：T(n)=O(f(n))。由此得到的 T(n) 的数量级叫“ 大O阶”。它表示随问题规模 n 的增大，算法执行时间增长 率和 f(n)的增长率相同，称作算法的渐进时间复杂度，简 称时间复杂度。其中 f(n) 是问题规模 n 的某个函数。
一般情况下，T(n)增长越慢，算法越优。
数据结构 与 算法
复习与习题解析(第1-5讲）
第一讲 绪论
了解数据结构有关概念的含义，特别 是数据的逻辑结构和存储结构之间的 关系；（重点）
熟悉类C语言的书写规范；
了解计算算法时间复杂度的方法。
（难点）
03/10/2020
2
数据结构的定义
按某种逻辑关系组织起来的一批数据（或 称带结构的数据元素的集合）应用计算机 语言并按一定的存储表示方式把它们存储 在计算机的存储器中，并在其上定义了一 个运算的集合。
数据的逻辑结构
（面向人类）
数据的存储结构
（面向计算机）
线性结构
非线性结构 顺序存储 链式存储
树形结构
图形结构
数据的运算（操作）：检索、排序、插入、删除、修改等
03/10/2020
6
四种基本逻辑结构
【集合】—— 数据元素间 除了“同属于一个集合”外 ，无其他关系。