数据结构1-绪论-青岛学院

1、数据结构第一章 绪论中国海洋大学青岛学院 孙月江Telmail:1.1 什么是数据结构1.2 基本概念和术语1.4 算法和算法分析1.3 抽象数据类型的表示与实现主要内容（4学时）：为什么要学习数据结构？数据结构不是教你怎样才能编程，而是教你怎样才能编好程;数据结构就是教你怎样用最精简的语言，利用最少的资源（包括时间和空间）编写出最优秀最合理的程序。 数据结构存在的意义就是使程序最优化。数据结构就是编程的思维，编程的灵魂，算法的精髓所在，没有了数据结构，程序就好像一个空核，是低效率的。 如果把程序看成一辆汽车，那么程序语言就构成了这辆车的车身和轮胎。而算法则是这辆车的

2、核心发动机。这辆车跑得是快是慢，关键就在于发动机的好坏（当然轮胎太烂了也不行），而数据结构就是用来改造发动机的。可以这么说，数据结构并不是一门语言，它是一种思想，一种方法，一种思维方式。它并不受语言的限制 。1.1 什么是数据结构CS是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示 ：学生信息、视频、图片等的表示信息的处理：查找、删除、修改、压缩、排序等信息的表示和组织直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象

3、之间存在的关系，这就是数据结构这门课所要研究的问题。一般来讲，用计算机解决一个具体问题时，大致需要下列几个步骤：首先从具体问题抽象出一个适当的数学模型：分析问题，从中提取操作的对象，并找出这些对象之间的关系，然后用数学语言加以描述。然后设计一个解此数学模型的算法最后编出程序、进行测试、调整直至得到最终答案。 1.1 什么是数据结构问题：比如黄蓉遇上神算子瑛姑，给她出的三道题目中有一题是这样的:今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？也就是说，有一个未知数，这个数除以三余二，除以五余三，除以七余二，问这个数是多少？数学模型：线性方程组算法：解方程组编程实现public

4、 class hr public static void main(String args) for(int x=0;x100;x+) if(x % 3 = 2)&(x % 5 = 3)&(x % 7 = 2) System.out.println(这个数字是：); System.out.println(x); 例1-1图书馆的书目检索系统自动化问题001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02.高等数学001，003理论力学002,线性代数004,L002,S001,003,樊映川001,华罗庚003,栾汝书004,图1.1 图书目录

5、文件示例 由这四张表构成的文件便是书目自动检索的数学模型，计算机的主要操作便是按照某个特定要求对书目文件进行查询。在这类文档管理的数学模型中，计算机处理的对象之间通常存在着的是一种最简单的线性关系，这类数学模型可称为线性的数据结构。“学生”表格9补充：电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排： (a1，b1)(a2，b2)(an，bn)其中ai，bi(i=1，2n) 分别表示某人的名字和对应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标

6、志。上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。例1-2 计算机和人对弈算法：?对弈的规则和策略棋盘及棋盘的格局(树)模型：?图1.2UNIX文件系统的系统结构图12算法：?通路之间相互矛盾的关系各种图模型：?图1.3例1-3 多叉路口交通灯的管理问题例：铺设城市的煤气管道算法：?模型：?如何规划使得总投资花费最少？图概括地说： 数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。或者说， 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。数据结构的发展历

7、史1968年美国唐欧克努特Donald E.Knuth教授开创了数据结构的最初体系从20世纪70年代中期到80年代初，各种版本的数据结构著作就相继出现。未来发展的两个方向： （1）面向各专门领域中特殊问题的数据结构：多维图形数据结构等 （2）抽象数据类型的观点来讨论数据结构。The Art of Computer Programming: 1. Fundamental Algorithms; 2. Seminumerical Algorithms; 3. Sorting and Searching；三卷中文名为基本算法、半数值算法及排序与查找。本书内容博大精深，作者因为三卷书获得美国计算机协会

