Обратная задача: Сбор данных по всей сети
Рассмотрим сбор данных по всей сети трехмерного гиперкуба в один узел (например, узел 000). То есть 8 узлов: 000, 001, 010,
011, 100, 101, 110 и 111. В узел 000 нужно передать данные (сообщения)
из всех остальных узлов гиперкуба.
Эффективный алгоритм таков:
- 1 шаг:
- Узел 100 ---- узел 000
- Узел 101 ---- узел 001
- Узел 110 ---- узел 010
- Узел 111 ---- узел 011
- 2 шаг:
- Узел 010 ---- узел 000
- Узел 011 ---- узел 001
- 3 шаг:
В случае сбора данных сообщения будут идти дольше, чем в случае рассылки
(пример 1), так как теперь пересылается из узла в узел не одно сообщение,
а несколько. Следовательно, общее время (time complexity) этого алгоритма
будет превышать O(log n).
[Назад]
[Оглавление]
[Вперед]
Последнее обновление 21.11.2001 WebMaster