书名：数据结构（Java版）（第3版）pdf/doc/txt格式电子书下载

推荐语：

作者：叶核亚著

出版社：电子工业出版社

出版时间：2011-08-01

书籍编号：30466593

ISBN：9787121136221

正文语种：中文

字数：135747

版次：3

所属分类：教材教辅-大学

版权信息

书名：数据结构（Java版）（第3版）

作者：叶核亚

ISBN：9787121136221

版权所有 · 侵权必究

第3版前言

本书是普通高等教育“十一五”国家级规划教材，可作为普通高等学校计算机及相近专业本科的数据结构课程教材。

数据结构是软件设计的重要理论和实践基础，数据结构设计和算法设计是软件系统设计的核心。“数据结构”课程讨论的知识内容，是软件设计的理论基础；“数据结构”课程介绍的技术方法，是软件设计中使用的基本方法。“数据结构”是理论与实践并重的课程，要求学生既要掌握数据结构的基础理论知识，又要掌握运行和调试程序的基本技能。因此，“数据结构”在计算机类各专业本科学生的培养过程中有着十分重要的地位，是计算机类各专业本科的一门核心课程，是培养程序设计能力的必不可少的重要环节。

“数据结构”课程内容多，概念抽象，理论深奥，递归算法难度较大，一直是计算机专业最难学的课程之一。本书精选基础理论内容，重点是数据结构设计和算法设计，通过降低理论难度和抽象性，加强实践环节等措施，进一步增强学生的理解能力和应用能力，力求取得较好的教学效果。

本书特色说明如下。

（1）内容全面、注重基础

本书全面系统地介绍数据结构的基础理论和算法设计方法，阐明线性表、树、图等数据模型的逻辑结构，讨论它们在计算机中的存储结构，讨论每种数据结构所能进行的多种操作，以及这些操作的算法设计和实现；针对软件设计中应用频繁的查找和排序问题，根据不同数据结构对操作的实际需求，给出多种查找和排序算法，并分析算法的执行效率。

本书的内容选择适合工科院校，理论叙述精练，简明扼要，结构安排合理，由浅入深，层次分明，重点突出，算法分析透彻，程序结构严谨规范。内容涉及的广度和深度符合本科培养目标的要求。

（2）采用Java语言描述数据结构和算法

表达数据结构和算法的设计思想不依赖于程序设计语言，实现数据结构和算法则依赖于程序设计语言。不仅如此，描述数据结构所采用的思想和方法还必须随着软件方法及程序设计语言的不断发展而发展。面向对象程序设计方法是目前软件开发的主流方法；Java语言是目前功能最强、应用最广泛的一种完全面向对象程序设计语言，具有成熟而严密的语法体系和强大的应用系统设计能力，其特有的面向对象、平台无关、内存自动管理、异常处理、多线程等机制，使其更健壮、更安全、更高效。因此，依托一种功能强大的程序设计语言，充分表达和实现复杂的设计思想，是提高程序设计能力的一种有效手段。

虽然Java语言放弃了C++语言的全局函数、结构体、指针、友元类、运算符重载、多重继承等功能，但这些丝毫不影响Java语言的功能和性能。Java通过引用模型实现了指针的功能，通过类实现了结构体类型，通过“单重继承+接口”方式实现了多重继承，通过内存自动管理机制自动释放动态分配的存储空间。Java语言提供的各种机制均体现出简单性原则，即对一个问题只给出一种解决方法，使程序简单、直接并且不造成歧义。

Java语言不仅具备表达数据结构和算法的基本要素，而且能使算法更简明、更直接。因此，采用Java语言描述数据结构和算法是可行的，作为面向对象的程序设计方法训练是十分恰当的，也是数据结构课程内容改革的必然，完全符合本科培养目标的要求。

（3）增强实际应用

数据结构是一门理论和实践紧密结合的课程，要在透彻理解理论知识的基础上，通过实践性环节，逐步锻炼程序设计能力。

注重传授基础理论知识，注重在实践环节中培养程序设计的基本技能，是本书前两版的重要特色，也是本书的重要特色。本书精心选择并设计一系列与实际应用息息相关的例题、习题、实验题、课程设计题等，使原本枯涩难懂的理论变得生动有趣，并以此说明数据结构和算法的必要性，以及它们对实际应用程序设计的指导作用。同时，要求学生能在生活中发现问题并解决问题，提高学习兴趣，力求在潜移默化中使学生理解和体会理论知识的重要性，并掌握如何使用它们的方法。

