Цитата:
доказано ли утверждение, что минимально возможное количество этих операций при вычислении формулы вида

равно

?
Простите, но может кто-нибудь объяснить простому IT'шнику как вообще можно посчитать выражение, содержащее

сложений и

умножений, за число операций меньшее чем

?
Конечно, если числа в выражении подчиняются некоторым априорно известным функциональным зависимостям, то, очевидно, оптимизация возможна. Действительно, пусть все

равны, тогда вынося

за "скобки" достаточно будет произвести лишь

операций (кстати, уже в этом случае получается, что изначальное предположение-теоремка неверна, т.е.

не есть минимально возможная оценка...)
Но также мне абсолютно очевидно, что в этой теме речь идет о чем-то совершенно другом, и мне естественно хотелось бы тоже вникнуть в суть проблемы, особенно учитывая возможную практическую ценность её для меня...

И ещё, в первоначальной версии заголовка темы упоминалась теория графов, но связь с ней почему-то (почти) не обсуждается... Как переформулировать задачу в терминах этой теории? Картинку, приведенную
maxal'ом я что-то не понял. Понял только, что она вроде бы решает или по крайней мере подразумевает задачку экономичного разложения числа на слагаемые, т.е. как бы обратную к исходной (примерно таким способом можно для данного

найти формулу --- суть набор

--- с минимальным

, но по прежнему непонятно как сверхэффективно вычислить формулу по уже имеющимся данным).
В общем, заранее спасибо за ответы...

P.S.: На счет ДПФ. Кажется существуют алгоритмы сложности

. Я как-то курил книжку H.J. Nussbaumer, "Fast Fourier Transform and Convolution Algorithms", вот там такой алгоритм предлагался, основанный на гармоническом анализе.