algorithm - 计算不同增量的循环迭代次数

Question

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);

现在我找到了初始 for 循环的迭代次数 n，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; }

这里借助大牛的回答是如何在O(1)中计算n然后i和x的迭代次数脚步。 i = 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

上面的公式是一个二次不等式，可以用 quadratic formula 求解:

(-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))

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

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

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

Answer 1

这是一个二次不等式，因此如果您可以在 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) )

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

但如果所有数量的大小都适中，则二分查找实际上也是 O(1) - 对数是有界的并且相当小 - 并且可能更快。