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