C++算法

数据结构与算法复杂度详解

介绍数据结构和算法的重要性，重点讲解时间复杂度和空间复杂度的概念及计算方法。通过大 O 渐进表示法分析算法效率，涵盖常数阶、线性阶、对数阶及平方阶等常见复杂度示例。同时结合轮转数组案例，展示如何通过空间换时间或优化算法降低复杂度，达到快和省的目标。

战神发布于 2026/3/23更新于 2026/4/1813K 浏览

数据结构与算法复杂度详解

算法复杂度示意图

算法效率动图

1. 算法复杂度

1.1 数据结构

数据结构 (Data Structure) 是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用，所以要学各式各样的数据结构，如：线性表、树、图、哈希等。

1.2 算法

算法 (Algorithm): 就是定义良好的计算过程，它取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

1.3 二者的重要性

研究算法和数据结构的最终目的就是为了'快'和'省'，快是指速度快，省是指耗费的内存等硬件资源少。而讨论数据结构和算法，必然涉及复杂度分析。包括时间复杂度分析和空间复杂度分析。

随着信息技术的快速发展，如今空间已不再稀缺，64G, 128G, 256G 已然平常，甚至还有 1TB。但是，这是否意味着我们可以不在乎空间复杂度呢？肯定不是。

小引：摩尔定律

集成电路上可以容纳的晶体管数目在大约每经过 18 个月到 24 个月便会增加一倍。换言之，处理器的性能大约每两年翻一倍，同时价格下降为之前的一半。

2. 算法效率

如何衡量一个算法的好坏呢？

案例引入：轮转数组

轮转数组问题

轮转数组示例

代码实现：

代码实现截图

代码实现造成结果:

运行结果截图

可以看见我们跑通了 37 个用例，但是在某一个用例时，超出了时间限制，这是什么原因导致的呢？我们可以看看这题给出的提示

题目提示

如果给出的数组非常大，里面存放了很多的数据，同时要轮转 90 次，这时就会超出时间的限制。那么，如何衡量其好与坏呢？为此我们需要引入复杂度的概念。

复杂度概念

算法在编写成可执行程序后，运行时需要耗费时间资源和空间 (内存) 资源。因此衡量⼀个算法的好坏，⼀般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度主要衡量⼀个算法的运行快慢，而空间复杂度主要衡量⼀个算法运行所需要的额外空间。

3. 时间复杂度

定义：在计算机科学中，算法的时间复杂度是⼀个函数式 T(N)，它定量描述了该算法的运行时间。时间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运行时间呢？

因为程序运行时间和编译环境和运行机器的配置都有关系，比如同⼀个算法程序，用一个老编译器运行编译和新编译器编译，在同样机器下运行时间不同。
同⼀个算法程序，用一个老低配置机器和新高配置机器，运行时间也不同。
并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

这个是我在VS 编译器 x64 位环境下，通过冒泡排序运行 3 次将 100000 排成升序各自所需要的时间，因此我们不去计算程序的运行时间。

运行时间对比

那么算法的时间复杂度是⼀个函数式 T(N) 到底是什么呢？这个T(N) 函数式计算了程序的执行次数。在编译链接过程中，我们知道算法程序被编译后生成二进制指令，CPU 执行这些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执行次数的函数式 T(N)，假设每句指令执行时间基本一样(实际中有差别，但是微乎其微)，那么执行次数时间就是等比正相关，这样也脱离了具体的编译运行环境。执行次数就可以代表程序时间效率的优劣。比如解决⼀个问题的算法 a 程序 T(N) = N，算法 b 程序 T(N) = N^2，那么算法 a 的效率⼀定优于算法 b。

执行次数对比

实际中我们计算时间复杂度时，计算的也不是程序的精确的执行次数，精确执行次数计算起来还是很麻烦的 (不同的一句程序代码，编译出的指令条数都是不⼀样的)，计算出精确的执行次数意义也不大，因为我们计算时间复杂度只是想比较算法程序的增长量级，也就是当 N 不断变大时 T(N) 的差别，上⾯我们已经看到了当 N 不断变大时常数和低阶项对结果的影响很小，所以我们只需要计算程序能代表增长量级的大概执行次数，复杂度的表示通常使用大 O 渐进表示法。

