WikiSort.ru - Не сортированное

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

Будем считать, что числа записаны в двоичной системе счисления, знаки которой ${\displaystyle 0}$ и ${\displaystyle 1}$ называются битами.

Опр.1. Запись знаков ${\displaystyle 0,1,+,-,(,)}$ , сложение, вычитание и умножение двух битов назовём одной элементарной или битовой операцией.

Рассмотрим простейший случай: пусть ${\displaystyle y=f(x)}$ есть вещественная функция вещественного переменного ${\displaystyle x,\quad a\leqslant x\leqslant b}$ , и пусть ${\displaystyle f(x)}$ удовлетворяет на ${\displaystyle (a,b)}$ условию Липшица порядка t ${\displaystyle \alpha }$ , ${\displaystyle 0<\alpha <1,}$ так что для ${\displaystyle x_{1},x_{2}\in (a,b):}$ ${\displaystyle |f(x_{1})-f(x_{2})|\leqslant |x_{1}-x_{2}|^{\alpha }.}$

Пусть ${\displaystyle n}$ — натуральное число.

Опр.2 Вычислить функцию ${\displaystyle y=f(x)}$ в точке ${\displaystyle x=x_{0}\in (a,b)}$ с точностью до ${\displaystyle n}$ знаков (с точностью ${\displaystyle 2^{-n}}$ ) значит найти такое число ${\displaystyle A,}$ что ${\displaystyle |f(x_{0})-A|\leqslant 2^{-n}.}$

Опр.3 Количество битовых операций достаточное для вычисления функции ${\displaystyle f(x)}$ в точке ${\displaystyle x=x_{0}}$ с точностью до ${\displaystyle n}$ знаков посредством данного алгоритма называется сложностью вычисления ${\displaystyle f(x)}$ в точке ${\displaystyle x=x_{0}}$ с точностью до ${\displaystyle n}$ знаков. Таким образом, сложность вычисления функции ${\displaystyle f(x)}$ в точке ${\displaystyle x=x_{0}}$ есть функция ${\displaystyle n}$ , а также ${\displaystyle f(x)}$ и ${\displaystyle x=x_{0}.}$ Эта функция обозначается через ${\displaystyle s_{f}(n)=s_{f,x_{0}}(n).}$

Ясно, что ${\displaystyle s_{f}(n)}$ зависит также от алгоритма вычисления и при разных алгоритмах будет разной. Сложность вычисления непосредственно связана со временем, затрачиваемым компьютером на это вычисление и потому иногда в литературе обозначается 'временной' функцией ${\displaystyle T(n)}$ ^[1].

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

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

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

Ссылки

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

См. также

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