8、1974年图灵奖(该奖被国际公认为计算机科学领域的最高奖项)。对于Knuth教授来说，衡量一个计算机程序是否完整的标准不仅仅在于它是否能够运行，他认为一个计算机程序应该是雅致的、甚至可以说是美的。计算机程序设计应该是一门艺术，一个算法应该像一段音乐，而一个好的程序应该如一部文学作品一般。如果你认为你是一名真正优秀的程序员读Knuth的计算机程序设计艺术，如果你能读懂整套书的话，请给我发一份你的简历。 Bill Gates一、数据与数据结构二、数据类型三、抽象数据类型1.2 基本概念和术语一、数据与数据结构 所有能输入到计算机中，且能被计算机程序处理的符号的总称。数据:是计算机操作的对象的总称。

9、是计算机处理的信息的某种特定的符号表示形式。数据可以分为两类：数值性数据非数值性数据 数据项： 是数据结构中讨论的最小单位。数据元素可以是数据项的集合。例如：描述一个运动员的数据元素可以是称之为组合项姓名俱乐部名称出生日期参加日期职务业绩年月日数据元素： 是数据（集合）中的一个“个体”，是数据结构中讨论的基本单位。可由若干个数据项组成。数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合N=0，1，-1，2，-2，字母字符数据对象是集合C=A，B，Z。数据结构：带结构的数据元素的集合。是相互之间存在一种或多种特定关系的数据元素的集合。 例，在2行3列的二维数组a1,

10、 a2, a3, a4, a5, a6 中六个元素之间存在两个关系:行的次序关系:列的次序关系:row = ,col = , a1 a3 a5 a2 a4 a6 a1 a2 a3a4 a5 a6 再例，在一维数组 a1, a2, a3, a4, a5, a6 的数据元素之间存在如下的次序关系:| i=1, 2, 3, 4, 5，6 或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。 可见，不同的“关系”构成不同的“结构”。注意：数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。数据结构主要指逻辑结构和物理结构数据之间的

11、相互关系称为逻辑结构。通常分为四类基本结构：集合 结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构 结构中的数据元素之间存在一对一的关系。树型结构 结构中的数据元素之间存在一对多的关系。图状结构或网状结构 结构中的数据元素之间存在多对多的关系。 25数据结构的形式定义为：数据结构是一个二元组： Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例：复数的数据结构定义如下： Complex=(C，R)其中：C是含两个实数的集合C1，C2，分别表示复数的实部和虚部。R=P，P是定义在集合上的一种关系C1，C2。26例1-4 设有一个数据结构的形式

