介绍

这是算法导论的第二章~

2.1 插入排序

• INSERTION-SORT(A) ：

for j = 2 to A.length
    key = A[j]
    i = j - 1
    while i > 0 and A[i] > key
        A[i+1] = A[i]
        i = i - 1
    A[i + 1] = key

正确性：
    循环不变式：在for循环每次迭代的开始，A[1..j-1]已排好序。
    初始化：当j=2，显然成立。
    保持：将A[j]插入合适位置，故迭代完后保持。
    终止：终止时，j=n+1,即A[1..n]已排好序。

• 练习2.1-1 Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array A = [31, 41, 59, 26, 41, 58].

too easy!

• 练习2.1-2 Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead of nondecreasing order.

for j = 2 to A.length:
    key = A[j]
    i = j - 1
    while i > 0 and A[i] < key
        A[i+1] = A[i]
        i = i - 1
    A[i + 1] = key

• 练习2.1-3 Consider the searching problem: Input: A sequence of n numbers A = [a1, a2, . . . , an] and a value v. Output: An index i such that v = A[i] or the special value NIL if v does not appear in A. Write pseudocode for linear search, which scans through the sequence, looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

LINEAR-SEARCH(A, v)
    i = 1
    while i <= A.length
        if A[i] == v
            return i
        i = i + 1
    return NIL

循环不变式：在while循环每次迭代的开始，A[1..i-1]不包含v。
初始化：当i=1，显然成立。
保持：若A[i]==v则会返回，故保持。
终止：终止时，i=A.length+1,故A[1..A.length]不包含v.

• 练习2.1-4 Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an (n + 1)-element array C. State the problem formally and write pseudocode for adding the two integers.

输入：
    A和B均为整形数组，A.length == B.length == n
    A, B中任意元素均为0或1
输出：
    C为整形数组，C.length == n + 1
    C中任意元素均为0或1

ADD-BINARY(A, B)
    n = length(A)
    C = Array[n+1]
    carry = 0
    for i = n to 1
        C[i+1] = (A[i] + B[i] + carry) % 2
        carry = (A[i] + B[i] + carry) / 2
    C[1] = carry
    return C

2.2 分析算法

• 在RAM(random-access machine)中进行算法分析。并不对内存层次(高速缓存和虚拟内存)进行建模。

• 运行时间是指执行的基本操作数或步数。

• 平均情况往往和最坏情况一样差。

• 练习2.2-1 Express the function n^3/1000-100n^2-100n+3 in terms of Θ-notation.

Θ(n^3)

• 练习2.2-2 Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[1]. Then find the second smallest element of A, and exchange it with A[2]. Continue in this manner for the first n - 1 elements of A. Write pseudocode for this algorithm, which is known as selection sort. What loop invariant does this algorithm maintain? Why does it need to run for only the first n - 1 elements, rather than for all n elements? Give the best-case and worst-case running times of selection sort in Θ- notation.

SELECTION-SORT(A)
    n = length(A)
    for i = 1 to n - 1
            min = i
        for j = i + 1 to n
            if A[j] < A[min]
                min = j
        temp = A[i]
        A[i] = A[min]
        A[min] = temp

循环不变式：在每次迭代开始前，A[1..i-1]已排序好，且为A中最小的i-1个元素。

显而易见。

最好情况和最坏情况：均为Θ(n^2)

• 练习2.2-3 Consider linear search again (see Exercise 2.1-3). How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in Θ-notation? Justify your answers.

平均情况(n+1)/2
最坏n
(1+2+3+...+n)/n = (n+1)/2
最后一个就是n喽~

• 练习2.2-4 How can we modify almost any algorithm to have a good best-case running time?

if input is the case
return result
我在leetcode上这样做过……if了所有测试。。。

2.3 设计算法

• Merge Sort

MERGE(A, p, q, r)
    n1 = q - p + 1
    n2 = r - q
    let L[1..n1+1] and R[l..n2+1] be new arrays
    for i = 1 to n1
        L[i] = A[p + i - 1]
    for j = 1 to n2
        R[j] = A[q + j]
    L[n1+1] = INFINITE
    L[n2+1] = INFINITE
    i = 1
    j = 1
    for k = p to r
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else A[k] = R[j]
            j = j + 1

循环不变式：每次循环开始前，子数组A[p..k-1]按从大到小顺序包含L[1..n1+1]和
R[n2+1]中的k-p个最小元素。且L[i]和R[j]是各自数组中未被复制回A的最小元素。

