对T(n)=T(n/3)+T(2n/3)+O(n)递归树高的理解

最近在看《算法导论》(原书第三版/(美)科尔曼(Cormen, T.H.)等著;殷建平等译.北京:机械工业出版社,2013.1(2017.6重印))的第4章“分治策略”(第52页)时,碰到了如下的一个问题:

在讨论该树的高度时,书上说“从根到叶的最长简单路径是\(n–>(2/3)n–>(2/3)^2 n…–>1\)”最终得出的结论是树的高度为\(log_{3/2} n\)。

我对此十分迷惑,树的高度应当是\(log_{3} n\),怎么会是\(log_{3/2}n\)呢?

网上这篇文章给出了答案:

即对于最左边子树的高度确实为\(log_{3}n\),但由于二项式系数的原因,最右边子树的高度实际上为\(log_{3/2} n\),高于最左子树。所以《算法导论》书中才说“最长简单路径…”“并不是递归树中每个层次的代价都是cn”“递归树并不是完全二叉树”,并以最右子树的高度来得出该递归式的上界是\(O\left(n lg n\right)\),而我忽略了“最长”二字。

该文也利用最左子树高度得出了递归式的下界:

即\(\Omega(n lg n)\)。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据