WikiSort.ru - Не сортированное

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

Битовая операция

Будем считать, что числа записаны в двоичной системе счисления, знаки которой ${\displaystyle 0}$ и ${\displaystyle 1}$ называются битами.

Определение. Запись знаков ${\displaystyle 0,\;1,\;+,\;-,\;(,)}$ , сложение, вычитание и умножение двух битов назовём одной элементарной или битовой операцией.

Сложность вычисления (битовая)

Для оценки качества быстрого метода или алгоритма используется функция битовая сложность вычисления которая обозначается через

${\displaystyle s_{f}(n)=s_{f,\;x_{0}}(n)}$ .

Функция сложности умножения имеет специальное обозначение

${\displaystyle M(n)}$ .

Оценка сложности наилучшего (в асимптотике) из известных в настоящее время алгоритмов умножения:

${\displaystyle O\left(n\cdot \log n\cdot 2^{O\left(\log ^{*}n\right)}\right)}$ .

Быстрый алгоритм вычисления функции

Назовём алгоритм вычисления функции ${\displaystyle f=f(x)}$ быстрым, если, предполагая наилучшую оценку для ${\displaystyle M(n)}$ , для этого алгоритма битовая сложность вычисления имеет вид:

${\displaystyle s_{f}(n)=O(M(n)\log ^{c}n),}$

где ${\displaystyle c}$ есть константа.

История вопроса

Первые задачи по битовой сложности вычисления были поставлены А.Н. Колмогоровым^[1], который при этом ссылался на работы Клода Шеннона и Норберта Винера, возбудившие его интерес к информатике.

Область быстрые алгоритмы появилась в 1960 году^[2], когда был найден первый быстрый метод — метод умножения Карацубы. Впоследствии метод Карацубы был обобщён до парадигмы «Разделяй и властвуй», другими важными примерами которой являются метод двоичного разбиения^[en], двоичный поиск, метод бисекции и др.

После метода Карацубы было построено много других быстрых методов, включая алгоритм Штрассена для быстрого умножения матриц ^[3] (обобщение идеи Карацубы на матрицы), метод умножения Шёнхаге — Штрассена^[4][5], метод БВЕ^[6] для вычисления простейших и высших трансцендентных функций. и т. д. Некоторые старые методы становятся быстрыми вычислительными методами, если использовать в них один из быстрых алгоритмов умножения, например, метод Ньютона для вычисления элементарных алгебраических функций и АГС метод Гаусса для вычисления простейших трансцендентных функций.

См. также

• Сложность вычисления (битовая)
• Быстрое умножение
• Алгоритм быстрого возведения в степень
• АГС метод Гаусса
• Метод БВЕ
• Длинная арифметика
• Быстрое преобразование Фурье

Примечания

Ссылки

• Карацуба Е. А. Быстрые алгоритмы и метод БВЕ