英文:
Are chained streams x * O(N)?
问题
假设集合中的项保持不变，如果我在一个流之后连接另一个流，在执行一些操作后，它们现在是否是 2 O(N)？
对于修改后的集合，情况也是一样的吗，现在是 O(N) + O(M)？
// O(n)
Stream.of("foo", "bar", "foobar")
.collect(Collectors.partitioningBy(s -> s.length() > 3));
// 2O(n)? O(N) + O(M)?
Stream.of("foo", "bar", "foobar")
.collect(Collectors.partitioningBy(s -> s.length() > 3))
.get(true)
.stream()
.collect(Collectors.toMap(String::length, Function.identity()));
英文:
Assuming the items in the sets stay the same, if I chain a stream after another, after performing some ops, are they now 2 O(N)?
Same with regards to a modified set, is it now O(N) + O(M)?
// o(n)
Stream.of("foo", "bar", "foobar")
.collect(Collectors.partitioningBy(s -> s.length() > 3));
// 2O(n)? O(N) + O(M)?
Stream.of("foo", "bar", "foobar")
.collect(Collectors.partitioningBy(s -> s.length() > 3))
.get(true)
.stream()
.collect(Collectors.toMap(String::length, Function.identity()));
答案1
得分: 0
在测量时间复杂度时，常数被忽略。O(2N) 和 O(N) 是相同的。
对于流（streams）的情况，可以像这样看待：
for (Item item : items) {
doSomething1(item);
doSomething2(item);
}
相对于：
for (Item item : items) {
doSomething1(item);
}
for (Item item : items) {
doSomething2(item);
}
在这两种情况下，总的时间复杂度都是 O(N)，其中 N 是项目（items）的数量。
英文:
When measuring time complexity, the constants are dropped. O(2N) is the same as O(N).
In the case of streams, it can be looked at like this:
for (Item item :items) {
doSomething1(item);
doSomething2(item);
}
Vs this:
for (Item item :items) {
doSomething1(item);
}
for (Item item :items) {
doSomething2(item);
}
In both cases the time complexity is O(N) overall, where N is the number of items.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论