|
Рассмотрим алгоритм быстрого умножения двух двоичных чисел методом Карацубы. Получим рекуррентность для оценки полного числа всех элементарных битовых арифметических операций алгоритма Карацубы. Обозначим $%Add(m)$% - число элементарных битовых арифметических операций, требуемых для сложения двух $%m$%-битовых чисел, $%Mul(m)$% - число элементарных битовых арифметических операций, требуемых для умножения двух $%m$%-битовых чисел методом Карацубы. Соотношение между $%Add(.)$% и $%Mul(.)$% (следует из алгоритма): $%Mul(2m) \le 3Mul(m+1) + O(Add(m))$%. Сложение в столбик дает оценку $%Add(m) = O(m)$%. Тогда получаем рекуррентность: задан 20 Мар '16 20:10 
Uchenitsa
показано 5 из 6
показать еще 1
|
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
20 Мар '16 20:10
показан
593 раза
обновлен
20 Мар '16 23:16
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
@Uchenitsa: мне кажется, здесь нужно уточнить условие. Если всё воспринимать буквально, то верхняя оценка даётся только для членов последовательности с чётными номерами. Тогда члены с нечётными номерами могут быть сколь угодно велики. Если подразумевается монотонность оценки, то есть $%T(2m+1)\le T(2m)$%, тогда что-то оценить становится возможно.
@falcao, прошу прощения за неточность. Условие исправлено. Дело в том, что эта рекуррентность - есть оценка сложности работы алгоритма Карацубы
@Uchenitsa: если так, то монотонность вытекает из общих соображений. Только я не то неравенство написал: имелось в виду, что $%T(2m-1)\le T(2m)$%. Как я понимаю, нужно доказать справедливость подходящей степенной оценки типа $%O(n^{\log_23})$%.
@falcao, да, все верно
@Uchenitsa: выход здесь достаточно простой. Чтобы не мешало +1, нужно рассмотреть сдвиг функции. А именно, оценивать S(n)=T(n+2) через рекуррентную формулу. Ясно, что асимптотика будет та же ввиду того, что (n+2)^c эквивалентно n^c.
@falcao, спасибо!