Анализ мемоизированной версии
(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), как и требовалось. ■
Еще по теме Анализ мемоизированной версии:
- 11. КРИМИНАЛИСТИЧЕСКИЕ ВЕРСИИ И ПЛАНИРОВАНИЕ РАССЛЕДОВАНИЯ
- Проверка криминалистической версии
- АНАЛИЗ
- АНАЛИЗ КОРОТКИЙ
- КОНТЕНТ - АНАЛИЗ
- Анализ документов
- МЕТОД АНАЛИЗА ЖИЗНИ
- АНАЛИЗ ДИСПЕРСИОННЫЙ
- Анализ линий
- АНАЛИЗ КАТЕГОРИАЛЬНЫЙ
- АНАЛИЗ АКТИВНЫЙ
- АНАЛИЗ ФАКТОРНЫЙ
- АНАЛИЗ РЕГРЕССИОННЫЙ
- РАБОТА АНАЛИЗА
- Анализ фигур
- АНАЛИЗ КАУЗАЛЬНО-ДИНАМИЧЕСКИЙ
- ПСИХИКА: АНАЛИЗ: ЕДИНИЦА