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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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


Будем считать, что числа записаны в двоичной системе счисления, знаки которой 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).

См. также[править | править вики-текст]