0

我写了下面的代码大纲，基本上是对一个数组 (a) 求和，其中每个元素都乘以一个值 x^i：

y = a(0)
i = 0
{y = sum from i=0 to (n-1) a(i) * x^i AND 0 <= n <= a.length} //Invariant

while (i < (n-1))
{y = sum from i=0 to (n-1) a(i) * x^i AND 0 <= n <= a.length AND i < (n-1)}
y = y + a(i)*x^i
i = i + 1
end while

{y = sum from i=0 to (n-1) a(i) * x^i} //Postcondition

请注意，我不希望代码编译 - 它只是代码应该如何工作的合理概述。我需要通过使用跟踪变量来提高代码的效率，因此需要使用链接不变量将所述变量与代码的其余部分连接起来。这就是我卡住的地方。在这种情况下跟踪什么有用？我曾考虑在每次迭代中保留总和值，但我不确定这是否有效。如果我能弄清楚要跟踪什么，我很确定将它链接到空间将是微不足道的。谁能看到我的算法如何通过跟踪变量得到改进？

4

2 回答 2

1

您的不变逻辑存在非 1 问题。这是跟踪部分电源操作的更正版本。

// Precondition: 1 <= n <= a.length

// Invariant:
{ 0 <= i < n AND xi = x^i AND y = sum(j = 0..i) . a(j) * x^j }

// Establish invariant at i = 0:
//   xi = x^0 = 1 AND y = sum(j=0..0) . a(j) * x^j = a(0) * x^0 = a(0) 
i = 0;   
xi = 1; 
y = a(0);

while (i < n - 1) {

  i = i + 1;            // Break the invariant
  xi = xi * x;          // Re-establish it
  y = y + a(i) * xi 
}

// Invariant was last established at i = n-1, so we have post condition:
{ y = sum(j = 0..n-1) . a(j) * x^j }

计算多项式的更常见和数值稳定的方法是使用霍纳规则

y = 0
for i = n-1 downto 0 do y = y * x + a(i)
于 2014-10-01T03:30:53.803 回答
0

所以看起来你正试图结束这个：

(a(0)*x^0) + (a(1)*x^1) + ... + (a(n-1)*x^(n-1))

那正确吗？

我认为提高性能的唯一方法是^操作成本高于*操作成本。在这种情况下，您可以随时跟踪x^n变量，x并在每次迭代中乘以该值。

事实上，在这种情况下，您可能会从数组的末尾开始并向后工作，x每次乘以，以产生：

(((...((a(n-1)*x+a(n-2))*x+...)+a(2))*x+a(1))*x)+a(0)

理论上这会比每次重新计算 x^i 稍微快一点，但它不会在算法上更快。它可能不会快一个数量级。

于 2014-09-30T22:49:31.313 回答