邓俊辉《数据结构》学习笔记

作者: oneoverzero | 来源:发表于2020-03-21 09:03 被阅读0次

邓俊辉《数据结构》学习笔记
那些B站上不可错过的学习视频
一些未完成的计划
串匹配之蛮力算法
String Matching
[LeetCode] 226. Invert Binary Tr
归并排序
散列表和素数
[书籍]《数据结构(C++语言)》(第三版) 邓俊辉编著清华
递归问题（邓公数据结构1.4节笔记）

P8 01-C-2

Notation	Meaning
大 $O$ 记号	给出复杂度的上界（即最坏的情形）
$\Omega$ 记号（也可以小写）	给出复杂度的下界（即最好的情形）
$\Theta$ 记号（也可以小写）	给出复杂度的确界

如下图所示：

[图片上传失败...(image-ae045d-1584752613060)]

对数复杂度的算法是非常高效的，因为对数复杂度无限接近于常数复杂度：
$\forall c> 0, \log n = O(n^c) \tag 1$

P11 01-D-2

幂方级数的时间复杂度：比幂次高出一阶
$\begin{aligned} & T_1(n) = 1 + 2 + \cdots + n = \frac{n(n+1)}{2} = O(n^2) \\ & T_2(n) = 1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6} = O(n^3) \\ & T_3(n) = 1^3 + 2^3 + \cdots + n^3 = \frac{n^2(n+1)^2}{4} = O(n^4) \\ & T_4(n) = 1^4 + 2^4 + \cdots + n^4 = \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30} = O(n^5) \end{aligned} \tag 2$
收敛级数的时间复杂度：为常数时间复杂度
$\begin{aligned} & \frac{1}{1 \times 2} + \frac{1}{2 \times 3} + \cdots + \frac{1}{(n-1) \times n} = 1 - \frac{1}{n} = O(1) \\ & 1 + \frac{1}{2^2} + \cdots + \frac{1}{n^2} < 1 + \frac{1}{2^2} + \cdots = \frac{\pi ^2}{6} = O(1) \\ & \frac{1}{3} + \frac{1}{7} + \frac{1}{8} + \frac{1}{15} + \frac{1}{24} + \frac{1}{26} + \frac{1}{31} + \frac{1}{35} + \cdots = 1 = O(1) \end{aligned} \tag 3$
两个特殊级数的时间复杂度：

调和级数： $h(n) = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} = \Theta(\log n)$ ；
对数级数： $\log 1 + \log 2 + \cdots + \log n = \log(n!) = \Theta(n \log n)$ 。

（至 P12 01-D-3）

邓俊辉《数据结构》学习笔记
P8 01-C-2 NotationMeaning大记号给出复杂度的上界（即最坏的情形）记号（也可以小写）给...
那些B站上不可错过的学习视频
计算机基础清华大学邓俊辉邓公的《数据结构》https://www.bilibili.com/video/av49...
一些未完成的计划
完成邓俊辉老师的《数据结构与算法》的学习完成CSAPP的学习以及相应的实验与南大的附加nemu 完成操作系统课程...
串匹配之蛮力算法
基于邓俊辉老师的c++数据结构问题描述：给定文本串T,长度n 如：1001101101模式串P,长度m，如： ...
String Matching
这里记录下《Introduction To Algorithm》邓俊辉的《数据结构》里字符串匹配的两种方法，一个是...
[LeetCode] 226. Invert Binary Tr
我们学过树的前序遍历（DFS）和层次遍历（BFS），在邓俊辉《数据结构（C++语言版）》的前序遍历和层次遍历的实现...
归并排序
归并排序的主要思想是“分而治之”，可以达到O(nlogn)的时间复杂度。下图引自敬爱的邓俊辉老师和尹霞老师数据结构...
散列表和素数
理解自：邓俊辉老师《数据结构：散列》 -以蝉为师我们假设有两个散列hash_a和hash_b,表a的长度M =...
[书籍]《数据结构(C++语言)》(第三版) 邓俊辉编著清华
《数据结构(C++语言)》(第三版) 清华大学出版社邓俊辉编著关于这本书这本书有配套的视频课程，全套课程可以...
递归问题（邓公数据结构1.4节笔记）
在邓俊辉的数据结构教材的1.4节中简要介绍了一下递归问题，在查阅相关资料后，发现递归问题包含了以下几个方面：线性...