Задача
В каком-то смысле задача умножения двух целых чисел настолько фундаменталь- на, что на первый взгляд может показаться, что это вообще не алгоритмический вопрос.
Но в действительности на уроках математики в младших классах объяс- няют конкретный (и довольно эффективный) алгоритм умножения двух целых чисел X и у, каждое из которых состоит из n цифр. Сначала вычисляется «частичное произведение», для чего каждая цифра у отдельно умножается на х, а полученные частичные произведения суммируются. (Рисунок 5.8 поможет вам вспомнить этот алгоритм. В начальной школе умножение всегда выполняется в десятичной систе- ме, но по основанию 2 оно работает точно так же.) Если взять отдельную операцию с парой битов за один шаг в этом вычислении, для вычисления каждого частичного произведения потребуется время O(n), а также время O(n) для объединения его с накапливаемой суммой всех частичных произведений. С n частичными суммами общее время выполнения составляет O(n2).Если вы особенно не задумывались над этим алгоритмом с начальной школы, перспективы его улучшения на первый взгляд кажутся сомнительными. Разве все эти частичные произведения не являются в каком-то смысле необходимыми? Но оказывается, время O(n2) можно улучшить при использовании другого, рекурсив- ного способа выполнения умножения.
Источник:
Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016
Еще по теме Задача:
- ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
- 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
- Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
- ЗАДАЧА
- ЗАДАЧА: РЕШЕНИЕ
- Основные задачи.
- в) Задачи
- в) Задачи
- ПСИХОАНАЛИЗ: ЗАДАЧА
- ЗАДАЧА ДВИГАТЕЛЬНАЯ
- Основные задачи
- Правило решаемой психологической задачи.
- Задачи и упражнения
- Терапевтическая задача
- 3. Задачи и функции социологии
-
Windows -
Архитектура компьютера -
Интернет -
Информатика -
Компьютер -
Компьютерные и телекоммуникационные системы -
Программирование -
Социальные сети -
-
Английский язык -
Астрология -
Астрономия -
Биология -
Военная литература -
Журналистика -
Компьютерная инженерия -
Педагогика -
Право -
Психология -
Социология -
Lecture.Center