算法导论

按有用程度 按页码先后 最新笔记

• 

  第168页

  KingsamChen (math,english,computer science)

  红黑树插入实例供图的b到c步骤中 c的图示印刷错了 (更多)

  红黑树插入实例供图的b到c步骤中

  c的图示印刷错了 (收起)

  2011-05-18 10:23:44   10回应

  收藏

  推荐
• 

  第557页

  [已注销]

  第32章 字符串匹配问题是指从一个较长字符串中找到一个和较短字符串完全相同的子串,输出所以符合条件的位移. 直觉上,所有确定性算法的时间复杂度的下限在O(n).n为长串长度.因为至少需要把长串中的所有字符遍历一遍得到结果.最后的KMP算法也确实达到了这个下限.说明在确定性算法中,不可能再有一个算法对此算法有明显性能提高了. 最简单的朴素算法是,将字符串中的每一个字符和模式中的第一个字符比较,如果不同,... (更多)

  第32章

  字符串匹配问题是指从一个较长字符串中找到一个和较短字符串完全相同的子串,输出所以符合条件的位移.

  直觉上,所有确定性算法的时间复杂度的下限在O(n).n为长串长度.因为至少需要把长串中的所有字符遍历一遍得到结果.最后的KMP算法也确实达到了这个下限.说明在确定性算法中,不可能再有一个算法对此算法有明显性能提高了.

  最简单的朴素算法是,将字符串中的每一个字符和模式中的第一个字符比较,如果不同,比较字符串第二个字符.如果相同,则比较模式中的第二个字符,直到完全匹配.这种方式的时间复杂度为O((n - m + 1)m).其中m是模式串长度,n是字符串长度.

  书中的第二个算法是kabin-karp算法.该算法的核心思想是,将模式串转化为一个基数为d的数字.其中d等于字母表中字母的个数.这样以来,模式串就变成了一个数字,而匹配字符串就变成了(n - m + 1)个数字.只需要比较(n - m + 1)次就可以得到结果.当然这里需要一些额外的预处理时间.计算这个d进制的数字需要O(m)的时间.虽然这个算法最坏情况下时间复杂度和上面的相同,实际使用中效果要好许多.

  算法性能的真正提高总是伴随着冗余数据的去消.这一步的优化将机器的性能发挥到最大.因为普通的机器一次可以将两个2^32以内的数字比较大小.而上面的朴素算法每次只比较一个很小的数字.

  举例说明,字符串为232332.模式串为236.朴素算法首先比较2和2,然后3和3,然后2和6不同,不匹配.而kabin-karp算法则是比较236和232不同.因为机器有能力一次就比较这么大的数字.

  那是不是说,比如机器字长为8,当模式串的值到256的时候就达到性能顶峰了呢?不是的.因为我们发现,全部所有可能的数字出现的可能性是比较低的,就本例而言,三字组从000到256每个都出现在长字串中,概率是比较小的.这说明8位的字长,可以表示更多的数字.比如我们将数字除以2来比较,那么上例中第二步比较时,长字串中值为323,模式串为236.6是偶数,3不是.所以不匹配,无论323前面两位是什么数字.当然这种方式误差也比较大,比如236是偶数,第一个232也是.

  这是因为除以2这个选择实在是太糟糕了.一般情况下都会选择一个素数.通过合理计算可以找到一个最优的数字.突然想到哈代曾经说,从实用主义的角度来看,他一生的价值为零.唏呈不已.

  通过合适的选择数值,机器和数字两方面都可以达到最好性能.那还有性能提高的空间吗?有的.

  编程中有一种很常用的方式是用时间来换空间,或者相反,用空间来时间.有限自动机的方法就是这样一种方法,它用空间来换取时间上的性能提高.不过如果单纯的交换不能叫性能提高.这种方式还利用了另外一个信息论中的原理:一件事物出现的概率越大,它包含的信息量越小.那么在一个有限长度的模式串中,它和所有等长的字符串的比较结果就只有有限个.而且,在比较字串前面取消一个字符,后面添加一个字符,这样的结果变化集也是有限的.

  也就是说,在很长很长的匹配过程中,出现的不同的匹配情况只有很少的有限种.频繁出现的情况包含的信息量小,我们就可以在计算机上用更少的空间来表示它.而不是每次出现都重新表示.

  这么做了以后,似乎已经没有任何可以提高的空间了.knuth,morris和pratt在1977年发表了一篇文章<fast pattern matching in strings>.再次爆表.

  我们知道,匹配算法已经不可能再提高了.所以KMP算法是对有限状态机中预处理算法进行的明显优化.

  不过看了这个算法之后,我不敢相信,这几个作者要把这个算法放在最后讲解.因为这个思路我自己一开始都隐隐有了.这个优化再次减少了冗余信息.它把有效信息保留,而不是每次比较以后都丢弃,而这些辅助的信息的数目又是有限的.

  它的思路是,在比较了若干个字符匹配以后,如果下一个字符不匹配,则前面匹配的字符是有用的信息.即如果后面的字符不同,可以直接跳过.

  比如,模式串ababaca.匹配到ababaabc..时,前面5个字符匹配,但第6个字符不匹配.那我们可以提前计算到,向后移一位,babaabc不可能匹配,因为前面第一个字符就不匹配.所以可以直接去匹配abaabc...

  我们来计算模式ababababca.如果仅有一个匹配,那么下一次后移一位.即pie(1)=1.如果仅匹配两位,那么下一次后移两位.因为后移一位是不可能匹配的.所以pie(2)=2.如果仅匹配三位,则后移三位.pie(3)=3.依次类推...

  代码后面给...

  //by dilfish at yantai
  #include <stdio.h>
  #include <string.h>
  #include <stdlib.h>
  #include <sys/types.h>
  #include <sys/stat.h>
  #include <fcntl.h>
  
  #define IDXLEN (10000)
  int idx = 0;
  unsigned long int naiveidx[IDXLEN] = {0};
  unsigned long int kmpidx[IDXLEN] = {0};
  
  
  //check the two ways result
  int check_idx(void)
  {
   int i,flag = 0;
   for(i = 0;i < idx;i ++)
  	{
  	 if(naiveidx[i] != kmpidx[i])
  		{
  		 flag = 1;
  		 break;
  		}
  	}
   if(flag == 1)
  	 printf("error1\n");
   else
  	printf("%d matches\n",idx);
   return 0;
  }
  
  
  //make chars in [a,e]
  int make_string(unsigned char *ptr,unsigned long int num)
  {
   unsigned long int i;
   for(i = 0;i < num;i ++)
  	 ptr[i] = (ptr[i] % 5) + 'a';
   return 0;
  }
  
  
  //random numbers
  unsigned long int generate_random(void *ptr,unsigned long int n)
  {
   int fd,ret,slice;
   char buffer[100] = {0};
   unsigned long int num = 0;
   fd = open("/dev/urandom",O_RDONLY);
   if(fd < 0)
  	return 0;
   while(num < n)
  	{
  	 if(n - num >= 100)
  		slice = 100;
  	 else
  		slice = n - num;
  	 ret = read(fd,ptr + num,slice);
  	 if(ret < 0)
  		break;
  	 num += ret;
  	}
   close(fd);
   return num;
  }
  
  
  //...
  int* compute_prefix_function(const unsigned char *p,int m)
  {
   int q,*pie = (int*)malloc(m * sizeof(int));
   int k = 0;
   bzero(pie,m * sizeof(int));
   pie[0] = 0;
   for(q = 1;q < m;q ++)
  	{
  	 while(k > 0 && p[k] != p[q])
  		k = pie[k];
  	 if(p[k] == p[q])
  		k ++;
  	 pie[q] = k;
  	}
   return pie;
  }
  
  
  //powered by Introduction to Algorithms
  int kmp(const unsigned char *str,const unsigned char *pattern)
  {
   int i,n,m,*pie,q = 0;
   n = strlen(str);
   m = strlen(pattern);
   pie = compute_prefix_function(pattern,m);
   idx = 0;
   for(i = 0;i < n;i ++)
  	{
  	 while(q > 0 && pattern[q] != str[i])
  		 q = pie[q - 1];
  	 if(pattern[q] == str[i])
  		 q ++;
  	 if(q == m)
  		{
  		 if(idx < IDXLEN)
  			{
  			 kmpidx[idx] = i - m + 1;
  			 idx ++;
  			}
  	 	 q = pie[q - 1];
  		}
  	}
   free(pie);
   return 0;
  }
  
  
  //...
  int naive(const unsigned char *str,const unsigned char *pattern)
  {
   int i,j = 0;
   int n,m;
   n = strlen(str);
   m = strlen(pattern);
   idx = 0;
   for(i = 0;i < n - m + 1;i ++)
  	{
  	 while(str[i + j] == pattern[j] && j < m)
  		j ++;
  	 if(j == m)
  		 if(idx < IDXLEN)
  			{
  			 naiveidx[idx] = i;
  			 idx ++;
  			}
  	 j = 0;
  	}
   return 0;
  }
  
  
  int main(int argc,char **argv)
  {
   #define  NUM (1000000)
   unsigned char str[NUM + 1] = {0};
   unsigned char pattern[] = "aba";
   struct timeval tns,tne,tks,tke;
   generate_random(str,NUM);
   make_string(str,NUM);
   str[NUM] = 0;
   #undef NUM
   gettimeofday(&tns,NULL);
   naive(str,pattern);
   gettimeofday(&tne,NULL);
   gettimeofday(&tks,NULL);
   kmp(str,pattern);
   gettimeofday(&tke,NULL);
   printf("%lu,%lu\n",tns.tv_sec,tns.tv_usec);
   printf("%lu,%lu\n",tne.tv_sec,tne.tv_usec);
   printf("%lu,%lu\n",tks.tv_sec,tks.tv_usec);
   printf("%lu,%lu\n",tke.tv_sec,tke.tv_usec);
   check_idx();
   return 0;
  }
  

  (收起)

  2011-08-06 14:31:23   1回应

  收藏

  推荐
