Задание 13 Параграф 5 ГДЗ Босова 11 класс (Информатика)

Подсчитайте сложность алгоритма перемножения двух натуральных чисел «столбиком» при условии, что одно из них состоит из $$n$$, а второе — из $$m$$ десятичных цифр.

При умножении двух чисел столбиком каждая цифра одного числа умножается на каждую цифру другого числа. Если одно число состоит из $$n$$ цифр, а другое — из $$m$$ цифр, то всего выполняется $$n \cdot m$$ умножений.

Следовательно, сложность алгоритма пропорциональна произведению числа цифр:

$$O(n \cdot m)$$

Ответ

$$O(n \cdot m)$$