12、定义可表示为DS=(D,S),其中D=a1,a2,a3,a4,a5,S=,，则它的逻辑结构用图描述见图1.4 。 线性表的逻辑结构描述a1a2a3a4a5例1-5 设一个数据结构的形式定义为DS=(D,S),其中D=a,b,c,d,e,f,g,h,S=,则它的逻辑结构用图描述见图1.5。例 1-6 设一个数据结构的形式定义为DS=(D,S),其中D=1,2,3,4,而S=(1,2),(1,3),(1,4),(2,3),(2,4),(3,4), 则它的逻辑结构用图描述见图1.6。存储结构（Storge Structure):数据结构在计算机中的表示(或称映象）称为数据的存储结构，又称为物理结构。

13、数据结构在计算机中有两种不同的表示方法：顺序表示和非顺序表示由此得出两种不同的存储结构：顺序存储结构和链式存储结构顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。数据的存储结构：逻辑结构在存储器中的映象“数据元素”的映象 ？“关系”的映象 ？数据元素的映象方法：例：用二进制位(bit)的位串表示数据元素(321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2关系的映象方法：（表示x, y的方法）顺序映象以相对的存储位置

14、表示后继关系。 例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C。而 C 是一个隐含值，整个存储结构中只含数据元素本身的信息。 x y链式映象 以附加信息(指针)表示后继关系。需要用一个和 x 在一起的附加信息指示 y 的存储位置。 y x 在不同的编程环境中，存储结构可有不同的描述方法。 当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。例如: 以三个带有次序关系的整数表示一个长整数时，可利用 C 语言中提供的整数数组类型。 typedef int Long_int 3定义长整数为:二、数据类型在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常

15、量或表达式，明确说明它们所属的数据类型。C语言的数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义数据类型:是一个值的集合和定义在此集合上的一组操作的总称。不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。使用数据类型可以实现信息隐蔽，即将用户不必了解的细节都封装在类型中。三、抽象数据类型(Abstract Data Type 简称ADT) 是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型的描述方法：抽象数据类型可用（D，S，P）三元组表示。D 是数据对象；S 是 D 上的关系集；P 是对 D 的基本操作集。 数据

16、类型与抽象数据类型的区别？数据类型：是一个值的集合和定义在该值上的一组操作的总称。抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。例如：各种高级程序设计语言中都拥有“整数”类型，尽管它们在不同处理器上实现的方法不同，但对程序员而言是“相同的”，因为它们的数学特性相同。抽象数据类型的范畴更广，不再局限于各处理器已定义和实现的数据类型，还包括用户根据需要自定义的数据类型。抽象数据类型的分类原子类型：变量的值是不可分解得。较少，已有的固有类型足以满足

17、需要。特殊情况下，也需要定义新的原子类型。固定聚合类型：其值由确定数目的成分按某种结构组成。例如：复数，分数可变聚合类型：构成的类型值的成分数目不确定。例如：有序整数序列，其中序列的长度是可变的。后两种统称为：结构类型ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名其中基本操作的定义格式为:基本操作名（参数表） 初始条件：初始条件描述 操作结果：操作结果描述 ADT常用定义格式赋值参数 只为操作提供输入值。引用参数 以&打头，除可提供输入值外，还将返回操作结果。初始条件 描述了操作执行之前数据结构和参数应满足的条件，若

18、不满足，则操作失败，并返回相应出错信息。操作结果 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。ADT Triplet 数据对象：D= e1,e2,e3|e1,e2,e3ElemSet (定义了关系运算的某个集合) 数据关系：R1=, 基本操作： InitTriplet( &T,v1,v2,v3) 操作结果：构造了三元组T，元素e1,e2和e3分别被赋以参数 v1，v2 和 v3 的值。 DestroyTriplet( &T) 操作结果：三元组T被销毁。 Get(T,i,&e) 初始条件：三元组已存在，i=3. 操作结果：用e返回的第i元的值例1-6 抽象

19、数据类型三元组的定义： Put(&T,i,e) 初始条件：三元组已存在，i 操作结果：改变的第i元的值为eIsAscending(T) 初始条件：三元组已存在 操作结果：如果的个元素按升序排列，则返回，否则返回IsDescending(T) 初始条件：三元组已存在 操作结果：如果的个元素按降序排列，则返回，否则返回Max(T,&e) 初始条件：三元组已存在 操作结果：用e返回的个元素中的最大值ADTTriplet例如，定义抽象数据类型“复数” 数据对象： De1,e2e1,e2RealSet 数据关系： R1 | e1是复数的实数部分, | e2 是复数的虚数部分 ADT Complex 基本

20、操作：AssignComplex( &Z, v1, v2 ) 操作结果：构造复数 Z,其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex( &Z) 操作结果：复数Z被销毁。 GetReal( Z, &realPart ) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。 GetImag( Z, &ImagPart )初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add( z1,z2, &sum )初始条件：z1, z2是复数。操作结果：用sum返回两个复数z1, z2 的和值。 ADT Complex多形数据类型是指其值的成分

21、不确定的数据类型。例如，例1-6中定义的抽象数据类型Triplet，其元素e1、e2和e3可以是整数或字符或字符串，甚至更复杂的由多种成分构成。然而，元素之间的关系相同，基本操作也相同，从抽象数据类型的角度看，具有相同的数学抽象特性，故称之为多形数据类型。1.3 抽象数据类型的表示和实现抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。以下对类C语言的描述作简要说明。（1）预定义常量和类型/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#defin

22、e OVERFLOW -2Typedef int Status; /Status是函数的类型，其值是函数结果状态代码（2）数据结构的表示（存储结构）用类型定义（typedef)描述。数据元素类型约定为ElemType,由用户在使用该数据类型时自行定义。（注意define与typedef的区别）函数类型 函数名（函数参数表） / 算法说明 语句序列 / 函数名除了函数的参数需要说明类型外，算法中使用的辅助变量可以不作变量说明，必要时对其作用给予注释。一般而言，a、b、c、d、e等用作数据元素名，i、j、k、l、m、n等用作整形变量名，p、q、r等用作指针变量名。当函数返回值为函数结果状态代码时，

23、函数定义为Status类型。为了便于算法描述，除了值调用方式外，增添了C+语言的引用调用的参数传递方式。在形参表中，以&打头的参数即为引用参数。（3）基本操作的算法都用以下形式的函数描述：简单赋值 变量名=表达式；串联赋值 变量名 1=变量名2=变量名k=表达式；成组赋值 （变量名1，变量名k）=（表达式1， ，表达式k）； 结构名=结构名； 结构名=（值1，值k）； 变量名 =表达式； 变量名起始下标.终止下标=变量名起始下标.终止下标；交换赋值 变量名 变量名；条件赋值 变量名=条件表达式？表达式T：表达式F；（4）赋值语名有条件语句1 if (表达式) 语句；条件语句2 if (表达式)

24、 语句； else 语句；开关语句1 switch （表达式） case值1: 语句序列1；break; case 值n：语句序列n;break ; default; 语句序列n+1； 开关语句2 switch case 条件1：语句序列1;break; case 条件n：语句序列n;break ; default:语句序列n+1； （5）选择语句有for语句 for（赋初值表达式序列；条件；修改表达式序列）语句；while语句 while（条件）语句； do-while语句 do 语句序列； while（条件）；（7）结束语句有函数结束语句 return 表达式； return; case结

25、束语句 break;异常结束语句 exit（异常代码）；（6）循环语句有（8）输入和输出语句有输入语句 scanf（格式串，变量1，变量n）；输出语句 printf （格式串，表达式1，表达式n）；通常省略格式串。（9）注释单行注释 / 文字序列（10）基本函数有求最大值 max（表达式1，表达式n)求最小值 min（表达式1，表达式n） 求绝对值 abs（表达式）求不足整数值 floor（表达式）求进位整数值 ceil （表达式）判定文件结束 eof（文件变量）或eof判定行结束 eoln（文件变量）或eoln(11)逻辑运算约定 与运算&：对于A&B，当A的值为0时，不再对B求值。 或运算

