Оценка сложности арифметических операций

1. Оценка сложности арифметических операций

2.

Асимптотические обозначения
- функция f ограничена сверху
функцией g,
- функция f ограничена снизу
функцией g,
- функции f,g имеют одинаковый
порядок роста, запись

3.

Свойства
;
;
Формула Стирлинга

4.

Примеры
;

5.

Основная лемма.
Если
для
то

6. Сложность арифметических операций над целыми числами

7.

Классификация алгоритмов
1) Полиномиальные алгоритмы
2) Экспоненциальные алгоритмы
3) Субэкспоненциальные алгоритмы

8.

– -длина числа x.
1) Сложность сложения
«столбиком»
и
вычитания
2) Сложность умножения и деления с
остатком «столбиком»

9.

3) Сложность возведения n-разрядного
числа в степень k-разрядного числа
Лемма. Сложность возведения в квадрат
сложность
обращения
чисел
удовлетворяют условиям

10.

Алгоритм Карацубы

11.

Алгоритм Евклида
Вычисление наибольшего общего делителя
целых чисел a и b>0 состоит из следующих
этапов: положим a0 a, a1 b и выполним
деления с остатком ai на ai+1:
a0 a1q1 a2 , 0 a2 a1 ,
a1 a2 q2 a3 , 0 a3 a2 ,
…………………………..
ak 2 ak 1qk 1 ak , 0 ak ak 1 ,
ak 1 ak qk .
ak =НОД(a,b).

12.

Расширенный
алгоритм
Евклида
позволяет не только вычислять наибольший
общий делитель целых чисел a и b>0, но и
представлять его в виде НОД(a,b)=ax+by для
некоторых x,y Z.
Значения x,y находятся в результате
обратного прохода этапов алгоритма Евклида,
в каждом из которых уравнение разрешается
ai ,
относительно
остатка
который
представляется в форме ai axi byi для
некоторых xi,yi Z.

13.

Очевидно, что x 0 1, y 0 0 , x1 0, y1 1 и
выполняются равенства:
ai ai 2 ai 1qi 1 ,
xi xi 2 xi 1qi 1 ,
yi yi 2 yi 1qi 1 .
Отсюда последовательно получаются искомые
представления для всех ai и, в частности,
представление НОД(a,b)= ak = axk by k .