Как вы указали, без точной структуры сети невозможно определить конкретное значение количества отправленных сообщений. Вместо этого мы можем посмотреть на его значение Big-O.
Теперь просто чтобы понять, что мы имеем в виду под Big-O:
- Big-O относится к верхней границе (т.е. наихудший возможный случай) сложности
- Возможно (и вполне вероятно, что в реальных системах) фактическое значение будет меньше
- Без какой-либо функции, которая описывает средний случай (например, каждый процесс связан, в среднем,
N / 2 с другими процессами), мы должны принять наихудший случай
- Под «наихудшим случаем» для этой проблемы мы подразумеваем максимальное количество отправленных сообщений
Итак, давайте предположим наихудший случай, когда каждый процесс связан с N - 1 другими процессами.
Давайте также определим некоторые переменные:
S: = множество процессов N: = количество процессов в S
Мы можем представить набор S как полный (каждый узел соединяется с каждым другим узлом) неориентированный граф, в котором каждый узел в графе соответствует процессу, а каждое ребро в графе соответствует 2 отправленным сообщениям (1 исходящая передача и один ответ).
Начиная с здесь , мы видим, что число ребер в полном графе равно (N(N-1))/2
Таким образом, в худшем случае количество отправленных сообщений составляет N(N-1) или N^2 - N.
Теперь, когда мы имеем дело с нотацией Big-O, нас интересует, как эта величина растет как функция N.
Из неравенства треугольника видно, что O(N^2 - N) является элементом O(N^2).
Таким образом, количество отправленных сообщений возрастает как N^2 в худшем случае.
Можно также достичь этого результата, используя матрицу смежности, то есть матрицу N x N, где 1 в (i, j)-м элементе относится к ребру от узла i к узлу j .
Поскольку в исходной задаче каждый процесс отправляет одно сообщение всем подключенным процессам, которые отвечают одним сообщением, мы видим, что для каждой пары (i, j) и (j, i) будет ребро (одно, представляющее исходящее сообщение). сообщение, один ответ). Исключением из этого будут пары, где i = j, т.е. Мы, процесс, не отправляем себе сообщение.
Таким образом, матрица будет полностью заполнена 1 с за исключением диагонали.
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
Вверху: матрица смежности для N = 4 .
Итак, сначала мы хотим определить формулу для общего числа отправленных сообщений как функцию от количества узлов.
По площади прямоугольника мы видим, что число 1 с в матрице (без учета диагонали) будет N x N = N^2.
Теперь мы должны рассмотреть диагональ. Число пар (x, x), которые могут существовать, задается функцией f(i) where Z(N) -> Z(N) x Z(N) : f(i) = (i, i) - это означает, что для этой функции будет ровно N различных решений.
Таким образом, общий результат заключается в том, что у нас есть N^2 - N сообщений с учетом диагонали.
Теперь мы используем те же рассуждения Big-O сверху, чтобы прийти к тому же выводу, количество сообщений в худшем случае растет как O(N^2).
Итак, теперь вам нужно только принять во внимание количество раундов, которые произошли, оставив вас с O (RN ^ 2).
Конечно, теперь вы должны подумать, действительно ли у вас наихудший случай ...