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

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

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

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

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

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

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

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

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

M.

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

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

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

s_f = Ologn),

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