26、|：对于A|B，当A的值为非0时，不再对B求值。例1-8 抽象数据类型Triplet的表示和实现。 /- - - - 采用动态分配的顺序存储结构- - - - - typedef ElemType *Triplet; / 由InitTriplet分配3个元素存储空间/- - - - 基本操作的函数原型说明- - - - - Status InitTriplet (Triplet &T, ElemType v1, ElemType v2, ElemType v3); /操作结果：构造了三元组，元素e1,e2和e3分别被赋以参数 v1，v2 和 v3 的值。 Status DestroyTripl

27、et ( Triplet &T); /操作结果：三元组T被销毁。Status Get ( Triplet T , int i , ElemType &e); /初始条件：三元组已存在，=i=3. /操作结果：用e返回的第i元的值Status Put (Triplet &T , int i , ElemType e); /初始条件：三元组已存在，=i= /操作结果：改变的第i元的值为e Status IsAscending (Triplet T); / 初始条件：三元组已存在 / 操作结果：如果的个元素按升序排列，则返回，否则返回Status IsDescending (Triplet T);

28、/ 初始条件：三元组已存在 / 操作结果：如果的个元素按降序排列，则返回，否则返回Status Max (Triplet T, ElemType &e) / 初始条件：三元组已存在/ 操作结果：用e返回的个元素中的最大值Status Min (Triplet T, ElemType &e) / 初始条件：三元组已存在 / 操作结果：用e返回的个元素中的最小值/- - - - 基本操作的函数原型说明- - - - -Status InitTriplet (Triplet &T, ElemType v1, ElemType v2, ElemType v3) /构造了三元组，依次置T的三个元素的初值

29、 v1，v2 和 v3 T=(ElemType *) malloc(3 *sizeof (ElemType ); /分配三个元素的存储空间 if (!T) exit ( OVERFLOW ) ; /分配存储空间失败 T0=v1; T1=v2; T2=v3; return OK; / InitTriplet Status DestroyTriplet ( Triplet &T) /销毁三元组T。 free ( T ); T = NULL; return OK; / InitTripletStatus Get ( Triplet T , int i , ElemType &e) /1=i=3,用e

30、返回的第i元的值 if ( i3 ) return ERROR; e = Ti-1; return OK; / GetStatus Put (Triplet &T , int i , ElemType e) /1=i=3,置的第i元的值为e if ( i3 ) return ERROR; Ti-1 = e; return OK; / PutStatus IsAscending (Triplet T) / 如果的个元素按升序排列，则返回，否则返回 return ( T0 =T1)& T1 =T1)& T1 =T2); / IsDescendingStatus Max (Triplet T, El

31、emType &e) / 用e返回的个元素中的最大值e = ( T0 =T1)?( T0 =T2)? T0 :T2):(T1 =T2)? T1 :T2);return OK; / MaxStatus Min (Triplet T, ElemType &e) / 用e返回的个元素中的最小值e = ( T0 =T1)?( T0 =T2)? T0 :T2):(T1 =T2)? T1 :T2);return OK; / Min 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。一个算法必须满足以下五个重要特性：1有穷性 2确定性 3可行性4有输入 5有输出1.4

