Интернет магазин китайских планшетных компьютеров



Компьютеры - Быстрые алгоритмы

22 января 2011


Оглавление:
1. Быстрые алгоритмы
2. История вопроса



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

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

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

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

Сложность вычисления

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

s_f=s_{f,\;x_0}.

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

M.

Наилучшая известная в настоящее время оценка сложности умножения есть M = O.

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

Назовём алгоритм вычисления функции f = f быстрым, если, предполагая наилучшую оценку для M, для этого алгоритма битовая сложность вычисления имеет вид:

sf = Ologn),

где c есть константа.



Просмотров: 1107


<<< Метод БВЕ