GingerBear
时间复杂度之merge sort
如果大家不太会分析时间复习度，可以看看这个系列。我最近会慢慢post一些比较常见的算法，我都会用数学的方法分析他们的时间复杂度。其实大部分我们常见的算法都可以用类似的几种数列方法来分析，大家看看帖子，然后在自己动手算算基本就会总结大部分方法了。我已经在斐波那契和kth largest那两个帖子发了两个分析，我剩下的会发发时间复杂度不一样的算法分析。 这一个post,讲下merge sort! 也就是所有时间复杂度是o(nlgn)的都大概可以这么分析。
@allen6432 我又来不耻下问了
- 能不能解释一下
T(n) = T(n/2) + O(n)这个表达式是什么意思？以及它是这么得来的？ - 为啥每次看到
n/2，就用2^a = n来代替？
来趁热打铁写一个merge sort，这里使用比较好理解的递归的方法，这个算法一般需要使用额外空间。额外空间使用的位置是merge两个数组的时候，需要一个更长的数组存放merge的结果。
在理想状况下正好能均分（强迫症患者的福音），试着考虑一下空间的使用情况，第一次merge应该发生在数组被切分到最细的时候，在最细的那一层，merge的是两个只有一个元素的数组，它使用了2个额外的空间返回合并的结果，在这一层共发生了n/2次merge，乘一下得出在最细层使用了n个额外空间。在往上一层，merge的是两个包含两个元素的数组，需要4个额外空间来存结果，在这一次发生了n/4次merge，乘一下还是n。以此类推直到最后一次大merge，需要merge是两个长度为n/2的数组，长度还是n。
所有总共的空间使用情况就是，n乘以**“层数”**。如果数组长度是n，那层数是多少呢？换句话说，长度为n的数组，要劈多少次才能得到一个长度为1的数组呢（没法再劈了）？既然每劈一次一半，n就除以2，那么如果要劈k次的才能得到长度为1的数组，n / (2^k) = 1。算一下就是k = log2n，所以层数就是lgn了。
所以空间复杂度就是n * log(n)个单位，即O(n log n)。
=========================== 华丽分割 ===========================
以上纯属是我的YY，看似很有道理，但其实是错的。
回过头来想想，其实空间是可以重复利用的，不像时间过去了就过去了，所以只需要一个长度为n的额外数组，就可以给满足不管是哪一层的哪一次merge的需求，所以其实空间复杂度是O(n)。给自己的一个教训就是，不要死钻牛角尖，跳出来想想可能会发现更加简单直接的方法。
另外，Merge Sort也有一些变种，可以做到不需要额外空间，成为in-place merge sort，这个就对编程能力是不小考验了，是一个不错的练习。
奇怪的想法
我产生了一个奇怪的想法想请教一下大家，程序的效率跟merge的的个数有没有关系？如果每次分成三块呢？分成四块呢？直接分成n块呢？
常规代码
static int[] mergeSort(int[] arr, int start, int end) {
if (start == end) {
int [] tmp = { arr[start] };
return tmp;
}
return merge(mergeSort(arr, start, (start + end) / 2), mergeSort(arr, (start + end) / 2 + 1, end));
}
static int[] merge(int[] arr1, int[] arr2) {
int[] ret = new int[arr1.length + arr2.length];
int i = 0, j = 0, k = 0;
while (i < arr1.length || j < arr2.length) {
// prevent array out bound, check bound first
if (j >= arr2.length) {
ret[k++] = arr1[i++];
} else if (i >= arr1.length) {
ret[k++] = arr2[j++];
} else if (arr1[i] >= arr2[j]){
ret[k++] = arr1[i++];
} else if (arr1[i] < arr2[j]){
ret[k++] = arr2[j++];
}
}
return ret;
}
public static void main(String [] args) {
int[] arr1 = {2, 34, 432, 2342, 232, 12, -123, 4};
mergeSort(arr1, 0 ,arr1.length - 1);
simpleAssert(Arrays.toString(arr1) == "[-123, 2, 4, 12, 34, 232, 432, 2342]", "regular");
}
static void simpleAssert(boolean ifTrue, String msg) {
String m = ifTrue ? "SUCCESS\t" : "FAILED\t";
System.out.println(m+msg);
}
@GingerBear 我没有考虑过他空间的复杂度，但是基于对时间复杂度的角度来说，分三段或者分多段一上，对效率提升影响几乎没有很大的变化。 分两段：O(nlog(2)n) 分a段是O(nlog(a)n)。也就是是说分多少段只是影响了底数，也就是这两个函数是一个常系数的倍数关系。