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