Расширения: основные усовершенствования алгоритма Анализ улучшенного времени выполнения
Если действовать чуть внимательнее при анализе приведенного выше метода, можно улучшить время выполнения до 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). ■
Еще по теме Расширения: основные усовершенствования алгоритма Анализ улучшенного времени выполнения:
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- Временной фактор в анализе серийных преступлений
- 3.2.4. Логический анализ основных понятий
- Тема 1. Основные принципы системного анализа
- Основная единица анализа: транзакция
- Основная единица анализа: транзакция
- Глава 2. Основные направления прикладного системного анализа
- 1.2. Основные понятия системного анализа
- Часть вторая. Основные методы анализа чувства беспокойства.
- Глава 1. Основные принципы системного анализа 1.1. Становление теории систем
- 1. Определение ключевых понятий, основные проявления и анализ ядра характера
- Резюме второй части. Основные методы анализа проблем, вызывающих чувство беспокойства.
- Статья 778. Улучшение нанимателем вещи, переданной в найм
- ГЛАВА 2 МИСТЕР РЕШАЮ-ВСЕ-ПРОБЛЕМЫ И КОМИТЕТ УСОВЕРШЕНСТВОВАНИЯ НА ДОМУ