算法时间复杂度比较

2022-03-16 本文已影响0人 spyn_n

排序算法比较

排序算法	平均时间	最差情形	稳定度	额外空间	备注
冒泡	O(n²)	O(n²)	稳定	O(1)	n小的时候较好
交换	O(n²)	O(n²)	不稳定	O(1)	n小的时候较好
选择	O(n²)	O(n²)	不稳定	O(1)	n小的时候较好
插入	O(n²)	O(n²)	稳定	O(1)	大部分已排序时较好
基数	O( $log_R{B}$ )	O( $log_R{B}$ )	稳定	O(1)	R是基数，B是真数
shell	O( $n*log{n}$ )	O(n^s) 1<s<2	不稳定	O(1)	s是所选分组
快速	O( $n*log{n}$ )	O(n²)	不稳定	O( $n*log{n}$ )	n大时较好
归并	O( $n*log{n}$ )	O( $n*log{n}$ )	稳定	O(1)	n大时较好
堆	O( $n*log{n}$ )	O( $n*log{n}$ )	不稳定	O(1)	n大时较好

其他

算法	平均时间
哈希	O(1)
二分查找	O( $log_2{n}$ )
二叉搜索树	O( $log_2{n}$ )
线性，遍历	O(n)

算法时间复杂度数排序依次：
常数阶O(1) < 对数阶O( $log_2{n}$ ) < 线性阶O(n) < 线性对数阶O(n* $log_2{n}$ ) < 平方阶O(n²) < 立方阶O(n³) < k次方阶O(n^k) < 指数阶O(2ⁿ).......

上一篇下一篇

猜你喜欢

热点阅读