- Сложность вычисления (битовая)
-
Для оценки качества быстрого метода или алгоритма используется функция сложность вычисления (битовая).
Будем считать, что числа записаны в двоичной системе счисления, знаки которой и называются битами.Опр.1. Запись знаков , сложение, вычитание и умножение двух битов назовём одной элементарной или битовой операцией.
Рассмотрим простейший случай: пусть есть вещественная функция вещественного переменного , и пусть удовлетворяет на условию Липшица порядка t , так что для
Пусть — натуральное число.
Опр.2 Вычислить функцию в точке с точностью до знаков (с точностью ) значит найти такое число что
Опр.3 Количество битовых операций достаточное для вычисления функции в точке с точностью до знаков посредством данного алгоритма называется сложностью вычисления в точке с точностью до знаков. Таким образом, сложность вычисления функции в точке есть функция , а также и Эта функция обозначается через
Ясно, что зависит также от алгоритма вычисления и при разных алгоритмах будет разной. Сложность вычисления непосредственно связана со временем, затрачиваемым компьютером на это вычисление и потому иногда в литературе обозначается 'временной' функцией [1].
Вопрос о поведении при для класса функций или конкретной функции , был впервые поставлен А.Н. Колмогоровым около 1956 года. [2]
Функция сложности умножения имеет специальное обозначение — .
Проблема поведения при была первой абсолютно нетривиальной проблемой теории быстрых вычислений.
Ссылки
- ↑ Д.E.Kнут, Искусство программирования на ЭВМ. т.2, Изд. Мир, Москва (1977).
- ↑ А.Н.Колмогоров, Теория информации и теория алгоритмов. Изд. Наука, Москва (1987).
См. также
Категория:- Вычислительная математика
Wikimedia Foundation. 2010.