精华内容
下载资源
问答
  • 归并排序时间复杂度过程分析

    万次阅读 多人点赞 2019-07-08 20:54:43
    归并排序方法就是把一组n个数的序列,折半分为两个序列,然后再将这两个序列再分,一直分下去,直到分为n个长度为1的...归并排序时间=分解时间+子序列排好序时间+合并时间 无论每个序列有多少数都折中分解,...

    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

    展开全文
  • 详谈归并排序时间复杂度过程推导----软考

    千次阅读 多人点赞 2019-04-29 11:57:24
    归并排序方法就是把一组n个数的序列,折半分为两...无论每个序列有多少数都折中分解,所以分解时间个常数,可以忽略不计。 则:归并排序总时间=子序列排好序时间+合并时间 如果假设一个序列有n个数的排序时间...

    归并排序方法就是把一组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

    展开全文
  • (1)冒泡排序时间复杂度: 1.比较相邻的元素,如果第一个比第二个大(升序),就交换他们两个 2.对每一对相邻的元素做同样的工作,从开始到结尾的最后一对 这步做完后,最后的元素会最大的数 3.针对所有的...

    时间复杂度我们使用大O表示法进行表示,

    (1)冒泡排序的时间复杂度:

    1.比较相邻的元素,如果第一个比第二个大(升序),就交换他们两个

    2.对每一对相邻的元素做同样的工作,从开始到结尾的最后一对

      这步做完后,最后的元素会是最大的数

    3.针对所有的元素重复以上的步骤,除了最后一个

    4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较

    5.稳定性:数值相同的元素在排序中不交换位置为稳定反之为不稳定

    6.最优复杂度:O(n)   最坏复杂度:O(n^2)   稳定性:稳定

     

    (2)快速排序的时间复杂度:

    通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行,以此达到整个数据变成有序序列

    过程描述:

    1、定义一个标杆,将列表的第一个元素存入标杆,列表的第一个位置相当于空出来了

    2、定义两个指针low,high,分别记录列表头和列表尾的位置

    3、判断low是不是小于high,列表尾high位置的元素是不是大于等于标杆,如果是high向左移动一位

      重复执行这步判断,当条件不成立时,让low位置存放当前high位置的元素

    4、判断low是不是小于high,列表头low位置的元素是不是小于标杆,如果是low向右移动一位

     重复执行这步判断,当条件不成立时,让high位置存放当前low位置的元素

    5、让4、5两步交替执行,直到low >= high时退出循环。此时low = high

    6、此时找到的low的位置就是标杆的位置,将记录的标杆元素,放置在这个位置。

    7、递归执行上述步骤直到low >= high时退出。

    8、最优时间复杂度计算:n拆分多少次能只剩一个元素,也就是n除以多少次2能等于1

      即n/2^x = 1 --> 2^x = n --> x = logn (log以2为底,n的对数)

      每次让列表中的值沿着初始值分为左右两半的过程的时间复杂度为n

      所以最优时间复杂度为nlogn

    9、最优复杂度:O(nlogn)    最坏复杂度:O(n^2)     稳定性:不稳定

     

    (3)归并快速排序的时间复杂度

    1、归并排序的思想是先递归分解数组,再合并数组

    2、将数组分解最小之后,然后合并两个有序数组。

    3、基本思路就是比较两个数组最前面的数,谁小就取谁,取了后相应的指针就往后移一位。

    4、然后再比较,直至一个数组为空,最后把两一个数组的剩余部分复制过来即可。

                      5、最优复杂度:O(nlogn)   最坏复杂度:O(nlogn)   稳定性:稳定

     

    (4)选择排序时间复杂度:

    1、始终从未排序的序列中找到最小的放到最前面

    2、将第一个元素先作为最小值,用第一个元素和后面的元素依次比较

    3、首次碰见比第一个元素更小的元素就记录这个“较小元素”的位置

    4、继续比较如果碰见比“较小元素”还更小的元素,就将记录的“较小元素”的位置信息,替换成“更小元素”的位置信息

    5、直到比较完整个序列,最小的元素位置信息就被记录下来了

    6、交换第一个元素和最小元素的位置,序列的头部就变成了最小的元素

    7、再将第二个元素先作为序列剩余元素的最小元素,和剩下的元素重复上述步骤进行比较

    8、将第二小的元素找到,并和第二个元素进行交换

    9、多次重复上述步骤n-1次,即可得到升序序列

    10、最优复杂度:O(n^2)    最坏复杂度:O(n^2)    稳定性:不稳定

    展开全文
  • 内部排序法的性能 快速排序法的平均执行时间...用堆排序和归并排序法效率高。当序列长度较短时,可采用容易实现的选择排序、插入排序 或者冒泡排序法。当序列长度较长时,宜采用快速排序、堆排序或者归并排序。...

    内部排序法的性能

    快速排序法的平均执行时间较少,但是在最坏的情况下它的性能会发生退化,这时不如
    用堆排序和归并排序法效率高。当序列长度较短时,可采用容易实现的选择排序、插入排序
    或者冒泡排序法。当序列长度较长时,宜采用快速排序、堆排序或者归并排序。

    展开全文
  • LeetCode: 164. 最大间距 排序之后, 计算相邻元素之间的最大差值。 要求: 在线性时间复杂度 和 空间复杂度 ...查看这部分源码 , 这个查找的时间复杂度是多少 >> 待补 int maxVal = Array
  • 排序(7):归并排序

    2020-04-15 23:25:55
    爱教育面试问归并排序时间复杂度多少: 归并排序:其基本思想分治策略,先进行划分,然后再进行合并。 假设要对数组C进行归并排序,步骤: 1.先将C划分为两个数组A和B(即把数组C从中间分开) 2.再分别对数组A...
  • 归并排序

    2019-04-21 11:46:34
    //分治的典型应用————归并排序 /* 数组排序任务可以如下完成: ...归并排序时间复杂度 对n个元素进行排序的时间: T(n) = 2*T(n/2) + a*n (a常数,具体多少不重要) = 2*(2*T(n/4)+a*n/2)+a...
  • 排序算法—归并排序

    2015-11-01 00:45:58
    /***************************** *归并排序:时间复杂度O(nlgn) *一种稳定的排序算法 ...其时间复杂度是多少呢? * ****************************/ void Sort(int *ary, int n)//归并排序,数组下标从0开始 {
  • 归并排序和快速排序

    2019-06-04 11:19:19
    归并排序 归并排序采用的分而治之和递归的思想,如果想要对一个数组进行归并排序,那么先将这个数组分为...优点:时间复杂度稳定,不管原数组的有序度为多少,需要进行的步骤都固定的。时间复杂度固定为O(n...
  • 归并排序(Merge Sort)

    2019-03-18 13:29:10
    若有两个已经升序的数组,将这两个子数组合并成一个升序数组的时间复杂度是多少? 只需要两个指针分别指向两个数组的首元素,比较它们的大小,选择其中较小的数按序放进合并数组,对应指针后移,最后将一个子数组...
  • 排序通常来说, 排序是为了进行快速排序衡量排序算法的优劣方式时间复杂度: 关键字的比较次数 与 记录的移动次数空间复杂度: 排序算法中需要多少辅助内存稳定性: 如果a原本在b前面, 且a=b, 排序之后a仍然在b的前面...
  • 在学习算法的过程中,我们难免会接触很多和排序相关的算法。总而言之,对于任何编程人员来说,基本的排序... 时间复杂度:需要排序的的关键字的比较次数和相应的移动的次数。 空间复杂度:分析需要多少辅助的内存。 ...
  • 分析 数组排序任务可以如下完成...归并排序时间复杂度 对n个元素进行排序的时间: T(n)=2T(n/2)+an (a常数,具体多少不重要) =2T(sT(n/4)+an/2)+an =4T(n/4)+2an …… =2k*T(n/2k)+kan 一直做到n/2^k=1(此时k...
  • 此题如果直接按照冒泡排序的方法排序并计算次数会超时,因为时间复杂度是O(n2) 其实分析一下,我们只要求出给出的数组中有多少个逆序对即可,下面的一种解法采用了归并排序的方法来求逆序对数。 #include #...
  • 排序分为内部排序和外部排序 ...(1)时间复杂度:它主要分析记录关键字的比较次数和记录的移动次数 (2)空间复杂度 :算法中使用的内存辅助空间的多少 (3)稳定性:若两个记录A和B的关键字值相等,但排序...
  • 今天这篇基于之前的 8 大排序算法基础之上,增加一个堆排序,也就是这么 9 个排序算法:冒泡排序、插入排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。它们对应的时间复杂度如下所示: ...
  • 求逆序对(复杂度为nlogn)

    千次阅读 2016-03-20 16:54:15
    问题: 对于一个包含N个非负整数的数组A[1..n],如果有i A[ j ],则称(A[ i] ,A[ j] )为数组A中的一个逆序对。 例如,数组(3,1,4,5,2)的逆序对有(3,1)...这个题目十分的经典,是归并排序的一个完美应用,分治
  • 做设计的,要兼顾程序时间复杂度,内存复杂度, 我觉得以上也同时要涉及人脑复杂度, 这直接于资金的投入多少钱什么...一下一个关于归并排序的例子, 我博客里面的,算法倒通俗易理解不用一直去检查
  • 排序专项练习

    千次阅读 2015-10-25 13:55:11
    1.当待排序记录已经从小到大排序或者...2.以下排序中时间复杂度最差的是 归并排序 选择排序 希尔排序 堆排序 答案 : B 3.最坏情况下 insert sort, quick sort ,merge sort 的复杂度分别是多少
  • 内部排序

    2017-05-06 16:06:17
    时间复杂度:比较次数和移动次数 空间复杂度:需要多少辅助内存 稳定性:若A和B关键字相等,排序后先后次序没变则称之为稳定的,否则不稳定的。 内部排序和外部排序: 需不需要辅助内存。 内部排序分类...
  • Java排序算法学习

    2017-03-11 19:17:12
    选择排序、快速排序、希尔排序、堆排序...时间复杂度是多少? 3、在什么情况下,算法出现最好情况 or 最坏情况? 4、每种算法的具体实现又是怎样的? 这个是排序算法里面最基本,也是最常考的问题。下面是我的小...
  • NLP面试题目总结

    千次阅读 2020-03-02 22:37:28
    最坏的时间复杂度是多少? 2. 归并排序算法 请实现归并排序,自行设计测试用例来说明算法的准确性,算法的时间和空间复杂度是多少?最坏的时间复杂度是多少? 3. 面对一个具体的问题,倾向于使用归并还是快排,为...
  • 常见的十大排序算法有:冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序等。 常见的十大排序算法,时间复杂度和空间复杂度如下图: 快速排序 快速排序...
  • 十大排序算法详解

    2019-12-31 12:20:54
    十大排序算法详解 10种排序算法的比较 ...无论代码执行多少行,只要没有循环等复杂结构,那这个代码的时间复杂度就是O(1) ②对数阶O(logn) ③线性阶O(n) 单层for循环 ④线性对数阶O(nlogN) 时间复杂度为O(logn)...
  • HDU5122 K.Bro Sorting

    2018-10-06 22:17:00
    题目大意: 定义一种新的排序算法:随机的选一个数,若比它后一个大就交换,直到后一个比它小,完成一次操作。...查找逆序对用归并排序时间复杂度就够了。 若从小到大排, 在归并排序每次合并...
  • 堆-堆排序

    2016-06-19 17:06:00
    堆排序,与归并排序一样,时间复杂度为O(nlgn),与插入排序一样,具有空间原址性:任何时候都只需要常数个额外的元素空间存储临时数据。(二叉)堆一个数组,可以被看成一个近似的完全二叉树,树上的每一个结点...
  • 作为程序员的小Q,他的数列和其他人的不...求逆序对问题用归并排序时间复杂度比暴力算法更低。 假设有一个数组{8,1,2,5,7,4,3,6} 首先归并排序第一次对数组进行分割 8 1 2 5 7 4 3 6 二次分割 8 1 25 ...
  • 统计递归树代表的时间复杂度通常计算每一层的时间,然后再看最多会分解到多少层。归并操作主要归并函数相关,也就是数据规模,这里递归树每层的数据规模都n。我们只需要知道这棵树的高度 h,用高度 h 乘以每...

空空如也

空空如也

1 2 3
收藏数 60
精华内容 24
关键字:

归并排序时间复杂度是多少