算法复杂度

大O记法

数据结构 查找 平均/最坏 插入 平均/最坏 删除 平均/最坏 遍历
数组 O(N)/O(N) O(N)/O(N) O(N)/O(N) ~~
有序数组 O(logN)/O(N) O(N)/O(N) O(N)/O(N) O(N)
链表 O(N)/O(N) O(1)/O(1) O(1)/O(1) ~~
有序链表 O(N)/O(N) O(N)/O(N) O(1)/O(1) O(N)
二叉查找树 O(logN)/O(N) O(logN)/O(N) O(logN)/O(N) O(N)
红黑树 O(logN)/O(logN) O(logN)/O(logN) O(logN)/O(logN) O(N)
平衡树 O(logN)/O(logN) O(logN)/O(logN) O(logN)/O(logN) O(N)
二叉堆/优先队列 O(1)/O(1) O(logN)/O(logN) O(logN)/O(logN) O(N)
哈希表 O(1)/O(1) O(1)/O(1) O(1)/O(1) O(N)


BigO