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

Следуя точной аналогии с доказательством (6.3), можно доказать посредством индукции поj, что этот алгоритм записывает OPT(j) в элемент массива M[j]; (6.1) предоставляет шаг индукции. Кроме того, как и ранее, Find-Solution можно передать заполненный массив M для получения оптимального решения помимо значения.
Наконец, время выполнения Iterative-Compute-Opt очевидно равно O(n), так как алгоритм явно выполняется в течение n итераций и проводит постоянное время в каждой из них.

Пример выполнения Iterative-Compute-Opt представлен на рис. 6.5. При каждой итерации алгоритм заполняет один дополнительный элемент массива M, сравнивая значение v. + M[p(j)] со значениемM[j - 1].

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