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

    万次阅读 多人点赞 2019-03-19 18:04:57
    归并排序时间复杂度分析归并排序工作原理时间复杂度计算如何插入一段漂亮的代码片KaTeX数学公式 归并排序 归并排序也叫(Merge sort)。 工作原理 将给定的数组一份为二 对两部分数组再使用归并排序使其有序 最后再...

    归并排序时间复杂度分析

    归并排序

    归并排序也叫(Merge sort)。

    工作原理

    1. 将给定的数组一份为二
    2. 对两部分数组再使用归并排序使其有序
    3. 最后再将两部分数组合并

    时间复杂度计算

    1、首先可知

    f ( n ) = 2 f ( n 2 ) + n           f(n)=2f(\frac{n}{2})+n \space\space\space\space\space\space\space\space\space f(n)=2f(2n)+n         
    其中: f ( n ) 表 示 对 n 个 数 进 行 归 并 排 序 f(n)表示对n个数进行归并排序 f(n)n 2 f ( n 2 ) 表 示 将 n 个 数 分 成 两 部 分 分 别 进 行 归 并 排 序 2f(\frac{n}{2})表示将n个数分成两部分分别进行归并排序 2f(2n)n n 表 示 对 两 个 子 过 程 结 束 之 后 合 并 的 过 程 n表示对两个子过程结束之后合并的过程 n
    2、推导
    f ( n 2 ) = 2 f ( n 4 ) + n 2           当 n = n 2 时 f(\frac{n}{2})=2f(\frac{n}{4})+\frac{n}{2} \space\space\space\space\space\space\space\space\space 当n=\frac{n}{2}时 f(2n)=2f(4n)+2n         n=2n
    f ( n 4 ) = 2 f ( n 8 ) + n 4           当 n = n 4 时 f(\frac{n}{4})=2f(\frac{n}{8})+\frac{n}{4} \space\space\space\space\space\space\space\space\space 当n=\frac{n}{4}时 f(4n)=2f(8n)+4n         n=4n
    … …           …… \space\space\space\space\space\space\space\space\space          
    f ( n 2 m − 1 ) = 2 f ( n 2 m ) + n 2 m − 1           当 n = n 2 m − 1 时 f(\frac{n}{2^{m-1}})=2f(\frac{n}{2^m})+\frac{n}{2^{m-1}} \space\space\space\space\space\space\space\space\space 当n=\frac{n}{2^{m-1}}时 f(2m1n)=2f(2mn)+2m1n         n=2m1n
    3、由此可得:

    f ( n ) = 2 f ( n 2 ) + n f(n)=2f(\frac{n}{2})+n f(n)=2f(2n)+n
    = 2 × ( 2 f ( n 4 ) + n 2 ) + n = 2\times\bigg(2f(\frac{n}{4})+\frac{n}{2}\bigg)+n =2×(2f(4n)+2n)+n
    = 2 2 f ( n 2 2 ) + 2 n =2^2f(\frac{n}{2^2})+2n =22f(22n)+2n
    = 2 2 × ( 2 f ( n 8 ) + n 4 ) + 2 n =2^2\times\bigg(2f(\frac{n}{8})+\frac{n}{4}\bigg)+2n =22×(2f(8n)+4n)+2n
    = 2 3 f ( n 2 3 ) + 3 n =2^3f(\frac{n}{2^3})+3n =23f(23n)+3n
    … … ……
    = 2 m f ( n 2 m ) + m n =2^mf(\frac{n}{2^m})+mn =2mf(2mn)+mn

    当 m 足够大时(仅剩一个数字时),可使得 n 2 m = 1 \frac{n}{2^m}=1 2mn=1
    求出 m = l o g 2 n m=log_2n m=log2n

    代 入    f ( n ) = 2 m f ( n 2 m ) + m n    中 可 得 代入 \space\space f(n)=2^mf(\frac{n}{2^m})+mn \space\space 中可得   f(n)=2mf(2mn)+mn  
    f ( n ) = 2 ( l o g 2 n ) f ( 1 ) + n ⋅ l o g 2 n f(n)=2^{(log_2n)}f(1)+n\cdot log_2n f(n)=2(log2n)f(1)+nlog2n
    其 中    f ( 1 ) = 0 其中\space\space f(1)=0   f(1)=0
    所 以 最 终    f ( n ) = n ⋅ l o g 2 n 所以最终\space\space f(n)=n\cdot log_2n   f(n)=nlog2n

    展开全文
  • 归并排序时间复杂度

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

    最好,最坏,评价时间复杂度都是  nlogn

    空间复杂度是  O(n)

     

     

    比较占内存,但是效率高且稳定

    转载于:https://www.cnblogs.com/wust221/p/5414828.html

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

    万次阅读 多人点赞 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

    展开全文
  • 归并排序时间复杂度推导

    千次阅读 2017-03-22 16:36:00
    众所周知,归并排序时间复杂度是O(N*lgN) 归并排序时间复杂度推导书上网上一抓一把,但是多数证明都是基于N=2k这个假设来证明的,下面我给出一般情况的证明。 先上归并排序代码: public class MergeSort ...

    众所周知,归并排序的时间复杂度是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

    展开全文
  • 归并排序算法 设置归并排序所化时间为 T(N)T(N)T(N),其中 NNN 为输入数据长度 ...4、归并排序好的左边和右边元素,时间复杂度 θ(N)\theta(N)θ(N) 设置归并排序所化时间为 T(N)T(N)T(N),其中 NNN 为输入
  • 今天讲讲,为什么归并排序时间复杂度是θ(nlgn) 我们知道归并排序是利用 递归函数 进行计算的一种分治排序算法,因此对其时间复杂度也可以用递归的方式进行计算。 首先我们要知道分治算法的流程: 分解、计算(将...
  • 详谈归并排序时间复杂度过程推导----软考

    千次阅读 多人点赞 2019-04-29 11:57:24
    归并排序时间=分解时间+子序列排好序时间+合并时间 无论每个序列有多少数都是折中分解,所以分解时间是个常数,可以忽略不计。 则:归并排序时间=子序列排好序时间+合并时间 如果假设一个序列有n个数的排序...
  • 归并排序时间复杂度----主定理

    万次阅读 2016-09-09 12:09:30
    这是《漫谈经典排序算法系列》第四篇,解析了归并排序。  各种排序算法的解析请参考如下: 《漫谈经典排序算法:一、从简单选择排序到堆排序的深度解析》 《漫谈经典排序算法:二、各种插入排序解析及性能...
  • T(n)=2T(n/2)+O(n),n=2^k。 想知道为什么最终答案为O(nlgn) Master大法好。这题自己推导也不难。把递推公式重复代入三次并化简:   ...可以看出规律了,而且很容易用归纳法证明。... ...
  • 归并排序及其复杂度分析

    千次阅读 2018-04-19 20:42:27
    /* * (二分)归并排序(稳定算法) * 基本思想:将数组递归分成越来越小的数集,直到每个数集只有一个数 ...* 空间复杂度分析:归并排序需要一个临时temp[]来储存归并的结果,所以 O(n) * * 基本...
  • 文章目录1. 基本思想2. 代码实现2.1 递归实现2.2 优化—非递归实现3...归并排序与快速排序的思想基本一致,唯一不同的是归并排序的基准值是数组的中间元素 快排 Link:[排序算法] 6. 快速排序多种递归、非递归实现及性能
  • 上篇文章中我们对归并排序时间复杂度使用递归树法进行了简答的分析,并得出了结果归并排序时间复杂度为,这里将使用代换法再进行一次分析。使用代换法解递归式的时候,主要的步骤有两步: 1)猜测解的结果 2...
  • 4.利用Master Theorem求归并排序时间复杂度 我们上一篇博客重点回顾了复杂度的概念,以及基本的复杂度计算方法。这篇博客我们利用归并排序Merge Sort算法带着大家深入计算复杂度。 1.归并排序概念 假设我们有一...
  • 通过图解分析归并排序流程,以及使用Master公式计算时间复杂度
  • 根号n段归并排序算法时间复杂度分析过程: 1.合并 根号n向下取整 段子数组使用的是自底向上两两归并的策略 2.根号n段归并排序算法时间复杂度的数学推导
  • 引言: 算法是计算机科学中的基础,程序=算法+数据结构,算法描述了我们将如何来处理数据的过程。本文将介绍两种算法的实现以及其中一种算法的复杂度分析过程。
  • 前两篇文章中分别是要用递归树、代换法对归并排序时间复杂度进行了简单的分析和证明,经过两次分析后,我们发现递归树法的特点是:可以很直观的反映出整个归并排序算法的各个过程,但因为要画出递归树所以比较麻烦...
  • 现在我们就借助归并排序来看看,如何用递归树,来分析递归代码的时间复杂度归并排序每次会将数据规模一分为二。我们把归并排序画成递归树,就是下面这个样子: 因为每次分解都是一分为二,所以代价很低,我们把...
  • 归并排序空间复杂度O(1)的实现

    千次阅读 2016-06-27 22:29:39
    正常的归并排序是利用分治法,即分解,解决,合并/* tmp_array[]:辅助数组。 left_pos:数组左半部分的游标 left_end:左边数组的右界限 */ void Merge(int array[], int tmp_array[], int left_pos, int right_pos...
  • 前面对算法分析的一些常用的 渐进符号 做了简单的描述,这里将使用归并排序算法做为一个实战演练。 这里首先假设读者对归并排序已经有了简单的了解(如果不了解的同学可以自行百度下归并排序的原理)。了解此算法...
  • 归并排序是建立在归并操作上的一种有效排序算法,该算法是采用分治法的一个典型应用。 这里的分治如何理解? 比如我们要统计本县城的高考状元,而一个县城中有很多中学,每个中学又有若干个班级,每个班级有若干名...
  • 两个重要的排序算法的时间复杂度比较。所用的代码比较简陋,使用控制台。
  • 排序算法之 归并排序 及其时间复杂度和空间复杂度 在排序算法中快速排序的效率是非常高的,但是还有种排序算法的效率可以与之媲美,那就是归并排序归并排序和快速排序有那么点异曲同工之妙,快速排序:是先...
  • 快排和归排的复杂度都是O(n*log n),为什么都用快排而...我们平时考虑时间复杂度的时候并不考虑常量的影响,但有时候常量的影响不可忽略,比如在这个问题上。但是大多数时候考虑复杂度的时候,可能还是不需要考虑...
  • 归并排序,其实就是递归+合并。
  • 排序大体分为两类:比较排序和非比较排序一 各个排序的基本实现1.直接插入排序和希尔排序//整体思路:往一段有序区间插入元素,end标记为有序区间的最后一个元素下标,要插入的元素下标为end+1此处就称tmp,先把他...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 63,344
精华内容 25,337
关键字:

归并排序时间复杂度