ГДЗ по информатике, 11 класс, Босова, номер 5.13: Основные сведения об алгоритмах
Информатика — Босова Л.Л., Босова А.Ю.
Павел Лебедев, методист по информатике Шпаргача обновлено 8 сентября 2026
Условие
Подсчитайте сложность алгоритма умножения «столбиком» двух натуральных чисел: одно состоит из n цифр, другое — из m цифр.
Номер как в учебнике. Условие — полный пересказ редакции: те же пункты, числа и факты, не цитата из книги.
Пошаговое решение
Для определения сложности алгоритма умножения «столбиком» необходимо проанализировать количество элементарных операций (сложение и умножение одноразрядных чисел), выполняемых при перемножении двух натуральных чисел.
Рассмотрим процесс по шагам. Пусть первое число имеет n цифр, а второе — m цифр. В классическом методе умножения мы берём каждую цифру второго числа и умножаем её на всё первое число. Это действие повторяется для каждой из m цифр второго множителя.
При умножении одной цифры второго числа на n-значное первое число выполняется n операций умножения одноразрядных чисел. Кроме того, в процессе сложения промежуточных результатов также происходит ряд операций сложения, но их порядок совпадает с порядком операций умножения. Таким образом, для одного столбца промежуточного произведения требуется порядка n элементарных действий.
Так как таких столбцов всего m, то общее количество элементарных операций пропорционально произведению количества цифр обоих множителей:
T(n,m)≈n·mВ терминах асимптотической сложности это записывается как O(n·m). Если считать, что оба числа имеют одинаковую длину (n=m), то сложность будет равна O(n2).
O(n·m)
Алгоритм школьного умножения требует выполнения n умножений для каждой из m цифр второго множителя, что даёт общее число операций порядка n×m.
Как решение?
Двойная оценка: понятность и подробность. Можно выбрать одно или оба.
У вас другое условие?
Загрузите фото — учтём ваши числа и редакцию.
Частые вопросы
Это точный номер 5.13 из моего учебника?
Номер совпадает с учебником «Информатика», Босова Л.Л., Босова А.Ю.. Формулировка — пересказ редакции, не дословная цитата. Если в вашей редакции другие числа — загрузите фото.
Какой ответ в задании 5.13?
Краткий ответ: O(n · m).
Как пользоваться этим разбором?
Сначала прочитайте условие и чертёж, затем шаги решения по порядку и сверьте свой ход с кратким ответом внизу.
Какой учебник имеется в виду?
«Информатика», Босова Л.Л., Босова А.Ю.. Проверьте часть, год и автора на обложке. Тема в учебнике: § 5. Основные сведения об алгоритмах.
Можно ли списать ответ без решения?
Лучше сначала решить самостоятельно, а разбор использовать для проверки хода и поиска ошибки.