32、.1 算法1.4 算法和算法分析 1有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。 2确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径，不允许有二义性。 例如下面这句话：张三对李四讲，他的儿子考上了大学。 确切含义？ 3可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。 4有输入 一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。 5有输出 它是一组与“输入”有确定关系的量值，是算法进行

33、信息加工后得到的结果，这种确定关系即为算法的功能。1.4.2 算法设计的要求 设计算法时，通常应考虑达到以下目标：1正确性2. 可读性3健壮性4高效率与低存储量需求1正确性 首先，算法应当满足以特定的“规格说明”方式给出的需求。 其次，对算法是否“正确”的理解可以有以下四个层次：a程序中不含语法错误； b程序对于几组输入数据能够得出满足要求的结果； c程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果； d程序对于一切合法的输入数据都能得出满足要求的结果； 通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。2. 可读性 算法主要是为了人的阅读与交流，其次才

34、是为计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。3健壮性 当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。4高效率与低存储量需求 通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。1.4.3 算法效率的度量 通常有两种衡量算法效率的方法: 事后统计法事前分析估算法缺点：1必须执行程序 2其它因素掩盖算法本质 一个用高级语言编写的程序在计算机上运行时所

35、消耗时间取决于下列因素：1算法选用的策略2问题的规模3编写程序的语言4编译程序产生的机器代码的质量5计算机执行指令的速度一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 撇开与计算机硬件、软件有关的因素，可以认为一个特定算法 “运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模

36、的函数。 一般情况下，算法中基本操作重复执行的次数是问题规模 n 的某个函数f(n)，算法的时间度量记作 T(n) = O(f(n) 它表示随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，称作算法的(渐近)时间复杂度（Asymptotic Time Complexity）。算法 = 控制结构 + 原操作 （固有数据类型的操作）算法的执行时间 =原操作(i)的执行次数原操作(i)的执行时间 算法的执行时间与 原操作执行次数之和成正比 如何估算算法的时间复杂度？ 从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法中重复执行的次数 作为算法运行

37、时间的衡量准则。(c) for(j=1;j=n;+j) for(k=1;k=n;+k) +x;s+=x; 语句频度： n2 T(n)=O(n2) 平方阶+x;s=0; 语句频度：1 T(n)=O(1) 常量阶(b) for(i=1;i=n;+i) +x;s+=x; 语句频度：n T(n)=O(n) 线性阶例：两个矩阵相乘void mult(int a, int b, int& c ) / 以二维数组存储矩阵元素，c 为 /a 和 b 的乘积 for (i=1; i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (k=1; k=n; +k) ci,j += ai

38、,k*bk,j; /for /mult基本操作: 乘法操作时间复杂度: O(n3)选择执行次数最多增长最快的一个原操作，一般是最内层的循环例1 求下列算法段的语句频度for(i=1; i=n; i+)for(j =1; j =i ; j+)x=x+1;分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环有关，因些，时间频度T(n)=1+2+3+n= 例1.2 分析以下程序段的时间复杂度for (i=1;in;i+) y=y+1; for (j=0; j=(2*n); j+)x+; /* 1 * /* 2 * /分析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。语句1的频度是：n-1语句2的频度是：则该程序段的时间复杂度：T(n)=例1.3 分析以下程序段的时间复杂度i=1;while (i=n) i=i*2语句1的频度是：1设语句2的频度是f(n)，则有：即 取最大值,则该程序段的时间复杂度为：/* 1 * /* 2 * /例1.4x=1;for (i=1;i=n;i+) for (j=1;j=i;j+) for