О-большое

Определение. Пусть и -две функции, определенные на наборах из r положительных целых чи­сел. Предположим, что существуют такие константы В и С, что, ко­гда все n_j больше B, обе функции положительны и В этом случае говорим, что функция f ограничена функцией g, и пишем f = 0(g).

Заметим, что равенство в обозначении f = 0(g) следует, скорее, понимать как неравенство <, а О-большое — как некоторую мульти­пликативную константу.

Пример 3. а) Пусть f(n) - произвольный многочлен степе­ни d с положительным старшим коэффициентом. Тогда, как легко показать, f(n)= O(n^d). В более общем случае можно показать, что f = O(g), если f (n)/g(n) имеет конечный предел при n→ ∞.

В примере 1 можно записать Time(n!) = O((n logn)²).

Функции f (n) и у нас будут часто обозначать вре­мя, которое требуется для решения некоторой арифметической задачи с целым числом п или с набором целых чисел в качестве исходных данных. Мы хотим получить наши оценки в виде достаточ­но простых функций g(п). При этом желательно, чтобы функции g (n) не давали чрезмерно завышенное представление о времени решения за­дач (хотя с чисто математической точки зрения замена функции g(п) в соотношении f =O(g) любой большей функцией корректна).

Образно говоря, соотношение f (n)=O(nd) показывает, что функ­ция f растет приблизительно как d-я степень аргумента. Напри­мер, если d=3, то оно говорит нам, что удвоение аргумента при­ведет к увеличению функции приблизительно в 8 раз. Соотноше­ние (где означает ) показывает, что функция возрастает приблизительно как d-я степень числа двоичных разрядов в п. Это так, потому что с точностью до мультиплика­тивной константы число бит равно приблизительно logn (а именно, ). Так, например, если , то удвоение числа бит в n (что гораздо сильнее увеличивает аргумент, нежели его удвоение) приводит к увеличению f(n) приблизительно в 8 раз.

Заметим, что запись означает, что функция f огра­ничена некоторой константой.

В общем случае, когда оценивается число двоичных операций, требующихся для решения какой-либо задачи, сначала надо опреде­лить и выписать подробную процедуру решения задачи. Конкретная пошаговая процедура выполнения вычислений называется алгорит­мом. Конечно, может существовать много разных алгоритмов, вы­полняющих одну и ту же работу. Можно воспользоваться тем из них, который попроще в записи, или тем, который быстрее работает, или выбрать какой-то компромисс между простотой и быстродействием. Использованный выше алгоритм умножения n на m далек от самого быстрого из известных. Но вместе с этим он много быстрее метода повторного сложения (m-кратного сложения числа n с собой).

Пример 4. Оценить время, требующееся для перевода числа из k бит в десятичную систему счисления.

Решение. Пусть п - целое из к бит, записанное в двоич­ной системе счисления. Алгоритм перевода следующий. Разделим n на 10 = (1010)₂. Остаток от деления — который является одним из чисел 0, 1, 10, 11, 100, 101, 110, 111, 1000 или 1001 — даст содержи­мое d₀ разряда единиц. Частное от деления возьмем вместо n, поде­лим на (1010)₂и возьмем остаток от этого деления в качестве d_l а частное — в качестве делимого при следующем делении на (1010)₂. Этот процесс должен повторяться столько раз, сколько десятичных разрядов содержится в числе n, т.е. раз. То­гда процесс будет завершен. Как много двоичных операций будет сделано? Мы сделали О (к) делений, каждое из них требовало O(4к) операций (делимое содержит не более к бит, а делитель (1010)₂ - 4 бита). Но О(4к)эквивалентно О(к) (постоянный множитель несуществен в обозначении О-большое). Поэтому общее число двоичных операций равно О(к)× О(к)=O(). Если желатель­но выразить оценку в терминах n, а не k, то, используя равенство , можно записать

Time (перевод n в десятичную систему счисления) = О (log² n).

Теорема (О сравнении операций)

Введем понятия:

M(n)– сложность операции умножения 2-х n разрядных чисел.

D(n)– сложность операции деления с остатком 2n разрядное на n разрядное.

S(n)– сложность операции возведения в квадрат n разрядного числа.

R(n)– сложность операции обращение n разрядного числа(под обратным к n разрядному числу N понимается дробь, полученная из отбрасыванием лишних знаков так, чтобы получилось n разрядное число).

Теорема. Пусть функции сложности удовлетворяют следующим условиям:

a) f (n)≥ n; и b) kf (n)≤ f (kn)

Тогда, если M(n), D(n), S(n), R(n)удовлетворяют а) и б), то M(n)≈ D(n)≈ S(n)≈ R(n).

Доказательство:

1)M(n) S(n), так как в силу тождества справедлива оценка M(n)≤ 3S(n)+4(n),

где 3S(n) - 3 возведения в квадрат, а 4(n)-четыре сложения. M(n) =O (S(n))Делению на два соответствует операция сдвига.

2)S(n) R(n), т.к. в силу равенства получаем оценку: S(n)≤ 3R(n)+2n, где 3R(n) - 3 обращения в квадрат, а 2n - два сложения.

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

3) :

Для доказательства воспользуемся итерационным методом Ньютона для нахождения обратного. Он заключается в вычислении последовательности итераций x(0), x(1), …, x(i), … по формуле: x(i+1)=2x(i)-Nx(i)². Данная последовательность действительно сходиться к , т.к. если x(i)= (1-δ), то

Поэтому при выборе начального значения x(0) так, что < (а это легко сделать по двум значащим разрядам N), мы получаем последовательность, в которой каждый раз число правильно вычисленных знаков после запятой удваивается. Благодаря этому мы можем теперь просто заменить нулями те знаки, которым нельзя доверять при данной итерации, и, постоянно удваивая число правильных знаков, через log n шагов получим нужное количество знаков. Отсюда вытекает оценка: (по лемме1) .

4) : из равенства

5) – очевидно

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

Метод Карацубы для оценки сложности операции умножения.

Суть метода заключается в рекурсивном повторении шага:

Пусть А и В – два n-разрядных числа. Разобьем их на два слагаемых (для простоты считаем, что )

Тогда

Таким образом, для вычисления произведения двух n-разрядных чисел нужно выполнить три умножения n/2-разрядных чисел и некоторое количество сложений, вычитаний и переносов. Поэтому для сложности данного алгоритма умножения справедлива оценка

Откуда по Лемме 2 где

 

Пример: умножим два числа 1101 и 1011 с помощью метода Карацубы.

 

Воспользовавшись тождеством

представим четырехзначные числа A и B в виде

и , где – двузначные числа. Тогда

.

Видно, что достаточно произвести всего три умножения двузначных чисел , , , на каждое из которых затратили не больше четырех элементарных умножений, т.е. всего затратим 12 умножений вместо 16 (и некоторое количество сложений). В данном случае: a₁=11, a₀=1, b₁=10, b₀=11, откуда

1101 × 1011=(10² × 11+1) × (10²× 10+11)=(10⁴+10²)× 11× 10+10²× 10× 1+(10²+1)× 1× 11=1113111

(Н.Коблиц., 2001)

 

Список литературы

А.В.Черемушкин Лекции по арифметическим алгоритмам в криптографии. [Книга]. - Москва: МЦНМО, 2002. - стр. 104.

Н.Коблиц. КУРС ТЕОРИИ ЧИСЕЛ И КРИПТОГРАФИИ. [Книга]. - Москва: Научное изд-во ТВП, 2001. - стр. 254.