为什么Java文档中不包含每个函数的时间/空间复杂度？

Question

您好，我想了解String类中"replaceAll"函数的时间复杂度，但是我找不到相关信息。（http://docs.oracle.com/javase/6/docs/api/java/lang/String.html）

Java是否应该在Javadoc中包含这些复杂性呢？我认为这对于某些人来说是非常重要的事情。

- jan1

Answer 1

大多数函数的时间复杂度相当直观。据我所知，replaceAll的时间复杂度为O(n)。

在我看来，没有什么比用分析工具（如分析器）进行实证测试更能说明问题，因为你使用的99%的方法很可能对应用程序的性能影响不大甚至没有影响。

- Peter Lawrey

Answer 2

如果有保证，复杂性可以被记录。例如，一些集合类记录了复杂性保证。例如，来自HashMap的内容：

该实现提供基本操作（get和put）的常数时间性能...

然而，有时候复杂性可能是：

• 没有保证，并且可以随着实现的修改而自由更改。
• 显然是O(1)。

- Andy Thomas

Answer 3

Java API 的 javadocs 规定了每个方法必须做什么，而不是如何做。API 的每个实现者（例如 OpenJDK、Oracle 的 JDK 等）在实现每个规定时都有一定的自由度，这种自由度可能包括进行优化，甚至在性能方面做出牺牲。因此，通常情况下，javadocs 不会指定函数的时间/复杂度等详细信息，除非某个方法必须满足特定的性能要求。

- Óscar López

Answer 4

如果你使用基本操作的空间/时间复杂度来驱动设计决策，那么你几乎肯定是错误的。

首先构建一个正确的应用程序，然后进行分析。然后优化分析过程揭示的瓶颈。

- kittylyst

Answer 5

一般来说，复杂度通常取决于难以分析的因素。这当然适用于 String.replaceAll，其中有效复杂度关键取决于 regex 字符串。(设计不良的正则表达式可能会使匹配非常缓慢。)

- Stephen C