Board logo

标题: 算法笔记 [打印本页]
作者: loranrowe    时间: 2005-1-19 13:12

1、算法是什么呢？
一种说法是，算法是一组明确定义了的以某些值作为输入，某些值作为输出的计算过程
  太抽象了。
其实也就是说，算法是有输入有输出的明确的计算过程
另一种说法是，算法可以看作是用于解决经过明确定义了的可计算问题的工具
该问题陈述了输入与输出间的关系，而算法则将这种关系用特定的计算过程实现出来
有一个问题，我用一段话将这个问题的解决方法记录下来，这段话就是一个算法？
不一定！
这个问题有可能是可陈述、可解决但不可计算的
比如说：你爱我吗？
显然这个问题是不可计算的，但是总会有一个解  
开个玩笑。
2、那么，到底算法要解决什么样的问题呢？
一般来说，一个成功的算法都具备两个特征：
挑战性：一个问题可能会有很多的候选解，但是大部分都不是我们想要的，把我们想要的挑出来！(挑三拣四)
有人用：没人用？算法再好又如何？(市侩啊市侩)
3、如何学算法？
我认为，学算法最重要的是学思想，学会如何思考问题。
在我们需要算法实例的时候可以google，难道思想也可以google么？就算google到了，还是要学来才能用。
4、算法不能解决所有的问题
一个问题，或者可以解决，或者不能解决。真的是这样么？
世界不总是二分的。
在算法领域内，有一类问题，至今不能确定是否可以解决。
NP-hard，n的多项式时间内是否可以找到解？
NP-complete，n的多项式时间内是否可以找到所有解？
都是这种问题，我们不知道能不能找到某个可以在可忍受的有限时间内结束的算法。(好绕啊)
5、算法学了有啥用呢？
算法可以解决问题。
就算不能解决问题，它可以帮助你思考。
就算是需要解决的问题在已解决问题领域内找不到任何帮助，多学点儿东西总没坏处的。
作者: Maxwell    时间: 2005-1-19 14:30

呵呵，我记得有本书上定义是对于任何有效输入都可以在有限步内停机的自动机，更抽象吧
作者: 天痕    时间: 2005-1-19 15:30



QUOTE:
原帖由Maxwell于2005-01-19, 14:30:53发表
呵呵，我记得有本书上定义是对于任何有效输入都可以在有限步内停机的自动机，更抽象吧  

这个好像是可计算理论里的有限自动机的可计算性（不要求结束时回到开始处）的定义  

对算法，搞竞赛的有这么个说法：给到题要求40分钟内解决，至少要花20分钟在考虑算法上                  当然过于简单的题不算
作者: Maxwell    时间: 2005-1-19 15:34



QUOTE:
原帖由天痕于2005-01-19, 15:30:15发表
这个好像是可计算理论里的有限自动机的可计算（不要求结束时回到开始处）的定义  

对算法，搞竞赛的有这么个说法：给到题要求40分钟内解决，至少要花20分钟在考虑算法上                  当然过于简单的题不算  

这是在学校图书馆借的一本老书上的定义，书不算很厚，蓝皮，我觉得写的很好，比现在某些算法书强不少。
呵呵，过于简单的题也不会给40分钟。
作者: loranrowe    时间: 2005-1-19 15:46

呵呵，还真有人看啊，坚定了我继续写下去的信心
我现在看的这本书，是the MIT Press出的Introduction to Algorithms
这本书应该是现在比较权威的教材之一了
争取用一到两个月的时间review一下
这本笔记做完，我准备从头再来一遍C++
VC用了好久，还没仔细学习过C++呢
Maxwell到时要多指教啊...
作者: Maxwell    时间: 2005-1-19 15:55

呵呵，客气了，我虽然程序写了不少，可是算法真没仔细研究过，正要跟兄好好学习一下
作者: dollbean    时间: 2005-1-19 17:06

算法是程序设计的精髓，好好学习一下
作者: loranrowe    时间: 2005-1-20 11:28

第二日:
1、如何分析一个算法？如何评价它？
分析一个算法意味着要估算其资源消耗。
资源包括内存、网络带宽、硬件计算能力，同时还有时间。
以同样的评价体系对每种算法进行分析
这样，在解决具体问题的时候，就可以对如何选择算法进行取舍：
我更在乎时间还是更在乎金钱......
时间和金钱你都不在乎？  
哪个长相顺眼就用哪个吧......

在讨论分析方法之前，首先要做一个算法的执行模型的假设
什么意思呢？就是说，算法要执行在一个什么样的环境之中
对于经典的，不考虑并发的算法而言，一般采用RAM(random-access machine，随机访问机)模型
在这种模型下，所有的指令都是顺序执行的
不过RAM还是要尽量的符合计算机的实际处理能力，不能滥用
假设给RAM加一个sort指令，那么所有的sort操作都可以用1条指令完成，这显然不符合实际
一般来说RAM的指令包括：
1)运算符：加减乘除、求余、取整
2)数据操作：读入、存储、copy
3)控制操作：分支、调用、返回
等等等
RAM能用的数据结构一般仅包括integer和floating指针，而且数据块的长度要受到严格的限制
1M的数据块的一次操作只要1的机器时间？不合理！
而且RAM不为存储器建立分层模型，存储器只有一个，没有cache和虚拟内存的概念(太不合理了！限制别人就可以，限制自己的全去掉)
假设每一条指令的执行时间是一个固定的常数，同时不会消耗内存。
限制这么多，分析起来当然困难了！
而且大多数非理想情况下，环境与RAM的假设是不同的
还有，并发算法用什么模型来分析呢？我也不知道，以后再说啦

说了这么多，基本上没啥有用的，据个例子吧
插入排序算法分析：
假设：
n=length[a]
t(j)为第五步对每个j，while循环的执行次数
sigma是求和运算，3个参数分别对应下限、上限及求和变量

INSERTION-SORT(A)                            一次操作时间         次数
1 for j<-2 to length[A]                      c1                   n
2   do key<-A[j]                             c2                   n-1
3     //将A[j]插入到已排序序列A[1..j-1]      0                    n-1(注释都要算？算上好，不出错)
4     i<-j-1                                 c4                   n-1
5     while i>0 and A>key                 c5                   sigma(j=2,n,t(j))
6       do A[i+1]<-A                      c6                   sigma(j=2,n,t(j)-1)
7          i<-i-1                            c7                   sigma(j=2,n,t(j)-1)
8     A[i+1]<-key                            c8                   n-1

总的时间消耗为：
T(n)=c1*n+c2*(n-1)+c4*(n-1)+c5*sigma(j=2,n,t(j))+c6*sigma(j=2,n,t(j)-1)+c7*sigma(j=2,n,t(j)-1)+c8*(n-1)
最好的情形，所有输入元素已排序：
显然t(j)=1,总的执行时间
T(n)=(c1+c2+c4+c5+c8)*n-(c2+c4+c5+c8)
最好情形下，T(n)是输入长度n的一个线性函数
最差的情形，所有输入元素已排序，不过是降序：
t(j)=j
sigma(j=2,n,t(j))=n*(n+1)/2-1
sigma(j=2,n,t(j)-1)=n*(n-1)/2
T(n)=()*n^2+()*n-()
括号里面的数，大家有兴趣的话可以自己算，都是常数
最差情形下，T(n)是n的形如a*n^2+b*n+c的二次函数

一般来说，分析算法的运行时间，通常有两个方面的考虑：最差情形和平均情形
为啥要分析最差？
分析最差情形可以知道一个算法对于输入长度为n的数据的最长执行时间(没有比它更差的了)
最差的情形经常出现=.=
平均情形经常和最差情形差不多
为啥要分析平均呢？
平均分析了算法运行时间的期望值(方差太难分析了)，在使用概率分析方法时是一个有效的度量

分析中的最后一个概念：阶
阶是指运行时间关于输入长度n的函数T(n)中，对T(n)增长产生最主要影响的某项，常系数一般只在同阶比较时才予以考虑
记为o()
比如，最好情形下的时间函数的阶是o(n)
一般可以认为，在最差情形下，高阶算法总比低阶算法运行时间长
作者: loranrowe    时间: 2005-1-20 17:00

2、设计的主要思想:分治
分治思想可以说是近现代科学研究的主要思维方法：
大问题解决不了？
先分成小问题，全部解决后再组合起来，大问题就可以解决了
用分治思想解决问题一般包括3个步骤：
分：把问题分解为多个子问题
治：如果子问题能解决最好，不能解决就继续分！
组合：所有的子问题都解决了，将子问题的解决方案组合为原问题的解决方案

以归并排序为例说明一下"分治"的思路:
问题：将n个元素顺序排列
解决：
分：将n个元素的序列分为两个子序列，每部分n/2个元素
治：将分开的两个子序列分别排序
组合：将排序后的子序列归并到一起

组合的过程是整个问题最终能够得到解决的关键！
归并算法：
将已经分别排序的A的子序列A[p..q]和A[q+1..r]归并为排序后的序列A[p..r]
MERGE(A,p,q,r)
1  n1<- q-p+1
2  n2<- r-q
3  create arrays L[1..n1+1] and R[1..n2+1]
4  for i<- 1 to n1
5    do L<-A[p+i-1]
6  for j<- 1 to n2
7    do R[j]<-A[q+j]
8  L[n1+1]<-infinite
9  R[n2+1]<-infinite//设置哨兵*
10 i<-1
11 j<-1
12 for k<-p to r
13   do if L<=R[j]
14     then A[k]<-L
15          i<-i+1
16     else A[k]<-R[j]
17          j<-j+1

* 这里为什么要多分配一个元素作为哨兵呢？作为思考题留给大家吧

分治过程--归并排序算法：
MERGE-SORT(A,p,r)
1 if p<r
2   then q<-floor((p+r)/2)
3        MERGE-SORT(A,p,q)
4        MERGE-SORT(A,q+1,r)
5        MERGE(A,p,q,r)

呵呵，粉简单吧，才5行就解决了，效率可比插入排序高多了！
不信？那就分析一下MERGE-SORT的效率吧：
设T(n)为n个元素排序的运行时间，如果n足够小，小于一个常数，记为n<=c,这时可以近似的认为T(n)=o(1)(这个你都不信！？omg，让c=1吧)
问题被分解为2个部分，每个部分有原问题1/2的规模(不过很多时候，分解出来的各部分之间尺寸并不一定一致)
分解需要时间D(n),组合需要时间C(n)
好了，T(n)的表达式出来了：
T(n)={
o(1)              if n<=c,
2T(n/2)+D(n)+C(n) otherwise.
}
对于归并排序算法来说
D(n)=o(1)
C(n)=o(n)
T(n)={
o(1)           if n=1,
2T(n/2)+o(n)   if n>1.
}
muhaha...还是递归的
好了，不卖关子了，最终结果
T(n)=o(n*lg(n))
想知道怎么得出来得么？我也想知道，明天见！
作者: 金圭子    时间: 2005-1-21 16:33

一直觉得这儿的确需要有人轮番讲课了。起码一个月讲一门吧…………（MW：就等你呢 -_\\，金圭子：做梦！！）

所以非常支持一下…………

不过我本人喜欢码字，但是从来没耐心看…………这个也是我到现在还不是名角只是票友的原因………………
作者: Maxwell    时间: 2005-1-21 18:25

金圭子把我想说的话替我说了。
作者: loranrowe    时间: 2005-1-21 23:08

两个人就知道灌水！
作者: Maxwell    时间: 2005-1-22 08:36

被批评了。。。
  我一直在认真读文章，还需要多多指点我啊。
作者: 天痕    时间: 2005-1-23 07:02



QUOTE:
原帖由loranrowe于2005-01-21, 10:52:15发表
1、递归
递归是什么呢？
递归是一组根据较小输入项的值来描述函数的方程或不等式(生活，是一团麻)
递归是一组方程或不等式
较小输入项是有直观解的，可以称作边界情形和边界值
根据边界值，用方程(方程的另一个意思就是等式)或不等式来描述一个函数，就是递归
在应用中，我们只需要描述边界并定义相应方程或不等式，递归的具体执行，亟递推求解过程，是由机器完成的
这种解是针对某种具体问题的具体解
在分析递归过程的效率时，我们需要一个形式上的解，或者叫做通解，递推的方法不再有效了

说到递归，我来说两句。
递归的好处不用说了，自然是结构清晰，但递归也有不小的坏处。
最直接的就是调试程序变麻烦了，还有就是内存的使用，若在递归里要开数组的话就要小心了。
另外有一点可能大家不注意，就是工具的限制。每个工具因为内存原因都对递归的层数有限制。VC可以将全部硬盘虚拟为内存，这个问题自然不明显（似乎递归的上限是200+）。但若是比较古老的工具，比如说TURBO PASCAL，只能用640K内存，递归上限是30层（也可能多两层，反正不超过33）。用这样的工具，则要注意用非递归的方式来写递归的程序（比如引入一个表示层数的变量，若原来的递归里要开数组，则可以把结构改成十字链表）

要说的就这么多，有时间的话附个程序给大家看一下。
作者: loranrowe    时间: 2005-1-23 10:08



QUOTE:
原帖由天痕于2005-01-23, 7:02:28发表
说到递归，我来说两句。
递归的好处不用说了，自然是结构清晰，但递归也有不小的坏处。
最直接的就是调试程序变麻烦了，还有就是内存的使用，若在递归里要开数组的话就要小心了。
另外有一点可能大家不注意，就是工具的限制。每个工具因为内存原因都对递归的层数有限制。VC可以将全部硬盘虚拟为内存，这个问题自然不明显（似乎递归的上限是200+）。但若是比较古老的工具，比如说TURBO PASCAL，只能用640K内存，递归上限是30层（也可能多两层，反正不超过33）。用这样的工具，则要注意用非递归的方式来写递归的程序（比如引入一个表示层数的变量，若原来的递归里要开数组，则可以把结构改成十字链表）

要说的就这么多，有时间的话附个程序给大家看一下。

一般来说，递归调用时保存的现场信息是压入栈中存放的
想要获得更大的递归深度，可以通过修改栈的大小实现
不过也不能从根本上解决问题
递归都可以改写为循环，这样就不受栈溢出的困扰了
不过这些不是算法要讨论的内容...
作者: Maxwell    时间: 2005-1-26 12:45

loranrowe可否把这些算法详细讲讲，不然我想大多数人是看不懂的
作者: loranrowe    时间: 2005-1-26 15:37



QUOTE:
原帖由Maxwell于2005-01-26, 12:45:26发表
loranrowe可否把这些算法详细讲讲，不然我想大多数人是看不懂的  

所有的算法？
还是仅仅排序这一部分？
其实线性时间的排序算法在实际应用的时候要受到很大限制
只要知道思路就可以了
所以算法描述都很简单
前面大部分算法描述的都已经很清楚了吧  
我是这么觉得，一直怕有人嫌我罗嗦，而且码字也蛮需要时间的
作者: Maxwell    时间: 2005-1-26 18:15

其实说起来笔记是比较提纲挈领言简意赅就可以了，不过可能多数人没有接触过这个，只凭三言两语看的摸不着头脑的，所以loranrowe兄应该详细的解释解释啊。
作者: loranrowe    时间: 2005-1-26 18:27



QUOTE:
原帖由Maxwell于2005-01-26, 18:15:08发表
其实说起来笔记是比较提纲挈领言简意赅就可以了，不过可能多数人没有接触过这个，只凭三言两语看的摸不着头脑的，所以loranrowe兄应该详细的解释解释啊。

前面已经写完的就先这样吧...  
后面我会注意的
说起来，排序算法是全部算法中最简单和普及的内容了
确实写的比较略
还好马上就要到不得不提、不得不详细写的数据结构部分了
作者: Maxwell    时间: 2005-1-26 18:55

虽然比较普及，但是基数桶那一篇非专业的应该了解的不多，再说这些算法看起来简单理解可不简单
作者: loranrowe    时间: 2005-1-27 11:26

排序(二)已修改
下午来贴第六日
作者: kingofworl    时间: 2005-1-27 21:59

看到loranrowe，金圭子等人，觉得自己总受帮助却对论坛未有尺寸之功甚感惭愧  别的忙帮不上，正好手里有以前做的排序算法例子，个人当时对冒泡排序掌握的还可以，如果说loranrowe的讲解过于理论了，那这段代码应该还是比较容易理解的
public void sfMaoPao(int data[],int data1[][])
        {
                int pass,i=0,temp,exchangeCnt;
               
                for(pass=0;pass<data.length;pass++)
                {
                        exchangeCnt=0;
                        for(i=0;i<data.length-pass-1;i++)
                        {
                                if(data>data[i+1])
                                {
                                        temp=data;
                                        data=data[i+1];
                                        data[i+1]=temp;
                                        exchangeCnt++;
                                }
                        }
                       
                       
                        for(i=0;i<data.length;i++)
                        {
                                data1[pass]=data;
                        }
                        if(exchangeCnt==0)
                        {
                                return;
                        }
                }
        }

有兴趣的朋友可以让maxwell或随便哪位高手讲讲，对他们来说一看就明白了
作者: loranrowe    时间: 2005-4-13 16:54

经过n久的沉寂，偶又回来了！
第七日：基本数据结构(二)
1、哈希表
也叫散列表
很多时候，应用程序需要这样一种结构
仅需要三个基本操作：
插入、查找、删除
哈希表就可以提供这样的功能组合

哈希表是一种在线性表基础上实现的数据结构
一般而言,可以把数组理解为一个不带操作线性表
为了便于理解,以数组的概念代替线性表
假定每个元素(数据项)都有一个域称为关键域
通过某种方法,如果可以在数组的下标和关键域值(简称关键值)之间建立某种映射关系(如果高中数学没忘光的话,应该记得这个概念)
那么这个数组就可以叫做一个哈希表
建立下标和关键值之间映射的方法,称为哈希函数,或者散列函数
在这里,散列的意思可以理解为,将集合中的元素,分散到了数组之中

哈希表是实现字典的一个很有效的手段
想到了点儿什么没有？bingle！拼音检字法就是一种有效的哈希方案
声母和韵母作为关键值，页码是数组下标，拼音检字表就是一个哈希表
不过想要检索到一个字，要计算两次哈希函数
第一次检索到声母，第二次检索到拼音对应的页码
偏旁部首检字也是类似的

最简单的哈希表是直接寻址表,下标等于关键值
哈希函数是T[k]=k,也就是y=x
插入、删除、查找操作都很好实现，就不一一列出了
而且这些操作都很快，o(1)时间就可以实现
但是这种表的缺陷也很明显，如果集合内关键值的取值范围很大，就要有一个相应大小的数组与之对应才行

这个问题也很好解决，想想字典是怎么做的
建立哈希函数的时候，使定义域大于值域，也就是缩小结果的取值范围
简单的讲就是从关键值中提取共性，比如拼音中的声母，比如部首检字法中的偏旁
作用都是一样的
这样就可以使不同的关键值被映射到哈希表中的同一个位置

这样又引出了两个问题：
1、数组的一个下标的位置只能存一个值，如何处理映射过来的多个值？
2、如何使对应到每个下标的元素个数不要相差太大
第一个问题很好解决，可以在数组中存放一个指向链表的指针，具体元素存放在链表中
第二个问题就很不好回答了，如果做不到这一点，一个哈希函数就必定不是一个好的哈希函数

2、二叉查找树(二叉搜索树)
二叉查找树首先是一颗二叉树，它仅比二叉树多了以下特性
假设x是二叉查找树上的一个节点
如果y是x的左子树上的一个节点，那么key[y]<=key[x]
如果y是x的右子树上的一个节点，那么key[y]>=key[x]
从这种意义上讲，一个升序排列的链表可以看作是一个所有左子为nil的二叉排序树

定义在二叉搜索树上的基本操作：
查找:
TREE-SEARCH(x,k)
1 if x = NIL or k= key[x]
2   then return x
3 if k<key[x]
4   then return TREE-SEARCH(left[x],k)
5   else return TREE-SEARCH(right[x],k)

非递归的查找算法:
ITERATIVE-TREE-SEARCH(x,k)
1 while x <> NIL and k <> key[x]
2      do if k < key[x]
3           then x <- left[x]
4           else x <- right[x]
5 return x

最小和最大
TREE-MINIMUM(x)
1 while left[x] <> nil
2      do x <- left[x]
3 return x

TREE-MAXIMUM(x)
1 while right[x] <> nil
2      do x <- right[x]
3 return x

后继与前驱
TREE-SUCCESSOR(x)
1 if right[x] <> NIL
2   then return TREE-MINIMUM(right[x])
3 y <- p[x]
4 while y <> NIL and x = right[y] //父亲节点是左孩子的直接后继
5      do x <- y
6         y <- p[y]
7 return y
求前驱把以上过程中左右反过来就可以了

插入与删除
插入比较简单,找到地方,插进去,嗯
TREE-INSERT(T,z)
1 y <- NIL
2 x <- root[T]
3 while x <> NIL
4      do y <- x
5         if key[z] < key [x]
6            then x <- left[x]
7            else x <- right[x]
8 p[z] <- y
9 if y = NIL
10   then root[T] <- z  //树T空的时候
11   else if key[z] < key[y]
12          then left[y] <- z
13          else right[y] <- z

删除就比较麻烦了,自己画个图可能会比较好理解
分以下几种情况：
如果z的左子树或者右子树为空，直接以左子树或右子树替换z
都不空的情况下
如果z的直接后继没有右子树(肯定没有左子树)，用后继替换z
如果后继有右子树，先用右子树替换后继，在用后继替换z
不知道有没有人能看懂我说了些什么  
TREE-DELETE(T,z)
1 if left[z] = NIL or right[z] = NIL
2   then y <- z
3   else y <- TREE-SUCCESSOR(z)
4 if left[y] <> NIL
5   then x <- left[y]
6   else x <- right[y]
7 if x <> NIL
8   then p[x] <- p[y]
9 if p[y] = NIL
10   then root[T] <- x
11   else if y = left[p[y]]
12          then left[p[y]] <- x
13          else right[p[y]] <- x
14 if y <> z
15   then key[z] <- key[y]
16        把y的数据copy到z
17 return y

就到这里，休息！
作者: loranrowe    时间: 2005-4-14 16:52

贴一个INTRODUCTION TO ALGORITHMS 2ed的目录
中文名为算法导论(第二版 影印版)
这也是这一系列帖子大概将要涉及内容的范围
ps:
再多罗嗦两句，想要写出让自己满意的程序
不管你用什么样的语言，什么样的设计思想
有两类知识是必须要学习的
数据结构和算法
这两者是以高级语言表达思想的基础
可以不以研究为目的，不需要精通，但至少要了解
高中代数老师教导我说：思路最重要
送与大家共勉之
Preface

I Foundation

Introduction

1 The Role of Algorithms in Computing

1.1 Algorithms
1.2 Algorithms as a technology

2 Getting Started

2.1 Insertion sort
2.2 Analyzing algorithms
2.3 Designing algorithms

