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

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

Будем считать, что числа записаны в двоичной системе счисления, знаки которой $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)$ зависит также от алгоритма вычисления и при разных алгоритмах будет разной. Сложность вычисления непосредственно связана со временем, затрачиваемым компьютером на это вычисление и потому иногда в литературе обозначается 'временной' функцией $T(n)$^[1].

Вопрос о поведении $s_f(n)$ при $n \to \infty$ для класса функций или конкретной функции $f$, был впервые поставлен А.Н. Колмогоровым около 1956 года. ^[2]

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

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

Ссылки

1. ↑ Д.E.Kнут, Искусство программирования на ЭВМ. т.2, Изд. Мир, Москва (1977).
2. ↑ А.Н.Колмогоров, Теория информации и теория алгоритмов. Изд. Наука, Москва (1987).

См. также

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