我一直在学习排序算法。
我卡在了找到归并排序复杂度上。
有人能解释一下h=1+lg(n)是怎么来的吗？
归并排序 - 递归树
4
- psj01
4
@MrFlick：不，那是给专业研究人员的。 - user541686
也许是 [cs.se]。 - MrFlick
@MrFlick：说实话，这个问题对于任何程序员来说都应该很容易解决，因此在这个网站上提问是非常合适的。 - user541686
看一下我的编辑，它可能会有帮助。 - user541686
1个回答
4
如果您不断地将n除以2，最终会得到1。换句话说，根据对数的定义，需要log2(n)次除以2才能实现这一点。
每次除以2，我们都会在递归树中添加一个新的层级。加上根层级（不需要任何划分），我们总共有log2(n)+1个层级。
以下是更酷的证明。注意，重新排列后，我们有T(2n)-2T(n)=2cn。
如果n=2^k，则我们有T(2^(k+1))-2T(2^k)=2c*2^k。
让我们简化这个混乱。我们定义U(k)=T(2^k)/(2c)。
然后我们有U(k+1)-2U(k)=2^k，或者，如果我们定义U'（k）=U（k+1）-U（k）：
U'(k)-U(k)=2^k
这里的k是离散的，但是我们可以让它连续，如果我们这样做，那么U'就是U的导数。
此时解决方案是显而易见的：如果您曾经求导过，那么您就知道，如果函数与其导数的差是指数级别的，那么函数本身就必须是指数级别的（因为只有在这种情况下，导数才是其自身的某个倍数）。
此时您就知道U(k)是指数级别的，因此您可以为指数中的未知系数插入一个指数，并将其重新插入以解决T。
每次除以2，我们都会在递归树中添加一个新的层级。加上根层级（不需要任何划分），我们总共有log2(n)+1个层级。
以下是更酷的证明。注意，重新排列后，我们有T(2n)-2T(n)=2cn。
如果n=2^k，则我们有T(2^(k+1))-2T(2^k)=2c*2^k。
让我们简化这个混乱。我们定义U(k)=T(2^k)/(2c)。
然后我们有U(k+1)-2U(k)=2^k，或者，如果我们定义U'（k）=U（k+1）-U（k）：
U'(k)-U(k)=2^k
这里的k是离散的，但是我们可以让它连续，如果我们这样做，那么U'就是U的导数。
此时解决方案是显而易见的：如果您曾经求导过，那么您就知道，如果函数与其导数的差是指数级别的，那么函数本身就必须是指数级别的（因为只有在这种情况下，导数才是其自身的某个倍数）。
此时您就知道U(k)是指数级别的，因此您可以为指数中的未知系数插入一个指数，并将其重新插入以解决T。
- user541686
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接