麻省理工学院：《算法导论》（英文版） Lecture 9 Prof charles e. leiserson

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 asymptot￾ically 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