1
1

Рассмотрим алгоритм быстрого умножения двух двоичных чисел методом Карацубы. Получим рекуррентность для оценки полного числа всех элементарных битовых арифметических операций алгоритма Карацубы. Обозначим $%Add(m)$% - число элементарных битовых арифметических операций, требуемых для сложения двух $%m$%-битовых чисел, $%Mul(m)$% - число элементарных битовых арифметических операций, требуемых для умножения двух $%m$%-битовых чисел методом Карацубы. Соотношение между $%Add(.)$% и $%Mul(.)$% (следует из алгоритма): $%Mul(2m) \le 3Mul(m+1) + O(Add(m))$%. Сложение в столбик дает оценку $%Add(m) = O(m)$%. Тогда получаем рекуррентность:
$%T(2m)\le 3T(m+1)+O(m)$%
Требуется привести асимптотический анализ рекуррентности (сложность в том, как показать, что во втором члене можно пренебречь прибавлением 1)

задан 20 Мар '16 20:10

изменен 20 Мар '16 20:57

@Uchenitsa: мне кажется, здесь нужно уточнить условие. Если всё воспринимать буквально, то верхняя оценка даётся только для членов последовательности с чётными номерами. Тогда члены с нечётными номерами могут быть сколь угодно велики. Если подразумевается монотонность оценки, то есть $%T(2m+1)\le T(2m)$%, тогда что-то оценить становится возможно.

(20 Мар '16 20:18) falcao

@falcao, прошу прощения за неточность. Условие исправлено. Дело в том, что эта рекуррентность - есть оценка сложности работы алгоритма Карацубы

(20 Мар '16 20:59) Uchenitsa

@Uchenitsa: если так, то монотонность вытекает из общих соображений. Только я не то неравенство написал: имелось в виду, что $%T(2m-1)\le T(2m)$%. Как я понимаю, нужно доказать справедливость подходящей степенной оценки типа $%O(n^{\log_23})$%.

(20 Мар '16 21:18) falcao

@falcao, да, все верно

(20 Мар '16 21:38) Uchenitsa

@Uchenitsa: выход здесь достаточно простой. Чтобы не мешало +1, нужно рассмотреть сдвиг функции. А именно, оценивать S(n)=T(n+2) через рекуррентную формулу. Ясно, что асимптотика будет та же ввиду того, что (n+2)^c эквивалентно n^c.

(20 Мар '16 23:14) falcao

@falcao, спасибо!

(20 Мар '16 23:16) Uchenitsa
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось

Вопрос был закрыт. Причина - "Вопрос отвечен и ответ принят". Закрывший - Uchenitsa 25 Мар '16 1:03

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

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

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

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

отмечен:

×154
×72
×63
×48
×21

задан
20 Мар '16 20:10

показан
523 раза

обновлен
20 Мар '16 23:16

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

по почте:

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

по RSS:

Ответы

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

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