3 Growth of Functions

3.1 Asymptotic notation
3.2 Standard notations and common functions

4 Recurrences

4.1 The substitution method
4.2 The recursion-tree method
4.3 The master method
4.4 Proof of the master theorem

5 Probabilistic Analysis and Randomized Algorithms

5.1 The hiring problem
5.2 Indicator random variables
5.3 Randomized algorithms
5.4 Probabi1istic analysis and further uses of indicator

II Sorting and Order Statistics

Introduction

6 Heapsort

6.1 Heaps
6.2 Maintaining the heap property
6.3 Building a heap
6.4 The heapsort algorithm
6.5 Priority queues

7 Quicksort

7.1 Description of quicksort
7.2 Performance ofquicksort
7.3 A randomized version of quicksort
7.4 Analysis ofquicksort

8 Sorting in Linear Time

8.1 Lower bounds for sorting
8.2 Counting sort
8.3 Radix sort
8.4 Bucket sort

9 Medians and Order Statistics

9.1 Minimum and maximum

9.2 Selection in expected linear time
9.3 Selection in worst-case linear time

III Data Structures

Introduction

10 Elementary Data Structures

10.1 Stacks and queues
10.2 Linked lists
10.3 Implementing pointers and objects
10.4 Representing rooted trees

11 Hash Tables

11.1 Direct-address tables
11.2 Hash tables
11.3 Hash functions
11.4 Open addressing
11.5 Perfect hashing

12 Binary Search Trees

12.1 What is a binary search tree?
12.2 Querying a binary search tree
12.3 Insertion and deletion
12.4 Randoinly built binary search trees

13 Red-Black Thees

13.1 Properties of red-black trees
13.2 Rotations
13.3 Insertion
13.4 Deletion

14 Augmenting Data Structures

14.1 Dynamic order statistics
14.2 How to augment a data structure
14.3 Interval trees

IV Advanced Desthe and Analysis Techniques

Introduction

15 Dynamic Programming

15.1 Assembly--line scheduling
15.2 Matrix-chain multiplication
15.3 Elements of dynamic programming
15.4 Longest common subsequence
15.5 Optimal binary search trees

16 Greedy Algorithms

16.1 An activity-selection problem
16.2 Elements of the greedy strategy
16.3 Huffman codes
16.4 Theoretical foundations for greedy methods
16.5 A task-scheduling problem

17 Amortized Analysis

17.1 Aggregate analysis
17.2 The accounting method
17.3 The potential method
17.4 Dynamic tables

V Advanced Data Structures

Introduction

18 B-Trees

18.1 Definition of B--trees
18.2 Basic operations on B-trees
18.3 Deleting a key from a B--tree

19 Binomial Heaps

19.1 Binomial trees and binomial heaps
19.2 Operations on binomial heaps

20 Fibonacci Heaps

20.1 Structure of Fibonacci heaps
20.2 Mergeable-heap operations
20.3 Decreasing a key and deleting a node
20.4 Bounding the maximum degree

21 Data Structures for Disjoint Sets

21.1 Disjoint--set operations
21.2 Linked-list representation of disjoint sets
21.3 Disjoint--set forests
21.4 Analysis of union by rank with path compression

VI Graph Algorithms

Introduction

22 Elementary Graph Algorithms

22.1 Representations of graphs
22.2 Breadth-first search
22.3 Depth-first search
22.4 Topological sort
22.5 Strongly connected components

23 Minimum Spanning Trees

23.1 Growing a minimum spanning tree
23.2 The algorithms of Kruskal and Prim

24 Single-Source Shortest Paths

24.1 The Bellman-Ford algorithm
24.2 Single-source shortest paths in directed acyclic graphs
24.3 Dijkstra’s algorithm
24.4 Difference constraints and shortest paths
24.5 Proofs of shortest-paths properties

25 All-Pairs Shortest Paths

25.1 Shortest paths and matrix multiplication
25.2 The Floyd-Warshall a1gorithm
25.3 Johnson’s algorithm for sparse graphs

26 Maximum Flow

26.1 Flow networks
26.2 The Ford-Fulkerson method
26.3 Maximum bipartite matching
26.4 Push--relabel algorithms
26.5 The relabel--to-front algorithm

VII Selected Topics

Introduction

27 Sorting Networks

27.1 Comparison networks
27.2 The zero-one principle
27.3 A bitonic sorting network
27.4 A merging network
27.5 A sorting network

28 Matrix Operations

28.1 Properties of matrices
28.2 Strassen’s algorithm for matrix multiplication
28.3 Solving systems of linear equations
28.4 Inverting matrices
28.5 Symmetric positive-definite matrices and least-squares approximation

29 Linear Programming

29.1 Standard and slack forms
29.2 Formulating problems as linear programs
29.3 The simplex algorithm
29.4 Duality
29.5 The initial basic feasible solution

30 Polynomials and the FFT

30.1 Representation of polynomials
30.2 The DFT and FFT
30.3 Efficient FFT implementations

31 Number-Theoretic Algorithms

31.1 E1ementary numbertheoretic notions
31.2 Greatest common divisor
31.3 Modular arithmetic
31.4 Solving modular linear equations
31.5 The Chinese remainder theorem
31.6 Powers of an element
31.7 The RSA public-key cryptosystem
31.8 Primality testing
31.9 Integer factorization

32 String Matching

32.1 The naive string-matching algorithm
32.2 The Rabin-Karp algorithm
32.3 String matching with finite automata
32.4 The Knuth-Morris-Pratt algorithm

33 Computational Geometry

33.1 Line--segment properties
33.2 Determining whether any pair of segments intersects
33.3 Finding the convex hull
33.4 Finding the c1osest pair of points

34 NP-Completeness

34.1 Polynomial time
34.2 Polynomial-time verification
34.3 NP-completeness and reducibility
34.4 NP--completeness proofs
34.5 NP-complete problems

