15

嗨，我想知道 String 类的“replaceAll”函数的时间复杂度是多少，但我找不到任何信息。（http://docs.oracle.com/javase/6/docs/api/ java/lang/String.html )

Java 将复杂性包含在 Javadoc 中不是更好吗？我相信有人知道这是一件非常重要的事情。

4

5 回答 5

9

大多数函数具有相当直接的时间复杂度。AFAIK，replaceAll 是 O(n)

恕我直言。没有什么比自己凭经验测试更好的了，例如使用分析器，因为您使用的 99% 的方法很可能对应用程序的性能几乎没有影响。

于 2012-04-10T15:40:27.883 回答
3

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

此实现为基本操作（get 和 put）提供恒定时间性能......

但是，有时复杂性是：

  • 不保证，并且可以通过修改实现来自由更改。
  • 显然 O(1)。
于 2012-04-10T15:40:16.247 回答
1

Java API 的 javadocs 指定了每个方法必须做什么的一般合同，而不是如何。API 的每个实现者（例如，OpenJDK、Oracle 的 JDK 等）对于如何实现每个合约都有一定的自由度，这种自由度可能包括进行优化，甚至牺牲性能。因此，javadocs 通常不会指定功能的时间/复杂性等细节，除非方法绝对有必要满足某些性能要求。

于 2012-04-10T15:41:05.107 回答
0

如果您使用基本操作的空间/时间复杂性来驱动设计决策，那么您几乎可以肯定做错了。

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

于 2012-04-10T15:45:36.293 回答
0

一般的答案是复杂性通常取决于难以分析的因素。这当然适用于String.replaceAll，其中有效复杂性严重取决于regex字符串。（设计不佳的正则表达式会使匹配变得非常缓慢。）

于 2012-04-10T15:58:18.870 回答