C语言 | 数据结构——数据类型与算法

r囧r小猫 2024-04-01 09:55 53阅读 0赞

**目录**

数据结构

抽象数据类型

算法(Algorithm)

定义

判断算法的指标

1.空间复杂度S(n)

2.时间复杂度T(n)

复杂度分析：

编辑

--------------------

## 数据结构 ##

数据对象在计算机中的组织方式，数据对象必定与一系列加在其上的操作相关联

⬆⬆⬆⬆⬆⬆完成这些操作所用的方法就是算法⬆⬆⬆⬆⬆⬆

## 抽象数据类型 ##

拆分成“抽象”与“数据类型”

**抽象**：即描述数据类型的方法不依赖于具体实现（只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题）

1.  与存放数据的机器无关
2.  与数据存储的物理结构无关
3.  与实现操作的算法均无关
4.  与实现操作的编程语言无关

**数据类型***(Abstract Data Type)*

1.  *数据对象集*
2.  *数据集合相关联的操作集*

![de78968c25504742b65783600ce4763d.jpeg][]

## 算法(Algorithm) ##

### 定义 ###

*  **一个有限指令集**
 *  **接受一些输入(有些情况下不需要输入)**
 *  **产生输出**
 *  **一定在有限步骤之后终止**
 *  **每一条指令必须**
    
     *  有充分明确的目标，不能有歧义
     *  在计算机能处理的范围只能
     *  描述应不依赖于任何一种计算机语言以及具体的实现手段

### 判断算法的指标 ###

#### 1.空间复杂度S(n) ####

根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断

#include <stdio.h>
    
    void PrintN(int N)
    {
        if(N){
            PrintN(N-1);
            printf("%d\n",N);
        }
        return;
    }
    
    int main()
    {
        int i;
        scanf("%d",&i);
        PrintN(i);
        return 0;
    }

**递归中**，要打印N个数，此时空间复杂度: **S(N) = C\*N**

即占用的空间与要输出的N个数成正比，当N过大，程序可用空间有限，此时就会爆掉

我们可以测试一下，输出10000和100000，很明显，后者直接报错，内存爆了

![367753af609f48d59dd7a74301683ee4.png][]

![fe1a18d0d78c4592ad1f643c06d8531c.png][]

#### 2.时间复杂度T(n) ####

根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。

在计算机中，做加减法的速度要比乘除法快，在下面两种写法不同的函数，前者的乘法运算更多，也更呆，所以消耗的时间也更多

前者的时间复杂度为 **T(n)=C1 \* n\*n+C2 \* n**

后者的时间复杂度为 **T（n）=C\*n**

double f(int n, double a[], double x)
    {
        int i;
        double p = a[0];
        for (i = 1;i<=n; i++)
            p+=(a[i]* pow(x,i));
        return p;
    }

double f(int n, double a[], double x)
    {
        int i;
        double p = a[n];
        for (i = n;i>0; i--)
            p = a[i-1]+x*p;
        return p;
    }

在分析一般算法效率时，我们经常关注下面的两种复杂度

1.  最坏情况复杂度**Tworst(n)**
2.  平均复杂度**Tavg(n)**

**Tavg(n)<=Tworst(n)**

#### 复杂度分析： ####

#### ![7ec938619db54c11924e18c5a2e5a770.png][] ####

for循环的时间复杂度等于循环次数乘以循环体代码的复杂度

if-else结构的复杂度取决于if的条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者最大

[de78968c25504742b65783600ce4763d.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/0222f587a8f947ae9e66d6235361d881.jpeg
[367753af609f48d59dd7a74301683ee4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/21397e6fbfff40378490db9b764646ef.png
[fe1a18d0d78c4592ad1f643c06d8531c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/008a28920b5c48c4b3b22bbf8065c8ab.png
[7ec938619db54c11924e18c5a2e5a770.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/879be5d69c1048ee9ce60dccc3b9ba79.png