《算法导论》学习总结 — XX.第24章 单源最短路径

建议先看看前言:http://www.wutianqi.com/?p=2298

更多单源最短路径算法见我的算法专题:http://www.wutianqi.com/sfzt.html

这里我补充一些里面未写到的。

继续阅读《算法导论》学习总结 — XX.第24章 单源最短路径

《算法导论》学习总结 — XX.第23章 最小生成树

建议先看看前言:http://www.wutianqi.com/?p=2298

以前写过一篇最小生成树的文章,见:http://www.wutianqi.com/?p=1284

最小生成树(Minimum Spanning Tree),全称“最小权值生成树”

有两种具体的实现算法

1.Kruskal算法

2.Prim算法

两者都用到了贪心算法。

继续阅读《算法导论》学习总结 — XX.第23章 最小生成树

《算法导论》学习总结—【目录】

公告:

1.预计完工时间:2012.1.31 暂时推后一段时间,这段时间找工作在

2.如果哪些朋友也写了CLRS的笔记,可以留下传送门(url),我会在下方添加汇总。

下一步计划:

1.把总结整理下,并开始进行第二轮的学习:做题+看书+看此笔记

2.希望大家帮忙把这篇目录多推广一下,让更多朋友一起讨论。

3.考虑弄一个群或论坛添加一个板块来讨论。

继续阅读《算法导论》学习总结—【目录】

《算法导论》学习总结 — 7.第八章(1) 决策树

建议先看看前言 : http://www.wutianqi.com/?p=2298

 

第八章将介绍几种非比较排序—计数排序,基数排序,桶排序,这三种排序都在线性时间下运行的。

这一节决策树其实是对前面的堆排序,快排等是最优的比较算法的证明,

首先说下《算法导论》上对决策树的定义:一棵决策树是一棵满二叉树(注意看下面解释),表示某排序算法作用于给定输入所做的所有比较,而控制结构,移动等都被忽略了。

注意:这里个人认为定义是错误的,决策树不是一棵满二叉树,连完全二叉树都不是。(不知道有没有朋友看到这里和我想法一样?)

首先看看只有三个元素时,决策树的图:

jueceshu

在决策树中,每个内结点都用i:j表示比较下标为i数组元素与下标为j的数组元素的大小。每一个叶结点是一个n个元素的全排列。

所以排序算法的执行对应于遍历一条从树的根到叶结点的路径

因为有n个结点,根据高中学的组合排列知识,知道有n!个情况,也就是n!个叶子结点。

在决策树中,从根到任意一个可达叶结点之间的最长路径的长度,表示对应的排序算法中最坏情况下的比较次数。这样,一个比较算法的最坏情况的比较次数就是其决策树的高度

定理8.1证明了任意一个比较算法在最坏情况下都需要做Ω(n lg n)次的比较。这个证明比较简单,可以看看书上的证明过程。

这一节其实没什么内容,就是一点基本的概念,以及了解比较算法可以通过转换为决策树这个模型去理解。

 

Tanky Woo 标签: