java - 从 ArrayDeque 获取元素的时间复杂度
问题描述
我在某些地方读到,Java 中的 LinkedList 添加和删除元素的时间复杂度为 O(1),而获取元素的时间复杂度为 O(n)。并且 ArrayList 有 O(1) 来获取元素和 O(n) 来添加和删除。
我有一个程序,它必须执行许多涉及从列表中插入和恢复元素的操作。所以,我想知道 ArrayDeque 访问元素的时间是否类似于 ArrayList。
解决方案
从javadoc,它是这样写的,
Most ArrayDeque operations run in amortized constant time. Exceptions include remove,
removeFirstOccurrence, removeLastOccurrence, contains, iterator.remove(), and the bulk
operations, all of which run in linear time.
所以,移除一个元素是线性时间运算,得到它应该是 O(1)。
编辑:
摊销恒定时间操作意味着大部分时间操作成本将为 O(1),除非在某些情况下可能,例如。当需要调整 ArrayDeque 的大小时。ArrayDeque 的 javadoc 还说,
Array deques have no capacity restrictions; they grow as necessary to support usage
因此,每当向 ArrayDeque 的末尾或开头添加新元素时,其大小都会发生变化 -> 因此,如果元素总数违反了 ArrayDeque 的容量属性,则需要调整其大小,这可能高于 O(1 )。但是如果你做很多这样的操作并平均时间复杂度,它将非常接近 O(1)。
推荐阅读
- c# - 随机范围返回两个数字而不是一个
- azure-language-understanding - 有人在 MS QnA 制造商上看到 CORS 问题吗?
- html - 当我改变窗口大小时,我的页面不断改变它的外观
- node.js - 使用 joi 验证节点中发布的数据
- python - 在 pygame 中使用颜色查找表
- android - 将数据从 Recycler View Adapter 发送到 BroadcastReciever
- laravel - Laravel 数据库队列频率
- java - 未使用的类未打包在 Maven 多模块项目中
- javascript - React i18next - 从 API 获取语言首选项并根据获取的首选项初始化 i18n
- typescript - 在函数类型中使用泛型