复旦大学：《数据结构与算法设计 Data Structures and Algorithm》课程英文讲义_Chapter 04 Soring

Data Structures and Algorithm Xiaoqing Zheng Zhengxq@fudan.edu.cn

Data Structures and Algorithm Xiaoqing Zheng zhengxq@fudan.edu.cn

Investment problem a Suppose that you try to in the stock market

Investment problem ‡ Suppose that you try to in the stock market

Deterministic algorithm STOCK-INVESTMENT(n) 1. best=0 fori←lton 23456 do investigate candidate if candidate i is better than candidate best then best buy candidate i Total cost: O(nc, mcb Worst case: O(nch

Deterministic algorithm STOCK-INVESTMENT ( n ) 1. best = 0 2. for i ← 1 to n 3. do investigate candidate i 4. if candidate i is better than candidate best 5. then best ← i 6. buy candidate i Total cost: O (nci + mc b ) Worst case: O (nc b )

Indicator random variable Indicator random variable r a associated with event A is defined as 1 ifa occurs o if a does not occur

Indicator random variable Indicator random variable I{ A } associated with event A is defined as 1 { } 0 A ⎧ = ⎨ ⎩ I if A occurs, if A does not occur

Analysis of investment problem Let X be the random variable whose value equals the numbers of times we buy a new stock if candidate i is better X=candidate i is better) 0 if candidate i is not better ane X=X1+X2+.+X

Analysis of investment problem Let X be the random variable whose value equals the numbers of times we buy a new stock. Xi = I{candidate i is better } = 1 0 ⎧ ⎨ ⎩ if candidate i is better, if candidate i is not better. and X = X1 + X2 + … + Xn

Analysis of investment problem Now we can compute EX EX]=E∑X ∑E[x i=1 ∑ 1/i Inn+O() Average cost: O(nnc

Analysis of investment problem Now we can compute E [X]: 1 [] [ ] n i i E XE X = = ∑ 1 [ ] n i i E X = = ∑ 1 1/ n i i = = ∑ = ln (1) n O+ Average cost: O (lnnc b )

Randomized algorithm RANDOMIZED-STOCK-INVESTMENT(n) 1. Randomly permute the list of candidates 2. best=0 fori←lton 34567 do investigate candidate i if candidate i is better than candidate best then best←i ly candidate i

Randomized algorithm RANDOMIZED-STOCK-INVESTMENT ( n ) 1. Randomly permute the list of candidates 2. best = 0 3. for i ← 1 to n 4. do investigate candidate i 5. if candidate i is better than candidate best 6. then best ← i 7. buy candidate i

Divide and conquer Quicksort an n-element array 1. Divide: partition the array into two subarrays around a pivot x such that elements in lower subarray ≤x≤ elements in upper subarray. ≤x x≤ 2. Conquer: recursively sort the two subarrays 3. Combine: Trivial Key: Linear-time partitioning subroutine

Divide and conquer Quicksort an n-element array: 1. Divide: Partition the array into two subarrays around a pivot x such that elements in lower subarray ≤ x ≤ elements in upper subarray. ≤ x x x ≤ 2. Conquer: Recursively sort the two subarrays. 3. Combine: Trivial. Key: Linear-time partitioning subroutine

Pseudocode for quicksort QUICKSORT(A,P, r) ifp< 2. then g+ PARTITION(A,,r) 3 QUICKSORT(A, p, g-1) QUICKSORT(A, 9+l, r Initial call: QUICKSORT(A, I

Pseudocode for quicksort QUICKSORT (A, p, r ) 1. if p < r 2. then q ← PARTITION (A, p, r ) 3. QUICKSORT (A, p, q – 1) 4. QUICKSORT (A, q + 1, r ) Initial call: QUICKSORT (A, 1, n )

Example of partitioning 287 3564

Example of partitioning 8 p 7 1 3 5 6 4 i r j 2