快速排序的时间复杂度和空间复杂度

蔚落 2022-10-29 03:14 183阅读 0赞

我们来分析一下快速排序法的性能。

> 快速排序的时间性能取决于快速排序递归的深度，

可以用递归树来描述递归算法的执行情况。

> 如图9‐9‐7所示，它是\{50,10,90,30, 70,40,80,60,20\}在快速排序过程中的递归过程。由于我们的第一个关键字是50，正好是待排序的序列的中间值，因此递归树是平衡的，此时性能也比较好。

# ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25zamxpdmU_size_16_color_FFFFFF_t_70] #

![image-20210207223931143][]

![image-20210207224022570][]  
**空间复杂度**，

主要是递归造成的栈空间的使用，最好情况，递归树的深度为logn

其空间复杂度也就为 O(logn)，

**最坏情况**，

需要进行n‐1递归调用，其空间复杂度为O(n)，

**平均情况，**

空间复杂度也为O(logn)。

可惜的是，由于关键字的比较和交换是跳跃进行的，因此，

> 快速排序是一种不稳定的排序方法。

参考文章[https://blog.csdn.net/nsjlive/article/details/102531375][https_blog.csdn.net_nsjlive_article_details_102531375]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25zamxpdmU_size_16_color_FFFFFF_t_70]: /images/20221024/99a7426d8cc04907ba680c06d2f7d038.png
[image-20210207223931143]: /images/20221024/f2e78e41391f4a55abe740d1de3f8af7.png
[image-20210207224022570]: /images/20221024/de1c803db7524acfb3f8496457702971.png
[https_blog.csdn.net_nsjlive_article_details_102531375]: https://blog.csdn.net/nsjlive/article/details/102531375

发表评论取消回复

表情：

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

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

相关阅读

相关空间复杂度和时间复杂度

时间复杂度和空间复杂度是衡量算法性能的关键指标。时间复杂度评估算法执行时间，空间复杂度评估内存消耗。本文将深入探讨它们的概念、计算方式以及如何优化算法以提高效率。复杂度分...

朴灿烈づ我的快乐病毒、/ 2024年04月23日 15:58/ 0 赞/ 102 阅读

相关时间复杂度和空间复杂度

如何衡量一个算法的好坏呢？方法：分析算法效率。算法效率分析分为两种：第一种是时间效率，时间效率被称为时间复杂度第二种是空间效率。空间效率被称作空间复杂度。时间复杂度主要衡...

Myth丶恋晨/ 2024年04月20日 14:25/ 0 赞/ 111 阅读

相关时间复杂度和空间复杂度

目录引入：算法的好与坏渐进时间复杂度空间复杂度什么是空间复杂度？空间复杂度的计算 -------------------- 引入：算法的好与坏衡

刺骨的言语ヽ痛彻心扉/ 2023年09月25日 22:46/ 0 赞/ 90 阅读

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

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

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

相关时间复杂度和空间复杂度

先说结论：常规的代码的算法时间复杂度是有规律的:看几重循环: 一重循环则为O(n)线性阶，二重循环为O(n^2) K方阶; 二分法则为O(logn)对数阶，二分例

Dear 丶/ 2023年01月18日 04:14/ 0 赞/ 197 阅读

相关时间复杂度和空间复杂度

一、时间复杂度 1、定义若存在函数，使得当趋向无穷大时，的极限值为不等于 0 的常数，则称是的同数量级函数，记作，称为算法的渐进时间复杂度，简称时间复

浅浅的花香味﹌/ 2022年11月12日 14:59/ 0 赞/ 298 阅读

相关快速排序的时间复杂度和空间复杂度

我们来分析一下快速排序法的性能。 > 快速排序的时间性能取决于快速排序递归的深度，可以用递归树来描述递归算法的执行情况。 > 如图9‐9‐7所示，它是\{50,10,9

蔚落/ 2022年10月29日 03:14/ 0 赞/ 184 阅读

相关时间复杂度和空间复杂度

算法的时间复杂度和空间复杂度合称为算法的复杂度。 1.时间复杂度（1）时间频度一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可

秒速五厘米/ 2022年08月21日 02:27/ 0 赞/ 303 阅读

相关时间复杂度和空间复杂度

一、为什么要研究时间和空间复杂度假设计算机是无限快的并且计算机存储器是免费的的，你还有什么理由来研究算法吗？即使只是因为你还想证明你的解法会终止并以正确的答案终

灰太狼/ 2022年04月13日 08:17/ 0 赞/ 444 阅读

相关时间复杂度和空间复杂度

[https://blog.csdn.net/zxm490484080/article/details/72210501][https_blog.csdn.net_zxm490

待我称王封你为后i/ 2021年09月15日 09:46/ 0 赞/ 516 阅读