极客教程不同数据结构的时间复杂性
时间复杂度是计算机科学中的一个概念，它涉及一组代码或算法处理或运行所需时间的量化，是输入量的函数。换句话说，时间复杂度是指一个程序处理一个给定的输入需要多长时间。一个算法的效率取决于两个参数：
- 时间复杂度：它被定义为一个特定指令集的执行次数，而不是所花的总时间。这是因为总时间也取决于一些外部因素，如使用的编译器、处理器的速度等。
- 空间复杂度：它是程序执行所需的总内存空间。
不同数据结构在不同操作中的最佳时间复杂性
| 数据结构 | 访问 | 搜索 | 插入 | 删除 |
|---|---|---|---|---|
| 阵列 | O(1) | O(1) | O(1) | O(1) |
| 堆栈 | O(1) | O(1) | O(1) | O(1) |
| 队列 | O(1) | O(1) | O(1) | O(1) |
| 单链表 | O(1) | O(1) | O(1) | O(1) |
| 双链表 | O(1) | O(1) | O(1) | O(1) |
| 哈希表 | O(1) | O(1) O(1) | O(1) | |
| 二进制搜索树 | O(log n) | O(log n) | O(log n) | O(log n) |
| AVL树 | O(log n) | O(log n) | O(log n) | O(log n) |
| B树 | O(log n) | O(log n) | O(log n) | O(log n) |
| 红黑树 | O(log n) | O(log n) | O(log n) | O(log n) |
不同数据结构对不同操作的最坏情况下的时间复杂度
| 数据结构 | 访问 | 搜索 | 插入 | 删除 |
|---|---|---|---|---|
| 阵列 | O(1) | O(N) | O(N) | O(N) |
| 堆栈 | O(N) | O(N) | O(1) | O(1) |
| 队列 | O(N) | O(N) | O(1) | O(1) |
| 单链表 | O(N) | O(N) | O(N) | O(N) |
| 双链表 | O(N) | O(N) | O(1) | O(1) |
| 哈希表 | O(N) | O(N) | O(N) | O(N) |
| 二进制搜索树 | O(N) | O(N) | O(N) | O(N) |
| AVL树 | O(log N) | O(log N) | O(log N) | O(log N) |
| 二进制树 | O(N) | O(N) | O(N) | O(N) |
| 红黑树 | O(log N) | O(log N) | O(log N) | O(log N) |
不同数据结构对不同操作的平均时间复杂度
| 数据结构 | 访问 | 搜索 | 插入 | 删除 |
|---|---|---|---|---|
| 阵列 | O(1) | O(N) | O(N) | O(N) |
| 堆栈 | O(N) | O(N) | O(1) | O(1) |
| 队列 | O(N) | O(N) | O(1) | O(1) |
| 单链表 | O(N) | O(N) | O(1) | O(1) |
| 双链表 | O(N) | O(N) | O(1) | O(1) |
| 哈希表 | O(1) | O(1) | O(1) | O(1) |
| 二进制搜索树 | O(log N) | O(log N) | O(log N) | O(log N) |
| AVL树 | O(log N) | O(log N) | O(log N) | O(log N) |
| B树 | O(log N) | O(log N) | O(log N) | O(log N) |
| 红黑树 | O(log N) | O(log N) | O(log N) | O(log N) |