liyiwen007
- 浏览: 107698 次
- 性别:
- 来自: 武汉
-
最新评论
-
luluandbobo：
为什么要先释放table[T]呢，它不是一个指针吗？如果释放掉 ...
《算法导论》笔记－－平摊分析 -
liuxuejin：
全为理论，我在网上找了N久都找 不到一个具体的B树操作磁盘文件 ...
《算法导论》笔记－－B树 -
westice：
非常好！正苦于怎么确定贝塞尔曲线的控制点，很好的思路。
[翻译] AGG 之贝塞尔插值 -
liyiwen007：
dracularking 写道第三种情况的图是不是不对，z成左 ...
《算法导论》笔记－－红黑树（一） -
dracularking：
第三种情况的图是不是不对，z成左子节点了？
《算法导论》笔记－－红黑树（一）
文章列表
我们常常会谈到也会听到“计划”，感觉做计划是很被重视，却又是“没什么作用”的一项工作。我就来简单地说说我对计划的一些体会，下面所说的“项目”，不一定非得是正儿八经的（软件）工程项目，也可以看成是做一件简单的事。
1. 做计划重要的是过程
如果为做计划而做计划，那计划很可能做成表面文章，对实践也起不到什么指导做作用。
- 2009-02-11 16:28
- 浏览 774
- 评论(0)
B树是平衡树的一种，主要用于操作存储在磁盘等二级存储设备上的大量数据。相比起内存（主存）来说，磁盘操作的速度非常慢（慢几个数量级），所以涉及到存储在磁盘的数据的时候，尽量减少磁盘的读取和写入操作对于提 ...
- 2009-02-04 18:38
- 浏览 5265
- 评论(1)
优先级队列也是一种基础的数据结构，应用非常广泛，并且经常作为其它算法的一部分出现。优先级队列一般分最大优先级队列和最小优先级队列。这两种优先级队列只是为了适应不同场合的需要而进行区分实现，在算法上来讲没有什么本质的不同。因此下面只讲最大优先级队列，所记内容都同时对称地适用于最小优先级队列。
最大优先级队列，是这样的一种队列结构，它的内部存放着一系列的元素，每个元素都对应着一个最优级，最大优先级队列不管各元素的入队顺序，在出队时，总是对应优先级最大的元素出队。比如对许多等待运行的进程来讲，进程调度器每次都取出一个优先级最高的进程执行一段时间，再取下一个优先级最高的进程，如此往复，就需要 ...
- 2009-01-28 18:36
- 浏览 2404
- 评论(0)
Huffman Code是应用很广泛的一种文本压缩编码方式。它的原理就是用不等长的编码来表示不同出现频率的字符。出现频率高的字符，就用比较短的编码来表示，出现频率低的，就是较长的编码来表示。如下表：
图中是一个文件中出现的字符（abcdeft）以及相应的出现频率。如果使用等长编码方式，则每个字符都要用三位来表示，总的长度就是300个bit，如果用变长码来表示，则总长度为224个bit。（对于出现频率最高的a，我们就用一个0来表示它，这样，可以节省很多空间）。Huffman编码的压缩比通常都在20%－90%。
Huffman编码是一种前缀编码方式，所谓前缀编码，即，在编码集合中 ...
- 2009-01-23 21:52
- 浏览 6320
- 评论(0)
假设某大学有一个活动室，我是这个活动管理员。某天，有6个社团都提出了使用活动室的要求，并告知了他们希望使用活动室的时间段（他们之间相互不知道对方的要求，因此时间安排是没有相互商量过的，可能有重叠）。 ...
- 2009-01-21 21:41
- 浏览 6510
- 评论(2)
对于一个操作的序列来讲，平摊分析（Amortize Analysis）得出的是在特定问题中这个序列下每个操作的平摊开销。
一个操作序列中，可能存在一、两个开销比较大的操作，在一般地分析下，如果割裂了各个操作的相关性或忽视问题的具体条件，那么操作序列的开销分析结果就可能会不够紧确，导致对于操作序列的性能做出不准确的判断。用平摊分析就可以得出更好的、更有实践指导意义的结果。因为这个操作序列中各个操作可能会是相互制约的，所以开销很大的那一、两个操作，在操作序列总开销中的贡献也会被削弱和限制。所以最终会发现，对于序列来讲，每个操作平摊的开销是比较小的。
我有这样的理解："对于一 ...
- 2009-01-20 18:37
- 浏览 4745
- 评论(1)
什么问题适合使用动态规划来解决？
如果一个问题具有以下两个特征，那么就可能适合用动态规划来解决：
1. 该问题具有最优子结构
2. 子结构独立且重叠
如果一个问题的最优解包含着该问题的子问题的最优解，那么这个问题就具有最优子结构。拥有最优子结构特征的问题，就有可能用动态规划来解决（当然，也有可能用贪婪算法）。
在递归式中，一个问题的子问题，以及子子问题的解决，很可能会用到很多重复的子问题的解，如果每一次都重新计算，那么重复的计算量非常大的，在动态规划中，会将子问题的解记录下来，这样，再次遇到该子问题时，就可以直接用已经保存的解。
综上，用动态规划来解决问题，主要按以下步骤来进行：
...
- 2009-01-15 19:25
- 浏览 1512
- 评论(0)
红黑树的节点删除
从红黑树上删除一个节点，可以先用普通二叉搜索树的方法，将节点从红黑树上删除掉，然后再将被破坏的红黑性质进行恢复。
我们回忆一下普通二叉树的节点删除方法：Z指向需要删除的节点，Y指向实质结构上被删除的结点，如果
- 2009-01-13 19:53
- 浏览 4155
- 评论(0)
满足下面几个条件的二叉搜索树，称为红黑树：
1. 任何一个节点都被着色――红色或是黑色。
2. 根节点是黑色的。
3. 所有的NIL节点都看成黑色（NIL节点是就是一个假想的或是无实在意义的节点，所有应该指向NULL的指针，都看成指向了NIL节点。包括叶节点的子节点指针或是根节点的父指针）。
4. 如果一个节点是红色的，那么它的子节点一定是黑色的。
5. 对于任何一个节点而言，从该节点到它的子孙节点中的NIL节点路径中，所包含的黑节点个数相同。
黑高度的定义：
二叉搜索树（binary search tree）是经过一定地组织形成的有特定结构特征的二叉树，支持各种动态集合（dynamic set）操作（如insert、delete、maximum、minimum等等）。这些操作的时间复杂度与树的高度成正比。一棵有n个节点的完全二叉树（complete binary tree）的高度不超过lgn。因此，对于完全二叉树的这些操作的最坏时间复杂度（worst-case time）为O(lgn)。但极端病态的二叉树，形状就与链表是一样的，那么，各项操作的最坏时间复杂度将变为O(n)。
由随机输入数据构建的二叉搜索树的期望高度是O(lgn) ...
- 2009-01-05 19:20
- 浏览 5397
- 评论(0)