Анализ алгоритма

Для начала заметим, что новый алгоритм максимального потока с масштабиро- ванием представляет собой простую реализацию исходного алгоритма Форда- Фалкерсона. Новые циклы, значение Δ и сокращенный остаточный граф Gf (Δ) нужны только для того, чтобы управлять выбором остаточного пути — чтобы ребра с большой остаточной пропускной способностью использовались как мож- но дольше.
Следовательно, все свойства, доказанные для исходного алгоритма Форда-Фалкерсона истинны и для новой версии; поток остается целочисленным в этом алгоритме, а следовательно, все остаточные пропускные способности также являются целочисленными.

(7.15) Если пропускные способности являются целочисленными, то в алгорит- ме максимального потока с масштабированием поток и остаточные пропускные способности также остаются целочисленными. Из этого следует, что при Δ = 1, Gf (Δ) не отличается от Gf — а следовательно, когда алгоритм завершает построение потока, f имеет максимальную величину.

Теперь рассмотрим время выполнения. Назовем итерацию внешнего цикла (с фиксированным значением Δ) фазой Δ-масштабирования. Легко дать верхнюю границу для количества разных фаз Δ-масштабирования в контексте значения

которое также использовалось в предыдущем разделе. Начальное

значение Δ не превышает C, уменьшается вдвое и никогда не опускается ниже 1. Следовательно,

(7.16) Количество итераций внешнего цикла не превышает 1 + [l

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

Еще по теме Анализ алгоритма:

  1. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  4. АЛГОРИТМ
  5. АЛГОРИТМ УДАЧИ
  6. Алгоритм исцеления:
  7. Алгоритм избавления от боли
  8. 2. Специфика и алгоритмы работы с источниками.
  9. Алгоритм обработки результатов.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
  12. Принципы анализа происшествия.
  13. АНАЛИЗ
  14. АНАЛИЗ КОРОТКИЙ
  15. КОНТЕНТ - АНАЛИЗ
  16. Анализ документов
  17. МЕТОД АНАЛИЗА ЖИЗНИ
  18. АНАЛИЗ ДИСПЕРСИОННЫЙ
  19. Анализ линий
  20. 4.2. Анализ одномерных распределений