为什么java不像C++那样记录渐近复杂性呢？

Question

我注意到Java库的标准文档(即ArrayList<>.add，remove，...不要像C++等价物那样包含方法的渐近复杂性。这似乎会极大地阻碍使用标准库在Java中开发高效的程序。还是我错过了什么？

Answer 1

java集合方法的运行时间没有记录在方法本身中，因为它们不属于特定的集合类，它们属于接口，如Collection接口或Map接口，这些接口与实现无关。

因此，如果实现接口的类是链表，则remove()方法可能有O(1)；如果实现接口的类是数组列表，则可能有O(n)；因此，接口不能保证方法的性能。

但是，如果您查看java的具体集合类本身的文档(例如，ArrayList )，您总是会发现一些注释，解释了类关于渐近复杂性的一般行为。它只是不会在类的每个方法中重复这个信息，因为a)它是不必要的，b)在绝大多数情况下，java代码访问接口，而不是具体的类，所以您可以看到的关于集合方法的唯一一种文档是由接口提供的文档，而不是由类提供的文档。

如果您确切地告诉我们您正在谈论哪些C++等效项，将会有所帮助，但我怀疑您正在查看的是具体的C++类或模板，而不是接口。当一个方法是非虚拟的，我们知道是哪个类在实现它，所以我们可以记录它的渐近复杂性。当方法是虚拟的时，我们不能做这样的事情。