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