Во-первых, это не для каких-либо домашних заданий, это просто алгоритм общего типа. В курсе параллельных вычислений, который я беру, у меня возникают проблемы с тем, чтобы обернуть голову вокруг стиля алгоритма, который имеет время выполнения O (что-то + ... log p). Например, мы рассмотрели алгоритмы сокращения последовательности: O (n / p + log p), где p = #procs, а n - размер проблемы. Бревно база 2.
Проблема, с которой я столкнулся, заключается в идее log (p). С одной стороны, я привык везде видеть log (n), сводя задачи к двум подзадачам размера n / 2 и т. Д. Вторая - просто идея иметь ступенчатую сложность алгоритма как log (p). Потому что это будет означать, что для проблемы фиксированного размера, если я увеличу количество процессоров, то я увеличу количество шагов в алгоритме? Я всегда думал о ступенчатой сложности алгоритма как о неотъемлемом последовательном аспекте алгоритма и, следовательно, увеличение или уменьшение числа процессоров не должно иметь никакого влияния на это. Это плохой способ думать об этом?
Полагаю, что было бы полезно использовать псевдокод алгоритмов, в которых время выполнения log (p) находится где-то в них.