常用排序算法时间复杂度和空间复杂度

算法 最差时间分析 平均时间复杂度 稳定度 空间复杂度
冒泡排序 O(n2) O(n2) 稳定 O(1)
插入排序 O(n2) O(n2) 稳定 O(1)
选择排序 O(n2) O(n2) 不稳定 O(1)
二叉树排序 O(n2) O(n*log2n) 不一定 O(n)
快速排序 O(n2) O(n*log2n) 不稳定 O(log2n)~O(n)
堆排序 O(n*log2n) O(n*log2n) 稳定度 O(1)
希尔排序 O O 不稳定 O(1)
归并排序 O O(n log n) 稳定 O(n)

常用查找算法时间复杂度和空间复杂度

算法 时间复杂度 描述
顺序查找 O(n) 存储结构为顺序存储或链接存储的线性表
二分查找 O(log2n) 元素必须是有序的,如果是无序的则要先进行排序
插值查找 O(log2(log2n)) 适用表长较大,关键字分布比较均匀的表
斐波那契查找 O(log2n) 要求开始表中记录的个数为某个斐波那契数小1,及n=F(k)-1
二叉查找树 O(logn) 最坏O(n)
分块查找 O(logn) 无序或有序队列
哈希查找 O(1)

算法的复杂度通常具有多种形式,按照数量级递增排序,依次是:

常数阶:O(1)
对数阶:O(log2n)
线性阶:O(n)
线性对数阶:O(nlog2n)
平方阶:O(n^2) ,立方阶:O(n^3) 。。。k次方阶:O(n^k)
指数阶:O(2n)
阶乘阶:O(n!)

参考文章:

发表评论

电子邮件地址不会被公开。 必填项已用*标注