【数据结构】1. 时间/空间复杂度

- 第 95 篇 -
Date: 2025 - 05 - 09
Author: 郑龙浩/仟墨
【数据结构 】

数据结构 - 1 -

了解数据结构与算法

1 什么是数据结构

官方: 数据结构(Data Structure)是计算机科学中存储、组织和管理数据的方式，它使得数据可以高效地访问和修改。

大白话: 数据结构就是高效存储和管理数据的方法，学习它就是为了更快地

• 查找数据
• 插入新数据
• 删除旧数据
• 修改已有数据
• …

2 什么是算法

• 算法和数据结构是不分家的，他们两个经常合起来去说。
• 而算法就是对数据的处理。
• 比如: 动态规划(DP)，排序，DFS(深搜)，BFS(广搜)，二叉树，红黑树…

3 数据结构的重要性？

• 考研必考(408之一) – 很重要
• 面试笔试的时候，数据结构与算法占比很大，大厂技术面试约占占比70%以上
• 学会数据结构，可以有效的提升程序的效率

一 时间复杂度_空间复杂度

复杂度是用来分析写的程序的运行的时间和空间的占用情况

说白了就是分析这个程序性能的

如果单纯的去在电脑上运行程序去看运行时间的多少来确定时间的话，是不正确的，比如一台8核16g的的电脑与一台2核4g的电脑，同一个程序，运行时间肯定不同，抛开设备去谈性能，就是耍流氓。

在做题的时候程序经常会超时，而如果会看时间复杂度和空间复杂度的话，可以在测试之前有效的节省时间，提高效率，很有用！

现代的计算机除了嵌入式以外基本上已经不关注空间了，因为现在的内存很大了。

1 时间复杂度

算法的时间复杂度是一个函数(数学中的函数，不是程序中的函数)，算的不是时间，算的是程序的执行次数

① 表示方法

使用大 O 符号: 描述函数渐进行为的数学符号

可以说是就是一种估算，上边的式子可以写成 O(N^2)

② 推导大 O 的规则:

• 如果项为常数，则用 1 替代

• 只保留次数函数的最高阶项 –> 其他项去掉，对整个结果的影响不是很大，所以可以忽略，只保留影响最大的项

• 如果最高阶项的系数是非1，那么要把系数变为1

  Eg: F(N) = 2N^4 + N –> O(N^4)

• 当程序复杂， 有最好最坏的不同的复杂度的时候，取最坏的复杂度，如下面的Eg4 Eg5

③ **代码示例 **

Eg 1

复杂度为: O(N^2)

// 请计算一下Func1基本操作执行了多少次？
void Func1(int N)
{
int count = 0;
// 执行次数: N^N == N^2
for (int i = 0; i < N ; ++ i) {for (int j = 0; j < N ; ++ j) {++count;}
}
// 执行次数: 2 * N
for (int k = 0; k < 2 * N ; ++ k) {++count;
}
// 执行次数: 10
int M = 10;
while (M--) {++count;
}
printf("%d\n", count);
}

所以不同的代码段加起来，Func1 总的执行的基本操作次数为: F(N) = N^2 + 2 * N + 10

实际计算时间复杂度的时候，不需要进行精确计算执行次数，只需要看出大概执行次数即可

Eg 2

// 计算Func2的时间复杂度？
// O(N)
void Func2(int N) {int count = 0;for (int k = 0; k < 2 * N; ++k) {++count;}int M = 10;while (M--) {++count;}printf("%d\n", count);
}

Eg 3

// 计算Func3的时间复杂度？
// O(N + M)
// 如果题目明确说，N > M，那么就是 O(N)
void Func3(int N, int M) {int count = 0;for (int k = 0; k < M; ++k) {++count;}for (int k = 0; k < N; ++k) {++count;}printf("%d\n", count);
}

Eg 4

// 计算Func4的时间复杂度？
// O(1)
void Func4(int N) {int count = 0;for (int k = 0; k < 100; ++k) {++count;}printf("%d\n", count);
}

Eg 5

• 最好的情况: 第一个就找到了 复杂度为: O(1)
• 平均的情况: 在中间找到: O((1/2) * N) --> 但是 1/2 通常被忽略
• 最坏的情况: 在最后一个找到: O(N)
• 取最坏的情况

// 计算strchr的时间复杂度？
// O(N)
// 查找 ch
const char *strchr(const char *str, char ch) {while (*str != '\0') {if (*str == ch)return str;++str;}return NULL;
}

Eg 6

