标题: 算法笔记, 第十日:贪心算法
性别:未知-离线 loranrowe

Rank: 3Rank: 3Rank: 3
组别 士兵
级别 奋威校尉
好贴 1
功绩 6
帖子 143
精华 0 点
现金 2136 通宝
编号 17767
注册 2004-9-16


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


推荐贴
顶部
性别:未知-离线 Maxwell

陈国公
监管使
枢密直学士
山南西道节度使

Rank: 18Rank: 18Rank: 18
柱国(正二品)
组别 节度使
级别 征东将军
好贴 4
功绩 1845
帖子 5764
精华 6 点
现金 144 通宝
编号 622
注册 2004-7-7


发表于 2005-1-19 14:30 资料 文集 短消息 只看该作者
呵呵,我记得有本书上定义是对于任何有效输入都可以在有限步内停机的自动机,更抽象吧


推荐贴
顶部
性别:男-离线 天痕

白衣伯爵中大夫

Rank: 10Rank: 10Rank: 10Rank: 10
组别 白衣卿相
级别 右将军
好贴 4
功绩 224
帖子 1150
精华 1 点
现金 2162 通宝
编号 208
注册 2003-8-29




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

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

对算法,搞竞赛的有这么个说法:给到题要求40分钟内解决,至少要花20分钟在考虑算法上                  当然过于简单的题不算
推荐贴
顶部
性别:未知-离线 Maxwell

陈国公
监管使
枢密直学士
山南西道节度使

Rank: 18Rank: 18Rank: 18
柱国(正二品)
组别 节度使
级别 征东将军
好贴 4
功绩 1845
帖子 5764
精华 6 点
现金 144 通宝
编号 622
注册 2004-7-7


发表于 2005-1-19 15:34 资料 文集 短消息 只看该作者


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

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

这是在学校图书馆借的一本老书上的定义,书不算很厚,蓝皮,我觉得写的很好,比现在某些算法书强不少。
呵呵,过于简单的题也不会给40分钟。
推荐贴
顶部
性别:未知-离线 loranrowe

Rank: 3Rank: 3Rank: 3
组别 士兵
级别 奋威校尉
好贴 1
功绩 6
帖子 143
精华 0 点
现金 2136 通宝
编号 17767
注册 2004-9-16


发表于 2005-1-19 15:46 资料 短消息 只看该作者
呵呵,还真有人看啊,坚定了我继续写下去的信心
我现在看的这本书,是the MIT Press出的Introduction to Algorithms
这本书应该是现在比较权威的教材之一了
争取用一到两个月的时间review一下
这本笔记做完,我准备从头再来一遍C++
VC用了好久,还没仔细学习过C++呢
Maxwell到时要多指教啊...
推荐贴
顶部
性别:未知-离线 Maxwell

陈国公
监管使
枢密直学士
山南西道节度使

Rank: 18Rank: 18Rank: 18
柱国(正二品)
组别 节度使
级别 征东将军
好贴 4
功绩 1845
帖子 5764
精华 6 点
现金 144 通宝
编号 622
注册 2004-7-7


发表于 2005-1-19 15:55 资料 文集 短消息 只看该作者
呵呵,客气了,我虽然程序写了不少,可是算法真没仔细研究过,正要跟兄好好学习一下
推荐贴
顶部
性别:男-离线 dollbean

Rank: 4
组别 士兵
级别 裨将军
功绩 3
帖子 304
精华 0 点
现金 2600 通宝
编号 30176
注册 2005-1-13


发表于 2005-1-19 17:06 资料 短消息 只看该作者
算法是程序设计的精髓,好好学习一下
推荐贴
顶部
性别:未知-离线 loranrowe

Rank: 3Rank: 3Rank: 3
组别 士兵
级别 奋威校尉
好贴 1
功绩 6
帖子 143
精华 0 点
现金 2136 通宝
编号 17767
注册 2004-9-16


发表于 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

Rank: 3Rank: 3Rank: 3
组别 士兵
级别 奋威校尉
好贴 1
功绩 6
帖子 143
精华 0 点
现金 2136 通宝
编号 17767
注册 2004-9-16


发表于 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))
想知道怎么得出来得么?我也想知道,明天见!
推荐贴
顶部
性别:未知-离线 金圭子

白衣伯爵中大夫

Rank: 14Rank: 14Rank: 14Rank: 14Rank: 14
组别 白衣卿相
级别 征西将军
好贴 4
功绩 265
帖子 4925
精华 5 点
现金 2303 通宝
编号 27961
注册 2004-12-16


