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

Чтобы преодолеть ограничение квадратичного времени для свертки, мы восполь- зуемся связью между сверткой и умножением двух многочленов, как в первом из рассмотренных выше примеров. Но вместо того, чтобы использовать свертку как примитив при умножении многочленов, мы будем использовать эту связь в об- ратном направлении.

Предположим, даны векторы a = (aQ, a1, ..., an-1) и b = (bQ,bl, ..., bn-1). Бу- дем рассматривать их как многочлены A(x) = aQ + a1x + a2x2 + ... an1xn-1 и B(x) = bQ + b{x + b2x2 + ... bn1x"-1 и посмотрим, как вычислить их произведение C(x) = А(x)В(x) за время O(n log n). Если c = (cQ, c1, ..., c2 2) — вектор коэффици- ентов C, то, как было сказано выше, c в точности представляет собой свертку a * b, поэтому нужный ответ можно напрямую получить из коэффициентов C(x).

Вместо того чтобы перемножать А и В в алгебраическом виде, мы можем рас- сматривать их как функции переменной x и перемножим так, как описано ниже.

(i) Сначала выбираем 2n значений x1, x2, ..., x2n и вычисляем A(x.) и B(x) для каждого j = 1, 2, ..., 2n.

(ii) Теперь C(x.) легко вычисляется для каждого j как произведение двух чисел

A(xj) и B(xj).

(iii) Остается восстановить C по значениям x1, x2, ..., x2n.

Для этого мы вос- пользуемся одним фундаментальным свойством многочленов: любой многочлен степени d может быть восстановлен по своим значениям для произвольного набора из d + 1 и более точек. Этот механизм, называемый полиномиальной интерполяцией, более подробно рассматривается ниже. А пока заметим, что для многочленов А и В, степень которых не превышает n - 1, степень произведения C не превышает 2n - 2, что позволяет реконструировать многочлен по значениям C(x1), C(x2), ..., C(x2n), вычисленным на шаге (ii).

Этот метод умножения многочленов имеет как положительные аспекты, так и недостатки. Сначала о хорошем: шаг (ii) требует только O(n) арифметических операций, поскольку в нем задействовано умножение O(n) чисел. Но на шагах (i) и (iii) ситуация выглядит уже не столь радужно. В частности, вычисление многочленов А и В для одного значения требует Ω(n) операций, а наш план требует выполнения 2n таких вычислений. Казалось бы, мы снова возвращаемся к квадра- тичному времени.

Чтобы эта идея заработала, необходимо найти множество из 2n значений x1, x2, ..., x2n, которые связаны определенным образом — например, для которых работа по вычислению A и B может быть повторно использована в разных вы- числениях. Множеством, для которого этот способ отлично работает, является множество комплексных корней из единицы.

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

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

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