Расширения: основные усовершенствования алгоритма Анализ улучшенного времени выполнения

Как выясняется, мы можем обеспечить более точный анализ времени выполнения для случая, если граф G содержит не слишком много ребер. Направленный граф с n узлами может иметь примерно до n2 ребер, так как теоретически ребро может связывать каждую пару узлов, но многие графы оказываются намного более раз- реженными.
Как мы уже неоднократно видели в примерах, при работе с графом, у которого количество ребер m значительно меньше n2, время выполнения может быть полезно записывать формулой, содержащей как m, так и n; это позволит уско- рить обработку для графов с относительно небольшим количеством ребер.

Если действовать чуть внимательнее при анализе приведенного выше метода, можно улучшить время выполнения до O(mn) без значительного изменения самого алгоритма.

(6.25) Метод кратчайшего пути может быть реализован за время O(mn). Доказательство. Рассмотрим вычисление элемента массива M[i, v] в соответ- ствии с рекуррентным отношением (6.23); имеем

Л/[У. v] = miп(А/[/ - 1. v]. miп (А/[У - 1. w] + с,и,)).

Мы предположили, что вычисление этого минимума может занять время до O(n), так как существуют n возможных узлов w. Но разумеется, этот минимум необходимо вычислять только по узлам w, с которым узел v связан ребром; обо- значим это число nv. В этом случае вычисление элемента массиваM[i,v] занимает время O(nv). Элемент должен вычисляться для каждого узла v и каждого индекса 0 < i < n - 1, поэтому в результате получается время выполнения


В главе 3 точно такой же анализ проводился для других алгоритмов, работаю- щих с графами, а утверждение (3.9) из этой главы использовалось для ограничения

выражения для ненаправленных графов. Здесь мы имеем дело с направ-

ленными графами, а nv обозначает количество ребер, выходящих из v. В некотором смысле работать со значением для направленных графов даже проще:

каждое ребро выходит ровно из одного узла V, поэтому каждое ребро учитывается

в этом выражении ровно один раз. Следовательно, имеем γ л,. — т. Подставляя этот результат в выражение


для времени выполнения, получаем границу времени выполнения O(mn). ■

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Расширения: основные усовершенствования алгоритма Анализ улучшенного времени выполнения:

  1. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  2. Временной фактор в анализе серийных преступлений
  3. 3.2.4. Логический анализ основных понятий
  4. Тема 1. Основные принципы системного анализа
  5. Основная единица анализа: транзакция
  6. Основная единица анализа: транзакция
  7. Глава 2. Основные направления прикладного системного анализа
  8. 1.2. Основные понятия системного анализа
  9. Часть вторая. Основные методы анализа чувства беспокойства.
  10. Глава 1. Основные принципы системного анализа 1.1. Становление теории систем
  11. 1. Определение ключевых понятий, основные проявления и анализ ядра характера
  12. Резюме второй части. Основные методы анализа проблем, вызывающих чувство беспокойства.
  13. Статья 778. Улучшение нанимателем вещи, переданной в найм
  14. ГЛАВА 2 МИСТЕР РЕШАЮ-ВСЕ-ПРОБЛЕМЫ И КОМИТЕТ УСОВЕРШЕНСТВОВАНИЯ НА ДОМУ