はインクリメント

Question

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

を変えてループの反復の数を計算ループ構造を使用することなくiとxを計算するエレガントな解決策がありますか？

私の考え：

私はOにO（N）からの複雑さを軽減するために人気のガウス総和式1+2+3+4+...+n = (n*(n+1))/2とバイナリ検索を使用することができます（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の数を発見したことを、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 < limit 
= i+x*n+(n*(n+1))/2*d < limit 
= d*n^2 + (2*x-d)*n - 2*(limit-i) < 0 

上記式は次不等式であり、quadratic formula用いて解くことができる：i = i+x*n+((n-1)*n)/2*d従って今解決することができる（上記参照）

(-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ループの数はnです。つの式を使用してとx（上記参照）：

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

Iは、単純なCプログラムを使用してこれらの式をテストし、それはしばらく（のための）ループと同じ結果を与えます。

Answer 1

これは2次の不等式です。したがって、O（1）で平方根を計算できる場合は、O（1）でそれを解くことができます。関与する番号のタイプによっては、可能かもしれないし、そうでないかもしれない。

最初にi >= limitの場合、反復はほとんどありません。n = 0だから、最初にi < limitと仮定して、それぞれのステップでという固定量で増分されたと仮定しよう。

あなたが解決したい不等式はその後、標準的な方法により

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

解決には、そのプロパティを持つ最小のn > 0が

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

のすべての場合である

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

が得られています量は適切な精度でdouble秒、それはO（1）計算です。しかし、量のいずれかが大きい場合、浮動小数点計算が少しずれている可能性があります。その後、調整する必要があります。適度な量の場合、1ステップで十分です。

しかし、すべての量が適度な大きさであれば、バイナリ検索は事実上O（1）である - 対数はかなり制限されており、それよりかなり速いかもしれない。