Карондеев
.pdfСложность арифметических операций с целыми числами
Карондеев А.М.
ИУ8-104
1
Сложность алгоритма
Элементарные операции
Вес элементарных операций
Требуемый размер памяти
2
Сложность алгоритма
Элементарные операции
Временная
сложность
Вес элементарных операций
Требуемый размер памяти |
Пространственная |
|
сложность |
||
|
3
Алгебраическая сложность алгоритма
Определена одна операция
Вес операции равен 1 и не
зависит от значений операндов
Число дополнительных
величин заданного типа
4
Битовая сложность алгоритма
Битовые операции
Вес любой битвой операции 1
Требуемое число
дополнительных бит памяти
5
Сложение
Битовая сложность
•O(n)
•Существенно зависит от всех битов входа => асимптотически лучше нельзя
6
Вычитание
Битовая сложность
•O(n)
•Сложение с отрицательный числом
7
Умножение
Битовая сложность
• Mn = ?
8
Умножение столбиком
Битовая сложность
• Mn = O(n2)
9
Метод Карацубы
Деление пополам
10