我正在学习 Java 数据结构课程 atm。我的一项任务要求我选择一个我选择的数据结构并编写一个拼写检查程序。我正在检查不同数据结构的性能。
我去了treeset的api，这就是它所说的......“这个实现为基本操作（添加，删除和包含）提供了有保证的log（n）时间成本。”
这会包括 removeAll() 吗？
我怎么能解决这个问题
先感谢您
问问题
565 次
2 回答
2
它不包括 removeAll()，但我不得不不同意 polkageist 的回答。根据实现的不同，removeAll() 可能会在恒定时间内执行，尽管执行似乎最有可能在线性时间内发生。
我认为如果 NlogN 以最糟糕的方式实现的话，它会是这样。如果要删除每个元素，则无需搜索元素。您拥有的任何元素都需要删除，因此无需搜索。
于 2011-11-09T20:53:36.407 回答
0
没有。对于大小为 k 的参数集合，removeAll() 的最坏情况上限当然是 O(k*log n) - 因为参数集合中包含的每个元素都必须从树集中删除 (这至少需要搜索它们），每次搜索都会产生 log n 的成本。
于 2011-11-09T00:00:04.730 回答