hand5.pdf

步骤

• Divide up problem into several subproblems (of the same kind).
• Solve (conquer) each subproblem recursively.
• Combine solutions to subproblems into overall solution.

Mergesort

• Recursively sort left half.
• Recursively sort right half.
• Merge two halves to make sorted whole.

时间复杂度

证明1：数学归纳法

证明2：

理解：对于每一次迭代，每一层的n总数是不变的, 然后所有的都会加到顶上，每一次向上总数都会+n, 一共会加log2N 次所以是Nlog2N

取有无上下界的情况是针对奇数，可以有左半边和右半边.

这个注意和之前的题的区别，n-1, 这个就没法保持每一层加的总数是定值，其实就是每一个节点都比下一层加上来的要-1了。那么要减去多少个1呢？第一种方法我们可以从上一题考虑，确实了每个节点除了叶子节点都-1了，那么总共的非叶子节点为2^层数-3 = 2^(log2N)-1 ,所以答案是NlogN-2^(logN)+1