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

ダニエルの答えの助けを借りて、反復回数を計算し、次に O(1) ステップで計算する方法を次にn示します。（上記を参照）したがって、次を解決できます。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

上記の式は 2 次不等式であり、次の2 次式を使用して解くことができます。

(-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) ループの反復回数がわかったので、次の 2 つの式を使用して計算できます (上記を参照) 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と仮定しましょう。xd

解決したい不等式は、

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

すべての量が s として適切な精度で表現できる場合double、それは O(1) 計算です。ただし、いずれかの量が大きい場合、浮動小数点の計算が少しずれている可能性があります。その後、調整する必要があります。適度な量の場合は、1 ステップで十分です。

しかし、すべての量が適度な大きさであれば、二分探索も実質的に O(1) になり、対数は制限され、かなり小さくなり、より高速になる可能性があります。

于 2012-05-09T23:08:59.503 に答える