我是一名计算机科学专业的学生,正在学习 Java 集合。 在我的学校,我们收到了一张图表,其中包含数据结构上不同操作的时间复杂度。图表中的一些内容对我来说没有意义。
链接列表 它说在末尾插入和查找元素数量的时间复杂度取决于实现。这是为什么?为什么不是 O(n)?
HashMap 对于 HashMap,它表示用于查找元素数量或确定 hashMap 是否为空的 tc 也依赖于 tc 实现。
TreeMap 对于 TreeMap 也是如此。根据该图表,确定元素数量的操作的 tc 取决于实现。它们意味着哪种实现?
最佳答案
LinkedList 的某些实现可以保留列表中元素的数量以及指向最后一个元素的指针,以便快速尾部插入。这意味着它们的时间复杂度为 O(1),因为这是一种快速的数据访问。
对于 HashMap
和 TreeSet
的实现也可以遵循类似的推理,如果它们使用其数据结构保存元素数量的计数,那么诸如 isEmpty()
和 size()
也可以完成 O(1)。
关于java - LinkedList、HashMap、TreeSet的时间复杂度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30695150/