Processing math: 21%

[Introduction to Algorithm] Max & Min

Minimum and Maximum

Given an array \[1...n\], find the maximum and minimum number in this array.

Naive Approach

It should take 2(n−1) comparison to find the maximum and minimum number in the array by iterating the array twice. It seems to exist a "smarter" way to find both min and max in one pass.

Simultaneous min and max solution

1539174266665

1539174266665

Selection in Expected Linear Time

Given an array \[1...n\], find the ith smallest number in this array.

The solution is the same as the partition function in quick sort.

1539175417111

1539175417111

def Randomized_Select(A, p, r, i):
    # for the initial array, p = 0, r = n - 1
    # A: array
    # i: ith smallest number
    if p == r:
        return A[p]
    q = Partition(A, p, r)
    k = q - p + 1
    # the pivot is the value of answer
    if i == k:
        return A[q]
    # left
    elif i < k:
        return Randomized_Select(A, p, q - 1, i)
    # right
    else:
        return Randomized_Select(A, q + 1, r, i - k)

Analysis

T(n)≤1n⋅n∑k=1T(max(k−1,n−k))+O(n)

We have

max(k-1,n-k)=\begin{cases} k-1 & if\ k\ >\lfloor n/2\rfloor \\ n-k & if\ k\leqslant \lfloor n/2\rfloor \end{cases}

=2k

Therefore,

T(n)\le \frac{2c}{n}\sum_{k=n/2}^{n}k+O(n)

=\frac{2c}{n}(\frac{n^2-n}{2}-\frac{n^2/4-3n/2+2}{2})+an

=\frac{c}{n}(\frac{3n^2}{4}+\frac{n}{2}-2)+an

=c(\frac{3n}{4}+\frac{1}{2}-\frac{2}{n})+an

\le \frac{3cn}{4}+\frac{c}{2}+an

=cn-(\frac{cn}{4}-\frac{c}{2}-an)

when n\geqslant \frac{c/2}{c/4-a} =\frac{2c}{c-4a}, T(n)=O(n)

Selection in Worst Case

  • Delete roughly 30% of element by partitioning
  • At least 1/2 of 5 element median \le x
    • At least n/5/2=n/10, median \le x
  • At least 3\cdot \lfloor n/10\rfloor element \le x
1539249591978

1539249591978

  • Let C(N) = # comparison on a file of size N
1539317460536

1539317460536

After the calculation, the T(n)=O(n)

1539318426134

1539318426134

Assume T(n)\le20c\ N

\begin{array}{l} T( N) =T(\lfloor N/5\rfloor ) +T( N-3\lfloor N/10\rfloor ) +O( N)\\ \ \ \ \ \ \ \ \ \leqslant 20c\ \lfloor N/5\rfloor +\ 20c\ ( N-3\lfloor N/10\rfloor ) +cN\\ \ \ \ \ \ \ \ \ =4c\ \lfloor N\rfloor \ +14c\ \lfloor N\rfloor \ +cN\\ \ \ \ \ \ \ \ \ \leqslant 20c\ \lfloor N\rfloor \end{array}

Reference

[1] http://www.cs.princeton.edu/~wayne/cs423/lectures/selection-4up.pdf

algorithm