《算法设计手册》杂题3道

更新时间：2022-08-12 16:59:10

最近找工作的事告一段落，发一些之前整理但未发表的文章。鉴于各个公司一般要求将所做笔试题和面试题保密，并要求在试卷上签署了相关协议，因此本人不会在后续博文中提及并分析，见谅。

1.归纳法找递归函数的输出（原书P16~17，1.3.4节）

归纳并证明下面函数的输出：

int increment(int y) {

　　if (y==0)

　　　　return 1;
　　if(y%2 == 1)

　　　　return 2*increment(y/2);
　　else

　　　　return y+1;
}

解答：

　　事实上increment(y)=y+1。

　　证明：

(1)（归纳法）y=0时输出1。

(2)

y为偶数时，输出y+1；

y为奇数时，不妨令y=2m+1，那么2*increment((2m+1)/2) = 2*increment(m)。由于m<y且increment(m)=m+1 （归纳假设），那么输出为2*(m+1) = y+1。

得证。

2.动态数组的时间复杂度（原书P67，3.1.1节）

用下面的方式实现动态数组：首先分配大小为1的连续空间，当需要填入第2个元素时，分配大小为2个连续空间，把原来的1个元素复制进新空间，再把新元素填入，销毁原空间；依次类推，动态数组的容量变化过程为1->2->4->8->...。当数组中一共有n个元素时，一共被复制了几次？

解答：

为简化分析，n此时是2的幂且刚好把数组填满。可以看出，其中1/2的元素没有被复制过，另外1/2在上次扩展时复制了一次。即，上次扩展时复制了n*(1/2)个元素。一共扩展了logn次，因此复制的总次数为：

《算法设计手册》杂题3道

其中2^logn = n。由极限知识可知，当n→∞时，和为2n。因此n个元素的复制次数不超过2n次，保持了O(n)的时间复杂度。

附注：

　　Nginx封装的数据结构ngx_array_t就是一种动态数组，采用了类似的内存分配策略。

3.最小堆第k小的元素与给定x的大小关系：k^th>=x是否成立？（原书P116~117，4.3.2节）

对一个数组实现的n个元素的最小堆和给定的实数x，判断堆中第k小元素是否大于等于x？（0<k<n）要求算法最坏时间复杂度为O(k)。（提示：没必要找出第k小元素的具体值）

解答：

　　最直接的两种解法：从堆中选取最小元素k次，时间复杂度O(klogn)；检查堆中前k层所有元素，时间复杂度O(n,2^k)。这两种解法都不符合时间复杂度的要求。

　　实际上是从根开始遍历所有值小于x的结点：

//第一次调用时，i=1,count=k
int heap_compare(heap *h,int i,int count,int x)
{
    if((count<=0)||(i>h->size))
        return count;
    if(h->h[i]<x) {
        count = heap_compare(h,LEFT(i),count-1,x);
        count = heap_compare(h,RIGHT(i),count,x);
    }
    return count;
}