• 

  第547页

  fluxay

  这页主要是讲Miller-Rabin算法对 PSEUDOPRIME的改进， 但是没有讲清楚为什么要判断第三种情况返回false，第四种情况返回true。 看了半天发现就是定理31.34的简单应用。 (更多)

  这页主要是讲Miller-Rabin算法对 PSEUDOPRIME的改进，

  但是没有讲清楚为什么要判断第三种情况返回false，第四种情况返回true。

  看了半天发现就是定理31.34的简单应用。 (收起)

  2012-01-30 15:24:27   回应

  收藏

  推荐

• 

  第1页

  海鸥 (http://blog.sina.com.cn/u/1851)

  

  (更多)

  
  

  (收起)

  2011-07-24 17:48:24   回应

  收藏

  推荐
• 

  第3页

  大众米线 (我做个弹弓子砸KFC家玻璃)

  所谓算法，就是良好定义的计算过程，它取一个或一组值作为输入，并产生出一个或一组值作为输出。 (更多)

  所谓算法，就是良好定义的计算过程，它取一个或一组值作为输入，并产生出一个或一组值作为输出。

  (收起)

  2011-10-07 21:52:46   回应

  收藏

  推荐
• 

  第9页

  大众米线 (我做个弹弓子砸KFC家玻璃)

  插入排序： 将未排序的那个数插入一个局部排好序的数组中。 (更多)

  插入排序：

  将未排序的那个数插入一个局部排好序的数组中。 (收起)

  2011-10-07 21:58:21   回应

  收藏

  推荐

• 

  第547页

  fluxay

  这页主要是讲Miller-Rabin算法对 PSEUDOPRIME的改进， 但是没有讲清楚为什么要判断第三种情况返回false，第四种情况返回true。 看了半天发现就是定理31.34的简单应用。 (更多)

  这页主要是讲Miller-Rabin算法对 PSEUDOPRIME的改进，

  但是没有讲清楚为什么要判断第三种情况返回false，第四种情况返回true。

  看了半天发现就是定理31.34的简单应用。 (收起)

  2012-01-30 15:24:27   回应

  收藏

  推荐
• 

  附录 B.5 树

  keep_it_real (No fear.No distractions.)

  最近钻研CLRS，以求在数据结构与算法方面更进一步学习，着实发现国外教材的严谨，全面，严奶奶着实不及。也发现前路漫漫，其修远兮，我必须上下而求索。也发现了一些中外教材定义上不一致的地方，尤以树这个方面比较突出。 一些差别： 1.深度，高度的定义 在严教材中，对深度和高度有如下定义（P120）： 结点的层次从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第l层，则其子树的根就在第l+1层。......树.. (更多)

  最近钻研CLRS，以求在数据结构与算法方面更进一步学习，着实发现国外教材的严谨，全面，严奶奶着实不及。也发现前路漫漫，其修远兮，我必须上下而求索。也发现了一些中外教材定义上不一致的地方，尤以树这个方面比较突出。

  一些差别：

  1.深度，高度的定义

  在严教材中，对深度和高度有如下定义（P120）：

  结点的层次从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第l层，则其子树的根就在第l+1层。......树中结点的最大层次称为树的深度或高度。

  而在CLRS中，却有不同的定义（附录B.5.2,P672):

  从根r到结点x的路径长度称为x在T中的深度。结点在树中的高度是从结点向下到某个叶结点最长简单路径中边的条数。而树的高度也等于树中结点的最大深度。

  严版的定义深度和高度等价，作为树的属性。而CLRS中深度与高度“互补”其和为树的深度（高度），对于树，也有高度的属性。

  2.满二叉树与完全二叉树的定义

  严教材中满二叉树定义如下（P124）：

  一棵深度为k且有2^k - 1个结点的二叉树称为满二叉树。

  而在CLRS中，则有严重的差别（附录B.5.3 P672):

  满二叉树：每个结点或者是叶结点，或度数为2，不存在度为1的结点。

  对于完全二叉树，严教材定义为（P124）：

  可对满二叉树的结点进行编号，约定从根结点起，从左向右，从上至下。深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一 对应时，称之为完全二叉树。（备注写道此定义版本众多，本书以此为准）。

  CLRS中则为（附录B.5.3 P673）:

  完全二叉树是所有的叶子结点都有相同深度，且所有内部结点度都为2.

  在Wikipedia中，完全二叉树与国内定义一致，与CLRS中不同，如下：

  A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

  Wikipedia对perfect binary tree（完美二叉树）定义与国内的满二叉树相同，即：

  A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level, and in which every parent has two children.[1] (This is ambiguously also called a complete binary tree.)

  CLRS英文版中对完全k叉树定义为：

  A complete k-ary tree is a k-ary tree in which all leaves have the same depth and all internal nodes have degree k.

  对于这些差别，其实：

  然而，许多这些差别是由于翻译问题造成的，请听我道来：

  在Wikipedia中，完全二叉树与国内定义一致，如下：

  A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

  Wikipedia对perfect binary tree（完美二叉树）定义与国内的满二叉树相同，即：

  A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level, and in which every parent has two children.[1] (This is ambiguously also called a complete binary tree.)

  CLRS英文版中对完全k叉树定义为：

  A complete k-ary tree is a k-ary tree in which all leaves have the same depth and all internal nodes have degree k.

  CLRS的译者们对complete的翻译没有考虑道英文定义中本来存在的歧义还有国内约定俗成的定义的忽视，造成了这样的混乱。国内的定义中满二叉树即为perfect binary tree,其翻译与full binary tree相近，wikipedia中对full binary tree的定义与CLRS中一致，即：

  A full binary tree (sometimes proper binary tree or 2-tree or strictly binary tree) is a tree in which every node other than the leaves has two children.Sometimes a full tree is ambiguously defined as a perfect tree.

  但CLRS直接将 full binary tree翻译为满二叉树，与国内约定俗成的满二叉树（perfect binary tree)相冲突。这同样是忽略了国外定义存在的争议和国内约定俗成的说法而进行翻译。

  总结一下对应关系：

  国内 国外

  完全二叉树<--->a complete binary tree

  满二叉树 <--->a perfect binary tree(a complete binary tree [ambiguously])

  无对应名称，即全部结点度数要么为2，要么为0的二叉树<--->a full binary tree(sometimes called a perfect binary tree[ambiguously])

  我想说的：

  物理学与计算机科学都与数学有着最紧密的关系。但与物理学基于客观存在的、不随主观意志改变的宇宙不同，计算机科学是关于我们千千万万的程序员、计算机科学家、黑客们创造的新的世界运行规律的科学，这些规律，具体表现为形形色色的协议、算法，是我们人类制定的。所以争议一直会存在。许多没有实质差别的争议，如大端法与小端法，如从0开始计数和从1开始，只是一个标准问题。

  CLRS是一部庞大的书，英文版有近1000页，翻译的难度与工作量可想而知。但也希望译者们能充分考虑到英文定义中本来存在的争议和国内相关约定俗成的说法，为一份标准献一份力量。

  从中也能看出国内教材往往立意较浅，从实用角度介绍了许多重要的数据结构，严教材充斥着略显蹩脚的C代码，语言也有些晦涩，也是国内大学的氛围所致，但作为入门级读物已经是非常不错，它的练习册也很好。而CLRS则从数学的根基开始力图构建一个涉及广泛的重要的结构和算法的高楼大厦，从实际效果看，他成功达到了他的目标。他严谨，稳重，甚至稍有笨重。希望对结构与算法，对计算机科学有心趣的同学能够跟我一起学习。在此推荐一个豆列：http://book.douban.com/doulist/229594/ 希望对你有所帮助。 (收起)

  2012-01-27 13:47:57   回应

  收藏

  推荐
