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

Время выполнения алгоритма определяется следующим образом. Для двух n-разрядных чисел выполняется постоянное количество сложений О(n)-разрядных чисел помимо трех рекурсивных вызовов. Пока проигнорируем тот факт, что x1 + x0 иy1 + y0 могут содержать n/2 + 1 битов (вместо n/2), так как это не влияет на асимптотические результаты; итак, каждый из рекурсивных вызовов работает с экземпляром размера n/2.
Вместо рекурсии с четверным ветвлением мы получаем тройное ветвление с временем выполнения, удовлетворяющим отношению

для константы с.

Перед нами тот самый случай q = 3 из (5.3), к которому мы стремились. Исполь- зуя разрешение рекуррентности, приведенное ранее в этой главе, имеем:

(5.13) Время выполнения рекурсивного умножения для двух n-разрядных

множителей равно

5.6.

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