《编程珠玑》笔记（第11-15章完）

• 第11章 排序
• 第12章 取样问题
• 第14章 堆

第11章 排序

1. 使用快排思想在O(字符总数)的复杂度下对n个长度不一的01串排序

   • 解：设x[0,...,n-1]中每一项都包含一个整数length和一个指向数组bit[1,...,length]的指针：

     1
     2
     3
     4
     5
     6
     7
     8
     9
     10
     11
     void bsort(l, u, depth)
       if l >= u return
       for i = [l, u]
         if x[i].length < depth
           swap(i, l++)
       m = l
       for i = [l, u]
         if x[i].bit[depth] == 0
           swap(i, m++)
       bsort(l, m-1, depth+1)
       bsort(m, u, depth+1)
     

     这其实就是一个基数排序思想。

第12章 取样问题

1. 输出\([0, n-1]\)范围内的\(m\)个随机整数（不能重复），要求每个子集被选取的可能性相等（这比要求每个数均以\(m/n\)概率选中的要求更强，见下文另一个习题）。
   • 解I

     • Knuth的方法，时间复杂度O(n)，空间复杂度O(1)：

       1
       2
       3
       4
       5
       6
       7
       select = m
       remaining = n
       for i = [0,n)
         if (bigrand() % remaining) < select
           print i
           select--
         remaining--
       

     • 证明：设选择的数为\(i_1, i_2, i_3, …, i_m\)。则选中这组数的概率为： \(\begin{eqnarray*} P &=& (1-\frac{m}{n})(1-\frac{m}{n-1})*\cdots*(1-\frac{m}{n-(i_1-1)})*\frac{m}{n-i_1} \\ & & *(1-\frac{m-1}{n-i_1-1})(1-\frac{m-1}{n-i_1-2})*\cdots*(1-\frac{m-1}{n-(i_2-1)})*\frac{m-1}{n-i_2} \\ & & *\cdots \\ & & *(1-\frac{1}{n-i_{m-1}-1})(1-\frac{1}{n-i_{m-1}-2})*...*(1-\frac{1}{n-(i_m-1)})*\frac{1}{n-i_m} \\ &=& \frac{m!(n-m)!}{n!} \\ &=& \frac{1}{C_n^m} \end{eqnarray*}\) 故。

   • 解II

     • Floyd的基于集合的随机选择算法，用set实现，时间复杂度O(mlogm)，空间复杂度O(m)：

       1
       2
       3
       4
       5
       6
       7
       8
       9
       set S;
       for(int j = n-m+1; j < n; ++j) {
         int t = bigrand() % j;
         if(S.find(t) == S.end()){
           S.insert(t); // t not in S
         } else {
           S.insert(j); // t in S
         }
       }
       

     • 证明：首先，前\(n-m+1\)个数（即\(0\)到\(n-m\)）的每一个最终不被选中的概率都是（第一轮不被选中，且，第二轮不被选中，且，…，故用乘法）：

       \[\frac{n-m}{n-m+1}*\frac{n-m+1}{n-m+2}*...*\frac{n-2}{n-1}*\frac{n-1}{n}=\frac{n-m}{n}\]

       ，故用1减即得。

       对于数\(i (i>n-m)\)，由于其前\(x=i-(n-m)\)轮都没有机会被选中，而从第\(x+1\)轮（此前已经选了\(i-(n-m)\)个数）开始，最终不被选中的概率是：第\(x+1\)轮不被选中的概率*以后每一轮都不被选中的概率，即：

       \[\left( 1-\frac{i-(n-m)+1}{i+1} \right)*\frac{i+1}{i+2}*\cdots*\frac{n-1}{n}=\frac{n-m}{n}\]

     问：如何证明每个子集被选中的概率都相等？

2. 编程过程中几个重要步骤
   1. 正确理解所遇到的问题
   2. 提炼出抽象问题
   3. 考虑尽可能多的解法
   4. 实现一种解决方案
3. 习题2：从\(n\)个元素中随机选\(m\)个，给出一个算法，其中每个元素的选中概率相等，但某些子集的选中概率比其他子集大。
   • 解：只随机一次，得出一个数\(i\)，则选择\(i\), \((i+1)\%n\), \((i+2)\%n\), …, \((i+m-1)\%n\)。

第14章 堆

1. 习题5：装箱问题：将n个权值（每个都介于0和1之间）分配给最少数目的单位容量箱。
   • 其启发式解法：将每个权值放到第一个合适的箱中（按升序扫描箱）。实现方式如下：
     • 先考虑线段树解法：对箱数组建立线段树，每条线段表示该线段包含的箱子的最大剩余容量，即可将升序扫描的复杂度降为O(log(n))。
     • 再考虑简化：可直接构建一棵类似堆的二叉树而不用另外开辟O(n)的空间构建线段树。
2. 给一个单链表的每个结点额外增加一个指针，使得访问第i个元素的时间为O(log(n))。

   • 解：考虑类似树状数组的方案。让每个结点i指向结点2i，则访问路径为：

     1
     2
     3
     4
     5
     6
     7
     8
     void path(n)
       if n == 0 print "start at 0, "
       else if even(n)
         path(n/2)
         print "double to ", n
       else
         path(n-1)
         print "increment to ", n
     

3. 另外一种二分搜索结构 把一个2^k-1元有序数组拷贝到一个“堆搜索”数组b中：a中奇数位元素按顺序放到b的后半部分，模4余2位置的元素按顺序放到b的剩余部分的后半部分，etc。修改后的二分搜索从i=1开始，每次将i置为2i或2i+1。

   本质：这其实是一颗静态二叉排序树。