Разделяй и властвуй. Повышение эффективности алгоритмов. Часть 3

В прошлой части мы рассмотрели общий подход к расчету эффективности алгоритмов с принципом "разделяй и властвуй", а также применение принципа к различным базовым алгоритмам.
Сегодня поговорим о следующем приеме. Как известно, составная часть принципа, это поделить задачу на подзадачи. Мы ни разу не касались, как именно делить. Просто делили на равные части. Но тут вот и есть нюанс, если поделить не абы как, а используя какую-то стратегию, то можно добиться применения принципа там, где это даже не очевидно. И именно эта тема станет предметом данной статьи на примере задачи умножения полиномов.
Как и в предыдущих частях, я упрощаю математическую часть, опуская различные нюансы и частные случаи, с целью сохранить научно-популярный характер публикации. При этом я пытаюсь сохранить основные элементы алгоритмов и математических основ. Я хочу подать информацию в кратком доступном виде, в виде математического пересказа, и если у кого-либо возникнет интерес, тот может легко найти полные и строгие математические выкладки по данной теме.

Читать далее