赞
踩
排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
---|---|---|---|---|---|---|
冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | In-place | 稳定 |
简单选择 | O(n²) | O(n²) | O(n²) | O(1) | In-place | 不稳定 |
直接插入 | O(n²) | O(n) | O(n²) | O(1) | In-place | 稳定 |
希尔排序 | O(nlogn) | O(nlog²n) | O(nlog²n) | O(1) | In-place | 不稳定 |
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | Out-place | 稳定 |
快速排序 | O(nlogn) | O(nlogn) | O(n²) | O(logn) | In-place | 不稳定 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | In-place | 不稳定 |
计数排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | Out-place | 稳定 |
桶排序 | O(n + k) | O(n + k) | O(n²) | O(n + k) | Out-place | 稳定 |
基数排序 | O(n * k) | O(n * k) | O(n * k) | O(n + k) | Out-place | 稳定 |
2.1、度量一个程序执行时间的两种方法
2.2、时间频度
2.3、时间复杂度
2.4、平均时间复杂度和最坏时间复杂度
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下,该算法的运行时间。
最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂
度。这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限,这就保证了算法的运行时间不会比最坏情况更长。
平均时间复杂度和最坏时间复杂度是否一致,和算法有关
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。