除了每章的实验题给出详细的训练目标、设计内容和设计要求之外，针对课程设计实践性环节，本书给出多种算法设计与分析的综合应用程序设计实例，详细说明需求方案、设计思想、模块划分、功能实现、调试运行等环节的设计方法，贯彻理论讲授和案例教学相结合的教学方法。

程序设计有其自身的规律，不是一蹴而就的，也没有捷径。程序员必须具备基本素质，必须掌握程序设计语言的基本语法以及算法设计思想和方法，并且需要积累许多经验。这个逐步积累的过程需要一段时间，需要耐心，厚积而薄发。

本书第1～9章是“数据结构”课程的主要内容，包括线性表、树、图等数据结构设计以及查找和排序算法设计；第10章为综合应用设计，包括课程设计的范例和参考选题。第1章介绍的Java开发运行环境包括JDK和MyEclipse，为其后各章运行和调试程序提供操作基础，熟练掌握集成开发环境的各种操作以及程序调试技术是程序设计的一项基本技能，也需要经过一个逐步积累的过程。

本书所有程序均已在JDK 6中调试通过。

本书由叶核亚编著，在写作过程中得到了许多帮助和支持。感谢南京大学计算机科学与技术系陈本林教授，陈教授认真细致地审阅了全稿，提出了许多宝贵意见，感谢黄纬、徐金宝、彭焕峰、刘晓璐、廖雷、阚建飞、陈瑞、沈晨鸣、陈立、陈建红、王青云、王少东、李林广等老师给予的帮助，感谢电子工业出版社的支持，感谢众多读者朋友对本书前两版提出的宝贵意见。

对书中存在的不妥与错漏之处，敬请读者朋友批评指正。

本书为任课教师提供配套的教学资源（包含电子教案和例题源代码），需要者可登录华信教育资源网（http：//www.hxedu.com.cn），注册之后进行下载。

读者反馈：unicode＠phei.com.cn。

作者

第1章 绪论

计算机数据处理的前提是数据组织，如何有效地组织数据和处理数据是软件设计的基本内容，也是“数据结构”课程的基本内容。

作为绪论，本章勾勒“数据结构”课程的一个轮廓，说明“数据结构”课程的目的、任务和主要内容。本章主要介绍数据结构概念所包含的数据逻辑结构、数据存储结构和数据操作等，介绍抽象数据类型概念，介绍算法概念、算法设计目标、算法描述和算法分析方法。本书采用Java语言的接口描述抽象数据类型，采用类实现接口，即实现抽象数据类型中描述的操作。

1.1 数据结构的基本概念

1.1.1 为什么要学习数据结构

软件设计是计算机学科的核心内容之一。进行软件设计时要考虑的首要问题是数据的表示、组织和处理方法，这直接关系到软件的工程化程度和软件的运行效率。

随着计算机技术的飞速发展，计算机应用从早期的科学计算扩大到过程控制、管理和数据处理等领域。计算机处理的对象也从简单的数值数据，发展到各种多媒体数据。软件系统处理的数据量越来越大，数据的结构也越来越复杂。因此，针对实际问题，如何合理地组织数据，如何建立合适的数据结构，如何设计好的算法，是软件设计的重要问题，而这些正是“数据结构”课程讨论的主要内容。

在计算机中，现实世界中的对象用数据来描述。“数据结构”课程的任务是，讨论数据的各种逻辑结构、在计算机中的存储结构以及各种操作的算法设计。“数据结构”课程的主要目的是，培养学生掌握处理数据和编写高效率软件的基本方法，为学习后续专业课程以及进行软件开发打下坚实基础。

数据结构是软件设计的重要理论和实践基础，数据结构设计和算法设计是软件系统设计的基础和核心。“数据结构”课程讨论的知识内容，是软件设计的理论基础；数据结构课程介绍的技术方法，是软件设计中使用的基本方法。“数据结构”是一门理论与实践并重的课程，要求学生既要掌握数据结构的基础理论知识，又要掌握运行和调试程序的基本技能。因此，“数据结构”课程在计算机学科本科培养过程中的地位十分重要，是计算机专业本科的核心课程，是培养程序设计能力的必不可少的重要环节。

