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
示します。(上記を参照)したがって、次を解決できます。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
上記の式は 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) ループと同じ結果が得られました。