第二章 算法效率分析基础

我常常说，当你对所讲的内容能够进行度量并能够用数字来表达的时候，证明你对这些内容是有所了解的。如果你不能用数字来表达，表明你的认识是不完整的，也是无法令人满意的：无论它是什么内容，它也许正处于知识的初级阶段，但在你的思想中，几乎从没把它上升到一个科学的高度。——开尔文爵士（1824-1907）

不是所有能计算的都有价值，不是所有有价值的都能被计算。 ——阿尔伯特●爱因斯坦（1879-1955）

习题2.1

6. 对任意排序算法如何扩充，才能使它在最优情况下的键值比较次数正好等于$n-1$($n$当然是列表的大小)。你认为这个方法对于任何排序算法都是一个有效的补充吗？

答： 增加一个验证输入是否是已经排好序的步骤（这个验证需要$n-1$次比较）；看起来是一个有效的补充，不过还是要根据实际情况，如果输入是有序的情况等几率很小，则增加这个补充没有什么意义；如果有大概率输入有序，则使用插入排序就好了，也就没有检查等必要了。所以，没有必要为排序算法增加这个额外的测试。

习题2.2

11. 更轻或者更重？ 你有$n>2$个外观相似的硬币和一个没有砝码的天平。其中一枚为假币，但是并不知道它比真币重还是轻。设计一个$O(1)$的算法来确定假币比真币重还是轻。

答： 题目要求只是判断假币的轻重，而没有说要找出这枚假币，当然如果能找出它自然可以判断出轻重，但是一般化之后通过二分查找最快也需要对数时间，无法达到题目要求的$O(1)$时间。

通过多次次称重来解决。思路如下：首先分两等份称重，必然一边轻，一一边重，如果假币在重的一半，则假币重于真币，反正的轻。然后选取重的一半，再等分为两半，如果这两半等重量，则说明没有假币，即可推断出假币重量轻。反之，则说明假币重。若无法等分，则可额外增加称重判断多出来的是真币还是假币。

12. 墙上的门 你面前时一堵朝两个方向无限延伸的墙。墙上有一扇门，但你并不知道门理你有多远，也不知道门位于哪个方向。你只有走到门面前才能看到它。假设从当前位置到门要走$n$（事先并不知道$n$的大小）步，请设计一个算法，是你最多$O(n)$步就能遇到门。

答: 第一感觉是两边都要走看，然后每次失败要加倍步数，但具体怎么走能够满足$O(n)$呢？

这里给出了一个具体的走法，不过原文证明有些错误：

首先以起始位置为原点建立实数轴，设折返次数为 $k = 0,1,2,3,4,5......$_
每次需要达到的坐标位置则为: $$a_k = \frac{(-2)^k-1}{3}$$

那么沿着实数轴连续两次折返的距离为：$\lvert a^{k+1} - a^k\rvert = 2^k$(原文这里有误，算成了$\frac {2^k}{3}$，应该是符号算错了)。

假设在第$k$(假设$k$为偶数)次的时候，路过了门，则有：$\lvert a_k\rvert = \lvert \frac{(-2)^k-1}{3}\rvert \ge n \to 2^k \ge 3n + 1 \to k \gt log_2(3n + 1)$

走过的步数之和为：$2^0 + 2^1 + 2^2 + ... + 2^{k-1} = 2^k -1 = 2^{log_2(3n+1)} = 3n + 1 \to O(n)$

也就是说，按照这样的钟摆式走法，大概在$log_2(3n+1)$次就可以路过门口了，这个走法的精髓是每次折返之后，走的距离是上一次走的$2$倍，指数级的渐进增长速率，加快检索的距离。

习题2.4

5. 汉诺塔谜题 为汉诺塔谜题设计一个非递归的算法，并用你熟悉的语言实现。

答：

// recursive solution
func hanoi(num int, from, aux, to string) {
  if num > 0 {
      hanoi(num-1, from, to, aux)
      fmt.Printf("Move disk %d from %s to %s\n", num, from, to)
      hanoi(num-1, aux, from, to)
    }
}

// iterative soluton
// ref: https://en.wikipedia.org/wiki/Tower_of_Hanoi#Iterative_solution
func hanoi2(from, aux, to *[]int) {
    var iter int
    var direction []*[]int

    // for printing
    tower := map[*[]int]string{from: "A", aux: "B", to: "C"}

    if len(*from)%2 == 0 {
        direction = []*[]int{from, aux, to} // means from->aux->to->from
    } else {
        direction = []*[]int{from, to, aux} // means from->to->aux->from
    }

    // when from&aux are empty, we'are done
    for len(*from) > 0 || len(*aux) > 0 {
        // smallest at peg1, move it to peg2 according `direction`
        peg1 := direction[iter%3]
        peg2 := direction[(iter+1)%3]
        peg3 := direction[(iter+2)%3]
        iter++

        // move smallest disk from peg1->peg2
        fmt.Printf("Move disk %d from %s to %s.\n", (*peg1)[len(*peg1)-1], tower[peg1], tower[peg2])
        *peg2 = append(*peg2, (*peg1)[len(*peg1)-1])
        *peg1 = (*peg1)[:len(*peg1)-1]

        // move non-smallest disk either peg1->peg3 or peg3->peg1
        l, r := len(*peg1), len(*peg3)
        if l > 0 || r > 0 {
            if l == 0 || (l != 0 && r != 0 && (*peg1)[l-1] > (*peg3)[r-1]) {
                fmt.Printf("Move disk %d from %s to %s.\n", (*peg3)[r-1], tower[peg3], tower[peg1])
                *peg1 = append(*peg1, (*peg3)[r-1])
                *peg3 = (*peg3)[:r-1]
            } else {
                fmt.Printf("Move disk %d from %s to %s.\n", (*peg1)[l-1], tower[peg1], tower[peg3])
                *peg3 = append(*peg3, (*peg1)[l-1])
                *peg1 = (*peg1)[:l-1]
            }
        }
    }
}

