C语言数据结构基础学习笔记——C语言基础
程序员文章站
2022-12-28 08:01:55
抽象数据类型(ADT)是指一个数学模型以及定义在该模型上的一组操作,通常用(数据对象,数据关系,基本操作集)这样的三元组来表示抽象数据类型。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合,由逻辑结构、存储结构、数据的运算组成。 数据结构的逻辑结构有线性结构(一对一)、树(一对多)以及图( ......
抽象数据类型(adt)是指一个数学模型以及定义在该模型上的一组操作,通常用(数据对象,数据关系,基本操作集)这样的三元组来表示抽象数据类型。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合,由逻辑结构、存储结构、数据的运算组成。
数据结构的逻辑结构有线性结构(一对一)、树(一对多)以及图(多对多)。
数据结构的存储结构有顺序结构、链式结构、索引结构和散列结构。
数据的运算由运算的定义以及运算的实现构成。
算法有以下五个特性:①有穷性;②确定性;③可行性;④输入;⑤输出。
时间复杂度t(n)=o(f(n)),其计算主要关注循环体的执行次数。
例1:
int sum=0; for(int i=0;i<=n;i++){ sum=sum+i; }
i从0到n一共执行了n+1次,所以其时间复杂度为o(n).
例2:
int sum=0; for(int i=1;i<=n;i=2*i){ sum=sum+i; }
i取值1,2,4,8…,设共循环了k次,则2k<=n即k<=log2n。所以其时间复杂度为o(log2n)。
对于多个循环体,时间复杂度的计算具有加法规则和乘法规则。
例3:
int x=0; for(int i=1;i<=n;i++) x++; for(i=1;i<=n;i++) for(int j=1;j<=n;j++) x++;
设整体的时间复杂度为t(n),第一个循环的时间复杂度为t1(n),第二个循环体的时间复杂度为t2(n)。
则t(n)=t1(n)+t2(n)=max{t1(n),t2(n)}=o(n2),这是时间复杂度计算的加法规则。
例4:
int sum=0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j=2*j){ sum=sum+j; } }
设整体的时间复杂度为t(n),外循环的时间复杂度为t1(n),内循环体的时间复杂度为t2(n)。
则t(n)=t1(n)*t2(n)=o(nlog2n),这是时间复杂度计算的乘法规则。
对于常见的时间复杂度,从左至右,时间性能依次降低:
o(1)<o(log2n)<o(n)<o(nlog2n)<o(n2)<o(n3)<o(2n)