algorithm - 优化算术表达式计算的算法

Question

假设我有一个由整数变量和算术运算组成的表达式：加法、减法和乘法。我知道每次乘法需要 M 秒，每次加法/减法需要 A 秒。是否有一种算法可以以最有效的方式计算表达式，以对变量进行任意赋值？（假设我只能在内存中存储一个数字）。

例子：

M=10

A=1

表达式：a*a+a*b+b*b。

最初有3次乘法和2次加法，所以总时间为3*M+2*A=32

但是，我们可以构建一个等价的表达式 (a+b)*(a+b)-a*b，它只有 2 次乘法和 3 次加法，因此总计算时间为 2*M+3*A=23。

score 1 · Accepted Answer

1

您想应用 sum product 算法。

看：

于 2013-09-04T00:35:34.320 回答

score 1 · Accepted Answer

你基本上想减少乘法的次数。一种方法如下（我不知道由此产生的成本降低是否可以证明算法的复杂性和成本是合理的）：

根据运算符优先级对允许添加的所有操作数执行添加。
形成必须进行乘法运算的操作数对。
在这些对中，取出共同的操作数并将它们的对应物相加。
更新对并转到第 3 步。
当没有这样的公共对时停止。然后只做剩下的计算。

例如：a*b + a*c + d*(e+f) 对 e & f 执行加法（比如 g = e + f）a*b + a*c + d*g 对：(a,b) ( a,c) (d,g) a 在第一对两对中很常见，所以我们添加 b 和 c。

2 回答 2