13. 烤汉堡 有$n$个汉堡需要在烤架上烤，但是烤架上一次只能放$2$个汉堡。每个汉堡都需要烤两面，不管是烤一个汉堡还是同时烤两个汉堡，烤好一个汉堡的一面用时1分钟。假设要在最短的时间内完成该任务，考虑下列递归算法。如果$n<2$，一个汉堡单独烤并翻面，两个汉堡则同时烤并翻面。如果$n>2$，两个汉堡同时烤并翻面，然后对余下的$n-2$个汉堡递归的应用同样的过程。

a. 给出该算法烤n个汉堡所需要的时间的递推关系并求解。

b. 对于任意$n>0$个汉堡，该算法完成任务的时间并不是最少的，为什么？

c. 给出一个在最少时间内完成烤汉堡任务的正确递归算法。

答：

a. $n>2$有，$F(n) = F(n-2) + 2$，$F(1) = 2;F(2)= 2$；按照上述递推关系可得：

$$F(n) = \begin{cases} n (n为偶数)\\ n+1 （n为奇数）\\ \end{cases}$$

b. 当$n$为奇数时，其最少完成时间也是$n$分钟：以三个汉堡为例，第一次烤其中两个a,b的一面，用时1分钟，然后烤a的另一面和c的一面，用时1分钟，最后烤b和c的另外一面，用时1分钟，所以总共用时3分钟。

c. $n>3$时，两个两个烤，当$n=3$时，按b中所给方法烤，总用时为n分钟，为最少时间。

14. 名人问题 $n$个人中的名人是指这样一个人：他不认识别人，但是每个人都认识他。任务就是找出这样一个名人，但只能通过询问“你认识他／她吗？”这种问题来完成。设计一个高效算法，找出该名人或者确定这群人中没有名人。你的算法在最坏情况下需要问多少个问题？

答： n个人排成一排，从第一个人开始，问他／她是否认识第二个人，如果他／她回答认识，则第一个人肯定不是名人，第二个人则可能是名人；如果回答不认识，则第二个人肯定不是名人，第一个则有可能是名人；然后根据回答接着问可能是名人的那个人，是否认识第三个人，一轮过后，会剩下一个人，他／她可能是名人。然后开始第二轮，验证第一轮的那个人是否是名人，依次问他／她是否认识其他人，并反问其他人是否认识他／她，如果有人不认识他／她，或者他／她认识其他人，则这群人没有名人，否则这个人就是名人。

最坏的情况下，需要问$3(n-1)$个问题，第一轮$(n-1)$个，第二轮$2(n-1)$个。

习题2.5

10. 当两个连续的斐波那契数$F(n)$和$F(n-1)$作为欧几里得算法的输入时，该算法需要做多少次求模运算？

答： 连续的斐波那契数是欧几里得算法的最差输入，得到结果需要做$n$次模运算

重要结论

• 如果算法是与数字特性相关的，在度量它的输入规模时，计算机科学家倾向于度量数字$n$的二进制表示中的位数$b$: $b = \lfloor log_2n\rfloor + 1$。

• 证明一个正整数$n$的二进制表示，其位数的计算公式如下：$b = \lceil log_2(n+1)\rceil$；也就是以上两个等式是等价的，可以用数学归纳法证明。

• 斐波那契数列的闭合解：

  $$F(n)=\frac {1} {\sqrt 5} (\phi^n - {\hat\phi}^n)$$ 其中$\phi = (1+\sqrt {5})/2 \approx 1.61803$ ，而${\hat\phi} = -1/\phi \approx -0.61803$。很难以令人相信，虽然公式包含了无理数的任意整数次幂，但是它的值恰好是全部的斐波那契数！闭合解明显指出了$F(n)$是呈指数级增长的，也就是说，$F(n)\in \Theta(\phi ^ n)$。因为${\hat\phi}$是在$-1$和$0$之间的小数，所以，当n去向于无穷大时，${\hat \phi}^n$趋向于无穷小。实际上，我们可以证明，方程的第二项$\frac {1} {\sqrt 5} {\hat\phi} ^n$对$F(n)$的影响在效果上等同于将第一项的值向最近的整数取整。换句话说，对于每一个非负整数n，$F(n) = \frac {1} {\sqrt 5} \phi ^ n$取整为最近的整数。