Оптимальным является следующее значение:
Если p <= n / log n, вы можете сделать это за O (n / p) время; в противном случае это O (log n), т.е. когда p> n / log n, вы ничего не получите по сравнению с p = n / log n.
Доказательство - нижняя граница:
Утверждение 1. Вы никогда не сможете сделать быстрее, чем Ω (n / p), потому что процессоры p могут дать только ускорение p
Утверждение 2: Вы не можете делать быстрее, чем Ω (log n), из-за модели CREW (см. Статью о непрощенном) если вы хотите проверить, имеет ли массив 0-1 хотя бы один 1, вам нужно время O (log n).
Доказательство - верхняя граница:
Утверждение 3: Вы можете найти максимум, используя n / log n процессоров и за время O (log n)
Доказательство: легко найти максимум с помощью n процессоров и зарегистрировать n времени; но на самом деле в этом алгоритме большинство процессоров большую часть времени бездействуют; подходящим ласточкиным хвостом (см., например, книгу о сложностях Пападимитриу) их число можно уменьшить до n / log n.
Теперь, имея менее n / log n процессоров, вы можете отдать работу, назначенную K процессорам, одному процессору, это делит требования к процессору на K и умножает требуемое время на K.
Пусть K = (n / log n) / p; предыдущий алгоритм выполняется за время O (K log n) = O (n / p) и требует n / (log n * K) = p процессоров.
Отредактировано: я только что понял, что когда p <= n / log n, алгоритм dasblinkenlight имеет ту же асимптотическую среду выполнения: </p>
n / p + log p <= n / p + log (n / log n) <= n / p + log n <= n / p + n / p <= 2n / p = O (n / p ) </p>
так что вы можете использовать этот алгоритм, который имеет сложность O (n / p), когда p <= n / log n и O (log n) в противном случае. </p>