爱撸代码的公孙镜

分类

读书笔记(8)

/ 注册

全部文章（共7篇）

《算法导论（原书第3版）》读书笔记

13.1 红黑树的性质红黑树是，在二叉搜索树基础上，加了一个叫“颜色”的存储位，可以是“RED”或“BLACK”。通过“对于每个结点，从该结点到后代叶子结点的简单路径上，均包含相同数目的黑色结点”这个规则，确保没有一条路径会比其它路径长出 2 倍，因而是近似于平衡的。树中每个结点包含 5 个属性：...

2021-01-29

0 0

《算法导论（原书第3版）》读书笔记

第十二章二叉搜索树对于一棵“完全”二叉树来说，最坏操作时间为 Θ(lgn)。然而，如果这棵树是一个 n 个结点组成的线性链，操作时间为 Θ(n)。在12.4节中，我们将看到一棵随机构造的二叉搜索树的期望高度为O(lgn)，因此这样一棵树上的动态集合的基本操作的平均运行的时间是 Θ(lgn)。实际...

2021-01-22

0 0

《算法导论（原书第3版）》读书笔记

11.1 直接寻址表什么是直接寻址表？就是用一个数组，数组的每个位置都保存一个元素。每个数组的位置称作“槽(slot)”。下图描绘了一个直接寻址表，槽 k 指向集合中的一个“关键字”为 k 的元素。如果该集合中没有关键字为 k 的元素，则 T[k] = NIL。特点：最大复杂度：O(1)最小复杂度...

2021-01-15

0 0

《算法导论（原书第3版）》读书笔记

堆排序A.length 是数组的长度，也就是上界A.heap-size 是有效的对元素的最后一个元素的位置，MAX-HEAPIFY要判断左孩子和右孩子是否越界维护堆的性质维护堆的性质，数组A和下标iMAX-HEAPIFY(A, i)l=LEFT(i) 左孩子r=RIGHT(i) 右孩子if l &...

2021-01-08

0 0

《算法导论（原书第3版）》读书笔记

课后题Problem 4.1 (Recurrence examples)Give asymptotic upper and lower bound for T(n) in each of the following recurrences. Assume that T(n) is constant ...

2020-12-25

0 0

《算法导论（原书第3版）》读书笔记

2、归并排序　　归并排序采用了算法设计中的分治法，分治法的思想是将原问题分解成n个规模较小而结构与原问题相似的小问题，递归的解决这些子问题，然后再去合并其结果，得到原问题的解。分治模式在每一层递归上有三个步骤：分解（divide）：将原问题分解成一系列子问题。解决（conquer）：递归地解答...

2020-12-10

0 0

《算法导论（原书第3版）》读书笔记

本章通过介绍插入排序和归并排序两种常见的排序算法来说明算法的过程及算法分析，在介绍归并排序算法过程中引入了分治算法策略。 1、插入排序　　输入：n个数（a1,a2,a3,...,an）　　输出：输入序列的一个排列（a1',a2',a3',...an'）使得（a1'≤a2'≤a3'≤...≤an'...

2020-12-03

0 0