第 1章 绪论
数据结构（ C++描述 ）
目录
1。 1 什么 是数据结构
1。 2 算法的 描述
1。 3 算法 分析
1。 4 退出
1.1什么是数据结构
1.1.1 数据结构示例
学号 姓名 性别 籍贯 电 话 通 讯 地 址
01 张三 男 长沙 8639000 麓山南路 327 号
02 李四 男 北京 23456789 学院路 435 号
03 王五 女 广州 30472589 天河路 478 号
04 赵六 男 上海 4123756 8 南京路 1563 号
05 钱七 女 南京 5013472 南京大学
06 刘八 女 武汉 6154372 6 武汉大学
07 朱九 男 昆明 4089651 云南大学
08 孙十 女 杭州 6154372 西湖路 6 35 号
图 1 - 1 学生数据表
1。线性表示例
2。树形结构示例
a
1
a
b c
b
1 a
2
Tt
b
2
c
1
c
2
d
d
1
d
2
d 3
图 1 - 2 树形结构示意图
一层
二层
三层
四层
3。图形结构示例
1 2
3
4 5
6
图 1 - 3 图形结构示意图
2,数据元素 （ data element）
数据元素是组成数据的基本单位 。
数据元素是一个数据整体中相对独立的单位 。 但
它还可以分割成若干个具有不同属性的项 （ 字
段 ）, 故不是组成数据的最小单位 。
1.1.2基本术语
1,数据 （ data）
数据是指能够输入到计算机中，并被计算机识别
和处理的符号的集合。
例如：数字、字母、汉字、图形、图像、声音
都称为数据。
3,数据对象 （ data object）
是性质相同的数据元素组成的集合, 是数据的一个子
集 。
例如, 整数数据对象的集合可表示为 N＝ {0,± 1，
± 2……,}, 字母字符数据对象的集合可表示为
C={‘A’,’B’,… ’Z’}。
4,数据类型 （ data type）
是一组性质相同的值的集合以及定义于这个值集合上
的一组操作的总称 。
例如, 高级语言中用到的整数数据类型, 是指由－
32768到 32767中值构成的集合及一组操作 （ 加, 减,
乘, 除, 乘方等 ） 的总称 。
5,抽象数据类型 （ Abstract Data Type）
是指一个数学模型以及定义在该模型上的
一组操作 。
在本书中, 描述一种抽象数据类型将采用如下书写格
式：
ADT <抽象数据类型名 > is
Data,< 数据描述 >
Operations:<操作声明 >
END
1.1.3 数据结构
1,数据结构 （ data structure）
是指相互之间存在一种或多种特定关系的数据元素所组
成的集合 。 具体来说, 数据结构包含三个方面的内容,
即数据的逻辑结构, 数据的存贮结构和对数据所施加的
运算 。 这三个方面的关系为：
（ 1） 数据的逻辑结构独立于计算机, 是数据本身所固
有的 。
（ 2） 存贮结构是逻辑结构在计算机存贮器中的映像,
必须依赖于计算机 。
（ 3） 运算是指所施加的一组操作总称 。 运算的定义直
接依赖于逻辑结构, 但运算的实现必依赖于存贮结构 。
2,从逻辑结构划分数据结构
数据结构从逻辑结构划分为：
（ 1） 线性结构
元素之间为一对一的线性关系, 第一个元素无直接
前驱, 最后一个元素无直接后继, 其余元素都有一
个直接前驱和直接后继 。
（ 2） 非线性结构
元素之间为一对多或多对多的非线性关系，每个元
素有多个直接前驱或多个直接后继。
3,从存贮结构划分数据结构
数据结构从存贮结构划分为：
(1)顺序存贮 （ 向量存贮 ）
所有元素存放在一片连续的存贮单元中, 逻辑上相
邻的元素存放到计算机内存仍然相邻 。
(2) 链式存贮
所有元素存放在可以不连续的存贮单元中, 但元素
之间的关系可以通过地址确定, 逻辑
上相邻的元素存放到计算机内存后不一定是相邻的。
(3)索引存贮
使用该方存放元素的同时, 还建立附加的索引表,
索引表中的每一项称为索引项, 索引项的一般形式
是,（ 关键字, 地址 ）, 其中的关键字是能唯一标
识一个结点的那些数据项 。
(4)散列存贮
通过构造散列函数, 用函数的值来确定元素存放的
地址 。
4,数据结构的抽象描述
数据结构可用二元组 D=(K,R)的形式来描述 。 其中,
K={a1,a2,…,an}为元素集合, R={r1,r2,…,rm}为关系的集合 。
例 1-5 设有一个线性表 (a1,a2,a3,a4,a5)，它的抽象描述可表示
为 D=(K,R),其中
K={a1,a2,a3,a4,a5},R={<a1,a2>,<a2,a3>,<a3,a4>,<a4,a5>}，则它
的逻辑结构用图描述见图 1-4 。
a1 a2 a3 a4 a5
图 1-4 线性表的逻辑结构描述
例 1-6 设一个数据结构的抽象描述为 D=(K,R),其中
K={a,b,c,d,e,f,g,h},r={<a,b>,<a,c>,<a,d>,<b,e>,<c,f>,<
c,g>,<d,h>},则它的逻辑结构用图描述见图 1-5。 a
b
c
d
e f g
h
图 1 - 5 树形结构抽象描述示意图
例 1-7 设一个数据结构的抽象描述为 D=(K,R),其中
K={1,2,3,4},而 R={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)},则它
的逻辑结构用图描述见图 1-6。
1 2
3 4
图 1 - 6 图形结构抽象描述示意图
1.2 算法的描述
1.2.1 基本概念
1,算法 （ algorithm）
通俗地讲, 算法就是一种解题的方法 。 更严格地说,
算法是由若干条指令组成的有穷序列, 它必须满足下
述条件 （ 也称为算法的五大特性 ）,
（ 1） 输入：具有 0个或多个输入的外界量 （ 算法开始
前的初始量 ）
（ 2） 输出：至少产生一个输出, 它们是算法执行完后
的结果 。
（ 3有穷性：每条指令的执行次数必须是有限的 。
（ 4)确定性：每条指令的含义都必须明确, 无二义性 。
（ 5)可行性：每条指令的执行时间都是有限的 。
2,算法和程序的关系
算法的含义与程序十分相似, 但二者是有区别的 。
一个程序不一定满足有穷性 （ 死循环 ）, 另外, 程
序中的指令必须是机器可执行的, 而算法中的指令
则无此限制 。 一个算法若用计算机语言来书写, 则
它就可以是一个程序 。
1.2.2算法描述
1,用流程图描述算法
一个算法可以用流程图的方式来描述, 输入输出,
判断, 处理分别用不同的框图表示, 用箭头表示流
程的流向 。 这是一种描述算法的较好方法, 目前在
一些高级语言程序设计中仍然采用 。
2,用自然语言描述算法
用我们日常生活中的自然语言（可以是中文形式，也可
以是英形式）也可以描述算法。
3,用其它方式描述算法
我们还可以用数学语言或约定的符号语言来描述算
法 。
4,用 C++描述算法
在本教材中, 我们将采用 C＋＋或类 C++来描述算法 。
并且用 C＋＋描述算法遵循如下规则：
（ 1） 所有算法的描述都用 C＋＋中的函数形式
函数类型 函数名 （ 形参及类型说明 ）
{ 函数语句部分
return(表达式值 )；
}
（ 2） 函数中的形式参数有两种传值方式
若为一般变量名, 则为单向传值, 若在变量前面增加
,&“符号, 则为双向传地址 。
例如有一个函数为 Void swap(&i,&j,k)则 i,j为双向
传地址参数, k为单向传值参数 。
（ 3） 函数的说明部分与函数的实现部分分离
在 C＋＋中，用函数来描述算法时，为使之与面象对象
的程序设计相匹配，一般将函数的说明部分与函数的实
现部分分离开来。
（ 4） 输入函数
C＋＋中的输入函数调用为, cin>>变量名。
（ 5） 输出函数
C＋＋中的输出函数调用为,cout<<变量名 。
(6) C++中的类
C++对于面向对象程序设计的支持,核心部分就是类的定义 。
类的定义体现了抽象数据类型的思想, 可以支持说明与实
现的分离, 将抽象数据类型的实现封装在类的内部, 使之
达到信息隐蔽的目的 。
（ 7） public 说明
对于 C++的类, 类成员可以用 public 声明, 表示这些东西为
公有的, 可以在此类及其它类中使用 。
（ 8） private 说明
对于 C++类, 类成员可以用 private声明, 表示这些东
西为私有的, 只能在本类中使用 。
（ 9） protected说明
对于 C++类，类成员可以用 protected声明，表示这部分是
受保护的，只能在本类及它的所有派生类中使用。
（ 10） C++的作用域
在 C++中, 每个变量都有一个作用域 。 在函数内声明
的变量, 仅能在该函数内部有效, 在类中声明的变量,
可以在该类内部有效, 在整个程序中都能使用的变量,
为全局变量, 否则称为局部变量 。 若一个全局变量与
一个局部变量同名, 则该范围内全局变量不起作用 。
若要使之起作用, 可以使用域操作符：：来实现 。
（ 11） 函数名重载
C++中允件多个函数取相同的函数名,但形式参数或返
回类型可以不同。
（ 12） 友元函数
在 C++的类的声明中,可以使用保留字 friend定义友元
函数, 使用友元函数可以在一个类中访问另一个类中
的私有成员 (PRIVATE)和被保护成员 (protected)。
（ 13） 内联 （ inline） 函数
在一个函数定义前加上 inline前缀就成为内联函数 。
使用内联函数可减少函数调用和参数传递的系统开销 。
1.3 算法分析
1.3.1 时间复杂度
1,时间频度
一个算法执行所耗费的时间, 从理论上是不能算出来的,
必须上机运行测试才能知道 。 但我们不可能也没有必要
对每个算法都上机测试, 只需知道哪个算法花费的时间
多, 哪个算法花费的时间少就可以了 。 并且一个算法花
费的时间与算法中语句的执行次数成正比例, 哪个算法
中语句执行次数多, 它花费时间就多 。 一个算法中的语
句执行次数称为语句频度或时间频度 。 记为 T(n)。
例 1-8 求下列算法段的语句频度
for(i=1; i<=n; i++)
for(j =1; j <=i ; j++)
x=x+1;
分析：该算法为一个二重循环，执行次数为内、外循
环次数相乘，但内循环次数不固定，与外循环有关，
因些，时间频度 T(n)=1+2+3+…+n= 2)1(?nn
2,时间复杂度
在刚才提到的时间频度中, n称为问题的规模, 当 n不
断变化时, 时间频度 T(n)也会不断变化 。 但有时我们
想知道它变化时呈现什么规律 。 为此, 我们引入时间
复杂度概念 。
设 T(n)的一个辅助函数为 g(n),定义为当 n大于等于某一
足够大的正整数 n0时, 存在两个正的常数 A和 B（ 其中
A≤B）, 使得 A≤T(n)/g(n)≤B均成立, 则称 g(n)是 T(n)的
同数量级函数 。 把 T(n)表示成数量级的形式为,T(n)=
Ｏ (g(n)),其中大写字母Ｏ为英文 Order（ 即数量级 ） 一
词的第一个字母 。
例如, 若 T(n)=n(n+1)/2,则有 1/4≤T(n)/n2≤1,故它的时
间复杂度为Ｏ (n2),即Ｔ (n)与 n2 数量级相同 。
例 1-9 分析下列算法段的时间频度及时间复杂度
for （ i=1;i<=n;i++）
for (j=1;j<=i;j++)
for ( k=1;k<=j;k++)
x=i+j-k;
分析算法规律可知时间频度
T(n)=1+(1+2)+(1+2+3)+...+(1+2+3+… +n)
=
=
= +
= [ + ]
由于有 1/6 ≤ T（ n)/ n3 ≤1,故时间复杂度为Ｏ (n3)。
?? ????nk k1 )...321(
?? ?nk kk1 2 )1(
??nk k122 ?
?
n
k
k
12
21 6 )12)(1( ?? nnn 2)1(?nn
在各种不同算法中, 若算法中语句执行次数为一个常
数, 则时间复杂度为 O(1),另外, 在时间频度不相同时,
时 间 复 杂 度 有 可 能 相 同, 如 T(n)=n2+3n+4 与
T(n)=4n2+2n+1它们的频度不同, 但时间复杂度相同,
都为 O(n2)。
按数量级递增排列, 常见的时间 复杂度有：
常数阶 O(1),对数阶 O(log2n),线性阶 O(n),
线性对数阶 O(nlog2n),平方阶 O(n2),立方阶 O(n3),...，
k次方阶 O(nk),指数阶 O(2n)。 随着问题规模 n的不断增大,
上述时间复杂度不断增大, 算法的执行效率越低 。
1.3.2 空间复杂度
1,空间频度
一个算法在执行时所占有的内存开销, 称为空间频
度, 但我们一般是讨论算法占用的辅助存储空间 。
讨论方法与时间频度类似, 不再赘述 。
２, 空间复杂度
与时间复杂度类似, 空间复杂度是指算法在计算机内
执行时所占用的内存开销规模 。 但我们一般所讨论的
是除正常占用内存开销外的辅助存储单元规模 。 讨论
方法与时间复杂度类似, 不再赘述 。
数据结构（ C++描述 ）
目录
1。 1 什么 是数据结构
1。 2 算法的 描述
1。 3 算法 分析
1。 4 退出
1.1什么是数据结构
1.1.1 数据结构示例
学号 姓名 性别 籍贯 电 话 通 讯 地 址
01 张三 男 长沙 8639000 麓山南路 327 号
02 李四 男 北京 23456789 学院路 435 号
03 王五 女 广州 30472589 天河路 478 号
04 赵六 男 上海 4123756 8 南京路 1563 号
05 钱七 女 南京 5013472 南京大学
06 刘八 女 武汉 6154372 6 武汉大学
07 朱九 男 昆明 4089651 云南大学
08 孙十 女 杭州 6154372 西湖路 6 35 号
图 1 - 1 学生数据表
1。线性表示例
2。树形结构示例
a
1
a
b c
b
1 a
2
Tt
b
2
c
1
c
2
d
d
1
d
2
d 3
图 1 - 2 树形结构示意图
一层
二层
三层
四层
3。图形结构示例
1 2
3
4 5
6
图 1 - 3 图形结构示意图
2,数据元素 （ data element）
数据元素是组成数据的基本单位 。
数据元素是一个数据整体中相对独立的单位 。 但
它还可以分割成若干个具有不同属性的项 （ 字
段 ）, 故不是组成数据的最小单位 。
1.1.2基本术语
1,数据 （ data）
数据是指能够输入到计算机中，并被计算机识别
和处理的符号的集合。
例如：数字、字母、汉字、图形、图像、声音
都称为数据。
3,数据对象 （ data object）
是性质相同的数据元素组成的集合, 是数据的一个子
集 。
例如, 整数数据对象的集合可表示为 N＝ {0,± 1，
± 2……,}, 字母字符数据对象的集合可表示为
C={‘A’,’B’,… ’Z’}。
4,数据类型 （ data type）
是一组性质相同的值的集合以及定义于这个值集合上
的一组操作的总称 。
例如, 高级语言中用到的整数数据类型, 是指由－
32768到 32767中值构成的集合及一组操作 （ 加, 减,
乘, 除, 乘方等 ） 的总称 。
5,抽象数据类型 （ Abstract Data Type）
是指一个数学模型以及定义在该模型上的
一组操作 。
在本书中, 描述一种抽象数据类型将采用如下书写格
式：
ADT <抽象数据类型名 > is
Data,< 数据描述 >
Operations:<操作声明 >
END
1.1.3 数据结构
1,数据结构 （ data structure）
是指相互之间存在一种或多种特定关系的数据元素所组
成的集合 。 具体来说, 数据结构包含三个方面的内容,
即数据的逻辑结构, 数据的存贮结构和对数据所施加的
运算 。 这三个方面的关系为：
（ 1） 数据的逻辑结构独立于计算机, 是数据本身所固
有的 。
（ 2） 存贮结构是逻辑结构在计算机存贮器中的映像,
必须依赖于计算机 。
（ 3） 运算是指所施加的一组操作总称 。 运算的定义直
接依赖于逻辑结构, 但运算的实现必依赖于存贮结构 。
2,从逻辑结构划分数据结构
数据结构从逻辑结构划分为：
（ 1） 线性结构
元素之间为一对一的线性关系, 第一个元素无直接
前驱, 最后一个元素无直接后继, 其余元素都有一
个直接前驱和直接后继 。
（ 2） 非线性结构
元素之间为一对多或多对多的非线性关系，每个元
素有多个直接前驱或多个直接后继。
3,从存贮结构划分数据结构
数据结构从存贮结构划分为：
(1)顺序存贮 （ 向量存贮 ）
所有元素存放在一片连续的存贮单元中, 逻辑上相
邻的元素存放到计算机内存仍然相邻 。
(2) 链式存贮
所有元素存放在可以不连续的存贮单元中, 但元素
之间的关系可以通过地址确定, 逻辑
上相邻的元素存放到计算机内存后不一定是相邻的。
(3)索引存贮
使用该方存放元素的同时, 还建立附加的索引表,
索引表中的每一项称为索引项, 索引项的一般形式
是,（ 关键字, 地址 ）, 其中的关键字是能唯一标
识一个结点的那些数据项 。
(4)散列存贮
通过构造散列函数, 用函数的值来确定元素存放的
地址 。
4,数据结构的抽象描述
数据结构可用二元组 D=(K,R)的形式来描述 。 其中,
K={a1,a2,…,an}为元素集合, R={r1,r2,…,rm}为关系的集合 。
例 1-5 设有一个线性表 (a1,a2,a3,a4,a5)，它的抽象描述可表示
为 D=(K,R),其中
K={a1,a2,a3,a4,a5},R={<a1,a2>,<a2,a3>,<a3,a4>,<a4,a5>}，则它
的逻辑结构用图描述见图 1-4 。
a1 a2 a3 a4 a5
图 1-4 线性表的逻辑结构描述
例 1-6 设一个数据结构的抽象描述为 D=(K,R),其中
K={a,b,c,d,e,f,g,h},r={<a,b>,<a,c>,<a,d>,<b,e>,<c,f>,<
c,g>,<d,h>},则它的逻辑结构用图描述见图 1-5。 a
b
c
d
e f g
h
图 1 - 5 树形结构抽象描述示意图
例 1-7 设一个数据结构的抽象描述为 D=(K,R),其中
K={1,2,3,4},而 R={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)},则它
的逻辑结构用图描述见图 1-6。
1 2
3 4
图 1 - 6 图形结构抽象描述示意图
1.2 算法的描述
1.2.1 基本概念
1,算法 （ algorithm）
通俗地讲, 算法就是一种解题的方法 。 更严格地说,
算法是由若干条指令组成的有穷序列, 它必须满足下
述条件 （ 也称为算法的五大特性 ）,
（ 1） 输入：具有 0个或多个输入的外界量 （ 算法开始
前的初始量 ）
（ 2） 输出：至少产生一个输出, 它们是算法执行完后
的结果 。
（ 3有穷性：每条指令的执行次数必须是有限的 。
（ 4)确定性：每条指令的含义都必须明确, 无二义性 。
（ 5)可行性：每条指令的执行时间都是有限的 。
2,算法和程序的关系
算法的含义与程序十分相似, 但二者是有区别的 。
一个程序不一定满足有穷性 （ 死循环 ）, 另外, 程
序中的指令必须是机器可执行的, 而算法中的指令
则无此限制 。 一个算法若用计算机语言来书写, 则
它就可以是一个程序 。
1.2.2算法描述
1,用流程图描述算法
一个算法可以用流程图的方式来描述, 输入输出,
判断, 处理分别用不同的框图表示, 用箭头表示流
程的流向 。 这是一种描述算法的较好方法, 目前在
一些高级语言程序设计中仍然采用 。
2,用自然语言描述算法
用我们日常生活中的自然语言（可以是中文形式，也可
以是英形式）也可以描述算法。
3,用其它方式描述算法
我们还可以用数学语言或约定的符号语言来描述算
法 。
4,用 C++描述算法
在本教材中, 我们将采用 C＋＋或类 C++来描述算法 。
并且用 C＋＋描述算法遵循如下规则：
（ 1） 所有算法的描述都用 C＋＋中的函数形式
函数类型 函数名 （ 形参及类型说明 ）
{ 函数语句部分
return(表达式值 )；
}
（ 2） 函数中的形式参数有两种传值方式
若为一般变量名, 则为单向传值, 若在变量前面增加
,&“符号, 则为双向传地址 。
例如有一个函数为 Void swap(&i,&j,k)则 i,j为双向
传地址参数, k为单向传值参数 。
（ 3） 函数的说明部分与函数的实现部分分离
在 C＋＋中，用函数来描述算法时，为使之与面象对象
的程序设计相匹配，一般将函数的说明部分与函数的实
现部分分离开来。
（ 4） 输入函数
C＋＋中的输入函数调用为, cin>>变量名。
（ 5） 输出函数
C＋＋中的输出函数调用为,cout<<变量名 。
(6) C++中的类
C++对于面向对象程序设计的支持,核心部分就是类的定义 。
类的定义体现了抽象数据类型的思想, 可以支持说明与实
现的分离, 将抽象数据类型的实现封装在类的内部, 使之
达到信息隐蔽的目的 。
（ 7） public 说明
对于 C++的类, 类成员可以用 public 声明, 表示这些东西为
公有的, 可以在此类及其它类中使用 。
（ 8） private 说明
对于 C++类, 类成员可以用 private声明, 表示这些东
西为私有的, 只能在本类中使用 。
（ 9） protected说明
对于 C++类，类成员可以用 protected声明，表示这部分是
受保护的，只能在本类及它的所有派生类中使用。
（ 10） C++的作用域
在 C++中, 每个变量都有一个作用域 。 在函数内声明
的变量, 仅能在该函数内部有效, 在类中声明的变量,
可以在该类内部有效, 在整个程序中都能使用的变量,
为全局变量, 否则称为局部变量 。 若一个全局变量与
一个局部变量同名, 则该范围内全局变量不起作用 。
若要使之起作用, 可以使用域操作符：：来实现 。
（ 11） 函数名重载
C++中允件多个函数取相同的函数名,但形式参数或返
回类型可以不同。
（ 12） 友元函数
在 C++的类的声明中,可以使用保留字 friend定义友元
函数, 使用友元函数可以在一个类中访问另一个类中
的私有成员 (PRIVATE)和被保护成员 (protected)。
（ 13） 内联 （ inline） 函数
在一个函数定义前加上 inline前缀就成为内联函数 。
使用内联函数可减少函数调用和参数传递的系统开销 。
1.3 算法分析
1.3.1 时间复杂度
1,时间频度
一个算法执行所耗费的时间, 从理论上是不能算出来的,
必须上机运行测试才能知道 。 但我们不可能也没有必要
对每个算法都上机测试, 只需知道哪个算法花费的时间
多, 哪个算法花费的时间少就可以了 。 并且一个算法花
费的时间与算法中语句的执行次数成正比例, 哪个算法
中语句执行次数多, 它花费时间就多 。 一个算法中的语
句执行次数称为语句频度或时间频度 。 记为 T(n)。
例 1-8 求下列算法段的语句频度
for(i=1; i<=n; i++)
for(j =1; j <=i ; j++)
x=x+1;
分析：该算法为一个二重循环，执行次数为内、外循
环次数相乘，但内循环次数不固定，与外循环有关，
因些，时间频度 T(n)=1+2+3+…+n= 2)1(?nn
2,时间复杂度
在刚才提到的时间频度中, n称为问题的规模, 当 n不
断变化时, 时间频度 T(n)也会不断变化 。 但有时我们
想知道它变化时呈现什么规律 。 为此, 我们引入时间
复杂度概念 。
设 T(n)的一个辅助函数为 g(n),定义为当 n大于等于某一
足够大的正整数 n0时, 存在两个正的常数 A和 B（ 其中
A≤B）, 使得 A≤T(n)/g(n)≤B均成立, 则称 g(n)是 T(n)的
同数量级函数 。 把 T(n)表示成数量级的形式为,T(n)=
Ｏ (g(n)),其中大写字母Ｏ为英文 Order（ 即数量级 ） 一
词的第一个字母 。
例如, 若 T(n)=n(n+1)/2,则有 1/4≤T(n)/n2≤1,故它的时
间复杂度为Ｏ (n2),即Ｔ (n)与 n2 数量级相同 。
例 1-9 分析下列算法段的时间频度及时间复杂度
for （ i=1;i<=n;i++）
for (j=1;j<=i;j++)
for ( k=1;k<=j;k++)
x=i+j-k;
分析算法规律可知时间频度
T(n)=1+(1+2)+(1+2+3)+...+(1+2+3+… +n)
=
=
= +
= [ + ]
由于有 1/6 ≤ T（ n)/ n3 ≤1,故时间复杂度为Ｏ (n3)。
?? ????nk k1 )...321(
?? ?nk kk1 2 )1(
??nk k122 ?
?
n
k
k
12
21 6 )12)(1( ?? nnn 2)1(?nn
在各种不同算法中, 若算法中语句执行次数为一个常
数, 则时间复杂度为 O(1),另外, 在时间频度不相同时,
时 间 复 杂 度 有 可 能 相 同, 如 T(n)=n2+3n+4 与
T(n)=4n2+2n+1它们的频度不同, 但时间复杂度相同,
都为 O(n2)。
按数量级递增排列, 常见的时间 复杂度有：
常数阶 O(1),对数阶 O(log2n),线性阶 O(n),
线性对数阶 O(nlog2n),平方阶 O(n2),立方阶 O(n3),...，
k次方阶 O(nk),指数阶 O(2n)。 随着问题规模 n的不断增大,
上述时间复杂度不断增大, 算法的执行效率越低 。
1.3.2 空间复杂度
1,空间频度
一个算法在执行时所占有的内存开销, 称为空间频
度, 但我们一般是讨论算法占用的辅助存储空间 。
讨论方法与时间频度类似, 不再赘述 。
２, 空间复杂度
与时间复杂度类似, 空间复杂度是指算法在计算机内
执行时所占用的内存开销规模 。 但我们一般所讨论的
是除正常占用内存开销外的辅助存储单元规模 。 讨论
方法与时间复杂度类似, 不再赘述 。
