12.4 - Clrs — ContextQMD

Exercises 12.4-1

Prove equation (12.3).

`Answer`

This is basic property of permutations and combinations. You can use Pascal triangle to prove

Exercises 12.4-2

Describe a binary search tree on n nodes such that the average depth of a node in the tree is Θ(lg n) but the height of the tree is w(lg n). Give an asymptotic upper bound on the height of an n-node binary search tree in which the average depth of a node is Θ(lg n).

`Answer`

满二叉树就满足n个节点平均高度为 Θ(lg n), 树高 lg n (w = 1)

渐进上界为 Θ(lg n)

Exercises 12.4-3

Show that the notion of a randomly chosen binary search tree on n keys, where each binary search tree of n keys is equally likely to be chosen, is different from the notion of a randomly built binary search tree given in this section.

`Answer`

a randomly built binary search tree, 随机构建二叉搜索树, 指的是构建过程的随机, 也就是通过依次插入的方式构建采用的初始序列随机, 这个序列有 n! 种排列方式, 因此随机构建的过程有 n! 种不同的情况

a randomly chosen binary search tree, 随机选择二叉搜索树, 指的是对于 n 个元素构成的所有二叉树进行选择的过程随机, 由于随机构建过程的初始序列没有任何要求, 因此排列情况是 n! 种, 而二叉搜索树要求有一定的大小关系 (一个节点的左孩子关键字不大于该节点关键字, 右孩子关键字不小于该节点关键字), 这意味着 n 个元素构成的二叉搜索树的个数肯定小于等于 n! (等号只在 n = 1 时取得)

Exercises 12.4-4

Show that the function f(x) = 2^x is convex.

`Answer`

首先, 有 (a + b)^2 = a^2 + b^2 + 2ab >= 4ab (等号仅在 a = b时取得)

设 x1 < x2, 有 (2^x1 + 2^x2)^2 / 4 > 2^(x1 + x2)

因此, (2^x1 + 2^x2) / 2 > 2^[(x1 + x2) / 2]

因此 f(x) = 2^x 是严格凸的

Exercises 12.4-5

Consider RANDOMIZED-QUICKSORT operating on a sequence of n distinct input numbers. Prove that for any constant k > 0, all but O(1/(n^k)) of the n! input permutations yield an O(nlgn) running time.

`Answer`

欲证明题等价于: n! 种输入排列运行时间不是 O(nlgn) 的排列个数 p(n) 一定满足 O(1/(n^k)) (对任意常数 k > 0 成立)

根据渐进上界的定义, 存在 c > 0 和 n0 > 0, 使得对所有 n >= n0, 有 0 <= p(n) <= c/(n^k) (任意常数 k > 0)

因此, p(n) 一定是常数

又因为只有当输入序列有序(最坏情况)时, 排序所需时间不为 O(nlgn), 这种排列只有常数个

Follow @louis1992 on github to help finish this task.