发表于 2005-1-21 16:33 资料 文集 短消息 只看该作者
一直觉得这儿的确需要有人轮番讲课了。起码一个月讲一门吧…………(MW:就等你呢 -_\\,金圭子:做梦!!)

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

不过我本人喜欢码字,但是从来没耐心看…………这个也是我到现在还不是名角只是票友的原因………………
推荐贴
顶部
性别:未知-离线 Maxwell

陈国公
监管使
枢密直学士
山南西道节度使

Rank: 18Rank: 18Rank: 18
柱国(正二品)
组别 节度使
级别 征东将军
好贴 4
功绩 1845
帖子 5764
精华 6 点
现金 144 通宝
编号 622
注册 2004-7-7


发表于 2005-1-21 18:25 资料 文集 短消息 只看该作者
金圭子把我想说的话替我说了。
推荐贴
顶部
性别:未知-离线 loranrowe

Rank: 3Rank: 3Rank: 3
组别 士兵
级别 奋威校尉
好贴 1
功绩 6
帖子 143
精华 0 点
现金 2136 通宝
编号 17767
注册 2004-9-16


发表于 2005-1-21 23:08 资料 短消息 只看该作者
两个人就知道灌水!
推荐贴
顶部
性别:未知-离线 Maxwell

陈国公
监管使
枢密直学士
山南西道节度使

Rank: 18Rank: 18Rank: 18
柱国(正二品)
组别 节度使
级别 征东将军
好贴 4
功绩 1845
帖子 5764
精华 6 点
现金 144 通宝
编号 622
注册 2004-7-7


发表于 2005-1-22 08:36 资料 文集 短消息 只看该作者
被批评了。。。
  我一直在认真读文章,还需要多多指点我啊。
推荐贴
顶部
性别:男-离线 天痕

白衣伯爵中大夫

Rank: 10Rank: 10Rank: 10Rank: 10
组别 白衣卿相
级别 右将军
好贴 4
功绩 224
帖子 1150
精华 1 点
现金 2162 通宝
编号 208
注册 2003-8-29




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

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

要说的就这么多,有时间的话附个程序给大家看一下。
推荐贴
顶部
性别:未知-离线 loranrowe

Rank: 3Rank: 3Rank: 3
组别 士兵
级别 奋威校尉
好贴 1
功绩 6
帖子 143
精华 0 点
现金 2136 通宝
编号 17767
注册 2004-9-16


发表于 2005-1-23 10:08 资料 短消息 只看该作者


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

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

一般来说,递归调用时保存的现场信息是压入栈中存放的
想要获得更大的递归深度,可以通过修改栈的大小实现
不过也不能从根本上解决问题
递归都可以改写为循环,这样就不受栈溢出的困扰了
不过这些不是算法要讨论的内容...
推荐贴
顶部
性别:未知-离线 Maxwell

陈国公
监管使
枢密直学士
山南西道节度使

Rank: 18Rank: 18Rank: 18
柱国(正二品)
组别 节度使
级别 征东将军
好贴 4
功绩 1845
帖子 5764
精华 6 点
现金 144 通宝
编号 622
注册 2004-7-7


发表于 2005-1-26 12:45 资料 文集 短消息 只看该作者
loranrowe可否把这些算法详细讲讲,不然我想大多数人是看不懂的
推荐贴
顶部
性别:未知-离线 loranrowe

Rank: 3Rank: 3Rank: 3
组别 士兵
级别 奋威校尉
好贴 1
功绩 6
帖子 143
精华 0 点
现金 2136 通宝
编号 17767
注册 2004-9-16


发表于 2005-1-26 15:37 资料 短消息 只看该作者


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

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

陈国公
监管使
枢密直学士
山南西道节度使

Rank: 18Rank: 18Rank: 18
柱国(正二品)
组别 节度使
级别 征东将军
好贴 4
功绩 1845
帖子 5764
精华 6 点
现金 144 通宝
编号 622
注册 2004-7-7


发表于 2005-1-26 18:15 资料 文集 短消息 只看该作者
其实说起来笔记是比较提纲挈领言简意赅就可以了,不过可能多数人没有接触过这个,只凭三言两语看的摸不着头脑的,所以loranrowe兄应该详细的解释解释啊。
推荐贴
顶部
性别:未知-离线 loranrowe

Rank: 3Rank: 3Rank: 3
组别 士兵
级别 奋威校尉
好贴 1
功绩 6
帖子 143
精华 0 点
现金 2136 通宝
编号 17767
注册 2004-9-16


发表于 2005-1-26 18:27 资料 短消息 只看该作者


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