35 Approximation Algorithms

35.1 The vertex-cover problem
35.2 The traveling-salesman problem
35.3 The set-covering problem
35.4 Randomization and linear programming
35.5 The subset-sum problem

VIII Appendix: Mathematical Background

Introduction

A Summations

A.1 Summation formulas and properties
A.2 Bounding summations

B Sets, Etc.

B.1 Sets
B.2 Relations
B.3 Functions
B.4 Graphs
B.5 Trees

C Counting and Probability

C.1 Counting
C.2 Probability
C.3 Discrete random variables
C.4 The geometric and binomial distributions
C.5 The tails of the binomial distribution

Bibliography
Index
作者: loranrowe    时间: 2005-4-15 16:34

第八日：基本数据结构(三)
一、红黑树
红黑树是一类特殊的二叉搜索树
同样有左子小、右子大的特点
只是每个节点都多了一个bit，用于表示该节点的颜色(只有红黑两色)
具体定义如下：
1、每个节点要么是红的，要么是黑的
2、根节点是黑色的
3、所有的叶节点(NIL)都是黑色的
4、如果某个节点是红的，那么它的两个子节点必然是黑的
5、对每一个节点，从该节点到它的叶节点的所有简单路径中，路过的黑色节点数量都是同样的。

第四、五条规定带来的是一种局部的平衡
在普通的二叉树中，搜索过程就是一次遍历过程
二叉查找树将这个过程简化为一个不断的选择过程：左或者右，每次都会抛弃另一边
红黑树则在此基础上带来了另外一些特性：左树和右树看起来不会差太多
这种特性显然为查找带来了很大的好处
相比普通的二叉查找树，可以有效的降低查找次数的期望值
但是，为了维持这一特性，是要付出代价的
在插入和删除一个节点的时候，这一节点的变化会为它的父亲和兄弟节点带来平衡性上的变化
多一个或者少一个红色的节点是不会有任何问题的
但是规定4决定了不是每一个节点都可以是红的
好了，今天偷个懒，这个问题就说这么多
更多的关于红黑树的讨论可以看这里
http://www.frontfree.net/view/article_606.html
比我写的好多了

二、增广(augmenting)数据结构？
在我们使用一些经典数据结构的时候，如果它们只能满足我们某一部分的需要
这时候，我们有可能会选择将原有数据结构进行扩展
一般而言，增广某种数据结构可以遵循如下步骤：
1、选择适当的元数据结构
2、决定将要在元数据结构基础上增加那些信息
3、确定新增加的数据域与原有的操作不存在冲突
4、实现新的操作

具体的处理方法见仁见智
(以下与算法无关)
通常，结构化的编程方法在增广数据结构及其功能时会比较困难
需要对原有编码和代码结构进行修改
面向对象的程序设计则不存在这样的问题
由于对象是对数据和功能的统一封装
一般可以很方便的通过继承和组合的方式实现
作者: 大汉天子    时间: 2005-4-15 20:26

这些东西给一些不是专业的人讲没有太大意义
在我们竞赛小组老师一对一讲都讲得很痛苦 何况这么网上文字叙述？
作者: 叶落秋寒    时间: 2005-4-16 07:29

看得真是很累滴说
排序还好理解
链表和二叉树，头痛ing...
看来不太适合偶...
作者: 陈珺    时间: 2005-4-16 12:01

推荐一本电子书<<现代计算机常用数据结构和算法>>
http://www.9soho.com/Software/catalog25/576.html
作者: loranrowe    时间: 2005-4-18 10:50

声明一下，我写这系列帖子的目的并不是教书育人，不是传播知识
首先这是写给自己看的，用于梳理思路
其次，希望能够传播算法这门学科中表达出的某些思想
这些思想通常比解决问题的方法更有用
但是，现在看来这点做的并不是很成功  
拿来主义是主流，我很理解
当然，如果能作为"同学"的借鉴也是我希望看到的
所以，如果拿来当教程看，会很痛苦
学习还是要看书的
论坛上只能点到即止
作者: van    时间: 2005-4-18 10:52

链表和二叉树，头痛ing...

直接用STL好了，list和set
作者: Maxwell    时间: 2005-4-19 08:39

set是集合吧，不是二叉树。set的存储结构是树，不过恐怕真用到树的地方set是不够的。
作者: loranrowe    时间: 2005-4-19 12:21

第九日：动态规划
今天开始来点有意思的
分治思想将问题分解为独立的子问题
解决子问题，并将答案合并就可以得到总问题的解
但是，很多情况下，分解开的子问题之间并不是相互独立的
动态规划方法利用了这种相关性，给出了一种通用的解决方案

动态规划可以解决这样一类问题：
1、如果问题的解决是需要分阶段的（可以分解为子问题）
2、每个子问题的解决都依赖于之前阶段子问题的解决，也就是说，存在子子问题，子问题和子子问题之间存在相关性，子问题共享子子问题的解
3、每个子子问题只出现一次，或者说，只有一个答案，存在最优解。这样，我们就可以建一个表，把它们记下来
用空间换取时间，这个道理说出来，大家都能理解
可是真正第一个提出问题并想到这种解决方法的人，无疑是天才

动态规划通常用于解决“最优问题”
这类问题通常存在很多解决方案，每个方案都对应一个值
我们希望求出得到最优(最大、最小)值的那个解决方案

动态规划算法的解决步骤可以采取以下四步
1、刻画最优解的结构
2、以递归的方法求最优解
3、回推，求得最优解的值