MERGE-SORT(A, p, r)
    if p < r
        q = (p + r) // 2
        MERGE-SORT(A, p, q)
        MERGE-SORT(A, q + 1, r)
        MERGE(A, p, q, r)

• 练习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].

  Too easy...
  

• 练习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..n1+1] and R[l..n2+1] be new arrays
    for i = 1 to n1
        L[i] = A[p + i - 1]
    for j = 1 to n2
        R[j] = A[q + j]
    L[n1+1] = INFINITE
    L[n2+1] = INFINITE
    i = 1
    j = 1
    k = 1
    while i < n1 + 1 and j < n2 + 1
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else A[k] = R[j]
            j = j + 1
        k = k + 1
    if i < n1 + 1
        for m = i to n1
            A[k] = A[m]
            k = k + 1
    else
        for n = j to n2
            A[k] = A[n]
            k = k + 1

• 练习2.3-3

很直接的递推法。

• 练习2.3-4 Insertion sort can be expressed 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.

if n = 1
    T(n) = 1
else T(n) = T(n-1) + n - 1

• 练习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 v and eliminate half of the sequence from further consideration. Binary search is an algorithm that 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 Θ(lg n).

BINARY-SEARCH(A, v)
    left = 1
    right = length(A)
    while left < right
        middle = (left + right) // 2
        if A[middle] == v
            return middle
        else if A[middle] > v
            left = middle + 1
        else right = middle - 1
    return NIL

最坏情况也只需要Θlg(n)次迭代。。

• 练习2.3-6 Observe that the while loop of lines 5 - 7 of the INSERTION-SORT procedure in Section 2.1 uses a linear search to scan (backward) through the sorted subarray A[1..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 Θ(n lg n)?

不能。还要移动元素呀。

• 练习2.3-7 Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.

1. 用哈希表可以达到Θ(n)

2. 先merge sort, 然后用two pointers一个朝后一个朝前扫描，leetcode上有一堆这种题。。

思考题

• 2-1 Insertion sort on small arrays in merge sort

  Although merge sort runs in Θ(n lg n) worst-case time and insertion sort runs in Θ(n^2) worst- case time, the constant factors in insertion sort make it faster for small n. Thus, it makes sense to use insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which n/k sublists of length k are sorted using insertion sort and then merged using the standard merging mechanism, where k is a value to be determined.

  a. Show that the n/k sublists, each of length k, can be sorted by insertion sort in Θ(nk) worst-case time.

  b. Show that the sublists can be merged in Θ(n lg (n/k) worst-case time.

  c. Given that the modified algorithm runs in Θ(nk + n lg (n/k)) worst-case time, what is the largest asymptotic (Θnotation) value of k as a function of n for which the modified algorithm has the same asymptotic running time as standard merge sort?

  d. How should k be chosen in practice?

a. T(k) = n/k*Θ(k^2) = Θ(nk)

b. 和归并排序一样，只是层数变成lg(n/k)了

c. lgn

d. 43

• 2-2 Bubblesort is a popular sorting algorithm. It works by repeatedly swapping adjacent elements that are out of order.

BUBBLESORT(A)
    for i = 1 to A.length - 1
        for j = A.length downto i + 1
            if A[j] < A[j-1]
                swap(A[j], A[j-1])

a. 还需证明数组中的元素就是原来的那些元素。

b. 内层for循环不变式：每次循环前，A[j..A.length]中最小元素是A[j]。

c. 外层for循环不变式：每次循环前，A[1..i-1]已排序号且是最小的i-1个元素。

d. Θ(n^2), 性能比insertion sort差一点。

• 2-3 Correctness of Horner’s rule

HORNER
    y = 0
    for i = n downto 0
        y = a[i] + x * y

a. Θ(n)

b. Θ(n^2)

c. 显而易见= =

• 2-4 Inversions

  Let A[1..n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A.

  a. List the five inversions of the array 2, 3, 8, 6, 1.

  b. What array with elements from the set {1, 2, . . . , n} has the most inversions? How many does it have?

  c. What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.

  d. Give an algorithm that determines the number of inversions in any permutation on n elements in Θ(n lg n) worst-case time. (Hint: Modify merge sort.)

a. (2,1) (3,1) (8,1) (6, 1) (8,6)

b. 逆序数组。n(n-1)/2

c. 移动元素次数就是逆序对数目k。Θ(n+k)

d. So easy.