Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 9 Prof charles e. leiserson
Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 9 Prof. Charles E. Leiserson
Binary-search-tree sort T< b Create an empty bst for i=l to n do TREe-INSERT(T, AiD Perform an inorder tree walk of t Example A=[3182675] 8 ree-walk time =O(n but how long does it take to build the bst c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.2
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.2 33 Binary-search-tree sort T ← ∅ ⊳ Create an empty BST for i = 1 to n do TREE-INSERT(T, A[i]) Perform an inorder tree walk of T. Example: A = [3 1 8 2 6 7 5] 11 88 22 66 55 77 Tree-walk time = O(n), but how long does it take to build the BST?
Analysis of bst sort BST sort performs the same comparisons as quicksort, but in a different order 3182675 8)675 675 The expected time to build the tree is asymptot ically the same as the running time of quicksort c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.3
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.3 Analysis of BST sort BST sort performs the same comparisons as quicksort, but in a different order! 3 1 8 2 6 7 5 1 2 8 6 7 5 2 6 7 5 5 7 The expected time to build the tree is asymptotically the same as the running time of quicksort
Node depth The depth of a node the number of comparisons made during TREE-INSERT. Assuming all input permutations are equally likely, we have Average node depth E∑( comparisons to insert no lO(nlgn) (quicksort analysis O(gn) c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.4
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.4 Node depth The depth of a node = the number of comparisons made during TREE-INSERT. Assuming all input permutations are equally likely, we have ( ) (lg ) ( lg ) 1 #comparisons to insert node 1 1 O n O n n n E i n n i = = = ∑= Average node depth . (quicksort analysis)
Expected tree height But, average node depth of a randomly built BST=O(g n) does not necessarily mean that its expected height is also O(g n)(although it is) Example ≤1gn Ave.deph≤1nlgn+nn O(gn) c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.5
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.5 Expected tree height But, average node depth of a randomly built BST = O(lg n) does not necessarily mean that its expected height is also O(lg n) (although it is). Example. ≤ lg n h = n (lg ) 2 lg 1 O n n n n n n = ⋅ Ave. depth ≤ ⋅ +
Height of a randomly built binary search tree Outline of the analysis: Prove jensen’ s inequali的, which says that feDs(XI for any convex function fand random variable x Analyze the exponential height of a randomly built bst on n nodes which is the random variable y= 2An where X is the random variable denoting the height of the bst Prove that 2ELAnl EJ2Xn1=E[Ym =O(n) and hence that EXn=O(g n) c 2001 by Charles E Leiserson Introduction to Algorithms Day 17 L9.6
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.6 Height of a randomly built binary search tree • Prove Jensen’s inequality, which says that f(E[X]) ≤ E[f(X)] for any convex function f and random variable X. • Analyze the exponential height of a randomly built BST on n nodes, which is the random variable Yn = 2Xn, where Xn is the random variable denoting the height of the BST. • Prove that 2E[Xn] ≤ E[2Xn ] = E[Yn] = O(n3), and hence that E[Xn] = O(lg n). Outline of the analysis:
Convex functions A functionf:R>R is convex if for all a,B≥0 such that a+β=1, we have fax+阝y)≤o(x)+B/f orax,y∈ R f afx)+ B) f fax+阝y) x ax+ B c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.7
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.7 Convex functions A function f : R → R is convex if for all α,β ≥ 0 such that α + β = 1, we have f(αx + βy) ≤ αf(x) + βf(y) for all x,y ∈ R. αx + βy αf(x) + βf(y) f(αx + βy) x y f(x) f(y) f
Convexity lemma Lemma Let f: R>R be a convex function an nd let (ap,a2,.,an) be a set of nonnegative constants such that 2la= 1. Then, for any set x,x2,.,xn) of real numbers, we have ∑axk|s∑a/(x) k=1 k=1 Proof By induction on n. For n=1, we have I=l, and hence fax,sav( trivially c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.8
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.8 Convexity lemma Lemma. Let f : R → R be a convex function, and let {α1, α2 , …, αn} be a set of nonnegative constants such that ∑k αk = 1. Then, for any set {x1, x2, …, xn} of real numbers, we have ( ) 1 1 ∑ ∑ = = ≤ nk k k nk k k f α x α f x Proof. By induction on n. For n = 1, we have α1 = 1, and hence f(α1x1) ≤ α1f(x1) trivially.
Proof (continued) Inductive step kkk= n-n +(1 k X k=1 k n algebra c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.9
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.9 Proof (continued) − = + − ∑ ∑− = =1 1 11 (1 )nk k n k n n n nk k k f x f x x α α α α α Inductive step: Algebra
Proof (continued) Inductive step k k k anIn+(l-a n n k=1 ≤an(x)+(-an)∑,“xk k=1 Convexity c 2001 by Charles E Leiserson Introduction to Agorithms Day17L9.10
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.10 Proof (continued) − ≤ + − − = + − ∑ ∑ ∑ − = − = = 1 1 1 1 1 1 ( ) (1 ) 1 (1 ) n k k n k n n n n k k n k n n n n k k k f x f x f x f x x α α α α α α α α α Inductive step: Convexity