如何对代码进行复杂度分析？（数据结构和算法）

hello 大家好

我是浩说

今天来偷摸学习一下 ：

如何对代码进行复杂度分析？（数据结构和算法）

视频版 - 看着更方便：

哔哩哔哩（横板）👉 https://b23.tv/EZUqDrF

小红书（竖版）👉 http://xhslink.com/lHiv7h

复杂度分析 是 数据结构和算法 中非常重要的知识点

你在看 数据结构和算法 相关内容的时候应该经常会看到像：

时间复杂度O(1)

O(n)

这样的字眼

复杂度是 用来衡量一个算法 的时间效率和空间利用率的依据

它能帮你判断哪些算法效率更高？

哪些算法更节省内存空间？

我们以一段代码为例 看看如何分析 时间复杂度

int sum = 0;
int i = 1;
int j = 1;

假设每条语句需要花费 一个时间单位

那么上面这段代码花费的时间 T = 3；

现在将代码补充一下，增加一层for循环

int c(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
}
}

这个for循环需要花费n个时间单位

于是 T = n +3;

我们转换成O时间复杂度表示法就是：

T = O(n + 3)；

这里的O表示 代码的执行时间 随着 数据规模增长 的 变化趋势

也就是说 当for循环中的n接近无限大的时候，后面的常量3就可以忽略不计了

所以这段代码最终的时间复杂度就是

O(n)

而最初的三行代码的时间复杂度就是

O(1)

这里的1并不是说一行代码

它的意思是代码的执行时间是常量级别的

不存在 循环、递归那种带有未知执行量的情况

所以这样的代码即便有成千上万行，由于执行时间是常量级别

所以时间复杂度依然是 O(1)

到这里

关于复杂度的基本概念我们已经有所了解

那么接下来 时间复杂度的分析技巧

首先

由于复杂度指的是一种变化趋势

所以常量级代码和系数都可以忽略不计

只关注循环执行次数最多的部分即可

比如下面这段代码中 两次循环带来的系数3

和常量级代码都可以忽略

2n + 3

最终的时间复杂度为 O(n)

int c(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (i; i <= n; ++i) {
}
for (j; j <= n; ++j) {
}
}

第二点

嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

比如这个嵌套循环

时间复杂度就等于内外两层循环的乘积

也就是O(n方)

int c(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (i; i <= n; ++i) {
  for (j; j <= i; ++j) {
  }
}
}

第三点

当代码中同时存在 常量级代码、循环以及嵌套循环

那么代码的最终复杂度取执行次数最多的

也就是嵌套循环的复杂度

O(n方)

最后

这些是常见的时间复杂度

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

以及时间复杂度的对比图

横向表示代码量 纵向表示执行时间

我是浩说 | 用娱乐的方式说编程 | 点赞关注！！！