欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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)