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

    万次阅读 多人点赞 2017-09-09 10:18:34
    归并排序时间复杂度分析主要参考了他的博文,他还讲解了其他排序的时间复杂度分析及算法实现。可以说合并排序是比较复杂的排序,特别是对于不了解分治法基本思想的同学来说可能难以理解。总时间=分解时间+解决问题...

    归并排序时间复杂度分析

    主要参考了他的博文,他还讲解了其他排序的时间复杂度分析及算法实现。

    可以说合并排序是比较复杂的排序,特别是对于不了解分治法基本思想的同学来说可能难以理解。总时间=分解时间+解决问题时间+合并时间。分解时间就是把一个待排序序列分解成两序列,时间为一常数,时间复杂度o(1).解决问题时间是两个递归式,把一个规模为n的问题分成两个规模分别为n/2的子问题,时间为2T(n/2).合并时间复杂度为o(n)。总时间T(n)=2T(n/2)+o(n).这个递归式可以用递归树来解,其解是o(nlogn).此外在最坏、最佳、平均情况下归并排序时间复杂度均为o(nlogn).从合并过程中可以看出合并排序稳定。
    用递归树的方法解递归式T(n)=2T(n/2)+o(n):假设解决最后的子问题用时为常数c,则对于n个待排序记录来说整个问题的规模为cn。

    这里写图片描述

    从这个递归树可以看出,第一层时间代价为cn,第二层时间代价为cn/2+cn/2=cn…..每一层代价都是cn,总共有logn+1层。所以总的时间代价为cn*(logn+1).时间复杂度是o(nlogn).

    展开全文
  • 归并排序时间复杂度过程分析

    千次阅读 2020-07-02 14:31:51
    归并排序时间=分解时间+子序列排好序时间+合并时间 无论每个序列有多少数都是折中分解,所以分解时间是个常数,可以忽略不计。 则:归并排序时间=子序列排好序时间+合并时间 如果假设一个序列有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。归并算法中比较耗时的是归并操作,也就是把两个子数组合并为大数组。从图中我们可以看出,每一层归并操作消耗的时间总和是一样的,跟要排序的数据规模有关。我们把每一层归并操作消耗的时间记作 n。

    现在,我们只需要知道这棵树的高度 h,用高度 h 乘以每一层的时间消耗 n,就可以得到总的时间复杂度 O(n∗h)。

    从归并排序的原理和递归树,可以看出来,归并排序递归树是一棵满二叉树。我们前两节中讲到,满二叉树的高度大约是 log2​n,所以,归并排序递归实现的时间复杂度就是 O(nlogn)。我这里的时间复杂度都是估算的,对树的高度的计算也没有那么精确,但是这并不影响复杂度的计算结果。

    总结

    • 归并排序的时间复杂读为nlogn,每一行时间复杂度O(n) 然后二叉树高度log(n)

    参考

    归并排序图解_鸭梨的博客-CSDN博客

    展开全文
  • 归并排序 :log2N 通过middle 分开两等分 创建一个空间装进那个空间里面 再赋值回原来的空间 #include<stdio.h> #include<stdlib.h> #include<string.h> voidmerge_sort(int*arry,int*...

    归并排序 :log2N

    通过middle 分开两等分  

    创建一个空间装进那个空间里面   再赋值回原来的空间

     

    #include <stdio.h>

    #include <stdlib.h>

    #include <string.h>

    void merge_sort(int *arry,int *temp,int left,int middle,int right){

    int left_min=left;

    int left_max=middle;

    int right_min=middle+1;

    int right_max=right;

    int k=left;

    while(left_min<=left_max&&right_min<=right_max){

    if(arry[left_min]<arry[right_min]){

               temp[k++]=arry[left_min++];

     

    }else{

    temp[k++]=arry[right_min++];

     

    }

     

     

    }

      while(left_min<=left_max){

              temp[k++]=arry[left_min++];

     

    }

      while(right_min<=right_max){

            temp[k++]=arry[right_min++];

      

      }

      for(k=left;k<=right;k++){      //赋值给arry这个空间

          arry[k]=temp[k];

      

      }

     

    }

    void mergesort(int *arry,int *temp,int left,int right){

       if(left<right){int middle=(left+right)/2;

       mergesort(arry,temp,left,middle);   //递归

       mergesort(arry,temp,middle+1,right);

       merge_sort(arry,temp,left,middle,right);

    }

       }

     

    void main(){

    int add;

    int arry[]={1,5,8,4,2,1,4,6};

    int temp[8];

    int arryLength=sizeof(arry)/sizeof(int);

    mergesort(arry,temp,0,arryLength-1);

    for(add=0;add<arryLength;add++){

       printf("%d,",arry[add]);

     

    }

    system("pause");

    }

    展开全文
  • 归并排序,其实就是递归+合并。
  • 归并排序是建立在归并操作上的一种有效排序算法,该算法是采用分治法的一个典型应用。 这里的分治如何理解? 比如我们要统计本县城的高考状元,而一个县城中有很多中学,每个中学又有若干个班级,每个班级有若干名...
  • 归并排序的空间复杂度

    千次阅读 2021-05-29 09:32:03
    (待会儿你会发现,即便是快速排序,最坏情况下,时间复杂度也是 O(n^2)。)但是,归并排序并没有像快排那样,应用广泛,这是为什么呢?因为它有一个致命的“弱点”,那就是归并排序不是原地排序算法。 这是因为归并...
  • 如何计算归并排序时间复杂度? 什么是归并排序归并排序的概念十分简单,就是“分而治之”的思想。这里我直接从网上找了一份对归并排序算法的比较好的介绍排序算法 。 计算时间复杂度 关键是怎么计算时间复杂度...
  • 归并排序时间=分解时间+子序列排好序时间+合并时间 无论每个序列有多少数都是折中分解,所以分解时间是个常数,可以忽略不计。 则:归并排序时间=子序列排好序时间+合并时间 1 如果假设一个序列有n个数的排序...
  • 归并排序(时间复杂度O(nlgn)(最坏))

    千次阅读 2014-06-02 14:58:37
    #include #include #include #define m 11 void merge(int arr[],int low,int mid,int high) ...int k,begin1 =low,end1 = mid,begin2 = mid+1,end2 = high;...int *temp = (int*)malloc((high - low +1)*s
  • 在排序算法中快速排序的效率是非常高的,但是还有种排序算法的效率可以与之媲美,那就是归并排序归并排序和快速排序有那么点异曲同工之妙,快速排序:是先把数组粗略的排序成两个子数组,然后递归再粗略分两个子...
  • 归并排序及其复杂度分析

    千次阅读 2018-04-19 20:42:27
    * 时间复杂度分析:递归分解数据,需要递归logN次,每次都需要对n个数据扫描一次,最好最坏平均都一样,所以O(nlogn) * 空间复杂度分析:归并排序需要一个临时temp[]来储存归并的结果,所以 O(n) * * 基本...
  • 归并排序算法的时间复杂度

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

    万次阅读 2016-09-09 12:09:30
    这是《漫谈经典排序算法系列》第四篇,解析了归并排序。  各种排序算法的解析请参考如下: 《漫谈经典排序算法:一、从简单选择排序到堆排序的深度解析》 《漫谈经典排序算法:二、各种插入排序解析及性能...
  • 几种排序最坏和最好情况下的时间复杂度

    万次阅读 多人点赞 2017-10-03 15:55:52
  • 引言: 算法是计算机科学中的基础,程序=算法+数据结构,算法描述了我们将如何来处理数据的过程。本文将介绍两种算法的实现以及其中一种算法的复杂度分析过程。
  • 归并排序、快速排序都使用了分治的思想,时间复杂度都是O(N*logN)。由于其时间复杂度低,所以被广泛的应用,比如Java Collection.sort; Mysql数据库中的排序;Tim排序等。
  • 八大排序算法一、直接插入1.基本思路在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。2.代码...
  • 在数列排序中,如果只有一个数,那么它本身就是有序的;如果只有两个数,那么一次比较就可以完成排序。也就是说,数越少,排序越容易。那么,如果有一个由大量数据组成的数列,我们很难快速地完成排序,该怎么办呢?...
  • 时间复杂度: 用T(n)T(n)T(n)表示排大小为nnn的数组的时间:T(n)=2T(n/2)+nT(1)=1T(n)=2T(n/2)+n T(1)=1T(n)=2T(n/2)+nT(1)=1 关于如何解这个递归方程,这里介绍其中一种,我们假设n是2的幂: 首先,我们递推关系式的...
  • 归并排序 如果要排序一个数组,先把数组从之间分成前后两部分,并将这两部分划分为最小单位后排序,最后将排好序的两部分再合并,这样整个数组就有序了。 其实,归并排序可以用分治的思想最后用递归的方式自顶向下...
  • 时间复杂度 空间复杂度       稳定性           关联性        最好          最差        平均  ...
  • 归并排序时间复杂度

    2016-04-20 22:45:00
    最好,最坏,评价时间复杂度都是 nlogn 空间复杂度是 O(n) 比较占内存,但是效率高且稳定 转载于:https://www.cnblogs.com/wust221/p/5414828.html
  • 归并排序与快速排序时间复杂度均为O(nlogn),适合大规模的数据排序且很常用,它们都用到了分治思想,将大的问题分解成小问题来解决。接下来我们分别对其进行分析。 归并排序(Merge Sort) 思路:归并排序的核心...
  • 为了加深对平均时间复杂度、最好时间复杂度最坏时间复杂度、空间复杂度的理解,以常见的排序算法为例,分析其时间和空间复杂度。 1 冒泡排序 平均时间复杂度O(n^2) 最坏时间复杂度O(n^2) 最好时间复杂度是...
  • 12种排序时间复杂度稳定性: 计数排序 基数排序 冒泡 插入 折半插入 归并 锦标赛 快速 希尔 桶排序 选择排序排序
  • 1》归并排序的步骤如下:  Divide: 把长度为n的输入序列分成两个长度为n/2的子序列。  Conquer: 对这两个子序列...2》时间复杂度:  这是一个递推公式(Recurrence),我们需要消去等号右侧的T(n),把T(n)写

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,931
精华内容 9,172
关键字:

归并排序的时间复杂度最坏