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

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

Exercise 2.2-1

Express the function n3/1000−100n2−100n+3 in terms of Θ−notation

Θ(n3)

Exercise 2.2-2

Consider sorting n numbers in an 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 invariants 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 the worst-case running times of selection sort in Θ−notation .

伪代码：（Pseudocode）

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

思想：每次选出剩余中的最小一个。

循环不变式：

在每一次迭代开始前， A[1..i−1] 都是已经排好序的（升序，并且以后位置也不会改变）。

为什么 n−1 个元素？

因为在 n−1 次，也就是最后一次循环中，就已经做出排序，留下的是较大的 A[n] 。

运行时间：

最坏情况运行时间： Θ(n2)

最好情况运行时间： Θ(n2)

Exercise 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 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 次。都为 Θ(n)

Exercise 2.2-4

How can we modify almost any algorithm to have a good best-case running time?

算法加入对最好情况的判断。比如：对于一个归并排序，如果输入已经是排好序的，就可以直接return。这样最好情况运行时间为 Θ(n)​ 。