精华内容
下载资源
问答
  • 归并排序算法的时间复杂度

    千次阅读 2019-07-10 17:37:12
    我们对n个元素进行归并排序,需要时间T(n), 那分解成两个子数组排序的时间都是T(n/2)。...归并排序的时间复杂度计算公式是: T(1) = C; n=1 时,只需要常量级的执行时间,所以表示为 C。 T(n) = 2*T(n/2...

    来自教程:https://time.geekbang.org/column/article/41913

    我们对n个元素进行归并排序,需要时间T(n),

    那分解成两个子数组排序的时间都是T(n/2)。

    merge()函数合并的时间复杂度是O(n)。

    归并排序的时间复杂度计算公式是:

    T(1) = C;   n=1 时,只需要常量级的执行时间,所以表示为 C。
    T(n) = 2*T(n/2) + n; n>1
    

    如何求T(n)?

    我们对T(n/2)一级一级分解:

    T(n) = 2*T(n/2) + n
         = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
         = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
         = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
         ......
         = 2^k * T(n/2^k) + k * n
         ......
    

    可以看出:T(n) = 2^{k} T(\frac{n}{2^{k}}) + kn

    \frac{n}{2^{k}} = 1时,就是最底层,也就是进行了k次之后达到了最底层。

    求出k = \log n,带入T(n)的公式,求出:T(n) = Cn + n\log n,使用大O表示法:T(n) = O(nlogn);

    而且归并排序的算法跟有序度无关,所以时间复杂度很稳定都是O(nLogN);

     

    展开全文
  • 这里我直接从网上找了一份对归并排序算法的比较好的介绍排序算法 。 计算时间复杂度 关键是怎么计算时间复杂度? 我们在假设数组的长度为n的基础上进行归并排序,假设排序的总共用时为T[n]T[n]T[n],则: 第一次,将...

    如何计算归并排序算法的时间复杂度?

    什么是归并排序?

    归并排序的概念十分简单,就是“分而治之”的思想。这里我直接从网上找了一份对归并排序算法的比较好的介绍排序算法

    计算时间复杂度

    关键是怎么计算时间复杂度?
    我们在假设数组的长度为n的基础上进行归并排序,假设排序的总共用时为T[n]T[n],则:
    第一次,将数组对半分,分别对两个子数组进行排序,并合并两个有序数组,所需要的时间为
    T[n]=T[n12]+T[n+12]+Θ[n] T[n]=T[\lceil\frac{n-1}{2}\rceil]+T[\lfloor\frac{n+1}{2}\rfloor]+\Theta[n]
    我们将其简写为
    T[n]=2T[n2]+Θ[n] T[n]=2\cdot{T[\frac{n}{2}]}+\Theta[n]
    同理,第二次,继续将子数组对半分,并分别对两个子子数组进行排序,并合并两个有序数组,所需要的时间为
    T[n2]=2T[n4]+Θ[n2] T[\frac{n}{2}]=2\cdot{T[\frac{n}{4}]}+\Theta[\frac{n}{2}]
    依照这个规律,我们计算T[n]T[n2]T[n4]T[2]T[1]T[n]、T[\frac{n}{2}]、T[\frac{n}{4}]。。。、T[2]、T[1],且最终可得到下面这个式子:
    T[n]=Θ[n]+2Θ[n2]+4Θ[n4]+...+nΘ[1]T[n]=n+2n2+4n4+...+n1 T[n]=\Theta[n]+2\Theta[\frac{n}{2}]+4\Theta[\frac{n}{4}]+...+n\Theta[1] T[n]=n+2\cdot\frac{n}{2}+4\cdot\frac{n}{4}+...+n\cdot1
    我们可以把Θ[n]\Theta[n]理解为在nn时间内完成的程序,则
    T[n]=n+2n2+4n4+...+n1=n+n+n+...+n=nlog2n \begin{aligned} T[n]&=n+2\cdot\frac{n}{2}+4\cdot\frac{n}{4}+...+n\cdot1 \\&=n+n+n+...+n \\&=n\cdot{log_2{n}} \end{aligned}
    这里,log2nlog_2{n}是怎么冒出来的?就是因为一共有log2nlog_2{n}nn相乘(不懂的话,自己好好思考一下)。
    因此,最终就可得到归并排序算法的时间复杂度为nlog2nn\cdot{log_2{n}}

    展开全文
  • 归并排序(MERGE-SORT)是建立在归并操作上一种有效的排序算法,该算法是采用分治法(Divide and Conquer)一个非常典型应用。 算法分析 排序思想就是将元素无限拆分,直到无可拆分为止,再将拆分元素...

    归并排序

    算法原理

    归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

    算法分析

    排序的思想就是将元素无限拆分,直到无可拆分为止,再将拆分的元素两两按序合并。

    归并排序的原理可以通过下面这张图看清楚:

    归并排序

    代码实现

    /**
     * @Title: mergeSort 
     * @Description: 归并排序 
     * @param: array
     * void @throws
     */
    public static void mergeSort(int[] array) {
        int[] temp = new int[array.length];
        sort(array, temp, 0, array.length - 1);
    }
    
    /**
     * @Title: sort
     * @Description: 使用归并排序,对array的left~right进行排序
     * @param: array
     * @param: temp
     * @param: left
     * @param: right
     */
    private static void sort(int[] array, int[] temp, int left, int right) {
        // 定义待排序中间元素
        int mid = (left + right) / 2;
        if (left < mid) {
            // 递归排序中间元素及左边的元素
            sort(array, temp, left, mid);
        }
        if (mid + 1 < right) {
            // 递归排序中间元素右边的元素
            sort(array, temp, mid + 1, right);
        }
        // 合并左右两边的元素
        merge(array, temp, left, mid, right);
    }
    
    /**
     * @Title: merge
     * @Description: 借助temp数组,合并mid元素左右的元素
     * @param: array
     * @param: temp
     * @param: left
     * @param: mid
     * @param: right
     */
    private static void merge(int[] array, int[] temp, int left, int mid, int right) {
        // 用于遍历左边元素
        int i = left;
        // 用于遍历右边元素
        int j = mid + 1;
        // 临时变量
        int t = 0;
        while (i <= mid && j <= right) {
            // 将左右两边最小的元素添加到temp数组中
            if (array[i] <= array[j]) {
                temp[t++] = array[i++];
            } else {
                temp[t++] = array[j++];
            }
        }
    
        while (i <= mid) {
            // 将左边剩余元素添加到temp数组中
            temp[t++] = array[i++];
        }
        while (j <= right) {
            // 将右边剩余元素添加到temp数组中
            temp[t++] = array[j++];
        }
        t = 0;
        // 将temp中的元素全部拷贝到原数组中
        while (left <= right) {
            array[left++] = temp[t++];
        }
    }  array[j] = temp;

    时间复杂度和算法稳定性

    从上面的代码中可以看出每次合并操作的时间复杂度是O(N),而二叉树的深度是log2N,所以总的时间复杂度是O(N*lgN)。

    因为在合并的时候,如果两个数相等,可以将前面的数先放到辅助数组中,所以归并排序是稳定的。

    相关代码都在github上:https://github.com/LebronChenX/sort

    喜欢这篇文章的朋友,欢迎长按下图关注公众号lebronchen,第一时间收到更新内容。
    扫码关注

    展开全文
  • 归并排序(MERGE-SORT)是建立在归并操作上一种有效的排序算法,该算法是采用分治法(Divide and Conquer)一个非常典型应用。将已有序子序列合并,得到完全有序序列;即先使每个子序列有序,再使子序列段...

    算法描述分析:

    归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并

    这是官方一点的对于归并排序的定义,简单的来说,我们把要排序的列表或者数组,每一次都给它递归生成n/2有序列表

    我们拿例子来看:

    有这样一个列表我们按照分治思想,先将它分为俩组

     

     按照这个思路,我们继续将列表分下去

    当我们通过递归分到只剩一个元素时,将俩边的元素进行合并成有序的一个列表

    接着其他递归出口也将对应的子列表,合并好

    一层层向上合并

    最后合并成一个列表

    复杂度分析:

    排序算法时间复杂度的比较图 转载:https://blog.csdn.net/weixin_40596016/article/details/79711682

    python 代码:

    # -*- coding: utf-8 -*-
    """
    Created on 
    
    @author: Administrator
    """
    #优化了网上对于合并的函数的复杂,pyhton的宗旨 
    #简洁胜过复杂
    #Complex is better than complicated.
    #利用列表性质
    def merge(leftList,rightList): 
        merges = []
        while leftList and rightList: #谁先出完循环结束
            if leftList[-1] >= rightList[-1]:  #将排序好的俩个列表从后放,谁最大谁放在后面
                merges.insert(0,leftList[-1])
                leftList.pop()
            else :
                merges.insert(0,rightList[-1])
                rightList.pop()
        merges=leftList+rightList+merges  #剩余相加即可,切记剩余的是小数要放在前面
        return merges
    def mergesort(a):
        if len(a)<=1:
            return a
        mid = len(a)//2
        rightList=mergesort(a[:mid])
        leftList=mergesort(a[mid:])
        return merge(leftList,rightList)
    
    a=[2,15,30,2,5,9,6]
    print (mergesort(a))

     

    展开全文
  • 插入排序算法采取增量式的策略解决问题,每次添一个元素到已排序的子序列中,逐渐将整个数组排序完毕,它的时间复杂度是O(n2)。下面介绍另一种典型的排序算法--归并排序,它采取分而治之(Divide-and-Conquer)的...
  • 根号n段归并排序算法时间复杂度分析过程: 1.合并 根号n向下取整 段子数组使用是自底向上两两归并策略 2.根号n段归并排序算法时间复杂度的数学推导
  • https://jimmee.iteye.com/blog/1985774时间复杂度n^2表示n平方,选择排序有时叫做直接选择排序或简单选择排序排序方法平均时间最好时间最坏时间桶排序(不稳定)O(n)O(n)O(n)基数排序(稳定)O(n)O(n)O(n)归并排序...
  • 然而,当该数列规模较大时,前述两种排序方式的时间复杂度为O(n)=n^2,所以我们需要更加高效的排序算法——归并排序,时间复杂度O(n)=nlogn。 算法核心概念 长度为1的数列为有序数列 就给出的两个有序数列,可以...
  • 自然归并排序算法时间复杂度分析

    千次阅读 2016-11-24 22:21:13
    最近在看一部美剧《breaking bad》,从中领会了不少东西。回头再看过去写博客,感觉真是很糟糕。...这篇对自然归并排序算法时间复杂度的分析便是第一篇。   对于普通归并排序算法,我就不
  • 归并排序也被认为是一种时间复杂度最优算法,我们还是按照基本过程,代码,最坏时间复杂度,平均时间复杂度,性能分析和改进这几个方面来展开讲述,为什么归并排序被认为是最优基于比较的排序算法(理论上)。...
  • 八种排序算法的时间复杂度复杂度

    万次阅读 多人点赞 2018-09-21 15:17:21
    1、稳定性 归并排序、冒泡排序、插入排序。基数排序是稳定的 ...最基础的四个算法:冒泡、选择、插入、快排中,快排的时间复杂度最小O(n*log2n),其他都是O(n2) 排序法 平均时间 最差情形 稳定度 ...
  • 时间复杂度为o(n)的排序算法:不是基于...八个经典排序算法的时间复杂度: O(n2)插入排序 选择排序 冒泡排序 O(n*logn)堆排序 希尔排序 快速排序 归并排序 八个经典排序算法的空间复杂度: O(1)插入排序 选择排序 冒泡
  • 时间复杂度为O(n^2)的排序算法 冒泡排序 选择排序 插入排序 希尔排序(它性能略优于O(n^2),但又次于O(nlogn),姑且归入此类) 二. 时间复杂度为O(nlogn)的排序算法 快速排序 归并排序 堆排序 三. 时间复杂度为...
  • 快速排序和二路归并排序的平均算法复杂度为O(nlog2n),请根据自己实现的代码,分别统计n=100000,1000000时上述两个算法的平均运行时间,并根据实验结果回答如下问题: 1)在上述输入规模下,两个算法的平均运行时间...
  • 一、常用排序算法的时间复杂度和空间复杂度表格 二、特点 1.归并排序: (1)n大时好,归并比较占用内存,内存随n的增大而增大,但却是效率高且稳定的排序算法。 (2)归并排序每次递归都要用到一个辅助表,...
  • 使用插入、冒泡、选择、快排、归并、堆排共6种排序算法对同一序列进行排序,统计排序所需平均时间并比较算法在时间优劣。供学习使用。
  • 常见排序算法及其时间复杂度

    万次阅读 多人点赞 2019-06-20 18:00:18
    稳定的排序算法1.1 冒泡排序1.1.1 冒泡排序流程1.1.2 冒泡排序实现1.2 插入排序1.2.1 插入排序流程1.2.2 插入排序实现1.3 归并排序1.3.1 归并排序流程1.3.2 归并排序的实现1.4 桶排序1.4.1 桶排序流程1.4.2 桶...
  • 各种排序算法的时间复杂度和空间复杂度 看起来归并排序还挺不错的,时间复杂度,空间复杂度都不错。 直接选择排序 排序过程: 1、首先在所有数据中经过n-1次比较选出最小的数,把它与第1个数据交换, 2、...
  • 排序算法之 冒泡排序及性能优化(时间复杂度+空间复杂度分析) 排序算法之 简单选择排序及时间复杂度分析 排序算法之 直接插入排序及时间复杂度分析 排序算法之 希尔排序及时间复杂度分析 排序算法之 快速排序及时间...
  • 排序算法之 归并排序 及其时间复杂度和空间复杂度 在排序算法中快速排序的效率是非常高的,但是还有种排序算法的效率可以与之媲美,那就是归并排序归并排序和快速排序有那么点异曲同工之妙,快速排序:是先...
  • 一、常用排序算法的时间复杂度和空间复杂度表格     二、特点   1.归并排序:   (1)n大时好,归并比较占用内存,内存随n的增大而增大,但却是效率高且稳定的排序算法。 (2)归并排序每次递归都要...
  • 排序算法的时间复杂度和空间复杂度 常用的内部排序方法有:交换排序(冒泡排序、快速排序)、选择排序(简单选择排序、堆排序)、插入排序(直接插入排序、希尔排序)、归并排序、基数排序(一关键字、多关键字)...
  • 各个排序算法及其时间复杂度

    千次阅读 2019-06-20 17:09:02
    稳定的排序算法1.1 冒泡排序1.1.1 冒泡排序流程1.1.2 冒泡排序实现1.2 插入排序1.2.1 插入排序流程1.2.2 插入排序实现1.3 归并排序1.3.1 归并排序流程1.3.2 归并排序的实现1.4 桶排序1.4.1 桶排序流程1.4.2 桶...
  • (1)简单的排序算法 排序方法 时间复杂度 冒泡排序 最好:O(n) 最坏:O(n2) 简单选择排序 O(n2) 直接插入排序 O(n2) 改进的排序算法 排序方法 时间复杂度 ...
  • 归并排序,其实就是递归+合并。
  • 排序算法的时间复杂度 排序算法 时间复杂度 稳定性 冒泡排序 O(n2) 稳定 插入排序 O(n2) 稳定 归并排序 O(N*logN) 稳定 选择排序 O(n2) 不稳定 快速排序 O(N*logN) 不稳定 堆排序 O(N*logN) 不...
  • 各种排序算法的时间复杂度

    万次阅读 多人点赞 2018-12-11 14:16:09
    冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法排序算法不稳定含义是:在排序之前,有两个数相等. 但是在排序结束之后,它们两个有可能改变顺序. 比如说:  在一个待排序队列中,A和B相等,且A排在B...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,287
精华内容 2,114
关键字:

归并排序算法的时间复杂度