嵌套循环优化

Question

我有这样的表情

for (size_t i = 0; i < expression.size(); i++){
    for (size_t j = i + 1; j < expression.size(); j++){
        result += (expression.at(j) - expression.at(i));
    }
    result += (g - expression.at(i));
}
return result;

在向量表达式中，例如，1,2,3。我试图得到如下内容：

f1=[(2-1)+(3-1)]
r1 = g-1
h1 = r1+f1

f2=[3-2]
r2 = g-2
h2 = r2+f2

f3 = 0
r3 = g-3
h3 = r3+f3

then h1+h2+h3

我现在正在做的是Θ(n^2)。有没有办法让它更快，即使没有循环？

Answer 1

加法是可交换的和结合的，因此可以在不改变最终结果的情况下重新排序和分组运算。(注:未考虑到中间计算中可能出现的溢出，这可能受到操作顺序和分组的影响。)

在使用n = expression.size()和x[k] = expression.at(k)的伪代码中，原始代码可以按以下方式细分，中间结果在注释中显示。

a = b = c = d = 0

for i = 0 to (n-1)
    for j = (i+1) to (n-1)
        a += x[j]
    // == x[i+1] + x[i+2] + ... x[n-1]
// a == 0 * x[0] + 1 * x[1] + 2 * x[2] + 3 * x[3] + ... + (n-1) * x[n-1]

for i = 0 to (n-1)
    for j = (i+1) to (n-1)
        b += x[i];
    // == (n-i-1) * x[i]
// b == (n-1) * x[0] + (n-2) * x[1] + ... + 2 * x[n-3] + 1 * x[n-2]

for i = 0 to (n-1)
    c += g
// c == n * g

for i = 0 to (n-1)
    d += expression.at(i))
// d == x[0] + x[1] + ... + x[n-1]

result = c     + a      - b     - d
       = n * g
               + (0     - (n-1) - 1) * x[0]
               + (1     - (n-2) - 1) * x[1]
               + ...
               + ((n-2) - 1     - 1) * x[n-2]
               + ((n-1) - 0     - 1) * x[n-1]

后一个result可以直接根据该公式计算，只需一个O(n)循环。