举一个矩阵连乘的例子
有一个矩阵序列(A_1,A_2,...,A_n)
如果我们希望计算矩阵的乘积A_1A_2...A_n
矩阵乘法仅定义了两两相乘的规则
一个p*q的矩阵和一个q*r的矩阵相乘，最终获得一个p*r的矩阵
算法如下：
MATRIX-MULTIPLY(A,B )
1 if columns[A] <> rows[B] //只有第一个矩阵的列数和第二个矩阵的行数相同，两个矩阵才可以相乘
2   then error "矩阵不相容"
3   else for i <- 1 to rows[A]
4           do for j <- 1 to columns[B]
5                 do C[i,j] <- 0
6                    for k <- 1 to columns[A]
7                       do C[i,j] <- C[i,j] + A[i,k] * B[k,j]
8        return C

可以看出，为了计算两个矩阵的乘积，一共要进行(p*q*r)次乘法运算
我们的目标是要尽量减少连乘时乘法运算的次数，以加快运算速度

以三个矩阵连乘为例
我们有以下两种种计算最终结果的运算顺序
A_1(A_2A_3)
(A_1A_2)A_3
假设它们分别是10×100,100×5,5×50的矩阵
那么，第一种顺序的乘法次数为：100*5*50+10*100*50 = 25000+50000 = 75000
第二种顺序的乘法次数为： 10*100*5+10*5*50 = 5000+2500 = 7500
差距还是很大di

考虑这个问题的特点，乘法次数与矩阵的内容无关，仅与矩阵的下标相关
我们要做的就是给矩阵加括号，事实上也就是给下标加括号
n个矩阵连乘，加括号的方法一共有
P(n)={
1, if n = 1
sigma(k=1, to n-1, P(k)P(n-k)), if n >= 2
}
将相邻矩阵的重复下标去除后，矩阵序列A的下标序列记为：
p=(p_0,p_1,...,p_n)

解决问题的第一步是找到最优解的结构，也就是如何通过子问题的最优解构建总问题的最优
我们将子问题的最优解记为m[i,j]，如果求得了i=1,j=n时得m，问题就解决了
对于n个矩阵连乘，无论如何加括号，最终总是可以分解为两个矩阵的乘法
可以简记为(A_1...A_i)*(A_i+1...A_n)
前面括号里面乘积是一个矩阵，后面也是
那么这样一组括号总的乘法次数为
m[1,i]+m[i+1,n]+p_0*p_i*p_n

然后是递推求解过程
n个矩阵一个有n-1组括号
所以
m[1,n]=
={
0, if n = 1
min{m[1,k]+m[k+1,n]+p_0*p_k*p_n}, if n > 1
}

m[i,j]{
0, if i = j
min{m[i,k]+m[k+1,j]+p_i-1*p_k*p_j}, if i < j
}

通过序列p，可以把每个m[i,j]都计算出来，记录它们的结果
一共需要记录(n*(n+1)/2)个结果

最后，通过这个公式
m[i,i+1]=p_i-1*p_i*p_i+1
就可以得到最终结果了

这样只是得到了最终结果的值，如果我们希望知道括号是如何加的(对连乘计算过程有意义)
还需要在每次计算m[i,j]时，记录k的取值

循环形式的具体算法：
MATRIX-CHAIN-ORDER(p)
1 n <- length[p] - 1
2 for i <- 1 to n
3    do m[i,i] <- 0
4 for l <- 2 to n //l表示链长
5    do for i <- l to n-l+1
6          do j <- i+l-1
7             m[i,j] <- infinite
8             for k <- i to j-1
9                do q <- m[i,k]+m[k+1,j]+p_i-1*p_k*p_j
10                  if q < m[i,j]
11                     then m[i,j] <- q
12                          s[i,j] <- k
13 return m and s
递归形式的算法留给大家自己写一下

这种方法大致运行时间为o(n^3)
空间消耗前面计算过，是n*(n+1)/2


作业：
1、写出递归形式的连乘算法
2、计算下标序列为
(5,10,3,12,5,50,6)
的矩阵连乘所需的最少乘法数
试着通过直觉提出一种算法
如果和你通过以上算法得到的答案一致的话
能不能证明这种直觉方法总是有效的？
作者: loranrowe    时间: 2005-4-19 12:43



QUOTE:
原帖由van于2005-04-18, 10:52:49发表
直接用STL好了，list和set

STL是c++的标准库吧？
不是每种语言都会定义基本数据结构的
如果我用C、pascal甚至BASIC语言写程序的时候
它们没有提供这种支持
只能通过语言提供的基本数据类型和功能进行组合和扩展
现在的编程工具(并不仅仅是语言本身)
提供了太多的kits，相应的，文档也膨胀了n倍
可是语言本身的功能并没有多大提高
计算机语言的演变只是想让开发者使用起来更轻松
可是事情并不见得如此
搞明白原理才能有备无患啊
作者: 陈珺    时间: 2005-4-20 19:16

我把我对哈希表理解说说
有一大堆数据,每个数据面前都做个记号,然后将这些记号分类,一种类型给一种名称.需要用的时侯只要把类型名称输入就会输出这些记号.
我的理解对不对呢
作者: loranrowe    时间: 2005-4-21 11:01

大概差不多吧，呵呵，理解这种东西不好评价
我认为，哈希的关键在于映射关系，可以把这种关系理解为索引
以有限的空间对应较多的数据，提高检索、修改等操作的效率
后面还要提到一种更为极端的数据结构B树
以极为有限的空间对应极多的数据，因此被广泛应用于跟物理存储相关的系统中
比如操作系统、数据库等等
作者: Maxwell    时间: 2005-4-21 13:13

哈希可以当作这么个过程，有n张卡片m个盒子，为了检索卡片方便，可以用某种方法根据卡片的内容计算出一个编号，然后到指定编号的盒子里去找这张卡片。它快就快在不需要从第一张卡片开始比较，而是根据你要找的内容算出它在哪个盒子里。所以哈希算法的好坏是由计算编号的算法决定的。
作者: loranrowe    时间: 2005-4-21 15:46

