Skip to content

Latest commit

 

History

History
93 lines (55 loc) · 7.14 KB

7.4.md

File metadata and controls

93 lines (55 loc) · 7.14 KB
Raw

Exercises 7.4-1

Show that in the recurrence

Answer

Exercises 7.4-2

Show that quicksort's best-case running time is Ω(nlgn).

Answer

According to the master theorem，it is Ω(nlgn)

Exercises 7.4-3

Show that q^2 +(n-q-1)^2 achieves a maximum over q = 0,1,...,n-1 when q=0 or q=n-1.

Answer

抛物线的简单性质~~~~

或者可以用不等式，转化成已知A+B = n - 1,求A^2 + B^2在[0,n-1]的最大值.

Just get by the property parabolic curve.

Exercises 7.4-4

Show that RANDOMIZED-QUICKSORT's expected running time is Ω(n lg n).

Answer

For a monotonically increasing function , we can approximate it by integrals:

(A.11)\int_{m-1}^{n}f(x)dx\leqslant \sum_{k=m}^{n}f(k)\leqslant \int_{m}^{n+1}f(x)dx

Similarly, for a monotonically decreasing function , would have:

\int_{m-1}^{n}f(x)dx\geqslant \sum_{k=m}^{n}f(k)\geqslant \int_{m}^{n+1}f(x)dx

Similar to the proof in (7.4):

E[X]=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\frac{2}{j-i+1}\\hspace{15.5mm}=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\frac{2}{j-i+1}\\hspace{15.5mm}=\sum_{i=1}^{n-1}\sum_{k=1}^{n-i}\frac{2}{k+1}\\hspace{15.5mm}\geqslant \sum_{i=1}^{n-1}2\int_{1}^{n-i}\frac{1}{k+1}\\hspace{15.5mm}=\sum_{i=1}^{n-1}2(ln(n-i+2)-O(1))\\hspace{15.5mm}\geqslant2\int_{1}^{n}ln(n-i+2)di-O(n)\\hspace{15.5mm}=\int_{2}^{n+1}ln(x)dx-O(n)\~\hspace{15.5mm}=2nln(n+1)-O(n)=\Omega (nlgn)

Exercises 7.4-5

The running time of quicksort can be improved in practice by taking advantage of the fast running time of insertion sort when its input is "nearly" sorted. When quicksort is called on a subarray with fewer than k elements, let it simply return without sorting the subarray. After the top-level call to quicksort returns, run insertion sort on the entire array to finish the sorting process. Argue that this sorting algorithm runs in O(nk + nlg(n/k)) expected time. How should k be picked, both in theory and in practice?

Answer

先看快速排序的那部分，当深度为lg(n/k)便停止了快速排序，所以快速排序的时间为O(nlg(n/k));再看插入排序那部分，现在有n/k个小数组，每个数组的大小为k，需要O(k^2)的时间排序，所以插入排序的时间是n/k * O(k^2) = O(nk).

理论上很难确定k,因为快速排序的渐近函数在数量级上优于插入排序；用实验确定是比较靠谱的方法.

The main idea is to note that the recursion stops when n^2*i = k, that is i = log2(n)(k). The recursion takes in total O(n * lg(n)(k)). The resulting array is composed of k subarrays of size n=k, where the elements in each subarray are all less than all the subarrays following it. Running Insertion-Sort on the entire array is thus equivalent to sorting each of the n/k subarrays of size k, which takes on the average n/k * O(k2) = O(nk) (the expected running time of Insertion-Sort is O(n^2)).

If k is chosen too big, then the O(nk) cost of insertion becomes bigger than (n lg n). Therefore k must be O(lg n). Furthermore it must be that O(nk + n lg (n)(k) ) = O(n lg n). If the constant factors in the big-oh notation are ignored, than it follows that k should be such that k < lg k which is impossible (unless k = 1) - the error comes from ignoring the constant factors. Let c1 be the constant factor in quicksort, and c2 be the constant factor in insertion sort. Than k must be chosen such that c2k + c1 lg n k < c1 lg n which requires c1k<c2 lg k. In practice these constants cannot be ignored (also there can be lower order terms in O(n lg n)) and k should be chosen experimentally.

English version solution copied from here

Exercises 7.4-6

Consider modifying the PARTITION procedure by randomly picking three elements from array A and partitioning about their median (the middle value of the three elements). Approximate the probability of getting at worst an α-to-(1 - α) split, as a function of α in the range 0 < α < 1.

Answer

假设α < 1/2并且能取相同的元素,这并不影响最后的结果.

先考虑概率小于α的这边，此时中位数落在nα内，也就是说至少选到了两个在nα内的数字.有以下几种组合

  1. 1，2，3都在
  2. 1，2在，3不在
  3. 1，3在，2不在
  4. 2，3在，1不在.

概率是1*(α^3)+3*(α^2*(1-α)) = 3α^2-2α^3.

概率大于(1-α)的概率和小于α是一样的.

因此最后的答案是6α^2-4α^3

Follow @louis1992 on github to help finish this task.