Обратная задача: Сбор данных по всей сети
Рассмотрим сбор данных по всей
сети трехмерного гиперкуба в один узел (например, узел 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