第十日：贪心算法
贪心算法和前面的动态规划一样，都不是具体的算法，而是一类解决问题方法的总称
它们要解决的问题也差不多
都可以分解为子问题，子问题都存在最优解
但是，贪心算法与动态规划的不同在于
贪心算法在解决每个阶段问题的时候，仅考虑当前阶段的最优解
而不考虑“将来”哪些子问题将成为最优解的组成部分，绝不为将来打算
这样，与动态规划相比，贪心算法在存储空间和运算时间上都具有优势
不过，无法保证“贪心”出来的结果一定是最好的

贪心算法的一个著名的例子：
霍夫曼编码(Huffman codes)
霍夫曼编码用于解决这样一个问题：
在通讯中需要传输大量的信息，我们希望通过对通讯内容进行编码使得通讯长度最小，以降低通讯成本
这就需要对通讯内容重新编码
一种基于统计的方法认为，如果我们给出现频率较多的“码”以较短代号，那么就可以有效的降低通讯的长度
Huffman code就是这样一种编码方法，它把固定长度的编码方案，替换为变长的编码方案

在计算机中，最简单的变长编码方案应该是以二进制数字，从小到大对应于出现频率从大到小的“码”
但是，这样在解码，也就是编码的反过程中，会出现二义性
比如，将e->0，a->1，b->01,c->10,d->11
那么，如果需要解码：1001
我们就无法知道，原码到底是aeea还是cb
这样就引出了一个概念：前缀编码
每个编码后的单词，不会是其他单词的前缀
比如以下编码方案：0,10,110,1110...
这样从前向后读编码后的文字，就不会出现二义性了

Huffman code显然考虑到了这一点，它以二叉树的形式提供编码方案
每个叶子节点表示一个编码
以深度表示编码长度
以左右表示0、1

由于叶子节点不存在子节点，所以可以避免成为其他编码的前缀

Huffman code的具体编码方案如下：
HUFFMAN(C )
1 n <- size_of[C]
2 Q <- C
3 for i <- 1 to n-1
4    do allocate a new node z
5       left[z] <- x <- EXTRACT-MIN(Q)
6       right[z] <- y <- EXTRACT-MIN(Q)
7       f[z] <- f[x] + f[y]
8       INSERT(Q,z)
9 return EXTRACT-MIN(Q)
解释一下
以上的伪代码是类C语言风格的，连续的赋值语句从右向左进行
C是待编码字母的集合，EXTRACT-MIN(X)操作从集合X中取f值最小的元素，被取出的元素不再属于集合X
f表示字母出现的频率，f值越小，越不容易在文章中出现

为什么说Huffman编码过程是一个Greedy过程呢？
原因就在于EXTRACT-MIN()操作，
每次该操作都会取出出现频率最小的那个元素，而不考虑取出的元素对整体编码方案是否最优

那么，到底Huffman code是不是一个最优的前缀编码方案呢？
如果不是，那它也不会这么有名了  
那么怎么定义最优呢？
如果一种方案得到的编码，平均长度比其他编码方案都要小，那么它就是最优的
这里的平均是经过f加权的平均值
证明过程就不写了
有兴趣可以自己证明，很简单

最后以一个问题结束，这个问题说明了Greedy不总是正确的
找零钱问题：
如果我们假设一种零钱方案如下：
1分、10分、20分、50分
提出一种贪心方法，使得每次支付得零钱数量最少

如果零钱方案变化为
1、5、8、10
原有方案是否可行？
为什么？
作者: Maxwell    时间: 2005-4-21 17:33

哈夫曼是贪心算法吗？好像不是吧？哈夫曼不是通过完整统计做出的最优结果吗？有种动态哈夫曼没准可以算贪心算法，不过对哈夫曼是贪心算法表示怀疑。
作者: loranrowe    时间: 2005-4-22 09:27



QUOTE:
原帖由Maxwell于2005-04-21, 17:33:57发表
哈夫曼是贪心算法吗？好像不是吧？哈夫曼不是通过完整统计做出的最优结果吗？有种动态哈夫曼没准可以算贪心算法，不过对哈夫曼是贪心算法表示怀疑。

Huffman树的构建过程确实是Greedy过程
完整统计只是统计了原始字母出现的频率
算法中所使用的贪婪准则为：从可用的二叉树中选出权重最小的两棵。
类似的还有最小生成树算法等等
Huffman编码最终会产生最优结果
这并不影响它是一个Greedy算法
再比如说背包问题
要求得无限制背包问题的最优解，动态规划是少不了的
甚至没有一个多项式时间的解法
但如果对放入背包的物品作一定的限制
Greedy过程足矣

有专门的关于什么样的问题，采用Greedy算法能够得到最优解的讨论
不过用到了线性代数中拟阵这个概念
就不贴了
作者: Maxwell    时间: 2005-4-22 10:43

搜索了一下，确实有把哈夫曼当作贪心算法的，不过也有很多不把它当成贪心算法的，这难道是个人看法不同？
我的理解贪心算法只能算那种可能产生不了最优解的算法，哈夫曼本身就是冲着整体最优解去的，只是这个问题正好每一步都是局部最优解，我倒是觉得它有一点分治的意思。
作者: loranrowe    时间: 2005-4-22 10:53



QUOTE:
原帖由Maxwell于2005-04-22, 10:43:39发表
搜索了一下，确实有把哈夫曼当作贪心算法的，不过也有很多不把它当成贪心算法的，这难道是个人看法不同？
我的理解贪心算法只能算那种可能产生不了最优解的算法，哈夫曼本身就是冲着整体最优解去的，只是这个问题正好每一步都是局部最优解，我倒是觉得它有一点分治的意思。

有一种说法是
如果找到一种能够解决现有问题的Greedy算法
就坚决的使用它
不要管它是不是最优的
至于分治
我认为它是所有算法思想的最初来源



欢迎光临 轩辕春秋文化论坛 (http://xycq.org.cn/forum/) Powered by Discuz! 5.0.0