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

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

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

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

Рассмотрим простейший случай: пусть $y=f(x)$ есть вещественная функция вещественного переменного $x,\quad a\leqslant x\leqslant b$, и пусть $f(x)$ удовлетворяет на $(a,b)$ условию Липшица порядка t $\alpha$, $0<\alpha <1,$ так что для $x_{1},x_{2}\in (a,b):$ $|f(x_{1})-f(x_{2})|\leqslant |x_{1}-x_{2}|^{\alpha }.$

Пусть $n$ — натуральное число.

Опр.2 Вычислить функцию $y=f(x)$ в точке $x=x_{0}\in (a,b)$ с точностью до $n$ знаков (с точностью $2^{-n}$) значит найти такое число $A,$ что $|f(x_{0})-A|\leqslant 2^{-n}.$

Опр.3 Количество битовых операций достаточное для вычисления функции $f(x)$ в точке $x=x_{0}$ с точностью до $n$ знаков посредством данного алгоритма называется сложностью вычисления $f(x)$ в точке $x=x_{0}$ с точностью до $n$ знаков. Таким образом, сложность вычисления функции $f(x)$ в точке $x=x_{0}$ есть функция $n$, а также $f(x)$ и $x=x_{0}.$ Эта функция обозначается через $s_{f}(n)=s_{f,x_{0}}(n).$

Ясно, что $s_{f}(n)$ зависит также от алгоритма вычисления и при разных алгоритмах будет разной. Сложность вычисления непосредственно связана со временем, затрачиваемым компьютером на это вычисление и потому иногда в литературе обозначается 'временной' функцией Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle T(n)} .

Вопрос о поведении $s_{f}(n)$ при Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n \to \infty} для класса функций или конкретной функции $f$, был впервые поставлен А. Н. Колмогоровым около 1956 года.

Функция сложности умножения имеет специальное обозначение — $M(n)$.

Проблема поведения $M(n)$ при $n\to +\infty$ была первой абсолютно нетривиальной проблемой теории быстрых вычислений.

См. также

• Быстрые алгоритмы
• АГС метод Гаусса
• Метод БВЕ