《算法导论》第二章-第3节_练习（参考答案）

算法导论（第三版）参考答案：练习2.3-1，练习2.3-2，练习2.3-3，练习2.3-4，练习2.3-5，练习2.3-6，练习2.3-7

Exercise 2.3-1

Using Figure 2.4 as a model, illustrate the operation of merge sort on the array A=⟨3,41,52,26,38,57,9,49⟩ .

Exercise 2.3-2

Rewrite the MERGE procedure so that it does not use sentinels, instead stopping once either array L or R has had all its elements copied back to A and then copying the remainder of the other array back into A .

MERGE(A, p, q, r)
  n1 = q - p + 1
  n2 = r - q
  let L[1..n₁] and R[1..n₂] be new arrays
  for i = 1 to n₁
      L[i] = A[p + i - 1]
  for j = 1 to n₂
      R[j] = A[q + j]
  i = 1
  j = 1
  for k = p to r
      if i > n₁  //判断L中是否取完
          A[k] = R[j]
          j = j + 1
      else if j > n₂  //判断R中是否取完
          A[k] = L[i]
          i = i + 1
      else if L[i] ≤ R[j]
          A[k] = L[i]
          i = i + 1
      else
          A[k] = R[j]
          j = j + 1

C code

#include <stdio.h>

void merge(int A[], int p, int q, int r) {
    int i, j, k;

    int n1 = q - p + 1;
    int n2 = r - q;

    int L[n1];
    int R[n2];

    for (i = 0; i < n1; i++)
        L[i] = A[p + i];
    for (j = 0; j < n2; j++)
        R[j] = A[q + j + 1];

    for(i = 0, j = 0, k = p; k <= r; k++) {
        if (i == n1) {
            A[k] = R[j++];
        } else if (j == n2) {
            A[k] = L[i++];
        } else if (L[i] <= R[j]) {
            A[k] = L[i++];
        } else {
            A[k] = R[j++];
        }
    }
}

void merge_sort(int A[], int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        merge_sort(A, p, q);
        merge_sort(A, q + 1, r);
        merge(A, p, q, r);
    }
}

Exercise 2.3-3

Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence

>T(n)=>{>2,>2T(n/2)+n,if n=2,if n=2k,for k>1.>>

is T(n)=nlgn

令: F(k)=T(2k)

即要证明： F(k)=2klg2k

当 k=1,n=2 时， F(1)=T(2)=2=2lg2=21lg21 ；成立

假设当 n=2k 时， F(k)=2klg2k ；

则当 n=2k+1 时，

F(k+1)=T(2k+1)=2T(2k+12)+2k+1=2T(2k)+2k+1=2⋅2klg2k+2k+1=2k+1(lg2k+1)=2k+1(lg2k+lg2)=2k+1lg2k+1

得证。

Exercise 2.3-4

We can express insertion sort as a recursive procedure as follows. In order to sort A[1..n] , we recursively sort A[1..n−1] and then insert A[n] into the sorted array A[1..n−1] . Write a recurrence for the running time of this recursive version of insertion sort.

递归式：

T(n)={θ(1),T(n−1)+C(n−1),if n=1,if n>1.

C(n) 是将一个元素插入到 A[n] 所需要的时间。

Exercise 2.3-5

Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence A is sorted, we can check the midpoint of the sequence against ν and eliminate half of the sequence from further consideration. The**binary search** algorithm repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is Θ(lgn) .

伪代码：（Pseudocode）

BINARY-SEARCH-ITERATION(A, v):
  low = 1
  high = A.length

  while low <= high
      mid = (low + high) / 2
      if A[mid] == v
          return mid
      if A[mid] < v
          low = mid + 1
      else
          high = mid - 1

  return NIL

BINARY-SEARCH-RECURSIVE(A, 1, A.length, v):
  low = 1
  high = A.length
  mid = (low + high) / 2

  if A[mid] == v
    return mid
  else if A[mid] < v
    BINARY-SEARCH-RECURSIVE(A, mid+1, high, v)
  else
    BINARY-SEARCH-RECURSIVE(A, low, mid-1, v)

  return NIL

递归式：

T(n+1)=T(n/2)+c

C code

// Indices in the C code are different
int binary_search(int A[], int length, int v) {
    int low  = 0;
    int high = length;

    int mid;
    while (low < high) {
        mid = (low + high) / 2;

        if (A[mid] == v)
            return mid;
        else if (A[mid] < v)
            low = mid + 1;
        else
            high = mid;
    }

    return -1;
}

Exercise 2.3-6

Observe that the while loop line 5-7 of the INSERTION-SORT procedure in Section 2.1 uses a linear search to scan (backward) through the sorted subarray A[i..j−1] . Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to Θ(nlgn) ?

不能。二分查找，只能在 Θ(lgn) 时间内完成查找，却不能用来移动元素。而插入排序line 5-7，在完成查找的同时需要移动元素。所以，即便在对数时间内查找到元素，仍然需要向右移动元素，而这在最坏情况下需要线性时间完成。尽管缩小了比较的时间，但还是需要进行相同数量的交换。

Exercise 2.3-7

★ Describe a Θ(nlgn) -time algorithm that, given a set S of n integers and another integer x , determines whether or not there exists two elements of S whose sum is exactly x .

Pseudocode：

PAIR-EXISTS(S, x):
  A = MERGE-SORT(S)

  for i = 1 to S.length
      if BINARY-SEARCH(A, x - S[i]) != NIL
          return true

  return false

归并排序时间— Θ(nlgn) ；迭代时间— Θ(nlgn) ；… 最终查找时间为 Θ(nlgn)