4 
for (; i < limit; i += x) {
  x += 100;
}

是否有一个优雅的解决方案来计算i而不x使用循环结构？

我的想法：

我可以使用流行的高斯求和公式1+2+3+4+...+n = (n*(n+1))/2和二分搜索将复杂度从 O(N) 降低到 O(log N)。

Assume i = 0, x = 0 then:
i = 0*100 + 1*100 + 2*100 + 3*100 + ... + (n-1)*100 = ((n-1)*n)/2*100

if (i != 0 && x != 0) then:
i = i + x+0*100 + x+1*100 + x+2*100 + ... + x+(n-1)*100 = i+x*n + ((n-1)*n)/2*100

Thus (i < limit) = (i+x*n+((n-1)*n)/2*100 < limit)

现在使用某种二进制搜索来找到n满足上述不等式的最大值。

if (i < limit)
    for (n = 1; i+x*n+((n-1)*n)/2*100 < limit; n -= j, n += 1)
        for (j = 1; i+x*n+((n-1)*n)/2*100 < limit; n += j, j += j);

现在我找到了n初始 for 循环的迭代次数，i可以x使用以下方法计算：

i += x*n+((n-1)*n)/2*100
x += 100*n

有什么建议么？有更快的 O(1) 解决方案吗？

O(1) 解决方案：

const int d = 100;
while (i < limit) { i += x; x += d; }

在 Daniel 的回答的帮助下，这里是如何计算迭代次数，n然后在 O(1) 步骤中计算。（见上文）因此我们现在可以解决：ixi = i+x*n+((n-1)*n)/2*d

i < limit
= i+x*n+(n*(n+1))/2*d < limit
= d*n^2 + (2*x-d)*n - 2*(limit-i) < 0

上面的公式是一个二次不等式，可以使用二次公式求解：

(-b ± (b^2-4ac)^0.5) / 2a

因此迭代次数n为：

a = d
b = 2*x-d
c = -2*(limit-i)
n = ceil((-b + sqrt(b*b-4*a*c)) / (2*a))

现在我们找到了n初始 while (for) 循环的迭代次数，我们可以计算i并x使用两个公式（见上文）：

i += x*n+((n-1)*n)/2*d
x += d*n

我使用一个简单的 C 程序测试了这些公式，它们给出了与 while (for) 循环相同的结果。

4

1 回答 1

2

这是一个二次不等式，因此如果您可以在 O(1) 中计算平方根，则可以在 O(1) 中解决它。根据所涉及号码的类型，这可能是可能的，也可能是不可能的。

如果i >= limit一开始，您很容易没有迭代，n = 0. 所以让我们假设i < limit在开始时，我们假设它在每一步x中增加一个固定的正数。d

你要解决的不等式是

n*(n+1)*d/2 + n*x >= limit - i

通过标准方法求解得到

n >= sqrt( (1/2 + x/d)^2 + 2*(limit - i)/d ) - (1/2 + x/d)

n > 0具有该属性的最小的是

ceiling( sqrt( (1/2 + x/d)^2 + 2*(limit - i)/d ) - (1/2 + x/d) )

如果所有的量都可以以足够的精度表示为doubles，那就是 O(1) 计算。但是，如果任何数量很大，则浮点计算可能会有些偏差。那你就得调整了。对于中等大小的数量，一步就足够了。

但是，如果所有数量的大小都适中，那么二进制搜索实际上也是 O(1) - 对数是有界的并且相当小 - 并且可能会更快。

于 2012-05-09T23:08:59.503 回答