C语言数据结构基础学习笔记——C语言基础

抽象数据类型（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次，则2^k<=n即k<=log₂n。所以其时间复杂度为o(log₂n)。

对于多个循环体，时间复杂度的计算具有加法规则和乘法规则。

例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(n²)，这是时间复杂度计算的加法规则。

例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(nlog₂n)，这是时间复杂度计算的乘法规则。

对于常见的时间复杂度，从左至右，时间性能依次降低：

o(1)<o(log₂n)<o(n)<o(nlog₂n)<o(n²)<o(n³)<o(2ⁿ)