不同数据结构的时间复杂性
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和 链接的区别
相关内容
热门资讯
500 行 Python 代码...
语法分析器描述了一个句子的语法结构，用来帮助其他的应用进行推理。自然语言引入了很多意外的歧义，以我们...
定时清理删除C:\Progra...
C:\Program Files (x86)下面很多scoped_dir开头的文件夹 写个批处理 定...
65536是2的几次方 计算2...
65536是2的16次方：65536=2⁶
65536是256的2次方：65536=256
6553...
Mobi、epub格式电子书如...
在wps里全局设置里有一个文件关联，打开，勾选电子书文件选项就可以了。
scoped_dir32_70...
一台虚拟机C盘总是莫名奇妙的空间用完，导致很多软件没法再运行。经过仔细检查发现是C:\Program...
小程序支付时提示：appid和...
[Q]小程序支付时提示：appid和mch_id不匹配
[A]小程序和微信支付没有进行关联，访问“小...
pycparser 是一个用...
`pycparser` 是一个用 Python 编写的 C 语言解析器。它可以用来解析 C 代码并构...
微信小程序使用slider实现...
众所周知哈，微信小程序里面的音频播放是没有进度条的，但最近有个项目呢，客户要求音频要有进度条控制，所...
python查找阿姆斯特朗数
题目解释
如果一个n位正整数等于其各位数字的n次方之和,则称该数为阿姆斯特朗数。 例如1^3 + 5...
Apache Doris 2....
亲爱的社区小伙伴们，我们很高兴地向大家宣布，Apache Doris 2.0.0 版本已于...