当前栏目
快速排序&归并排序—时间复杂度分析
引言:
大家好,我是小星星,今天要梳理的知识点是——快速排序和归并排序时间复杂度分析。
一、快排时间复杂度分析
快速排序的时间复杂度在O(nlogn)~ O(n^2)之间,下面我分别分析这两种情况:
(一)快速排序的最好情况O(nlogn)
快速排序的实现方式,就是在当前区间中选择一个x,区间中所有比x小的数都需要放到x的左边,而比x大的数则放到右边。在理想的情况下,我们选取的分界点刚好就是这个区间的中位数。也就是说,在操作之后,正好将区间分成了满足数字个数相等的左右两个子区间(快排是按照值的大小划分,个数可能相等,可能不等)。此时就和归并排序基本一致了:
递归的第一层,n个数被划分为2个子区间,每个子区间的数字个数为n/2;
递归的第二层,n个数被划分为4个子区间,每个子区间的数字个数为n/4;
递归的第三层,n个数被划分为8个子区间,每个子区间的数字个数为n/8;
…
递归的第logn层,n个数被划分为n个子区间,每个子区间的数字个数为1;
以上过程与归并排序基本一致,而区别就是,归并排序是从最后一层开始进行merge操作,自底向上;而快速排序则从第一层开始交换区间中数字的位置,是自顶向下的。但是,merge操作和快速排序的调换位置操作,时间复杂度是一样的,对于每一个区间,处理的时候,都需要遍历一次区间中的每一个元素。这也就意味着,快速排序和归并排序一样,每一层的总时间复杂度都是O(n),因为需要对每一个元素遍历一次。而且在最好的情况下,同样也是有logn层,所以快速排序最好的时间复杂度为O(nlogn)。
(二)快速排序的最坏情况O(n^2)
对于每一个区间,我们在处理的时候,选取的轴刚好就是这个区间的最大值或者最小值。比如我们需要对n个数排序,而每一次进行处理的时候,选取的轴刚好都是区间的最小值。于是第一次操作,在经过调换元素顺序的操作后,最小值被放在了第一个位置,剩余n-1个数占据了2~n个位置;第二次操作,处理剩下的n-1个元素,又将这个子区间的最小值放在了当前区间的第1个位置,以此类推…每次操作,都只能将最小值放到第一个位置,而剩下的元素,则没有任何变化。所以对于n个数来说,需要操作n次即n层,才能为n个数排好序。而每一次操作都需要遍历一次剩下的所有元素,这个操作的时间复杂度是O(n),所以总时间复杂度为O(n^2)。
其实上面的过程,我们可以换一个角度理解:每次操作,找出最小值放到剩余区间的第一个位置,这不就是选择排序的实现方式吗?而选择排序的时间复杂度就是O(n ^ 2),所以上面的过程也就O(n^2)。
二、归并排序时间复杂度分析
归并排序的时间复杂度是O(nlogn),且这个时间复杂度是稳定的,不随需要排序的序列不同而产生波动。下面我来分析一下~
假设我们需要对一个包含n个数的序列使用归并排序,并且使用的是递归的实现方式,那么过程如下:
递归的第一层,将n个数划分为2个子区间,每个子区间的数字个数为n/2;
递归的第二层,将n个数划分为4个子区间,每个子区间的数字个数为n/4;
递归的第三层,将n个数划分为8个子区间,每个子区间的数字个数为n/8;
…
递归的第logn层,将n个数划分为n个子区间,每个子区间的数字个数为1;
在整个归并排序的过程中,每一层的子区间,长度都是上一层的1/2。分析可知,当子区间的长度为1时,共划分了logn层。而归并排序的merge操作,则是从最底层开始(子区间为1的层),对相邻的两个子区间进行合并,过程如下:
在第logn层(最底层),每个子区间的长度为1,共n个子区间,每相邻两个子区间进行合并,总共合并n/2次。n个数字都会被遍历一次,所有这一层的总时间复杂度为O(n);
…
在第2层,每个子区间长度为n/4,总共有4个子区间,每相邻两个子区间进行合并,总共合并2次。n个数字都会被遍历一次,所以这一层的总时间复杂度为O(n);
在第1层,每个子区间长度为n/2,总共有2个子区间,只需要合并一次。n个数字都会被遍历一次,所以这一层的总时间复杂度为O(n);
通过上面的过程我们可以发现,对于每一层来说,在合并所有子区间的过程中,n个元素都会被操作一次,所以每一层的时间复杂度都是O(n),共有logn层,所以归并排序的时间复杂度就是O(nlogn)。
三、写在最后
学习算法的重点是学习编程思维,这件事值得我们慢慢去做,做很久很久。漫漫长路,感谢有你~
如果各位大佬发现哪里有问题的话,欢迎指出~
如果你觉得我这篇文章对你有帮助的话,欢迎你订阅我的算法专栏并给我三连关注支持一下~,你们的支持是我更新的动力,感谢各位!
相关文章
- 前端面试 【JavaScript】— typeof 是否能正确判断类型?
- 前端面试 【JavaScript】— instanceof 能否判断基本数据类型?
- 前端面试 【JavaScript】— 能不能手动实现一下 instanceof 的功能?
- 前端面试 【JavaScript】— Object.is和=== 有什么区别?
- 前端面试 【JavaScript】— JS中类型转换有哪几种?
- 前端面试 【JavaScript】— == 和 ===有什么区别?
- 前端面试 【JavaScript】— 对象转原始类型是根据什么流程运行的?
- JavaScript 的 parseInt() 函数
- javascript实现两个数字进行组合
- JS监听键盘按键
- 大前端开发中的路由管理之五:Flutter篇
- Javascript的DOM操作
- 在Vue项目中使用WebSocket技术
- 新手向:前端程序员必学基本技能——调试JS代码
- React 毁了 Web 开发!
- 「JS 逆向百例」cnki 学术翻译 AES 加密分析
- 商标注册域名后缀用什么?商标和域名有哪些区别?
- 网站建设流程是怎样的?需要看重哪些细节?
- 网站域名商标注册流程是什么?网站域名商标有什么用?
- 如何建设一个实用性强的网站 网站上线后如何运营