详谈归并排序时间复杂度过程推导----软考

你的名字 2022-02-12 16:21 199阅读 0赞

归并排序方法就是把一组n个数的序列，折半分为两个序列，然后再将这两个序列再分，一直分下去，直到分为n个长度为1的序列。然后两两按大小归并。如此反复，直到最后形成包含n个数的一个数组。

归并排序总时间=分解时间+子序列排好序时间+合并时间

无论每个序列有多少数都是折中分解，所以分解时间是个常数，可以忽略不计。

则：归并排序总时间=子序列排好序时间+合并时间

--------------------

如果假设一个序列有n个数的排序时间为T(n)，T(n)是一个关于n的函数，随着n的变化而变化。

**那么我们将n个数的序列，分为两个(n/2)的序列。**

![20190429110939184.png][]

那么T(n)=2\*T(n/2)+合并时间

由于合并时，两个子序列已经组内排好序了，那我们将两个排好序的序列组合成一个大的有序序列，只需要一个if循环即可。if循环中有n个数需要比较，所以时间复杂度为n。

那么T(n)=2\*T(n/2)+n

**我们再将两个n/2个序列再分成4个(n/4)的序列。**

![20190429111349924.png][]

一个（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)的序列。**

![20190429111757388.png][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW5namlhYmFvNTU1NQ_size_16_color_FFFFFF_t_70][]

大家有没有找到规律，右边式子中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

[20190429110939184.png]: /images/20220212/784fed5a2fd34221ab2f5387f0b49088.png
[20190429111349924.png]: /images/20220212/8d37fa27b9a74e809824daf88d2f5e89.png
[20190429111757388.png]: /images/20220212/d2f7a51d857f458d9b323e7065190c9c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW5namlhYmFvNTU1NQ_size_16_color_FFFFFF_t_70]: /images/20220212/42e959eb8a764c408c78f351999906e8.png

发表评论取消回复

表情：

评论列表（有 0 条评论，199人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构】详谈复杂度

目录 1.前言 2.什么是复杂度 3.如何计算时间复杂度 1.引例 2.二分查找 3.常见的复杂度 4.如何计算空间复杂度 5.关于递归 6.总结 -

谁借莪１个温暖的怀抱￠/ 2024年03月27日 09:05/ 0 赞/ 89 阅读

相关排序算法分类排序算法时间复杂度、空间复杂度、稳定性

排序算法比较表格 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4u

你的名字/ 2024年02月19日 20:34/ 0 赞/ 84 阅读

相关快速排序和归并排序及他们的时间复杂度

时间复杂度时间复杂度是算法分析中用来衡量算法执行时间与输入规模之间关系的一种度量方式。它表示算法的运行时间随着输入规模的增长而增长的趋势。时间复杂度通常使用大O

秒速五厘米/ 2023年10月13日 08:11/ 0 赞/ 65 阅读

相关 [时间复杂度]-排序算法的时间复杂度

我们经常可以看到这样的描述：软件=数据结构+算法，可见算法基础对于一个程序员的重要性。算法中，有两个基本概念：时间复杂度和空间复杂度。时间复杂度：描述算法执行消耗的时

今天药忘吃喽~/ 2023年09月24日 14:38/ 0 赞/ 107 阅读

相关排序算法：时间复杂度和空间复杂度

1，常见的排序分类排序算法分为内部排序和外部排序两种，内部排序是完全在内存中完成，外部排序需要使用外部介质，如硬盘，中间件等，此次排序算法只考虑内部排序内

绝地灬酷狼/ 2023年02月27日 13:58/ 0 赞/ 176 阅读

相关归并排序时间复杂度----主定理

http://blog.csdn.net/touch\_2011/article/details/6785881 1、序言 > 这是《漫谈经典排序[算法][Link 1

忘是亡心i/ 2022年09月25日 12:18/ 0 赞/ 168 阅读

相关归并排序算法、时间复杂度和稳定性

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

客官°小女子只卖身不卖艺/ 2022年05月17日 06:17/ 0 赞/ 230 阅读

相关详谈直接插入排序、冒泡排序时间复杂度过程推导----软考

想了解时间复杂度首先要将排序过程弄懂。直接插入排序首先有一组n个数的数组。我们进行升序排列。先选前两个数进行比较，进行升序排列组成一个有序序列。然后每次从数组后

水深无声/ 2022年02月13日 18:28/ 0 赞/ 152 阅读

相关详谈归并排序时间复杂度过程推导----软考

归并排序方法就是把一组n个数的序列，折半分为两个序列，然后再将这两个序列再分，一直分下去，直到分为n个长度为1的序列。然后两两按大小归并。如此反复，直到最后形成包含n个数的一个

你的名字/ 2022年02月12日 16:21/ 0 赞/ 200 阅读

相关排序算法之时间复杂度、空间复杂度

<table> <thead> <tr> <th>排序算法</th> <th>最好时间</th> <th>平均时间</th> <th>

￡神魔★判官ぃ/ 2021年09月18日 04:22/ 0 赞/ 551 阅读