归并排序时间复杂度分析
 
归并排序
工作原理
时间复杂度计算
 

 
归并排序
 
归并排序也叫（Merge sort）。
 
工作原理
 
将给定的数组一份为二
对两部分数组再使用归并排序使其有序
最后再将两部分数组合并
 
 
时间复杂度计算
 
1、首先可知
 
$$f(n)=2f(\frac{n}{2})+n$$
 其中：$$f(n)表示对n个数进行归并排序$$ $$2f(\frac{n}{2})表示将n个数分成两部分分别进行归并排序$$ $$n表示对两个子过程结束之后合并的过程$$
 2、推导
 $$f(\frac{n}{2})=2f(\frac{n}{4})+\frac{n}{2}当n=\frac{n}{2}时$$
 $$f(\frac{n}{4})=2f(\frac{n}{8})+\frac{n}{4}当n=\frac{n}{4}时$$
 $$\dots \dots$$
 $$f(\frac{n}{2^{m-1}})=2f(\frac{n}{2^m})+\frac{n}{2^{m-1}}当n=\frac{n}{2^{m-1}}时$$
 3、由此可得：
 
$$f(n)=2f(\frac{n}{2})+n$$
 $$=2\times (2f(\frac{n}{4})+\frac{n}{2})+n$$
 $$=2^{2}f(\frac{n}{2^2})+2n$$
 $$=2^2\times (2f(\frac{n}{8})+\frac{n}{4})+2n$$
 $$=2^{3}f(\frac{n}{2^3})+3n$$
 $$\dots \dots$$
 $$=2^{m}f(\frac{n}{2^m})+mn$$
 
当 m 足够大时(仅剩一个数字时)，可使得$$\frac{n}{2^m}=1$$
 求出 $$m=lo{g}_{2}n$$
 
$$代入f(n)=2^{m}f(\frac{n}{2^m})+mn中可得$$
 $$f(n)=2^{(lo{g}_{2}n)}f(1)+n\cdot lo{g}_{2}n$$
 $$其中f(1)=0$$
 $$所以最终f(n)=n\cdot lo{g}_{2}n$$

https://blog.csdn.net/liangjiabao5555/article/details/89670082
 
归并排序方法就是把一组n个数的序列，折半分为两个序列，然后再将这两个序列再分，一直分下去，直到分为n个长度为1的序列。然后两两按大小归并。如此反复，直到最后形成包含n个数的一个数组。
 
归并排序总时间=分解时间+子序列排好序时间+合并时间
 
无论每个序列有多少数都是折中分解，所以分解时间是个常数，可以忽略不计。
 
则：归并排序总时间=子序列排好序时间+合并时间
 

如果假设一个序列有n个数的排序时间为T(n)，T(n)是一个关于n的函数，随着n的变化而变化。
 
那么我们将n个数的序列，分为两个(n/2)的序列。
 
 
那么T(n)=2*T(n/2)+合并时间
 
由于合并时，两个子序列已经组内排好序了，那我们将两个排好序的序列组合成一个大的有序序列，只需要一个if循环即可。if循环中有n个数需要比较，所以时间复杂度为n。
 
那么T(n)=2*T(n/2)+n
 
 
 
我们再将两个n/2个序列再分成4个(n/4)的序列。
 
 
一个（n/2）序列排序时间=两个(n/4)的序列排序时间+两个(n/4)的序列的合并为一个（n/2）的序列时间
 
T(n/2)=2*T(n/4)+n/2
 
将T(n/2)带入到T(n)中，T(n)=2*(2*T(n/4)+n/2)+n，
 
通过化简T(n)=4*T(n/4)+2n
 
 
 
我们再将4个n/4个序列再分成8个(n/8)的序列。
 
 
T(n/4)=2*T(n/8)+n/4
 
将T(n/4)带入到黄色公式中，T(n)=4*(2*T(n/8)+n/4)+2n
 
通过化简T(n)=8*T(n/8)+3n
 
······
 

这样分下去，前面我们已经说过了，分为n个序列，每个序列里只有一个数为止。
 
前面我们假设的一个序列有n个数的排序时间为T(n)，现在每个序列只有一个数，所以不需要进行组内排序，时间复杂度为0。T(1)=0
 
 
大家有没有找到规律，右边式子中n前面的系数随着层数的增加而增加，第一层公式中没有n，则系数为0，第二层n的系数为1，第三层为2，第四层为3。那么规律就出来了，n前面的系数为层数减1。
 
那这个图有没有很熟悉，就像一个二叉树一样，通过二叉树的知识点我们可以知道，一个n个结点的二叉树层数为(log2n)+1。
 
那么n前面的系数为层数减1。
 
(log2n)+1-1=log2n
 
那log2n就是最底层n的系数。
 
 
 
那么我们最后一层是不是可以这样表示
 
T(n)=n*T(1)+(log2n)*n
 
T(1)=0，那么T(n)=(log2n)*n
 
所以归并排序的时间复杂度为nlog2n

 
众所周知，归并排序的时间复杂度是O(N*lgN)
 
 
归并排序的时间复杂度推导书上网上一抓一把，但是多数证明都是基于N=2k这个假设来证明的，下面我给出一般情况的证明。
 
 
先上归并排序代码：
 
 
 
  
public class MergeSort implements Sort {
    private static int count = 0;

    @Override
    public int[] sort(int[] data) {
        return sort(data, 0, data.length - 1);
    }

    private int[] sort(int[] data, int low, int high) {
        if (low == high) {
            return new int[] { data[low] };
        }
        int mid = (low + high) >> 1;
        int[] left = sort(data, low, mid); //(1)
        int[] right = sort(data, mid + 1, high); //(2)

        int[] result = new int[high - low + 1];
        int i = 0, k = 0;
//(3) 
        for (int j = 0; j < result.length; j++) {
            count++;
            if (i == left.length) {
                result[j] = right[k++];
            } else if (k == right.length) {
                result[j] = left[i++];
            } else {
                if (left[i] <= right[k]) {
                    result[j] = left[i++];
                } else {
                    result[j] = right[k++];
                }
            }
        }
        return result;
    }

}
 
 
 
 
根据代码可以看出，时间消耗主要在我标红的3个地方，可以得出：
 
 
 
 
我们知道每一个整数都可以表示为2i+k的形式，如1=20+0，5=22+1，10=23+2，因此
 
 
设N=2i+k
 
 
令n=i+1，则有：
 
 
 
 
根据我们对i和k的定义，k<2i（不然如果k>=2i那么i就应该能取到i+1了）。
 
 
因此有：
 
 
 
 
所以有：
 
 
 
 
回到开头的公式：
 
 
 
 
所以：
 
 
 
 
据此可以得出归并排序的时间复杂度是O(N*lgN)。
 
 
 
 
转载于:https://www.cnblogs.com/sheeva/p/6600666.html

 
最好，最坏，评价时间复杂度都是  nlogn
 
 
空间复杂度是  O(n)
 
 
 
 
 
 
 
 
比较占内存，但是效率高且稳定
 
转载于:https://www.cnblogs.com/wust221/p/5414828.html