复杂度

算法复杂度

在数据结构与算法的学习中，我们最常见的就是用大O符号来描述算法的复杂度。

算法复杂度变化

以下是一些最常用的大O标记法列表以及它们与不同大小输入数据的性能比较。

大O标记法 计算10个元素 计算100个元素 计算1000个元素
O(1) 1 1 1
O(log N) 3 6 9
O(N) 10 100 1000
O(N log N) 30 600 9000
O(N^2) 100 10000 1000000
O(2^N) 1024 1.26e+29 1.07e+301
O(N!) 3628800 9.3e+157 4.02e+2567

数据结构操作的复杂性

数据结构 连接 查找 插入 删除 备注
数组 1 n n n
栈 n n 1 1
队列 n n 1 1
链表 n n 1 1
哈希表 - n n n 在完全哈希函数情况下，复杂度是O(1）
二分查找树 n n n n 在平衡树情况下，复杂度是O(log(n))
B树 log(n) log(n) log(n) log(n)
红黑树 log(n) log(n) log(n) log(n)
AVL树 log(n) log(n) log(n) log(n)
布隆过滤器 - 1 1 - 存在一定概率的判断错误（误判成存在）

数组排序算法的复杂性

名称 最优 平均 最坏 内存 稳定 备注
冒泡排序 n n^2 n^2 1 Yes
插入排序 n n^2 n^2 1 Yes
选择排序 n^2 n^2 n^2 1 No
堆排序 n log(n) n log(n) n log(n) 1 No
归并排序 n log(n) n log(n) n log(n) n Yes
快速排序 n log(n) n log(n) n^2 log(n) No 在in-place版本下，内存复杂度通常是O(log(n))
希尔排序 n log(n) 取决于差距序列 n (log(n))^2 1 No
计数排序 n + r n + r n + r n + r Yes r -数组里最大的数
基数排序 n * k n * k n * k n + k Yes k -最长key的升序

图操作

堆操作

最近更新于0001-01-01