《数据结构与算法之美》学习笔记之复杂度

绝地灬酷狼 2022-03-16 05:54 166阅读 0赞

> 本系列是极客时间中**前 Google 工程师王争《数据结构与算法之美》专栏**的学习笔记，想加强数据结构及算法能力的同学可以直接购买此专栏，[跳转链接在此][Link 1]

复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构与算法的内容基本上就掌握了一半

### 什么是复杂度分析 ###

数据结构和算法解决是**如何让计算机更快时间、更省空间的解决问题**，因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。

> 复杂度描述的是算法执行时间或占用空间与数据规模的增长关系。

### 如何进行复杂度分析 ###

#### 大 O 表示法 ####

##### 来源 #####

**算法的执行时间与每行代码的执行次数成正比，用 T(n) = O(f(n)) 表示**。其中 T(n) 表示算法执行总时间，f(n) 表示每行代码执行总次数，而 n 往往表示数据的规模

##### 特点 #####

以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以常量阶、低阶以及系数实际上对这种增长趋势不产生决定性影响，故在做时间复杂度分析时忽略这些项。

#### 复杂度分析法则 ####

##### 只关注循环执行次数最多的一段代码 #####

在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了

##### 加法法则：总复杂度等于量级最大的那段代码的复杂度 #####

如果 T1(n)=O(f(n)), T2(n)=O(g(n));

那么 T(n) = T1(n) + T2(n) = max(O(f(n)), O(g(n))) = O(max(f(n), g(n)))

##### 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积 #####

可以把乘法法则看成是嵌套循环:

如果 T1(n) = O(f(n)), T2(n) = O(g(n))

那么 T(n) = T1(n) \* T2(n) = O(f(n)) \* O(g(n)) = O(f(n) \* g(n))

##### 总结 #####

1.  单段代码看高频：比如循环
2.  多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度
3.  嵌套代码求乘机：比如递归、多重循环等
4.  多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加

### 常用复杂度级别 ###

1.  多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括， O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2)（平方阶）、O(n^3)（立方阶）
2.  非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括， O(2^n)（指数阶）、O(n!)（阶乘阶）

### 最坏、最好、平均及均摊时间复杂度 ###

#### 最好时间复杂度 ####

代码在最理想的情况下执行的时间复杂度

#### 最坏时间复杂度 ####

代码在最坏情况下执行的时间复杂度

#### 平均时间复杂度 ####

用代码在所有情况下执行的次数加权平均值表示

#### 均摊时间复杂度 ####

在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。**基本上均摊结果就等于低级别复杂度**

### 声明 ###

本文更多是本人学习笔记之用，更多详细的讲解及代码，请查看极客时间专栏[《数据结构与算法之美》][Link 1]

[Link 1]: https://link.juejin.im?target=http%3A%2F%2Fgk.link%2Fa%2F102gi

发表评论取消回复

表情：

评论列表（有 0 条评论，166人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构与算法之空间复杂度

算法的空间复杂度 1. 类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模n的函数。 2....

怼烎@/ 2024年04月17日 20:45/ 0 赞/ 55 阅读

相关数据结构与算法之时间复杂度

算法的时间复杂度 1. 一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(...

比眉伴天荒/ 2024年04月17日 20:45/ 0 赞/ 74 阅读

相关数据结构与算法之美复杂度分析(上)

前言为什么需要复杂度分析大O复杂度表示法如何进行复杂度分析几种常见时间复杂度空间复杂度文章是观看王争老师的数据结构与算

向右看齐/ 2023年09月28日 12:38/ 0 赞/ 99 阅读

相关【数据结构与算法】三 █算法复杂度█ 一时间复杂度

【数据结构与算法】三 █算法复杂度█ 一时间复杂度上一篇文中提到反转 ,并通过一个小的算法实现了功能,当时的数组长度不到10,那么有几个不同的数组,我们怎么来判断算法

小灰灰/ 2022年08月20日 09:25/ 0 赞/ 203 阅读

相关数据结构之算法时间复杂度

想要学会算法时间复杂度，那么就要先弄清楚几个概念。 1. 什么是算法时间复杂度？ 2. 它有什么用呢？ 3. 写法记作 T(n)=O(f(n)) T(n):语句

雨点打透心脏的1/2处/ 2022年05月25日 00:14/ 0 赞/ 237 阅读

相关算法之美1 - 复杂度分析

复杂度时间复杂度和空间复杂度 -------------------- 03 | 复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？ > 一、什么是复

向右看齐/ 2022年03月25日 08:58/ 0 赞/ 171 阅读

相关《数据结构与算法之美》学习笔记之复杂度

> 本系列是极客时间中前 Google 工程师王争《数据结构与算法之美》专栏的学习笔记，想加强数据结构及算法能力的同学可以直接购买此专栏，[跳转链接在此][Link 1] 复

绝地灬酷狼/ 2022年03月16日 05:54/ 0 赞/ 167 阅读

相关《数据结构与算法之美》学习笔记之开篇

> 本系列是极客时间中前 Google 工程师王争《数据结构与算法之美》专栏的学习笔记，想加强数据结构及算法能力的同学可以直接购买此专栏，[跳转链接在此][Link 1]

比眉伴天荒/ 2022年03月16日 05:52/ 0 赞/ 206 阅读

相关数据结构与算法之美--01时间复杂度分析

复杂度分析上听了极客时间的数据结构与算法之美课程后，受益匪浅，把一些我认为比较重要的知识点总结下来，虽然大部分是复制粘贴的。。。。。数据结构与算法之美音频文件，需要

我不是女神ヾ/ 2022年03月06日 11:14/ 0 赞/ 222 阅读

相关数据结构与算法之时间复杂度详解

数据结构与算法之时间复杂度详解 -------------------- 目录 1. 排序算法的介绍和分类 2. 算法的时间复杂度概念 3. 常见的时间复杂

朱雀/ 2022年01月11日 08:11/ 0 赞/ 217 阅读