Может ли прирост производительности для параллельного алгоритма с N потоками быть больше, чем N?

Теоретический вопрос, может быть, он очевиден:

Возможно ли, что алгоритм, реализованный параллельно с N потоками, будет выполняться более чем в N раз быстрее, чем исходный однопоточный алгоритм? Другими словами, может ли коэффициент усиления быть лучше линейного в зависимости от количества потоков?

11
задан Jakub M. 25 October 2011 в 16:20
поделиться