嵌套循环和流的时间复杂性

Question

我希望以下假设得到证实。以下嵌套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)));

上述两种说法的时间复杂度相同吗？

Answer 1

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

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