不同数据结构的时间复杂性
admin
2023-07-30 20:15:41
0次

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

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

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

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

上一篇：JVM和DVM的区别

下一篇：URL和 链接的区别

相关内容

热门资讯

Mobi、epub格式电子书如... 在wps里全局设置里有一个文件关联，打开，勾选电子书文件选项就可以了。
定时清理删除C:\Progra... C:\Program Files (x86)下面很多scoped_dir开头的文件夹 写个批处理 定...
scoped_dir32_70... 一台虚拟机C盘总是莫名奇妙的空间用完，导致很多软件没法再运行。经过仔细检查发现是C:\Program...
500 行 Python 代码... 语法分析器描述了一个句子的语法结构，用来帮助其他的应用进行推理。自然语言引入了很多意外的歧义，以我们...
小程序支付时提示：appid和... [Q]小程序支付时提示：appid和mch_id不匹配 [A]小程序和微信支付没有进行关联，访问“小...
pycparser 是一个用... `pycparser` 是一个用 Python 编写的 C 语言解析器。它可以用来解析 C 代码并构...
微信小程序使用slider实现... 众所周知哈，微信小程序里面的音频播放是没有进度条的，但最近有个项目呢，客户要求音频要有进度条控制，所...
65536是2的几次方 计算2... 65536是2的16次方：65536=2⁶ 65536是256的2次方：65536=256 6553...
Apache Doris 2.... 亲爱的社区小伙伴们，我们很高兴地向大家宣布，Apache Doris 2.0.0 版本已于...
项目管理和工程管理的区别 项目管理 项目管理，顾名思义就是专注于开发和完成项目的管理，以实现目标并满足成功标准和项目要求。 工...