数据结构：算法时间复杂度

数据结构

image-20250330164232582

image-20250330164410787

虚拟内存地址

内存条、显卡、各种适配卡都有其各自的存储地址空间。
操作系统将这些设备的存储地址空间抽象成一个巨大的一维数组空间。
对于内存的每一个字节会分配一个32位或64位的编号，这个编号称为内存地址。

类型定义

C程序编译后，会以三种形式使用内存：

静态全局内存

静态声明的变量和全局变量使用这部分内存，这些变量在程序开始运行时
分配，直到程序终才消失。

自动内存（栈内存)

函数内部声明的变量使用这部分内存，在函数被调用时才创建。

动态内存（堆内存)

根据需求编写代码动态分配内存，可以编写代码释放，内存中的内容直到
释放才消失。

在C语言中，我们需要使用malloc函数实现动态分配内存，他会从堆内存中选取一片空间，并返回这片空间的指针。该函数传入的参数是需要的空间体积。

完了需要使用free来释放内存

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char const *argv[]) {
    char *s;
    s = (char*)malloc(6 * sizeof(char)); 
    strcpy(s, "Hello"); 
    printf("%s\n", s);  
    free(s);         
    return 0;
}

为了避免计算错误，我们通常使用sizeof操作符来确保分配的内存大小正确。

时间复杂度

也称渐近时间复杂度，T(n)=O(f(n))
随着问题规模n的增大，算法执行时间和增长率和f(n)增长率成正比。

程序运行的总时间主要与两点有关，执行每条语句的耗时和每条语句的执行效率

由于语句的执行要由源程序翻译成目标代码，目标代码经装配再执行，因此语句执行一次实际所需的具体时间是与机器的软、硬件环境（如机器速度、编译程序质量等)密切相关的。所以，所谓的算法分析并非实际执行所需时间，而是针对算法中语句的执行次数做出估计，从中得到算法执行时间的信息。

时间频度

时间频度并不是单纯指循环执行次数或条件判断次数，而是指算法中某个基本操作的总执行次数。具体来说：

  • 如果基本操作是循环体内的计算，时间频度就是循环体的执行次数。
  • 如果基本操作是条件判断，时间频度就是条件判断的执行次数。
  • 如果基本操作是某种组合操作（如循环和判断的组合），时间频度就是这些操作的总执行次数。

image-20250331141248103

计算频度指的是代码执行的次数，最外层循环需要在执行n次之后在做一次 (i == n)的判断，所以执行频度为n+1，但是外层循环在最后一次判断不会通过，所以内层第一循环不会执行，所以内层循环为n次。

1.png

所以，F(n) = 各层循环的计算频度的和。取得n的最高次幂为M

image-20250331143101268

上述代码中如果n == 0，那么只会进行一次判断，所以 F(n) = 1，T(n) = O(1)

如果n很大很大，时间复杂度为1。

最好时间复杂度：算法在最好情况下的时间复杂度。
最坏时间复杂度：算法在最坏情况下的时间复杂度。
平均时间复杂度：算法在所有可能的情况下，按照输入实例以等概率出现时，算法计
量的加权平均值。
对算法时间复杂度的度量，通常只讨论算法在最坏情况下的时间复杂度，
即分析在最坏情况下，算法执行时间的上界。

对数的时间复杂度

image-20250331144619221

空间复杂度

空间复杂度主要用来描述某个算法对应的程序想在计算机上执行，除了用来存储代码和输入数据的内存空间外，还需要额外的空间。

抽象数据类型 ADT

ADT是一种编程概念，用于定义数据的类型及其操作，而不涉及具体实现细节。它提供了一种将数据的逻辑表示与物理实现分离的方法，从而使程序更具可维护性和可扩展性。
在C语言中，ADT通常通过结构体和函数的结合来实现。结构体用于定义数据的类型，而函数用于操作这些数据。通过这种方式，程序员可以隐藏数据的内部结构，仅暴露出操作数据的接口。

说白了，就是java当中的抽象类，是C++ 中的自定义类。