算法导论3.1 Exercises 答案

3.1-1

令\(n=3k+r\)，其中\(r\in\{0,1,2\},k\ge 0\)。其中\(n\)是数组\(A\)长度。可以发现，\(3k+r\)可以表出任意正整数。

假设数组\(A\)中最大的\(k\)个元素恰好在数组的最左边。那么最终插入排序完成后，这\(k\)个元素最终在最右边的\(k\)个位置。这\(k\)个元素至少要移动\(k+r\)步。因此，这\(k\)个数总共需要移动\(k^2+kr\)步，那么这个算法的时间复杂度下限为\(\Omega(k^2+kr)\)。当\(n\)足够大时，\(k\gg r\)，因此回代\(k=\dfrac{n-r}{3}\)，得到\(\Omega\left(\dfrac{(n-r)(n+2r)}{9}\right)\)，舍去低阶的项\(r\)后得到\(\Omega(n^2)\)。

3.1-2

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\)轮循环中会固定进行\(n-i\)次，总共次数为\(\dfrac{n(n-1)}{2}\)，因此时间复杂度的上限为\(O(n^2)\)。

同样的，假设当前数组\(A\)长度\(n=3k\)，其中最小的\(k\)个数位于数组的最后\(k\)个位置。那么在第\(i(i\le k)\)次外循环时，内循环至少要先完成中间的\(k\)个数的比较（也就是\(A[k+1:2k]\)里的数），才能够对最后\(k\)个数进行比较。这些无用对比较次数为\(k\)次，对于前\(k\)小对元素，这些无用的比较次数为\(k^2\)，也就是\(\dfrac{n^2}{9}\)，因此这个算法有\(\Omega(n^2)\)的下界。最终，选择排序算法的最坏时间复杂度为\(\Theta(n^2)\)。

3.1-3

1. 分数\(\alpha\)的分母必须能够整除数组长度\(n\)。
2. \(0<\alpha < 0.5\)，否则前\(\alpha n\)个位置和后\(\alpha n\)个位置产生覆盖，这个问题没有讨论的意义。

这\(\alpha n\)个元素通过中间的\((1-2\alpha)n\)个位置至少需要\(\alpha(1-2\alpha)n^2\)次。

令\(f(\alpha)=\alpha(1-2\alpha)\)，那么\(f'(\alpha)=1-4\alpha\)。令\(f'(\alpha)=0\)，得到\(\alpha =\dfrac{1}{4}\)。也就是说，只有当\(\alpha =\dfrac{1}{4}\)时，才能最大化这\(\alpha n\)个元素通过中间\((1-2\alpha) n\)个位置的次数。