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

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

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


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

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

Рассмотрим простейший случай: пусть есть вещественная функция вещественного переменного , и пусть удовлетворяет на условию Липшица порядка t , так что для

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

Опр.2 Вычислить функцию в точке с точностью до знаков (с точностью ) значит найти такое число что

Опр.3 Количество битовых операций достаточное для вычисления функции в точке с точностью до знаков посредством данного алгоритма называется сложностью вычисления в точке с точностью до знаков. Таким образом, сложность вычисления функции в точке есть функция , а также и Эта функция обозначается через

Ясно, что зависит также от алгоритма вычисления и при разных алгоритмах будет разной. Сложность вычисления непосредственно связана со временем, затрачиваемым компьютером на это вычисление и потому иногда в литературе обозначается 'временной' функцией [1].

Вопрос о поведении при для класса функций или конкретной функции , был впервые поставлен А.Н. Колмогоровым около 1956 года. [2]

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

Проблема поведения при была первой абсолютно нетривиальной проблемой теории быстрых вычислений.

Ссылки[править | править вики-текст]

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

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