第一讲:数据结构概论
主讲人:刘财政
B站:@计算机考研刘财政考纲要求CON T EN T S
目录
考点一 基本概念
考点二 逻辑结构 ★
考点三 物理结构 ★
考点四 算法的概念和评价
考点五 时间复杂度 ★ ★ ★
考点六 空间复杂度 ★ ★考纲要求CON T EN T S
目录
考点一 基本概念
考点二 逻辑结构 ★
考点三 物理结构 ★
考点四 算法的概念和评价
考点五 时间复杂度 ★ ★ ★
考点六 空间复杂度 ★ ★考点一:基本概念
什么是数据结构呢?
数据结构
数据 结构
什么是数据?什么是数据元素?
数据元素
关系
什么是结构?关系指的是什么?考点一:基本概念
数据:所有能输入到计算机中并能被程序识别和处理的符号集合
数值数据:整数、实数等
数据
非数值数据:图形、图象、声音、文字等考点一:基本概念
数据元素:数据的基本单位,在程序中作为一个整体进行考虑和处理
数据项
数据项:构成数据元素的最小单位
数据元素
通常情况下,数据元素具有相同个数和类型的数据项
数据元素(data element)是数据的基本单位,在计算机程序中通常
作为一个整体考虑和处理。一个数据元素可由若干个数据项(data
item)组成,数据项是数据不可分割的最小单位。考点一:基本概念
数据结构
数据结构 = 数据对象 + 结构
数据 结构
相同性质的数 数据元素之间的
据元素的集合 关系构成结构
数据元素 关系
数据结构(data structure)即数据的组织形式,它是数据元素
之间存在的一种或多种特定关系的数据元素集合。考点一:基本概念
数据结构
数据结构 = 数据对象 + 结构
数据 结构
相同性质的数 数据元素之间的
据元素的集合 关系构成结构
数据元素 关系考点一:基本概念
数据结构:相互之间存在一定关系的数据元素的集合
数据的逻辑结构:数据元素之间逻辑关系的整体
数据的逻辑结构在形式上可定义为一个二元组:
Data_Structure = (D, R)
其中 D 是数据元素的有限集合,R 是 D 上关系的集合
A B Data_Structure = (D, R)
其中D = {A, B, C, D, E, F, G}
R = {R1},R1 = {(A, B), (A, E), (A,
F C
G
F), (B, C), (B, D), (C, D), (D, E), (D,
G), (E, F), (E, G)}
E D考点一:基本概念
数据结构四要素:
◆ 数据元素之间的逻辑关系 数据的逻辑结构
逻辑结构
◆ 数据元素及其关系在计算机存储器中的存储方
存储结构
式 数据的存储结构(或物理结构)
数据运算 ◆ 施加在该数据上的操作 数据运算
数据应用 ◆ 在实际中的应用或者应用场景 数据应用考点一:基本概念
数据类型
int a, b; a = 10000000000000; a = a % b;
float x, y; x = 1234567.123; x = x % y;
数据类型:一组值的集合以及定义于这个值集上的一组操作考点一:基本概念
数据类型
int a, b; a = 10000000000000; a = a % b;
float x, y; x = 1234567.123; x = x % y;
数据结构不同于数据类型,也不同于数据对象,它不仅要描述数据
类型的数据对象,而且要描述数据对象各元素之间的相互关系。
在C语言中数据类型有:基本类型和构造类型。考点一:基本概念
抽象数据类型(Abstract Data Type ,简称ADT)
指的是从求解问题的数学模型中抽象出来的数据逻辑结构和运算
(抽象运算),而不考虑计算机的具体实现。
抽象数据类型 = 逻辑结构 + 抽象运算考点一:基本概念
例如,定义复数抽象数据类型Complex
一个复数的形式:e+ei 或(e,e)
1 2 1 2
ADT Complex {
数据对象:
D={ e e | e e均为实数 }
1, 2 1, 2
数据关系:
R={<e e> | e是复数的实部,e 是复数的虚部
1, 2 1 2
}
基本运算:
AssignComplex(&z,v1,v2):构造复数Z。
运
DestroyComplex(&z):复数z被销毁。
算
功
GetReal(z,&real):返回复数z的实部值。
能
GetImag(z,&Imag):返回复数z的虚部值。 描
述
Add(z1,z2,&sum):返回两个复数z1、z2的和。
} ADT Complex考点一:基本概念
抽象数据类型(Abstract Data Type ,简称ADT)
抽象数据类型不考虑数据项,把具体的数据类型抽象掉了
抽象数据类型只考虑数据结构和基本操作考点一:基本概念
抽象数据类型(Abstract Data Type ,简称ADT)
抽象层 设计层
● 数据模型(逻辑结构) ● 数据表示(存储结构)
● 操作集合 ● 算法
(a)定义——ADT定义
(b)设计——数据结构设计
实现层(C++、Java、…) 实现层(C、…)
● 成员变量 ● 自定义数据类型
类
● 成员函数 ● 自定义函数
(c)实现——程序语言实现考点一:基本概念
抽象数据类型(Abstract Data Type ,简称ADT)
ADT 抽象数据类型名
DataModel
数据元素之间逻辑关系的定义
Operation
操作 1
输入:执行此操作所需要的输入
功能:该操作将完成的功能 操作接口(函数原型)
输出:执行该操作后产生的输出
操作 2
……
操作 n
……
endADT考点一:基本概念
抽象数据类型(Abstract Data Type ,简称ADT)
抽象数据类型:定义功能 ADT
线性结构 树形结构 图状结构
编程实现该数据结构CON T EN T S
目录
考点一 基本概念
考点二 逻辑结构 ★
考点三 物理结构 ★
考点四 算法的概念和评价
考点五 时间复杂度 ★ ★ ★
考点六 空间复杂度 ★ ★考点二:逻辑结构
逻辑结构
数据元素之间的关系可以是元素之间代表某种含义的自然关系,也
可以是为处理问题方便而人为定义的关系
这种人为定义的 “关系”称为数据元素之间的逻辑关系,相应的
结构称为逻辑结构/概念结构。考点二:逻辑结构
逻辑结构
(1)集合:数据元素之间没有关系
(2)线性结构:数据元素之间是一对一的线性关系
(3)树结构:数据元素之间是一对多的层次关系
(4)图结构:数据元素之间是多对多的任意关系考点二:逻辑结构
逻辑结构
(1)集合
元素之间关系:无。
特点:数据元素之间除了“属于同一个集合”的
关系外,别无其他逻辑关系。是最松散的,不受任何
制约的关系。考点二:逻辑结构
逻辑结构
(2)线性结构
元素之间关系:一对一。
特点:开始元素和终端元素都是唯一的,除此之外,其余元素都
有且仅有一个前驱元素和一个后继元素。考点二:逻辑结构
逻辑结构
(3)树形结构
元素之间关系:一对多。
特点:开始元素唯一,终端元素不唯一。
除终端元素以外,每个元素有一个或多个后
继元素;除开始元素外,每个元素有且仅有
一个前驱元素。考点二:逻辑结构
逻辑结构
(4)图形结构
元素之间关系:多对多。
特点:所有元素都可能有多个前驱元素和多个
后继元素。考点二:逻辑结构
逻辑结构
说明:
1、逻辑结构与数据元素本身的形式、内容无关
2、逻辑结构与数据元素的相对位置无关
3、逻辑结构与所含结点个数无关
4、逻辑结构与计算机无关考点二:逻辑结构
逻辑结构
树形结构、图形结构、集合结构统称为非线性结构
数据结构可以可以分为线性结构和非线性结构【政哥题型总结】考点二:逻辑结构
1.逻辑上通常可以将数据结构分为( )。
A.动态结构和静态结构 B.顺序结构和链式结构
C.线性结构和非线性结构 D.初等结构和组合结构考点二:逻辑结构
1.逻辑上通常可以将数据结构分为( )。
A.动态结构和静态结构 B.顺序结构和链式结构
C.线性结构和非线性结构 D.初等结构和组合结构
C 【解析】 按照逻辑结构,可以把数据结构分为集合结构、线性结构、
树形结构和图状结构,在分类上,集合结构、树形结构和图状结构统称
为非线性结构,因此分为线性结构和非线性结构。B选项对应的是两个
主要的存储结构,即顺序结构和链式结构。考点二:逻辑结构
2.下列数据结构中,( )是非线性数据结构。
A.栈 B.队列 C.二叉树 D.线性表考点二:逻辑结构
2.下列数据结构中,( )是非线性数据结构。
A.栈 B.队列 C.二叉树 D.线性表
C 【解析 】 按照逻辑结构,可以把数据结构分为集合结构、线性结
构、树形结构和图状结构,其中线性结构包括线性表、栈、队列、广
义表(广义线性结构)、串等;树形结构包括树、二叉树等;图形结构
包括有向图和无向图、带权图和无权图等。CON T EN T S
目录
考点一 基本概念
考点二 逻辑结构 ★
考点三 物理结构 ★
考点四 算法的概念和评价
考点五 时间复杂度 ★ ★ ★
考点六 空间复杂度 ★ ★考点三:物理结构
数据结构:相互之间存在一定关系的数据元素的集合
数据的存储(物理)结构:数据及其逻辑结构在计算机中的表示
数据元素
内存
逻辑关系
想 法 算 法
计算机语言如何进行内存分配?
数据表示
数据处理
存储结构实质上是内存分配,在具体实现时依赖于计算机语言考点三:物理结构
在存储程序的计算机中,数据和指
令都是以二进制形式存储在存储器
中的。从存储器存储的内容来看两
者并无区别,都是由0和1组成的
二进制序列。考点三:物理结构
数据的存储(物理)结构:数据及其逻辑结构在计算机中的表示
数据元素
内存
逻辑关系
• 数据元素
数据元素
• 也就是各个属性值(数据项)
• 线性结构,集合结构
逻辑结构
• 图型结构,树型结构考点三:物理结构
物理结构有四种基本类型:
① 顺序结构
② 链式结构
③ 索引结构
④ 散列结构考点三:物理结构
(1)顺序存储结构:用一组连续的存储单元
…
依次存储数据元素,数据元素之间的逻辑关系 起始地址
由元素的存储位置表示
red
➢ 在C语言中,通常用一维数组表示顺序存储结构; green
➢ 数据元素存放的地址是连续的;
blue
➢ 随机存取表中元素;
➢ 插入和删除操作需要移动元素;
…
存储结构实质上是内存分配,在具体实现时依赖于计算机语言考点三:物理结构
(2)链接存储结构:用一组任意的存储单元存
…
储数据元素,数据元素之间的逻辑关系用指针
0200
green
来表示
起始地址 0300
0208
➢ 用结构体类型表示链式存储结构; red
0200
➢ 比顺序存储结构的存储密度小;
…
➢ 逻辑上相邻的节点物理上不必相邻;
0300
➢ 插入、删除灵活 (只要改变节点中的指针);
blue
➢ 查找结点时链式存储要比顺序存储慢。
∧
…
➢ 每个结点是由数据域和指针域组成;
存储结构实质上是内存分配,在具体实现时依赖于计算机语言考点三:物理结构
(3)索引结构: 除建立存储结点信息外,还建立附加的索引表来标识结
点的地址。索引表由若干索引项组成。
索引 数据
➢ 索引存储结构是用结点的索引号来确定
1 3.0
结点存储地址;
2 2.3
➢ 优点是检索速度快;
3 3.5
➢ 缺点增加了附加的索引表,会占用较多的
4 5.0
存储空间;
5 -8.5
6 11.0
存储结构实质上是内存分配,在具体实现时依赖于计算机语言考点三:物理结构
(4)散列存储方法:散列存储,又称hash存储,是一种试图将数据元素的
存储位置与关键码之间建立确定对应关系的查找技术。
𝑓
➢ x(数据元素) ՜ y(存储位置)
➢ 散列法存储的基本思想是:由节点的关键码值决定节点的存储地址。
散列技术除了可以用于查找外,还可以用于存储。
存储结构实质上是内存分配,在具体实现时依赖于计算机语言考点三:物理结构
【背诵内容】考点三:物理结构
逻辑结构和存储结构的关系
数据的逻辑结构属于用户视图,是面向问题的
数据的存储结构属于具体的实现视图,是面向计算机的
数据的逻辑结构反映了数据本身的构成方式
数据的存储结构反映了数据在内存的存储表示
问 题 想 法
算 法
程 序
逻辑结构
存储结构
存储结构
抽象模型
数据表示
程序语言
基本思路
数据处理 编程环境【政哥题型总结】考点三:物理结构
1.在设计存储结构时,通常不仅要存储各数据元素的值,还要存储( )。
A.数据的处理方法 B.数据元素的类型
C.数据元素之间的关系 D.数据的存储方法考点三:物理结构
C 【解析】 冯·诺依曼计算机告诉我们,指令和数据都是以二进制的形
式存放在内存中的。因此,在设计时,物理结构必须包括数据元素的
存储和元素之间的关系的表示,并且物理结构必须体现逻辑结构的逻
辑关系是设计的关键。因此,在设计存储结构时,通常不仅要存储各
数据元素的值,还要存储数据元素之间的关系。考点三:物理结构
2.以下与数据的存储结构无关的术语是( )。
A.循环队列 B.链表 C.哈希表 D.栈考点三:物理结构
D【解析】本题比较综合,这里总结一下,大家先记住,逻辑结构包括
线性表、栈、队列、树、二叉树、有向图、无向图、带权图、无权图、
哈夫曼树、完全二叉树和满二叉树。
物理结构包括顺序表、单链表、双链表、静态链表、链栈、顺序栈、
顺序队列、循环队列、链队列、二叉链树、三叉链树、邻接表、邻接
矩阵和哈希表等。CON T EN T S
目录
考点一 基本概念
考点二 逻辑结构 ★
考点三 物理结构 ★
考点四 算法的概念和评价
考点五 时间复杂度 ★ ★ ★
考点六 空间复杂度 ★ ★考纲框架CON T EN T S
目录
考点一 基本概念
考点二 逻辑结构 ★
考点三 物理结构 ★
考点四 算法的概念和评价
考点五 时间复杂度 ★ ★ ★
考点六 空间复杂度 ★ ★考点四:算法的概念和评价
算法(Algorithm):是对特定问题求解方法(步骤)的一种描述,是指
令的有限序列,其中每一条指令表示一个或多个操作。
算法可以有三种表示形式:
➢ 伪代码
➢ 自然语言
➢ 流程图
操作步骤:
1. ………
输 出
输 入
2. ………
3. ………考点四:算法的概念和评价
在一群数中,查找特定值考点四:算法的概念和评价
输入 算法 输出
算法描述的一般格式
返回值 算法对应的函数名(形参列表)
{
函
//临时变量的定义
数
//实现由输入参数到输出参数的操作
体
…
}
⚫ 返回值:通常为bool类型,表示算法是否成功执行。
⚫ 形参列表:由输入型参数和输出型参数构成。
算法输入
算法输出考点四:算法的概念和评价
算法的五个重要的特性
(1) 有穷性:在有穷步之后结束,算法能够停机。
(2) 确定性:无二义性。
(3) 可行性:可通过基本运算有限次执行来实现,
也就是算法中每一个动作能够被机械地执行。
(4) 输入:0个或多个输入
表示存在数据处理
(5) 输出:1个或多个输出考点四:算法的概念和评价
算法和程序的区别
不一定满足有
穷性
◼ 程序是指使用某种计算机语言对一个算法的具体实现,即具体要怎么做。
◼ 算法侧重于对解决问题的方法描述,即要做什么。
一定满足有穷
性
◼ 算法用计算机语言描述 程序考点四:算法的概念和评价
什么是算法分析?
算法设计:面对一个问题,如何设计一个有效的算法
检
指
验
导
评
改
估
进
算法分析:对已设计的算法,如何评价或判断其优劣考点四:算法的概念和评价
CPU时间 时间性能分析
分析算法占用的资源
内存空间 空间性能分析
算法分析目的:分析算法的时空效率以便改进算法性能。考点四:算法的概念和评价
效率指的是算法执行的时间
存储量需求指算法执行过程中所需要的最大存储空间THANKSCON T EN T S
目录
考点一 基本概念
考点二 逻辑结构 ★
考点三 物理结构 ★
考点四 算法的概念和评价
考点五 时间复杂度 ★ ★ ★
考点六 空间复杂度 ★ ★考点五:时间复杂度
算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗
的时间来度量。其方法通常有两种:
事后统计:计算机内部进行执行时间和实际占用空间的统计。
问题:必须先运行依据算法编制的程序;依赖软硬件环境,容易掩
盖算法本身的优劣;没有实际价值。考点五:时间复杂度
算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗
的时间来度量。其方法通常有两种:
事后统计:计算机内部进行执行时间和实际占用空间的统计。
⚫ 编写程序的语言不同
所以不能用绝对执行时
⚫ 执行程序的环境不同
间进行比较。
⚫ 其他因素考点五:时间复杂度
算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗
的时间来度量。其方法通常有两种:
事前分析:求出该算法的一个时间界限函数。
与此相关的因素有:
➢ 依据算法选用何种策略;
➢ 程序设计的语言;
➢ 编译程序所产生的机器代码的质量;
➢ 机器执行指令的速度;
➢ 问题的规模;
➢ 数据的初始状态有关考点五:时间复杂度
一个算法是由控制结构(顺序、分支和循环三种)和原操作构成的。
算法的基本构成:
控制语句1 控制语句2 … 控制语句n
原操作 原操作 原操作
⚫ 顺序结构:按照所述顺序处理 指固有数据类型的
操作,如+、-、*、
⚫ 分支结构:根据判断条件改变执行流程
/、++和--等
⚫ 循环结构:当条件成立时,反复执行给定的处理
操作
◼ 算法执行时间取决于两者的综合效果。考点五:时间复杂度
看一个简单例子
void fun(int a[],int n)
{ int i;
for (i=0;i<n;i++)
a[i]=2*i;
原操作
for (i=0;i<n;i++)
printf("%d", a[i]);
printf("\n");
}考点五:时间复杂度
算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗
的时间来度量。其方法通常有两种:
事前分析:求出该算法的一个时间界限函数。
◼ 求出算法所有原操作的执行次数(也称为频度),它是问题规模n
的函数,用T(n)表示。
◼ 算法执行时间 = 原操作所需的时间×T(n)。所以T(n)与算法的执行
时间成正比。
◼ 用T(n)表示算法的执行时间。考点五:时间复杂度
若T(n) = a nm+ a nm-1 + + an+ a是一个m次多项式,则T(n) = O(nm)
m m-1 1 0
关注增长率——忽略所有低次幂和最高次幂的系数考点五:时间复杂度
算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗
的时间来度量。其方法通常有两种:
事前分析:求出该算法的一个时间界限函数。
◼ 算法中基本操作重复执行的次数是问题规模n的某个函数,其时间
量度记作 T(n)=O(f(n)),称作算法的渐近时间复杂度(Asymptotic
Time complexity),简称时间复杂度。
◼ 一般地,常用最深层循环内的语句中的原操作的执行频度(重复执行
的次数)来表示。【政哥题型总结】考点五:时间复杂度
1、设 n 是描述问题规模的非负整数,下面程序片段的时间复杂度是()
for(i=1; i<=n; ++i) {
i = 1 ①②
++x; ①
i = 2 ①②
s+=x ; ② n次
i = 3 ①②
}
A.O(log n) B.O(n) i = n ①②
2
C.O(nlog n) D.O(n2)
2考点五:时间复杂度
B【解析】本题中最内层循环语句是++x; s+=x ;
执行1次,++x; s+=x ; 共计执行2次;
执行2次,++x; s+=x; 共计执行了4次
依次类推,
假设程序执行了K次,++x; s+=x ;,一共乘了2* K次,于是2* K < n; 得到时间
复杂度是O(n),选择B。考点五:时间复杂度
2、设n是描述问题规模的非负整数,下面程序片段的时间复杂度是()。
int x=n*n;
while(x>=1){
x=x/2;
}
A、O (log n) B、O (n)
2
C、O (nlog n) D、O (n1/2)
2
i = 1 x = x / 2
i = 2 x = x / 2 / 2 = x / 22
i = 3 x = x / 2 / 2 / 2 = x / 23
i = k x= x / 2 / 2… / 2 / 2 = x / 2k>=1
k个2
x初值是n*n,得到 2k<n * n => O(log n)
2考点五:时间复杂度
3、下面算法的时间复杂度为()
int f(unsigned int n) {
if(n==0||n==1) return 1;
else return n* f(n-1);
}
A. O(1) B.O(n) C.O(n2) D.O(n!)
递归:就是在运行的过程中不断地调用自己考点五:时间复杂度
3、下面算法的时间复杂度为()
①
int f(unsigned int n) { ①递归初始条件
②
if(n==0||n==1) return 1; 递归三要素 ②递归终止条件
else return n* f(n-1);
③递归转移条件
③
}
A. O(1) B.O(n) C.O(n2) D.O(n!)
递归:就是在运行的过程中不断地调用自己考点五:时间复杂度
3、下面算法的时间复杂度为()
①
int f(unsigned int n) { ①递归初始条件
if(n==0||n==1) return 1; 递归三要素 ②递归终止条件
else return n* f(n-1);
③递归转移条件
③
}
A. O(1) B.O(n) C.O(n2) D.O(n!)
f(n)
f(n-1) 执行顺序
f(n-2)
调用顺序
…
f(2)
f(1)考点五:时间复杂度
3、下面算法的时间复杂度为()
①
int f(unsigned int n) { ①递归初始条件
if(n==0||n==1) return 1; 递归三要素 ②递归终止条件
else return n* f(n-1);
③递归转移条件
③
}
A. O(1) B.O(n) C.O(n2) D.O(n!)
𝑛=𝑛−1
n 1; 共执行了n次,所以时间复杂度是O(n)考点五:时间复杂度
4、给定下面算法如下,其时间复杂度是( )。
①
int fun(int n) {
①递归初始条件
if (n<=1)② return 1;
递归三要素
②递归终止条件
return 1 + fun(n/2);
③递归转移条件
③
}
A. O(log n) B. O(n) C. O(nlog n) D. O(n2)
2 2
f(n)
f(n/2)
调用顺序
f(n/4)
…
f(2)
f(1)考点五:时间复杂度
4、给定下面算法如下,其时间复杂度是( )。
①
int fun(int n) {
①递归初始条件
if (n<=1)② return 1;
递归三要素
②递归终止条件
return 1 + fun(n/2);
③递归转移条件
③
}
A. O(log n) B. O(n) C. O(nlog n) D. O(n2)
2 2
𝑛=𝑛/2
n 1 共执行了log n次,所以时间复杂度是O(log n)
2 2考点五:时间复杂度
5、设n是描述问题规模的非负整数,下列程序段的时间复杂度是()。
for(i=1; i<=n; ++i){
i = 1 ①
for(j=1; j<=n; ++j) {
++x;
i = 2 ①
s+=x ;
n次
i = 3 ①
}
}
i = n ①
2n
语句频度为:2n2 ,其时间复杂度为:O(n2) ,即为平方阶。考点五:时间复杂度
6、如果do(IT)这个算法的复杂度为n,n为描述问题规模的非负整数(n≥0),下
面程序片段的时间复杂度是( )。
int x=2;
while(i≤n){
do(IT);
x=x*2;
}
A.O(n) B.O (log n) C.O(nlog n) D.O(n2)
2 2考点五:时间复杂度
C【解析】本题中最内层循环语句是x=2*x和do(IT);并且二者的执行频度一样,
我们假设一共执行执行K次,
执行1次,x = x * 2
执行2次,x = x * 2 * 2
依次类推,
执行K次,j= K,x = x * 2 * 2 *…* 2,一共乘了K个2,于是sum = 2K < n; 得
到x=2*x和do(IT)的执行频度是log2n,
do(IT);的时间复杂度是n,根据乘法原理,得到时间复杂度是O(nlog2n) 。考点五:时间复杂度
7、【2022.1】下列程序段的时间复杂度是( )。
int sum=0;
for(int i =1; i <=n; i * =2)
for(int j =0;j<i; j++)
sum++;
A. O(log n) B. O(n) C. O(nlogn) D. O(n2)考点五:时间复杂度
B.【解析】本题为多层循环中嵌套循环指针相关类型题,题目中采用的
是两重循环,外层循环用K表示执行的轮次,且外层循环的循环变量每
次乘以2,则有n = 2K, 所以K = log n;
2
于是,内层循环的执行次数为M,
当M = 1时,内层循环执行1次,
当M = 2时,内层循环执行2次,
当M = 4时,内层循环执行4次,
当M= n时,内存循环执行了n次。
1−2𝑙𝑜𝑔𝑛
于是内重循环次数是1 + 2 + 4 + ⋯+ n=20+21+…+2logn-1= = n-1
1−2
项
log 𝑛
2
= O(n).考点五:时间复杂度
8、下列函数的时间复杂度是______。
int i=0,s=0,n=一个正整数;
while(s<n) s=s+i++;
A.O(log n) B.O(n0.5) C.O(n) D.O(1)
2
B 【解析】 本题中最内层循环语句是sum += ++ i;
执行1次,1= 0 + 1; sum = 1 + 0
执行2次,2 = 1* 1; sum = 1 + 2
依次类推,
执行K次,j= K,K = K-1 + 1; sum = 1 + 2 + … + K;
𝐾(𝐾+1)
于是sum = < n; 得到时间复杂度是O(n1/2),T(n) = O( n1/2)。
2THANKSCON T EN T S
目录
考点一 基本概念
考点二 逻辑结构 ★
考点三 物理结构 ★
考点四 算法的概念和评价
考点五 时间复杂度 ★ ★ ★
考点六 空间复杂度 ★ ★考点六:空间复杂度
空间复杂度:用于量度一个算法运行过程中临时占用的存储空间大小。
一般也作为问题规模n的函数,采用数量级形式描述,记作:
S(n) = O(g(n))
程序代码
执行数据
辅助空间/临时变量考点六:空间复杂度
为什么空间复杂度分析只考虑临时占用的存储空间?
如果max函数中再考虑形参a的空间,
int max(int a[],int n)
就重复累计了执行整个算法所需的空间。
{ int i,maxi=0;
max算法的空间复杂度为O(1)
for (i=0;i< n;i++)
if (a[i]>a[maxi])
maxi=i; max()
return a[maxi];
}
max(b,n)
void maxfun()
maxfun()
{ int b[]={1,2,3,4,5},n=5;
printf("Max=%d\n",max(b,n));
}
maxfun算法中为b数组分配了相
应的内存空间,其空间复杂度为
O(n)考点六:空间复杂度
int fun(int n)
{ int i,j,k,s;
s=0; 临时占用的存储空
for (i=0;i< n;i++)
间:函数体内分配
for(j=0;j<=i;j++)
的空间
for (k=0;k<=j;k++)
s++;
return(s);
}
算法中临时分配的变量个数与问题规模n无关,所以空间复杂度均为O(1)。
若一个算法的空间复杂度为O(1),则称此算法为原地工作或就地工作算
法。【政哥题型总结】考点六:空间复杂度
1、下列函数的空间复杂度是______。
int func (int n){
int i=0, sum=0;
while(sum< n) sum += ++ i;
return i ;
}
A. O(log n) B. O(n1/2) C. O(n) D. O(1)
2
D【解析】空间复杂度是算法运行过程中所需的临时变量,此题中只有i,sum,
两个临时变量,空间复杂度是O(1)。考点六:空间复杂度
2、下面程序段的空间复杂度是()。
for(i = 0; i< m; i++ )
for(j = 0;j<n;j++)
a[i][j]=i* j;
A.O(m2) B.O(n2) C.O(m×n) D.O(m+n)
C【解析】空间复杂度是算法运行过程中所需的临时变量,此题中只有i,m,
n三个临时变量以及a[i][j]数组,空间复杂度是O(m×n)。考点六:空间复杂度
3、求整数n(n≥0)阶乘的算法如下,其空间复杂度是______。
int fact(int n) {
if (n<=1) return 1;
return n×fact(n-1);
}
A. O(log n) B. O(n) C. (nlog n) D. O(n2)
2 2考点六:空间复杂度
B【解析】本算法的最内层语句是:n×fact(n-1);每递归一次,n减1,共运行n-
1次,时间复杂度是O(n)。递归运算,即算法中出现了调用自身的情形。递归
的边界条件是 n-l, 每调用一次 fact(), 传入该层 fact()的参数值减1。采用递归
式来表示时间复杂度有
𝑂 1 𝑛 ≤ 1
fact(𝑛) = ቊ
fact 𝑛 − 1 + 1 𝑛 > 1
则 fact(n) = fact(n-1) + 1 = fact(n-2) + 2 =…= fact(1) + n-1 = O(n), 在调用
的过程中,使用栈进行存储,故空间复杂度为 O(n)。THANKS