不同数据结构的时间复杂性

时间复杂度是计算机科学中的一个概念,它涉及一组代码或算法处理或运行所需时间的量化,是输入量的函数。换句话说,时间复杂度是指一个程序处理一个给定的输入需要多长时间。一个算法的效率取决于两个参数:

  • 时间复杂度:它被定义为一个特定指令集的执行次数,而不是所花的总时间。这是因为总时间也取决于一些外部因素,如使用的编译器、处理器的速度等。
  • 空间复杂度:它是程序执行所需的总内存空间。

不同数据结构在不同操作中的最佳时间复杂性

数据结构 访问 搜索 插入 删除
阵列 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)