在计算机界流传着一句经典名言“数据结构+算法=程序设计”（瑞士Niklaus Wirth教授），这句话简洁、明了地说明了程序（或软件）与数据结构和算法的关系，以及“数据结构”课程的重要性。

1.1.2 什么是数据结构

数据（data）是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。数据是信息的符号表示，是计算机程序的处理对象。除了数值数据外，计算机能够处理的数据还有字符串等非数值数据，以及图形、图像、音频、视频等多媒体数据。

表示一个事物的一组数据称为一个数据元素（data element），数据元素是数据的基本单位。数据元素可以是一个不可分割的原子项，也可以由多个数据项组成。数据项（data item）是数据元素中有独立含义的、不可分割的最小标识单位。例如，一个整数、一个字符都是原子项，一个学生数据元素由学号、姓名、性别和出生日期等多个数据项组成。关键字（key）是数据元素中用于识别该元素的一个或多个数据项，能够唯一识别数据元素的关键字称为主关键字（primary key）。

在由数据元素组成的数据集合中，数据元素之间通常具有某些内在联系。研究数据元素之间存在的关系并建立数学模型，是设计有效地组织数据和处理数据方案的前提。

数据结构是指数据元素之间存在的关系。一个数据结构（data structure）是由n（n≥0）个数据元素组成的有限集合，数据元素之间具有某种特定的关系。

数据结构概念包含三方面：数据的逻辑结构、数据的存储结构和数据的操作。

1.数据的逻辑结构

数据的逻辑结构是指数据元素之间的逻辑关系，用一个数据元素的集合和定义在此集合上的若干关系来表示，常被简称为数据结构。

根据数据元素之间逻辑关系的不同数学特性，数据结构可分为三种：线性结构、树结构和图（如图1-1所示），其中树和图又被称为非线性结构。

图1-1 三种数据结构

图1-1以图示法表示数据的逻辑结构，一个圆表示一个数据元素，圆中的字符表示数据元素的标记或取值，连线表示数据元素之间的关系。

（1）线性结构

线性结构是最简单的数据结构，数据元素之间具有线性关系，即除第一个和最后一个元素外，每个元素有且仅有一个前驱元素和一个后继元素，第一个元素没有前驱元素，最后一个元素没有后继元素。在图1-1（a）中，元素B的前驱是A，后继是C，元素A没有前驱，元素D没有后继。线性表、串、栈和队列等都是线性结构。

