Найти диапазон этого алгоритма - PullRequest
0 голосов
/ 23 мая 2011

У меня есть следующие алгоритмы:

  SUM-ARRAY(A,B,C):
     n = A.length
     grain-size = 1
     r = ceil(n/grain-size)
     for k = 0 to r-1:
          spawn ADD-S(A,B,C,k*grain-size+1, min((k+1)*grain-size,n))

     sync


  ADD-S(A,B,C,i,j):
  for k=i to j:
     C[k]=A[k]+B[k]

Хорошо, у меня есть следующее обсуждение с моей группой:

Мы хотим найти диапазон этого алгоритма, и некоторые из нас думают, что это тэта (1) и другие тэта (n).

Есть ли какая-нибудь помощь там?

Ответы [ 3 ]

1 голос
/ 24 мая 2011

Диапазон, или критическая длина пути, может быть определен как «теоретически самое быстрое время, когда работа может быть выполнена на компьютере с бесконечным числом процессоров».

В вашем случае все порожденные итерации независимы, поэтому все могут выполняться одновременно, если имеется достаточно процессоров.И каждая итерация обрабатывает grain-size большой кусок работы.Таким образом, диапазон - это Theta (grain-size), который может быть эквивалентен либо Theta (1), либо Theta (n), либо даже Theta (sqrt (n)), если вы установите размер зерна таким способом.Для размера зерна 1, как в вашем коде, span равен Theta (1), т.е. не зависит от количества итераций.

0 голосов
/ 28 апреля 2014

Когда размер зерна равен 1, диапазон равен O (n), поскольку цикл for будет принимать n раз O (1), даже если все дочерние элементы будут работать параллельно, родительский поток все равно будет принимать O (1). ) для операции «порождение».

Источник: Это из решения алгоритма курса CS.

0 голосов
/ 23 мая 2011

Полагаю, вам нужна сложность алгоритма.

Итак, вы, по сути, добавляете два массива A и B в другой массив C, и вы делаете это, вызывая r подпроцесс, каждый из которых добавляет часть длины grain_size из A и B.

Я рассуждаю так:

  • ADD-S добавляет m = grain_size элементов двух массивов, и поэтому его сложность равна Theta (m)
  • SUM-ARRAY порождает r подпроцессов, каждый из которых выполняет ADD-S, поэтому его сложность равна Theta (r *)m) = Theta (n)

Итак, мой ответ - Theta (n).

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...