所以我一直在研究排序算法。
我一直在寻找合并排序的复杂性。
有人可以向我解释一下 h=1+lg(n)
最佳答案
如果你继续将 n 除以 2，你最终会得到 1。
也就是说，根据对数的定义，需要 log2(n) 除以 2 才能实现这一点。
每次除以 2 时，我们都会向递归树添加一个新级别。
将其添加到根级别(不需要任何划分)，我们总共有 log2(n) + 1 个级别。
这是一个更酷的证明。请注意，重新排列后，我们有 T(2n) - 2 T(n) = 2 c n。
如果 n = 2k，那么我们有 T(2k + 1) - 2 T(2k) = 2 c 2k。
让我们简化一下困惑。让我们定义 U(k) = T(2k)/(2 c)。
然后我们有 U(k + 1) - 2 U(k) = 2k，或者，如果我们定义 U'(k) = U(k + 1) - U(k):
U'(k) - U(k) = 2k
k 在这里是离散的，但我们可以让它是连续的，如果我们这样做，那么 U' 是 U 的导数。
在这一点上，解决方案是显而易见的:如果您曾经使用过导数，那么您就会知道，如果一个函数与其导数的差是指数的，那么该函数本身必须是指数的(因为只有在这种情况下，导数才会是自身的一些倍数)。
那时您知道 U(k) 是指数的，因此您可以为指数中的未知系数插入指数，然后将其重新插入以求解 T。
关于sorting - 归并排序——递归树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24347941/