• 外层循环 n 次，内层每次循环 n - 1 次，所以构成了等差数列
• 第一层:n - 1次，第二层n - 2次，第三层n - 3次…最后1次 --> d 为 1 的等差数列
• 根据等差数列公式得出: F(N) = (n(n-1)) / 2 --> n^2/2 - n/2
• 最坏的时间复杂度: O(N^2) --> 数组逆序的时候
• 最好的时间复杂度: O(n) --> 数组有序
• 空间复杂度: O(1) --> 原地排序，空间很小

// 冒泡排序
// 计算BubbleSort的时间复杂度？
void BubbleSort(int *a, int n) {assert(a);for (size_t end = n; end > 0; --end) {int exchange = 0;for (size_t i = 1; i < end; ++i) {if (a[i - 1] > a[i]) {Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

Eg 7

这个就有点复杂了，首先来看，查找了多少次呢？？

每次查找都除以2，直到找到为止，如下所示

• 第 1 次：搜索范围 = n
• 第 2 次：搜索范围 = n / 2
• 第 3 次：搜索范围 = n / 4
• …
• 第 k 次：搜索范围 = n / 2^(k-1)

最坏情况终止条件是搜索范围 <=1，也就是

n / 2^(k-1) <= 1 --> n <= 2^(k-1) * 1 --> k-1 >= log2(N) --> k >= log2(n) + 1

• 因此，最多需要 log2(n) + 1 次比较

// 计算BinarySearch的时间复杂度？
// O(log N)
int BinarySearch(int *a, int n, int x) {assert(a);int begin = 0;int end = n;while (begin < end) {int mid = begin + ((end - begin) >> 1);if (a[mid] < x)begin = mid + 1;else if (a[mid] > x)end = mid;elsereturn mid;}return -1;
}

Eg 8

n 的阶乘就是从 n 乘到 1，而这个过程中，无非就是乘了n次，所以复杂度也是 O(N) 了

也就是递归了n次或者循环了n次

// 计算阶乘递归Factorial的时间复杂度？
// 阶乘
// 时间复杂度: O(N)
// 空间复杂度: O(N)
// 递归版
long long Factorial(size_t N) { return N < 2 ? N : Factorial(N - 1) * N; 
}
// 时间复杂度: O(N)
// 空间复杂度: O(1)
// 迭代版
long long Factorial(size_t N) {long long result = 1;for (size_t i = 1; i <= N; ++i)result *= i;return result;
}

Eg 9

动手画二叉树可以助于理解

第1层: fib(n) // --> 次数2^0
第2层: fib(n-1)               fib(n-2) // --> 次数 2^1
第3层: fib(n-2) fib(n-3)      fib(n-3) fib(n-4) // --> 次数 2^2
...
第n层: // --> 次数 2^(n-1)

将每一层的次数放到一个序列里面，可以构成一个等比数列，q为2

根据等比公式，得出2^n - 1

2^0 + 2^1 + 2^2 + ... + 2^(n-1) ==> 2^n - 1 ----> O(2^n)

// 计算斐波那契递归的时间复杂度?
// O(2^n)
int Fibonacci(int n) {if (n <= 1) {return n;  // 基本情况：F(0)=0, F(1)=1}return Fibonacci(n - 1) + Fibonacci(n - 2);  // 递归调用
}

2 空间复杂度

① 介绍:

空间复杂度不计算空间， 而是粗略计算定义的变量个数

除了嵌入式开发，一般不太在乎空间复杂度，因为嵌入式是在设备上，如果那个设备放内存条的空间很小，导致内存很小，这样的话就要优化空间复杂度

表示方法dz

与时间复杂度一样，用 O() 表示

推导大 O 的方法

• 空间是看的变量或固定大小的数组的个数

• 如果大小是常数，则用 1 代替

• 只保留最高阶项(只保留对空间影响最大的项)

  • 如果最高的项系数为非1，则将系数变为1

  Eg: F(N) = 3N + 4 --> O(N)

• 递归会占用栈空间，需要根据递归深度和每层的分配的额外空间计算

• 当空间在不同的情况下不同时，有最好和最坏复杂度，取最坏的复杂度

• 动态分配的孔吉纳需要根据实际占用计算 –> 动态数组，哈希表

  Eg: 生成一个大小为 N 的动态数组 –> O(N)

② 代码示例

参数，第一个为指针，第二个为变量，所以算作两个
后边总共定义了3个变量

总共加起来才5个，所以空间复杂度为 O(1)

// 冒泡排序
// 计算BubbleSort的空间复杂度？
void BubbleSort(int *a, int n) {assert(a);for (size_t end = n; end > 0; --end) {int exchange = 0;for (size_t i = 1; i < end; ++i) {if (a[i - 1] > a[i]) {Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}