数据结构与算法
算法复杂度
大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) |