常见排序算法时间复杂度和空间复杂度_n个数排序的时间复杂度

作者：小小林熬夜学编程 | 2024-03-16 19:23:07

踩

n个数排序的时间复杂度

在这里插入图片描述

快速排序时间复杂度：

可以看这个视频视频
https://www.bilibili.com/video/BV1xb411T7dN?spm_id_from=333.337.search-card.all.click

N个数据
第1次分成2组=2^1
第2次分成4组=2^2
第3次分成8组=2^3
…
第t次分成 2^t 组，完成所有数据的排序
所以2^t = N
所以 t = log2N 也就是logN ，也就是空间复杂度为 logN
在每一次排序里，又遍历了所有数据，所以每一次的时间复杂度是 N
所以，快速排序总的平均时间复杂度是 o(NlogN)
在这里插入图片描述
最坏的情况：
已经正序或者逆序排好了顺序，那么第一次要排N 个数，第二次 N-1 个，第三次 N-2 个，构成一个等差数列，所以时间复杂度为 (a1+an)*N/2=(N+1)*N/2 ≈ N^2
所以时间复杂的最差为 o(N^2)

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/251553