+
+
Posts List
  1. 为什么需要复杂度分析
  2. 大O复杂度表示法
  3. 时间复杂度分析
    1. 1. 只关注循环次数最多的一段代码
    2. 2. 总复杂度等于量级最大的那段代码的复杂度
    3. 3. 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
  4. 常见的几种时间复杂度
    1. O(1)
    2. O(logn) 与 O(nlogn)
    3. O(m+n)、O(m*n)
  5. 空间复杂度分析
  6. 课后思考
  7. 文末推广

数据结构与算法之美:复杂度分析基础(上)

本文为学习「即刻时间」栏目《数据结构与算法之美》03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?所做笔记。

此专栏的邀请海报放在本文末尾,如果有兴趣加入学习,可以扫描海报上的二维码,我也将获得一定金额的返利。

为什么需要复杂度分析

通过事后统计法得到的算法执行时间和占用内存大小存在弊端:

  1. 依赖测试环境
  2. 受数据规模影响大

大O复杂度表示法

代码的执行时间$T(n)$与每行代码的执行次数$n$成正比。
这个规律表示为:

大O时间复杂度并不具体代表代码真正的执行时间,而是代表代码执行时间随数据规模增长的变化趋势,也叫做渐近时间复杂度,简称时间复杂度

当n很大时,公式中的低阶项可以忽略,只需要记录一个最大量级。

时间复杂度分析

1. 只关注循环次数最多的一段代码

1
2
3
4
5
const sayHello = function (n) {
var i = 0;
for (; i < n; i++)
console.log('Hello')
};

其中第2行代码是常量级的执行时间,第4行和第5行代码执行次数与n成一次关系,因此第2行代码的执行时间可以忽略,总的时间复杂度为$O(n)$。

2. 总复杂度等于量级最大的那段代码的复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const sayABC = function (n) {
var i = 0;
for (; i < 100; i++)
console.log('A')

i = 0;
for (; i < n; i++)
console.log('B')

i = 0;
var j = 0
for (; i < n; i++)
for (; j<n; j++)
console.log('C')
};

可以看到代码由三部分组成,第一部分输出100次A,第二部分输出n次B,第三部分输出$n^2$次C,那么总的时间复杂度就等于量级最大的$O(n^2)$。

这一段原标题是「加法法则」,然而内容明显是求Max,故删去”加法法则”字样。

3. 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

1
2
3
4
5
i = 0;
var j = 0
for (; i < n; i++)
for (; j<n; j++)
console.log('C')

截取sayABC()函数的第三部分,这个两层循环可以看作$n\times n$,因此时间复杂度为$O(n^2)$。

常见的几种时间复杂度

对于以上的复杂度量级,可以分为两类:

  • 多项式量级(图中左列)
  • 非多项式量级(图中右列)

这里的「多项式量级」不同于「多项式」

时间复杂度为非多项式量级的算法问题叫做NP(非确定多项式)问题。也就是说,当n越来越大,非多项式量级算法的执行时间会急剧增加,执行时间急剧增长,因此被认为是非常低效的算法。(低效所以就不讲了)

O(1)

$O(1)$ 只是常量级时间复杂度的一种表示方法,并不是只执行了一次。

1
2
3
var a = 1;
var b = 2;
var c = a+b;

比如这段代码,即使有3行,它的时间复杂度也是$O(1)$。

一般情况下,只要算法中不存在循环语句、递归语句,即使有成千上万行代码,其时间复杂度也是$O(1)$。

O(logn) 与 O(nlogn)

对数阶时间复杂度非常常见,同时也是最难分析的一种时间复杂度。

1
2
3
4
var i=0;
while (i<n) {
i *= 2;
}

在上面的代码中,只要能计算出代码循环了多少次,就能知道整段代码的时间复杂度。不难发现,循环变量i的取值是一个等比数列:

所以,我们只要知道x是多少,就知道这行代码执行的次数了,因此只需求解$2^x=n$便能得到$x=\log_2n$。因此,这段代码的时间复杂度就是$O(\log_2n)$,再忽略掉对数的底,即为$O(\log n)$。

为什么对数的底可以忽略呢?这是因为,对数之间可以相互转化$\log_an=\frac{\log_bn}{\log_ba}$,其中的$\log_ba$为常数,我们又知道,大O标记复杂度是忽略系数的,因此无论底取任意值都没有意义,故忽略。

O(m+n)、O(m*n)

当传入两个参数mn且顺序执行循环时,复杂度为$O(m+n)$。
当传入两个参数mn且嵌套执行循环时,复杂度为$O(m*n)$

空间复杂度分析

类比时间复杂度,空间复杂度的全称就是渐进空间复杂度,表示算法的存储空间与数据规模之间的增长关系。

1
2
3
4
5
6
7
8
const sayWhat(n){
var i = 0;
var arr = [];
for (; i<n; i++)
arr[i] = i*i;
for (i = 0; i<n; i++)
console.log(arr[i])
}

在第2行代码中,申请了一个空间存储变量i,为常量阶。第3行代码中,声明了一个数组arr,但还未立即给它赋值,而是通过第4行代码每次循环给它赋值。最后arr的总长度为n,是n的一次项,所以整段代码的空间复杂度是O(n)

我们常见的空间复杂度就是$O(1)$、$O(n)$和$O(n^2)$,像对数阶复杂度平时都用不到。而且,空间复杂度比时间复杂度分析要简单很多。

课后思考

课后思考:

有人说,我们项目之前都会进行性能测试,再做代码的时间复杂度、空间复杂度分析,是不是多此一举呢?而且,每段代码都分析一下时间复杂度和空间复杂度,是不是浪费时间呢?你怎么看待这个问题呢?

  1. 如果是先做性能测试再做复杂度分析的话,复杂度分析有必要,因为性能测试依赖测试环境并且受数据规模影响很大,复杂度分析可以得到一个通用的结果。如果是先做复杂度分析再做性能测试,也有必要,因为实践是检验真理的唯一标准,并且项目最终的目的都是为了落地。

  2. 经过老师这堂课的讲解,复杂度分析并不需要大规模的计算,很多时候瞄一眼就看出来了。即便是代码量很大,也可以通过「分治」的思想,将多段代码结合到一起分析,求出总的时间复杂度。因此并不是浪费时间。

文末推广

如果觉得我的博客帮助了你,并且想深入学习数据结构与算法,可以扫描下方二维码加入学习,我将获得一定金额的返利。

43A533147CA691AC31B02A2DE7CAF79C

本文作者: rhinoc

本文链接: https://www.rhinoc.top/cid216_2/

版权声明: 本博客所有文章除特别声明外,均采用BY-NC-SA 4.0国际许可协议,转载请注明。

打赏
Love U 3000
  • Through WeChat
  • Through Alipay