3.1 大 O 表示法

大 O 表示法规则

大 O 表示法推导

什么意思呢？我们以上面Func1 为例，T(N)=N^2+2*N+10。根据大 O 阶第一条规则:只保留最高阶项,O(N)=N^2。

Func1 示例

3.2 时间复杂度示例练习

例 1

例 1 代码

Func2 执行的基本操作次数： T (N) = 2N + 10 根据推导规则第 3 条得出: Func2 的时间复杂度为：O(N)

例 2

例 2 代码

T (N) = M + N 因此：Func2 的时间复杂度为：O(N)

例 3

例 3 代码

T (N) = 100 根据推导规则第 1 条得出 Func2 的时间复杂度为：O(1)

例 4

例 4 代码

strchr 执行的基本操作次数：（1）若要查找的字符在字符串第一个位置，则：T (N) = 1 （2）若要查找的字符在字符串最后的⼀个位置，则：T (N) = N （3）若要查找的字符在字符串中间位置，则：T (N) =N/2 因此：strchr 的时间复杂度分为：最好情况：O(1) 最坏情况：O(N) 平均情况：O(N) 由于大 O 表示法一般表示最坏的情况，即O(N)

例 5

例 5 代码

（1）若数组有序，则：T (N) = N, O(N) （2）若数组有序且为降序，则：T (N) =N ∗ (N + 1)/2, 即 O(N^2) 因此：BubbleSort 的时间复杂度取最差情况为：O(N^2 )

例 6

例 6 代码

当 n=2 时，执行次数为 1 当 n=4 时，执行次数为 2 当 n=16 时，执行次数为 4 假设执行次数为 x，则 2x = n 因此执行次数：x = log n 因此：func5 的时间复杂度取最差情况为：O(log2 n)

提问：那么 log2n,logn,lgn 等有区别吗？是没有区别的，我们要注意的是增长量级，即变化的 n，无论底数为多少，当 n 越来越大时，这个底数对结果的影响是越来越小的，当 n 趋于无穷时，这个影响可以忽略不计，因此上面几种表示方法都是可以的。

例 7

例 7 代码

调用一次 Fac 函数的时间复杂度为 O(1) 而在 Fac 函数中，存在 n 次递归调用 Fac 函数因此：阶乘递归的时间复杂度为：O(n)

算递归的复杂度的万能公式：创建了多少次函数栈帧 (递推了多少次)*单次递归执行的次数。

4. 空间复杂度

空间复杂度也是⼀个数学表达式，是对⼀个算法在运行过程中因为算法的需要额外临时开辟的空间。空间复杂度不是程序占用了多少 bytes 的空间，因为常规情况每个对象大小差异不会很大，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大 O 渐进表示法。注意：函数运行时所需要的栈空间 (存储参数、局部变量、⼀些寄存器信息等) 在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

4.1 空间复杂度示例练习

例 1

例 1 空间

BubbleSort 额外申请的空间有 exchange，end 有限个局部变量，使用了常数个额外空间。 因此空间复杂度为 O(1)。

例 2

例 2 空间

Fac 递归调用了 N 次，额外开辟了 N 个函数栈帧， 每个栈帧使用了常数个空间因此空间复杂度为：O(N)

5. 案例扩展

轮转数组

轮转数组优化

按照思路 1 的方法：经过上面复杂度的学习，我们可以得出其时间复杂度为 O(N^2), 当给的数据过大，轮转次数过多时，势必会造成超过时间限制。

5.1 优化方案 1：采用空间换时间的方法

我们如何将 O(N^2) 的时间复杂度降为 O(N) 呢 (即只嵌套一层循环)?

空间换时间

可以发现这里的空间复杂度为 O(N)，那么是否可以让空间复杂度降为 O(1)，同时又保持时间复杂度为 O(N) 呢？见优化方案 2。

5.2 优化方案 2(优解):

优解步骤 1

优解步骤 2

优解步骤 3

代码看似更复杂了些，但它同时满足了降时间复杂度为 O(N) 和空间复杂度为 O(1)。

结束动图

数据结构与算法复杂度详解