合并两个排序列表，下限
merging two sorted lists, lower bound
使用决策树和你对 (a) 部分的回答，证明任何正确合并两个排序列表的算法必须至少执行 2n − o(n) 次比较。
(a) 部分的答案：2n 过 n 种方法将 2n 个数字分成两个排序列表，每个列表有 n 个数字
(2n 超过 n) <= 2^h
h >= lg(2n)! / (n!)^2
= lg(2n!) - 2lg(n!)
= Θ(2nlg(2n)) - 2Θ(nlg(n)) <----
= Θ(2n) <----
我不明白最后一步。怎么可能是Θ(2n)？
您可以将乘积的对数表示为单独对数 (the first property here) 的总和：
2*n*lg(2*n) = 2*n*(lg(2) + lg(n)) = 2*n*(1 + lg(n))
所以
2*n*(1 + lg(n)) - 2*n*lg(n) =
2*n+ 2*n*lg(n)) - 2*n*lg(n) = 2*n
使用决策树和你对 (a) 部分的回答，证明任何正确合并两个排序列表的算法必须至少执行 2n − o(n) 次比较。
(a) 部分的答案：2n 过 n 种方法将 2n 个数字分成两个排序列表，每个列表有 n 个数字 (2n 超过 n) <= 2^h
h >= lg(2n)! / (n!)^2
= lg(2n!) - 2lg(n!)
= Θ(2nlg(2n)) - 2Θ(nlg(n)) <----
= Θ(2n) <----
我不明白最后一步。怎么可能是Θ(2n)？
您可以将乘积的对数表示为单独对数 (the first property here) 的总和：
2*n*lg(2*n) = 2*n*(lg(2) + lg(n)) = 2*n*(1 + lg(n))
所以
2*n*(1 + lg(n)) - 2*n*lg(n) =
2*n+ 2*n*lg(n)) - 2*n*lg(n) = 2*n