Сложность времени во вложенных циклах и потоках - PullRequest
Новая
       7

Сложность времени во вложенных циклах и потоках

1 голос
/ 26 сентября 2019

Я бы хотел подтвердить следующее предположение.Временная сложность, следующая за вложенными для циклов, идентична: 

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)));

Одинакова ли временная сложность обоих приведенных выше операторов?

1 Ответ

1 голос
/ 26 сентября 2019

Что касается сложности времени, то да - эти операции работают одинаково в терминах выполняемых «doSomethings».5 раз 1 миллион, естественно, равен 1 миллиону раз. 5.

Проблема заключается в деталях - я бы точно не гарантировал, что эти операции будут выполняться одинаково в реальном мире, потому что вы столкнетесь с реальным миром.ограничения, такие как использование памяти, количество ядер, проблемы с кэшированием / выравниванием памяти и т. д. Конечно, если эти проблемы не сильно повлияют на вашу производительность каким-то неожиданным образом, вы ожидаете, что обе операцииприблизительно эквивалентное время выполнения.

...