• 

  第八章 线性时间排序

  白轻扬

  问题1：决策树是满二叉树？ 中文版第97页，讲到一棵决策树是一棵满二叉树，查了查数据结构的书，满二叉树的定义是指深度为k且有2^k-1个节点的二叉树（严蔚敏《数据结构 C语言版》，按照导论上对深度的定义，应该修正为2^(k+1)-1）。从导论上所配的图8-1来说，显然这并不是满二叉树，所以感觉导论这点好像说的不对。 在导论上提出决策树模型时有个约定，假设所有输入元素不同。其实决策树模型也包含了输入序列中某些输入... (更多)

  问题1：决策树是满二叉树？

  中文版第97页，讲到一棵决策树是一棵满二叉树，查了查数据结构的书，满二叉树的定义是指深度为k且有2^k-1个节点的二叉树（严蔚敏《数据结构 C语言版》，按照导论上对深度的定义，应该修正为2^(k+1)-1）。从导论上所配的图8-1来说，显然这并不是满二叉树，所以感觉导论这点好像说的不对。

  在导论上提出决策树模型时有个约定，假设所有输入元素不同。其实决策树模型也包含了输入序列中某些输入值或者全部输入值相等的情况。

  问题2：

  决策树在同等输入规模下，是否因比较排序算法而异？

  对于不同的排序算法，我一开始觉得决策树的结构应该不一样。nlgn只是一个比较优的比较次数下界，对于某些效率不高的诸如冒泡、插入等算法，比较次数是n^2次，相应的决策树的高度也会升高。

  但是，决策树会不会本身就是一个满足最少比较次数的结构？毕竟，这个模型的提出就是为了找到一个比较次数的下界，模型的提出忽略了诸如元素在比较后的移动、比较的循环控制的信息，即，决策树展示的是比较排序算法在给定输入规模下的最小比较次数。因此我比较倾向于后一种理解，即给定输入规模下决策树的结构是确定的。

  问题3：

  课后习题8.1—3，不会做。

  对网络上看的答案表示不太能理解，一般都是根据定理8.1得出，但是问题是，定理中的h指的是决策树的（最大）深度，但是怎样说明n!种输入至少有一半都保持在h的深度？此题目解答暂定。

  问题4：

  课后习题8.1-4，关于最后题目给出的提示的一点思考

  题目最后给了提示，一直不太明白其意义。后来在参考了答案的情况下才了解，题中给的n/k个子序列并非相互独立（尽管有条件：：每个子序列的元素都小于后继子序列元素，大于前驱子序列元素）可以认为第i+1个子序列的决策树是以第i个子序列的决策树为基础的（这时第i个子序列的比较已经完毕），应该从一共（至少）有(k!)^(n/k)个叶节点入手。

  如果n/k个子序列相互独立，那么问题就变成了对n/k个长度为k的元素分别进行比较，再将比较次数相加就可以了。这样根据定理8.1-4，可得出比较次数应该是不少于(n/k)(klgk) = nlgk。虽然结果是一样的，但是问题的背景是不同的。 (收起)

  2011-11-25 20:52:15   回应

  收藏

  推荐