Предположим, удалось установить, что любое число можно возвести в квадрат за O(n), где n – длина числа в двоичной записи. Докажите, что тогда любые два числа можно перемножать за O(n), где n – длина максимального из чисел в двоичной записи

задан 3 Мар 3:31

Находим (a+b)^2 и (a-b)^2 за линейное время. Берём разность. Это тоже требует линейного времени (для 2n-значных чисел). Получаем 4ab. Два раза делим на 2 -- это легко сделать за линейное время. Итого O(n).

(3 Мар 4:06) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×240
×154
×72

задан
3 Мар 3:31

показан
149 раз

обновлен
3 Мар 4:06

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru