Главная > Разное > Теоретические основы проектирования компьютерных сетей
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

4.4.2 Оценка вычислительной сложности метода

Оценку вычислительной сложности метода полиномиальной аппроксимации проведем для однородных экспоненциальных сетей, эффективные вычислительные алгоритмы и оценки количества арифметических операций для которых были приведены в разделе 3.1.

Для экспоненциального распределения длительности обслуживания в центрах сети уравнение (4.22) принимает вид

где введены обозначения

При решении уравнения (4.23) используется ограничение и один из итерационных методов, например метод деления пополам, дающий оценку количества арифметических операций. Легко показать, что при выполнении условия

функция , а при

функция Следовательно, корень уравнения лежит в интервале

Очевидно, что после m операций получим интервал такой, что

Пусть - требуемая точность решения. Обозначим . Полагая без ограничения общности получаем количество итераций, необходимых для отыскания решения с точностью Заметим, что и, следовательно, при большом количестве центров число итераций .

Пусть, например, . Тогда .

Полагая, что количество арифметических операций, необходимых для выполнения одной итерации, не превышает имеем

Таким образом, при исследовании сетей большой размерности предложенный метод в вычислительном отношении значительно лучше метода Бузена.

<< Предыдущий параграф Следующий параграф >>
Оглавление