Анализ мемоизированной версии

Конечно, этот алгоритм очень похож на предыдущую реализацию; однако мемои- зация позволяет сократить время выполнения.

(6.4) Время выполнения M-Compute-Opt(n) равно O(n) (предполагается, что вход- ные интервалы отсортированы по конечному времени).

Доказательство. Время, потраченное на один вызов M-Compute-Opt, равно O(1) без учета времени, потраченного в порожденных им рекурсивных вызовах. Таким образом, время выполнения ограничивается константой, умноженной на коли- чество вызовов M-Compute-Opt. Так как сама реализация не предоставляет явной верхней границы для количества вызовов, для получения границы мы попытаемся найти хорошую метрику «прогресса».

Самой полезной метрикой прогресса является количество «непустых» эле- ментов M. В исходном состоянии оно равно 0; но при каждом переходе на новый уровень с выдачей двух рекурсивных вызовов M-Compute-Opt заполняется новый элемент, а следовательно, количество заполненных элементов увеличивается на 1. Так как M содержит только n + 1 элемент, из этого следует, что количество вызовов

M-Compute-Opt не превышает O(n), а следовательно, время выполнения M-Compute- Opt(n) равно O(n), как и требовалось. ■

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

Еще по теме Анализ мемоизированной версии:

  1. 11. КРИМИНАЛИСТИЧЕСКИЕ ВЕРСИИ И ПЛАНИРОВАНИЕ РАССЛЕДОВАНИЯ
  2. Проверка криминалистической версии
  3. АНАЛИЗ
  4. АНАЛИЗ КОРОТКИЙ
  5. КОНТЕНТ - АНАЛИЗ
  6. Анализ документов
  7. МЕТОД АНАЛИЗА ЖИЗНИ
  8. АНАЛИЗ ДИСПЕРСИОННЫЙ
  9. Анализ линий
  10. АНАЛИЗ КАТЕГОРИАЛЬНЫЙ
  11. АНАЛИЗ АКТИВНЫЙ
  12. АНАЛИЗ ФАКТОРНЫЙ
  13. АНАЛИЗ РЕГРЕССИОННЫЙ
  14. РАБОТА АНАЛИЗА
  15. Анализ фигур
  16. АНАЛИЗ КАУЗАЛЬНО-ДИНАМИЧЕСКИЙ
  17. ПСИХИКА: АНАЛИЗ: ЕДИНИЦА