前面已经写完的就先这样吧...  
后面我会注意的
说起来,排序算法是全部算法中最简单和普及的内容了
确实写的比较略
还好马上就要到不得不提、不得不详细写的数据结构部分了
推荐贴
顶部
性别:未知-离线 Maxwell

陈国公
监管使
枢密直学士
山南西道节度使

Rank: 18Rank: 18Rank: 18
柱国(正二品)
组别 节度使
级别 征东将军
好贴 4
功绩 1845
帖子 5764
精华 6 点
现金 144 通宝
编号 622
注册 2004-7-7


发表于 2005-1-26 18:55 资料 文集 短消息 只看该作者
虽然比较普及,但是基数桶那一篇非专业的应该了解的不多,再说这些算法看起来简单理解可不简单
推荐贴
顶部
性别:未知-离线 loranrowe

Rank: 3Rank: 3Rank: 3
组别 士兵
级别 奋威校尉
好贴 1
功绩 6
帖子 143
精华 0 点
现金 2136 通宝
编号 17767
注册 2004-9-16


发表于 2005-1-27 11:26 资料 短消息 只看该作者
排序(二)已修改
下午来贴第六日
推荐贴
顶部
性别:男-离线 kingofworl

Rank: 7Rank: 7Rank: 7Rank: 7
组别 校尉
级别 右将军
好贴 1
功绩 21
帖子 1022
精华 0 点
现金 3040 通宝
编号 18811
注册 2004-10-12


发表于 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

Rank: 3Rank: 3Rank: 3
组别 士兵
级别 奋威校尉
好贴 1
功绩 6
帖子 143
精华 0 点
现金 2136 通宝
编号 17767
注册 2004-9-16


发表于 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

Rank: 3Rank: 3Rank: 3
组别 士兵
级别 奋威校尉
好贴 1
功绩 6
帖子 143
精华 0 点
现金 2136 通宝
编号 17767
注册 2004-9-16


发表于 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

Rank: 3Rank: 3Rank: 3
组别 士兵
级别 奋威校尉
好贴 1
功绩 6
帖子 143
精华 0 点
现金 2136 通宝
编号 17767
注册 2004-9-16


发表于 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、实现新的操作

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

Rank: 4
组别 校尉
级别 忠义校尉
功绩 18
帖子 261
精华 1 点
现金 8282 通宝
编号 27418
注册 2004-12-10
家族 轩辕学院


发表于 2005-4-15 20:26 资料 主页 文集 短消息 只看该作者
这些东西给一些不是专业的人讲没有太大意义
在我们竞赛小组老师一对一讲都讲得很痛苦 何况这么网上文字叙述?
推荐贴
顶部
性别:女-离线 叶落秋寒

英国公主监造使谏议大夫

Rank: 12Rank: 12Rank: 12
组别 翰林学士
级别 后将军
功绩 447
帖子 1572
精华 9 点
现金 398 通宝
编号 108
注册 2005-1-29
来自 天界


看得真是很累滴说
排序还好理解
链表和二叉树,头痛ing...
看来不太适合偶...
推荐贴
顶部
性别:未知-离线 陈珺

Rank: 6Rank: 6Rank: 6
组别 校尉
级别 军师将军
好贴 5
功绩 26
帖子 927
精华 0 点
现金 2646 通宝
编号 3820
注册 2003-12-27
来自 福建福州


发表于 2005-4-16 12:01 资料 个人空间 短消息 只看该作者
推荐一本电子书<<现代计算机常用数据结构和算法>>
http://www.9soho.com/Software/catalog25/576.html
推荐贴
顶部
性别:未知-离线 loranrowe

Rank: 3Rank: 3Rank: 3
组别 士兵
级别 奋威校尉
好贴 1
功绩 6
帖子 143
精华 0 点
现金 2136 通宝
编号 17767
注册 2004-9-16


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

平曲侯泸川军节度使

Rank: 13Rank: 13Rank: 13Rank: 13
柱国(正二品) 工神
组别 节度使
级别 军师将军
好贴 3
功绩 475
帖子 984
精华 11 点
现金 17517 通宝
编号 25461
注册 2004-11-24


发表于 2005-4-18 10:52 资料 主页 文集 短消息 只看该作者
链表和二叉树,头痛ing...

直接用STL好了,list和set


推荐贴
顶部

正在浏览此帖的会员 - 共 1 人在线




当前时区 GMT+8, 现在时间是 2019-9-18 23:14
苏ICP备11088966号 轩辕春秋 2003-2015 www.xycq.net

Powered by Discuz! 5.0.0 2001-2006 Comsenz Inc.
Processed in 1.123202 second(s), 8 queries , Gzip enabled

清除 Cookies - 联系我们 - 轩辕春秋 - Archiver - WAP