时间戳

首页 > 解决方案 > 嵌套循环和流的时间复杂度

java - 嵌套循环和流的时间复杂度

问题描述

我希望确认以下假设。嵌套 for 循环之后的时间复杂度是相同的：

List<Integer> smallList = List.of(1, 2, 3, 4, 5);
List<Integer> bigList = IntStream.range(1, 1_000_000).boxed().collect(Collectors.toList());

for (int i : smallList) {
    for (int j : bigList) {
        doSomething(i, j);
    }
}

for (int j : bigList) {
    for (int i : smallList) {
        doSomething(i, j);
    }
}

我的假设是时间复杂度是相同的，因为 5 x 1_000_000 调用 doSomething 与 1_000_000 x 5 调用 doSomething 相同。这是正确的吗？如果是，如果涉及流，这也是真的吗？

smallList.stream().forEach(i -> bigList.stream().forEach(j -> doSomething(i,j)));
bigList.stream().forEach(j -> smallList.stream().forEach(i -> doSomething(i,j)));

上述两个语句的时间复杂度是否相同？

标签： javajava-streamtime-complexity

解决方案

关于时间复杂度，是的 - 这些操作在执行的“doSomethings”方面操作相同。5乘以100万自然等于100万乘以5。

问题在于细节——我当然不能保证这些操作在现实世界中执行相同，因为你会遇到现实世界的限制，比如内存使用、核心数量、缓存/内存对齐问题等。当然，如果这些问题不会以某种意想不到的方式严重影响您的性能，那么您会期望看到这两个操作的执行时间大致相等。

推荐阅读