- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
≤
What happened here?
■ Let’s show that T(n) = O(n) by substitution
19 9/26/2010
Randomized Selection
● Assume T(n) ≤ cn for sufficiently large c:
T ( n) ≤ ≤ = = = 2 n 1 ∑/ 2T (k ) + Θ(n ) n k =n
22
9/26/2010
9.3 Selection in worst-case linear time
23
9/26/2010
Worst-Case Linear-Time Selection
● What follows is a worst-case linear time
algorithm, really of theoretical interest only ● Basic idea:
20
Multiply it out What happened here?
9/26/2010
Randomized Selection
● Assume T(n) ≤ cn for sufficiently large c:
T ( n) ≤ = = = ≤ cn c(n 1) 1 + Θ(n ) 2 2 cn c cn c + + Θ(n ) 4 2 cn c cn + Θ(n ) 4 2 cn c cn + Θ(n ) 4 2 cn (if c is big enough)
minimum element in a set? The maximum?
MINIMUM(A) 1 min ← A[1] 2 for i ← 2 to length[A] 3 do if min > A[i] 4 then min ← A[i] 5 return min
5
9/26/2010
Simultaneous Minimum and Maximum
10
≥ A[q] r
9/26/2010
Randomized Selection
● Analyzing RandomizedSelect()
■ Worst case: partition always 0:n-1 T(n) = T(n-1) + O(n) = ??? = O(n2) (arithmetic series) ○ No better than sorting! ■ “Best” case: suppose a 9:1 partition T(n) = T(9n/10) + O(n) = ??? = O(n) (Master Theorem, case 3) ○ Better than sorting! ○ What if this had been a 99:1 split?
■ If n is even, there are 2 medians
2
ห้องสมุดไป่ตู้
9/26/2010
Selection Problem
Input: A set A of n (distinct) numbers and a number i, with 1 ≤ i ≤ n. Output: The element x ∈ A that is larger than exactly i - 1 other elements of A.
11 9/26/2010
Randomized Selection
12
9/26/2010
Randomized Selection
13
9/26/2010
Calculating expectation
14
9/26/2010
Calculating expectation
15
9/26/2010
Calculating expectation
n 2 1 2c n 1 ∑ k ∑ k + Θ(n ) n k =1 k =1
2c 1 1n n What happened here? (n 1)n 1 + Θ(n ) Expand arithmetic series 2 n 2 2 2 cn c(n 1) 1 + Θ(n ) 2 2
■ Generate a good partitioning element ■ Call this element x
24
9/26/2010
Worst-Case Linear-Time Selection
● The algorithm in words:
1. Divide n elements into groups of 5 2. Find median of each group (How? How long?) 3. Use Select() recursively to find median x of the n/5 medians 4. Partition the n elements around x. Let k = rank(x) 5. if (i == k) then return x if (i < k) then use Select() recursively to find ith smallest element in first partition else (i > k) use Select() recursively to find (i-k)th smallest element in last partition
q = RandomizedPartition(A, p, r)
≤ A[q] p q
9
≥ A[q] r
9/26/2010
Randomized Selection
RandomizedSelect(A, p, r, i) if (p == r) then return A[p]; q = RandomizedPartition(A, p, r) k = q - p + 1; if (i == k) then return A[q]; if (i < k) then return RandomizedSelect(A, p, q-1, i); else return RandomizedSelect(A, q+1, r, i-k); k ≤ A[q] p q
21
9/26/2010
Summary of randomized order-statistic selection Works fast: linear expected time. Excellent algorithm in practice. But, the worst case is very bad: Θ(n2).
■ A practical randomized algorithm with O(n)
expected running time ■ A cool algorithm of theoretical interest only with O(n) worst-case running time
8
9/26/2010
16
9/26/2010
Calculating expectation
17
9/26/2010
Calculating expectation
18
9/26/2010
Randomized Selection
T (n ) ≤
1 n 1 ∑ T (max(k , n k 1)) + Θ(n ) n k =0 2 n 1 ∑/ 2T (k ) + Θ(n ) n k =n
Introduction to Algorithms
9 Medians and Order Statistics
1
9/26/2010
Order Statistics
● The ith order statistic in a set of n elements is
the ith smallest element ● The minimum is thus the 1st order statistic ● The maximum is the nth order statistic ● The median is the n/2 order statistic
● Can we find the minimum and maximum with
less than twice the cost? ● Yes:
■Walk through elements by pairs ○Compare each element in pair to the other ○Compare the largest to maximum, smallest to minimum ■Total cost: 3 comparisons per 2 elements ≤3 n/2 = O(3n/2)
25 9/26/2010
Choosing the pivot
26
9/26/2010
Choosing the pivot
27
9/26/2010
Choosing the pivot
28
9/26/2010
Choosing the pivot
29
9/26/2010
Analysis
30
9/26/2010
The recurrence we started with What happened here? Substitute T(n) ≤ cn for T(k) What happened here? “Split” the recurrence
2 n 1 ∑/ 2ck + Θ(n ) n k =n
● How can we calculate order statistics? ● What is the running time?
3
9/26/2010
9.1 Minimum and Maximum
4
9/26/2010
Minimum and Maximum
● How many comparisons are needed to find the
Randomized Selection
● Key idea: use partition() from quicksort
■ But, only need to examine one subarray ■ This savings shows up in running time: O(n)
● We will again use a slightly different partition
The recurrence so far
Multiply it out What happened here? Subtract c/2 What happened here?
Rearrange the arithmetic What happened here? we set out to prove What happened here?
■ At least 1/2 of the medians = n/5 / 2 = n/10
● How many elements are ≤ x?
■ At least 3 n/10 elements
3 n/10 ≥ n/4 (How large?) ● So at least n/4 elements ≤ x ● Similarly: at least n/4 elements ≥ x
Analysis(Assume all elements are distinct.)
31
9/26/2010
Analysis(Assume all elements are distinct.)
32
9/26/2010
Worst-Case Linear-Time Selection
● How many of the 5-element medians are ≤ x?
6
9/26/2010
9.2 Selection in expected linear time
7
9/26/2010
The Selection Problem
● A more interesting problem is selection:
finding the ith smallest element of a set ● We will show:
