我试图列出常见数据结构的操作的时间复杂性,如数组、二进制搜索树、堆、链表等,特别是我指的是Java。它们很常见,但我猜我们中的一些人对确切的答案并不是百分之百有信心。任何帮助,特别是参考资料,我们都非常感谢。
例如,对于单链表:改变一个内部元素是O(1)。你怎么能做到呢?在更改元素之前,必须先搜索该元素。此外,对于Vector,添加内部元素的形式为O(n)。但是为什么我们不能使用索引在分期固定的时间内完成呢?如果我遗漏了什么,请纠正我。
我把我的发现/猜测作为第一个答案。
发布于 2021-10-24 16:36:30
Baeldung在这里指出了ArrayList、LinkedList和CopyOnWriteArrayList的一些时间复杂性:https://www.baeldung.com/java-collections-complexity和地图实现在这里:https://www.baeldung.com/java-hashmap
他还添加了基准,以突出实现之间的差异。
https://stackoverflow.com/questions/7294634
复制相似问题