数据元素可以是一个数、字符、字符串或其他复杂形式的数据。例如，整数序列{1，2，3，4，5，6}，字母序列{\'A\'，\'B\'，\'C\'，…，\'Z\'}，表1-1所示的学生序列都是线性表，数据元素之间具有顺序关系。

表1-1 学生信息表

其中，学生数据元素由“学号”、“姓名”、“年龄”等数据项组成，“姓名”可以作为标识一个学生的关键字，“学号”是能够唯一标识一个学生的主关键字。

（2）树结构

树结构是数据元素之间具有层次关系的一种非线性结构，树中数据元素通常称为结点。树结构的层次关系是指，根（最顶层）结点没有前驱结点（称为父母结点），除根之外的其他结点有且仅有一个父母结点，所有结点可有零到多个后继结点（称为孩子结点）。在图1-1（b）中，A是树的根结点，B结点有一个父母结点A，有3个孩子结点E、F和G。家谱、Windows文件系统的组织方式、淘汰赛的比赛规则等都是树结构。具有树结构的淘汰赛比赛规则如图1-2所示，其中数据是2010年南非世界杯足球赛淘汰赛的比赛结果。

图1-2 淘汰赛的树结构

（3）图

图也是非线性结构，每个数据元素可有多个前驱元素和多个后继元素。例如，交通道路图、飞机航班路线图等都具有图结构。图1-3是从南京飞往昆明的航班路线图，有直飞航班，也有经停重庆或长沙的航班，边上数值表示两地间的千米数。

图1-3 南京飞往昆明的航班路线图

2.数据的存储结构

数据元素及其关系在计算机中的存储表示或实现称为数据的存储结构，也称为物理结构。软件系统不仅要存储所有数据，还要正确地表示出数据元素之间的逻辑关系。

数据的逻辑结构从逻辑关系角度观察数据，与数据的存储无关，是独立于计算机的。而数据的存储结构是逻辑结构在计算机内存中的实现，是依赖于计算机的。

数据存储结构的基本形式有两种：顺序存储结构和链式存储结构。

顺序存储结构使用一组连续的内存单元依次存放数据元素，元素在内存中的物理存储次序与它们的逻辑次序相同，即每个元素与其前驱及后继元素的存储位置相邻。这样，元素的物理存储次序体现数据元素间的逻辑关系，通常使用程序设计语言中的数组实现。

链式存储结构使用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，数据元素间的关系需要采用附加信息特别指定。通常，采用指针变量记载前驱或后继元素的存储地址，由数据域和地址域组成的一个结点表示一个数据元素，通过地址域把相互直接关联的结点链接起来，结点间的链接关系体现数据元素间的逻辑关系。

线性表可采用上述两种存储结构。线性表（a₀，a₁，…，a_n-1）的两种存储结构如图1-4所示。

图1-4 线性表（a₀，a₁，…，a_n-1）的两种存储结构

图1-4（a）采用顺序存储结构存储线性表（a₀，a₁，…，a_n-1），数据元素占用所有存储空间，各元素a_i（0≤i<n）连续存储，逻辑上相邻的数据元素a_i-1、a_i和a_i+1在存储位置上也相邻，数据的存储结构体现数据的逻辑结构。图1-4（b）采用链式存储结构存储线性表（a₀，a₁，…，a_n-1），各元素a_i分散存储，每个元素a_i必须用一个包含数据域和地址域的结点存储，数据域保存数据元素a_i，地址域保存元素a_i的前驱和（或）后继结点的地址。结点间的链接关系体现数据的逻辑结构。

如果一个数据元素由多个数据项组成，则数据域有多个。例如，学生线性表的顺序和链式存储结构如图1-5所示。

图1-5 学生信息表的两种存储结构

顺序存储结构和链式存储结构是两种最基本、最常用的存储结构。除此之外，将顺序存储结构和链式存储结构进行组合，还可以构造出一些更复杂的存储结构。

3.数据操作

数据操作指对一种数据结构中的数据元素进行各种运算或处理。每种数据结构都有一组数据操作，其中包含以下基本操作。

⊙ 初始化。

⊙ 判断是否空状态。

⊙ 统计数据元素个数。

⊙ 判断是否包含指定元素。

⊙ 按某种次序访问所有元素，每个元素只被访问一次，称为遍历操作。

⊙ 获取指定元素值。

⊙ 设置指定元素值。

⊙ 插入指定元素。

⊙ 删除指定元素。

⊙ 查找指定元素。

数据操作定义在数据的逻辑结构上，对数据操作的实现依赖于数据的存储结构。例如，线性表包含上述一组数据操作，采用顺序存储结构或链式存储结构，都可实现这些操作。

1.1.3 数据类型与抽象数据类型

1.数据类型

类型（type）是具有相同逻辑意义的一组值的集合。数据类型（data type）是指一个类型和定义在这个类型上的操作集合。数据类型定义了数据的性质、取值范围以及对数据所能进行的各种操作。例如，Java语言的整数类型int，除了数值集合[-2³¹，…，-2，-1，0，1，2，…，2³¹-1]之外，还包括在这个值集上的操作集合[+，-，*，/，%，=，==，！=，＜，＜=，＞，＞=]。

程序中的每个数据都属于一种数据类型，决定了数据的类型也就决定了数据的性质以及对数据进行的运算和操作，同时数据也受到类型的保护，确保对数据不能进行非法操作。

高级程序设计语言通常预定义一些基本数据类型和构造数据类型。基本数据类型的值是单个的、不可分解的，它可直接参与该类型所允许的运算。构造数据类型是使用已有的基本数据类型和已定义的构造数据类型按照一定的语法规则组织起来的较复杂的数据类型。构造数据类型的值由若干元素组合而成，这些元素按某种结构组织在一起。

Java语言的基本数据类型有整数类型、浮点数类型、字符类型、布尔类型，构造数据类型（称为引用类型）有数组、类和接口。

数据类型与数据结构两个概念的侧重点不同。数据类型研究的是每种数据所具有的特性，以及对这种特性的数据能够进行哪些操作；数据结构研究的是数据元素之间具有的相互关系，数据结构与数据元素的数据类型无关，也不随数据元素值的变化而改变。

2.抽象数据类型

抽象数据类型（Abstract Data Type，ADT）是指一个数学模型以及定义在该模型上的一组操作。例如，复数是数学中常用的一种类型，一个复数a+ib由实部a和虚部b两部分组成，i是虚部标记。复数抽象数据类型描述如下：

大多数程序设计语言没有提供复数类型。程序员需要实现ADT Complex所声明的操作。

（1）数据抽象

抽象数据类型和数据类型本质上是一个概念，它们都表现数据的抽象特性。数据抽象是指“定义和实现相分离”，即将一个类型上的数据及操作的逻辑含义与具体实现分离。程序设计语言提供的数据类型是抽象的，仅描述数据的特性和对数据操作的语法规则，并没有说明这些数据类型是如何实现的。程序设计语言实现了它预定义数据类型的各种操作。程序员按照语言规则使用数据类型，只考虑对数据执行什么操作（做什么），而不必考虑怎样实现这些操作（怎样做）。

例如，赋值语句的语法定义为“变量=表达式”，表示先求得指定表达式的值，再将该值赋给指定变量。程序员需要关注所用数据类型的值能够参加哪些运算、表达式是否合法、表达式类型与变量类型是否赋值相容等；至于如何存储一个整数、变量的存储地址是什么、如何求得表达式值等实现细节则不必关注，这些操作由语言的实现系统完成。

数据抽象是研究复杂对象的基本方法，也是一种信息隐蔽技术，从复杂对象中抽象出本质特征，忽略次要细节，使实现细节相对于使用者不可见。抽象层次越高，其软件复用程度也越高。抽象数据类型是实现软件模块化设计思想的重要手段。一个抽象数据类型是描述一种特定功能的基本模块，由各种基本模块可组织和构造起来一个大型软件系统。

（2）抽象数据类型的声明

抽象数据类型的规范描述包括ADT名称、数据描述和操作描述，操作描述包括操作名、初始条件和操作结果。例如，集合ADT描述如下：

与使用数据类型描述数据特性一样，通常使用抽象数据类型描述数据结构，将线性表、树、图等数据结构分别定义为各种抽象数据类型，一种抽象数据类型描述一种数据结构的逻辑特性和操作，与该数据结构在计算机内的存储及实现无关。

在实际应用中，必须实现这些抽象数据类型，才能使用它们。而实现抽象数据类型依赖于数据存储结构。例如，线性表可分别采用顺序存储结构或链式存储结构实现，详见第2章。

3.用Java语言的接口描述抽象数据结构

Java语言的接口提供方法声明与方法实现相分离的机制，使实现指定接口的多个类之间表现出共同的行为能力。例如，集合接口SSet声明如下，文件名为SSet.java。

SSet<T>声明为泛型接口，T是类型形式参数，指定元素的数据类型，T的实际类型参数是类，在声明和创建对象时指定。

泛型也称为类属（generic），是对类型系统的一种强化措施。泛型通过类型参数，使一个类或一个方法可在多种类型的对象上操作，增强编译时的类型安全，避免类型转换的麻烦和潜在错误。泛型含义同C++的类模板。Java从JDK 5开始支持泛型。

public接口中方法的默认修饰符是public abstract，抽象方法只有方法声明没有方法体，由实现该接口的类提供方法实现。实现SSet接口的Set类声明如下：

该类必须实现SSet接口中声明的所有方法。

每种数据结构就是一个实现表示抽象数据类型接口的类，每个类提供接口中方法的不同实现。接口中的方法在不同的类中表现出多态性。

Java约定，一个Java源程序文件（*.java）中可以声明多个类或接口，但声明为public的类或接口只能有一个，且文件名必须与该类名相同。

1.2 算法

1.2.1 什么是算法

1.算法定义

曾获图灵奖的著名计算科学家D.Knuth对算法做过一个为学术界广泛接受的描述性定义：一个算法（algorithm）是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。

算法的规则必须满足以下5个特性。

① 有穷性：对于任意一组合法的输入值，算法在执行有穷步骤之后一定能结束。即算法的操作步骤为有限个，且每步都能在有限时间内完成。

② 确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。

③ 可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。

④ 有输入：算法有零个或多个输入数据。输入数据是算法的加工对象，既可以由算法指定，也可以在算法执行过程中通过输入得到。

⑤ 有输出：算法有一个或多个输出数据。输出数据是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。

有穷性和可行性是算法最重要的两个特征。

2.算法设计目标

算法设计应满足以下5个目标。

⊙ 正确性：算法应确切地满足应用问题的需求，这是算法设计的基本目标。

⊙ 健壮性：即使输入数据不合适，算法也能做出适当处理，不会导致不可控结果。

⊙ 高时间效率：算法的执行时间越短，时间效率越高。

⊙ 高空间效率：算法执行时占用的存储空间越少，空间效率越高。

⊙ 可读性：算法表达思路清晰，简洁明了，易于理解。

如果一个操作有多个算法，应该选择执行时间短和存储空间占用少的算法。但是，执行时间短和存储空间占用少有时是矛盾的，往往不可兼得，此时，算法的时间效率通常是首要考虑因素。

3.算法描述

算法是对问题求解过程的描述，精确地指出怎样从给定的输入信息得到要求的输出信息，其中操作步骤的语义明确，操作序列的长度有限。

可以用自然语言描述算法。例如，查找是数据结构的一种基本操作，有多种查找算法可实现查找功能，最简单的是顺序查找算法。在图1-5所示的学生信息表中，以“姓名”为关键字进行顺序查找，从线性表的一端开始，依次将每位学生姓名与给定值进行比较，若有相等者，则查找成功，查找操作结束；否则继续比较，直到比较完所有元素，仍未有相等者，则查找不成功，给出结果信息。

也可以用伪码描述算法。采用伪码描述顺序查找算法如下：

用自然语言或伪码描述算法能够抽象地描述算法设计思想，但是计算机无法执行。因此，数据结构和算法实现需要借助程序设计语言，将算法表达成基于一种程序设计语言的可执行程序。

4.算法与数据结构

算法建立在数据结构之上，对数据结构的操作需要用算法来描述。例如，线性表有遍历、插入、删除、查找、排序等操作；树有遍历、查找、插入、删除等操作。通过研究算法，能够更深刻地理解数据结构的操作。

算法设计依赖于数据的逻辑结构，算法实现依赖于数据的存储结构。例如，线性表的插入和删除操作，采用顺序存储结构，由于数据元素是相邻存储的，所以插入前和删除后都必须移动一些元素；采用链式存储结构，插入或删除一个元素，只需要改变相关结点的链接关系，无须移动元素。线性表（a₀，a₁，…，a_n-1）两种存储结构的插入操作如图1-6所示。

图1-6 线性表（a₀，a₁，…，a_n-1）两种存储结构的插入操作

实现一种抽象数据类型，需要选择合适的存储结构，使得以下两方面的综合性能最佳：数据操作所花费的时间短，占用的存储空间少。对线性表而言，当不需要频繁进行插入和删除操作时，可采用顺序存储结构；当插入和删除操作很频繁时，可采用链式存储结构。

1.2.2 算法分析

算法分析主要包含时间代价和空间代价两方面。

1.时间代价分析

算法的时间代价是指算法执行时所花费的CPU时间量，是算法中涉及的存、取、转移、加、减等各种基本运算的执行时间之和，与参加运算的数据量有关，很难事先计算得到。

算法的时间效率是指算法的执行时间随问题规模的增长而增长的趋势，通常采用时间复杂度（time complexity）来度量。当问题的规模以某种单位从1增加到n时，解决这个问题的算法在执行时所耗费的时间也以某种单位从1增加到T（n），则称此算法的时间复杂度为T（n）。当n增大时，T（n）也随之增大。

采用算法的渐进分析中的大O表示法作为算法时间复杂度的渐进度量值。大O表示法是指，当且仅当存在正整数c和n₀，使得T（n）≤cf（n）对所有的n≥n₀成立时，称该算法的时间增长率与f（n）的增长率相同，记为T（n）=O（f（n））。

若算法的执行时间是常数级，不依赖于数据量n的大小，则时间复杂度为O（1）；若算法的执行时间是n的线性关系，则时间复杂度为O（n）。同理，对数级、平方级、立方级、指数级的时间复杂度分别为O（log2n）、O（n2）、O（n3

....