Разработка алгоритма

В основу улучшенного алгоритма заложен более умный способ разбиения произ- ведения на частичные суммы. Предположим, вычисления ведутся по основанию 2

Уравнение (5.1) сводит проблему решения одной n-разрядной задачи (умно- жение двух n-разрядных чисел x и у) к проблеме решения четырех n/2-разрядных задач (вычисление произведений x1y1, x1y0, x0y1 и x0y0).

Таким образом, появляется первый кандидат на решение методом «разделяй и властвуй»: рекурсивное вы- числение результатов для этих четырех n/2-разрядных экземпляров с последую- щим объединением их с использованием уравнения (5.1). Объединение решений требует постоянного количества сложений О(n)-разрядных чисел, поэтому оно выполняется за время O(n); следовательно, время выполнения T(n) ограничивается рекуррентным отношением


для константы c. Хватит ли этого, чтобы обеспечить субквадратичное время вы- полнения? Чтобы получить ответ, достаточно заметить, что это просто случай q = 4 класса рекуррентных отношений в (5.3). Как было показано ранее в этой главе, решение имеет вид Г(я)
<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Разработка алгоритма:

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