算法导论2.2 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 790 阅读时长 ≈ 1 分钟

2.2-1

\[\Theta(n^3)\]

2.2-2

1
2
3
4
5
6
7
8
SELECTION-SORT(A, n)
  for i = 1 to n - 1
    minpos = i
    for j = i + 1 to n
      if A[j] < A[minpos]
        minpos = j
      swap(a[i], a[minpos])

循环不变量：到了第\(i\)次迭代前，\(A[1:i-1]\)已经保持有序，并且是数组\(A\)中前\(i-1\)小的数。第\(i\)次迭代完成后，\(minpos\)所指向的数必定是数组\(A\)中第\(i\)小的数。交换\(A[i],A[minpos]\)后，\(A[1:i]\)仍然保持有序，并且是数组\(A\)中前\(i\)小的数。

2.2-3

如下是抄自2.1-4中LINEAR-SEARCH算法的伪代码。

1
2
3
4
5
LINEAR-SEARCH(A, n, x)
  for i = 1 to n
    if A[i] == x
      return i
  return NIL

假设数组\(A\)中每个元素相互独立，它们各自等于\(x\)的概率分别为\(p\)。

那么，循环最终在第\(i\)次迭代结束的概率为\(p(1-p)^{i-1}\)。那么最终算法找不到元素\(x\)的概率为\((1-p)^n\)。

可以看出，随着\(n\)增大，\(i\)的分布律和几何分布\(GE(p)\)类似，考虑使用几何分布对这个分布律进行近似。几何分布的期望值为\(np\)，那么平均需要检查的元素个数为\(np\)，也就是\(\Theta(n)\)。最坏情况下全部\(n\)个元素都检查完，也就是\(\Theta(n)\)。

平均情况下的运行时间：第一行代码和第二行代码都会运行\(np\)次，第三行和第四行其中只有一个会被执行，因此平均运行时间为\(c_1np+c_2np+(1-p)^nc_4+(1-(1-p)^n)c_3\)，也就是\(\Theta(n)\)。

最坏情况下的运行时间：找不到元素。因此第一行代码运行\(n+1\)次，第二行代码运行\(n\)次，第四行代码运行\(1\)次，因此运行时间为\(c_1(n+1)+c_2n+c_4\)，也就是\(\Theta(n)\)。

2.2-4

  1. 在排序算法执行前先判断数组是否有序，如果有序那么提前返回结果，否则照样执行排序算法。

  2. 使用一些随机算法先将原来的数组乱序。