Stream、string split和collect一起使用时的时间复杂度

Question

我必须使用逗号分隔符拆分字符串并在其中查找值。我在想哪种方法更快地在数组中拆分字符串并检查数组是否包含它或在 Set 中拆分字符串并在 Set 中进行查找。

我想知道Java中下面两个语句的时间复杂度是多少：

// statement #1
Set<String> result = Stream.of(givenString.split(",")).collect(Collectors.toSet());

// statement #2
String[] split = givenString.trim().split(",");

他们都是O(n)吗？

Answer 1

令n为字符串长度，k为comma-separated个单词的数量，w为单词的最大长度。另外，假设我们的单位成本是字符 comparison/copying.

将字符串拆分为单词（String.split() 方法）将花费 O(n)。

如果 Set 实现为 TreeSet，则根据这些词构建 Set 将花费 O(k * log(k) * w)，如果 Set 实现，则需要 O(k * w)实现为 HashSet（具有一些合理的负载系数）。因此，大致分别为 O(n * log(n)) 和 O(n)。在 Set 中搜索将分别是 O(log(k) * w) 和 O(1)（大约 O(log(n)) 和 O(1)）。

构建数组（或 ArrayList）将花费 O(k * w) 或大约 O(n)。在数组中搜索也将是 O(k * w).

因此，如果您只打算执行一些搜索，那么构建一个 Set 没有多大意义；您可以在 List 中使用简单（顺序）搜索（例如 List.indexOf）。但如果要进行多次搜索，提前建一个Set，肯定会更有效。

Stream、string split和collect一起使用时的时间复杂度

Time complexity when Stream, string split and collect are used together

java

time-complexity