Merge sort的有关问题
Merge sort的问题
数组＜１、５、３、７、２、６、４、８＞
１、
Merge sort算法的时间复杂度为：
Tb（n）为：
Tb（1）=0；
Tb（n）=Tb（┎ｎ/２┑）+Tb（┖ｎ/２┙）+（┖ｎ/２┙），ｎ＞＝２；
基于算法的记述请说明一下。
２、上式用O计算量应该如何表示？
一个练习册上的题我一点思路也没有请大家指教一下。
------解决方案--------------------
当前问题规模为 n，所花时间为 T(n).
归并的过程中，每一次都呗划分成两个子问题，每个子问题规模为 (n/2),所花时间就可以表示为T(n/2),既然是两个子问题，那么就是 2T(n/2), 这两个子问题完成以后，还要合并一次，花费时间为 cn, c为一个常数，因此解决当前规模为n的问题，花费的总时间为
2T(n/2)+cn.
数组＜１、５、３、７、２、６、４、８＞
１、
Merge sort算法的时间复杂度为：
Tb（n）为：
Tb（1）=0；
Tb（n）=Tb（┎ｎ/２┑）+Tb（┖ｎ/２┙）+（┖ｎ/２┙），ｎ＞＝２；
基于算法的记述请说明一下。
２、上式用O计算量应该如何表示？
一个练习册上的题我一点思路也没有请大家指教一下。
------解决方案--------------------
当前问题规模为 n，所花时间为 T(n).
归并的过程中，每一次都呗划分成两个子问题，每个子问题规模为 (n/2),所花时间就可以表示为T(n/2),既然是两个子问题，那么就是 2T(n/2), 这两个子问题完成以后，还要合并一次，花费时间为 cn, c为一个常数，因此解决当前规模为n的问题，花费的总时间为
2T(n/2)+cn.